**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}

**Category / Keywords: **secret-key cryptography / Mirror Theory, Sum of Permutation, PRP, PRF, H-Technique

**Date: **received 4 Jun 2020, last revised 4 Jun 2020

**Contact author: **sahaa 1993 at gmail com,mridul nandi@gmail com,avirocks dutta13@gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20200605:195323 (All versions of this report)

**Short URL: **ia.cr/2020/669

[ Cryptology ePrint archive ]