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

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
pseudorandom functionspseudorandom permutationsLuby-Rackoff backwardsgeneric 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2008/009}},
      url = {https://eprint.iacr.org/2008/009}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.