Quantum Separation of Pseudorandom Unitaries, Isometries, and Function-Like States Confirms Non-Equivalence

The quest to build secure communication systems relies on mathematical objects that mimic random processes, but function deterministically, and recent research explores these concepts within the realm of quantum computing. Aditya Gulati from University of California, Santa Barbara, Yao-Ting Lin, also from University of California, Santa Barbara, and Tomoyuki Morimae from Yukawa Institute for Theoretical Physics, Kyoto University, alongside Shogo Yamada, demonstrate fundamental differences between three key quantum analogues of classical pseudorandom functions, pseudorandom unitaries, pseudorandom isometries, and pseudorandom function-like states. Their work establishes that these objects are not interchangeable, proving it is impossible to build one from another using simple, ‘black-box’ constructions. This separation is crucial because it clarifies the landscape of quantum cryptographic primitives and guides the development of more robust and efficient quantum security protocols, revealing which building blocks offer genuinely distinct capabilities. The team achieves this separation by constructing a specific quantum oracle, effectively creating a test that distinguishes between these different types of quantum processes.

Quantum Pseudorandomness, Unitaries, and Isometries Differ

Pseudorandom functions represent a fundamental building block in classical cryptography. However, establishing their quantum equivalents remains a challenge, despite the potential for applications including symmetric-key encryption, message authentication, commitments, and multiparty computations. Pseudorandom unitaries (PRUs) and pseudorandom isometries (PRIs) are two proposed quantum analogues of these functions. This work establishes a clear separation between PRUs, PRIs, and pseudorandom function-like states, demonstrating that these objects are not polynomially equivalent. Specifically, the researchers prove that any efficient algorithm capable of distinguishing between a PRI and a pseudorandom function-like state can also efficiently distinguish between a PRU and a pseudorandom function-like state. This result clarifies the relationships between these quantum primitives and provides insights into their potential for cryptographic applications, contributing to a more nuanced understanding of quantum cryptography and guiding the development of secure quantum protocols.

Distinguishing Quantum Pseudorandom State Generators and Unitaries

The study investigates the relationships between pseudorandom unitaries (PRUs), pseudorandom isometries (PRIs), and pseudorandom function-like state generators (PRFSGs), quantum analogues of classical pseudorandom functions. Researchers aimed to determine if these quantum primitives are equivalent, addressing a fundamental open question in quantum cryptography. To explore this, the team focused on proving the impossibility of constructing certain primitives from others, specifically ruling out “black-box constructions”, methods where one primitive can be built from another without detailed knowledge of its internal workings. The research employed a novel approach centered around constructing a specialized “separation oracle,” a quantum algorithm designed to distinguish between the outputs of different cryptographic primitives, effectively demonstrating that one cannot be built from another.

The team meticulously engineered this oracle to exploit subtle differences in the mathematical properties of PRUs, PRIs, and PRFSGs, allowing them to prove negative results regarding black-box constructions. Specifically, they demonstrated that non-adaptive PRUs with a limited number of ancilla qubits, specifically, O(log λ), cannot be constructed in a black-box manner from PRFSGs. Further investigations revealed that PRIs with a limited “stretch” cannot be constructed from PRFSGs via a black-box method. Additionally, PRIs with short stretch also cannot be constructed from PRIs with large stretch using a black-box approach. These findings demonstrate that different types of PRIs are not interchangeable, and that constructing more complex PRIs from simpler ones is not always possible.

PRU, PRI, and PRFSG Separations Demonstrated

This work presents significant advances in understanding the relationships between quantum cryptographic primitives, specifically pseudorandom unitaries (PRUs), pseudorandom isometries (PRIs), and pseudorandom function-like state generators (PRFSGs). Researchers addressed the open question of whether these quantum analogs of pseudorandom functions are equivalent, by demonstrating limitations in constructing some of these primitives from others. The team proved that a black-box construction of non-adaptive PRUs with O(log λ) ancilla qubits from PRFSGs is impossible. The proof involves constructing a specific “separation oracle” and an adversary that can distinguish between a genuine PRU and one constructed from a PRFSG. The researchers achieved these separations by designing adversaries based on quantum singular value transformations, a technique that could prove useful for establishing other separations in quantum cryptography. These results contribute to a more nuanced understanding of the landscape of quantum cryptographic primitives and their interrelationships, paving the way for the development of more secure and efficient quantum cryptographic protocols.

Quantum PRF and PRU Separations Proven

This research significantly advances the understanding of fundamental cryptographic primitives in the quantum realm, specifically exploring the relationships between pseudorandom functions (PRFs) and their quantum analogues. Scientists have demonstrated that certain direct constructions between these primitives are impossible, ruling out the existence of black-box constructions of pseudorandom unitaries (PRUs) and pseudorandom isometries (PRIs) from pseudorandom function-like state generators (PRFSGs). These negative results clarify the landscape of quantum cryptography by establishing clear separations between these important building blocks. The team achieved these separations through the construction of a carefully designed unitary oracle, allowing them to prove that certain constructions are not possible without making additional assumptions.

The researchers acknowledge that their current results focus on specific scenarios and that extending these separations to cases with different query access to the oracle requires further investigation. The findings contribute to a more nuanced understanding of the security foundations of quantum cryptography and guide the development of more robust and efficient cryptographic protocols. The techniques developed in this research, particularly the use of singular value transformations, are expected to be valuable for establishing further separations between quantum cryptographic primitives.