Paper 2022/686

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

Abstract

In CRYPTO'03, Patarin conjectured a lower bound on the number of distinct solutions $(P_1,\dots ,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,\dots$, $P_q$ are pairwise distinct. This result is known as \emph{``$$ Theorem for any $$''} or alternatively as \emph{Mirror Theory for general $$}, which was later proved by Patarin in ICISC'05. Mirror theory for general $$ 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 $$ theorem for a wide range of $$, typically up to order $$. 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 $$-bit security proof for six round Feistel cipher, and provide updated security bounds.