Paper 2022/686

Proof of Mirror Theory for a Wide Range of $\xi_{\max}$

Benoît Cogliati, Thales DIS France SAS, Meudon, France
Avijit Dutta, Institute for Advancing Intelligence, TCG-CREST, Kolkata, India
Mridul Nandi, Indian Statistical Institute, Kolkata, India, Institute for Advancing Intelligence, TCG-CREST, Kolkata, India
Jacques Patarin, Laboratoire de Mathématiques de Versailles, Versailles, France, Thales DIS France SAS, Meudon, France
Abishanka Saha, Indian Statistical Institute, Kolkata, India

In CRYPTO'03, Patarin conjectured a lower bound on the number of distinct solutions $(P_1, \ldots, P_{q}) \in (\{0, 1\}^{n})^{q}$ satisfying a system of equations of the form $X_i \oplus X_j = \lambda_{i,j}$ such that $P_1, P_2, \ldots$, $P_{q}$ are pairwise distinct. This result is known as \emph{``$P_i \oplus P_j$ Theorem for any $\xi_{\max}$''} or alternatively as \emph{Mirror Theory for general $\xi_{\max}$}, which was later proved by Patarin in ICISC'05. Mirror theory for general $\xi_{\max}$ stands as a powerful tool to provide a high-security guarantee for many blockcipher-(or even ideal permutation-) based designs. Unfortunately, the proof of the result contains gaps that are non-trivial to fix. In this work, we present the first complete proof of the $P_i \oplus P_j$ theorem for a wide range of $\xi_{\max}$, typically up to order $O(2^{n/4}/\sqrt{n})$. Furthermore, our proof approach is made simpler by using a new type of equation, dubbed link-deletion equation, that roughly corresponds to half of the so-called orange equations from earlier works. As an illustration of our result, we also revisit the security proofs of two optimally secure blockcipher-based pseudorandom functions, and $n$-bit security proof for six round Feistel cipher, and provide updated security bounds.

Available format(s)
Secret-key cryptography
Publication info
Mirror theorySum of PermutationsPRPPRFH-Coefficient Technique
Contact author(s)
benoit cogliati @ gmail com
avirocks dutta13 @ gmail com
mridul nandi @ gmail com
jpatarin @ club-internet fr
sahaa 1993 @ gmail com
2023-02-23: last of 4 revisions
2022-05-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benoît Cogliati and Avijit Dutta and Mridul Nandi and Jacques Patarin and Abishanka Saha},
      title = {Proof of Mirror Theory for a Wide Range of  $\xi_{\max}$},
      howpublished = {Cryptology ePrint Archive, Paper 2022/686},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.