Proof of Mirror Theory for ξ max = 2
Avijit Dutta, Mridul Nandi, Abishanka Saha · IEEE Transactions on Information Theory · 2022
In ICISC-05, and in the ePrint 2010/287, Patarin claimed a lower bound on the number of$2 q$tuples of$n$-bit strings$(P_{1}, \ldots, P_{2q}) \in ({\{0,1\}}^{n})^{2q}$satisfying$P_{2i - 1} \oplus P_{2i} = \lambda _{i}$for$1 \leq i \leq q$such that$P_{1}, P_{2}, \ldots $,$P_{2q}$are distinct and$\lambda _{i} \in {\{0,1\}} ^{n} \setminus \{0^{n}\}$. This result is known asMirror theoryand widely used in cryptography. It stands as a powerful tool to provide a high-security guarantee for many block cipher-(or even ideal permutation-) based designs. In particular, Mirror theory has a direct application in the security of XOR of block ciphers. Unfortunately, the proof of Mirror theory contains some unverifiable gaps and several mistakes. This paper provides a simple and verifiable proof of Mirror theory.