[LR88] How to Construct Pseudorandom Permutations from Pseudorandom Functions

Authors: Michael Luby, Charles Rackoff | Venue: SIAM Journal on Computing 1988 | Source

Abstract

We show how to efficiently construct a pseudorandom invertible permutation generator from a pseudorandom function generator. Goldreich, Goldwasser and Micali GGM86 introduce the notion of a pseudorandom function generator and show how to efficiently construct a pseudorandom function generator from a pseudorandom bit generator. We use some of the ideas behind the design of the Data Encryption Standard for our construction. A practical implication of our result is that any pseudorandom bit generator can be used to construct a block private key cryptosystem which is secure against chosen plaintext attack, which is one of the strongest known attacks against a cryptosystem.

BibTeX

Copy

@Article{LubRac88,
  author = {Michael Luby and Charles Rackoff},
  title = {How to construct pseudorandom permutations from pseudorandom functions},
  journal = {{SIAM} Journal on Computing},
  volume = {17},
  number = {2},
  year = {1988},
}