---
res:
bibo_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.
@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Ueli
foaf_name: Maurer, Ueli M
foaf_surname: Maurer
- foaf_Person:
foaf_givenName: Krzysztof Z
foaf_name: Krzysztof Pietrzak
foaf_surname: Pietrzak
foaf_workInfoHomepage: http://www.librecat.org/personId=3E04A7AA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9139-1654
bibo_doi: 10.1007/3-540-39200-9_34
bibo_volume: 2656
dct_date: 2003^xs_gYear
dct_publisher: Springer@
dct_title: The security of many round Luby Rackoff pseudo random permutations@
...