[{"intvolume":"      2656","publication_status":"published","year":"2003","quality_controlled":"1","article_processing_charge":"No","conference":{"location":"Warschau, Polen","end_date":"2003-05-08","start_date":"2003-05-04","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques"},"alternative_title":["LNCS"],"date_published":"2003-06-04T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://crypto-test.ethz.ch/publications/files/MauPie03.pdf"}],"fulldoi":"https://doi.org/10.1007/3-540-39200-9_34","oa":1,"day":"04","publisher":"Springer Nature","month":"06","doi":"10.1007/3-540-39200-9_34","volume":2656,"date_created":"2018-12-11T12:02:02Z","status":"public","author":[{"full_name":"Maurer, Ueli","first_name":"Ueli","last_name":"Maurer"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654"}],"title":"The security of many round Luby Rackoff pseudo random permutations","_id":"3210","extern":"1","abstract":[{"lang":"eng","text":"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 &lt; α, 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. "}],"oa_version":"Preprint","type":"conference","citation":{"chicago":"Maurer, Ueli, and Krzysztof Z Pietrzak. “The Security of Many Round Luby Rackoff Pseudo Random Permutations,” 2656:544–61. Springer Nature, 2003. <a href=\"https://doi.org/10.1007/3-540-39200-9_34\">https://doi.org/10.1007/3-540-39200-9_34</a>.","apa":"Maurer, U., &#38; 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, Warschau, Polen: Springer Nature. <a href=\"https://doi.org/10.1007/3-540-39200-9_34\">https://doi.org/10.1007/3-540-39200-9_34</a>","mla":"Maurer, Ueli, and Krzysztof Z. Pietrzak. <i>The Security of Many Round Luby Rackoff Pseudo Random Permutations</i>. Vol. 2656, Springer Nature, 2003, pp. 544–61, doi:<a href=\"https://doi.org/10.1007/3-540-39200-9_34\">10.1007/3-540-39200-9_34</a>.","ama":"Maurer U, Pietrzak KZ. The security of many round Luby Rackoff pseudo random permutations. In: Vol 2656. Springer Nature; 2003:544-561. doi:<a href=\"https://doi.org/10.1007/3-540-39200-9_34\">10.1007/3-540-39200-9_34</a>","ieee":"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, Warschau, Polen, 2003, vol. 2656, pp. 544–561.","short":"U. Maurer, K.Z. Pietrzak, in:, Springer Nature, 2003, pp. 544–561.","ista":"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."},"page":"544 - 561","date_updated":"2026-05-21T12:04:42Z","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","publication_identifier":{"isbn":["9783540140399","9783540392002"]},"OA_type":"hybrid","OA_place":"repository","language":[{"iso":"eng"}],"publist_id":"3473"}]