Verifiable quantum advantage in extremely low depth

Verifiable quantum advantage in extremely low depth Alexandru Gheorghiu

arXiv:2609.01448v1 [quant-ph] 1 Sep 2026

IBM Research agheorghiu@ibm.com

Abstract. We give a sampling problem that is solvable by shallow quantum circuits, hard for polynomialtime classical algorithms under lattice-based assumptions, and efficiently verifiable by a classical computer. The quantum sampler admits two implementations: one uses log-logarithmic-depth quantum circuits with one- and two-qubit gates, i.e., QNC0 [log log] circuits, while the other uses constant-depth quantum circuits with unbounded fan-in gates, i.e., QAC0 circuits. Our construction can be seen as compiling the Learning with Errors (LWE)-based single-round proof of quantumness of Arabadjieva et al. [AGGM25] to very low depth. The price paid for this compilation is the reliance on less standard, though wellmotivated, assumptions: in addition to the lattice knowledge assumption used in [AGGM25], we require a strengthened variant of the adaptive-hardcore-bit property of LWE, for which we provide supporting evidence. Unlike previous low-depth proofs of quantumness, the quantum computation here requires no mid-circuit measurements or feed-forward: it consists only of running a shallow circuit and sampling from its output distribution. This shows that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.

1

Introduction

A basic goal in quantum complexity theory is to understand how little quantum computation is needed to obtain an advantage over efficient classical algorithms. For such an advantage to provide a convincing test of quantumness, however, a classical verifier should also be able to check it efficiently. Constant-depth quantum circuits are among the most restricted models of quantum computation, yet under plausible assumptions they can still solve classically hard problems. We ask whether their outputs can also retain enough structure for efficient classical verification. A positive answer would broaden our understanding of shallow quantum circuits and mark a step toward more practical tests of quantumness. Let us start by taking stock of the evidence for the power of shallow quantum circuits. Sampling the output distribution of a constant-depth quantum circuit can be hard for polynomial-time classical algorithms under plausible complexity-theoretic assumptions. This was shown by Terhal and DiVincenzo [TD04] and later extended to constant-depth architectures suited to quantum simulators, with hardness holding also on average [MSM17, BVHS+ 18, HHB+ 20]. The later results adapt hardness arguments developed for the broader class of instantaneous quantum polynomial-time (IQP) circuits, whose depth is low but not constant [BJS11, BMS16]. Relative to a black-box random oracle, sampling hardness can even be made unconditional: a constant-depth circuit that queries the oracle can sample from the Fourier spectrum of the oracle’s truth table [Aar10, BBF+ 26]. Beyond the oracle setting, one can prove unconditional separations between quantum circuits and shallow classical circuits [BGK18, CSV21, GS20, HdOSZ26]. Such separations can also be robust to noise [BGKT20] and hold on average rather than only in the worst case [BWKST19]. A complementary line of research by Høyer and Špalek [HŠ05] showed that constant-depth quantum circuits with unbounded fan-out—the class QNC0f —can approximate the quantum Fourier transform and the arithmetic needed for Shor’s algorithm [Sho97].1 With polynomial-time classical pre- and post-processing, 1

Throughout this paper, QNC0 , QNC0 [log log], QAC0 , and QNC0f denote classes of circuits rather than classes of problems. Let us also note why we restrict attention to sampling rather than decision problems: in a sublogarithmicdepth circuit over bounded-arity gates, each output bit depends on at most 2o(log λ) = λo(1) input qubits, so any decision problem solved by such circuits can be simulated classically in subexponential time. In particular, for constant-depth circuits over bounded-arity gates the corresponding decision task is solvable in classical polynomial time, and for log-logarithmic depth in quasipolynomial time 2polylog(λ) .

this yields an efficient factoring algorithm. More recently, Grier, Morris, and Wu showed that constant-depth quantum circuits with unbounded fan-in gates, the class QAC0 , can compute functions in TC0 , the class of constant-depth threshold circuits, when given multiple copies of the input [GMW26]. This is significant because proving lower bounds against TC0 remains a major challenge for current circuit lower-bound techniques, which face barriers such as natural proofs [RR97, NR04]. Shallow quantum circuits can also implement sophisticated cryptographic primitives. For instance, Foxman et al. [FPVY26] showed, under cryptographic assumptions, that pseudorandom unitaries admit exact QNC0f implementations and inverse-polynomial-accuracy QAC0 implementations. In related work, Gheorghiu showed that pseudoentangled states, states that “hide” their entanglement structure, can be prepared by QNC0 circuits, i.e., constant-depth circuits with bounded fan-in and bounded fan-out gates [Ghe26]. Despite these results, our understanding of shallow quantum computation has an important verification gap. No task is known that is simultaneously solvable by QNC0 circuits, hard for general polynomial-time classical computation, and efficiently verifiable by a classical algorithm. Unconditional shallow-circuit separations rule out only correspondingly shallow classical circuits, while generic sampling hardness does not provide an efficient predicate for recognizing a valid sample. The verifiable problems known to be both solvable by shallow quantum circuits and classically hard either require unbounded fan-out gates, as in the Høyer–Špalek setting [HŠ05], or use mid-circuit measurements and classical feed-forward, as in the interactive proofs of quantumness with shallow circuits of Hirahara and Le Gall [HLG21] and of Liu and Gheorghiu [LG22], and in the non-interactive protocol of Chia and Hung [CH23], which in addition uses a black-box random oracle as part of the quantum circuit.2 This leaves the following basic question: Is there a (white-box) problem solvable by QNC0 circuits, classically hard, and efficiently verifiable? We make partial progress toward answering this question by providing a sampling task with the following properties: • it is classically hard under plausible lattice assumptions; • its samples are classically verifiable in polynomial time; • it is solvable by polynomial-width, log-logarithmic-depth quantum circuits (i.e., QNC0 [log log] circuits); • it is solvable by polynomial-width, constant-depth quantum circuits with unbounded fan-in gates (i.e., QAC0 circuits). Since QAC0 ⊆ QNC0f [HŠ05, TT16], the sampling task is also solvable by QNC0f circuits, though we do not emphasize this point: as mentioned, a similar task can already be solved using the Høyer–Špalek result. Our reason for targeting QAC0 is that it appears to be a much weaker class. Whether polynomial-size constantdepth QAC0 circuits can compute parity—equivalently, fan-out—is a long-standing open problem: the best known circuits have exponential size [Ros21]. Polynomial-size QAC0 circuits are known only for fan-out on polylogarithmically many qubits [GMW26], and circuits with few ancilla qubits provably cannot compute parity, even approximately [NPVY24]. By contrast, adding the fan-out gate makes threshold arithmetic exactly computable in constant depth and collapses the resulting depth hierarchy [HŠ05, TT16]. As far as is known, QAC0 lacks precisely the operation that gives QNC0f its power. An important subtlety with such a result concerns circuit width. A polynomial-size circuit on w qubits can always be simulated classically by maintaining its 2w -dimensional state vector. In particular, a circuit whose width is polylogarithmic in a parameter λ has simulation cost at most 2polylog(λ) . It is relatively straightforward to construct such quantum circuits that solve a classically hard problem, produce a verifiable solution, and have log-logarithmic depth. The idea is to use the Cleve–Watrous parallelization of Shor’s algorithm to factor a semiprime with polylogarithmic bit length [CW00]. More concretely, suppose we wish to factor a semiprime represented using polylog(λ) bits. The best known classical algorithms have quasipolynomial cost in λ, namely 2polylog(λ) .3 With the Cleve–Watrous parallelization, however, the corresponding quantum circuit has depth 2

We also note that the Chia and Hung result is not merely a proof of quantumness, but a protocol for certifying the depth of quantum provers [CH23]. 3 This is the case when the semiprime has ω(log3 λ) bits.

2

log(polylog(λ)) = O(log log λ). This is unsatisfactory, however: the construction merely expresses the input length as polylogarithmic in a larger parameter, and with respect to the actual input size the depth remains logarithmic. One could instead ask for polynomially many small semiprimes to be factored in parallel, thereby obtaining polynomial total width while preserving log-logarithmic depth, but the classical running time would remain quasipolynomial.4 We argue that to obtain a genuine separation at polynomial width, we need a task with exponential classical hardness in the security parameter: ideally, no 2o(λ) -time classical algorithm should solve it, while bounded-arity quantum circuits of depth O(log log λ) can. Our construction achieves these properties under the assumptions stated below. Theorem 1.1 (Informal). Assume the subexponential knowledge-of-lattice-point (LK-1/4) assumption (Assumption 5.3) and the adaptive-hardcore-bit assumption with carry predicates (Assumption 6.7). There is a family of sampling problems, indexed by a security parameter λ, whose samples can be verified in classical polynomial time. This is illustrated as a challenge–response task in Protocol 2.1. An honest quantum sampler is accepted with probability 1 − negl(λ) and has two polynomial-size implementations: a QNC0 [log log] circuit over one- and two-qubit gates and a constant-depth QAC0 circuit with unbounded fan-in gates. By contrast, any uniform classical sampler running in time 2o(λ) is accepted with probability at most 3/4 + negl(λ). Both quantum implementations consist of a single unitary circuit followed by a final measurement layer and require neither mid-circuit measurements nor classical feed-forward. Table 1 summarizes how our results compare to previous work on quantum advantage from shallow circuits. The LK-1/4 and carry-predicate assumptions are nonstandard, so we briefly motivate their origins. Our starting point is the LWE-based proof of quantumness of Brakerski et al. [BCM+ 21] (BCMVV), together with the single-round variant of Arabadjieva et al. [AGGM25] (AGGM). A proof of quantumness is a protocol between a classical polynomial-time verifier and a purportedly quantum polynomial-time prover: the verifier issues challenges that an efficient quantum prover can answer, but that no efficient classical prover should answer with comparable success. The original BCMVV protocol has two rounds (four messages) and requires the quantum prover to perform mid-circuit measurements. Single-round variants, consisting of one challenge and one response, can be obtained either in the random-oracle model [BKVV20, YZ24, CH23] or under a knowledge assumption, as in AGGM. The random-oracle route is ill-suited to a low-depth result: because the oracle is a black box, it provides no circuit-depth guarantee. Indeed, a light-cone argument shows that any exact one- and two-qubit-gate implementation of a function with n input bits and one output bit, where the output depends on every input bit, must have depth Ω(log n). We therefore follow AGGM’s fully white-box approach, which is based on the LK assumption. In cryptography, knowledge assumptions are non-falsifiable:5 unlike the hardness of factoring or LWE, they are not efficiently testable by an external challenger. Instead, a knowledge assumption makes a claim about the structure of algorithms—namely, that any algorithm accomplishing a certain task must “know” an associated witness. This is formalized through an efficient extractor, tailored to the algorithm, that recovers the witness from the algorithm’s input and random tape. For intuition, consider a one-way function whose image is a small random subset of its codomain. If an algorithm, given a description of the function, outputs a point in its image, a knowledge assumption asserts that it must have known a corresponding preimage. Such functions are known as extractable one-way functions [CD09, BCPR16]. Knowledge assumptions were introduced by Damgård, who used them to construct a public-key encryption scheme designed to resist chosen-ciphertext attacks (CCA) [Dam92]. Variants were subsequently refined for three-round zero-knowledge arguments [HT98, BP04] and used in succinct non-interactive arguments of knowledge (SNARKs) and practical verifiable-computation systems such as Pinocchio [GGPR13, PHGR13]. Thus, although non-falsifiable, knowledge assumptions have served as a cryptographic design tool for more than three decades. 4

This argument applies to QAC0 as well: factoring these small semiprimes can be done by a constant-depth QAC0 circuit. This is achieved with fan-out gates that act on only polylogarithmically many qubits. Fan-out at that scale can be performed in polynomial-width QAC0 , as shown recently by Grier, Morris, and Wu [GMW26]. 5 This is a technical term; it does not mean that the assumption literally cannot be falsified.

3

Classical hardness

Verifiable

Quantum depth

Mid-circuit meas.

Fan-out

Fan-in

Black box

Sampling hardness [TD04, MSM17, BVHS+ 18, HHB+ 20]

exponential

no

O(1)

no

bounded

bounded

no

Fourier sampling [Aar10, BBF+ 26]

exponential

no

O(1)

no

bounded

bounded

yes

Unconditional separations [BGK18, CSV21, HdOSZ26]

shallow circuits

yes

O(1)

no

bounded

bounded

no

Interactive shallow Clifford circuits [GS20]

NC1 circuits

yes

O(1)

yes

bounded

bounded

no

Parallelized Shor [Sho97, CW00]

exponential

yes

O(log λ)

no

bounded

bounded

no

Factoring with fan-out [HŠ05]

exponential

yes

O(1)

no

unbounded

bounded

no

Interactive proofs of quantumness [HLG21, LG22]

exponential

yes

O(1)

yes

bounded

bounded

no

Proofs of quantum depth [CH23]

exponential

yes

O(1)

yes

bounded

bounded

yes

Single-round proofs of quantumness [AGGM25]

exponential

yes

O(log λ)

no

bounded

bounded

no

This work (QNC0 [log log])

exponential

yes

O(log log λ)

no

bounded

bounded

no

This work (QAC0 )

exponential

yes

O(1)

no

bounded

unbounded

no

Table 1. Comparison with previous work on quantum advantage from shallow circuits. “Classical hardness” is the classical time complexity that the task is conjectured to require, measured in a security parameter λ in which the input size is polynomial. The unconditional separations hold without assumptions but only against shallow classical circuits (the interactive variant of Grier and Schaeffer [GS20] is hard for NC1 circuits), and the hardness of Fourier sampling is unconditional relative to a random oracle; the remaining rows rely on complexity-theoretic or cryptographic assumptions, with the last two using those of Theorem 1.1, which rule out 2o(λ) -time samplers. “Verifiable” indicates whether a classical polynomial-time verifier can check the output. The remaining columns list the quantum resources used: circuit depth, mid-circuit measurements with classical feed-forward, gate fan-out and fan-in, and black-box (random-oracle) access. Green marks an ideal property, yellow an acceptable caveat, and orange and red increasingly significant limitations for the goal of verifiable quantum advantage in low depth. Note that unbounded fan-in is orange because it is viewed as being weaker than unbounded fan-out, which is in red.

The LK assumption is a lattice-based knowledge assumption: roughly, an algorithm that, given a description of a lattice, outputs a noisy lattice point must know the lattice point closest to it. It was introduced in work on CCA-secure somewhat homomorphic encryption [LMSV12]; related lattice-knowledge assumptions have since been used in efficient constructions of lattice-based designated-verifier zero-knowledge SNARKs [GMNO18, ISW21]. Even under the LK assumption, the honest AGGM prover must evaluate a logarithmic-depth circuit. We use randomized encodings to compile the prover’s computation to one that can instead be evaluated either in log-logarithmic depth or in constant depth with unbounded fan-in gates. Classical hardness rests on a subexponential form of the LK assumption of AGGM, as well as an adaptive-hardcore-bit assumption for 4

LWE with carry predicates. Informally, BCMVV proved the classical hardness of their interactive test using an adaptive-hardcore-bit property which follows from LWE. This states that no efficient algorithm, given an LWE public key, can predict a self-chosen parity of the secret non-negligibly better than guessing, subject to an admissibility condition that excludes degenerate choices. Our assumption states that adaptively chosen carry bits do not help: the algorithm may augment its parity with bits that flip when partial sums of the LWE equations are added to values of its choice, making the predicted bit nonlinear in the LWE secret. The carry bits account for the structure that our randomized encoding places in the prover’s equation; the assumption is not currently known to follow from standard LWE, though we provide partial evidence toward such a reduction.

2

Technical Overview

We first recall the BCMVV and AGGM protocols and the LWE-based trapdoor claw-free function, then describe the randomized encoding, the encoded quantum strategy, verification and classical hardness, and the circuit depth, and finally summarize the protocol. BCMVV and AGGM We begin with a brief recap of the proof of quantumness of Brakerski et al. [BCM+ 21]. The protocol uses trapdoor claw-free functions (TCFs) constructed from LWE. A TCF f can be generated and evaluated efficiently and is 2-to-1. Thus, every output y ∈ Im(f ) has exactly two preimages x0 and x1 ; the pair (x0 , x1 ), for which f (x0 ) = f (x1 ) = y, is called a claw. Claw-freeness requires that no efficient algorithm can find such a triple (x0 , x1 , y). For the TCFs used in BCMVV, this property is based on the conjectured intractability of LWE. The description of f is also generated together with a secret trapdoor that enables efficient inversion: given the trapdoor and any y ∈ Im(f ), a polynomial-time algorithm can recover the corresponding claw (x0 , x1 ). We use this idealized description for clarity; the noisy LWE instantiation below has small correctness and boundary errors. BCMVV use a somewhat stronger variant of a standard TCF. In addition to being unable to find a claw, no efficient algorithm should be able, with probability non-negligibly greater than 1/2, to produce an image with a valid preimage as well as an admissible string d satisfying the equation d · (x0 ⊕ x1 ) = 0. This requirement is known as the adaptive-hardcore-bit property (AHCB). Intuitively, given an input-output pair, it is intractable to predict even one bit of information about the other preimage in the claw. Brakerski et al. showed, based on the intractability of LWE, that their TCF construction satisfies this property [BCM+ 21]. We can now describe their protocol. The verifier first samples a TCF satisfying the AHCB property together with its trapdoor, denoted (f, τ ), and sends the description of f to the prover. The prover responds with a point y ∈ Im(f ). The verifier then chooses uniformly between two challenges. In the preimage test, it asks for an x such that f (x) = y. In the equation test, it asks for an admissible string d such that d · (x0 ⊕ x1 ) = 0, where (x0 , x1 ) are the preimages of y. Both conditions can be checked efficiently. For the preimage test, the verifier evaluates f on the prover’s response and checks that the result equals y. For the equation test, it uses the trapdoor τ to recover (x0 , x1 ) from y and checks the equation for d. Any classical prover that succeeds in this protocol with probability non-negligibly greater than 3/4 can be used to violate the AHCB property. By contrast, in this idealized description there is a simple quantum strategy that succeeds with probability 1. Suppressing normalization, the quantum prover first prepares the state X |x⟩|f (x)⟩, x

and measures the second register, obtaining some y ∈ Im(f ). Since f is a TCF, the first register collapses to 1 √ (|x0 ⟩ + |x1 ⟩). 2

(1)

The prover retains this state and sends y to the verifier. Upon receiving the challenge, it measures the state in Equation (1) in either the computational basis (for the preimage test) or the Hadamard basis (for the 5

equation test). Despite its simple structure, the protocol is interactive and requires the prover to keep the state in Equation (1) coherent until it receives the verifier’s challenge. Arabadjieva et al. [AGGM25] show how to replace this interactive protocol with a single-round one using a knowledge assumption. To see the main idea, suppose that the TCF had the following additional property: whenever a classical algorithm produces an image y ∈ Im(f ), an efficient extractor can recover a corresponding preimage from the algorithm’s input and random coins. In essence, this says that a classical prover that evaluates the TCF must “know” the preimage on which the evaluation was performed. The preimage challenge would then no longer be necessary. Instead, the prover could return (y, d) in a single response, and the verifier would only need to check that y is a valid image and that the equation for d is correct. Existing knowledge assumptions do not, however, establish both extractability and the AHCB property for the same function family. AGGM instead use two function families whose public descriptions are computationally indistinguishable. The first is the original TCF f , which satisfies the AHCB property based on LWE. The second is an injective function g for which the knowledge-of-lattice-point (LK) assumption provides the required extractor. Rather than choosing a challenge after receiving y, the verifier chooses one of these functions at the outset and hides this choice in its description. An efficient classical prover cannot tell which function it received and must return (y, d) without a subsequent challenge. For f , the verifier uses its trapdoor to recover the claw and check the equation for d; for g, it uses its trapdoor to check that y is a valid image. If a classical prover succeeds for g, the knowledge assumption gives an extractor that recovers a preimage of y. Indistinguishability transfers this extraction guarantee to f , where the extracted preimage and an accepted equation would violate the AHCB property. An honest quantum prover, by contrast, can obtain y and d by measuring the two registers of its state and can therefore send both values at once without waiting for another message from the verifier. For this reason, the LK extraction guarantee is assumed only for classical algorithms.6 In terms of depth, the AGGM prover must coherently evaluate the LWE-based TCF. Standard implementations have either logarithmic depth or constant depth with unbounded fan-out [GH20]. To obtain a shallow implementation with bounded fan-out, we adapt the randomized encoding for binary affine maps proposed in [Ghe26] to affine maps over a ring. Before explaining this construction, let us first describe the two functions to be encoded: the LWE-based TCF of BCMVV and the extractable function of AGGM. The LWE-based TCF Throughout, we write all vectorial quantities in boldface. In LWE, one is given a matrix A ∈ Zm×n and a vector As + e mod q, where s ∈ Znq is secret, e is a short error vector sampled from q the truncated discrete Gaussian DZmq ,B of parameter B, and q is the modulus. The search variant of LWE asks one to recover s from (A, As + e mod q) [Reg09]. The BCMVV instantiation chooses the secret from {0, 1}n . Its LWE-based TCF is defined by f (b, x) = Ax + b · (As + e) + η

