**Generic Attacks for the Xor of k random permutations**

*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}

**Category / Keywords: **secret-key cryptography / pseudorandom functions, pseudorandom permutations, Luby-Rackoff backwards, generic attacks

**Date: **received 7 Jan 2008, last revised 14 Apr 2013

**Contact author: **valerie nachef at u-cergy fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20130414:173806 (All versions of this report)

**Short URL: **ia.cr/2008/009

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]