Trapdoored Clifford Operators and Applications

Trapdoored Clifford Operators and Applications Minki Hhan1 and Hojune Lee1 1

KAIST, Daejeon, Korea

arXiv:2610.01848v1 [quant-ph] 1 Oct 2026

minkihhan@kaist.ac.kr, hojunelee@kaist.ac.kr

Abstract Random Clifford operators have numerous applications in quantum computing, including randomized benchmarking, classical shadows, and quantum authentication. However, sampling and implementing uniformly random n-qubit Clifford incur near-quadratic complexity due to the size of Clifford group. We introduce a cryptographic way to overcome these barriers: trapdoored Clifford operator distributions whose samples are computationally indistinguishable from uniformly random Cliffords, yet implementing them can be much faster given the trapdoor. We construct a distribution of trapdoored Clifford operators whose elements can be sampled and implemented in near-linear time under a variant of the learning parity with noise assumption. Our constructions allow fast tableau action on Pauli labels for classical simulation, and also can be optimized to admit polylogarithmic-depth implementation. Along the way, we construct trapdoored matrices over finite fields that support efficient multiplication by both a matrix and its inverse, resolving an open question left by Vaikuntanathan and Zamir [SODA’26]. We use these constructions to obtain faster protocols based on random Cliffords. We also explore their applications to the worst-case to average-case reductions for matrix and Clifford problems including the iterated matrix multiplication and Clifford circuit synthesis. In particular, we show the hardness of batching Clifford circuits: synthesizing circuits that apply the same Clifford to multiple registers is at least as hard as worst-case matrix multiplication, even when synthesis succeeds on a small constant fraction of random Cliffords. This extends to approximate implementations by general quantum circuits.

AI use disclosure. AI use disclosure. ChatGPT (from 5.5 Pro to 6 Astra) was used during the preparation of this manuscript. Many of the constructions and proofs, as well as initial drafts of some sections, were generated by ChatGPT. The authors wrote the current manuscript based on these materials with AI assistance and take full responsibility for its content. 1

Contents 1 Introduction 1.1 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 3 4 5

2 Trapdoored Matrix Distributions 2.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Base Construction from (Dual) Ring-LPN Assumptions . . . . . . . . . . . . . . . . . . . . . 2.3 Trapdoored Triangular Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Trapdoored Invertible Triangular Matrices with Efficient Inversion . . . . . . . . . . . . . . . 2.5 Trapdoored Invertible Matrices with Efficient Inversion . . . . . . . . . . . . . . . . . . . . . . 2.6 Depth-Efficient Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 5 6 8 12 14 16

3 Trapdoored Clifford Distributions 17 3.1 Uniform random Clifford Oprators and Decomposition of Clifford Operators . . . . . . . . . . 17 3.2 Trapdoored Hadamard-free Clifford Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3 Trapdoored Clifford Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4 Applications 21 4.1 Clifford authentication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2 Worst-case to Average-case Reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.3 From average-case parallel Clifford implementations to matrix multiplication . . . . . . . . . 24

2

1

Introduction

Clifford circuits, also known as stabilizer circuits and generated by Hadamard, phase, and controlled-NOT (CX) gates, play a central role in quantum computing. Their algebraic structure enables efficient classical simulation via the stabilizer formalism [AG04]. On the other hand, adjoining a non-Clifford gate such as the T gate yields a universal gate set for quantum computation. These properties also make Clifford operators central to quantum error correction [Got97] and fault-tolerant quantum computation [Got98]. Random Clifford operators are also widely used in various areas of quantum computing, including randomized benchmarking [MGE11], classical shadow estimation [HKP20], and quantum state tomography [KZG16]. They also underpin constructions of random stabilizer codes [BF13b] and quantum authentication schemes [ABOEM17]. Efficient sampling of uniformly random Clifford operators and their efficient circuit implementation have been extensively studied. For n-qubit Cliffords, Koenig and Smolin [KS14] gave an O(n3 )-time classical sampling algorithm. Bravyi and Maslov [BM21] achieved O(n2 ) sampling time with circuits of size O(n2 ), and van den Berg [VDB21] subsequently gave a simpler method with the same complexity. This is near-optimal as the optimal circuit size is known to be Θ(n2 / log n) [AG04, Corollary 9]. This may still be unsatisfactory: even a single application of a uniformly random Clifford operator typically requires a nearly quadratic number of elementary gates and nearly linear depth. In this paper, we ask whether this cost can be circumvented by relaxing uniform randomness to pseudorandomness, i.e., indistinguishability from uniform randomness against efficient quantum algorithms. This relaxation suffices for most applications, which involve only polynomial-time quantum computations. We further require these operators to admit hidden, efficient circuit implementations, whose descriptions serve as trapdoors. We call such operators trapdoored Clifford operators, a quantum analogue of the trapdoored matrices introduced in [BN25, VZ26].

1.1

Our Results

Our main result is the construction of trapdoored Clifford operators under the cryptographic assumptions. Theorem 1.1 (Informal). Under the (dual) ring learning parity with noise (LPN) assumption, we can sample (a description of ) a trapdoored n-qubit Clifford operator C together with its trapdoor tdC in n1+ε time, where tdC gives an implementation of C using n1+ε elementary gates and n1+ε clean ancillary qubits for arbitrarily small constant ε > 0. These can be reduced into n · poly log(n) assuming subexponential hardness. Our trapdoored Clifford operators also support near-linear evaluation of the corresponding conjugate action on any Pauli label, providing a more efficient classical simulation. Furthermore, the Clifford circuit implementation can be done in a polylogarithmic depth under all-to-all connectivity. A key ingredient of our trapdoored Clifford operators is the trapdoored matrices over finite field that supports efficient multiplication, inversion and more under the same assumptions. This resolves an open question left in [VZ26, Section 3]. Theorem 1.2 (Informal). Under the (dual) ring learning parity with noise (LPN) assumption, we can sample (a description of ) a trapdoored invertible matrix M ∈ GL(n, Fq ) together with its trapdoor tdM in n1+ε time for any ε > 0. The trapdoor supports matrix-vector multiplication by M , M T , M −1 , and M −T in n1+ε time and polylogarithmic depth. The time can be reduced into n · poly log(n) assuming subexponential hardness. Along the way, we also construct the trapdoored triangular and symmetric matrices. Together all of these, we can embed them into the Bravyi–Maslov Clifford sampler [BM21], which was obtained using the Bruhat decomposition. Interestingly, the Bruhat decomposition is used in constructing the above trapdoored matrices with efficient inversions. This structure also allows efficient computation of determinant of the sampled matrices, which answers another question in [VZ26] affirmatively.

3

1.2

Applications

Immediate applications. For many fundamental protocols repeatedly sample and apply random Clifford operations, our construction immediately replace them by the trapdoored Clifford operators. • Efficient simulation and verification. Given the trapdoor, conjugating a Pauli operator by Cliffords takes near-linear time. This speeds up the Pauli calculations in stabilizer simulation [AG04] and direct fidelity estimation of Clifford channels [FL11]. It also can be used in few T -gate simulation [BG16], imposing random-looking Cliffords to the actual quantum algorithm while allowing efficient classical simulation using trapdoors. • 3-designs and classical shadows. Uniform random Cliffords form an exact 3-design [Zhu17, Web16]. The trapdoored Clifford operators may lose this property, yet they still look like an (approximate) 3-design from the efficient algorithm’s view. This motivates its use in classical shadows [HKP20]: one applies a sampled Clifford to an unknown state and records the measurement outcome repeatedily. The resulting data can later be used to predict many efficiently computable observables, including fidelities with stabilizer states chosen after measurement. • Random stabilizer codes. Applying a uniform random Clifford to a state followed by zero ancillas gives a random stabilizer code. This can be used in several protocols including quantum secret sharing and erasure-resilient communications [PQS26, Mat17, KO26]. • Clifford authentication. The same template used in the Clifford authentication [ABOEM17]. Using trapdoored Clifford improves their efficiency; for the quantum authentication, this argument only ensures the soundness against efficient attacks. Adapting the technique used in [ABOEM17] turning arbitrary adversary into Paulis, we actually prove the negligible soundness error against all adversarial behavior in Section 4.1. Other applications include gate-set shadow estimation and quantum data hiding [HIK+ 23, DLT02]. Worst-case to average-case reductions. The worst-to-average reduction for the matrix multiplication asks if given a black-box algorithm to compute the matrix multiplication for an average input, one can compute A · B for almost all A, B using almost the same time. It was considered in [BLR90] and answered in a positive way. Subsequent works showed that this is possible even if the given algorithm works correctly (or even approximately correctly [HS25, GSS24]) only on a very small fraction of inputs [AGGS22, HS23]. Using the trapdoored matrices, [VZ26] showed that this worst-to-average behavior is pravelent in many linear algebra problems. Our trapdoored invertible matrices also yield worst-case-to-average-case reductions for linear algebra and Clifford problems, extending this framework. Our main application for the linear algebra problems are the iterated matrix multiplication and determinant computation. The worst-case to average-case reduction for the iterated matrix multiplication was studied in [GLR+ 91, GS92] for the black-box algorithm works correctly most (or at least half for large characteristic [GS92]) of the inputs. We show the worst-case to average-case reduction for the iterated matrix multiplication even when the given algorithm works correctly for a tiny fraction of the inputs. The determinant computation was studied in [VZ26]. We improve the error rate: For any ε > 0, the reduction works with the error rate 1/2 + ε for sufficiently large q. Finally, we study the cost of synthesizing Clifford circuits. We prove the worst-to-average reduction for the Clifford circuit synthesis given the tableau. Further, we relate the average-case of batched Clifford circuits to the worst-case matrix multiplication. Suppose an algorithm, given the tableau of a random 2n-qubit Clifford C, constructs a Clifford circuit for C ⊗n with constant success probability. We convert it into an algorithm that multiplies any two n × n matrices over F2 with high probability. Thus, faster synthesis of circuits applying the same Clifford operator to multiple registers would imply faster worst-case matrix multiplication, even if synthesis produces approximate implementations for only an arbitrarily small constant fraction of random Clifford operators. In other words, batched Clifford circuit synthesis is at least as hard as matrix multiplication. 4

1.3

Notation

Fields and Matrices. Let q be a fixed prime power, and let Fq denote the field with q elements. For positive integers n and m, write [n] := {1, . . . , n} and let Matn×m (Fq ) denote the set of n × m matrices over Fq . All matrix classes below are defined over Fq ; we omit the field from the notation. We write Un and Ln for the sets of n × n upper and lower triangular matrices, respectively. The subsets of strictly upper triangular and invertible upper triangular matrices are denoted by Un◦ and Un∗ , respectively:  Un◦ := U ∈ Un Uii = 0 for all i ∈ [n] ,  Un∗ := U ∈ Un Uii ̸= 0 for all i ∈ [n] . The classes L◦n and L∗n are defined analogously. We denote the set of symmetric matrices by  Symn := M ∈ Matn×n (Fq ) M T = M , where M T denotes the transpose of M . Finally, Sn denotes the set of n × n permutation matrices, which have exactly one entry equal to 1 in each row and each column and all other entries equal to 0. Cryptography. A nonnegative function negl(n) is negligible if, for every c > 0, it is smaller than n−c for all sufficiently large n. We use computational indistinguishability against any quantum polynomial-time (QPT) distinguishers, denoted by ≈c . Complexity. All logarithms are to base 2. All asymptotic statements are with respect to the dimension n as e n → ∞. We write O(n) = O(n · polylog n) for quasi-linear complexity bounds. Probability and Distributions. The uniform distribution over a set X is denoted by Unif(X). For a noise rate ε ∈ (0, 1), let BerFq (ε) denote the distribution over Fq that outputs 0 with probability 1 − ε and a uniformly random element of Fq \ {0} with probability ε.

