Paper 2020/734
Mirror Theory: A simple proof of the Pi+Pj Theorem with xi_max=2
Benoît Cogliati and Jacques Patarin
Abstract
We provide a simple and complete proof of the famous Pi⊕Pj Theorem in the particular case where ξmax=2. This Theorem gives a lower bound for the number of solutions of simple linear systems of equations in the case where all the variables have to be pairwise distinct. Such systems often occur in cryptographic proofs of security, and this particular Theorem can be used to prove that the function x↦P(0||x)⊕P(1||x) is an optimally secure pseudorandom function when P is a uniformly random permutation.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Mirror Theorysecurity proofsoptimal security
- Contact author(s)
- benoitcogliati @ hotmail fr
- History
- 2020-06-18: received
- Short URL
- https://ia.cr/2020/734
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/734,
author = {Benoît Cogliati and Jacques Patarin},
title = {Mirror Theory: A simple proof of the Pi+Pj Theorem with xi_max=2},
howpublished = {Cryptology ePrint Archive, Paper 2020/734},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/734}},
url = {https://eprint.iacr.org/2020/734}
}
