Introduction to Mirror Theory: Analysis of Systems of Linear Equalities and Linear Non Equalities for Cryptography

Jacques Patarin

Abstract

\begin{abstract} In this paper we will first study two closely related problems:\\ 1. The problem of distinguishing $f(x\Vert 0)\oplus f(x \Vert 1)$ where $f$ is a random permutation on $n$ bits. This problem was first studied by Bellare and Implagliazzo in~\cite{BI}.\\ 2. The so-called Theorem $P_i \oplus P_j$'' of Patarin (cf~\cite{P05}). Then, we will see many variants and generalizations of this Theorem $P_i \oplus P_j$'' useful in Cryptography. In fact all these results can be seen as part of the theory that analyzes the number of solutions of systems of linear equalities and linear non equalities in finite groups. We have nicknamed these analysis Mirror Theory'' due to the multiples induction properties that we have in it. \end{abstract}

Note: rectification of typos

Available format(s)
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Xor of random permutationsSecurity proofs beyond the Birthday Bound
Contact author(s)
valerie nachef @ u-cergy fr
History
2017-02-19: last of 2 revisions
See all versions
Short URL
https://ia.cr/2010/287

CC BY

BibTeX

@misc{cryptoeprint:2010/287,
author = {Jacques Patarin},
title = {Introduction to Mirror Theory: Analysis of Systems of Linear Equalities and Linear Non Equalities for Cryptography},
howpublished = {Cryptology ePrint Archive, Paper 2010/287},
year = {2010},
note = {\url{https://eprint.iacr.org/2010/287}},
url = {https://eprint.iacr.org/2010/287}
}

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