Generic Attacks for the Xor of k random permutations

Jacques Patarin

Paper 2008/009

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 random -bit to -bit permutations. When , we will get an attack of computational complexity . This result was already stated in \cite{BI}. On the contrary, for , our analysis is new. We will see that the best known attacks require much more than computations when not all of the 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 is wanted, for example when is very small. \end{abstract}

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: pseudorandom functions pseudorandom permutations Luby-Rackoff backwards generic attacks
Contact author(s): valerie nachef @ u-cergy fr
History: 2013-04-14: revised; 2008-01-07: received; See all versions
Short URL: https://ia.cr/2008/009
License: CC BY

BibTeX

@misc{cryptoeprint:2008/009,
      author = {Jacques Patarin},
      title = {Generic Attacks for the Xor of k random permutations},
      howpublished = {Cryptology {ePrint} Archive, Paper 2008/009},
      year = {2008},
      url = {https://eprint.iacr.org/2008/009}
}