IACR Cryptology ePrint Archive · 2010 · 55 citations · 10 references
ComputingComputer ScienceMathematicsCryptographyInformation TheoryTheory Of ComputationCryptographic ComplexityGroup Theory
In this paper we will first study two closely related problems: 1. The problem of distinguishing f(x‖0) ⊕ f(x‖1) where f is a random permutation on n bits. This problem was first studied by Bellare and Implagliazzo in [3]. 2. The so-called “Theorem Pi⊕Pj” of Patarin (cf [23]). Then, we will see many variants and generalizations of this “Theorem Pi ⊕ Pj” 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.
10