Welcome to the resource topic for 2022/686
Title:
Proof of Mirror Theory for any \xi_{\max}
Authors: Benoît Cogliati, Avijit Dutta, Mridul Nandi, Jacques Patarin, and Abishanka Saha
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.
ePrint: https://eprint.iacr.org/2022/686
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .