CryptoDB
Generic Attacks for the Xor of k random permutations
| Authors: | |
|---|---|
| Download: | |
| 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} |
BibTeX
@misc{eprint-2008-17686,
title={Generic Attacks for the Xor of k random permutations},
booktitle={IACR Eprint archive},
keywords={secret-key cryptography / pseudorandom functions, pseudorandom permutations, Luby-Rackoff backwards, generic attacks},
url={http://eprint.iacr.org/2008/009},
note={ valerie.nachef@u-cergy.fr 13885 received 7 Jan 2008},
author={Jacques Patarin},
year=2008
}