How to Construct Pseudorandom Permutations from Pseudorandom Functions

1988/04/01 by Michael Luby, Charles Rackoff · 937 citations
Computer Science · Mathematics · #Algorithm #Block (permutation group theory) #Block cipher #Chaos-based Image/Signal Encryption #Coding theory and cryptography #Combinatorics #Computer science #Computer security #Construct (python library) #Cryptographic Implementations and Security #Cryptography #Cryptosystem #Encryption #Generator (circuit theory) #Linear congruential generator #Mathematics #Physics #Plaintext #Pseudorandom function family #Pseudorandom generator #Pseudorandom generator theorem #Pseudorandom number generator #Pseudorandom permutation #Pseudorandomness #Random permutation #Random seed #Self-shrinking generator

paper · doi:10.1137/0217022

published in SIAM Journal on Computing 17(2), 373-386 (Society for Industrial and Applied Mathematics)

openalex publication_date 1988/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31

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 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
• A New Type of Cipher
• More on additive triples of bijections
• Permutation Generators Based on Unbalanced Feistel Network: Analysis of the Conditions of Pseudorandomness
• Practical Massively Parallel Sorting
• Understanding the Related-Key Security of Feistel Ciphers from a Provable Perspective
• Limitations of the Even-Mansour construction
• Adiantum: length-preserving encryption for entry-level processors
• Deterministic and Efficiently Searchable Encryption
• How to Leak a Secret
• On Cryptographic Assumptions and Challenges
• Constraint Logic Programming over Infinite Domains with an Application to Proof
• The Block Cipher Companion
• Guesswork and Variation Distance as Measures of Cipher Security
• Backdoor Attacks on Black-Box Ciphers Exploiting Low-Entropy Plaintexts
• A Pseudorandom Generator from any One-way Function

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