Unconditional Certified Randomness without Structure

Unconditional Certified Randomness without Structure

arXiv:2608.31112v1 [quant-ph] 31 Aug 2026

Andrea Coladangelo∗ Dakshita Khurana† Saachi Mutreja‡ Bhaskar Roberts§ Joseph Slote¶ Avishay Tal∥

Abstract We obtain a certified randomness protocol in the quantum random oracle model. The protocol is non-interactive and publicly verifiable with a classical verifier, and is based on Yamakawa and Zhandry’s proof of quantumness [JACM’24]. We prove unconditional security of this protocol against adversaries making subexponentially-many adaptive quantum queries to the random oracle. Prior work on certified randomness relative to a random oracle additionally assumed the Aaronson–Ambainis conjecture or proved security only against low query-depth adversaries.

∗ University of Washington. Email: coladan@cs.washington.edu † University of Illinois Urbana-Champaign and NTT Research. Email: dakshita@illinois.edu ‡ Columbia University. Email: sm5540@columbia.edu § UC Berkeley and NTT Research. Email: bhaskarroberts@gmail.com ¶ University of Washington. Email: jslote@cs.washington.edu ∥ UC Berkeley. Email: atal@berkeley.edu

Contents 1 Introduction 1.1 Our result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 2

2 Overview 2.1 The Yamakawa–Zhandry search problem . . . . . . . . . . . . . . . . . . . . . . . 2.2 The min-entropy proof strategy at a high level . . . . . . . . . . . . . . . . . . . . 2.3 Reprogramming heavy coordinates and the query-norm polytope . . . . . . . . . 2.4 Modifying the code and biasing the oracle . . . . . . . . . . . . . . . . . . . . . . 2.5 Security of the updated construction . . . . . . . . . . . . . . . . . . . . . . . . .

3 3 4 8 11 12

3 Preliminaries 13 3.1 Quantum Random Oracle Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 Query-Bounded Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4 Reprogramming Lemmas 17 4.1 Local Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.2 The Query Norm Polytope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5 Error-Correcting Codes 20 5.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.2 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.3 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 6 Certifiable Min-Entropy Protocol 26 6.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 6.2 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 6.3 Proof of Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 7 Proof of the Min-Entropy Property 38 7.1 Low-entropy adversaries heavily query correct answers. . . . . . . . . . . . . . . 38 7.2 Query-bounded adversaries cannot heavily query a correct answer. . . . . . . . . 40 7.3 Finishing the proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 8 AI Disclosure

45

9 Acknowledgments

46

A Proof of Corollary 7.2

48

1

Introduction

Randomness is an inherent feature of quantum mechanics: even complete knowledge of a quantum state does not, in general, determine the outcome of a measurement. Certified randomness takes this idea a step further: it allows a classical user to verify the randomness of a measurement produced by an untrusted quantum device. Protocols for certified randomness have a long tradition in quantum information theory. They were first studied in the so-called device-independent setting, where a classical user interacts with two or more non-communicating quantum devices and certifies randomness through the violation of a Bell inequality [Col06, PAM+ 10, VV12, MS16, MS17, AFDF+ 18]. More recently, a line of work initiated by Brakerski et al. [BCM+ 21] has shown that randomness can also be certified using a single quantum device, replacing the physical assumption of non-communication by an assumption on the computational power of the device. The first protocols were based on the quantum hardness of the Learning With Errors problem (LWE) [MVV22]. In a later work, Aaronson and Hung [AH23] showed that sampling-based quantum advantage experiments can also be turned into certified randomness protocols, under a novel, non-standard complexity-theoretic assumption. Both the device-independent and computational approaches have limitations and leave important desiderata unmet. In the device-independent setting, while security is information-theoretic, it relies on physically enforcing a non-communication condition between spatially separated devices, which is generally impractical. The existing LWE-based protocols [BCM+ 21, MVV22] require some rounds of interaction with the quantum device, in between which the device should maintain a coherent state. Moreover, they produce randomness that is only privately verifiable (using a trapdoor held only by the verifier). The sampling-based protocol of [AH23] has the advantage of being likely within reach of the capabilities of current devices, but verification requires exponential time. Certifiable randomness in the quantum random oracle model (QROM). Recently, Yamakawa and Zhandry [YZ24] (henceforth YZ, for short) proposed an alternative approach to certified randomness. This came as a (conditional) corollary of their breakthrough complexity theory result, which showed an unconditional quantum advantage for an NP-search problem in the quantum random oracle model (QROM). Informally, the NP-search problem is the following: given a suitable code 𝐶 ⊂ Σ𝑛 , find a codeword 𝑥 ∈ 𝐶 such that 𝐻𝑖 (𝑥𝑖 ) = 0 for all coordinates 𝑖 ∈ [𝑛], where 𝐻 = (𝐻 1, . . . , 𝐻𝑛 ) : Σ𝑛 → {0, 1}𝑛 is a random oracle mapping alphabet symbols to bits. They then showed that there exists an efficient quantum algorithm solving the problem with polynomially many queries to 𝐻 , whereas exponentially many queries are necessary for any classical algorithm. Now, the YZ quantum algorithm has the following curious property: it does not return a fixed correct solution, but rather an (essentially) uniformly random one. As pointed out by Yamakawa and Zhandry, the Aaronson–Ambainis conjecture [AA14] implies that this is not a coincidence: for any quantum advantage relative to a random oracle alone, the quantum algorithm that solves the problem must generate some entropy in its output. Applied to the YZ problem, this yields a certified randomness protocol assuming the Aaronson–Ambainis conjecture is true. Moreover, this protocol has very desirable features. It involves a single prover (so no communication assumption is needed). It is non-interactive: the quantum device simply produces a 1

candidate solution, with no further interaction with the verifier. It is publicly verifiable, since anyone with access to the random oracle can efficiently check whether the reported output is a valid solution. So reliance on the Aaronson–Ambainis conjecture appears to be the main shortcoming of the YZ certified randomness protocol. While this conjecture is widely believed to be true, it has resisted proof despite concerted study; e.g. [Mon12, BSdW22, LZ23, Gut24, Bha25]. Motivated by the above discussion, we focus here on the following question: Does certified randomness exist unconditionally in the QROM? In particular, we would like such a protocol to retain the desirable features mentioned above: single-prover, non-interactivity, and public verifiability. An affirmative answer to this question would also provide further evidence for the veracity of the Aaronson–Ambainis conjecture, as it would settle one of its important consequences.

1.1

Our result

In this work, we answer the above question affirmatively. We show that a slight variant of the YZ problem unconditionally certifies randomness in the QROM. Moreover, the resulting protocol is non-interactive and publicly verifiable. The variant differs from the original YZ problem only in the choice of code 𝐶 and the distribution of the random oracle 𝐻 = (𝐻 1, . . . , 𝐻𝑛 ) (which in turn can be simulated in the standard QROM without loss). In the original problem, each 𝐻𝑖 : Σ → {0, 1} maps every symbol independently to a uniformly random bit. In our variant, the bits are instead biased: independently√for every input, 𝐻𝑖 outputs 0 with probability 1 − 𝑝, and 1 with probability 𝑝, where 𝑝 = 1/Θ( 𝑛). We note that this biased random oracle can be constructed straightforwardly in the QROM itself. We discuss the new choice of code 𝐶 and its properties in the technical overview (Section 2). We refer to this YZ variant as the biased YZ problem. We show the following: Theorem 1.1 (Informal). The biased YZ problem in the QROM is a certified min-entropy protocol (as formally defined in Definition 6.1) with the following guarantee: for every 𝑐 ∈ (0, 1/2), the protocol 𝑐 yields min-entropy at least Ω(𝑛𝑐 ) with security against adversaries making at most 2𝑜 (𝑛 ) adaptive queries. The protocol is single-prover, non-interactive, and publicly verifiable. We elaborate further on the notion of a certified min-entropy protocol (introduced in [YZ24]). Informally, a certified min-entropy protocol in the QROM provides the following informationtheoretic guarantee: subject only to a bound on the number of quantum queries made by the prover, with high probability over sampling a random oracle 𝐻 and conditioned on acceptance in the protocol, the verifier’s output must have high min-entropy. Our certified min-entropy protocol has a particularly simple form: the prover returns a solution to the biased YZ problem (which is defined with respect to 𝐻 ), and, upon checking that it is valid, the verifier outputs the solution itself. Therefore, put more thoroughly, the guarantee of Theorem 1.1 is as follows: for any 𝑐 ∈ 𝑐 (0, 1/2) and any (even computationally unbounded) adversary A making 2𝑜 (𝑛 ) quantum queries to the random oracle, with overwhelming probability over 𝐻 , the following holds: if A 𝐻 is accepted with any noticeable probability, the min-entropy of its output, conditioned on acceptance, must be at least Ω(𝑛𝑐 ). 2

Our starting point is a recent result of Khurana, Roberts, and Tal [KRT26], showing that the original YZ problem certifies min-entropy against provers who make their poly(𝑛) queries in at most 𝑜 (log 𝑛) adaptive layers. In the present work, we are able to lift this restriction on adaptivity entirely, albeit for a slight variant of the YZ problem. As a result, we obtain a protocol to certify 𝑐 min-entropy (in the QROM) even against provers that make 2𝑜 (𝑛 ) adaptive queries (a doubly exponential improvement). Our proof is cast in the formalism of hybrid arguments and oracle reprogramming. The main innovation is a relaxed reprogramming guarantee that holds even when modifying the oracle at heavily-queried coordinates: we show that any string x ∈ Σ𝑛 with heavy query weight on many of its symbols retains significant query weight under many different reprogrammings. From a technical standpoint, a key perspective shift is to work with the square root of query weight, which we term the “query norm.” We then reason about the “query norm polytope,” defined by a system of linear constraints that limit how query norms can change between pairs of oracles. We provide an overview of these proof ideas in the next section. Finally, we remark that the YZ quantum advantage is remarkable for another reason: it remains the only known example of a genuinely “structure-less” quantum advantage, in the sense that it arises relative to a random oracle without leveraging any additional algebraic or computational structure. Since its introduction, the YZ construction has spurred a broader effort to understand this new source of quantum advantage. Most recently, it has inspired “Decoded Quantum Interferometry” (DQI) [JSW+ 25], a new framework for quantum algorithms for optimization (which recovers the YZ algorithm as a special case). Thus, beyond providing a certified randomness protocol with several desirable properties, our result makes progress in understanding a key structural property—inherent randomness—of this new source of quantum advantage (albeit for a slight variant of the original YZ problem).

2

Overview

2.1

The Yamakawa–Zhandry search problem

Let us recall the general structure of the YZ search problem [YZ24]. Let 𝐶 ⊆ Σ𝑛 be a code over a large alphabet Σ, and let 𝐻𝑖 : Σ → {0, 1},

𝐻 = (𝐻 1, . . . , 𝐻𝑛 ),

be a random oracle. We say a string x = (𝑥 1, . . . , 𝑥𝑛 ) ∈ Σ𝑛 is correct if x∈𝐶

and

𝐻𝑖 (𝑥𝑖 ) = 0

for every 𝑖 ∈ [𝑛].

The YZ search problem is to find any correct x, given quantum query access to 𝐻 . For an appropriate choice of code 𝐶, Yamakawa–Zhandry gave an algorithm (henceforth the YZ algorithm) which finds a correct x using a single layer of parallel quantum queries. An important property of 𝐶, which will become crucial later on, is that it is list-recoverable: given short lists 𝑆𝑖 of possible symbols at each coordinate 𝑖 ∈ [𝑛], there are very few codewords that are compatible with most of the 𝑆𝑖 ’s; i.e., there are few x = (𝑥 1, . . . , 𝑥𝑛 ) ∈ 𝐶 for which 𝑥𝑖 ∈ 𝑆𝑖 for many 𝑖. 3

The honest prover prepares the uniform superposition over 𝐶 and, independently for each coordinate, the uniform superposition over symbols hashing to zero. After Fourier transforming both registers, the first register is supported on 𝐶 ⊥ , while the second behaves like a sparse error vector because of the oracle bias. The prover uses error-correcting properties of the dual code 𝐶 ⊥ to perform convolution, effectively computing the unitary ∑︁ ∑︁ ∑︁ 𝛼𝑐 |𝑐⟩ ⊗ 𝛽𝑒 |𝑒⟩ ↦→ 𝛼𝑐 𝛽𝑒 |𝑐 + 𝑒⟩ 𝑐∈𝐶 ⊥

𝑐∈𝐶 ⊥,𝑒

𝑒

By the convolution theorem, performing a Fourier transform of the above state yields the intersection of the primal values on both registers. Thus, measuring the resulting state outputs x ∈ 𝐶 such that ∀𝑖 ∈ [𝑛], 𝐻𝑖 (𝑥𝑖 ) = 0.

2.2

The min-entropy proof strategy at a high level

