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

##### Abstract

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)
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
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
History
2022-05-31: approved
See all versions
Short URL
https://ia.cr/2022/686

CC BY

BibTeX

@misc{cryptoeprint:2022/686,
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{https://eprint.iacr.org/2022/686}},
url = {https://eprint.iacr.org/2022/686}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.