Abstract
Luby and Rackoff showed how to construct a (super-)pseudorandom permutation {0, 1}2n → {0, 1}2n → {0, 1}2n from some number r of pseudo-random functions {0, 1}n → {0, 1}n. Their construction, motivated by DES, consists of a cascade of r Feistel permutations. A Feistel permutation 1for a pseudo-random function f is defined as (L, R) → (R, L ⊕ f(R)), where L and R are the left and right part of the input and ⊕ denotes bitwise XOR or, in this paper, any other group operation on {0, 1}n. The only non-trivial step of the security proof consists of proving that the cascade of r Feistel permutations with independent uniform random functions {0, 1}n → {0, 1}n, denoted Ψ r2n , is indistinguishable from a uniform random permutation {0, 1}2n → {0, 1}2n by any computationally unbounded adaptive distinguisher making at most O(2cn) combined chosen plaintext/ciphertext queries for any c < α, where α is a security parameter.
Luby and Rackoff proved α = 1/2 for r = 4. A natural problem, proposed by Pieprzyk is to improve on α for larger r. The best known result, α = 3/4 for r = 6, is due to Patarin. In this paper we prove α = 1 − O(1/r), i.e., the trivial upper bound α = 1 can be approached. The proof uses some new techniques that can be of independent interest.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
W. Aiello and R. Venkatesan, Foiling birthday attacks in length-doubling transformations — Benes: A non-reversible alternative to Feistel, Advances in Cryptology — EUROCRYPT’ 96, Lecture Notes in Computer Science, vol. 1070, pp. 307–320, Springer-Verlag, 1996.
O. Goldreich, S. Goldwasser, and S. Micali, How to construct random functions, Journal of the ACM, vol. 33, no. 4, pp. 210–217, 1986.
L. R. Knudsen, The security of Feistel ciphers with six rounds or less, Journal of Cryptology vol. 15, no. 3, pp. 207–222, Springer-Verlag, 2002.
S. Lucks, Faster Luby-Rackoff ciphers, Fast Software Encryption, Lecture Notes in Computer Science, vol. 1039, pp. 189–203, Springer-Verlag, 1996.
M. Luby and C. Rackoff, How to construct pseudo-random permutations from pseudo-random functions, SIAM J. on Computing, vol. 17, no. 2, pp. 373–386, 1988.
U. M. Maurer, A simplified and generalized treatment of Luby-Rackoff pseudorandom permutation generators, Advances in Cryptology — EUROCRYPT’ 92, Lecture Notes in Computer Science, vol. 658, pp. 239–255, Springer-Verlag, 1992.
—, Indistinguishability of random systems Advances in Cryptology — EUROCRYPT’ 02, Lecture Notes in Computer Science, vol. 2332, pp. 110–132, Springer-Verlag, 2002.
M. Naor and O. Reingold, On the construction of pseudorandom permutations: Luby-Rackoff revisited, Journal of Cryptology, vol. 12, no. 1, pp. 29–66, 1999.
J. Patarin, How to construct pseudorandom permutations from a single pseudorandom function, Advances in Cryptology — EUROCRYPT’ 92, Lecture Notes in Computer Science, vol. 658, pp. 256–266, Springer-Verlag, 1992.
—, About Feistel schemes with six (or more) rounds, Fast Software Encryption, Lecture Notes in Computer Science, vol. 1372, pp. 103–121, Springer-Verlag, 1998.
S. Patel, Z. Ramzan, and G. Sundaram, Towards making Luby-Rackoff ciphers optimal and practical, Fast Software Encryption, Lecture Notes in Computer Science, vol. 1636, pp. 171–185, Springer-Verlag, 1999.
J. Pieprzyk, How to construct pseudorandom permutations from single pseudorandom functions, Advances in Cryptology — EUROCRYPT’ 90, Lecture Notes in Computer Science, vol. 473, pp. 140–150, Springer-Verlag, 1990.
Z. Ramzan and L. Reyzin, On the round security of symmetric-key cryptographic primitives, Advances in Cryptology — CRYPTO’ 00, Lecture Notes in Computer Science, vol. 1880, pp. 376–393, Springer-Verlag, 2000.
S. Vaudenay, Adaptive-attack norm for decorrelation and super-pseudorandomness, Proc. of SAC’99, Lecture Notes in Computer Science, vol. 1758, pp. 49–61, Springer-Verlag, 2000.
Y. Zheng, T. Matsumoto, and H. Imai, Impossibility and optimality results on constructing pseudorandom permutations, Advances in Cryptology — EUROCRYPT’ 89, Lecture Notes in Computer Science, vol. 434, pp. 412–422, Springer-Verlag, 1989.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 International Association for Cryptologic Research
About this paper
Cite this paper
Maurer, U., Pietrzak, K. (2003). The Security of Many-Round Luby-Rackoff Pseudo-Random Permutations. In: Biham, E. (eds) Advances in Cryptology — EUROCRYPT 2003. EUROCRYPT 2003. Lecture Notes in Computer Science, vol 2656. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-39200-9_34
Download citation
DOI: https://doi.org/10.1007/3-540-39200-9_34
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-14039-9
Online ISBN: 978-3-540-39200-2
eBook Packages: Springer Book Archive