How to Construct Pseudorandom Permutations from Pseudorandom Functions

DOI10.1137/0217022zbMath0644.94018OpenAlexW2077300005WikidataQ29398612 ScholiaQ29398612MaRDI QIDQ3787920

Publication date: 1988

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0217022

zbMATH Keywords

security pseudorandom bit generator Riesz measure Data Encryption Standard pseudorandom function generator block private key cryptosystem pseudorandom invertible permutation generator

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Random number generation in numerical analysis (65C10)

Related Items

Subquadratic SNARGs in the random oracle model ⋮ How to build an ideal cipher: the indifferentiability of the Feistel construction ⋮ Related-key analysis of generalized Feistel networks with expanding round functions ⋮ Computational hardness of optimal fair computation: beyond Minicrypt ⋮ Optimum attack on 3-round Feistel-2 structure ⋮ Cryptography from Learning Parity with Noise ⋮ Extended meet-in-the-middle attacks on some Feistel constructions ⋮ A construction of the simplest super pseudorandom permutation generator ⋮ The GGM Function Family Is a Weakly One-Way Family of Functions ⋮ More efficient DDH pseudorandom generators ⋮ Bloom Filters in Adversarial Environments ⋮ On Reverse-Engineering S-Boxes with Hidden Design Criteria or Structure ⋮ New Attacks on Feistel Structures with Improved Memory Complexities ⋮ Sparse pseudorandom distributions ⋮ Improving algorithm 2 in multidimensional (zero-correlation) linear cryptanalysis using \(\chi^2\)-method ⋮ Quantum cryptanalysis on contracting Feistel structures and observation on related-key settings ⋮ Full indifferentiable security of the XOR of two or more random permutations using the \(\chi^2\) method ⋮ Anonymous IBE, leakage resilience and circular security from new assumptions ⋮ Constructing parallel long-message signcryption scheme from trapdoor permutation ⋮ Derandomized constructions of \(k\)-wise (almost) independent permutations ⋮ A construction of a cipher from a single pseudorandom permutation. ⋮ Mathematical problems in cryptology ⋮ Beyond-birthday security for permutation-based Feistel networks ⋮ A study of password security ⋮ Quantum attacks against type-1 generalized Feistel ciphers and applications to CAST-256 ⋮ Towards Understanding the Known-Key Security of Block Ciphers ⋮ Attacking BEAR and LION Schemes in a Realistic Scenario ⋮ Using Bernstein-Vazirani algorithm to attack block ciphers ⋮ Pseudo-mixing Time of Random Walks ⋮ Hardness-preserving reductions via cuckoo hashing ⋮ Authenticated Encryption Mode for Beyond the Birthday Bound Security ⋮ A Proof of Security in O(2 n ) for the Benes Scheme ⋮ Quantum key-recovery attack on Feistel constructions: Bernstein-Vazirani meet Grover algorithm ⋮ Applications of Simon's algorithm in quantum attacks on Feistel variants ⋮ On Lai-Massey and quasi-Feistel ciphers ⋮ Pseudorandomness analysis of the (extended) Lai-Massey scheme ⋮ Tweakable enciphering schemes using only the encryption function of a block cipher ⋮ On the provable security of BEAR and LION schemes ⋮ Probably Secure Keyed-Function Based Authenticated Encryption Schemes for Big Data ⋮ Robust Multi-property Combiners for Hash Functions Revisited ⋮ Tweakable block ciphers ⋮ Square reflection cryptanalysis of 5-round Feistel networks with permutations ⋮ Revisiting iterated attacks in the context of decorrelation theory ⋮ Non-cryptographic primitive for pseudorandom permutation. ⋮ Being a permutation is also orthogonal to one-wayness in quantum world: impossibilities of quantum one-way permutations from one-wayness primitives ⋮ Adaptive zero-knowledge proofs and adaptively secure oblivious transfer ⋮ Cryptanalysis of Ladder-DES ⋮ On the security of remotely keyed encryption ⋮ About Feistel Schemes with Six (or More) Rounds ⋮ Monkey: Black-Box Symmetric Ciphers Designed for MONopolizing KEYs ⋮ RIV for Robust Authenticated Encryption ⋮ Improved Mixing Time Bounds for the Thorp Shuffle ⋮ Generic attacks with standard deviation analysis on a-Feistel schemes ⋮ On rate-1 and beyond-the-birthday bound secure online ciphers using tweakable block ciphers ⋮ On Integral Distinguishers of Rijndael Family of Ciphers ⋮ Deterministic encryption with the Thorp shuffle ⋮ Generic attacks on the Lai-Massey scheme ⋮ On the optimality of non-linear computations for symmetric key primitives ⋮ Notions and relations for RKA-secure permutation and function families ⋮ A randomness test for block ciphers ⋮ Building blockcipher from small-block tweakable blockcipher ⋮ Luby-Rackoff revisited: on the use of permutations as inner functions of a Feistel scheme ⋮ A general mixing strategy for the ECB-Mix-ECB mode of operation ⋮ Distinguishing Distributions Using Chernoff Information ⋮ Toward an Easy-to-Understand Structure for Achieving Chosen Ciphertext Security from the Decisional Diffie-Hellman Assumption ⋮ A Provable-Security Treatment of the Key-Wrap Problem ⋮ Efficient Chosen Ciphertext Secure Public Key Encryption under the Computational Diffie-Hellman Assumption ⋮ Hash Functions from Defective Ideal Ciphers ⋮ On the XOR of Multiple Random Permutations ⋮ Distinguishing properties and applications of higher order derivatives of Boolean functions ⋮ Pseudorandomness of Camellia-like scheme ⋮ Implementing, and keeping in check, a DSL used in E-learning ⋮ Online Ciphers from Tweakable Blockciphers ⋮ Analysis of the single-permutation encrypted Davies-Meyer construction ⋮ Cryptanalysis of Feistel Networks with Secret Round Functions ⋮ Robust multi-property combiners for hash functions ⋮ Verifiable random functions: relations to identity-based key encapsulation and new constructions ⋮ Verifiable Random Functions from Identity-Based Key Encapsulation ⋮ Mind the composition: birthday bound attacks on EWCDMD and SoKAC21 ⋮ Three third generation attacks on the format preserving encryption scheme FF3 ⋮ An Almost m-wise Independent Random Permutation of the Cube ⋮ Provable related-key security of contracting Feistel networks ⋮ Generic Attacks on Feistel Networks with Internal Permutations ⋮ Distinguishers for Ciphers and Known Key Attack against Rijndael with Large Blocks ⋮ Building Secure Block Ciphers on Generic Attacks Assumptions ⋮ The “Coefficients H” Technique ⋮ Breaking Symmetric Cryptosystems Using Quantum Period Finding ⋮ Keyed hash functions ⋮ Building Blockcipher from Tweakable Blockcipher: Extending FSE 2009 Proposal ⋮ Security of Hash-then-CBC Key Wrapping Revisited ⋮ Indifferentiability of 8-Round Feistel Networks ⋮ A Domain Extender for the Ideal Cipher ⋮ Truly Efficient String Oblivious Transfer Using Resettable Tamper-Proof Tokens ⋮ Synthesizers and their application to the parallel construction of pseudo-random functions ⋮ Quantum statistical mechanics of encryption: reaching the speed limit of classical block ciphers ⋮ The summation-truncation hybrid: reusing discarded bits for free ⋮ Black-box use of one-way functions is useless for optimal fair coin-tossing ⋮ Guaranteeing the diversity of number generators ⋮ Quantum generic attacks on key-alternating Feistel ciphers for shorter keys ⋮ Pseudorandom Functions: Three Decades Later ⋮ Breaking symmetric cryptosystems using the offline distributed Grover-Meets-Simon algorithm ⋮ Keyed sum of permutations: a simpler RP-based PRF ⋮ Impossibility of indifferentiable iterated blockciphers from 3 or less primitive calls ⋮ Post-quantum security on the Lai-Massey scheme ⋮ Jammin' on the deck ⋮ BBB security for 5-round even-Mansour-based key-alternating Feistel ciphers ⋮ Noise-free thumbnail-preserving image encryption based on MSB prediction ⋮ Luby-Rackoff backwards with more users and more security ⋮ Provable security of HADES structure ⋮ Quantum attacks on Lai-Massey structure ⋮ Bet-or-pass: adversarially robust Bloom filters ⋮ \texttt{Horst} meets \textit{Fluid}-SPN: Griffin for zero-knowledge applications ⋮ Generic Attacks on Unbalanced Feistel Schemes with Expanding Functions ⋮ The security of the cipher block chaining message authentication code ⋮ A New Structural-Differential Property of 5-Round AES ⋮ Public-Seed Pseudorandom Permutations ⋮ Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier? ⋮ Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier? ⋮ Obfustopia built on secret-key functional encryption ⋮ Tweakable Enciphering Schemes from Hash-Sum-Expansion ⋮ Two New Efficient CCA-Secure Online Ciphers: MHCBC and MCBC ⋮ Tweakable Pseudorandom Permutation from Generalized Feistel Structure ⋮ Finding Collisions in Interactive Protocols---Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments ⋮ Private Information Retrieval Using Trusted Hardware ⋮ Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts ⋮ Feedback linearly extended discrete functions

This page was built for publication: How to Construct Pseudorandom Permutations from Pseudorandom Functions