# Unconditionally secure block cipher for a finite number of blocks

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.

• We don't assume unconditional proof of security on modern cryptography. We require that the schemes must resist any attack of the probabilistic polynomial-time adversaries where the advantage of the adversary must be negligible. Or are you using a different meaning for those 3 words? Dec 16 '20 at 21:35
• @kelalaka I do mean unconditional proof of security, I suppose this is more of a theoretical question than a practical one.
– GEG
Dec 16 '20 at 21:36
• If there is no condition then the attacker already breaks the AES, however, there is unconditional secure QKD. Dec 16 '20 at 21:38
• @kelalaka I do mean a classical implementation as well. Would existence of such a system prove $P \not= NP$? This seems to be where this is going.
– GEG
Dec 16 '20 at 21:40

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.
• I apologize for the naive question, but how does this not prove $P \not=NP$? If I understand you correctly such a scheme allows you to encrypt more bits than required by the key with perfect information-theoretic security, and the proof of security is not conditioned on any unproven assumptions?
• You don't encrypt more bits than required by the key; here the key comprises the polynomial coefficients for your $4$ Luby-Rackoff functions. Each polynomial requires $hn/2$ bits, muktiplied by $4$ results in $2hn$ key bits. You can only encrypt $h$ blocks of $2n$ bits each, for a total of also $2hn$ bits. In the case of the single polynomial function, you need degree $4h$, not $h$, since you evaluate the polynomial $4$ times per blockcipher call. That was my mistake. Dec 17 '20 at 2:19