How to Construct Pseudo-Random Permutations from Pseudo-Random Functions (Abstract)

By Michael Luby, C. Rackoff. 1986

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

On Generalized Feistel Networks (2010, methodology): “classical FEISTEL [n] 2q r+1 ( 4q / 2 )r 6r − 1 Theorem 6 [10, 13, 26]”
Lecture Notes on Cryptography (2001, background): “The concept of pseudorandom functions is due to Goldreich, Goldwasser and Micali [97], while that of pseudorandom permutation is due to Luby and Rackoff [138].”
Sequences of games: a tool for taming complexity in security proofs (2004, methodology): “We now give an analysis of the Luby-Racko construction for building a pseudo-random permutation family out of a pseudo-random function family [ LR88 ].”
Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation (2009, unknown): “The table is equipped with a hash function h0 : U → [m] that is sampled from a collection of k-wise independent hash functions (see Section 2 for constructions of such functions with succinct representations and constant evaluation time).”
How to Encipher Messages on a Small Domain (2009, methodology): “For balanced Feistel, the classical analysis by Luby and Rackoff [17] shows that three rounds provide CPA-security (four rounds for CCA-security) to nearly 2n/4 queries.”
Pseudorandom Functions: Three Decades Later (2017, background): “This is unavoidable for the Luby–Rackoff construction; Aiello and Venkatesan [1] proved that the four-round Feistel network is not (poly(k) ·2k/4,2k/4, 12)-pseudorandom.”
OCB: a block-cipher mode of operation for efficient authenticated encryption (2001, background): “Our proof of privacy assumes that the underlying block cipher is good in the sense of a pseudorandom permutation (PRP) [6] [26], while our proof of authenticity assumes that the block cipher is a strong PRP [26].”
Formal certification of code-based cryptographic proofs (2009, background): “The notion of pseudorandom permutation is due to Luby and Rackoff [1988], who also observe that the notions of pseudorandom function and permutation are no different in an asymptotic setting, and show how to construct a pseudorandom permutation from a pseudorandom function.”
The Security of the Cipher Block Chaining Message Authentication Code (2000, methodology): “The last method appears in an informational Annex of [13] and has now been analyzed by Petrank and Rackoff [18].”
A taxonomy of privacy-preserving record linkage techniques (2013, background): “A PRF is a secure algorithm that when given an n -bit seed k , and an n -bit argument x , it returns an n -bit string f k ( x ) such that it is infeasible to distinguish f k ( x ) for random k from a truly random function [98].”
Breaking Symmetric Cryptosystems Using Quantum Period Finding (2016, background): “In a seminal work, Luby and Rackoﬀ proved that a three-round Feistel scheme is a secure pseudo-random permutation [33].”