2

Trapdoored Matrix Distributions

We begin with a general definition of trapdoored matrix distributions. We then formalize our (dual) ringLPN assumptions and review the existing construction that serves as our starting point. Building on this construction, we obtain trapdoored triangular matrices and extend the construction to the invertible matrices. The resulting distributions admit efficient sampling, and their trapdoors support efficient matrix–vector multiplication by both the sampled matrix and its inverse.

2.1

Definition

Definition 2.1 (Trapdoored Matrix Distribution). For any n ∈ N and m = poly(n), let H ⊆ Matn×m (Fq ) be a nonempty family of matrices and F = {fi : H × Xi → Yi } be a family of mappings. An efficiently samplable distribution D over tuples (M, {Cfi ,M }), where M ∈ H and each Cfi ,M is a circuit, is called a trapdoored matrix distribution over H supporting F if the following conditions hold: (i) Correctness. For every sampled tuple (M, {Cfi ,M }), every fi ∈ F, and every x ∈ Xi , Cfi ,M (x) = fi (M, x). (ii) Pseudorandomness. The marginal distribution of M under D is computationally indistinguishable from Unif(H). Namely, for every QPT distinguisher A, for all sufficiently large n, with m = poly(n) as above, Pr (M,{C})←D

[A(M ) = 1] −

Pr

U ←Unif(H)

5

[A(U ) = 1] ≤ negl(n).

The circuit family {Cfi ,M } is called the trapdoor for M . For any fixed H ⊆ Matn×m (Fq ), we define the matrix–vector multiplication map n mult : H × Fm q → Fq ,

mult(H, x) = Hx,

and the transpose multiplication map multT : H × Fnq → Fm q ,

multT (H, x) = H T x.

