Quantum pseudorandomness is an emerging research area. Ji, Liu, and Song defined pseudorandom states (PRSs) and pseudorandom unitaries (PRUs) as quantum analogs of pseudorandom generators and pseudorandom functions. A unitary oracle separation result between one-way functions and PRSs/PRUs, established by Kretschmer, suggests that certain quantum primitives may remain secure even if classical cryptography is compromised. This insight has spurred extensive work on quantum pseudorandomness and its applications in quantum cryptography. Many constructions of PRSs have been established under standard assumptions, yet building a secure PRU was a long-standing open problem. This dissertation aims to narrow the gap between PRSs and PRUs and presents results that go beyond PRSs. We introduce Pseudorandom State Scramblers (PRSSs), a new primitive that lies between PRSs and PRUs. A PRSS maps any pure state to a pseudorandom state, a property shared with PRUs but not with PRSs. We present a construction of PRSSs inspired by the well-known Kac’s walk, and in particular, we develop a parallel variant that significantly accelerates the mixing time, enabling an efficient construction. PRSSs support cryptographic tasks not known to be achievable from PRSs alone, including a quantum encryption scheme and a succinct quantum state commitment. Additionally, when suitable classical randomness is provided, our construction exhibits a special dispersing property not known to be satisfied by any existing construction of quantum pseudorandom primitives. Our subsequent work shows that, without asymptotically increasing the number of steps, our construction based on the parallel Kac’s walk yields PRUs with standard or even strong security. The proof builds on a recently developed technique for establishing adaptive security, known as the path-recording method. This result provides an alternative construction of PRUs and further showcases the power of this proof technique. In addition, this dissertation includes two side projects. The first revisits the Hidden Subgroup Problem over ℤn, providing a simplified analysis of a known quantum algorithm using elementary lattice tools. The second establishes a quantum analogue of a classical impossibility result for statistical non-interactive zero-knowledge arguments, showing limitations of black-box reductions under classical-query quantum adversaries.
Quantum pseudorandomness is an emerging research area. Ji, Liu, and Song defined pseudorandom states (PRSs) and pseudorandom unitaries (PRUs) as quantum analogs of pseudorandom generators and pseudorandom functions. A unitary oracle separation result between one-way functions and PRSs/PRUs, established by Kretschmer, suggests that certain quantum primitives may remain secure even if classical cryptography is compromised. This insight has spurred extensive work on quantum pseudorandomness and its applications in quantum cryptography. Many constructions of PRSs have been established under standard assumptions, yet building a secure PRU was a long-standing open problem. This dissertation aims to narrow the gap between PRSs and PRUs and presents results that go beyond PRSs. We introduce Pseudorandom State Scramblers (PRSSs), a new primitive that lies between PRSs and PRUs. A PRSS maps any pure state to a pseudorandom state, a property shared with PRUs but not with PRSs. We present a construction of PRSSs inspired by the well-known Kac’s walk, and in particular, we develop a parallel variant that significantly accelerates the mixing time, enabling an efficient construction. PRSSs support cryptographic tasks not known to be achievable from PRSs alone, including a quantum encryption scheme and a succinct quantum state commitment. Additionally, when suitable classical randomness is provided, our construction exhibits a special dispersing property not known to be satisfied by any existing construction of quantum pseudorandom primitives. Our subsequent work shows that, without asymptotically increasing the number of steps, our construction based on the parallel Kac’s walk yields PRUs with standard or even strong security. The proof builds on a recently developed technique for establishing adaptive security, known as the path-recording method. This result provides an alternative construction of PRUs and further showcases the power of this proof technique. In addition, this dissertation includes two side projects. The first revisits the Hidden Subgroup Problem over ℤn, providing a simplified analysis of a known quantum algorithm using elementary lattice tools. The second establishes a quantum analogue of a classical impossibility result for statistical non-interactive zero-knowledge arguments, showing limitations of black-box reductions under classical-query quantum adversaries.
Abstract. Quantum pseudorandom state generators ( PRSG s) have stimulated exciting developments in recent years. A PRSG , on a fixed initial (e.g., all-zero) state, produces an output state that is computationally indistinguishable from a Haar random state. However, pseudorandomness of the output state is not guaranteed on other initial states. In fact, known PRSG constructions provably fail on some initial states. In this work, we propose and construct quantum pseudorandom state scramblers ( PRSS s), which can produce a pseudorandom state on an arbitrary initial state. In the information-theoretical setting, we obtain a scrambler which maps an arbitrary initial state to a distribution of quantum states that is close to Haar random in total variation distance. As a result, our scrambler exhibits a dispersing property. Loosely, it can span an [Formula: see text]-net of the state space. This significantly strengthens what standard PRSG s can induce, as they may only concentrate on a small region of the state space provided that the average output state approximates a Haar random state. Our PRSS construction develops a parallel extension of the famous Kac’s walk, and we show that it mixes exponentially faster than the standard Kac’s walk. This constitutes the core of our proof. We also describe a few applications of PRSS s. While our PRSS construction assumes a postquantum one-way function, PRSS s are potentially a weaker primitive and can be separated from one-way functions in a relativized world similar to standard PRSG s.
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 Quantum States (PRS) were introduced by Ji, Liu and Song as quantum analogous to Pseudorandom Generators. They are an ensemble of states efficiently computable but computationally indistinguishable from Haar random states. Subsequent works have shown that some cryptographic primitives can be constructed from PRSs. Moreover, recent classical and quantum oracle separations of PRS from One-Way Functions strengthen the interest in a purely quantum alternative building block for quantum cryptography, potentially weaker than OWFs. However, our lack of knowledge of extending or shrinking the number of qubits of the PRS output still makes it difficult to reproduce some of the classical proof techniques and results. Short-PRSs, that is PRSs with logarithmic size output, have been introduced in the literature along with cryptographic applications, but we still do not know how they relate to PRSs. Here we answer half of the question, by showing that it is not possible to shrink the output of a PRS from polynomial to logarithmic qubit length while still preserving the pseudorandomness property, in a relativized way. More precisely, we show that relative to Kretschmer's quantum oracle (TQC 2021) short-PRSs cannot exist (while PRSs exist, as shown by Kretschmer's work).
Quantum computation gives rise to new pseudorandom primitives for states and unitaries, including pseudorandom state generators (PRSGs), pseudorandom function-like state generators (PRFSGs), and pseudorandom unitaries (PRUs). In this paper, we show a full unitary oracle separation between PRFSGs and PRUs.
The separation holds between the strongest state notion and the weakest unitary notion: even adaptively secure, quantum-accessible PRFSGs do not imply non-adaptively secure, forward-only PRUs, even when their implementations are allowed to be non-unitary and use an arbitrary number of ancillary qubits. This reveals a fundamental distinction between pseudorandomness for quantum states and for quantum unitaries.
Our main technical idea is to view a candidate PRU construction with access to state generation oracles as a map from the underlying oracle states to implemented unitaries, and to study the derivatives of this map. These derivatives are inherently low rank, and we exploit this low-rank structure to distinguish the resulting unitaries from truly random ones. We believe this differential perspective may be useful for studying other structural questions about quantum states and unitaries.
Quantum pseudorandomness has found applications in many areas of quantum information, ranging from entanglement theory, to models of scrambling phenomena in chaotic quantum systems, and, more recently, in the foundations of quantum cryptography. Kretschmer (TQC '21) showed that both pseudorandom states and pseudorandom unitaries exist even in a world without classical one-way functions. To this day, however, all known constructions require classical cryptographic building blocks which are themselves synonymous with the existence of one-way functions, and which are also challenging to implement on realistic quantum hardware. In this work, we seek to make progress on both of these fronts simultaneously - by decoupling quantum pseudorandomness from classical cryptography altogether. We introduce a quantum hardness assumption called the Hamiltonian Phase State (HPS) problem, which is the task of decoding output states of a random instantaneous quantum polynomial-time (IQP) circuit. Hamiltonian phase states can be generated very efficiently using only Hadamard gates, single-qubit Z rotations and CNOT circuits. We show that the hardness of our problem reduces to a worst-case version of the problem, and we provide evidence that our assumption is plausibly fully quantum; meaning, it cannot be used to construct one-way functions. We also show information-theoretic hardness when only few copies of HPS are available by proving an approximate t-design property of our ensemble. Finally, we show that our HPS assumption and its variants allow us to efficiently construct many pseudorandom quantum primitives, ranging from pseudorandom states, to quantum pseudoentanglement, to pseudorandom unitaries, and even primitives such as public-key encryption with quantum keys.
We provide the first evidence relative to a classical oracle that pseudorandom unitaries (PRUs) can exist without quantum-computable one-way functions.
To obtain this result, we first prove that five independent random diagonal phase layers interleaved with Hadamard transforms U=F5HF4HF3HF2HF1 form a strong PRU with security under adaptive, controlled access to the unitary, its inverse, transpose, and complex conjugate.
Our main result is that, when the phase layers are implemented using a classical random oracle O, the construction remains secure against uniform BQP adversaries with coherent access to suitable Boolean completions of classical-input $QMA^{PH}^{O}}$ decision problems. Such an adversary can invert (even quantum-computable) one-way functions and solve efficiently verifiable one-way puzzles defined relative to O. Our result therefore provides classical-oracle evidence that PRUs do not imply quantum-computable one-way functions, in the form of a black-box separation.
We substantially strengthen the classical-oracle result of Kretschmer, Qian, and Tal (STOC 2025) by obtaining PRUs secure against these QMA-aided adversaries. Our construction also consists of a simple, efficient circuit that queries a random function, suggesting a route to concrete implementation via the random-oracle heuristic.