Mirror Theory and its Applications in Cryptography

Abstract

The indistinguishability security of a cryptographic construction refers to the maximum advantage of an interactive adversary to distinguish between the real and ideal world, where in the real world it interacts with the construction, and in the ideal world it interacts with its idealized counterpart. In the field of information-theoretic provable security, we bound this indistinguishability advantage by the statistical distance between the random variables representing the transcript of interaction in the real and ideal worlds, respectively. One of the most popular techniques in bounding the statistical distance is the H-Coefficient Technique introduced by J. Patarin, for which a set of transcripts is identified as good, and the probability of realizing such a good transcript in the real world is lower-bounded. For numerous constructions in practice, lower-bounding this real-world interpolation probability reduces to lower-bounding the number of solutions to a system of equations and non-equations over a field. The theory of achieving optimum lower bounds to a system of equations and non-equations is termed Mirror Theory by J. Patarin. Although several Mirror Theory statements have been conjectured and profusely used in beyond-birthday bound analysis of a multitude of constructions, the proofs of such statements are either non-existent or at least have significant non-verifiable gaps.

In this thesis, we have presented the first simple verifiable proofs of several variants of Mirror Theory and applied them to security analyses of various cryptographic schemes.

As our first contribution, we proved that the number of pairwise disjoint solutions to a system of bivariate equations over n-bit variables, such that no two equations share any common variable, is at least the average number of such solutions. This translates via the H-coefficient technique to the n-bit security for the sum of permutations PRF constructions.

As our second contribution, we show that the number of pairwise disjoint solutions to a system of bivariate equations over n-bit variables, which even has quite a large block-maximality, is at least the average number of such solutions. Here block-maximality of a system of equations refers to the maximum number of variables that get determined when one variable is assigned a particular value. Note that, in our previous simpler result the block-maximality was just two. This translates via the H-coefficient technique to the n-bit security for several PRF constructions, like XORP[w], 2k-HtmB-p2, and the PRP construction, six-round Feistel network.

As our third contribution, we have used a Mirror Theory statement in the tweakable permutation setting, where the variables are partitioned into two sets and solutions need to be pairwise disjoint within the two sets only, to prove 3n/4-bit security of the tweakable blockcipher construction paradigm, LRW+, proposed by us, that includes as subcases the CLRW2 and 4LRW1 constructions proposed in the seminal paper of Liskov, Rivest, and Wagner. The LRW+ paradigm was proposed to achieve beyond-birthday-bound security, as we have given a birthday-bound attack on the TNT or 3LRW1 construction, disproving the long-held belief that the latter is beyond-birthday-bound tweakable blockcipher.

Finally, as our fourth contribution, we have given a lower bound to the number of solutions (which are pairwise disjoint within a partition of the variables) to a system of equations (need not be bivariate) where the solutions are not allowed to take values in certain forbidden sets. We have used this variant of Mirror Theory to prove optimal 3n/4-security of single key variants of double-block-hash-then-sum MAC constructions, like 1k-LightMAC+, 1k-PMAC+, and the PRF construction, sum of k Even-Mansour.

Several of the security proofs mentioned above are indeed tight.