NTT Labs rules out simple paths to quantum hardness proofs

Whether useful structured hardness can arise from unstructured assumptions is a fundamental question in complexity and cryptography. The longstanding Bennett-Gill question asks whether NP∩coNP remains hard relative to a random oracle; recently gave a conditional affirmative answer in the classical setting. They establish the quantum analogue: if, then with probability 1 over a random oracle O. This finding is significant because Shor’s algorithms invalidate traditional methods for establishing computational difficulty, while current cryptography doesn’t readily offer provably hard problems for quantum computers.

NP∩coNP Hardness via Random Oracles

Random oracles, essentially black boxes that provide random responses to queries, is a framework for investigating this question, offering computational difficulty without imposing specific algebraic structures. The team’s work builds upon the Bennett-Gill question, which originally asked if NP∩coNP remains hard relative to a random oracle, and extends it to the quantum realm, acknowledging that the quantum version is not merely a classical question recast.

The implications of this work are particularly relevant given that Shor’s algorithms invalidate traditional number-theoretic approaches to establishing hardness. A key distinction lies in the contrast between structured and unstructured sources of hardness; one-way permutations offer a structured path, while injective one-way functions represent an unstructured approach.

Previous research, including work by Blum and Impagliazzo and Rudich, ruled out black-box constructions of hard languages in NP∩coNP from ordinary one-way functions, and Bitansky, Degwekar, and Vaikuntanathan strengthened this barrier to include injective one-way functions and indistinguishability obfuscation. The current research builds on these findings, demonstrating that even with these advanced cryptographic tools, deriving two-sided certification alongside hardness remains difficult.

“These results expose a substantial obstacle to deriving two-sided certification together with hardness from generic cryptographic primitives,” the researchers note. The team’s analysis reveals that the difficulty in establishing quantum hardness is not simply a matter of scaling up classical techniques, but rather requires fundamentally new approaches.

Their findings rule out this approach, suggesting that the non-black-box techniques employed in their primary result are essential for achieving a separation between classical and quantum complexity. This barrier excludes a broad class of approaches to deriving structured quantum hardness from generic cryptographic primitives, providing partial evidence that the techniques used are critical. The team’s approach involved building NIZKs with an unbounded prover, using Z-tamperable hidden bits and generating public values independent of the hidden bits.

The proof relies on a Bennett-Gill lemma to transition from positive-probability decidability to a fixed oracle machine, enabling the application of zero knowledge. “The desired conclusion quantifies over random oracles and all polynomial-time oracle machines,” the researchers explain.

Unstructured Assumptions and Structured Hardness

Researchers found that constructing “structured quantum hardness” is more difficult than previously understood. Their analysis reveals that deriving two-sided certification alongside quantum hardness is obstructed by fundamental limitations. The research extends a classical result concerning the Bennett-Gill question, which asks whether NP∩coNP remains hard even when evaluated against a random oracle. This finding is not merely a quantum extension of a known classical result. It carries a distinct quantum significance.

The researchers specifically investigated the possibility of constructing such languages using cryptographic primitives, aiming to determine whether unstructured sources of hardness could give rise to structured quantum hardness. Their findings indicate that this is not generally possible, at least not through simple, black-box constructions. The researchers emphasize that their findings do not rule out the possibility of structured quantum hardness altogether, but rather highlight the challenges associated with deriving it from unstructured assumptions.

Limitations of Number-Theoretic Hardness Candidates

The availability of established cryptographic candidates does not, in itself, resolve a fundamental question in complexity theory, according to recent work. Researchers found that simply possessing a problem believed to be difficult to solve, a conjectured hardness of a search task or promise problem, does not automatically yield a language with efficiently verifiable certificates for both correct and incorrect answers on every input. This limitation applies to approaches using coding theory, multivariate polynomial systems and isogenies of elliptic curves, all currently explored as potential foundations for cryptography.

