Paper 2022/686

Proof of Mirror Theory for any $\xi_{\max}$

Benoît Cogliati, CISPA Helmholtz Center for Information Security, Saabrücken, Germany
Avijit Dutta, Institute for Advancing Intelligence, TCG-CREST, Kolkata, India
Mridul Nandi, Indian Statistical Institute, 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 $X_1, X_2, \ldots$, $X_{q}$ are pairwise distinct is either 0 or greater than the average over all $\lambda_{i,j}$ values in $\{0,1\}^n$. This result is known as ``$P_i \oplus P_j$ for any $\xi_{\max}$'' or alternatively as 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 block cipher-(or even ideal permutation-) based designs. Unfortunately, the proof of the result contains gaps which are non-trivial to fix. In this work, we present the first complete proof of the $P_i \oplus P_j$ for any $\xi_{\max}$ theorem. As an illustration of our result, we also revisit the security proofs of two optimally secure blockcipher-based pseudorandom functions, and provide updated security bounds. Our result is actually more general in nature as we consider equations of the form $X_i \oplus X_j = \lambda_k$ over a commutative group under addition, and of exponent 2.

Available format(s)
Secret-key cryptography
Publication info
Mirror theory Sum of Permutations PRP PRF H-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
2022-05-31: approved
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 any $\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.