The security of many round Luby Rackoff pseudo random permutations

U. Maurer, K.Z. Pietrzak, in:, Springer, 2003, pp. 544–561.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
Series Title
LNCS
Abstract
Luby and Rackoff showed how to construct a (super-)pseudo-random permutation {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 Ψ2nr 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 a 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 a = 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.
Publishing Year
Date Published
2003-06-04
Volume
2656
Page
544 - 561
Conference
EUROCRYPT: Theory and Applications of Cryptographic Techniques
IST-REx-ID

Cite this

Maurer U, Pietrzak KZ. The security of many round Luby Rackoff pseudo random permutations. In: Vol 2656. Springer; 2003:544-561. doi:10.1007/3-540-39200-9_34
Maurer, U., & Pietrzak, K. Z. (2003). The security of many round Luby Rackoff pseudo random permutations (Vol. 2656, pp. 544–561). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Springer. https://doi.org/10.1007/3-540-39200-9_34
Maurer, Ueli, and Krzysztof Z Pietrzak. “The Security of Many Round Luby Rackoff Pseudo Random Permutations,” 2656:544–61. Springer, 2003. https://doi.org/10.1007/3-540-39200-9_34.
U. Maurer and K. Z. Pietrzak, “The security of many round Luby Rackoff pseudo random permutations,” presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, 2003, vol. 2656, pp. 544–561.
Maurer U, Pietrzak KZ. 2003. The security of many round Luby Rackoff pseudo random permutations. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 2656. 544–561.
Maurer, Ueli, and Krzysztof Z. Pietrzak. The Security of Many Round Luby Rackoff Pseudo Random Permutations. Vol. 2656, Springer, 2003, pp. 544–61, doi:10.1007/3-540-39200-9_34.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar