How to Construct Pseudorandom Permutations from Pseudorandom Functions

Citations Over TimeTop 10% of 1988 papers

Abstract

We show how to efficiently construct a pseudorandom invertible permutation generator from a pseudorandom function generator. Goldreich, Goldwasser and Micali ["How to construct random functions," Proc. 25th Annual Symposium on Foundations of Computer Science, October 24–26, 1984.] 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.

Related Papers

• → A Pseudorandom Generator from any One-way Function(1999)1,659 cited
• → How to Construct Pseudorandom Permutations from Pseudorandom Functions(1988)921 cited
• → How to Construct Pseudorandom Permutations from Single Pseudorandom Functions(1991)51 cited
• → How to Construct Pseudorandom and Super Pseudorandom Permutations from One Single Pseudorandom Function(2007)65 cited
• → Yet Another Pseudorandom Number Generator(2017)11 cited