Structured Quantum Hardness from Unstructured Assumptions

Structured Quantum Hardness from Unstructured Assumptions Xiao Liang1∗ , Takashi Yamakawa2 , and Chak Fai Yung3 1

arXiv:2611.07413v1 [quant-ph] 5 Nov 2026

The Chinese University of Hong Kong, Hong Kong xiaoliang@cuhk.edu.hk 2 NTT Social Informatics Laboratories, Japan takashi.yamakawa@ntt.com 3 The Chinese University of Hong Kong, Hong Kong cfyung2@cse.cuhk.edu.hk

Abstract. 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; [GIK+ 23, STOC’23] recently gave a conditional affirmative answer in the classical setting. We establish the quantum analogue: if UP ̸⊆ BQP, then NPO ∩ coNPO ̸⊆ BQPO with probability 1 over a random oracle O. Beyond extending the classical result, this separation has a distinctly quantum significance: Shor’s algorithms defeat canonical number-theoretic hardness candidates, while lattice assumptions and other leading post-quantum cryptographic assumptions do not directly supply hard languages with two-sided classical certification on every input. Our conditional oracle separation provides evidence that such structured quantum hardness can nevertheless arise from unstructured sources. Complementing this result, we rule out fully black-box quantum reductions of worst-case quantum hardness in NP∩coNP to post-quantum injective one-way functions and indistinguishability obfuscation. This barrier excludes a broad class of black-box approaches to deriving structured quantum hardness from generic cryptography primitives, providing partial evidence that the non-black-box techniques in our first result are essential. Keywords: Quantum Complexity · Random Oracle · Non-Interactive Zero Knowledge · Pseudorandom Hash functions · Black-Box Impossibility

∗

The work described in this paper was partially supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China [Project No.: CUHK 24208025].

Table of Contents

Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Technical Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Building NIZKs with an Unbounded Prover: the Classical Starting Point . . . . . . . . . . 2.2 Strong δ-Dense PRHFs and Their Application to NIZK . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Completing the Separation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 A Random Oracle is a Strong PRHF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Quantum Black-Box Impossibility via a Universal Decision Oracle . . . . . . . . . . . . . . . . 3 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Random Oracles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Useful Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Simulating Two Oracles using One . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Non-Interactive Zero-Knowledge Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Compressed Partially-Fixed Oracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Strong δ-Dense PRHF: Definition and Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Strong δ-Dense PRHF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Random Oracle is a Strong (1 − 1e )-Dense PRHF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Proof of Lem. 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Hybrids H0 and H1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 Hybrid H2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.3 Hybrid H2.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.4 Hybrid H3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.5 Hybrid H4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.6 Hybrid H5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.7 Hybrid H6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . s 4.4 Proof of Claim 1: H0 ≈ H1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.1 Proof Strategy Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.3 Technical Tools regarding Random Oracles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . s 4.4.4 Proving H0 ≈ H1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . s 4.5 Proof of H1 ≈ H2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . cq 4.6 Proof of H2 ≈ H2.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 NIZK in the URS-PRHF Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Security Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 NIZK in QROM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1 Structure of Our Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Instantiating the PRHF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Replacing the URS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.1 Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.2 Soundness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

iii 1 2 4 5 6 8 10 10 14 16 17 17 20 21 23 24 24 25 26 27 28 28 29 31 32 33 34 34 35 35 39 49 54 57 58 59 65 65 66 66 67 67

6.3.3 Zero Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Combining the Two Oracles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5 Final Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Oracle Separation between NP ∩ coNP and BQP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1 Technical Tool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Post-Quantum injOWF Implies UP ⊈ BQP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 The Oracle-Aided Language LO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4 Membership in NPO ∩ coNPO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.5 Non-Membership in BQPO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Black-Box Impossibility of Constructing Quantum-Hard NP ∩ coNP Problems . . . . . . . . . . 8.1 Black-Box Framework and Technical Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1.1 Oracle Access and the Black-Box Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1.2 The Universal Decision Oracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1.3 A Quantum Hybrid Bound for Coupled Oracles . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Warm-Up: Separation from injOWFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Separation from i O and injOWFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.1 Oracle Construction and Resource Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.2 One-Wayness in the Presence of the Augmented Oracle . . . . . . . . . . . . . . . . . . . . 8.3.3 Obfuscation Security in the Presence of the Augmented Oracle . . . . . . . . . . . . . . 8.3.4 Consequence for Efficient Black-Box Reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Acknowledgments and AI Disclosure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A More Basic Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.1 Probability Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Statistical Distance and Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.3 Efficient Approximability of 1e and 1 − 1e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B Length-Tripling Random Oracles as Post-Quantum injOWFs . . . . . . . . . . . . . . . . . . . . . . . .

iii

68 70 70 72 72 75 76 76 76 81 81 81 83 85 87 92 92 94 96 103 104 105 107 107 108 109 110

1

Introduction

Understanding how the structure of a computational problem governs its complexity is a central theme in theoretical computer science. Additional structure may enable efficient algorithms, but it may also endow a problem with useful properties without making it tractable. Distinguishing these possibilities is essential to understanding which forms of computational hardness can exist and what they can accomplish. This tension is particularly pronounced in cryptography, where the algebraic structure underlying a hard problem often enables powerful applications, while simultaneously providing a foothold for algorithmic attacks. A fundamental question is therefore whether useful forms of structured hardness inherently require structured assumptions, or whether they can instead arise from generic, unstructured sources of computational difficulty. A concrete setting for studying this question is the class NP ∩ coNP, whose languages admit polynomial-size, efficiently verifiable certificates for both membership and nonmembership. This two-sided certification requirement provides a complexity-theoretic notion of structure. Whether such a requirement is compatible with intractability is captured by the classical conjecture P ̸= NP∩ coNP. However, compared with P ̸= NP, this conjecture is supported by a much narrower collection of natural candidate problems. Among the most prominent are decision problems associated with integer factorization and discrete logarithms. Their presumed hardness has motivated extensive study and underlies important cryptographic constructions, but their considerable mathematical structure leaves open the possibility of unexpected algorithmic advances. For example, number-fieldsieve algorithms achieve heuristic subexponential running times for integer factorization [BLP93] and for discrete logarithms in prime fields [Gor93]. A longstanding line of research asks whether hardness in NP ∩ coNP can instead be obtained from unstructured sources [BG81, BI87, Rud88, Tar89, BDV17, GIK+ 23]. Random oracles provide a natural framework for investigating this question. A uniformly random function supplies computational difficulty without imposing a particular algebraic structure; a separation relative to such an oracle can therefore provide evidence that hardness need not depend on special properties of an explicit mathematical construction. The seminal work of Bennett and Gill [BG81] established PO ̸= NPO with probability 1 over a random oracle O, and asked whether PO ̸= NPO ∩ coNPO holds as well. They proved the latter separation when O is a random permutation (a structured source of hardness), but left the random-function case open. The same distinction arises when constructing hard languages in NP ∩ coNP from cryptographic primitives. One-way permutations (OWPs) yield such languages through black-box constructions. Injective one-way functions (inj-OWFs), by contrast, are viewed as an unstructured source of hardness in this context: a sufficiently length-expanding random function is both injective and one-way except with negligible probability [GIK+ 23]. Here, “unstructured” does not mean the absence of every mathematical property, but rather the absence of additional constraints that cannot be obtained from a random function. In this regard,, results of Blum and Impagliazzo [BI87] and Rudich [Rud88] rule out black-box constructions of hard languages in NP ∩ coNP from OWFs; Bitansky, Degwekar, and Vaikuntanathan [BDV17] strengthened this barrier to inj-OWFs, even when additionally allowing black-box access to indistinguishability obfuscation (i O). These results expose a substantial obstacle to deriving two-sided certification together with hardness from generic cryptographic primitives. Recently, [GIK+ 23] overcame this obstacle through a non-black-box approach. Assuming UP ̸⊆ RP (an assumption implied by the existence of inj-OWFs), they established NPO ∩ coNPO ⊈ PO with probability 1 over a random oracle O. Their result gives a conditional affirmative answer to Bennett–Gill question. 1

Structured Quantum Hardness? In contrast, the picture in the quantum regime is much less understood. In fact, this is not merely asking the quantum version of a classical question: Shor’s algorithms [Sho94] solve integer factorization and discrete logarithms in quantum polynomial time, removing two of the principal sources of evidence for classical hardness in NP ∩ coNP. These algorithms sharply illustrate the underlying concern: the structure supporting useful certification and cryptographic applications can also enable an efficient quantum algorithm. Thus, the quantum setting asks whether two-sided classical certification can coexist with quantum hardness, even after allowing the algorithmic capabilities that defeat canonical problems serving as evidence for the classical Bennett–Gill question. Moreover, the leading sources of conjectured post-quantum hardness makes the situation more fascinating: Lattice problems, including learning with errors (LWE), short integer solution (SIS), and the approximate shortest vector problem (GapSVP), are widely conjectured to resist quantum algorithms at appropriate parameters and underpin much of post-quantum cryptography [Pei15]. Nevertheless, these conjectures do not directly furnish hard languages in NP∩coNP. The distinction here is subtle: the obstacle is not simply the absence of efficiently checkable no-certificates. Indeed, Aharonov and Regev [AR04] established two-sided classical certification for suitable gap versions of lattice problems, placing them in Promise-NP ∩ Promise-coNP. These guarantees, however, apply only to inputs satisfying the promise; they do not provide certificates of the correct answer on every input. Likewise, standard formulations of SIS and LWE do not directly supply the required language with two-sided certification either. It is also worth mentioning that other approaches to postquantum cryptography draw on problems in coding theory, multivariate polynomial systems, and isogenies of elliptic curves [CJL+ 16]. These approaches raise the same complexity-theoretic issue: conjectured hardness of a search task or a promise problem does not, by itself, provide a language with efficiently verifiable certificates for both answers on every input. Thus, the availability of postquantum cryptographic candidates therefore does not by itself resolve the question considered here. This gives the quantum Bennett–Gill question a distinctive motivation beyond its classical version. There is also an important distinction between assuming quantum hardness for an already structured primitive and deriving structured quantum hardness from an unstructured source. For example, a one-way permutation secure against quantum polynomial-time algorithms yields a language in NP∩coNP outside BQP: its unique inverse provides certificates for either value of an inverse bit, while an efficient quantum algorithm for deciding these bits would allow inversion, using error amplification. Here, however, the structure needed for two-sided certification is already supplied by the assumption: every output has exactly one preimage. Likewise, the random-permutation separation of [BBBV97] provides relativized evidence for quantum hardness in NP ∩ coNP, but starts from an oracle with this same structural guarantee. Our aim is instead to obtain two-sided certification together with quantum hardness without assuming such permutation structure at the outset. Question: Can structured quantum hardness be derived from unstructured sources? 1.1

Our Results

We obtain both positive and negative results concerning this question. We summarize them below. Unstructured Quantum Hardness. Our first result gives a conditional affirmative answer to the quantum Bennett–Gill question. Specifically, assuming that UP contains a language outside BQP, we show that a random oracle almost surely yields a language with two-sided classical certification that remains hard even for quantum algorithms. Note that both the assumption UP ⊈ BQP and a random oracle are regarded as sources of unstructured hardness. Thus, Thm. 1 provides evidence 2

toward an affirmative answer to the question posed above. (Here and throughout, BQPO denotes bounded-error quantum polynomial time with quantum query access to O.) Theorem 1. If UP ⊈ BQP, then it holds that NPO ∩ coNPO ⊈ BQPO with probability 1 over the choice of a random oracle O. Importantly, the proof of Thm. 1 makes non-black-box use of a language L ∈ UP \ BQP to construct the desired quantum-hard language.4 If this use of L could instead be made black-box, one could hope to use the random oracle itself to construct an oracle language LO in place of L.5 Such an approach, if carried out, would establish the conclusion of Thm. 1 without the additional assumption UP ⊈ BQP, thereby resolving the quantum Bennett–Gill question. However, replacing this non-black-box use with a black-box construction appears challenging. Our investigation of this obstacle leads to the impossibility result below, which provides partial evidence that the non-blackbox nature of Thm. 1 seems essential. Black-Box Impossibilities for Cryptographic Attempts. For lower bounds, an ideal result would be to rule out every construction of a quantum-hard language in NPO ∩coNPO based solely on a random oracle. However, such a result would seem too ambitious at present. Instead, we consider a cryptographic analogue: can we establish an impossibility result when the quantum random oracle is replaced by a cryptographic primitive capturing a comparable form of unstructured hardness? Such a result would still provide useful insight into the limitations of black-box approaches. Injective one-way functions are a natural candidate. As discussed earlier, inj-OWFs can be viewed as an unstructured source of hardness. Moreover, the analogous question has been studied in the classical setting: Bitansky, Degwekar, and Vaikuntanathan [BDV17] ruled out fully black-box constructions of hard languages in NP ∩ coNP from inj-OWFs, even with additional access to i O. We establish a corresponding impossibility result in the quantum setting. Theorem 2. There is no fully black-box6 quantum reduction of any (even worst-case) quantum hard problem in NP ∩ coNP to post-quantum i O and post-quantum inj-OWFs. Consequently, there is no such reduction to the following post-quantum cryptographic primitives: public-key encryption, oblivious transfer, deniable encryption, and functional encryption. Strong PRHF and a Unified Reduction for QROM NIZK. An important technical ingredient for Thm. 1 is a non-interactive zero-knowledge (NIZK) proof for NP in the quantum random oracle model (QROM), without additional computational assumptions. As discussed in the classical setting [GIK+ 23], obtaining such a proof system is challenging: standard approaches either rely on structured assumptions beyond random oracles or provide soundness only against polynomial-time provers.7 Constructing NIZK proofs for NP in the (Q)ROM without additional assumptions remains an important open problem. [GIK+ 23] bypasses this obstacle using an unbounded honest prover. We obtain in Thm. 3 its post-quantum analogue. However, as explained below, our construction relies on new technical ideas rather than a direct quantization of their techniques. 4

As will become clear in the following sections, non-black-box use here refers to generating a non-interactive zeroknowledge proof for a statement involving the definition of L. 5 A sufficiently length-expanding restriction of a random oracle is injective and post-quantum one-way with overwhelming probability (see Lem. 41). This yields an oracle language in UPO outside BQPO , rather than requiring the separate assumption UP ⊈ BQP. 6 Strictly speaking, what we rule out is slightly more general than the traditional definition of fully black-box constructions, due to the non-black-box use of obfuscating circuits with injOWF-gates. This is similar to [BDV17]. 7 A system with soundness only against computationally bounded provers is called a NIZK argument, rather than a NIZK proof.

3

Theorem 3. There exists an (unbounded-prover) post-quantum NIZK proof for NP in the quantum random oracle model. Strong δ-Dense PRHFs. The approach underlying Thm. 3 constitutes one of our main technical contributions. [GIK+ 23]’s results are obtained by introducing a cryptographic primitive called a δ-dense pseudorandom hash function (PRHF). Their approach has two steps: (i) constructing the desired NIZK from a PRHF, and (ii) showing that a random oracle satisfies PRHF security. There is, however, a subtle mismatch between these components. The step-(i) reduction from NIZK to PRHF requires a non-uniform PRHFs secure against “function-dependent” adversaries. In contrast, their step-(ii) proof of a random oracle’s PRHF properties provides only a uniform guarantee. Consequently, directly substituting the random oracle for the PRHF in the NIZK construction can introduce inefficient “oracle-dependent” preprocessing that render the security reduction inefficient. Therefore, the two steps do not compose directly. To address this issue, [GIK+ 23] provides a separate security proof for the NIZK construction in the random oracle model, in addition to its analysis in the PRHF setting. Indeed, [GIK+ 23, Remark 7.6] leaves open whether a random oracle satisfies PRHF security against oracle-dependent adversaries. Rather than attacking this open question, we take a different approach. Our starting point is a change in perspective: instead of treating the mismatch solely as a limitation of existing techniques for handling oracle-dependent adversaries, we view it as an issue with the interface provided by the PRHF definition. This suggests seeking a strengthened notion that both admits a random-oracle instantiation and supports a NIZK security reduction without the problematic oracle-dependent preprocessing. Following this perspective, we introduce strong δ-dense PRHFs. We show that a random oracle is a strong PRHF and that a strong PRHF suffices to construct the desired NIZK through a unified security reduction, independently of how the strong PRHF is instantiated. Moreover, we establish both components in the quantum setting, yielding Thm. 3 and demonstrating the robustness of the strengthened PRHF notion. More details are provided in Sec. 2. We believe that the strong PRHF is a cleaner and more natural primitive that will find further applications in cryptographic constructions. 1.2

Related Work

It is also worth noting that there do exist other candidates for quantum hardness in NP ∩ coNP, beyond the number-theoretic problems mentioned earlier. Parity games, simple stochastic games, and related graph-game problems are important representatives [Con92, CJK+ 17]. These problems have motivated substantial algorithmic research; notably, parity games admit a quasipolynomialtime algorithm [CJK+ 17]. Nevertheless, no polynomial-time classical or quantum algorithms are known for these general game problems. Their unresolved complexity supplies candidates for hardness, but a different kind of evidence from the number-theoretic assumptions traditionally used in cryptography. In particular, proposing that one of these games is quantum-hard does not explain whether such hardness follows from a generic post-quantum cryptographic assumption. The evidence for quantum hardness in NP ∩ coNP is consequently narrower than the classical picture might initially suggest. Another route to quantum hardness in NP ∩ coNP proceeds through classical derandomization. Under suitable circuit-hardness assumptions, AM = NP and hence AM∩coAM = NP∩coNP [MV05]. Since SZK ⊆ AM∩coAM [AT03], any language in SZK\BQP, together with such a derandomization assumption, would yield a language in (NP ∩ coNP) \ BQP. Graph non-isomorphism is a natural candidate. Other candidate languages in SZK include the decision versions of tensor isomorphism and code equivalence over finite fields, problems whose search variants have been studied for postquantum cryptography purpose [GGPS23, DMR11]. 4

Combined with classical derandomization, these assumptions therefore provide another route to quantum hardness in NP∩coNP. This route, however, starts from specific algebraic problems already admitting statistical zero-knowledge proofs and invokes an additional derandomization assumption. Our focus is instead on deriving two-sided classical certification together with quantum hardness from unstructured sources.

2

Technical Overview

Our starting point is the work of [GIK+ 23]: if UP ⊈ RP, then NPO ∩coNPO ⊈ PO with probability 1 over a random oracle O. We first recall the main ingredients of their construction, emphasizing the aspects relevant to extending their approach to the quantum setting. From a hard promise problem to a hard language. Fix a language Lunique ∈ UP \ RP, and let Runique be its polynomial-time witness relation. Thus, every x ∈ Lunique has a unique polynomial-length witness wx , whereas every x ∈ / Lunique has no witness. For simplicity, we use a fixed polynomial witness length, padding witnesses uniquely if necessary. Consider the language  Lalmost := (x, i) ∃w : Runique (x, w) = 1 ∧ wi = 1 . Clearly, Lalmost ∈ NP. Moreover, a polynomial-time decider for Lalmost would recover the unique witness bit by bit whenever one exists; checking the recovered witness would then decide Lunique . Hence, Lalmost ∈ / P. The difficulty is establishing membership in coNP. For a NO-instance (x, i), there are two cases: – Good case: x ∈ Lunique . The unique witness wx certifies nonmembership by satisfying Runique (x, wx ) = 1 and (wx )i = 0. Uniqueness rules out a different witness whose ith bit is 1. – Problematic case: x ∈ / Lunique . No witness exists, and there need not be an efficiently verifiable certificate of this fact. Thus, the witness-bit problem has both YES- and NO-certificates under the promise x ∈ Lunique , but extending this guarantee to all inputs is nontrivial. The idea of [GIK+ 23] is to enforce this promise by appending an efficiently verifiable proof π of x ∈ Lunique . Given a deterministic polynomial-time verifier V , define  Lproof,V := (x, i, π) (V (x, π) = 1) ∧ (∃w s.t. Runique (x, w) = 1 ∧ wi = 1) . Here, V is fixed for the language, and proofs have polynomially bounded length. For intuition, suppose that the proof system has perfect completeness and perfect soundness. An NP certificate is simply wx . To certify nonmembership, either the verifier rejects π, which can be checked directly, or wx certifies that its ith bit is 0. Soundness ensures that an accepting proof cannot occur in the problematic case. Consequently, Lproof,V ∈ NP ∩ coNP. Preserving hardness is subtler. If π simply reveals wx , then the construction satisfies completeness and soundness but yields an easy language. The proof must therefore enforce the promise without revealing the witness. This motivates using a non-interactive zero-knowledge (NIZK) proof: its efficient simulator generates proofs without knowing wx . Why zero knowledge preserves hardness. A NIZK construction in the random oracle model is required to have a simulator, which can produce both a simulated proof and simulated oracle responses. Informally, a decider for LO proof,V , applied to the simulated proof for each index i, recovers the witness bit by bit. Zero knowledge transfers the correctness of this recovery from genuine proofs 5

to simulated ones. Checking the recovered witness gives a one-sided-error algorithm for Lunique : it always rejects NO-instances and accepts YES-instances with high probability. Making this argument rigorous requires more than the usual simulation argument. The desired conclusion quantifies over random oracles and all polynomial-time oracle machines. The proof in [GIK+ 23] uses a Bennett–Gill lemma [BG81] to pass from positive-probability decidability to a suitable fixed oracle machine, to which zero knowledge can be applied. (We remark that extending this hardness argument to quantum algorithms is a separate issue from constructing a quantumsecure NIZK; we return to it in Sec. 2.3.) There is also a soundness qualification. The construction provides adaptive statistical soundness: except with negligible probability over the oracle, no false statement of a given length has an accepting proof. Since these failure probabilities are summable, the Borel–Cantelli lemma implies that almost every oracle has only finitely many exceptional statement lengths. For each such oracle, these lengths can be handled separately when establishing membership in NPO ∩ coNPO . This is why statistical proofs, rather than merely computationally sound arguments, are essential. NIZK from unstructured assumptions. The remaining challenge is to construct the required NIZK without structured assumptions. Previously known NIZK proofs in the uniform reference string model relied on structured primitives, whereas standard random-oracle constructions such as Fiat–Shamir generally provide only arguments. Importantly, this application does not require an efficient honest prover: it requires only an efficient verifier and simulator. The main technical contribution of [GIK+ 23] is an unbounded-prover NIZK proof system for NP in the classical randomoracle model.

2.1

Building NIZKs with an Unbounded Prover: the Classical Starting Point

Z-tamperable hidden bits. [GIK+ 23] proceeds through the Z-tamperable-hidden-bits model. The prover receives a hidden string r = (r1 , . . . , rm ) of independent, possibly biased bits and may reveal selected positions to the verifier. A malicious prover may additionally change any 0 to a 1, but cannot change a 1 to a 0. To construct NIZK in this model, [GIK+ 23] adapts the classical hidden-bits construction for graph Hamiltonicity. The hidden bits encode many sparse matrices, some of which contain an ncycle as a submatrix and zeros elsewhere. For each such matrix, the prover shows that the cycle is contained in a permutation of the input graph, revealing only entries corresponding to nonedges. The remaining matrices are fully revealed and checked not to be of this form. The new difficulty is that one-sided tampering lets a cheating prover destroy every cycle matrix by adding a 1, thereby making it eligible for disclosure and disposal. The construction counters this attack with a statistical check on the number of revealed matrices containing at least n + 1 ones. Destroying cycle matrices increases this count. Moreover, the matrices are sufficiently sparse that almost all matrices already containing more than n ones occupy more than n rows or columns, and hence cannot be hidden inside an n × n submatrix. Thus, the prover cannot offset the increase by withholding enough other matrices. Concentration bounds then yield statistical soundness. Implementing the hidden bits. Let H : {0, 1}n → {0, 1}n have image density approximately δ, for an efficiently approximable constant δ ∈ (0, 1). For a uniformly random public value y, define ( r(y) =

0, 1,

y ∈ Image(H) . y∈ / Image(H) 6

An unbounded prover can determine r(y) and, when r(y) = 0, sample a uniformly random preimage v of y. To reveal a zero, it provides v, which the verifier checks by evaluating H(v) = y. To reveal a one, it provides the symbol ⊥, without proving nonmembership. This implements precisely the allowed direction of tampering: a prover may withhold an existing preimage and claim a one, but cannot produce a preimage of a value outside the image. Furthermore, independent uniform values y1 , . . . , ym induce independent hidden bits with bias approximately 1 − δ. Density and one-sided verifiability therefore allow the soundness of the hidden-bits protocol to carry over. The role of pseudorandomness. Zero knowledge requires additional properties. In [GIK+ 23, Definition 4.6], a δ-dense pseudorandom hash function (PRHF) satisfies, in addition to image density, the following: – Output pseudorandomness: H(Un ) is computationally indistinguishable from Un . – Preimage pseudorandomness: the following distributions are computationally indistinguishable: (v, H(v)),

v ← {0, 1}n ,

and

(v, y),

y ← Image(H), v ← H −1 (y).

Both properties are required against non-uniform polynomial-size adversaries. The second property is not automatic from the first: sampling a uniform input weights each output according to its number of preimages, whereas sampling a uniform image element does not. These properties enable a particularly simple simulator in the uniform reference string (URS) model. First, run the hidden-bits simulator to obtain the revealed bits and the associated proof. Independently sample uniform v1 , . . . , vm and set yi = H(vi ). For each revealed zero, provide vi ; for each revealed one, provide ⊥. Thus, the simulator knows a preimage for every public value, including those presented as having no preimage. Why is this indistinguishable from an honest execution? For a revealed zero, preimage pseudorandomness justifies replacing a uniform image element and its uniform preimage with (H(vi ), vi ). For a one, the honest public value is uniform outside the image. Output pseudorandomness and preimage pseudorandomness together imply that this distribution is also indistinguishable from H(Un ): the uniform distribution is a constant-weight mixture of the uniform image and nonimage distributions, and the uniform image distribution is already indistinguishable from H(Un ). After these replacements, the public values are generated independently of the hidden bits, allowing the hidden-bits zero-knowledge property to complete the argument. PRHF does not directly give a random-oracle NIZK. A length-preserving random function has image density approximately 1 − e−1 and satisfies the required pseudorandomness properties against polynomial-query adversaries; see [GIK+ 23, Appendix B]. One might therefore hope simply to instantiate the PRHF with a random oracle. However, the security guarantees needed by the above reduction do not match those established for the oracle. The PRHF-to-NIZK proof uses non-uniform hybrid reductions to hardwire intermediate values that need not be efficiently computable, including hidden-bit transcripts and samples conditioned on image membership. For a fixed explicit function H, this is permitted by the PRHF definition. If H is replaced by a random oracle, however, the corresponding advice may depend on the sampled oracle itself. The reduction would therefore require preimage pseudorandomness against adversaries equipped with oracle-dependent advice, potentially obtained by unbounded preprocessing of the oracle. [GIK+ 23] does not establish this stronger guarantee. The distinction is oracle-dependent advice, not merely whether an adversary is uniform or non-uniform. As explained in [GIK+ 23, Remark 7.6], this mismatch prevents a direct composition of the two results. Instead, the authors prove zero knowledge separately in the classical random-oracle model. 7

Their simulator samples public values, programs preimages for the simulated zeros, and answers subsequent oracle queries by lazy sampling. A direct hybrid argument analyzes the resulting joint distribution without invoking PRHF security with oracle-dependent advice. This proves security against classical polynomial-query adversaries, but does not by itself establish security for quantum superposition queries. Consequently, both this simulation step and the subsequent hardness argument must be addressed when extending the approach to the quantum setting. 2.2

Strong δ-Dense PRHFs and Their Application to NIZK

Our starting point is a change in perspective: rather than overcoming oracle-dependent nonuniformity by proving security against stronger adversaries, we redesign the interface provided by the PRHF definition. The original reduction introduces oracle-dependent auxiliary information when it replaces individual samples while fixing the remaining transcript. We instead formulate a security experiment that exposes the entire polynomial-size collection of samples from the outset. This leads to strong δ-dense PRHFs. Our approach simultaneously removes the need for oracle-dependent advice and extends the primitive to the post-quantum setting. We establish two complementary results: strong postquantum PRHFs suffice for the NIZK construction through a uniform, black-box reduction, and a quantum random oracle instantiates this strengthened notion. Consequently, the random-oracle instantiation follows from the same abstract reduction, without a separate random-oracle-specific proof of the zero-knowledge property. Strong preimage pseudorandomness. Our new notion of strong δ-dense PRHFs retains the density and pseudorandomness requirements: the image of H occupies approximately a δ fraction of its codomain, and H(v) for uniform v is pseudorandom against quantum adversaries with oracle access to H. The principal change is the third requirement, strong preimage pseudorandomness. Let H : {0, 1}n → {0, 1}ℓ(n) , let p(n) be a polynomial, and set γ = 1 − δ. Consider two distributions that both expose
T := r = (r1 , . . . , rp(n) ), {yi }i∈[p(n)] , {vi }i∈I0 , where I0 := {i | i ∈ [p(n)] s.t. ri = 0}. In both distributions, the bits ri are sampled independently with probability γ of being one. The distributions differ in how they generate the remaining samples: – Backward sampling (D0H ). If ri = 0, sample yi uniformly from Image(H) and then sample vi uniformly from PreImage(yi ). If ri = 1, sample yi uniformly from {0, 1}ℓ(n) \ Image(H).8 This distribution need not be efficiently sampleable. $

– Forward sampling (D1H ). Independently sample vi ← − {0, 1}n and set yi = H(vi ) for every i. Let Hn be the family of H with security parameter n. Strong preimage pseudorandomness requires     H ← Hn , H ← Hn , |H⟩ ≤ negl(n), Pr A|H⟩ (T ) = 1 : − Pr A (T ) = 1 : T ← D0H T ← D1H where |H⟩ indicates that A has quantum access to H as an oracle.9 We require security against polynomial-query quantum adversaries A, allowing oracle-independent auxiliary input. Their com8

If the set {0, 1}ℓ(n) \Image(H) is empty, we simply set yi to a fixed value (e.g., 0ℓ(n) or ⊥). We adopt this convention whenever sampling from an empty set. This does not affect any of our results, since the empty-set case occurs with only negligible probability throughout the paper. 9 Here, we model H as an oracle because it is ultimately instantiated as a random oracle in our main theorem. Alternatively, H may be treated as a plain-model primitive that could potentially be instantiated under algebraic assumptions in future work. In that case, the description of H should be provided to A in the security definition.

8

putation between oracle queries need not be efficient; this distinction is essential because our NIZK application invokes an unbounded prover. The property replaces the entire collection at once, even though the adversary sees all hidden bits, receives preimages at every zero position, and can query H in superposition. In particular, it accommodates subsequent computations depending on the full hidden-bit string without fixing their outputs as oracle-dependent advice. From strong PRHFs to NIZK with URS. We retain the construction of [GIK+ 23], but give a different zero-knowledge reduction. Recall that a Z-tamperable hidden-bits (ZHB) proof allows the prover to reveal selected hidden bits and to change a zero into a one, but not conversely. To implement these bits, parse the uniform reference string as y1 , . . . , yphbs (n) and define ( ri =

0 if yi ∈ Image(H), 1 otherwise.

The unbounded prover computes r and runs ZHB.Pγ (r, x), obtaining an index set I and a ZHB proof. It opens a zero by providing a uniformly sampled preimage of yi , and opens a one by providing ⊥. The verifier checks the supplied preimages and invokes the ZHB verifier on the resulting bits. A prover can always replace a preimage by ⊥, but cannot provide a preimage of a point outside the image. This realizes exactly the permitted zero-to-one tampering. Completeness and soundness then follow from the corresponding ZHB properties and the density guarantee. For zero knowledge, first rewrite the real experiment by sampling the hidden bits before the public values. Conditioned on H, the probability that ri = 1 is 1 − |Image(H)|/2ℓ(n) . The density guarantee allows us to replace this probability by 1 − δ at negligible statistical cost. The resulting samples are distributed as D0 (i.e., the Backward sampling defined above). We now apply strong preimage pseudorandomness once, to replace D0 by D1 . The reduction receives the complete challenge transcript, runs ZHB.Pγ (r, x), retains the openings selected by its output, and passes the resulting URS transcript to the distinguisher. Although the ZHB prover may be computationally unbounded, it makes no queries to H; hence the reduction remains polynomialquery-bounded. Unlike the coordinate-by-coordinate argument of [GIK+ 23], this reduction neither fixes the ZHB proof nor supplies the remaining samples as oracle-dependent advice. After the replacement, all pairs (vi , H(vi )) are generated independently of r. The final transcript therefore depends on the ZHB execution only through its revealed bits and proof. Statistical zero knowledge of the ZHB system now allows us to replace these by the output of ZHB.Simγ (x). This gives an efficient simulator: generate the simulated ZHB transcript, sample all pairs forward, and reveal the preimages selected by its zero bits. The reduction is genuinely black-box in H, independently of its implementation. In Sec. 2.4, we establish that a random oracle is a strong (1 − e−1 )-dense post-quantum PRHF, which represents our another technical contribution. Together, these results yield a URS-model NIZK relative to a quantum random oracle. Eliminating the URS. To obtain the eventual QROM-only NIZK, we need to remove the URS. Our strategy is to derive the URS from an independent oracle OURS , while using OPRHF for the PRHF. The simulator must answer superposition queries consistently with the simulated URS and its correlations with remaining entries of the oracle(s); and classical lazy sampling does not suffice in the quantum setting. We formalize a compressed partially-fixed oracle, Com(H), which perfectly emulates a random oracle conditioned on a prescribed partial function H. It stores the fixed entries explicitly and compresses the remaining entries using the compressed-oracle technique [Zha19]. Our simulator runs the URS simulator using a persistent compressed PRHF oracle, then 9

initializes the URS oracle conditioned on the resulting URS. Retaining both oracle states preserves the required correlations throughout subsequent quantum interaction, with polynomial overhead. This step implements the simulated experiment efficiently. Combining the oracles. Finally, we combine the two independent oracles into one by domain separation: OURS (z) = O(0∥z) and OPRHF (z) = O(1∥z). A quantum adversary may query a superposition of the two prefixes, so separate oracle access does not immediately give the required combined interface. We simulate each combined query exactly using four separate queries: compute each oracle’s answer into an ancilla, conditionally XOR it into the answer register, and uncompute. This works even when the prefix is entangled with the adversary’s workspace. Thus, the two-oracle security argument transfers to a single quantum random oracle, completing the construction. 2.3

Completing the Separation

With our QROM NIZK in hand, we complete the separation by adapting the argument of [GIK+ 23]. We first instantiate the verifier in LO proof,V with our NIZK verifier. The certificate argument remains classical: adaptive statistical soundness, together with the Borel–Cantelli lemma, ensures O O for almost every oracle. The remaining task is to rule out quanthat LO proof,V ∈ NP ∩ coNP tum polynomial-time deciders. Suppose a fixed quantum oracle machine decides this language with bounded error on every input for at least a 2/3 fraction of oracles. Given an accepting proof for x ∈ Lunique , we can use this machine to recover the unique witness bit by bit. Replacing the genuine proof and oracle access by our efficient NIZK simulator preserves each bit’s recovery probability by quantum zero knowledge. Repeating with independent simulator instances and taking majority votes therefore recovers the entire witness with high probability. Checking the recovered witness ensures that NO-instances are always rejected, yielding an oracle-free BQP algorithm for Lunique . This contradicts Lunique ∈ / BQP. To pass from this high-probability bound to an almost-sure separation, we give a quantum formulation of [BG81, Lemma 1]. Its structural requirements hold here: bounded witness enumeration gives a total 10 oracle decider, and the verifier’s input-length-separated oracle access ensures that changing finitely many oracle bits affects only finitely many language instances. The standard finite-prefix hardwiring and finite-input correction argument from [BG81] thus applies to quantum machines as well, showing that each fixed machine decides the language only on a measure-zero set of oracles. A countable union over machines completes the proof that, assuming UP ⊈ BQP, we have NPO ∩ coNPO ̸⊆ BQPO with probability 1 over O. 2.4

A Random Oracle is a Strong PRHF

We show that a uniformly random function H : {0, 1}n → {0, 1}n is a strong post-quantum δ-dense PRHF for δ = 1 − e−1 . The δ-density property follows from [GIK+ 23], while image pseudorandomness against quantum queries follows from a standard one-way-to-hiding (O2H) argument [AHU19]. We focus on the new strong preimage pseudorandomness (recall the definition on Page 8): for every polynomial p(n), backward sampling D0 and forward sampling D1 produce indistinguishable collections
T := r = (r1 , . . . , rp(n) ), {yi }i∈[p(n)] , {vi }i∈I0 . even when the distinguisher makes polynomially-many quantum queries to H. Recall that backward sampling chooses yi uniformly from Image(H) and then a uniform preimage vi when ri = 0, and chooses yi outside the image when ri = 1. Forward sampling instead chooses a 10

An oracle machine is total if it halts on every input for every oracle. No polynomial-time bound is required.

10

uniform vi and sets yi = H(vi ) at every position, revealing vi only when ri = 0. We fix r throughout the overview, and let I0 and I1 denote the sets of indices where ri = 0 and ri = 1, respectively; (note that I0 ∪ I1 = [p(n)]). All bounds are uniform over its choice and therefore also hold after averaging over r. We suppress negligible collision and exceptional-size events, which our formal proof in Sec. 4.2 handles explicitly. The difficulty is that T and the oracle available to the adversary depend on the same random function. Replacing one sample while fixing the others risks introducing oracle-dependent advice. We instead transform the entire collection and the queried oracle jointly. This is not a direct application of quantum tools, e.g., the O2H lemma [AHU19]. Although such tools can bound the effect of changing an oracle on a set of inputs, its usefulness depends on bounding the adversary’s probability of querying that set. Here, the information in T is correlated with the locations we wish to change. Non-trivial ideas and efforts are required to bound the query-hitting probability. We build a sequence of hybrids, where we gradually switch from the backward-sampling distribution to the forward-sampling distribution. In the following, we provide a high-level overview of the main steps in the proof, while deferring the technical details to Sec. 4.2. Generating outputs outside the image by modifying the oracle. We start from the backwardsampling distribution D0 . We first change how the outputs at positions i ∈ I1 are generated. Rather $

than choosing yi outside the image, we sample vi ← − {0, 1}n , set yi = H(vi ), and keep vi hidden. Then, we modify every entry of the oracle H whose value is one of these selected outputs, replacing its value with fresh randomness outside the selected outputs. Consequently, these yi ’s are absent from the image of the modified oracle, as required by backward sampling. To distinguish it from the orignial oracle H, we denote this modified oracle as H ∗ ; also note that H ∗ is now the oracle supplied to the adversary. To see why this modification is safe, notice that the number of outputs missing from a random function’s image is sharply concentrated. Thus, choosing a random function and then uniform missing outputs is statistically close to choosing the outputs first and then a random function avoiding them. Meanwhile, polynomially many forward evaluations produce almost uniform distinct outputs. Conditional on the locations being modified, the other entries already avoid those outputs; resampling the modified entries yields the corresponding distribution of an oracle avoiding them. We must also account for the (vi , yi ) pairs for each i ∈ I0 : these pairs were sampled backward from the original oracle, but the adversary now receives the modified oracle. Their sampling distribution need not coincide with backward sampling from that modified oracle, since the modification can change both its image and its preimage sets. We show that this discrepancy has negligible statistical cost. Only a small number of image elements and preimage sets are affected, and a uniformly selected image element encounters these changes with negligible probability. This establishes closeness of the joint distributions of T and the modified oracle, rather than merely closeness of the selected outputs. After this step, every yi has a designated input vi in the original oracle, but those with i ∈ I1 remain hidden. Canceling the global bias introduced by backward sampling. Next, for all x satysfying H(x) ∈ / {yi }i∈[p(n)] , we modify the value of H ∗ (x) to an independent uniform value outside {yi }i∈[p(n)] . That is, we resample entries of the constructed oracle H ∗ , but determine their locations using the original oracle H. A tempting argument is that, after fixing the selected outputs and all their preimage sets under H, the remaining entries of H are independent and uniform outside those outputs. Unfortunately, backward sampling prevents this argument from being correct. 11

Indeed, conditional on the original oracle being H = h, the probability of sampling any specified pairs {(yi , vi )}i∈I0 consistent with h is |Image(h)|−|I0 | ·

1 . h |PreImage (y )| i i∈I Y

0

Here the image and preimage sets are those of the original oracle H = h, before any modification. Now, consider the distribution of the remaining entries of h afterQwe fix the selected outputs and 1 their complete preimage sets under h: the preimage-size factors i∈I0 |PreImage are fixed, but h (y )| i

the factor |Image(h)|−|I0 | can still vary across completions of the remaining oracle entries. These completions therefore need not have equal conditional probabilities: backward sampling introduces a global bias into the unexposed part of the original table. We cancel this bias by temporarily changing the distribution of the original oracle. We introduce e that plays the same role as H, but have the following probability density (and all a new oracle H e in place of H): subsequent sampling and oracle-construction steps remain unchanged, using H |Image(h)||I0 | X . |Image(f )||I0 |

h i e =h = Pr H

f :{0,1}n →{0,1}n

The additional weight cancels the image-size factor from backward sampling exactly. Once the selected outputs, their designated inputs, and all entries mapping to them are fixed, the factors arising from choosing uniform preimages are also fixed. The remaining entries are now independent uniform values outside the selected outputs, so they can be replaced by fresh randomness. We show that this change of distribution has negligible statistical cost. The image size is sharply concentrated around (1 − e−1 )2n , and its polynomial power varies by only a negligible relative amount on typical tables. Notice that conditioned on {(vi , yi )}i∈[p(n)]

and

PreImageH ({yi }i∈[p(n)] ), e

e e the entries H(x) at inputs x ∈ / PreImageH ({yi }i∈[p(n)] ) are then independent and uniform over e Replacing {0, 1}n \ {yi : i ∈ [p(n)]}. At these inputs, the constructed oracle H ∗ still agrees with H. ∗ these entries of H by fresh independent values from the same distribution therefore leaves the joint distribution of T and H ∗ unchanged. We can then return to the original uniform oracle H e is only an intermediate tool helping us to analyze the at negligible statistical cost. That is, the H statistical closeness. In the remainder of the overview, H again denotes this uniformly sampled original oracle, while H ∗ denotes the constructed oracle supplied to the adversary.

Making the additional preimage locations hidden. Having refreshed the entries at inputs x satisfying H(x) ∈ / {yi : i ∈ [p(n)]}, we next consider the preimages of y1 , . . . , yp(n) under H. For each i, the input vi is one preimage of yi , but yi may also have other preimages. We now modify H ∗ at all such preimages except v1 , . . . , vp(n) ; that is, at inputs in S = PreImageH ({yi }i∈[p(n)] ) \ {v1 , . . . , vp(n) }.

(1)

Previously, for an input x in this set with H(x) = yi , H ∗ (x) was yi for i ∈ I0 , and an independent uniform value in {0, 1}n \ {yj : j ∈ I1 } for i ∈ I1 . We now replace H ∗ (x) in both cases by an independent uniform value in {0, 1}n \ {yj : j ∈ [p(n)]}. We leave the entries at v1 , . . . , vp(n) unchanged: H ∗ (vi ) = yi for i ∈ I0 , while H ∗ (vi ) remains a previously sampled uniform value in {0, 1}n \ {yj : j ∈ I1 } for i ∈ I1 . 12

Thus, the versions of H ∗ before and after this modification can differ only at inputs in the set S defined in Eq. (1). We plan to use O2H to argue that the adversary cannot distinguish these two versions. To do so, we need to bound the probability that a query hits S. Let B be the good event that (i) the selected outputs {yi }i∈[p(n)] are distinct, (ii) every output of H has at most n preimages, and (iii) |Image(H)| ≥ 2n−1 . It follows from standard collision bounds and random-function concentration bounds that Pr[B] = 1 − negl(n). Conditioned on event B, it hold that |S| ≤ p(n)n. But this size bound alone is insufficient for O2H: a small set can still be easy to query if the adversary’s input reveals its location. We instead prove that S is hidden in the particular experiment used to bound the query-hitting probability. Consider the new experiment with the modified H ∗ . For analysis, condition on the good event B and all pairs {(vi , yi )}i∈[p(n)] , including the inputs with i ∈ I1 that are not revealed to the adversary. Once these pairs are fixed, the H ∗ depends only on fresh randomness, whereas S depends on the original H. The adversary’s interaction with H ∗ is therefore conditionally independent of S. Moreover, the original sampling procedure is invariant under permutations of the domain fixing all designated inputs {vi }i∈[p(n)] . Conditional on the designated pairs, the good event B, and |S| = s, the set S is consequently a uniform s-element subset of the remaining domain. Hence a measured query in this experiment hits S with probability at most Pr[measured query lies in S] ≤

p(n)n 2n − p(n)

.

O2H now bounds the distinguishing advantage of a q-query adversary by s p(n)n 2q + negl(n) = negl(n). n 2 − p(n) The order of these arguments is essential. We first change the joint distribution to obtain conditional independence, then use symmetry to bound the query-hitting probability, and only then apply O2H. We do not infer that a hidden-set hitting probability is preserved merely because two distributions of the adversary’s visible information are close. Also, conditioning on the designated pairs is only an analytical tool: no reduction receives them as oracle-dependent advice. Identifying backward and forward sampling after resampling. The constructed oracle H ∗ now depends only on the designated pairs and fresh randomness. It no longer exposes information about additional preimages in the original table. At this point, we change the sampling only for i ∈ I0 : instead of choosing yi uniformly from Image(H) and then a uniform preimage vi , we choose vi uniformly from {0, 1}n and set yi = H(vi ). The positions with i ∈ I1 already use forward sampling and remain unchanged. Symmetry shows that these two ways of generating the designated pairs become statistically interchangeable after the preceding oracle modifications. Conditional on distinct designated inputs and distinct selected outputs, permutations of the domain and range act transitively on the possible tuples {(vi , yi )}i∈[p(n)] . Both the mixed sampling procedure before this change and the all-forward procedure after it are invariant under these permutations; thus, they induce the same conditional distribution on the tuples. Given such a tuple, the constructed oracle H ∗ supplied to the adversary is generated by the same rule in both experiments. Consequently, the two experiments have the same conditional joint distribution of T and H ∗ . The excluded collision events contribute only negligible statistical error. This argument does not identify the original joint distributions of T and H. Rather, it establishes statistical closeness of the joint distributions of T and H ∗ after the preceding resampling steps have removed the dependence of H ∗ on the original preimage sets beyond the information specified by {(vi , yi )}i∈[p(n)] . 13

Restoring the original random oracle. Now that every pair is generated by forward sampling, we can undo the remaining oracle modifications using quantum collision-finding and preimagesearch bounds, together with O2H. First, restore the entries at the undisclosed inputs mapping to selected outputs. Querying such an input produces a second input with the same original output as a designated input, and hence a collision in the original random function. The reduction generates the designated pairs with polynomially many queries and simulates the relevant intermediate oracle by explicitly reprogramming the designated inputs with ri = 1. Quantum collision-finding bounds make the resulting query-hitting probability negligible. Finally, restore the entries at those hidden designated inputs. Hitting one of them entails finding a preimage of one of the forward-sampled outputs with ri = 1. A quantum multi-target preimagesearch bound applies to this distribution. The pairs revealed at positions ri = 0 are generated by additional oracle queries within the same reduction, rather than supplied as oracle-dependent advice. O2H then shows that restoring these last entries is indistinguishable. The resulting experiment is exactly D1 with access to the unmodified random oracle. We remark that the main work of this proof is not the final invocation of O2H or of quantum collision and preimage bounds. It is the distributional preparation that makes these quantum tools useful: canceling the global bias of image sampling, refreshing the unexposed oracle entries, and proving that the remaining disagreement locations are hidden. This allows the proof to handle the entire collection jointly, with bounds depending only on the number of oracle queries and not on the adversary’s intervening computation. 2.5

Quantum Black-Box Impossibility via a Universal Decision Oracle

We construct an oracle world in which post-quantum injOWFs and i O exist, but every NP ∩ coNP problem produced by a fully black-box construction is easy. Besides the source oracle, which implements the two primitives, this world contains a decision oracle: an additional interface that solves the decision problems arising from such constructions. Both the adversary and the security reduction may query this interface, including in superposition. The challenge is therefore to make it powerful enough to defeat every proposed construction of NP ∩ coNP languages without enabling quantum attacks on the source primitives, i.e., injOWFs and i O. A powerful decision oracle with short certificates. An NP ∩ coNP problem has two verifiers: one certifies membership, and the other certifies nonmembership. For each input, exactly one verifier has an accepting witness. Following [BDV17], our oracle Decide takes such a verifier pair and an input, and returns the side with an accepting witness. There is an essential restriction on the pairs it accepts. Call a source implementation admissible if it satisfies the primitives’ functional requirements, such as injectivity and correct evaluation of obfuscated programs; it need not satisfy their security requirements. A verifier pair is valid only if, for every input and every admissible source implementation, exactly one side has an accepting witness. We call this property universal complementarity. Invalid pairs receive ⊥. The universality matches the functional guarantee of a fully black-box construction: its output must define an NP ∩ coNP problem for every functionally correct implementation of its sources. Thus, Decide solves the constructed problem, but need not solve arbitrary verifier pairs that happen to be complementary for the particular sampled oracle. This restriction also protects the sources. Fix a valid decision query and one source oracle, called the reference oracle, against which we compare later modifications. If the verifiers make at most r source queries, an accepting witness under the reference oracle uses at most r oracle answers. Any modification preserving those answers preserves acceptance. Universal complementarity 14

prevents the opposite side from also accepting, so the decision bit cannot change. Each decision answer therefore has a small critical set, even though finding its witness may require unbounded computation. This stability property is inherited from [BDV17]. From local stability to quantum security. Quantum queries may place amplitude on many inputs simultaneously, and their amplitudes depend on earlier oracle interactions. Consequently, an unconditional bound on the probability that a fixed answer changes is insufficient. To resolve this difficulty, we establish a conditional-coupling lemma, which is similar to the quantum hybrid from [Unr14, ARU14]. For coupled oracles (F1 , F2 ), suppose that Pr[F1 (u) ̸= F2 (u) | F2 ] ≤ γ

for every reference realization F2 and input u.

Then, for a T -query quantum algorithm whose initial state is independent of the sampled oracle pair, √ the expected trace distance between its final states under F1 and F2 is at most 2T γ. Conditioning on the entire reference oracle accommodates the dependence of its query states on that oracle. We apply this bound to the combined source and decision interfaces; critical sets control disagreement at decision queries. As a warm-up, let f : {0, 1}n → {0, 1}n+1 be a random injection. Sample y uniformly outside its image and plant y at an independent uniform input x, obtaining g. The joint distribution of (g, x, y) is exactly that obtained by sampling a uniform injection g and an independent uniform input x, and setting y = g(x). In contrast, under the reference function f , the same challenge has no preimage. Conditioned on f and y, a fixed decision answer changes only if x hits its critical set, with probability at most r/2n for verifiers making at most r source queries. Checking an inverter’s output with one additional query therefore gives p Pr[invert] ≤ 2(T + 1) r/2n . Thus, the unbounded decision interface does not destroy one-wayness, even when queried coherently. Obfuscation with adaptive quantum side information. Following [BDV17], we implement obfuscation by an injective encoding table mapping a circuit and randomness (C, r) to a handle b An evaluation oracle executes the circuit encoded by that handle; the obfuscated program is a C. wrapper calling this interface. We must also specify evaluation on handles outside the table’s image. b to each (possibly malformed) handle C. b If C b A backup map φ assigns a circuit description φ(C) b b is outside the image, the evaluation oracle answers a query (C, z) according to φ(C); otherwise, it evaluates the circuit encoded by the table. The admissible oracle family allows every such backup map. This freedom lets us move a challenge handle out of the encoding table while preserving its visible functionality. The principal difficulty is adaptive challenge selection: the adversary chooses C0 , C1 after oracle access and retains a quantum state correlated with the encoding table. Reprogramming only the eventual challenge entry does not establish the required independence. We use the row-reprogramming architecture of [BDV17], analyzing the full joint distribution of the oracle, challenge, and residual quantum state. First, we sample the uniform tape r ∈ {0, 1}n that will be used to generate the challenge handle. For the pre-challenge execution only, we replace the encoding table on the entire row {(C, r) : C} by an ordered tuple D of distinct fresh handles outside the original table’s image. The challenge and post-challenge oracle still use the original table. The coupling hides this modification: each fixed source query changes with probability O(2−n ), and critical sets give an O(q2−n ) bound for decision queries whose verifiers make at most q source queries. Conditioned on r, D, and the modified prechallenge oracle, the adversary’s classical outputs and residual quantum state are independent of 15

b uniformly outside the the erased original row. We can therefore sample the challenge handle C b This original table’s image and D, and reprogram the post-challenge table to map (Cb , r) to C. replacement preserves exactly the joint distribution of the challenge bit, pre-challenge output state, challenge handle, and post-challenge oracle. Next, we restore only the original pre-challenge oracle, retaining both the fresh challenge handle and the single-entry post-challenge reprogramming. Closeness of averaged states would not suffice here, because the subsequent computation depends on the reprogramming randomness. Instead, our coupling bound controls the expected trace distance of paired executions. More precisely, for each fixed original oracle, let ρr,D and ρref be the complete pre-challenge output states under the modified and original oracles, respectively. The bound controls Er,D [TD(ρr,D , ρref )], rather than merely the distance between the averaged states. For each fixed (r, D, b), challenge generation and the post-challenge execution form the same channel in the two experiments, so contractivity applies before averaging. With the original pre-challenge oracle restored, the pre-challenge output state is independent of r, and the selected circuits again satisfy C0f ≡ C1f . Finally, we undo the single-entry post-challenge reprogramming, restoring the original table b = C0 . The fresh handle C b is now outside the table’s image, so it is value at (Cb , r), and set φ(C) evaluated through the backup map. Evaluation at this publicly known handle is unchanged because Cbf ≡ C0f . The source interfaces can differ only at the encoding query (Cb , r) and at evaluation queries using its original handle. These locations are hidden by the uniform tape r, allowing another application of critical sets and the coupling bound. The final experiment is independent of the challenge bit. Throughout these comparisons, validity is tested against the same family containing all backup maps, so every modification remains admissible and the stability argument continues to apply. Preserving one-wayness and concluding. To preserve one-wayness after adding obfuscation, we fix the encoding and backup tables and coherently simulate their interfaces using the injOWFonly oracle. One subtlety is that fixing these tables can make a previously invalid verifier pair complementary. The simulation must therefore retain the original universal-validity test before translating decision queries. This predicate is independent of the sampled function, so its finite truth table can be hardwired in the query-bounded simulation. Our bounds restrict evaluation lengths and verifier resources in addition to external query counts. Every efficient construction and reduction meets these restrictions for some polynomial bound. The two source primitives thus remain quantum-secure, whereas one decision query solves the constructed language exactly. A fully black-box security reduction would turn this solver into an attack on a source primitive, giving the contradiction.

3

Preliminaries

Notation. Let PPT denotes for a probabilistic polynomial time, and QPT denotes for quantum polynomial time. We say that a function f (n) is negligible in n if f (n) = n−ω(1) , and we denote this by f (n) = negl(n). We say that a function g(n) is polynomial in n if g(n) = p(n) for some fixed polynomial p, and we denote this by g(n) = poly(n). When we consider a non-uniform QPT adversary, we often specify it by a sequence of polynomialsize quantum circuits with quantum advice {Aλ , ρλ }λ∈N . In an execution with the security parameter λ, A runs Aλ taking ρλ as the advice. For simplicity, we often omit the index λ and just write Aρ to mean a non-uniform QPT algorithm specified by {Aλ , ρλ }λ∈N . If R is a random variable (or distribution), then r ← R denotes sampling r according to R. If T $

is a finite set, then i ← − T denotes sampling i uniformly at random from T . Throughout this work, 16

we take the convention that once we need to sample from an empty set, the output is defined to be some special symbol (e.g., ⊥ or 0n ). For t ∈ N, we use [t] to denote the set [t] := {1, . . . , t}. For x ∈ {0, 1}∗ , we write |x| for its bit length. For i ∈ N, we write ⟨i⟩ for the standard binary representation of i without leading zeros. For i ∈ {0, . . . , 2ℓ − 1},we write ⟨i⟩ℓ denotes its ℓ-bit binary representation, padded with leading zeros when necessary. We collect more basic preliminaries in Sec. A. 3.1

Random Oracles

Let O denote the distribution over functions O : {0, 1}∗ → {0, 1} obtained by independently $

sampling O(x) ← − {0, 1} for every x ∈ {0, 1}∗ . We refer to O ← O as a random oracle. Thus, O denotes the distribution of random oracles, whereas O denotes a particular oracle sampled from this distribution. As in [GIK+ 23], a single random oracle O : {0, 1}∗ → {0, 1} can be viewed as simultaneously providing independent random functions of arbitrary polynomially bounded input and output lengths. The following lemma justifies this interpretation by setting m(n) = n. Lemma 1 ([GIK+ 23, Lemma 3.7]). For any function m : N → N, a random oracle O ← O can be interpreted as a countably infinite family of mutually independent random functions {On,m : {0, 1}n → {0, 1}m(n) }n∈N . In particular, for every n ∈ N, we write On as the uniform distribution over all functions from {0, 1}n to {0, 1}n , where each instance is denoted by On . Throughout this paper, we will often need to sample oracles with proper input and output lengths as On,m ← On,m . When the input and output lengths are clear from the context, we will simply write O ← O, omitting the subscripts n and m. Oracle access. For an oracle algorithm A, we write A|O⟩ to indicate that A is given quantum oracle access to O. The quantum access to On,m is implemented through the standard unitary UOn,m : |x⟩ |y⟩ 7−→ |x⟩ |y ⊕ On,m (x)⟩ , for x ∈ {0, 1}n and y ∈ {0, 1}m(n) . We refer to one application of UOn,m as one quantum query to On,m . Classical oracle access corresponds to querying this unitary on computational-basis states. When we write h i Pr b = 1 : b ← A|O⟩ (x) , O←O

the probability is taken over the sampling of O ← O as well as all internal randomness and measurement outcomes of A. 3.2

Useful Lemmas

Lemma 2 ([YZ21, Corollary 4.13]). For any n, m, q ∈ N, any fixed y ∈ {0, 1}n , and any quantum algorithm A making at most q quantum queries to a random oracle On : {0, 1}m → {0, 1}n , we have h i (2q + 1)2 Pr On (x) = y : x ← A|O⟩ (y) ≤ . O←O 2n 17

$

Taking the probability over y ← − {0, 1}n in the above lemma, we have the following corollary. Corollary 1. For any n, m, q ∈ N and any quantum algorithm A making at most q quantum queries to a random oracle On : {0, 1}m → {0, 1}n , we have h i (2q + 1)2 Pr On (x) = y : x ← A|O⟩ (y) ≤ . $ 2n O←O,y ← −{0,1}n Lemma 3 (Preimage Resistance). For any n, m, q ∈ N and any quantum algorithm A making at most q quantum queries to a random oracle On : {0, 1}n → {0, 1}n , we have h i 2n(2q + 1)2 + 1 Pr On (x) = On (x′ ) : x ← A|O⟩ (On (x′ )) ≤ . $ 2n O←O,x′ ← −{0,1}n Proof. We first show that, over the random choice of O ← O, the following event occurs with probability at most 2−n : – E: max

y∈{0,1}n

PreImageOn (y) > 2n

Then, X

Pr [E] ≤

O←O

X

y∈{0,1}n S⊆{0,1}n |S|=2n+1

=

X

X

Pr [On (z) = y for every z ∈ S]

O←O

(Union Bound)

Y 1

2n y∈{0,1}n S⊆{0,1}n z∈S |S|=2n+1  n  2 n −n(2n+1)

=2

2 2n + 1 (2n )2n+1 −n(2n+1) 2n ≤ 2n 2 = (2n + 1)! (2n + 1)! 2n 2n 1 ≤ n = n. = Qn 4 2 i=1 (2i)(2i + 1) We then observe that, for each fixed oracle O and each y ∈ {0, 1}n ,   |{z ∈ {0, 1}n : On (z) = y}| Pr On (x′ ) = y = . n $ 2 ′ n x← −{0,1}

(2)

We can now bound the success probability using Eq. (2): h i Pr On (x) = On (x′ ) : x ← A|O⟩ (On (x′ )) $ O←O, x′ ← −{0,1}n   h i X   Pr On (x′ ) = y Pr On (x) = y : x ← A|O⟩ (y)  = EO←O  $ −{0,1}n y∈{0,1}n x′ ←   h i X 2n ≤ n EO←O  Pr On (x) = y : x ← A|O⟩ (y)  + Pr [E] (Eq. (2)+ conditional on ¬E) O←O 2 n y∈{0,1}

18

h i On (x) = y : x ← A|O⟩ (y) + Pr [E] Pr O←O $ O←O, y ← −{0,1}n 2n(2q + 1)2 ≤ + Pr [E] O←O 2n 2n(2q + 1)2 + 1 . ≤ 2n = 2n

(Corollary 1) (PrO←O [E] ≤ 2−n )

This completes the proof of Lem. 3. Corollary 2 (Multi-Target Preimage Resistance). For any n, m, k, q ∈ N and any quantum algorithm A making at most q quantum queries to a random oracle On : {0, 1}n → {0, 1}n , we have # "
2 $ n, 2n 2(q + k) − 1 + 1 O ← O, x , . . . , x ← − {0, 1} 1 k ≤k· . Pr ∃i ∈ [k], On (x) = On (xi ) : 2n x ← A|O⟩ (On (x1 ), . . . , On (xk )) Proof. The main idea is to reduce the multi-target preimage search problem to a single-target preimage search problem. Assume that there exist a quantum algorithm A that can find a preimage of one of the k targets with high probability ,i.e.. # "
2 $ n 2n 2(q + k) − 1 + 1 O ← O, x , . . . , x ← − {0, 1} , 1 k >k· Pr ∃i ∈ [k], On (x) = On (xi ) : . 2n x ← A|O⟩ (On (x1 ), . . . , On (xk )) We can construct a new quantum algorithm B making at most q + k − 1 quantum queries to the oracle On that breaks Lem. 3 as follows: Algorithm 3.1: Reduction B

B(y ∗ ) $

1. Sample index j ← − [k]. $

2. Set yj = y ∗ , sample xi ← − {0, 1}n and set yi = On (xi ) for all i ∈ [k] \ {j}. 3. Output A|O⟩ (y1 , . . . , yk ) Define the index set I(x) = {i : On (x) = yi } which corresponds to the set of indices of the targets that x is a preimage of. Notice that. Pr[A succeeds] ≤ Pr[I(x) ̸= ∅] We have that since j is sampled uniformly at random from [k] and B succeeds if and only if j ∈ I(x), we have Pr[B succeeds] ≥ Pr[j ∈ I(x)|I(x) ̸= ∅] Pr[I(x) ̸= ∅] 1 ≥ · Pr[A succeeds] k
2 2n 2(q + k − 1) + 1 + 1 > 2n
2 2n 2(q + k) − 1 + 1 > , 2n which contradicts Lem. 3.

19

Lemma 4 ([Zha15, Theorem 3.1]). For any n, m, q ∈ N and any quantum algorithm A making at most q quantum queries to a random oracle On : {0, 1}m → {0, 1}n , we have i q3 On (x) = On (x′ ) ∧ x ̸= x′ : (x, x′ ) ← A|O⟩ ≤ O( n ). O←O 2 Pr

h

The following lemma, usually referred to as the one-way-to-hiding lemma, serves as an important tool in the proof of Lem. 10. Lemma 5 ([AHU19, Theorem 3]). Let S be a random subset of X. Let G, H : X → Y be arbitrary random functions satisfying G(x) = H(x) for all x ∈ / S. Let z be an arbitrary, possibly random string. (S, G, H, and z may have arbitrary joint distribution.) Let A be a quantum oracle algorithm making at most q quantum queries to its oracle. Define B H to be the oracle algorithm that, on input z, proceeds as follows: $

1. sample i ← − [q]; 2. run AH (z) until immediately before its i-th query; 3. measure all query-input registers in the computational basis and output the set T of measurement outcomes. Define   Pleft := Pr b = 1 : b ← AH (z) ,   Pright := Pr b = 1 : b ← AG (z) , and   Pguess := Pr S ∩ T ̸= ∅ : T ← B H (z) . Here, the probabilities are taken over the joint distribution of (S, G, H, z), the internal randomness and measurement outcomes of the corresponding algorithms. Then, for any joint distribution of G, H, S, z, it holds that p |Pleft − Pright | ≤ 2q Pguess . 3.3

Simulating Two Oracles using One

In this subsection, we recall that joint quantum queries to two oracles can be simulated exactly using separate access, with constant query overhead and linear additional gate cost per query. Consequently, security with respect to two independent quantum-accessible random oracles is preserved under the following implementation O0 (x) = O(0∥x),

O1 (x) = O(1∥x),

where O is a single quantum-accessible random oracle. Separate and joint oracle access. Let O0 , O1 : {0, 1}n → {0, 1}n be functions. Separate quantum access to these functions provides the query unitaries UOb : |x⟩ |y⟩ 7−→ |x⟩ |y ⊕ Ob (x)⟩

(∀b ∈ {0, 1}).

Each oracle call applies one of these two unitaries, while the algorithm may perform arbitrary quantum operations between calls. In particular, its registers may be arbitrarily entangled. 20

Joint access additionally allows the oracle index to be queried in superposition through the unitary UO0 ,O1 : |b⟩ |x⟩ |y⟩ 7−→ |b⟩ |x⟩ |y ⊕ Ob (x)⟩ . The following lemma shows that this joint interface can be implemented using separate access. Lemma 6 (Simulation of the Joint Oracle). Given separate access to O0 and O1 , the unitary UO0 ,O1 can be implemented exactly using two queries to each oracle and O(n) additional gates. The simulation uses an n-qubit ancilla initialized and returned to |0n ⟩. Proof. Introduce an n-qubit ancilla register t, initialized to |0n ⟩. On a computational-basis input |b⟩ |x⟩ |y⟩ |0n ⟩, perform the following steps. 1. Apply UO0 to (x, t) to compute O0 (x) into t, obtaining |b⟩ |x⟩ |y⟩ |O0 (x)⟩ . 2. XOR t into y conditioned on b = 0, obtaining |b⟩ |x⟩ |y ⊕ (1 − b)O0 (x)⟩ |O0 (x)⟩ . 3. Apply UO0 again to (x, t) to uncompute t. Since UO0 is an XOR-query unitary, the resulting state is |b⟩ |x⟩ |y ⊕ (1 − b)O0 (x)⟩ |0n ⟩ . 4. Repeat the above procedure using O1 , with the XOR conditioned on b = 1. This gives |b⟩ |x⟩ |y ⊕ (1 − b)O0 (x) ⊕ bO1 (x)⟩ |0n ⟩ . Since y ⊕ (1 − b)O0 (x) ⊕ bO1 (x) = y ⊕ Ob (x), the procedure implements UO0 ,O1 and returns the ancilla to |0n ⟩. By linearity, the simulation is exact for arbitrary inputs, including those entangled with other registers. The procedure makes two queries to each oracle. Each controlled-XOR operation requires O(n) gates, yielding the claimed gate complexity. 3.4

Non-Interactive Zero-Knowledge Proof

We begin by recalling the definitions necessary for formalizing NIZK proof systems in our setting. Definition 1 (Polynomial-Query-Bounded Quantum Oracle Algorithm). We say that a quantum oracle algorithm A(·) is polynomial-query-bounded if there exists a polynomial p : N → N such that, for every input x ∈ {0, 1}∗ and every oracle H, the execution of A|H⟩ makes at most p(|x|) quantum queries to H. Definition 2 (Efficiently-Approximable Constant). We say that a constant (real number) γ ∈ (0, 1) is Efficiently-Approximable if there exists a polynomial-time deterministic algorithm Approxγ such that for all n ∈ N, – Approxγ (1n ) outputs a rational number γ b = a/b, where a, b are integers in binary representation. – For all n ∈ N, |γ − Approxγ (1n )| ≤ 21n . 21

Then, we recall the definition of NIZK proof systems in the Z-Tamperable-Hidden-Bits model, which is a variant of the standard NIZK proof system that allows for tampering with hidden bits. Definition 3 (NIZK Proof in the ZHB Model [GIK+ 23, Definition 4.2]). An (unboundedprover) non-interactive zero-knowledge (NIZK) proof system in the Z-Tamperable-Hidden-Bits(ZHB) model for a language L is a family of algorithms {Πγ = (Genγ , Pγ , Vγ )} parameterized by EfficientlyApproximable constants γ ∈ (0, 1), where: – Genγ (1n ) is a PPT hidden bit string generator that given an input length n outputs a hidden bit string r ∈ {0, 1}pγ,hbs (n) for some (fixed) polynomial pγ,hbs where each bit ri of r is sampled independently from a Bernoulli distribution with Pr[ri = 1] = γ b where γ b = Approxγ (1n ). – Pγ (r, x) is an (unbounded, randomized) honest prover algorithm that takes as input a hidden bit string r ∈ {0, 1}pγ,hbs (|x|) and x ∈ L, and outputs a set of indices I ⊆ [pγ,hbs (|x|)] and a proof π. – Vγ (x, I, {ri }i∈I , π) is a polynomial-time deterministic verifier that takes as input x, an index set I ⊆ [pγ,hbs (|x|)], the bits {ri }i∈I of the hidden bit string r corresponding to I, and a proof π, and outputs either 1 (accept) or 0 (reject). We require Π to satisfy the following completeness, soundness, and zero knowledge requirements: – Perfect Completeness: For all Efficiently-Approximable constants γ ∈ (0, 1) and all x ∈ L, h i Pr Vγ (x, I, {ri }i∈I , π) = 1 : r ← Genγ (1|x| ), (I, π) ← Pγ (r, x) = 1 where the probability is over the randomness of Genγ and Pγ . – (Adaptive) Statistical Soundness: For all Efficiently-Approximable constants γ ∈ (0, 1), there exists a negligible function negl(·) such that,

Pr

r←Genγ (1n )

[∃(x, I, f, π) such that x ∈ / L, |x| = n, Vγ (x, I, {e ri = ZeroFlip(ri , fi )}i∈I , π) = 1] ≤ negl(|x|)

where ZeroFlip(ri , fi ) = (ri ⊕ fi if ri = 0; ri if ri = 1). – Statistical Zero Knowledge: For all efficiently-approximable constants γ ∈ (0, 1) (as per Def. 2), there exists a PPT simulator Simγ , for all adversaries A, there exists a negligible function negl(·) such that all x ∈ L , h i | Pr A(x, I, {ri }i∈I , π) = 1 : r ← Genγ (1|x| ), (I, π) ← Pγ (r, x) − Pr[A(x, I ∗ , {ri∗ }i∈I ∗ , π ∗ ) = 1 : (I ∗ , {ri∗ }i∈I ∗ , π ∗ ) ← Simγ (x)]| ≤ negl(|x|) where the probability is over the randomness of Genγ , Pγ , Simγ , and A. Definition 4 (NIZK Proof in the QROM). An (unbounded-prover) non-interactive zero knowledge (NIZK) proof system in the quantum random oracle model (QROM) for a language L is a tuple of algorithms Π = (P (·) , V (·) ) with access to a random oracle O. – P O (x) is an (unbounded, randomized) honest prover algorithm that is given oracle access to a random oracle O, takes as input x ∈ L, and outputs a proof π. – V O (x, π) is a polynomial-time deterministic verifier that is given oracle access to a random oracle O, takes as input x and a proof π, and outputs either 1 (accept) or 0 (reject). 22

We require Π to satisfy the following completeness, soundness, and zero knowledge requirements: – Perfect Completeness: For all x ∈ L, it holds that   Pr V O (x, π) = 1 : π ← P O (x) = 1. O←O

– (Adaptive) Statistical Soundness: It holds that Pr [∃(x, π) such that x ∈ / L, |x| = n, and V O (x, π) = 1] ≤ negl(|x|).

O←O

– Zero Knowledge: There exists a stateful QPT simulator Sim = (SimProof, SimRO) such that for all x ∈ L andall polynomial-query-bounded quantum oracle algorithm A(·) (Def. 1), h i Pr A|O⟩ (x, π) = 1 : π ← P O (x) h i − Pr A|SimRO(st,·)⟩ (x, π ∗ ) = 1 : (st, π ∗ ) ← SimProof(x) ≤ negl(|x|). 3.5

Compressed Partially-Fixed Oracle

We introduced compressed partially-fixed oracles to simulate a random oracle conditioned on a prescribed classical table. This formulation adapts the compressed-oracle technique of [Zha19]. Our zero-knowledge simulator initializes the oracle with a prescribed classical table and retains its private state throughout subsequent quantum interaction. We therefore spell out this fixed-table specialization and its efficient sparse implementation. We first formalize the conditional oracle distribution. Definition 5 (Conditional Distribution of a Random Oracle). Let n, m ∈ N be parameters. A subset Q ⊆ {0, 1}n × {0, 1}m is a partial function if ∀(x, y), (x, y ′ ) ∈ Q, it holds that y = y ′ . We write dom(Q) := {x : ∃y such that (x, y) ∈ Q} and write Q(x) = y when (x, y) ∈ Q. Given a partial function Q, the conditional distribution of random oracle, denoted as O|Q , is the uniform distribution over all functions F : {0, 1}n → {0, 1}m consistent with Q. Equivalently, ( Q(x) x ∈ dom(Q), O|Q (x) := . $ m y← − {0, 1} x ∈ {0, 1}n \ dom(Q) In the above definition, the unspecified values are sampled independently once and then retained, so repeated queries to the same input return the same value. We next describe an efficient stateful simulation of quantum access to this distribution. For a stateful simulator C ← Com(H), access to |C⟩ means coherent access to its query procedure, with its private state retained between queries. We also write |Com(H)⟩ when initialization is implicit; all queries then use the same initialized simulator. Thus, A|Com(H)⟩ denotes A interacting coherently with a single initialized simulator whose private state is retained and updated between queries. The following lemma shows that quantum access to O|H can be simulated exactly by a stateful oracle, with time and space polynomial in n, m, |H|, and the number of queries. Lemma 7 (Compressed Partially-Fixed Oracle). Let n, m ∈ N be parameters. For a given partial function H ⊆ {0, 1}n ×{0, 1}m , there exists a (stateful) oracle Com(H) called the compressed partially-fixed oracle satisfying the following properties: 23

– Perfect Indistinguishability: For any (potentially unbounded) quantum algorithm A, h i h i Pr A|O|H ⟩ = 1 − Pr A|Com(H)⟩ = 1 = 0, where the first probability includes sampling O ← O|H , and both include the internal randomness and measurement outcomes of the interacting algorithms. – Efficient constructability: Initializing Com(H) and answering q queries require time and space polynomial in n, m, |H|, and q. Proof. We derive the lemma from Zhandry’s compressed-oracle simulation [Zha19]. Let S = dom(H), and let F : {0, 1}n → {0, 1}m be a uniformly random function. Define ( H(x), x ∈ S, GH,F (x) = F (x), x ∈ / S. Then GH,F is distributed uniformly among the functions extending H. Under the standard XOR-query convention, a quantum query to GH,F can be implemented using two queries to F . Specifically, first compute F (x) into a fresh scratch register. Then XOR H(x) into the response register when x ∈ S, and XOR the scratch register into the response register otherwise. Finally, use a second query to F to uncompute the scratch register. All computations involving H are performed coherently, with H hardwired. The resulting transformation is exactly |x, z, 0m ⟩ 7−→ |x, z ⊕ GH,F (x), 0m ⟩ . Define Com(H) by replacing access to F in this implementation with access to Zhandry’s ordinary compressed oracle. For any quantum algorithm A, its composition with the above implementation is itself a quantum oracle algorithm. Zhandry’s perfect simulation guarantee therefore implies that replacing the uniformly random oracle F by its compressed implementation preserves A’s acceptance probability exactly. Since GH,F is distributed as O|H , the claimed equality follows.

4 4.1

Strong δ-Dense PRHF: Definition and Construction Strong δ-Dense PRHF

Our definition of the strong δ-dense PRHF considers polynomially many correlated samples and only requires strong pre-image pseudorandomness against non-unifrom QPT quantum adversaries. In the zero-knowledge proof of [GIK+ 23], single-instance pre-image pseudorandomness is lifted to polynomially many samples through a coordinate-by-coordinate hybrid argument. The reduction for each adjacent pair non-uniformly fixes the hidden-bit string, the corresponding ZHB proof, and all samples outside the distinguished coordinate. Because this auxiliary information may depend on H, instantiating H with a random oracle would require security against adversaries whose advice depends on the sampled oracle. Formally, we introduce our notion of a Strong PRHF as follows. Definition 6 (Strong δ-Dense PRHF). Let δ ∈ (0, 1) be a Efficiently-Approximable constant as per Def. 2 and n ∈ N. Let ℓ : N → N be a polynomial, and let {Hn }n∈N be an ensemble of distributions over functions H : {0, 1}n → {0, 1}ℓ(n) . We call this ensemble a strong δ-dense post-quantum PRHF if the following conditions hold: 24

Box 1: Distributions D0 and D1 Distribution D0 (n, Hn , p(n), r):

Distribution D1 (n, Hn , p(n), r):

1. According to r = (r1 , . . . , rp(n) ), define the index sets:

1. According to r = (r1 , . . . , rp(n) ), define the index sets:

I0 := {i ∈ [p(n)] | ri = 0}

I0 := {i ∈ [p(n)] | ri = 0}

I1 := {i ∈ [p(n)] | ri = 1}

(= [p(n)] \ I0 ) .

I1 := {i ∈ [p(n)] | ri = 1}

2. Define preimage and image sets:

(= [p(n)] \ I0 ) . $

Image := {y ∈ {0, 1}ℓ(n) | ∃z ∈ {0, 1}n : H(z) = y}

− {0, 1}n and define 2. For all i ∈ [p(n)], sample vi ← yi := H(vi ).

PreImage(y) := {z ∈ {0, 1}n | H(z) = y}.

3. Output:
T = {ri }i∈[p(n)] , {yi }i∈[p(n)] , {vi }i∈I0 .

3. For all i ∈ [p(n)]: $

$

− − Image and vi ← (a) If ri = 0, then sample yi ← PreImage(yi ); $

− {0, 1}ℓ (n) \ Image. (b) If ri = 1, then sample yi ← 4. Output:
T = {ri }i∈[p(n)] , {yi }i∈[p(n)] , {vi }i∈I0 .

1. (δ-Density) For any function Hn : {0, 1}n → {0, 1}ℓ(n) , let pHn denote the probability that a $

random y ← − {0, 1}ℓ(n) is in the range of Hn . It holds that Pr [pHn ∈ [δ − negl(n), δ + negl(n)] : Hn ← Hn ] ≥ 1 − negl(n), 2. (Pseudorandomness) For all non-uniform QPT adversary A, it holds that # # " " $ $ n, ℓ(n) , x ← − {0, 1} y ← − {0, 1} n n Pr A(1 , Hn , Hn (x)) = 1 : − Pr A(1 , Hn , y) = 1 : ≤ negl(n). Hn ← Hn Hn ← Hn 3. (Strong Pre-Image Pseudorandomness) For any non-uniform QPT adversary A, any polynomial p(n), any bit-vector r = (r1 , . . . , rp(n) ), it holds that     Hn ← Hn ; Hn ← Hn ; Pr A(1n , Hn , T ) = 1 : − Pr A(1n , Hn , T ) = 1 : ≤ negl(n), T ← D0 T ← D1 where D0 and D1 are the D0 (n, Hn , p(n), r) and D1 (n, Hn , p(n), r), respectively, defined in Box 1. 4.2

Random Oracle is a Strong (1 − 1e )-Dense PRHF

In this subsection, we show that a random oracle is a strong (1 − 1e )-dense PRHF as per Def. 6. Remark 1 (Random Oracles as δ-dense PRHFs). We first need to clarify an important modeling subtlety: in Def. 6, the QPT adversary A receives the full description of H as input. However, this is impossible when we talk about an oracle construction, since the QPT adversary cannot receive the full description of a random oracle. Thus, when we say “a random oracle is a strong (1 − 1e )dense PRHF,” it actually means a variant of as per Def. 6 where the QPT adversary is modeled as a QPT oracle machine and receives quantum oracle access to H (which we will instantiate as a random oracle) instead of the full description of H. We take this modeling convention throughout the paper, whenever we instantiate the strong δ-dense PRHF with a random oracle. 25

The first two requirements of our strengthened δ-dense PRHF notion—δ-density and postquantum pseudorandomness—follow from established analyses of random oracles in [GIK+ 23] and [HXY19], respectively. For completeness, we list them as Lem. 8 and Lem. 9 below. Lemma 8 ([GIK+ 23, Lemma B.3]). Fixed any n ∈ N, let On : {0, 1}n → {0, 1}n be a random oracle. There exists negligible function negl(·) such that       1 1 1− Pr pOn ∈ − negl(n), 1 − + negl(n) ≥ 1 − negl(n), On ←On e e where pOn :=

Pr [∃x ∈ {0, 1}n : On (x) = y] . y← −{0,1}n $

Lemma 9 ([HXY19, Theorem 2]). For all QPT oracle-aided adversary A, it holds that " # " # $ $ n, n, x ← − {0, 1} y ← − {0, 1} |On ⟩ n |On ⟩ n Pr A (1 , On (x)) = 1 : − Pr A (1 , y) = 1 : ≤ negl(n). On ← On On ← On Explanation of Lem. 9. The result of [HXY19, Theorem 2] is actually more general: it considers a salted random oracle O : [K] × [N ] → [M ] for some K, N, M ∈ N and permits the adversary to receive an S-bit classical advice string that may depend on O. To obtain the lemma above, set K = 1, N = M = 2n , use no auxiliary advice, and let T = q(n) be the adversary’s polynomial query bound. The resulting distinguishing advantage is at most !   ! 4 1/6 2/3 q(n) q(n) e e O =O , 2n 2n/6 which is negligible in n. Identifying [2n ] with {0, 1}n through binary representation and omitting the trivial salt coordinate yields precisely the statement above. Strong Pre-Image Pseudo-randomness. To establish strong pre-image pseudo-randomness, we depart from the proof of [GIK+ 23]. We state the lemma below and prove it in Sec. 4.3. Lemma 10. For any non-uniform QPT oracle-aided adversary A, any polynomial p(n), and any bit-vector r = (r1 , . . . , rp(n) ), it holds that     On ← On ; On ← On ; |On ⟩ n |On ⟩ n ≤ negl(n), Pr A (1 , T ) = 1 : − Pr A (1 , T ) = 1 : T ← D0 T ← D1 where D0 and D1 are the D0 (n, On , p(n), r) and D1 (n, On , p(n), r), respectively, defined in Box 1. 4.3

Proof of Lem. 10

We proceed to prove Lem. 10. Our proof actually works for any (potentially unbounded) A as long as she makes only a polynomial number of quantum oracle queries. Notation. We will prove the lemma via a sequence of hybrids H0 , H1 , . . . , H6 . Each hybrid Hi depends on the same parameters including the security parameter n, the oracle distribution On , the polynomial p(n), the bit-vector r = (r1 , . . . , rp(n) ). For succinctness, we suppress them from the notation and simply write Hi , instead of Hi (n, On , p(n), r). 26

Throughout the proof, we use the convention that once we need to sample from an empty set, the output is defined to be some special symbol (e.g., ⊥ or 0n ). It is straightforward from the description that the output of H0 (Expr. 1) is identically distributed to that of A|On ⟩ (1n , T ) when On ← On and T ← D0 (n, On , p(n), r). Similarly, the output of H6 (Expr. 8) is identically distributed to that of A|On ⟩ (1n , T ) when On ← On and T ← D1 (n, On , p(n), r). Therefore, our goal is to show that the output distributions of H1 and H6 are negligibly close. i.d. For two hybrid experiments Hi and Hj , we write Hi == Hj if Pr[Hi = 1] = Pr[Hj = 1] for s every adversary A, Hi ≈ Hj if | Pr[Hi = 1] − Pr[Hj = 1]| is negligible for all possibly inefficient cq

adversaries A, and Hi ≈ Hj if | Pr[Hi = 1] − Pr[Hj = 1]| is negligible for every quantum adversary A making polynomially many oracle queries. 4.3.1

Hybrids H0 and H1

Hybrid H0 : This is the game corresponding to D0 . We formally describe it in Expr. 1. Experiment 1: Hybrid H0

( 1. According to the input r = (r1 , . . . , rp(n) ), define

I0 := {i ∈ [p(n)] | ri = 0} I1 := {i ∈ [p(n)] | ri = 1}

.

2. Sample On ← On ; ( ImageOn := {y ∈ {0, 1}n : ∃z ∈ {0, 1}n such that On (z) = y} 3. Define PreImageOn (y) := {z ∈ {0, 1}n : On (z) = y} 4. ∀i ∈ [p(n)], sample {yi }i∈[p(n)] and {vi }i∈I0 as follows: $

$

– If ri = 0, then set yi ← − ImageOn , vi ← − PreImageOn (yi ), $

– If ri = 1, then set yi ← − {0, 1}n \ ImageOn . 5. Invoke the adversary A|On ⟩ ({ri }i∈[p(n)] , {yi }i∈[p(n)] , {vi }i∈I0 ) Hybrid H1 : We present H1 in Expr. 2 and highlight its difference from H0 in red color. In this hybrid, we change the sampling method for yi when ri = 1 and redirect the points to form a new oracle On∗ . Experiment 2: Hybrid H1

( 1. According to the input r = (r1 , . . . , rp(n) ), define

I0 := {i ∈ [p(n)] | ri = 0} I1 := {i ∈ [p(n)] | ri = 1}

2. Sample On ← On ; ( ImageOn := {y ∈ {0, 1}n : ∃z ∈ {0, 1}n such that On (z) = y} 3. Define PreImageOn (y) := {z ∈ {0, 1}n : On (z) = y} ( I0 := {i ∈ [p(n)] | ri = 0} 4. Define I1 := {i ∈ [p(n)] | ri = 1} 5. ∀i ∈ [p(n)], sample {yi }i∈[p(n)] and {vi }i∈I0 as follows: 27

.

$

$

− PreImageOn (yi ), − ImageOn , vi ← – If ri = 0, then set yi ← $

− {0, 1}n , yi = On (δi ) – If ri = 1, then set δi ← ( S $ ← − {0, 1}n \ {yi }i∈I1 if z ∈ i∈I1 PreImageOn (yi ) ∗ 6. On (z) := On (z) otherwise ∗

7. Invoke the adversary A|On ⟩ ({ri }i∈[p(n)] , {yi }i∈[p(n)] , {vi }i∈I0 ) s

Claim 1. It holds that H0 ≈ H1 . The proof of Claim 1 is one of the most technically involved parts. We present it to Sec. 4.4. 4.3.2

Hybrid H2

We present H2 in Expr. 3 and highlight its difference from HS 1 in red color. In this hybrid, we fresh sample a fresh oracle On while preserving all the points in i∈I0 ∪I1 PreImage(yi ) and redirect S those “bad” points (some x not in Onfresh while preserving all the points in i∈I0 ∪I1 PreImage(yi ) but x 7→ yi in Ofresh ) to form a new oracle On∗ . Experiment 3: Hybrid H2

( 1. According to the input r = (r1 , . . . , rp(n) ), define

I0 := {i ∈ [p(n)] | ri = 0} I1 := {i ∈ [p(n)] | ri = 1}

.

2. Sample On ← On ( ImageOn := {y ∈ {0, 1}n : ∃z ∈ {0, 1}n such that On (z) = y} 3. Define PreImageOn (y) := {z ∈ {0, 1}n : On (z) = y} ( I0 := {i ∈ [p(n)] | ri = 0} 4. Define I1 := {i ∈ [p(n)] | ri = 1} 5. ∀i ∈ [p(n)] : $

$

– If ri = 0, then set yi ← − ImageOn , vi ← − PreImageOn (yi ) $

– If ri = 1, then set δi ← − {0, 1}n , yi = On (δi )  $   − {0, 1}n \ {yi }i∈I1 ← 6. On∗ (z) := On (z)   $ ← − {0, 1}n \ {y }

i i∈I0 ∪I1

∗⟩ |On

7. Invoke the adversary A

S if z ∈ i∈I1 PreImageOn (yi ) S if z ∈ i∈I0 PreImageOn (yi ) otherwise

({ri }i∈[p(n)] , {yi }i∈[p(n)] , {vi }i∈I0 )

s

Claim 2. It holds that H1 ≈ H2 . The proof of Claim 2 is another technically involved part of the proof. We present it in Sec. 4.5. 4.3.3

Hybrid H2.5

We introduce an intermediate hybrid H2.5 . The only difference is that H2.5 handles the i ∈ I0 case in the same manner as H2 (i.e., yi uniformly from the image of the random oracle, and then 28

sample δi uniformly from its preimage), but everything else is the same as in H3 . We present the full description of H2.5 in Expr. 4, highlighting its differences from H2 in red color. Experiment 4: Hybrid H2.5

( 1. According to the input r = (r1 , . . . , rp(n) ), define

I0 := {i ∈ [p(n)] | ri = 0} I1 := {i ∈ [p(n)] | ri = 1}

.

2. Sample On ← On ( I0 := {i ∈ [p(n)] | ri = 0} 3. Define I1 := {i ∈ [p(n)] | ri = 1} 4. ∀i ∈ [p(n)] : $

$

− PreImageOn (yi ), and define vi := δi . − ImageOn and δi ← – If ri = 0, then sample yi ← $

− {0, 1}n , yi = On (δi ) – If ri = 1, then set δi ←  S $   − {0, 1}n \ {yi }i∈I1 if z ∈ i∈I1 {δi } ← S 5. On∗ (z) := On (z) if z ∈ i∈I0 {δi }   $ ← − {0, 1}n \ {yi }i∈I0 ∪I1 otherwise ∗

6. Invoke the adversary A|On ⟩ ({ri }i∈[p(n)] , {yi }i∈[p(n)] , {vi }i∈I0 ) cq

Claim 3. It holds that H2 ≈ H2.5 . The proof of Claim 3 is another technically involved part of the proof. We present it in Sec. 4.6. 4.3.4

Hybrid H3

We present H3 in Expr. 5 and highlight its difference from H2 in red color. In this hybrid, we try to redirect less points and show the indistinguishability of the two oracles towards polynomial-query bound quantum adversary through one-way to hiding lemma. Experiment 5: Hybrid H3

( 1. According to the input r = (r1 , . . . , rp(n) ), define

I0 := {i ∈ [p(n)] | ri = 0} I1 := {i ∈ [p(n)] | ri = 1}

2. Sample On ← On 3. ∀i ∈ [p(n)] : $

– If ri = 0, then sample δi ← − {0, 1}n and define yi := On (δi ) and vi := δi . $

– If ri = 1, then set δi ← − {0, 1}n , yi = On (δi )  $   − {0, 1}n \ {yi }i∈I1 ← 4. On∗ (z) := On (z)   $ ← − {0, 1}n \ {y }

i i∈I0 ∪I1

S if z ∈ i∈I1 {δi } S if z ∈ i∈I0 {δi } otherwise

∗

5. Invoke the adversary A|On ⟩ ({ri }i∈[p(n)] , {yi }i∈[p(n)] , {vi }i∈I0 ) 29

.

s

Claim 4. It holds that H2.5 ≈ H3 . Proof. Let r = (r1 , . . . , rp(n) ) be the corresponding input vector. Define the following event: – Event E: for every distinct i, j ∈ [p(n)], it holds that yi ̸= yj . Since On (δi ) = yi , event E also implies that all the δi ’s are distinct. Conditional on the event E, the tuple {(δi , yi )}i∈[p(n)] has exactly the same distribution in both games: it is uniform over pairs of ordered lists with distinct entries within each list. To see this, both sampling procedures are invariant under arbitrary, independent relabelings of the domain and codomain. Those relabelings can map any such collision-free tuple to any other. Furthermore, it holds that once this tuple {(δi , yi )}i∈[p(n)] is fixed, the construction of On∗ is identical in both hybrids: the only retained original-oracle values are (i ∈ I0 ),

On (δi ) = yi

and all other entries are freshly sampled according to the same rules described in Expr. 4. Thus, the adversary’s views conditioned on E are identical. Next, we proceed to bound Pr[¬E] in both hybrids. In H2.5 , consider any pair {yi , yj }: if the index i belongs to I0 , conditional on On , then yi is uniform over Image(On ) and is independent of yj . Hence, for such an i ∈ I0 , it holds that   1 Pr [yi = yj ] = E H2.5 H2.5 |Image(On )| ≤ 2−n/2 + Pr [|Image(On )| ≤ 2n/2 ] H2.5

−n/2

=2

+ negl(n).

(Lem. 11)

Otherwise (also in H2.5 ), both i and j belong to I1 , it holds that Pr[yi = yj ] = 2−n + (1 − 2−n )2−n ≤ 21−n ≤ 2−n/2 for sufficiently large n. In H3 , all δi ’s are sampled independently and uniformly from {0, 1}n . Consequently, this bound Pr[yi = yj ] ≤ 2−n/2 holds for all pairs {yi , yj }i,j∈[p(n)] in H3 as well. Therefore, for either b ∈ {2.5, 3}, a union bound gives Pr[¬E] = Pr[∃ 1 ≤ i < j ≤ p(n) : yi = yj ] Hb Hb X ≤ Pr[yi = yj ] 1≤i<j≤p(n)

Hb

   p(n)  −n/2 ≤ 2 + negl(n) = negl(n). 2 We then have ∆(distr(V2.5 ), distr(V3 )) ≤ Pr [¬E] + Pr[¬E] H2.5 H3    p(n)  −n/2 ≤2 2 + negl(n) = negl(n), 2 where Vb denotes the adversary’s view in hybrid Hb . The negligible bound above is uniform over ρ. This completes the proof of Claim 4.

30

4.3.5

Hybrid H4

We present H4 in Expr. 6 and highlight its difference from H3 in red color. Experiment 6: Hybrid H4

( 1. According to the input r = (r1 , . . . , rp(n) ), define

I0 := {i ∈ [p(n)] | ri = 0} I1 := {i ∈ [p(n)] | ri = 1}

.

2. Sample On ← On ( I0 := {i ∈ [p(n)] | ri = 0} 3. Define I1 := {i ∈ [p(n)] | ri = 1} 4. ∀i ∈ [p(n)] : $

− {0, 1}n and define yi := On (δi ) and vi := δi . – If ri = 0, then sample δi ← $

− {0, 1}n , yi = On (δi ) – If ri = 1, then set δi ←  S $   − {0, 1}n \ {yi }i∈I1 if z ∈ i∈I1 {δi } ← S $ 5. On∗ (z) := ← − {0, 1}n \ {yi }i∈I0 ∪I1 if z ∈ i∈I0 ∪I1 PreImageOn (yi ) \ {δi }i∈I0 ∪I1    O (z) otherwise n ∗

6. Invoke the adversary A|On ⟩ ({ri }i∈[p(n)] , {yi }i∈[p(n)] , {vi }i∈I0 ) Remark 2. Note that the conditions in each piecewise oracle definition are checked sequentially, from top to bottom. Each condition is considered only if all preceding conditions are false; the first satisfied condition determines the applicable branch. The “otherwise” branch applies only if every preceding condition is false. This convention applies to both H3 and H4 . In particular, if δi = δj for some i ∈ I0 and j ∈ I1 , their common input is handled by the first branch in both hybrids. Thus, overlapping conditions are resolved consistently, including when designated inputs collide. i.d.

Claim 5. It holds that H3 == H4 . Proof. First, notice that the joint distribution of the following variables is identical in both hybrids: {(δi , yi )}i∈[p(n)]

(3)

i.d.

Then, to show H3 == H4 , it suffices to show that conditioned on these variables, the distribution of the oracle table of On∗ is also identical in both hybrids. Toward that, we consider the distribution of On∗ (z) for any z ∈ {0, 1}n conditioned on the above variables. We have the following cases: S 1. For z ∈ i∈I0 {δi }, both of the oracle return the same value yi S 2. For z ∈ i∈I1 {δi }, both of the oracle return a uniformly random value in {0, 1}n \ {yi }i∈I1 3. For the remaining z, conditioning on Expression (3) leaves On (z) independent and uniform over {0, 1}n . In H3 , On∗ (z) is sampled uniformly from {0, 1}n \ {yi }i∈I0 ∪I1 . In H4 , On (z) is retained if it lies outside {yi }i∈I0 ∪I1 ; otherwise, it is resampled uniformly from {0, 1}n \ {yi }i∈I0 ∪I1 . Thus, the remaining entries are independently uniform over {0, 1}n \ {yi }i∈I0 ∪I1 in both hybrids. i.d.

Thus, the two final oracles are identically distributed and we can conclude that H3 == H4 . This completes the proof of Claim 5.

31

4.3.6

Hybrid H5

We present H5 in Expr. 7 and highlight its difference from H4 in red color. Experiment 7: Hybrid H5

( 1. According to the input r = (r1 , . . . , rp(n) ), define

I0 := {i ∈ [p(n)] | ri = 0} I1 := {i ∈ [p(n)] | ri = 1}

.

2. Sample On ← On ( I0 := {i ∈ [p(n)] | ri = 0} 3. Define I1 := {i ∈ [p(n)] | ri = 1} 4. ∀i ∈ [p(n)] : $

− {0, 1}n and define yi := On (δi ) and vi := δi . – If ri = 0, then sample δi ← $

– If ri = 1, then set δi ← − {0, 1}n , yi = On (δi )  $ S  − {0, 1}n \ {yi }i∈I1 if z ∈ i∈I1 {δi } ← S 5. On∗ (z) := On (z) if z ∈ i∈I0 ∪I1 PreImageOn (yi ) \ {δi }i∈I0 ∪I1   On (z) otherwise ∗

6. Invoke the adversary A|On ⟩ ({ri }i∈[p(n)] , {yi }i∈[p(n)] , {vi }i∈I0 ) cq

cq

Claim 6. It holds that H4 ≈ H5 , where ≈ denotes indistinguishability against polynomial-query quantum adversary. Proof. We use one-way-to-hiding lemma to reduce indistinguishability to collision resistance. Apply Lem. 5 with auxiliary input z = ({ri }i∈[p(n)] S , {yi }i∈[p(n)] , {vi }i∈I0 ), G and H equal to the final oracle On∗ in H4 and H5 respectively, and S = i∈I0 ∪I1 PreImageOn (yi ) \{δi }i∈I0 ∪I1 . It is obvious that the two oracles agree outside S. Let q(n) be the query count of the fixed adversary and let B be thepmeasured-query extractor defined in Lem. 5. Then its distinguishing advantage is at most 2q(n) Pguess , where ∗

Pguess = Pr[T ∩ S ̸= ∅ : T ← B |On ⟩ (z)]. H5

(4)

Then, to finish the proof of Claim 6, it suffices to show that Pguess defined in (4) is negligible for any q(n)-query adversary. We proceed to establish that below. 1 Assume for contradiction that there is a polynomial poly(n) such that Pguess ≥ poly(n) for infinitely many n. We then construct an oracle-aided quantum algorithm CollisionFinder that can find a collision pair for oracle On with non-negligible probability as follows: CollisionFinder|On ⟩ : 1. Repeat the steps to produce z := ({yi }i∈[p(n)] , {vi }i∈I0 ) as in hybrid H5 ; In particular, record the values {δi }i∈I0 ∪I1 for later use. ∗

2. Invoke the oracle algorithm T ← B On (z) where the oracle On∗ is defined in the same manner as in the hybrid H5 . 3. Check whether there exists a t ∈ T such that On (t) = yi and t ̸= δi for some i ∈ I0 ∪ I1 . 4. If such a pair exists, then output the corresponding pair (δi , t) as the collision pair and halt. 32

Although CollisionFinder is given oracle access only to On , it can coherently simulate On∗ using recorded value in Step 1. It can be easily seen that whenever T ∩ S ̸= ∅, this CollisionFinder algorithm returns a collision for |On ⟩; hence the success probability of collision finding is at least Pguess , which is non-negligible. However, this contradicts Lem. 4. This completes the proof of Claim 6.

4.3.7

Hybrid H6

We present H6 in Expr. 8 and highlight its difference from H5 in red color. Experiment 8: Hybrid H6

( 1. According to the input r = (r1 , . . . , rp(n) ), define

I0 := {i ∈ [p(n)] | ri = 0} I1 := {i ∈ [p(n)] | ri = 1}

.

2. Sample On ← On ( I0 := {i ∈ [p(n)] | ri = 0} 3. Define I1 := {i ∈ [p(n)] | ri = 1} 4. ∀i ∈ [p(n)] : $

– If ri = 0, then sample δi ← − {0, 1}n and define yi := On (δi ) and vi := δi . $

– If ri = 1, then set δi ← − {0, 1}n , yi = On (δi ) 5. Delete the definition of On∗ . 6. Invoke the adversary A|On ⟩ ({ri }i∈[p(n)] , {yi }i∈[p(n)] , {vi }i∈I0 ) cq

cq

Claim 7. It holds that H5 ≈ H6 , where ≈ denotes indistinguishability against polynomial-query quantum adversary. Proof. We use one-way-to-hiding lemma to reduce indistinguishability to preimage finding. Apply Lem. 5 with auxiliary input S z = ({yi }i∈[p(n)] , {vi }i∈I0 ), G and H equal to the final oracle in H5 and H6 respectively, and S = i∈I1 {δi }. It is obvious that the two oracles agree outside S. Let q(n) be the query count of the fixed adversary and let B be the p measured-query extractor defined in Lem. 5. Then its distinguishing advantage is at most 2q(n) Pguess , where Pguess = Pr[T ∩ S ̸= ∅ : T ← B |On ⟩ (z)]. H6

(5)

Then, to finish the proof of Claim 7, it suffices to show that Pguess defined in (5) is negligible for any q(n)-query adversary. We proceed to establish that below. 1 Assume for contradiction that there is a polynomial poly(n) such that Pguess ≥ poly(n) for infinitely many n. We then construct an oracle-aided quantum algorithm PreImageFinder that, given challenge values z1 , . . . , zp(n) sampled as in Corollary 2, finds a preimage of one of these values under On with non-negligible probability, as follows: PreImageFinder|On ⟩ (z1 , z2 , ..., zp(n) ): 1. Repeat the steps to produce z := ({ri }i∈[p(n)] , {yi }i∈[p(n)] , {vi }i∈I0 ) as in hybrid H5 ; except for the following change in step 4: 33

– If ri = 1, set yi = zi 2. Invoke the oracle algorithm T ← B |On ⟩ (z) 3. Check whether there exists a t ∈ T such that such that On (t) = yi for some i ∈ I1 . 4. If such a pair exists, then output the corresponding point t as the targeted pre-image and halt. The substitution yi = zi for i ∈ I1 in Step 1 preserves the joint distribution of the oracle and the transcript π in H6 , since the challenge values in Corollary 2 are sampled in exactly the same manner as the corresponding yi . Whenever T ∩S ̸= ∅, PreImageFinder returns a point t satisfying On (t) = yi = zi for some i ∈ I1 . Hence, its success probability is at least Pguess , which is nonnegligible. This contradicts Corollary 2. This completes the proof of Claim 7.

s

4.4

Proof of Claim 1: H0 ≈ H1

4.4.1

Proof Strategy Overview s

We prove H0 ≈ H1 by establishing the stronger statement that the joint distributions of the complete oracle table and the indexed inputs supplied to A are statistically close in the two experiments. We first introduce the notation used throughout the proof in Sec. 4.4.2. We then establish useful technical lemmas concerning random oracles and their sampling distributions in Sec. 4.4.3. Finally, s in Sec. 4.4.4, we use these lemmas to construct the hybrid argument proving H0 ≈ H1 . b 0 and To analyze these joint distributions directly, we introduce the joint-output experiments H b 1 , defined in Expr. 9 and 19, respectively. Similar as H0 and H1 , these experiments have a input H bit vector r = (ri )i∈[p(n)] and output the complete oracle table together with the inputs that would be supplied to A, rather than invoking A. For convenience, we organize these inputs into two ordered tuples: T contains the labels yi at indices with ri = 1, and W contains the pairs (yi , vi ) at indices with ri = 0, both listed in increasing index order. These tuples and the associated sampling notation are defined formally in the following Sec. 4.4.2. The joint-output formulation allows us to compare distributions without tracking the adversary’s oracle queries. It also permits convenient changes in sampling order: conditional on the originally sampled oracle On and the fixed bit vector, the pairs comprising W are independent of one another, of T , and of the randomness used to modify the oracle. Thus, we may sample T and construct the reported oracle before sampling W , without changing their joint distribution. We then establish a chain of statistically close intermediate experiments, s s b0 ≈ b1, H ··· ≈ H

by gradually changing the sampling procedures and the reported oracle. Each transition incurs only negligible statistical distance, with bounds uniform over r. Finally, given r and the output of either joint-output experiment, we can reconstruct all indexed inputs and run A with the reported oracle. For each b ∈ {0, 1}, this common randomized transformation recovers Hb conditioned on r. Since randomized post-processing cannot increase stab 0 and H b 1 implies that of the corresponding tistical distance (Lem. 38), the statistical closeness of H s conditional experiments. Averaging over the common distribution of r therefore yields H0 ≈ H1 . 34

4.4.2

Notation

Let N = 2n . Since p(n) is polynomially bounded, we restrict attention to sufficiently large n such that p(n) < N . Write I0 = {i : ri = 0},

r = (ri )i∈[p(n)] ,

I1 = {i : ri = 1}.

To simplify the presentation, define the ordered tuples T = (yi )i∈I1 , W = ((yi , vi ))i∈I0 , with indices in increasing order. Given r, the pair (T, W ) contains precisely the labels and witnesses supplied to A. For any function f : {0, 1}n → {0, 1}n , use the image and preimage notation from the hybrids: Imagef = {y ∈ {0, 1}n : ∃z ∈ {0, 1}n , f (z) = y},

PreImagef (y) = {z ∈ {0, 1}n : f (z) = y}.

Let Kf denote the distribution of one positive label–witness pair: 1 , Kf (y, v) = |Image | |PreImagef (y)|  0,  

f

f (v) = y,

(6)

f (v) ̸= y.

Thus, sampling from Kf means sampling y uniformly from Imagef and then sampling v uniformly from PreImagef (y). The distribution Kf⊗a describes all a independently sampled positive pairs for some integer a. When a = 0, it is the point mass on the empty tuple. Finally, we recall the convention that once we need to sample from an empty set, the output is defined to be some special symbol (e.g., ⊥ or 0n ). 4.4.3

Technical Tools regarding Random Oracles

In this subsection, we establish several properties of random oracles that will be used in the proof s of H0 ≈ H1 . These results allow us to bound the abort probabilities and justify the changes in sampling across the subsequent hybrids. Lemma 11 (Image size of a random oracle). Fix any n ∈ N, let On be a random oracle from {0, 1}n to {0, 1}n . n/2 −n2n−1

Pr [|Image(On )| ≤ 2n/2 ] ≤ 2n2

On ←On

= negl(n).

Proof. Let L = ⌊2n/2 ⌋. For any fixed L-element subset A ⊆ {0, 1}n , independence of the oracle outputs gives  2n L Pr [Image(On ) ⊆ A] = . On ←On 2n Thus, by a union bound, Pr [|Image(On )| ≤ 2n/2 ] =

On ←On

Pr [∃A ⊆ {0, 1}n : |A| = L, Image(On ) ⊆ A]  n   2n 2 L ≤ L 2n On ←On

35



n L

L 2n

≤ (2 )

2n

2n/2 2n

2n/2

≤ (2n )

!2n

n/2 −n2n−1

= 2n2

Lemma 12 (Concentration of the Image Size). For any n ∈ N, let On : {0, 1}n → {0, 1}n be sampled from On , and let   µ := EOn ←On |ImageOn | . Then

  n!   1 2 1 1− 1− n ≥ 1− 2n ≥ 2n−1 . 2 e

µ = 2n Moreover, for every t ≥ 0, Pr



On ←On

|Image

On

   2t2 | − µ ≥ t ≤ 2 exp − n . 2

In particular, Pr

On ←On

h

 i  |ImageOn | − µ ≥ 23n/4 ≤ 2 exp −2 · 2n/2 .

(7)

Proof. For each y ∈ {0, 1}n , we have 

Pr

On ←On

y∈ / Image

On



 n 1 2 = 1− n . 2

For each y ∈ {0, 1}n , let Iy be the indicator of the event y ∈ ImageOn . Since X |ImageOn | = Iy , y∈{0,1}n

linearity of expectation gives µ=

X

X

E[Iy ] =

y∈{0,1}n

y∈{0,1}n

Pr

On ←On

  y ∈ ImageOn .

For any fixed y ∈ {0, 1}n , the event y ∈ / ImageOn occurs precisely when On (x) ̸= y for every x ∈ {0, 1}n . The oracle entries are independent and uniformly distributed, so Pr

On ←On



y∈ / Image

On



Y

=

n  1 2 Pr [On (x) ̸= y] = 1 − n . On ←On 2 n

x∈{0,1}

Substituting this identity into the expression for µ yields n

µ=2

  n! 1 2 1− 1− n . 2 36

Finally, the inequality 1 − u ≤ e−u for u ≥ 0 implies n   n 1 2 −n 2 1− n ≤ e−2 = e−1 . 2 Consequently,   1 µ≥ 1− 2n ≥ 2n−1 , e where the last inequality follows from e > 2 The image size is a function of the 2n independent oracle entries {On (x)}x∈{0,1}n . Changing any one entry changes the image size by at most one. Thus, lem. 36, with each ci = 1, gives     2t2 On Pr |Image | − µ ≥ t ≤ 2 exp − n . On ←On 2 Setting t = 23n/4 proves eq. (7). Lemma 13 (Preimage distribution for forward sampling). Fix n ∈ N. Sample On ← On $

and δ ← − {0, 1}n independently. Then i.d.

|PreImageOn (On (δ))| == 1 + X,

X ∼ Binomial(2n − 1, 2−n ).

Proof. Condition on δ = z and On (z) = y. The input z itself belongs to PreImageOn (y). Each of the remaining 2n − 1 inputs maps to y independently with probability 2−n . The claimed distribution follows, since it does not depend on the conditioned values z and y. $

Corollary 3 (of Lem. 13, tail bound for preimage size). Sample On ← On and δ ← − {0, 1}n independently. Then   Pr |PreImageOn (On (δ))| > log n = negl(n). $ δ← −{0,1}n , On ←On Proof. By Lem. 13, the preimage size is distributed as 1 + X, where X ∼ Binomial(2n − 1, 2−n ),

E[X] = 1 − 2−n < 1.

Let t = ⌊log n⌋. Since X is integer-valued, 1 + X > log n is equivalent to X ≥ t. For sufficiently large n, we have t ≥ 1. Applying Corollary 6 with µ = 1 gives   Pr |PreImageOn (On (δ))| > log n = Pr[X ≥ t]  e t ≤ e−1 t = negl(n). The final bound is negligible because t = Θ(log n) and (e/t)t = exp(−Θ(log n log log n)). Lemma 14 (Changing the sampling order). Let I1 be any fixed subset of [p(n)] where p(n) is a polynomially bounded function of n. The games G0 and G1 defined in Box 2 are statistically s close: G0 ≈ G1 . 37

Box 2: Games G0 and G1 : Changing the sampling order Game G0 (I1 ):

Game G1 (I1 ):

1. Sample On ← On .

− {0, 1}n . 1. ∀i ∈ I1 , sample yi ←

$

$

− {0, 1}n \ ImageOn . 2. ∀i ∈ I1 , sample yi ← (Recall our convention that yi is set to a special symbol (e.g., 0n ) if {0, 1}n \ ImageOn = ∅.)

2. Set T := {yi }i∈I1 . 3. Sample an oracle On where each On (x) is independently sampled from {0, 1}n \ T .

3. Set T := {yi }i∈I1 .

4. Output (On , T ).

4. Output (On , T ).

Proof. Write N := 2n and m := |I1 | = poly(n). The case m = 0 is immediate, so assume 1 ≤ m < N , as holds for all sufficiently large n. In this proof, instead of T , we use the ordered samples y = (y1 , . . . , ym ) in the output; replacing y by its underlying set T cannot increase statistical distance. Let P0 (·, ·) and P1 (·, ·) denote the probability mass functions of the joint distribution of (On , y) in G0 and G1 , respectively, and write PrGb for probability in game Gb . Define K(On ) := N − |ImageOn |. To make G0 well-defined when K(On ) = 0, set y = (0n , . . . , 0n ) in that case; the analysis below shows that this convention affects only a negligible probability mass. Define the bad event   (8) Ebad := |K(On ) − N/e| > N 3/4 ∨ (∃ 1 ≤ i < j ≤ m, s.t. yi = yj ) , and define the set of good output pairs by   yi ∈ / ImageOn for every i ∈ [m],   G := (On , y) : yi ̸= yj for every 1 ≤ i < j ≤ m, .   |K(On ) − N/e| ≤ N 3/4 For all sufficiently large n, in either game the output belongs to G exactly when Ebad does not occur. For a uniform random oracle, the missing-image count satisfies E[K(On )] = N (1 − 1/N )N = N/e + O(1) For a uniformly sampled random oracle, the missing-image count K(On ) = N − |ImageOn | satisfies  E[K(On )] = N

1−

1 N

N =

N + O(1). e

Since K(On ) differs from the image size only by subtraction from N , lem. 12 gives the same concentration bound for K(On ) around its expectation. Moreover, for all sufficiently large N , E[K(On )] −

N 1 ≤ N 3/4 . e 2

Therefore,  Pr

On ←On

   N 1 3/4 3/4 K(On ) − >N ≤ Pr |K(On ) − E[K(On )]| > N On ←On e 2 1

≤ 2e− 2 38

√

N

.

Otherwise, K(On ) = Ω(N ), and a union bound bounds the probability of a sample collision by
m 2 2 /K(On ) = O(m /N ). For all sufficiently large n, the case K(On ) = 0 is included in the deviation event. Hence, by Eq. (8), 1

Pr[Ebad ] = O(e− 2

√

G0

N

+ m2 /N ) = negl(n).

(9)

Fix (On , y) ∈ G. Since the samples are distinct, P0 (On , y) = N −N K(On )−m ,

P1 (On , y) = N −m (N − m)−N .

Set a := N −N (e/N )m . For every pair in G, K(On ) = (N/e)(1 + O(N −1/4 )), uniformly over these pairs. Consequently,

P0 (On , y) = a · exp O(mN −1/4 ) , P1 (On , y) = a · exp O(m2 /N ) . Since m = poly(n), there exists a negligible function ε = ε(n) such that, uniformly over (On , y) ∈ G, |P0 (On , y) − a| ≤ εa,

|P1 (On , y) − a| ≤ εa.

(10)

In particular, X

(1 − ε)|G|a ≤

P0 (On , y) ≤ 1.

(On ,y)∈G

Summing Eq. (10) therefore yields X 2ε |P0 (On , y) − P1 (On , y)| ≤ 2ε|G|a ≤ = negl(n). 1−ε

(11)

(On ,y)∈G

By Eq. (9) and (11), Pr[Ebad ] ≤ Pr[Ebad ] + Pr[(On , y) ∈ G] − Pr[(On , y) ∈ G] G1

G0

G0

G1

= negl(n). Finally,  1 X ∆(P0 , P1 ) ≤ 2

 |P0 (On , y) − P1 (On , y)| + Pr[Ebad ] + Pr[Ebad ] = negl(n). G0

(On ,y)∈G

G1

Lemma 15 (Resampling outside the preimage). The games G0 and G1 defined in Box 3 are i.d.

identically distributed: G0 == G1 . S Proof. Fix any attainable pair (S, T ). Since S = i∈I1 PreImage(yi ), every oracle value outside S must lie outside T . All remaining constraints defining (S, T ) involve only the sampled inputs and the restriction On |S . Consequently, conditional on (S, T ), the values {On (x)}x∈S are independent and uniformly distributed over {0, 1}n \ T . The resampling step in G1 therefore samples On |S from exactly its conditional distribution in G0 , preserving the joint distribution of (S, T, On |S ).

4.4.4

s

Proving H0 ≈ H1

b 0 : We present H b 0 , the joint-output experiment corresponding to H0 , in Expr. 9. Hybrid H

39

Box 3: Games G0 and G1 : Resampling Outside the Preimage Game G0 :

Game G1 :

1. Sample On ← On .

1. Run Steps 1–4 of G0 to obtain (On , S, S, T ). $

2. For every x ∈ S, independently resample

− {0, 1}n 2. For each i ∈ I1 , independently sample δi ← and set yi := On (δi ).

$

On (x) ← − {0, 1}n \ T.

3. Set T := {yi }i∈I1 . S 4. Set S := i∈I1 PreImage(yi ) and S := {0, 1}n \ S.

3. Name the resulting function generated by On restricted to S by On |S .

5. Name the resulting function generated by On restricted to S by On |S .

Output (S, T, On |S ).

Output (S, T, On |S ).

b 0 ({ri }i∈[p(n)] ) Experiment 9: Hybrid H

1. Sample On ← On ; 2. For i ∈ I1 : $

– Sample yi ← − {0, 1}n \ ImageOn . 3. Set T := {yi }i∈I1 ⊗|I |

4. Sample W ∼ KOn 0 5. Output (On , T, W )

b 0.1 : We present H b 0.1 in Expr. 10 and highlight its difference from H b 0 in red color. In this Hybrid H $

hybrid, we first sample yi ← − {0, 1}n independently for each i ∈ I1 and set T = {yi }i∈I1 . We then sample each On (x) independently and uniformly from {0, 1}n \ T , ensuring that T ∩ ImageOn = ∅. ⊗|I | For i ∈ I0 , the pairs (yi , vi ) are sampled as before, namely W ∼ KOn 0 . b 0.1 ({ri }i∈[p(n)] ) Experiment 10: Hybrid H

1. For i ∈ I1 : $

– Sample yi ← − {0, 1}n 2. Set T := {yi }i∈I1 3. Sample On where each x ∈ {0, 1}n , On (x) is sampled independently and uniformly from {0, 1}n \ T ; ⊗|I |

4. Sample W ∼ KOn 0 5. Output (On , T, W )

s

b0 ≈ H b 0.1 . Claim 8. It holds that H Proof. First, by Lem. 14, the joint distributions of the following variables are statistically indistinguishable in the two hybrids: On , T = {yi }i∈I1 . (12) Next, observe that, conditioned on the variables in Expression (12), both hybrids sample W ⊗|I | from the same distribution KOn 0 . Thus, their full outputs (On , T, W ) are obtained by applying the 40

same randomized transformation to their respective distributions of the variables in Expression (12). Since statistical distance cannot increase under such a transformation by Lem. 38, the full output distributions are also statistically indistinguishable. s b 0.1 , completing the proof of Claim 8. b0 ≈ H This yields H

b 0.2 : We present H b 0.2 in Expr. 11 and highlight its difference from H b 0.1 in red color. In Hybrid H ⊗|I | this hybrid, we rename the sampled function On to F . Accordingly, we sample W ∼ KF 0 and output (F, T, W ). This change is purely notational and preserves the output distribution. b 0.2 ({ri }i∈[p(n)] ) Experiment 11: Hybrid H

1. For i ∈ I1 : $

− {0, 1}n – Sample yi ← 2. Set T := {yi }i∈I1 3. Sample F where each x ∈ {0, 1}n , F (x) is sampled independently and uniformly from {0, 1}n \ T; ⊗|I0 |

4. Sample W ∼ KF

5. Output (F , T, W ) i.d.

b 0.1 == H b 0.2 . Claim 9. It holds that H b 0.1 except a notational change where we rename the sampled Proof. This hybrid is identical to H function On to F . Therefore, the two distributions are identical. b 0.3 : We present H b 0.3 in Expr. 12 and highlight its difference from H b 0.2 in red color. In Hybrid H this hybrid, we generate {yi }i∈I1 by first sampling On ← On and then independently sampling $

δSi ← − {0, 1}n and setting yi = On (δi ) for each i ∈ I1 . We set T = {yi }i∈I1 and introduce S = On (yi ), the set of all inputs that On maps into T . i∈I1 PreImage b 0.3 ({ri }i∈[p(n)] ) Experiment 12: Hybrid H

1. Sample On ← On ; 2. For i ∈ I1 : $

– Sample δi ← − {0, 1}n , yi = On (δi ) 3. Set T := {yi }i∈I1 S 4. Define S := i∈I1 PreImageOn (yi ), S := {0, 1}n \ S 5. Sample a function F : {0, 1}n → {0, 1}n where each entry independently: ( pick uniformly from {0, 1}n \ T if x ∈ S, F (x) = pick uniformly from {0, 1}n \ T if x ∈ S. ⊗|I0 |

6. Sample W ∼ KF

7. Output (F, T, W ) 41

s

b 0.3 . b 0.2 ≈ H Claim 10. It holds that H b 0.3 are pairwise Proof. Write k = |I1 |. Let E denote the event that the inputs {δi }i∈I1 sampled in H distinct. First, conditioned on E, the values yi = On (δi ) are independent and uniformly distributed over b 0.3 conditioned on E is identical to its distribution in H b 0.2 . {0, 1}n . Thus, the distribution of T in H b 0.2 and on T together with E in H b 0.3 , both hybrids sample every enNext, conditioned on T in H ⊗|I | n try of F independently and uniformly from {0, 1} \T , and then sample W ∼ KF 0 . Consequently, i.d. b b 0.2 == (H0.3 | E). Therefore, we have H   |I1 | −n b b ∆(H0.2 , H0.3 ) ≤ Pr[¬E] ≤ Pr[∃i ̸= j ∈ I1 : δi = δj ] ≤ 2 = negl(n). 2

b 0.4 : We present H b 0.4 in Expr. 13 and highlight its difference from H b 0.3 in red color. In Hybrid H n this hybrid, we set F (x) = On (x) for every x ∈ {0, 1} \ S instead of resampling these values. Since i.d. b b 0.3 == retaining these values has the same distribution as resampling them, we have H H0.4 . b 0.4 ({ri }i∈[p(n)] ) Experiment 13: Hybrid H

1. Sample On ← On ; 2. For i ∈ I1 : $

– Sample δi ← − {0, 1}n , yi = On (δi ) 3. Set T := {yi }i∈I1 S 4. Define S := i∈I1 PreImageOn (yi ), and S := {0, 1}n \ S 5. Sample a function F : {0, 1}n → {0, 1}n where each entry independently: ( pick uniformly from {0, 1}n \ T if x ∈ S, F (x) = On (x) if x ∈ S. ⊗|I0 |

6. Sample W ∼ KF

7. Output (F, T, W ) i.d. b b 0.3 == Claim 11. It holds that H H0.4 .

Proof. First, by Lem. 15, the following variables have identical joint distributions in both hybrids: S, T, F |S ,

(13)

b 0.3 independently resamples the where F |S denotes the restriction of F to inputs in S. Here, H b 0.4 retains their original values. oracle entries at inputs x ∈ S, while H Next, conditioned on the variables in Expression (13), both hybrids sample each F (x) for x ∈ S independently and uniformly from {0, 1}n \ T . Thus, (S, T, F ) has the same joint distribution in both hybrids. ⊗|I | Finally, both hybrids sample W ∼ KF 0 using fresh randomness. Consequently, their full i.d. b b 0.3 == outputs (F, T, W ) are identically distributed, establishing H H0.4 .

42

b 0.5 : We present H b 0.5 in Expr. 14 and highlight its difference from H b 0.4 in red color. In this Hybrid H $

− Image(F ) and abort if PreImageF (yi ) ̸= PreImageOn (yi ). hybrid, for each i ∈ I0 , we sample yi ← Intuitively, an abort is unlikely because it can occur only when yi ∈ F (S), which is small compared s b 0.5 . b 0.4 ≈ H with Image(F ), giving H b 0.5 ({ri }i∈[p(n)] ) Experiment 14: Hybrid H

1. Sample On ← On ; 2. For i ∈ I1 : $

− {0, 1}n , yi = On (δi ) – Sample δi ← 3. Set T := {yi }i∈I1 S 4. Define S := i∈I1 PreImageOn (yi ), S := {0, 1}n \ S 5. Sample a function F : {0, 1}n → {0, 1}n where each entry independently: ( pick uniformly from {0, 1}n \ T if x ∈ S, F (x) = On (x) if x ∈ S. 6. Initialize W = {}. 7. For i ∈ I0 : $

– Sample yi ← − Image(F ) – Abort if PreImageF (yi ) ̸= PreImageOn (yi ) $

– Sample vi ← − PreImageOn (yi ) – W = W ∪ {(yi , vi )} 8. Output (F, T, W ) s b 0.4 ≈ b 0.5 . Claim 12. It holds that H H

Proof. First, the following variables have the same joint distribution in both hybrids: On , S, T, F.

(14)

b 0.5 does not abort, both hybrids Next, conditioned on the variables in Expression (14), whenever H use the same preimage sets and therefore sample each vi from the same distribution. Thus, it suffices b 0.5 aborts. to bound the probability that H Since F agrees with On outside S and never outputs a value in T , the preimages of a label y ∈ Image(F ) can differ only if y ∈ F (S). Thus, a union bound over the |I0 | label samples gives Pr[Abort | On , S, T, F ] ≤

X

Pr[yi ∈ F (S) | On , S, T, F ]

i∈I0

=

X i∈I0

=

|F (S)| |Image(F )|

|I0 | |F (S)| |Image(F )| 43

≤

|I0 | |S| . |Image(F )|

Moreover, 

 [

E[|S|] = E

PreImageOn (On (δi )) 

i∈I1

 ≤ E

 X

|PreImageOn (On (δi ))|

i∈I1

X   = E |PreImageOn (On (δi ))| i∈I1

 X 2n − 1 1+ = 2n i∈I1   2n − 1 = |I1 | 1 + 2n ≤ 2|I1 |.

(Lem. 13)

Here each preimage class contains δi itself, and each other input has the same oracle output with probability 2−n . By Lem. 11, i h n/2 n−1 Pr |Image(On )| ≤ 2n/2 ≤ 2n2 −n2 . Outside this exceptional event, F retains every original image value outside T , so |Image(F )| ≥ |Image(On )| − |T | > 2n/2 − |I1 | ≥ 2n/2−1 , where the last inequality holds for sufficiently large n, since |I1 | is polynomially bounded. Combining these bounds and averaging over the randomness yields i i h h Pr[Abort] ≤ Pr |Image(On )| ≤ 2n/2 + Pr Abort ∧ |Image(On )| > 2n/2 |I0 | E[|S|] 2n/2−1 4|I0 | |I1 | n/2 n−1 ≤ 2n2 −n2 + 2n/2 = negl(n). ≤ 2n2

n/2 −n2n−1

+

s b 0.4 ≈ b 0.5 . We therefore establish H H

b 0.6 : We present H b 0.6 in Expr. 15 and highlight its difference from H b 0.5 in red color. In Hybrid H b this hybrid, we remove the abort check introduced in H0.5 . Since this check causes an abort only s b 0.5 ≈ b 0.6 . with negligible probability, removing it gives H H b 0.6 ({ri }i∈[p(n)] ) Experiment 15: Hybrid H

1. Sample On ← On ; 2. For i ∈ I1 : 44

$

− {0, 1}n , yi = On (δi ) – Sample δi ← 3. Set T := {yi }i∈I1 S 4. Define S := i∈I1 PreImageOn (yi ), S := {0, 1}n \ S 5. Sample a function F : {0, 1}n → {0, 1}n where each entry independently: ( pick uniformly from {0, 1}n \ T if x ∈ S, F (x) = On (x) if x ∈ S. 6. Initialize W = {}. 7. For i ∈ I0 : $

− Image(F ) – Sample yi ← – Abort if PreImageF (yi ) ̸= PreImageOn (yi ) $

– Sample vi ← − PreImageOn (yi ) – W = W ∪ {(yi , vi )} 8. Output (F, T, W ) s

b 0.5 ≈ H b 0.6 . Claim 13. It holds that H s b 0.6 . The argument for H b 0.4 ≈ b 0.5 Proof. The two hybrids differ only in the abort check removed in H H s b 0.5 ≈ already shows that this check is triggered with probability at most negl(n), establishing H b 0.6 . H

b 0.7 : We present H b 0.7 in Expr. 16 and highlight its difference from H b 0.6 in red color. In this Hybrid H hybrid, we introduce abort checks to ensure that |S| is polynomially bounded and |Image(On )| is exponentially large. These bounds let us control the effect of modifying On on S in the subsequent s b 0.6 ≈ b 0.7 . hybrids. Since the checks trigger only with negligible probability, we have H H b 0.7 ({ri }i∈[p(n)] ) Experiment 16: Hybrid H

1. Sample On ← On ; 2. For i ∈ I1 : $

– Sample δi ← − {0, 1}n , yi = On (δi ) 3. Set T := {yi }i∈I1 S 4. Define S := i∈I1 PreImageOn (yi ), S := {0, 1}n \ S 5. Sample a function F : {0, 1}n → {0, 1}n where each entry independently: ( pick uniformly from {0, 1}n \ T if x ∈ S, F (x) = On (x) if x ∈ S. 6. Abort if |S| ≥ p(n) log(n) or |Image(On )| ≤ 2n/2 7. Initialize W = {}. 8. For i ∈ I0 : 45

$

− Image(F ) – Sample yi ← $

− PreImageOn (yi ) – Sample vi ← – W = W ∪ {(yi , vi )} 9. Output (F, T, W ) s b 0.7 . b 0.6 ≈ H Claim 14. It holds that H

b 0.7 . Thus, it suffices to Proof. The two hybrids differ only in the two abort checks introduced in H bound the abort probability. First, recall that S is the union of the preimage sets of the k = |I1 | sampled oracle outputs yi = On (δi ). Hence, |S| =

[

≤

X

PreImageOn (On (δi ))

i∈I1

|PreImageOn (On (δi ))|.

i∈I1

Since |I1 | ≤ p(n), the event |S| ≥ p(n) log n implies that at least one of these preimage sets has size at least log n. Next, Corollary 3 also bounds the probability that each such preimage set has size at least log n by negl(n): take t = ⌈log n⌉ − 1 in that calculation. Thus, by a union bound and Lem. 11, h i Pr[Abort] ≤ Pr[|S| ≥ p(n) log n] + Pr |Image(On )| ≤ 2n/2 i h X   n/2 On ≤ Pr |PreImage (On (δi ))| ≥ log n + Pr |Image(On )| ≤ 2 i∈I1 n/2 −n2n−1

≤ |I1 | · negl(n) + 2n2

(Corollary 3+Lem. 11)

= negl(n). s b 0.6 ≈ b 0.7 . We therefore conclude that H H

b 0.8 : We present H b 0.8 in Expr. 17 and highlight its difference from H b 0.7 in red color. In Hybrid H this hybrid, for each i ∈ I0 , we sample yi uniformly from Image(On ) instead of Image(F ). When the abort checks pass, the two images differ by only a negligible fraction of their elements, giving s b 0.7 ≈ b 0.8 . H H b 0.8 ({ri }i∈[p(n)] ) Experiment 17: Hybrid H

1. Sample On ← On ; 2. For i ∈ I1 : $

– Sample δi ← − {0, 1}n , yi = On (δi ) 3. Set T := {yi }i∈I1 S 4. Define S := i∈I1 PreImageOn (yi ), S := {0, 1}n \ S 46

5. Sample a function F : {0, 1}n → {0, 1}n where each entry independently: ( pick uniformly from {0, 1}n \ T if x ∈ S, F (x) = On (x) if x ∈ S. 6. Abort if |S| ≥ p(n) log(n) or |Image(On )| ≤ 2n/2 7. Initialize W = {}. 8. For i ∈ I0 : $

− Image(On ) – Sample yi ← $

− PreImageOn (yi ) – Sample vi ← – W = W ∪ {(yi , vi )} 9. Output (F, T, W ) s b 0.7 ≈ b 0.8 . Claim 15. It holds that H H

Proof. First, the two hybrids have identical initial sampling and abort checks. In particular, the following variables have the same joint distribution: On , T, F.

(15)

If either initial abort check is triggered, both hybrids abort. Otherwise, condition on fixed values of the variables in Expression (15). Define the following event: – Event E: for all i ∈ I0 , it holds that yi ∈ Image(F ) ∩ Image(On ). Next, conditioned on these variables and on E, both hybrids sample each yi independently and uniformly from Image(F ) ∩ Image(On ), and then sample each vi uniformly from PreImageOn (yi ). Their conditional output distributions are therefore identical. It remains to bound the probability that E fails under each hybrid. Notice that F and On differ only on S; then, since the difference in their range must be induced by the difference in their domain, we have |Image(F ) \ Image(On )| ≤ |S| ≤ p(n) log n

(16)

|Image(On ) \ Image(F )| ≤ |S| ≤ p(n) log n

(17)

b 0.7 and H b 0.8 . where the |S| ≤ p(n) log n bound follows from the common abort check at Step 6 in H Moreover, the initial abort checks also ensure that |Image(On )| > 2n/2

(18)

|Image(F )| ≥ |Image(On )| − |S|

(19)

> 2n/2 − p(n) log n

(20)

Thus, by a union bound, Pr [¬E | On , T, F ] = Pr [∃i ∈ I0 : yi ∈ Image(F ) \ Image(On ) | On , T, F ] b 0.7 H

b 0.7 H

≤

|I0 | |Image(F ) \ Image(On )| |Image(F )| 47

|I0 |p(n) log n . 2n/2 − p(n) log n

≤

(Eq. (16) and Eq. (20))

Similarly, Pr [¬E | On , T, F ] = Pr [∃i ∈ I0 : yi ∈ Image(On ) \ Image(F ) | On , T, F ] b 0.8 H

b 0.8 H

|I0 | |Image(On ) \ Image(F )| |Image(On )| |I0 |p(n) log n . ≤ 2n/2 ≤

(Eq. (17) and Eq. (18))

For each fixed nonaborting initial sample, the statistical distance is at most the sum of these two failure probabilities by Lem. 38. Averaging over the common initial randomness gives b 0.7 , H b 0.8 ) ≤ ∆(H

|I0 |p(n) log n |I0 |p(n) log n + = negl(n), n/2 2 2n/2 − p(n) log n

s b 0.7 ≈ b 0.8 . establishing H H

b 0.9 : We present H b 0.9 in Expr. 18 and highlight its difference from H b 0.8 in red color. Hybrid H b 0.9 ({ri }i∈[p(n)] ) Experiment 18: Hybrid H

1. Sample On ← On ; 2. For i ∈ I1 : $

– Sample δi ← − {0, 1}n , yi = On (δi ) 3. Set T := {yi }i∈I1 S 4. Define S := i∈I1 PreImageOn (yi ), S := {0, 1}n \ S 5. Sample a function F : {0, 1}n → {0, 1}n where each entry independently: ( pick uniformly from {0, 1}n \ T if x ∈ S, F (x) = On (x) if x ∈ S. 6. Abort if |S| ≥ p(n) log(n) or |Image(On )| ≤ 2n/2 7. Initialize W = {}. 8. For i ∈ I0 : $

– Sample yi ← − Image(On ) $

– Sample vi ← − PreImageOn (yi ) – W = W ∪ {(yi , vi )} 9. Output (F, T, W ) s b 0.8 ≈ b 0.9 . Claim 16. It holds that H H s b 0.9 . and the proof of H b 0.6 ≈ b 0.7 Proof. The two hybrids differ only in the abort check removed in H H s b 0.8 ≈ H b 0.9 . already shows that this check triggers with negligible probability, establishing H

48

c1 : We present H c1 in Expr. 19 and highlight its difference from H b 0.9 in red color. In this Hybrid H ⊗|I | hybrid, we express the sampling of the pairs (yi , vi ) for i ∈ I0 as W ∼ KO 0 . This is purely a i.d. c b 0.9 == H1 . notational change and preserves the output distribution, giving H c1 ({ri }i∈[p(n)] ) Experiment 19: Hybrid H

1. Sample On ← On ; 2. For i ∈ I1 : $

− {0, 1}n , yi = On (δi ) – Sample δi ← 3. Set T := {yi }i∈I1 S 4. Define S := i∈I1 PreImageOn (yi ), S := {0, 1}n \ S 5. Sample a function F : {0, 1}n → {0, 1}n where each entry independently: ( pick uniformly from {0, 1}n \ T if x ∈ S, F (x) = On (x) if x ∈ S. ⊗|I |

6. Sample W ∼ KOn 0 7. Output (F, T, W )

i.d. c b 0.9 == Claim 17. It holds that H H1 .

Proof. This is just a notational change,where we do not explicity write out the sampling of W in b 0.9 anymore. Therefore, the two distributions are identical. H s

Completing the proof of H0 ≈ H1 : By the previous hybrids indistinguishability claims and the triangle inequality, for every r = (ri )i∈[p(n)] , we have b 0 (r), H c1 (r)) = negl(n), ∆(H These experiments only reorder independent sampling operations and replace the invocation of A by the output of its complete input and oracle table. Thus, applying the original adversary cb recovers Hb for b ∈ {0, 1}. By Lem. 38, statistical distance cannot increase under invocation to H s this transformation. Then the above hybrids indistinguishability establishing H0 ≈ H1 . 4.5

s

Proof of H1 ≈ H2 s

Proof Strategy Overview. We prove H1 ≈ H2 by establishing the stronger statement that the joint distributions of the complete constructed oracle On∗ and the indexed inputs supplied to A are statistically close. Recall that the two hybrids have the same initial sampling. For each i ∈ I0 , they independently sample $

yi ← − ImageOn ,

$

vi ← − PreImageOn (yi ),

and, for each i ∈ I1 , they independently sample $

δi ← − {0, 1}n ,

yi := On (δi ). 49

Their constructions of On∗ differ only at inputs [ PreImageOn (yi ). z∈ / i∈[p(n)]

At these inputs, H1 retains On (z), whereas H2 independently samples a fresh uniform value from {0, 1}n \ {yi : i ∈ [p(n)]}. Intuitively, after fixing the sampled information and the preimage sets of the selected labels, the remaining oracle entries should already be uniform over the outputs other than the selected labels. However, sampling yi uniformly from the image for each i ∈ I0 introduces the factor 1 . |ImageOn ||I0 | The image size can depend on the remaining oracle entries, so these entries are not immediately independent and uniform. e 1 and H e 2 in which each initial To remove this dependence, we introduce modified experiments H On |I0 | oracle table is sampled with probability proportional to |Image | . The two factors then cancel i.d. e e 1 == exactly, allowing us to prove H H2 . We next show that the modified oracle sampling is s e b for each b ∈ {1, 2}. statistically close to uniform sampling, establishing Hb ≈ H Throughout the proof, restrict attention to sufficiently large n such that p(n) < 2n . We retain the notation I0 = {i ∈ [p(n)] : ri = 0}, I1 = {i ∈ [p(n)] : ri = 1}. The bit vector has the same distribution in both original hybrids and is independent of the initially sampled oracle. Thus, we may sample the bit vector first without changing either original experiment. e 1 . We present H e 1 in Expr. 20. This hybrid differs from H1 only in the distribution of Hybrid H the initially sampled oracle. The modified sampling is used only for the proof and need not have an efficient implementation. e1 Experiment 20: Hybrid H

( 1. According to the input r = (r1 , . . . , rp(n) ), define

I0 := {i ∈ [p(n)] | ri = 0} I1 := {i ∈ [p(n)] | ri = 1}

.

2. Sample On ∈ On according to   |Imagef ||I0 | Pr On = f | {ri }i∈[p(n)] = X |Imageg ||I0 |

for every f ∈ On .

g∈On

3. For each i ∈ I0 , independently sample $

$

yi ← − ImageOn ,

vi ← − PreImageOn (yi ).

4. For each i ∈ I1 , independently sample $

δi ← − {0, 1}n ,

yi := On (δi ).

5. Construct On∗ as in H1 . In particular, set On∗ (z) := On (z)

if z ∈ /

[ i∈[p(n)]

50

PreImageOn (yi ).

All other branches of the oracle construction remain unchanged. 6. Invoke A with the same indexed inputs and oracle access as in H1 , and output its result. e 2 . We present H e 2 in Expr. 21. This hybrid uses the same modified initial sampling as Hybrid H e 1 , but resamples the oracle entries outside the selected preimage sets, as in H2 . Equivalently, it H differs from H2 only in the distribution of the initially sampled oracle. e2 Experiment 21: Hybrid H

e 1 to obtain 1. Run Steps 1–4 of H {yi }i∈[p(n)] ,

On ,

{vi }i∈I0 ,

{δi }i∈I1 .

2. Construct On∗ as in H2 . In particular, for every input [ z∈ / PreImageOn (yi ), i∈[p(n)]

independently sample $

On∗ (z) ← − {0, 1}n \ {yi : i ∈ [p(n)]}, e1. using fresh randomness. On all remaining inputs, use the same oracle construction as in H 3. Invoke A with the same indexed inputs and oracle access as in H2 , and output its result. i.d. e e 1 == Claim 18. It holds that H H2 .

Proof. We prove that the complete constructed oracle On∗ and the indexed inputs supplied to A have identical joint distributions in the two experiments. First, the following variables have the same joint distribution in both experiments:
{yi }i∈[p(n)] , {vi }i∈I0 , {δi }i∈I1 , (21) PreImageOn (yi ) i∈[p(n)] . Condition on any attainable values of these variables. Consider an oracle table f consistent with the fixed values in Expression (21). Conditional on On = f , the probability of sampling the specified labels, witnesses, and inputs is 2−n|I1 |

1 . |Image | |PreImagef (yi )| i∈I Y

f

0

Indeed, for each i ∈ I1 , sampling the specified δi has probability 2−n , after which yi is determined by f (δi ). For each i ∈ I0 , the two denominator terms correspond to sampling yi uniformly from the image and then vi uniformly from its preimage set. Multiplying by the modified probability of sampling the table f gives Y |Imagef ||I0 | 1 X · 2−n|I1 | f g |I0 | |Image | |PreImagef (yi )| |Image | i∈I0 g∈On

= X

2−n|I1 |

1 . f |Imageg ||I0 | i∈I |PreImage (yi )| Y

0

g∈On

51

The factors involving |Imagef | cancel exactly. Moreover, the preimage sizes in the remaining expression are fixed by Expression (21). Thus, every consistent oracle table has the same conditional probability. Next, the fixed preimage sets determine the oracle value at every input in [ PreImageOn (yi ). i∈[p(n)]

At any other input, the oracle value must lie in {0, 1}n \ {yi : i ∈ [p(n)]}. Conversely, any assignment of the remaining oracle entries to values in this set preserves all the fixed information in Expression (21). Consequently, conditional on the fixed information, the entries     [ On On (z) : z ∈ / PreImage (yi )   i∈[p(n)]

are independent and uniformly distributed over {0, 1}n \ {yi : i ∈ [p(n)]}. This conclusion does not require the labels yi to be distinct. e 1 retains entries that already have exactly the distribution from which H e 2 resamTherefore, H ples. On the remaining inputs, both experiments use the same oracle construction, which depends only on the fixed information and fresh randomness. Their complete constructed oracle tables and indexed inputs therefore have identical conditional distributions. Averaging over Expression (21) and then over the common distribution of {ri }i∈[p(n)] preserves i.d. e e 1 == this identity. Applying the common adversary invocation establish H H2 . Notice that the identity concerns the constructed oracle On∗ supplied to A. We do not additionally reveal the original table On .

s eb. Claim 19. For every b ∈ {1, 2}, it holds that Hb ≈ H

e b differ only in the distribution Proof. Consider an arbitrary b ∈ {1, 2}. The experiments Hb and H of the initially sampled oracle. Thus, it suffices to bound the statistical distance between uniform oracle sampling and the modified sampling. Intuitively, the modified sampling assigns larger weights to oracle tables with larger images. However, almost all uniformly sampled tables have nearly the same image size, so their sampling weights are nearly equal. Let   µ := EOn ←On |ImageOn | . By Lem. 12, we have µ ≥ 2n−1 and h i n/2 Pr |ImageOn | − µ > 23n/4 ≤ 2e−2·2 . On ←On

(22)

We use this concentration bound to compare the weights of the typical tables and separately bound the total contribution of the exceptional tables to the normalization. For the following calculation, define the rescaled weight of a table f by w(f ) :=

|Imagef | µ 52

!|I0 | .

Dividing all weights by the same number µ|I0 | does not change the modified sampling distribution. First, consider a table f satisfying |Imagef | − µ ≤ 23n/4 . Since µ ≥ 2n−1 , we have 1 − 21−n/4 ≤

|Imagef | ≤ 1 + 21−n/4 . µ

Consequently, (1 − 21−n/4 )|I0 | ≤ w(f ) ≤ (1 + 21−n/4 )|I0 | . Using |I0 | ≤ p(n), together with (1 − x)k ≥ 1 − kx and (1 + x)k ≤ ekx , gives
|w(f ) − 1| = O p(n)2−n/4 .

(23)

Here we use p(n)2−n/4 = o(1). The bound is uniform over all such tables and all choices of the bit vector. Next, for every oracle table, including those outside the preceding image-size bound, we have 0 ≤ w(f ) =

|Imagef | µ

!|I0 |

 n |I0 | 2 ≤ 2p(n) . ≤ µ

where the last inequality uses µ ≥ 2n−1 . Thus, the exceptional tables have very small probability, and even their largest possible weights have negligible total contribution. More precisely, combining Eq. (22) and (23) gives  
n/2 EOn ←On |w(On ) − 1| ≤ O p(n)2−n/4 + (2p(n) + 1) · 2e−2·2 = negl(n).

(24)

It remains to account for the normalization of the weights. Let ε(n) be a negligible upper bound on Equation (24), uniform over the bit vector. Then by triangle inequality, we have |EOn ←On [w(On )] − 1| ≤ EOn ←On [|w(On ) − 1|] ≤ ε(n). In particular, the average weight is also close to one. n Since |On | = 2n·2 , the probability of a particular table f under the modified sampling is w(f ) w(f ) 1 X . = n·2n · 2 EOn ←On [w(On )] w(g) g∈On

Therefore, the statistical distance between uniform and modified oracle sampling is 1 X 1 1 w(f ) n − n · n·2 n·2 2 2 2 EOn ←On [w(On )] f ∈On

EOn ←On [|w(On ) − EOn ←On [w(On )]|] 2EOn ←On [w(On )] EOn ←On [|w(On ) − 1|] + |1 − EOn ←On [w(On )]| ≤ 2EOn ←On [w(On )] =

53

≤

ε(n) = negl(n). 1 − ε(n)

e b apply the Finally, for each fixed bit vector and each b ∈ {1, 2}, all subsequent steps of Hb and H same randomized transformation to the initially sampled oracle. Since statistical distance cannot increase under such a transformation, the joint distributions of the constructed oracle and the indexed inputs are statistically close. The same holds after invoking A. The bound is uniform over {ri }i∈[p(n)] . Averaging over its common distribution therefore gives s e b for every b ∈ {1, 2}. Hb ≈ H s

Completing the proof of H1 ≈ H2 . By Claims 18 and 19, we have s i.d. e s e 1 == H2 ≈ H2 . H1 ≈ H

The triangle inequality therefore gives e 2 ) + ∆(H e 2 , H2 ) = negl(n), e 1 ) + ∆(H e1, H ∆(H1 , H2 ) ≤ ∆(H1 , H s

establishing H1 ≈ H2 . 4.6

cq

Proof of H2 ≈ H2.5 cq

Below, we establishes H2 ≈ H2.5 . Proof strategy overview. We couple the two experiments so that their constructed oracles agree outside a small set of inputs. We then show that, in H2.5 , the locations of these inputs remain hidden even given the complete constructed oracle and the sampled information. Consequently, measuring a query in an execution with the H2.5 oracle hits this set with only negligible probability. By the one-way-to-hiding (O2H) bound, a non-negligible distinguishing advantage would contradict this query bound. Fix a quantum polynomial-time adversary A, and let q = q(n) ≥ 1 be a polynomial upper bound on its number of oracle queries. Write p = p(n). For each i ∈ I0 , write δi = vi , and define
W := (yi , δi ) i∈[p] , D := {δi : i ∈ [p]}, Y := {yi : i ∈ [p]}. We also write Y1 := {yi : i ∈ I1 }. The variable W contains all the indexed inputs supplied to A, as well as the designated inputs δi for i ∈ I1 . We condition on these additional inputs only for the analysis; the experiments do not reveal them to A. Restricting to the good event. For an oracle table f , define K(f ) := max |PreImagef (y)|, y∈{0,1}n

M (f ) := |Imagef |.

Consider the event       B := all yi are distinct ∩ K(On ) ≤ n ∩ M (On ) ≥ 2n−1 . 54

The distinctness bound established in the proof of Claim 4 applies here, since H2 and H2.5 have the same initial sampling. Combining this bound with Lem. 12 and the preimage-size bound obtained from Lem. 13 and Corollary 6 by a union bound over all 2n inputs, we obtain Pr[¬B] = negl(n). The event B concerns only the common initial sampling, so it has the same probability in both experiments. For now, condition both experiments on B. Since On (δi ) = yi for every i ∈ [p], distinctness of the labels implies distinctness of the designated inputs. Thus, |D| = p. Define the hidden set   [ PreImageOn (yi ) \ D. S :=  i∈[p]

On B, we have |S| ≤ pn.

(25)

∗ ∗ Coupling the constructed oracles. Let On,2 and On,2.5 denote the constructed oracles in H2 and H2.5 , respectively. Use the same initial oracle On and the same sampled data W in both experiments. Couple the remaining oracle randomness as follows:

– At every δi with i ∈ I1 , use the same fresh uniform output from {0, 1}n \ Y1 . – At every δi with i ∈ I0 , both constructed oracles output yi . S – At every input outside i∈[p] PreImageOn (yi ), use the same fresh uniform output from {0, 1}n \Y . – At the remaining inputs, sample the oracle values according to their respective prescribed distributions. All fresh samples at distinct inputs are independent within each oracle construction. Since the labels are distinct on B, the designated-input cases do not conflict. This coupling therefore preserves both conditional experiment distributions and satisfies ∗ ∗ On,2 (z) = On,2.5 (z)

for every z ∈ / S.

(26)

The agreement outside the selected preimage sets uses the fact that H2 already resamples its background entries uniformly from {0, 1}n \ Y . The hidden set remains hidden in H2.5 . Fix any attainable value of W under the conditioning ∗ on B. The complete oracle On,2.5 can be generated from this fixed information and independent fresh randomness: at each designated input its distribution is determined by W , and at every other input it is independently uniform over {0, 1}n \Y . In particular, the construction does not otherwise use the initial oracle On . It follows that ∗ On,2.5 and S are conditionally independent given (W, B).

(27)

This remains true despite conditioning on B, since B depends only on the initial sampling, not on ∗ the fresh randomness used to construct On,2.5 . Intuitively, after fixing W and conditioning on B and |S| = s, every s-element subset of {0, 1}n \ D should be equally likely to be S. We justify this symmetry by reshuffling the truth table outside D, preserving the sampling probabilities while permuting the locations of S. 55

Formally, consider any permutation π of {0, 1}n that fixes every point in D, and replace the initial oracle table f by f ◦ π −1 . Uniform oracle sampling is invariant under this transformation. Moreover, it preserves the image of f , the cardinality of every preimage set, and the values at all designated inputs. Consequently, the probability of generating the fixed data W is unchanged. Indeed, for i ∈ I0 , sampling yi uniformly from the image and then δi uniformly from its preimage has the same probability before and after the transformation. For i ∈ I1 , the same holds for sampling δi uniformly from {0, 1}n and setting yi = f (δi ). The event B is also invariant under this transformation, whereas the hidden set S is mapped to π(S). Consequently, for every attainable s, S | (W, B, |S| = s)

is uniform among the s-subsets of {0, 1}n \ D.

(28)

Indeed, permutations fixing D act transitively on these s-subsets. Combining Eq. (27) and (28), we conclude that conditioning additionally on the complete table ∗ On,2.5 does not change this uniform distribution. Thus, even the complete accessible oracle does not reveal the locations of S outside D. Bounding the probability of a measured query. Consider an execution of A with oracle ∗ and its prescribed indexed inputs. For each j ∈ [q], consider the experiment that runs A On,2.5 until immediately before its j-th oracle query and measures that query’s input register in the computational basis. An execution making fewer than j queries is treated as a failure to hit S. Fix attainable values of ∗ W, On,2.5 , |S| = s under the conditioning on B. Let µj (z) denote the probability that the measured query is z under ∗ this conditioning. The adversary’s execution uses only its indexed inputs, the oracle On,2.5 , and its own randomness. Hence its query distribution does not depend further on S. By the conditional uniformity established above,   ∗ , B, |S| = s Pr measured query j ∈ S W, On,2.5 X s s pn = µj (z) n ≤ n ≤ n . 2 −p 2 −p 2 −p z ∈D /

The last inequality follows from Eq. (25). Averaging over the conditioned variables preserves the bound. Let Phit be the probability of obtaining an element of S when choosing j uniformly from [q] and performing the preceding measurement in the H2.5 execution, with the initial sampling conditioned on B. Then pn Phit ≤ n . (29) 2 −p Applying O2H. Let A[Hb ] denote the output of A in experiment Hb , and define the conditional distinguishing advantage εB := |Pr[A[H2 ] = 1 | B] − Pr[A[H2.5 ] = 1 | B]| . The coupled oracles agree outside S by Eq. (26). The O2H bound, with measured queries taken ∗ from the execution using On,2.5 , therefore gives εB ≤ 2q

p Phit .

56

(30)

The bound permits arbitrary correlations among the two oracle tables, the set S, and the auxiliary input. The conditional independence proved above is needed to bound Phit , not to apply O2H itself. Removing the conditioning. Finally, the two experiments have the same initial sampling distribution and therefore the same probability of B. Decomposing their acceptance probabilities according to B and ¬B, we obtain |Pr[A[H2 ] = 1] − Pr[A[H2.5 ] = 1]| ≤ Pr[B]εB + Pr[¬B] s p(n)n ≤ 2q(n) + negl(n) = negl(n). n 2 − p(n) cq

Since A was arbitrary, this establishes H2 ≈ H2.5 . This completes the proof of Claim 3.

5

NIZK in the URS-PRHF Model

In this section, we construct a post-quantum NIZK proof from a strong δ-dense post-quantum PRHF, using a uniform random string (URS) as setup. This construction is not a URS NIZK in the standard sense: both the prover and the verifier additionally require access to an honestly generated (strong δ-dense post-quantum) PRHF as per Def. 6. The PRHF sampling algorithm samples a function H from a family Hn . If this algorithm is public-coin, its random coins can be included in the URS. However, future potential instantiations of PRHFs from concrete assumptions may require private-coin sampling. In that case, our construction does not yield a URS NIZK in the standard sense. We therefore formalize the notion achieved by our construction in Def. 7: in addition to a standard URS, the prover and the verifier are given access to an honestly generated PRHF. We call this the URS-PRHF model. This model serves only as an intermediate step toward our final construction in the QROM in Sec. 6, where we implement both the URS and the PRHF using a random oracle. The URS-PRHF model suffices for this purpose. Definition 7 (NIZK Proof in the URS-PRHF Model). Let {Hn }n∈N be a (strong δ-dense post-quantum) PRHF as per Def. 6. An (unbounded-prover) non-interactive zero knowledge (NIZK) proof system in the URS-PRHF model for a language L is a tuple of algorithms Π = (P, V ). $

The setup consists of a uniform random string σ ← − {0, 1}ℓ(n) , where ℓ is a polynomial, and an independently sampled PRHF Hn ← Hn , where n = |x|. – P (Hn , σ, x) is an (unbounded, randomized) honest prover algorithm that takes as input the code of Hn , the URS σ, and x ∈ L, and outputs a proof π. – V (Hn , σ, x, π) is a polynomial-time deterministic verifier that takes as input the code of Hn , the URS σ, x, and a proof π, and outputs either 1 (accept) or 0 (reject). We require Π to satisfy the following completeness, soundness, and zero knowledge requirements: – Perfect Completeness: For all x ∈ L with |x| = n, it holds that   Hn ← Hn ,   $ Pr V (Hn , σ, x, π) = 1 : σ ← − {0, 1}ℓ(n) ,  = 1. π ← P (Hn , σ, x) 57

– Statistical Soundness: It holds that Pr

Hn ←Hn

[∃(x, π) such that x ∈ / L, |x| = n, and V (Hn , σ, x, π) = 1] ≤ negl(n).

$

σ← −{0,1}ℓ(n)

– Zero Knowledge: There exists a QPT simulator Sim such that, for all x ∈ L with |x| = n and all QPT algorithms A, # " $ ℓ(n) , H ← H , σ ← − {0, 1} n Pr A(Hn , σ, x, π) = 1 : n π ← P (Hn , σ, x)   Hn ← Hn , ∗ ∗ − Pr A(Hn , σ , x, π ) = 1 : ∗ ∗ ≤ negl(n). (σ , π ) ← Sim(Hn , x) The simulator is given the code of the honestly sampled Hn and simulates the URS and the proof, without modifying Hn . 5.1

Construction

In this subsection, we present a construction satisfying Def. 7. The construction and its security proof also apply when HPRHF is instantiated by a random oracle: The proof relativizes by replacing each evaluation of HPRHF with an oracle query. We use this oracle formulation in the QROM construction of Sec. 6.5. We first recall the following existence result. Lemma 16 ([GIK+ 23, Theorem 5.1]). For every language L ∈ NP and every efficiently approximable constant γ ∈ (0, 1), there exists a NIZK proof system in the Z-Tamperable-Hidden-Bits model,
ZHB-NIZKγ = ZHB.Genγ , ZHB.Pγ , ZHB.Vγ , with simulator ZHB.Simγ , satisfying the requirements of Def. 3. The construction closely follows the framework of [GIK+ 23]. The main differences are that we instantiate it with our strong δ-dense post-quantum PRHF in place of the δ-dense hash function used there, and establish security against quantum adversaries. Algorithm 5.1: URS Generator URS.Gen(1n )

URS.Gen(1n ): 1. For i ∈ [phbs (n)], sample a uniformly random yi ∈ {0, 1}ℓ(n) 2. Output urs = y1 · · · yphbs (n) Algorithm 5.2: URS Prover URS.P

URS.P(urs, HPRHF , x): 1. Parse urs as y1 , . . . , yphbs (n) where n = |x|. 2. For i ∈ [phbs (n)], $

(a) If ∃z ∈ {0, 1}n such that HPRHF (z) = yi , sample vi ← − {z ∈ {0, 1}n : HPRHF (z) = yi }, and set ri = 0. (b) If ∄z ∈ {0, 1}n such that HPRHF (z) = yi , set vi =⊥ and ri = 1. 58

3. (ZHB.I, ZHB.π) ← ZHB.Pγ (r, x) where r = r1 . . . rphbs (n) . 4. Return π := (ZHB.I, {vi }i∈ZHB.I , ZHB.π). Algorithm 5.3: URS Verifier URS.V

URS.V(urs, HPRHF , x, π): 1. Parse urs as y1 , . . . , yphbs (n) where n = |x|. 2. Parse π as (ZHB.I, {vi }i∈ZHB.I , ZHB.π). 3. For i ∈ ZHB.I, – If vi =⊥, set rei = 1. – If vi ̸=⊥, and HPRHF (vi ) = yi , set rei = 0. – If vi ̸=⊥, and HPRHF (vi ) ̸= yi , reject. 4. Return ZHB.Vγ (x, ZHB.I, {e ri }i∈ZHB.I , ZHB.π) Throughout the following analysis, let L ∈ NP denote the language for which the underlying ZHB-NIZKγ is defined. The constructed URS-NIZK proves membership in the same language L, and we write n = |x| for the length of a statement x. 5.2

Security Proof

Note that the completeness and soundness of the above NIZK proof system directly follows from [GIK+ 23] as the quantum-accessibility of zero-knowledge adversary will not affect the the above two properties, we will then focus on the zero-knowledge property. Lemma 17. If HPRHF is a δ-dense post-quantum PRHF for some Efficiently-Approximable constant δ ∈ (0, 1) and ZHB.NIZKγ with γ = 1 − δ satisfies statistical zero knowledge in the Z-TamperableHidden-Bits model, then there exists a QPT simulator URS.Sim and for all x ∈ L and all nonuniform QPT adversary A,   HPRHF ← Hn ; − PrA(urs, HPRHF , x, π) = 1 : urs ← URS.Gen(1|x| ); π ← URS.P(urs, HPRHF , x)   HPRHF ← Hn ; ∗ ∗ Pr A(urs , HPRHF , x, π ) = 1 : ≤ negl(n). (urs∗ , π ∗ ) ← URS. Sim(HPRHF , x); Proof. We complete the proof by giving the explicit construction of the simulator URS.Sim and proving that it is indistinguishable from the real prover URS.P through hybrid arguments. Algorithm 5.4: URS Simulator URS.Sim

URS.Sim(HPRHF , x): 1. Let n = |x|. 2. (ZHB.I, {ri }i∈ZHB.I , ZHB.π) ← ZHB.Simγ (x). 3. For i ∈ [phbs (n)], sample vi ← {0, 1}n , and set yi = HPRHF (vi ). 4. For i ∈ ZHB.I, (a) If ri = 1, set vi′ =⊥ 59

(b) If ri = 0, set vi′ = vi . 5. Output (urs = (y1 . . . yphbs (n) ), π = (ZHB.I, {vi′ }i∈ZHB.I , ZHB.π)). Hybrid H0 : This is the real-world game where the adversary interacts with the real prover.We formally describe it in Expr. 22. Experiment 22: Hybrid H0

1. Let n = |x|. 2. For i ∈ [phbs (n)], $

− {0, 1}ℓ(n) . (a) Sample yi ← $

− {z ∈ {0, 1}n : HPRHF (z) = yi }, (b) If ∃z ∈ {0, 1}n such that HPRHF (z) = yi , and sample vi ← and set ri = 0. (c) If ∄z ∈ {0, 1}n such that HPRHF (z) = yi , set vi =⊥ and ri = 1. 3. (ZHB.I, ZHB.π) ← ZHB.Pγ (r, x) where r = r1 . . . rphbs (n) . 4. Output (urs = (y1 . . . yphbs (n) ), π = (ZHB.I, {vi }i∈ZHB.I , ZHB.π)). Hybrid: H1 We present H1 in Expr. 23 and highlight its difference from H0 in red color. In this hybrid, we just interchange the order of sampling yi and sampling vi for those ri = 0 without changing the distribution. Experiment 23: Hybrid H1

1. Let n = |x|. 2. For i ∈ [phbs (n)], (a) Sample ri ∈ {0, 1} such that Pr[ri = 1] = γ ′ where γ ′ = 1 − Pry←{0,1}ℓ(n) [∃z s.t. HPRHF (z) = y] 3. (ZHB.I, ZHB.π) ← ZHB.Pγ (r, x) where r = r1 . . . rphbs (n) . ( Image := {y ∈ {0, 1}ℓ(n) : ∃z ∈ {0, 1}n such that HPRHF (z) = y} 4. Define PreImage(y) := {z ∈ {0, 1}n : HPRHF (z) = y} 5. For i ∈ [phbs (n)], (a) If ri = 0, sample yi ← Image and vi ← PreImage(yi ), and set vi′ = vi . (b) If ri = 1, sample yi ← {0, 1}ℓ(n) \ Image, and set vi′ =⊥. 6. Output (urs = (y1 . . . yphbs (n) ), π = (ZHB.I, {vi′ }i∈ZHB.I , ZHB.π)). i.d.

Claim 20. It holds that H0 == H1 . Proof. The above hybrid is the same as the previous hybrid, except that we have changed the way of generating the (ri , vi , yi ). Observe the following statistical facts in hybrid H1 : – The distribution of (ZHB.I, ZHB.π) only depends on the random r and the input x. 60

– For any i ̸= j, the distribution of (ri , vi , yi ) is independently and identically distributed as (rj , vj , yj ). – For any i, we have Pr[ri = 1] = Pr

$

y← −{0,1}ℓ(n)

[∄z ∈ {0, 1}n such that HPRHF (z) = y].

– For any i, conditioned on ri = 0, yi is uniformly distributed over all elements in the image of HPRHF , and vi is uniformly distributed over all pre-images of yi . – For any i, conditioned on ri = 1, yi is uniformly distributed over all elements that are not in the image of HPRHF , and vi = ⊥. Therefore, it is identical for us to first sample each ri based on the distribution of HPRHF , and then sample yi and vi based on conditional probability induced by ri . Also, as (ZHB.I, ZHB.π) only depends on r, as long as the distribution of r is the same, the distribution of final output for (ZHB.I, ZHB.π) will also be the same.

Hybrid: H2 We present H2 in Expr. 24 and highlight its difference from H1 in red color. In this hybrid, we replace the exact sampling probability of ri with its approximation, changing the resulting distribution by only a negligible statistical distance. Experiment 24: Hybrid H2

1. Let n = |x|. 2. For i ∈ [phbs (n)], (a) Sample ri ∈ {0, 1} such that Pr[ri = 1] = 1 − Approxδ (1n ) Notice that this change reflects the δ-density property in Property 1, with δ replaced by its efficiently computable approximation Approxδ (1n ) from Def. 2. 3. (ZHB.I, ZHB.π) ← ZHB.Pγ (r, x) where r = r1 . . . rphbs (n) . ( Image := {y ∈ {0, 1}ℓ(n) : ∃z ∈ {0, 1}n such that HPRHF (z) = y} 4. Define PreImage(y) := {z ∈ {0, 1}n : HPRHF (z) = y} 5. For i ∈ [phbs (n)], (a) If ri = 0, sample yi ← Image and vi ← PreImage(yi ), and set vi′ = vi . (b) If ri = 1, sample yi ← {0, 1}ℓ(n) \ Image, and set vi′ =⊥. 6. Output (urs = (y1 . . . yphbs (n) ), π = (ZHB.I, {vi′ }i∈ZHB.I , ZHB.π)). s

Claim 21. It holds that H1 ≈ H2 . Proof. Let D0,x and D1,x be the distributions of binary string r sampled in hybrid H1 (x) and H2 (x) respectively. Based on the δ-density property of HPRHF , we have: ′

γ =1−

[∃z ∈ {0, 1}n such that HPRHF (z) = y]

Pr $

y← −{0,1}ℓ(n)

= 1 − δ ± negl(n)

(Property 1 of Def. 6)

n

(Def. 2)

= 1 − Approxδ (1 ) ± negl(n) 61

As the distribution of each ri is independently and identically distributed, we can bound the statistical distance between D0,x and D1,x with Lem. 37 as follows: ∆(D0,x , D1,x ) ≤ phbs (n) · negl1 (n) = negl2 (n) As these two hybrids only differ in the way of sampling r, and thus there exist a negligible function negl(n) such that: ∆(H1 (x), H2 (x)) ≤ negl(n)

Hybrid: H3 We present H3 in Expr. 25 and highlight its difference from H2 in red color. In this hybrid, we changed the way of sampling vi′ as we defined in the Strong-PreImage Pseudorandomness of the δ-dense post-quantum PRHF . Experiment 25: Hybrid H3

1. Let n = |x|. 2. For i ∈ [phbs (n)], (a) Sample ri ∈ {0, 1} such that Pr[ri = 1] = 1 − Approxδ (1n ) 3. (ZHB.I, ZHB.π) ← ZHB.Pγ (r, x) where r = r1 . . . rphbs (n) . 4. Deletion of the definition of Image and PreImage 5. For i ∈ [phbs (n)], $

(a) If ri = 0, then set vi ← − {0, 1}n , yi = HPRHF (vi ) and set vi′ = vi $

(b) If ri = 1, then set vi ← − {0, 1}n , yi = HPRHF (vi ) and set vi′ =⊥ 6. Output (urs = (y1 . . . yphbs (n) ), π = (ZHB.I, {vi′ }i∈ZHB.I , ZHB.π)). cq

Claim 22. It holds that H2 ≈ H3 . Proof. In this argument, we try to reduce the distinguishability between hybrid H2 and hybrid H3 to breaking the Strong-PreImage Pseudorandomness of the δ-dense post-quantum PRHF. Assume for contradiction that there exist a QPT quantum distinguisher A such that: |Pr[A(H2 (x)) = 1] − Pr[A(H3 (x)) = 1]| ≥

1 poly(n)

We can then construct a non-uniform algorithm Bρ that can break the Strong-PreImage Pseudorandomness of the δ-dense post-quantum PRHF w.r.t. the game defined in Box 1. The algorithm Bρ ’s non-uniform advice ρ contains the snapshot of the execution of H3 at (inclusively) Step 3. In particular, it contains the statement x and the corresponding (ZHB.I, ZHB.π), and the bit-vector r = (r1 . . . rphbs (n) ). Then, Bρ starts to participate the Strong-PreImage Pseudorandomness game by receiving the challenge transcript (r, {yi }i∈[phbs (n)] , {vi }i∈I0 ) from the challenger. (Note that we can assume without loss of generality that this r in the challenge is the same r contained in Bρ ’s non-uniform advice, because the strong pre-image pseudo-randomness defined in Property 3 holds against any bit-vector r.)

62

Algorithm 5.5: Bρ that can break the Strong-PreImage Pseudorandomness

Bρ (1n , HPRHF , r, {yi }i∈[phbs (n)] , {vi }i∈I0 ): 1. Extract x and the corresponding (ZHB.I, ZHB.π) from the non-uniform advice ρ of B. 2. For i ∈ [phbs (n)], (a) If ri = 0, set vi′ = vi (b) If ri = 1, set vi′ =⊥ 3. Set urs = (y1 . . . yphbs (n) ), π = (ZHB.I, {vi′ }i∈ZHB.I , ZHB.π) 4. Invoke A(urs, HPRHF , x, π) and output whatever A outputs. Refering to the strong pre-image pseudorandomness property in Item 3 of Def. 6, the challenge transcript
{ri }i∈[p(n)] , {yi }i∈[phbs (n)] , {vi }i∈I0 is distributed exactly as in hybrid H2 when sampled from D0 , and exactly as in hybrid H3 when sampled from D1 . Consequently, Pr[Bρ (D0 ) = 1] = Pr[A(H2 (x)) = 1]

and

Pr[Bρ (D1 ) = 1] = Pr[A(H3 (x)) = 1].

Therefore, we have: |Pr[Bρ (D0 ) = 1] − Pr[Bρ (D1 ) = 1]| = |Pr[A(H2 (x)) = 1] − Pr[A(H3 (x)) = 1]| ≥

1 , poly(n)

which contradicts the Strong-PreImage Pseudorandomness of the δ-dense post-quantum PRHF. Thus we can conclude that H2 and H3 are indistinguishable towards QPT adversaries with PRHFindependent non-uniform advice.

Hybrid H4 : We present H4 in Expr. 26 and highlight its difference from H3 in red color. In this hybrid, we replace the real proof generated by ZHB.Pγ with the output of the statistical zeroknowledge simulator ZHB.Simγ . Experiment 26: Hybrid H4

1. Let n = |x|. 2. (ZHB.I, {ri }i∈ZHB.I , ZHB.π) ← ZHB.Simγ (x). $

3. For every i ∈ [phbs (n)], sample vi ← − {0, 1}n and set yi = HPRHF (vi ). 4. For every i ∈ ZHB.I, (a) If ri = 0, set vi′ = vi . (b) If ri = 1, set vi′ =⊥. 5. Output (urs = (y1 . . . yphbs (n) ), π = (ZHB.I, {vi′ }i∈ZHB.I , ZHB.π)). s

Claim 23. It holds that H3 ≈ H4 . Proof. In this argument, we try to reduce the distinguishability between hybrid H3 and hybrid H4 to breaking the statistical zero-knowledge property of the ZHB.NIZK. 63

Recall that γ = 1 − δ. We choose the approximation algorithm for γ such that Approxγ (1n ) = 1 − Approxδ (1n ). Therefore, the distribution of r in H3 is identical to the distribution generated by ZHB.Genγ (1n ). Assume for contradiction that there exists a quantum distinguisher A such that |Pr[A(H3 (x)) = 1] − Pr[A(H4 (x)) = 1]| ≥

1 . poly(n)

We can then construct an adversary A2 that breaks the statistical zero-knowledge property of the ZHB.NIZK as follows: Algorithm 5.6: A2 that breaks the Statistical Zero-Knowledge Property of the ZHB.NIZK

A2 (x, ZHB.I, {ri }i∈ZHB.I , ZHB.π): 1. Let n = |x|. $

2. Sample HPRHF ← −H. $

3. For every i ∈ [phbs (n)], sample vi ← − {0, 1}n independently and set yi = HPRHF (vi ). 4. For every i ∈ ZHB.I, (a) If ri = 0, set vi′ = vi . (b) If ri = 1, set vi′ =⊥. 5. Set urs = (y1 . . . yphbs (n) ) and π = (ZHB.I, {vi′ }i∈ZHB.I , ZHB.π) 6. Output A(urs, HPRHF , x, π). We first argue that A2 exactly simulates hybrid H3 when its input is sampled from the real-world distribution of the ZHB.NIZK. In this case, r ← ZHB.Genγ (1n ) and (ZHB.I, ZHB.π) ← ZHB.Pγ (r, x). After receiving the revealed bits {ri }i∈ZHB.I , the adversary A2 samples every vi independently, sets yi = HPRHF (vi ), and defines vi′ in exactly the same manner as hybrid H3 . Therefore,   r ← ZHB.Genγ (1n ), Pr A2 (x, ZHB.I, {ri }i∈ZHB.I , ZHB.π) = 1 : (ZHB.I, ZHB.π) ← ZHB.Pγ (r, x) = Pr[A(H3 (x)) = 1]. Similarly, when the input of A2 is sampled from the simulated-world distribution (ZHB.I, {ri }i∈ZHB.I , ZHB.π) ← ZHB.Simγ (x), the output distribution of A2 is identical to the output distribution of A in hybrid H4 . Therefore, Pr [A2 (x, ZHB.I, {ri }i∈ZHB.I , ZHB.π) = 1 : (ZHB.I, {ri }i∈ZHB.I , ZHB.π) ← ZHB.Simγ (x)] = Pr[A(H4 (x)) = 1]. 64

By combining the above two equalities, we have |Pr [A2 (RealZHB (x)) = 1] − Pr [A2 (SimZHB (x)) = 1]| = |Pr[A(H3 (x)) = 1] − Pr[A(H4 (x)) = 1]| ≥

1 . poly(n)

This contradicts the statistical zero-knowledge property of the ZHB.NIZK. Thus, we can conclude that hybrid H3 and hybrid H4 are statistically indistinguishable. Completes the proof of Zero-Knowledge: By combining the indistinguishability between hybrid H0 and hybrid H4 , we can conclude that the real-world interaction between the adversary and the real prover is computationally indistinguishable from the output of the simulator towards any QPT quantum adversary with H-independent non-uniform advice. This completes the proof of the ZK property in the URS-PRHF model.

6 6.1

NIZK in QROM Structure of Our Construction

We now turn our URS-PRHF-model NIZK construction into a NIZK proof system in the QROM by realizing both the PRHF and the reference string using a single quantum random oracle. Our strengthened post-quantum PRHF definition allows us to reuse the proof for the zero-knowledge property from Sec. 5 when we instantiate the PRHF using a random oracle. This differs from [GIK+ 23], where the use of hash-dependent non-uniform advice prevents the URS zero-knowledge proof from directly carrying over to the random-oracle setting. The remaining work is to simulate the oracle supplying the URS and to justify combining the two oracle interfaces. We organize the construction into the following three steps: 1. Instantiate the PRHF in our URS-PRHF-model NIZK construction (Sec. 5.1) with a quantum random oracle OPRHF . This step relies on our result that random oracles instantiate strong post-quantum PRHFs (Sec. 4.2), and yields a URS-PRHF-model NIZK proof system relative to OPRHF . 2. Replace the URS with values of an independent random oracle OURS , obtaining a NIZK proof system with access to two independent quantum random oracles. The conditional compressed oracle enables efficient simulation of OURS conditioned on the reference string produced by the URS simulator. 3. Apply the two-oracle-to-one-oracle technique (Sec. 3.3) to implement both oracles using a single quantum random oracle, yielding the desired NIZK proof system in the QROM. For the random-oracle instantiation of the URS-PRHF-model NIZK construction (Sec. 5.1), the PRHF density parameter and the complementary hidden-bit parameter are 1 δ =1− , e

1 γ =1−δ = . e

The construction requires both constants to be efficiently approximable. It suffices to establish this property for γ = 1/e: subtracting an approximation to γ from 1 yields an approximation to δ with the same error. The proof is standard and is deferred to Sec. A.3. 65

6.2

Instantiating the PRHF

Our analysis (Sec. 4.2) shows that a quantum random oracle OPRHF ← O instantiates a (1 − 1/e)dense post-quantum PRHF. Since 1 − 1/e is efficiently approximable (Corollary 8), applying our URS-PRHF-model construction (Sec. 5.1) yields a NIZK proof system with both URS and RO:
ΠURS = URS.Gen, URS.POPRHF , URS.VOPRHF , with simulator URS.Sim|OPRHF ⟩ . We use the zero-knowledge guarantee established in Sec. 5.1 against polynomial-time quantum distinguishers with quantum oracle access to OPRHF . All security probabilities include the sampling of OPRHF ← O, together with the randomness and measurement outcomes of the relevant algorithms. The oracle is sampled once and remains fixed throughout each experiment. 6.3

Replacing the URS

Lemma 18 (Eliminating the URS). Suppose that ΠURS , relative to OPRHF , has perfect completeness, adaptive statistical soundness with error εs (n), and zero knowledge against polynomialquery-bounded quantum distinguishers, with a QPT oracle simulator. Then there exists an unbounded-prover NIZK proof system ΠTWO−QROM for L with separate quantum access to two independent random oracles OURS and OPRHF , without an additional reference string. The system preserves perfect completeness, adaptive statistical soundness with error εs (n), and zero knowledge against the same class of distinguishers, with a stateful QPT simulator. Proof. We construct ΠTwoQROM by deriving the reference string from OURS and invoking the prover and verifier of the URS-PRHF-model construction with quantum access to OPRHF . We then analyze its security properties separately. Throughout the following analysis, an integer index i used as an input to OURS is understood to denote ⟨i⟩n , its padded n-bit binary representation as defined in Sec. 3. The same convention applies to integer-labelled oracle locations in sets, conditioning events, and partial tables. For simplicity, we suppress these encodings until the final construction in Sec. 6.5, where we write them explicitly. Let n = |x| and m = phbs (n). The reference string in the instantiated URS system consists of m independent, uniformly distributed n-bit blocks. We obtain these blocks from a random oracle OURS , sampled independently of OPRHF , by setting yi := OURS (i),

i ∈ [m].

Define Un (OURS ) := OURS (1)∥ · · · ∥OURS (m). The prover and verifier are defined as follows. Algorithm 6.1: Two-Oracle QROM Prover TwoQROM.P

TwoQROM.POURS ,OPRHF (x): 1. Set n = |x| and m = phbs (n). 2. For each i ∈ [m], query OURS at i to obtain yi = OURS (i). 3. Set urs = y1 ∥ · · · ∥ym . 4. π ← URS.POPRHF (urs, x) and return π.

66

Algorithm 6.2: Two-Oracle QROM Verifier TwoQROM.V

TwoQROM.VOURS ,OPRHF (x, π): 1. Set n = |x| and m = phbs (n). 2. For each i ∈ [m], query OURS at i to obtain yi = OURS (i). 3. Set urs = y1 ∥ · · · ∥ym . 4. Return URS.VOPRHF (urs, x, π). Since the values of OURS at distinct inputs are independent and uniform, Un (OURS ) has exactly the distribution generated by URS.Gen(1n ). Moreover, it is independent of OPRHF . Hence,

OPRHF , Un (OURS ) ≡ OPRHF , URS.Gen(1n ) , (31) where the reference string on the right is generated independently of OPRHF . Conditioning on the reference string fixes only the values OURS (1), . . . , OURS (m). The remaining values OURS (z), for z ∈ / [m], remain mutually independent and uniformly distributed, and are independent of OPRHF . For a fixed statement x, this property also holds after conditioning on the honest proof π: the prover accesses OURS only to obtain urs, and its subsequent computation depends only on urs, x, its internal randomness, and OPRHF . More explicitly, fix x and let z1 , . . . , zt ∈ / [m] be distinct oracle inputs. For arbitrary v1 , . . . , vt ∈ {0, 1}n ,   t ^ Pr  OURS (zj ) = vj OPRHF = F, urs = u0 , π = π0  = 2−nt , j=1

whenever the conditioning event has positive probability. Thus, writing u0 = y1 ∥ · · · ∥ym , quantum access to OURS under this conditioning is exactly emulated by the partially-fixed compressed oracle initialized with the partial table {(i, yi ) : i ∈ [m]}. 6.3.1

Completeness

Lemma 19 (Perfect completeness). If ΠURS has perfect completeness, then ΠTwoQROM has perfect completeness. Proof. Fix x ∈ L and let n = |x|. By construction and the distributional identity in (31),   Pr TwoQROM.VOURS ,OPRHF (x, π) = 1 : π ← TwoQROM.POURS ,OPRHF (x)   urs ← URS.Gen(1n ), OPRHF = Pr URS.V (urs, x, π) = 1 : π ← URS.POPRHF (urs, x) = 1. The first probability includes the independent sampling of OURS and OPRHF ; the second includes the independent sampling of OPRHF and urs. Both probabilities also include the internal randomness of the algorithms. The final equality follows from the perfect completeness of ΠURS . 6.3.2

Soundness

Lemma 20 (Adaptive statistical soundness). If ΠURS has adaptive statistical soundness with error εs (n), then ΠTwoQROM has adaptive statistical soundness with the same error. 67

Proof. For a fixed oracle OPRHF and reference string urs, define   Badn (OPRHF , urs) := ∃x ∈ {0, 1}n \ L, ∃π : URS.VOPRHF (urs, x, π) = 1 . Every statement of length n uses the same reference string Un (OURS ). Therefore,   Pr ∃x ∈ {0, 1}n \ L, ∃π : TwoQROM.VOURS ,OPRHF (x, π) = 1 OURS , OPRHF 
 = Pr Badn OPRHF , Un (OURS ) OURS , OPRHF

=

Pr

OPRHF ←O, urs←URS.Gen(1n )

[Badn (OPRHF , urs)]

≤ εs (n). The second equality follows from (31), and the final inequality is the adaptive statistical soundness of ΠURS . The existential quantifiers range over all false statements of length n and all proofs. Thus, the argument permits adaptive statement selection and computationally unbounded cheating provers.

6.3.3

Zero Knowledge

For a reference string urs = y1 ∥ · · · ∥ym , define HDurs := {(i, yi ) : i ∈ [m]}. This table defines a consistent partial function because its inputs are distinct. By Lem. 7 , Com(HDurs ) perfectly emulates quantum access to a random oracle conditioned on its first m values being y1 , . . . , ym . All remaining values are mutually independent, uniformly distributed n-bit strings. Algorithm 6.3: Proof Simulator TwoQROM.SimProof

TwoQROM.SimProof(x): 1. Set n = |x| and m = phbs (n). 2. Initialize the PRHF-oracle simulator: CPRHF ← Com(∅). 3. Run: (urs∗ , π ∗ ) ← URS.Sim|CPRHF ⟩ (x). Retain the resulting state of CPRHF . ∗ and set HD∗ := {(i, y ∗ ) : i ∈ [m]}. 4. Parse urs∗ = y1∗ ∥ · · · ∥ym i

5. Initialize the URS-oracle simulator: CURS ← Com(HD∗ ). 6. Output (st, π ∗ ), where st contains the current joint state of CURS and CPRHF . Algorithm 6.4: Oracle Simulator TwoQROM.SimRO

TwoQROM.SimRO maintains st and provides two quantum oracle interfaces: 1. Upon a query to |OURS ⟩, apply the query operation of CURS . 2. Upon a query to |OPRHF ⟩, apply the query operation of CPRHF . Each operation acts coherently on the query registers and the corresponding compressed-oracle state. Return the query registers and retain the resulting joint simulator state for subsequent queries. 68

The oracle simulation continues from the state produced during the execution of URS.Sim, preserving its correlations with the simulated reference string and proof. Only the URS-oracle simulator is initialized with a nonempty conditioning table, namely HD∗ . At initialization, conditioned on (urs∗ , π ∗ ), the unspecified URS-oracle values are fresh, mutually independent uniform strings, independent of the preceding simulation. Lemma 21 (Zero knowledge). Suppose that ΠURS satisfies zero knowledge against polynomialquery-bounded quantum distinguishers with access to |OPRHF ⟩. Then ΠTwoQROM satisfies zero knowledge against polynomial-query-bounded quantum distinguishers with separate access to |OURS ⟩ and |OPRHF ⟩, with an efficient stateful simulator. Proof. Fix a polynomial-query-bounded quantum distinguisher A and a statement x ∈ L, and let n = |x|. We construct a URS-PRHF-model distinguisher B |OPRHF ⟩ such that any non-negligible distinguishing advantage of A contradicts the zero-knowledge guarantee of Sec. 5.2. Algorithm 6.5: URS Distinguisher B

B |OPRHF ⟩ (urs, x, π): 1. Set n = |x| and m = phbs (n), and parse urs = y1 ∥ · · · ∥ym . 2. Initialize CURS ← Com(HDurs ). 3. Run A(x, π), answering its queries to |OURS ⟩ using CURS and forwarding its queries to |OPRHF ⟩ to the supplied oracle. Retain the state of CURS throughout the interaction. 4. Output the bit returned by A. Real experiment. When (urs, π) is a real URS transcript, B exactly reproduces the real experiment for ΠTwoQROM . Indeed, urs is uniform and independent of OPRHF . Conditioned on urs, OPRHF , and π, the URS-oracle values outside [m] remain mutually independent and uniform, as shown above. Lem. 7 therefore gives an exact emulation of quantum access to the URS oracle under this conditioning. Consequently, i h preal := Pr A|OURS ⟩,|OPRHF ⟩ (x, π) = 1 : π ← TwoQROM.POURS ,OPRHF (x)   urs ← URS.Gen(1n ), |OPRHF ⟩ = Pr B (urs, x, π) = 1 : . π ← URS.POPRHF (urs, x) This equality also holds when queries to the two oracles are interleaved. For each fixed OPRHF , its query operations are intervening operations on the distinguisher’s registers, which are covered by the exact simulation in Lem. 7. Simulated experiment. When (urs∗ , π ∗ ) is generated by URS.Sim|OPRHF ⟩ , the reduction runs A(x, π ∗ ) with access to the same OPRHF and to Com(HDurs∗ ) as its URS-oracle interface. Apply Lem. 7 with the empty partial function to this entire computation: the execution of URS.Sim, the initialization of the conditional URS oracle, and the subsequent execution of A. Replacing OPRHF throughout by a single persistent Com(∅) preserves the output distribution exactly. The resulting computation is precisely the simulation defined above. Retaining the PRHForacle state throughout preserves all correlations among urs∗ , π ∗ , and subsequent oracle responses. In the following experiment, |CURS ⟩ and |CPRHF ⟩ denote the two stateful interfaces maintained by TwoQROM.SimRO using the joint state st returned by TwoQROM.SimProof. We obtain h i psim := Pr A|CURS ⟩,|CPRHF ⟩ (x, π ∗ ) = 1 : (st, π ∗ ) ← TwoQROM.SimProof(x) 69

h i = Pr B |OPRHF ⟩ (urs∗ , x, π ∗ ) = 1 : (urs∗ , π ∗ ) ← URS.Sim|OPRHF ⟩ (x) . Reduction and efficiency. The reduction B makes no additional queries to OPRHF beyond those made by A. By Lem. 7, simulating the URS oracle adds only polynomial overhead in n, the query count, and the size of HDurs . Since A is polynomial-query-bounded, B is also polynomial-querybounded. Applying the zero-knowledge guarantee of ΠURS to B and using the two identities above yields preal − psim ≤ negl(n). Finally, URS.Sim is QPT, and a QPT distinguisher makes only polynomially many additional oracle queries. The PRHF compressed oracle handles their combined query sequence while retaining its state throughout. The URS compressed oracle starts with m prescribed entries and handles polynomially many subsequent queries. Lem. 7 therefore gives polynomial time and space for both oracle simulations. Thus, the proof simulator is QPT, the stateful oracle simulator runs in polynomial time throughout any QPT interaction, and the transformation introduces no additional distinguishing error. Together, Lem. 19 to 21 prove Lem. 18.

6.4

Combining the Two Oracles

There exists an unbounded-prover NIZK proof system for NP in the QROM with perfect completeness, adaptive statistical soundness, and zero knowledge against quantum polynomial-time oracle-aided distinguishers. Let O ← O be a single random oracle. By Lem. 1, interpret O as providing mutually independent random functions On+1,n : {0, 1}n+1 → {0, 1}n , n ∈ N. For each n and every z ∈ {0, 1}n , define OURS (z) := On+1,n (0∥z),

OPRHF (z) := On+1,n (1∥z).

These restrictions are independent random functions from {0, 1}n to {0, 1}n , since their input domains are disjoint. The resulting system therefore inherits perfect completeness and adaptive statistical soundness from ΠTwoQROM . The oracle-merging lemma (Sec. 3.3) gives an exact implementation of each query to |On+1,n ⟩ using four queries to the separate interfaces |OURS ⟩ and |OPRHF ⟩, with polynomial-time overhead. This implementation also applies when the prefix register is in superposition or entangled with other registers. Thus, any QPT distinguisher with access to |O⟩ induces a QPT distinguisher with separate access to |OURS ⟩ and |OPRHF ⟩. 6.5

Final Construction

Combining the above results and exploiting the exact construction in Sec. 5.1, we state the final construction of a NIZK proof system for NP in the QROM.

70

Algorithm 6.6: The Prover QRO.PO

QRO.PO (x): 1. Let n = |x|. 2. For i ∈ [phbs (n)], set yi = On+1,n (0||⟨i⟩n ) where ⟨i⟩n is the n-bit binary representation of i as we defined in Sec. 3 3. For i ∈ [phbs (n)], $

− {z ∈ {0, 1}n : On+1,n (1||z) = yi }, (a) If ∃z ∈ {0, 1}n such that On+1,n (1||z) = yi , sample vi ← and set ri = 0. (b) If ∄z ∈ {0, 1}n such that On+1,n (1||z) = yi , set vi =⊥ and ri = 1. 4. (ZHB.I, ZHB.π) ← ZHB.Pe−1 (r, x) where r = r1 . . . rphbs (n) . 5. Return π := (ZHB.I, {vi }i∈ZHB.I , ZHB.π). Algorithm 6.7: The Verifier QRO.VO

QRO.VO (x, π): 1. Let n = |x|. 2. For i ∈ [phbs (n)], set yi = On+1,n (0||⟨i⟩n ) 3. Parse π as (ZHB.I, {vi }i∈ZHB.I , ZHB.π). 4. For i ∈ ZHB.I, – If vi =⊥, set rei = 1. – If vi ̸=⊥, and On+1,n (1||vi ) = yi , set rei = 0. – If vi ̸=⊥, and On+1,n (1||vi ) ̸= yi , reject. ri }i∈ZHB.I , ZHB.π) 5. Return ZHB.Ve−1 (x, ZHB.I, {e Algorithm 6.8: Proof Simulator QRO.SimProof

QRO.SimProof(x): 1. Let n = |x|. 2. (ZHB.I, {ri }i∈ZHB.I , ZHB.π) ← ZHB.Sim 1 (x). e

3. Create history database HD = {}. 4. For i ∈ [phbs (n)] $

(a) Sample vi ← − {0, 1}n . $

(b) If (1∥vi , y) ∈ HD for some y, set yi = y. Otherwise, sample yi ← − {0, 1}n . (c) Update history database HD = HD ∪ {(0||⟨i⟩n , yi ), (1||vi , yi )} 5. For i ∈ ZHB.I, (a) If ri = 1, set vi′ =⊥ (b) If ri = 0, set vi′ = vi . 6. Set π = (ZHB.I, {vi′ }i∈ZHB.I , ZHB.π). 71

7. Return (st, π), where st contains the current state of the compressed oracle Com(HD). Algorithm 6.9: Oracle Simulator QRO.SimRO

QRO.SimRO(st): 1. Answer each quantum query using the compressed partially fixed oracle with regard to the current state st, retaining its updated state for subsequent queries.

7

Oracle Separation between NP ∩ coNP and BQP

We now prove the random-oracle separation informally stated in Thm. 1. Theorem 4. If UP ⊈ BQP, then   Pr NPO ∩ coNPO ⊈ BQPO = 1.

O←O

To prove Thm. 4, we adapt the language construction of [GIK+ 23] using the QROM NIZK proof system from Sec. 6.5. We start with a language L0 ∈ UP \ BQP and define an oracle-aided language LO on triples (x, i, π). The proof π certifies that x ∈ L0 , and membership in LO asks whether the i-th bit of the unique witness for x is 1. Uniqueness and the statistical soundness of the proof system give LO ∈ NPO ∩ coNPO for almost every oracle (Lem. 24). We then establish quantum hardness in Lem. 25. If a fixed quantum oracle machine decided LO on at least a 2/3 fraction of oracles, we could use it together with the NIZK simulator to recover the unique witness bit by bit without access to O. Verifying the recovered witness would give a BQP decider for L0 . Finally, we apply the Bennett–Gill argument in Lem. 22 to conclude that, with probability 1 over O, no quantum polynomial-time oracle machine decides LO . 7.1

Technical Tool

We use a quantum formulation of the Bennett–Gill argument [BG81, Lemma 1] to pass from a bound for each fixed quantum oracle machine to an almost-sure hardness result. Under the finitedependence and decidability conditions below, a uniform gap from probability 1 implies that each fixed machine decides the language only on a measure-zero set of oracles. Since there are countably many such machines, their success sets together still have measure zero. This lemma serves as a key technical tool in Sec. 7.5, where we use it to show that LO ∈ / BQPO for almost every oracle O. Lemma 22 ([BG81, Lemma 1], Refurnished). Let L(·) be an oracle-dependent language such that each bit of the oracle affects the membership of only finitely many strings in LO ; that is, for every j ∈ N there exists a finite set Fj such that for any two oracles O and O′ differing only in ′ their j-th bit, and for any (x, i, π) ∈ / Fj , we have LO (x, i, π) = LO (x, i, π), where ( LO (x, i, π) :=

1 0

(x, i, π) ∈ LO . otherwise

Moreover, assume that LO is decidable by an oracle Turing machine that halts on all inputs for every oracle O. 72

(·)

(·)

Let D(·) = {D1 , D2 , . . .} be the set of all possible oracle-aided polynomial-time quantum Turing Machines. If there exists a constant ε ∈ (0, 1] such that for all k ∈ N,  h i 2 |O⟩ ∗ O Pr ∀(x, i, π) ∈ {0, 1} , Pr Dk (x, i, π) = L (x, i, π) ≥ < 1 − ε, O 3 then  h i 2 |O⟩ ∗ O = 0. Pr ∃k ∈ N such that ∀(x, i, π) ∈ {0, 1} , Pr Dk (x, i, π) = L (x, i, π) ≥ O 3

(32)

Proof. Since a countable union of events of probability zero still has probability zero, it suffices to prove that, for every k ∈ N,  h i 2 |O⟩ Pr ∀(x, i, π) ∈ {0, 1}∗ , Pr Dk (x, i, π) = LO (x, i, π) ≥ = 0. O 3 Below, we fix k. For each n ∈ N, let Sn be the set of all oracles O such that h i 2 |O⟩ ∀(x, i, π) ∈ {0, 1}≤n , Pr Dk (x, i, π) = LO (x, i, π) ≥ , 3 where {0, 1}≤n denotes the set of all bit strings of length at most n. Then, it suffices to prove that " # \ Pr O ∈ Sn = 0. O

n∈N

To this end, we establish the following claim. Claim 24. For any m ∈ N, there exists m′ > m such that Pr[O ∈ Sm′ | O ∈ Sm ] < 1 − ε. O

We first complete the proof of Lem. 22 assuming Claim 24, and then proceed to prove Claim 24 itself. By the claim, we may choose an increasing sequence m0 < m1 < m2 < · · · such that Pr[O ∈ Smj | O ∈ Smj−1 ] < 1 − ε O

for all j ∈ N.

Since {Sn }n is monotonically decreasing, we have Pr[O ∈ Smj ] = Pr[O ∈ Smj ∧ O ∈ Smj−1 ] O

O

= Pr[O ∈ Smj | O ∈ Smj−1 ] Pr[O ∈ Smj−1 ] O

O

< (1 − ε) Pr[O ∈ Smj−1 ]. O

By induction, we have Pr[O ∈ Smj ] < (1 − ε)j Pr[O ∈ Sm0 ] ≤ (1 − ε)j . O

O

73

Since {Sn }n is monotonically decreasing, the following holds as desired # " \ Pr O ∈ Sn = lim Pr[O ∈ Sn ] ≤ lim (1 − ε)j = 0 O

n→∞ O

n∈N

j→∞

This finishes the proof of Lem. 22, modulo the proof of Claim 24, which we provide below. Proof of Claim 24: Let Tk (m) denote the maximum running time of Dk on inputs of length at most m. Then, on inputs of length at most m, the machine Dk can make oracle queries of length at most Tk (m), and hence can access only the first 2Tk (m) bits of O. Also, let M be the oracle Turing machine guaranteed by the assumption of the lemma, which decides LO and halts on every input for every oracle O. For every m, there exists a finite bound U (m) such that M O halts within U (m) steps on every input of length at most m, uniformly over all oracles O. Indeed, this follows from König’s lemma, since otherwise there would exist an oracle O and an input on which M O does not halt. Therefore, whether O ∈ Sm depends only on the first 2Rk (m) bits of O, where Rk (m) := max{Tk (m), U (m)}. Consequently, to prove the claim it suffices to show that there exists m′ such that, for every R (m) s ∈ {0, 1}2 k , Pr[O ∈ Sm′ | O has prefix s] < 1 − ε, O

or equivalently, Pr[s ∗ O ∈ Sm′ ] < 1 − ε, O

where s ∗ O denotes the oracle obtained by replacing the first 2Rk (m) bits of O with s. Since there are only finitely many such strings s, and since the sets Sn are monotonically decreasing in n, we may interchange the order of quantifiers over s and m′ .11 Namely, it suffices to R (m) show that for every s ∈ {0, 1}2 k there exists m′ such that Pr[s ∗ O ∈ Sm′ ] < 1 − ε. O

Below, we fix s, and prove that the above holds for some m′ . Since 2Rk (m) is a finite constant, by the premise of Lem. 22 there exists a finite set Bm ⊆ {0, 1}∗ such that for all oracles O, LO (x, i, π) = Ls∗O (x, i, π)

for all (x, i, π) ∈ / Bm .

e |O⟩ as follows: We define a modified oracle-aided quantum Turing machine D k |O⟩

|s∗O⟩

e : On input (x, i, π), if (x, i, π) ∈ Bm , output LO (x, i, π); otherwise, output D – D k k

(x, i, π).

e k is also a QPT machine, since s and Bm are finite and, as shown above, LO is Note that D e (·) belongs to the family D(·) computable in oracle-independent constant time on Bm . Namely, D k defined in the statement of Lem. 22. Thus, it follows from the premise of Lem. 22 that  h i 2 |O⟩ ∗ O e Pr ∀(x, i, π) ∈ {0, 1} , Pr Dk (x, i, π) = L (x, i, π) ≥ < 1 − ε. O 3 11

Suppose that for each s there exists m′s such that PrO [s ∗ O ∈ Sm′s ] < 1 − ε. Let m′ := maxs m′s . Then Sm′ ⊆ Sm′s for all s, and hence Pr[s ∗ O ∈ Sm′ ] ≤ Pr[s ∗ O ∈ Sm′s ] < 1 − ε. O

O

74

By construction, for all O and all (x, i, π) ∈ Bm , it holds that e |O⟩ (x, i, π) = LO (x, i, π). D k Moreover, for for all O and all (x, i, π) ∈ / Bm , e |O⟩ (x, i, π) = D|s∗O⟩ (x, i, π) D k k

and

LO (x, i, π) = Ls∗O (x, i, π).

Therefore,  h i 2 |s∗O⟩ s∗O < 1 − ε. Pr ∀(x, i, π) ∈ / Bm , Pr Dk (x, i, π) = L (x, i, π) ≥ O 3 This immediately implies  h i 2 |s∗O⟩ ∗ s∗O (x, i, π) = L (x, i, π) ≥ Pr ∀(x, i, π) ∈ {0, 1} , Pr Dk < 1 − ε, O 3 or equivalently (by the definition of Sn ), " Pr s ∗ O ∈ O

# \

Sn < 1 − ε.

n∈N

Since the sets Sn are monotonically decreasing, " lim Pr[s ∗ O ∈ Sn ] = Pr s ∗ O ∈

n→∞ O

O

# \

Sn < 1 − ε.

n∈N

Hence, there exists m′ such that Pr[s ∗ O ∈ Sm′ ] < 1 − ε. O

This completes the proof of Claim 24.

7.2

Post-Quantum injOWF Implies UP ⊈ BQP

For a better illustration of the oracle separation result between NP ∩ coNP and BQP, we start by first establishing the connection between the existence of injective post-quantum one-way function and the separation between UP and BQP, instead of directly starting with a vague language that lies in UP \ BQP. It does not mean that the existence of injective post-quantum one-way function is necessary for the separation between NP ∩ coNP and BQP, but it provides us a more clear starting point to construct such oracle separation result. Lemma 23. If there exists an injective post-quantum one-way function f : {0, 1}∗ → {0, 1}∗ , then UP ̸⊆ BQP. Proof. Consider the language built from the function f as follows: L := {(y, i) ∈ {0, 1}∗ × N : ∃x ∈ {0, 1}∗ , f (x) = y ∧ xi = 1 ∧ i ≤ |x|} . Here, the index i is encoded in binary. It is easy to see that L ∈ NP since we can verify the membership of every y in L with the corresponding x as the witness. The uniqueness of the witness x is guaranteed by the injectivity of f . Also, the BQP hardness of L follows from the post-quantum one-wayness of f , otherwise the pre-image can be inverted with bit-by-bit recovery alongside with the standard amplification of BQP. We can then conclude that L ∈ UP \ BQP. 75

7.3

The Oracle-Aided Language LO

Following [GIK+ 23], we construct an oracle-aided language whose instances ask for a bit of a unique witness. Fix a base language L0 ∈ UP\BQP (Existence is guaranteed by the assumption UP ⊈ BQP) and a witness relation RL0 . Let ΠNIZK = (P (·) , V (·) ) be the QROM NIZK proof system from Sec. 6.5 instantiated for L0 . We form an oracle-aided language by attaching a proof of x ∈ L0 to each query about a bit of its unique witness. For a fixed oracle O, define
 (33) LO := (x, i, π) ∃w : (x, w) ∈ RL0 ∧ wi = 1 ∧ ΠNIZK .V O (x, π) = 1 . We proceed to show that LO belongs to NPO ∩ coNPO for almost every oracle in Sec. 7.4. We establish its quantum hardness in Sec. 7.5. 7.4

Membership in NPO ∩ coNPO

The following lemma follows directly from [GIK+ 23, Lemma 8.4]. As in their construction, our QROM proof system has a classical prover and verifier and satisfies perfect completeness and adaptive statistical soundness. We only use its zero-knowledge guarantee against quantum adversaries in Sec. 7.5. Lemma 24 ([GIK+ 23, Lemma 8.4]). If UP ⊈ BQP, then with probability 1 over the choice of a random oracle O ← O, the language LO defined in Eq. (33) belongs to NPO ∩ coNPO . Equivalently,   Pr LO ∈ NPO ∩ coNPO = 1. O←O

7.5

Non-Membership in BQPO

We now show that the oracle-aided language defined in Eq. (33) remains hard for quantum polynomialtime algorithms with superposition access to the oracle. The proof uses the QROM NIZK simulator to turn a machine that decides LO on every input for at least a 2/3 fraction of oracles into an oraclefree BQP decider for L0 . We then apply Lem. 22 to turn the resulting bound for each fixed machine into an almost-sure hardness result. Lemma 25. If UP ⊈ BQP, then with probability 1 over the choice of a random oracle O ← O, the language LO defined in Eq. (33) lies outside BQPO . Equivalently,   Pr LO ∈ / BQPO = 1. O←O

Proof. Fix any oracle-aided QPT machine D(·) , and define the set of good oracles on which D decides LO on all inputs as  h i 2 ∗ |O⟩ O GD := O : ∀(x, i, π) ∈ {0, 1} , Pr D (x, i, π) = L (x, i, π) ≥ . 3 To apply Lem. 22 for the separation results, we first have to show that PrO [O ∈ GD ] < 2/3, note that 23 here can be replaced by any real number ε where 12 < ε < 1 Assume for contradiction that PrO [O ∈ GD ] ≥ 2/3 We then build a quantum decider in BQP for the base language L0 with the help of the zero-knowledge simulator constructed in the previous section. In particular, the real oracle-aided decider for the i-th bit is defined as follows:

76

|O⟩

Algorithm 7.1: Real-decider for i-th bit: D(i) |O⟩

D(i) (x, π) 1. Prepare an empty multiset Bits = {} 2. for j ∈ [|x|] (a) Invoke D|O⟩ (x, i, π), add the output to Bits 3. Return the majority element in Bits. Lemma 26. For all (x, w) ∈ RL0 and all i ∈ [p(|x|)], we have   2 O ← O, |O⟩ ≥ − negl(|x|). Pr D(i) (x, π) = wi : π ← P O (x) 3 Here, P is the honest NIZK prover, and the decider uses the same sampled oracle O. The probability also includes the internal randomness and measurement outcomes of the algorithms. Proof. By perfect completeness, an honestly generated proof π ← P O (x) satisfies V O (x, π) = 1 with probability 1. Hence, conditioned on O ∈ GD , each invocation of D|O⟩ (x, i, π) outputs wi with probability at least 2/3. Let X be the random variable of the count of wi in Bits and Xj = 1 if D|O⟩ (x, i, π) = wi in the |O⟩ j-th iteration, otherwise Xj = 0. Notice the event that the output of D(i) (x, π) is wi is equivalent to the event that X is larger than |Bits| 2 , and the bad event probability is bounded by the Chernoff bound as follows:   h i |Bits| |O⟩ Pr D(i) (x, π) ̸= wi = Pr X ≤ 2   |x| X |x|  Xj ≤ = Pr  2 j=1   |x| X 1 2|x|  = Pr  Xj ≤ (1 − ) 4 3 j=1   |x| X 1 ≤ Pr  Xj ≤ (1 − )E[X] 4 j=1   1 2 1 ≤ exp −E[X] · ( ) · (Chernoff Bound) 4 2   2|x| 1 ≤ exp − · 3 32   |x| = exp − 48 =negl(|x|) Averaging over the choice of O , we obtain h i |O⟩ Pr D(i) (x, π) = wi ≥ Pr[O ∈ GD ] − negl(|x|) O

77

≥

2 − negl(|x|), 3

as desired. e without actual access to the oracle is defined as follows: The quantum decider D e Algorithm 7.2: Simulated-decider for i-th bit: D(x, i)

e i) D(x, 1. Invoke SimProof(x) to get (st, π) |SimRO(st,·)⟩

2. Return D(i)

(x, π).

Lemma 27. For all (x, w) in the relation RL0 and all i ∈ [p(|x|)], h i e i) = wi ≥ 2 − negl(|x|). Pr D(x, 3 |O⟩

Proof. Apply the zero-knowledge property of the NIZK to D(i) which is polynomial-bound. The probability that this bit equals wi differs by at most a negligible amount. Combining this with Lem. 26 proves the lemma. e i) is at least By Lem. 27, for some negligible function neglsim , the success probability of D(x, 2/3 − neglsim (|x|). Since neglsim is negligible, there exists a constant n0 such that, for every n ≥ n0 , we have neglsim (n) ≤ 1/15. Therefore, for every |x| ≥ n0 , 2 2 1 3 − neglsim (|x|) ≥ − = . 3 3 15 5 This bound is not required to hold when |x| < n0 . Instead, for these input lengths we can exhaustively search for the unique witness using the efficiently decidable relation RL0 as L0 ∈ UP. Although this search takes exponential time as a function of |x|, its running time on the branch |x| < n0 is bounded by 2p(n0 ) · poly(n0 ), which is a fixed constant. We define the amplified quantum decider as follows: b Algorithm 7.3: Amplified decider for i-th bit: D(x, i)

b i) D(x, 1. Let n = |x|. 2. If n < n0 : (a) Enumerate every w ∈ {0, 1}≤p(n) . (b) If (x, w) ∈ RL0 , return wi . (c) If no such witness exists, return 0. 3. Prepare an empty multiset Bits = {}. 4. For j ∈ [n]: e i), and add its output to Bits. (a) Invoke a fresh instance of D(x, 5. Return the majority element in Bits. 78

We then show that the amplified decider recovers each witness bit with overwhelming probability. Lemma 28. For all (x, w) in the relation RL0 and all i ∈ [p(|x|)], i h b i) = wi ≥ 1 − negl(|x|). Pr D(x, b i) decide the witness bit wi perfectly, which Proof. For the case that |x| < n0 , it is clearly that D(x, means h i b i) = wi = 1 Pr D(x, For the case that |x| ≥ n0 , e i) Let Xj be the indicator random variable for the event that the j-th invocation of D(x, P|x| outputs wi , and let X = j=1 Xj . Every invocation uses fresh randomness for the simulator and the quantum machine. By Lem. 27, for all sufficiently large |x| we have E[X] ≥ 3|x|/5. Therefore, by a Chernoff bound,   h i |x| b i) ̸= wi = Pr X ≤ Pr D(x, 2     1 ≤ Pr X ≤ 1 − E[X] 6   E[X] ≤ exp − 72   |x| ≤ exp − 120 = negl(|x|). which means

h i b i) = wi ≥ 1 − negl(|x|). Pr D(x,

This completes the proof of Lem. 28. We then give the final decision algorithm D∗ (x) for deciding the membership of the language L0 as follows: Algorithm 7.4: Final witness-recovering decider: D∗ (x)

D∗ (x) 1. For i ∈ [p(|x|)] b i). (a) wi ← output of D(x, 2. If there exists a prefix u of w (possibly u = w) such that (x, u) ∈ RL0 , output 1. Else output 0 We claim that the above algorithm D∗ (x) is a BQP decider for L0 . For those x ∈ / L0 There does not exist any w such that (x, w) ∈ RL0 by the definition of UP, thus the output of 79

D∗ (x) is always 0. Therefore, we conclude that D∗ (x) correctly decides membership in L0 , which is ∀x ∈ / L0 , Pr[D∗ (x) = 0] = 1 For those x ∈ L0 Notice that D∗ decides x only if the corresponding uniquen witness w satisfies (x, w) ∈ RL0 is recovered. Formally, for any fixed x ∈ L0 , we analyze the probability of the event that D∗ (x) outputs 1: Pr [D∗ (x) = 1] h i b ≥ Pr ∀i ∈ [p(|x|)], D(x, i) = wi h i b i) ̸= wi = 1 − Pr ∃i ∈ [p(|x|)], D(x, h i b i) ̸= wi ≥ 1 − p(|x|) Pr D(x, ≥ 1 − p(|x|) · negl(|x|)

(Union Bound) (Lem. 28)

≥ 1 − negl(|x|) for some negligible function negl(·). Thus, we conclude that D∗ (x) correctly decides membership in L0 . The above two cases imply that D∗ is a BQP decider for the language L0 , contradicting the assumption that L0 ∈ UP \ BQP. Therefore, for every fixed oracle-aided QPT machine D(·) , Pr[O ∈ GD ] < O

2 1 =1− . 3 3

It remains to check that LO satisfies the two structural conditions of Lem. 22. The language is decidable by an oracle Turing machine that always halts: on input (x, i, π), the machine can enumerate the polynomially bounded witnesses for L0 , check the relation, and run the NIZK verifier. Moreover, a fixed bit of the random oracle belongs to a fixed input-length component. The verifier on an instance x accesses only this component, and the index i and every well-formed proof π have polynomially bounded length; Hence, changing one oracle bit affects only finitely many strings in LO . We can now invoke Lem. 22 with ε = 1/3. It follows that, with probability 1 over the choice of O, no oracle-aided QPT machine decides LO on all inputs. Equivalently, Pr[LO ∈ / BQPO ] = 1. O

Finishing the proof of Thm. 4. Assume UP ⊈ BQP. By Sec. 7.4 and 7.5, the events LO ∈ NPO ∩ coNPO and LO ∈ / BQPO each have probability 1 over O ← O. It follows that   Pr NPO ∩ coNPO ⊈ BQPO = 1.

O←O

80

8

Black-Box Impossibility of Constructing Quantum-Hard NP ∩ coNP Problems

We next establish our main impossibility result. Theorem 5. There is no fully black-box quantum reduction of any (even worst-case) quantum-hard problem in NP ∩ coNP to post-quantum i O and post-quantum inj-OWFs. To prove Thm. 5, we follow the two-oracle paradigm introduced by Hsiao and Reyzin [HR04]. This paradigm rules out fully black-box constructions of a primitive Y from a primitive X by exhibiting two oracles: an oracle F that realizes X and an auxiliary oracle G that breaks the proposed construction of Y , while X remains secure even given access to both F and G. A fully black-box construction and its security reduction would yield a contradiction in this oracle world. We use the quantum formulation of this framework due to Hosoyamada and Yamakawa [HY20], in which quantum algorithms may have superposition access to both oracles. Our auxiliary oracle is a universal decision oracle for complementary verifier pairs. Importantly, it is required to decide only those pairs that remain complementary relative to every implementation of the source primitive under consideration. This is precisely the structure guaranteed by a fully black-box construction. We start by specifying necessary preliminaries (Sec. 8.1). We then show a warm-up case of separating injOWFs only, without considering i O (Sec. 8.2). In this warm-up, the base oracle is a family of random injective functions. We show that it remains one-way against quantum adversaries even in the presence of the quantum-accessible decision oracle. We then extend the oracle construction to incorporate i O (Sec. 8.3). 8.1

Black-Box Framework and Technical Tools

We first specify the oracle interfaces and the black-box model. We then define the decision oracle and establish the structural property that makes it possible to analyze its effect on source security. Finally, we give a quantum hybrid lemma that converts this structural property into a bound against superposition queries. 8.1.1

Oracle Access and the Black-Box Model

Throughout, a sampled classical oracle is a deterministic function. Quantum access to a classical function h means access to its unitary evaluation oracle Oh |k, v⟩ = |k, v ⊕ h(k)⟩ . When an oracle implements a randomized classical procedure, its randomness is supplied as an explicit input. In particular, an obfuscation oracle has the form i O(C, r), where r is the obfuscator’s random tape. Any randomness used to sample an oracle table is sampled once at the beginning of the experiment; the table is then held fixed throughout all queries. We use post-quantum i O for classical oracle-aided circuits. The adversary may make quantum oracle queries both before and after receiving the obfuscation. Definition 8 (Post-Quantum Indistinguishability Obfuscation). Let C = {Cn }n∈N be a class of classical oracle-aided circuits, where every C ∈ Cn has size n. Let Γ = {Γn }n∈N be an oracle distribution ensemble. In the experiments below, the oracle tuple is sampled from Γn and is held fixed throughout the experiment. A PPT algorithm i O is a post-quantum indistinguishability obfuscator for C relative to Γ if the following hold. 81

1. Functionality. For every n ∈ N and every C ∈ Cn , h i bΓ ≡ C Γ : C b ← i OΓ (1n , C) = 1. Pr C Γ,iO

2. Post-Quantum Indistinguishability. For every non-uniform QPT oracle-aided adversary A = (A1 , A2 ) that produces C0 , C1 ∈ Cn satisfying C0Γ ≡ C1Γ with probability one, h i 1 iO AdviO (n) = Pr Exp (n) = 1 − ≤ negl(n), Γ,iO,C,A Γ,iO,C,A 2 where ExpiO Γ,iO,C,A (n) is the experiment defined in Expr. 27. Experiment 27: Security for Post-Quantum iO

ExpiO Γ,iO,C,A (n) : 1. Sample the oracle tuple according to Γn . |Γ ⟩

2. (C0 , C1 , st) ← A1 (1n ). (The register st may contain quantum side information.) $

3. b ← − {0, 1}. b ← i OΓ (1n , Cb ). 4. C |Γ ⟩

b 5. b′ ← A2 (st, C). 6. Output 1 if b′ = b, and output 0 otherwise. We next formalize the black-box constructions ruled out by our result. The verifiers are classical, as required for an NP ∩ coNP language, whereas the security reduction may be quantum. The universal structure requirement below is essential: the same verifier pair must remain complementary for every functionally correct implementation of the source primitives. Definition 9 (Quantum Fully Black-Box Construction). A post-quantum fully black-box construction of a hard NP ∩ coNP problem from injOWFs and i O for a class C of classical circuits with injOWF-gates consists of two classical polynomial-time oracle-aided verifiers (V0 , V1 ) and a quantum oracle-aided reduction R satisfying the following conditions. In the efficient formulation, R is polynomial-time. For the quantitative formulation, we allow an otherwise inefficient reduction and bound relevant oracle-query complexity explicitly with parameters qR (n) and εR (n) below. 1. NP ∩ coNP Structure. Let S be the family of all oracle tuples (f, i O) satisfying the prescribed syntax and output-length bounds, such that f is injective and i O is a deterministic function b f ≡ C f for every C ∈ C, every random tape r, and of the circuit and its random tape with C (·) b C := i O(C, r). For every (f, i O) ∈ S and every input z, exactly one bit b ∈ {0, 1} satisfies ∃w : Vbf,iO (z, w) = 1. The witnesses have polynomially bounded length. Thus, defining membership by the verifier V1 , the pair (V0 , V1 ) defines a language Lf,iO ∈ NPf,iO ∩ coNPf,iO . 2. Quantum Black-Box Security Proof. There exist functions qR (·) ≥ 1 and εR (·) > 0 such that the following holds. (In the efficient formulation, qR (n) is polynomial and εR (n) is inversepolynomial.) Let Γ be any distribution over oracle tuples supported on S. For any quantum 82

oracle-aided adversary A that decides Lf,iO exactly in the worst case, namely, for every input z, h i Pr A|f ⟩,|iO⟩ (z) = b ∀z ∈ {0, 1}n , b ∈ {0, 1} s.t. ∃w : Vbf,iO (z, w) = 1 = 1, (f,iO)←Γ

the reduction breaks either f or i O. More precisely, for infinitely many n ∈ N, either h i Pr R|A⟩,|f ⟩,|iO⟩ (1n , f (x)) = x ≥ εR (n), (f,iO)←Γ $

x← −{0,1}n

or AdviO (n) ≥ εR (n). Γ,iO,C,R|A⟩ In both experiments, R makes at most qR (n) queries in total to its oracle interfaces. Moreover, for every computational-basis input z appearing in a query to A, every (f, i O) ∈ S, every witness w, and each b ∈ {0, 1}, the execution Vbf,iO (z, w) makes at most qR (n) oracle queries. The oracle interface supplied for a quantum adversary is part of the black-box model; the notation |A⟩ does not assert a canonical coherent implementation of an arbitrary quantum channel. For a deterministic classical adversary, we use its unitary function-evaluation interface. This is the only adversary interface needed for the decision-oracle attack below. Remark 3 (Role of the auxiliary quantitative formulation). Def. 9 includes both an efficient and a quantitative formulation. The efficient formulation is the standard quantum fully black-box notion and is the notion targeted by our main separation theorem. The quantitative formulation serves only as an auxiliary framework for proving this separation. Our quantitative results (e.g., Thm. 6 and Thm. 7) concern this auxiliary formulation under additional restrictions on the permitted queries, including bounds on evaluation-query lengths and on the resources of verifiers submitted to the decision oracle. These results exclude otherwise inefficient reductions with certain super-polynomial query bounds qR satisfying those restrictions. They do not rule out the quantitative formulation in general, nor do they establish lower bounds on bare oracle-query complexity for unrestricted inefficient reductions. These restricted quantitative results nevertheless suffice for our main goal: For every fixed efficient construction and reduction, we show that composition with our separating adversary satisfies all the additional resource restrictions for some polynomial bound p(n). Since this polynomial bound is eventually dominated by the superpolynomial bounds covered by our quantitative results, those results rule out the standard efficient formulation (e.g., see Corollaries 4 and 5). The inefficient formulation is therefore a tool for establishing the efficient separation, rather than a stronger notion that we claim to rule out in full generality. The corresponding definition for constructions from injOWFs alone is obtained by omitting the obfuscation oracle and the alternative of breaking iO. 8.1.2

The Universal Decision Oracle

We now define the auxiliary oracle that breaks a proposed NP ∩ coNP construction. Its validity test depends only on the oracle family S, rather than on the particular realized oracle. This universal validity requirement is what allows us to control how its answer changes when the realized oracle is modified. 83

Definition 10 ([BDV17, Definition 4.4]). For a family of classical oracles S and an oracle Ψ ∈ S, define the classical function DecideΨS as follows. Its input is a pair of classical oracle-aided verifier circuits (V0 , V1 ) and an input z. 1. Check that the circuits have compatible input formats and, for every Ψ ′ ∈ S and every input z ′ of their common input length, exactly one bit b ∈ {0, 1} satisfies ′

∃w : VbΨ (z ′ , w) = 1. If this condition fails, output ⊥. We call a verifier pair satisfying this condition valid relative to S. 2. Output the unique bit b ∈ {0, 1} for which ∃w : VbΨ (z, w) = 1. Malformed inputs are answered by ⊥. The oracle is defined only for realizations Ψ ∈ S. The definition specifies a function and imposes no computational bound on the validity test or the search for an accepting witness. We give quantum algorithms access to the reversible evaluation oracle of this function. If a fixed verifier pair remains complementary for every Ψ ′ ∈ S, then its associated language is decidable using one call to DecideΨS . In particular, this applies to every verifier pair satisfying the structure requirement of Def. 9. It does not apply to an arbitrary pair that is complementary only for the realized oracle Ψ , nor does it apply to verifiers that themselves query DecideΨS . To analyze source security, we distinguish the number of queries made by an adversary from the number made by the verifiers in a decision-oracle query. Definition 11 (Bounded Decision-Oracle Queries). A query Q = (V0 , V1 , z) is r-bounded relative to S if, for every Ψ ∈ S, every witness w, and each b ∈ {0, 1}, the execution VbΨ (z, w) makes at most r queries to Ψ . An adversary making at most T quantum queries to the base oracle and the decision oracle is required to have only r-bounded well-formed decision queries in its computational-basis query support, for every oracle realization under consideration. Malformed queries are allowed and receive the fixed answer ⊥. When T = r = q, we call such an adversary q-query. Although the decision oracle itself is computationally unbounded, its answer to a valid rbounded query is certified by at most r base-oracle answers. The following consequence of the NP ∩ coNP structure is the key property used in our analysis. Lemma 29 ([BDV17, Claim 4.6]). For every valid r-bounded query Q = (V0 , V1 , z) and every Ψ ∈ S, there is a set C = C(Ψ, V0 , V1 , z) of at most r classical oracle queries such that, for every Ψ ′ ∈ S, ′ Ψ |C = Ψ ′ |C =⇒ DecideΨS (Q) = DecideΨS (Q). Proof. We include the proof for completeness. Let b = DecideΨS (V0 , V1 , z), and fix an accepting witness w for VbΨ (z, w). Let C contain the oracle queries made in this verification. Since the query is r-bounded, |C| ≤ r. If Ψ ′ agrees with Ψ on C, the same verification follows the same execution and accepts relative to Ψ ′ . Since the verifier pair remains complementary for every oracle in S, the decision bit relative to Ψ ′ must also be b.

84

8.1.3

A Quantum Hybrid Bound for Coupled Oracles

The classical argument of [BDV17] bounds the probability that an adversary encounters a query on which two oracle realizations disagree. This reasoning does not directly apply to quantum adversaries, whose queries may be superpositions of many inputs: measuring a query to identify a differing point can disturb the computation. We instead establish a conditional-coupling lemma for the quantum oracle hybrid argument. If the probability of disagreement at every fixed input is at most γ, conditioned on the reference √ oracle, then any T -query quantum adversary has distinguishing advantage at most 2T γ. The proof follows the hybrid and projector method underlying [ARU14, Lemmas 35 and 37]. Combined with Lem. 29, this formulation lets us use classical pointwise disagreement bounds even when the adversary has superposition access to the decision oracle. We first recall the trace-distance estimate used in the proof. Throughout this section, TD denotes trace distance with the 12 ∥ · ∥1 convention. Lemma 30 ([Unr14, ARU14]). Let |Ψ0 ⟩ and |Ψ1 ⟩ be normalized quantum states that can be written as b ∈ {0, 1}, |Ψb ⟩ = |Ψb∗ ⟩ + |Φ∗ ⟩ , where both |Ψb∗ ⟩ are orthogonal to |Φ∗ ⟩. Then TD( |Ψ0 ⟩ , |Ψ1 ⟩) ≤ 2 ∥ |Ψ1∗ ⟩∥ . Lemma 31 (Quantum Queries to Coupled Oracle Distributions). Let γ ∈ [0, 1], and let Γ1 and Γ2 be distributions over classical functions from {0, 1}n to {0, 1}m . Suppose there is a joint distribution µ on pairs (f1 , f2 ) whose marginals are Γ1 and Γ2 , respectively, such that for every f2′ in the support of Γ2 and every z ∈ {0, 1}n ,   (34) Pr f1 (z) ̸= f2 (z) f2 = f2′ ≤ γ. (f1 ,f2 )←µ

Let A be a quantum oracle algorithm making at most T queries, whose initial state is independent of the sampled oracle pair. If ρf denotes its final state with oracle f , then E

(f1 ,f2 )←µ

√ [TD(ρf1 , ρf2 )] ≤ 2T γ.

In particular, if A outputs a bit, then √ Pr [A|f1 ⟩ = 1] − Pr [A|f2 ⟩ = 1] ≤ 2T γ.

f1 ←Γ1

f2 ←Γ2

Proof. We purify the algorithm’s initial state and intermediate operations, retaining any purification registers as part of its workspace. It suffices to prove the bound for these purified final states, since discarding registers cannot increase trace distance. Let A, K, V denote the workspace, query-input, and query-output registers, respectively. For a function f , write Of |a, k, v⟩AKV = |a, k, v ⊕ f (k)⟩AKV . Absorbing the initial oracle-independent computation into |Ψ 0 ⟩, let |Ψf0 ⟩ = |Ψ 0 ⟩ ,

|Ψfi ⟩ = Ui Of |Ψfi−1 ⟩ , 85

i ∈ {1, . . . , T },

where the Ui are oracle-independent unitaries. Algorithms making fewer queries can be padded with inactive query slots; the same argument applies to their active-query subspaces. Hybrid bound. For fixed (f1 , f2 ), define Dif1 ,f2 := TD( |Ψfi1 ⟩ , |Ψfi2 ⟩). By the triangle inequality and unitary invariance of trace distance,   i−1 Dif1 ,f2 = TD Of1 |Ψfi−1 ⟩ , O |Ψ ⟩ f2 f2 1   f1 ,f2 i−1 ≤ Di−1 + TD Of1 |Ψfi−1 ⟩ , O |Ψ ⟩ . f2 f2 2 Since D0f1 ,f2 = 0, it follows that DTf1 ,f2 ≤

T −1 X

TD Of1 |Ψfi2 ⟩ , Of2 |Ψfi2 ⟩ .

i=0

Projector bound. For z ∈ {0, 1}n , define Qz := IA ⊗ |z⟩ ⟨z|K ⊗ IV , and define the disagreement projector X Qf1 ,f2 = Qz . z: f1 (z)̸=f2 (z)

Fix i, and abbreviate Q = Qf1 ,f2 and |ψ⟩ = |Ψfi2 ⟩. The two states Of1 |ψ⟩ and Of2 |ψ⟩ have the common component |Φ∗ ⟩ = Of1 (I − Q) |ψ⟩ = Of2 (I − Q) |ψ⟩ . Their remaining components are |Ψb∗ ⟩ = Ofb Q |ψ⟩ ,

b ∈ {1, 2}.

Both oracle unitaries preserve the query-input register. Consequently, each |Ψb∗ ⟩ is orthogonal to |Φ∗ ⟩ and has norm ∥Q |ψ⟩ ∥. By Lem. 30,
TD Of1 |Ψfi2 ⟩ , Of2 |Ψfi2 ⟩ ≤ 2 Qf1 ,f2 |Ψfi2 ⟩ . Averaging over the coupling. Taking expectation over (f1 , f2 ) ← µ gives f ,f E[DT1 2 ] ≤ 2 µ

T −1 X i=0

h E µ

Qf1 ,f2 |Ψfi2 ⟩

i

.

(35)

By Jensen’s inequality, h E µ

Q

f1 ,f2

|Ψfi2 ⟩

i

r h i 2 ≤ E Qf1 ,f2 |Ψfi2 ⟩ . µ

The state |Ψfi2 ⟩ depends only on the reference oracle f2 . Since the projectors Qz are mutually orthogonal, " #   X 2 2 f1 ,f2 i i |Ψf2 ⟩ = E Qz |Ψf2 ⟩ Pr[f1 (z) ̸= f2 (z) | f2 ] E Q µ

f2 ←Γ2

µ

z

" ≤γ

E

f2 ←Γ2

X z

86

2 Qz |Ψfi2 ⟩

#

= γ, where the inequality uses Inequality (34). Substituting into Inequality (35), we obtain √ f ,f E[DT1 2 ] ≤ 2T γ. µ

Finally, for any fixed final measurement, the difference in the probability of an outcome is at most the trace distance. Since µ has marginals Γ1 and Γ2 , Pr [A|f1 ⟩ = 1] − Pr [A|f2 ⟩ = 1]

f1 ←Γ1

f2 ←Γ2

h

≤

E

(f1 ,f2 )←µ

i √ DTf1 ,f2 ≤ 2T γ.

This completes the proof of Lem. 31.

8.2

Warm-Up: Separation from injOWFs

This subsection serves as a warm-up for the Sec. 8.3 by demonstrating the main technical tool underlying our black-box separation. We construct an injective function oracle that remains oneway against quantum queries even in the presence of the universal decision oracle. Since the decision oracle decides every verifier pair arising from a fully black-box construction, this suffices to rule out such constructions from injOWFs alone. In the next subsection, we strengthen the result by incorporating i O. n m Notation. Let Im n denote the uniform distribution on all injective functions from {0, 1} to {0, 1} . In this subsection, S denotes the family of full oracle ensembles

f = {fk }k∈N ,

fk : {0, 1}k −→ {0, 1}k+1 ,

where each fk is injective. The random injOWF oracle is sampled by choosing independently fk ← Ik+1 k

for every k ∈ N.

We write f (z) = f|z| (z). For the security proof at input length n, we prove a stronger statement: all components f−n := {fk : k ̸= n} may be fixed arbitrarily, and only fn is sampled at random. This allows the adversary and the verifiers in its decision queries to access the entire oracle family, including input lengths other than n. The following Thm. 6 is the post-quantum analogue of the injOWF security statement in [BDV17, Theorem 4.8]. Its role in the separation is to establish source security in the two-oracle construction. The other requirement follows from the definition of DecidefS : every universally complementary verifier pair can be decided with one oracle query. We give the resulting black-box contradiction after the proof. Theorem 6. Fix n ∈ N, arbitrary injective components f−n , and integers T ≥ 0 and r ≥ 1. Let A be an otherwise computationally unbounded quantum oracle adversary making at most T queries 87

in total to f and DecidefS , with all well-formed decision-oracle queries r-bounded. The description and initial state of A are independent of the sampled component fn . Then r i h r |f ⟩,|DecidefS ⟩ (f (x)) = x ≤ 2(T + 1) A Pr . n n+1 2 fn ←In $ x← −{0,1}n In particular, if T, r ≤ q(n) = O(2n/6 ), the inversion probability is O(2−n/4 ). The same bounds hold when all components of f are sampled independently as above. Proof. Fix n, f−n , and A as in the theorem. The proof first samples a fresh value y outside Image(fn ) and plants it at a uniformly random input x ∈ {0, 1}n . The planted experiment has the same distribution as the real inversion experiment. We then remove the planting while keeping the challenge y. In the resulting experiment, y has no preimage under fn . Thus, a successful inverter distinguishes the two experiments by making one additional query to check its proposed preimage. The key structural ingredient is Lem. 29. For each fixed reference oracle f , every valid r-bounded decision query has a critical set of at most r inputs. Planting at a uniformly random n-bit input therefore changes the answer to any fixed decision query with probability at most r/2n . We apply Lem. 31 to the combined oracle (f, DecidefS ) to obtain a quantum distinguishing bound of 2(T + 1)

p r/2n .

Hybrid H0 . This is the real inversion experiment. The components f−n remain fixed throughout all hybrids. Experiment 28: Hybrid H0

1. fn ← In+1 n . $

2. x ← − {0, 1}n . f

3. Invoke A|f ⟩,|DecideS ⟩ (f (x)). The adversary wins if its output equals x. Hybrid H1 . We sample y uniformly outside Image(fn ) and plant it at a uniformly random input x. The resulting full oracle g agrees with f everywhere except at x. The difference from H0 is highlighted in red color. Experiment 29: Hybrid H1

1. fn ← In+1 n . $

2. x ← − {0, 1}n . $

3. y ← − {0, 1}n+1 \ Image(fn ). ( 4. Define the full oracle g by g(z) =

y if z = x, f (z) otherwise.

g

5. Invoke A|g⟩,|DecideS ⟩ (y). Again, the adversary wins if its output equals x. Since y ∈ / Image(fn ), the modified component gn is injective and g ∈ S. 88

Claim 25. The joint distributions of the base oracle, the planted point, and the challenge satisfy i.d.

(f, x, f (x)) in H0 == (g, x, y) in H1 . Consequently, the adversary’s winning probabilities in H0 and H1 are equal. Proof. For each fixed x, the modified function gn is uniformly distributed over In+1 n . Indeed, for any fixed injective gn , its challenge value must be y = gn (x), and its possible predecessors fn are obtained by replacing gn (x) with any value outside Image(gn ). There are exactly 2n such predecessors, each having the same sampling probability. Thus, gn is uniform and independent of the uniform point x. Since y = gn (x) and g−n = f−n , the stated joint distributions are identical. The decision oracle is determined by the full underlying oracle, so including it preserves this equality of distributions. This completes the proof of Claim 25.

Hybrid H2 . We remove the planting and give the adversary access to the reference oracle f , while keeping the challenge y outside Image(fn ). The difference from H1 is highlighted in red color. Experiment 30: Hybrid H2

1. fn ← In+1 n . $

2. x ← − {0, 1}n . $

3. y ← − {0, 1}n+1 \ Image(fn ). f

4. Invoke A|f ⟩,|DecideS ⟩ (y). To compare these hybrids, we turn the inverter into a bit-output distinguisher. Given a challenge y and access to an underlying oracle h and its decision oracle, define B as follows: h

1. Run A|h⟩,|DecideS ⟩ (y) and obtain an output a. 2. If a ∈ / {0, 1}n , output 0. 3. Query h(a) and output 1 if and only if h(a) = y. The algorithm B makes at most T + 1 oracle queries, and its decision-oracle queries remain rbounded. In the following claim, the subscripts H1 and H2 specify the sampling of the oracle and challenge in the corresponding hybrids. Claim 26. It holds that r h i h i r |g⟩,|DecidegS ⟩ |f ⟩,|DecidefS ⟩ Pr B (y) = 1 − Pr B (y) = 1 ≤ 2(T + 1) . H1 H2 2n Proof. We apply Lem. 31 to a tagged oracle combining the base oracle and the decision oracle. For every h ∈ S, define Feh (0, z) = h(z), Feh (1, Q) = DecidehS (Q), where Q = (V0 , V1 , z) is an r-bounded query. Malformed inputs receive the fixed answer ⊥. Encodings of non-r-bounded decision queries can also be assigned ⊥ when extending Feh to a total function, since they never occur in the query support of the algorithms under consideration. For each fixed input length, the querying algorithm has finite query registers. We pad all relevant encodings and answers to fixed lengths. Thus Feh can be viewed as a classical function on a finite 89

fixed-length domain, and access to the two oracle interfaces is simulated by access to Feh without increasing the number of queries. Conditioning on the challenge. Fix y ∈ {0, 1}n+1 . Since every injective fn has exactly 2n values outside its image, the conditional distribution of fn given the challenge y is fn ← In+1 |y∈ / Image(fn ). n The point x remains uniform and independent of f under this conditioning. Let Γ1,y and Γ2,y be the corresponding distributions of merged oracles: $

Γ1,y :

fn ← In+1 |y∈ / Image(fn ), n g = fx→y , output Feg ;

x← − {0, 1}n ,

Γ2,y :

fn ← In+1 |y∈ / Image(fn ), n

output Fef .

Here f−n is the fixed collection of components from the theorem statement, and fx→y changes only the value at x. We couple these distributions by sampling the same f and a uniform x and outputting (Feg , Fef ), g = fx→y . Pointwise disagreement. Fix the full reference oracle f in the support of the conditional distribution, and fix a merged-oracle input w. We claim that h i r Pr Feg (w) ̸= Fef (w) ≤ n . (36) $ 2 n x← −{0,1} There are three cases. – If w = (0, z) is a direct query to the base oracle and |z| = n, then Pr[g(z) ̸= f (z)] = Pr[x = z] = 2−n ≤ r2−n . x

x

If |z| ̸= n, the disagreement probability is zero. – If w = (1, Q) is an r-bounded decision query whose verifier pair is invalid relative to S, both answers are ⊥. Indeed, the validity test depends only on the verifier pair and the family S, not on the realized oracle. Malformed inputs likewise have disagreement probability zero. – Suppose w = (1, Q) is a valid r-bounded query, where Q = (V0 , V1 , z). Let CQ = C(f, V0 , V1 , z) be the critical set from Lem. 29. Then |CQ | ≤ r. Since g ∈ S and f and g differ only at x, the condition x ∈ / CQ implies DecidefS (Q) = DecidegS (Q). Consequently, h i |CQ ∩ {0, 1}n | r Pr DecidefS (Q) ̸= DecidegS (Q) ≤ Pr[x ∈ CQ ] = ≤ n. n x x 2 2 Inputs outside the allowed query domain have a fixed answer in both merged oracles and hence also have disagreement probability zero. This proves Inequality (36). The estimate holds for every fixed full reference oracle f . Since Fef is a deterministic function of f , averaging over reference oracles with the same merged-oracle realization gives the same estimate conditioned on Fef . Thus the coupling satisfies the hypothesis of Lem. 31 with γ = min{1, r2−n }. 90

Applying the quantum hybrid bound. Let By be the algorithm obtained by hardwiring y as the challenge input to B and routing its queries through the merged oracle. It makes at most T + 1 queries. By Lem. 31, Pr

|Fe ⟩ [By g = 1] −

Feg ←Γ1,y

Pr

|Fe ⟩ [By f = 1]

√

≤ 2(T + 1) γ ≤ 2(T + 1)

Fef ←Γ2,y

r

r . 2n

Finally, the challenge has the same uniform marginal distribution in both hybrids. For every fixed y ∈ {0, 1}n+1 , Pr[y is the sampled challenge] =

Prfn [y ∈ / Image(fn )] 1/2 = n = 2−(n+1) . 2n 2

Averaging the preceding bound over y completes the proof of Claim 26.

Completing the proof of Thm. 6. In H1 , the function gn is injective and gn (x) = y. Therefore, h i g Pr B |g⟩,|DecideS ⟩ (y) = 1 = Pr[H1 wins]. H1

In H2 , the challenge y is outside Image(fn ), and B rejects every output outside {0, 1}n . Hence h i f Pr B |f ⟩,|DecideS ⟩ (y) = 1 = 0. H2

Combining Claims 25 and 26, we obtain r r Pr[H0 wins] = Pr[H1 wins] ≤ 2(T + 1) . 2n The probability is also at most 1, proving the quantitative bound. If T, r ≤ q(n) = O(2n/6 ), then r 2(T + 1)

r r q(n) ≤ 2(q(n) + 1) = O(2−n/4 ). 2n 2n

The bound holds uniformly over the fixed components f−n , so averaging over independently sampled components gives the same result for the full random oracle ensemble. This completes the proof of Thm. 6.

Consequence for black-box constructions. We now relate the security theorem to the goal of this subsection. Corollary 4. There is no fully black-box quantum construction of a worst-case quantum-hard language in NP ∩ coNP from post-quantum injOWFs, in the sense of the injOWF-only version of Def. 9. 91

Proof. Suppose such a construction (V0 , V1 , R) exists. Instantiate its source oracle by the random injective family f defined above. By the structure requirement, (V0 , V1 ) remains complementary for every f ∈ S. Thus an adversary can decide the constructed language exactly by submitting the corresponding verifier circuits and input to DecidefS . For each input length, the polynomial-time verifier machines are compiled into classical oracle-aided circuits. The resulting decision procedure has a unitary implementation using the decision oracle, so it also supplies the coherent interface needed by the quantum reduction. Replace every call by R to this adversary with its decision-oracle implementation. The resulting inverter makes polynomially many queries to f and DecidefS , and every decision-oracle query contains verifiers making polynomially many base-oracle queries. By Thm. 6, its inversion probability is O(2−n/4 ). On the other hand, the black-box security requirement gives inverse-polynomial inversion probability for infinitely many input lengths, since the adversary decides the constructed language exactly. This is a contradiction. This completes the proof of Corollary 4.

8.3

Separation from i O and injOWFs

We now extend the warm-up construction to include i O. Following [BDV17], we augment the injective function oracle with an injective encoding oracle and an evaluation oracle. We show that both source primitives remain secure against quantum adversaries with access to the universal decision oracle. We first specify the oracle family and the resource bounds used in the security analysis. We then prove one-wayness by a coherent simulation using the warm-up construction, and prove obfuscation security by a sequence of coupled-oracle hybrids. Finally, we show that every efficient fully black-box reduction induces an adversary satisfying these resource bounds for some polynomial parameter. The quantitative bounds below concern a resource model that controls evaluation-query lengths as well as oracle-query counts. They do not assert a lower bound on bare oracle-query complexity for unrestricted inefficient reductions. 8.3.1

Oracle Construction and Resource Bounds

Oracle setting. We use full oracle families indexed by all input lengths. As in the warm-up, let f = {fk }k∈N ,

fk : {0, 1}k −→ {0, 1}k+1 ,

where each fk is injective. Let O = {Ok }k∈N ,

Ok : {0, 1}2k −→ {0, 1}5k ,

where each Ok is injective. We parse an input to Ok as a pair (C, r) ∈ {0, 1}k × {0, 1}k . We fix a padded circuit-description convention under which a k-bit description specifies a classical circuit with f -gates and at most k oracle queries on every input. Malformed circuit descriptions denote a fixed zero circuit with the prescribed interface. Incompatible evaluation inputs receive ⊥. These conventions make circuit evaluation a total function and apply equally to circuits encoded by O and to the backup circuits defined below. A backup map is a family φ = {φk }k∈N ,

φk : {0, 1}5k −→ {0, 1}k . 92

b ∈ {0, 1}5k , define For C ( b Evalf,O φ (C, z) =

C f (z)

b for some (C, r), if Ok (C, r) = C

b f (z) φk (C)

b∈ if C / Image(Ok ).

Injectivity of Ok makes the first case unambiguous. Malformed oracle inputs receive ⊥. Write
Ψ (f, O, φ) := f, O, Evalf,O , Ψφ = Ψ (f, O, φ). φ The underlying oracle family is   fk : {0, 1}k → {0, 1}k+1 is injective for every k,   SΨ := Ψ (f, O, φ) : Ok : {0, 1}2k → {0, 1}5k is injective for every k, .   φk : {0, 1}5k → {0, 1}k is arbitrary for every k In particular, SΨ ranges over all backup maps, even when a security experiment fixes one particular φ. We use this same family in the validity test of DecideSΨ throughout every experiment and hybrid. For a fixed backup map φ, the random oracle realization is obtained by sampling independently fk ← Ik+1 k ,

Ok ← I5k 2k

for every k ∈ N.

All sampled tables remain fixed throughout the experiment. Define the augmented oracle tuple   Ψ (f,O,φ) , Γ (f, O, φ) := f, O, Evalf,O φ , DecideSΨ and let Γφ denote its distribution under this sampling. Obfuscation and the implementation interface. On input a circuit description C ∈ {0, 1}n , $ b = On (C, r), and returns the canonical oracle-aided the obfuscator samples r ← − {0, 1}n , computes C Ψφ b z). We denote this obfuscator by i O. For every wrapper E b that evaluates E (z) = Evalf,O (C, C

b C

φ

Ψ

realization in SΨ , every circuit C, and every random tape r, EOnφ(C,r) ≡ C f . Thus functionality holds for every admissible implementation, not only with high probability over the sampled tables. The input circuit has only f -gates, whereas the returned wrapper has an Eval-gate. Accordingly, returned programs execute relative to the ambient oracle tuple. This is the implementation convention used when applying the black-box framework in this subsection: calls to obfuscation and executions of returned programs are compiled into calls to O and Eval, respectively. It is not a claim that ECb is an f -only circuit. b and parsed The wrapper has size polynomial in n, and its description can be constructed from C b b to recover C. Hence giving the adversary C in the security experiment is equivalent to giving it the canonical wrapper ECb . Reprogramming notation. For a fixed r ∈ {0, 1}n , write T = (∗, r) := {(C, r) : C ∈ {0, 1}n }, ordered lexicographically by C. If D is an ordered tuple of 2n distinct elements of {0, 1}5n , then OT 7→D maps each element of T to the corresponding entry of D and agrees with O elsewhere. Sampling an ordered subset means sampling uniformly without replacement, including a uniformly random ordering. Similarly, O(C,r)7→Cb changes only the value at (C, r), and φC7b→C changes only the backup circuit b All these modifications leave components at other lengths unchanged. assigned to C. 93

Resource bounds. Unlike the warm-up in Sec. 8.2, a single evaluation query can invoke a circuit containing many f -gates. We therefore bound the lengths of evaluation encodings in addition to the number of external oracle queries. Definition 12 (Resource-Bounded Queries). Let q ≥ 1. In this subsection, a quantum adversary with access to Γ (f, O, φ) is q-query if it satisfies the following conditions. 1. Direct function queries. It makes at most q queries to f . 2. Encoding and evaluation queries. It makes at most q queries in total to O and Eval. Every b z) has |C| b ≤ 5q. Thus the selected circuit, whether recovered well-formed evaluation query (C, from O or supplied by φ, makes at most q queries to f . 3. Decision queries. It makes at most q queries to DecideSΨ . For every well-formed query (V0 , V1 , z), every Ψ ∈ SΨ , every witness w, and each b ∈ {0, 1}, the execution VbΨ (z, w) satisfies the first two conditions above. The verifiers have access only to Ψ , not to the decision oracle. For quantum queries, the restrictions apply to every computational-basis query in the support of the query state, including in the hybrid executions used below. Malformed queries are allowed and receive ⊥. For a two-stage adversary, the query bounds apply to the two stages combined. Thus a q-query adversary makes at most 3q queries to the augmented tuple. Each verifier in a decision query makes at most 2q queries to the underlying tuple Ψ . Consequently, Lem. 29 supplies a critical set of size at most 2q for every valid decision query. The adversaries considered below may otherwise be computationally unbounded. Their descriptions and initial states are independent of the sampled oracle component, apart from information obtained through the stated experiment. 8.3.2

One-Wayness in the Presence of the Augmented Oracle

We first show that access to the encoding, evaluation, and decision interfaces does not destroy one-wayness. The proof fixes O and φ and simulates their interfaces using the warm-up oracle. The simulation must preserve the validity test of the full decision oracle, including on invalid verifier pairs. Theorem 7. Fix n ∈ N, an integer q ≥ 1, a backup map φ, an injective encoding family O, and arbitrary injective components f−n . Let A be a q-query quantum adversary whose description and initial state are independent of fn . Then h i   Pr A|Γ (f,O,φ)⟩ (fn (x)) = x ≤ O q 3 2−n/2 . fn ←In+1 n $

x← −{0,1}n

In particular, if q(n) = O(2n/12 ), the inversion probability is O(2−n/4 ). The same bounds hold when all components of f and O are sampled independently as above, with φ fixed. Proof. Fix n, q, φ, O, f−n , and A as in the theorem. Let Sf denote the injective-function family |f ⟩,|Decidef ⟩

Sf from Sec. 8.2. We construct a quantum adversary B that perfectly simulates A|Γ (f,O,φ)⟩ . 2 The simulator makes O(q ) queries in total, and each translated decision query is O(q 2 )-bounded relative to Sf . Applying Thm. 6 with these two bounds gives the result.

94

Fixed tables and oracle-independent computation. At the fixed security parameter, all query registers have finite length. The relevant portions of O, its inverse, and φ can therefore be hardwired into a finite simulation circuit. This circuit may be inefficient, as permitted by the query model, but its description is independent of the sampled component fn . The same observation applies to the predicate ValidSΨ (V0 , V1 ) from Def. 10. On the finite set of verifier descriptions that fit in the query registers, this predicate has a finite truth table. We hardwire that table and evaluate it reversibly without queries to f . This does not require an efficient or uniform algorithm for deciding universal validity. Simulation of the base interfaces. Given the challenge y = fn (x), the simulator runs A(y) and answers its queries as follows. 1. f -queries. The simulator forwards the query to its own f oracle. 2. O-queries. The simulator answers using the fixed encoding tables. This requires no queries to f. b z), the simulator determines the circuit 3. Eval-queries. On input (C, (
b b ∈ Image(O), π1 O−1 (C) if C C= b φ(C) otherwise. It then evaluates C f (z). By the evaluation-length restriction, this circuit makes at most q queries to f . To implement the oracle response coherently, the simulator reversibly selects C, evaluates it while retaining the computation history, XORs the result into the answer register, and reverses the evaluation and selection. All workspace is restored to zero. The resulting map is b z, v⟩ |0⟩ 7−→ |C, b z, v ⊕ Evalf,O b |C, φ (C, z)⟩ |0⟩ . This costs O(q) queries to f per evaluation query, including uncomputation. The same construction handles superpositions of different query inputs. Controlled routing between interfaces incurs at most constant-factor query overhead. Simulation of the decision interface. For a well-formed query Q = (V0 , V1 , z), the simulator first reversibly computes ValidSΨ (V0 , V1 ). If the pair is invalid, it returns ⊥. Suppose the pair is valid. The simulator compiles each Vb into an f -aided verifier Db by replacing its O- and Eval-queries with the classical simulations described above. For every f ′ ∈ Sf , every input z ′ , and every witness w, ′

Ψ (f ′ ,O,φ)

Dbf (z ′ , w) = Vb

(z ′ , w).

Since Ψ (f ′ , O, φ) ∈ SΨ and (V0 , V1 ) is valid relative to SΨ , the pair (D0 , D1 ) is valid relative to Sf . Therefore, Ψ (f,O,φ)

DecidefSf (D0 , D1 , z) = DecideSΨ

(V0 , V1 , z).

The original validity test is essential here. An invalid pair relative to SΨ can become valid after O and φ are fixed. Querying the translated pair without first checking its original validity would therefore not simulate the full decision oracle. The translation of a valid query is computed reversibly while retaining the original query. The simulator evaluates the translated decision oracle into the answer register and then uncomputes the 95

translation and validity flag. For invalid or malformed queries, it instead returns the fixed answer ⊥ and cleans its workspace. Thus this simulation implements the exact unitary function-evaluation interface, including on superpositions of valid and invalid queries. Query accounting. The simulator forwards at most q direct f -queries and simulates at most q evaluation queries, each at cost O(q). It also makes O(q) queries to DecidefSf . Hence its total query count satisfies TB = O(q 2 ). For a translated verifier Db , the direct f -queries contribute at most q, and the simulated evaluation queries contribute at most q 2 . Thus every translated decision query is rB -bounded for rB = O(q 2 ). This bound holds for every f ′ ∈ Sf and every witness on the submitted input. The verifier’s internal queries are not additional queries made by B; they enter the warm-up theorem through the separate parameter rB . Applying the warm-up theorem. The simulation is exact and its initial state is independent of fn . By Thm. 6,   h i |f ⟩,|DecidefS ⟩ |Γ (f,O,φ)⟩ f (fn (x)) = x Pr A (fn (x)) = x = Pr B r rB ≤ 2(TB + 1) 2n   = O q 3 2−n/2 . $

Here the probabilities average over fn ← In+1 and x ← − {0, 1}n . n n/12 −n/4 For q(n) = O(2 ), the last expression is O(2 ). The estimate is uniform over the fixed choices of f−n and O, so averaging over their independent sampling gives the same bound for the full random oracle ensemble. This completes the proof of Thm. 7.

8.3.3

Obfuscation Security in the Presence of the Augmented Oracle

We next prove post-quantum obfuscation security. The proof follows the row-reprogramming hybrids of [BDV17], using Lem. 31 to control quantum queries. The first reprogramming hides all encodings using a random tape r during the pre-challenge phase. This allows us to replace the challenge encoding by a fresh value without changing the joint distribution of the challenge, post-challenge oracle, and residual quantum state. We then restore the original pre-challenge oracle. Finally, we replace the challenge encoding by a backup evaluation of C0 . Functional equivalence of C0 and C1 makes the resulting experiment independent of the challenge bit. Theorem 8. Fix n ∈ N, an integer q ≥ 1, a backup map φ, an injective family f , and injective encoding components O−n . Sample On ← I5n 2n . Let A = (A1 , A2 ) be a q-query quantum adversary whose description and initial state are independent of On . In the real experiment, A1 outputs equalsize circuit descriptions C0 , C1 ∈ {0, 1}n satisfying C0f ≡ C1f with probability one. Then, it hold that h i 1   Pr ExpiO (n) = 1 − ≤ O q 3/2 2−n/2 . 2 The experiment uses the augmented oracle Γ (f, O, φ) and the obfuscator i O. In particular, for q(n) = O(2n/6 ), the advantage is O(2−n/4 ). Averaging over independently sampled f and O−n gives the same bound for AdviO Γφ ,iO,C,A (n). 96

Proof. Fix n, q, φ, f, O−n , and A as in the theorem. Only On is sampled in the experiments below. We write Image(On ) explicitly when referring to the component being modified. Merged-oracle notation. For fixed f , define the tagged classical function GO,φ (0, z) := f (z), GO,φ (1, (C, r)) := O(C, r), b z)) := Evalf,O b GO,φ (2, (C, φ (C, z), Ψ (f,O,φ)

GO,φ (3, Q) := DecideSΨ

(Q).

For the fixed query-register lengths, we pad encodings and answers to obtain a function on a finite fixed-length domain. Malformed queries receive ⊥. Inputs outside the resource-bounded domain may also be assigned ⊥, since they never occur in the executions under consideration. Access to the four interfaces is thereby represented by at most 3q queries to GO,φ . All comparisons below use the same family SΨ in the decision-oracle validity test. Hybrid H0 . This is the real obfuscation experiment. Experiment 31: Hybrid H0

1. On ← I5n 2n . $

$

2. b ← − {0, 1} and r ← − {0, 1}n . |Γ (f,O,φ)⟩

3. (C0 , C1 , st) ← A1

(1n ).

b ← On (Cb , r). 4. C |Γ (f,O,φ)⟩

5. b′ ← A2

b (st, C).

6. Output 1 if b′ = b, and output 0 otherwise. The register st may contain quantum side information. We say that a hybrid wins when its output is 1. Hybrid H1 . We change only the pre-challenge oracle. For a uniformly random tape r, we replace the entire row T = (∗, r) by fresh encodings D. The challenge and post-challenge oracle still use the original table O. Its difference from H0 is highlighted in red color. Experiment 32: Hybrid H1

1. On ← I5n 2n . $

$

2. b ← − {0, 1} and r ← − {0, 1}n . 3. Sample D uniformly as an ordered subset of size 2n of {0, 1}5n \ Image(On ). 4. Set T = (∗, r). |Γ (f,OT 7→D ,φ)⟩

5. (C0 , C1 , st) ← A1

(1n ).

b ← On (Cb , r). 6. C |Γ (f,O,φ)⟩

7. b′ ← A2

b (st, C).

8. Output 1 if b′ = b, and output 0 otherwise. We first establish the pointwise estimate needed to compare the pre-challenge states. This is the quantum-hybrid input corresponding to [BDV17, Claim 4.18]. 97

Lemma 32 (Row-Reprogramming Disagreement). Fix a full reference encoding family O. $

Sample r ← − {0, 1}n and an ordered subset D as in H1 , and let T = (∗, r). For every fixed allowed merged-oracle input w, Pr [GOT 7→D ,φ (w) ̸= GO,φ (w)] ≤ 4q 2−n . r,D

Proof. Fix w. Since D consists of distinct values outside Image(On ), the modified encoding oracle remains injective. Both underlying tuples therefore belong to SΨ . We consider the four query types. 1. Queries to f . The function family is unchanged, so the disagreement probability is zero. 2. Queries to O. A query at a length other than n is unchanged. At length n, a fixed input (C, s) changes only if s = r. Hence its disagreement probability is at most 2−n . 3. Queries to Eval. An evaluation query whose encoding has length other than 5n is unchanged. e belongs to On (T ) or to D. At length 5n, its answer can change only if its encoding C e has at most one preimage under On , so By injectivity, a fixed C e ∈ On (T )] ≤ 2−n . Pr[C r

Also, e ∈ D] ≤ Pr[C D

2n ≤ 21−4n . 25n − 22n

Thus the disagreement probability is at most 2−n + 21−4n ≤ 21−n . 4. Queries to Decide. If the verifier pair is invalid relative to SΨ , both answers are ⊥. Otherwise, let
CQ = C Ψ (f, O, φ), V0 , V1 , z be the reference critical set from Lem. 29. By Def. 12, |CQ | ≤ 2q. If the two underlying tuples agree on CQ , their decision answers agree. A union bound using the preceding direct-query estimates gives h i Ψ (f,O ,φ) Ψ (f,O,φ) Pr DecideSΨ T 7→D (Q) ̸= DecideSΨ (Q)

r,D

≤ |CQ | 21−n ≤ 4q 2−n . Malformed inputs and inputs outside the allowed domain have the same fixed answer in both oracles. This completes the proof of Lem. 32. For subsequent comparisons, set √ ∆pre := 6q γpre .

γpre := 4q 2−n , Claim 27. It holds that

|Pr[H1 wins] − Pr[H0 wins]| ≤ ∆pre . 98

Proof. Fix the full reference oracle O, in addition to the already fixed f and φ. Couple the prechallenge oracles by sampling (r, D) as in H1 and taking (F1 , F2 ) = (GOT 7→D ,φ , GO,φ ) . The reference oracle F2 is fixed. By Lem. 32, this coupling satisfies the conditional disagreement hypothesis of Lem. 31 with γ = γpre . Let ρr,D denote the complete classical–quantum output state of A1 under the modified oracle, including C0 , C1 and its residual state. Let ρref denote the corresponding state under the reference oracle. Since A1 makes at most 3q merged-oracle queries, Lem. 31 gives √ E [TD(ρr,D , ρref )] ≤ 6q γpre = ∆pre .

r,D

For each fixed (r, D, b), challenge generation and the execution of A2 form the same channel in the two experiments: the challenge is On (Cb , r) and the post-challenge oracle is Γ (f, O, φ). Contractivity of trace distance therefore bounds the difference in winning probabilities for this continuation by TD(ρr,D , ρref ). Averaging over (r, D, b) and then over On proves the claim. The expected trace-distance conclusion is important here. The continuation depends on r, so closeness of only the averaged pre-challenge states would not suffice. This completes the proof of Claim 27. Hybrid H2 . We keep the reprogrammed pre-challenge oracle, but replace the challenge by a fresh encoding and reprogram its post-challenge entry accordingly. Its difference from H1 is highlighted in red color. Experiment 33: Hybrid H2

1. On ← I5n 2n . $

$

2. b ← − {0, 1} and r ← − {0, 1}n . 3. Sample D uniformly as an ordered subset of size 2n of {0, 1}5n \ Image(On ). 4. Set T = (∗, r). |Γ (f,OT 7→D ,φ)⟩

(1n ).
$ b← 6. C − {0, 1}5n \ Image(On ) ∪ D . 5. (C0 , C1 , st) ← A1

|Γ (f,O(C ,r)7→Cb ,φ)⟩

7. b′ ← A2

b

b (st, C).

8. Output 1 if b′ = b, and output 0 otherwise. In set expressions involving D, we identify the ordered tuple with its underlying set. Claim 28. The joint distributions of the challenge bit, the pre-challenge output state, the challenge, and the post-challenge oracle are identical in H1 and H2 . Consequently, Pr[H1 wins] = Pr[H2 wins]. Proof. Condition first on f, φ, O−n , b, r, D, OT 7→D .

(37)

These variables determine the entire oracle supplied to A1 . Its classical outputs and conditional residual density operator are therefore independent of the erased values On |T . 99

Condition further on the classical outputs C0 , C1 , and write u = (Cb , r) ∈ T . Fix all entries On (v) for v ̸= u, and define
V := {0, 1}5n \ {On (v) : v ∈ {0, 1}2n , v ̸= u} ∪ D . Under the original sampling, the remaining entry On (u) is uniform over V . Indeed, every injective completion compatible with the conditioned data has the same probability: On is uniform, and the number of possible ordered choices of D outside its image depends only on the image size. b = On (u) and is therefore uniform over V . In H2 , first a = On (u) is In H1 , the challenge is C b uniform over V , and then C is uniform over V \ {a}. For every h ∈ V , X 1 1 1 b = h] = = . Pr[C H2 |V | |V | − 1 |V | a∈V \{h}

Thus the challenge is uniform over V in both hybrids. In either experiment, the post-challenge encoding oracle agrees with the fixed table away from b Its evaluation and decision interfaces are determined by this table, the fixed u and maps u to C. f, φ, and the fixed family SΨ . The conditional residual state of A1 is the same and independent of the hidden entry a. Hence the relevant joint classical–quantum distributions are identical. Averaging over the conditioned variables completes the proof of Claim 28.

Hybrid H3 . We restore the original pre-challenge oracle. The challenge sampling and post-challenge reprogramming remain unchanged. Its difference from H2 is highlighted in red color. Experiment 34: Hybrid H3

1. On ← I5n 2n . $

$

2. b ← − {0, 1} and r ← − {0, 1}n . 3. Sample D uniformly as an ordered subset of size 2n of {0, 1}5n \ Image(On ). |Γ (f,O,φ)⟩

4. (C0 , C1 , st) ← A1

(1n ).

$ b← 5. C − {0, 1}5n \ Image(On ) ∪ D . |Γ (f,O(C ,r)7→Cb ,φ)⟩

6. b′ ← A2

b

b (st, C).

7. Output 1 if b′ = b, and output 0 otherwise. Claim 29. It holds that |Pr[H3 wins] − Pr[H2 wins]| ≤ ∆pre . Proof. Fix the full reference oracle O. The pre-challenge states are exactly ρr,D and ρref from the proof of Claim 27. Hence E [TD(ρr,D , ρref )] ≤ ∆pre . r,D

b uniformly outFor each fixed (r, D, b), both experiments use the same continuation: sample C side Image(On ) ∪ D, and run A2 with oracle Γ (f, O(Cb ,r)7→Cb , φ). This is a common channel on the complete pre-challenge output state, including the classical circuit descriptions. Contractivity followed by averaging over (r, D, b) and On proves the claim. This completes the proof of Claim 29.

100

Hybrid H4 . We remove the post-challenge encoding reprogramming. Instead, we set the backup b to C0 . Since C b is outside the image of On , the challenge evaluates to C f in this circuit at C 0 experiment. Its difference from H3 is highlighted in red color. Experiment 35: Hybrid H4

1. On ← I5n 2n . $

$

2. b ← − {0, 1} and r ← − {0, 1}n . 3. Sample D uniformly as an ordered subset of size 2n of {0, 1}5n \ Image(On ). |Γ (f,O,φ)⟩

4. (C0 , C1 , st) ← A1

(1n ).

$ b← 5. C − {0, 1}5n \ Image(On ) ∪ D . |Γ (f,O,φC7 b →C )⟩

6. b′ ← A2

0

b (st, C).

7. Output 1 if b′ = b, and output 0 otherwise. The next estimate corresponds to [BDV17, Claim 4.22]. Its reference oracle uses the modified backup map, which is why SΨ must include all backup maps. Lemma 33 (Challenge-Reprogramming Disagreement). Fix f, O, φ, a bit b, circuits C0 , C1 ∈ {0, 1}n with C0f ≡ C1f , and b ∈ {0, 1}5n \ Image(On ). C For every fixed allowed merged-oracle input w, h i Pr GO(C ,r)7→Cb ,φ (w) ̸= GO,φC7b →C (w) ≤ 2q 2−n . 0 b $ r← −{0,1}n Proof. Define the reference tuple Ψ2 := Ψ (f, O, φC7b→C0 ) and, for each r ∈ {0, 1}n , define (r)

Ψ1

:= Ψ (f, O(C ,r)7→Cb , φ). b

b∈ The reference tuple belongs to SΨ because the family permits arbitrary backup maps. Since C / (r) Image(On ), the reprogrammed encoding oracle remains injective, so Ψ1 ∈ SΨ for every r. Fix w and consider its query type. 1. Queries to f . Both tuples use the same f , so the disagreement probability is zero. 2. Queries to O. At length n, a fixed input (C, s) changes only if (C, s) = (Cb , r). Its disagreement probability is therefore at most 2−n . Other lengths are unchanged. b the first tuple returns C f (z) and the reference 3. Queries to Eval. At the challenge encoding C, tuple returns C0f (z). These answers agree because C0f ≡ C1f . e the evaluation answers can differ only if At any other encoding C,

b

e = On (Cb , r). C e equals this This is the encoding removed by the reprogramming. Injectivity implies that a fixed C value for at most one choice of r. Thus every fixed evaluation query has disagreement probability at most 2−n . Encodings at other lengths are unchanged. 101

4. Queries to Decide. Invalid verifier pairs receive ⊥ in both tuples. For a valid query Q = (V0 , V1 , z), choose the critical set at the reference tuple, CQ = C(Ψ2 , V0 , V1 , z). This set is independent of r and has size at most 2q. By Lem. 29, disagreement of the decision answers requires disagreement at some point of CQ . Hence   (r) X Ψ1 (r) Ψ2 Pr DecideSΨ (Q) ̸= DecideSΨ (Q) ≤ Pr[Ψ1 (u) ̸= Ψ2 (u)] r

u∈CQ

r

≤ |CQ | 2−n ≤ 2q 2−n . Malformed inputs and inputs outside the allowed domain again have disagreement probability zero. This completes the proof of Lem. 33. Set

√ ∆post := 6q γpost .

γpost := 2q 2−n , Claim 30. It holds that

|Pr[H4 wins] − Pr[H3 wins]| ≤ ∆post . Proof. The pre-challenge oracle is the original oracle in both experiments. Condition on the classical data b f, O, φ, b, D, C0 , C1 , C, and let ρst denote the resulting conditional residual density operator. b and the entire pre-challenge execution, are independent of r. ConThe sampling of D and C, sequently, after this conditioning, r remains uniform over {0, 1}n and ρst is independent of r. Moreover, admissibility in the real experiment implies C0f ≡ C1f with probability one here, since the pre-challenge execution uses the same original oracle. Couple the post-challenge merged oracles by sampling this uniform r and taking   (F1 , F2 ) = GO(C ,r)7→Cb ,φ , GO,φC7b →C . b

0

The reference oracle F2 is fixed under the conditioning. By Lem. 33, the coupling satisfies the hypothesis of Lem. 31 with γ = γpost . b ⟨C|. b This state is independent of the sampled Apply that lemma to A2 with initial state ρst ⊗ |C⟩ oracle pair. Since A2 makes at most 3q merged-oracle queries, the difference in its probability of √ outputting the fixed bit b is at most 6q γpost = ∆post . Averaging over the common distribution of the conditioned classical data proves the claim. This completes the proof of Claim 30. Completing the proof of Thm. 8. In H4 , the pre-challenge state, challenge, and post-challenge oracle are all independent of b. The decision-oracle validity predicate also uses the same fixed family SΨ , independently of b. Thus 1 Pr[H4 wins] = . 2 Combining Claims 27 to 30, we obtain Pr[H0 wins] −

1 ≤ 2∆pre + ∆post 2 102

p p ≤ 12q 4q 2−n + 6q 2q 2−n   = O q 3/2 2−n/2 . For q(n) = O(2n/6 ), this is O(2−n/4 ). The bound is uniform over the fixed f and O−n . Averaging over their independent sampling gives the claimed security bound for Γφ . The advantage here is the absolute bias after averaging over the oracle distribution, as in Def. 8; we do not interchange this quantity with the expected absolute bias of individual oracle realizations. This completes the proof of Thm. 8.

8.3.4

Consequence for Efficient Black-Box Reductions

We now connect the two source-security theorems to the black-box separation. The implementation convention specified in Sec. 8.3.1 is essential: source circuits have only f -gates, but returned obfuscated programs execute relative to the ambient oracle tuple. Corollary 5. Under this ambient-oracle implementation convention, there is no efficient fully black-box quantum construction of a worst-case quantum-hard language in NP ∩ coNP from postquantum injOWFs and post-quantum i O for classical circuits with injOWF-gates. Proof. Suppose an efficient fully black-box construction (V0 , V1 , R) exists. Fix a backup map φ, and instantiate the source primitives using the independently sampled families f, O and the obfuscator from Sec. 8.3.1. Compiling the construction’s interfaces. Compile the construction’s verifiers into classical Ψ -aided verifiers (Ve0 , Ve1 ). An obfuscation query on (C, r) is implemented by querying O(C, r) and forming the canonical wrapper. Executing such a wrapper is implemented by the corresponding Eval-query. The compilation has polynomial overhead and preserves the verifiers’ behavior. Every tuple in SΨ gives an injective function and a functionally correct obfuscation implementation. The universal structure requirement therefore implies that (Ve0 , Ve1 ) is valid relative to SΨ . Consequently, the deterministic adversary Adec (z) := DecideΨSΨ (Ve0 , Ve1 , z) decides the constructed language exactly on every input. At each input length, the verifier machines are compiled into oracle-aided circuits. Reversibly forming this decision query and uncomputing its description supplies the coherent function-evaluation interface required by the reduction. Polynomial resource inclusion. Replace each call by R to Adec with this decision-oracle implementation, and compile the source interfaces as above. Since the reduction is efficient, it uses polynomially many oracle calls and polynomial-length query registers. The construction’s verifier circuits also have polynomial size, including after interface compilation. It follows that a single polynomial p(n) bounds: 1. the number of queries to each augmented-oracle interface; 2. the lengths of all evaluation encodings queried by the composed reduction; and 3. the corresponding query counts and evaluation lengths inside every verifier submitted to DecideSΨ , for every witness and every underlying realization. 103

These are syntactic bounds on the composed algorithms and circuits, so they also hold in the hybrid executions. Increasing p if necessary, the induced source adversaries are p(n)-query in the sense of Def. 12. There is no requirement that p(n) equal the reduction’s original oracle-query bound. Contradiction with source security. By Thm. 7 and 8, the induced inverter and admissible obfuscation distinguisher have, respectively, success and advantage at most     O p(n)3 2−n/2 and O p(n)3/2 2−n/2 . Both are negligible; in particular, both are O(2−n/4 ) for sufficiently large n. On the other hand, Adec decides the constructed language exactly in the worst case. The black-box security requirement therefore makes R break one of the source primitives with inversepolynomial success or advantage for infinitely many input lengths. This contradicts the preceding bounds. This completes the proof of Corollary 5. The polynomial-resource inclusion argument is sufficient for the efficient-reduction impossibility. The quantitative source-security theorems also apply to inefficient adversaries satisfying Def. 12, but they do not by themselves give an exponential lower bound on the bare number of oracle queries made by an arbitrary inefficient reduction.

9

Acknowledgments and AI Disclosure

We thank Yuval Ishai and Alexis Korb for helpful discussions about their work [GIK+ 23]. GPT-5.6 and GPT-6 were used to improve the clarity and quality of the writing, correct spelling and grammatical errors, and proofread the manuscript. No AI tools were used to generate any of the ideas or techniques presented in this work, except for minor fixes to bugs identified by AI tools.

104

References AHU19.

Andris Ambainis, Mike Hamburg, and Dominique Unruh. Quantum security proofs using semi-classical oracles. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology – CRYPTO 2019, Part II, volume 11693 of Lecture Notes in Computer Science, pages 269–295, Santa Barbara, CA, USA, August 18–22, 2019. Springer, Cham, Switzerland. doi:10.1007/978-3-030-26951-7_10. 10, 11, 20 AR04. Dorit Aharonov and Oded Regev. Lattice problems in NP cap coNP. In 45th Annual Symposium on Foundations of Computer Science, pages 362–371, Rome, Italy, October 17–19, 2004. IEEE Computer Society Press. doi:10.1109/FOCS.2004.35. 2 ARU14. Andris Ambainis, Ansis Rosmanis, and Dominique Unruh. Quantum attacks on classical proof systems: The hardness of quantum rewinding. In 55th Annual Symposium on Foundations of Computer Science, pages 474–483, Philadelphia, PA, USA, October 18–21, 2014. IEEE Computer Society Press. doi:10. 1109/FOCS.2014.57. 15, 85 AT03. Dorit Aharonov and Amnon Ta-Shma. Adiabatic quantum state generation and statistical zero knowledge. In 35th Annual ACM Symposium on Theory of Computing, pages 20–29, San Diego, CA, USA, June 9–11, 2003. ACM Press. doi:10.1145/780542.780546. 4 BBBV97. Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510–1523, 1997. doi:10.1137/ S0097539796300933. 2 BDV17. Nir Bitansky, Akshay Degwekar, and Vinod Vaikuntanathan. Structure vs. hardness through the obfuscation lens. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology – CRYPTO 2017, Part I, volume 10401 of Lecture Notes in Computer Science, pages 696–723, Santa Barbara, CA, USA, August 20–24, 2017. Springer, Cham, Switzerland. doi:10.1007/978-3-319-63688-7_23. 1, 3, 14, 15, 84, 85, 87, 92, 96, 97, 101 BG81. Charles H. Bennett and John Gill. Relative to a random oracle A, PA ̸= NPA ̸= coNPA with probability 1. SIAM Journal on Computing, 10(1):96–113, 1981. doi:10.1137/0210008. 1, 6, 10, 72 BI87. Manuel Blum and Russell Impagliazzo. Generic oracles and oracle classes (extended abstract). In 28th Annual Symposium on Foundations of Computer Science, pages 118–126, Los Angeles, CA, USA, October 12–14, 1987. IEEE Computer Society Press. doi:10.1109/SFCS.1987.30. 1 BLP93. Joe P. Buhler, Hendrik W. Lenstra, Jr., and Carl Pomerance. Factoring integers with the number field sieve. In Arjen K. Lenstra and Jr. Hendrik W. Lenstra, editors, The Development of the Number Field Sieve, volume 1554 of Lecture Notes in Mathematics, pages 50–94. Springer, 1993. doi:10.1007/BFb0091539. 1 CJK+ 17. Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan. Deciding parity games in quasipolynomial time. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, 49th Annual ACM Symposium on Theory of Computing, pages 252–263, Montreal, QC, Canada, June 19–23, 2017. ACM Press. doi:10.1145/3055399.3055409. 4 CJL+ 16. Lily Chen, Stephen Jordan, Yi-Kai Liu, Dustin Moody, Rene Peralta, Ray Perlner, and Daniel Smith-Tone. Report on post-quantum cryptography. NIST Internal Report 8105, National Institute of Standards and Technology, 2016. doi:10.6028/NIST.IR.8105. 2 Con92. Anne Condon. The complexity of stochastic games. Information and Computation, 96(2):203–224, 1992. doi:10.1016/0890-5401(92)90048-K. 4 DMR11. Hang Dinh, Cristopher Moore, and Alexander Russell. Quantum fourier sampling, code equivalence, and the quantum security of the mceliece and sidelnikov cryptosystems, 2011. URL: https://arxiv.org/abs/ 1111.4382, arXiv:1111.4382. 4 GGPS23. Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, and Adrian She. On the algebraic proof complexity of Tensor Isomorphism, 2023. URL: https://arxiv.org/abs/2305.19320, arXiv:2305.19320. 4 GIK+ 23. Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, and Amit Sahai. Hard languages in NP ∩ coNP and NIZK proofs from unstructured hardness. In Barna Saha and Rocco A. Servedio, editors, 55th Annual ACM Symposium on Theory of Computing, pages 1243–1256, Orlando, FL, USA, June 20–23, 2023. ACM Press. doi:10.1145/3564246.3585119. i, 1, 3, 4, 5, 6, 7, 9, 10, 17, 22, 24, 26, 58, 59, 65, 72, 76, 104, 108 GLZ24. Jesse Goodman, Xin Li, and David Zuckerman. Improved condensers for Chor-Goldreich sources. In 65th Annual Symposium on Foundations of Computer Science, pages 1513–1549, Chicago, IL, USA, October 27– 30, 2024. IEEE Computer Society Press. doi:10.1109/FOCS61266.2024.00096. 107 Gor93. Daniel M. Gordon. Discrete logarithms in GF (p) using the number field sieve. SIAM Journal on Discrete Mathematics, 6(1):124–138, 1993. doi:10.1137/0406010. 1 HR04. Chun-Yuan Hsiao and Leonid Reyzin. Finding collisions on a public road, or do secure hash functions need secret coins? In Matthew Franklin, editor, Advances in Cryptology – CRYPTO 2004, volume 3152 of Lecture Notes in Computer Science, pages 92–105, Santa Barbara, CA, USA, August 15–19, 2004. Springer Berlin Heidelberg, Germany. doi:10.1007/978-3-540-28628-8_6. 81

105

HXY19.

HY20.

MV05. Pei15. Rud88.

Sho94.

Tar89. Unr14.

YZ21.

Zha15. Zha19.

Minki Hhan, Keita Xagawa, and Takashi Yamakawa. Quantum random oracle model with auxiliary input. In Steven D. Galbraith and Shiho Moriai, editors, Advances in Cryptology – ASIACRYPT 2019, Part I, volume 11921 of Lecture Notes in Computer Science, pages 584–614, Kobe, Japan, December 8–12, 2019. Springer, Cham, Switzerland. doi:10.1007/978-3-030-34578-5_21. 26 Akinori Hosoyamada and Takashi Yamakawa. Finding collisions in a quantum world: Quantum blackbox separation of collision-resistance and one-wayness. In Shiho Moriai and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2020, Part I, volume 12491 of Lecture Notes in Computer Science, pages 3–32, Daejeon, South Korea, December 7–11, 2020. Springer, Cham, Switzerland. doi:10.1007/ 978-3-030-64837-4_1. 81 Peter Bro Miltersen and N. V. Vinodchandran. Derandomizing Arthur–Merlin games using hitting sets. Computational Complexity, 14(3):256–279, 2005. doi:10.1007/s00037-005-0197-7. 4 Chris Peikert. A decade of lattice cryptography. Cryptology ePrint Archive, Report 2015/939, 2015. URL: https://eprint.iacr.org/2015/939. 2 Steven Rudich. Limits on the Provable Consequences of One-way Functions. PhD thesis, EECS Department, University of California, Berkeley, Dec 1988. URL: http://www2.eecs.berkeley.edu/Pubs/ TechRpts/1988/6060.html. 1 Peter W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In 35th Annual Symposium on Foundations of Computer Science, pages 124–134, Santa Fe, NM, USA, November 20–22, 1994. IEEE Computer Society Press. doi:10.1109/SFCS.1994.365700. 2 Gábor Tardos. Query complexity, or why is it difficult to separate N P A ∩ coN P A from P A by random oracles A? Combinatorica, 9(4):385–392, 1989. doi:10.1007/BF02125350. 1 Dominique Unruh. Revocable quantum timed-release encryption. In Phong Q. Nguyen and Elisabeth Oswald, editors, Advances in Cryptology – EUROCRYPT 2014, volume 8441 of Lecture Notes in Computer Science, pages 129–146, Copenhagen, Denmark, May 11–15, 2014. Springer Berlin Heidelberg, Germany. doi:10.1007/978-3-642-55220-5_8. 15, 85 Takashi Yamakawa and Mark Zhandry. Classical vs quantum random oracles. In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology – EUROCRYPT 2021, Part II, volume 12697 of Lecture Notes in Computer Science, pages 568–597, Zagreb, Croatia, October 17–21, 2021. Springer, Cham, Switzerland. doi:10.1007/978-3-030-77886-6_20. 17 Mark Zhandry. A note on the quantum collision and set equality problems. Quantum Info. Comput., 15(7–8):557–567, May 2015. 20 Mark Zhandry. How to record quantum queries, and applications to quantum indifferentiability. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology – CRYPTO 2019, Part II, volume 11693 of Lecture Notes in Computer Science, pages 239–268, Santa Barbara, CA, USA, August 18– 22, 2019. Springer, Cham, Switzerland. doi:10.1007/978-3-030-26951-7_9. 9, 23, 24

106

A

More Basic Preliminaries

A.1

Probability Inequalities

Lemma 34 (Chernoff PBound). Let X1 , . . . , Xn be independent random variables taking values in {0, 1}, and let X = ni=1 Xi . Then for any δ ≥ 0 and µ ≥ E[X], we have  Pr[X ≥ (1 + δ)µ] ≤

eδ (1 + δ)(1+δ)

µ

Proof. Proof for this version of Chernoff bound can be found in standard literature, e.g., [GLZ24, Theorem 4].

Corollary 6. Let X1 , . . . , Xn be independent random variables taking values in {0, 1}, and let P X = ni=1 Xi . Then for any t ≥ µ and µ ≥ E[X], we have Pr[X ≥ t] ≤ e−µ

 eµ t t

Proof. It directly follows from Lem. 34 by setting δ = µt − 1.

Lemma 35 (Cauchy Schwarz Inequality). For any Random variables X and Y , we have E[XY ] ≤

p E[X 2 ] · E[Y 2 ]

Corollary 7. For any Random variable X, we have E[X] ≤

p E[X 2 ]

Proof. Let Y = 1 in Lem. 35, we have E[X] ≤

p

E[X 2 ] · E[12 ] =

p

E[X 2 ]

Lemma 36 (McDiarmid’s Inequality). Let X = (X1 , . . . , Xm ) be a vector ofQindependent random variables, where each Xi takes values in a finite set Xi . Suppose that F : m i=1 Xi → R satisfies |F (x) − F (x′ )| ≤ ci for some constants c1 , . . . , cm > 0, whenever x and x′ differ only in coordinate i. Then, for every t ≥ 0,     2t2 Pr |F (X) − E[F (X)]| ≥ t ≤ 2 exp − Pm 2 . i=1 ci 107

A.2

Statistical Distance and Properties

For distributions P, Q on a finite set Ω, denote the statistical distance between P and Q as ∆(P, Q) :=

1X |P (x) − Q(x)|. 2 x∈Ω

Lemma 37 ([GIK+ 23, Lemma 3.15]). If A = (A1 , . . . , An ) and B = (B1 , . . . , Bn ) are sequences of independent random variables such that ∀i ∈ [n],

∆(Ai , Bi ) ≤ ε,

then
∆ (A1 , . . . , An ), (B1 , . . . , Bn ) ≤ nε. Also recall that statistical distance does not increase under post-processing: Lemma 38. Let P and Q be probability distributions on a finite set X , and let A be a randomized transformation from X to a finite set Y. Write A(P ) and A(Q) for the output distributions obtained by applying A to an input drawn from P and Q, respectively. Then ∆(A(P ), A(Q)) ≤ ∆(P, Q). In particular, discarding coordinates cannot increase statistical distance. Proof. For each x ∈ X and y ∈ Y, define A(y | x) := Pr[A(x) = y], where the probability P is over the internal randomness of A. For every x ∈ X , we have A(y | x) ≥ 0 for all y ∈ Y and y∈Y A(y | x) = 1. Writing P (x) and Q(x) for the corresponding probability masses, the definition of statistical distance and the triangle inequality give ∆(A(P ), A(Q)) =

1X X (P (x) − Q(x))A(y | x) 2 y∈Y x∈X

≤

1XX |P (x) − Q(x)|A(y | x) 2 y∈Y x∈X

X 1X = |P (x) − Q(x)| A(y | x) 2 x∈X

y∈Y

1X = |P (x) − Q(x)| 2 x∈X

= ∆(P, Q). The final assertion follows by taking A to be the deterministic projection onto the coordinates being retained.

108

A.3

Efficient Approximability of 1e and 1 − 1e

Lemma 39 (Efficient Approximability of 1e ). There exist a deterministic polynomial-time algorithms Approx 1 output a rational number γn = e an bn for some an , bn ∈ N such that, for every n ≥ 2 satisfying 1 an − ≤ 2−n e bn Consequently, 1e is efficiently approximable. Proof. On input 1n , the algorithm Approx1/e outputs γn which is a positive rational number and can be written as n X an n! γn = , an := (−1)k , bn := n!, bn k! k=0

where an , bn ∈ N follows. Consider the Taylor expansion of f (x) = e−x around x = 0, evaluated at x = 1. Taylor’s theorem gives n 1 X (−1)k = + Rn , e k! k=0

where, for some ξ ∈ (0, 1), Rn =

f (n+1) (ξ) . (n + 1)!

Since f (n+1) (ξ) = e−ξ ≤ 1, we obtain 1 1 − γn = |Rn | ≤ . e (n + 1)! Since (n + 1)! ≥ 2n for every n ≥ 1, we then obtain 1 1 an − ≤ ≤ 2−n . e bn (n + 1)! Finally, the algorithm performs O(n) arithmetic operations on integers of bit length bounded by O(log(n!)) = O(n log n). Therefore, Approx1/e runs in deterministic polynomial time. Corollary 8 (Efficient Approximability of 1 − 1e ). There exists a deterministic polynomialtime algorithm Approx1−1/e that, on input 1n , output a rational number γn = abnn for some an , bn ∈ N such that, for every n ≥ 1 satisfying   1 an 1− − ≤ 2−n . e bn Consequently, 1 − 1e is efficiently approximable. 109

Proof. On input 1n , the algorithm Approx1−1/e invokes Approx1/e (1n ) from Lem. 39. If ′

a Approx1/e (1 ) = ′n , bn n

′

′

for some an , bn ∈ N then it outputs ′

′

b −a γn := n ′ n bn By Lem. 39, ′

1 an − ′ ≤ 2−n . e bn Therefore,     ′ ′ b −a 1 1 − γn = 1 − − n ′ n 1− e e bn ′

a 1 = ′n − e bn ≤ 2−n . The invocation of Approx1/e takes polynomial time, and the additional subtraction b − a can be performed in time polynomial in the bit lengths of a and b. Hence, Approx1−1/e is a deterministic polynomial-time algorithm.

B

Length-Tripling Random Oracles as Post-Quantum injOWFs

The following two lemma justifying the assumption UP ⊈ BQP underlying our subsequent oracleseparation results. In particular, we show that a length-tripling random oracle heuristically instantiates a post-quantum injective one-way function with overwhelming probability. Notice that a length-tripling random oracle can be generated independently by setting m(n) = 3n in our interpretation of random oracles by Lem. 1. Lemma 40 (Overwhelming Injectivity of length-tripling random oracle). Fix any n ∈ N, for any length-tripling random oracle Oinj : {0, 1}n → {0, 1}3n , we have Pr [∃x1 , x2 ∈ {0, 1}n such that Oinj (x1 ) = Oinj (x2 ) ∧ x1 ̸= x2 ] ≤ negl(n) $ O← −O Proof. Fix any two distinct inputs x1 , x2 ∈ {0, 1}n , since Oinj is a random oracle and its outputs are independent and uniformly distributed over {0, 1}3n , we have   23n 1 Pr Oinj (x1 ) = Oinj (x2 ) = 6n = 3n . $ 2 2 O← −O There are

 n 2 < 22n 2 110

pairs of distinct elements of {0, 1}n . Therefore, Pr [∃x1 , x2 ∈ {0, 1}n : x1 ̸= x2 ∧ Oinj (x1 ) = Oinj (x2 )] $ O← −O  n 2 ≤ · 2−3n 2

(Union Bound)

< 22n · 2−3n = 2−n = negl(n)

Lemma 41 (Post-Quantum Oneway-ness of length-tripling random oracle). Fix any n ∈ N, for any length-tripling random oracle Oinj : {0, 1}n → {0, 1}3n and quantum oracle-aided adversary A making at most q = poly(n) queries, we have h i Pr A|Oinj ⟩ (Oinj (x)) = x ≤ negl(n). $ $ O← −O,x← −{0,1}n Proof. Assume that there exists a quantum adversary A making at most q queries that inverts a uniformly random length-tripling oracle Oinj : {0, 1}n → {0, 1}3n with success probability h i ε := Pr A|Oinj ⟩ (Oinj (x)) = x . Oinj ,x

We construct an adversary B for the length-preserving preimage-search problem in Lem. 3, with parameter m = 3n. Adversary B is given quantum oracle access to a uniformly random function H : {0, 1}3n → $

$

{0, 1}3n and a challenge y = H(w), where w ← − {0, 1}3n is hidden. It samples r ← − {0, 1}2n once and runs A on y, simulating its oracle byOr (z) := H(z ∥ r) Each quantum query to Or can be simulated using one quantum query to H by appending the fixed string r to the query input. If A outputs z, then B outputs z ∥ r. For the analysis, write w = x ∥ s, where x ∈ {0, 1}n and s ∈ {0, 1}2n . The event r = s occurs with probability 2−2n . Conditioned on this event, Or is a uniformly random function from {0, 1}n to {0, 1}3n , x is uniform and independent of Or , and y = Or (x). Hence A outputs x with probability ε. When r ̸= s, B cannot output w. Therefore, h i Pr B |H⟩ (H(w)) = w = 2−2n ε. H,w

Applying Lem. 3 at input length 3n, we obtain h i
2−2n ε ≤ Pr H B |H⟩ (H(w)) = H(w) H,w

≤

6n(2q + 1)2 + 1 . 23n

Consequently, ε≤

6n(2q + 1)2 + 1 = negl(n), 2n

since q = poly(n).

111

Related documents

• Effective Physical Processes and Active Information in Quantum Computing#748401
• A Separation Between Types of Quantum Oracle Separations#1143305
• An Oracle Separating Conjectures about Incompleteness in the Finite Domain#1014427
• Unleashing Computational Organization Theory with Quantum Probability Theory#1278975
• Major unsolved problems in theoretical computer science?#787499