18 Nov 2026, Wed

Researchers Release New Study on Separating Pseudorandom Codes from Quantum Random Oracles

A new paper recently submitted to the Cryptology ePrint Archive explores the intricate boundaries between cryptography, error-correcting codes, and quantum mechanics, shedding light on the fundamental limits of constructing certain cryptographic primitives. Authored by Nico Döttling and Anne Müller from the Helmholtz Center for Information Security alongside Mahesh Sreekumar Rajasree from the University of Warsaw, the research paper—designated as Paper 2026/2774—is titled "Separating Pseudorandom Codes from Quantum Random Oracles." The work delves into the complex nature of pseudorandom codes (PRCs), examining how they behave when transitioned from classical computing frameworks into the realm of quantum computation and quantum information.

At the heart of the research is the concept of pseudorandom codes, which are unique cryptographic objects designed to achieve two goals that typically conflict with one another: robust resilience to noise and computational indistinguishability from genuinely random strings. In classical cryptography, ensuring that a string can withstand transmission over a noisy channel usually requires specific algebraic or combinatorial structures that make the data predictable or distinguishable to an observer with unlimited computational power. Conversely, making a string appear completely random and indistinguishable from uniform noise typically destroys the structured redundancy required to recover from errors. PRCs successfully reconcile these competing demands, making them a fascinating subject of study within theoretical cryptography.

Despite their theoretical appeal, recent academic work has demonstrated significant limitations regarding how these codes can be built. Specifically, researchers have previously shown that classical symmetric-key pseudorandom codes operating over binary alphabets cannot be constructed from minimal cryptographic assumptions—such as standard one-way functions—through the use of black-box reductions. Black-box reductions are a foundational technique in complexity theory and cryptography, serving as a way to prove security by showing that if an adversary can break a constructed scheme, that same adversarial algorithm can be used as a black box to break the underlying foundational assumption. The inability to construct classical PRCs via black-box reductions from one-way functions established a major barrier in classical cryptography.

Driven by these prior findings, the authors of Paper 2026/2774 set out to revisit this fundamental question within the context of the quantum era. As quantum computers and quantum information protocols continue to advance, cryptographic assumptions must be re-evaluated to ensure they hold against adversaries armed with quantum algorithms. The research team first investigated pseudorandom codes that feature classical codewords while allowing for quantum algorithms and quantum adversaries.

Through rigorous analysis, the researchers proved that symmetric-key pseudorandom codes that are robust against Bernoulli noise—a standard probabilistic noise model where each bit or symbol has an independent chance of being flipped or corrupted—admit no black-box construction from quantum random oracles. Because quantum random oracles serve as an idealized model for quantum-secure cryptographic primitives, this result directly implies that such codes cannot be built from quantum-secure one-way functions via black-box reductions either. This key finding establishes a significant theoretical milestone: the classical black-box barrier that has long hindered the construction of pseudorandom codes not only persists in the quantum computational setting but remains firmly intact, even when both the adversary and the construction mechanisms are permitted to leverage quantum capabilities.

Faced with this persistent separation barrier when dealing with classical codewords under quantum scrutiny, the research team shifted their perspective to explore a broader and more native quantum cryptographic paradigm: the notion of quantum pseudorandom codes, or QPRCs. In this fully quantum setting, the codewords themselves are no longer classical bit strings but are instead complex quantum states. Furthermore, the security requirement is redefined so that these quantum states are computationally indistinguishable from Haar-random states, which are the quantum mechanical equivalent of uniformly distributed random states over a Hilbert space.

Building upon this novel formulation, the authors transitioned from negative impossibility results to a series of notable positive results, outlining several conditions under which quantum pseudorandom codes can indeed be successfully constructed. First, by assuming the existence of quantum-secure one-way functions, the research team constructed QPRCs that offer security against a single encoding query. These codes allow for multiple copies of the challenge state to be evaluated and are capable of tolerating an error rate that matches the capacity of any classical uniquely decodable binary error-correcting code when subjected to either a dephasing channel or a bit-flip channel.

Expanding further into different query models and error profiles, the researchers also examined existing work in the field. They demonstrated that pseudorandom function services featuring proofs of destruction, a concept previously introduced by Behera and colleagues at the Theory of Cryptography Conference (TCC) in 2023, can be effectively extended. By building on this prior foundation, the authors constructed a zero-bit quantum pseudorandom code that is secure against multiple encoding queries. This particular construction exhibits remarkable resilience, as it can tolerate an unbounded number of phase errors, though it remains restricted to handling only a constant number of bit-flip errors.

In their final major contribution, the researchers looked at even stronger cryptographic foundations. Assuming the existence of quantum-secure single-query pseudorandom states, commonly abbreviated as 1PRS, the authors successfully constructed single-query, single-copy quantum pseudorandom codes. These advanced codes are robust enough to tolerate arbitrary Pauli noise up to the full decoding radius of a standard quantum error-correcting code that relies on unique decoding. This result bridges the gap between quantum error correction—a discipline dedicated to protecting fragile quantum information from environmental decoherence—and quantum cryptography, which seeks to generate computational pseudorandomness and security guarantees.

The paper provides a comprehensive theoretical roadmap for understanding how noise and pseudorandomness interact in a quantum world. By confirming that the classical barriers to building pseudorandom codes extend to quantum random oracles, while simultaneously carving out new pathways via quantum states and advanced cryptographic assumptions, Döttling, Müller, and Rajasree have mapped out critical boundaries for future research in post-quantum cryptography and quantum information theory.

Leave a Reply

Your email address will not be published. Required fields are marked *