Cryptology ePrint Archive: Report 2010/287

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}

Category / Keywords: secret-key cryptography / Xor of random permutations, Systems of linear Equalities and Linear non Equalities in finite groups, Security proofs beyond the Birthday Bound

Date: received 14 May 2010, last revised 19 Feb 2017

Contact author: valerie nachef at u-cergy fr

Available format(s): PDF | BibTeX Citation

Note: rectification of typos

Version: 20170219:113851 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]