Unconditionally secure block cipher for a finite number of blocks

Question

I am wondering if someone can point me toward a block cipher that provides unconditional security for only a bounded number of encryptions.  For example, you can encrypt $h > 1$ length $n>1$ blocks with unconditional proof of security, but encrypting more than $h$ blocks will break the security of the whole system (or perhaps it can continue to remain secure, this matters less).
Does such a block cipher exist, and if so can you point me toward the relevant literature or implementations?  In particular, I am assuming that if the secret key can be represented with $d$ bits, then $hn > d$, so the cipher can encrypt more bits (with unconditional security) than was required for storing the key.

Samuel Neves · Accepted Answer

The PEANUT and WALNUT ciphers are an example of this (see also Vaudenay's decorrelation theory for the theory behind these ciphers). The idea is simple: take a provably secure construction, like the Luby-Rackoff scheme, and instantiate it with random functions that are identical to random up to $h$ invocations.
For example, if your block cipher works on $n=128$-bit blocks, it is easy to come up with a $64$-bit random function that is indistinguishable from random up to $h$ evaluations: a random polynomial of degree $h-1$ over $mathbb{F}_{2^{64}}$. It takes $hn/2$ bits to represent such a polynomial. You cannot do better than this and remain information-theoretically secure.
Since with Luby-Rackoff you need $4$ rounds with an independent random function each, you need $4$ random polynomials as above to obtain a cipher that has an unconditional attack advantage bound
$$
mathbf{Adv}^{mathrm{sprp}}_E(q) le frac{q^2}{2^{64}} + frac{q^2}{2^{128}},,
$$
provided the number of queries $q$ stays under the maximum $h$. Security completely breaks down after $h+1$ queries.
With some extra complications you can reduce this to a single random degree-$4h$ polynomial and $4$ Luby-Rackoff rounds.

Unconditionally secure block cipher for a finite number of blocks

One Answer

Add your own answers!

Ask a Question