(mod q),

where η ← DZmq ,BP for a width BP ≫ B. It is useful to make the function noise explicit by writing u = As + e

(mod q),

f (b, x; η) = Ax + bu + η

(mod q).

The bit b selects one of two noisy branches. Suppose that branch b = 0 is evaluated at (x0 , η 0 ). Taking x1 = x0 − s and η 1 = η 0 − e on branch b = 1 gives f (0, x0 ; η 0 ) = f (1, x1 ; η 1 ). Such pairs form claws of the function. The function noise η is sampled from a range much wider than that of the LWE error e, so translating it by e preserves all but a negligible fraction of its mass. Consequently, almost 6

While the LK assumption already provides a separation between classical and quantum computations, it is unclear whether it is sufficient, on its own, to obtain a proof of quantumness. This is why the AGGM protocol uses both LK and LWE.

6

every output produced by one branch also occurs on the other. The x-components of the two inputs differ by the secret s, so finding both would reveal s and thereby break search-LWE. Although we omit the details here, one can efficiently sample the LWE instance (A, u) together with a trapdoor that enables efficient inversion of f . The extractable function used by AGGM has the same public affine form, g(b, x; η) = Ax + bu + η

(mod q),

but here the full matrix [A | u] is generated as a single trapdoor matrix, rather than taking u = As + e. Except with negligible probability, every image of this function has a unique preimage over the input and noise ranges considered in the protocol, and the LK assumption says that a classical algorithm producing a valid image must know that preimage. Under LWE, the public descriptions of f and g are computationally indistinguishable to efficient classical provers, so a prover cannot adapt its strategy to the function it receives. A randomized encoding for affine maps over a ring The remaining task is to obtain low-depth implementations of these two functions. Direct evaluation does not suffice: the functions effectively compute long sums modulo q, which require logarithmic depth. Instead, we construct low-depth randomized encodings of these functions. A randomized encoding of a function F is a new randomized function Fb that retains key properties of F . Let M = [A | u] ∈ Zm×t , v = (x, b) ∈ Ztq , t = n + 1. q The affine map that we wish to encode, which computes either f or g, is v 7−→ Mv + η. Each output coordinate is a sum involving essentially every coordinate of v, and each coordinate of v is reused in every row of M. Rather than compute these sums and distribute the inputs directly, the randomized encoding replaces Mv + η by a longer string and defers the global work to a classical decoder. We need three properties. First, the decoder must recover the original output. Second, the encoded string must reveal nothing else: its distribution should depend on (v, η) only through Mv + η. Third, given an input and a compatible encoded string, it must be possible to reconstruct the randomness used to create that string. Shallow implementation also requires locality: every symbol of the longer string should depend on only a constant number of source values, and no source value should be used in more than a constant number of symbols. An encoding with these properties for binary affine maps was given in [Ghe26]; here we generalize it to maps over Zq . To see the basic idea behind the encoding, first consider S(a1 , . . . , at ) = a1 + · · · + at

(mod q).

This is the modulo-q analog of the parity function. Choose independent uniform masks h1 , . . . , ht−1 ∈ Zq , and set h0 = ht = 0. The randomized encoding for S outputs cj = aj + hj−1 − hj

(mod q),

j = 1, . . . , t.

One can think of hj as moving a random amount from position j to position j + 1: it is subtracted from cj and added back into cj+1 . This is why the hj are called path masks: the positions 1, . . . , t form a path, each mask sits on an edge between consecutive positions and shuttles a random amount one step along it, and summing along the path cancels every mask; see Figure 1. Each cj therefore uses only one input and its two neighboring masks. Adding the encoded symbols causes the masks to cancel in adjacent pairs: t X j=1

cj =

t X

aj + (h0 − h1 ) + (h1 − h2 ) + · · · + (ht−1 − ht ) = S(a1 , . . . , at ).

j=1

7

h2

h1

c1 = a1 − h1

c2 = a2 + h1 − h2

h3

c3 = a3 + h2 − h3

c4 = a 4 + h 3

Fig. 1. The path-mask encoding of the sum a1 + a2 + a3 + a4 modulo q, for t = 4. The symbols form a path, and the mask hj lives on the j-th edge: it moves a random amount from position j to position j + 1, subtracted from cj and added to cj+1 . Summing along the path cancels every mask and returns the sum.

Thus, the decoder recovers S, even though each cj is computed locally. The tuple (c1 , . . . , ct ) also hides the individual summands. For any fixed total, it is uniform over all tuples whose coordinates have that total. Given only the total, one can therefore sample c1 , . . . , ct−1 uniformly and choose ct to make the sum correct. Thus, two inputs with the same sum give exactly the same distribution of encoded tuples. Applying this path-mask encoding independently to every row of Mv would handle the long sums, but it would still use the same input vj in every row. We need to avoid this reuse in order to preserve constant locality. To do this, we add a second layer of random masks. For each input coordinate j, choose fresh uniform values rj,1 , . . . , rj,m ∈ Zq and output wj,i = rj,i − rj,i+1

wj,0 = vj + rj,1 ,

(i = 1, . . . , m − 1).

From these symbols, the classical decoder can derive a separately masked version of vj for row i: ej,i = wj,0 − v

i−1 X

wj,i′ = vj + rj,i .

i′ =1

The long prefix sum is performed only by the decoder. The encoder touches vj once, in wj,0 , and every other w-symbol is just the difference of two adjacent masks. ej,i introduces an unwanted correction Mi,j rj,i . We hide and collect these The decoder’s masked value v corrections using the path-mask encoding above. Independently for each row i, choose uniform masks hi,1 , . . . , hi,t−1 , set hi,0 = hi,t = 0, and produce zi,j = Mi,j rj,i + hi,j−1 − hi,j . Adding across row i cancels the h-masks and leaves precisely the unwanted correction: X X zi,j = Mi,j rj,i . j

j

The decoder can therefore recover the i-th coordinate of the matrix product: X X X ej,i − Mi,j v zi,j = Mi,j vj . j

j

j

Finally, the function noise is inserted locally. We replace the first z-symbol in row i by b zi,1 = zi,1 − η i and leave the other symbols unchanged. Since the decoder subtracts the z-symbols, its output becomes X X ej,i − b zi,j = (Mv)i + η i . Mi,j v j

j

8

This completes the encoding of the affine map. The two mask layers address different obstacles. The r-masks prevent one input from feeding every matrix row, while the h-masks break each row’s correction sum into independently computable local terms. The z-symbols. The masks make its distribution depend only on the encoded output consists of all the w- and b decoded value, just as in the addition example. More concretely, for a fixed input the map from the uniform r-masks to the w-string is a bijection, so w is uniform and hides v. Once w and the decoded value are fixed, the h-masks make each row of b z uniform subject only to the required row sum. The masks are also uniquely reconstructible. Given v and an encoded output, one first decodes it to y = Mv + η and obtains η = y − Mv. Restoring zi,1 = b zi,1 + η i , one recovers the r-masks successively from the w-symbols and then the h-masks successively from the z-symbols. Most importantly, the quantum part of this computation is entirely local. Every encoded symbol depends on at most three source words. Conversely, each input word appears once, each r-mask appears in at most two w-symbols and one z-symbol, and each h-mask appears in two adjacent z-symbols; each function-noise word also appears once. All of the prefix sums and row sums occur later in the classical decoder. Once the encoded symbols have been measured, that decoder may copy and reuse them freely. The encoded quantum strategy We can now explain the quantum prover’s strategy in the protocol. As mentioned, the prover will be asked to evaluate an encoding of an affine function. We track the prover’s state through the computation, suppressing normalization and, until they matter, the scratch registers used for the arithmetic. Write Fb(b, x, η; r, h) for the encoded output, the string of all w- and b z-symbols. The prover first prepares a uniform superposition over the branch bit, the input, the function noise, and the two collections of masks, next to an output register initialized to zero: X |b, x, η, r, h⟩|0⟩. b,x,η,r,h

In the shallow construction, the function noise is uniform over a centered interval of power-of-two size. This both preserves the overlap between the two TCF branches and allows its superposition to be prepared exactly using Hadamard gates followed by a fixed modular translation. Second, the prover evaluates the encoding into the output register: X |b, x, η, r, h⟩|Fb(b, x, η; r, h)⟩. b,x,η,r,h

Every symbol of Fb depends on only a constant number of source words, so this step is local. Third, the prover erases the function-noise register. This step is needed because the two sides of a TCF claw use different values of η: if the noise remained, it would become part of the final Hadamard relation below. Since η i enters a single symbol, b zi,1 = Mi,1 r1,i − hi,1 − η i , the local reversible update η i ←− η i + b zi,1 + hi,1 − Mi,1 r1,i maps η i to zero on every basis state of the superposition. After this update, and after uncomputing the arithmetic scratch, the state is X |b, x, 0, r, h⟩|Fb(b, x, η; r, h)⟩; b,x,η,r,h

the noise value survives only inside the output register. Finally, the prover applies Hadamards to the registers containing b, x, r, h and measures everything. All measurements occur at the end; for the analysis it is convenient to view the output register as measured first, which is equivalent because the measurements act on different registers and commute. Measuring the output register yields an encoded string, and the surviving superposition consists of exactly the sources that produce it. Perfect privacy says that the two original preimages of the decoded value induce identical distributions on encoded strings, and randomness reconstruction says that exactly one mask assignment is compatible with 9

each of them. Except for a negligible fraction of boundary and shifted-noise cases, the unmeasured registers are therefore in the state 1 √ (|0, ζ 0 ⟩ + |1, ζ 1 ⟩) , 2

ζ b = Jq (xb ), Jq (r(b) ), Jq (h(b) ) ,

where Jq denotes componentwise binary representation and r(b) , h(b) are the unique masks compatible with the input xb and the measured output; the erased function noise appears in neither string. The string ζ b is the extended preimage on branch b, and (b, ζ b ) the complete extended preimage. The Hadamard measurement of these registers produces a uniformly random direction D and a bit C satisfying C = D · (ζ 0 ⊕ ζ 1 ). The randomized encoding has thus preserved the interference between the two preimages used by the original protocol while making the coherent computation local. Verification and classical hardness The verifier chooses uniformly between the TCF f and its indistinguishable extractable counterpart g. When it chooses g, its trapdoor recovers the decoded preimage, and it checks that the encoded output is a valid encoding of that preimage, masks included (Definition 6.3). When it chooses f , its trapdoor recovers the two original preimages, and randomness reconstruction recovers the corresponding ζ 0 , ζ 1 ; the verifier then checks the stated equation C = D · (ζ 0 ⊕ ζ 1 ), together with an admissibility condition on D (Definition 6.6, analyzed in Appendix A). It is worth writing out what this equation says, because its structure dictates the assumption we make. The two extended preimages differ in three ways. The inputs differ by the LWE secret: x1 = x0 − s. Recall that the encoded input is v = (x, b); the shift means that vj changes by −sj for j ≤ n, while the branch coordinate vn+1 = b changes by +1. The r-masks differ by coordinates of s: once the encoded output is fixed, the first w-symbol of column j determines rj,1 = wj,0 − vj , and the remaining w-symbols fix the differences of adjacent masks, so each input shift propagates down its column with opposite sign: (1)

(0)

rj,i = rj,i + sj

(j ≤ n),

(1)

(0)

rn+1,i = rn+1,i − 1.

The h-masks differ by partial sums of the LWE equations: telescoping the first j symbols of row i gives P P hi,j = j ′ ≤j (Mi,j ′ rj ′ ,i − zi,j ′ ), and across the two branches the r-shifts contribute j ′ ≤j Ai,j ′ sj ′ while restoring the erased noise (η 1 = η 0 − e) contributes ei , so X (1) (0) hi,j = hi,j + σi,j (s), σi,j (s) = ei + Ai,j ′ sj ′ (mod q). j ′ ≤j

The parity D · (ζ 0 ⊕ ζ 1 ) compares such values bitwise. Because the secret is binary, the x- and r-contributions are linear in s, with coefficients the prover can compute from its own transcript. The h-contributions are nonlinear: XORing the binary representations of two values that differ by a modular shift produces the carry pattern of that shift. For instance, adding 1 to 3 turns 0011 into 0100 and flips three bits, while adding 1 to 4 turns 0100 into 0101 and flips one: the flipped bits show how far the carry propagates, and this depends jointly on the shift and on the value being shifted. This is similar in spirit to the crypto dark matter proposals of Boneh et al. [BIP+ 18] and the alternating-moduli constructions that followed [DGH+ 21], which build cryptographic primitives by composing linear functions over two different moduli, a composition that is nonlinear over either modulus; here the two moduli are q and 2. Altogether, the checked equation takes the form M M
(0) (0) C = ⟨a, s⟩ ⊕ β ⊕ di,j · Jq (hi,j ) ⊕ Jq (hi,j + σi,j (s)) . i

j≤n−1

The last column j = n, where σi,n (s) = ui is public, contributes only to the offset bit β. Each carry term (0) is anchored at the branch-0 mask hi,j , the value at which the carry pattern of adding σi,j (s) is read off; 10

we call this value the base point of the term, and, as the example above shows, the same shift produces different carries at different base points. The linear coefficient a, the offset bit β, the bit masks di,j , and the base points are all computable from the public key, one extended preimage, and D, without the secret; the displayed equation is written for branch 0, and the branch-1 preimage gives an equivalent sign-flipped form. Computability without the secret is what will turn a successful classical prover into an adversary for our
(0) (0) assumption. We call each term of the double XOR, i.e., di,j · Jq (hi,j ) ⊕ Jq (hi,j + σi,j (s)) , a carry predicate: (0)

a choice of a row i, a prefix length j, a base point ξ (here ξ = hi,j ), and a selection d of bit positions. The LK assumption provides an extractor that obtains a decoded preimage from any successful classical strategy, and randomness reconstruction extends it to the full string ζ b , masks included. Indistinguishability lets this extraction event be transferred from g to f . Since the verifier chooses the two functions uniformly, an average success probability exceeding 3/4 by more than the reduction error would imply that, with probability correspondingly larger than 1/2, a classical prover both holds an extended preimage and supplies a correct equation of the displayed form. We therefore assume an adaptive hardcore bit with carry predicates: no efficient algorithm, given the public key, can produce a linear function of the secret, a list of carry predicates of its choice, and a prediction of the resulting parity that is correct non-negligibly more often than a random guess, subject to an admissibility condition that excludes degenerate choices. With no carry bits this is the BCMVV adaptive-hardcore-bit property, which follows from LWE; our assumption essentially states that allowing adaptively chosen carry bits does not help. To see what the carry bits add, consider a single carry predicate with base point ξ = 0: it contributes bits of Jq (σi,j (s)), the binary representation of the partial sum itself. The top bit of σi,j (s) is a threshold function of the secret, far outside the linear parities ⟨a, s⟩ ⊕ β that the BCMVV theorem controls. Unfortunately, unlike for the ordinary adaptive hardcore bit, we were not able to derive this statement from standard LWE. Nevertheless, we provide some evidence for why such a reduction might be true in Appendix B. The carry-predicate assumption also implies that the keys of f and g are indistinguishable (the key-mode indistinguishability of Lemma 5.4, with f the equation key and g the image key). A direct reduction converts a distinguisher for the two keys into a predictor for a two-coordinate parity of the binary LWE secret. Thus the two cryptographic assumptions used for classical soundness are LK extraction for g and the carry-predicate assumption for f , with the latter also supplying key-mode indistinguishability. The resulting soundness bound is 3/4 + negl(λ). Circuit depth To see why the prover can perform the evaluation in shallow depth, let q be an L-bit prime, where L = Θ(log2 λ); the parameters are fixed in Section 6.1. Each output symbol of the randomized encoding is the result of only a constant number of additions, subtractions, and multiplications on L-bit words. With bounded-arity gates these operations have depth O(log L), and the encoding’s constant input locality allows all symbol calculations to run in parallel. Since L = Θ(log2 λ), this gives depth O(log log λ). The same local arithmetic can be shown to be implementable in constant depth with fan-out gates of size poly(L) = logO(1) λ. Grier, Morris, and Wu show how to exactly implement fan-out of this size with polynomial-size standard-QAC0 circuits [GMW26]. Together with the constant input locality, this lets all local blocks run in parallel on disjoint registers and yields an exact constant-depth QAC0 implementation. The construction uses only polynomially many source, mask, output, and scratch words, so both implementations have polynomial width. They perform exactly the same encoded computation, produce the same transcript distribution, and use only final measurements. The superposition over inputs and masks can also be prepared with polynomially many parallel blocks of size poly(L). This can once again be done either with bounded-arity gates in log-logarithmic depth or with a QAC0 circuit. The protocol in brief Protocol 2.1 summarizes the steps described in this overview. The formal version, with the parameters and the exact checks, is Protocol 6.11; the formal statement of Theorem 1.1 is Theorem 6.16. The honest quantum prover is accepted with probability 1 − negl(λ), and, under our assumptions, no uniform classical prover of time 2o(λ) is accepted with probability exceeding 3/4 + negl(λ). 11

Protocol 2.1 (Simplified overview protocol). Input: a security parameter λ. 1. Challenge. The verifier samples, with equal probability, either the claw-free function f (b, x; η) = Ax + bu + η (mod q), where u = As + e is an LWE sample, or its extractable counterpart g of the same public form, where [A | u] is a single trapdoor matrix; the two descriptions are computationally indistinguishable. It keeps the trapdoor and sends (A, u) to the prover. 2. Response. The prover prepares a uniform superposition over the branch bit b, the input x, the function noise η, and the encoding masks r, h; evaluates the randomized encoding Fb(b, x, η; r, h) into an output register; erases the function-noise register in place; applies Hadamards to the registers holding (b, x, r, h); and measures all registers. This computation admits both a QNC0 [log log] implementation with one- and two-qubit gates and a constant-depth QAC0 implementation. The prover sends the measured encoded b, the direction D, and the bit C. output y 3. Verification. b decodes to a valid image of g, checked using the trapdoor. – If the verifier sampled g: it accepts if y b—the binary encodings of – If the verifier sampled f : it recovers the two extended preimages ζ 0 , ζ 1 of y the two claw preimages together with their reconstructed masks—using the trapdoor and randomness reconstruction. It accepts if D passes the admissibility test and C = D · (ζ 0 ⊕ ζ 1 ).

3

Related Work

