International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Proof of Mirror Theory for a Wide Range of ξmax

Authors:
Benoit Cogliati , Thales DIS France SAS, Meudon, France
Avijit Dutta , Institute for Advancing Intelligence, TCG-CREST
Mridul Nandi , Indian Statistical Institute, Kolkata; Institute for Advancing Intelligence, TCG-CREST
Jacques Patarin , Thales DIS France SAS, Meudon, France; Laboratoire de Mathématiques de Versailles, UVSQ, CNRS, Université Paris-Saclay, Versailles, France
Abishanka Saha , Indian Statistical Institute, Kolkata
Download:
DOI: 10.1007/978-3-031-30634-1_16 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2023
Abstract: In CRYPTO'03, Patarin conjectured a lower bound on the number of distinct solutions (P1,…,Pq)∈({0,1}n)q satisfying a system of equations of the form Xi⊕Xj=λi,j such that P1,P2,…, Pq are pairwise distinct. This result is known as \emph{``Pi⊕Pj Theorem for any ξmax"} or alternatively as \emph{Mirror Theory for general ξmax}, which was later proved by Patarin in ICISC'05. Mirror theory for general ξ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 Pi⊕Pj theorem for a wide range of ξmax, typically up to order O(2n/4/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.
BibTeX
@inproceedings{eurocrypt-2023-32917,
  title={Proof of Mirror Theory for a Wide Range of $\xi_{\max}$},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-30634-1_16},
  author={Benoit Cogliati and Avijit Dutta and Mridul Nandi and Jacques Patarin and Abishanka Saha},
  year=2023
}