In classical cryptography, we rely on pseudorandom functions (PRFs) to generate strings that look like noise but are actually deterministic. In the quantum world, the "gold standard" for randomness is the Haar measure—a way of picking a truly random transformation (unitary) or state from the infinite sea of possibilities in Hilbert space. However, implementing a truly Haar-random operation is exponentially difficult.
The research direction emerging from these papers focuses on quantum pseudorandomness: constructing states and operations that are indistinguishable from Haar-random ones to any observer with polynomial time and energy, but which can be created efficiently. This framework provides the bedrock for "unclonable" cryptography, where the laws of physics—specifically the No-Cloning Theorem—prevent the unauthorized duplication of digital assets.
The Hierarchy of Quantum Randomness
To build a quantum-secure world, researchers have defined a hierarchy of primitives that mimic Haar randomness with increasing complexity.
- Pseudorandom States (PRS): These are ensembles of quantum states that look like random vectors in Hilbert space. Zhengfeng Ji, Fang Song, and Yi-Kai Liu formalized this concept, showing that if you have a quantum-secure one-way function, you can create a state that "fakes" being Haar-random.
- Pseudorandom Unitaries (PRU): These are actual circuits that scramble any input state. For years, it was unclear if PRUs could be built efficiently. Recently, Fermi Ma and Hsin-Yuan Huang proved that PRUs can be constructed from standard cryptographic assumptions using a "path-recording" framework.
- Pseudorandom Isometries (PRI): Bridging the gap between states and unitaries, Prabhanjan Ananth and his colleagues introduced PRIs to allow for "length extension"—stretching a small quantum seed into a much larger, secure quantum state.
The Multi-Copy Security Problem
A unique challenge in quantum cryptography is the "multi-copy" setting. In classical systems, if you can't break a code with one copy of a message, you usually can't break it with ten. In quantum systems, having multiple identical copies of a state allows an adversary to perform quantum tomography or shadow tomography, potentially revealing the "secret" structure of the state.
Prabhanjan Ananth, Alexander Poremba, and Saachi Mutreja have pioneered models where security is defined by the attacker's inability to produce more valid outputs than the number of queries they made. This is crucial for applications like Quantum Money, first envisioned by Scott Aaronson in 2011. If a bank issues five quantum banknotes, a secure system must ensure that an attacker with those five notes cannot use quantum measurements to forge a sixth.
To solve this, Ananth and Eli Goldin developed a "purification compiler" that mathematically transforms single-copy security guarantees into multi-copy ones, ensuring that "unclonable" really means unclonable, even in bulk.
Efficiency through Designs and Permutations
While the theory is robust, the implementation must be efficient. Truly random unitaries require exponential circuit depth, which is impossible for today's hardware. Researchers use unitary $t$-designs—ensembles that match the first $t$ moments of the Haar measure—as a shortcut.
Adam Bouland has shown that we can "lift" classical pseudorandom permutations into quantum pseudorandom unitaries. This allows us to use well-understood classical math to create complex quantum randomness. Similarly, Thomas Schuster and Jonas Haferkamp demonstrated that by "gluing" together small local patches of randomness, we can achieve global pseudorandomness in extremely shallow circuits, making these protocols viable for near-term quantum computers.
A New Foundation for Cryptography
Perhaps the most provocative shift in this field is the idea that we might not need classical One-Way Functions (OWFs) at all. Prabhanjan Ananth, Henry Yuen, and others have argued that Pseudorandom Quantum States (PRS) could be the "minimal" primitive for the quantum era. They showed that you can build complex tools like bit-commitments and multiparty computation using only PRS, suggesting that quantum mechanics provides its own inherent source of cryptographic hardness that is fundamentally different from the mathematical puzzles of the classical world.