Sampling advantage from shallow circuits As mentioned in the introduction, hardness of classically sampling the outputs of constant-depth quantum circuits was first established by Terhal and DiVincenzo [TD04]. Worst-case and average-case hardness arguments were developed for the low- but not constant-depth IQP model [BJS11, BMS16] and were subsequently brought to constant depth proper, for measurement-based and quenched-Hamiltonian architectures [MSM17, BVHS+ 18, HHB+ 20]. None of these sampling tasks is known to be efficiently verifiable. Proposals that hide a verification secret inside an IQP circuit [SB09, BCJ25] have faced secret-extraction attacks [KM23, GH25], so their classical security remains unsettled. In the black-box setting, Fourier sampling relative to a random oracle is solvable by constant-depth circuits with oracle gates and is unconditionally hard classically [Aar10, RT22, BBF+ 26]; it supports certified randomness, but with a verifier that runs in exponential time [BBF+ 26]. Unconditional separations Bravyi, Gosset, and König proved unconditionally that a relation problem solvable by QNC0 circuits requires logarithmic depth classically [BGK18]. This separation was made noisetolerant [BGKT20], extended to hardness against AC0 circuits [BWKST19] and, in interactive form, against NC1 [GS20], developed into certifiable randomness against low-depth adversaries [CSV21], and generalized to a depth hierarchy for shallow circuits [HdOSZ26]. Unconditional and exponentially large quantum advantages are also known in sample complexity [BBW26, BMSW+ 25]. These tasks are all efficiently verifiable, but their hardness holds only against restricted classical models rather than against all polynomial-time algorithms. Cryptographic tests of quantumness BCMVV introduced the LWE-based test of quantumness underlying our result [BCM+ 21]; Mahadev’s verification protocol and the computational Bell test of KahanamokuMeyer et al. developed closely related forms of classical verification [Mah22, KMCVY22]. Single-round variants were obtained in the random-oracle model [BKVV20, YZ24] or fully white-box by using knowledge assumptions [AGGM25]. On the depth side, Hirahara and Le Gall [HLG21] and Liu and Gheorghiu [LG22] compressed the honest prover of such protocols to constant-depth circuits interleaved with mid-circuit measurements and classical feed-forward, and Chia and Hung combined these ingredients with a random 12

oracle to certify the depth of a quantum device [CH23]. Compared with these works, our honest prover runs a single white-box shallow circuit with one final measurement layer, at the cost of less standard assumptions. Fan-out, fan-in, and shallow arithmetic The distinction between unbounded fan-in and unbounded fan-out goes back to early work on parallel quantum computation [MN01, GHMP02]. Høyer and Špalek showed that fan-out yields constant-depth implementations of the arithmetic behind Shor’s algorithm [HŠ05], building on the logarithmic-depth parallelization of Cleve and Watrous [CW00], and Takahashi and Tani proved the exact collapse of the fan-out depth hierarchy [TT16]. For fan-in, Grier, Morris, and Wu showed that QAC0 circuits can compute TC0 functions when given many copies of the input [GMW26]; our QAC0 compilation uses their exact polylogarithmic fan-out construction. Foxman et al. construct pseudorandom unitaries in these shallow classes [FPVY26], and their use of QAC0 parallels ours: Rosenthal showed that fan-out has approximate constant-depth QAC0 implementations of exponential size [Ros21], and Foxman et al. instantiate a refinement of that construction on blocks of logarithmically many qubits, where its size becomes polynomial and its error inverse-polynomial. In both cases QAC0 supplies fan-out only at small scales—for us, the polylogarithmic arithmetic blocks of the randomized encoding—and the construction is arranged so that no larger fan-out is ever needed. Randomized encodings Randomized encodings with constant locality originate in the work of Applebaum, Ishai, and Kushilevitz on cryptography in NC0 [AIK06]. Our encoding is a q-ary path-mask analog of the binary encoding recently used for constant-depth pseudoentanglement [Ghe26].

4

Discussion

Our results leave open the central question raised in the introduction: can verifiable quantum advantage be achieved with QNC0 circuits? The two implementations we gave approach this question from complementary directions. The bounded-arity implementation has depth O(log log λ), while the constant-depth implementation uses unbounded fan-in gates. Thus, neither gives a constant-depth circuit over only one- and two-qubit gates. There are a few ways one could imagine pushing this construction to a true QNC0 one. First, the reason for the log-logarithmic depth, or the unbounded fan-in, is that we must perform arithmetic on L-bit numbers, where L = polylog(λ). If it were possible to construct analogous functions over a constant-size modulus, then L = O(1) and we would have a QNC0 implementation. Unfortunately, constructing trapdoor claw-free functions over a constant-size modulus has proven difficult. The closest construction is the lossy trapdoor function family of Dao and Jain, based on the Dense-Sparse Learning Parity with Noise (LPN) assumption [DJ25]. In fact, this is precisely what allows the pseudoentanglement construction of [Ghe26] to have a QNC0 implementation. However, the lossy trapdoor functions are not 2-to-1, and the trapdoor there cannot invert the lossy function. Neither property is needed for a pseudoentanglement construction, but both are needed for a verifiable test of quantumness (at least in this formulation). A second possibility is to change the randomized encoding, rather than the TCFs. Specifically, one would need a polynomial-length randomized encoding with the same output- and input-locality properties at the level of individual bits rather than individual q-ary symbols. In particular, every encoded output bit should depend on only a constant number of input and random bits, and every input or random bit should occur in only a constant number of output formulas. To carry over the present proof directly, the encoding should also retain efficient decoding, perfect privacy, and efficient unique randomness reconstruction. The coherent superpositions over the encoding randomness and function noise would have to be preparable in constant depth with bounded-arity gates. Classical soundness would additionally require an analog of the carry-predicate assumption for the resulting encoding. We were not able to find a randomized encoding satisfying all of these properties. A separate cryptographic open problem is to derive Assumption 6.7 from standard LWE. At our parameters, the standard BCMVV reductions already yield key-mode indistinguishability and the adaptive hardcore bit for the original preimages, i.e., the linear version of the property we need. (The quasipolynomial-size modulus 13

easily accommodates the noise gaps these reductions require.) What they do not yield is the tolerance of carry predicates, which let the adversary’s equation involve carry bits of the partial sums of the LWE equations. As mentioned, though, we do provide some evidence that the carry-predicate version of the adaptivehardcore-bit property should indeed hold against classical adversaries. To explain why, we first recall what violating the assumption would mean. A successful adversary, given the public P key, chooses a linear function of the binary LWE secret, a selection of carry bits of the partial sums ei + j ′ ≤j Ai,j ′ sj ′ evaluated at base points of its choice, and a correct prediction of the combined parity, subject to an admissibility condition that excludes degenerate choices. In Appendix B we show that various efficient classical strategies for doing this must fail if LWE is hard. Below, n denotes the length of the binary LWE secret. First, no efficient classical algorithm can, once its base points are chosen, predict these parities, carry bits included, for uniformly random challenges, non-negligibly better than guessing. If one could, rerunning it on many random challenges from the same saved state and applying Goldreich–Levin reconstruction [GL89] would recover the secret in full, contradicting the indistinguishability of the two key modes. Second, a different reduction tolerates an adversary that chooses its own challenges once its base points are fixed, provided it can be rerun from that point to produce many equations that are overwhelmingly often correct and its challenge distribution is not too concentrated: challenges that retain all but n/4 bits of the maximum possible min-entropy still lead to a contradiction. An adversary therefore cannot escape the reduction merely by biasing its choice of challenges. Third, we show that, perhaps unsurprisingly, if the adversary makes no use of the carry predicates, so that its predicted bit is a linear function of the secret, then to succeed it would have to break the ordinary adaptive-hardcore-bit property, even when its choices are fully adaptive. A sharper version also holds: if such an adversary’s predictions have merely inverse-polynomial bias, then having slightly more than n/2 bits of min-entropy in its linear function already yields a contradiction. The proofs turn these predictors directly into key-mode distinguishers and adversaries against the ordinary BCMVV adaptive-hardcore-bit game. The underlying difficulty in proving the full carry-predicate version outright is the nonlinear dependence of the checked equation on the secret: the privacy and randomness-reconstruction properties of the randomized encoding are not enough to map it back to the BCMVV hardcore bit. A possible way to avoid the adaptive hardcore bit altogether would be to base the construction on the proof of quantumness of Kahanamoku-Meyer et al. [KMCVY22] instead of BCMVV: their computational Bell test replaces the hardcore-bit check with a CHSH-style test and needs only the claw-free structure of the trapdoor family. However, that protocol has three rounds of interaction instead of two, and it is unclear whether knowledge assumptions can collapse it to a single round, as is possible with BCMVV [AGGM25]. In terms of practicality, our construction likely cannot be implemented on near-term devices due to the e 4 log6 λ). large width of the circuits involved. A conservative estimate shows that the width of the circuit is O(λ Much of this overhead comes from the encoding masks, together with the workspace used to perform local arithmetic in parallel. Reducing the expansion of the randomized encoding and the workspace needed for its coherent evaluation, without increasing the depth or weakening security, is an important direction for future work.

Statement on AI usage The main ideas for the results in the paper are my own. I have, however, made extensive use of OpenAI’s ChatGPT 5.6 Sol and Anthropic’s Claude Fable in deriving the proofs and in writing this paper (mainly copy-editing, improving phrasing and so on). The carry-predicate form of Assumption 6.7 was proposed by Claude. I had initially expressed the assumption as an adaptive-hardcore-bit property of the randomized encoding of the original trapdoor claw-free function. I then asked Claude for a more self-contained statement, and it reformulated the assumption in terms of carry bits of the partial sums of the LWE equations, stated directly from the public key, with no reference to the encoding. Unfortunately, neither model was able to help me prove it based on LWE (even in conjunction with other assumptions), though they were also unable to disprove it. I have independently checked all the proofs. 14

5

Preliminaries

We fix notation, recall the basic notions of quantum information we use, and define the circuit classes considered in this paper. 5.1

Notation

Vectorial quantities (including bit strings viewed as vectors) and matrices are typeset in boldface. For example, x, η, d, D are vectors, while A, K, M are matrices. Scalars, random variables, sets, register names, and algorithms remain in ordinary math font. Indexed matrix entries retain the bold base symbol, as in Ai,j , while coordinates of vectors are set in italic where the bold form would be cluttered, as in sj for the j-th coordinate of s. Entries of the mask arrays r, h are written like matrix entries, rj,i and hi,j ; when a branch (b) (b) superscript is attached we drop the boldface and write rj,i , hi,j . We write δ j for the j-th standard basis vector, and, for a positive integer N , [N ] = {1, . . . , N }. For an integer q ≥ 2, we write Zq for the ring of integers modulo q and L = ⌈log2 q⌉ for its bit length (in our construction q is chosen with 2L−1 ≤ q < 2L , so this agrees with the parameter L of Section 6.1). For a scalar, vector, or array of elements of Zq , Jq (·) denotes its entrywise canonical L-bit binary encoding, concatenated in the natural order; thus Jq (x) ∈ {0, 1}nL for x ∈ Znq . In our construction, q is an odd prime, so some L-bit strings represent integers at least q; such a string is not the canonical encoding of any ring element, and the verifier rejects any response in which one appears. Binary inner products are over F2 . For a residue a ∈ Zq , centerq (a) denotes its centered integer representative: for even q, it lies in [−q/2, q/2), and for odd q, it lies in [−(q − 1)/2, (q − 1)/2]. We apply this convention coordinatewise to vectors. A negligible function f , denoted f = negl(λ), is a function f : N → R such that f (λ) = o(λ−c ) for every constant c > 0. For λ ∈ N, we write 1λ for the string of λ ones. 5.2

Quantum information

We briefly recall the standard quantum formalism and refer to [NC10] for a complete treatment. The state space of n qubits is the 2n -dimensional complex Hilbert space (C2 )⊗n , with the P computational basis {|x⟩ : x ∈ {0, 1}n } indexed by n-bit strings. A pure state is a unit vector |ψ⟩ = x αx |x⟩ in this space. A quantum circuit is a sequence of gates, unitary operators acting on one or more qubits, followed by measurements. Measuring a register in the computational basis returns outcome x with probability |αx |2 . The Hadamard gate acts on one qubit as H|b⟩ = √12 (|0⟩ + (−1)b |1⟩) for b ∈ {0, 1}; measuring a register in the Hadamard basis means applying H to each of its qubits and then measuring in the computational basis. We use the following standard calculation from LWE-based proofs of quantumness [BCM+ 21]. Measuring the state √12 (|0⟩|ζ 0 ⟩ + |1⟩|ζ 1 ⟩), for ζ 0 , ζ 1 ∈ {0, 1}n , entirely in the Hadamard basis yields a uniformly random string d ∈ {0, 1}n together with a bit c satisfying c = d · (ζ 0 ⊕ ζ 1 ). 5.3

Circuit classes

We use the standard definitions of the circuit classes QNC0 , QAC0 , and QNC0f [AK+ 26]. Throughout, these names refer to classes of circuits rather than classes of problems. A quantum circuit layer is a tensor product of gates acting on pairwise disjoint sets of qubits. The class QNC0 consists of polynomial-size, constant-depth circuits over one- and two-qubit gates. We write QNC0 [log log] when the depth is O(log log λ). The class QAC0 additionally permits generalized Toffoli gates V |x1 , . . . , xt , y⟩ 7−→ |x1 , . . . , xt , y ⊕ i xi ⟩ with an unbounded number of controls; equivalently, it permits generalized controlled-Z after a one-qubit basis change on the target. This is unbounded fan-in. It does not let one qubit participate in several gates in the same layer. 15

The distinct class QNC0f augments bounded-arity constant-depth circuits with the unbounded fan-out gate |s, x1 , . . . , xt ⟩ 7−→ |s, x1 ⊕ s, . . . , xt ⊕ s⟩. Fan-out prepares GHZ states in constant depth, so the content of one register can feed many gates in the same layer. In particular, the fan-out gates on polylogarithmically many qubits used by our constant-depth arithmetic are available directly, so both of our circuit implementations carry over to QNC0f . We keep QAC0 and QNC0f separate throughout. Circuits are classically compiled from the public instance in polynomial time. Ancillas start in computational-basis states, arbitrary one-qubit gates are allowed, and all measurements occur in one final layer. 5.4

Proofs of quantumness

We now formalize the proofs of quantumness discussed in Section 1. We use the single-round formulation of AGGM [AGGM25], consisting of one challenge and one response. Definition 5.1 (Single-round proof of quantumness, based on [BCM+ 21, AGGM25]). A singleround proof of quantumness consists of a classical generator Gen, a classical verifier, and an honest quantum prover, all parameterized by a security parameter λ. The generator produces a pair (k, t) ← Gen(1λ ), where k is the public challenge and t is the private verification data. The prover receives k and returns one classical message, after which the verifier, using t, accepts or rejects. 1. Completeness. The protocol has completeness c(λ) if the honest quantum prover is accepted with probability at least c(λ). 2. Soundness. The protocol has classical soundness at most s(λ) if every fixed uniform7 probabilistic polynomial-time classical prover is accepted with probability at most s(λ) for all sufficiently large λ. The honest prover’s quantum circuit is generated classically from the public challenge; in our case it admits two implementations of the same computation: one over bounded-arity entangling gates, the other over generalized Toffoli gates of unbounded fan-in. 5.5

Learning with Errors

In the Learning with Errors (LWE) problem [Reg09], one is given a matrix A ← Zm×n and a vector q As + e mod q, where s ∈ Znq is secret and e is a short error vector; the decisional variant asks one to distinguish this pair from (A, u) with u uniform. The (subexponential) LWE assumption states that no efficient (even subexponential-time) classical or quantum algorithm can solve either of these two problems. We do not use LWE as an assumption for our main result, instead relying on the stronger carrypredicate assumption. However, we use LWE to provide partial evidence for the carry-predicate assumption in Appendix B. There, the specific LWE parameters used are explained in more detail. 5.6

Lattice trapdoors

We use the standard LWE trapdoor generator of Micciancio and Peikert [MP12], in the form used by BCMVV [BCM+ 21]. Theorem 5.2 (Trapdoor generation, based on [MP12]). There are polynomial-time algorithms (TrapGen, TrapInv) and a constant cT > 0 with the following properties. For m ≥ cT n log q, (A, tA ) ← TrapGen(1n , 1m , q) 7

Soundness is stated against uniform provers because the LK assumption below, like knowledge assumptions generally, is implausible against non-uniform adversaries with arbitrary auxiliary input [BCPR16].

16

produces a matrix statistically close to uniform together with a trapdoor for bounded-distance inversion. Except on a trapdoor-failure event, if y = Av + e

(mod q),

v ∈ Znq ,

e ∈ Zm q ,

∥ centerq (e)∥2 < rn :=

q CT

p

n⌈log2 q⌉

,

then TrapInv(tA , y) returns the unique pair (v, e) ∈ Znq × Zm q satisfying this bound, for an absolute constant CT > 0 determined by the generator. We choose the constants in the generator so that its public marginal has statistical distance at most 2−Ω(n) from uniform and its trapdoor failure probability is at most 2−Ω(n) . These explicit rates are needed for comparison with the security bounds below, which are subexponential in n. 5.7

The knowledge-of-lattice-point assumption

The public input to the LK experiment is the complete parameter tuple (q, K, n, m, Q, W ), where Q and W are the input and noise domain bounds fixed in Section 6.1; thus the modulus and domain bounds are available to both the adversary and extractor. We suppress this metadata in the notation below m×(n+1) and call K the lattice part of the instance. For K ∈ Zq , let L(K) = {Kv + qz : v ∈ Zn+1 , z ∈ Zm }. Write λ1 (L(K)) and λ∞ 1 (L(K)) for the length of a shortest nonzero lattice vector in the Euclidean and ℓ∞ norms, respectively. For a generated matrix K outside the trapdoor-failure event, the uniqueness statement in Theorem 5.2 implies λ1 (L(K)) ≥ rn+1 . (2) Indeed, a nonzero lattice vector of Euclidean norm below rn+1 would give √ two distinct bounded-error representations of its residue modulo q. Consequently λ∞ (L(K)) ≥ r / m, which is all we use. We use n+1 1 the online LK-1/4 relation of AGGM [AGGM25], a variant of the lattice knowledge assumption of [LMSV12]: when an algorithm outputs a point within λ∞ 1 (L(K))/4 of the lattice, an online extractor must return the corresponding nearby lattice point. Assumption 5.3 (Subexponential LK-1/4, based on [LMSV12, AGGM25]). There is a constant √ c > 0 such that for every classical algorithm of time at most 2c n in the LK-1/4 experiment, there is an online √ stateful extractor with polynomial overhead and failure probability at most 2−c n , for the trapdoor-matrix ensemble of Section 6.1. The assumption averages over the trapdoor key, the adversary’s random tape, and the extractor’s independent random tape. It is a knowledge assumption and is separate from LWE. Here “online stateful extractor” means a uniform, straight-line classical algorithm given only the public tuple, the adversary code and random tape, and its own independent coins; it receives no trapdoor. Its code can therefore be run unchanged on a syntactically identical equation key; this is used in the soundness proof of Theorem 6.16. 5.8

The AGGM counting argument

Soundness of our protocol rests on the following counting argument, which is the single-round argument of AGGM [AGGM25] stated with explicit error terms. Lemma 5.4 (Counting argument, based on [AGGM25]). Consider a single-round proof of quantumness whose generator chooses uniformly between two public-key modes, an image mode and an equation mode, and fix a classical prover. Suppose that: 17

1. the two key modes have distinguishing advantage at most εhid for every procedure composed from the prover and the extraction procedure below; 2. in image mode there is an extraction procedure, using only public data, that recovers a checked preimage— one verified against the prover’s output by a public validity check—whenever the verifier accepts, except with probability εext ; and 3. in equation mode, the prover together with the extraction procedure produces both such a checked preimage and an accepting equation with probability at most 1/2 + εhc . Then the prover is accepted with probability at most 3 1 + (εhid + εext + εhc ). 4 2 Proof. Let Q be the event that the extraction returns a checked preimage and let E be equation-mode acceptance, both under an equation key. Since the extraction procedure uses only public data, key-mode indistinguishability transfers Q between the two key distributions, so image-mode acceptance is at most Pr[Q] + εext + εhid . Moreover, Pr[Q] + Pr[E] ≤ 1 + Pr[Q ∩ E] ≤

3 + εhc . 2

Since the verifier chooses the two modes uniformly, the prover’s acceptance probability is at most
1 3 1 1 Pr[Q] + εext + εhid + Pr[E] ≤ + (εhid + εext + εhc ), 2 2 4 2 ⊔ ⊓

which is the claimed bound.

In our instantiation, εhid is negligible under the carry-predicate assumption by Lemma 6.10; hence key-mode indistinguishability contributes only a negligible term to the soundness bound. 5.9

Randomized encodings

A randomized encoding of a function F replaces F (v) by the output of a randomized function Fb(v; ρ) that reveals F (v) but nothing else about v. We use the following properties. Definition 5.5 (Randomized encoding, based on [IK00, AIK06]). Let F : V → Y be a function. A function Fb : V × R → Yb is a perfect randomized encoding of F with randomness reconstruction if the following conditions hold. 1. Decoding. There is a function Dec : Yb → Y such that Dec(Fb(v; ρ)) = F (v) for every v ∈ V and ρ ∈ R. 2. Perfect privacy. There is a randomized simulator Sim such that, for every v ∈ V , the distribution of Sim(F (v)) equals the distribution of Fb(v; ρ) for uniform ρ ← R. 3. Randomness reconstruction. There is a function Rrc : V × Yb → R such that, for every v ∈ V and b in the support of Fb(v; ·), ρ = Rrc(v, y b) is the unique element of R with Fb(v; ρ) = y b. every y All three functions are required to be computable in classical polynomial time. Randomized encodings were introduced by Ishai and Kushilevitz [IK00] and developed further, with constant locality, by Applebaum, Ishai, and Kushilevitz [AIK06]; randomness reconstruction is the additional property used in [Ghe26]. For shallow implementations we also track locality: every output symbol should depend on only a constant number of source symbols, and no source symbol should occur in more than a constant number of output formulas. These two properties are the encoding’s constant output locality and constant input locality. 18

6

The Encoded-LWE Sampling Problem

In this section, we give a construction with polynomial width and nearly exponential assumed hardness. Its security is conditional on Assumptions 5.3 and 6.7. The latter is an adaptive-hardcore-bit assumption for LWE in which the adversary may include carry bits of the partial sums of the LWE equations in the parity it must predict; it also implies the key-mode indistinguishability needed for soundness. The randomized encoding supplies the remaining structural properties. The prime-modulus LWE assumption of Appendix B yields the ordinary adaptive-hardcore-bit property of the decoded maps (b, x, η) 7→ Ax + bu + η, used as partial evidence for Assumption 6.7; it is not needed for the main theorem. We fix parameters in Section 6.1, present the randomized encoding and its properties in Section 6.2, and state the carry-predicate assumption in Section 6.3. We then present the protocol in Section 6.4 and prove its completeness, soundness, and circuit bounds in Section 6.5. 6.1

Parameters

Let λ be the security parameter; all parameters are functions of it. Set     L = 4 (log2 (λ + 2))2 , n = 2 c1 (λ2 + λ + L)/2 , m = ⌈c2 (n + 1)L⌉,

(3)

where c1 , c2 are sufficiently large for the BCMVV and trapdoor theorems. Sample a prime 2L−1 ≤ q < 2L .

(4)

Concretely, the setup tests c3 λL independent uniform odd L-bit candidates, for a sufficiently large constant c3 , and, if none is prime, returns a fixed challenge on which the verifier rejects every response. Prime density bounds make this abort probability 2−Ω(λ) , while keeping strict polynomial worst-case generation time. We assume LK-1/4 √ and the carry-predicate assumption are √ secure for this parameter ensemble against adversaries of time 2c n , with failure or advantage at most 2−c n , for a fixed constant c > 0; both assumptions are thus subexponential in the binary-secret dimension n. The LWE assumption used only for the partialevidence results is stated in Appendix B. Since n = Θ(λ2 ), the assumed security level is 2Θ(λ) in the 2 security parameter. The modulus q = 2Θ(log λ) is quasipolynomial in the security parameter, while its bit length remains polylogarithmic. Together with the two superpolynomial noise gaps verified in Appendix C, its primality places the parameters in the BCMVV regime. A uniform Zq register has the exact shallow preparation proved in Lemma 6.12 (Section 6.5). Let CT be the constant of Theorem 5.2, and define rG =

q CT

p

(n + 1)L

,

P =

rG . 2m

Since L = ⌈log2 q⌉, the radius rG equals the inversion radius rn+1 of Theorem 5.2 at dimension n + 1; in particular rG < rn . Further define 
jW = max {1} ∪ j ∈ Z≥1 : 4m2 CT2 (n + 1)L 22j ≤ q 2 , W = 2 jW . (5) This defines a positive integer for every λ. For all sufficiently large λ, the second set in Equation (5) is nonempty, and maximality gives P/2 < W ≤ P . Set Q = 2L/2 ,

BV = 2L/4 .

Let E = {z − W/2 mod q : z = 0, . . . , W − 1}, X = {0, . . . , Q − 1}n , X0 = {1, . . . , Q − 1}n ,

X1 = {0, . . . , Q − 2}n . 19

Thus E is a centered interval of power-of-two size, but it is not a contiguous interval in the canonical binary ordering. Its uniform state is prepared exactly by applying Hadamards to an unsigned index z ∈ {0, . . . , W −1} and reversibly replacing it by η = z −W/2 (mod q). This public translation has bounded-fan-in depth O(log L) and constant QAC0 depth. The calculation in Appendix C (Lemma C.1) gives n = Θ(λ2 ),

mBV 2n + = negl(λ). W Q

m = Θ(λ2 L),

(6)

For the key error we use exactly the BCMVV truncated discrete Gaussian DZq ,BV [BCM+ 21]: its centered weights are proportional to exp(−πz 2 /BV2 ) on |z| ≤ BV , and zero outside this interval. The classical key generator samples this finite distribution to statistical distance at most 2−Ω(n) in polynomial time, using a sampler whose output always lies in the support |z| ≤ BV ; this sampling error is included in the negligible key-generation error below. In equation mode, sample (A, tA ) ← TrapGen(1n , 1m , q),

s ← {0, 1}n ,

e ← DZmq ,BV ,

u = As + e,

so every coordinate of e has centered magnitude at most BV . The decoded map, computable from the public key, is (b, x, η) 7−→ y = Ax + bu + η (mod q), η ∈ Em. In image mode, (K, tK ) ← TrapGen(1n+1 , 1m , q), and the m × (n + 1) matrix is parsed as K = [A | u]; the decoded map has the same form. In either mode, the complete public key is k = (q, n, m, Q, W, A, u). The required indistinguishability of these two key modes follows from the carry-predicate assumption (Lemma 6.10). For an equation key, trapdoor inversion gives the two original preimages related by x1 = x0 − s. We retain only the truncated domains X0 and X1 ; this loses at most 2n/Q honest probability. Shifting the function noise by e loses at most mBV /W . In image mode, W ≤ rG /(2m) places every valid output inside the trapdoor and LK-1/4 decoding radii, as verified explicitly in Lemma 6.15. 6.2

The encoding

Here, we construct a Zq analog of the encoding for binary linear maps used in recent work on constant-depth pseudoentanglement [Ghe26]. m×(n+1) Let M ∈ Zq . For v ∈ Zn+1 , sample independent uniform masks q r = (rj,i )j∈[n+1], i∈[m] ,

h = (hi,j )i∈[m], j∈[n] ,

and set hi,0 = hi,n+1 = 0. Define REM (v; r, h) = (w, z) by wj,i = rj,i − rj,i+1

wj,0 = vj + rj,1 , zi,j = hi,j−1 − hi,j + Mi,j rj,i

(j ∈ [n + 1]).

(i ∈ [m − 1]),

(7) (8)

All operations are modulo q. The h-masks are called path masks: the symbols zi,1 , . . . , zi,n+1 of row i form a path, and hi,j sits on the edge between the j-th and (j + 1)-st symbols, subtracted from the first and added to the second, so that summing along the path cancels every mask and leaves the row sum. Lemma 6.1 (Properties of the linear-map encoding). The map in Equations (7) and (8) is a perfect randomized encoding of v 7→ Mv with randomness reconstruction, in the sense of Definition 5.5. Moreover, each output symbol depends on at most three source symbols, and every source symbol occurs in only a constant number of output formulas. 20

Proof. From w, compute ej,i (w) = wj,0 − v

i−1 X

wj,i′ = vj + rj,i .

i′ =1

The path masks telescope, so n+1 X j=1

zi,j =

n+1 X

Mi,j rj,i .

j=1

Consequently the decoder returns X

ej,i (w) − Mi,j v

X

j

zi,j = (Mv)i .

j

For fixed v, the map r 7→ w is a bijection. Conditioned on w, each row of z is uniform subject to the single constraint imposed by the decoded value. This gives a perfect simulator from Mv, as in the path-mask argument above. Given v, w, reconstruct rj,1 = wj,0 − vj , rj,i+1 = rj,i − wj,i . Given r, z, reconstruct the path masks from hi,j = hi,j−1 + Mi,j rj,i − zi,j . The last coordinate checks hi,n+1 = 0. This proves randomness reconstruction. Locality follows directly from Equations (7) and (8). For occurrence, vj occurs once, each rj,i occurs in at most two w-formulas and one z-formula, and each hi,j occurs twice. ⊓ ⊔ Suppressing the metadata (q, n, m, Q, W ) of k in the notation, put Mk = [A | u] and v = (x, b). To add function noise η ∈ E m , replace zi,1 by zi,1 − η i . (9) The decoder then returns Mk v + η = Ax + bu + η. Each noise symbol η i occurs in exactly one output symbol, so the locality and occurrence bounds of Lemma 6.1 persist for the noisy encoding. We write Fbk (b, x, η; r, h) b = (w, b for the complete encoded output, and parse such an output as y z), where b zi,1 = zi,1 − η i and the b, first decode y and compute η = y − Ax − bu. Before other coordinates are unchanged. Given b, x and y invoking the reconstruction algorithm of Lemma 6.1, restore the noiseless symbol by setting zi,1 = b zi,1 + η i

for every i.

(10)

Randomness reconstruction applied to (w, z) then recovers the unique (r, h), including the final-coordinate consistency checks. Thus the complete coins (η, r, h) are efficiently recoverable; applying the noiseless reconstruction directly to (w, b z) would be incorrect. Lemma 6.2 (Privacy of the noisy encoding). For uniform independent r, h, the distribution Fbk (b, x, η; r, h) depends on (b, x, η) only through the decoded value Ax + bu + η. Moreover, for a fixed original input and a fixed encoded output in its support, the encoding coins are unique. Proof. Fix v = (x, b). As in Lemma 6.1, the map r 7→ w is a bijection. Conditioned on w, every row of b z is uniform subject to the single constraint that its decoder equals (Mk v + η)i : subtracting η i from one path symbol changes only that constraint. This gives the same perfect simulator from the decoded value for every (v, η) in its fiber. Uniqueness follows by computing η, restoring Equation (10), and using the reconstruction formulas in Lemma 6.1. ⊔ ⊓ 21

After writing the encoded output, the honest prover clears the function-noise register through the row-local operation η i ←− η i + b zi,1 + hi,1 − Mi,1 r1,i (mod q). (11) Equation (9) makes the new value identically zero on every honest basis state. 6.3

The carry-predicate assumption

We first fix the validity relation used by both the verifier and the security analysis, then define carry predicates and admissibility and state the assumption. We then decompose the verifier’s parity into the form the assumption covers and derive key-mode indistinguishability. Definition 6.3 (Extended preimages and the validity relation). Let ζ = (Jq (x), Jq (r), Jq (h)) ∈ {0, 1}Next ,

Next = L n + m(2n + 1) ,

denote the canonical binary encoding of the registers other than the branch bit; a complete extended preimage b, b, x), let Reck decode y b to y, form the centered residual is a pair (b, ζ). On input (k, y η = y − Ax − bu

(mod q),

reject unless η ∈ E m , restore the symbols in Equation (10), and run randomness reconstruction. It returns b. Define (η, r, h) only if all reconstruction checks pass and recomputing Fbk (b, x, η; r, h) gives exactly y bk (b R y; b, ζ) = 1

(12)

if and only if ζ parses canonically as (Jq (x), Jq (r), Jq (h)), x ∈ Xb , and Reck (b y, b, x) = (η, r, h) succeeds. Definition 6.4 (Paired images). For an equation key with private data t = (tA , s, e), define ExtInvt (b y) as follows. Decode to y, apply TrapInv(tA , y) and TrapInv(tA , y − u), and obtain candidates (x0 , η 0 ) and (x1 , η 1 ). Check x1 = x0 − s, η 0 = η 1 + e, x0 ∈ X0 , x1 ∈ X1 , and the two instances of Equation (12); use Reck to fill in the encoding coins. On success, ExtInvt returns (ζ 0 , ζ 1 ). A valid paired image is an encoded output on which this algorithm succeeds. For an equation key, the trapdoor recovers both extended preimages of an honest encoded output; the algorithm in Definition 6.4 makes this explicit. Honest encoded outputs are valid paired images except on the boundary, shifted-noise-overlap, and trapdoor-failure events quantified below. The verifier’s equation test checks a parity of ζ 0 ⊕ ζ 1 along a direction produced by the prover’s final Hadamard measurement. These parities have a useful structure. Because the secret is binary, the x- and r-registers of the two extended preimages differ by shifts in {0, ±1}, so their contribution to any parity is a linear function of s with coefficients computable from the transcript and either extended preimage. The h-registers differ by partial sums of the LWE equations, and their contribution consists of binary carry bits. The assumption below states that parities of this form are unpredictable. It is stated directly in terms of the public key, with no reference to the encoding. Definition 6.5 (Carry predicates). Fix a public key k. For s′ ∈ {0, 1}n , i ∈ [m], and j ∈ [n], put σi,j (s′ ) = ui −

n X

Ai,j ′ s′j ′

(mod q).

(13)

j ′ =j+1

A carry predicate is a tuple p = (i, j, ξ, d) with i ∈ [m], j ∈ [n − 1], ξ ∈ Zq (the base point), and 0 ̸= d ∈ {0, 1}L . A predicate list P is a finite set of carry predicates with pairwise distinct index pairs (i, j). For a sign χ ∈ {±1}, define ΦχP : {0, 1}n → {0, 1} by M

ΦχP (s′ ) = d · Jq (ξ) ⊕ Jq ξ + χ σi,j (s′ ) . (14) (i,j,ξ,d)∈P

22

The key alone. At s′ = s it equals the partial sum P map σi,j of Equation (13) is defined from the public ′ ei + j ′ ≤j Ai,j ′ sj ′ of the i-th LWE equation, while σi,n (s ) = ui is public, which is why the terminal index j = n is excluded from predicate lists. The string Jq (ξ) ⊕ Jq (ξ + ω) consists of the bit positions that flip when ω is added to ξ modulo q; away from the modular wrap it equals Jq (ω) XORed with the vector of carry bits of the addition, so ΦχP (s) is an XOR of selected bits of the partial sums and of their carries, evaluated at base points of the adversary’s choice. The function noise appears nowhere: the error e enters only through the public u. The assumption restricts the adversary’s choices through an admissibility condition. For an integer ν, call a string c ∈ {0, 1}ν balanced if ν 2ν ≤ wt(c) ≤ , 3 3 where wt(c) denotes the Hamming weight of c. Let J = {3L, . . . , n−3L}, which is nonempty for all sufficiently large parameters. Columns within 3L of either end are not used to certify row sensitivity: given the public key, the partial sum σi,j (s) is ei plus at most 3L secret-dependent terms for j < 3L and ui minus at most 3L such terms for j > n − 3L, so predicates placed there depend on few secret coordinates. The proof of Proposition 6.9 uses only that J is nonempty, and 3L is a convenient choice. Let R = { ±2a mod q : 0 ≤ a ≤ L/4 }. We split a bit vector indexed by [n] into two halves, its first and last n/2 coordinates, and a bit vector indexed by [m] into halves after the first ⌊m/2⌋ coordinates. Definition 6.6 (Admissible pairs). Fix an equation key k with private data t = (tA , s, e), a sign χ, a vector a ∈ {0, 1}n , and a predicate list P. Put Ψ (s′ ) = ⟨a, s′ ⟩ ⊕ ΦχP (s′ ) and s(j) = s ⊕ δ j , and define Sj = Ψ (s) ⊕ Ψ (s(j) ) (j ∈ [n]), M
∆ρ,i = d · Jq (ξ + χσi,j (s)) ⊕ Jq (ξ + χσi,j (s) + χρ)

(15) (ρ ∈ R, i ∈ [m]),

(16)

(i,j,ξ,d)∈P j∈J

where the XOR in Equation (16) ranges over the predicates in P with row index i and column index j ∈ J . The bit Sj is the directional derivative of Ψ at s in the direction δ j . The bit ∆ρ,i is the change in ΦχP (s), restricted to the predicates with column index in J , when the i-th key coordinate ui , equivalently the error coordinate ei , is shifted by ρ. The pair (a, P) satisfies the sensitivity condition for χ if both halves of a, both halves of (Sj )j∈[n] , and, for every ρ ∈ R, both halves of (∆ρ,i )i∈[m] are balanced. It satisfies the linearity condition if P = ∅, so that Ψ (s′ ) = ⟨a, s′ ⟩ is linear, and a is nonzero on the half designated for χ: the first n/2 coordinates for χ = +1 and the last n/2 for χ = −1. Write Adm(k, t, χ, a, P) = 1 if (a, P) satisfies either condition. Assumption 6.7 (Adaptive hardcore bit with carry predicates). Let GenEq denote the equation-key generation of Section 6.1. Define  carry Hk,t = (χ, a, P, C) : Adm(k, t, χ, a, P) = 1, C = ⟨a, s⟩ ⊕ ΦχP (s) ,  carry H k,t = (χ, a, P, C) : Adm(k, t, χ, a, P) = 1, C = 1 ⊕ ⟨a, s⟩ ⊕ ΦχP (s) . √

There is a constant c > 0 such that for every quantum algorithm A of time at most 2c n , Pr

carry [A(k) ∈ Hk,t ]−

(k,t)←GenEq (1λ )

Pr

carry

√

[A(k) ∈ H k,t ] ≤ 2−c n .

(k,t)←GenEq (1λ )

In particular, A may choose the sign, the linear function, the predicate list, and C adaptively after seeing the public key; the private data t is used only to evaluate membership in the two sets. As for the BCMVV adaptive hardcore bit, the honest quantum prover does not contradict the assumption: the induced data of a transcript is computed from ζ b , which the prover’s Hadamard measurement consumes in producing D and C. The soundness proof of Theorem 6.16 uses the assumption only against classical algorithms. 23

For P = ∅, the game asks the adversary to predict a self-chosen linear function of the binary secret, and the linearity condition is the retained-branch part of the admissibility requirement d ∈ Gk,0,x0 ∩ Gk,1,x1 of the adaptive-hardcore-bit theorem of BCMVV [BCM+ 21]; the direction set of Equation (19) imposes it at both branches (see Appendix B). That case of the assumption is provable at our parameters from the subexponential prime-modulus LWE assumption, as shown in Appendix B. The content of the assumption is therefore that adaptively chosen carry bits of the partial sums do not help. The carries make ΦχP nonlinear in s, and this nonlinearity is what separates the assumption from the BCMVV theorem. The balance conditions exclude the elementary carry-cancellation attacks analyzed in Appendix A; passing them is not proved to imply hardness, and we do not claim that standard LWE implies this assumption. Because the underlying modulus is prime and the error scales follow the BCMVV hierarchy, the primemodulus LWE assumption of Appendix B supplies key-mode indistinguishability and the ordinary adaptivehardcore-bit property for the decoded maps directly; we prove this, together with three restricted consequences, there. They rule out a classical predictor that commits to its base points and can then be rerun from one saved state on independent uniform challenges (Proposition B.5); a classical sampler that can be repeatedly invoked from the same state and satisfies a pointwise conditional min-entropy bound and overwhelming equation correctness (Proposition B.7); and every adversary restricted to empty predicate lists, in this last case with full adaptivity (Proposition B.8). None of these restricted statements establishes the fully adaptive game above. Assumption 6.7 remains an independent assumption. We now connect the assumption to the protocol. Parse a direction as
D = (Dxj )j∈[n] , (Drj,i )j∈[n+1],i∈[m] , (Dhi,j )i∈[m],j∈[n] , where every displayed block is an L-bit string. Fix a valid paired image and a branch b, write χb = (−1)b , and parse ζ b = (Jq (xb ), Jq (r(b) ), Jq (h(b) )). The induced data of the transcript at branch b is (ab (D), βb (D), Pb (D)), where
M r
(b) (b) Dj,i · Jq (rj,i ) ⊕ Jq (rj,i + χb ) , (17) ab (D)j = Dxj · Jq (xb,j ) ⊕ Jq (xb,j − χb ) ⊕ βb (D) =

M

Drn+1,i ·

i

i
M h (b) (b) Jq (rn+1,i ) ⊕ Jq (rn+1,i − χb ) ⊕ Di,n · i

(b) (b) Jq (hi,n ) ⊕ Jq (hi,n + χb ui ) ,

(18)

(b)

̸ 0, j ≤ n − 1}. All three are computable in deterministic polynomial and Pb (D) = {(i, j, hi,j , Dhi,j ) : Dhi,j = time from (k, b, ζ b , D). Lemma 6.8 (Decomposition). For every valid paired image, every branch b ∈ {0, 1}, and every direction D, D · (ζ 0 ⊕ ζ 1 ) = ⟨ab (D), s⟩ ⊕ βb (D) ⊕ ΦχPbb (D) (s). The proof is in Appendix A, together with a converse (Lemma A.2): every pair (a, P) arises, with βb (D) = 0, as the induced data of a transcript that the adversary can generate itself. The assumption therefore grants the adversary at least the freedom that the protocol exposes, and every pair it ranges over is one that the adversary can realize at some branch. The verifier accepts directions whose induced data is admissible at both branches: 
b k,t,ζ ,ζ = D : Adm k, t, χb , ab (D), Pb (D) = 1 for both b ∈ {0, 1} . G (19) 0 1 Proposition 6.9 (Checkability and density). The predicate Adm is computable in uniform deterministic polynomial time given (k, t). Pointwise for every valid paired image, Pr

D←{0,1}Next

b k,t,ζ ,ζ ] ≤ 2−Ω(n) . [D ∈ /G 0 1

The direction set is evaluated only by the classical verifier, so it does not affect the honest prover’s depth. We prove Proposition 6.9, together with an analysis of the elementary attacks motivating Definition 6.6, in Appendix A. The counting argument also needs key-mode indistinguishability; we show that it already follows from Assumption 6.7. 24

Lemma 6.10 (The carry-predicate assumption implies √ key-mode indistinguishability). Under Assumption 6.7, no uniform quantum algorithm of time 2o( n) distinguishes the public equation and image keys in Section 6.1 with non-negligible advantage. Proof. Suppose that D distinguishes the two public-key modes, and let ∆real be its signed equation-minusimage gap. Let εstat = negl(λ) collect the two public-marginal distances of the trapdoor generators and the finite-precision error-sampling distance. Replacing these distributions by their idealized versions gives KEq = [A | As + e]

and

KIm = [A | u],

where A and u are uniform and s ← {0, 1}n and e ← DZmq ,BV ; all suppressed public metadata is unchanged. Write pEq and pIm for the probabilities that D outputs one in these two experiments. Then ∆real − (pEq − pIm ) ≤ εstat . We construct an adversary B for Assumption 6.7. Fix j1 ∈ [n/2] and j2 ∈ {n/2 + 1, . . . , n}, and let T = {j1 , j2 }. Given an equation key (A, u = As + e), sample g = (gj1 , gj2 ), g′ = (gj′ 1 , gj′ 2 ) ← {0, 1}2 and R ← Zm×2 . Replace the columns AT by R, obtaining A′ , and set q u′ = u − AT g + Rg′ . If g = sT , then [A′ | u′ ] is distributed as KEq when A and e are ideal, and within εstat of it otherwise, with the two replacement secret coordinates given by g′ . If g ̸= sT , some coordinate of sT − g is 1 or −1; hence the discarded uniform columns in AT (sT − g) make u′ uniform and independent of A′ . In that case [A′ | u′ ] is distributed as KIm when A is ideal, and within εstat of it otherwise. Run D on this rerandomized key, let Y be its output, set C = gj1 ⊕ gj2 ⊕ Y, and output (+1, δ j1 ⊕ δ j2 , ∅, C). This output satisfies the linearity condition of Definition 6.6 for every key: the predicate list is empty carry carry and the linear function is nonzero at the first-half coordinate j1 . Membership in Hk,t or H k,t is therefore exactly the test of C against ⟨δ j1 ⊕ δ j2 , s⟩ = sj1 ⊕ sj2 . By data processing, replacing the real public matrix marginal and implemented error sampler by their ideal distributions changes the signed expectation by at most O(εstat ). Let µEq = 1 − 2pEq and µIm = 1 − 2pIm . Among the four choices of g, one equals sT ; of the other three, two have the opposite parity from sT and one has the same parity. Therefore   1 E (−1)C⊕(sj1 ⊕sj2 ) = (µEq − µIm − µIm + µIm ) 4 pIm − pEq = . 2 Up to the statistical error above, the advantage of B is therefore, in absolute value, half the key-distinguishing gap: 1 Adv(B) ≥ |∆real | − O(εstat ). 2 √

The reduction invokes D once and otherwise has polynomial overhead. If√ D runs in time 2o( n) , then for all sufficiently large parameters the reduction runs in time at most 2c n , where c is the constant in Assumption 6.7, contradicting the assumption whenever the original gap is non-negligible. ⊓ ⊔ 6.4

The protocol

Our single-round proof of quantumness is Protocol 6.11 below.

25

Protocol 6.11 (Single-round proof of quantumness from the encoded LWE family). Input: a security parameter λ, in unary. 1. The verifier generates the parameters of Section 6.1, samples a mode mode ← {Eq, Im} uniformly, and generates the corresponding equation or image key. For an equation key it retains t = (tA , s, e); for an image key it retains t = tK . It sends the public key k = (q, n, m, Q, W, A, u) to the prover. 2. The prover prepares a uniform superposition over b ∈ {0, 1},

x ∈ X,

η ∈ Em,

r,

h

as follows: (a) the b-register and the low L/2 qubits of each L-qubit xj -register are Hadamard states, because their side lengths are powers of two; the top L/2 qubits of each xj -register hold the leading zeros of Jq (xj ) and remain |0⟩ until the final Hadamards; (b) each function-noise register is prepared as an unsigned zi ∈ {0, . . . , W − 1} by Hadamards and translated in place to η i = zi − W/2 (mod q); (c) every coordinate of r, h is prepared independently in the exact state |Uq ⟩ using Lemma 6.12. It computes Fbk (b, x, η; r, h) into an output register, applies the operation in Equation (11) to clear η, and clears all arithmetic scratch. It then applies Hadamards to the registers containing (b, x, r, h) and measures all registers; write C ∈ {0, 1} for the outcome on the b-register and D ∈ {0, 1}Next for the b, the direction D, outcome on the registers containing (x, r, h). It sends the verifier the encoded output y the bit C, and the measured scratch registers. b to y. 3. The verifier rejects malformed responses and nonzero scratch registers, and decodes y – if mode = Eq: it runs ExtInvt (b y) (Definition 6.4) and rejects on failure; otherwise it obtains (ζ 0 , ζ 1 ) b k,t,ζ ,ζ (Equation (19)) and and accepts if and only if D ∈ G 0 1 C = D · (ζ 0 ⊕ ζ 1 ). – if mode = Im: it runs TrapInv(t, y) to obtain a candidate (v, η), parses v = (x, b), rejects unless b ∈ {0, 1}, and runs Reck (b y, b, x). It accepts if and only if these steps produce a string ζ satisfying bk (b R y; b, ζ) = 1 (Definition 6.3). All of the honest prover’s measurements are performed at the end. Measuring the encoded output before the Hadamard registers is used only as an equivalent description in the completeness proof; the projectors commute. 6.5

Complexity and security

We first give the exact preparation of the uniform Zq state (Lemma 6.12) and bound the depth and width of the honest prover (Lemma 6.13), then compile it into standard QAC0 (Lemma 6.14), show that an accepting image transcript yields an LK query (Lemma 6.15), and finally prove Theorem 6.16 by the counting argument of Lemma 5.4. Lemma 6.12 (Exact uniform prime-field state). For every public prime satisfying Equation (4), the state q−1 1 X |Uq ⟩ = √ |z⟩ q z=0 has an exact, bounded-arity preparation of depth O(log L) and an exact constant-depth QAC0 preparation. Polynomially many independent copies can be prepared in parallel with the same depth. 26

Proof. Apply Hadamards to obtain the uniform state on {0, . . . , 2L − 1}, and mark a basis string precisely when z < q. The marked weight is q/2L ∈ [1/2, 1). Exact amplitude amplification with phase matching therefore maps this state to its normalized marked projection using a constant number of generalized Grover steps [Høy00]. Symmetry within the marked subspace makes that projection exactly |Uq ⟩. Each marked-subspace phase is implemented by computing the public comparison [z < q], applying the prescribed one-qubit phase to its flag, and uncomputing. A phase about the initial Hadamard state is obtained by conjugating a phase on |0L ⟩ by Hadamards. The phase angles are efficiently computable functions of the known rational q/2L , and arbitrary one-qubit rotations are allowed in our circuit model. Comparisons and the two multi-controlled phases have clean bounded-arity depth O(log L). For the QAC0 implementation, comparison is in uniform TC0 [HAB02]; its standard QNC0f realization uses fan-out only within a poly(L)-size block, and the exact polylogarithmic-fan-out compiler of Grier–Morris–Wu converts it to constant-depth QAC0 [GMW26, Corollary 10]. A multi-controlled phase is obtained by computing its conjunction into one flag, applying the one-qubit phase, and uncomputing. All work registers return to zero, and disjoint copies of the construction run in parallel. ⊔ ⊓ Lemma 6.13 (Encoded circuit complexity). The honest prover in Protocol 6.11 has an exact boundedarity implementation of depth O(log L) = O(log log λ). The source and output registers contain Θ(mnL) = Θ(λ4 L2 ) = Θ(λ4 log4 λ) qubits. A direct parallel reversible implementation has width 2 e e 4 L3 ) = O(λ e 4 log6 λ). O(mnL ) = O(λ

Proof. Every symbol in Equations (7) to (9) uses a constant number of additions, subtractions, and multiplications by public L-bit constants. Standard bounded-fan-in addition and public-constant multiplication e 2 ) reversible workspace per encoded symbol. Distinct encoded symbols use have depth O(log L) and use O(L distinct mask inputs, except for the constant number of occurrences displayed in the formulas, so no dense fan-out tree is needed. All symbols are evaluated in parallel and their scratch is uncomputed before the final Hadamards. Counting the w, z, r, h symbols gives Θ(mn) symbols and proves the claims. The operation in Equation (11) is one further constant composition of the same local arithmetic operations and has the same depth bound. All prime-field mask registers are prepared in parallel by Lemma 6.12, adding O(log L) depth e and only O(L) clean workspace per mask. ⊔ ⊓ We next compile the same prover into standard QAC0 by replacing every fan-out gate of polylogarithmic arity with the exact constant-depth circuit of Grier, Morris, and Wu. Lemma 6.14 (Exact compilation into standard QAC0 ). The honest prover in Protocol 6.11 has an exact, polynomial-size, constant-depth QAC0 implementation. Every circuit layer is a tensor product of gates on pairwise disjoint qubit sets. Proof. First consider one output-symbol formula in Equations (7) to (9). It is a constant composition of addition, subtraction, and multiplication by a public constant on L-bit strings. These operations have uniform polynomial-size TC0 circuits [HAB02]. Their clean reversible implementations are therefore constant-depth QNC0f circuits: exact unbounded fan-out realizes the required threshold and arithmetic operations [HŠ05,TT16]. The local circuit has size poly(L), so every fan-out gate in it has arity at most poly(L) = logO(1) λ. Grier, Morris, and Wu prove that, for every fixed d, fan-out on logd λ targets has an exact polynomial-size, constant-depth standard-QAC0 implementation [GMW26, Corollary 10]. Choose d larger than the fixed 27

exponent in the preceding display and replace every local fan-out gate by that circuit. A layer of the original QNC0f circuit contains disjoint fan-out gates; their replacement circuits use private ancillas and hence run in parallel as a constant number of QAC0 layers. Exact uncomputation returns those ancillas to zero. It remains to run all output-symbol blocks at once. The occurrence bound in Lemma 6.1 lets us make the constant number of copies of each source symbol required by distinct blocks using a constant number of bounded-arity CNOT layers. The blocks then have disjoint supports and can run in parallel. Reversing the copy layers after compute–copy–uncompute clears their ancillas. The row-local operations in Equation (11) use the same compilation and execute in parallel. There are polynomially many blocks, each of polynomial size in λ, so the total size is polynomial and the depth is constant. State preparation, the final Hadamards, and measurement add only constant depth: the translation used to prepare E is one more public-constant arithmetic block of the same kind, and the uniform prime-field mask preparation is constant-depth QAC0 by Lemma 6.12. ⊔ ⊓ The next lemma turns an accepting image-mode transcript into an LK-1/4 query and shows that the extracted lattice point determines the unique valid extended preimage; it supplies the extraction procedure of Lemma 5.4. Lemma 6.15 (Image-mode extraction). Except with negligible probability over an image key, an accepting image transcript gives an LK-1/4 query whose extracted lattice point determines the unique valid extended preimage in polynomial time using only public data. Proof. Except with probability at most q n+1−m for a uniform matrix (plus the trapdoor generator’s statistical error), K has full column rank over Fq . Gaussian elimination over this field then computes a public left inverse BK = In+1

(mod q).

(20)

If the image test accepts, it has found v = (x, b) and η ∈ E m with y = Kv + η. Since every centered coordinate of η has magnitude at most W/2, √ mW rG ∥ centerq (η)∥2 ≤ ≤ √ < rG . 2 4 m Moreover, Equation (2) gives rG λ∞ 1 (L(K)) ≥ √ , m

∥ centerq (η)∥∞ ≤

rG 1 ≤ λ∞ (L(K)). 4m 4 1

We apply Assumption 5.3 to the classical algorithm that runs the prover and outputs the decoded point y; decoding is public and polynomial time, so this algorithm obeys the same time bound up to a polynomial factor, and its online extractor is the one used here and in the soundness proof. Thus the online LK extractor returns the nearby lattice point p ∈ L(K). It need not return its coefficients: reducing modulo q and using Equation (20) recovers v = Bp (mod q). The extraction procedure then checks that b ∈ {0, 1} and x ∈ Xb , computes η = y − p (mod q), and runs Reck on the encoded image. The verifier’s relation check and uniqueness in Lemma 6.2 then give exactly one valid ζ. ⊔ ⊓ We can now state and prove the main result. Theorem 6.16 (Main result). Assume Assumptions 5.3 and 6.7 for the parameter ensemble in Equations (3) and (4). Then Protocol 6.11 is a single-round proof of quantumness (Definition 5.1) with the following properties. 1. Completeness. The honest quantum prover is accepted with probability 1 − negl(λ). It admits both an exact polynomial-size, constant-depth QAC0 implementation and an exact bounded-arity implementation of log-logarithmic depth QNC0 [log log]. Both implementations use only final measurements. 28

2. Soundness. Every fixed uniform probabilistic polynomial-time classical prover is accepted with probability at most 3/4 + negl(λ). Moreover, every fixed uniform classical prover of time 2o(λ) is accepted with probability at most 3/4 + negl(λ) for all sufficiently large λ. In particular, the honest and classical acceptance probabilities are separated by a constant (for example, by at least 1/8) for all sufficiently large λ. Proof. Completeness. The two implementations are given by Lemmas 6.13 and 6.14. For the acceptance probability, first restrict to x0 ∈ X0 , x1 = x0 − s ∈ X1 , and pairs η 0 = η 1 + e lying in E m on both branches. The excluded boundary and shifted-noise mass is at most 2n/Q + mBV /W , as in Equation (6). The two original preimages then have the same decoded image. By Lemma 6.2, they induce identical distributions on encoded outputs, and randomness reconstruction gives one coin string per original preimage and encoded output. Moreover, outside the trapdoor-failure event of A, for each b ∈ {0, 1} there is at most one x with m m y − bu − Ax ∈ E √ , by the uniqueness statement of Theorem 5.2 at dimension n: every η ∈ E has ∥ centerq (η)∥2 ≤ m W/2 < rG < rn . Hence (0, x0 ) and (1, x1 ) are the only sources with noise in E m that map to this output. Conditioned on such an output, the surviving registers are therefore the equal superposition
1 √ |0, ζ 0 ⟩ + |1, ζ 1 ⟩ . 2 The final Hadamards act on all L qubits of every xj -register, so they give a uniform D ∈ {0, 1}Next and a branch outcome satisfying C = D · (ζ 0 ⊕ ζ 1 ) exactly. By Proposition 6.9, the verifier rejects at most a 2−Ω(n) fraction of these directions. In image mode, restrict to x ∈ Xb , which excludes mass at most n/Q. Every retained honest basis state then passes Equation (12) by construction, and trapdoor inversion recovers it within the radius proved in Lemma 6.15. The excluded branch-boundary mass, shifted-noise mass, and prime-sampling abort together contribute negl(λ) by Equation (6) and the 2−Ω(λ) prime-sampling abort bound of Section 6.1; trapdoor, key-sampling, and image-mode full-rank failures are smaller. This proves completeness 1 − negl(λ). Soundness. Fix a classical prover, and let I be image-mode acceptance and E be equation-mode acceptance. In the image experiment, run the online extractor from Lemma 6.15, and let Q be the event that bk (b it returns a tuple (b y, b, ζ b , D, C) satisfying R y; b, ζ b ) = 1. The lemma and Assumption 5.3 give Pr[I] ≤ Pr[Q] + εext Im

Im

√ −Ω( n)

for εext = 2 . The extraction procedure, including the public-left-inverse computation, uses only the public key and the online extractor. The equation/image key indistinguishability established in Lemma 6.10 therefore transfers the event Q: Pr[Q] − Pr[Q] ≤ εkey , Im

Eq

where εkey = negl(λ). In the equation experiment, let Uuniq be the good-key event on which trapdoor inversion is unique throughout the noise radius. Its complement has probability δuniq = 2−Ω(n) . On Q ∩ E ∩ Uuniq , the extracted ζ b equals the branch-b string returned by ExtInvt : Lemma 6.2 rules out a second valid mask string for that branch. Consider the algorithm that computes the induced data of the extracted transcript and outputs
χb , ab (D), Pb (D), C ⊕ βb (D) . carry Whenever Q ∩ E ∩ Uuniq occurs, this output lies in Hk,t : the verifier’s direction test includes the branch-b carry admissibility check, and the parity is correct by Lemma 6.8. The same output lies in H k,t when the direction test passes but the parity is flipped; on extraction failure the algorithm outputs a fixed tuple with a = 0 and an empty predicate list, which is inadmissible. The two sets are disjoint, so Assumption 6.7 implies carry Pr[Q ∩ E] ≤ Pr[Hk,t ] + δuniq ≤ Eq

29

1 1 + εahcb + δuniq , 2 2

√

where εahcb = 2−Ω( n) . Applying Lemma 5.4 with εhid = εkey , extraction failure εext , and hardcore-bit advantage εhc = εahcb /2 + δuniq gives s(λ) ≤

3 3 + O(εext + εkey + εahcb + δuniq ) = + negl(λ). 4 4

The last equality uses key-mode indistinguishability from Lemma 6.10; the rank, trapdoor, key-sampling, LK, and hardcore-bit errors are negligible as well. √ For the time-bounded claim, fix a uniform prover of time 2o(λ) . Since n = Θ(λ2 ), we have n = Θ(λ), so √ the prover runs in time 2o( n) , and the polynomial overhead in the key-hiding, extractor, and hardcore-bit reductions stays below the time bounds of Assumption 5.3 and Assumption 6.7 for all sufficiently large λ. The preceding bound applies unchanged. ⊔ ⊓

References Aar10.

AGGM25.

AIK06. AK+ 26. BBF+ 26.

BBW26. BCJ25.

BCM+ 21.

BCPR16.

BGK18. BGKT20. BIP+ 18.

BJK+ 25.

BJS11.

Scott Aaronson. BQP and the polynomial hierarchy. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC 2010), pages 141–150. ACM, 2010. arXiv:0910.4698. (Pages 1, 4, and 12.) Petia Arabadjieva, Alexandru Gheorghiu, Victor Gitton, and Tony Metger. Single-round proofs of quantumness from knowledge assumptions. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), volume 325 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. arXiv:2405.15736. (Pages 1, 3, 4, 6, 12, 14, 16, and 17.) Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography in NC0 . SIAM Journal on Computing, 36(4):845–888, 2006. Preliminary version in FOCS 2004. (Pages 13 and 18.) Scott Aaronson, Greg Kuperberg, et al. The Complexity Zoo. https://complexityzoo.net, 2026. Accessed August 2026. (Page 15.) Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn, and Avishay Tal. On certified randomness from Fourier sampling or random circuit sampling. Quantum, 10:2002, 2026. arXiv:2111.14846. (Pages 1, 4, and 12.) Marcello Benedetti, Harry Buhrman, and Jordi Weggemans. Provable and verifiable quantum advantage in sample complexity. Physical Review Letters, 136:040601, 2026. arXiv:2502.08721. (Page 12.) Michael J. Bremner, Bin Cheng, and Zhengfeng Ji. Instantaneous quantum polynomial-time sampling and verifiable quantum advantage: Stabilizer scheme and classical security. PRX Quantum, 6:020315, 2025. arXiv:2308.07152. (Page 12.) 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. arXiv:1804.00640. (Pages 3, 5, 12, 15, 16, 20, 24, 37, 38, and 44.) Nir Bitansky, Ran Canetti, Omer Paneth, and Alon Rosen. On the existence of extractable one-way functions. SIAM Journal on Computing, 45(5):1910–1952, 2016. Preliminary version in STOC 2014. (Pages 3 and 16.) Sergey Bravyi, David Gosset, and Robert König. Quantum advantage with shallow circuits. Science, 362(6412):308–311, 2018. arXiv:1704.00690. (Pages 1, 4, and 12.) Sergey Bravyi, David Gosset, Robert König, and Marco Tomamichel. Quantum advantage with noisy shallow circuits. Nature Physics, 16:1040–1045, 2020. arXiv:1904.01502. (Pages 1 and 12.) Dan Boneh, Yuval Ishai, Alain Passelègue, Amit Sahai, and David J. Wu. Exploring crypto dark matter: New simple PRF candidates and their applications. In Theory of Cryptography (TCC 2018), volume 11240 of Lecture Notes in Computer Science, pages 699–729. Springer, 2018. (Page 10.) Shi Bai, Hansraj Jangir, Elena Kirshanova, Tran Ngo, and William Youmans. A quasi-polynomial time algorithm for the extrapolated dihedral coset problem over power-of-two moduli. In Advances in Cryptology—CRYPTO 2025, Part II, volume 16001 of Lecture Notes in Computer Science, pages 416–448. Springer, 2025. (Page 37.) Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings of the Royal Society A, 467:459–472, 2011. arXiv:1005.1407. (Pages 1 and 12.)

