Paper 2008/009

Generic Attacks for the Xor of k random permutations

Jacques Patarin


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

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
pseudorandom functionspseudorandom permutationsLuby-Rackoff backwardsgeneric attacks
Contact author(s)
valerie nachef @ u-cergy fr
2013-04-14: revised
2008-01-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jacques Patarin},
      title = {Generic Attacks for the Xor of k random permutations},
      howpublished = {Cryptology ePrint Archive, Paper 2008/009},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.