Establishing an impossibility result when a quantum random oracle is replaced by a cryptographic primitive offers useful insight into the limitations of “black-box” approaches to deriving structured quantum hardness. The team specifically investigated injective one-way functions as a candidate for this primitive, recognizing them as an unstructured source of hardness.

The current research extends this finding to the quantum realm, demonstrating a corresponding impossibility result. For a NO-instance (x,i), two cases arise: either x is in the unique solution set, or it is not. The decider for $L_{proof,V}^O$, when applied to the simulated proof for each index i, recovers the witness bit by bit. Zero knowledge, in effect, transfers the correctness of this recovery from genuine proofs to simulated ones.

The team notes that extending the hardness argument to quantum algorithms is separate from constructing a quantum-secure NIZK. The research highlights the challenges in constructing a quantum-hard language in NP∩coNP based solely on a random oracle. While an ideal result would be to rule out every such construction, the team acknowledges this is currently too ambitious.

The work offers a partial explanation for why establishing such hardness remains a significant hurdle, even as quantum computing technology continues to advance. The researchers emphasize that the availability of cryptographic candidates does not, by itself, resolve the underlying complexity-theoretic questions.

Implications for Post-Quantum Cryptographic Assumptions

The reliance on lattice problems as the foundation for many post-quantum cryptographic systems does not automatically guarantee a path to provable quantum hardness, according to recent findings. This distinction is critical, as the ability to efficiently verify solutions is essential for cryptographic security, and its absence complicates efforts to establish robust quantum hardness. This work extends a longstanding question in complexity theory, initially posed as the Bennett-Gill question, to the quantum realm.

This finding highlights a fundamental challenge: the very structure that supports useful certification and cryptographic applications could also inadvertently enable an efficient quantum algorithm, undermining the intended security. The researchers demonstrate that even allowing for the algorithmic capabilities that defeat canonical problems, those previously used as evidence for classical hardness, does not resolve the issue of coexisting certification and quantum hardness.

Specifically, they demonstrate there is no fully black-box quantum reduction of any worst-case quantum hard problem in NP∩coNP to post-quantum indistinguishability obfuscation (iO) and post-quantum injective one-way functions (inj-OWFs). This means that a certain type of construction, one that relies solely on these generic cryptographic primitives, cannot be used to prove quantum hardness for problems in NP∩coNP. “There is no such reduction to the following post-quantum cryptographic primitives: public-key encryption, oblivious transfer, deniable encryption, and functional encryption,” the paper states.

The implications extend beyond lattice-based cryptography, encompassing other post-quantum candidates as well. This approach, while not exhaustive, offers valuable insight into the limitations of black-box methods and suggests that more sophisticated, non-black-box techniques may be necessary.

The work builds on the classical starting point of Z-tamperable hidden bits, proceeding through the Z-tamperable-hidden-bits model where a prover receives a hidden string and may reveal selected positions to the verifier. Constructing non-interactive zero-knowledge (NIZK) proofs for NP in the quantum random oracle model (QROM) without additional assumptions remains an open problem. The team’s work obtains its post-quantum analogue, furthering the understanding of the challenges involved.

The researchers note that this is not merely asking the quantum version of a classical question, as Shor’s algorithms have already removed two of the principal sources of evidence for classical hardness in NP∩coNP by efficiently solving integer factorization and discrete logarithms. The team’s work provides partial evidence that the non-black-box techniques used in their research are essential for achieving this goal, suggesting that relying solely on generic cryptographic primitives is unlikely to be sufficient. The research highlights the need for continued investigation into alternative approaches to establishing provable quantum hardness, particularly those that move beyond the limitations of black-box reductions and explore more complex, structured constructions.

More like this

Quantum Research NewsQuantum causal confusion is rare, as oblique states dominate

PhysicsQuantum timing, not power, controls atomic motion in a crystal

Quantum Research NewsA new dissipator lowers qubit temperature by 14 millikelvin

Quantum Research NewsPenn State physicist details quasiparticle control in van der Waals materials