For each oracle ℎ, the YZ algorithm returns a sample from a distribution that is essentially uniform over the set of correct x’s. In recent work, Khurana, Roberts, and Tal [KRT26] proved that this randomness is inherent in the output of any algorithm from a certain restricted class that correctly solves the YZ problem. More specifically, [KRT26] proved unconditionally that the output of any successful, query-efficient prover has high min-entropy, provided the prover’s poly(𝑛)-many queries are made in at most 𝑜 (log 𝑛) adaptive layers. In a nutshell, the main difficulty with many layers of adaptive queries is that the prover’s query weight may depend on the oracle itself. Reprogramming the oracle may therefore change not only the prover’s final output, but also the locations queried in all subsequent layers. The proof in [KRT26] handled these dependencies via a layer-by-layer bootstrapping argument, which limited them to 𝑜 (log 𝑛) adaptive layers. Our argument shares the same high-level template as [KRT26], but develops a new reprogramming argument in order to obtain the full query-bound. As is typical with reprogramming arguments, we begin by defining a “currency” that the prover must pay to query any oracle entry 𝐻𝑖 (𝑥), and whose total amount is controlled by the total number of queries 𝑄 made by the prover. We then derive a contradiction by analyzing how this currency would have to be distributed across the coordinates 𝑖 and symbols 𝑥𝑖 from any correct, high-probability codeword x. 𝑗 In the present work, this currency is the query norm 𝑤 e𝑖,𝑥 , which is charged at each query 𝑗 ∈ [𝑄] according to overlap of the pre-query state 𝜓 𝑗−1 with each of the oracle indices (𝑖, 𝑥) ∈ [𝑛] × Σ: 𝑤 e𝑖,𝑥𝑗 := Π𝑖,𝑥 · 𝜓 𝑗−1 2 . Here Π𝑖,𝑥 := |𝑖, 𝑥⟩⟨𝑖, 𝑥 | ⊗ I, where the projection |𝑖, 𝑥⟩⟨𝑖, 𝑥 | acts on the oracle register and I acts on the algorithm’s work register. The query norm appears as an intermediate quantity in many hy𝑗 brid arguments and is the square root of the familiar query weight, 𝑤𝑖,𝑥 := (e 𝑤𝑖,𝑥𝑗 ) 2 . It is elementary to see that the query norm across all queries and oracle coordinates is controlled by the number of queries as follows: Í e𝑖,𝑥𝑗 ) 2 ≤ 𝑄 . 𝑗,𝑖,𝑥 (𝑤 To discuss how query norm is distributed across oracle indices, it is useful to denote by total Í𝑄 query norm the cumulative quantity 𝑤 e𝑖,𝑥 := 𝑗=1 𝑤 e𝑖,𝑥𝑗 paid to each oracle coordinate (𝑖, 𝑥). This 4

allows us to designate certain strings x ∈ Σ𝑛 as being “heavily queried” in the following sense. For any string x = (𝑥 1, . . . , 𝑥𝑛 ), we say x is (𝑚, 𝑡)-heavily queried by the algorithm Aℎ if 𝑚 coordinates of x each receive total query norm at least 𝑡 under ℎ:  x is (𝑚, 𝑡)-heavily queried ⇐⇒ # 𝑖 ∈ [𝑛] : 𝑤 e𝑖,𝑥𝑖 ≥ 𝑡 ≥ 𝑚 .
We will mostly be interested in 0.9𝑛, 𝛽 -heavily queried x’s for a fixed, noticeable 𝛽 ∈ 1/poly(𝑛, 𝑄) to be chosen later. For this canonical parameter choice we will just say x is heavily queried. In the vocabulary just established, our argument splits into two main claims: Claim A (Low-entropy provers heavily query correct answers). With high probability over the random oracle ℎ ← 𝐻 , if Aℎ returns a correct x with noticeable probability (i.e., A has low min-entropy under ℎ), then x must be heavily queried. Claim B (Query-bounded provers cannot heavily query a correct answer). Suppose 𝑐 A makes no more than 2𝑜 (𝑛 ) queries. Then with high probability over ℎ ← 𝐻 , no correct x is heavily queried by Aℎ . Instantiated appropriately, these statements together yield the quoted lower bound in Theorem 1.1. We remark that an important difference between the approach used here and the one used in [KRT26] is that in the two claims above, as well as their proof, we stick with query norm, rather than passing to query weight 𝑤𝑖,𝑥𝑗 := (𝑤 e𝑖,𝑥𝑗 ) 2 , as is typical with hybrid arguments. While relaxing hybrid argument bounds to query weight is often sufficient (and indeed is sometimes tight—e.g., as in the original [BBBV97] bound for unstructured search), an analysis in terms of query weight seems to be too loose to obtain effective reprogramming bounds in our setting. Claims A and B are both proved via reprogramming arguments, as we outline next. We will need the following elementary swapping lemma, which is standard in hybrid arguments (see e.g. [EJPV98, Lemma 2], [BBBV97, Theorem 3.3]). If oracles ℎ and ℎ′ differ on a set 𝑋 ⊆ [𝑛] × Σ, then the Euclidean distance between the adversary’s states after 𝑗 queries satisfies 𝜓 ℎ𝑗 − 𝜓 ℎ𝑗

′

≤2 2

𝑗 ∑︁ ∑︁ 𝑗 ′ =1 (𝑖,𝑥)∈𝑋

′

𝑤 e𝑖,𝑥𝑗 (ℎ) ≤ 2

∑︁

𝑤 e𝑖,𝑥 (ℎ).

(𝑖,𝑥)∈𝑋

Since this Euclidean distance upper-bounds the trace distance, it also upper-bounds the TV distance of any measurement’s outputs for the two states. We first explain how to carry out the proofs of Claims A and B over the unbiased oracle distribution that assigns each oracle bit independently and uniformly at random. These analyses will eventually require slight modifications to apply to a biased random oracle, as we explain in Section 2.5. 2.2.1

Proving Claim A: Low-entropy provers heavily query correct answers

Setup and bad1 oracles. Fix a noticeable threshold  ℎ 𝛼 := 4𝑛𝛽 and call an oracle ℎ “bad1 ” ℎif there exists an x such that x is correct for ℎ, Pr A = x ≥ 𝛼, yet x is not heavily queried by A . 5

(We consider this case bad since the output Aℎ does not have high min-entropy.) Our goal is to establish an upper bound on Pr[𝐻 is bad1 ]. For each bad1 ℎ, fix an xℎ that is correct for ℎ, returned with probability at least 𝛼 by Aℎ , and not heavily queried. We will argue there is a large set of oracles F (ℎ) such that xℎ is still returned with noticeable probability: Pr[A𝑔 = xℎ ] ≥ 𝛼/2 for all 𝑔 ∈ F (ℎ). Moreover, we will argue that for bad1 oracles ℎ and ℎ′, all the pairs (𝑔, xℎ ), 𝑔 ∈ F (ℎ) and (𝑔′, xℎ′ ), 𝑔′ ∈ F (ℎ′) are distinct. Supposing we can establish a lower bound |F (ℎ)| ≥ 𝐾 for all bad1 ℎ, we thus conclude: ∑︁ ∑︁   1≥ Pr 𝐻 = 𝑔 and A 𝐻 = xℎ (Disjointness) ℎ bad 𝑔∈F (ℎ)

=

∑︁ ∑︁

Pr[𝐻 = 𝑔] Pr[A𝑔 = xℎ ]

ℎ bad 𝑔∈F (ℎ)

≥

∑︁ ∑︁ 𝛼 Pr[𝐻 = ℎ] 2

(𝐻 is unbiased, so Pr[𝐻 = ℎ] = Pr[𝐻 = 𝑔])

ℎ bad 𝑔∈F (ℎ)

≥

𝐾𝛼 Pr[𝐻 is bad1 ], 2

from which we obtain the desired upper bound on the fraction of bad oracles: Pr[𝐻 is bad1 ] ≤

2 . 𝐾𝛼

For the right value of 𝐾, this gives the desired bound on the fraction of bad oracles. We will argue that 𝐾 will be large enough so that this value is small. Reprogramming. The large family F (ℎ) is derived as follows. Because xℎ is not heavily queried, there is a set of coordinates 𝐼 ⊆ [𝑛], |𝐼 | = 0.1𝑛, such that each coordinate-symbol of xℎ in 𝐼 is lightly queried: 𝛼 𝑤 e𝑖,𝑥𝑖 (ℎ) < 𝛽 = for every 𝑖 ∈ 𝐼 . 4𝑛 We use 𝐼 to produce a large number of oracles on which the adversary still outputs xℎ with high probability, while making sure to retain the disjointness property. This is done by reprogramming: for every subset of low total query norm coordinates, 𝑆 ⊆ {(𝑖, 𝑥𝑖 ) : 𝑖 ∈ 𝐼 }, let ℎ𝑆 be the oracle obtained by changing the oracle entries at all (𝑖, 𝑥) ∈ 𝑆 from zero to one. The swapping lemma gives E E 𝑆 𝜓𝑄ℎ − 𝜓𝑄ℎ

(Swapping Lemma)

≤

2

2

∑︁ (𝑖,𝑥𝑖 )∈𝑆

𝑤 e𝑖,𝑥𝑖 (ℎ) < 2 · 0.1𝑛 ·

𝛼 𝛼 ≤ . 4𝑛 2

Consequently, the adversary continues to output xℎ with probability at least 𝛼/2 under every oracle ℎ𝑆 , and with F (ℎ) := {ℎ𝑆 }𝑆 , we have |F (ℎ)| ≥ 20.1𝑛 =: 𝐾. Finally, distinctness of (𝑔, x) pairs follows from the fact that for any (𝑔, x) in any family, the original oracle ℎ for which 𝑔 ∈ F (ℎ) may be uniquely recovered by resetting the values of 𝑔 to zero at the indices (𝑖, 𝑥𝑖 ) from x = (𝑥 1, . . . , 𝑥𝑛 ). We thus conclude that except for a negligible fraction of all oracles ℎ, all correct x output by ℎ A with probability at least 𝛼 must be heavily queried. 6

2.2.2

Proving Claim B: Query-bounded provers cannot heavily query a correct answer

We now provide an overview of the proof of Claim B, which will be the most substantial part of our argument. Setup and bad2 oracles. Our goal is to prove that for almost all oracles there is no heavily queried correct x. At a high level, this is achieved by the following counting argument. Call an oracle ℎ “bad2 ” if Aℎ does manage to heavily query a correct x for ℎ, and set up a bipartite graph with these bad2 oracles as the left vertices and all oracles as the right vertices. We will define edges via reprogramming, and argue that the degrees of the left vertices are uniformly large, say at least 𝐷 L , while the degrees of the right vertices are uniformly small, say at most 𝑑 R . Counting the number of edges in two ways—based on the left- and right-degrees respectively—we find 𝐷 L · |bad2 | ≤ # of edges ≤ 𝑑 R · |all|, from which we conclude that the fraction of bad2 oracles is at most 𝑑 R /𝐷 L . Lower-bounding the left-degree. Let ℎ be a bad2 oracle. We would like to associate ℎ with many alternative oracles 𝑔 while ensuring that each 𝑔 isn’t associated with too many bad2 ℎ’s. However, unlike in the first claim, we are not guaranteed a supply of “lightly queried” coordinates in x—in fact there may be none at all. Thus we cannot use the swapping lemma, which essentially relies on A “not noticing” the reprogramming, and no such guarantee is available for heavy coordinates. This is especially true in adaptive algorithms: because the adversary is making 𝑄 adaptive queries, a priori there is nothing preventing A from using information gained from a heavy query on one entry of ℎ to detect that ℎ has been modified, and then changing its behavior completely. Despite these challenges, we are able to obtain the following key result: Lemma C (Heavy-coordinate reprogramming, informal version of Lemma 4.3). For any oracle ℎ and any x that is (0.9𝑛, 𝛽)-heavily queried, there are 2Ω(𝑛) -many oracles 𝑔, each obtained by reprogramming ℎ at a subset of the coordinate-symbol pairs (𝑖, 𝑥𝑖 ) of x, such that    √ 𝛽 x is Ω( 𝑛), Ω 𝑄 2𝑛2 -heavily queried under 𝑔. The heavy-coordinate reprogramming lemma defines the edges in the bipartite graph under discussion and thus directly√yields a 2Ω(𝑛) lower bound on 𝐷 L . One notices that in 𝑔, the number of heavy coordinates is Ω( 𝑛), which is quadratically worse than in the original ℎ. Looking ahead, this will cause some difficulty with bounding 𝑑 R . This lemma is the technical heart of our argument, and we outline its proof in the next subsection. Upper-bounding the right-degree. Note that while xℎ is generally no longer correct for the oracles 𝑔 returned by the heavy-coordinate reprogramming lemma, it is of course still in the code 𝐶. Therefore to bound the right-degree, it suffices to argue: 7

√ Claim. For any oracle 𝑔, there are very few x’s that (i) are Ω( 𝑛), 1/poly(𝑛, 𝑄) heavily queried by A𝑔 and (ii) are in the code 𝐶. This is proved as follows. By an elementary calculation, the fact that A𝑔 makes at most 𝑄 queries means there are few oracle coordinates (𝑖, 𝑥) with noticeable total query norm.1 Now form the lists {𝑆𝑖 }𝑛𝑖=1 , where 𝑆√𝑖 contains those
𝑥 ∈ Σ such that (𝑖, 𝑥) has noticeable total √ query norm. By definition, any Ω( 𝑛), 1/poly(𝑛, 𝑄) -heavily queried x = (𝑥 1, . . . , 𝑥𝑛 ) has Ω( 𝑛) coordinates such that 𝑥𝑖 ∈ 𝑆𝑖 . It remains only to invoke the list-recovery property of our code 𝐶, which precisely stipulates that there are few x in 𝐶. At this point a reader familiar with the details of the code 𝐶 employed in the original YZ problem may notice an issue: the code in the original YZ problem has inadequate list recovery parameters to be applied in the argument above; in particular, it can only limit the number of codewords that are consistent with a constant fraction of lists 𝑆𝑖 . On the other hand, the parameters of the heavy coordinate reprogramming lemma require us to control the number of codewords √ consistent with a vanishing 𝑂 (1/ 𝑛) fraction of 𝑆𝑖 ’s, and it is not clear how to strengthen the lemma to loosen our requirements. Our solution will be to circumvent the difficulty by modifying 𝐶 to improve its list recovery parameters, which allows the above argument to go through. However, the modification also creates a new issue: the completeness of the protocol is no longer guaranteed, because the honest YZ algorithm no longer succeeds with high probability. Our solution to this is to replace the uniformly random oracle with a biased random oracle, which recovers the YZ algorithm’s high probability of success. A consequence of these complications is that the counting arguments just described, both for Claim A and for Claim B, must become weighted counting arguments to match the biasedness of the oracles—but this final adjustment is fairly straightforward. We now turn to explaining the ideas behind the heavy-coordinate reprogramming lemma. Then we detail the necessary code modifications and oracle biasing. Remark. The use of biased oracles and codes with better list-recovery seems to be an emerging theme for the YZ problem. Related modifications to the YZ problem have appeared in recent works, both in communication complexity [GGJL25] and for separating QCMA from QMA [BHV26].

2.3

Reprogramming heavy coordinates and the query-norm polytope

Here we explain our approach to reprogramming oracles on coordinates receiving large total query norm (Lemma C), beginning with a new geometric perspective afforded by the query norm. Local stability of query norms. As remarked above, the swapping lemma is inadequate for understanding the distribution of total query norm on coordinates of a given x after reprogramming the oracle at locations with large query norm. We obtain additional control by applying the swapping lemma to the intermediate states of the computation as follows. Let ℎ and ℎ′ differ on 1 Indeed, for every query 𝑗, we have Í

𝑗 2 e𝑖,𝑥 ) = 1, and so for every 𝜂 > 0, there are at most 𝑄 2 /𝜂 2 oracle (𝑖,𝑥 ) ∈ [𝑛]×Σ (𝑤

inputs whose total query norm is at least 𝜂.

8

a set 𝑋 ⊆ [𝑛] × Σ. For any oracle input 𝑢 = (𝑖, 𝑥), the reverse triangle inequality gives 𝑤 e𝑢𝑗 (ℎ) − 𝑤 e𝑢𝑗 (ℎ′) =

′

Π𝑢 𝜓 ℎ𝑗−1

− Π𝑢 𝜓 ℎ𝑗−1

2 ℎ ℎ′ ≤ 𝜓 𝑗−1 − 𝜓 𝑗−1 ∑︁ ∑︁ ≤2 𝑤 e𝑣𝑡 (ℎ), 𝑡 < 𝑗 𝑣 ∈𝑋

2

2

where the last inequality is the swapping lemma applied immediately before the 𝑗-th query. Summing over 𝑗 ∈ [𝑄] and applying another triangle inequality yields ∑︁ |𝑤 e𝑢 (ℎ) − 𝑤 e𝑢 (ℎ′)| ≤ 2𝑄 𝑤 e𝑣 (ℎ). 𝑣 ∈𝑋

We call this inequality the local stability of query norms. It says that if the inputs on which two oracles differ have small query norm under ℎ, then the total query norm assigned to any fixed input, 𝑢, cannot change substantially when passing from ℎ to ℎ′. The query-norm polytope. Simultaneously applying local stability across all oracles yields a set of linear constraints whose feasible region we refer to as the query-norm polytope. With H denoting the set of all oracles and writing 𝑤 e𝑖,𝑥 (ℎ) to index the (𝑖, 𝑥, ℎ) th entry of a vector 𝑤 e ∈ R𝑛·|Σ|·|H | , the query-norm polytope is given by:       P𝑄 = 𝑤 e ∈ R𝑛·|Σ|·|H |     

for all 𝑖 ∈ [𝑛], 𝑥 ∈ Σ, ℎ ∈ H, Í |𝑤 e𝑖,𝑥 (ℎ) − 𝑤 e𝑖,𝑥 (ℎ𝑆 )| ≤ 2𝑄 (𝑖 ′,𝑥 ′ )∈𝑆 𝑤 e𝑖 ′,𝑥 ′ (ℎ)

𝑤 e𝑖,𝑥 (ℎ) ∈ [0, 𝑄]

      .    for all 𝑖 ∈ [𝑛], 𝑥 ∈ Σ, ℎ ∈ H, 𝑆 ⊆ [𝑛] × Σ  

As before, ℎ𝑆 denotes the oracle obtained from ℎ by flipping its output on every input in 𝑆. We will be interested in the constraints imposed by the query-norm polytope on a family of reprogrammings. To that end, fix an oracle ℎ and consider a set 𝑀 ⊆ [𝑛] × Σ such that 𝑤 e𝑢 (ℎ) ≥ 𝛽

for every 𝑢 ∈ 𝑀 .

The main consequence of the query-norm polytope is that query norm cannot disappear from all of 𝑀 under a large family of reprogrammings. More precisely, let 𝑘 be any integer satisfying   𝑘 ≤ |𝑀 |. 1+ 2 The main claim internal to the proof of the heavy-coordinate reprogramming lemma is that there exists a set of “protected” inputs   𝑘 , 𝐴𝑘 ⊆ 𝑀, |𝐴𝑘 | ≤ 2 such that the following holds. For every subset 𝑆 ⊆ 𝑀 \ 𝐴𝑘 , the adversary interacting with the reprogrammed oracle ℎ𝑆 assigns query norm at least 𝜏 :=

𝛽 (8𝑄 |𝑀 |) 2 9

to at least 𝑘 inputs in 𝑀. In other words, after protecting only 𝑘2 inputs, we may freely reprogram an arbitrary subset of all remaining inputs in 𝑀 while guaranteeing that at least 𝑘 inputs in 𝑀 continue to have noticeable query norm after reprogramming (though the identities of these 𝑘 still-noticeable coordinates may differ across reprogrammed oracles ℎ𝑆 ). Next, we provide some intuition for why this is true. Intuition for the polytope argument. Consider first the case 𝑘 = 1. Suppose that some reprogramming made every input in 𝑀 have very small query norm. Starting from this reprogrammed oracle ℎ′, reverse the reprogramming to go back to ℎ. Because all the inputs being changed are light under the reprogrammed oracle, local stability says that this reversal cannot substantially increase the query norm at any particular input. But this contradicts the assumption that every input in 𝑀 has query norm at least 𝛽 under ℎ. Thus, every reprogramming leaves at least one input in 𝑀 noticeably queried. The general statement iterates this observation. If every reprogramming already leaves 𝑘 heavy inputs, there is nothing to prove. Otherwise, fix an oracle ℎ★ having fewer than 𝑘 heavy inputs and partition 𝑀 into the sets  Heavy := 𝑢 ∈ 𝑀 : 𝑤 e𝑢 (ℎ★) ≥ 𝜏 and Light := 𝑀 \ Heavy. Heavy contains at least 1 input and at most 𝑘 − 1 inputs. A two-step hybrid argument based on local stability shows that any reprogramming of 𝐻 on arbitrary set of inputs in Light cannot make every input in Heavy light, i.e., at least one of the heavy inputs of ℎ★ must survive. We then apply the argument recursively to Light, obtaining another 𝑘 − 1 heavy inputs there at the cost 𝑘−1
of protecting 2 inputs. To make the conclusion uniform over all reprogrammings, we protect the at most 𝑘 − 1 inputs in Heavy, together with the inputs protected by the recursive application. Thus, the number of protected inputs satisfies     𝑘 −1 𝑘 |𝐴𝑘 | ≤ (𝑘 − 1) + = . 2 2 Note here that guaranteeing 𝑘 surviving heavy inputs costs 𝑂 (𝑘 2 ) protected inputs. The remaining bottleneck. Suppose that 𝑀 contains a linear number of symbols of a codeword. To leave a linear number of symbols freely reprogrammable, the polytope argument above allows us to set √ 𝑘 = Θ( 𝑛). Consequently, we obtain exponentially many reprogrammed√oracles, under every one of which the adversary continues to place noticeable query norm on Θ( 𝑛) symbols of the same codeword. This is precisely what was promised by the heavy-coordinate reprogramming lemma, Lemma C. Unfortunately, as mentioned above, this falls short of what is needed to use the code from the prior work. The original Yamakawa–Zhandry code is list recoverable when a codeword agrees with the supplied symbol lists √ on a linear number of coordinates. In contrast, our polytope argument only preserves Θ( 𝑛) heavily queried symbols. One could hope to prove a stronger reprogramming statement that preserves a linear number of heavy inputs while still leaving a linear number of inputs freely reprogrammable. We record this as an open question: 10

Question 1. Can the heavy-coordinate reprogramming lemma (Lemma C) be improved to the following? Let ℎ be any oracle and let x ∈ Σ𝑛 that is (Ω(𝑛), 𝛽)-heavily queried by a 𝑄-query algorithm
ℎ Ω(𝑛) A . Then there are 2 -many oracles 𝑔 for which x is Ω(𝑛), Ω(𝛽/poly(𝑄, 𝑛)) -heavily queried. Note that it is possible that Question 1 could be resolved using nothing more than the query-norm polytope framework established above, which is convenient because it reduces Question 1 to a question purely about high-dimensional geometry. As we explain √ next, we circumvent Question 1 by modifying the code so that list recovery requires only Θ( 𝑛) approximately known symbols.

2.4

Modifying the code and biasing the oracle

We use a folded Reed–Solomon code 𝐶 ⊆ Σ𝑛 of length 𝑛 and rate 𝑅 = 101√𝑛 . For any constant 𝑐 ∈  𝑐 (0, 1/2), define ℓ = 2𝑛 . The code satisfies the following low-agreement list-recovery property. For every sequence of lists 𝑆 1, . . . , 𝑆𝑛 ⊆ Σ, |𝑆𝑖 | ≤ ℓ, √ 𝑛

there are at most 𝐿 = 2𝑂 (𝑛 log 𝑛) codewords 𝑥 ∈ 𝐶 such that 𝑥𝑖 ∈ 𝑆𝑖 on at least 5 coordinates. Thus, the agreement required by list recovery exactly matches the number of surviving heavy symbols supplied by the query-norm polytope. This lower-rate code solves the security mismatch, but it is not immediately compatible with the Yamakawa–Zhandry quantum algorithm. That algorithm moves to the Fourier basis and ⊥ decodes an error relative to the dual code √ 𝐶 . For our choice of parameters, the dual code decoder tolerates errors supported on only 𝑂 ( 𝑛) symbols. Unfortunately, the error in the dual basis is nonzero in at least a constant fraction of coordinates, which makes decoding in the dual basis impossible and destroys completeness. 𝑐

Using a biased random oracle. We repair correctness by biasing the random oracle2 . Let 𝑝 be the unique power of 1/2 satisfying 1 1 √ <𝑝≤ √ . 80 𝑛 40 𝑛 For every input (𝑖, 𝑥) ∈ [𝑛] × Σ, independently sample ( 1, with probability 𝑝, 𝐻𝑖 (𝑥) = 0, with probability 1 − 𝑝. The verifier continues to accept a codeword x = (𝑥 1, . . . , 𝑥𝑛 ) only when 𝐻𝑖 (𝑥𝑖 ) = 0 for every 𝑖 ∈ [𝑛]. Since 𝑝 is a negative power of two, this biased oracle can be implemented from an ordinary random oracle: truncate the ordinary oracle output to 𝑑 bits, where 𝑝 = 2−𝑑 , and output 1 if and only if all 𝑑 bits are equal to 1. As a result of this bias, the uniform superposition over the zero-preimages of 𝐻𝑖 is now highly concentrated on the zero frequency after applying the Fourier transform.√The Fourier error is nonzero in any particular coordinate √ with probability only 𝑂 (𝑝) = 𝑂 (1/ 𝑛). Hence the total number of nonzero coordinates is 𝑂 ( 𝑛) with overwhelming probability, placing the error within the unique-decoding radius of 𝐶 ⊥ which fixes the completeness problem described above. 2 Note that our eventual certified randomness protocol will be in the “standard” quantum random oracle model.

11

2.5

Security of the updated construction

Weighted counting under the biased oracle. The query-norm bounds, the swapping lemma, local stability, and the query-norm polytope are pointwise statements about fixed oracles, so they are unaffected by the bias. Only the final counting steps in the reprogramming arguments must change. Recall that if ℎ𝑆 is obtained from ℎ by changing |𝑆 | oracle values from zero to one, then     Pr 𝐻 = ℎ𝑆 𝑝 |𝑆 | = . Pr[𝐻 = ℎ] 1−𝑝 More generally, if 𝑇 is a set of zero-valued inputs under ℎ, then the total probability mass of all reprogrammings of 𝑇 compared to Pr[𝐻 = ℎ] is   Í 𝑆 ∑︁  𝑝  |𝑆 |  1  |𝑇 | 𝑆 ⊆𝑇 Pr 𝐻 = ℎ = = . (1) Pr[𝐻 = ℎ] 1−𝑝 1−𝑝 𝑆 ⊆𝑇 In the first reprogramming argument (Claim A, outlined in Section 2.2.1), the families of oracle-output pairs are disjoint, and the adversary’s probability of outputting 𝑥 decreases by at most a factor of two. Taking |𝑇 | = 0.1𝑛, weighted counting therefore shows that 2 (1 − 𝑝) 0.1𝑛 . 𝛼 In the second reprogramming argument (Claim B, outlined in Section 2.2.2), recall that we defined a bipartite graph where the left vertices are bad2 oracles and the right vertices are all oracles. We then defined edges via the heavy-coordinate reprogramming lemma, and aimed to obtain a lower bound 𝐷 L on the degree of the left vertices and an upper bound 𝑑 R on the degree of the right. In the standard random oracle case, counting the number of edges in two ways then gives that the fraction of bad2 oracles is at most 𝐷𝑑R𝐿 , which, for a standard random oracle, coincides with Pr[𝐻 is bad2 ]. For our biased oracle, we should work directly with the quantity of interest, namely the probability mass on bad2 oracles. Note that the total probability mass of all reprogrammings is larger than the probability mass of the original oracle by a factor of at least 1/(1−𝑝) 4𝑛/5 , by (1). Since each resulting oracle belongs to at most 𝐿 families, we have √
Pr[𝐻 is bad2 ] ≤ 𝐿(1 − 𝑝) 4𝑛/5 = exp −Ω( 𝑛) Pr[𝐻 is bad1 ] ≤

From reprogramming to min-entropy. We can now put the two reprogramming arguments together. Suppose that the verifier accepts with probability at least 𝛿, where 𝛿 is inverse polynomial, but that the accepting output distribution has min-entropy at most ℎ ∞ = 𝑜 (𝑛𝑐 ). Then some correct codeword x has conditional probability at least 2−ℎ∞ among the accepting outputs, and 𝑐 hence unconditional output probability at least 𝛼 = 𝛿 · 2−ℎ∞ . In particular, 𝛼 −1 = 2𝑜 (𝑛 ) . Then, the first reprogramming argument (Claim A) says that, except for an exceptional set of probability mass at most 2𝛼 −1 (1 − 𝑝) 0.1𝑛 , such a predictable correct answer must be heavily queried on almost all of its symbols. Since √ √
𝑐) −1 𝑜 (𝑛 𝑝 = Θ(1/ 𝑛) and 𝑐 < 1/2, the factor 𝛼 = 2 is dominated by the exp −Ω( 𝑛) decay of 0.1𝑛 (1 − 𝑝) , and hence this exceptional probability is negligible. 12

The second reprogramming argument (Claim B) says that the probability that any correct codeword is heavily queried on almost all of its symbols is at most 𝐿(1 − 𝑝) 4𝑛/5 = negl(𝑛), where 𝐿 = 2𝑂 (𝑛 log 𝑛) . Thus, except with negligible probability over the oracle, the two conclusions 𝑐 are incompatible. We conclude that every adversary making 𝑄 = 2𝑜 (𝑛 ) queries and causing the verifier to accept with noticeable probability must produce an accepting output distribution with min-entropy at least ℎ ∞ = 𝑜 (𝑛𝑐 ). 𝑐

Returning to the standard QROM. Finally, although we have described the construction using a biased random oracle 𝐻 , it can be implemented using an ordinary uniform random oracle. Write 𝑝 = 2−𝑑 , and let 𝐹 be a uniformly random 𝑑-bit-output oracle. We may now define the biased oracle 𝐻 via 𝐻 (𝑢) = 1 ⇐⇒ 𝐹 (𝑢) = 1𝑑 , so that 𝐻 (𝑢) = 1 with probability exactly 2−𝑑 = 𝑝, independently for every input 𝑢. There is a final, minor subtlety: one might worry that the full oracle 𝐹 reveals more information than the single biased bit 𝐻 . To handle this, we may equivalently generate 𝐹 by first sampling 𝐻 , then independently sampling a residual oracle 𝐺, and setting ( 1𝑑 , 𝐻 (𝑢) = 1, 𝐹 (𝑢) = 𝐺 (𝑢), 𝐻 (𝑢) = 0, where 𝐺 (𝑢) is uniform over {0, 1}𝑑 \ {1𝑑 }. For every fixed choice 𝐺 = 𝑔, an adversary querying the full oracle 𝐹𝐻,𝑔 can be viewed as an adversary querying 𝐻 , with 𝑔 incorporated into its computation between queries. Our security bounds hold for every such fixing of 𝑔. Applying the biased-oracle result after fixing 𝑔, and then averaging over 𝐺, proves the min-entropy guarantee conditioned on the entire uniform oracle 𝐹 . Hence the construction is secure in the standard QROM. We provide more details in Appendix A.

3

Preliminaries

The following lemma says that the Euclidean distance between two states upper-bounds the trace distance. Lemma 3.1. For any quantum pure states |𝜓 ⟩ and |𝜙⟩, TraceDist (|𝜓 ⟩ , |𝜙⟩) ≤ ∥|𝜓 ⟩ − |𝜙⟩∥ 2 . Proof. This follows from the Fuchs–van de Graaf inequality, e.g., [NC12, Ch. 9]: √︃ √︁ √︁ TraceDist (|𝜓 ⟩ , |𝜙⟩) ≤ 1 − |⟨𝜓 |𝜙⟩| 2 ≤ 2 (1 − |⟨𝜓 |𝜙⟩|) ≤ 2 (1 − Re ⟨𝜓 |𝜙⟩) = ∥|𝜓 ⟩ − |𝜙⟩∥ 2 . □

13

3.1

Quantum Random Oracle Model

Bellare and Rogaway [BR93] defined the random oracle as a black-box oracle providing access to a uniformly random function whose inputs and outputs are arbitrarily long. The oracle 𝐹 takes as input a binary string 𝑥 ∈ {0, 1}∗ of any finite length, and outputs a uniformly random binary string 𝐹 (𝑥) of any desired length. Furthermore, quantum algorithms and adversaries can query the random oracle on a quantum superposition of inputs, and the oracle responds coherently. This is known as the quantum random oracle model (QROM) [BDF+ 11]. Biased Random Oracle. Our construction uses a biased random oracle, which can in turn be constructed in the QROM. The biased random oracle 𝐻 is parametrized by a finite set 𝑆 and a (power of two) bias 𝑝 = 2−𝑑 for some 𝑑 ∈ N. 𝐻 is a randomly chosen function mapping 𝑆 → {0, 1} that is sampled from the following distribution. For each input 𝑥 ∈ 𝑆, independently sample 𝐻 (𝑥) ∈ {0, 1} such that Pr[𝐻 (𝑥) = 1] = 𝑝 and Pr[𝐻 (𝑥) = 0] = 1 − 𝑝. The biased random oracle 𝐻 can be implemented with query access to the regular random oracle 𝐹 by appropriately encoding any inputs and outputs of 𝐹 . For instance, to query 𝐻 on some input 𝑥 ∈ 𝑆, we represent 𝑥 as a bitstring, query 𝐹 (𝑥), truncate the and finally  output to  𝑑 bits, 𝑑 𝑑 −𝑑 set 𝐻 (𝑥) = 1 if and only if 𝐹 (𝑥) = 1 . This way, Pr[𝐻 (𝑥) = 1] = Pr 𝐹 (𝑥) = 1 = 2 = 𝑝. In subsequent sections, this encoding is implicit, so we will treat the biased oracle 𝐻 as the random oracle without mentioning 𝐹 .

3.2

Query-Bounded Algorithms

Here we define a quantum algorithm A that makes 𝑄 quantum queries to an oracle. Let A 𝐻 denote a quantum algorithm A with quantum query access to oracle 𝐻 . A is parametrized by a number 𝑄 ≥ 1, which is the maximum number of queries that A can make. Without loss of generality, let A 𝐻 operate as follows: • A starts with an initial pure state |𝜓 0 ⟩ = 𝜓 0𝐻 on registers 𝑅 = (𝑅𝑄 , 𝑅𝐴 ) • For each query 𝑗 ∈ [𝑄]: E 𝐻 – A submits the query register 𝑅𝑄 of 𝜓 𝑗−1 to the oracle 𝐻 . Then 𝐻 acts as a phase oracle on 𝑅𝑄 , and returns 𝑅𝑄 to A. E – A applies 𝑈 𝑗 to its state to obtain a new state 𝜓 𝑗𝐻 . E • Finally, A applies measurement 𝑀 to 𝜓𝑄𝐻 and outputs the measurement outcome. 𝑗 Next, we define the query norm 𝑤 e𝑖,𝑥 (𝐻 ) to upper-bound the amplitude magnitude given to query (𝑖, 𝑥) during the 𝑗-th query. In the literature on quantum query complexity, it is common to deal with the related quantity of query weight, which is the probability of obtaining a query (𝑖, 𝑥) if we measure the 𝑗-th query. Query norm is the square root of query weight.

14

Definition 3.2 (Query Norm). For each possible classical query (𝑖, 𝑥) ∈ [𝑛] × Σ and each query 𝑗 index 𝑗 ∈ [𝑄], let 𝑤 e𝑖,𝑥 (𝐻 ) be the query norm that A 𝐻 gives to (𝑖, 𝑥) on the 𝑗-th query: 𝑗 𝐻 𝑤 e𝑖,𝑥 (𝐻 ) = Π𝑖,𝑥 𝜓 𝑗−1

2

where Π𝑖,𝑥 is the projector to the space querying the (𝑖, 𝑥) location of the oracle, i.e., Π𝑖,𝑥 = |𝑖, 𝑥⟩⟨𝑖, 𝑥 |𝑅𝑄 ⊗ I𝑅𝐴 . We define the total query norm that A 𝐻 gives to (𝑖, 𝑥) as ∑︁ 𝑗 𝑤 e𝑖,𝑥 (𝐻 ) := 𝑤 e𝑖,𝑥 (𝐻 ). 𝑗 ∈[𝑄]

Lemma 3.3. The following holds with respect to any quantum query algorithm A that makes 𝑄 queries to an oracle 𝐻 : • For any 𝑗 ∈ [𝑄], ∑︁

𝑗 (𝑤 e𝑖,𝑥 (𝐻 )) 2 = 1 .

(𝑖,𝑥)∈[𝑛]×Σ

• For any 𝛼 > 0, there are at most 𝑄 2 /𝛼 2 inputs (𝑖, 𝑥) ∈ [𝑛] × Σ such that 𝑤 e𝑖,𝑥 (𝐻 ) ≥ 𝛼. Proof. For the first item, ∑︁

∑︁

𝑗 (𝑤 e𝑖,𝑥 (𝐻 )) 2 =

(𝑖,𝑥)∈[𝑛]×Σ

𝐻 𝐻 𝜓 𝑗−1 Π (𝑖,𝑥) 𝜓 𝑗−1

(𝑖,𝑥)∈[𝑛]×Σ

© ∑︁ ª 𝐻 𝐻 = 𝜓 𝑗−1 ·­ Π (𝑖,𝑥) ® · 𝜓 𝑗−1 « (𝑖,𝑥)∈[𝑛]×Σ ¬ 𝐻 𝐻 = 𝜓 𝑗−1 𝜓 𝑗−1 =1. For the second item, let 𝑋 = {(𝑖, 𝑥) ∈ [𝑛] × Σ : 𝑤 e𝑖,𝑥 (𝐻 ) ≥ 𝛼 }. Then, for every (𝑖, 𝑥) ∈ 𝑋 , by Cauchy–Schwarz, 𝑄 𝑄   2 1 ∑︁ ∑︁ 𝑗 𝑗 𝑤 e𝑖,𝑥 (𝐻 ) 𝑤 e𝑖,𝑥 (𝐻 ) ≥ · 𝑄 𝑗=1 𝑗=1

!2 ≥

Thus, summing over all (𝑖, 𝑥) ∈ 𝑋 we get 𝑄 ∑︁ ∑︁

𝑗 (𝐻 )) 2 ≥ (𝑤 e𝑖,𝑥

(𝑖,𝑥)∈𝑋 𝑗=1

15

𝛼2 · |𝑋 | . 𝑄

𝛼2 𝑄

On the other hand, from the first item, we get 𝑄 ∑︁ ∑︁

𝑗 (e 𝑤𝑖,𝑥 (𝐻 )) 2 ≤

𝑗=1 (𝑖,𝑥)∈𝑋

𝑄 ∑︁

∑︁

𝑗 (e 𝑤𝑖,𝑥 (𝐻 )) 2 = 𝑄 .

𝑗=1 (𝑖,𝑥)∈[𝑛]×Σ 2

By comparing the two, we get 𝛼𝑄 · |𝑋 | ≤ 𝑄, or equivalently, |𝑋 | ≤ 𝑄 2 /𝛼 2 , which completes the proof. □ Lemma 3.4 says that the adversary’s states on two oracles 𝐻 and 𝐻 ′ will be close in Euclidean distance if the adversary gives small query norm to the positions where the oracles differ. Our version of this lemma is adapted from, though different from, [EJPV98, Lemma 2] and [BBBV97, Theorem 3.3]. Lemma 3.4 (Swapping Lemma, Adapted from [EJPV98] Lemma 2, [BBBV97] Theorem 3.3). Given two oracles 𝐻, 𝐻 ′, let 𝑋 ⊆ [𝑛] × Σ be the subset of inputs on which 𝐻 and 𝐻 ′ differ. Then, for any 𝑗 ∈ [𝑄], 𝑗 ∑︁ ∑︁ 𝑗′ 𝐻 𝐻′ 𝜓𝑗 − 𝜓𝑗 ≤ 2 𝑤 e (𝐻 ) . 𝑖,𝑥 2 𝑗 ′ =1 (𝑖,𝑥)∈𝑋

E E ′ Proof. Write 𝜓 𝑗 := 𝜓 𝑗𝐻 and 𝜙 𝑗 := 𝜓 𝑗𝐻 for brevity, and write 𝑂 and 𝑂 ′ for the phase oracles implementing 𝐻 and 𝐻 ′, respectively. Thus 𝑂 |𝑖, 𝑥⟩ |𝑎⟩ = (−1) 𝐻 (𝑖,𝑥) |𝑖, 𝑥⟩ |𝑎⟩, and likewise for 𝑂 ′. In particular, 𝑂 and 𝑂 ′ agree on every basis state whose query register lies outside 𝑋 , while on every (𝑖, 𝑥) ∈ 𝑋 they differ by a relative phase of −1, so  ∑︁ ∑︁  ′ ±2 Π𝑖,𝑥 . (𝑂 − 𝑂 ′) = (−1) 𝐻 (𝑖,𝑥) − (−1) 𝐻 (𝑖,𝑥) Π𝑖,𝑥 = (𝑖,𝑥)∈𝑋

(𝑖,𝑥)∈𝑋

Consequently, for any state |𝜓 ⟩, ∑︁

′

(𝑂 − 𝑂 ) |𝜓 ⟩ 2 =

±2 Π𝑖,𝑥 |𝜓 ⟩

(𝑖,𝑥)∈𝑋

2

≤2

∑︁

Π𝑖,𝑥 |𝜓 ⟩ 2 ,

(𝑖,𝑥)∈𝑋

where the last step is the triangle inequality. The algorithm begins in the same state under both oracles, so |𝜓 0 ⟩ = |𝜙 0 ⟩. For each subsequent query index 𝑗 ∈ [𝑄], 𝜓 𝑗 = 𝑈 𝑗 𝑂 𝜓 𝑗−1

𝜙 𝑗 = 𝑈 𝑗 𝑂 ′ 𝜙 𝑗−1 .

and

Therefore 𝜓𝑗 − 𝜙𝑗

2

= 𝑈 𝑗 𝑂 𝜓 𝑗−1 − 𝑈 𝑗 𝑂 ′ 𝜙 𝑗−1

2

′

= 𝑂 𝜓 𝑗−1 − 𝑂 𝜙 𝑗−1

2

′

≤ 𝑂 𝜓 𝑗−1 − 𝑂 𝜓 𝑗−1 = (𝑂 − 𝑂 ′) 𝜓 𝑗−1 16

2

+ 𝑂 ′ 𝜓 𝑗−1 − 𝑂 ′ 𝜙 𝑗−1

+ 𝜓 𝑗−1 − 𝜙 𝑗−1 2

2

2

© ∑︁ ª ≤ ­2 Π𝑖,𝑥 𝜓 𝑗−1 2 ® + 𝜓 𝑗−1 − 𝜙 𝑗−1 « (𝑖,𝑥)∈𝑋 ¬ © ∑︁ 𝑗 ª = ­2 𝑤 e𝑖,𝑥 (𝐻 ) ® + 𝜓 𝑗−1 − 𝜙 𝑗−1 2 . « (𝑖,𝑥)∈𝑋 ¬ Unrolling the recurrence and using |𝜓 0 ⟩ = |𝜙 0 ⟩ gives the claimed bound.

4

2

□

Reprogramming Lemmas

In this section, we present a core technique for reprogramming a random oracle (Lemma 4.3), which will be used in our proof of the min-entropy property (Section 7). Lemma 4.3 considers an oracle 𝐻 on which the adversary gives high (≥ 𝛽) query norm to each input in a given set 𝑀. Essentially, the adversary spreads its query norm broadly over 𝑀. Next, we will reprogram 𝐻 on a subset of 𝑀 such that the adversary still spreads its norm somewhat broadly over 𝑀. We show that there are 2Ω(|𝑀 |) ways to reprogram 𝐻 such that the adversary gives somewhat high   √︁ 𝛽 ≥ (8𝑄 |𝑀 |) 2 query norm to |𝑀 | inputs in 𝑀.

4.1

Local Stability

We start by a straightforward corollary to the swapping lemma (Lemma 3.4), which we call the “local stability of query norms”. The idea is to view query norms themselves as a measurement on the state. Thus, changing input coordinates with small query norms barely changes the query norms of all other coordinates. Lemma 4.1 (Local Stability of Query Norms). Given two oracles 𝐻, 𝐻 ′ over [𝑛] × Σ, let 𝑋 ⊆ [𝑛] × Σ be the subset of inputs on which 𝐻 and 𝐻 ′ differ. Then, for any 𝑗 ∈ [𝑄], and any (𝑖, 𝑥) ∈ [𝑛] × Σ, ∑︁ ∑︁ ′ 𝑗 𝑗 𝑤 e𝑖,𝑥 (𝐻 ) − 𝑤 e𝑖,𝑥 (𝐻 ′) ≤ 2 𝑤 e𝑖𝑗′,𝑥 ′ (𝐻 ) 𝑗 ′ < 𝑗 (𝑖 ′ ,𝑥 ′ )∈𝑋

E E 𝐻 𝐻 ′ is at most Proof. From Lemma 3.4, we have that the ℓ2 -distance between 𝜓 𝑗−1 and 𝜓 𝑗−1 ∑︁ ∑︁ ′ 2 𝑤 e𝑖𝑗′,𝑥 ′ (𝐻 ), 𝑗 ′ < 𝑗 (𝑖 ′ ,𝑥 ′ )∈𝑋

so it suffices to prove that ′

𝑗 𝑗 𝐻 𝐻 𝑤 e𝑖,𝑥 (𝐻 ) − 𝑤 e𝑖,𝑥 (𝐻 ′) ≤ 𝜓 𝑗−1 − 𝜓 𝑗−1

. 2

Indeed, by the definition of query norm, 𝑗 𝑗 𝐻 𝑤 e𝑖,𝑥 (𝐻 ) − 𝑤 e𝑖,𝑥 (𝐻 ′) = Π𝑖,𝑥 𝜓 𝑗−1

′

2

𝐻 − Π𝑖,𝑥 𝜓 𝑗−1 ′

𝐻 𝐻 ≤ Π𝑖,𝑥 𝜓 𝑗−1 − Π𝑖,𝑥 𝜓 𝑗−1

≤

2

2

(Reverse Triangle Inequality)

′

𝐻 𝐻 𝜓 𝑗−1 − 𝜓 𝑗−1

2

17

.

□

Given an oracle 𝐻 and a subset of inputs 𝑋 ⊆ [𝑛] × Σ, we denote by 𝐻 ⊕ 𝑋 the oracle that is obtained from 𝐻 by flipping the coordinates in 𝑋 , i.e., for each (𝑖, 𝑥) ∈ [𝑛] × Σ, (𝐻 ⊕ 𝑋 )(𝑖, 𝑥) = 𝐻 (𝑖, 𝑥) if (𝑖, 𝑥) ∉ 𝑋 and (𝐻 ⊕ 𝑋 )(𝑖, 𝑥) = 1 − 𝐻 (𝑖, 𝑥) if (𝑖, 𝑥) ∈ 𝑋 . Corollary 4.2. Given any oracle 𝐻 , any subset 𝑋 ⊆ [𝑛] × Σ, and any input (𝑖, 𝑥) ∈ [𝑛] × Σ, we have ∑︁ |𝑤 e𝑖,𝑥 (𝐻 ) − 𝑤 e𝑖,𝑥 (𝐻 ⊕ 𝑋 )| ≤ 2𝑄 · 𝑤 e𝑖 ′,𝑥 ′ (𝐻 ) (2) (𝑖 ′ ,𝑥 ′ )∈𝑋

Proof.

𝑄   ∑︁ 𝑗 𝑗 |𝑤 e𝑖,𝑥 (𝐻 ) − 𝑤 e𝑖,𝑥 (𝐻 ⊕ 𝑋 )| = 𝑤 e𝑖,𝑥 (𝐻 ) − 𝑤 e𝑖,𝑥 (𝐻 ⊕ 𝑋 ) 𝑗=1

≤

𝑄 ∑︁

𝑗 𝑗 𝑤 e𝑖,𝑥 (𝐻 ) − 𝑤 e𝑖,𝑥 (𝐻 ⊕ 𝑋 )

𝑗=1

≤

𝑄 ∑︁ ∑︁ ∑︁ ′ 2 𝑤 e𝑖𝑗′,𝑥 ′ (𝐻 ) 𝑗=1

≤ 2𝑄 ·

𝑄 ∑︁ ∑︁ 𝑗 ′ =1 (𝑖 ′ ,𝑥 ′ )∈𝑋

= 2𝑄 ·

∑︁ (𝑖 ′ ,𝑥 ′ )∈𝑋

4.2

(Lemma 4.1)

𝑗 ′ < 𝑗 (𝑖 ′ ,𝑥 ′ )∈𝑋

′

𝑤 e𝑖𝑗′,𝑥 ′ (𝐻 )

𝑤 e𝑖 ′,𝑥 ′ (𝐻 ) .

□

The Query Norm Polytope

With Equation (2), the set of query norms that a quantum query algorithm can obtain on different oracles satisfies a system of linear inequality constraints. This is similar to a linear program, but without any objective function, thus we call it the query norm polytope. In Section 7, we will consider an oracle 𝐻 for which the query algorithm places significant weight on each input in a set 𝑀 ⊆ [𝑛] × Σ of size Ω(𝑛). The main result in this section is a proof Ω(|𝑀 |) ways to reprogram 𝐻 by modifying a subset of the inputs in 𝑀, such that that there √︁ are 2 at least |𝑀 | of the inputs in 𝑀 still have significant query norm, and hence significant query weight. For a set of inputs 𝑀 ⊆ [𝑛] × Σ and an oracle 𝐻 , denote by F𝐻 (𝑀) = {𝐻 ⊕ 𝑋 : 𝑋 ⊆ 𝑀 } the set of oracles obtained by reprogramming 𝐻 on any subset of 𝑀. Lemma 4.3. Let 𝑀 ⊆ [𝑛] × Σ be a non-empty set of inputs, let 𝐻 be an oracle, and let 𝛽 > 0, such 𝑘
that for each (𝑖, 𝑥) ∈ 𝑀, 𝑤 e𝑖,𝑥 (𝐻 ) ≥ 𝛽. Then, for any 𝑘 ∈ N such that 1 + 2 ≤ |𝑀 |, there exists a
subset 𝐴𝑘 ⊆ 𝑀 of size at most 𝑘2 such that for any oracle 𝐻 ′ ∈ F𝐻 (𝑀 \ 𝐴𝑘 ), there are at least 𝑘 ′ 𝛽 inputs in 𝑀 for which A 𝐻 puts query norm ≥ (8𝑄 |𝑀 |) 2 . Proof. The proof is by induction on 𝑘. 18

Fix 𝐻, 𝑛, Σ, 𝛽. We prove by induction on 𝑘, that for all 𝑀 ⊆ [𝑛] × Σ of size ≥ 1 + 𝑘2 , such
that for all (𝑖, 𝑥) ∈ 𝑀, 𝑤 e𝑖,𝑥 (𝐻 ) ≥ 𝛽, there exists a subset 𝐴𝑘 ⊆ 𝑀 of size at most 𝑘2 such that ′ for any oracle 𝐻 ′ ∈ F𝐻 (𝑀 \ 𝐴𝑘 ), there are at least 𝑘 inputs in 𝑀 for which A 𝐻 puts query norm 𝛽 ≥ (8𝑄 |𝑀 |) 2 . Base Case: 𝒌 = 1. Any reprogramming has one heavily queried input: We begin with the special case of 𝑘 = 1. In this case 𝐴𝑘 = ∅, and we need to prove that for any reprogramming obtained by flipping a subset 𝑋 ⊆ 𝑀, i.e. for any 𝐻 ′ ∈ F𝐻 (𝑀), at least one input in 𝑀 has query 𝛽 𝛽 norm ≥ (8𝑄 |𝑀 |) 2 . In fact, we will show that at least one input in 𝑀 has query norm ≥ 4𝑄 |𝑀 | , and we’ll use the stronger lower bound later in the induction step as well. Assume by contradiction that this is not the case. Then, there exists a set 𝑋 ⊆ 𝑀, such that for all (𝑖, 𝑥) ∈ 𝑀 we have 𝛽 𝑤 e𝑖,𝑥 (𝐻 ⊕ 𝑋 ) < 4𝑄 |𝑀 | But then, applying Equation (2) with
the role of 𝐻 and 𝐻 ⊕ 𝑋 swapped, on any (𝑖, 𝑥) ∈ 𝑀 (at least one of which exists as |𝑀 | ≥ 1 + 𝑘2 ), yields a contradiction, since ∑︁ 3𝛽 𝛽 𝛽 ≤ |e 𝑤𝑖,𝑥 (𝐻 ⊕ 𝑋 ) − 𝑤 e𝑖,𝑥 (𝐻 )| ≤ 2𝑄 · 𝑤 e𝑖 ′,𝑥 ′ (𝐻 ⊕ 𝑋 ) ≤ 2𝑄 · |𝑋 | · ≤ . 4 4𝑄 |𝑀 | 2 ′ ′ (𝑖 ,𝑥 )∈𝑋

where the lower bound is by the hypothesis that 𝑤 e𝑖,𝑥 (𝐻 ) ≥ 𝛽 for each (𝑖, 𝑥) ∈ 𝑀. 𝛽

Induction Step: Assume 𝑘 ≥ 2 and that the theorem is known for 𝑘 −1. Let 𝜏 := (8𝑄 |𝑀 |) 2 . There are two cases. Case 1: Every oracle in F𝑯 (𝑴) has at least 𝒌 inputs in 𝑴 with query norm at least 𝝉. Then we are done immediately, by taking 𝐴𝑘 = ∅. Case 2: Some oracle in F𝑯 (𝑴) has fewer than 𝒌 inputs in 𝑴 with query norm at least 𝝉. Fix 𝐻 ′ to be such an oracle. Define Heavy := {(𝑖, 𝑥) ∈ 𝑀 : 𝑤 e𝑖,𝑥 (𝐻 ′) ≥ 𝜏 },

Light := 𝑀 \ Heavy 𝛽

Since every oracle in F𝐻 (𝑀) has at least one input in 𝑀 with query norm ≥ 4𝑄 |𝑀 | (as we argued in the base case), we see that Heavy is non-empty, and by assumption its size is at most 𝑘 − 1. Next, we claim that every oracle in F𝐻 (Light) has at least one input in Heavy whose query norm is at least 𝜏. Let 𝐻 1 be any oracle in F𝐻 (Light). Our goal is to show that there exists (𝑖, 𝑥) ∈ Heavy such that 𝑤 e𝑖,𝑥 (𝐻 1 ) ≥ 𝜏. Hybrid Oracle. Consider the hybrid oracle 𝐻 2 that equals 𝐻 1 on Light, equals 𝐻 ′ on Heavy, and equals both on ([𝑛] × Σ) \ 𝑀. We have that (i) 𝐻 2 = 𝐻 ′ ⊕ 𝑋 1 for some 𝑋 1 ⊆ Light on the one hand, and (ii) 𝐻 2 = 𝐻 1 ⊕ 𝑋 2 for some 𝑋 2 ⊆ Heavy on the other hand.

19

𝑯 2 has a heavily queried input in Heavy. Let (𝑖 0, 𝑥 0 ) ∈ Heavy be the input in Heavy with ′ the highest query norm according to A 𝐻 . By the above discussion, its query norm is at least 𝛽 4𝑄 |𝑀 | (which is significantly larger than the threshold 𝜏 used to define Heavy). From the first identity, by local stability (Equation (2)), we get that its query norm on 𝐻 2 is at least ∑︁ 𝛽 𝛽 − 2𝑄 |𝑀 |𝜏 ≥ . 𝑤 e𝑖 0,𝑥 0 (𝐻 2 ) ≥ 𝑤 e𝑖 0,𝑥 0 (𝐻 ′) − 2𝑄 · 𝑤 e𝑖 ′,𝑥 ′ (𝐻 ′) ≥ 4𝑄 |𝑀 | 8𝑄 |𝑀 | ′ ′ (𝑖 ,𝑥 )∈𝑋 1

𝑯 1 has a heavily queried input in Heavy. Next, assume towards contradiction that for every (𝑖, 𝑥) ∈ Heavy, the query norm of A 𝐻1 on (𝑖, 𝑥) is less than 𝜏. Then, for the above (𝑖 0, 𝑥 0 ) ∈ Heavy we get a contradiction from local stability (Equation (2)) (using 𝐻 2 = 𝐻 1 ⊕ 𝑋 2 for 𝑋 2 ⊆ Heavy), since ∑︁ 𝛽 𝑤 e𝑖 0,𝑥 0 (𝐻 2 ) ≤ 𝑤 e𝑖 0,𝑥 0 (𝐻 1 ) + 2𝑄 · 𝑤 e𝑖,𝑥 (𝐻 1 ) ≤ 𝜏 + 2𝑄 · |Heavy| · 𝜏 ≤ 3𝑄 |𝑀 | · 𝜏 < 8𝑄 |𝑀 | (𝑖,𝑥)∈𝑋 2

Applying the Induction Hypothesis.

Observe that

|Light| = |𝑀 | − |Heavy|   𝑘 𝑘 · (𝑘 − 1) 2 · (𝑘 − 1) − ≥1+ − (𝑘 − 1) = 1 + 2 2 2   (𝑘 − 2) · (𝑘 − 1) 𝑘 −1 =1+ =1+ 2 2 By the induction hypothesis applied to Light and 𝑘 − 1, there is a set 𝐴𝑘−1 ⊆ Light with   𝑘 −1 |𝐴𝑘−1 | ≤ 2 such that every oracle in F𝐻 (Light \ 𝐴𝑘−1 ) has at least 𝑘 − 1 inputs in Light whose query norm is 𝛽 at least (8𝑄 |Light|) 2 ≥ 𝜏. But F𝐻 (Light \ 𝐴𝑘−1 ) ⊆ F𝐻 (Light), and every oracle in F𝐻 (Light) has at least one additional input in Heavy (which is disjoint from Light) that has query norm at least 𝜏. Hence, every oracle in F𝐻 (Light \ 𝐴𝑘−1 ) has at least 𝑘 inputs in 𝑀 whose query norm is at least 𝜏.
𝑘
We take 𝐴𝑘 = 𝐴𝑘−1 ∪ Heavy. The number of coordinates in 𝐴𝑘 is at most (𝑘 − 1) + 𝑘−1 2 = 2 and every oracle in F𝐻 (𝑀 \ 𝐴𝑘 ) has at least 𝑘 inputs in 𝑀 whose query norm is at least 𝜏. This completes the induction. □ We remark that the only property about query norms that we used in the proof was local stability (Equation (2)).

5

Error-Correcting Codes

In this section, we construct a family of error-correcting codes that will be used in our certifiable min-entropy construction. Our code family is similar to the √ one in [YZ24, Section 4], except we adjust the parameters to allow list-recovery when only 𝑂 ( 𝑛) symbols are approximately known. 20

We first define folded Reed–Solomon codes (Section 5.1). Then we construct a family of such codes by choosing the parameters appropriately (Section 5.2). Finally, we state and prove the properties that we need from this code family (Section 5.3). This section is adapted from [YZ24, Section 4] and uses similar definitions, notation, and proof strategies.

5.1

Definitions

This section comes almost verbatim from [YZ24, Section 4]. A code of length 𝑛 ∈ N over a finite alphabet Σ is a subset 𝐶 ⊆ Σ𝑛 . Linear Codes. A code 𝐶 is said to be linear if its alphabet is Σ = F𝑞 for some prime power 𝑞 and 𝐶 ⊆ F𝑞𝑛 is a linear subspace of F𝑞𝑛 . Folded Linear Codes. A code 𝐶 is said to be a folded linear code if its alphabet is Σ = F𝑚 𝑞 for 𝑛 𝑛·𝑚 some prime power 𝑞 and a positive integer 𝑚 and 𝐶 ⊆ Σ is a linear subspace of F𝑞 where 𝑛 is the length of 𝐶 and we embed 𝐶 into F𝑞𝑛·𝑚 in the canonical way. Dual Codes. defined as

⊥ For a folded linear code 𝐶 ⊆ Σ𝑛 over the alphabet Σ = F𝑚 𝑞 , its dual code 𝐶 is

𝐶 ⊥ = {z ∈ Σ𝑛 : x · z = 0 ∀x ∈ 𝐶} Definition 5.1 (List Recovery). Let Σ be a finite alphabet, let 𝑛 ∈ N, and let 𝐶 ⊆ Σ𝑛 be a code of length 𝑛. Let 𝜁 ∈ [0, 1], and let ℓ, 𝐿 ∈ N. The code 𝐶 is (𝜁 , ℓ, 𝐿)-list recoverable if the following holds: For every sequence of sets 𝑆 1, . . . , 𝑆𝑛 ⊆ Σ

such that

|𝑆𝑖 | ≤ ℓ

∀𝑖 ∈ [𝑛],

there are at most 𝐿 codewords x = (𝑥 1, . . . , 𝑥𝑛 ) ∈ 𝐶 satisfying |{ 𝑖 ∈ [𝑛] : 𝑥𝑖 ∈ 𝑆𝑖 }| ≥ (1 − 𝜁 ) · 𝑛. Generalized Reed–Solomon Codes. A generalized Reed–Solomon code GRSF𝑞 ,𝛾,𝑘,v over F𝑞 w.r.t. a generator 𝛾 of F𝑞∗ , the degree parameter 0 ≤ 𝑘 ≤ 𝑁 , and v = (𝑣 1, . . . , 𝑣 𝑁 ) ∈ F𝑞∗ 𝑁 , where 𝑁 = 𝑞 − 1 is defined as follows:   GRSF𝑞 ,𝛾,𝑘,v := (𝑣 1 𝑓 (𝛾), 𝑣 2 𝑓 (𝛾 2 ), . . . , 𝑣 𝑁 𝑓 (𝛾 𝑁 ) : 𝑓 ∈ F𝑞 [𝑥] deg≤𝑘 where F𝑞 [𝑥] deg≤𝑘 denotes the set of polynomials over F𝑞 of degree at most 𝑘. We remark that GRSF𝑞 ,𝛾,𝑘,v is a linear code over F𝑞 with length 𝑁 = 𝑞 − 1 and dimension 𝑘 + 1. A Reed–Solomon code is a special case of a generalized Reed–Solomon code where v = (1, . . . , 1). There is a classical deterministic unique decoding algorithm GRSUniqueDecodeF𝑞 ,𝛾,𝑘,v for GRSF𝑞 ,𝛾,𝑘,v (e.g., the Berlekamp–Welch algorithm) that corrects up to ⌊(𝑑 min − 1)/2⌋ = ⌊(𝑁 −

21

𝑘 − 1)/2⌋ errors in time poly(𝑁 , log 𝑞) [Ber68, WB86].3 More precisely, for any z ∈ F𝑞𝑁 , if there exists x ∈ GRSF𝑞 ,𝛾,𝑘,v with hw(z − x) ≤ ⌊(𝑁 − 𝑘 − 1)/2⌋, then GRSUniqueDecodeF𝑞 ,𝛾,𝑘,v (z) returns this (necessarily unique) codeword; otherwise it returns ⊥. Folded Reed–Solomon Codes. A folded Reed–Solomon Code FRS is parametrized by a prime power 𝑞, a generator 𝛾 of F𝑞∗ , the degree parameter 0 ≤ 𝑘 < 𝑁 , where 𝑁 = 𝑞 − 1, and the folding 𝑁 ∈ N. Then the code FRSF𝑞 ,𝛾,𝑚,𝑘 is defined as follows: parameter 𝑚 ∈ N, where 𝑛 = 𝑚 FRSF𝑞 ,𝛾,𝑚,𝑘 =

n

o  𝑛−1 𝑓 (𝛾 𝑗𝑚+1 ), 𝑓 (𝛾 𝑗𝑚+2 ), . . . , 𝑓 (𝛾 𝑗𝑚+𝑚 ) 𝑗=0 : 𝑓 ∈ F𝑞 [𝑥] deg≤𝑘

𝑘+1 𝑛 𝑘+1 , and Rate(FRS Note that Σ = F𝑚 F𝑞 ,𝛾,𝑚,𝑘 ) = 𝑁 . 𝑞 and FRSF𝑞 ,𝛾,𝑚,𝑘 ⊆ Σ , |FRSF𝑞 ,𝛾,𝑚,𝑘 | = 𝑞

5.2

Construction

Here we construct a family of folded Reed–Solomon codes that will satisfy the requirements of Lemma 5.2. Our construction simply entails choosing the parameters (𝑞, 𝛾, 𝑚, 𝑘). We construct the family of codes {𝐶𝜆 }𝜆∈N as follows. For all sufficiently large 𝜆 ∈ N, choose the following parameters:
• Choose 𝑐 to be a constant ∈ 0, 12 . • 𝑞(𝜆) = 22⌊log 𝜆⌋ • 𝛾 (𝜆) is an arbitrary generator of F𝑞∗ . • 𝑚(𝜆) = 2 ⌊log 𝜆⌋ + 1 • 𝑁 (𝜆) = 𝑞(𝜆) − 1 𝑁 (𝜆) • 𝑛(𝜆) = 𝑚(𝜆) = 2 ⌊log 𝜆⌋ − 1

• 𝑅(𝜆) =

√1 10 𝑛(𝜆)

• 𝑘 (𝜆) = ⌊𝑅(𝜆)𝑁 (𝜆)⌋ Note that 𝑚(𝜆) = 𝑛(𝜆) + 2, 𝑁 (𝜆) = 𝑚(𝜆)𝑛(𝜆) = 𝑛(𝜆)(𝑛(𝜆) + 2), 𝑞 = (𝑛(𝜆) + 1) 2, Σ = F𝑚 𝑞. Finally, set 𝐶𝜆 = FRSF𝑞 (𝜆) ,𝛾 (𝜆),𝑚(𝜆),𝑘 (𝜆) . 3 One may clear the nonzero multipliers 𝑣

𝑖 and apply any unique decoder for (ordinary) Reed–Solomon codes.

22

5.3

Properties

The following lemma gives several properties of our code that will be useful in the certifiable min-entropy protocol. Lemma 5.2 (Adapted from Lemma 4.2 in [YZ24]). The family {𝐶𝜆 }𝜆∈N from Section 5.2 is a family of length 𝑛 where 𝑛 = Θ(𝜆), |Σ| = 𝑛 Θ(𝑛) = of folded linear codes over the alphabet Σ𝜆 = F𝑚(𝜆) 𝑞(𝜆) 2Θ(𝑛 log 𝑛) that satisfies the following for sufficiently large 𝜆: 1. 𝐶𝜆 is (𝜁 (𝜆), ℓ (𝜆), 𝐿(𝜆))-list recoverable (Definition 5.1), where 1 𝜁 (𝜆) = 1 − √︁ , 5 𝑛(𝜆)

 𝑐  ℓ (𝜆) = 2 (𝜆 ) ,

𝐿(𝜆) = 2𝑂 (𝜆 log 𝜆) . 𝑐

2. There is an efficient deterministic decoding algorithm Decode𝐶𝜆⊥ for 𝐶𝜆⊥ that satisfies the following. Let D be any distribution over Σ that takes 0 with probability at least 1 − 401√𝑛 . Then, it holds that √ ⊥ −Ω( 𝜆) ⊥ Pr n [∀x ∈ 𝐶𝜆 , Decode𝐶𝜆 (x + e) = x] ≥ 1 − 2 e←D

The rest of this subsection is devoted to proving Lemma 5.2. Proof. First Item.

We prove Item 1 of Lemma 5.2, relying on a result from [GR08] and [Rud07].

Theorem 5.3 ([Rud07, Section 3.6], [GR08], [YZ24, Lemma 4.3]). Let 𝑞 be a prime power, 𝛾 ∈ F𝑞∗ be a generator, 𝑁 = 𝑞 − 1, 𝑘 < 𝑁 be a positive integer, and 𝑚 be a positive integer that divides 𝑁 . For positive integers ℓ, 𝑟 , and 𝑠, with 𝑠 ≤ 𝑚, and a real 0 < 𝜁 < 1, suppose 1

(𝑁 ℓ𝑘 𝑠 ) 𝑠+1 𝑁 (1 − 𝜁 ) · ≥ 1 + 𝑟𝑠 · 𝑚 𝑚 −𝑠 +1 and 

𝑁ℓ (𝑟 + 𝑠) · 𝑘

(3)

1  𝑠+1

<𝑞

(4)

Then, FRSF𝑞 ,𝛾,𝑚,𝑘 is (𝜁 , ℓ, 𝑞𝑠 )-list recoverable. We proceed with the proof of Item 1 by establishing Equation (3) and Equation (4). We begin with Equation (3) which by rearranging is equivalent to
1 𝑚 1 + 𝑟𝑠 · 𝑚−𝑠+1 · (𝑁 ℓ𝑘 𝑠 ) 𝑠+1 ≤ (1 − 𝜁 ) · 𝑁 (5) Let 𝑠 = ⌊10𝜆𝑐 ⌋ and 𝑟 = 10𝑠. Note that the right-hand side of Equation (5) is 𝑁 (1 − 𝜁 ) · 𝑁 = √ ≥ 2𝑘 5 𝑛 So it remains to prove that the left-hand side of Equation (5) is at most 2𝑘. Indeed, the left-hand side (of Equation (5)) is a product of three factors: 23

(i) 1 + 𝑟𝑠 = 1.1, √ 𝑚 ≤ 1.1, where the inequality holds for 𝜆 large enough since 𝑚 ≥ 𝜆/2 and 𝑠 ≤ 10 𝜆, (ii) 𝑚−𝑠+1 1

(iii) and (𝑁 ℓ𝑘 𝑠 ) 𝑠+1 . 1

It remains to show that (𝑁 ℓ𝑘 𝑠 ) 𝑠+1 ≤ 1.1𝑘 to show that the left-hand side of Equation (5) is at most 1 (1.1) 3𝑘 ≤ 2𝑘. We do so by comparing (𝑁 ℓ𝑘 𝑠 ) 𝑠+1 to 𝑘. 1   𝑠+1 1 1 𝑐 𝑐 𝑐 𝑁ℓ (𝑁 ℓ𝑘 𝑠 ) 𝑠+1 = ≤ (𝑁 ℓ) 𝑠+1 ≤ 2𝜆 /(10𝜆 ) · 22 log(𝜆)/(10𝜆 ) ≤ 20.1+𝑜 𝜆 (1) ≤ 1.1 𝑘 𝑘

for large enough 𝜆. Overall, we got
1 𝑚 · (𝑁 ℓ𝑘 𝑠 ) 𝑠+1 ≤ (1.1) 3 · 𝑘 ≤ 2𝑘 ≤ (1 − 𝜁 ) · 𝑁 1 + 𝑟𝑠 · 𝑚−𝑠+1 for large enough 𝜆, which completes the proof of Equation (3). As for Equation (4), following a similar calculation, 

𝑁ℓ (𝑟 + 𝑠) · 𝑘

1  𝑠+1

√ ≤ (𝑟 + 𝑠) · 1.1 ≤ 130 𝜆

for large enough 𝜆, and 𝑞 ≥ 𝜆 2 /4 is asymptotically much larger. In summary, for our choice of parameters, both Equation (3) and Equation (4) are satisfied and therefore Theorem 5.3 guarantees that the corresponding 𝑚-folded Reed–Solomon code is 𝑐 𝑐 (𝜁 , ℓ, 𝐿)-list recoverable for 𝐿 = 𝑞𝑠 ≤ (𝜆 2 ) 10𝜆 = 2𝑂 (𝜆 log 𝜆) , which completes the proof of Item 1. Second Item. We prove the dual-decoding property of Lemma 5.2. Throughout this proof, we identify 𝑛 Σ𝑛 = (F𝑚 𝑞)

with

F𝑞𝑁

by concatenating the 𝑛 folded blocks. This is possible because 𝑁 = 𝑚 · 𝑛. Accordingly, we use the same notation for a folded word and its corresponding unfolded word. In particular, when e ← D𝑟𝑛 , we also regard e as an element of F𝑞𝑁 , and hw(e) denotes its Hamming weight in F𝑞𝑁 . Since 𝐶 = FRSF𝑞 ,𝛾,𝑚,𝑘 is an 𝑚-folded Reed–Solomon code, its dual is an 𝑚-folded generalized Reed–Solomon code 𝐶 ⊥ = GRSF(𝑚) 𝑞 ,𝛾,𝑁 −𝑘−2,v for some v ∈ F𝑞𝑁 . Let 𝑑 := 𝑁 − 𝑘 − 2. Thus 𝑑 is a polynomial degree bound for the unfolded dual code. Then the dimension of the dual code is 𝑑 + 1 = 𝑁 − 𝑘 − 1, and its minimum distance (from the Singleton bound) is 𝑑 min (𝐶 ⊥ ) = 𝑁 − 𝑑 = 𝑘 + 2. 24

Define



 𝑘 +1 𝜏 := . 2 Since our noise weight is at most 𝜏 = ⌊(𝑘 + 1)/2⌋ with high probability (shown below), unique decoding of the unfolded GRS dual suffices.4 We define Decode𝐶 ⊥ as follows: Decode𝐶 ⊥ (z): On input z ∈ Σ𝑛 , run GRSUniqueDecodeF𝑞 ,𝛾,𝑑,v (z) with decoding radius 𝜏. If GRSUniqueDecode outputs a codeword of 𝐶 ⊥ , then return this codeword. Otherwise, if GRSUniqueDecode outputs ⊥, then return 0. Note that 2𝜏 ≤ 𝑘 + 1 < 𝑘 + 2 = 𝑑 min (𝐶 ⊥ ), so there can be at most one dual codeword x within distance 𝜏 of any received word z, and 𝜏 is exactly the unique-decoding radius of the dual. The decoder is therefore deterministic and runs in time polynomial in 𝑁 and log 𝑞, hence polynomial in 𝜆. Next define the set  GoodErrors := e ∈ F𝑞𝑁 : hw(e) ≤ 𝜏 . For any x ∈ 𝐶 ⊥ and e ∈ GoodErrors, the codeword x is the unique dual codeword at distance at most 𝜏 from x + e. Since hw(e) ≤ 𝜏, the unique decoder returns x, and therefore Decode𝐶 ⊥ (x + e) = x

for every x ∈ 𝐶 ⊥, e ∈ GoodErrors.

(6)

It remains to bound Pr [e ∉ GoodErrors].

e←Drn

Parse e ∈ Σ𝑛 as e = (𝑒 1, . . . , 𝑒𝑛 ),

e𝑖 ∈ F𝑚 𝑞,

and define the number of nonzero folded blocks by 𝑌 := {𝑖 ∈ [𝑛] : e𝑖 ≠ 0} . Next, by definition of D, ∀𝑖 ∈ [𝑛], independently, Pr[e𝑖 = 0] ≥ 1 −

1 √ . 40 𝑛

We define 𝑋 to be a random variable that stochastically dominates 𝑌 : 1 𝑋 ∼ Bin (𝑛, 𝑝) for 𝑝 = √ 40 𝑛

√ 𝑛 𝜇 := E[𝑋 ] = . 40

Every nonzero folded block contributes at most 𝑚 nonzero unfolded field coordinates. Hence, when 𝑌 ≤ 2𝑝𝑛, 𝑅𝑁 𝑘 + 1 hw(e) ≤ 𝑚𝑌 ≤ 𝑚 · 2𝑝𝑛 = 2𝑝𝑁 = ≤ 2 2 4 By contrast, [YZ24] uses list decoding of the dual [GS99] because their (unbiased) noise has weight about 𝑁 /2,

which exceeds the unique-decoding radius of their dual.

25

The weight is an integer, so  𝑘 +1 = 𝜏. hw(e) ≤ 2 This implies that e ∈ GoodErrors. In summary, 

𝑌 ≤ 2𝑝𝑛

=⇒

e ∈ GoodErrors.

Next, we will use the multiplicative Chernoff bound, 2

Pr[𝑋 > (1 + 𝛿)𝜇] ≤ 𝑒 −𝛿 𝜇/(2+𝛿)

∀𝛿 ≥ 0

Setting 𝛿 = 1, the multiplicative Chernoff bound says the following. Pr [e ∉ GoodErrors] ≤ Pr[𝑌 > 2𝑝𝑛] ≤ Pr[𝑋 > 2𝜇]   √  √  ≤ exp(−𝜇/3) = exp −Ω( 𝑛) = exp −Ω( 𝜆)

e←Drn

Combining this inequality with (6) proves Item 2.

6

□

Certifiable Min-Entropy Protocol

In this section, we present constructions of certifiable min-entropy protocols and prove their correctness. We follow the template of [YZ24]’s proof of quantumness, but with the following main differences. First, we use the family of error-correcting codes constructed in Section 5.2, √ which allow list recovery when only (1−𝜁 )𝑛 = 𝑂 ( 𝑛) symbols are approximately known. Second, we use a biased random oracle to reduce the noise in the dual basis. In Section 6.1, we define certifiable min-entropy protocols. In Section 6.2, we present two constructions of such protocols. Construction 6.2 achieves 𝑜 (𝜆𝑐 ) bits of min-entropy, and Construction 6.4 uses complexity leveraging to provide any poly(𝜆) bits of min-entropy. Finally, in Section 6.3, we prove the correctness of these protocols.

6.1

Definition

A certifiable min-entropy protocol is an interactive proof system between a quantum prover and a classical verifier, where any prover that causes the verifier to accept with noticeable probability must be sampling their accepting proofs from a distribution with high min-entropy. In the random oracle model, the prover has quantum query access to the random oracle, and the min-entropy of the proof is computed after conditioning on the choice of oracle. That way, the proof will provide additional randomness beyond the randomness of the oracle. Definition 6.1 below recalls the definition of a certifiable min-entropy protocol from [YZ24] (almost verbatim). We modify the min-entropy property to allow us to specify the maximum number of queries 𝑄 and the min-entropy threshold ℎ ∞ . Definition 6.1 (Certifiable Min-Entropy Protocol, adapted from [YZ24] Definition 3.5). A (keyless, non-interactive, publicly verifiable) certifiable min-entropy protocol relative to a random oracle (not necessarily uniformly random) consists of the algorithms (Prove, Verify) with the following syntax. 26

Syntax. • Prove𝐻 (1𝜆 , 1ℎ∞ ) → 𝜋: This is a QPT algorithm that takes the security parameter 1𝜆 and a minentropy threshold 1ℎ∞ as input. It makes poly(𝜆, ℎ ∞ ) quantum queries to a random oracle 𝐻 (not necessarily uniformly random), and outputs a classical proof 𝜋. • Verify𝐻 (1𝜆 , 1ℎ∞ , 𝜋) → 𝑥: This is a deterministic classical polynomial-time algorithm that takes 1𝜆 , 1ℎ∞ , and a proof 𝜋 as input. It makes poly(𝜆, ℎ ∞ ) queries to the random oracle 𝐻 , and outputs either a string 𝑥 (whose length may depend on 𝜆, ℎ ∞ ), or ⊥ indicating rejection. We also require a certifiable min-entropy protocol to satisfy the following properties: Correctness.

For any ℎ ∞ = ℎ ∞ (𝜆), we have   Pr Verify𝐻 (1𝜆 , 1ℎ∞ , 𝜋) = ⊥ : 𝜋 ← Prove𝐻 (1𝜆 , 1ℎ∞ ) ≤ negl(𝜆). 𝐻

(𝑄, ℎ ∞ )-Certifiable Min-Entropy. Given a function 𝑄 = 𝑄 (𝜆) and a polynomially-bounded function ℎ ∞ = ℎ ∞ (𝜆), the protocol satisfies (𝑄, ℎ ∞ )-certifiable min-entropy if for any unboundedtime adversary A that makes at most 𝑄 quantum queries to 𝐻 , and any inverse-polynomial function 𝐻 (1𝜆 , 1ℎ ∞ ) be the 𝛿 (·) 5 , there is a negligible function negl(·) such that the following holds. Let A⊤ distribution Verify𝐻 [1𝜆 , 1ℎ∞ , A 𝐻 (1𝜆 , 1ℎ∞ )], conditioned on the output not being ⊥. Then: h    i  𝐻 𝜆 ℎ∞ Pr Pr Verify𝐻 [1𝜆 , 1ℎ∞ , A 𝐻 (1𝜆 , 1ℎ∞ )] ≠ ⊥ ≥ 𝛿 (𝜆) ∧ 𝐻 ∞ A⊤ (1 , 1 ) ≤ ℎ ∞ (𝜆) ≤ negl(𝜆). 𝐻

If (𝑄, ℎ ∞ ) are not specified, we say that the protocol satisfies certifiable min-entropy if for any polynomial functions (𝑄, ℎ ∞ ) 6 , the protocol satisfies (𝑄, ℎ ∞ )-certifiable min-entropy.

6.2

Construction

In this section, we give constructions of certifiable min-entropy protocols in the QROM. Error-Correcting Code. Let {𝐶𝜆 }𝜆∈N be the family of codes given in Section 5.2. In the following, we omit 𝜆 from the subscript of 𝐶𝜆 since it is clear from context. We also use the notation defined in Lemma 5.2. The code has an alphabet Σ = F𝑚 𝑞 and satisfies the requirements of Lemma 5.2 with an arbitrary 0 < 𝑐 < 1/2. Biased Random Oracle. The biased random oracle 𝐻 is a random variable over functions mapping [𝑛] × Σ → {0, 1}, and it is parametrized by the unique bias 801√𝑛 < 𝑝 ≤ 401√𝑛 which is a power of 1/2. Next, 𝐻 is sampled from the following distribution, known as H . For each (𝑖, 𝑥) ∈ [𝑛] × Σ, independently sample 𝐻 (𝑖, 𝑥) ∈ {0, 1} such that Pr[𝐻 (𝑖, 𝑥) = 1] = 𝑝. Finally, 𝐻 can be implemented in the QROM as discussed in Section 3.1. Additionally, for each 𝑖 ∈ [𝑛], let 𝐻𝑖 : Σ → {0, 1} be the function 𝐻 (𝑖, ·). Finally, for any x = (𝑥 1, . . . , 𝑥𝑛 ) ∈ Σ𝑛 , let us abuse notation and say that 𝐻 (x) = [𝐻 1 (𝑥 1 ), . . . , 𝐻𝑛 (𝑥𝑛 )]. 5 Specifically, we quantify over all 𝑒 ∈ N, and set 𝛿 (𝜆) = 𝜆 −𝑒 . 6 Specifically, we quantify over all 𝑑 ∈ N, and set ℎ

𝑑 ∞ (𝜆) = 𝜆 .

27

Certifiable Min-Entropy Protocols. Now we construct certifiable min-entropy protocols using the code 𝐶 and the biased oracle 𝐻 defined above. Construction 6.2 provides 𝑜 (𝜆𝑐 ) bits of min-entropy, whereas Construction 6.4 provides any poly(𝜆) bits of min-entropy. Construction 6.2 (Min-entropy = 𝑜 (𝜆𝑐 )). Prove𝐻 (1𝜆 , 1ℎ∞ ) : 1. For each 𝑖 ∈ [𝑛], generate the state ∑︁

|𝜙𝑖 ⟩ ∝

|e𝑖 ⟩

e𝑖 ∈Σ:𝐻𝑖 (e𝑖 )=0

This is done as follows. Generate a uniform superposition over all e𝑖 ∈ Σ, coherently evaluate 𝐻𝑖 (e𝑖 ), and measure the output. If the measurement outcome is 0, then we have succeeded in generating |𝜙𝑖 ⟩. Repeat the above procedure at most 𝜆 times. If we fail to generate |𝜙𝑖 ⟩ within 𝜆 trials, then abort Prove and output 𝜋 = ⊥. 2. Set |𝜙⟩ = |𝜙 1 ⟩ ⊗ · · · ⊗ |𝜙𝑛 ⟩ 3. Generate the state |𝜓 ⟩ ∝

∑︁

|x⟩

x∈𝐶

4. Apply QFT𝑛Σ to both |𝜓 ⟩ and |𝜙⟩.7 At this point, we have the state, |𝜂⟩ = QFTΣ⊗𝑛 |𝜓 ⟩ ⊗ QFTΣ⊗𝑛 |𝜙⟩ 5. Let 𝑈 add and 𝑈 decode be the unitaries defined as follows for any x, e ∈ Σ𝑛 : Uadd

Udecode

|x⟩|e⟩ −−−→ |x⟩|x + e⟩ −−−−−→ |x − DecodeC⊥ (x + e)⟩|x + e⟩ where Decode𝐶 ⊥ is the decoder for 𝐶 ⊥ as required in Item 2 of Lemma 5.2. Then apply the following unitaries to |𝜂⟩ (from right to left): h
⊗𝑛 i 𝐼 ⊗ QFT−1 · 𝑈 decode · 𝑈 add Σ 6. Measure the second register to obtain x ∈ Σ𝑛 , and output 𝜋 = x. 7 We use the definition of QFT

Σ given in [YZ24, Section 2.2]

28

Verify𝐻 (1𝜆 , 1ℎ∞ , 𝜋): 1. If 𝜋 = ⊥, then output ⊥ and halt. Otherwise, parse 𝜋 = x = (𝑥 1, . . . , 𝑥𝑛 ). 2. If x ∈ 𝐶, and 𝐻𝑖 (𝑥𝑖 ) = 0 for all 𝑖 ∈ [𝑛], then output x. Otherwise, output ⊥. Theorem 6.3. Construction 6.2 is a certifiable min-entropy protocol (Definition 6.1) that satisfies 𝑐 syntax, correctness, and (𝑄, ℎ ∞ )-certifiable min-entropy for any 𝑄 = 2𝑜 (𝜆 ) and any ℎ ∞ (𝜆) = 𝑜 (𝜆𝑐 ), where 𝑐 < 1/2 is a constant parameter of the list-recoverable code (Section 5.2). Proof. It is clear by inspection that the syntax property is satisfied. Next, Theorem 6.6 proves 𝑐 correctness, and Theorem 7.1 proves (𝑄, ℎ ∞ )-certifiable min-entropy for any 𝑄 = 2𝑜 (𝜆 ) and any ℎ ∞ (𝜆) = 𝑜 (𝜆𝑐 ). □ Next, Construction 6.4 uses complexity leveraging on Construction 6.2 to provide ℎ′∞ bits of min-entropy for any ℎ′∞ = poly(𝜆′), where 𝜆′ denotes the security parameter. Essentially, we run Construction 6.2 with a security parameter 𝜆 that is at least ℎ′2/𝑐 ∞ . Then the min-entropy  𝑐/2  = ℎ′∞ bits guarantee of Construction 6.2 implies that this construction provides at least ℎ′2/𝑐 ∞ of min-entropy. Construction 6.4 (Min-entropy = poly(𝜆′)). Let (Prove, Verify) be the functions defined in Construction 6.2. Additionally, let n o 𝜆(𝜆′, ℎ′∞ ) = max 𝜆′, ℎ′2/𝑐 ∞ ℎ ∞ (𝜆′, ℎ′∞ ) = 𝜆(𝜆′, ℎ′∞ )𝑐/2 where 𝑐 is the parameter of the code 𝐶. Next, we construct (Prove′, Verify′) below: ′

′

′

′

Prove′𝐻 (1𝜆 , 1ℎ∞ ) : and output 𝜋.

Compute 𝜆 = 𝜆(𝜆′, ℎ′∞ ) and ℎ ∞ = ℎ ∞ (𝜆′, ℎ′∞ ), compute 𝜋 ← Prove𝐻 (1𝜆 , 1ℎ∞ ),

Verify′𝐻 (1𝜆 , 1ℎ∞ , 𝜋): and output x.

Compute 𝜆 = 𝜆(𝜆′, ℎ′∞ ) and ℎ ∞ = ℎ ∞ (𝜆′, ℎ′∞ ), compute x = Verify𝐻 (1𝜆 , 1ℎ∞ , 𝜋),

Theorem 6.5. Construction 6.4 is a certifiable min-entropy protocol (Definition 6.1) that satisfies syntax, correctness, and certifiable min-entropy (i.e. it satisfies (𝑄 ′, ℎ′∞ )-certifiable min-entropy for any 𝑄 ′ = poly(𝜆′) and any ℎ′∞ (𝜆′) = 𝜆′𝑑 , where 𝑑 ∈ N). Proof. It is straightforward to verify that the syntax property is satisfied. We note that Prove′ and Verify′ have runtimes and query complexities that are poly(𝜆′, ℎ′∞ ). These algorithms run Prove𝐻 (1𝜆 , 1ℎ∞ ) or Verify𝐻 (1𝜆 , 1ℎ∞ , 𝜋), whose runtimes and query complexities are poly(𝜆, ℎ ∞ ). Furthermore, 𝜆 and ℎ ∞ are poly(𝜆′, ℎ′∞ ), so the runtimes and query complexities of Prove′ and Verify′ are poly(𝜆′, ℎ′∞ ). Next, we claim that the correctness property is satisfied. For any ℎ′∞ = ℎ′∞ (𝜆′), let 𝜆 = 𝜆(𝜆′, ℎ′∞ ) and ℎ ∞ = ℎ ∞ (𝜆′, ℎ′∞ ) = 𝜆𝑐/2 . Then there exists a negligible function negl such that h  ′ ′   ′ ′ i ′𝐻 𝜆 ℎ∞ ′𝐻 Pr Verify 1 , 1 , 𝜋 = ⊥ : 𝜋 ← Prove 1𝜆 , 1ℎ∞ 𝐻

29

h    i = Pr Verify𝐻 1𝜆 , 1ℎ∞ , 𝜋 = ⊥ : 𝜋 ← Prove𝐻 1𝜆 , 1ℎ∞ 𝐻

≤ negl(𝜆) This follows from the description of Construction 6.4 and the correctness of Construction 6.2 (Theorem 6.6).  
It just remains to argue that negl 𝜆 𝜆′, ℎ′∞ (𝜆′) is negligible in 𝜆′. Since negl is negligible, we have that for any positive exists an integer 𝜆𝑑 such that for all 𝜆 > 𝜆𝑑 , |negl(𝜆)| <  ′ ′integer  𝑑, there −𝑑 ′ ′ 𝜆 . Also note that 𝜆 𝜆 , ℎ ∞ (𝜆 ) ≥ 𝜆 for all 𝜆′ ∈ N. Then for all 𝜆′ > 𝜆𝑑 , 𝜆 𝜆′, ℎ′∞ (𝜆′) ≥ 𝜆′ > 𝜆𝑑 , and   −𝑑  
≤ 𝜆′−𝑑 negl 𝜆 𝜆′, ℎ′∞ (𝜆′) < 𝜆 𝜆′, ℎ′∞ (𝜆′)  
Therefore, the function negl 𝜆 𝜆′, ℎ′∞ (𝜆′) is negligible in 𝜆′. This shows that Construction 6.4 satisfies correctness. Finally, we claim that Construction 6.4 satisfies (𝑄 ′, ℎ′∞ )-certifiable min-entropy for any 𝑄 ′ = poly(𝜆′) and ℎ′∞ (𝜆′) = 𝜆′𝑑 , where 𝑑 ∈ N. First, let us set the parameters. Next, for any 𝜆′, let  𝜆 = 𝜆(𝜆′, ℎ′∞ ) = max 𝜆′, 𝜆′2𝑑/𝑐 ,

𝑐/2

𝑄 = 2𝜆 ,

ℎ ∞ = 𝜆𝑐/2 . 2𝑑

Note that (𝜆′, ℎ′∞ ) can be computed efficiently from (𝜆, 𝑐, 𝑑) as follows. If 2𝑑𝑐 > 1, then 𝜆 = 𝜆′ 𝑐 , 𝑐 so 𝜆′ = 𝜆 2𝑑 . Otherwise, if 2𝑑𝑐 ≤ 1, then 𝜆 = 𝜆′. Next, we can compute ℎ′∞ = 𝜆′𝑑 . ′ ′
Second, let A ′ be an arbitrary adversary for (Prove′, Verify′) that takes inputs 1𝜆 , 1ℎ∞ and ′ makes at most 𝑄 ′ (𝜆′) queries to 𝐻 . Let 𝑑) to construct an adversary A for
us use A and (𝑐, 𝜆 ℎ ∞ , then computes (𝜆 ′, ℎ ′ ) from (𝜆, 𝑐, 𝑑) as described above, (Prove, Verify). A takes inputs 1 , 1 ∞ ′ ′
′
′𝐻 1𝜆 ′ , 1ℎ ∞ and finally runs A ′ 1𝜆 , 1ℎ∞ and outputs its result. Additionally, let A⊤ be the dis′ ′ ′ ′𝐻 𝜆 ′ ℎ ∞ ′𝐻 𝜆 ℎ ∞ tribution of Verify [1 , 1 , A (1 , 1
)] conditioned on the output not being ⊥. Note that ′
′𝐻 1𝜆 ′ , 1ℎ ∞ 𝐻 1𝜆 , 1ℎ ∞ , which is the distribution of Verify𝐻 [1𝜆 , 1ℎ ∞ , A 𝐻 (1𝜆 , 1ℎ ∞ )] A⊤ is the same as A⊤ conditioned on the output not being ⊥. Third, let us argue that the certifiable min-entropy property of Construction 6.2 applies to our choices of 𝑄, ℎ ∞, A. Note that 𝑄 (𝜆) = 2𝜆

𝑐/2

= 2𝑜 (𝜆 ) 𝑐

ℎ ∞ (𝜆) = 𝜆𝑐/2 = 𝑜 (𝜆𝑐 ) Furthermore, the number of queries to 𝐻 made by A (1𝜆 , 1ℎ∞ ) is at most 𝑄 ′ (𝜆′) = poly(𝜆′) ≤ 2𝜆

′𝑐/2

≤ 2𝜆

𝑐/2

= 𝑄 (𝜆)

for sufficiently large 𝜆′. Fourth, the certifiable min-entropy property of Construction 6.2 (Theorem 7.1) implies that for any inverse-polynomial function 𝛿 (·), there is a negligible function negl(·) such that     Pr Verify𝐻 [1𝜆 , 1ℎ∞ , A 𝐻 (1𝜆 ,
1ℎ∞ )] ≠ ⊥ ≥ 𝛿 (𝜆) negl(𝜆) ≥ Pr 𝐻 (1𝜆 , 1ℎ ∞ ) ≤ ℎ (𝜆) ∧𝐻 ∞ A⊤ 𝐻 ∞     ′ ′ ′ ′𝐻 𝜆 ′ ℎ ∞ ′𝐻 𝜆 ℎ Pr Verify [1 , 1 , A (1 ,
1 ∞ )] ≠ ⊥ ≥ 𝛿 (𝜆) = Pr ′ ′𝐻 (1𝜆 ′ , 1ℎ ∞ ) ≤ ℎ ∞ (𝜆) ∧𝐻 ∞ A⊤ 𝐻 30

Fifth, let us relate 𝛿 (𝜆) to 𝛿 (𝜆′) and ℎ ∞ (𝜆) to ℎ′∞ (𝜆′). 𝛿 (𝜆) = 𝜆 −𝑒 for some 𝑒 ∈ N, so for sufficiently large 𝜆′, 𝛿 (𝜆′) ≥ 𝛿 (𝜆). Additionally,  ℎ′∞ (𝜆′) = 𝜆′𝑑 ≤ max 𝜆′𝑐/2, 𝜆′𝑑 = 𝜆𝑐/2 = ℎ ∞ (𝜆) Then  negl(𝜆) ≥ Pr 𝐻

 ≥ Pr 𝐻

   ′ ′ ′ ′ Pr Verify′𝐻 [1𝜆 , 1ℎ∞ , A ′𝐻 (1𝜆 ,
1ℎ∞ )] ≠ ⊥ ≥ 𝛿 (𝜆) ′ ′𝐻 (1𝜆 ′ , 1ℎ ∞ ) ≤ ℎ ∞ (𝜆) ∧𝐻 ∞ A⊤    ′ ′ ′ ′ Pr Verify′𝐻 [1𝜆 , 1ℎ∞ , A ′𝐻 (1𝜆 ,
1ℎ∞ )] ≠ ⊥ ≥ 𝛿 (𝜆′) ′ ′𝐻 (1𝜆 ′ , 1ℎ ∞ ) ≤ ℎ′∞ (𝜆′) ∧𝐻 ∞ A⊤

Finally, negl(𝜆) = negl(𝜆[𝜆′, ℎ′∞ (𝜆′)]) is negligible in 𝜆′ because 𝜆[𝜆′, ℎ′∞ (𝜆′)] ≥ 𝜆′. This completes the proof of (𝑄 ′, ℎ′∞ )-certifiable min-entropy. □

6.3

Proof of Correctness

Theorem 6.6 (Correctness). Construction 6.2 satisfies correctness (Definition 6.1). The rest of Section 6.3 is devoted to proving Theorem 6.6. First, we show that Prove aborts with negligible probability. Let 𝑀 := |Σ|, and for all 𝐻 , define 𝑇𝑖𝐻𝑖 = {e𝑖 ∈ Σ : 𝐻𝑖 (e𝑖 ) = 0}, Observe that |𝑇𝑖𝐻𝑖 | ∼ Bin(𝑀, 1 − 𝑝), and 𝜇𝑖 = E[|𝑇𝑖𝐻𝑖 |] = (1 − 𝑝) · 𝑀 ≥ 3𝑀 4 . For all 𝑖 ∈ [𝑛], let 𝐺𝑖 := {𝐻 : |𝑇𝑖𝐻𝑖 | ≥ and let 𝐺 =

𝑀 } 2

𝑀 2 𝑖 𝐺𝑖 . Because 2 ≤ 3 𝜇𝑖 , the lower tail multiplicative Chernoff bound implies that

Ó

Pr [¬𝐺𝑖 ] 𝐻

= Pr [|𝑇𝑖𝐻𝑖 | < 𝐻

𝑀 ] 2

1 ≤ Pr [|𝑇𝑖𝐻𝑖 | < (1 − )𝜇𝑖 ] 𝐻 3 ≤ exp{−Ω(𝑀)} A union bound implies that Pr𝐻 [¬𝐺] ≤ 𝑛 · exp{−Ω(𝑀)}. Fix any 𝐻 ∈ 𝐺. Then for every 𝑖 ∈ [𝑛], the probability that all 𝜆 attempts to prepare |𝜙𝑖 ⟩ fail is at most 2−𝜆 . From a union bound, Pr[Prove aborts |𝐻 ] ≤ 𝑛 · 2−𝜆 . It follows that Pr [Prove𝐻 aborts ] 𝐻

≤ Pr [¬𝐺] + Pr [Prove𝐻 aborts ∧ 𝐻 ∈ 𝐺] 𝐻

𝐻

31

≤ 𝑛 · exp{−Ω(𝑀)} + 𝑛 · 2−𝜆 ≤ negl(𝜆) Now we will use a similar analysis to that of [YZ24]. The main technical lemma in [YZ24] is the following. Lemma 6.7 ([YZ24, Lemma 5.1]). Let |𝜓 ⟩ and |𝜙⟩ be quantum states on a quantum system over an alphabet Σ = F𝑚 𝑞 written as ∑︁ |𝜓 ⟩ = 𝑉 (x)|x⟩ x∈Σ𝑛

|𝜙⟩ =

∑︁

𝑊 (e)|e⟩

e∈Σ𝑛 Let 𝐹 : Σ𝑛 → Σ𝑛 be a function. Let Good ⊆ Σ𝑛 × Σ𝑛 be a subset such that for any (x, e) ∈ Good, we

have 𝐹 (x + e) = x. Let Bad be the complement of Good, i.e. Bad = (Σ𝑛 × Σ𝑛 ) \ Good. Suppose that we have, ∑︁ 2 b (e) ≤ 𝜖 𝑉b (x)𝑊 (7) (x,e)∈Bad

and

2

∑︁

∑︁

z∈Σ𝑛

(x,e)∈Bad :x+e=z

b (e) ≤ 𝛿 𝑉b (x)𝑊

(8)

Let 𝑈 add and 𝑈 𝐹 be unitaries defined as follows: 𝑈 add

𝑈𝐹

|x⟩ |e⟩ −−−→ |x⟩ |x + e⟩ −−→ |x − 𝐹 (x + e)⟩ |x + e⟩ . Then we have         ∑︁ ⊗𝑛 ⊗𝑛 ⊗𝑛 √ |Σ|𝑛/2 · √ |0⟩⊗|z⟩ |𝜓 ⟩⊗|𝜙⟩ 𝑉 (z)·𝑊 (z)· . 𝐼 ⊗(QFT−1 ) ·𝑈 ·𝑈 · QFT ⊗QFT · ≈ 𝐹 add Σ Σ Σ 𝜖+ 𝛿 z∈Σ𝑛

In this notation, for any vectors v, w and any 𝑑 > 0, v ≈𝑑 w means ∥v − w∥ 2 ≤ 𝑑. Now, let us instantiate the variables of Lemma 6.7. For a fixed 𝐻 , define 𝑇𝑖𝐻𝑖 = {e𝑖 ∈ Σ : 𝐻𝑖 (e𝑖 ) = 0},

𝑇 𝐻 = 𝑇1𝐻1 × · · · × 𝑇𝑛𝐻𝑛 .

Let us define several amplitude functions:    √1  |𝐶 | 𝑉 (x) =  0    √︂ 1   𝐻𝑖  𝑇𝑖 𝑊𝑖𝐻𝑖 (e𝑖 ) =   0 

if x ∈ 𝐶

∀x ∈ Σ𝑛

otherwise if e𝑖 ∈ 𝑇𝑖𝐻𝑖

∀𝑖 ∈ [𝑛], e𝑖 ∈ Σ otherwise 32

  if e ∈ 𝑇 𝐻 √ 1𝐻  𝑇 | | 𝑊 (e) =  0 otherwise Ö 𝑊𝑖𝐻𝑖 (e𝑖 ) . =

∀e ∈ Σ𝑛

𝐻

𝑖∈[𝑛]

Additionally, let 𝐹 = Decode𝐶 ⊥ , and assume for now that with overwhelming probability over the choice of 𝐻 , there exist subsets Good, Bad such that inequalities (7) and (8) are true for negligible functions 𝜖 and 𝛿 respectively. This assumption will be justified in Claim 6.8. Then, Lemma 6.7 directly corresponds to the honest Prove algorithm and implies that an honestly generated proof 𝜋 will satisfy 𝑉 (𝜋) · 𝑊 𝐻 (𝜋) > 0, except with negligible probability. If 𝑉 (𝜋) · 𝑊 𝐻 (𝜋) > 0, then 𝜋 ∈ 𝐶 and 𝐻𝑖 (𝜋𝑖 ) = 0 for all 𝑖 ∈ [𝑛]. This value of 𝜋 will be accepted by Verify, so Verify will not output ⊥. This proves correctness. It remains to prove that Equations (7) and (8) are true for negligible functions 𝜖 and 𝛿. Let 𝑀 := |Σ|. Let 𝜇𝑝 denote the distribution on functions ℎ : Σ → {0, 1} defined by 𝜇𝑝 (ℎ) := (1 − 𝑝) |ℎ

−1 (0)|

𝑝 |ℎ

−1 (1)|

.

Thus, the original biased oracle 𝐻 = (𝐻 1, . . . , 𝐻𝑛 ) is obtained by sampling 𝐻 1, . . . , 𝐻𝑛 independently from 𝜇𝑝 . Define the following events: 𝑛 n o Û ∀𝑖 ∈ [𝑛] E𝑖 := 𝑇𝑖𝐻𝑖 ≠ ∅ , E := E𝑖 . 𝑖=1

E𝑖 is the event that at least one input to 𝐻𝑖 hashes to 0, and ¬E𝑖 is the event that 𝐻𝑖 (e𝑖 ) = 1 for every e𝑖 ∈ Σ. Then 𝑛 ∑︁ Pr[¬E] ≤ Pr[¬E𝑖 ] = 𝑛𝑝 𝑀 = negl(𝜆), 𝑖=1

Define the conditioned one-coordinate distribution e 𝜇𝑝 as the distribution of 𝐻𝑖 conditioned on E𝑖 . Formally, for any ℎ : Σ → {0, 1}, −1 −1   (1 − 𝑝) |ℎ (0)| 𝑝 |ℎ (1)|    , ℎ −1 (0) ≠ ∅, 1 − 𝑝𝑀 e 𝜇𝑝 (ℎ) :=    0, ℎ −1 (0) = ∅.  Sampling 𝐻 conditioned on E is equivalent to sampling 𝐻 1, . . . , 𝐻𝑛 independently from 𝜇e𝑝 . Throughout the remainder of the proof, whenever 𝐻 or 𝐻𝑖 appears in an expectation or probability, it is sampled from 𝜇e𝑝 𝑛 or 𝜇e𝑝 , respectively, unless stated otherwise. Note that Pr[E] = 1 − negl(𝜆), so 𝜇𝑝𝑛 and 𝜇e𝑝 𝑛 are statistically close. Finally, define 𝑝 − 𝑝𝑀 𝑝 ★ := . 1 − 𝑝𝑀 Then 1−𝑝 0 ≤ 𝑝 ★ ≤ 𝑝, 1 − 𝑝★ = . 1 − 𝑝𝑀

33

Claim 6.8 (Biased analogue of [YZ24, Claim 6.4]). With probability 1−negl(𝜆) over 𝐻 = (𝐻 1, . . . , 𝐻𝑛 ) ∼ 𝜇e𝑝 𝑛 , there are subsets Good ⊆ Σ𝑛 × Σ𝑛 and Bad = (Σ𝑛 × Σ𝑛 )\Good such that Decode𝐶 ⊥ (x + e) = x

for all (x, e) ∈ Good,

and we have ∑︁

2

b 𝐻 (e) ≤ negl(𝜆) 𝑉b (x)𝑊

(x,e)∈Bad

and

2

∑︁

∑︁

b 𝐻 (e) ≤ negl(𝜆) . 𝑉b (x)𝑊

z∈Σ𝑛 (x,e)∈Bad :x+e=z

Proof. By the definition of 𝑉 ,   √1 ⊥ ,  |𝐶 | b 𝑉 (x) =   0, 

Define

x ∈ 𝐶 ⊥,

(9)

x ∉ 𝐶⊥.

 GoodErrors := e ∈ Σ𝑛 : ∀x ∈ 𝐶 ⊥, Decode𝐶 ⊥ (x + e) = x , BadErrors := Σ𝑛 \ GoodErrors. Since 𝑝 ★ ≤ 𝑝 ≤ 401√𝑛 , Lemma 5.2 implies that, √

Pr 𝑛 [e ∈ BadErrors] ≤ 2−Ω( 𝜆) .

(10)

e←D ★ 𝑝

for any distribution D𝑝 ★ that samples 0 with probability 1 − 𝑝 ★. Set Good := 𝐶 ⊥ × GoodErrors, Bad := (Σ𝑛 × Σ𝑛 ) \ Good. By definition, Decode𝐶 ⊥ (x + e) = x

for every (x, e) ∈ Good.

Because 𝑉b (x) = 0 for x ∉ 𝐶 ⊥ , ∑︁

2

2

∑︁

b 𝐻 (e) = 𝑉b (x)𝑊

b 𝐻 (e) , 𝑊

(11)

e∈BadErrors

(x,e)∈Bad

2 2

∑︁

∑︁

z∈Σ𝑛 (x,e)∈Bad :x+e=z

b 𝐻 (e) = 𝑉b (x)𝑊

∑︁

∑︁

z∈Σ𝑛

x∈𝐶 ⊥,

b 𝐻 (e) . 𝑉b (x)𝑊

(12)

e∈BadErrors :x+e=z

By a standard averaging argument, it is enough to establish " # √ ∑︁ 2 b 𝐻 (e) ≤ 2−Ω( 𝜆) , E𝐻 𝑊 e∈BadErrors

34

(13)

and

    2  ∑︁ √ ∑︁   b 𝐻 (e)  ≤ 2−Ω( 𝜆) . E𝐻  𝑉b (x)𝑊  z∈Σ𝑛  ⊥, x∈𝐶   e∈BadErrors   :x+e=z  

(14)

Then Markov’s inequality will complete the proof of Claim 6.8. Claim 6.9. Let 𝜋 : Σ → Σ be a permutation. Then the distributions of 𝐻𝑖 and 𝐻𝑖 ◦ 𝜋 (resp. 𝐻 and 𝐻 ◦ 𝜋 ⊗𝑛 ) are identical. Proof of claim. Composition with 𝜋 preserves the cardinality of the set of preimages of 0. More concretely, for all 𝑖 ∈ [𝑛] |{e𝑖 ∈ Σ : 𝐻𝑖 (e𝑖 ) = 0}| = |{e𝑖 ∈ Σ : (𝐻𝑖 ◦ 𝜋)(e𝑖 ) = 0}|. Proof of Equation (13).

♦

We first prove the following claim.

Claim 6.10. For every 𝑖 ∈ [𝑛],  E𝐻𝑖

b 𝐻𝑖 (0) 𝑊 𝑖

2

 = 1 − 𝑝 ★.

Proof of claim. Equation (15) is proven as follows: " 2#   ∑︁ 2 1 b 𝐻𝑖 (0) = E𝐻𝑖 √ 𝑊𝑖𝐻𝑖 (a) E𝐻𝑖 𝑊 𝑖 𝑀 a∈Σ h i E𝐻𝑖 𝑇𝑖𝐻𝑖 = 𝑀 1−𝑝 . = 1 − 𝑝𝑀 = 1 − 𝑝★ . Note that the distribution D (𝑖) on Σ defined by   2 𝐻 (𝑖) 𝑖 b (𝑒) D (𝑒) = E𝐻𝑖 𝑊 𝑖

(15)

♦

(16)

is the same for all 𝑖 ∈ [𝑛]. Thus, we can denote it by D. Observe further that D satisfies the condition of Lemma 5.2, namely D (0) = 1 − 𝑝 ★ for 𝑝 ★ ≤ 401√𝑛 . For every e = (e1, . . . , e𝑛 ) ∈ Σ𝑛 , 𝑛 Ö

b 𝐻𝑖 (e𝑖 ). 𝑊 𝑖

(17)

Combining (16), (17), and conditional independence yields   2 𝐻 b (e) = D 𝑛 (e). E𝐻 𝑊

(18)

b 𝐻 (e) = 𝑊

𝑖=1

35

Consequently, by (10), " ∑︁

E𝐻

b𝐻

𝑊 (e)

2

# ∑︁

=

e∈BadErrors

D 𝑛 (e)

e∈BadErrors

= Pr 𝑛 [e ∈ BadErrors] e←D

√

≤ 2−Ω( 𝜆) . This proves (13). Proof of Equation (14).

b satisfies the following: Define 𝐵 : Σ𝑛 → C so that 𝐵 ( b = 1, e ∈ BadErrors . 𝐵(e) 0, e ∉ BadErrors

Claim 6.11.

2

∑︁

∑︁

z∈Σ𝑛

x∈𝐶 ⊥, e∈BadErrors :x+e=z

b 𝐻 (e) = 𝑉b (x)𝑊

Proof of claim. For every z ∈ Σ𝑛 , ∑︁

∑︁

  2 𝑉 (z) 𝐵 ∗ 𝑊 𝐻 (z) .

z∈Σ𝑛

∑︁

b 𝐻 (e) = 𝑉b (x)𝑊

x∈𝐶 ⊥, e∈BadErrors :x+e=z

b 𝑊 b 𝐻 (e) 𝑉b (x) 𝐵(e)

x,e∈Σ𝑛 :x+e=z

i h  b·𝑊 b 𝐻 (z) = 𝑉b ∗ 𝐵 
 = 𝑉¤```````` · 𝐵 ∗ 𝑊 𝐻 (z) . The first equality uses 𝑉b (x) = 0 for all x ∉ 𝐶 ⊥ ; the last equality is the convolution theorem. Parseval’s theorem completes the proof. ♦ Claim 6.12. For every z ∈ Σ𝑛 ,  E𝐻

𝐵 ∗𝑊

𝐻



(z)

2



√

≤ 2−Ω( 𝜆) .

Proof of claim. First observe that for any z0, z1 ∈ Σ𝑛 ,       2 2 𝐻 𝐻 E𝐻 𝐵 ∗ 𝑊 (z0 ) = E𝐻 𝐵 ∗ 𝑊 (z1 ) . Indeed, let 𝜏𝑖 (a) := a + (z0 )𝑖 − (z1 )𝑖 36

∀𝑖 ∈ [𝑛], a ∈ Σ

(19)

and τ = (𝜏1, . . . , 𝜏𝑛 ). Therefore,  E𝐻



𝐵 ∗ 𝑊 𝐻 (z0 )

2

2#

"



∑︁

= E𝐻

𝐵(x)𝑊 𝐻 (z0 − x)

x∈Σ𝑛 2#

" ∑︁

= E𝐻

𝐵(x)𝑊 𝐻 ◦τ (z1 − x)

x∈Σ𝑛 2#

" ∑︁

= E𝐻

𝐵(x)𝑊 𝐻 (z1 − x)

 x∈Σ    2 𝐻 = E𝐻 𝐵 ∗ 𝑊 (z1 ) , 𝑛

where the third equality uses Claim 6.9. Then, for any z ∈ Σ𝑛 ,       2 2 1 ∑︁ 𝐻 ′ 𝐻 E𝐻 𝐵 ∗ 𝑊 (z) = 𝑛 E𝐻 𝐵 ∗ 𝑊 (z ) 𝑀 z′ ∈Σ𝑛 " #  ∑︁  2 1 = 𝑛 E𝐻 𝐵 ∗ 𝑊 𝐻 (z′) 𝑀 ′ 𝑛 "z ∈Σ # ∑︁ 2 1 b 𝑊 b 𝐻 (e) = 𝑛 E𝐻 𝑀 𝑛/2 𝐵(e) 𝑀 e∈Σ𝑛 # " ∑︁ 2 b 𝐻 (e) 𝑊 = E𝐻 ≤𝑒

e∈BadErrors √ −Ω( 𝜆)

.

The third equality uses Parseval’s theorem and the convolution theorem; the last inequality is from (13). ♦ Finally, Claims 6.11 and 6.12, together with the definition of 𝑉 , give 2#

" E𝐻

∑︁

∑︁

z∈Σ𝑛

x∈𝐶 ⊥, e∈BadErrors :x+e=z

b 𝐻 (e) 𝑉b (x)𝑊

" = E𝐻

∑︁





𝑉 (z) 𝐵 ∗ 𝑊 𝐻 (z)

2

#

z∈Σ𝑛

1 ∑︁ E𝐻 = |𝐶 | z∈𝐶



𝐵 ∗𝑊

𝐻



2



(z)

√

≤ 𝑒 −Ω( 𝜆) . This proves Equation (14) and completes the proof of Claim 6.8.

37

□

7

Proof of the Min-Entropy Property

Our main result (Theorem 7.1) says that the construction in Section 6.2 provides Ω(𝜆𝑐 ) bits of 𝑐 min-entropy, for some constant 𝑐 < 1/2, as long as the adversary is limited to 2𝑜 (𝜆 ) -many queries. Theorem 7.1 (Certifiable Min-Entropy). Construction 6.2 (which is relative to a biased random 𝑐 oracle) satisfies (𝑄, ℎ ∞ )-certifiable min-entropy (Definition 6.1) for any 𝑄 = 2𝑜 (𝜆 ) and any ℎ ∞ (𝜆) = 𝑜 (𝜆𝑐 ), where 𝑐 < 1/2 is a constant parameter of the list-recoverable code (Section 5.2). As mentioned earlier, the biased random oracle used in Construction 6.2 can be implemented in the standard QROM as described at the start of Section 3.1. Moreover, though perhaps not immediately obvious, the resulting protocol in the QROM retains exactly the same certifiable min-entropy guarantee. So, we have the following corollary. Corollary 7.2. Construction 6.2, instantiated in the QROM, satisfies (𝑄, ℎ ∞ )-certifiable min-entropy 𝑐 (Definition 6.1) for any 𝑄 = 2𝑜 (𝜆 ) and any ℎ ∞ (𝜆) = 𝑜 (𝜆𝑐 ), where 𝑐 < 1/2 is a constant parameter of the list-recoverable code (Section 5.2). We include a proof of Corollary 7.2 in Appendix A. The rest of Section 7 is devoted to proving Theorem 7.1. Let (𝐻, X) be the random variables referring to the random oracle and A’s output respectively, and let (ℎ, x) be generic values that they take. (𝐻, X) are jointly sampled from the following distribution. First 𝐻 ← H , and then X ← A 𝐻 (1𝜆 , 1ℎ∞ ).

7.1

Low-entropy adversaries heavily query correct answers.

First, we prove that if the adversary is able to output a correct answer x with high probability, then they must have given non-negligible query norm to most symbols of x. Intuitively, this is because the adversary must check that most symbols of x actually hash to 0; otherwise, they would output x even when those symbols hash to 1. Lemma 7.3. Let 𝛼 ∈ (0, 1], 𝑝 ∈ (0, 1), and 𝑠 ∈ [𝑛]. Let 𝑄 be the query complexity of A. Recall that 𝐻 is a 𝑝-biased oracle. Then, over the randomness of (𝐻, X), the probability that we sample a pair (ℎ, x) that satisfies all of the following conditions is at most 2 · (1 − 𝑝)𝑠 : 1. There exists a set 𝐼 ⊆ [𝑛], |𝐼 | = 𝑠, such that for all 𝑖 ∈ 𝐼 , 𝛼 . 𝑤 e𝑖,𝑥𝑖 (ℎ) < 4𝑛 2. x has high probability given ℎ: Pr[X = x|𝐻 = ℎ] ≥ 𝛼. 3. x is correct: x ∈ 𝐶 and ℎ(x) = 0. Proof. Let 𝑆 be the set of all pairs (ℎ, x) that satisfy the conditions of Lemma 7.3. Pr[𝑆] is the probability that all the conditions of Lemma 7.3 are satisfied, over the randomness of sampling ℎ ← H and x ← Aℎ . We will show that Pr[𝑆] ≤ 2 · (1 − 𝑝)𝑠 . Next, for each (ℎ, x) ∈ 𝑆, let us construct a set 𝑇ℎ,x of pairs (ℎ′, x). 𝛼 Fix a set 𝐼 ⊆ [𝑛] of size 𝑠 such that for all 𝑖 ∈ 𝐼 , 𝑤 e𝑖,𝑥𝑖 (ℎ) < 4𝑛 . To construct 𝑇ℎ,x , choose any (potentially empty) subset of {(𝑖, 𝑥𝑖 )}𝑖∈𝐼 and reprogram ℎ on these inputs, flipping the output from 0 to 1. Let us call the new oracle ℎ′. Let 𝑇ℎ,x be the set of all pairs (ℎ′, x) that can be constructed in this way. 38

Properties: • The sets 𝑇ℎ,x are disjoint. That is to say, for any two distinct pairs (ℎ 1, x1 ) and (ℎ 2, x2 ) in 𝑆, 𝑇ℎ1,x1 ∩ 𝑇ℎ2,x2 = ∅ . Indeed, for any (ℎ′, x′) ∈ 𝑇ℎ,x , x = x′, and ℎ can be computed from (ℎ′, x′) by reprogramming ℎ′ to map x′ to 0. This procedure computes (ℎ, x) from any (ℎ′, x′) ∈ 𝑇ℎ,x , so the sets 𝑇ℎ,x must be disjoint. • For any (ℎ′, x) ∈ 𝑇ℎ,x , Pr[X = x|𝐻 = ℎ′] ≥

1 · Pr[X = x|𝐻 = ℎ] . 2

(20)

This follows from the swapping lemma (Lemma 3.4) and Lemma 3.1. The adversary samples E E ′ ℎ ℎ their output x by applying a measurement 𝑀 to their final state (either 𝜓𝑄 or 𝜓𝑄 ). Ei h ′E Pr[X = x|𝐻 = ℎ] − Pr[X = x|𝐻 = ℎ′] ≤ TraceDist 𝜓𝑄ℎ , 𝜓𝑄ℎ E E ′ ≤ 𝜓𝑄ℎ − 𝜓𝑄ℎ ∑︁ ∑︁ 2 𝑗 ≤2 𝑤 e𝑖,𝑥 (ℎ) 𝑖 𝑗 ∈[𝑄]

(Lemma 3.1) (Lemma 3.4)

(𝑖,𝑥𝑖 ): ℎ(𝑖,𝑥𝑖 )≠ℎ ′ (𝑖,𝑥𝑖 )

𝛼 ≤2· · |𝐼 | 4𝑛 𝛼 ≤ 2 1 ≤ · Pr[X = x|𝐻 = ℎ], 2 which yields Equation (20) upon rearrangement. Finishing the proof: Now, we will show that Pr[𝑆] ≤ 2 · (1 − 𝑝)𝑠 . ′ Let Pr
𝑇ℎ,x be over the randomness of sampling ℎ′ ← H and x ← Aℎ given ℎ′. Since the sets 𝑇ℎ,x (ℎ,x)∈𝑆 are mutually disjoint, ∑︁   1≥ Pr 𝑇ℎ,x (ℎ,x)∈𝑆

=

∑︁

∑︁

Pr[𝐻 = ℎ′] · Pr[X = x|𝐻 = ℎ′]

(ℎ,x)∈𝑆 (ℎ ′ ,x)∈𝑇ℎ,x

1 · Pr[X = x|𝐻 = ℎ] 2 ′ (ℎ,x)∈𝑆 (ℎ ,x)∈𝑇ℎ,x ∑︁ ∑︁ 1 = Pr[X = x|𝐻 = ℎ] · · Pr[𝐻 = ℎ′] . 2 ′ ≥

∑︁

(ℎ,x)∈𝑆

∑︁

Pr[𝐻 = ℎ′] ·

(ℎ ,x)∈𝑇ℎ,x

39

(By Equation (20))

We compare the internal sum to Pr[𝐻 = ℎ]. Since 𝐻 is 𝑝-biased, Pr[𝐻 (𝑖, 𝑥) = 1] = 𝑝 for any (𝑖, 𝑥) ∈ [𝑛] × Σ. If ℎ′ is obtained from ℎ by reprogramming a subset of coordinates 𝐽 ⊆ 𝐼 from 0 to 1, then   |𝐽 | 𝑝 ′ . Pr[𝐻 = ℎ ] = Pr[𝐻 = ℎ] · 1−𝑝 Summing over all subsets 𝐽 ⊆ 𝐼 , we get ∑︁

′

Pr[𝐻 = ℎ ] = Pr[𝐻 = ℎ] ·

(ℎ ′ ,x)∈𝑇ℎ,x

= Pr[𝐻 = ℎ] ·

∑︁ 

 𝑝 |𝐽 | 1−𝑝

𝐽 ⊆𝐼 𝑠 ∑︁  ∑︁

 𝑝 𝑘 1−𝑝

𝑘=0 𝐽 ⊆𝐼 :|𝐽 |=𝑘 𝑠   ∑︁

𝑠  𝑝  𝑘  1−𝑝  𝑠−𝑘 · 1−𝑝 · 1−𝑝 𝑘 𝑘=0   1−𝑝 𝑠 𝑝 = Pr[𝐻 = ℎ] · 1−𝑝 + 1−𝑝  𝑠 1 . = Pr[𝐻 = ℎ] · 1−𝑝 = Pr[𝐻 = ℎ] ·

Plugging this back into the above inequality gives ∑︁   1≥ Pr 𝑇ℎ,x (ℎ,x)∈𝑆

≥

∑︁

Pr[X = x|𝐻 = ℎ] ·

(ℎ,x)∈𝑆

=

∑︁

Pr[X = x|𝐻 = ℎ] ·

(ℎ,x)∈𝑆

= Pr[𝑆] ·

1 · 2

∑︁

Pr[𝐻 = ℎ′]

(ℎ ′ ,x)∈𝑇ℎ,x

 𝑠 1 1 · Pr[𝐻 = ℎ] · 1−𝑝 2

1  1 𝑠 · . 2 1−𝑝

Rearranging this last display shows that the conditions of Lemma 7.3 are satisfied with probability Pr[𝑆] ≤ 2 · (1 − 𝑝)𝑠 . □

7.2

Query-bounded adversaries cannot heavily query a correct answer.

Here, we prove that if the adversary’s query complexity is 2𝑜 (𝜆 ) , then with overwhelming probability over 𝐻 , A 𝐻 does not heavily query any correct answer x. Heavy querying means that many symbols of x each receive large query norm from A 𝐻 . 𝑐

Lemma 7.4. Let 𝛼 = 𝛼 (𝜆) be any function satisfying 𝛼 (𝜆) ≥ 2−𝑜 (𝜆 ) . Let 𝑄 = 𝑄 (𝜆) be any function 𝑐 satisfying 𝑄 (𝜆) = 2𝑜 (𝜆 ) . Let A be any quantum query algorithm making at most 𝑄 queries. Then, with probability at least 1 − 𝐿 · (1 − 𝑝) 4𝑛/5 over the randomness of 𝐻 , 𝐻 satisfies the following condition: 𝑐

40

For all x such that x is correct (x ∈ 𝐶 and 𝐻 (x) = 0), there exists a set 𝐼 ⊆ [𝑛], |𝐼 | = ⌈𝑛/10⌉, such that for all 𝑖 ∈ 𝐼 , 𝑤 e𝑖,𝑥𝑖 (𝐻 ) <

𝛼 . 4𝑛

Proof. Put 𝑠 = ⌈𝑛/10⌉. Let 𝑆 be the set of oracles that violate the condition of Lemma 7.4. Our goal is to show that Pr[𝑆] ≤ 𝐿 · (1 − 𝑝) 4𝑛/5 . This implies that with probability ≥ 1 − 𝐿 · (1 − 𝑝) 4𝑛/5 , over the randomness of 𝐻 , the condition of Lemma 7.4 is satisfied. Constructing the bad set: For any ℎ ∈ 𝑆, we will construct a set of oracles 𝑇ℎ that includes ′ ℎ as well as exponentially-many “bad” oracles ℎ′ where Aℎ wastes query norm on an incorrect answer xℎ . First, given an ℎ ∈ 𝑆, pick a value xℎ = (𝑥 1, . . . , 𝑥𝑛 ) and a set 𝐼ℎ ⊆ [𝑛] such that: 1. xℎ is correct (xℎ ∈ 𝐶 and ℎ(xℎ ) = 0), and 2. |𝐼ℎ | ≥ 𝑛 − 𝑠 + 1, and for all 𝑖 ∈ 𝐼ℎ , 𝑤 e𝑖,𝑥𝑖 (ℎ) ≥

𝛼 . 4𝑛

Such values of (xℎ , 𝐼ℎ ) must exist because ℎ violates the condition of Lemma √ 7.4. 𝛼 Second, we apply Lemma 4.3 with 𝑀 = {(𝑖, 𝑥𝑖 ) : 𝑖 ∈ 𝐼ℎ }, 𝛽 = 4𝑛 , 𝑘 := ⌈ 𝑛/5⌉, and sufficiently large 𝑛. Then there exists a set 𝐴𝑘 ⊆ 𝑀 such that   𝑘 4𝑛 |𝑀 \ 𝐴𝑘 | ≥ 𝑛 − 𝑠 + 1 − ≥ 2 5 √ and for each ℎ′ ∈ Fℎ (𝑀 \ 𝐴𝑘 ) there are at least 𝑛/5 values of 𝑖 ∈ 𝐼ℎ for which 𝑤 e𝑖,𝑥𝑖 (ℎ′) ≥

𝛽 𝛽 𝛼 ≥ = . 2 2 (8𝑄 |𝑀 |) (8𝑄𝑛) 256𝑄 2𝑛 3

Third, we take 𝑇ℎ = Fℎ (𝑀 \ 𝐴𝑘 ). √ Finally, let us say that Aℎ heavily queries x if there exists a set 𝐼 1 ⊆ [𝑛] of size |𝐼 1 | ≥ 𝑛/5 such that for all 𝑖 ∈ 𝐼 1 , 𝛼 . 𝑤 e𝑖,𝑥𝑖 (ℎ) ≥ 256𝑄 2𝑛 3 ′

The previous discussion shows that for each ℎ′ ∈ 𝑇ℎ , Aℎ heavily queries xℎ . ′

Claim 7.5. For sufficiently large 𝜆, the number of codewords that Aℎ heavily queries is at most 𝐿. Proof of claim. By Lemma 3.3, for any 𝜂 > 0, there are at most (𝑄 2 /𝜂 2 ) inputs (𝑖, 𝑥) ∈ [𝑛] × Σ with query norm 𝑤 e𝑖,𝑥 (ℎ′) ≥ 𝜂. Picking 𝜂 = 256𝑄𝛼 2𝑛3 , gives, for sufficiently large 𝜆, at most 256𝑄 2𝑛 3 𝑄 · 𝛼 2



2

41

≤ 2𝑜 (𝜆 ) ≤ ℓ 𝑐

coordinates (𝑖, 𝑥) such that 𝑤 e𝑖,𝑥 (ℎ) ≥ 256𝑄𝛼 2𝑛3 . √ ′ If Aℎ heavily queries x then at least 𝑛/5 coordinates of x belong to the above list of inputs that have query norm ≥ 256𝑄𝛼 2𝑛3 . Then, the list recoverability property of 𝐶 (Definition 5.1 and lemma 5.2) says that the number of codewords x that satisfy this property is ≤ 𝐿. ♦ Claim 7.6. Any ℎ′ belongs to 𝑇ℎ for at most 𝐿 values of ℎ ∈ 𝑆. Proof of claim. Assume toward contradiction that there are 𝐿 + 1 distinct values of ℎ ∈ 𝑆 such that ℎ′ ∈ 𝑇ℎ . Call them {ℎ 𝑗 : 𝑗 ∈ [𝐿 + 1]}. Let x 𝑗 , also known as xℎ 𝑗 , be the string used to ′ construct 𝑇ℎ 𝑗 . We know that Aℎ heavily queries each x 𝑗 , but there are at most 𝐿 codewords that ′ Aℎ heavily queries. By the pigeonhole principle, there are two different values 𝑗, 𝑗 ′ ∈ [𝐿 + 1] such that x 𝑗 = x 𝑗 ′ . Furthermore, ℎ 𝑗 can be constructed from ℎ′ and x 𝑗 by reprogramming ℎ′ to map x 𝑗 to 0. By the same procedure, ℎ 𝑗 ′ can be constructed from ℎ′ and x 𝑗 ′ . Since x 𝑗 = x 𝑗 ′ , this implies that ℎ 𝑗 = ℎ 𝑗 ′ because they are constructed from (ℎ′, x 𝑗 ) by the same procedure. In summary (ℎ 𝑗 , x 𝑗 ) = (ℎ 𝑗 ′ , x 𝑗 ′ )—a contradiction. Therefore the initial assumption must be false, so in fact there are at most 𝐿 values of ℎ ∈ 𝑆 for which ℎ′ ∈ 𝑇ℎ . ♦ Now we can finish the proof. Since each ℎ′ ∈ H belongs to at most 𝐿 different sets 𝑇ℎ , ∑︁ 𝐿≥ Pr[𝐻 ∈ 𝑇ℎ ] ℎ∈𝑆

∑︁

=

∑︁ Pr[𝐻 = ℎ′]

Pr[𝐻 = ℎ] ·

Pr[𝐻 = ℎ]

ℎ ′ ∈𝑇ℎ

ℎ∈𝑆

.

We claim that for any ℎ ∈ 𝑆, ∑︁ Pr[𝐻 = ℎ′] ℎ ′ ∈𝑇ℎ

Pr[𝐻 = ℎ]

≥



1 1−𝑝

 𝑛−𝑠+1− (𝑘2) .

This holds since 𝑇ℎ is obtained by considering the reprogrammings of all subsets of 𝑀 ′ = 𝑀 \ 𝐴𝑘 . For each 𝐽 ⊆ 𝑀 ′ we have   𝑝 |𝐽 | Pr[𝐻 = ℎ ⊕ 𝐽 ] = . Pr[𝐻 = ℎ] 1−𝑝 Overall,

∑︁ Pr[𝐻 = ℎ′] ℎ ′ ∈𝑇ℎ

Pr[𝐻 = ℎ]

∑︁ Pr[𝐻 = ℎ ⊕ 𝐽 ]

=

𝐽 ⊆𝑀 ′

Pr[𝐻 = ℎ]

=

∑︁ 

   |𝑀 ′ | 𝑝 |𝐽 | 1 = . 1−𝑝 1−𝑝

𝐽 ⊆𝑀 ′

Plugging this into the above inequality gives ∑︁ 𝐿≥ Pr[𝐻 ∈ 𝑇ℎ ] ℎ∈𝑆

=

∑︁

Pr[𝐻 = ℎ] ·

ℎ∈𝑆

≥ Pr[𝑆] ·



1 1−𝑝

∑︁ Pr[𝐻 = ℎ′]

ℎ ′ ∈𝑇ℎ  |𝑀 ′ |

, 42

Pr[𝐻 = ℎ]

which after rearranging yields ′

Pr[𝑆] ≤ 𝐿 · (1 − 𝑝) |𝑀 | ≤ 𝐿 · (1 − 𝑝) 4𝑛/5 .

7.3

□

Finishing the proof

Let us assume toward contradiction that Theorem 7.1 is false. Then there is some 𝑄 = 2𝑜 (𝜆 ) , some ℎ ∞ = 𝑜 (𝜆𝑐 ), some adversary A making 𝑄 queries, and some inverse polynomial function 𝛿 (𝜆) such that 𝑐

Pr 𝐻

h

   i 𝐻 𝜆 ℎ∞ Pr Verify [1 , 1 , A (1 , 1 )] ≠ ⊥ ≥ 𝛿 (𝜆) ∧ 𝐻 ∞ A⊤ (1 , 1 ) ≤ ℎ ∞ (𝜆) = 𝛽 (𝜆) 

𝐻

𝜆

ℎ∞

𝐻

𝜆

ℎ∞





for some non-negligible 𝛽 (𝜆). Let us define 𝛼 (𝜆) = 𝛿 (𝜆) · 2−ℎ∞ (𝜆) and recall that 𝑠 = ⌈𝑛/10⌉. Let us also define two events based on 𝐻 : • Let Event1 be the event that 𝐻 satisfies:     𝐻 𝜆 ℎ∞ (1 , 1 ) ≤ ℎ ∞ (𝜆). Pr Verify𝐻 [1𝜆 , 1ℎ∞ , A 𝐻 (1𝜆 , 1ℎ∞ )] ≠ ⊥ ≥ 𝛿 (𝜆) ∧ 𝐻 ∞ A⊤ (Recall that we assumed this event happens with some non-negligible probability 𝛽 (𝜆).) • Let Event2 be the event that 𝐻 satisfies the following condition: For all x such that x is correct (x ∈ 𝐶 and 𝐻 (x) = 0), there exists a set 𝐼 ⊆ [𝑛] of size 𝑠 such that for all 𝑖 ∈ 𝐼 , 𝛼 . 𝑤 e𝑖,𝑥𝑖 (𝐻 ) < 4𝑛 Finally, let us define an event based on (𝐻, X) as the event that the conditions of Lemma 7.3 (repeated below for convenience) are satisfied. • Let Event3 be the event that (𝐻, X) have values (ℎ, x) that satisfy: 1. Aℎ gives a small total query norm to at least 𝑠 positions of x. I.e., there exists a set 𝐼 ⊆ [𝑛] of size 𝑠 such that for all 𝑖 ∈ 𝐼 , 𝑤 e𝑖,𝑥𝑖 (𝐻 ) <

𝛼 . 4𝑛

2. x has high probability given ℎ: Pr[X = x|𝐻 = ℎ] ≥ 𝛼. 3. x is correct: x ∈ 𝐶 and ℎ(x) = 0. As 𝛼 (𝜆) = 𝛿 (𝜆)·2−ℎ∞ (𝜆) = 2−𝑜 (𝜆 ) satisfies the conditions of Lemma 7.4 we get that Pr𝐻 [Event2 ] is overwhelming, namely Pr [Event2 ] ≥ 1 − 𝐿 · (1 − 𝑝) 4𝑛/5 . 𝑐

𝐻

With that, we derive a lower bound on Pr𝐻 [Event1 ∧ Event2 ]. Pr [Event1 ∧ Event2 ] ≥ Pr [Event1 ] − Pr [¬Event2 ] 𝐻

𝐻

43

𝐻

≥ 𝛽 (𝜆) − 𝐿 · (1 − 𝑝) 4𝑛/5 ≥ 𝛽 (𝜆)/2 . where in the last inequality we used the fact that 𝛽 (𝜆) is non-negligible while 𝐿 · (1 − 𝑝) 4𝑛/5 is negligible. Toward contradiction, our goal will be to derive a lower bound on Pr𝐻,X [Event3 ] showing it is at least Pr𝐻 [Event1 ∧ Event2 ] · 𝛼 (𝜆). Toward this end, we prove the following lemma. Lemma 7.7. Let ℎ be any value of 𝐻 that satisfies Event1 and Event2 . Then there exists an xℎ such that (ℎ, xℎ ) satisfy Event3 .   Proof. The first condition of Event1 is Pr Verify𝐻 [1𝜆 , 1ℎ∞ , A 𝐻 (1𝜆 , 1ℎ∞ )] ≠ ⊥ ≥ 𝛿 (𝜆), which is equivalent to: Pr [X ∈ 𝐶 ∧ 𝐻 (X) = 0|𝐻 = ℎ] ≥ 𝛿 (𝜆). X

Next, 

𝐻 𝜆 ℎ∞ 𝐻 ∞ A⊤ (1 , 1 )







= − log max Pr [X = x|𝐻 = ℎ, (X ∈ 𝐶 ∧ 𝐻 (X) = 0)] . x

X

Furthermore, for any x that is correct with respect to ℎ (x ∈ 𝐶 ∧ ℎ(x) = 0), PrX [X = x, (X ∈ 𝐶 ∧ 𝐻 (X) = 0)|𝐻 = ℎ] X PrX [X ∈ 𝐶 ∧ 𝐻 (X) = 0|𝐻 = ℎ] PrX [X = x|𝐻 = ℎ] = PrX [X ∈ 𝐶 ∧ 𝐻 (X) = 0|𝐻 = ℎ] PrX [X = x|𝐻 = ℎ] . ≤ 𝛿 (𝜆)
𝐻 (1𝜆 , 1ℎ ∞ ) ≤ ℎ (𝜆), which implies that: The second condition of Event1 is 𝐻 ∞ A⊤ ∞   − log max Pr [X = x|𝐻 = ℎ, (X ∈ 𝐶 ∧ 𝐻 (X) = 0)] ≤ ℎ ∞ (𝜆), Pr [X = x|𝐻 = ℎ, (X ∈ 𝐶 ∧ 𝐻 (X) = 0)] =

x

or equivalently,

X

max Pr [X = x|𝐻 = ℎ, (X ∈ 𝐶 ∧ 𝐻 (X) = 0)] ≥ 2−ℎ∞ (𝜆) . x

X

Then there exists an xℎ such that Pr [X = xℎ |𝐻 = ℎ, (X ∈ 𝐶 ∧ 𝐻 (X) = 0)] ≥ 2−ℎ∞ (𝜆) > 0 . X

Furthermore, this xℎ is correct (xℎ ∈ 𝐶 ∧ ℎ(xℎ ) = 0) because otherwise, PrX [X = xℎ |𝐻 = ℎ, (X ∈ 𝐶 ∧ 𝐻 (X) = 0)] = 0. Then   Pr X = xℎ |𝐻 = ℎ ≥ 𝛿 (𝜆) · Pr [X = xℎ |𝐻 = ℎ, (X ∈ 𝐶 ∧ 𝐻 (X) = 0)] X

X −ℎ ∞ (𝜆)

≥ 𝛿 (𝜆) · 2 = 𝛼 (𝜆) .

In summary, if Event1 occurs, then there exists an xℎ such that: 44

• xℎ is correct: xℎ ∈ 𝐶 ∧ ℎ(xℎ ) = 0, and   • PrX X = xℎ |𝐻 = ℎ ≥ 𝛼 (𝜆). Furthermore, since this xℎ is correct, Event2 implies that this xℎ -value also satisfies the following condition: There exists a set 𝐼 ⊆ [𝑛] of size 𝑠 such that for all 𝑖 ∈ 𝐼 , 𝑤 e𝑖,xℎ (𝐻 ) < 𝑖

𝛼 . 4𝑛

This shows that (ℎ, xℎ ) satisfy all the conditions of Event3 .

□

By Lemma 7.7, if Event1 ∧ Event2 occur for some ℎ, then there exists some special xℎ such that (ℎ, xℎ ) satisfy the conditions of Event3 . Furthermore, Event3 guarantees that:   Pr X = xℎ |𝐻 = ℎ ≥ 𝛼 (𝜆) . X

One way to satisfy the conditions of Event3 is to sample an ℎ that satisfies the conditions of Event1 ∧ Event2 and then to sample the particular xℎ value that is guaranteed to satisfy Event3 . The probability of sampling values (h, xℎ ) of this form is ≥ Pr [Event1 ∧ Event2 ] · 𝛼 (𝜆) ≥ 𝐻

and thus Pr [Event3 ] ≥ 𝐻,X

𝛽 (𝜆) · 𝛼 (𝜆) 2

𝛽 (𝜆) · 𝛼 (𝜆) . 2

On the other hand, by Lemma 7.3, Pr [Event3 ] ≤ 2 · (1 − 𝑝)𝑠 . 𝐻,X

Combining the two inequalities, we get that  √  𝑐 4 · (1 − 𝑝)𝑠 ≤ 𝑂 (𝑒 −𝑝𝑛/10 · 2𝑜 (𝜆 ) ) = exp −Ω( 𝑛) = negl(𝜆), 𝛽 (𝜆) ≤ 𝛼 (𝜆) which is a contradiction to the fact that 𝛽 (𝜆) is non-negligible.

8

AI Disclosure

ChatGPT 5.6 was used to refine the parameter choices of the family of FRS codes. All other techniques in this work were human-generated. The authors also brainstormed ideas in conversation with AI, but none of those techniques were used in the paper. Brainstorming with AI brought a lot of interesting approaches and a counterexample to stronger variants of Question 1, but so far the question remains open.

45

9

Acknowledgments

A.C. thanks Boyang Chen for helpful discussions and is grateful for support from the Google Research Scholar program. D.K. was supported in part by AFOSR, NSF CNS-2247727, and a Google Research Scholar award. S.M. thanks Henry Yuen for valuable discussions. A.T. was supported by NSF CAREER award CCF-2145474. This material is based upon work supported by the Air Force Office of Scientific Research under award number FA9550-23-1-0543.

References [AA14]

Scott Aaronson and Andris Ambainis. The need for structure in quantum speedups, 2014.

[AFDF+ 18] Rotem Arnon-Friedman, Frédéric Dupuis, Omar Fawzi, Renato Renner, and Thomas Vidick. Practical device-independent quantum cryptography via entropy accumulation. Nature Communications, 9(1):459, 2018. [AH23]

Scott Aaronson and Shih-Han Hung. Certified randomness from quantum supremacy. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 933–944. ACM, 2023.

[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, October 1997. [BCM+ 21] Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh V. Vazirani, and Thomas Vidick. A cryptographic test of quantumness and certifiable randomness from a single quantum device. Journal of the ACM, 68(5):31:1–31:47, 2021. [BDF+ 11]

Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. Random oracles in a quantum world. In Dong Hoon Lee and Xiaoyun Wang, editors, Advances in Cryptology – ASIACRYPT 2011, pages 41–69, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.

[Ber68]

Elwyn R. Berlekamp. Algebraic Coding Theory. McGraw-Hill, 1968.

[Bha25]

Sreejata Kishor Bhattacharya. Random restrictions of bounded low degree polynomials are juntas. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), pages 17–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025.

[BHV26]

John Bostanci, Andrew Huang, and Vinod Vaikuntanathan. Separating quantum and classical advice with good codes. In 67th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2026. To appear.

[BR93]

Mihir Bellare and Phillip Rogaway. Random oracles are practical: a paradigm for designing efficient protocols. In Proceedings of the 1st ACM Conference on Computer 46

and Communications Security, CCS ’93, page 62–73, New York, NY, USA, 1993. Association for Computing Machinery. [BSdW22] Nikhil Bansal, Makrand Sinha, and Ronald de Wolf. Influence in completely bounded block-multilinear forms and classical simulation of quantum algorithms. In Shachar Lovett, editor, 37th Computational Complexity Conference, CCC 2022, Philadelphia, PA, USA, July 20-23, 2022, volume 234 of LIPIcs, pages 28:1–28:21. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2022. [Col06]

Roger Colbeck. Quantum and Relativistic Protocols for Secure Multi-Party Computation. PhD thesis, University of Cambridge, 2006. Available as arXiv:0911.3814.

[EJPV98]

A. Ekert, R. Jozsa, R. Penrose, and Umesh Vazirani. On the power of quantum computation. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 356(1743):1759–1768, 08 1998.

[GGJL25]

Mika Göös, Tom Gur, Siddhartha Jain, and Jiawei Li. Quantum communication advantage in TFNP. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, page 1465–1475, New York, NY, USA, 2025. Association for Computing Machinery.

[GR08]

Venkatesan Guruswami and Atri Rudra. Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Transactions on Information Theory, 54(1):135–150, 2008.

[GS99]

Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed–Solomon and algebraic-geometry codes. IEEE Transactions on Information Theory, 45(6):1757– 1767, 1999.

[Gut24]

Francisco Escudero Gutiérrez. Influences of fourier completely bounded polynomials and classical simulation of quantum algorithms. Chicago Journal of Theoretical Computer Science, 2024(2), August 2024.

[JSW+ 25]

Stephen P Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V Isakov, Tanuj Khattar, and Ryan Babbush. Optimization by decoded quantum interferometry. Nature, 646(8086):831–836, 2025.

[KRT26]

Dakshita Khurana, Bhaskar Roberts, and Avishay Tal. Certified randomness without structure against shallow-query adversaries. In Proceedings of the 67th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2026). IEEE Computer Society, November 2026. To appear.

[LZ23]

Shachar Lovett and Jiapeng Zhang. Fractional certificates for bounded functions. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, MIT, Cambridge, Massachusetts, USA, January 10-13, 2023, volume 251 of LIPIcs, pages 84:1–84:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.

47

[Mon12]

Ashley Montanaro. Some applications of hypercontractive inequalities in quantum information theory. Journal of Mathematical Physics, 53(12), 2012.

[MS16]

Carl A Miller and Yaoyun Shi. Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices. Journal of the ACM (JACM), 63(4):1–63, 2016.

[MS17]

Carl A Miller and Yaoyun Shi. Universal security for randomness expansion from the spot-checking protocol. SIAM Journal on Computing, 46(4):1304–1335, 2017.

[MVV22]

Urmila Mahadev, Umesh Vazirani, and Thomas Vidick. Efficient certifiable randomness from a single quantum device. arXiv preprint arXiv:2204.11353, 2022.

[NC12]

Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, June 2012.

[PAM+ 10] Stefano Pironio, Antonio Acín, Serge Massar, Antoine Boyer de la Giroday, Dzmitry N. Matsukevich, Peter Maunz, Steven Olmschenk, David Hayes, Le Luo, T. Andrew Manning, and Christopher Monroe. Random numbers certified by Bell’s theorem. Nature, 464(7291):1021–1024, 2010. [Rud07]

Atri Rudra. List Decoding and Property Testing of Error Correcting Codes. Phd dissertation, University of Washington, Seattle, Washington, 2007.

[VV12]

Umesh V. Vazirani and Thomas Vidick. Certifiable quantum dice: Or, true random number generation secure against quantum adversaries. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC ’12), pages 61–76. ACM, 2012.

[WB86]

Lloyd R. Welch and Elwyn R. Berlekamp. Error correction for algebraic block codes. U.S. Patent 4,633,470, 1986.

[YZ24]

Takashi Yamakawa and Mark Zhandry. Verifiable quantum advantage without structure. Journal of the ACM, 71(3):1–50, June 2024.

A

Proof of Corollary 7.2

Here, we show that the min-entropy guarantee of Theorem 7.1 also holds, with identical asymptotic parameters, relative to a standard random oracle that is used to instantiate the biased random oracle of Construction 6.2. The instantiation from a standard random oracle 𝐹 can be thought of as an encoding Enc : F −→ H,

𝐻 𝐹 := Enc(𝐹 ),

where 𝐹 is uniform over regular random oracles and 𝐻 𝐹 has the desired 𝑝-biased random-oracle distribution. This encoding is the one described at the start of Section 3.1: we assume 𝑝 = 2−𝑑 for some integer 𝑑; then 𝐻 𝐹 (𝑥) is defined by representing 𝑥 as a bitstring, truncating 𝐹 (𝑥) to 𝑑 bits, 48

  and finally setting 𝐻 𝐹 (𝑥) = 1 if and only if 𝐹 (𝑥) = 1𝑑 . This way, Pr[𝐻 (𝑥) = 1] = Pr 𝐹 (𝑥) = 1𝑑 = 2−𝑑 = 𝑝. The encoding map is not invertible, but we can define a map that goes the other way, by including precisely the extra randomness in 𝐹 that is not determined by 𝐻 𝐹 : Dec : H × R −→ F ,

𝐹ℎ,𝑟 := Dec(ℎ, 𝑟 ),

with the following properties. First, Enc(𝐹ℎ,𝑟 ) = ℎ

for every ℎ, 𝑟 .

Second, for 𝐻 drawn from the biased distribution and 𝑅 drawn independently, 𝑑

(𝐻, 𝐹𝐻,𝑅 ) = (Enc(𝐹 ), 𝐹 ),

𝐹 ← uniform.

(21)

Third, for every fixed 𝑟 , a query to 𝐹ℎ,𝑟 can be simulated with two queries to ℎ: compute ℎ(𝑥), use it to answer the 𝐹ℎ,𝑟 query, then uncompute ℎ. Now, our goal is to establish a min-entropy guarantee on any quantum algorithm 𝐵 that makes queries to 𝐹 and solves the problem of Construction 6.2, where 𝐹 is used to instantiate the biased oracle 𝐻 . 𝑐 Let us fix any functions 𝑄 (𝜆) = 2𝑜 (𝜆 ) and ℎ ∞ (𝜆) = 𝑜 (𝜆𝑐 ), any 𝐹 -oracle algorithm 𝐵 that makes at most 𝑄 queries to 𝐹 , and any inverse polynomial function 𝛿. Then for any 𝑟 , define an 𝐻 -oracle algorithm 𝐴𝑟 as follows: 𝐴ℎ𝑟 := 𝐵 𝐹ℎ,𝑟 . (22) 𝐴𝑟 simulates each query of 𝐵 to 𝐹ℎ,𝑟 by making two queries to ℎ, as described above. Note that 𝐴𝑟 𝑐 makes at most 𝑄 ′ := 2𝑄 = 2𝑜 (𝜆 ) queries to 𝐻 . Additionally, the output of 𝐵 𝐹ℎ,𝑟 has an identical distribution to the output of 𝐴ℎ𝑟 . In particular, 𝐹 letting 𝐵 ⊤ℎ,𝑟 and 𝐴ℎ⊤,𝑟 denote the respective distributions of outputs conditioned on the output being correct, we have i h   𝐹 max Pr 𝐵 ⊤ℎ,𝑟 = 𝑧 = max Pr 𝐴ℎ⊤,𝑟 = 𝑧 . 𝑧

𝑧

Similarly, if validity of an answer is described by the relation 𝑉 (ℎ, 𝑧), then     Pr 𝑉 (Enc(𝐹ℎ,𝑟 ), 𝐵 𝐹ℎ,𝑟 ) ≠ ⊥ = Pr 𝑉 (ℎ, 𝐴ℎ𝑟 ) ≠ ⊥ . Then the proof of Theorem 7.1 implies that there exists a negligible function 𝛽 (𝜆) such that for any 𝑟 and 𝜆, h  i    Pr Pr 𝑉 (𝐻, 𝐴𝑟𝐻 ) ≠ ⊥ ≥ 𝛿 (𝜆) ∧ max Pr 𝐴𝐻⊤,𝑟 = 𝑧 ≥ 2−ℎ∞ (𝜆) ≤ 𝛽 (𝜆) , (23) 𝐻

𝑧

Note that we can use the same negligible function 𝛽 for any adversary 𝐴𝑟 because the proof of Theorem 7.1 derives the same upper-bound 𝛽 for every 𝑄 ′-query adversary.

49

Then, averaging over 𝑟 ← 𝑅, and using the distribution identity (21), we get h  i   𝐹  Pr Pr 𝑉 (Enc(𝐹 ), 𝐵 𝐹 ) ≠ ⊥ ≥ 𝛿 (𝜆) ∧ max Pr 𝐵 ⊤ = 𝑧 ≥ 2−ℎ∞ (𝜆) 𝑧 𝐹 h  h i i  𝐹𝐻,𝑅 𝐹𝐻,𝑅 −ℎ ∞ (𝜆) = Pr Pr 𝑉 (Enc(𝐹𝐻,𝑅 ), 𝐵 ) ≠ ⊥ ≥ 𝛿 (𝜆) ∧ max Pr 𝐵 ⊤ = 𝑧 ≥ 2 𝑧 𝐻,𝑅 h  i    𝐻 𝐻 −ℎ ∞ (𝜆) = E𝑅 Pr Pr 𝑉 (𝐻, 𝐴𝑅 ) ≠ ⊥ ≥ 𝛿 (𝜆) ∧ max Pr 𝐴⊤,𝑅 = 𝑧 ≥ 2 𝑧

𝐻

≤ E𝑅 [𝛽 (𝜆)] = 𝛽 (𝜆). where the last inequality holds by the guarantee of Equation (23). This shows that the min-entropy guarantee of Equation (23) transfers with the same parameters to any 𝐹 -oracle algorithm 𝐵, up to a factor of 12 in the number of queries, which does not affect the asymptotic statement.

50

Related documents

• Certifying Randomness or its Lack Thereof for General Network Scenarios#1130480
• Deterministic chance#736753
• Randomness is an unavoidably epistemic concept#109107
• A Randomness Test Formalism for Neutral Measures and Beyond#1076398
• Cardy random matrix theory#1115781