Paper 2020/669

Proof of Mirror Theory for $\xi_{\max}=2$

Avijit Dutta and Mridul Nandi and Abishanka Saha

Abstract

In \textsf{ICISC-05}, \textsf{ePrint-10} and \textsf{patarin-book}, Patarin proved that the number of solutions of $(P_1, \ldots, P_{2q})$ with distinct $P_1, P_2, \ldots$, $P_{2q}$ from $\{0,1\}^n$ satisfying $P_{2i - 1} \oplus P_{2i} = \lambda_i$ ($\neq 0$), $1 \leq i \leq q$ is at least \begin{center} $\frac{(2^n)_{2q}}{2^{nq}}$ for all $q \leq \frac{2^n}{134}$ \end{center} where $(2^n)_{2q} := 2^n(2^n-1) \cdots (2^n - 2q + 1)$. This result is known as \textit{Mirror Theory}. Mirror theory stands out to be a powerful tool to provide a high security guarantee for many block cipher (or even an ideal permutation) based designs. Unfortunately, the proof of mirror theory contains some unverifiable gaps and several mistakes. In this paper, we revisit the proof strategy of \textsf{ePrint-10} and \textit{provide a detailed proof of the mirror theory by correcting the mistakes and filling up gaps}. In particular, we prove the mirror theory for all $q \leq 2^n/33.1$ (a wider range than what was originally claimed by Patarin). As an application, we show that the maximum PRF-advantage of sum of domain separated random permutation is \textbf{exactly} $1- (1 - 2^{-n})^q$, $\forall q \leq 2^n/33.1$. Using similar proof strategy, we also prove the following mirror theory for sum of two independent permutations: the number of solutions of $(P_1, Q_1, \ldots, P_{q}, Q_q)$ with distinct $P_1, P_2, \ldots$, $P_{q}$ and distinct $Q_1, \ldots, Q_q$ satisfying $P_{i} \oplus Q_i = \lambda_i$ for any fixed $\lambda_i \in \{0,1\}^n$, $1 \leq i \leq q$ is at least \begin{center} $\frac{(2^n)_{q} \times (2^n)_q}{2^{nq}} \times (1 - \frac{1.2q^2}{2^{2n}}-\frac{108n^3}{2^{2n}})$,\ \ for all $q \leq \frac{2^n}{13}$. \end{center}