Fact-checked by Grok 2 weeks ago

Pseudorandom permutation

A pseudorandom permutation (PRP) is a keyed family of permutations over a finite domain such that, when the key is chosen uniformly at random, no efficient adversary can distinguish the permutation from a uniformly random permutation with non-negligible probability, even after adaptively querying the permutation on polynomially many inputs.^[1] Formally, for a PRP \Pi = \{\pi_K : \{0,1\}^n \to \{0,1\}^n\}_{K \in \{0,1\}^s}, each \pi_K is a bijection, efficiently computable, and for any probabilistic polynomial-time distinguisher D making at most q queries, the advantage \left| \Pr[D^{\pi_K}(\cdot) = 1] - \Pr[D^\pi(\cdot) = 1] \right| is negligible in n, where \pi is a random permutation and the probabilities are over random K and \pi.^[2] A related notion is the strong PRP (SPRP), which remains indistinguishable even when the adversary has oracle access to both the forward permutation and its inverse.^[1] In cryptography, PRPs serve as the standard security model for block ciphers, such as AES, which encrypt fixed-length blocks of data under a secret key by permuting the plaintext in a way that appears random to unauthorized parties.^[2] This indistinguishability ensures that block ciphers resist attacks like distinguishing the cipher from random behavior, thereby providing confidentiality against chosen-plaintext adversaries. PRPs differ from pseudorandom functions (PRFs) in that they are bijective, enabling efficient decryption, but both primitives are foundational for symmetric-key protocols including message authentication and key derivation.^[3] The concept of PRPs was formalized in 1988 by Luby and Rackoff, who demonstrated how to construct a PRP from a PRF using a Feistel network: three rounds suffice for PRP security against chosen-plaintext attacks, while four rounds are needed for SPRP security against chosen-ciphertext attacks, with concrete bounds like \epsilon + q^2 / 2^n for the distinguishing advantage. Their construction, inspired by the DES cipher, composes rounds of the form L_{i+1} = R_i, R_{i+1} = L_i \oplus f_k(R_i), where f_k is a keyed PRF, proving security under the PRF assumption.^[1] Subsequent work by Naor and Reingold in 1999 improved this by constructing super-pseudorandom permutations (also known as strong PRPs or SPRPs) from PRFs using pairwise-independent permutations, enhancing efficiency and security proofs for practical implementations. These results underpin the design of modern block ciphers and enable provable security in cryptographic schemes.^[2]

Fundamentals

Definition

A pseudorandom permutation (PRP) is a keyed family of permutations over a finite domain that is computationally indistinguishable from a truly random permutation by any efficient adversary with access to the permutation as an oracle.^[4] This primitive models the ideal behavior of block ciphers in cryptography, where the permutation appears random under a secret key, ensuring that no polynomial-time algorithm can reliably detect patterns or predict outputs beyond what chance would allow. Formally, consider a function family E: \{0,1\}^\kappa \times \{0,1\}^n \to \{0,1\}^n, where \kappa is the key length. The family E is a PRP if for every probabilistic polynomial-time distinguisher D, the distinguishing advantage

\left| \Pr[D^{E_k(\cdot)}(1^\kappa) = 1] - \Pr[D^{P(\cdot)}(1^\kappa) = 1] \right|

is negligible in \kappa, with k chosen uniformly at random from \{0,1\}^\kappa and P a uniformly random permutation from the set of all bijections on \{0,1\}^n. Here, the superscript notation D^{E_k(\cdot)} indicates that D has oracle access to the function E_k, defined as E_k(x) = E(k, x). Typically, the domain and codomain are both \{0,1\}^n for some block length n, with the security parameter \kappa \geq n to ensure the key space is sufficiently large relative to the message space. Each E_k must be a permutation, meaning it is bijective: for every fixed key k, E_k maps \{0,1\}^n onto itself in a one-to-one manner, and there exists an efficient algorithm to compute the inverse E_k^{-1}.^[4] This keyed structure guarantees invertibility under the secret key while preserving the pseudorandom appearance.

Security Notions