30

BKVV20.

Zvika Brakerski, Venkata Koppula, Umesh V. Vazirani, and Thomas Vidick. Simpler proofs of quantumness. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), volume 158 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. arXiv:2005.04826. (Pages 3 and 12.) BKW03. Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM, 50(4):506–519, 2003. arXiv:cs/0010022. (Page 43.) Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd. Average-case complexity versus apBMS16. proximate simulation of commuting quantum computations. Physical Review Letters, 117:080501, 2016. arXiv:1504.07999. (Pages 1 and 12.) BMSW+ 25. Marcello Benedetti, Gabriel Marin-Sanchez, Jordi Weggemans, Matthias Rosenkranz, and Harry Buhrman. Unconditional and exponentially large violation of classicality. CoRR, abs/2511.11008, 2025. (Page 12.) BP04. Mihir Bellare and Adriana Palacio. The knowledge-of-exponent assumptions and 3-round zero-knowledge protocols. In Advances in Cryptology—CRYPTO 2004, volume 3152 of Lecture Notes in Computer Science, pages 273–289. Springer, 2004. (Page 3.) BVHS+ 18. Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz, Robert Raussendorf, and Jens Eisert. Architectures for quantum simulation showing a quantum speedup. Physical Review X, 8:021010, 2018. arXiv:1703.00466. (Pages 1, 4, and 12.) BWKST19. Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal. Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC 2019), pages 515–526. ACM, 2019. arXiv:1906.08890. (Pages 1 and 12.) CD09. Ran Canetti and Ronny Ramzi Dakdouk. Towards a theory of extractable functions. In Theory of Cryptography (TCC 2009), volume 5444 of Lecture Notes in Computer Science, pages 595–613. Springer, 2009. (Page 3.) CH23. Nai-Hui Chia and Shih-Han Hung. Non-interactive classical verification of quantum depth: A fine-grained characterization. IACR Cryptology ePrint Archive, 2023:1911, 2023. (Pages 2, 3, 4, and 13.) CSV21. Matthew Coudron, Jalex Stark, and Thomas Vidick. Trading locality for time: Certifiable randomness from low-depth circuits. Communications in Mathematical Physics, 382(1):49–86, 2021. arXiv:1810.04233. (Pages 1, 4, and 12.) CW00. Richard Cleve and John Watrous. Fast parallel circuits for the quantum Fourier transform. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2000), pages 526–536. IEEE, 2000. arXiv:quant-ph/0006004. (Pages 2, 4, and 13.) Dam92. Ivan Damgård. Towards practical public key systems secure against chosen ciphertext attacks. In Advances in Cryptology—CRYPTO ’91, volume 576 of Lecture Notes in Computer Science, pages 445–456. Springer, 1992. (Page 3.) DGH+ 21. Itai Dinur, Steven Goldfeder, Tzipora Halevi, Yuval Ishai, Mahimna Kelkar, Vivek Sharma, and Greg Zaverucha. MPC-friendly symmetric cryptography from alternating moduli: Candidates, protocols, and applications. In Advances in Cryptology—CRYPTO 2021, volume 12828 of Lecture Notes in Computer Science, pages 517–547. Springer, 2021. (Page 10.) DJ25. Quang Dao and Aayush Jain. Lossy cryptography from code-based assumptions. Journal of Cryptology, 38(4):32, 2025. Preliminary version in CRYPTO 2024; arXiv:2402.03633. (Page 13.) FGKP09. Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami. On agnostic learning of parities, monomials, and halfspaces. SIAM Journal on Computing, 39(2):606–645, 2009. (Page 43.) FPVY26. Ben Foxman, Natalie Parham, Francisca Vasconcelos, and Henry Yuen. Random unitaries in constant (quantum) time. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), volume 362 of Leibniz International Proceedings in Informatics (LIPIcs), pages 61:1–61:25. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026. arXiv:2508.11487. (Pages 2 and 13.) GGPR13. Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct NIZKs without PCPs. In Advances in Cryptology—EUROCRYPT 2013, volume 7881 of Lecture Notes in Computer Science, pages 626–645. Springer, 2013. (Page 3.) GH20. Alexandru Gheorghiu and Matty J. Hoban. On estimating the entropy of shallow circuit outputs. CoRR, abs/2002.12814, 2020. (Page 6.) GH25. David Gross and Dominik Hangleiter. Secret-extraction attacks against obfuscated instantaneous quantum polynomial-time circuits. PRX Quantum, 6:020314, 2025. arXiv:2312.10156. (Page 12.) Ghe26. Alexandru Gheorghiu. Pseudoentanglement in constant depth: How trivial states can have non-trivial entanglement structure. CoRR, abs/2605.31448, 2026. (Pages 2, 6, 7, 13, 18, and 20.)

