Welcome to the resource topic for 2008/009
Title:
Generic Attacks for the Xor of k random permutations
Authors: 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}
ePrint: https://eprint.iacr.org/2008/009
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .