Cryptology ePrint Archive: Report 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}

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