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

Avijit Dutta; Mridul Nandi; Abishanka Saha

Paper 2020/669 Original: eprint.iacr.org/2020/669 ↗

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

Avijit Dutta

Mridul Nandi

Abishanka Saha

Abstract

In ICISC-05, and in the ePrint $2010/287$, Patarin claimed a lower bound on the number of $2q$ tuples of $n$-bit strings $(P_1, \ldots, P_{2q}) \in (\{0,1\}^{n})^{2q}$ satisfying $P_{2i - 1} \oplus P_{2i} = \lambda_i$ for $1 \leq i \leq q$ such that $P_1, P_2, \ldots$, $P_{2q}$ are distinct and $\lambda_i \in \{0,1\}^n \setminus \{0^n\}$. This result is known as {\em Mirror theory} and widely used in cryptography. It stands as a powerful tool to provide a high-security guarantee for many block cipher-(or even ideal permutation-) based designs. In particular, Mirror theory has a direct application in the security of XOR of block ciphers. Unfortunately, the proof of Mirror theory contains some unverifiable gaps and several mistakes. This paper provides a simple and verifiable proof of Mirror theory.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint.
History: 2022-04-28: last updated; 2020-06-05: published
Short URL: https://ia.cr/2020/669
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2020/669,
      author = {Avijit Dutta and Mridul Nandi and Abishanka Saha},
      title = {Proof of Mirror Theory for $\xi_{\max}=2$},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/669},
      year = {2020},
      url = {https://eprint.iacr.org/2020/669}
}