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.

  • $\begingroup$ 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? $\endgroup$
    – kelalaka
    Dec 16 '20 at 21:35
  • $\begingroup$ @kelalaka I do mean unconditional proof of security, I suppose this is more of a theoretical question than a practical one. $\endgroup$
    – GEG
    Dec 16 '20 at 21:36
  • $\begingroup$ If there is no condition then the attacker already breaks the AES, however, there is unconditional secure QKD. $\endgroup$
    – kelalaka
    Dec 16 '20 at 21:38
  • $\begingroup$ @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. $\endgroup$
    – 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.

  • $\begingroup$ 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? $\endgroup$
    – GEG
    Dec 17 '20 at 1:27
  • $\begingroup$ 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. $\endgroup$ Dec 17 '20 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.