The security of a pseudorandom permutation (PRP) is formalized through an indistinguishability experiment between the PRP and a truly random permutation. In this game, an adversary \mathcal{A} is given oracle access to either the PRP E_K, where K is chosen uniformly at random from the key space \{0,1\}^\kappa, or to a random permutation \pi chosen uniformly from the set of all permutations on \{0,1\}^n. The adversary may make up to q adaptive queries to the oracle, receiving the corresponding outputs, and at the end outputs a bit b' where b'=1 if it believes the oracle is the random permutation (b=1) and b'=0 otherwise. The advantage of the adversary is defined as \left| \Pr[b' = 1 \mid b=0] - \Pr[b' = 1 \mid b=1] \right|, and a PRP is secure if this advantage is negligible in the security parameter \kappa for any probabilistic polynomial-time adversary.^[5] A function \mu(\kappa) is negligible if for every constant c > 0, there exists \kappa_0 such that for all \kappa > \kappa_0, \mu(\kappa) < 1/\kappa^c. This ensures that no efficient adversary can distinguish the PRP from random with more than a computationally insignificant probability, even after polynomially many queries.^[5] A stronger variant is the strong pseudorandom permutation (SPRP), where the adversary receives oracle access to both the forward direction E_K and the inverse direction E_K^{-1}. The indistinguishability game proceeds analogously, but now the oracle emulates a random bijection \pi along with its inverse \pi^{-1}, and the adversary outputs b'=1 if it believes the oracles implement the random bijection and inverse, with advantage \left| \Pr[b' = 1 \mid b=0] - \Pr[b' = 1 \mid b=1] \right| remaining negligible. This provides resistance against attacks that exploit knowledge of the inverse mapping.^[5] Security as a PRP implies basic indistinguishability in the forward direction, but SPRP requires additional robustness to inverse queries, making it the standard notion for block ciphers like AES that support efficient decryption. While PRP security suffices for some applications, SPRP ensures comprehensive protection against adaptive chosen-plaintext and chosen-ciphertext attacks up to the query limit.^[5] In terms of query complexity, the security of a PRP or SPRP is analyzed with respect to the number q of oracle queries made by the adversary. Bounds on the distinguishing advantage typically scale with q, such as O(q^2 / 2^n) for ideal random oracles, but for concrete PRPs, the advantage remains negligible as long as q is polynomial in \kappa and subexponential in the block length n. This highlights the importance of limiting query numbers in security reductions to maintain negligible overall advantage.^[5]

Modeling and Constructions

Block Cipher Model

In cryptographic analysis, a pseudorandom permutation (PRP) serves as an idealized model for a block cipher, where for each key, the cipher behaves like a truly random permutation over the message space.^[4] This abstraction assumes that the block cipher's encryption function, under a fixed key, maps plaintext blocks bijectively to ciphertext blocks in a manner indistinguishable from a random permutation to any efficient adversary with access to chosen-plaintext or chosen-ciphertext queries.^[6] Such modeling is crucial for proving the security of higher-level constructions, such as modes of operation (e.g., CBC or GCM), where the PRP assumption enables reductions showing that if the mode is insecure, then the underlying block cipher must be distinguishable from a random permutation.^[7] The PRP model was formalized in the seminal work of Luby and Rackoff, who introduced pseudorandom permutations as a theoretical foundation for block ciphers, replacing the impractical idealization of truly random permutations per key with computationally feasible approximations.^[4] This formalization built on earlier notions but provided the first rigorous framework for constructing and analyzing secure permutations from pseudorandom functions, emphasizing security against adaptive chosen-plaintext attacks.^[8] Even and Mansour (1997) later extended this paradigm by demonstrating how a single pseudorandom function could underpin a full block cipher construction, further solidifying the PRP's role as a replacement for ideal ciphers in provable security proofs.^[9] Real-world block ciphers can be distinguished from ideal PRPs through cryptanalytic attacks that exploit structural weaknesses, such as differential cryptanalysis, which identifies high-probability input-output differences propagating through the cipher's rounds, or linear cryptanalysis, which approximates the cipher as a linear equation over GF(2) to recover key bits. These attacks violate the PRP security notion by allowing adversaries to detect non-random behavior after fewer queries than the ideal case would permit, highlighting the gap between theoretical models and practical implementations.^[10] Block cipher designs, such as AES, aim to approximate PRP behavior up to the birthday bound of approximately $2^{n/2} queries for an n-bit block size, beyond which collisions in the permutation domain enable distinguishing attacks via the birthday paradox. For AES-128 (n=128), this bound is around $2^{64} queries, guiding the cipher's round count and diffusion properties to resist known attacks within this limit.^[7] In practice, the PRP assumption extends to key-dependent permutations through the key schedule, which derives round subkeys from the master key; the overall family is treated as a collection of independent PRPs, one per key, assuming the schedule produces pseudorandom subkeys that maintain the permutation's indistinguishability across multiple keys.^[4] This multi-key extension supports security analyses in scenarios involving key rotation or related-key attacks, though real schedules must be designed to avoid biases that could correlate permutations across keys.^[11]

Constructions from PRFs

One prominent method for constructing pseudorandom permutations (PRPs) from pseudorandom functions (PRFs) is the Luby-Rackoff construction, which employs Feistel networks with PRFs as round functions.^[4] In this approach, the input plaintext is split into two equal halves, denoted as the left half L_0 and the right half R_0, each of length n bits, for a total block size of $2n bits. For each round r from 1 to the number of rounds, the output halves are computed as L_r = R_{r-1} and R_r = L_{r-1} \oplus F_i(R_{r-1}), where F_i is a keyed PRF with independent keys for each round i. The final output is the concatenation of L_k and R_k after k rounds, and the inverse is obtained by running the network backwards using the same structure due to the self-invertibility of the Feistel design.^[4] The original Luby-Rackoff result proves that a three-round Feistel network (LR3) constructed this way is a secure PRP if the round functions are secure PRFs, meaning no distinguisher making q adaptive queries can distinguish the construction from a random permutation with advantage better than O(q^2 / 2^n).^[4] Extending to four rounds (LR4) yields a strong PRP (SPRP), secure even against chosen-ciphertext queries, with advantage O(q^2 / 2^n).^[4] These bounds hold in the ideal model where the PRFs are indistinguishable from random functions, providing a provable security reduction from the PRF assumption. The standard three- and four-round variants remain foundational for PRP security.^[12] Despite these guarantees, the constructions inherit limitations from the underlying PRF security and the Feistel structure. The quadratic term in the advantage bound implies vulnerability beyond the birthday bound, approximately \sqrt{2^n} queries, where collisions in the PRF outputs enable distinguishing attacks.^[13] Additionally, beyond four rounds, the networks become susceptible to related-key attacks, where an adversary exploiting differences in related keys can recover information about the round keys with advantage exceeding the birthday bound, as demonstrated in analyses of Feistel-based PRPs.^[14] Another construction is the Even-Mansour scheme, which builds a PRP from a single PRF F and two independent n-bit keys K_1, K_2 by computing the output as K_2 \oplus F(K_1 \oplus x) for input x, yielding PRP security with advantage O(q^2 / 2^n) under q queries.^[9] This minimal design contrasts with multi-round Feistel networks but shares the birthday security limitation.^[9]

Connection to Pseudorandom Functions

A pseudorandom function (PRF) is a keyed family of efficiently computable functions F: \{0,1\}^\kappa \times \{0,1\}^m \to \{0,1\}^n such that, for a randomly chosen secret key k \in \{0,1\}^\kappa, the function F_k: \{0,1\}^m \to \{0,1\}^n is computationally indistinguishable from a truly random function chosen uniformly from the set of all such functions, with no requirement that F_k be a permutation. The PRP/PRF switching lemma establishes a direct theoretical link between pseudorandom permutations (PRPs) and PRFs: if E: \{0,1\}^\kappa \times \{0,1\}^n \to \{0,1\}^n is a secure PRP, then for any adversary making at most q queries to E on distinct inputs, the adversary's view is computationally indistinguishable from interacting with a random function from \{0,1\}^n to \{0,1\}^n, with distinguishing advantage at most q(q-1)/2^{n+1}. This holds because the probability that the adversary queries the same input twice under a random permutation is negligible (at most q^2/2^{n+1}), allowing the PRP to emulate a PRF when restricted to distinct inputs. From a security perspective, PRP security implies PRF security, as a PRP is a bijective PRF and the switching lemma bounds the additional advantage from potential repetitions. However, the converse does not hold without further assumptions: a secure PRF need not be invertible or bijective, as it may map multiple inputs to the same output, preventing direct use as a PRP. To achieve PRP security from a PRF, additional structure is required, such as the Luby-Rackoff construction, which builds a PRP using multiple applications of the PRF in a Feistel-like scheme (see "Constructions from PRFs"). Historically, Jacques Patarin's work in the 1990s advanced these connections through analyses of generalized Feistel networks, demonstrating how a single PRF can yield a secure PRP (and even a super pseudorandom permutation secure against adaptive chosen-ciphertext attacks) with provable bounds using the H-coefficient technique for distinguishing advantages.^[15]

Unpredictable Permutations

A pseudorandom permutation (PRP) provides strong security by being indistinguishable from a truly random permutation, but a weaker primitive known as an unpredictable permutation (UP) focuses solely on resistance to prediction of outputs on unqueried inputs. Formally, a family of permutations \Pi = \{\pi_s : \{0,1\}^n \to \{0,1\}^n\}_{s \in \{0,1\}^\lambda} is unpredictable if no efficient adversary can predict \pi_s(x) for a randomly chosen unqueried x after adaptively querying the permutation on polynomially many distinct points.^[16] This security is formalized through a prediction game where the adversary \mathcal{A} interacts with oracles for the forward permutation \pi_s and its inverse \pi_s^{-1}. The adversary makes at most q queries to these oracles on distinct inputs, receiving the corresponding outputs. Subsequently, a challenge input x \notin Q (where Q is the set of queried inputs) is selected uniformly at random from the domain excluding Q, and the adversary outputs a guess y' for \pi_s(x). The adversary wins if y' = \pi_s(x). The advantage of \mathcal{A} is defined as \Pr[\mathcal{A} \text{ wins}] - 2^{-n}, and \Pi is (t, q, \epsilon)-unpredictable if for all adversaries running in time at most t, the advantage is at most \epsilon. For cryptographic security, \epsilon must be negligible in the security parameter \lambda.^[16] Unpredictable permutations are implied by PRPs, as the indistinguishability property prevents any efficient prediction of outputs, but the converse does not hold: there exist UPs that are distinguishable from random permutations yet remain unpredictable. This weaker guarantee suffices for certain applications like message authentication codes, where full pseudorandomness is unnecessary.^[17] The concept of unpredictability originated in the 1980s work on pseudorandom functions and one-way functions, notably by Goldreich, Goldwasser, and Micali, who introduced it for functions in the context of constructing pseudorandom generators and stream ciphers from weaker assumptions. The notion was later extended to permutations in analyses of block cipher constructions, such as Feistel networks.^[16] As an example, the output distribution of a one-way permutation paired with a random string via the Goldreich-Levin construction—specifically, (f(x), \langle x, r \rangle) where f is a one-way permutation, x is random, and r is a random string—yields an unpredictable function under the assumption that f is one-way, as predicting the hardcore bit \langle x, r \rangle given f(x) and r is hard. This illustrates how one-wayness can imply unpredictability in related settings.

Applications

In Symmetric Cryptography

Pseudorandom permutations (PRPs) form the foundational building blocks for symmetric encryption schemes, primarily through their role as block ciphers. In standard modes of operation such as Cipher Block Chaining (CBC) and Counter (CTR), the overall security of the encryption reduces to the PRP assumption on the underlying block cipher. For instance, in CTR mode, the block cipher generates a pseudorandom keystream via successive encryptions of counter values, which is then XORed with the plaintext blocks; the resulting scheme achieves indistinguishability under chosen-plaintext attack (IND-CPA) security with advantage approximately equal to the PRP distinguishing advantage plus a birthday term q(q-1)/2^{n+1}, where q is the number of blocks and n is the block size. Similarly, CBC mode chains encryptions by XORing each plaintext block with the previous ciphertext before applying the block cipher, providing IND-CPA security under the same PRP assumption, again limited by the birthday bound due to potential collisions in the permutation outputs.^[18] In contrast, Electronic Codebook (ECB) mode applies the block cipher independently to each plaintext block without chaining. While PRP security implies one-wayness under chosen-plaintext attack (OW-CPA) for ECB, it does not provide semantic security (IND-CPA) due to pattern leakage from identical ciphertexts for repeated plaintext blocks, failing even for small q if the adversary chooses messages with repeats. Without repeats, security is further limited to q << 2^{n/2}, as the birthday paradox enables collisions that reveal statistical patterns, allowing distinguishability from ideal encryption; beyond this bound, the probability of collisions approaches 1, compromising security. This limitation arises from the birthday paradox, where with roughly 2^{n/2} blocks, two plaintexts are likely to map to the same ciphertext under a random permutation, but ECB's deterministic nature exacerbates pattern leakage even earlier if repeated blocks occur.^[19]^[20] For keyed encryption of multi-block messages, the PRP's key serves as the master key for the block cipher, with modes deriving effective subkey behaviors through iterative applications: in CBC, each block's encryption incorporates prior outputs as implicit subkey modifications via XOR, while CTR uses the key to expand counters into independent keystream blocks without direct subkey derivation. This allows secure handling of arbitrary-length messages under the single PRP key, provided the total blocks remain below the birthday bound to avoid collision risks.^[18] A prominent example is the Advanced Encryption Standard (AES), which is designed and analyzed as an approximate PRP with 128-bit blocks. Cryptanalytic efforts, including differential and linear attacks, have not broken the PRP assumption; the best known distinguishers are generic attacks achieving only 2^{64} complexity for AES-128, far below full breaks, confirming that AES maintains PRP security against known attacks up to its birthday bound.^[21]^[2] Hybrid constructions combine PRPs with hash functions to achieve authenticated encryption, providing both confidentiality and integrity. In the Galois/Counter Mode (GCM), the block cipher operates in CTR mode for encryption under the PRP assumption, while a universal hash function (GHASH) over a finite field authenticates the ciphertext and associated data; the scheme proves secure as an authenticated encryption with associated data (AEAD) primitive, with privacy and authenticity bounds reducing to the PRP security plus hash collision probability, enabling efficient protection up to roughly 2^{64} blocks for 128-bit PRPs.^[22]

In Protocol Design

Pseudorandom permutations (PRPs) play a crucial role in key derivation functions (KDFs) within cryptographic protocols, enabling the expansion of short master keys into multiple longer pseudorandom keys while maintaining security. In blockcipher-based KDFs, a PRP such as AES is employed in counter mode to generate distinct keys by encrypting non-repeating nonces, allowing derivation of up to $2^n keys for an n-bit block size without relying on the traditional PRP-to-PRF switching argument. This approach ensures security in the unique-key model, where keys are random but distinct, with unpredictability preserved up to roughly q < 2^{n/2} queries, and an advantage bound of \epsilon + b(b-1)2^{-n} \cdot q / (1 - b^2 (q-1) 2^{-n}) for block size b. For instance, the XAES-256-GCM construction uses an AES-256-based CMAC with nonces to derive 256-bit keys, achieving security against up to $2^{80} distinct nonces in practice.^[23] In protocols relying on random oracles, PRPs can model permutation-based oracles to instantiate hash functions for commitments and padding, enhancing provable security without full random oracle assumptions. For protocols like OAEP padding in RSA encryption, analyses explore replacing random oracles with pseudorandom primitives, including PRPs, to achieve chosen-ciphertext security in the standard model, though direct PRP instantiations focus on non-malleable properties derived from the underlying trapdoor permutation. This modeling ensures that commitments remain binding and hiding, as PRPs provide indistinguishable permutations from random ones, supporting the all-but-one lossy property needed for secure padding.^[24] PRPs facilitate the simulation of random permutations in zero-knowledge proof systems, particularly through Fiat-Shamir transformations that leverage ideal permutations for challenge generation. In the duplex sponge Fiat-Shamir (DSFS) variant, an ideal PRP serves as the core permutation in a sponge construction to transform interactive proofs into non-interactive zero-knowledge arguments, minimizing permutation calls to approximately $1/r \cdot (\delta + \sum \ell_P(i)) for absorption phases, where r is the rate and \ell_P(i) denotes message lengths. This approach supports sigma protocols and multi-round public-coin interactive proofs, with soundness error bounded by \epsilon_{srIP}(t) + 25t^2 / |\Sigma|^c and zero-knowledge error by z_{IP} + t / |\Sigma|^{\min\{\delta, c\}} + t \cdot \sum \lceil \ell_V(i)/r \rceil / |\Sigma|^{r+c}, assuming state-restoration security of the underlying interactive proof. Implementations using PRPs like Keccak or Poseidon demonstrate practical efficiency for elliptic curve or field-based proofs.^[25] In secure multi-party computation (MPC), PRPs are integral to Yao's garbled circuits protocol, where they encrypt wire labels to ensure the indistinguishability of garbled tables from random values, preserving privacy during circuit evaluation. The garbler (P1) uses a PRP, such as AES implemented as a PRF, to generate garbled rows for each gate: for an AND gate, the entry e_{v_a, v_b} = H(k_{v_a}^a \| k_{v_b}^b \| i) \oplus k_{v_c}^c \oplus (v_a \cdot v_b) \Delta, where H is the PRP-derived function, k are wire keys, i indexes the gate, and \Delta is a global offset to randomize labels. This construction allows the evaluator (P2) to decrypt only the path corresponding to their input via oblivious transfer, with security against semi-honest adversaries relying on the PRP's pseudorandomness to make unauthorized decryptions yield random outputs. For malicious security, extensions like cut-and-choose check multiple garbled circuits, with PRPs ensuring no information leakage even under tampering attempts.^[26] Emerging applications of PRPs address post-quantum considerations, with lightweight PRP-based ciphers like PRINCE undergoing analysis for quantum resistance as of 2025 standards. PRINCE, constructed via the FX scheme with an \alpha-reflection property, achieves post-quantum security in the Quantum Ideal Cipher Model (QICM), secure against adversaries making q_C classical and q_Q quantum queries, with advantage at most $4(q_C \sqrt{q_Q} + q_Q \sqrt{q_C}) \cdot 2^{-(m+n)/2} for key size n and block size m when q_C \ll 2^n, or q_Q^2 \cdot 2^{-m} otherwise. These bounds match known quantum attacks like Grover's search and BHT collision-finding, confirming PRINCE's viability for quantum-safe symmetric protocols without requiring doubled key sizes beyond standard recommendations. Quantum resource estimations further validate its efficiency, with circuit depths suitable for near-term quantum devices.^[27]

References

[1]
Cryptography - Pseudo-Random Permutations
Pseudo-random permutations are used to model block ciphers, and are one-to-one functions from {0,1}^n to {0,1}^n, with efficient evaluation.
[2]
[PDF] Notes #7: Pseudorandom Permutations
In these notes we introduce and briefly study the concept of a pseudorandom permutation (PRP). This formalizes a notions of security that one can reasonably ...
[3]
[PDF] Lecture 15 1 Pseudorandom Functions and Permutations
We can define an analogous notion of a pseudorandom permutation (PRP). Here, we con- sider functions P : {0, 1}k x {0, 1}m → {0, 1}m such that, for all s G ...
[4]
How to Construct Pseudorandom Permutations from Pseudorandom ...
We show how to efficiently construct a pseudorandom invertible permutation generator from a pseudorandom function generator.Missing: original paper
[5]
[PDF] Introduction to Modern Cryptography | Yehuda Lindell
put “Introduction to Modern Cryptography” in the subject line. Page 7. vii ... Pseudorandom permutation, 94–95, 201,. 243 block cipher as, 159–161.
[6]
[PDF] Block Ciphers/Pseudorandom Permutations
Definition: Pseudorandom Permutation is exactly the same as a Pseudorandom Function, except for every key 𝑘, 𝐹𝑘 must be a permutation and it must be ...
[7]
[PDF] Chapter 3 Pseudorandom Functions
Pseudorandom functions (PRFs) are central tools in protocol design, especially for shared-key cryptography, and can model block ciphers.
[8]
[PDF] On the Construction of Pseudo-Random Permutations: Luby-Rackoff ...
Luby and Rackoff [26] showed a method for constructing a pseudo-random permutation from a pseudo-random function. The method is based on composing four (or ...
[9]
A construction of a cipher from a single pseudorandom permutation
Jul 2, 1996 · A construction of a cipher from a single pseudorandom permutation. Published: June 1997. Volume 10, pages 151–161, (1997); Cite this ...
[10]
[PDF] Block ciphers, pseudorandom functions and permutations
The total length of all queries. behavior of its random instance is computationally indistinguishable from that of a random permutation.
[11]
[PDF] A Security Analysis of Key Expansion Functions Using ... - Hal-Inria
Nov 22, 2016 · The extraction step generates a uniformly random or pseudorandom seed key from the master key that may be an output of an imperfect physical ...
[12]
On the Construction of Pseudo-Random Permutations: Luby-Rackoff ...
Luby and Rackoff showed a method for constructing a pseudo-random permutation from a pseudo-random function. The method is based on composing four (or three for ...Missing: original | Show results with:original
[13]
[PDF] Luby-Rackoff Ciphers from Weak Round Functions?
In par- ticular, to prove the security of the original three-round Luby-Rackoff cipher it is enough to prove – the purely information-theoretic result – that ...
[14]
[PDF] A Theoretical Treatment of Related-Key Attacks: RKA-PRPs, RKA ...
We show that there are inherent limitations to the security one can achieve against related-key attacks. Namely, we identify some relatively simple classes Φ of ...
[15]
How to Construct Pseudorandom and Super ... - SpringerLink
May 18, 2001 · In this paper we will solve two open problems concerning pseudorandom permutations generators. 1. We will see that it is possible to obtain ...
[16]
[PDF] Feistel Networks made Public, and Applications
Feb 11, 2007 · [27] M. Luby and C. Rackoff, How to construct pseudo-random permutations from pseudo-random functions, in. SIAM Journal on Computing, Vol. 17 ...<|control11|><|separator|>
[17]
[PDF] Message Authentication Codes from Unpredictable Block Ciphers
Jun 2, 2009 · Question 1 Can one build an efficient variable-input-length MAC from a block cipher which is modeled as an unpredictable permutation (UP) on n- ...
[18]
[PDF] Introduction to cryptology (GBIN8U16) 93 Passive encryption
(Any) good PRP is enough to build a good IND-CPA encryption scheme. ▻ One also gets a lower-bound (cf. supra): security collapses at the birthday bound.
[19]
Question about "ECB mode is OW-CPA secure if block cipher is PRP"
Apr 28, 2024 · I'm reading "Cryptography Made Simple" Theorem 13.4, which states that "ECB mode is OW-CPA secure assuming the underlying block cipher ek acts ...Why shouldn't I use ECB encryption? - Cryptography Stack ExchangeIs the inverse of a secure PRP also a secure PRP?More results from crypto.stackexchange.comMissing: provable | Show results with:provable
[20]
[PDF] 8 Block Cipher Modes of Operation - The Joy of Cryptography
The attacks rely solely on the fact that encryption leaks the length of the plaintexts. 8.3 Security of OFB Mode. In this section we will prove that OFB mode ...
[21]
[PDF] Block Ciphers 3.1 Pseudo - Random Functions (PRF) - USF Crypto
Figure 3.6: Encryption with the ECB mode (middle) compared with a secure mode (right) ... These values have the same puropose: providing semantic security in the ...
[22]
The Security and Performance of the Galois/Counter Mode of ...
The recently introduced Galois/Counter Mode (GCM) of operation for block ciphers provides both encryption and message authentication, using universal hashing.Missing: provable Vjgea
[23]
None
**Paper Summary: Blockcipher-Based Key Derivation without PRP/PRF Switching**
[24]
[PDF] Toward RSA-OAEP without Random Oracles
We show RSA-OAEP is PA-RO when modeling H as a RO if G is a pseudorandom generator and F is both second-input extractable and common-input extractable.
[25]
[PDF] A Fiat–Shamir Transformation From Duplex Sponges
Jul 9, 2025 · We analyze a variant of the Fiat–Shamir transformation based on an ideal permutation. The transformation relies on the popular duplex sponge ...
[26]
[PDF] A Pragmatic Introduction to Secure Multi-Party Computation
3.1 Yao's Garbled Circuits Protocol. Yao's Garbled Circuits protocol (GC) is the most widely known and celebrated. MPC technique. It is usually seen as best ...
[27]
Quantum resource estimation of PRINCE and Midori Block Ciphers
In this paper, the symmetric key cryptographic algorithms, PRINCE and Midori block ciphers are converted into the quantum circuit which will be used for ...