How to Construct Pseudorandom Permutations from Pseudorandom Functions

1988/04/01 by Michael Luby, Charles Rackoff · 8 citations
Computer Science · #Chaos-based Image/Signal Encryption #Coding theory and cryptography #Cryptographic Implementations and Security

paper · doi:10.1137/0217022

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.

Cited by

• Finding Collisions in Interactive Protocols -- Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments
• Computational pseudorandomness, the wormhole growth paradox, and\n constraints on the AdS/CFT duality
• Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation
• Breaking Symmetric Cryptosystems Using Quantum Period Finding
• Local Access to Huge Random Objects through Partial Sampling
• Classical Encryption and Authentication under Quantum Attacks
• Using Bernstein-Vazirani Algorithm to Attack Block Ciphers
• An Enciphering Scheme Based on a Card Shuffle

Related

• A Simple construction of the Pseudorandom Generator from Permutation
• Pseudorandom Permutations from Random Reversible Circuits
• Random Bit Generator Mechanism Based on Elliptic Curves and Secure Hash Function
• Revisiting the Concrete Security of Goldreich's Pseudorandom Generator
• Increasing Randomness Using Permutations on Blocks