Welcome to the resource topic for
**2008/009**

**Title:**

Generic Attacks for the Xor of k random permutations

**Authors:**
Jacques Patarin

**Abstract:**

\begin{abstract} Xoring the output of k permutations, k\geq 2 is a very simple way to construct pseudo-random functions (PRF) from pseudo-random permutations (PRP). Moreover such construction has many applications in cryptography (see \cite{BI,BKrR,HWKS,SL} for example). Therefore it is interesting both from a theoretical and from a practical point of view, to get precise security results for this construction. In this paper, we will describe the best attacks that we have found on the Xor of k random n-bit to n-bit permutations. When k=2, we will get an attack of computational complexity O(2^n). This result was already stated in \cite{BI}. On the contrary, for k \geq 3, our analysis is new. We will see that the best known attacks require much more than 2^n computations when not all of the 2^n outputs are given, or when the function is changed on a few points. We obtain like this a new and very simple design that can be very usefull when a security larger than 2^n is wanted, for example when n is very small. \end{abstract}

**ePrint:**
https://eprint.iacr.org/2008/009

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .