Pseudorandom functions (PRFs) are one of the most fundamental primitives in classical cryptography. On the other hand, in quantum cryptography, it is possible that PRFs do not exist but their quantum analogues could exist, and still enabling many applications including SKE, MACs, commitments, multiparty computations, and more. Pseudorandom unitaries (PRUs) [Ji, Liu, Song, Crypto 2018], pseudorandom isometries (PRIs) [Ananth, Gulati, Kaleoglu, Lin, Eurocrypt 2024], and pseudorandom function-like state generators (PRFSGs) [Ananth, Qian, Yuen, Crypto 2022] are major quantum analogs of PRFs. PRUs imply PRIs, and PRIs imply PRFSGs, but the converse implications remain unknown. An important open question is whether these natural quantum analogues of PRFs are equivalent. In this paper, we partially resolve this question by ruling out black-box constructions of them: 1. There are no black-box constructions of $O(\logλ)$ -ancilla PRUs from PRFSGs. 2. There are no black-box constructions of $O(\logλ)$ -ancilla PRIs with $O(\logλ)$ stretch from PRFSGs. 3. There are no black-box constructions of $O(\logλ)$ -ancilla PRIs with $O(\logλ)$ stretch from PRIs with $Ω(λ)$ stretch. Here, $O(\logλ)$ -ancilla means that the generation algorithm uses at most $O(\logλ)$ ancilla qubits. PRIs with $s(λ)$ stretch is PRIs mapping $λ$ qubits to $λ+s(λ)$ qubits. To rule out the above black-box constructions, we construct a unitary oracle that separates them. For the separations, we construct an adversary based on the quantum singular value transformation, which would be independent of interest and should be useful for other oracle separations in quantum cryptography.Pseudorandom functions (PRFs) are one of the most fundamental primitives in classical cryptography. On the other hand, in quantum cryptography, it is possible that PRFs do not exist but their quantum analogues could exist, and still enabling many applications including SKE, MACs, commitments, multiparty computations, and more. Pseudorandom unitaries (PRUs) [Ji, Liu, Song, Crypto 2018], pseudorandom isometries (PRIs) [Ananth, Gulati, Kaleoglu, Lin, Eurocrypt 2024], and pseudorandom function-like state generators (PRFSGs) [Ananth, Qian, Yuen, Crypto 2022] are major quantum analogs of PRFs. PRUs imply PRIs, and PRIs imply PRFSGs, but the converse implications remain unknown. An important open question is whether these natural quantum analogues of PRFs are equivalent. In this paper, we partially resolve this question by ruling out black-box constructions of them: 1. There are no black-box constructions of $O(\logλ)$-ancilla PRUs from PRFSGs. 2. There are no black-box constructions of $O(\logλ)$-ancilla PRIs with $O(\logλ)$ stretch from PRFSGs. 3. There are no black-box constructions of $O(\logλ)$-ancilla PRIs with $O(\logλ)$ stretch from PRIs with $Ω(λ)$ stretch. Here, $O(\logλ)$-ancilla means that the generation algorithm uses at most $O(\logλ)$ ancilla qubits. PRIs with $s(λ)$ stretch is PRIs mapping $λ$ qubits to $λ+s(λ)$ qubits. To rule out the above black-box constructions, we construct a unitary oracle that separates them. For the separations, we construct an adversary based on the quantum singular value transformation, which would be independent of interest and should be useful for other oracle separations in quantum cryptography.

arXiv:2510.04486Oct 6, 20250 citations

Quantum Pseudorandom Error-Correcting Codes

Min-Hsiu Hsieh, Shogo Yamada

Pseudorandom error-correcting codes (PRCs), introduced by Christ and Gunn [CRYPTO 2024], are classical error-correcting codes whose codewords are computationally indistinguishable from uniformly random strings. We initiate the study of quantum analogues of PRCs. We define quantum pseudorandom error-correcting codes (QPRCs). Assuming that Learning Parity with Noise (LPN) is hard for $2^{O(\sqrt{n})}$ -time quantum algorithms, we construct QPRCs whose encodings are indistinguishable from Haar-random isometries. We call these pseudorandom isometric error-correcting codes (PRICs), and our construction is robust to all $o(n \frac{\log \log n}{\log n})$ -local quantum noise, where $n$ is the number of physical qubits. Under the same assumption, we also construct QPRCs whose encodings are indistinguishable from the completely depolarizing channel and that are robust to all $αn$ -local quantum noise for some constant $α>0$ . The latter QPRCs give a direct quantum analogue of classical PRCs. To construct PRICs, we develop two technical ingredients of independent interest. First, we introduce a new classical cryptographic primitive which we call pseudorandom functional error-correcting codes (PRFCs) and construct them under the same LPN assumption. Second, we develop a new efficient decoding procedure within the codeword-stabilized (CWS) framework introduced in [Cross, Smith, Smolin, and Zeng, IEEE ISIT 2008], which is a generic framework for constructing quantum error-correcting codes by combining (possibly nonlinear) classical error-correcting codes and graphs. This resolves the open problem of finding a general method for efficiently decoding such CWS codes based on nonlinear classical codes, raised in [Li, Dumer, Grassl, and Pryadko, Physical Review A 2010].Pseudorandom error-correcting codes (PRCs), introduced by Christ and Gunn [CRYPTO 2024], are classical error-correcting codes whose codewords are computationally indistinguishable from uniformly random strings. We initiate the study of quantum analogues of PRCs. We define quantum pseudorandom error-correcting codes (QPRCs). Assuming that Learning Parity with Noise (LPN) is hard for $2^{O(\sqrt{n})}$-time quantum algorithms, we construct QPRCs whose encodings are indistinguishable from Haar-random isometries. We call these pseudorandom isometric error-correcting codes (PRICs), and our construction is robust to all $o(n \frac{\log \log n}{\log n})$-local quantum noise, where $n$ is the number of physical qubits. Under the same assumption, we also construct QPRCs whose encodings are indistinguishable from the completely depolarizing channel and that are robust to all $αn$-local quantum noise for some constant $α>0$. The latter QPRCs give a direct quantum analogue of classical PRCs. To construct PRICs, we develop two technical ingredients of independent interest. First, we introduce a new classical cryptographic primitive which we call pseudorandom functional error-correcting codes (PRFCs) and construct them under the same LPN assumption. Second, we develop a new efficient decoding procedure within the codeword-stabilized (CWS) framework introduced in [Cross, Smith, Smolin, and Zeng, IEEE ISIT 2008], which is a generic framework for constructing quantum error-correcting codes by combining (possibly nonlinear) classical error-correcting codes and graphs. This resolves the open problem of finding a general method for efficiently decoding such CWS codes based on nonlinear classical codes, raised in [Li, Dumer, Grassl, and Pryadko, Physical Review A 2010].

quant-pharXiv:2609.38986Oct 1, 20260 citations

Real-Valued Somewhat-Pseudorandom Unitaries

Zvika Brakerski, Nir Magrafta

arXiv:2403.16704Lecture notes in computer scienceNov 27, 20248 citations

Simple Constructions of Linear-Depth t-Designs and Pseudorandom Unitaries

Tony Metger, Alexander Poremba, Makrand Sinha +1 more

Uniformly random unitaries, i.e. unitaries drawn from the Haar measure, have many useful properties, but cannot be implemented efficiently. This has motivated a long line of research into random unitaries that “look” sufficiently Haar random while also being efficient to implement. Two different notions of derandomisation have emerged: $t$ -designs are random unitaries that information-theoretically reproduce the first $t$ moments of the Haar measure, and pseudorandom unitaries (PRUs) are random unitaries that are computationally indistinguishable from Haar random. In this work, we take a unified approach to constructing $t$ -designs and PRUs. For this, we introduce and analyse the “ $PFC$ ensemble”, the product of a random computational basis permutation $P$ , a random binary phase operator $F$ , and a random Clifford unitary $C$ . We show that this ensemble reproduces exponentially high moments of the Haar measure. We can then derandomise the $PFC$ ensemble to show the following: •Linear-depth $t$ -designs. We give the first construction of a (diamond-error) approximate $t$ -design with circuit depth linear in $t$ . This follows from the $PFC$ ensemble by replacing the random phase and permutation operators with their $2t$ -wise independent counterparts. •Non-adaptive PRUs. We give the first construction of PRUs with non-adaptive security, i.e. we construct unitaries that are indistinguishable from Haar random to polynomial-time distinguishers that query the unitary in parallel on an arbitary state. This follows from the $PFC$ ensemble by replacing the random phase and permutation operators with their pseudorandom counterparts. •Adaptive pseudorandom isometries. We show that if one considers isometries (rather than unitaries) from $n$ to $n+\omega(\log n)$ qubits, a small modification of our PRU construction achieves adaptive security, i.e. even a distinguisher that can query the isometry adaptively in sequence cannot distinguish it from Haar random isometries. This gives the first construction of adaptive pseudorandom isometries. Under an additional conjecture, this proof also extends to adaptive PRUs.Uniformly random unitaries, i.e. unitaries drawn from the Haar measure, have many useful properties, but cannot be implemented efficiently. This has motivated a long line of research into random unitaries that “look” sufficiently Haar random while also being efficient to implement. Two different notions of derandomisation have emerged:$t$-designs are random unitaries that information-theoretically reproduce the first$t$moments of the Haar measure, and pseudorandom unitaries (PRUs) are random unitaries that are computationally indistinguishable from Haar random. In this work, we take a unified approach to constructing$t$-designs and PRUs. For this, we introduce and analyse the “$PFC$ensemble”, the product of a random computational basis permutation$P$, a random binary phase operator$F$, and a random Clifford unitary$C$. We show that this ensemble reproduces exponentially high moments of the Haar measure. We can then derandomise the$PFC$ensemble to show the following: •Linear-depth$t$-designs. We give the first construction of a (diamond-error) approximate$t$-design with circuit depth linear in$t$. This follows from the$PFC$ensemble by replacing the random phase and permutation operators with their$2t$-wise independent counterparts. •Non-adaptive PRUs. We give the first construction of PRUs with non-adaptive security, i.e. we construct unitaries that are indistinguishable from Haar random to polynomial-time distinguishers that query the unitary in parallel on an arbitary state. This follows from the$PFC$ensemble by replacing the random phase and permutation operators with their pseudorandom counterparts. •Adaptive pseudorandom isometries. We show that if one considers isometries (rather than unitaries) from$n$to$n+\omega(\log n)$qubits, a small modification of our PRU construction achieves adaptive security, i.e. even a distinguisher that can query the isometry adaptively in sequence cannot distinguish it from Haar random isometries. This gives the first construction of adaptive pseudorandom isometries. Under an additional conjecture, this proof also extends to adaptive PRUs.

arXiv:2404.12647Annual Symposium on Foundations of Computer ScienceOct 27, 202424 citations

On The Simplest Quantum-Secure Block Cipher

Gorjan Alagic, Joseph Carolan, Christian Majenz +1 more

Pseudorandom permutations are ubiquitous in theoretical and applied cryptography. PRPs that offer security even against adversaries making quantum queries are of increasing interest, and used in applications ranging from constructing pseudorandom unitaries to separating SZK from BQP. A successful framework for constructing classically-secure PRPs is the key-alternating Even-Mansour approach, which interleaves applications of public permutations with additions of round keys. The single-round construction is already classically secure in the ideal permutation model (IPM), with added rounds offering improved concrete security. However, in the quantum-query setting, the status of this framework is presently unclear. A simple quantum-query attack based on Simon's algorithm breaks the one-round cipher. For two or more rounds, security is only known against non-adaptive adversaries who must prepare all queries in advance. In this work, we show that the two-round Even-Mansour cipher is information theoretically secure in the IPM against adversaries making polynomially-many adaptive forward and inverse quantum queries to all available oracles. Our proof uses compressed permutation oracles and a specially crafted isometry relating the ideal and real experiments. We also show that this construction is minimal, in the sense that essentially any cipher constructed via a single call to a public permutation is quantumly insecure.Pseudorandom permutations are ubiquitous in theoretical and applied cryptography. PRPs that offer security even against adversaries making quantum queries are of increasing interest, and used in applications ranging from constructing pseudorandom unitaries to separating SZK from BQP. A successful framework for constructing classically-secure PRPs is the key-alternating Even-Mansour approach, which interleaves applications of public permutations with additions of round keys. The single-round construction is already classically secure in the ideal permutation model (IPM), with added rounds offering improved concrete security. However, in the quantum-query setting, the status of this framework is presently unclear. A simple quantum-query attack based on Simon's algorithm breaks the one-round cipher. For two or more rounds, security is only known against non-adaptive adversaries who must prepare all queries in advance. In this work, we show that the two-round Even-Mansour cipher is information theoretically secure in the IPM against adversaries making polynomially-many adaptive forward and inverse quantum queries to all available oracles. Our proof uses compressed permutation oracles and a specially crafted isometry relating the ideal and real experiments. We also show that this construction is minimal, in the sense that essentially any cipher constructed via a single call to a public permutation is quantumly insecure.

