Generic attacks for the Xor of k random permutations

Abstract : Xoring the output of k permutations, k ≥ 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 [2,3,4,5] 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(2n ). This result was already stated in [2]. On the contrary, for k ≥ 3, our analysis is new. We will see that the best known attacks require much more than 2n computations when not all of the 2n 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 useful when a security larger than 2n is wanted, for example when n is very small. © 2013 Springer-Verlag.
Document type :
Conference papers
Complete list of metadatas

https://hal.uvsq.fr/hal-02177221
Contributor : Équipe Hal Uvsq <>
Submitted on : Monday, July 8, 2019 - 5:12:17 PM
Last modification on : Wednesday, July 10, 2019 - 1:30:32 AM

Links full text

Identifiers

Collections

Citation

J. Patarin. Generic attacks for the Xor of k random permutations. 11th International Conference on Applied Cryptography and Network Security, ACNS 2013, Jun 2013, Banff, AB, Canada. pp.154-169, ⟨10.1007/978-3-642-38980-1_10⟩. ⟨hal-02177221⟩

Share

Metrics

Record views

19