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

Avijit Dutta; Mridul Nandi; Abishanka Saha

Paper 2020/669

Proof of Mirror Theory for $ξ_{max} = 2$

Avijit Dutta, Mridul Nandi, and Abishanka Saha

Abstract

In ICISC-05, and in the ePrint $2010 / 287$ , Patarin claimed a lower bound on the number of $2 q$ tuples of $n$ -bit strings $(P_{1}, \dots, P_{2 q}) \in ({0, 1}^{n})^{2 q}$ satisfying $P_{2 i - 1} \oplus P_{2 i} = λ_{i}$ for $1 \leq i \leq q$ such that $P_{1}, P_{2}, \dots$ , $P_{2 q}$ are distinct and $λ_{i} \in {0, 1}^{n} ∖ {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.

Note: This version of the paper greatly simplifies the proof over its earlier version with a simplified notations and terminologies.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. IEEE Transactions on Information Theory
Keywords: Mirror Theory Sum of Permutation PRP PRF H-Technique
Contact author(s): sahaa 1993 @ gmail com
mridul nandi @ gmail com
avirocks dutta13 @ gmail com
History: 2022-04-28: last of 2 revisions; 2020-06-05: received; See all versions
Short URL: https://ia.cr/2020/669
License: CC BY

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

Paper 2020/669

Proof of Mirror Theory for ξmax=2

Abstract

Metadata

Proof of Mirror Theory for $ξ_{max} = 2$