Proof of Mirror Theory for $\xi_{\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 $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.

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

Available format(s)
Category
Secret-key cryptography
Publication info
Published elsewhere. IEEE Transactions on Information Theory
Keywords
Mirror TheorySum of PermutationPRPPRFH-Technique
Contact author(s)
sahaa 1993 @ gmail com
mridul nandi @ gmail com
avirocks dutta13 @ gmail com
History
2022-04-28: last of 2 revisions
See all versions
Short URL
https://ia.cr/2020/669

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},
note = {\url{https://eprint.iacr.org/2020/669}},
url = {https://eprint.iacr.org/2020/669}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.