quant-pharXiv:2609.40350Oct 1, 20260 citations

O(\logλ)

-ancilla PRUs from PRFSGs. 2. There are no black-box constructions of

O(\logλ)

-ancilla PRIs with

O(\logλ)

stretch from PRFSGs. 3. There are no black-box constructions of

O(\logλ)

-ancilla PRIs with

O(\logλ)

stretch from PRIs with

Ω(λ)

stretch. Here,

O(\logλ)

-ancilla means that the generation algorithm uses at most

O(\logλ)

ancilla qubits. PRIs with

s(λ)

stretch is PRIs mapping

λ

qubits to

λ+s(λ)

qubits. To rule out the above black-box constructions, we construct a unitary oracle that separates them. For the separations, we construct an adversary based on the quantum singular value transformation, which would be independent of interest and should be useful for other oracle separations in quantum cryptography.

2^{O(\sqrt{n})}

-time quantum algorithms, we construct QPRCs whose encodings are indistinguishable from Haar-random isometries. We call these pseudorandom isometric error-correcting codes (PRICs), and our construction is robust to all

o(n \frac{\log \log n}{\log n})

-local quantum noise, where

n

is the number of physical qubits. Under the same assumption, we also construct QPRCs whose encodings are indistinguishable from the completely depolarizing channel and that are robust to all

αn

-local quantum noise for some constant

α>0

. The latter QPRCs give a direct quantum analogue of classical PRCs. To construct PRICs, we develop two technical ingredients of independent interest. First, we introduce a new classical cryptographic primitive which we call pseudorandom functional error-correcting codes (PRFCs) and construct them under the same LPN assumption. Second, we develop a new efficient decoding procedure within the codeword-stabilized (CWS) framework introduced in [Cross, Smith, Smolin, and Zeng, IEEE ISIT 2008], which is a generic framework for constructing quantum error-correcting codes by combining (possibly nonlinear) classical error-correcting codes and graphs. This resolves the open problem of finding a general method for efficiently decoding such CWS codes based on nonlinear classical codes, raised in [Li, Dumer, Grassl, and Pryadko, Physical Review A 2010].

t

-designs are random unitaries that information-theoretically reproduce the first

t

moments of the Haar measure, and pseudorandom unitaries (PRUs) are random unitaries that are computationally indistinguishable from Haar random. In this work, we take a unified approach to constructing

t

-designs and PRUs. For this, we introduce and analyse the “

PFC

ensemble”, the product of a random computational basis permutation

P

, a random binary phase operator

F

, and a random Clifford unitary

C

. We show that this ensemble reproduces exponentially high moments of the Haar measure. We can then derandomise the

PFC

ensemble to show the following: •Linear-depth

t

-designs. We give the first construction of a (diamond-error) approximate

t

-design with circuit depth linear in

t

. This follows from the

PFC

ensemble by replacing the random phase and permutation operators with their

2t

-wise independent counterparts. •Non-adaptive PRUs. We give the first construction of PRUs with non-adaptive security, i.e. we construct unitaries that are indistinguishable from Haar random to polynomial-time distinguishers that query the unitary in parallel on an arbitary state. This follows from the

PFC

ensemble by replacing the random phase and permutation operators with their pseudorandom counterparts. •Adaptive pseudorandom isometries. We show that if one considers isometries (rather than unitaries) from

n

n+\omega(\log n)

qubits, a small modification of our PRU construction achieves adaptive security, i.e. even a distinguisher that can query the isometry adaptively in sequence cannot distinguish it from Haar random isometries. This gives the first construction of adaptive pseudorandom isometries. Under an additional conjecture, this proof also extends to adaptive PRUs.