When n = m, we also define the inverse multiplication map ( H −1 x, n n inv : H × Fq → Fq ∪ {⊥}, inv(H, x) = ⊥,

if H is invertible, otherwise,

and the inverse-transpose multiplication map ( T

inv : H × Fnq → Fnq ∪ {⊥},

T

inv (H, x) =

(H T )−1 x = (H −1 )T x, ⊥,

if H is invertible, otherwise.

We track the sampling complexity of the distribution and the evaluation complexity of its trapdoor circuits, as formalized below. Definition 2.2 (Sampling and Trapdoor Efficiency). Let D be a trapdoored matrix distribution supporting F = {fi }. We say that D is T -samplable if a description of a tuple drawn from D can be sampled in time T with overwhelming probability.1 We say that D supports Ti -efficient evaluation of fi if, with overwhelming probability, the sampled circuit Cfi ,M can be evaluated in time Ti on every input. Remark 2.3 (Sampling trapdoors and explicit representations). Sampling efficiency measures the time needed to produce the trapdoor, which also serves as a succinct description of the sampled matrix M . Constructing the full array of entries of M from this description incurs an additional cost, accounted for separately. In the pseudorandomness experiment, the distinguisher receives this explicit matrix representation, without the trapdoor. The same convention applies to our trapdoored Clifford operators: the sampled trapdoor fully determines the operator, whereas the distinguisher receives its signed tableau without the trapdoor.

2.2

Base Construction from (Dual) Ring-LPN Assumptions

The standard decisional learning parity with noise (LPN) assumption concerns noisy linear equations over F2 [BFKL93, Ale03, LM13]; we use its analogue over a fixed finite field Fq [BCGI18]. For a suitable noise rate ε > 0, this assumption asserts that polynomially many samples (ri , ri · s + ei ),

ri ← Unif(Fnq ), ei ∼ BerFq (ε),

with a shared secret s ← Unif(Fnq ) are jointly computationally indistinguishable from independent uniform samples in Fnq × Fq . The vectors ri and errors ei are sampled independently of one another and of s. Ring-LPN is a structured variant of LPN in which the noisy linear equations are defined over a polynomial quotient ring [HKL+ 12, BCG+ 20]. We consider the ring R = Fq [x]/(xn − 1) and sample a shared secret s ← Unif(R). For a suitable noise rate ε > 0, each error is a polynomial ei (x) =

n−1 X

eij xj ,

eij ∼ BerFq (ε).

j=0 1 Here, overwhelming probability means probability at least 1 − negl(n) over the sampling randomness. This qualification concerns efficiency only; correctness holds for every sampled tuple.

6

The corresponding decisional ring-LPN assumption asserts that polynomially many samples ri ← Unif(R),

(ri , ri s + ei ),

are jointly computationally indistinguishable from independent uniform samples in R × R. All ri and error coefficients eij are sampled independently of one another and of s, and all operations are performed in R. A dual-LPN assumption is specified by an efficient sampler for a public matrix H ∈ Matn×k (Fq ), where n < k = poly(n). For a specified matrix distribution and suitable noise rate ε > 0, the dual-LPN assumption states that [BCH+ 25] (H, u) ≈c (H, He), u ← Unif(Fnq ), e ∼ BerFq (ε)k . The sampling of H is included in both distributions, and H, e, and u are sampled independently. A standard hybrid argument over the columns then implies that, for any m = poly(n) and the same sampled H, (H, U ) ≈c (H, HE),

U ← Unif(Matn×m (Fq )), E ∼ BerFq (ε)k×m .

Structured LPN variants use public matrices that admit fast matrix–vector multiplication, such as Toeplitz matrices [LM13] and suitable quasi-cyclic matrices [BCG+ 20, AMBD+ 18]. Following [BCH+ 25], we use quasi-cyclic matrices of the form H = [In | C], where C is a uniformly random n × n circulant matrix. Identifying vectors with coefficient vectors in R, multiplication by C corresponds to multiplication by a uniformly random ring element a ∈ R. Thus, writing e = (e0 , e1 ), the syndrome He corresponds to e0 + ae1 , where both e0 and e1 have independent noisy coefficients. We refer to the hardness assumption for this distribution as (dual) ring-LPN ; its secret e1 is sparse, whereas the introductory ring-LPN formulation above uses a uniform secret. Multiplication by H takes O(n log n log log n) field operations via fast polynomial multiplication [CK91], and hence admits a circuit of size O(n log2 n). We formalize this instantiation in two forms, which we call the standard (dual) ring-LPN assumption and the strong (dual) ring-LPN assumption. In each experiment below, the displayed random variables are sampled independently, and the probability also includes the distinguisher’s internal randomness and measurement outcomes. Let Qn denote the following family of quasi-cyclic matrices:  Qn := [In | C] | C is an n × n circulant matrix . Conjecture 2.4 (Standard Ring-LPN Assumption in Dual Form [BCH+ 25]). For a suitable noise rate ε(n) > 0 satisfying nε(n) 1 −→ ∞, ε(n) < , 2 4 log n every QPT distinguisher A satisfies

Pr Q←Unif(Qn ) e←BerFq (ε(n))2n

[A(Q, Qe) = 1] −

Pr

[A(Q, u) = 1] ≤ negl(n)

Q←Unif(Qn ) u←Unif(Fn q)

for all sufficiently large n. The negligible function may depend on A and ε. In particular, we conjecture that this assumption holds for ε(n) = (log n)c /n with any fixed c > 2; these rates satisfy the stated parameter restrictions for all sufficiently large n. Motivated by the subexponential LPN assumption in [VZ26], we also consider a quantitative assumption against quantum distinguishers. Conjecture 2.5 (Strong Ring-LPN Assumption in Dual Form). There exists a constant α ∈ (0, 1) such that, for any suitable noise rate ε(n) > 0 satisfying nε(n) −→ ∞, log2 n

7

ε(n) <

1 , 4

α

every quantum 2(nε(n)) -time distinguisher A satisfies

Pr

[A(Q, Qe) = 1] −

Q←Unif(Qn ) e←BerFq (ε(n))2n

Pr

[A(Q, u) = 1] ≤ 2−(nε(n))

α

Q←Unif(Qn ) u←Unif(Fn q)

for all sufficiently large n. The strong assumption quantifies security as a function of the noise rate on the stated parameter range. For ε(n) = (log n)c /n with c > 2 and cα > 1, it guarantees negligible advantage against every QPT distinguisher. α α For any fixed noise rate ε ∈ (0, 1/4), it assumes security against 2(nε) = 2Θ(n ) -time quantum algorithms, α α with advantage at most 2−(nε) = 2−Θ(n ) . Several constructions of trapdoored matrix distributions over Matn×m (Fq ) are known under variants of the LPN assumption [BN25, BCH+ 25, VZ26]. We use the (dual) ring-LPN construction of [BCH+ 25], instantiated with the quasi-cyclic matrix family Qn . The following lemma states its guarantees in terms of our efficiency definition. Lemma 2.6 ([BCH+ 25]). Let n ∈ N, m = Θ(n), and ε(n) = (log n)c /n for a fixed constant c > 2. Under Conjecture 2.4 at noise rate ε(n), there exists an O(nmε)-samplable trapdoored matrix distribution over Matn×m (Fq ) supporting O(nmε)-efficient evaluation of mult. Proof. Independently sample H = [In | C] ← Unif(Qn ) and E ∼ BerFq (ε)2n×m , and set M = HE. The trapdoor evaluates M x as H(Ex), so correctness is immediate. Pseudorandomness follows from Conjecture 2.4 by the column hybrid argument above. Let W denote the number of nonzero entries of E, so that E[W ] = 2nmε. Sparse multiplication by E costs O(n + m + W ), while quasi-cyclic multiplication by H costs O(n log2 n). Thus the expected circuit size is O(nmε + n log2 n), as in [BCH+ 25, Proposition 5.1]. For sampling, we store only the n defining coefficients of C and the nonzero entries of E. Exact geometric skipping [BF13a] generates these sparse entries in expected time O(nmε), giving the same expected bound for sampling the succinct matrix description and its trapdoor circuit. By a Chernoff bound, W = O(nmε) with overwhelming probability, since nmε = Θ(n(log n)c ). Hence the sampled circuit runs in O(nmε + n log2 n) time on every input with overwhelming probability. Concentration of the gap-sampling times gives the same bound for sampling.2 Finally, m = Θ(n) and c > 2 imply n log2 n = o(nmε), so the sparse-error contribution dominates the quasi-cyclic cost: O(nmε + n log2 n) = O(nmε). Both efficiency requirements of Definition 2.2 follow.

2.3

Trapdoored Triangular Matrices

For n, m ∈ N with m = Θ(n) and a suitable noise rate ε(n) > 0, let DM (n, m, ε) denote the trapdoored matrices distribution over Matn×m (Fq ) defined in Lemma 2.6. In this subsection, we construct trapdoored matrix distributions over triangular matrices with efficient sampling and trapdoor circuits for mult, multT . The complexity bounds are near-linear under the standard (dual) ring-LPN assumption and quasi-linear under its strong variant. Corollary 2.13 summarizes the results for upper-triangular, lower-triangular, and symmetric matrices. We begin with strictly upper-triangular matrices. Theorem 2.7. Recall that Un◦ denotes the set of n × n strictly upper-triangular matrices. The following statements hold: 2We use a randomized word RAM with Θ(log n)-bit words and polynomial-time precision access to the normalized noise rate. The exact sampler of [BF13a] has uniformly bounded running-time moments of every fixed order; a standard moment bound on O(nmε) independent calls gives the claimed overwhelming-probability runtime.

8

e 1+δ )-samplable (i) Under the standard (dual) ring-LPN assumption, for any 0 < δ < 1, there exists an O(n ◦ 1+δ e trapdoored matrix distribution over Un supporting O(n )-efficient mult. e trapdoored matrix (ii) Under the strong (dual) ring-LPN assumption, there exists an O(n)-samplable ◦ e distribution over Un supporting O(n)-efficient mult. Both parts of Theorem 2.7 use the same sampling algorithm, Algorithm 1 below. Fix an integer c > 2; in the strong case, choose c so that cα > 1, where α is the constant in Conjecture 2.5. The choice of assumption determines the base dimension b. For part (i), we take b = ⌈nδ ⌉ for the chosen 0 < δ < 1; for part (ii), the strong assumption allows us to reduce b to ⌈8 logc n⌉. These choices yield the two complexity bounds in Theorem 2.7. We present the common sampling algorithm and establish its pseudorandomness and efficiency for both choices of b. Algorithm 1 Sampling from a Trapdoored Matrix Distribution over Un◦ Require: Initial dimension n, an integer c > 2, and a base dimension b, chosen as above for the relevant assumption. 1: procedure StrictUpperTriangular(d) 2: if d ≤ b then 3: U ← Unif(Ud◦ ) 4: Let Cmult,U be a O(d2 )-circuit computing x 7→ U x for any x ∈ Fdq . 5: else 6: (M, Cmult,M ) ← DM (⌈d/2⌉, ⌊d/2⌋, (2 logc n)/d) 7: (U1 , Cmult,U1 ) ← StrictUpperTriangular(⌈d/2⌉) 8: (U2 , Cmult,U2 ) ←  StrictUpperTriangular(⌊d/2⌋) U1 M 9: U← 0 U2 ⌈d/2⌉

10: Cmult,U : (x1 , x2 ) 7→ (Cmult,U1 (x1 ) + Cmult,M (x2 ), Cmult,U2 (x2 )) for any x1 ∈ Fq 11: end if 12: return (U, Cmult,U ) 13: end procedure

⌊d/2⌋

, x2 ∈ Fq

.

The following three lemmas establish pseudorandomness, sampling efficiency, and circuit size, respectively. Throughout the remainder of this subsection, we assume that the initial dimension n is a sufficiently large power of 2 and that c is chosen as specified above. Lemma 2.8. The matrix distribution induced by Algorithm 1 is computationally indistinguishable from Unif(Un◦ ) under either of the following parameter choices: under the standard (dual) ring-LPN assumption, take b = ⌈nδ ⌉ for a fixed 0 < δ < 1 and an integer c > 2; under the strong (dual) ring-LPN assumption, take b = ⌈8 logc n⌉ with an integer c > 2 satisfying cα > 1. Proof. Let Hybridi denote the matrix distribution obtained by setting the base dimension in Algorithm 1 to nn o bi = max i , b , 2 while keeping the original n in the noise rates. Then Hybrid0 = Unif(Un◦ ), and HybridL coincides with the output distribution of Algorithm 1, where L = ⌈log(n/b)⌉. Fix a QPT distinguisher A, and write di =

n , 2i

εi =

2i+1 logc n 2 logc n = . di n

For i ∈ [L], adjacent hybrids differ only in 2i−1 off-diagonal blocks: these are uniform in Hybridi−1 and sampled from DM (di , di , εi−1 ) in Hybridi . A hybrid argument over the blocks and then over their di columns 9

reduces distinguishing the two hybrids to distinguishing a uniform vector from Qe, where Q ← Unif(Qdi ) and e ∼ BerFq (εi−1 )2di . The columns within each real block share the same public Q. Choosing a block and a column uniformly gives a single-sample quantum reduction running in time poly(n). Denoting its advantage by ηi , we obtain   ∆i := Pr[A(Hybridi ) = 1] − Pr A(Hybridi−1 ) = 1 n ≤ 2i−1 di ηi = ηi . 2 Under the standard (dual) ring-LPN assumption in Conjecture 2.4, take b = ⌈nδ ⌉ for a fixed 0 < δ < 1. Since di ≥ dL > b/2, for sufficiently large n we have di > Moreover,

nδ , 2

εi−1 =

1 logc n 2 logc n < . < δ di n 4

logc n di εi−1 = ≥ logc−2 n −→ ∞. 2 2 log di log di

Thus the noise rates lie in the required range. Since n < (2di )1/δ , each reduction runs in polynomial time in di . The assumption therefore gives ηi = negl(di ) = negl(n), and summing over the L = O(log n) levels yields L X

L

∆i ≤

i=1

nX ηi = negl(n). 2 i=1

Under the strong (dual) ring-LPN assumption in Conjecture 2.5, take b = ⌈8 logc n⌉. Now di > b/2 ≥ 4 logc n, so logc n di εi−1 1 εi−1 = ≥ logc−2 n −→ ∞. < , di 4 log2 di Hence these noise rates also lie in the required range. Since cα > 1, the time bound α

2(di εi−1 ) = 2(log n)

cα

= n(log n)

cα−1

eventually exceeds the polynomial running time of each reduction. The single-sample advantage is therefore cα bounded by ηi ≤ 2−(log n) , giving L X i=1

∆i ≤

nL −(log n)cα 2 = negl(n). 2

In either case, HybridL is computationally indistinguishable from Hybrid0 , completing the proof. Lemma 2.9. Algorithm 1 runs in time O(n logc+1 n + nb) with overwhelming probability. Proof. Let L = ⌈log(n/b)⌉. At depth i = 0, . . . , L − 1, there are 2i blocks of dimension di = n/2i , each using an error matrix of size di × (di /2) at rate εi = 2 logc n/di . Let Wi be the total number of nonzero error entries at this depth. Then d2 E[Wi ] = 2i · i · εi = n logc n. 2 Chernoff bounds and a union bound over the L = O(log n) depths give Wi = O(n logc n) simultaneously at every depth with overwhelming probability in n. The error matrices are sampled by exact geometric skipping. Applying the sampling-time concentration argument from Lemma 2.6 to the gap calls across all blocks at each depth gives O(n logc n) sampling time with overwhelming probability. Sampling the defining coefficients and constructing the circuits adds O(n log2 n + Wi ) time with overwhelming probability. Since c > 2, the total cost per depth is O(n logc n). 10

The leaf dimensions sum to n and are at most b, so sampling the uniform leaf matrices and constructing their circuits costs O(nb) with overwhelming probability. Summing these costs gives
O n logc n · log(n/b) + nb = O(n logc+1 n + nb), as claimed. Lemma 2.10. With overwhelming probability, the circuit Cmult,U sampled by Algorithm 1 has size O(n logc+1 n+ nb). Proof. Let Wi be the total error weight at depth i, as in the proof of Lemma 2.9. Sparse multiplication contributes O(n + Wi ) gates, while quasi-cyclic multiplication and the additions combining the recursive blocks contribute O(n log2 n) gates. With overwhelming probability, Wi = O(n logc n) at every depth, so c > 2 gives a total of O(n logc n) gates per depth. Summing over the O(log(n/b)) depths and adding the O(nb) gates at the leaves yields O(n logc+1 n + nb), completing the proof. The distribution sampled by Algorithm 1 also supports efficient multT . We obtain the corresponding trapdoor circuit by applying Tellegen’s principle, also known as the transposition principle. For later use, we state the principle in the following general form. Lemma 2.11 (Tellegen’s Principle [BLS03]). Let F be a field and M ∈ Matn×m (F), where n, m ∈ N and m = O(n). Suppose a circuit C of size T (n) computes x 7→ M x using only additions and multiplications by constants in F. Then a circuit C T of size O(T (n) + n) computing y 7→ M T y can be constructed from C in time O(T (n) + n). Remark 2.12. Once the sampled trapdoor is fixed, all circuits we construct for mult and for inv on invertible matrices use only additions and multiplications by field constants. Unrolling any recursive calls therefore yields linear arithmetic circuits to which Lemma 2.11 applies. Throughout the paper, we will invoke this lemma without further comment to obtain the corresponding circuits for multT and invT . Our sampling and circuit-size bounds have the same order and are at least linear in n, so this preserves the stated sampling and evaluation bounds. Combining Theorem 2.7 with Lemma 2.11, we extend the construction to the matrix families in the following corollary. Recall that L0n and Ln denote the sets of strictly lower-triangular and lower-triangular n × n matrices over Fq , respectively, and Symn denotes the set of n × n symmetric matrices over Fq . Corollary 2.13. Let H be any of the matrix families Un◦ , L◦n , Un , Ln , or Symn . Then the following statements hold: e 1+δ )(i) Under the standard (dual) ring-LPN assumption, for any fixed 0 < δ < 1, there exists an O(n 1+δ e samplable trapdoored matrix distribution over H supporting O(n )-efficient evaluation of both mult and multT . e (ii) Under the strong (dual) ring-LPN assumption, there exists an O(n)-samplable trapdoored matrix e distribution over H supporting O(n)-efficient evaluation of both mult and multT . Proof. Sample U from the distribution in Theorem 2.7, and independently sample a diagonal matrix D whose diagonal entries are independent and uniform in Fq . For the five choices of H listed above, use, respectively, U,

U T,

U + D,

U T + D,

U + U T + D.

When U is uniform over Un◦ , these matrices are uniform over their respective families. Pseudorandomness therefore follows by efficient post-processing. Each multiplication circuit uses at most one copy of the circuit for U and one for U T , together with O(n) additional gates for diagonal multiplication and additions. The same holds for transpose multiplication. Sampling D and constructing these circuits preserves the stated sampling and evaluation bounds, completing the proof. 11

2.4

Trapdoored Invertible Triangular Matrices with Efficient Inversion

We now extend the construction in Corollary 2.13 to Un∗ , the group of invertible upper-triangular matrices over Fq (a Borel subgroup of GL(n, Fq )). In addition to matrix–vector multiplication, the resulting trapdoors support the inverse and inverse-transpose actions inv and invT defined in Section 2.1. The following theorem summarizes our guarantees. Theorem 2.14. Let Un∗ denote the group of n × n invertible upper-triangular matrices over Fq . e 1+δ )(i) Under the standard (dual) ring-LPN assumption, for any fixed 0 < δ < 1, there exists an O(n T e 1+δ )-efficient mult, mult , inv, and samplable trapdoored matrix distribution over Un∗ supporting O(n invT . e (ii) Under the strong (dual) ring-LPN assumption, there exists an O(n)-samplable trapdoored matrix T T ∗ e distribution over Un supporting O(n)-efficient mult, mult , inv, and inv . Both parts of Theorem 2.14 use Algorithm 3, with Algorithm 2 as a subroutine. As in the preceding subsection, fix an integer c > 2; in the strong case, also require cα > 1, where α is the constant in Conjecture 2.5. We take b = ⌈nδ ⌉ in part (i) and b = ⌈8 logc n⌉ in part (ii). An upper-triangular matrix is invertible if and only if all its diagonal entries are nonzero. Accordingly, Algorithm 3 forms U ∗ = U + D, where U is sampled by Algorithm 1 and D is an independent, uniformly random invertible diagonal matrix. Algorithm 2 follows the recursive block structure of U to construct a circuit Cinv,U ∗ computing y 7→ (U ∗ )−1 y. The circuit computes the lower diagonal block first and substitutes the result into the upper block; and use back-substitution3 at the base dimension. Algorithm 2 Generating an Efficient Inversion Circuit Require: (U, Cmult,U ) from Algorithm 1, an invertible diagonal matrix D, and the same base dimension b. 1: procedure EfficientInversionCircuit(d, U, Cmult,U , D) 2: U∗ ← U + D 3: if d ≤ b then 4: Construct a size-O(d2 ) circuit Cinv,U ∗ by back-substitution. 5: else 6: d1 ← ⌈d/2⌉, d2 ← ⌊d/2⌋ 7: Obtain the stored block descriptions U1 , U2 , M from U , and write D = diag(D1 , D2 ). 8: Obtain the circuits Cmult,U1 , Cmult,U2 , and Cmult,M from the recursive description of Cmult,U . 9: C1 ← EfficientInversionCircuit(d1 , U1 , Cmult,U1 , D1 ) 10: C2 ← EfficientInversionCircuit(d2 , U2 , Cmult,U2 , D2 ) 11: Define Cinv,U ∗ on input (y1 , y2 ) by: z ← C2 (y2 );
output C1 (y1 − Cmult,M (z)), z . 12: end if 13: return Cinv,U ∗ 14: end procedure Pseudorandomness follows from Lemma 2.8 by common hybrid argument. The sampled multiplication circuit Cmult,U ∗ has the same asymptotic size as in Corollary 2.13, since the diagonal contribution costs only 3 For an invertible upper-triangular matrix A = (a ), back-substitution solves Ax = y by computing ij d   X xi = a−1 yi − aij xj , ii

i = d, d − 1, . . . , 1.

j=i+1

The diagonal inverses are precomputed circuit constants. There are d(d − 1)/2 off-diagonal terms, so constructing and evaluating the circuit both take O(d2 ) time.

12

Algorithm 3 Sampling from a Trapdoored Matrix Distribution over Un∗ Require: Dimension n, with c and b chosen as in Algorithm 1 for the relevant assumption. 1: procedure InvertibleUpperTriangular(n) 2: Sample D = diag(a1 , . . . , an ) with independent ai ← Unif(Fq \ {0}). 3: Construct a size-O(n) circuit Cmult,D computing x 7→ Dx. 4: (U, Cmult,U ) ← StrictUpperTriangular(n) 5: U∗ ← U + D 6: Cmult,U ∗ : x 7→ Cmult,U (x) + Cmult,D (x) 7: Cinv,U ∗ ← EfficientInversionCircuit(n, U, Cmult,U , D) 8: return (U ∗ , Cmult,U ∗ , Cinv,U ∗ ) 9: end procedure

O(n). It remains to establish the correctness of Algorithm 2 and to bound its running time and the size of its output circuit Cinv,U ∗ . Lemma 2.15. Algorithm 2 runs in time O(n logc+1 n + nb) with overwhelming probability over the input sampled by Algorithm 1, for any invertible diagonal matrix D. The same running-time bound holds for Algorithm 3 with overwhelming probability. Proof. We access the input subcircuits through their stored references and construct the output circuit by writing each gate once. At an internal node of dimension d, we copy Cmult,M and add O(d) gates to connect the two recursively constructed inverse circuits. The child circuits are constructed directly in the output, so their gates are not copied again at their parent nodes. By the proof of Lemma 2.10, the total size of the off-diagonal circuits at each depth is O(n logc n) with overwhelming probability, simultaneously over all depths. The connecting gates add P only2 O(n) per depth. There are O(log(n/b)) internal levels. At the leaves, constructing the circuits costs ℓ O(dℓ ) ≤ O(nb), since P dℓ ≤ b and ℓ dℓ = n. Thus the total construction time is
O n logc n · log(n/b) + nb = O(n logc+1 n + nb). For Algorithm 3, Lemmas 2.9 and 2.10 give the same bound for sampling U and constructing the multiplication circuit. Sampling D and handling diagonal multiplication add only O(n) work with overwhelming probability, so the claimed bound follows. Lemma 2.16. For every input satisfying the requirements of Algorithm 2, the constructed circuit Cinv,U ∗ correctly computes y 7→ (U ∗ )−1 y. With overwhelming probability over the input sampled by Algorithm 1, its size is O(n logc+1 n + nb). Proof. Correctness follows by induction on the block dimension d. For d ≤ b, the circuit solves (U + D)x = y by back-substitution. Otherwise, let A1 = U1 + D1 and A2 = U2 + D2 , both of which are invertible. By induction, the algorithm’s circuit computes z = A−1 2 y2 ,

x1 = A−1 1 (y1 − M z).

Hence its output satisfies       x1 A1 x 1 + M z y (U + D) = = 1 , z A2 z y2 proving correctness. Each internal node contributes one off-diagonal multiplication circuit and O(d) additional gates, while each leaf contributes O(d2 ) gates. The gate count in the proof of Lemma 2.15 therefore gives the claimed size bound with overwhelming probability.

13

Substituting the two choices of b into Lemmas 2.15 and 2.16 gives bounds of O(n1+δ ) and O(n logc+1 n), respectively. For each fixed sample, the inverse circuit uses only additions and multiplication by field constants, so Lemma 2.11 also yields an inverse-transpose circuit with the same asymptotic bounds. Together with the pseudorandomness and multiplication guarantees above, this proves Theorem 2.14. As in Corollary 2.13, transposing the sampled matrices gives the same guarantees for the family L∗n of invertible lower-triangular matrices. Transposition simply interchanges mult with multT and inv with invT , preserving all sampling and evaluation bounds.

2.5

Trapdoored Invertible Matrices with Efficient Inversion

We now extend our construction from invertible triangular matrices to the full general linear group GL(n, Fq ), preserving efficient sampling and all four trapdoor operations. The following theorem summarizes the resulting guarantees. Theorem 2.17. Let GL(n, Fq ) denote the group of n × n invertible matrices over Fq . e 1+δ )(i) Under the standard (dual) ring-LPN assumption, for any fixed 0 < δ < 1, there exists an O(n 1+δ e samplable trapdoored matrix distribution over GL(n, Fq ) supporting O(n )-efficient mult, multT , inv, and invT . e (ii) Under the strong (dual) ring-LPN assumption, there exists an O(n)-samplable trapdoored matrix T e distribution over GL(n, Fq ) supporting O(n)-efficient mult, mult , inv, and invT . Our construction relies on the Bruhat decomposition for split reductive groups. In this decomposition, the double cosets of a Borel subgroup partition the group and are indexed by elements of the Weyl group. For GL(n, Fq ), we take the Borel subgroup to be Un∗ and represent the Weyl group by the permutation matrices Sn . This gives the following standard decomposition. Lemma 2.18 (Bruhat decomposition). The group GL(n, Fq ) is the disjoint union of the double cosets Un∗ σUn∗ indexed by σ ∈ Sn , namely, G GL(n, Fq ) = Un∗ σUn∗ . σ∈Sn

To sample uniformly from GL(n, Fq ) via this decomposition, we first choose σ ∈ Sn with probability proportional to the size of its double coset Un∗ σUn∗ . This size is determined by the inversion number of the permutation corresponding to σ, defined by In (σ) := #{(i, j) ∈ [n] × [n] | i < j, σ(i) > σ(j)}. Specifically, Un∗ σUn∗ = Un∗ q In (σ) . These weights define the Mallows distribution on Sn . Definition 2.19 (Mallows Distribution [Mal57]). The Mallows distribution Mn,q on Sn assigns to each σ ∈ Sn the probability Un∗ σUn∗ (q − 1)n q In (σ) Pr [τ = σ] = = Qn . k τ ←Mn,q GL(n, Fq ) k=1 (q − 1) For fixed q, repeated insertion sampling generates σ ← Mn,q in expected time O(n) [LB14]. To obtain a uniform sample from GL(n, Fq ), it remains to sample uniformly within the selected double coset. The following lemma shows that independent uniform triangular factors suffice. Lemma 2.20. If U1 , U2 ← Unif(Un∗ ) and σ ← Mn,q are sampled independently, then U1 σU2 ∼ Unif(GL(n, Fq )). 14

Proof. Write G = GL(n, Fq ) and B = Un∗ . Conditioned on any fixed σ, the pair (AU1 , U2 C) has the same distribution as (U1 , U2 ) for every A, C ∈ B. Thus the distribution of U1 σU2 is invariant under left and right multiplication by B. Since these operations act transitively on BσB, the product is uniform on that double coset. For any M ∈ G, let s ∈ Sn be the unique permutation with M ∈ BsB. By the definition of Mn,q and the conditional uniformity above, Pr[U1 σU2 = M ] = Pr[σ = s] ·

1 |BsB| 1 1 = · = . |BsB| |G| |BsB| |G|

Hence U1 σU2 is uniform over G. For the trapdoored construction, we generate U1 and U2 independently using Algorithm 3 and sample σ independently from Mn,q . A standard hybrid argument, replacing the two triangular factors one at a time and using Lemma 2.20, shows that U1 σU2 is computationally indistinguishable from a uniform element of GL(n, Fq ). Concretely, we independently sample (Ui , Cmult,Ui , Cinv,Ui ) using Algorithm 3 for i ∈ {1, 2}, and sample σ from the Mallows distribution Mn,q independently of both tuples. Since σ and σ −1 simply permute coordinates, their actions admit circuits Cmult,σ and Cinv,σ of size O(n), constructible in O(n) time. Setting G = U1 σU2 , we define its trapdoor circuits by Cmult,G = Cmult,U1 ◦ Cmult,σ ◦ Cmult,U2 , Cinv,G = Cinv,U2 ◦ Cinv,σ ◦ Cinv,U1 . These circuits compute multiplication by G and G−1 , respectively. The resulting distribution preserves the sampling and evaluation bounds of the triangular construction. Finally, Lemma 2.11 supplies circuits for multT and invT with the same asymptotic bounds. Together with the pseudorandomness argument above, this proves Theorem 2.17. Our construction has two further consequences: exact determinant evaluation for sampled matrices and efficient polynomial actions after a pseudorandom change of basis. Corollary 2.21 (Efficient evaluation of determinants). Let M be sampled by the construction in Theorem 2.17. Given its trapdoor, det M can be computed exactly in time O(n). Proof. Write M = U σV as in the construction of Theorem 2.17. The sampler already knows the diagonal entries of U, V and the permutation σ. Let c(σ) be the number of cycles of σ, including fixed points. Traversing these cycles takes O(n) time and gives det σ = (−1)n−c(σ) . Hence ! n ! n Y Y n−c(σ) det M = (−1) Uii Vii i=1

i=1

can be computed exactly in O(n) time. Retaining this value with the trapdoor preserves the sampling bounds and the matrix marginal. Fast forward and inverse actions also allow efficient evaluation of matrix powers after a pseudorandom change of basis. We apply this to block-diagonal matrices with small blocks, whose powers can be computed separately. Corollary 2.22 (Efficient powers of pseudorandom conjugates). Fix a polynomial-time constructible blockdiagonal matrix B = diag(B1 , . . . , Bm ) ∈ Matn×n (Fq ) whose blocks have size at most r = polylog(n). Under the strong (dual) ring-LPN assumption, sample G with its trapdoor from Theorem 2.17 and set A = GBG−1 . Then A is computationally indistinguishable from a uniform element of the conjugacy class Cl(B) = {P BP −1 : P ∈ GL(n, Fq )}. e Given the blocks of B and the trapdoor for G, we can compute Ak v in O(n) time for every v ∈ Fnq and every O(1) integer 1 ≤ k ≤ n , including the computation of the block powers. 15

Proof. For uniform P ∈ GL(n, Fq ), the matrix P BP −1 is uniform on Cl(B). Since B is polynomial-time constructible and conjugation is polynomial-time computable, the pseudorandomness of G gives the first claim. For the power action, use
k Ak v = G diag(B1k , . . . , Bm )(G−1 v) . P Writing ri for the size of Bi , repeated squaring computes the block powers in O( i ri3 log(k + 1)) = P e e O(nr2 log(k + 1)) = O(n) time. Applying the precomputed blocks takes O( i ri2 ) = O(nr) = O(n) time, e and the two changes of basis also take O(n) time using the trapdoor. Correctness holds for every sample, and the resource bound follows from Theorem 2.17. e 1+δ ) time Under the standard (dual) ring-LPN assumption, the same evaluation guarantee holds in O(n −1 for any fixed 0 < δ < 1. More generally, the identity f (A) = Gf (B)G transfers any linear circuit for f (B)v to one for f (A)v with only the cost of the two changes of basis added. The pseudorandomness guarantee is relative to Cl(B): conjugation preserves the characteristic polynomial and other similarity invariants of B.

2.6

Depth-Efficient Implementation

We modify Algorithms 2 and 3 so that all trapdoor circuits have poly-logarithmic depth, while preserving the preceding sampling and circuit-size bounds. The key change is to sample each block in the factored form  ∗   ∗   U1∗ M U1 0 Id1 M U U∗ = 1 = . 0 U2∗ 0 U2∗ 0 Id2 Then, we have    Id1 −M (U1∗ )−1 0 0 Id2 0 (U2∗ )−1 . For the inverse matrix–vector multiplication we first applies the two diagonal inverses in parallel and then subtracts M times the lower output from the upper output. We measure classical depth using bounded-fan-in linear arithmetic circuits over the fixed field Fq , with unrestricted fan-out. Formally, we state as following theorem: (U ∗ )−1 =

Theorem 2.23 (Depth Optimization). Theorems 2.14 and 2.17 admit modified samplers with the same sampling and circuit-size bounds, whose circuits for mult, multT , inv, and invT have depth O(log2 n). The recursion continues to dimension 1, but uses uniform off-diagonal blocks whenever d ≤ b; the hardness assumption is used only above this cutoff. This also avoids constructing dense inverse matrices at the leaves. We also assume that the initial dimension n is large power of 2. Proof. The correctness of each circuit is clear. For the pseudorandomness, since U1∗ is always invertible, the map M 7→ U1∗ M forms a bijection. This implies that the distribution of U1∗ M is computationally indistinguishable from uniform random matrices. As we mentioned, although the recursion continues to dimension 1, for nodes d ≤ b is filled by uniform random matrices. Hence, same with the proof of Theorem 2.14 the distribution of U ∗ is computationally indistinguishable from uniform distribution. Now we prove the depth bound. At a node of dimension d > b, the stored description is M = HE, where H = [Id1 | C] and C is circulant. Balanced sums implement both E and E T in depth O(log d). Fast polynomial multiplication [CK91], with the circulant coefficients fixed, gives a linear circuit for C of size O(d log2 d) and depth O(log d). Since C T is also circulant, the same bounds hold for H and H T . At dimensions 1 < d ≤ b, balanced matrix–vector multiplication gives the same depth bound for M and M T . In each of the four factorizations above, the two diagonal-block actions run in parallel, and the shear adds only O(log d) depth. Thus their maximum depth D(d) satisfies D(1) = O(1),

D(d) ≤ D(d/2) + O(log d),

2

which gives D(n) = O(log n). Finally, replace the triangular samplers in Section 2.5 by Algorithm 4. This proves the claim for Theorem 2.17 as well. 16

Algorithm 4 Sampling Depth-Efficient Trapdoored Matrices over Un∗ Require: Initial dimension n(assumed power of 2), with c and b as in Algorithm 1. 1: procedure OptimizedInvertibleUpper(d) 2: if d = 1 then 3: Sample a ← Unif(Fq \ {0}). 4: return ([a], x 7→ ax, y 7→ a−1 y) 5: end if 6: if d ≤ b then 7: M ← Unif(Matd/2×d/2 (Fq )) 8: Construct a size O(d2 )-circuit Cmult,M 9: else 10: (M, Cmult,M ) ← DM (d1 , d2 , (2 logc n)/d) 11: end if 12: For i = 1, 2, (Ui∗ , Cmult,Ui∗ , Cinv,Ui∗ ) ← OptimizedInvertibleUpper(d/2)  ∗   U1 0 Id1 M ∗ 13: U ← 0 U2∗ 0 Id2 14: Define Cmult,U ∗ on input (x1 , x2 ) by: z ← x1 + Cmult,M (x2 );
output Cmult,U1∗ (z), Cmult,U2∗ (x2 ) . 15: Define Cinv,U ∗ on input (y1 , y2 ) by: compute v ← Cinv,U1∗ (y1 ) and w ← Cinv,U2∗ (y2 ) in parallel;
output v − Cmult,M (w), w . 16: return (U ∗ , Cmult,U ∗ , Cinv,U ∗ ) 17: end procedure

3

Trapdoored Clifford Distributions

We now use the trapdoored matrix distributions from Section 2 to construct trapdoored Clifford Operators: efficiently samplable Clifford operators together with trapdoors, such that computationally indistinguishable from uniform and the trapdoors support efficient evaluation of selected actions. In this case, both classical actions and quantum actions are considered. The size of quantum circuits are determined by the number of basic Clifford operators including X, H, P, CX and number of ancilla qubits. Let P n and C n denote the Pauli and Clifford operators ignoring global phases, respectively. Throughout this section, the underlying field is F2 . Clifford operators act on P n ≃ F2n 2 by conjugation. We order the Pauli generators as X1 , . . . , Xn , Z1 , . . . , Zn . With this convention, a label (a, b) ∈ Fn2 × Fn2 specifies the Pauli operator represented by X a Z b .

3.1

Uniform random Clifford Oprators and Decomposition of Clifford Operators

Our construction builds on the uniform Clifford sampler of Bravyi and Maslov [BM21]. We recall the matrix parameters underlying this sampler, with the aim of replacing its uniform matrix distributions by the trapdoored distributions from Section 2. The Hadamard-free Clifford operators are those Clifford operators that map each computational basis state to another computational basis state, up to a phase. We denote them by F n ⊆ C n . Up to global phase, every F ∈ F n is specified by vectors a, b ∈ Fn2 , a symmetric matrix Γ ∈ Symn , and an invertible matrix ∆ ∈ GL(n, F2 ). Its action on computational basis can be written by T

F |x⟩ = iQΓ (x) (−1)b ∆x |∆x ⊕ a⟩ ,

17

x ∈ Fn2 .

Here, ∆x ⊕ a and bT ∆x are computed over F2 , while the quadratic phase QΓ (x) is defined by QΓ (x) := xT Γx =

n X

Γjj xj + 2

j=1

X

Γjk xj xk

(mod 4).

1≤j<k≤n

We denote this operator by F (a, b, Γ, ∆) = F . To decompose Clifford operators, we use the Borel subgroup B n ⊆ F n , obtained by restricting ∆ to invertible lower-triangular matrix in L∗n . Let Hi denote the Hadamard gate on the i-th qubit, and identify Sn with the group of qubit permutations. The set of Clifford operators admits the Bruhat decomposition [BM21, Theorem 1] ! n G G Y hi Cn = Bn Hi S Bn . h∈{0,1}n S∈Sn

i=1

A convenient variant of the Bravyi–Maslov sampler chooses (h, S) from their quantum Mallows distribution Section 3] and, independently, two uniform4 Borel factors FL , FR ∈ B n . Then C = Qn [BM21, hi FL ( i=1 Hi )SFR is uniform on C n : the quantum Mallows law selects each double coset with probability proportional to its size, and the two independent uniform Borel factors give a uniform element within that coset due to Lemma 2.20. e Sampling (h, S) takes O(n) time [BM21, Lemma 6]. Each uniform Borel factor is obtained by independently n sampling a, b ∈ F2 , Γ ∈ Symn , and ∆ ∈ L∗n uniformly, so sampling and recording the full factorization takes O(n2 ) time. In the following subsections, we replace these uniform symmetric and lower-triangular matrices by the trapdoored distributions from Section 2, while retaining the quantum Mallows law and uniform Pauli corrections. We first construct trapdoored Hadamard-free Clifford operators and then obtain trapdoored distributions over all Clifford operators.

3.2

Trapdoored Hadamard-free Clifford Operators

We construct trapdoored Clifford operators over F n and B n , supporting both application on quantum states and tableau action on Pauli labels. For any F = F (a, b, Γ, ∆) ∈ F n , we define the quantum action app by app(F, |ψ⟩) := F |ψ⟩ for every n-qubit state |ψ⟩, extending the computational-basis action in Section 3.1 by linearity. Conjugation ′ ′ by F maps X p1 Z p2 to X p1 Z p2 up to a global phase. The induced classical action on Pauli labels is      ∆ 0 ∆p1 p1 tab(F, [p1 , p2 ]T ) := [p′1 , p′2 ]T = = , ∆−T Γ ∆−T p2 ∆−T (Γp1 + p2 ) where ∆−T = (∆−1 )T . We use the trapdoor framework of Section 2.1, with a quantum circuit Qapp,F 5 and a classical circuit Ctab,F . We say that the trapdoor quantum circuit supports T -efficient quantum application if, with overwhelming probability over sampling, Qapp,F uses O(T ) of basic Clifford gates X, H, P, CX and r = O(T ) ancillary qubits, with gates allowed between any pair of qubits. The sampled quantum circuit Qapp,F must satisfy ⊗r
⊗r Qapp,F |ψ⟩ ⊗ |0⟩ = F |ψ⟩ ⊗ |0⟩ for every n-qubit state |ψ⟩. In particular, the ancillary qubits are initialized and returned to zero. Sampling complexity includes producing a succinct description of F and both trapdoor circuits; efficiency for classical action tab is defined same as in Definition 2.2. 4 In the original paper, they state the canonical form of each Clifford operators by restricting the parameters of left Borel operator. Since this decomposition is based on Bruhat decomposition, Lemma 2.20 can be applied here. Hence, we consider that FL , FR ∈ Bn sampled uniformly. 5We use Q to denote quantum circuits, to avoid confusion between classical circuits.

18

Theorem 3.1 (Trapdoored Hadamard-free Clifford Operators). Let H be either F n or B n . The following statements hold: e 1+δ )(i) Under the standard (dual) ring-LPN assumption, for any fixed 0 < δ < 1, there exists an O(n 1+δ e samplable trapdoored distribution over H supporting O(n )-efficient quantum application app and classical evaluation of tab. e (ii) Under the strong (dual) ring-LPN assumption, there exists an O(n)-samplable trapdoored distribution e over H supporting O(n)-efficient quantum application app and classical evaluation of tab. In each case, the distribution of F , represented by F (a, b, Γ, ∆), is computationally indistinguishable from Unif(H), in the sense of Definition 2.1. e 1+δ ), O(n)} e Proof. We give a common construction for both parts, writing T (n) ∈ {O(n for the corresponding sampling and circuit-size bound from Section 2. Independently sample a, b ← Unif(Fn2 ), a uniform diagonal matrix D, and U with its trapdoor from Algorithm 1. Set Γ = U + U T + D, retaining the circuit for U . Independently sample ∆ with its trapdoor: for H = B n , transpose a sample from Theorem 2.14; for H = F n , use Theorem 2.17. These constructions supply circuits for ∆, ∆−1 , and ∆−T with the stated bounds. Replacing U and ∆ by independent uniform matrices, one at a time, gives computationally indistinguishable hybrids by the corresponding matrix guarantees. In the final hybrid, Γ is uniform over Symn , since (U, D) 7→ U + U T + D is a bijection. Thus all four parameters of F are independent and uniform over their respective domains, yielding a uniform element of H by the parameterization in Section 3.1. For Ctab,F , compute Γp1 as U p1 + U T p1 + Dp1 , and then compute the two output blocks ∆p1 and −T ∆ (Γp1 + p2 ). The retained circuits and Lemma 2.11 give both circuit construction and evaluation in O(T (n)) time. To construct Qapp,F , we first make the linear circuits reversible. A size-s XOR circuit for a matrix M yields the operation EM : |x⟩ |y⟩ 7−→ |x⟩ |y ⊕ M x⟩ using O(s + n) CNOT gates and ancillary qubits: compute the intermediate values into fresh qubits, XOR the outputs into the second register, and reverse the intermediate computation. All additional workspace is returned to zero and is omitted from the notation. The matrix circuits above are linear over F2 , so this applies with s = O(T (n)). For the quadratic phase, use QΓ (x) =

n X

Djj xj + 2(xT U x mod 2)

(mod 4).

j=1

Apply EU to compute U x into a zero register, apply a CZ gate between each pair of corresponding qubits in T the two registers, and then reverse EU . This produces the phase (−1)x U x and resets the second register to zero. Applying P = diag(1, i) to each qubit j with Djj = 1 supplies the diagonal phase, giving iQΓ (x) . Next, implement the linear change of basis labels by E

SWAP

E

−1

∆ |x⟩ |0n ⟩ −−→ |x⟩ |∆x⟩ −−−−→ |∆x⟩ |x⟩ −−∆ −−→ |∆x⟩ |0n ⟩ .

Finally, apply Z b followed by X a . The resulting action is exactly F |x⟩ ⊗ |0n ⟩, including its phase, and all ancillary qubits are returned to zero. Correctness on arbitrary input states follows by linearity. Each sampled linear circuit is used only a constant number of times, with O(n) additional gates for the phases, register swap, and Pauli correction. Hence Qapp,F has O(T (n)) basic Clifford gates and ancillary qubits, and its gate list can be constructed in O(T (n)) time. Sampling the succinct parameters and constructing e 1+δ ) and O(n) e both trapdoor circuits therefore preserve the O(n bounds in the two cases. Correctness holds for every sample; all resource bounds hold with overwhelming probability, as in the underlying matrix constructions. 19

The construction of Theorem 3.1 also supports the inverse actions app−1 and tab−1 with the same asymptotic bounds. The inverse quantum action is app−1 (F, |ψ⟩) := F −1 |ψ⟩, whose computational-basis action is −1 T F −1 |y⟩ = i−QΓ (∆ (y⊕a)) (−1)b (y⊕a) ∆−1 (y ⊕ a) . The inverse tableau action is −1

tab

T

(F, [p1 , p2 ] ) = tab(F

−1

∆−1 , [p1 , p2 ] ) = Γ∆−1 T



0 ∆T

    ∆−1 p1 p1 = . p2 Γ∆−1 p1 + ∆T p2

Reversing Qapp,F implements app−1 with only constant overhead, since P −1 = P 3 and the other basic gates are self-inverse. For tab−1 , the retained circuits for Γ and ∆−1 , together with the circuit for ∆T obtained by Lemma 2.11, give the same O(T (n)) construction and evaluation bounds. Let Fi = F (ai , bi , Γi , ∆i ) ∈ F n for i = 1, 2. Inversion and composition satisfy the following parameter identities [BM21, Proposition 1], up to global phase:
−T −1 −1 F1−1 = F ∆−1 , 1 a1 , b− , ∆1 Γ1 ∆1 , ∆1
T F1 ◦ F2 = F a1 ⊕ ∆1 a2 , b12 , Γ2 + ∆2 Γ1 ∆2 , ∆1 ∆2 . Here F1 ◦ F2 applies F2 first, and b− , b12 ∈ Fn2 are the resulting Pauli-Z correction vectors, including the linear phases generated when the quadratic phases are reduced modulo 4. All matrix and vector operations in these identities are over F2 . When F1 and F2 have trapdoors as above with circuit-size bound T (n), the Pauli correction vectors can be recovered in O(nT (n)) time by comparing the computational-basis phases at 0, e1 , . . . , en with the corresponding canonical quadratic phases, where ej is the j-th standard basis vector. The transformed matrix parameters retain O(T (n))-size multiplication circuits, since their actions are sums or compositions of a constant number of the original matrix actions; the required inverse and transpose actions for the new ∆ parameters are obtained similarly. Composing the forward and inverse action circuits already constructed also gives O(T (n))-size circuits for app, app−1 , tab, and tab−1 of the resulting operators, without requiring explicit recovery of the new Pauli correction vectors.

3.3

Trapdoored Clifford Operators

We now extend the construction to the full family of Clifford operators, obtaining our main result. Starting from the Bravyi–Maslov sampler recalled in Section 3.1, we replace its two uniform Borel factors by independent samples from the trapdoored distribution of Theorem 3.1. The resulting operator distribution remains computationally indistinguishable from uniform, while the retained trapdoors support both quantum application and classical tableau action. The construction preserves the sampling and evaluation bounds of the Hadamard-free case: sampling the Hadamard and permutation layers takes quasi-linear time, and their actions incur only linear overhead. Theorem 3.2 (Trapdoored Clifford distributions). The following statements hold: e 1+δ )(i) Under the standard (dual) ring-LPN assumption, for any fixed 0 < δ < 1, there exists an O(n 1+δ e samplable trapdoored Clifford distribution over C n supporting O(n )-efficient quantum application app and classical evaluation of tab. e (ii) Under the strong (dual) ring-LPN assumption, there exists an O(n)-samplable trapdoored Clifford e distribution over C n supporting O(n)-efficient quantum application app and classical evaluation of tab. In each case, the operator marginal is computationally indistinguishable from Unif(C n ), in the sense of Definition 2.1. e 1+δ ), O(n)} e Proof. We give a common construction for both parts, writing T (n) ∈ {O(n for the corresponding sampling and circuit-size bound in Theorem 3.1. Independently sample F1 , F2 ∈ B n with their trapdoors 20

from that theorem, taking H = B n . Independently of these factors, sample (h, S) from the quantum Mallows e distribution in O(n) time [BM21, Lemma 6], and set Hh :=

n Y

h

Hj j ,

C := F1 Hh SF2 .

j=1

Replacing F1 and then F2 by independent uniform Borel operators gives computationally indistinguishable hybrids by Theorem 3.1, since the product defining C is polynomial-time computable from classical descriptions of its factors. In the final hybrid, C is uniform on C n by the sampler in Section 3.1. Thus the operator marginal is pseudorandom against QPT distinguishers. For quantum application, concatenate the circuits in the same order: Qapp,C = Qapp,F1 ◦ (Hh S) ◦ Qapp,F2 , where each factor acts on the data register and its own ancillary register, and is extended by the identity on the other ancillary registers. The Hadamard layer uses at most n gates, and S can be implemented using at most n − 1 SWAP gates, each consisting of three CNOT gates. Hence Qapp,C uses O(T (n)) basic Clifford gates and ancillary qubits, implements C on every input state, and returns all ancillary qubits to zero. For the classical tableau action, let Dh = diag(h1 , . . . , hn ) and let ΠS be the permutation matrix satisfying ΠS ej = eS(j) . With our ordering of the Pauli labels, the two middle layers have tableaux     In − D h Dh ΠS 0 THh = , TS = . Dh In − D h 0 ΠS Therefore TC = TF1 THh TS TF2 . Construct Ctab,C by applying these four actions from right to left, using the sampled circuits for F1 and F2 . The two middle actions only permute Pauli-label bits and take O(n) time, so both construction and evaluation of Ctab,C take O(T (n)) time. Sampling the succinct factor descriptions and constructing both trapdoor circuits therefore preserve the e 1+δ ) and O(n) e O(n bounds in the two cases. Correctness holds for every sample; all resource bounds hold with overwhelming probability, as in Theorem 3.1. The same modification of Section 2.6 also gives depth-efficient Clifford implementations. A size-s, depth-d XOR circuit can be implemented reversibly using O(s + n) CNOT gates and clean ancillary qubits, with depth O((d + 1) log(s + n)): replace fan-out by binary CNOT copying trees, compute the intermediate values, copy the outputs, and uncompute. The strictly upper-triangular circuits used for quadratic phases likewise have depth O(log2 n), using the same shallow off-diagonal circuits and balanced sums at the leaves. Thus, using the modified matrix samplers, the constructions of Theorems 3.1 and 3.2 support quantum application and its inverse in depth O(log3 n), with the same gate-count and ancilla bounds. Here we use the all-to-all connectivity model of Section 3.2; any qubit permutation is a product of two layers of disjoint SWAP gates.

4

Applications

4.1

Clifford authentication

We prove that the use of trapdoored Cliffords in authentication gives information-theoretical soundness. We begin by recalling the definitions. Definition 4.1 (One-time quantum authentication [DNS12]). A quantum authentication scheme (QAS) consists of a tuple of QPT algorithms (KeyGen, Enc, Dec) where Dec outputs a message or ⊥. Let k ← KeyGen. • (Completeness) Deck ◦ Enck = idM for every key k.

21

• (ε-soundness) For every attack channel Λ on the ciphertext and side information E, there are completely positive maps Φacc , Φrej on E, whose sum is trace-preserving, such that 1 ∥Ek [(Deck ⊗ idE ) ◦ Λ ◦ (Enck ⊗ idE )] − I∥⋄ ≤ ε, 2 where I(ρM E ) = (idM ⊗ Φacc )(ρM E ) + |⊥⟩ ⟨⊥| ⊗ Φrej (TrM ρM E ). Definition 4.2 (Trapdoored Clifford authentication). Let n = ℓ + e and ε = 2−e , with e ≥ 1. The trapdoored Clifford authentication scheme is as follows. KeyGen: Generate a trapdoored Clifford C, and independently sample a uniform random Pauli P and a uniform qubit permutation π. Write k to denote them and Ck = P πC for simplicity. ⊗e Enc: Apply Ck to |ψ⟩ ⊗ |0⟩ . Dec: Apply Ck† and measure the last e qubits. Return the first ℓ qubits if the outcome is 0e , and ⊥ otherwise. Under the strong (dual) ring-LPN assumption of Theorem 3.2, key generation, encoding, and decoding run in time n1+o(1) with overwhelming probability, using the retained circuit and its reversal. Theorem 4.3. Under the pseudorandomness assumption of Theorem 3.2, trapdoored Clifford authentication is a QAS with perfect completeness and (ε + negl(n))-soundness. Proof sketch. We use the fact that averaging over P cancels the cross terms in the Pauli Pexpansion of any attack [ABOEM17, Lemma 5.1]. From this, it suffices to consider the attack of the form Q Q ⊗ ΦQ , where P Q(σ) = QσQ† , the maps ΦQ are completely positive, Q ΦQ is trace-preserving, and they are independent of V := πC. Thus it suffices to bound the acceptance probability of every Q ̸= I. For uniform random Clifford C, the Pauli-partitioning lemma and the counting argument in the proof of [ABOEM17, Theorem 1.4] give   4ℓ 2e − 1 Pr V † QV has only I, Z on the last e qubits = n < 2−e 4 −1

(1)

for every Q = ̸ I. Averaging over the uniform qubit permutation π makes this probability depend only on the numbers of X, Y , and Z in Q. There are only polynomially many such choices, and the event above can be tested efficiently using C and C † . Now we consider the case of trapdoored Cliffords. Suppose that some Q had acceptance probability (the left-hand side of Eq. (1)) at least p0 + 1/ poly(n) for p0 = (4ℓ 2e − 1)/(4n − 1). Note that the acceptance probability is characterized by the numbers of its X, Y , and Z factors because of π. There are polynomially many cases, so we can test them to determine if there exists such Q. This gives an efficient distinguisher for two cases, contradicting the pseudorandomness. Thus every Q ̸= I has acceptance probability at most p0 + negl(n) < ε + negl(n) uniformly. Completeness is immediate.

4.2

Worst-case to Average-case Reductions

We revisit the worst-case to average-case reductions for linear algebra problems and consider some Clifford problems.6 Iterated matrix multiplication. We extend the worst-to-average-case reductions for linear algebra [VZ26] to products of many invertible matrices. Theorem 4.4. Let Fq be a fixed finite field, let d = d(n) ≥ 2 be polynomially bounded, and let ε > 0. Assume the strong (dual) ring-LPN assumption. Let A : GL(n, Fq )d → Fn×n be a randomized polynomial-time q algorithm running in time T (n) such that, for every sufficiently large n,   Pr A(B1 , . . . , Bd ) = Bd · · · B1 ≥ ε. B1 ,...,Bd ←Unif(GL(n,Fq ))

6 The results of this section requires nonuniform variants of the strong LPN assumption, which was implicit in [VZ26].

22

Then we can construct an algorithm that, for any A1 , . . . , Ad ∈ GL(n, Fq ), computes Ad · · · A1 with high e (n)). probability, in time O(T Proof. Let A1 , . . . , Ad be the input matrices. Independently sample trapdoored matrices R1 , . . . , Rd from −1 2 e Theorem 2.17, and let R0 = I. Define Bi = Ri Ai Ri−1 for i ∈ [d], which can be computed in time O(dn ) using trapdoors. We observe that Bd · · · B1 = Rd Ad · · · A1 . Thus, whenever A is correct, Y = Rd−1 A(B1 , . . . , Bd ) equals the desired product. By pseudorandomness, the candidate Y equals Ad · · · A1 with probability at least ε − negl(n). We verify 2 e correctness with high probability in O(dn ) time using Freivalds’ algorithm. For sufficiently large n, each trial succeeds with probability at least ε/2. Repeating O( logε n )  the procedure  2 e T (n)+dn as desired. times gives the correct product with high probability. The total running time is O ε

Determinant computation. We improve the determinant reductions of [VZ26] using the exact determinants provided by Corollary 2.21. Qn Theorem 4.5. Let Fq be a fixed finite field, let ε > 0, and let sq,n = 1 − j=1 (1 − q −j ). Assume the strong (dual) ring-LPN assumption. Let A : Fn×n → Fq be a randomized polynomial-time algorithm running in time q T (n) such that, for every sufficiently large n, ( s2,n + ε, q = 2, Pr [A(B) = det B] ≥ (1 + s )/2 + ε, q > 2. B←Unif(Fn×n ) q,n q Then we can construct an algorithm that, for any A ∈ Fn×n , computes det A with high probability, in time q e O(T (n)). For q > 2, it also suffices that A succeeds with probability at least 1/2 + ε on uniform GL(n, Fq ). Proof sketch. We adapt the proofs of [VZ26, Lemmas 6.6 and 6.7], using the exact determinant of each sampled mask instead of computing it with the average-case algorithm. For q > 2, sample a trapdoored R ∈ GL(n, Fq ), compute det R exactly in O(n) additional time by Corollary 2.21, and set Z = A(RA)/ det R. Since a uniform matrix is singular with probability sq,n , the all-matrix promise gives [A(B) = det B] ≥

Pr

B←Unif(GL(n,Fq ))

ε (1 + sq,n )/2 + ε − sq,n 1 1 = + ≥ + ε. 1 − sq,n 2 1 − sq,n 2

First analyze the case where R is uniform on GL(n, Fq ). If A is invertible, the matrix RA is uniform over GL(n, Fq ), so Pr[Z = det A] ≥ 1/2 + ε. If A is singular, det R is uniform over F× q even conditioned on RA, so each nonzero value of Z has probability at most 1/(q − 1) ≤ 1/2. Repeat this computation independently t = O(ε−2 log n) times. If some nonzero value appears more than (1/2 + ε/2)t times among the results, return that value; otherwise, return zero. For q = 2, sample r from the rank distribution of a uniform binary matrix in O(n2 ) time, and let R = U diag(Ir , 0)V, where U, V are independent trapdoored invertible matrices. Then det R = 1{r=n} . For uniform U, V , the matrix R is uniform. Writing u = 1 − s2,n , the disagreement probability Pr[A(RA) ̸= det R] is at most u − ε when A is invertible, and at least u when A is singular, by the conditional determinant argument of [VZ26, Lemma 6.7]. Repeat this procedure independently t = O(ε−2 log n) times. Return one if A(RA) ̸= det R occurs fewer than (u − ε/2)t times, and zero otherwise. All relevant events are polynomial-time testable from the sampled matrices, since their determinants are polynomial-time computable. Thus pseudorandomness changes the probabilities above by only negl(n). In e 2 ) time, both cases, O(ε−2 log trials suffice by concentration. Each trial takes T (n) + O(n  n) independent  2 T (n)+n e e (n)). giving total time O = O(T 2 ε

23

Clifford circuit synthesis. We give a worst-to-average-case reduction for Clifford circuit synthesis given the corresponding tableau. We say that an algorithm implement a Clifford C if it maps |ϕ⟩ |0∗ ⟩ to C |ϕ⟩ |0∗ ⟩. Theorem 4.6. Let ε > 0. Assume the strong (dual) ring-LPN assumption. Let A be a randomized polynomialtime algorithm running in time T (n) that, given a signed Clifford tableau τD , outputs a Clifford circuit for D such that, for every sufficiently large n,   Pr A(τD ) implements D ≥ ε. D←Unif(C n )

Then we can construct an algorithm that, given any signed Clifford tableau, outputs a correct implementation e (n)). with clean ancillas with high probability, in time O(T Proof. Let C be the input Clifford. Sample a trapdoored Clifford R from Theorem 3.2. Define D = RC, e 2 ) using the trapdoor. Run A(D) to obtain a candidate whose signed tableau can be computed in time O(n circuit Q; whenever A implements the correct Clifford, appending the inverse implementation of R to Q gives e an implementation of C. This adds O(n) gates and ancillary qubits. By pseudorandomness, Q correctly implements D with probability at least ε − negl(n). We verify e (n) + n2 ) time using random Pauli conjugation and ancillary stabilizer correctness with high probability in O(T tests. Each trial succeeds with probability at least ε/2 for large the procedure O( logε n ) times gives  n. Repeating  2 e T (n)+n . a correct implementation with high probability in time O ε

4.3

From average-case parallel Clifford implementations to matrix multiplication

We reduce worst-case matrix multiplication to constructing parallel implementations of a random Clifford. Note that the reduction from the worst-case matrix multiplication to the worst-case parallel Clifford implementations is rather straightforward using UA below, although we were not aware of this result in the literature. The main implication here is that the same complexity persists in the parallel implementation of average-case Cliffords, even though random Cliffords are unlikely to be these classical-like UA . Theorem 4.7. Let ε > 0. Assume the strong (dual) ring-LPN assumption. Let A be a randomized polynomialtime algorithm running in time T (n) that, given the signed tableau τC of a 2n-qubit Clifford C, outputs a Clifford circuit on 2n2 qubits such that, for every sufficiently large n,   Pr A(τC ) implements C ⊗n ≥ ε. C←Unif(Cliff(2n))

Then we can construct a classical algorithm that, for any A, B ∈ Fn×n , computes AB with high probability, in 2 e (n)). time O(T Proof. Let A, B be the input matrices, and define the Clifford UA |u, v⟩ = |u + Av, v⟩ . Sample a trapdoored 2n-qubit Clifford R from Theorem 3.2. Define C = RUA , whose tableau can be e 2 ) using the trapdoor. Run A(τC ) to obtain a candidate circuit Γ. computed in time O(n Write B = [b1 · · · bn ], and define PB =

n O

I ⊗n ⊗ X(bj ) ,

X(b) =

j=1

n O

X bk .

k=1

Compute a circuit for Q = (R† )⊗n ΓPB Γ† R⊗n , which is a product of single-qubit Paulis, using the trapdoor e (n) + n2 ). in total time O(T Whenever A is correct, we have Q=

n O

X(Abj ) ⊗ X(bj ) .

j=1

24

Given the product Pauli structure, we can recover the entries of Abj for each j from the circuit for Q if it is correct. In other words, the circuit for Q gives a candidate Y for the product AB. Whenever A is correct, Y = AB. By pseudorandomness, Y equals AB with probability at least ε − negl(n). We verify correctness with e 2 ) time using Freivalds’ algorithm. Each trial succeeds with probability at least ε/2 high probability in O(n for large n. Repeating the procedure O(ε−1 log n) times gives the correct product with high probability in
e (T (n) + n2 )/ε = O(T e (n)). time O We next extend Theorem 4.7 to approximate implementations by general quantum circuits. Theorem 4.8. Let ε > 0 and η ∈ [0, 1) be constants. Assume the quantum-secure strong (dual) ring-LPN assumption. Let A be a randomized polynomial-time algorithm running in time T (n) that, given the signed tableau τC of a 2n-qubit Clifford C, outputs a (possibly non-Clifford) circuit with channel GC on 2n2 qubits such that, for every sufficiently large n,   1 Pr ∥GC − UC ⊗n ∥⋄ ≤ η ≥ ε, C←Unif(Cliff(2n)), A 2 where UV (ρ) = V ρV † . Then we can construct a quantum algorithm that, for any A, B ∈ Fn×n , computes AB 2 e (n)). with high probability in time O(T Proof. Define UA |u, v⟩ = |u + Av, v⟩ as in the proof of Theorem 4.7. Sample a trapdoored 2n-qubit Clifford e 2 ) time using the trapdoor, and run A(τC ). R from Theorem 3.2. Set C = RUA , compute τC in O(n Nn † ⊗n Write B = [b1 · · · bn ]. Apply GC followed by (R ) to j=1 |0n , bj ⟩, and measure the first n qubits of Nn each block to obtain the columns of a candidate Y . The ideal decoded state is j=1 |Abj , bj ⟩. Whenever the approximation condition holds, the diamond-norm bound changes any measurement event’s probability by at most η, so Y = AB with probability at least 1 − η. For uniform R, the Clifford C is uniform, giving success probability at least ε(1 − η). The event Y = AB is quantum polynomial-time testable from τR : compute AB classically and synthesize R† from its tableau using [AG04, Theorem 8]. Thus pseudorandomness gives success probability at least ε(1 − η) − negl(n) for the trapdoored procedure. Verify each candidate with high probability using Freivalds’ algorithm and repeat independently O((ε(1 − −1 e η)) log n) times. This gives the correct product with high probability in time O((T (n) + n2 )/(ε(1 − η))) = e O(T (n)).

25

References [ABOEM17] Dorit Aharonov, Michael Ben-Or, Elad Eban, and Urmila Mahadev. Interactive proofs for quantum computations. arXiv preprint arXiv:1704.04487, 2017. 3, 4, 22 [AG04]

Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A—Atomic, Molecular, and Optical Physics, 70(5):052328, 2004. 3, 4, 25

[AGGS22]

Vahid R. Asadi, Alexander Golovnev, Tom Gur, and Igor Shinkar. Worst-case to average-case reductions via additive combinatorics. In Stefano Leonardi and Anupam Gupta, editors, 54th ACM STOC, pages 1566–1574. ACM Press, June 2022. 4

[Ale03]

Michael Alekhnovich. More on average case vs approximation complexity. In 44th FOCS, pages 298–307. IEEE Computer Society Press, October 2003. 6

[AMBD+ 18] Carlos Aguilar-Melchor, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, and Gilles Zémor. Efficient encryption from random quasi-cyclic codes. IEEE Transactions on Information Theory, 64(5):3927–3943, 2018. 7 [BCG+ 20]

Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. Efficient pseudorandom correlation generators from ring-lpn. In Annual International Cryptology Conference, pages 387–416. Springer, 2020. 6, 7

[BCGI18]

Elette Boyle, Geoffroy Couteau, Niv Gilboa, and Yuval Ishai. Compressing vector OLE. In David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang, editors, ACM CCS 2018, pages 896–912. ACM Press, October 2018. 6

[BCH+ 25]

Fabrice Benhamouda, Caicai Chen, Shai Halevi, Yuval Ishai, Hugo Krawczyk, Tamer Mour, Tal Rabin, and Alon Rosen. Encrypted matrix-vector products from secret dual codes. In Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security, pages 394–408, 2025. 7, 8

[BF13a]

Karl Bringmann and Tobias Friedrich. Exact and efficient generation of geometric random variates and random graphs. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, ICALP 2013, Part I, volume 7965 of LNCS, pages 267–278. Springer, Berlin, Heidelberg, July 2013. 8

[BF13b]

Winton Brown and Omar Fawzi. Short random circuits define good quantum error correcting codes. In 2013 IEEE International Symposium on Information Theory, pages 346–350, 2013. 3

[BFKL93]

Avrim Blum, Merrick Furst, Michael Kearns, and Richard J Lipton. Cryptographic primitives based on hard learning problems. In Annual international cryptology conference, pages 278–291. Springer, 1993. 6

[BG16]

Sergey Bravyi and David Gosset. Improved classical simulation of quantum circuits dominated by Clifford gates. Physical Review Letters, 116(25):250501, 2016. 4

[BLR90]

Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. In 22nd ACM STOC, pages 73–83. ACM Press, May 1990. 4

[BLS03]

Alin Bostan, Grégoire Lecerf, and Éric Schost. Tellegen’s principle into practice. In Proceedings of the 2003 international symposium on Symbolic and algebraic computation, pages 37–44, 2003. 11

[BM21]

Sergey Bravyi and Dmitri Maslov. Hadamard-free circuits expose the structure of the clifford group. IEEE Transactions on Information Theory, 67(7):4546–4563, 2021. 3, 17, 18, 20, 21

26

[BN25]

Mark Braverman and Stephen Newman. Practical secure delegated linear algebra with trapdoored matrices. In Theory of Cryptography Conference, pages 97–118. Springer, 2025. 3, 8

[CK91]

David G Cantor and Erich Kaltofen. On fast multiplication of polynomials over arbitrary algebras. Acta Informatica, 28(7):693–701, 1991. 7, 16

[DLT02]

David P. DiVincenzo, Debbie W. Leung, and Barbara M. Terhal. Quantum data hiding. IEEE Transactions on Information Theory, 48(3):580–598, 2002. 4

[DNS12]

Frédéric Dupuis, Jesper Buus Nielsen, and Louis Salvail. Actively secure two-party evaluation of any quantum operation. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 794–811. Springer, Berlin, Heidelberg, August 2012. 21

[FL11]

Steven T. Flammia and Yi-Kai Liu. Direct fidelity estimation from few Pauli measurements. Physical Review Letters, 106(23):230501, 2011. 4

[GLR+ 91]

Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, and Avi Wigderson. Selftesting/correcting for polynomials and for approximate functions. In 23rd ACM STOC, pages 32–42. ACM Press, May 1991. 4

[Got97]

Daniel Gottesman. Stabilizer Codes and Quantum Error Correction. PhD thesis, California Institute of Technology, 1997. 3

[Got98]

Daniel Gottesman. Theory of fault-tolerant quantum computation. Physical Review A, 57(1):127– 137, 1998. 3

[GS92]

Peter Gemmell and Madhu Sudan. Highly resilient correctors for polynomials. Information Processing Letters, 43(4):169–174, 1992. 4

[GSS24]

Ashish Gola, Igor Shinkar, and Harsimran Singh. Matrix multiplication reductions. In APPROX/RANDOM, volume 317, pages 34:1–34:15, 2024. 4

[HIK+ 23]

J. Helsen, M. Ioannou, J. Kitzinger, E. Onorati, A. H. Werner, J. Eisert, and I. Roth. Shadow estimation of gate-set properties from random sequences. Nature Communications, 14:5039, 2023. 4

[HKL+ 12]

Stefan Heyse, Eike Kiltz, Vadim Lyubashevsky, Christof Paar, and Krzysztof Pietrzak. Lapin: an efficient authentication protocol based on ring-lpn. In International Workshop on Fast Software Encryption, pages 346–365. Springer, 2012. 6

[HKP20]

Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16(10):1050–1057, 2020. 3, 4

[HS23]

Shuichi Hirahara and Nobutaka Shimizu. Hardness self-amplification: Simplified, optimized, and unified. In Barna Saha and Rocco A. Servedio, editors, 55th ACM STOC, pages 70–83. ACM Press, June 2023. 4

[HS25]

Shuichi Hirahara and Nobutaka Shimizu. Error-correction of matrix multiplication algorithms. In Michal Koucký and Nikhil Bansal, editors, 57th ACM STOC, pages 785–794. ACM Press, June 2025. 4

[KO26]

Kao-Yueh Kuo and Yingkai Ouyang. Degenerate quantum erasure decoding. npj Quantum Information, 12:75, 2026. 4

[KS14]

Robert Koenig and John A Smolin. How to efficiently select an arbitrary clifford group element. Journal of Mathematical Physics, 55(12), 2014. 3

27

[KZG16]

Richard Kueng, Huangjun Zhu, and David Gross. Low rank matrix recovery from Clifford orbits, 2016. 3

[LB14]

Tyler Lu and Craig Boutilier. Effective sampling and learning for mallows models with pairwisepreference data. The Journal of Machine Learning Research, 15(1):3783–3829, 2014. 14

[LM13]

Vadim Lyubashevsky and Daniel Masny. Man-in-the-middle secure authentication schemes from lpn and weak prfs. In Annual Cryptology Conference, pages 308–325. Springer, 2013. 6, 7

[Mal57]

Colin L Mallows. Non-null ranking models. i. Biometrika, 44(1/2):114–130, 1957. 14

[Mat17]

Ryutaroh Matsumoto. Unitary reconstruction of secret for stabilizer-based quantum secret sharing. Quantum Information Processing, 16:202, 2017. 4

[MGE11]

Easwar Magesan, J. M. Gambetta, and Joseph Emerson. Scalable and robust randomized benchmarking of quantum processes. Physical Review Letters, 106(18):180504, 2011. 3

[PQS26]

Alexander Poremba, Yihui Quek, and Peter W. Shor. The learning stabilizers with noise problem. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), volume 362 of Leibniz International Proceedings in Informatics (LIPIcs), pages 108:1–108:19, 2026. 4

[VDB21]

Ewout Van Den Berg. A simple method for sampling random clifford operators. In 2021 ieee international conference on quantum computing and engineering (qce), pages 54–59. IEEE, 2021. 3

[VZ26]

Vinod Vaikuntanathan and Or Zamir. Improving algorithmic efficiency using cryptography: Trapdoored matrices and applications. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2554–2574. SIAM, 2026. 3, 4, 7, 8, 22, 23

[Web16]

Zak Webb. The clifford group forms a unitary 3-design. Quantum Information & Computation, 16:1379–1400, 2016. 4

[Zhu17]

Huangjun Zhu. Multiqubit clifford groups are unitary 3-designs. Physical Review A, 96(6):062336, 2017. 4

28

Related documents

• Trapdoored Clifford Operators and Applications#1157119
• On Some Cognitive Features of Clifford Algebraic Quantum Mechanics and the Origin of Indeterminism in this Theory: A Derivation of Heisenberg Uncertainty Principle by Using the Clifford Algebra#711836
• Faster Quantum Monte Carlo Simulation by Random Compilation#997362
• Spectral boundaries of deterministic matrices deformed by rotationally invariant random non-Hermitian ensembles#925932
• Extracting high fidelity quantum computer hardware from random systems#420804