Paper 2020/669

Proof of Mirror Theory for $\xi_{\max}=2$

Avijit Dutta, Mridul Nandi, and Abishanka Saha


In ICISC-05, and in the ePrint $2010/287$, Patarin claimed a lower bound on the number of $2q$ 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 as {\em Mirror theory} and 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.

Note: This version of the paper greatly simplifies the proof over its earlier version with a simplified notations and terminologies.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. IEEE Transactions on Information Theory
Mirror TheorySum of PermutationPRPPRFH-Technique
Contact author(s)
sahaa 1993 @ gmail com
mridul nandi @ gmail com
avirocks dutta13 @ gmail com
2022-04-28: last of 2 revisions
2020-06-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Avijit Dutta and Mridul Nandi and Abishanka Saha},
      title = {Proof of Mirror Theory for $\xi_{\max}=2$},
      howpublished = {Cryptology ePrint Archive, Paper 2020/669},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.