---
OA_place: repository
OA_type: hybrid
_id: '3210'
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 < α, 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. '
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Ueli
  full_name: Maurer, Ueli
  last_name: Maurer
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
citation:
  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>'
  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>'
  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>.
  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.'
  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.'
  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>.
  short: U. Maurer, K.Z. Pietrzak, in:, Springer Nature, 2003, pp. 544–561.
conference:
  end_date: 2003-05-08
  location: Warschau, Polen
  name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
  start_date: 2003-05-04
date_created: 2018-12-11T12:02:02Z
date_published: 2003-06-04T00:00:00Z
date_updated: 2026-05-21T12:04:42Z
day: '04'
doi: 10.1007/3-540-39200-9_34
extern: '1'
fulldoi: https://doi.org/10.1007/3-540-39200-9_34
intvolume: '      2656'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://crypto-test.ethz.ch/publications/files/MauPie03.pdf
month: '06'
oa: 1
oa_version: Preprint
page: 544 - 561
publication_identifier:
  isbn:
  - '9783540140399'
  - '9783540392002'
publication_status: published
publisher: Springer Nature
publist_id: '3473'
quality_controlled: '1'
status: public
title: The security of many round Luby Rackoff pseudo random permutations
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 2656
year: '2003'
...