31

GHMP02.

Frederic Green, Steven Homer, Cristopher Moore, and Christopher Pollett. Counting, fanout and the complexity of quantum ACC. Quantum Information and Computation, 2(1):35–65, 2002. arXiv:quantph/0106017. (Page 13.) GL89. Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way functions. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC 1989), pages 25–32. ACM, 1989. (Pages 14 and 40.) GMNO18. Rosario Gennaro, Michele Minelli, Anca Nitulescu, and Michele Orrù. Lattice-based zk-SNARKs from square span programs. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 556–573. ACM, 2018. (Page 4.) Daniel Grier, Jackson Morris, and Kewen Wu. QAC0 contains TC0 (with many copies of the input). GMW26. CoRR, abs/2601.03243, 2026. (Pages 2, 3, 11, 13, and 27.) GS20. Daniel Grier and Luke Schaeffer. Interactive shallow Clifford circuits: Quantum advantage against NC1 and beyond. In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC 2020), pages 875–888. ACM, 2020. arXiv:1911.02555. (Pages 1, 4, and 12.) HAB02. William Hesse, Eric Allender, and David A. Mix Barrington. Uniform constant-depth threshold circuits for division and iterated multiplication. Journal of Computer and System Sciences, 65(4):695–716, 2002. (Page 27.) HdOSZ26. Min-Hsiu Hsieh, Michael de Oliveira, Sathyawageeswar Subramanian, and Xingjian Zhang. Worst-case depth hierarchy for shallow quantum circuits. CoRR, abs/2606.16425, 2026. (Pages 1, 4, and 12.) HHB+ 20. Jonas Haferkamp, Dominik Hangleiter, Adam Bouland, Bill Fefferman, Jens Eisert, and Juan BermejoVega. Closing gaps of a quantum advantage with short-time Hamiltonian dynamics. Physical Review Letters, 125:250501, 2020. arXiv:1908.08069. (Pages 1, 4, and 12.) HLG21. Shuichi Hirahara and François Le Gall. Test of quantumness with small-depth quantum circuits. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), volume 202 of Leibniz International Proceedings in Informatics (LIPIcs), pages 59:1–59:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. arXiv:2105.05500. (Pages 2, 4, and 12.) Peter Høyer. Arbitrary phases in quantum amplitude amplification. Physical Review A, 62(5):052304, Høy00. 2000. arXiv:quant-ph/0006031. (Page 27.) HŠ05. Peter Høyer and Robert Špalek. Quantum fan-out is powerful. Theory of Computing, 1:81–103, 2005. arXiv:quant-ph/0208043. (Pages 1, 2, 4, 13, and 27.) HT98. Satoshi Hada and Toshiaki Tanaka. On the existence of 3-round zero-knowledge protocols. In Advances in Cryptology—CRYPTO ’98, volume 1462 of Lecture Notes in Computer Science, pages 408–423. Springer, 1998. (Page 3.) IK00. Yuval Ishai and Eyal Kushilevitz. Randomizing polynomials: A new representation with applications to round-efficient secure computation. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2000), pages 294–304. IEEE, 2000. (Page 18.) Yuval Ishai, Hang Su, and David J. Wu. Shorter and faster post-quantum designated-verifier zkSNARKs ISW21. from lattices. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pages 212–234. ACM, 2021. (Page 4.) Gregory D. Kahanamoku-Meyer. Forging quantum data: Classically defeating an IQP-based quantum KM23. test. Quantum, 7:1107, 2023. arXiv:1912.05547. (Page 12.) KMCVY22. Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani, and Norman Y. Yao. Classically verifiable quantum advantage from a computational Bell test. Nature Physics, 18:918–924, 2022. arXiv:2104.00687. (Pages 12 and 14.) LG22. Zhenning Liu and Alexandru Gheorghiu. Depth-efficient proofs of quantumness. Quantum, 6:807, 2022. arXiv:2107.02163. (Pages 2, 4, and 12.) Jake Loftus, Alexander May, Nigel P. Smart, and Frederik Vercauteren. On CCA-secure somewhat LMSV12. homomorphic encryption. In Selected Areas in Cryptography (SAC 2011), volume 7118 of Lecture Notes in Computer Science, pages 55–72. Springer, 2012. (Pages 4 and 17.) Mah22. Urmila Mahadev. Classical verification of quantum computations. SIAM Journal on Computing, 51(4):1172–1229, 2022. Preliminary version in FOCS 2018; arXiv:1804.01082. (Pages 12 and 38.) Cristopher Moore and Martin Nilsson. Parallel quantum computation and quantum codes. SIAM Journal MN01. on Computing, 31(3):799–815, 2001. arXiv:quant-ph/9808027. (Page 13.) MP12. Daniele Micciancio and Chris Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller. In Advances in Cryptology—EUROCRYPT 2012, volume 7237 of Lecture Notes in Computer Science, pages 700–718. Springer, 2012. (Page 16.)

32

MSM17.

NC10. NPVY24.

NR04. PHGR13. Reg09. Ros21.

RR97. RT22. SB09. Sho97.

TD04.

TT16. YZ24.

A

Jacob Miller, Stephen Sanders, and Akimasa Miyake. Quantum supremacy in constant-time measurementbased computation: A unified architecture for sampling and verification. Physical Review A, 96:062320, 2017. arXiv:1703.11002. (Pages 1, 4, and 12.) Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 10th anniversary edition, 2010. (Page 15.) Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, and Henry Yuen. On the Pauli spectrum of QAC0 . In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), pages 1498–1506. ACM, 2024. arXiv:2311.09631. (Page 2.) Moni Naor and Omer Reingold. Number-theoretic constructions of efficient pseudo-random functions. Journal of the ACM, 51(2):231–262, 2004. (Page 2.) Bryan Parno, Jon Howell, Craig Gentry, and Mariana Raykova. Pinocchio: Nearly practical verifiable computation. In 2013 IEEE Symposium on Security and Privacy, pages 238–252. IEEE, 2013. (Page 3.) Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 56(6):34:1–34:40, 2009. Preliminary version in STOC 2005. (Pages 6, 16, and 37.) Gregory Rosenthal. Bounds on the QAC0 complexity of approximating parity. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPIcs), pages 32:1–32:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. arXiv:2008.07470. (Pages 2 and 13.) Alexander A. Razborov and Steven Rudich. Natural proofs. Journal of Computer and System Sciences, 55(1):24–35, 1997. (Page 2.) Ran Raz and Avishay Tal. Oracle separation of BQP and PH. Journal of the ACM, 69(4):30:1–30:21, 2022. Preliminary version in STOC 2019. (Page 12.) Dan Shepherd and Michael J. Bremner. Temporally unstructured quantum computation. Proceedings of the Royal Society A, 465:1413–1439, 2009. arXiv:0809.0847. (Page 12.) Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509, 1997. arXiv:quant-ph/9508027. (Pages 1 and 4.) Barbara M. Terhal and David P. DiVincenzo. Adaptive quantum computation, constant depth quantum circuits and Arthur–Merlin games. Quantum Information and Computation, 4(2):134–145, 2004. arXiv:quant-ph/0205133. (Pages 1, 4, and 12.) Yasuhiro Takahashi and Seiichiro Tani. Collapse of the hierarchy of constant-depth exact quantum circuits. Computational Complexity, 25(4):849–881, 2016. arXiv:1112.6063. (Pages 2, 13, and 27.) Takashi Yamakawa and Mark Zhandry. Verifiable quantum advantage without structure. Journal of the ACM, 71(3):20:1–20:50, 2024. arXiv:2204.02063. (Pages 3 and 12.)

The Admissibility Predicate

This appendix proves Lemma 6.8 and Proposition 6.9, and explains why the balance tests in Definition 6.6 rule out several elementary classical strategies. Passing the tests is not known to imply a hardcore bit, and the arguments below do not derive Assumption 6.7 from LWE. Rather, they show that the assumption is being made for an explicit predicate that accepts almost all of the honest challenges while excluding the carry-cancellation and padding strategies described below. The BCMVV result uses a similar admissible set. A.1

Preimage differences and the decomposition

We first make explicit how the two extended preimages of a valid paired image differ. The decomposition of Lemma 6.8 then follows by splitting the parity over the register blocks, and the realizability lemma at the end of the subsection shows that every pair (a, P) arises from a transcript that the adversary can generate itself. Lemma A.1 (Preimage differences). Fix a valid paired image, a branch b, and write χb = (−1)b . Then, modulo q, (1−b) (b) (1−b) (b) x1−b = xb − χb s, rj,i = rj,i + χb sj (j ≤ n), rn+1,i = rn+1,i − χb , and

 (1−b)

hi,j

(b)

= hi,j + χb ei +

 X

(b)

Ai,j ′ sj ′  = hi,j + χb σi,j (s).

j ′ ≤j

33

Proof. The relation between the decoded preimages is part of Definition 6.4. Equality of the w-part of the two encodings then gives (1−b)

rj,i

(b)

= rj,i + χb sj

(j ≤ n),

(1−b)

(b)

rn+1,i = rn+1,i − χb ,

because passing to the other branch changes vj by −χb sj for j ≤ n and the branch coordinate vn+1 by χb , and rj,1 = wj,0 − vj negates these changes and propagates them down each column. Equality of the b z-part and η 0 − η 1 = e similarly gives the h-relation, by telescoping Equation (8) along row i. At the last stored path mask, j = n, the parenthesized value is (As + e)i = ui ; the branch column then contributes
(1−b) (b) Mi,n+1 rn+1,i − rn+1,i = −χb ui , so the telescoped difference returns to zero at j = n + 1, as required by the boundary condition hi,n+1 = 0 on both branches. ⊔ ⊓ Proof (of Lemma 6.8). Fix a branch b and abbreviate χ = χb and J = Jq . By Lemma A.1, the parity splits over the register blocks as M
D · (ζ 0 ⊕ ζ 1 ) = Dxj · J(xb,j ) ⊕ J(xb,j − χsj ) j

M

(b) (b) (b) (b) Drj,i · J(rj,i ) ⊕ J(rj,i + χsj ) ⊕ Drn+1,i · J(rn+1,i ) ⊕ J(rn+1,i − χ)

⊕

MM j≤n

i

⊕

M

Dhi,j ·

i

(b) (b) J(hi,j ) ⊕ J(hi,j + χ σi,j (s)) .

i,j

Since sj ∈ {0, 1}, the j-th x-term equals sj · Dxj · (J(xb,j ) ⊕ J(xb,j − χ)), and the (j, i)-th r-term equals (b)

(b)

sj · Drj,i · (J(rj,i ) ⊕ J(rj,i + χ)); summing over j and i gives ⟨ab (D), s⟩ by Equation (17). The branch column and the terminal h-column, where σi,n (s) = ui , do not depend on s and sum to βb (D) by Equation (18). The remaining h-terms are exactly ΦχPb (D) (s) by Equation (14). ⊔ ⊓ Lemma A.2 (Realizability). For every sign χ, every a ∈ {0, 1}n , and every predicate list P, there is a transcript with a direction, computable in polynomial time, whose induced data at the branch b with (−1)b = χ is exactly (a, 0, P), and whose encoded output is a valid paired image for every (s, e) in the support of the key generation, except on the trapdoor-failure event. Proof. Take b with (−1)b = χ, x = 1 if b = 0 and x = (Q − 2)1 if b = 1, η = 0, r = 0, hi,j = ξ for each (i, j, ξ, d) ∈ P and hi,j = 0 otherwise, and encode honestly. Outside the trapdoor-failure event, the checks of Definition 6.4 succeed for every (s, e) in the support: the two relations hold by construction, x and x − χs lie in the two branch domains, and η = 0 and η − χe lie in E m because BV < W/2. Choose Dhi,j = d on the listed blocks and zero elsewhere, in particular on the terminal column; Dr = 0; and, for each j, a block Dxj with Dxj · (Jq (xj ) ⊕ Jq (xj − χ)) = aj , which is solvable for both bit values because the word in parentheses is nonzero. With this support βb (D) = 0, and the induced data is (a, 0, P). ⊓ ⊔ A.2

Polynomial-time checkability and pointwise density

The bits Sj and ∆ρ,i of Definition 6.6 are computed from the secret s, the public matrix and key vector, and the pair under test. There are O(n + mL) of them, each computed by polynomially many modular operations, canonical encodings, and binary inner products. Hence even the direct implementation of Adm is deterministic polynomial time. It remains to prove density. If Uν is uniform in {0, 1}ν , then a Hoeffding bound (deviation ν/6 from the mean ν/2) gives Pr[Uν is not balanced] ≤ 2 exp(−ν/18). (21) Fix a valid paired image and a branch b, and consider the induced data of a uniform direction D. We show that every vector tested by the sensitivity condition at (ab (D), Pb (D)) is individually uniform. Joint independence between these vectors is neither claimed nor needed. 34

Fix j. Conditional on all direction blocks other than Dxj , the bit ab (D)j contains the term
Dxj · Jq (xb,j ) ⊕ Jq (xb,j − χb ) . The word in parentheses is nonzero because xb,j − χb ̸= xb,j in Zq and canonical encoding is injective. Distinct coordinates use disjoint Dxj -blocks. Consequently ab (D) is exactly uniform.
The directional derivatives Sj of Equation (15) satisfy Sj = ab (D)j ⊕ ΦχPbb (D) (s) ⊕ ΦχPbb (D) (s(j) ) , and the Φ-difference does not involve Dx . The same block Dxj therefore makes the complete vector (Sj )j∈[n] uniform after conditioning on all r- and h-blocks. (b) Finally fix ρ ∈ R and a row i, and choose any j0 ∈ J . Writing w = hi,j0 + χb σi,j0 (s), the bit ∆ρ,i of Equation (16) contains the term
Dhi,j0 · Jq (w) ⊕ Jq (w + χb ρ) , including the case Dhi,j0 = 0, in which the pair (i, j0 ) is simply not listed in Pb (D) and contributes zero. The coefficient word is nonzero because every ρ ∈ R is nonzero modulo the odd prime q. Different rows use disjoint Dh -blocks, so the vector (∆ρ,i )i is exactly uniform. Let ν = n/2, and put m0 = ⌊m/2⌋ and m1 = ⌈m/2⌉. Applying Equation (21), at each of the two branches, to the two halves of ab (D), the two halves of (Sj )j∈[n] , and the two halves of (∆ρ,i )i∈[m] for each of the 2(⌊L/4⌋ + 1) shifts ρ ∈ R, gives b k,t,ζ ,ζ ] ≤ 16 exp(−ν/18) Pr[D ∈ /G 0 1
+ 8 ⌊L/4⌋ + 1 (exp(−m0 /18) + exp(−m1 /18)) = 2−Ω(n) .

(22)

Here the factor eight in the second line accounts for two branches, two signs, and the two tails in Equation (21). A direct union bound is valid despite correlations among the tests. Failing the sensitivity condition at some b k,t,ζ ,ζ , so this proves Proposition 6.9 pointwise for every valid paired branch is the only way to leave G 0 1 image. The honest prover still samples D uniformly by its final Hadamards; it does not conditionally sample from the direction set, so the predicate adds no quantum depth. A.3

Elementary attacks excluded by the balance tests

Consider the adversary’s predicate Ψ (s′ ) = ⟨a, s′ ⟩ ⊕ ΦχP (s′ ). Its value at s is the target parity, and Sj is by definition the directional derivative of Ψ at s in the direction δj : Sj = Ψ (s) ⊕ Ψ (s ⊕ δ j ). A carry cancellation is a choice of (a, P) in which the carry term ΦχP (s′ ) agrees with ⟨a, s′ ⟩ up to a constant, so that Ψ (s) is known without knowledge of s. Any cancellation that holds at s and at all of its Hamming neighbors, so that Ψ is locally constant at s, has all directional derivatives zero and is inadmissible. More generally, a pair whose predicate has a nonzero derivative in fewer than one third of the coordinates of either secret half fails the corresponding balance test. This includes any carry cancellation involving only a bounded number of secret coordinates, as well as XOR padding by other locally constant functions. Once carry predicates are used, the balance test on a separately prevents an attack from setting the linear coefficient to zero or concentrating it on a few selected coordinates. The terminal column cannot repair a failed test: its partial sum is the public ui , so it is excluded from predicate lists outright and contributes only a known bit to the protocol’s parities. The row tests address a second form of padding. A predicate list whose predicates with j ∈ J meet fewer than one third of the rows in either half gives vectors (∆ρ,i )i∈[m] of weight below the balanced range at every tested shift. Lists supported only on columns outside J make every ∆ρ,i zero; they fail the sensitivity 35

condition, and the linearity condition forces P = ∅. Hence a predicate list supported on one or a few rows cannot be made admissible by padding with columns near the ends. The row tests also exclude cancellation of the error within a row. Two predicates in row i at columns j1 < j2 ∈ J with the same wordPd, say the low-order bit at base point ξ = 0, have XOR lsb(ς)⊕[σi,j1 (s)+ς ≥ q] with ς = σi,j2 (s) − σi,j1 (s) = j1 <j ′ ≤j2 Ai,j ′ sj ′ mod q, so ei enters only through the wrap indicator, and ∆ρ,i = [σi,j1 (s) ≥ q − ρ] ⊕ [σi,j2 (s) ≥ q − ρ] is nonzero with probability O(ρ/q); rows of this form give weight far below m/3 at every tested shift. Conversely, ∆ρ,i = 1 certifies only that the bits selected in row i change parity when ui is shifted by ρ. A fixed word such as d = {0, . . . , ⌊L/4⌋ + 1} at ξ = 0 has ∆2a ,i = 1 with probability 2/3 at every a, so placed on three quarters of the rows of each half it passes the row tests with expected weight near m/2; the tests force a constant fraction of the rows to depend on ei at each scale, but they do not force this dependence to be unpredictable. Shifts by positive and negative powers of two probe carry behavior at every scale from one through the key-error scale BV . A padding strategy that passes the sensitivity condition must therefore spread sensitivity of the selected bits over a constant fraction of the LWE rows at every one of these scales, in addition to spreading its secret-coordinate sensitivity over both secret halves. The preceding arguments show only that terminal or locally constant padding cannot repair these failures. Whether correlated many-row padding can retain a bias is left to Assumption 6.7. The vector (Sj )j∈[n] equals (Ψ (s(j) ))j∈[n] or its bitwise complement according to the value of the target parity Ψ (s). Since the balance interval is invariant under complementation, the test on (Sj )j∈[n] depends only on the values of Ψ at the Hamming neighbors of s and not on the target parity itself. Nevertheless, the tests certify only local sensitivity at the secret s. A many-row predicate could in principle have balanced derivatives and remain predictable on the LWE distribution, and the tests at powers of two do not enumerate every possible shift. Excluding such correlated predicates remains part of the unproved content of Assumption 6.7.

B

Partial Evidence for the Carry-Predicate Assumption

Assumption 6.7 allows an adversary to choose the linear function, the predicate list, and its base points jointly, after seeing the public key. We do not know how to reduce this fully adaptive game to the ordinary BCMVV adaptive-hardcore-bit property. In this appendix, we prove three restricted results. First, key-mode indistinguishability rules out a predictor that commits to its base points and can then be rerun from the same saved state on independent uniform challenges. Second, the ordinary adaptive-hardcore-bit property rules out a sampler that can be repeatedly invoked from one saved state, produces overwhelmingly correct equations, and chooses challenges of sufficiently high conditional min-entropy. Third, every adversary restricted to empty predicate lists has negligible advantage, with full adaptivity; the case P = ∅ of Assumption 6.7, in which admissibility reduces to the linearity condition of Definition 6.6, therefore follows from Assumption B.1 at the security level of Proposition B.2. Recall from Section 6.1 the security parameter λ, the prime modulus q, its bit length L = ⌈log2 q⌉ = Θ(log2 λ), the dimension n of the binary LWE secret, and the number m of LWE samples. The reductions rest on Proposition B.2, which supplies key-mode indistinguishability and the ordinary adaptive-hardcore-bit bound for the decoded family under Assumption B.1. Here and below, the decoded family is the decoded map of Section 6.1, (x, η) 7→ Ax + bu + η on Xb × E m , viewed as a pair of functions indexed by b ∈ {0, 1}; dec dec its ordinary adaptive-hardcore-bit game is the BCMVV game with the sets Hk,t and H k,t of Section B.2. Conditions A.1–A.4 of BCMVV hold at our parameters as stated, without relaxation (verified in Section B.1). The reductions use the canonical map Jq of Section 5 together with bitwise XOR and linear algebra over F2 on its output. B.1 Set

The LWE assumption  λ2 ℓ= , L 

l √ m BL = 2 ℓ , 36

so that ℓ = Θ(λ2 / log2 λ) and, by Equation (3), n ≥ c1 (ℓL + λ). As in [BCM+ 21], the construction of Section 6 uses an LWE instance whose secret is binary. This simply means that the entries of the secret are 0 and 1, though it is still viewed as a vector over Zq ; its length is the parameter n. The assumption below instead has a secret uniform over Zℓq : by the lossy-mode argument of BCMVV (their Theorem 2.8 and the proof of their Lemma 4.4), LWE with a uniformly random binary secret of length n = Ω(ℓ log q + λ) is at least as hard as LWE at dimension ℓ with a uniform secret, which is why the assumption is stated at dimension ℓ. We use the truncated discrete Gaussian DZq ,BL of BCMVV [BCM+ 21]: its weight at a centered representative z is proportional to exp(−πz 2 /BL2 ) for |z| ≤ BL , and is zero otherwise. Assumption B.1 (Subexponential prime-modulus LWE, based on [Reg09, BCM+ 21]). There is a fixed constant 1/2 < δLWE < 1 such that, for every polynomially bounded sample count m′ , no uniform δ quantum algorithm of time at most 2ℓ LWE distinguishes (A, As + e)

from

(A, u) ′

′

×ℓ with advantage that is non-negligible as a function of λ, where A ← Zm , s ← Zℓq , e ← DZmq ,BL , and q ′

u ← Zm q . We apply it with m′ = m. This is a parameter-specific, fine-grained LWE assumption; worst-case LWE reductions do not by themselves establish its precise√time–advantage curve. The modulus has quasipolynomial magnitude, and the error satisfies the usual BL ≥ 2 ℓ threshold. Regev’s quantum worst-case-to-average-case reduction therefore applies and relates this ensemble to worst-case lattice problems at approximation factor   2 ℓq e O = 2O(log ℓ) BL [Reg09]. This places the assumption in the standard LWE regime at a quasipolynomial approximation factor, although the reduction does not prove the asserted subexponential running-time hardness. The standard dual-lattice attack estimate has exponent   ℓ e e 2 ), Θ = Θ(λ log(q/BL ) which is larger than ℓδLWE [BCM+ 21, Remark 4.2]. Thus this attack does not contradict the assumption, but the comparison is a parameter check rather than a proof of hardness. The recent quasipolynomial algorithm for extrapolated dihedral coset problems (EDCP) of Bai et al. [BJK+ 25] is also consistent with this assumption. Their algorithm is specific to power-of-two moduli, 3 whereas q is prime. Moreover, at our quasipolynomial modulus its state requirement is 2Ω(log ℓ log q) = 2Ω(log ℓ) , 2 whereas the applicable LWE-to-EDCP reduction supplies at most 2O(log ℓ) states. It therefore does not yield an attack on the LWE ensemble used here. We now check the hypotheses of the original BCMVV theorem for our construction, rather than use a quantitative relaxation of them. Recall also the equation-key Gaussian width BV from Section 6.1, and let BP =

2CT

p

q mn log2 q

be the BCMVV function-noise scale. The dimensions satisfy n = Ω(ℓ log q + λ),

m = Ω(n log q).

Moreover, since L = Θ(log2 λ), BL = poly(λ), and BV = 2L/4 , 2 BV = 2Θ(log λ) , BL

2 BP = 2Θ(log λ) . BV

37

(23)

Both ratios are superpolynomial in λ. Thus Conditions A.1–A.4 of BCMVV [BCM+ 21], namely the two dimension conditions, the definition of BP , and the superpolynomial noise gaps, hold at our parameters, and q is prime as their construction requires. In particular, the statistical losses from the overlap of the two function distributions (their Lemma 2.4) and from the error-shifting step in the lossy-matrix hybrid of their Lemma 4.4 are negligible. Proposition B.2 (Prime-modulus BCMVV consequences). Under Assumption B.1, both of the following advantages are negligible for every uniform quantum polynomial-time algorithm: 1. the advantage in distinguishing the equation key (A, As + e), with s ← {0, 1}n , from the image-key distribution; 2. the signed advantage in the ordinary BCMVV adaptive-hardcore-bit game for the decoded prime-modulus family, made precise in Section B.2. The same conclusion holds for adversaries of time 2ℓ polynomial running-time overhead.

δ′

for every fixed 0 < δ ′ < δLWE . The reductions have

Proof. The preceding parameter check verifies Conditions A.1–A.4 of BCMVV [BCM+ 21]. Key-mode indistinguishability follows from the hybrid in the proof of [BCM+ 21, Lemma 4.4], which replaces the public matrix by a lossy matrix (their Theorem 2.8) and shifts the error; the same argument appears in Mahadev [Mah22]. The adaptive-hardcore-bit lemma, [BCM+ 21, Lemma 4.3], proved from the leakage bound of their Lemma 4.4, gives the ordinary adaptive-hardcore-bit property. (The ordinary game contains no function-noise sample, so its statement applies to our family even though our function noise is uniform rather than the BCMVV Gaussian at scale BP .) All statistical hybrids are negligible: the noise-overlap and error-shifting losses by Equation (23), and the finite-precision key-sampling error by the sampler of Section 6.1, whose statistical distance from DZq ,BV is 2−Ω(n) ; every computational hybrid reduces with polynomial overhead to Assumption B.1. For the subexponential statement, such overhead is absorbed by replacing δLWE with any fixed smaller exponent δ′ . ⊔ ⊓ This proposition concerns only the decoded family. It does not establish Assumption 6.7, which also admits carry bits of the partial sums of the LWE equations. We use it as a standard-LWE basis for the partial evidence in this appendix, rather than as a hypothesis of the main result. B.2

The decoded relation

We now make the ordinary adaptive-hardcore-bit game for the decoded family precise; it is the target of the reductions below. Put NX = nL, and, for b ∈ {0, 1}, x ∈ Znq , and d ∈ {0, 1}NX parsed as n blocks of L bits, define the induced coefficient
Ib,x (d)j = dj · Jq (xj ) ⊕ Jq (xj − (−1)b ) ,

j ∈ [n].

Following BCMVV [BCM+ 21], the direction set Gk,b,x consists of the d for which Ib,x (d) is nonzero on the branch-b half of [n]: the first n/2 coordinates for b = 0 and the last n/2 for b = 1. Because the secret is binary, for the intended pair with x1−b = xb − (−1)b s we have the pointwise identity
d · Jq (x0 ) ⊕ Jq (x1 ) = ⟨Ib,xb (d), s⟩. (24) In the ordinary BCMVV adaptive-hardcore-bit game for the decoded family, the adversary outputs a branch b, a preimage xb ∈ Xb , a direction d ∈ {0, 1}NX , and a bit; write x1−b = xb − (−1)b s for the partner preimage. dec Define Hk,t to contain the tuples

b, xb , d, d · Jq (x0 ) ⊕ Jq (x1 ) 38

dec

with xb ∈ Xb , x1−b ∈ X1−b , and d ∈ Gk,0,x0 ∩ Gk,1,x1 , and let H k,t be obtained by flipping the last bit. The distinguished failure symbol ⊥, as well as every malformed output, is by convention in neither set. Item 2 of Proposition B.2 says that every efficient algorithm B has negligible signed gap: Pr

dec [B(k) ∈ Hk,t ]−

(k,t)←GenEq (1λ )

Pr

dec

[B(k) ∈ H k,t ] ≤ negl(λ).

(k,t)←GenEq (1λ )

The second and third results use the following procedure to convert a linear function of the secret into a decoded tuple. Lemma B.3 (Fiber realization). There is a polynomial-time procedure that, given χ ∈ {±1} and ϕ ∈ {0, 1}n , outputs (b, x, d) with (−1)b = χ, with x ∈ Xb and x − χs ∈ X1−b for every s in the support of the key generation, where we write xb = x and x1−b = x − χs, and with d uniform in {d : Ib,x (d) = ϕ}; in particular, pointwise,
d · Jq (x0 ) ⊕ Jq (x1 ) = ⟨ϕ, s⟩. Moreover: 1. if ϕ is nonzero on the branch-b half, then d ∈ Gk,b,xb with certainty; and 2. except with probability 2−Ω(n) over the key, Prd [d ∈ / Gk,1−b,x1−b ] ≤ 2−n/8 . Proof. Take x = 1 for b = 0 and x = (Q − 2)1 for b = 1; both branch domains are then respected for every binary s. Independently for each j, sample dj uniformly among the solutions of dj · gj = ϕj , where gj = Jq (xj ) ⊕ Jq (xj − χ) ̸= 0; both values of ϕj have solutions, and the resulting d is uniform in the fiber. The displayed identity is Equation (24), and item 1 is the definition of Gk,b,xb . For item 2, consider the opposite-branch coefficient I1−b,x1−b (d). On coordinates with sj = 1, the oppositebranch word equals gj , so the coefficient equals ϕj . On coordinates with sj = 0, the opposite-branch word is gj′ = Jq (xj ) ⊕ Jq (xj + χ), which is nonzero and distinct from gj because 2χ ̸≡ 0 (mod q); over F2 , distinct nonzero words are linearly independent, so, conditioned on dj · gj = ϕj , the bit dj · gj′ is uniform. Hence the opposite-branch coefficient restricted to the zero coordinates of s in the (1 − b)-half is uniform, and it vanishes on the whole half with probability at most 2−z , where z is the number of such coordinates. Since s is uniform, z ≥ n/8 except with probability 2−Ω(n) over the key, by a Chernoff bound. ⊓ ⊔ B.3

Uniform independent challenges

Fix a key, a sign χ, and an assignment of base points ξ : [m] × [n − 1] → Zq , and collect the bits unknown to the adversary into the string  
Z = s, Jq (ξi,j ) ⊕ Jq (ξi,j + χ σi,j (s)) i∈[m], j∈[n−1] ∈ {0, 1}NZ , NZ = n + m(n − 1)L. A challenge is a pair (a, Dh ) ∈ {0, 1}n × ({0, 1}L )m×(n−1) , with Dh = (Dhi,j )i∈[m],j∈[n−1] . Writing P(Dh , ξ) for the predicate list {(i, j, ξi,j , Dhi,j ) : Dhi,j ̸= 0}, a challenge is a parity of Z: ⟨(a, Dh ), Z⟩ = ⟨a, s⟩ ⊕ ΦχP(Dh ,ξ) (s). Answering a challenge correctly is therefore winning the game of Assumption 6.7 at the pair (a, P(Dh , ξ)), up to admissibility; a uniform challenge is admissible except with probability 2−Ω(n) , by Proposition 6.9 applied at the branch b with (−1)b = χ to the honestly encoded transcript in the proof of Lemma A.2, with coins hi,j = ξi,j for j ≤ n − 1; since the words Jq (xb,j ) ⊕ Jq (xb,j − χ) are nonzero and the Dx , Dr blocks are disjoint from the Dh blocks, the pair (ab (D), Pb (D)) of a uniform direction has exactly the law of (a, P(Dh , ξ)) for a uniform challenge. 39

Definition B.4 (Resettable uniform-challenge predictor). A resettable uniform-challenge predictor consists of two classical algorithms A = (Acom , Apred ). On input an equation key k, the first algorithm outputs a sign χ, an assignment of base points ξ, and a classical snapshot st that can be copied and restored. Given st and a challenge (a, Dh ), a fresh invocation of Apred , with fresh random coins ϱ, outputs one bit. Let tr = (k, t, χ, ξ, st) denote the complete first-stage transcript and let Z = Z(tr) be as above. Define h i h h corrtr = E(a,Dh ) uniform (−1)Apred (st,a,D ;ϱ)⊕⟨(a,D ),Z⟩ ,

(25)

ϱ

and the uniform-challenge advantage Advuc (A) = |Etr [corrtr ]|. Proposition B.5 (Uniform challenges). Let A = (Acom , Apred ) be a resettable uniform-challenge predictor (Definition B.4) with stage running times Tcom , Tpred and Advuc (A) ≥ µ > 0 for a known µ. Then there is a distinguisher between the equation- and image-key modes of running time Tcom + poly(NZ , 1/µ) Tpred + NZ

and advantage at least µ/3 − negl(λ). Consequently, every efficient resettable uniform-challenge predictor has negligible advantage: an inverse-polynomial µ makes the reduction efficient and its advantage non-negligible, contrary to Proposition B.2. Proof. Suppose that |Etr corrtr | ≥ µ. Then Etr |corrtr | ≥ µ, and hence Pr [|corrtr | ≥ µ/2] ≥ tr

µ µ ≥ , 2−µ 2

since otherwise the expectation of |corrtr |, which is always at most one, would be smaller than µ. Fix such a transcript. Reset access to Apred gives a randomized Boolean oracle whose Fourier coefficient at Z has magnitude at least µ/2, by Equation (25). Apply the Goldreich–Levin list-decoding algorithm [GL89] at threshold µ/4; since the oracle is randomized, we use its form for [−1, 1]-valued functions. Using poly(NZ , 1/µ) reset invocations, it returns a list of poly(1/µ) candidates that contains Z with probability at least 2/3. Fresh prediction coins cause no difficulty: repeated invocations estimate, to additive accuracy O(µ), the bounded oracle h i h gst (a, Dh ) = Eϱ (−1)Apred (st,a,D ;ϱ) . The stated success probability includes amplification of these estimates and a union bound over all adaptive list-decoder queries. For each list element, parse its first n bits as a candidate secret s′ and accept if ∥ centerq (u −As′ )∥∞ ≤ BV ; the distinguisher outputs “equation” if some candidate is accepted. On an equation key, the true Z is on the list except with probability 1/3 whenever |corrtr | ≥ µ/2, and its s-block passes the test; the acceptance probability is at least (µ/2)(2/3) = µ/3. On an image key, [A | u] is statistically close to uniform, and u the
mfor uniform probability that any of the 2n binary vectors passes the test is at most 2n (2BV + 1)/q = 2−Ω(mL) . The distinguishing advantage is therefore at least µ/3 − negl(λ), and Proposition B.2 bounds it by a negligible function. Formally, if the predictor’s advantage were non-negligible, fix an inverse-polynomial lower bound attained on an infinite subsequence and use it as µ. ⊔ ⊓ If the uniform-challenge experiment also filters through the admissibility predicate, removing the filter changes the correlation by at most the probability of an inadmissible challenge, 2−Ω(n) , so the same conclusion holds with µ − 2−Ω(n) in place of µ. Assumption B.1 absorbs the polynomial overhead of the reduction for inverse-polynomial µ. The proposition nevertheless remains structurally weaker than Assumption 6.7: it requires a predictor that commits to its base points and can then be reset and queried on independent uniform challenges. 40

B.4

High-min-entropy equation samplers

The honest Hadamard experiment produces a uniformly random direction, and the induced challenge of Section B.3 then has the maximum possible min-entropy, namely NZ bits. We next ask how far a sampler may depart from this benchmark while still being ruled out by the ordinary property. The conclusion in this subsection requires equations that are correct with overwhelming probability; samplers with inverse-polynomial bias are treated in Section B.5 for the linear case. Definition B.6 (Resettable equation sampler). A resettable equation sampler is a pair (Acom , S) of classical algorithms. The first algorithm, Acom (k), produces a sign χ, an assignment of base points ξ, and one fixed, copyable classical snapshot st. Let tr = (k, t, χ, ξ, st) be the complete transcript, including the private key data, and let Z = Z(tr) ∈ {0, 1}NZ be as in Section B.3. The sampler is invoked as ′

′

′

(a(τ ) , Dh,(τ ) , C (τ ) ) ← S st, (a(τ ) , Dh,(τ ) , C (τ ) )τ ′ <τ

with fresh coins; all persistent copyable state is included in st and the displayed history. For an integer 0 ≤ κent ≤ NZ , the sampler has conditional min-entropy deficiency at most κent and equation error at most ε if, for every transcript and every positive-probability history, ′

′

′

′

′

′

max Pr[(a(τ ) , Dh,(τ ) ) = (a, Dh ) | tr, (a(τ ) , Dh,(τ ) , C (τ ) )τ ′ <τ ] ≤ 2−NZ +κent ,

(a,Dh )

(26)

Pr[C (τ ) ̸= ⟨(a(τ ) , Dh,(τ ) ), Z⟩ | tr, (a(τ ) , Dh,(τ ) , C (τ ) )τ ′ <τ ] ≤ ε. Deficiency zero forces a uniform challenge, while a challenge uniform on a codimension-κent subspace attains the bound in Equation (26). This is worst-case conditional min-entropy, rather than the average or smooth variant. If samples are conditionally independent given each fixed transcript, it suffices to impose the corresponding pointwise bound for every transcript. Proposition B.7 (High-entropy correct-equation samplers). Let (Acom , S) be a resettable equation sampler (Definition B.6) with conditional min-entropy deficiency at most κent and equation error at most ε. For any 0 < δrk < 1, put 
 T = 8 NZ + ln(1/δrk ) . There is an ordinary decoded-family adaptive-hardcore-bit adversary, using T invocations of S and polynomial additional time, whose signed advantage is at least 1 − 2κent −n/2 − 2−n/8 − 2−Ω(n) − 2(δrk + T ε).

(27)

Thus such an efficient sampler is ruled out whenever the quantity in Equation (27) is non-negligibly positive. For example, with δrk = 2−n/8 we have T = O(NZ ), and Proposition B.2 rules out efficient resettable samplers satisfying κent ≤ n/4, T ε = 2−Ω(n) . Proof. Write N = NZ . The reduction collects T equations. For the following rank and correctness estimates, fix a transcript. Let Vτ = span{(a(1) , Dh,(1) ), . . . , (a(τ ) , Dh,(τ ) )}. While dim Vτ −1 < N − κent , the conditional min-entropy bound gives Pr[(a(τ ) , Dh,(τ ) ) ∈ Vτ −1 | history] ≤ |Vτ −1 |2−N +κent ≤

1 . 2

Thus the rank increments stochastically dominate independent Bernoulli(1/2) trials until rank N − κent . To verify the constant in T , put µT = T /2. Then µT ≥ 4(N + ln(1/δrk )) and N − κent ≤ N ≤ µT /4. A Chernoff bound, coupled to the adaptive increments until the target rank is reached, gives h i
Pr rank (a(1) , Dh,(1) ), . . . , (a(T ) , Dh,(T ) ) < N − κent ≤ exp(−9µT /32) ≤ δrk . 41

Conditional on the transcript, except with probability at most T ε, all sampled equations are correct. Let Γ be the binary matrix whose rows are the sampled challenges and let C = (C (1) , . . . , C (T ) ). If the sampled matrix has rank below N − κent , or if Γ z = C is inconsistent, the reduction outputs ⊥. Otherwise, Gaussian elimination gives {z ∈ {0, 1}N : Γ z = C} = z∗ + ker Γ , dim ker Γ ≤ κent , and on the correct-equations event the true string Z belongs to this affine space. Projecting onto the s-coordinates gives s ∈ a∗ + U, dim U ≤ κent . Sample ϕ uniformly from U ⊥ ⊆ {0, 1}n , set c = ⟨ϕ, a∗ ⟩; since s ⊕ a∗ ∈ U , the equation ⟨ϕ, s⟩ = c is exact. Run the fiber realization (Lemma B.3) on (χ, ϕ) to obtain (b, x, d), and output (b, x, d, c) to the decoded game; the equation is exact by the displayed identity there. For the direction conditions: U ⊥ has density at least 2−κent in {0, 1}n , and the set of vectors vanishing on the branch-b half has density 2−n/2 , so ϕ is nonzero there except with probability 2κent −n/2 ; the opposite-branch condition fails with probability at most 2−n/8 on a 1 − 2−Ω(n) key event. On the full success event and for a direction satisfying both conditions, the reduction’s output lies in dec Hk,t . If a direction condition fails, the output lies in neither set and contributes zero; only when the success dec

event fails can the output lie in H k,t , and on that event its contribution is at least −1. The success event fails with probability at most βfail = δrk + T ε, and on the success event the direction conditions fail with probability at most γdir = 2κent −n/2 + 2−n/8 + 2−Ω(n) . Therefore its signed advantage is at least (1 − βfail − γdir ) − βfail = 1 − γdir − 2βfail , ⊔ ⊓

which proves Equation (27).

In particular, Proposition B.7 rules out an exact sampler whose challenges, for one fixed snapshot, are independent uniform, or equivalently remain uniform conditioned on every prior history. More generally, the entropy may be lowered from its maximum value NZ by as many as n/4 bits: each challenge may be up to a factor 2n/4 more likely than it would be under the uniform distribution, and the conclusion still follows. The successive challenge distributions may depend on all preceding equations, but the equations themselves must be correct with overwhelming probability. B.5

Linear predicates

We now consider adversaries whose predicate lists are empty, so that the predicted bit is a linear function of the secret. For this class the assumption is not merely supported by evidence: at the security level of Proposition B.2, it follows from Assumption B.1. Proposition B.8 (Empty predicate lists). Let A be a uniform quantum polynomial-time algorithm in the game of Assumption 6.7 whose output always has P = ∅. Under Assumption B.1, the signed advantage of A is negligible. Proof. An empty predicate list makes every bit ∆ρ,i in Equation (16) zero, so the sensitivity condition fails, and admissibility is equivalent to the linearity condition: a nonzero on the half designated for χ. The reduction runs A(k) to obtain (χ, a, ∅, C), and outputs ⊥ if the output is inadmissible; for empty predicate lists this is the public condition that a be nonzero on the designated half, so the reduction can check it. Otherwise it runs the fiber realization (Lemma B.3) on (χ, a) and outputs (b, x, d, C) to the decoded game. dec The equation d · (Jq (x0 ) ⊕ Jq (x1 )) = ⟨a, s⟩ is exact, so the output lies in Hk,t exactly when A’s output lies carry carry in Hk,t , and in the flipped set exactly when it lies in H k,t , provided d ∈ Gk,0,x0 ∩ Gk,1,x1 . The branch-b condition (item 1 of Lemma B.3) holds with certainty by the linearity condition, and the opposite-branch condition (item 2) fails with probability at most 2−n/8 on a 1 − 2−Ω(n) key event; on the failure events the output lies in neither decoded set and contributes zero to the signed gap. Hence the reduction’s signed advantage is within 2−n/8 + 2−Ω(n) of A’s, and Proposition B.2 bounds the former by a negligible function. ⊔ ⊓ 42

In particular, the case P = ∅ of Assumption 6.7 follows from Assumption B.1 at the security level of Proposition B.2, so Assumption 6.7 strengthens a statement that is provable at our parameters. The proposition extends to samplers that are only weakly correct, provided their linear functions are sufficiently spread; this rules out a family of attacks that need not respect the admissibility predicate at all. Definition B.9 (Linear sampler). A linear sampler is a pair (Acom , S) of uniform polynomial-time classical algorithms. On input k, the first algorithm outputs a sign χ and one copyable snapshot st. One invocation of S(st) outputs (a, C) ∈ {0, 1}n × {0, 1} satisfying, conditioned on every fixed (k, t, st), H∞ (a | k, t, st) ≥ hmin , 1 Pr[C = ⟨a, s⟩ | k, t, st] ≥ + γ. 2

(28) (29)

The joint distribution of (a, C) is otherwise arbitrary; in particular, the error probability may depend on a. Proposition B.10 (Biased linear samplers). Let (Acom , S) be a linear sampler (Definition B.9) with parameters hmin , γ. Then there is a polynomial-time ordinary decoded-family adaptive-hardcore-bit adversary whose signed advantage is at least 2γ − γgood ,

γgood ≤ 2n/2−hmin + 2−n/8 + 2−Ω(n) .

(30)

Consequently, Proposition B.2 rules out the sampler whenever 2γ−γgood is non-negligibly positive. In particular, for any inverse-polynomial γ it suffices that ln m hmin ≥ + log2 (2/γ) . (31) 2 This conclusion uses only one sampler invocation. Proof. The reduction invokes S once, obtains (a, C), runs the fiber realization on (χ, a), and outputs (b, x, d, C) to the decoded game. The equation bit d · (Jq (x0 ) ⊕ Jq (x1 )) = ⟨a, s⟩ is exact and does not depend on the fiber choice. Write Y = (−1)C⊕⟨a,s⟩ ; by Equation (29), E[Y | k, t, st] ≥ 2γ. The output enters the correct or flipped decoded set according to Y whenever d ∈ Gk,0,x0 ∩ Gk,1,x1 , and neither set otherwise, so filtering changes the signed expectation by at most the failure probability of the direction conditions. For the branch-b condition, the min-entropy bound Equation (28) gives Pr[a vanishes on the half designated for χ] ≤ 2n/2−hmin , since that set has 2n/2 elements, each of probability at most 2−hmin . The opposite branch fails with probability at most 2−n/8 on a 1 − 2−Ω(n) key event. The overall signed gap is therefore at least 2γ − γgood with γgood as displayed. Finally, Equation (31) gives 2n/2−hmin ≤ γ/2, so Equation (30) is at least 3γ/2 − 2−Ω(n) , which is non-negligible for every inverse-polynomial γ and contradicts Proposition B.2. ⊔ ⊓ When the linear functions are uniform and repeated labeled samples are independent, the equations above can also be viewed as LPN with coefficient-dependent, or adversarial, classification noise. Known agnostic-learning algorithms reduce parity learning under the uniform distribution with such adversarial classification noise to parity learning with random classification noise; combining this reduction with the Blum–Kalai–Wasserman algorithm gives a subexponential algorithm [FGKP09,BKW03]. The direct argument above is stronger for our purpose: it needs neither repeated samples nor a noise model, and it preserves any inverse-polynomial correlation without first recovering the secret. The three results are complementary, and their restrictions delimit what remains open. The first requires reset access to a predictor after its base points are fixed, the second requires many correct equations for one fixed snapshot, and the third covers only empty predicate lists. These restrictions leave open the fully adaptive game in Assumption 6.7, where the linear function, the predicate list, and the base points may be chosen jointly and used once. 43

C

Parameters for the Encoded Construction

In this appendix, we prove the parameter estimates used in the completeness and soundness arguments. Recall from Section 6.1 and Appendix B that   L = 4 (log2 (λ + 2))2 = Θ(log2 λ), 2L−1 ≤ q < 2L with q prime, ℓ = Θ(λ2 /L),

n = Θ(λ2 ),

that the trapdoor inversion radius is rG =

q CT

p

(n + 1)L

m = Θ(nL),

,

and that P =

rG , 2m

Q = 2L/2 ,

l √ m BL = 2 ℓ ,

BV = 2L/4 ,

BP =

2CT

q p . mn log2 q

Lemma C.1 (Parameter estimates). For all sufficiently large λ, the following hold. 1. Noise hierarchy. BL < BV < BP , and the ratios BV /BL and BP /BV are superpolynomial in λ. 2. Completeness errors. mBV /W + 2n/Q = negl(λ). 3. Interval overlap and no wrap-around. 2BV < W and 2W + 2BV < q. √ 4. Trapdoor uniqueness radii. m BV < rG , every η ∈ E m satisfies ∥ centerq (η)∥2 < rG , and ∥ centerq (η + e)∥2 < rG for every key error e in the support of DZmq ,BV . 5. LK-1/4 radius. For every generated matrix K satisfying Equation (2), every η ∈ E m satisfies ∥ centerq (η)∥∞ ≤ 41 λ∞ 1 (L(K)). Proof. The three noise scales satisfy   λ , BL = Θ √ L

BV = 2L/4 ,

BP =

2L+O(1) . λ2 L

Thus BL < BV < BP for all sufficiently large parameters, and BV = 2L/4−O(log λ) , BL

BP = 23L/4−O(log λ) BV

are both superpolynomial in λ. These are precisely the two noise-gap conditions in BCMVV [BCM+ 21], as in Equation (23); this proves the first item. For the second item, note that for sufficiently large λ, the definition in Equation (5) makes W the largest power of two satisfying the integer inequality 4m2 CT2 (n + 1)L W 2 ≤ q 2 . Equivalently, W ≤ P , and maximality gives W > P/2. Consequently, mBV 4m2 BV < W r G  = O λ5 L5/2 2−3L/4 = negl(λ). Also,   2n = O λ2 2−L/2 = negl(λ). Q The same estimates give BV = negl(λ), W

2W + 2BV = λ−3+o(1) . q 44

The second estimate is used only as a deterministic no-wrap inequality; it is not a completeness-error term. In particular, 2BV < W and 2W + 2BV < q for all sufficiently large λ, proving the third item. For the fourth item, every centered noise vector in E m satisfies √ mW rG ∥ centerq (η)∥2 ≤ ≤ √ < rG . 2 4 m The key error also satisfies

√

  m BV = O λ2 L2−3L/4 = negl(λ). rG

Hence, for all sufficiently large λ, ∥ centerq (η + e)∥2 ≤ ∥ centerq (η)∥2 +

√

m BV < rG .

These are the two trapdoor-uniqueness bounds used for equation keys. √ Finally, λ∞ 1 (L(K)) ≥ rG / m by Equation (2), and hence ∥ centerq (η)∥∞ ≤

W rG 1 ≤ ≤ λ∞ (L(K)). 2 4m 4 1

This is the LK-1/4 inequality used in Lemma 6.15, and it uses only the lower bound of Equation (2).

⊓ ⊔

The main register lengths are nL = Θ(λ2 log2 λ),

mL = Θ(λ2 log4 λ),

mnL = Θ(λ4 log4 λ).

The last quantity is, up to a constant factor, the number of qubits in the source and output registers of Lemma 6.13.

45

Related documents

• A Note on Universal Positivity of Rank-Two Quantum Greedy Elements#1141774
• Existence and nonexistence of commutativity gadgets for entangled CSPs#1062636
• On the Figures of Merit for Quantum Software Security: Toward a Benchmarking Rubric#432458
• Quantifying entanglement in quantum thermodynamics via separability constraints#1069762
• Quantum Variational Approaches to the Maximum Independent Set Problem at Utility Scale#630056