Constant-Rate Certified Deletion

Constant-Rate Certified Deletion Kai-Min Chung1 , Tzu-Hsiang Huang2 , Wei-Hsiang Hung1 , Shota Yamada3

arXiv:2610.03590v1 [cs.CR] 2 Oct 2026

1

Academia Sinica, Taipei, Taiwan kmchung@iis.sinica.edu.tw, arniehung@iis.sinica.edu.tw 2 University of Illinois Urbana-Champaign, USA th57@illinois.edu 3 National Institute of Advanced Industrial Science and Technology (AIST), Tokyo, Japan yamada-shota@aist.go.jp

Abstract We present a unified framework for upgrading a broad class of cryptographic primitives to support constant-rate certified deletion. Previous constructions require a linear number of qubits per encrypted bit of certified-deletable plaintext. In contrast, we obtain the first constant-rate constructions in the plain model that achieve certified deletion while preserving everlasting security. Our approach applies to a wide range of “all-or-nothing”–type primitives based on BB84-style encodings, including commitment schemes, public-key encryption, attribute-based encryption, and fully homomorphic encryption. Beyond this class, we also obtain constant-rate certified deletion for primitives built from subspace coset states, such as blind delegation, secure software leasing, functional encryption, and differing-inputs iO, and CCA-PKE. Importantly, our framework does not introduce any additional assumptions beyond those required by the underlying certified deletion primitives. Finally, under the hardness of SIS, we show that public verifiability can be incorporated into BB84and coset-based certified deletion. In combination with our constant-rate constructions, this yields publicly verifiable certified deletion schemes with constant rate.

1

Contents 1

Introduction 1.1 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 5

2 Technical Overview 5 2.1 Constant-Rate Certified Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 An alternative approach to coset state CD . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 Publicly Verifiable Deletion with Constant-Rate. . . . . . . . . . . . . . . . . . . . . . . . . 12 3

Preliminaries 14 3.1 Linear Algebra Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 Quantum Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4

Quantum Source Seedless Extractor 19 4.1 Quantum Source of Randomness Based on BB84 States . . . . . . . . . . . . . . . . . . . . 19 4.2 Quantum Source of Randomness Based on Subspace Coset States . . . . . . . . . . . . . . 21

5

Certified Deletion for BB84 States 27 5.1 Main Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.2 Applications of BB84 Constructions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

6

Certified Deletion for Subspace Coset States 39 6.1 Main Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.2 Applications of Subspace Coset State Constructions . . . . . . . . . . . . . . . . . . . . . . 53

7

Publicly Verifiable Certified Deletion

54

2

1

Introduction

Certified Deletion. The right to be forgotten, a prominent legal concept in modern privacy regulations like the General Data Protection Regulation [EC16], mandates data erasure to protect personal privacy and autonomy. This right is essential for giving individuals control over their personal data and a chance to move past their digital history. However, ensuring compliance with this privacy mandate, especially when the underlying device is untrusted, raises a fundamental question: Is it possible to prove that a piece of data has been deleted? In the classical world, this is impossible, as classical information can be copied arbitrarily many times. Even if we protect the data by encryption, future leakage of the secret key or advances in cryptanalysis may break the scheme and allow an adversary to recover the plaintext. On the other hand, quantum information sheds new light on this problem. The no-cloning theorem asserts that it is generally impossible to copy a quantum state. Furthermore, the uncertainty principle implies that certain pairs of measurements cannot both be known precisely at the same time. This destructive nature of quantum mechanics opens the possibility of incorporating cryptographic schemes with quantum information to achieve provable data deletion. Broadbent and Islam [BI20] were the first to formalize the notion of certified deletion (CD) in the context of one-time secret-key encryption. Their construction achieves security against unbounded adversaries, even if the secret key is later leaked, provided that the adversary has issued a deletion certificate and it has been successfully verified. Subsequently, Hiroka, Morimae, Nishimaki, and Yamakawa [HMNY21] and Poremba [Por22] extended certified deletion to public-key primitives, considering public-key encryption (PKE) and attribute-based encryption (ABE), and fully homomorphic encryption (FHE), respectively. Since public-key primitives inevitably rely on computational assumptions, their security can hold only against bounded adversaries prior to deletion. However, their definitions restrict security even further, ensuring protection only against bounded adversaries after the deletion certificate has been issued and verified. Independently, Bartusek and Khurana [BK23] and [HMNY22] strengthen the security to certified everlasting security where adversaries become unbounded after issuing a deletion certificate. The notion has become the standard of certified deletion. Certified deletion was initially studied for “all-or-nothing”–type primitives, where the security definition guarantees that an adversary can either decrypt the entire plaintext or learn nothing at all. Follow-up works further extended certified deletion to primitives beyond the “all-or-nothing” setting, where the adversary may obtain partial information about the encoded message within the security game. Specifically, Bartusek et al. [BGK+ 24] study maliciously blind delegation, obfuscation, and functional encryption schemes, while Hiroka et al. [HKM+ 24] focus on functional encryption. A line of work focuses on publicly verifiable deletion (PVD), where the deletion verification key is public and anyone can verify deletion using this key [Por22, BGK+ 24, BKP23, BKM+ 23, KNY23, KS25]. [Por22] constructed PKE and FHE schemes with PVD based on the conjecture that the Ajtai hash function satisfies a strong Gaussian-collapsing property. [BKP23] later introduced the notion of target-collapsing hash functions, which are sufficient for PVD. They proved the conjecture of [Por22] by showing that Ajtai hash functions are target-collapsing under the LWE assumption, and further demonstrated that injective (or almost-regular) one-way functions are target-collapsing. [BKM+ 23] subsequently weakened the underlying assumptions required for PVD, showing that standard one-way functions suffice. Independently, [KNY23] achieved PVD by signing BB84 states in the computational basis, assuming one-way functions or minimal quantum-planted NP hardness. These two approaches were subsequently unified in [BKK+ 26]. On the other hand, the subspace coset state compiler of [BGK+ 24] enables primitives beyond the all-or-nothing type with PVD, assuming indistinguishability obfuscation (iO). [KS25] considers secret sharing with publicly verifiable deletion. 3

However, existing certified deletion schemes in the plain model suffer from a significant inefficiency. In particular, Bartusek and Raizes [BR24] posed the problem of constructing commitments with certified deletion whose size is not much larger than the committed message. Unfortunately, all known constructions that achieve certified everlasting security require Θ(λ) qubits to encrypt a single classical bit,1 resulting in a total communication cost of Θ(nλ) qubits for an n-bit message. This multiplicative dependence on the security parameter constitutes a significant overhead and eliminating this multiplicative dependence on λ remains an open challenge. Barriers to constant-rate deletion. The inefficiency of certified deletion schemes is not coincidental. The core obstacle lies in the proof technique used in the plain model. To establish certified deletion security, one must prove a seemingly paradoxical statement: a message has been information-theoretically deleted from the adversary’s view, even though it was previously information-theoretically determined by the ciphertext. The proof technique pioneered by [BK23] resolves this tension by guessing a random string to replace the message-dependent component of the ciphertext, thereby delaying the experiment’s dependence on the actual message until after the adversary outputs the deletion certificate. This deferral allows the security analysis to argue that the message dependence can later be removed once the certificate has been verified. However, the guessing step incurs a security loss exponential in the message length, making it infeasible to guess all message bits and thus precluding constant-rate deletion. In the following, we examine existing constructions to highlight the barriers to achieving constant rates. We define the rate as the size of the message (the plaintext) divided by the number of qubits required during the communication. Existing Encoding Techniques. Existing certified deletion encodings can be broadly categorized into three approaches: • BB84-type encodings [BI20, HMNY21, HMNY22, BK23, KNY23]. While [BI20, HMNY21, HMNY22] achieve constant rate, they either rely on non-standard definitions or assume the quantum random oracle model (QROM). To meet the standard definition in the plain model, [BK23, KNY23] require Θ(λ) qubits to ensure that the adversary cannot guess all deletion positions, as their proofs rely on a cut-and-choose argument. • Subspace coset state encodings [BGK+ 24]. These generalize the BB84-based approach to subspace coset states, but their analysis depends on an exponential gap between a coset and a noisy superspace, which again necessitates Θ(λ) qubits. • Hash-based PVD constructions [Por22, BKP23, BKM+ 23]. These constructions rely on the hardness of inverting a hash function, which forces the preimage—and hence the number of encoding qubits—to be at least Θ(λ). In all three approaches, the number of encoding qubits grows linearly with the security parameter λ. When combined with the [BK23] guessing technique, this limits the classical message length to O(log λ) and yields a subconstant rate of O(log λ)/Θ(λ) under standard security definitions in the plain model. This motivates the central question of our work: Can we construct constant-rate certified deletion in the plain model, with only a small qubit overhead over the classical plaintext? 1

If one is satisfied with merely negligible security, then ω(log λ) qubits are sufficient. However, in most settings a failure probability smaller than inverse exponential is required, in which case Θ(λ) qubits are needed to encrypt a single classical bit.

4

1.1

Our Results

Our work answers the above question in the affirmative. Our main contributions are summarized below. • Constant-rate certified deletion theorems. We establish constant-rate certified deletion theorems for both BB84 states and subspace coset states. These results yield two generic compilers: one enables constant-rate certified deletion for “all-or-nothing”-type primitives instantiated from BB84 states, including commitment, secret key encryption, public-key encryption, attribute-based encryption, fully homomorphic encryption, timed-release encryption, and witness encryption. The other enables constant-rate certified deletion for primitives beyond the “all-or-nothing”-type instantiated from subspace coset states, including blind delegation, secure software leasing, functional encryption, differing-inputs iO, and CCA-PKE. Specifically, assuming that the message length is much longer than the security parameter λ, we obtain rate-(1 − ϵ) certified deletion for primitives instantiated from BB84 states for any constant ϵ > 0 (See Remark 5.5), and we obtain rate- 14 certified deletion for primitives instantiated from coset subspace states. We attain a constant-rate certified deletion by employing the following techniques. – Overcoming barrier to provable security. We overcome the technical obstacle to provable security that arises from the guessing technique of [BK23]. Our analysis proves certified deletion even in the presence of leakage originating from the unguessed portion of the ciphertext. – Seedless randomness extraction from weak quantum sources. As an intermediate contribution, we prove a new seedless randomness extraction theorem from weak quantum sources for BB84 states, where the weakness of the source stems from the aforementioned leakage. • Constant-rate public verifiable deletion from SIS. We also study how to add public verifiability to our constant-rate constructions obtained above. Existing techniques [Por22, BGK+ 24, BKP23, BKM+ 23, KNY23, KS25] destroy the rate, as they require deletion certificates of linear size. The only exception relies on indistinguishability obfuscation [BGK+ 24], a strong assumption without a standard instantiation. Assuming the hardness of SIS, we show that public verifiability can be incorporated into certified deletion for BB84 and subspace coset states. Combined with our constant-rate constructions, this yields publicly verifiable certified deletion for all-or-nothing-type primitives with a constant rate.

2

Technical Overview

2.1

Constant-Rate Certified Deletion

Certified Deletion Theorem by [BK23] Let us start with the main theorem of certified deletion for BB84 state [BK23]. Let (Gen, Enc, Dec) be a post-quantum semantically-secure encryption scheme. Then, for any adversary A and any message m ∈ {0, 1}, we define the following experiment EXPA (m) as follows: • Sample x, θ ← {0, 1}n and initialize A with M

H θ |x⟩, m ⊕

i:θ[i]=0

5

x[i], Enc(θ).

• A’s output is parsed as a string x′ ∈ {0, 1}n and a residual state ρ. • (Verification step): If x[i] = x′ [i] for all i such that θ[i] = 1, then output ρ. Otherwise, output a special symbol ⊥. [BK23] shows that for any efficient adversary A, TD(EXPA (0), EXPA (1)) ≤ negl(λ). Roughly speaking, x′ serves as the deletion certificate. What the above theorem says is that if the adversary passes the verification by submitting a correct deletion certificate, it loses the information of m in an information-theoretic sense, conditioned on passing the verification. Breaking Circularity by Guessing We then explain the security proof strategy. The intuition for the security is as follows: Assume that an adversary A is initialized with H θ |x⟩ only. Then, in order to pass the verification step (x[i] = x′ [i] for all i such that θ[i] = 1), A must measure “almost” all qubits in Hadamard basis, since the adversary Lhas no knowledge on θ and cannot selectively measure the Hadamard position. Hence, we expect that x[i] looks random to A, since it almost loses the information of |x⟩θ after the i:θ[i]=0 L measurement. Next, consider the case where A is given m ⊕ x[i] and Enc(θ) additionally. We may i:θ[i]=0

say that the latter does not L reveal the information of θ, but the former is dependent on θ. Namely, there is a circularity. To argue that x[i] is random, θ should be hidden. However, to say θ is hidden, we may want i:θ[i]=0 L to say x[i] is random (i.e., independent of θ). To overcome this circularity, they guess a bit b replacing i:θ[i]=0 L m⊕ x[i] and defer the dependency of m until after the adversary outputs x′ and ρ. This guessing step i:θ[i]=0

incurs a factor-1/2 loss in trace distance, corresponding to the probability of guessing the wrong bit. Structure of the Post-Verification State Second, they aim to justify that, after A passes the verification step, the quantum L state behaves as if measured in the Hadamard basis at positions where θ[i] = 0. This ensures that x[i] is independent of A’s output state ρ. Such a condition would hold if the adversary i:θ[i]=0

measured those qubits honestly in the Hadamard basis. To show that the adversary cannot deviate substantially from the honest strategy, we argue that θ is hidden from A. To this end, we purify the adversary’s view as follows: X |x⟩C |x⟩A , b, Enc(θ), x

where C and A represent the challenger’s and the adversary’s register, respectively. The additional register C serves as a purification that acts as a “handle” for the adversary’s internal information about x on the challenger’s side, allowing us to reason about the adversary’s knowledge via measurements performed by the challenger. After the adversary’s output, the challenger measures C in the θ basis. This reduces the dependence on θ from A’s view. For the moment, assume that Enc(θ) is replaced by Enc(0). Then, A’s view is completely independent of θ and we can defer the choice of θ to the point after A outputs x′ . In such a setting, we can rely on cut-and-choose argument over the random subset defined by θ to ensure that the register C is almost H|x′ ⟩:2 If the state in the register C is far from H|x′ ⟩, measurement of C at positions where θ[i] = 1 results in a string that is inconsistent with x′ with high probability. We can 2

This notation means that we apply the Hadamard gate H to all the qubits. Looking ahead, we will use similar notation for QFT.

6

formalize this argument to characterize the structure of the state after the adversary passes verification as follows: X H|x′ + s⟩Cθ0 |ψs ⟩A , (1) s:h(s) is small

where h(·) represents the Hamming weight, Cθ0 is the challenger’s register consisting of the position i with θ[i] = 0, and |ψs ⟩ is an arbitrary state that may be entangled with Cθ0 . This structure formalizes the high-level notion that the adversary has measured “almost” all the qubits in the Hadamard basis and therefore has lost most of the information of {xi }i:θ[i]=0 . Applying the XOR Extractor Lemma At this point, we can invoke the XOR extractor lemma by [ABKK23] that shows XOR is a good deterministic randomness extractor for the quantum source in Equation L (1), in the sense that if we measure the register Cθ0 in the computational basis to obtain xθ0 , then xθ0 [i] is i

uniformly random and independent of other variables. The outputs L of the two experiments are both the state ρ, conditioned on the guessing bit being correct, i.e. b = m ⊕ xθ0 [i]. It is therefore crucial to show that i L xθ0 [i] is independent of the adversary’s state ρ; otherwise, the outputs of the two experiments could differ i

by a large trace distance due to underlying correlations. Efficiently Checkable Predicate The above discussion was carried out in the ideal world where Enc(θ) is replaced with Enc(0). In the real world, however, A receives Enc(θ). One may naively argue that since the L real world is computationally indistinguishable from the ideal world, the fact that i:θ[i]=0 x[i] is random in the ideal experiment implies the same in the real experiment. While this conclusion is ultimately true in our setting, justifying it is non-trivial, as computational indistinguishability does not in general imply statistical indistinguishability. To resolve this issue, we apply the XOR extractor lemma directly in the real world. For this purpose, it suffices to guarantee that Cθ0 has the structure described in Equation (1). At first glance, this is unclear, since in the real world θ is only computationally hidden from A. The crucial observation is that whether Cθ0 satisfies the structural condition of Equation (1) constitutes an efficiently checkable predicate. Indeed, we can apply the Hadamard measurement to Cθ0 and verify whether the resulting string has small Hamming distance from x′ . This procedure runs in polynomial time and determines whether the desired structural condition holds. Suppose, for contradiction, that the predicate is satisfied with noticeably different probabilities in the ideal and real worlds. Then we can construct a reduction that receives either Enc(θ) or Enc(0), simulates both the challenger and the adversary, and evaluates the above predicate. If the acceptance probabilities differ noticeably, this yields a distinguisher against the semantic security of the encryption scheme. Therefore, the predicate must hold with negligibly close probabilities in the two experiments. Putting everything together, we conclude that the structural condition transfers from the ideal world to the real world. Consequently, the XOR bit remains information-theoretically hidden even in the real world. Constant Rate Extractor We now turn to proving constant-rate certified deletion, where the message length satisfies k = Θ(n). The first step is to replace the XOR extractor {0, 1}n → {0, 1} with a high-rate extractor {0, 1}n → {0, 1}k . Let us now move to show constant-rate certified deletion theorem. [BR24] already suggest a candidate high-rate extractor R ∈ Fk×n , where F is a polynomial bounded sized finite field. R is a Maximum Distance Separable code, i.e., every k columns of R are linearly independent. Since such

7

a matrix does not exist over the binary field for our parameters, we move to a larger field and replace the Hadamard basis with the Fourier basis over F. Accordingly, the first step of the experiment is modified as follows: Sample x ← F2n , balanced θ ← {0, 1}2n , and initialize A with QFTθ |x⟩, m + Rxθ0 , Enc(θ), where xθ0 is the substring of x where θ[i] = 0. A natural attempt would be to guess an entire string b ← Fk to replace m + Rxθ0 . However, this would incur an exponential loss in the guessing step, as the success probability would be |F|−k . Consequently, even if the modified experiments were negligibly close, this would not imply that the original experiments have negligible trace distance. Position-wise Guessing We now explain how to overcome this issue. For simplicity, suppose we only require deletion of the first field element of the message. If we directly applied the proof technique of [BK23], we would still need to guess the entire message string. In contrast, our approach proceeds one field element at a time. We aim to show that Rxθ0 is uniformly random and independent of the adversary’s view at that single field position. However, the adversary now has a partial leakage of x and θ. For example, if b replaces the first position, then the adversary’s view includes (m + Rxθ0 ) [2 : k], which reduces the possible value of x and θ. Hence, even if the adversary passes the verification, the state in the register Cθ0 is no longer guaranteed to have the structure of Equation (1). Unentangling the Message Carrying Part To restore the cut-and-choose argument, we must ensure that θ is hidden from the adversary at the crucial point of the proof. To this end, we introduce fresh randomness r ← Fk that computationally one-time pads the message leakage. Concretely, we modify the initialization of A to QFTθ |x⟩, m + Rxθ0 + r, Enc(θ, r). (2) The randomness r only provides computational hiding, but this suffices for our purposes. Intuitively, the presence of r allows us to delay the sampling of θ to a later point in the game. For the time being, we switch to the ideal world where Enc(θ, r) is replaced with Enc(0, 0) and continue the analysis. θ P We now describe how this delay is achieved. First, we purify the state QFT |x⟩ into an EPR pair x |x⟩C |x⟩A . In the original sampling procedure, θ is chosen immediately and the standard-basis positions are measured to obtain xθ0 , from which Rxθ0 + r is computed and given to the adversary. Instead, we perform an equivocation argument. Since r is uniform and independent in the ideal world (where Enc encrypts zero), we may equivalently sample ℓ ← Fk uniformly and set r := ℓ − m − Rxθ0 . The adversary then receives ℓ together with the register A. This preserves the joint distribution, as r remains uniformly distributed and independent. P In this alternative generation procedure, we may first prepare the EPR pair x |x⟩C |x⟩A , send the register A and the random string ℓ to the adversary, and postpone the sampling of θ and the computation of xθ0 . Since the operations of sampling θ and defining r are local to the challenger, they commute with A’s computation of x′ . We may therefore delay the choice of θ until after A outputs x′ . Structure of the Post-Verification State Working in the ideal world where Enc(θ, r) is replaced with Enc(0, 0), the above delay allows us to sample θ only after A outputs x′ . This restores the cut-and-choose argument in the constant-rate setting. 8

In particular, we may choose θ and then measure the standard-basis positions to obtain xθ0 only after receiving x′ . Therefore, if the adversary passes the verification step, the joint state of the challenger and the adversary must be negligibly close to a state of the following form: X QFT−1 |x′ + s⟩Cθ0 |ψs ⟩A . (3) s:h(s) is small

This is the analogue of Equation (1) in the single-bit case. We now incorporate the linear extractor R into the analysis. Recall that the masking term involves Rxθ0 , which corresponds to measuring Cθ0 in the computational basis and applying the linear map R. To analyze this coherently, we first apply the linear transformation |y⟩Cθ0 7→ |y⟩Cθ0 |Ry⟩C2 , where C2 is an auxiliary register. We then measure C2 and obtain an outcome ℓ′ ∈ Fk . In the position-wise guessing strategy, we only guess the first coordinate of Ry. Accordingly, we decompose R into its first row R1 and the remaining rows R−1 . Measuring C2 except for the first coordinate amounts to fixing the linear constraint R−1 y = ℓ′−1 . Conditioned on this outcome, the joint state becomes X X −⟨y,x′ +s⟩ ω|F| |y⟩Cθ0 |ψs ⟩A .

(4)

s:h(s) is small y:R−1 y=ℓ′−1

Intuitively, the superposition is now restricted to a coset of the linear subspace defined by R−1 y = ℓ′−1 . This restriction reflects the leakage of k − 1 field elements of Rxθ0 to the adversary. The remaining question is whether the first coordinate R1 y is still random under this constraint. Extracting Randomness from the Restricted State We now argue that the first coordinate R1 y remains uniformly random even under the linear constraint R−1 y = ℓ′−1 . The starting point is the high-rate extraction lemma of [BR24], which (for our choice of R) guarantees that measuring the register Cθ0 in the computational basis in the non-restricted state Equation (3) yields a string y such that the value Ry ∈ Fk is (perfectly) uniform and independent of the adversary’s state. In particular, the joint distribution of (R−1 y, R1 y) is uniform over Fk−1 × F, and hence R1 y is uniform even conditioned on R−1 y. Equivalently, consider the following two-step measurement on Equation (3): first compute and measure R−1 y to obtain ℓ′−1 , and then compute and measure R1 y to obtain ℓ′1 . Since (R−1 y, R1 y) is uniform, the outcomes ℓ′−1 and ℓ′1 are independent, and conditioning on ℓ′−1 does not affect the distribution of ℓ′1 . Finally, observing that measuring R−1 y in Equation (3) yields exactly the restricted state in Equation (4), we conclude that in the restricted state the value R1 y remains statistically close to uniform and independent of the adversary’s state, as required for the position-wise guessing argument. Finding an Efficiently Checkable Predicate It remains to argue that the structural condition captured by the restricted state in Equation (4) can be verified efficiently. This is required in order to transfer the argument from the ideal world to the real world via a reduction. Recall that the restricted state has the form X X −⟨y,x′ +s⟩ ω|F| |y⟩Cθ0 |ψs ⟩A . (5) s:h(s) is small y:R−1 y=ℓ′−1

9

The inner summation ranges over a coset of the linear subspace defined by R−1 y = ℓ′−1 . To test whether the state is close to this form, we apply the Fourier transform over F to the register Cθ0 . A direct calculation shows that X X −⟨y,x′ +s⟩ ⟨α,w⟩ QFT ω|F| |y⟩ ∝ ω|F| |x′ + s + w⟩, (6) y:R−1 y=ℓ′−1

w∈rowSpan(R−1 )

where α depends only on ℓ′−1 . Thus, after the Fourier transform, the superposition is supported on shifts of x′ + s by elements of the row span of R−1 . At this point, the MDS property of R becomes crucial. Since s has small Hamming weight and R has maximum distance, the error vector s can be efficiently recovered from x′ + s + w using the error-correction capability of the code defined by R. Standard linear-algebraic operations over F therefore allow us to map the above superposition to a state of the form X |s⟩Cθ0 |ψs ⟩A . (7) s:h(s) is small

Consequently, we obtain an efficiently checkable predicate: we apply the above transformation and accept if and only if the resulting state is supported on small-weight s. All required operations—Fourier transforms and linear transformations over F—run in polynomial time. As in the single-bit case, if this predicate were satisfied with noticeably different probabilities in the ideal and real worlds, this would yield a distinguisher against the semantic security of the encryption scheme. Therefore, the structural condition holds with negligibly close probability in both worlds. Why a Naive Check Is Not Sufficient Our efficiently checkable predicate is implemented via a carefully designed unitary that maps the state in Equation (6) to the structured form in Equation (7). Intuitively, this transformation enforces the exact structural condition required on the register Cθ0 from which randomness is extracted. A natural alternative would be to apply the QFT to Cθ0 , measure in the computational basis, and decode the outcome to recover the error parameter s. Since an adversary that passes the verification produces a state consistent with some small s and coding word w, this naive check would accept with overwhelming probability. However, this is not sufficient. Such a test only verifies that the marginal distribution of Cθ0 is consistent with some pair (s, w). It does not restrict how the adversary’s register may be entangled with these parameters. While entanglement with respect to the small error parameter s is allowed by the extraction lemma, entanglement with respect to the coset parameter w is not. If the adversary’s state remains entangled with w, then the extracted randomness may still depend on w and hence on the adversary’s register. Our unitary therefore enforces a stronger structural condition: it eliminates the dependence on w and ensures that any remaining entanglement is confined solely to s. This additional control is essential for applying the extraction lemma and guaranteeing that the extracted randomness is independent of the adversary’s state. Remark 2.1 (Number of qubits). It is important to identify which messages should be sent through a quantum channel, as this will affect the rate we are interested in. One might think that the classical message m+Rxθ0 +r in Equation (2) should be sent using a quantum channel, since in our security proof we consider a purification of it. We want to show that the real-world view is indistinguishable from the purification view. However, if we use a classical channel in the real world, then the two views are in fact distinguishable by the adversary, since classical and quantum channels are physically realized by entirely different devices. Fortunately, it is 10

still acceptable to use a classical channel to send m + Rxθ0 + r. Indeed, consider a hybrid world that is equivalent to the real world, except that we send |m + Rxθ0 + r⟩ through a quantum channel. In this setting, our results show that no efficient adversary wins the game. Now, we want to show that this implies no efficient adversary wins the game in the real world. Suppose (by contradiction) that an efficient adversary A wins the game in the real world. Then, define A′ as follows: 1. Measure |m + Rxθ0 + r⟩ in computational basis. 2. Run A on the same input except that m + Rxθ0 + r is a classical string. Then, it is clear that A′ wins the game in the hybrid world.

2.2

An alternative approach to coset state CD

Our technique for upgrading the BB84 certified deletion theorem to the constant-rate regime is to identify an efficiently checkable and randomness extractable predicate, even when the partial leakage is entangled with the BB84 state. Fortunately, for coset-state-based constructions, there is a clever way to circumvent the issue of entanglement. We explain this by first recalling the main theorem on certified deletion for coset states [BGK+ 24]. Let Z be a post-quantum subspace-hiding distribution, i.e., there is an efficient simulator Z(S, T, u, w) ≈c Sim(G, T, u, x) for random subspace cosets S ⊥ + w ⊂ G + x and S + v ⊂ T + u. Then, for any adversary A and any message m ∈ {0, 1}, we define the following experiment EXPA (m) as follows: • Sample a random n/2-dimension subspace S of Fn2 , v ← co(S), w ← co(S ⊥ ), random T + u such that T + u ⊆ S + v and initialize A with |Sv,w ⟩,

Z(S, T, u, w, m ⊕ ⟨v, 1⟩).

• A’s output is parsed as a string z̃ ∈ Fn2 and a residual state ρ. • (Verification step): If z̃ ∈ S ⊥ + w, then output ρ. Otherwise, output a special symbol ⊥. [BGK+ 24] shows that for any efficient adversary A, TD(EXPA (0), EXPA (1)) ≤ negl(λ). To upgrade the construction to the constant-rate regime, we again enlarge the field to F and replace the XOR extractor with an arbitrary full-rank matrix R. The construction becomes |Sv,w ⟩,

Z(S, T, u, w, m + Rv).

Similarly, we would like to apply position-wise guessing in our analysis. For example, to argue that the first field element of the message is hidden, we sample a uniform element b during the hybrid argument and replace the first coordinate of m + Rv with b. Next, if we purify |Sv,w ⟩ to X |v0 ⟩C |Sv0 +u,w ⟩A (8) v0 ∈T /S

as in [BGK+ 24], the resulting state has the partial leakage (m + R(v0 + u))[2 : k] entangled with the purification state in Equation (8). Instead, we purify |Sv,w ⟩ to X |vker ⟩C |Svker +vimg +u,w ⟩A . (9) vker ∈ker R−1 |T /S

11

It is clear that (m + R(vker + vimg + u))[2 : k] is independent of vker and hence is not entangled with the purification state in Equation (9). In general, to argue that the i-th element of the message is hidden, we purify vker into a superposition over the subspace
ker R−i |T /S . Define S + := span S, ker R−i |T /S . Following a similar calculation to that in [BGK+ 24], it suffices to show that the adversary A cannot output a vector ze such that  /  ze ∈ S ⊥ + w (S + )⊥ + veker + w , (10) given some information (which we omit here). It is clear that if the adversary output a vector in Equation (10), then there exists a new adversary A′ output ze′ such that  ze′ ∈ S ⊥ (S + )⊥ , given G, S + , and T . We conclude the proof by switching the sampling procedure. In the original procedure, S and T are sampled first, which uniquely determines ker(R−1 |T /S ) and hence S + . Equivalently, we may first sample G, S + , and T , and then sample S conditioned on these choices. As a result, we may defer sampling S until after the adversary outputs ze′ . This allows us to conclude that A′ cannot win with non-negligible probability. Why clever purification does not work for BB84-based construction: At first glance, it may seem that the proof for the BB84-based construction can be obtained by following the same approach as for the coset-state-based construction. However, this approach fails. A BB84-based construction simply chooses S as a span of some computational basis. Let B := span (v1 , . . . , vj ) be the maximal subset spanned by computational basis vectors such that B ≤ S + . It is clear that G⊥ ≤ S ≤ B ≤ S + . Furthermore, once S + is given to the adversary A′ , it is easy to find B. The adversary A′ is defined as follows: 1. If B ⪇ S + , let H := B.   If B = S + , randomly choose i ∈ [j], let H := span v1 , . . . , vi−1 , vi+1 , . . . , v 3n −k+1 . 4

2. Uniformly sample a vector ze′ ∈ H ⊥ and return ze′ . n

2 If B ⪇ S + , then (S + )⊥ ⪇ H ⊥ ≤ S ⊥ . If B = S + , the probability that S ≤ H ⪇ S + is p := 1 − 3n −k+1 . 4

Condition on this event,we have (S + )⊥ ⪇ H ⊥ ≤ S ⊥ . Hence, if we choose a vector in H ⊥ uniformly at 1 random, we get ze′ ∈ S ⊥ (S + )⊥ with probability at least 1 − |F| . The overall winning probability of Adv′ is   1 p 1 − |F| , which is inverse polynomial.

2.3

Publicly Verifiable Deletion with Constant-Rate.

We then show how to add public verifiability to certified deletion based on BB84 and coset states, assuming the shortest integer solutions (SIS) assumption. Our transformation preserves the constant-rate property. Combined with our constant-rate certified deletion theorem, this yields certified deletion with public verifiability (PVD) without asymptotically degrading the rate. We begin by recalling the key idea of [KNY23], which achieves PVD for BB84 assuming one-way functions, albeit at a low rate. For simplicity, we use the binary encoding case (rather than the finite-field case). In BB84-based certified deletion, one prepares |x⟩θ for x, θ ∈ {0, 1}n . In the standard design, the message is masked using the bits xi in the computational-basis positions θ0 := {i : θ[i] = 0}, while the 12

deletion certificate is derived from the Hadamard-basis positions θ1 := {i : θ[i] = 1}. A first observation in [KNY23] is that one may swap the roles of the two bases without loss of generality; we may therefore derive the certificate from θ0 (and use θ1 for masking). Under this convention, the deletion certificate is a string x′ ∈ {0, 1}n , and it is verified by checking x′ [i] = x[i] for all i ∈ θ0 . Since the verification requires x and θ, it is only privately verifiable. To make this check publicly verifiable, [KNY23] “signs” each BB84 qubit with a digital signature. Concretely, for each position i, they attach (coherently) a digital signature σi on the message (i, x[i]). Upon measuring in the computational basis, one obtains x[i] together with a valid signature σi on (i, x[i]). The deletion certificate consists of the revealed measurement outcomes together with the corresponding signatures, and can be verified using the public verification key.3 Security hinges on the fact that an adversary cannot “flip” a signed bit while passing verification. Specifically, consider any i ∈ θ0 . Since the encoding on these positions is in the computational basis, the adversary can obtain at most a signature on (i, x[i]), but is never given a signature on (i, x̄[i]) (even in the superposition). Therefore, by signature unforgeability, no adversary can produce a purported certificate that contains x̄[i] at some checked position i ∈ θ0 together with a valid signature. Hence any certificate that passes verification must be consistent with the underlying x on all checked coordinates, as required. This solution, while elegant, comes at a low rate: in [KNY23] each qubit is accompanied by a signature register, and thus the overhead is at least λ bits per qubit. Moreover, the bit-wise approach does not extend in any straightforward way to coset states, where the state is not a tensor product of single-qubit encodings and one cannot isolate positions that behave as independent classical bits. To overcome both issues, we adopt an alternative viewpoint of BB84 states that naturally generalizes beyond product structure. Rather than viewing |x⟩θ as a tensor product of computational-basis states and Hadamard-basis states, we view it as a uniform superposition over strings satisfying a policy determined by (x, θ). Concretely, X 1 |x⟩θ = p |m⟩, |T x,θ | m∈T x,θ

T x,θ := {m ∈ {0, 1}n : m[i] = x[i] if i ∈ θ0 }.

This suggests signing the entire string m (in superposition) instead of signing each qubit individually. If the signature is compact, then the signature register is short and hence the constant-rate property is preserved. Let us formalize the desired guarantee. We would like to enforce that any successful adversary outputs x′ consistent with x on the checked coordinates, i.e., x′ [i] = x[i] for all i ∈ θ0 . Equivalently, given a signed superposition of the form X 1 p |m, σm ⟩, |T x,θ | m∈T x,θ we want to prevent the adversary from producing a pair (m′ , σ ′ ) such that m′ ∈ / T x,θ and σ ′ verifies as a valid signature on m′ . This is not captured by standard EUF-CMA signatures, since the adversary is given (in superposition) exponentially many valid signatures {σm }m∈T x,θ at once, whereas EUF-CMA only grants polynomially many signing queries. We therefore turn to a signature primitive that enforces a signing policy at the key level. Concretely, we use constrained signatures (CS) [Tsa17, KMY25]. In CS, a signing key skf is associated with a predicate (or function) f , and it can sign a message m only if f (m) = 1. We can view skf as a compact “compressed representation” of the ability to sign all messages m satisfying f (m) = 1. Single-key unforgeability requires 3

The original construction uses one-time signatures with fresh keys per position; for exposition we instead sign (i, x[i]) using a standard signature scheme.

13

that, given skf , it is infeasible to output a valid signature on any m∗ with f (m∗ ) = 0, while signatures are publicly verifiable. Importantly for us, CS can be instantiated for general circuits from the SIS assumption, and the resulting signatures are compact, i.e., their length is essentially independent of the message length. Using CS, one can sign the BB84 state by coherently signing each branch m in the superposition with a key skfx,θ , where fx,θ (m) = 1 iff m ∈ T x,θ . If an adversary A outputs (m′ , σ ′ ) with m′ ∈ / T x,θ and σ ′ valid ′ ′ for m , then this immediately yields a forgery against CS for fx,θ , since fx,θ (m ) = 0. However, using a key skfx,θ that depends on (x, θ) is problematic in our certified-deletion applications: in the relevant reductions, (x, θ) are hidden (and the simulator may only receive a BB84/coset state instance as a black box), so we must be able to generate the signed state without knowing (x, θ). To address this, we instead sign using the “unconstrained” key skf=1 for the constant predicate f=1 = 1, and rely on function privacy of CS to argue that, for messages satisfying the policy, signing under skf=1 is indistinguishable from signing under skfx,θ . At a high level, function privacy states that for any functions f, g and any message m with f (m) = g(m), a signature on m produced under skf is statistically indistinguishable from one produced under skg . To lift this guarantee to our setting—where we sign a quantum superposition over exponentially many messages—it is conceptually convenient to first work in the random oracle model (ROM). In the ROM, we can sign the quantum state coherently by deriving the signing randomness H(m) for each branch m via the random oracle H. This way, the signing randomness is uniformly random and independent across (distinct) branches. We then coherently sign the message using this randomness and uncompute it. This lets us invoke function privacy on each branch, which in turn yields statistical indistinguishability of the resulting signed states. Of course, a truly random oracle cannot be instantiated efficiently. However, our signing procedure uses the oracle only twice (to compute H(m) and to uncompute it). We therefore replace H by a 4-wise independent hash family and invoke Zhandry’s lemma [Zha12], which states that for any algorithm making q quantum queries, a 2q-wise independent hash function is statistically indistinguishable from a random oracle.

3

Preliminaries

Let λ be a security parameter. Let negl(·) denote an arbitrary negligible function; that is, a function such that for any c ∈ N, there exists an N ∈ N such that for all n ≥ N , negl(n) ≤ n−c . Let F denote a finite field. We consider a family of fields {Fλ }λ∈N of polynomial bounded size; that is, f (λ) := |Fλ | is bounded above by some polynomial in λ. Furthermore, in our construction, we assume that Fλ is a prime field, for all λ. That is, |Fλ | is a prime number. We define an indicator 1ϕ , where ϕ is either true or false. If ϕ is true, then 1ϕ = 1. Otherwise, 1ϕ = 0. We define [n] := {1, 2, . . . , n} and [n]0 := {0, 1, 2, . . . , n}. Given a string x ∈ Fn . Let h(x) denote the Hamming weight of x, which counts the number of non- zero indices of x. Let x1 , x2 ∈ Fn . The Hamming distance, denoted by h(x1 , x2 ), is defined as the number of indices at which x1 and x2 differ. Given an index i ∈ [n], let x[i] denote the i-th bit of x. Similarly, let x[−i] denote the sub-string obtained from x by deleting its i-th bit. Furthermore, given a subset P ⊆ [n], let x[P ] denote the sub-string obtained from x by keeping only the bits whose indices are in P . Similarly, let x[−P ] denote the sub-string obtained from x by keeping only the bits whose indices are not in P . Besides, given 1 ≤ a ≤ b ≤ n, we define x[a : b] := x[P ], where P = {a, a + 1, . . . , b}. Let θ ∈ {0, 1}n be a binary string. Let θ0 := {i : θ[i] = 0} and θ1 := {i : θ[i] = 1} denote the sets of positions i where θ[i] equals 0 and 1, respectively. Let x ∈ Fn . Define xθ0 and xθ1 to be the subvectors of x consisting of the entries x[i] for i ∈ θ0 and i ∈ θ1 , respectively. Let R ∈ Fk×n be a matrix. For all i ∈ [k], let R−i denote the (k − 1) × n matrix obtained from R by 14

removing its i-th row. Furthermore, we always use capital bold letter to represent a matrix. We define TD(·, ·) to denote the trace distance of two inputs, overloading the notation so that the inputs may be either quantum states or random variables. The trace distance between states ρ, τ , denoted TD(ρ, τ ), is defined as q  1 1 † TD(ρ, τ ) := ∥ρ − τ ∥1 := Tr (ρ − τ ) (ρ − τ ) . 2 2 Let A be a class of adversaries.4 We say that two families of distributions {D0 }λ and {D1 }λ are indistinguishable against A , denoted by D0 ≈A D1 , if for any adversary in A , its advantage in the following game is negligible in λ: 1. The challenger samples s0 ← D0 , s1 ← D1 , and a bit b ← {0, 1}. It then sends sb to the adversary. 2. The adversary outputs a bit b′ . The adversary’s advantage is defined as Pr[b = b′ ] − 12 .

3.1

Linear Algebra Preliminaries

Definition 3.1 (Properties of Extractors). Let F be a finite field and consider some integer k ≤ n. Let R ∈ Fk×n be a matrix. We now define some properties for an extractor R. • Full-rank: There exist k columns of R that are linearly independent. • Maximum Distance Separable (MDS): Every set of k columns of R are linearly independent. • Efficiently Decodable: View R as an encoder. We say that R can correct up to r errors if there exists a deterministic decoder D : Fn → Fk such that D(mR + e) = m, for all m ∈ Fk and all e ∈ Fn with h(e) ≤ r. An efficient decoder requires that D runs in polynomial time. Example 3.2. Reed–Solomon codes satisfy all the properties in Definition 3.1 as long as |F| ≥ n. Let (Fn , ·) be an n-dimensional vector space equipped with the dot product defined as follow: Let v := (v1 , . . . , vn ), w := (w1 , . . . , wn ) ∈ Fn . Then, v · w :=

n P

vi · w i .

i=1

Also, for each i ∈ [n], let ei ∈ Fn denote the i-th standard basis vector, which is the zero vector except for a 1 in the i-th coordinate. Let V be a finite-dimensional vector space. A set S ⊆ V is a subspace if it is closed under addition and scalar multiplication, denoted S ≤ V . A hyperplane of V is a subspace of a vector space V that has dimension |V | − 1. Let S0 , S1 < V be subspaces. Suppose S0 ∩ S1 = {0}; then their direct sum is written as S0 ⊕ S1 . This means that for any vector v ∈ S0 + S1 := {s0 + s1 : s0 ∈ S0 , s1 ∈ S1 }, there exist unique vectors s0 ∈ S0 and s1 ∈ S1 such that v = s0 + s1 . 4

Following [BGK+ 24], we assume that A is closed under constant-factor increases in space and time.

15

Let V and W be finite-dimensional vector spaces, let S ≤ V , and let R : V 7→ W be a linear function. The image of R under S, denoted by R(S), is the subspace {w ∈ W : ∃s ∈ S s.t. R(s) = w} ≤ W. The fundamental theorem of linear maps says that dim V = dim im R + dim ker R. For a subspace S ≤ V , the dual subspace is defined as S ⊥ := {v ∈ V : ∀u ∈ S, v · u = 0}. Note that unlike in traditional inner product spaces, S ⊥ does not necessarily form a direct sum complement to S; Specifically, it is possible that S ∩ S ⊥ ̸= {0}. For any vector v ∈ V , the coset of S to which v belongs is defined as S + v := {u : ∃s ∈ S, u = s + v}. The set of cosets forms a partition of V , with each coset having equal sizes. Also, for any v, u ∈ Fn , S + v = S + u if and only if v − u ∈ S. A representative coset of S, denoted as co(S) ≤ V , is a subspace that contains exactly one vector from every coset of S. Given S ≤ V , the representative coset co(S) is not unique, and hence the definition of co(S) should be clear from the context. We also denote a representation coset of S as V /S. Lemma 3.3 ([BGK+ 24]). For subspaces S, C ≤ Fn , the following are equivalent: 1. C is a representative coset of S. 2. Fn := S ⊕ C. Based on standard linear algebra, V /S typically denotes the quotient space of V by the subspace S. However, in our setting, we view V /S as a subspace of V , equal to co(S), as a notational shorthand. Note that this is justified since the quotient space V /S is isomorphic to co(S). The following example will be used throughout the paper to define co(S) and V /S. Example 3.4. Let V be a vector space with dimension n. Suppose we are given a subspace S and a basis {v1 , . . . , vn } such that S := span (v1 , . . . , vm ) with m ≤ n. Then, co(S) = V /S can be defined as span (vm+1 , . . . , vn ). Proposition 3.5. The following are properties for dual subspaces and coset. 1. n = dim(S) + dim(S ⊥ ). 2. (S ⊥ )⊥ = S. 3. Consider any subspace S ≤ Fn and two distinct representative cosets of S, namely co(S)1 and co(S)2 . Then, for any v1 ∈ co(S)1 , there exists a unique v2 ∈ co(S)2 such that v1 + S = v2 + S.
4. Fix any subspaces A, B ≤ Fn . If span (A, B) = Fn , then (A ∩ B)⊥ = span A⊥ , B ⊥ . 5. Fix any subspaces S ≤ S + ≤ Fn and any well-defined co(S) and co(S + ). Let P := S + ∩ co(S) and D := co(S + )⊥ ∩ S ⊥ , then P ⊕ D⊥ = Fn .

16

Proof. The proofs of first to third are standard and are therefore omitted. First, we prove the fourth statement. By the definition of dual space, we have A⊥ , B ⊥ ≤ (A ∩ B)⊥ .
Hence, span A⊥ , B ⊥ ≤ (A ∩ B)⊥ . Furthermore, A⊥ ∩ B ⊥ = {0} implies that   dim span A⊥ , B ⊥ = dim(A⊥ ) + dim(B ⊥ ) = 2n − dim(A) − dim(B). Besides,   dim (A ∩ B)⊥ = n − (dim(A) + dim(B) − n) = 2n − dim(A) − dim(B).
Hence, (A ∩ B)⊥ = span A⊥ , B ⊥ . Next, we prove the fifth statement, which is similar to Lemma 5.12 in [BGK+ 24]. We know that D⊥ := (co(S + )⊥ ∩ S ⊥ )⊥ = S ⊕ co(S + ). The last equality follows by the fact that S, co(S + ) ≤ (co(S + )⊥ ∩ S ⊥ )⊥ , dim(S) + dim(co(S + )) = dim(co(S + )⊥ ∩ S ⊥ )⊥ , S ∩ co(S + ) = {0}. Let z = z ′ + z ′′ ∈ P ∩ D⊥ such that z ′ ∈ S and z ′′ ∈ co(S + ). Since z ∈ P ≤ S + , z ′′ := z − z ′ ∈ S + . But z ′′ ∈ co(S + ) as well, so z ′′ = 0. Hence, z = z ′ ∈ S. But z ∈ co(S) as well, so z = 0. Therefore, P ∩ D⊥ = {0}. We conclude the proof by checking the dimension of P and D⊥ . Since dim(P ) = dim(S + ) + dim(co(S)) − n = dim(co(S + )⊥ ) + dim(S ⊥ ) − n = dim(D), we have that dim(P ) + dim(D⊥ ) = n. By Proposition 3.5 we define the following: Definition 3.6. Fix a subspace S and two distinct representative cosets of S, namely co(S)1 and co(S)2 . Also, fix v1 ∈ co(S)1 . We said that v2 ∈ co(S)2 is a vector that corresponds to the choice of v1 , if v2 ∈ co(S)2 is the unique vector such that v1 + S = v2 + S.

3.2

Quantum Preliminaries

Definition 3.7 (Subspace Coset States). For any subspace S ⊆ Fn and vectors v, w ∈ Fn , the coset state |Sv,w ⟩ is defined as: X 1 z·w |Sv,w ⟩ := p ω|F| |z⟩. |S| z∈S+v Proposition 3.8. The following are the properties for subspace coset state. ⊥ • QFT⊗n |Sv,w ⟩ = ω v·w |S−w,v ⟩.

17

• QFT−1

⊗n

⊥ |Sv,w ⟩ = ω v·w |Sw,−v ⟩.

• Let v ∈ co(S) and w ∈ co(S ⊥ ). Let (v ′ , w′ ) correspond to the choice of (v, w). Then |Sv,w ⟩ = |Sv′ ,w′ ⟩. Proof. We prove the first identity; the second follows similarly. X 1 z·w QFT⊗n |Sv,w ⟩ = QFT⊗n · p ω|F| |z⟩ |S| z∈S+v X X (s+v)·(w+y) 1 ω |y⟩ =p |S||F|n y∈Fn s∈S |F| X v·(w+y) 1 =p ω · |S| · 1w+y∈S ⊥ |y⟩ |S||F|n y∈Fn |F| X 1 v·w p ω v·y |y⟩ = ω|F| |S ⊥ | y∈S ⊥ −w |F| v·w ⊥ = ω|F| |S−w,v ⟩, P s·t = |S| · 1 where the third equation follows from s∈S ω|F| t∈S ⊥ and the fourth equation follows from ⊥ n |S| · |S | = |F| .

Lemma 3.9 (Gentle Measurement, [Win02]). Let ρ be a quantum state and let (Π, I − Π) be a projective measurement such that Tr(Πρ) ≥ 1 − δ. Let ρ′ :=

ΠρΠ Tr(Πρ)

√ be the state after applying (Π, I − Π) to ρ and post-selecting on obtaining Π. Then, TD(ρ, ρ′ ) ≤ 2 δ. Lemma 3.10 (Cut-and-Choose, [BF10] Appendix B.3 and Theorem 3). Let |ψ⟩AE be an arbitrary pure quantum state, where register A consists of 2n-qudit, each of dimension |F|. Also, let U1 , . . . , U2n be arbitrary unitaries, each of dimension |F| × |F|. Define a random variable X as follows: 1. Sample P ⊆ [2n] uniformly at random, with |P | = n. 2. Apply U1 , . . . , U2n to register A, acting on each qudit respectively. 3. Measure register A in computational basis and obtain outcome s := s1 ∥s2 ∥ . . . ∥s2n , where si ∈ F for all i. 4. If s[P ] = 0n and h (s[−P ]) > c, set X = 1. Otherwise, set X = 0. √ 2 Then, Pr[X = 1] ≤ 4e−2n·(c/n)2 /32 = 2e−c /32n . The following lemmas are useful for analyzing the advantage of a quantum adversary querying an oracle. Lemma 3.11 ([Zha12]). Let O be an oracle drawn from a 2q-wise independent function family. Any quantum algorithm making at most q queries to O has zero advantage in distinguishing O from a truly random function. Lemma 3.12 ([BZ13]). Let X and Y be sets. Let Dx and Dx′ be distributions on Y. Suppose there exists ϵ ≥ 0, such that for all x ∈ X , TD(Dx , Dx′ ) ≤ ϵ. Let O, O′ : X → Y be functions where, for each x, O(x) and O′ (x) are independently drawn from Dx and Dx′ , respectively. Then any quantum algorithm making at p ′ 3 most q queries to either O or O cannot distinguish the two, except with probability at most cq ϵ with some constant c. 18

4

Quantum Source Seedless Extractor

In this section, we define two distinct quantum sources of randomness, which are extractable using a deterministic extractor: one based on BB84 states and the other on coset states. Readers may skip this section and return to it when needed in Sections 5.1 and 6.1. Due to space constraints, we defer some definitions and proofs throughout the paper to the full version.

4.1

Quantum Source of Randomness Based on BB84 States

First, we define a function f , which will be used in the definition of our quantum source of randomness. The definition of f depends on R ∈ Fk×n , and we assume that R, whose rows are linearly independent, is clear from the context. Definition 4.1. Define f : rowSpan(R) × Fk → F as follows: Express x ∈ rowSpan(R) as a unique linear combination of rows of R. Suppose k X x := αi Ri , i=1

where Ri is the i-th row of the matrix R. Then, we define f as f (x, y) =

k X

αi · y[i].

i=1

Proposition 4.2. f is a bilinear function. Proof. Let x, w ∈ rowSpan(R), y, z ∈ Fk , and γ ∈ F. Suppose x :=

k P i=1

x + w :=

k P

αi Ri and w :=

k P

βi Ri . Then,

i=1

(αi + βi ) · Ri . Hence,

i=1

 k k k P P P    f (x + w, y) = (αi + βi ) · y[i] = αi · y[i] + βi · y[i] = f (x, y) + f (w, y)    i=1 i=1 i=1   k k k  P P P   αi · (y + z)[i] = αi · y[i] + αi · z[i] = f (x, y) + f (x, z)  f (x, y + z) = i=1

i=1

i=1

k k P P    f (γ · x, y) = (γ · αi ) · y[i] = γ · (αi ) · y[i] = γ · f (x, y)    i=1 i=1   k k  P P   αi · (γ · y)[i] = γ · αi · y[i] = γ · f (x, y).  f (x, γ · y) = i=1

i=1

Theorem 4.3 (Conditional Quantum Source Seedless Extractor for BB84 States). Let F be a prime field and consider some integer k ≤ n. Let R ∈ Fk×n be a matrix such that R is MDS (Definition 3.1). Let R−i equal to R but without the i-th row. Let X := X1 , . . . , Xn be a register containing n F-qudits and E be an arbitrary size register. Fix any x ∈ Fn . Consider any quantum state X X 1 |γ⟩XE := p · |x + s + w⟩X ⊗ αw · |ψs ⟩E , (11) |F|k−1 s∈Fn w∈rowSpan(R ) −i

h(s)≤ n−k 2

19

where f (−w,−ℓ′ )

• αw = ω|F|

, for an arbitrary ℓ′ ∈ Fk and f is defined in Definition 4.1.

• {|ψs ⟩}s are arbitrary states such that |γ⟩ is normalized. Let ρEY be the mixed state that results from the following procedure: 1. For each i ∈ [n], apply QFT−1 over F to each register Xi . 2. Initialize a fresh register Y := Y1 · · · Yk containing k F-qudits. Apply the isometry I : |x⟩X 7→ |x⟩X ⊗ |Rx⟩Y . 3. Trace out register X. Then, we have the following state:    ρEY =  

X

s∈Fn h(s)≤ n−k 2

 1 X |r⟩⟨r| |F|

 ED  ⊗ |ψs ⟩⟨ψs | ⊗ ℓ′−i ℓ′−i  Y−i

! .

r∈F

Yi

E

Proof. We track how the state evolves: 1 QFT−1 over F on X (11) 7−−−−−−−−−−−→ p |F|n+k−1 1 I 7− →p |F|n+k−1

X

X

−(x+s+w)·y

X

ω|F|

|y⟩X ⊗ αw · |ψs ⟩E

s∈Fn w∈rowSpan(R−i ) y∈Fn h(s)≤ n−k 2

X

X

X

−(x+s+w)·y

ω|F|

|y⟩X ⊗ αw · |ψs ⟩E ⊗ |Ry⟩Y

(12)

s∈Fn w∈rowSpan(R−i ) y∈Fn h(s)≤ n−k 2

Tracing out register X in term (12) yields ρEY 



      X X X 1   −(x+s +w )·y (x+s +w )·y = n+k−1 ω|F| 1 1 ω|F| 2 2 αw1 αw2 |ψs1 ⟩⟨ψs2 | ⊗ |Ry⟩⟨Ry|Y    |F| y∈Fn  s1 ,s2 ∈Fn w1 ,w2 ∈rowSpan(R−i )  h(s1 )≤ n−k  2

h(s2 )≤ n−k 2

X

=

|ψs1 ⟩⟨ψs2 |E ⊗

s1 ,s2 ∈Fn h(s1 )≤ n−k 2 h(s2 )≤ n−k 2

   = 

E

1 |F|n+k−1

X

X

|ℓ⟩⟨ℓ|Y ·

ℓ∈Fk

αw1 αw2 ·

w1 ,w2 ∈rowSpan(R−i )

X

(s −s )·y (w −w )·y ω|F|2 1 ω|F|2 1

y∈Fn Ry=ℓ

 X s∈Fn h(s)≤ n−k 2

  X 1  |ψs ⟩⟨ψs | ⊗  2k−1 |ℓ⟩⟨ℓ|Y · |F|  k ℓ∈F

 X w1 ,w2 ∈rowSpan(R−i )

E

20

f (w −w1 ,ℓ) 

αw1 αw2 ω|F| 2

(13)



   = 

X s∈Fn h(s)≤ n−k 2

  X 1  |ψs ⟩⟨ψs | ⊗  2k−1 |ℓ⟩⟨ℓ|Y · |F|  k ℓ∈F

X s∈Fn h(s)≤ n−k 2

ω|F|

(14)



w1 ,w2 ∈rowSpan(R−i )

E

   = 

 f (w2 −w1 ,ℓ−ℓ′ )

X

 ED  |ψs ⟩⟨ψs | ⊗ ℓ′−i ℓ′−i ⊗  Y−i

1 X |r⟩⟨r| |F|

!

r∈F

.

(15)

Yi

E

We explain why the equality (13) holds. Suppose, w1 , w2 are fixed and y ∈ Fn is an arbitrary vector satisfying Ry = ℓ. Then, (w2 − w1 ) · y = f (w2 − w1 , ℓ). (w −w )·y

Hence, ω|F|2 1 can be viewed as a constant inside the summation over ℓ, w1 , w2 . Now, suppose s1 ̸= s2 . We know that h(s2 − s1 ) ≤ n − k, and hence there are k positions where s2 − s1 is zero, while the remaining n − k positions are arbitrary but not all zero; we denote these remaining positions by P , which consist of n − k indices. By the MDS properties of R, the values of y at positions in P can be chosen arbitrarily, while the values at positions outside P are uniquely determined by R and ℓ. Then, we have X (s −s )·y X (s −s )[P ]·y[P ] ω|F|2 1 = ω|F|2 1 = 0, y∈Fn Ry=ℓ

y[P ]∈Fn−k

where the last equality follows from the fact that (s2 − s1 )[P ] is not all zero. The equality (14) follows from the fact that f is a bilinear function. Finally, we explain why the last equality (15) holds. We first consider the case that ℓ−i ̸= ℓ′−i . Then, X

f (w −w1 ,ℓ−ℓ′ )

ω|F| 2

= |F|k−1 ·

w1 ,w2 ∈rowSpan(R−i )

X

f (w,ℓ−ℓ′ )

ω|F|

X

= |F|k−1 ·

′

ω α·(ℓ−i −ℓ−i ) = 0,

α∈Fk−1

w∈rowSpan(R−i )

where the last equality follows from the definition of f . We then consider the case that ℓ−i = ℓ′−i . No matter the value of ℓi , we have X X f (w −w ,ℓ−ℓ′ ) ω|F| 2 1 = |F|k−1 · ω α·0 = |F|2k−2 . w1 ,w2 ∈rowSpan(R−i )

4.2

α∈Fk−1

Quantum Source of Randomness Based on Subspace Coset States

We define a sampling process to generate various subspaces, which will be useful in our construction. Before that we show a proposition that help us to define the sampling process. Proposition 4.4. Let λ ∈ N be a security parameter, c > 0 be a constant, k + cλ ≤ n3 , F be a finite field satisfying 2 ≤ |F|, and R ∈ Fk×n be a full-rank matrix. If k + cλ vectors w1 , . . . , wk+cλ ∈ Fn are sampled uniformly at random subject to being linearly independent, then with 1 − negl(λ) probability, R(span (w1 , . . . , wk+cλ )) = Fk . 21

Proof. By the fundamental theorem of linear maps, it is sufficient to find a subspace B ≤ span (w1 , . . . , wk+cλ ) with dimension k such that B ∩ ker R = {0}. We can choose B with the following procedure: 1. Let j = 0 2. For 1 ≤ ℓ ≤ k, do the following: (a) j ← j + 1 (b) If wj ∈ / span (ker R, z1 , . . . zℓ−1 ), let zℓ := wj . Continue the loop (i.e., jump back to Step 2). (c) If j = k + cλ, return B := ⊥; otherwise, jump back to Step (a). 3. Return B := span (z1 , . . . , zk ). Suppose {wi } are sampled uniformly random, then Pr[⊥] = ≤

Pr [ ∃ hyperplane H ∀j ∈ [k + cλ], R(wj ) ∈ H] X Pr [ ∀j ∈ [k + cλ], yj ∈ H]

wj ←Fn

H⪇Fk dim(H)=k−1

≤

X

yj ←Fk

|F|−1

k+cλ

H⪇Fk dim(H)=k−1

k+cλ |F|k − 1 · |F|−1 |F| − 1 = negl(λ), =

where the first inequality follows from union bound, R is full-rank, and wj is sampled uniformly random; the second equality counts the number of hyperplanes of Fk . Furthermore, if {wi } are sampled uniformly random, then they are linearly independent with overwhelming probability. Hence, the above procedure outputs ⊥ with negligible probability. Since wj ∈ / span (ker R, z1 , . . . zℓ−1 ) for all ℓ ∈ [k], a standard linear algebra argument implies that B ∩ ker R = {0}. Proposition 4.5. Given subspace A, co(A) ≤ Fn , then co(A⊥ ) := co(A)⊥ is well-defined. Proof. By Lemma 3.3, co(A⊥ ) must be some subspace V ≤ Fn such that A⊥ ⊕ V = Fn . Hence, it
is sufficient to show that A⊥ ⊕ co(A)⊥ = Fn . Indeed, by Proposition 3.5, span A⊥ , co(A)⊥ = Fn . Furthermore, dim(A⊥ ) + dim(co(A)⊥ ) = n. Definition 4.6 (Procedure to Sample Subspaces). Given parameters k, n, λ ∈ N such that k + λ ≤ n4 , let F be a prime field, and let R ∈ Fk×n be a full rank matrix. We say that   [S, T ] := S, T, co(S), co(T ), co(S ⊥ ), co(T ⊥ ), {Pi }i∈[k] , {Di }i∈[k] , {Si+ }i∈[k] , P is sampled uniformly at random over Fn if the sampling procedure is described as below: 22

o n 1. Sample n2 linearly independent vectors z1 , . . . , z n2 uniformly at random. Then, sample n4 linearly n o independent vectors z n2 +1 , . . . , z 3n uniformly at random. 4

2. Define   S := span z1 , . . . , z n2 . 3. Let

  T = span z1 , . . . , z 3n . 4

If one of the following events happen, the sampling procedure is said to fail:   • span z n2 +1 , . . . , z 3n ∩ S ̸= {0} or 4    ̸= Fk • R span z n2 +1 , . . . , z 3n 4

If the procedure fails, return ⊥ together with all subspaces. This occurs with only negligible probability. Indeed, since n4 ≥ Θ(λ), the first event occurs with negligible probability. Moreover, since n 4 ≥ k + Θ(λ), Proposition 4.4 implies that the second event also occurs with negligible probability. Finally, the claim follows by the union bound. n o 4. Sample n4 linearly independent vectors z 3n +1 , . . . , zn uniformly at random such that together with 4 o n z1 , . . . , z 3n form a basis of Fn . 4

5. Let

    , . . . , z co(S) := span z n n     ( 2 +1)     , . . . , z co(T ) := span z 3n n  ( 4 +1) ⊥ ⊥ co(S ) := (co(S))      co(T ⊥ ) := co(T )⊥    P := T /S := co(S) ∩ T

(By Proposition 4.5) (By Proposition 4.5)

6. For each i ∈ [k], define (

Pi := ker R−i |P Si+ := span (S, Pi )

7. For each i ∈ [k], let βi be a set of linearly independent vectors such that: ( Pi ∩ span (βi ) = {0} span (Pi , βi ) = P. Define P/Pi := span (βi ). 8. For each i ∈ [k], we define co(Si+ ), co((Si+ )⊥ ), and Di as follows:    +  co(S ) := span β , z , . . . , z 3n  n i i +1  4

co((Si+ )⊥ ) := co((Si+ ))⊥    D := co((S + )⊥ ) ∩ S ⊥ i i

23

(By Proposition 4.5)

dim

n 2

0

n 2

co(S)

S Si+

vker vimg T

3n 4 −k+1

P

u

0

co(S ⊥ )

S⊥

w

ṽker ṽimg (Si+ )⊥ n 4 +k−1

co(T ⊥ )

co(T )

3n 4

D

v0 := vker + vimg ∈ P

dim

T⊥ n 4

ṽ0 := ṽker + ṽimg ∈ D

Figure 1: Coset basis decomposition. Each blue rectangle represents a vector space. An overlap between the sides of two rectangles indicates that they share a subset of basis vectors, with the size of the overlap corresponding to the dimension of the shared subspace. We say that the subspaces [S, T ] are sampled successfully (over Fn ) if they do not return ⊥ at Step 3. When given [S, T ], we condition on the event that they are sampled successfully. We illustrate the relationships among the different subspaces and vectors, defined in Definition 4.6, in the following Figure 1. Next, we present several propositions and theorems that are useful for proving our main theorem. Proposition 4.7. The following algorithm can be implemented efficiently. 1. Sample [S, T ] uniformly at random over dimension n and sample (vimg + u, w) ← co(Si+ ) × co(S ⊥ ), where vimg ∈ P/Pi and u ∈ co(T ). P |vker ⟩|Svker +vimg +u,w ⟩. 2. Construct √1 |Pi | v

ker ∈Pi

Proof. Given v, w ∈ Fn . We show how to construct |Sv,w ⟩. 1 X 1 X minus v |0⟩ 7→ p |z⟩ 7−−−−→ p |z − v⟩ |S| z∈S |S| z∈S X z ′ ·(−v) X (z ′ +w)·(−v) 1 1 QFT⊗n w·v 7−−−−→ p ω|F| |z ′ ⟩ = ω|F| ·p ω|F| |z ′ ⟩ ⊥ ⊥ |S | z ′ ∈S ⊥ |S | z ′ ∈S ⊥ X 1 add w (z ′ +w)·(−v) ′ w·v w·v ⊥ 7−−−→ ω|F| ·p ω|F| |z + w⟩ = ω|F| · |Sw,−v ⟩ ⊥ |S | z ′ ∈S ⊥ QFT⊗n

7−−−−→ |Sv,w ⟩, where the firstP mapping can be implemented by Gaussian elimination. To construct the state in Step 2, we again implement |vker ⟩ using Gaussian elimination. Then, conditioned on vker , we construct |Svker +vimg +u,w ⟩ vker ∈Pi

using the algorithm described above.

24

Proposition 4.8. Given [S, T ], for each i ∈ [k], there exists a unitary Ui such that for any vker ∈ Pi , X v ·ev 1 ω ker ker · |e vker ⟩ Ui |vker ⟩ = p |Di | ve ∈D |F| i

ker

and for any veker ∈ Di ,

X −v ·ev 1 Ui† |e vker ⟩ = p ω ker ker · |vker ⟩. |Pi | v ∈P |F| ker

i

Also, Ui can be implemented efficiently. Proof. First, we define Ui and calculate Ui |vker ⟩ as follows. 1

X

|0⟩|vker ⟩ 7→

q

7→

|Di⊥ | z∈Di⊥ X 1

q

|Di⊥ | z∈Di⊥ X 1

7→ QFT⊗n

7−−−−→

|z⟩|vker ⟩ |z + vker ⟩|vker ⟩

X (z+v )·0 1 |z + vker ⟩|0⟩ = q ω|F| ker |z + vker ⟩|0⟩ = |(Di⊥ )vker ,0 ⟩ ⊥ ⊥ |Di | z∈Di⊥ |Di | z∈Di⊥ X v ·ev 1 |(Di )0,vker ⟩ = p ω ker ker |e vker ⟩ ⊗ |0⟩. |Di | ve ∈D |F| q

ker

i

The third mapping follows from the fact that Pi ⊕ Di⊥ = Fn (by Proposition 3.5), and hence there exists a function such that z + vker 7→ vker . Furthermore, this function can be efficiently implemented by using Gaussian elimination. The last mapping simply apply QFT⊗n on the first register. Next, we calculate U † |e vker ⟩ by reversing all of the operations above. ⊗n X −(z+v )·ev (QFT−1 ) 1 |e vker ⟩|0⟩ 7−−−−−−−→ p ω|F| ker ker |z + vker ⟩|0⟩ |F|n ⊥

z∈Di vker ∈Pi

7→

X −(z+v )·ev 1 p ω|F| ker ker |z + vker ⟩|vker ⟩ |F|n ⊥ z∈Di vker ∈Pi

7→

X −(z+v )·ev X X −v ·ev 1 1 1 p ω|F| ker ker |vker ⟩ ω|F| ker ker |z⟩|vker ⟩ = q |z⟩ · p ⊥ |F|n |P | i v ∈P ⊥ ⊥ |D | z∈Di vker ∈Pi

7→

|0⟩ ⊗ p

i

1

X

|Pi | v

z∈Di

ker

i

−vker ·e vker ω|F| |vker ⟩.

ker ∈Pi

The first and second mappings follows from the fact that Pi ⊕ Di⊥ = Fn . The equation follows from the fact that z ∈ Di⊥ and veker ∈ Di , and hence z · veker = 0.

25

Theorem 4.9 (Quantum Source Seedless Extractor for Coset States). Fix k ≤ n ∈ N. Let F be a prime field and let R ∈ Fk×n be a matrix such that R has full rank. Given subspaces [S, T ] over Fn (Definition 4.6). Let X be a register containing n F-qudits. Consider any quantum state |γ⟩X := |e vker ⟩X ,

(16)

such that veker ∈ Di for some i. Let ρY be the mixed state that results from the following procedure: 1. Apply Ui† on register X, where Ui is defined as Proposition 4.8.

2. Initialize a fresh register Y := Y1 · · · Yk containing k F-qudits. Apply the isometry I : |x⟩X 7→ E |x⟩X ⊗ R(x + a) , for some arbitrary fixed a ∈ Fn . Y

3. Trace out register X. Then, ρY =

! 1 X |ℓ⟩⟨ℓ| |F| ℓ∈F

⊗ (Ra) [−i]Y−i .

Yi

Proof. |γ⟩X :=

|e vker ⟩X

Apply U † on X

i 7−−−−−− −−→

Apply I

7−−−−→ Trace out X

7−−−−−−→

=

X 1 p ω −vker ·evker |vker ⟩X |Pi | v ∈P i ker E X 1 p ω −vker ·evker |vker ⟩X ⊗ R(vker + a) Y |Pi | v ∈P i ker ED X 1 R(vker + a) R(vker + a) |Pi | Y vker ∈Pi ! ED 1 X ⊗ (Ra)[−i] (Ra)[−i] . |ℓ⟩⟨ℓ| |F| Y−i ℓ∈F

Yi

The first mapping follows from Proposition 4.8. Next, we prove the last equality. Let W = ker R|Pi . Since vker ∈ Pi , R(vker ) ∈ span (ei ). Hence, the Y−i registers must contain a fixed vector (Ra)[−i]. Furthermore, R(T /S) = Fk implies that R(Pi ) = span (ei ), and hence W ⪇ Pi . For each v ∈ Pi , consider the coset v + W . These cosets are either identical or disjoint and they all have the same size. Let x, y, w ∈ Pi such that x = y + w. Then, we know that R(x) = R(y) ⇐⇒ R(w) = 0 ⇐⇒ x + W = y + W Since W ⪇ Pi , there exists a v ∈ Pi such that v + W ̸= W . This implies that the set W, v + W, 2v + W, . . . , (|F| − 1)v + W are all disjoint and their union is Pi . Since  R(W ), R(v + W ), R(2v + W ), . . . , R((|F| − 1)v + W ) = F, the register Yi has the state ! 1 X |ℓ⟩⟨ℓ| . |F| ℓ∈F

26

Yi

5

Certified Deletion for BB84 States

In this section, we extend the certified everlasting lemma [BK23] to the constant-rate regime. When instantiated with “all-or-nothing”–type primitives, this extension yields certified deletion constructions with constant-rate.

5.1

Main Theorem

Here, we prove the constant-rate version of the certified deletion lemma. To capture a wide range of applications, we abstract out the hiding mechanism underlying the primitives as quantum operation Z with semantic security, following [BK23]. Z may be public key encryption, secret key encryption, commitments, or witness encryption. Definition 5.1 (Semantically Secure). We say that a quantum operation {Zλ }λ∈N is semantically-secure against any non-uniform QPT {Aλ }λ∈N , if for all polynomial poly(·), for all s1 , s2 ∈ Fpoly(λ) , for all σλ with poly(λ) qubits, the following holds: Pr[Aλ (Zλ (s1 ), σλ ) = 1] − Pr[Aλ (Zλ (s2 ), σλ ) = 1] = negl(λ). Theorem 5.2. Let λ ∈ N be the security parameter. Fix k, n ∈ N such that 3k + Θ(λ) ≤ 2n. Consider a family of finite prime fields {Fλ }λ∈N with polynomial bounded field sizes. Let R ∈ Fk×n be a matrix  n−k  that is both MDS and efficiently decodable with error 2 (Definition 3.1). Let m ∈ Fk be a classical message and Z n o = {Zλ (·)}λ∈N be a quantum operation with classical input. Define the following distribution Aλ EXPλ (m) over quantum states, obtained by running Aλ as follows. λ∈N

1. Sample x ← F2n , a balanced θ ← {0, 1}2n , which means that θ is sampled randomly under the condition h(θ) = n, and r ← Fk . Initialize Aλ with QFTθ |x⟩, m + Rxθ0 + r, Zλ (θ, r).

(17)

2. Aλ ’s output is parsed as a string x′ ∈ F2n and a residual state ρ. If xθ1 = x′θ1 , then output ρ, and otherwise output a special symbol ⊥. If Z is semantically-secure against any non-uniform QPT {Aλ }λ∈N (Definition 5.1), then for all non-uniform QPT {Aλ }λ∈N and for all m ∈ Fk ,   Aλ k λ TD EXPA (18) λ (m), EXPλ (0 ) = negl(λ).
⊗2n Remark 5.3. An honest deletion operation applies QFT−1 to the quantum state, measures the resulting state in the computational basis, and sends all measurement outcomes to the sender. Remark 5.4. Equation (17) in Theorem 5.2 demonstrates that our construction attains a constant rate. Specifically, the hidden message m has a size of k · log |F| bits, while the quantum state QFTθ |x⟩, which encrypts the message, consists of 2n · log |F| qubits. By setting 2n = 3k + Θ(λ), we achieve a constant rate of approximately 13 assuming that the message size is significantly larger than the security parameter. Moreover, Equation (18) formalizes that all information regarding the underlying message m is deleted once the deletion proof x′ is certified. 27

Remark 5.5. The statement in Theorem 5.2 does not imply an approximate rate-1 construction. However, it is enough to set (1 + ϵ)k + Θ(λ) ≤ n, for any constant ϵ > 0. Moreover, we do not need to sample a balanced θ in Step 1. To minimize the number of quantum bits used, we may sample θ ← {0, 1}n+ϵn such that exactly n entries are 0 (computational basis, for encrypting m) and ϵn entries are 1 (Hadamard basis, for verified deletion). The size of x is then adjusted to Fn+ϵn to match the length of θ. With this adjustment, we obtain a rate-(1 − ϵ′ ) certified deletion scheme for primitives instantiated from BB84, for any constant ϵ′ > 0. Since the proof is similar, we instead present the main theorem with cleaner parameters for clarity. To achieve an approximately rate-1 construction, the main difference in the proof is the use of an unbalanced cut-and-choose argument. Additionally, if one is satisfied with merely negligible security, then (1 + ϵ)k + ω(log λ) ≤ n are sufficient. However, in most settings a failure probability smaller than inverse exponential is required, in which case Θ(λ) is required instead of ω(log λ). Proof of Theorem 5.2. To prove the theorem, we define a sequence of hybrid distributions. We start by k λ defining Hyb0 (m) to be identical to EXPA λ (m). Our goal is therefore to show that Hyb0 (m) and Hyb0 (0 ) are statistically close for all m. We establish this via a hybrid argument over individual field elements. Without loss of generality, we focus on the first coordinate: specifically, we show that Hyb0 (m) and Hyb0 (m + αe1 ) are statistically close for any α ∈ F, where e1 = 1|0k−1 . To this end, we introduce a sequence of hybrid experiments from Hyb0 to Hyb3 , such that each pair of consecutive hybrids is statistically indistinguishable. It therefore suffices to show that Hyb3 (m) and Hyb3 (m + αe1 ) are statistically close. This final step relies on the extraction lemma from Theorem 4.3. Applying the extraction lemma requires that the challenger’s quantum state satisfies a specific structural condition. This condition is enforced by inserting a measurement M in Hyb3 . To argue that introducing M only negligibly affects the experiment, we show that its outcome is almost fixed and invoke the gentle measurement lemma. To establish this, we further introduce sub-hybrids Hyba2 through Hybe2 . The consecutive games are indistinguishable by the semantic security of Z, and if the outcome distribution of M were to change noticeably, the measurement result itself would yield a predicate that distinguishes the hybrids, since the measurement can be efficiently implemented. Hyb0 (m):

λ This is the distribution {EXPA λ (m)}λ∈N described above.

Hyb1 (m): In this hybrid, the first field of the second register (which contains information about the message) is replaced by a uniformly random field element b ← F. The dependence on the first element of the message, m[1] ,is deferred until after the adversary sends a deletion certificate x′ . 1. Sample x ← F2n , a balanced θ ← {0, 1}2n , r ← Fk , b ← F. 2. Initialize Aλ with QFTθ |x⟩Aθ0 Aθ1 , b∥(m + Rxθ0 + r)[2 : k], Zλ (θ, r). Aλ ’s output is parsed as a string x′ ∈ F2n and a residual state ρ. Here, |x⟩Aθ0 Aθ1 denotes an encoding of x into a register A consisting of 2n qudits. The register A is notationally decomposed into two parts, Aθ0 and Aθ1 : the i-th qudit belongs to Aθ0 if θ[i] = 0, and to Aθ1 if θ[i] = 1, where θ[i] is the i-th bit of θ ∈ {0, 1}2n . Importantly, this decomposition is only for the purpose of analysis. In the actual experiment, the entire register A—containing all 2n qudits—is provided at once, and the holder of A has no information about the partition induced by θ. 3. If b ̸= (m + Rxθ0 + r)[1] or xθ1 ̸= x′θ1 , then output ⊥. Otherwise, output ρ. 28

Hyb2 (m): In this hybrid, x is purified, and its choice is deferred until after the adversary sends a deletion certificate x′ . 1. Sample a balanced θ ← {0, 1}2n , r ← Fk , and b ← F. Prepare the following state: E E E X E x b∥(m + Rxθ0 + r)[2 : k] ⊗ x b∥(m + Rxθ0 + r)[2 : k] x

Cθ0 Cθ1

C2

Aθ0 Aθ1

A2

.

2. Initialize Aλ with the registers Aθ0 Aθ1 A2 , Zλ (θ, r). Aλ ’s output is parsed as a string x′ ∈ F2n and a residual state ρ. 3. Measure Cθ0 and Cθ1 with computational basis and Fourier basis, respectively. That is, apply QFT⊗n on Cθ1 and measure in computational basis. Say we obtain x. 4. If b ̸= (m + Rxθ0 + r)[1] or xθ1 ̸= x′θ1 , then output ⊥. Otherwise, output ρ. Hyb3 (m): In this hybrid, we insert a projective measurement {M, I − M} immediately before Step 3 of the previous hybrid Hyb2 (m). The measurement {M, I − M} is defined right after the hybrid is described. 1. Sample a balanced θ ← {0, 1}2n , r ← Fk , and b ← F. Prepare the following state: E E E X E x b∥(m + Rxθ0 + r)[2 : k] ⊗ x b∥(m + Rxθ0 + r)[2 : k] x

Cθ0 Cθ1

C2

Aθ0 Aθ1

A2

.

2. Initialize Aλ with the registers Aθ0 Aθ1 A2 and Z(θ, r). Aλ ’s output is parsed as a string x′ ∈ F2n and a residual state ρ. 3. Apply a projective measurement {M, I − M} and post-select on obtaining the outcome I − M. Note that in the hybrids, the guessed field element b is placed at position i = 1. Also, the definition of M is determined by θ, x′ , r, m[−i], and i. 4. Measure Cθ0 and Cθ1 with computational basis and Fourier basis, respectively. Say we obtain x. 5. If b ̸= (m + Rxθ0 + r)[1] or xθ1 ̸= x′θ1 , then output ⊥. Otherwise, output ρ. To define M, we first define a unitary Ux,a [i] through its inverse. −1 [i]: Let x ∈ Fn and a ∈ Fk . U −1 [i] is a unitary that satisfies the following for all s such Definition of Ux,a x,a that h(s) ≤ n−k : 2 −1 Ux,a [i]

|x + s⟩ 7−−−−→ QFT−1

⊗n

·p

1

X

|F|k−1

f (x+s−y,−a)

ω|F|

|y⟩,

y∈x+s+rowSpan(R−i )

where f is defined in Definition 4.1 and R−i denote the (k − 1) × n matrix obtained from R by removing its i-th row. −1 [i] is indeed a unitary. Suppose s ̸= s are two vectors, with both Hamming First, we will show that Ux,a 1 2 n−k weight not greater than 2 . The property that every set of k columns of R is linearly independent implies that

29

every non-zero vector in rowSpan(R) has Hamming weight at least n − k + 1, whereas h(s1 − s2 ) ≤ n − k. Hence, 0 ̸= s1 − s2 ̸∈ rowSpan(R). This implies that s1 − s2 ̸∈ rowSpan(R−i ). Then, x + s1 + rowSpan(R−i ) ∩ x + s2 + rowSpan(R−i ) = ∅. −1 [i] preserves orthogonality and the norm, it can be extended to a unitary. Second, we will show Since Ux,a that Ux,a [i] can be implemented efficiently.

QFT−1 Apply QFT⊗n

7−−−−−−−−→ =

⊗n

X 1 f (x+s−y,−a) ω|F| |y⟩ ·p k−1 |F| y∈x+s+rowSpan(R−i ) X f (x+s−y,−a) ω|F| |y⟩

1 p |F|k−1 y∈x+s+rowSpan(R ) −i E X f (−cT ·R ,−a) −i ω|F| x + s + cT · R−i c∈Fk−1

Initialized registers ABC

7−−−−−−−−−−−−−→ Efficient Decoder

7−−−−−−−−−→ Compute f based on A and D

7−−−−−−−−−−−−−−−−→ Apply a phase shift depends on C

7−−−−−−−−−−−−−−−−−−→ Uncompute C then D

7−−−−−−−−−−−→ Apply QFT⊗(k−1) on B

7−−−−−−−−−−−−−→ Trace out BCD

7−−−−−−−−→

D

E X f (−cT ·R ,−a) 1 −i p |0⟩A ω|F| |0⟩B |0⟩C x + s + cT · R−i D |F|k−1 c∈Fk−1 E X f (−cT ·R ,−a) 1 −i p ω|F| |0⟩B |0⟩C x + s + cT · R−i |x + s⟩A D |F|k−1 c∈Fk−1 E E X f (−cT ·R ,−a) 1 −i p |x + s⟩A ω|F| |c⟩B f (−cT · R−i , −a) x + s + cT · R−i C D |F|k−1 c∈Fk−1 E E X 1 p |c⟩B f (−cT · R−i , −a) x + s + cT · R−i |x + s⟩A C D |F|k−1 c∈Fk−1 X 1 p |x + s⟩A |c⟩B |0⟩C |0⟩D |F|k−1 c∈Fk−1 |x + s⟩A |0⟩B |0⟩C |0⟩D |x + s⟩

The step of the “efficient decoder” can be implemented efficiently, since R is efficiently decodable and x is known. Hence, there exists an efficient classical algorithm such that for all c ∈ Fk , x + s + cT · R 7→ cT · R, and furthermore, it can compute x + s. Definition of projective measurement {M, I−M}: Here, we define a measurement Mi . The measurement M appearing in Hyb3 is the special case of i = 1, i.e., M = M1 . The definition of Mi is determined by θ, x′ , r, m[−i], and i. We will define a CPTP map Φ, and let Q be a unitary that uses extra ancilla and defers all measurements in Φ. The projective measurement Mi is then defined as Q† ΠQ, where Π := |0⟩⟨0|Ans denotes the orthogonal projector. Φ is defined as follows: 1. Measure C2 in computational basis and obtain b∥ℓ.

30

2. Apply Ux′θ ,ℓ−(r+m)[−i] [i] and QFT on Cθ0 and Cθ1 , respectively. Measure Cθ0 and Cθ1 , obtaining xθ0 0 and xθ1 , respectively. 3. If xθ1 ̸= x′θ1 or h(xθ0 , x′θ0 ) ≤ n−k 2 , then set the “Ans” register as |1⟩ (i.e., I − M). Otherwise, set it as |0⟩. Analyzing the Hybrids.

In the following, we relate TD(Hybi (m), Hybi (m + αe1 )) for different i.

Lemma 5.6. Let e1 ∈ Fk be the indicator string in which all positions are 0 except the first position, which is 1. For all m ∈ Fk and for all α ∈ F, we have 1 · TD (Hyb0 (m), Hyb0 (m + α · e1 )) |F| = TD (Hyb1 (m), Hyb1 (m + α · e1 )) = TD (Hyb2 (m), Hyb2 (m + α · e1 )) . Proof. Let us consider the first equation. If b = (m + Rxθ0 + r)[1], the output distribution is identical to Hyb0 (m). Otherwise, the output distribution is ⊥, regardless of whether the input is m or m + α · e1 . Also, b is sampled uniformly at random and independent of any other variables. Hence,   1 1 TD (Hyb1 (m), Hyb1 (m + α · e1 )) = · TD (Hyb0 (m), Hyb0 (m + α · e1 )) + 1 − · 0. |F| |F| The second equation follows since purification and deferral of operations leave the outcome distribution unchanged. For relating the trace distance in Hyb2 and that in Hyb3 , we need the following lemma. Since the proof is somewhat involved, we defer the proof for the time being. Lemma 5.7. For all m ∈ Fk , the measurement outcome at Step 3 in Hyb3 (m) yields the outcome I − M with 1 − negl(λ) probability. Lemma 5.8. For all m ∈ Fk and α ∈ F, we have TD (Hyb2 (m), Hyb2 (m + α · e1 )) ≤ TD (Hyb3 (m), Hyb3 (m + α · e1 )) + negl(λ). Proof. By Lemma 5.7, we know that the projective measurement at Step 3 in Hyb3 yields the outcome I − M with probability 1 − negl(λ). Next, the Gentle Measurement Lemma 3.9 implies that the claim holds. Indeed, let ρ be the joint state (including both the challenger’s and the adversary’s view) after Step 2 in Hyb2 , and let ρ′ be the joint state after Step 3 in Hyb3 . By Gentle Measurement lemma, TD(ρ, ρ′ ) ≤ negl′ (λ). This implies that for all m ∈ Fk , TD(Hyb2 (m), Hyb3 (m)) ≤ negl′ (λ). Hence, TD (Hyb2 (m), Hyb2 (m + α · e1 )) ≤ TD (Hyb2 (m), Hyb3 (m)) + TD (Hyb3 (m), Hyb3 (m + α · e1 )) + TD (Hyb3 (m + α · e1 ), Hyb2 (m + α · e1 )) ≤ TD (Hyb3 (m), Hyb3 (m + α · e1 )) + 2 · negl′ (λ).

Lemma 5.9. For all m ∈ Fk and α ∈ F, we have TD (Hyb3 (m), Hyb3 (m + α · e1 )) ≤ negl(λ). 31

Proof. First three steps of Hyb3 are independent of m[1]. Hence, the challenger’s and the adversary’s joint view after Step 3 is identical between Hyb3 (m) and Hyb3 (m + α · e1 ). The measurement outcome I −M guarantees that either (a) xθ1 ̸= x′θ1 or (b) h(xθ0 , x′θ0 ) ≤ n−k 2 . Suppose we condition on the case where event (a) occurs. Then, there is no advantage between the two hybrids, since the hybrids always output ⊥ in Step 5. Moreover, event (a) occurs with the same probability in both hybrids. Therefore, it suffices to condition on the case where event (b) occurs. Moreover, even under this condition, the joint view of the challenger and the adversary remains identical between Hyb3 (m) and Hyb3 (m + α · e1 ). If the event (b) occurs, the state after step 3 must have the form   X (19) Ux−1 [1] · |x′θ0 + s⟩Cθ0 ⊗ |ψs ⟩A , ′ ,ℓ′ θ0

Cθ0

s∈Fn h(s)≤ n−k 2

with ℓ′ := ℓ − (r + m)[2 : k]. Then, Equation (19)
⊗n 1 = QFT−1 C p θ0 |F|k−1 =

⊗n 1 QFT−1 C p θ0 |F|k−1

X

f (x′θ +s−y,−ℓ′ )

X

ω|F| 0

|y⟩Cθ0 ⊗ |ψs ⟩A

s∈Fn y∈x′θ +s+rowSpan(R−1 ) 0 h(s)≤ n−k 2

X

X

f (−w,−ℓ′ )

|x′θ0 + s + w⟩Cθ0 ⊗ ω|F|

· |ψs ⟩A ,

(20)

s∈Fn w∈rowSpan(R−1 ) h(s)≤ n−k 2

where {|ψs ⟩}s are arbitrary states such that the state in Equation (20) is normalized. Moreover, {ψs }s remains identical between Hyb3 (m) and Hyb3 (m + α · e1 ). By the extractor Theorem 4.3, we know that if we measure Cθ0 register and obtain xθ0 , then Rxθ0 [1] is uniformly random and independent of the adversary’s view. Hence, checking whether b ̸= (m + Rxθ0 + r)[1] or b ̸= (m + Rxθ0 + r)[1] + α occurs with equal probability and is independent of the residual state ρ. Note that although r is sampled uniformly at random, it is not independent of the adversary’s view and therefore is not a good source of randomness. Putting everything together, we conclude the proof of Theorem 5.2. By Lemmata 5.6, 5.8 and 5.9, we have k

TD(Hyb0 (m), Hyb0 (0 )) ≤

k X

TD Hyb0 0i−1 ∥m[i : k] , Hyb0 0i ∥m[i + 1 : k]

i=1

≤ k · |F| · negl(λ) = negl′ (λ), where the first inequality follows from the triangle inequality. Note that previous hybrids and Claims are all based on “guessing” the first entry as b. We need to slightly modified all the hybrids and Claims for each i. For example, in Hyb1 , we have to replace the ith entry of (m + Rxθ0 + r) with b at Step 2. Also, check whether b ̸= (m + Rxθ0 + r) [i] at Step 3. The modification is straightforward and we omit the details. This completes the proof of Theorem 5.2. It remains to prove Lemma 5.7, which claims that the measurement result is I − M in Hyb3 with overwhelming probability. The rest of this subsection is devoted to the proof of the lemma. 32

Proof of Lemma 5.7. We introduce the following “branch-hybrids”, Hyba2 (m) through Hybe2 , to argue that the projective measurement {M, I − M} inserted in Hyb3 (m) yields the outcome I − M with overwhelming probability, using the semantic security of Z. Hyba2 (m): In this hybrid, we simulate the outcome of the projective measurement {M, I − M} performed in Step 3 of Hyb3 (m). 1. Sample a balanced θ ← {0, 1}2n , r ← Fk , and b ← F. Prepare the following state: E E E X E x b∥(m + Rxθ0 + r)[2 : k] ⊗ x b∥(m + Rxθ0 + r)[2 : k] x

Cθ0 Cθ1

C2

Aθ0 Aθ1

A2

.

2. Initialize Aλ with registers Aθ0 Aθ1 A2 and Z(θ, r). Aλ ’s output is parsed as a string x′ ∈ F2n . 3. Measure C2 in computational basis and obtain b∥ℓ. 4. Apply Ux′θ ,ℓ−(r+m)[2:k] [1] and QFT on Cθ0 and Cθ1 , respectively. Measure Cθ0 and Cθ1 , obtaining 0 xθ0 and xθ1 , respectively. 5. If xθ1 ̸= x′θ1 or h(xθ0 , x′θ0 ) ≤ n−k 2 , then return I − M. Otherwise, return M. Hybb2 (m): In this hybrid, the measurement of C2 is moved to occur prior to the initialization of Aλ ’s register. In addition, Z(θ, r) is replaced by Z(02n , 0k ). 1. Sample a balanced θ ← {0, 1}2n , r ← Fk , and b ← F. Prepare the following state E E E X E x b∥(m + Rxθ0 + r)[2 : k] ⊗ x b∥(m + Rxθ0 + r)[2 : k] x

Cθ0 Cθ1

C2

Aθ0 Aθ1

A2

.

2. Measure C2 in computational basis and obtain b∥ℓ. 3. Initialize Aλ with registers Aθ0 Aθ1 A2 and Z(02n , 0k ). Aλ ’s output is parsed as a string x′ ∈ F2n . 4. Apply Ux′θ ,ℓ−(r+m)[2:k] [1] and QFT on Cθ0 and Cθ1 , respectively. Measure Cθ0 and Cθ1 , obtain xθ0 0 and xθ1 , respectively. 5. If xθ1 ̸= x′θ1 or h(xθ0 , x′θ0 ) ≤ n−k 2 , then return I − M. Otherwise, return M. Hybc2 : In this hybrid, the register A2 is unentangled from the other registers. Also, the register C2 is constructed from register Cθ0 . In addition, the operation U −1 no longer depends on m. 1. Sample a balanced θ ← {0, 1}2n , b ← F, and ℓ ← Fk−1 . Prepare the following state X |x⟩Cθ0 Cθ1 ⊗ |x⟩Aθ0 Aθ1 , b∥ℓA2 . x

2. Apply the isometry I: |x⟩Cθ0 7→ |x⟩Cθ0 |R−1 xθ0 ⟩C2 , where R−1 ∈ F(k−1)×n is equal to R but without the first row. 33

3. Measure C2 in computational basis and obtain ℓ′ ∈ Fk−1 . 4. Initialize Aλ with register Aθ0 Aθ1 A2 and Z(02n , 0k ). Aλ ’s output is parsed as a string x′ ∈ F2n . 5. Apply Ux′θ ,ℓ′ [1] and QFT on Cθ0 and Cθ1 , respectively. Measure Cθ0 and Cθ1 , obtain xθ0 and xθ1 , 0 respectively. 6. If xθ1 ̸= x′θ1 or h(xθ0 , x′θ0 ) ≤ n−k 2 , then return I − M. Otherwise, return M. Hybd2 :

In this hybrid, some operations acting on different registers are reordered.

1. Sample b ← F and ℓ ← Fk−1 . Prepare the following state X |x⟩C ⊗ |x⟩A , b∥ℓA2 . x

2. Initialize Aλ with register AA2 and Z(02n , 0k ). Aλ ’s output is parsed as a string x′ ∈ F2n . 3. Sample a balanced θ ← {0, 1}2n . 4. Apply QFT on Cθ1 . Measure Cθ1 and obtain xθ1 . If xθ1 ̸= x′θ1 , then return I − M. 5. Apply the isometry I : |x⟩Cθ0 7→ |x⟩Cθ0 |R−1 xθ0 ⟩C2 . 6. Measure C2 in computational basis and obtain ℓ′ . 7. Apply Ux′θ ,ℓ′ [1] on Cθ0 . Measure Cθ0 and obtain xθ0 . 0

8. If h(xθ0 , x′θ0 ) ≤ n−k 2 , then return I − M. Otherwise, return M. Hybe2 :

In this hybrid, we perform a measurement and post-select on the register Cθ0 .

1. Sample b ← F and ℓ ← Fk−1 . Prepare the following state X |x⟩C ⊗ |x⟩A , b∥ℓA2 . x

2. Initialize Aλ with register AA2 and Z(02n , 0k ). Aλ ’s output is parsed as a string x′ ∈ F2n . 3. Sample a balanced θ ← {0, 1}2n . 4. Apply QFT on Cθ1 . Measure Cθ1 and obtain xθ1 . If xθ1 ̸= x′θ1 , then return I − M. 5. Define the following projector Πx′θ : 0

Πx′θ := 0

X

QFT−1

⊗n

|y⟩⟨y|QFT⊗n .

y∈Fn h(y,x′θ )≤ n−k 2 0

Apply a projective measurement {Πx′θ , I − Πx′θ } on Cθ0 and post-selecting on obtaining the outcome 0 0 Πx′θ . 0

34

6. Apply the isometry I : |x⟩Cθ0 7→ x

E Cθ0

R−1 xθ0

E C2

.

7. Measure C2 in computational basis and obtain ℓ′ . 8. Apply Ux′θ ,ℓ′ [1] on Cθ0 . Measure Cθ0 and obtain xθ0 . 0

9. If h(xθ0 , x′θ0 ) ≤ n−k 2 , then return I − M. Otherwise, return M. Analyzing the Sub-hybrids In the following, we show that the measurement outcome are only negligibly different between the consecutive hybrids.   Lemma 5.10. For all m ∈ Fk , Pr [Hyba2 (m) = I − M] ≥ Pr Hybb2 (m) = I − M − negl(λ). Proof. In Hybb2 , we measure the C2 register before sending the quantum state to the adversary. Since the adversary operates on different registers, their operation commutes with the measurement on C2 . that there exists hNext, suppose (by contradiction) i h i a polynomial p(·) such that for infinite many λ, a b 1 Pr Hyb2 (m) = I − M < Pr Hyb2 (m) = I − M − p(λ) . We will construct a reduction R that breaks the semantic security of Z. The reduction R runs exactly as the experiment Hybb2 , except that in Step 3, Aλ ’s registers are initialized as Aθ0 Aθ1 A2 , ch, where ch is either Z(θ, r) or Z(02n , 0k ), as sent by the challenger. By the definition of Ux′θ ,ℓ−(r+m)[2:k] [1], all operations can be implemented efficiently (This is why we say 0 the predicate is efficiently checkable), and hence R is a QPT algorithm. Finally, if the experiment outputs M, R guesses the challenge is Z(θ, r). Otherwise, R guesses the challenge is Z(02n , 0k ). Then, R breaks the 1 semantic security with advantage 2·p(λ) . Lemma 5.11. For all m ∈ Fk , Hybb2 (m) = Hybc2 . Proof. The following first term is the state described in Hybb2 (m) at Step 1.

Measure C

2 7−−−−−−→

E E E X E 1 p · x b∥(m + Rxθ0 + r)[2 : k] ⊗ x b∥(m + Rxθ0 + r)[2 : k] Cθ0 Cθ1 C2 Aθ0 Aθ1 A2 |F||θ| x X 1 p |x⟩Cθ0 Cθ1 |x⟩Aθ0 Aθ1 , b∥ℓA2 , b∥ℓC2 · |θ|−k+1 |F| x (m+Rxθ0 +r)[2:k]=ℓ

=

1 p · |θ|−k+1 |F|

X x Rxθ0 [2:k]=ℓ−(r+m)[2:k]

|x⟩Cθ0 Cθ1 |x⟩Aθ0 Aθ1 , b∥ℓA2 , b∥ℓC2

(21)

The second term holds since columnSpan(R−1 ) has dimension k − 1, where R−1 is equal to R but without the first row. Hence, the state of Hybb2 (m) after Step 2 is the mixed state of term (21) over the randomness of θ, r, ℓ, and b, where they are sampled uniformly and independently on their own domain. Next, we consider

35

the mixed state of Hybc2 after Step 3. The first term below corresponds to the state described in Hybc2 at Step 1.

I

7− → Measure C

2 7−−−−−−→

X 1 p · |x⟩Cθ0 Cθ1 |x⟩Aθ0 Aθ1 , b∥ℓA2 |F||θ| x X 1 p |x⟩Cθ0 Cθ1 |Rxθ0 [2 : k]⟩C2 |x⟩Aθ0 Aθ1 , b∥ℓA2 · |F||θ| x X 1 p · |x⟩Cθ0 Cθ1 |x⟩Aθ0 Aθ1 , b∥ℓA2 , ℓ′C2 |θ|−k+1 |F| x

(22)

Rxθ0 [2:k]=ℓ′

Again, the third term holds since columnSpan(R−1 ) has dimension k − 1. Hence, the state of Hybc2 (m) after Step 3 is the mixed state of term (22) over the randomness of θ, ℓ, ℓ′ , and b, where they are sampled uniformly and independently on their own domain. In Hybb2 (m), it uses the view of registers Cθ0 Cθ1 Aθ0 Aθ1 A2 , as well as variables ℓ − (r + m)[2 : k] to obtain output. Similarly, in Hybc2 , it uses the view of registers Cθ0 Cθ1 Aθ0 Aθ1 A2 , as well as variables ℓ′ to obtain output. It appears that the distribution of both hybrids’ view is identical. Lemma 5.12. Hybc2 = Hybd2 . Proof. Consider Hybc2 . (i) The adversary Aλ ’s operations are moved forward to Step 2. (ii) Sampling of θ is deferred until after the adversary Aλ ’s operations. (iii) The operation on the Fourier register Cθ1 is moved forward, but performed after sampling θ. The reordering preserves the output distribution, since the operations act on different registers and therefore commute. Lemma 5.13. Pr[Hybd2 = I − M] ≥ Pr[Hybe2 = I − M] − negl(λ). Proof. Consider the state after Step 2 in both hybrids and we know that this state is fixed. Suppose the adversary Aλ causes xθ1 = x′θ1 with probability p(λ) in Step 4. Note that the only source of randomness is the sampling of θ during Step 3. Let q(λ) denote the probability that the projective measurement outcome corresponds to I −Πx′θ at Step 5 in Hybe2 , conditioning on the event that xθ1 = x′θ1 . We have 3k +Θ(λ) ≤ 2n. 0

′

1 −x [i] QFT, Hence, by the Cut-and-Choose Lemma 3.10 with c := n−k 2 ≥ 6 (n + Θ(λ)) and all Ui set to X where X is the Pauli-X operator, we have 2

2

p(λ) · q(λ) ≤ 2e−(n+Θ(λ)) /(6 ·32n) = negl(λ). Let ρ and ρ′ are the states after Step 4 in Hybd2 and after Step 5 in Hybe2 , respectively. By gentle measurement Lemma 3.9, we have p TD(ρ, ρ′ ) ≤ 2 q(λ). p Hence, the distributions of the two hybrids, Hybd2 and Hybe2 , differ with probability p(λ) · 2 q(λ) ≤ negl′ (λ). Lemma 5.14. Pr [Hybe2 = I − M] = 1.

36

Proof. The following is the state after Step 5 of Hybe2 . X
⊗n ′ QFT−1 |xθ0 + s⟩Cθ0 ⊗ |ψs ⟩

(23)

s∈Fn h(s)≤ n−k 2

1

=

X

p |F|n

X

  − x′θ +s x 0

ω|F|

|x⟩Cθ0 ⊗ |ψs ⟩,

s∈Fn x∈Fn h(s)≤ n−k 2

where |ψs ⟩ is an arbitrary (non-normalized) state that may be entangled with Cθ0 and makes the state in (23) normalized. Apply the isometry I : |x⟩Cθ0 7→ |x⟩Cθ0 |R−1 xθ0 ⟩C2 at Step 6. Then, the state becomes 1

X

X

p |F|n

  − x′θ +s x 0

ω|F|

|x⟩Cθ0 |R−1 x⟩C2 ⊗ |ψs ⟩.

s∈Fn x∈Fn h(s)≤ n−k 2

At Step 7, suppose we measure C2 and we obtain ∗∥ℓ′ . The remaining state becomes 1

X

p |F|n−k+1

=

=

  − x′θ +s x

X

ω|F|

0

x s∈Fn R−1 x=ℓ′ h(s)≤ n−k 2

1 1 ⊗n ·p QFT−1 C · p θ0 n |F| |F|n−k+1

X

⊗n 1 QFT−1 C · p θ0 |F|k−1

|x⟩Cθ0 ⊗ |ψs ⟩

X

  − x′θ +s−y x

X

ω|F|

0

x s∈Fn y∈Fn R−1 x=ℓ′ h(s)≤ n−k 2

|y⟩Cθ0 ⊗ |ψs ⟩

f (x′θ +s−y, −ℓ′ )

X

X

s∈Fn h(s)≤ n−k 2

y y∈x′θ +s+rowSpan(R−1 )

ω|F| 0

|y⟩Cθ0 ⊗ |ψs ⟩.

(24)

0

The last equality holds by the following: Consider y ∈ x′θ0 + s + rowSpan(R−1 ) and an arbitrary x satisfied R−1 x = ℓ′ . Then, x′θ0 + s − y ∈ rowSpan(R−1 ). This implies that (x′θ0 + s − y) · (−x) = f (x′θ0 + s − y, −ℓ′ ). Together with the fact that columnSpan(R−1 ) has dimension k − 1, we have X x Rx[2:k]=ℓ′

  − x′θ +s−y x

ω|F|

0

f (x′θ +s−y, −ℓ′ )

|y⟩Cθ0 ⊗ |ψs ⟩ = |F|n−k+1 · ω|F| 0

|y⟩Cθ0 ⊗ |ψs ⟩.

Since the size of rowSpan(R−1 ) is |F|k−1 , we know that the state in (24) has norm 1 and hence any y∈ / x′θ0 + s + rowSpan(R−1 ) has amplitude 0. Next, at Step 8, we apply Ux′θ ,ℓ′ on Cθ0 in Equation (24), and the state becomes 0 X |x′θ0 + s⟩Cθ0 ⊗ |ψs ⟩. s∈Fn h(s)≤ n−k 2 ′ After measuring the register Cθ0 , we obtain an outcome xθ within Hamming distance n−k 2 of xθ0 and hence e the output of Hyb2 is I − M with probability 1.

37

We conclude the proof of Lemma 5.7. By Lemmata 5.10 to 5.14, we know that the projective measurement at Step 3 in Hyb3 yields the outcome I − M with probability 1 − negl(λ). Indeed, the procedure in Hyba2 is equivalent to Steps 1 through 3 in Hyb3 , with the following difference: Hyba2 does not defer the measurement and does not do post-selection. Hence, the measurement outcome probabilities of I − M and M are identical in both hybrids. This completes the proof of Lemma 5.7.

5.2

Applications of BB84 Constructions.

[BK23] propose a unified approach for upgrading “all-or-nothing”-type cryptographic primitives to support certified deletion. We first present their main theorem with minor modifications to align with our format. Theorem 5.15 ([BK23], Theorem 3.1). Let λ be the security parameter, R ∈ {0, 1}1×λ be the all-ones matrix, m ∈ {0, 1} be a single bit n message and o {Zλ (·, ·)}λ∈N be a quantum operation with classical input. Aλ Define the following distribution EXPλ (m) over quantum states, obtaining by running Aλ as follows. λ∈N

1. Sample x ← {0, 1}2λ and a balanced θ ← {0, 1}2λ . Initialize Aλ with H θ |x⟩, Zλ (θ, m + Rxθ0 ). 2. Aλ ’s output is parsed as a string x′ ∈ {0, 1}2λ and a residual state ρ. If xθ1 = x′θ1 , then output ρ, and otherwise output a special symbol ⊥. If Z is semantically-secure against any non-uniform QPT {Aλ }λ∈N (Definition 5.1), then for all non-uniform QPT {Aλ }λ∈N ,   Aλ λ TD EXPA (0), EXP (1) = negl(λ). λ λ They use Theorem 5.15 as a black box to upgrade various cryptographic schemes to support certified deletion, including commitment schemes, secret-key encryption, public-key encryption, attribute-based encryption, fully homomorphic encryption, timed-release encryption, and witness encryption. Suppose the underlying message is a string; they encrypt the message bitwise. Formally, let m ∈ {0, 1}k with some k ∈ N, the construction is as follows: (i) For each i ∈ [k], sample xi ← {0, 1}2λ and balanced θi ← {0, 1}2λ . (ii) Construct n i o n  o H θ |xi ⟩ , Zλ θi , m[i] + R(xi )θi , 0

i∈[k]

i∈[k]

where R = 1λ is an all-ones vector in their construction. To upgrade the cryptographic scheme to support constant-rate certified deletion, one modification is to replace the quantum state and the extractor matrix R with our constructions. The proof follows that of [BK23], except that Theorem 5.15 is replaced by our constant-rate version, Theorem 5.2. However, since the message m + Rxθ0 serves as an input to Z in Theorem 5.15, our construction should account for this. Let m ∈ Fk with some k ∈ N, the construction is as follows: (i) Sample x ← F2n and a balanced θ ← {0, 1}2n , and r ← Fk , with n = λ + 1.5k. (ii) Construct QFTθ |x⟩, m + Rxθ0 + r, Zλ (θ, r, m + Rxθ0 + r). The proof of modified Theorem 5.2 follows a similar logic to the original. However, when purifying x in Hyb2 , Hyb3 , Hyba2 , and Hybb2 , the term Zλ (θ, r, b∥(m + Rxθ0 + r)[2 : k]) must be purified together. If Z is a randomized function, it is sufficient to use the same randomness coherently. To explain this, we slightly ∗ ∗ modify Hybb2 and Hybc2 to obtain Hybb2 and Hybc2 as follows: 38

∗

Hybb2 (m): 1. Sample a balanced θ ← {0, 1}2n , r ← Fk , and b ← F. Prepare the following state E X E ⊗ b∥(m + Rxθ0 + r)[2 : k] x C2

Cθ0 Cθ1

x

x

E Aθ0 Aθ1

E b∥(m + Rxθ0 + r)[2 : k]

A2

E Zλ (θ, r, b∥(m + Rxθ0 + r)[2 : k])

A3

.

2. Measure C2 in computational basis and obtain b∥ℓ. 3. Initialize Aλ with registers Aθ0 Aθ1 A2 A3 . Aλ ’s output is parsed as a string x′ ∈ F2n . 4. Apply Ux′θ ,ℓ−(r+m)[2:k] [1] and QFT on Cθ0 and Cθ1 , respectively. Measure Cθ0 and Cθ1 , obtain xθ0 0 and xθ1 , respectively. 5. If xθ1 ̸= x′θ1 or h(xθ0 , x′θ0 ) ≤ n−k 2 , then return I − M. Otherwise, return M. ∗

Hybc2 : 1. Sample a balanced θ ← {0, 1}2n , b ← F, and ℓ ← Fk−1 . Prepare the following state X |x⟩Cθ0 Cθ1 ⊗ |x⟩Aθ0 Aθ1 , b∥ℓA2 . x

2. Apply the isometry I: |x⟩Cθ0 7→ |x⟩Cθ0 |R−1 xθ0 ⟩C2 , where R−1 ∈ F(k−1)×n is equal to R but without the first row. 3. Measure C2 in computational basis and obtain ℓ′ ∈ Fk−1 . 4. Initialize Aλ with register Aθ0 Aθ1 A2 and Z(0, 0, 0). Aλ ’s output is parsed as a string x′ ∈ F2n . 5. Apply Ux′θ ,ℓ′ [1] and QFT on Cθ0 and Cθ1 , respectively. Measure Cθ0 and Cθ1 , obtain xθ0 and xθ1 , 0 respectively. 6. If xθ1 ̸= x′θ1 or h(xθ0 , x′θ0 ) ≤ n−k 2 , then return I − M. Otherwise, return M. ∗

∗

The equality Hybb2 = Hybc2 follows similarly to Hybb2 = Hybc2 . Indeed, the challenger will measure the C2 register in the computational basis. Consequently, b∥(m+Rxθ0 +r)[2 : k] and Zλ (θ, r, b∥(m+Rxθ0 +r)[2 : k]) will collapse to classical strings. This also justifies why it is sufficient to use the same randomness for Z across all superposition. Furthermore, we apply the semantic security of Z to show that the output of Z is indistinguishable between the two hybrids.

6

Certified Deletion for Subspace Coset States

6.1

Main Theorem

Note that we provide a visual illustration in Figure 1 of the subspaces defined in Definition 4.6. Hence, when we sample [S, T ], the following are well-defined.   S, T, co(S), co(T ), co(S ⊥ ), co(T ⊥ ), {Pi }i∈[k] , {Di }i∈[k] , {Si+ }i∈[k] , P 39

and T /S, {P/Pi }i∈[k] are well-defined. We define the notion of subspace hiding, which is similar to [BGK+ 24]. Definition 6.1 (Subspace Hiding). Let A be a class of adversaries. Sample [S, T ] uniformly at random over dimension n (Definition 4.6). Choose an arbitrary R ∈ Fk×n . Also, sample (u, w) ← co(T ) × co(S ⊥ ) and an arbitrary string m′ ∈ Fk . We say that a QPT operation {Zλ }λ∈N is subspace-hiding for A if there exists a QPT simulator {Sλ }λ∈N such that ⊥ • Sample a 3n 4 -dimension superspace G of S uniformly at random. Let x ∈ co(G) be the unique coset such that S ⊥ + w ⊂ G + x. We have that

R, S, T, u, w, Zλ (S, T, u, w, m′ ) ≈A R, S, T, u, w, Sλ (G, T, u, x, m′ ). Theorem 6.2. Let λ be the security parameter. Fix k, n ∈ N such that 4k + Θ(λ) ≤ n. Consider a family of finite prime fields {Fλ }λ with polynomial bounded sizes (and for simplicity, we suppress the subscript). Let m ∈ Fk be classical messages, R ∈ Fk×n be a full rank n matrix, and o {Zλ (·)}λ∈N be a quantum operation Aλ with classical input. Define the following distribution EXPλ (m) over quantum states, obtained by λ∈N

running Aλ as follows.

1. Sample [S, T ] uniformly at random over Fn (Definition 4.6). Next, sample (v, w) ← co(S) × co(S ⊥ ), uniformly at random. 2. Let u ∈ co(T ) be the unique coset such that S + v ⊂ T + u. Initialize Aλ with |Sv,w ⟩, Zλ (S, T, u, w, m + Rv). 3. Aλ ’s output is parsed as a string ze ∈ Fn and a residual state ρ. If ze ∈ S ⊥ + w, then output ρ, and otherwise output a special symbol ⊥. Let A be a class of adversaries that contains QPT algorithms. If {Zλ }λ∈N is subspace-hiding for A (Definition 6.1), then for all {Aλ }λ∈N ∈ A and for all m ∈ Fk ,   Aλ k λ TD EXPA (m), EXP (0 ) = negl(λ). λ λ
⊗n ⊥ Remark 6.3. An honest deletion operation applies QFT−1 to the quantum state, obtaining |Sw,−v ⟩, measures the resulting state in the computational basis, and sends all measurement outcomes to the sender. Proof of Theorem 6.2. To prove the theorem, we define a sequence of hybrid distributions. We start by k λ defining Hyb0 (m) to be identical to EXPA λ (m). Our goal is therefore to show that Hyb0 (m) and Hyb0 (0 ) are statistically close for all m. We establish this via a hybrid argument over individual field elements. Without loss of generality, we focus on the first coordinate: specifically, we show that Hyb0 (m) and Hyb0 (m + αe1 ) are statistically close for any α ∈ F, where e1 = 1|0k−1 . To this end, we introduce a sequence of hybrid experiments from Hyb0 to Hyb4 , such that each pair of consecutive hybrids is statistically indistinguishable. It therefore suffices to show that Hyb4 (m) and Hyb4 (m + αe1 ) are statistically close. This final step relies on the extraction lemma from Theorem 4.9. Applying the extraction lemma requires that the challenger’s 40

quantum state satisfies a specific structural condition. This condition is enforced by inserting a measurement M in Hyb4 . To argue that introducing M only negligibly affects the experiment, we show that its outcome is almost fixed and invoke the gentle measurement lemma. To establish this, we further introduce sub-hybrids Hyba3 through Hybe3 . The consecutive games are indistinguishable by the subspace-hiding security of Z, and if the outcome distribution of M were to change noticeably, the measurement result itself would yield a predicate that distinguishes the hybrids, since the measurement can be efficiently implemented. Hyb0 (m):

λ This is the distribution {EXPA λ (m)}λ∈N described above.

Hyb1 (m): In this hybrid, the first field element of m + Rv is replaced by a uniformly random field element b ← F. The dependence on the message m[1] is deferred until after the adversary sends a proof ze. 1. Sample [S, T ] uniformly at random over Fn . Sample vectors (v, w) ← co(S) × co(S ⊥ ) and a field b ← F. Prepare |Sv,w ⟩A 2. Let u ∈ co(T ) be the unique coset such that S + v ⊂ T + u. Initialize Aλ with A, Z (S, T, u, w, b∥(m + Rv)[2 : k]) . Aλ ’s output is parsed as a string ze ∈ Fn and a residual state ρ. 3. If b ̸= (m + Rv)[1] or ze ̸∈ S ⊥ + w, then output ⊥. Otherwise, output ρ. Hyb2 (m):

In this hybrid, |Sv,w ⟩A is obtained by purifying the choice of vker , followed by a measurement.

1. Sample [S, T ] uniformly at random over Fn (Definition 4.6). Hence, we have P1 = ker(R−1 |P ) and S + := span (S, P1 ). Sample vectors (vimg , u, w) ← (P/P1 ) × co(T ) × co(S ⊥ ) and a field b ← F. Prepare X 1 p |vker ⟩C |Svker +vimg +u,w ⟩A , |P1 | v ∈P1 ker

and measure the C register to obtain vker . Let v = vker + vimg + u. 2. Initialize Aλ with A, Z(S, T, u, w, b∥(m + Rv)[2 : k]). Aλ ’s output is parsed as a string ze ∈ Fn and a residual state ρ. 3. If b ̸= (m + Rv)[1] or ze ̸∈ S ⊥ + w, then output ⊥. Otherwise, output ρ. Hyb3 (m): In this hybrid, vker is purified, and its choice is deferred until after the adversary sends a proof ze. 1. Sample [S, T ] uniformly at random over Fn . Hence, we have P1 = ker(R−1 |P ) and S + := span (S, P1 ). Sample vectors (vimg , u, w) ← (P/P1 ) × co(T ) × co(S ⊥ ) and a field b ← F. Prepare X 1 p |vker ⟩C |Svker +vimg +u,w ⟩A . |P1 | v ∈P1 ker

41

2. Initialize Aλ with A, Z(S, T, u, w, b∥(m + R(vimg + u))[2 : k]). Aλ ’s output is parsed as a string ze ∈ Fn and a residual state ρ. 3. Measure the C register to obtain vker . Let v = vker + vimg + u. If b ̸= (m + Rv)[1] or ze ̸∈ S ⊥ + w then output ⊥. Otherwise, output ρ. Hyb4 (m): In this hybrid, we insert a projective measurement immediately before Step 3 of the previous hybrid Hyb3 (m). We define the measurement M immediately after describing the hybrid. 1. Sample [S, T ] uniformly at random over Fn . Hence, we have P1 = ker(R−1 |P ) and S + := span (S, P1 ). Sample vectors (vimg , u, w) ← (P/P1 ) × co(T ) × co(S ⊥ ) and a field b ← F. Prepare X 1 p |vker ⟩C |Svker +vimg +u,w ⟩A . |P1 | v ∈P1 ker

2. Initialize Aλ with A, Z(S, T, u, w, b∥(m + R(vimg + u))[2 : k]). Aλ ’s output is parsed as a string ze ∈ Fn and a residual state ρ. 3. Apply a projective measurement {M, I − M} and post-selecting on obtaining the outcome I − M. Note that in the hybrids, the definition of M is determined by the position of guessed b, which is at i = 1. 4. Measure the C register to obtain vker . Let v = vker + vimg + u. If b ̸= (m + Rv)[1] or ze ̸∈ S ⊥ + w, then output ⊥. Otherwise, output ρ. Definition of projective measurement {M, I − M}: We will define a CPTP map Φ, and let Q be a unitary that uses extra ancilla and defers all measurements in Φ. The projective measurement I − M is then defined as Q† ΠQ, where Π := |1⟩⟨1|Ans denotes the orthogonal projector. Φ is defined as follows: 1. Let i = 1. Apply Ui on register C, where Ui is defined in Proposition 4.8. Measure C in computational basis to obtain veker .
⊥ 2. If ze ̸∈ S ⊥ + w or ze ∈ S + + veker + w, then set the “Ans” register as |1⟩. Otherwise, set it as |0⟩. Analyzing the Hybrids.

In the following, we relate TD(Hybi (m), Hybi (m + αe1 )) for different i.

Lemma 6.4. Let e1 ∈ Fk be the indicator string in which all positions are 0 except the first position, which is 1. For all m ∈ Fk and for all α ∈ F, we have 1 · TD (Hyb0 (m), Hyb0 (m + α · e1 )) |F| = TD (Hyb1 (m), Hyb1 (m + α · e1 )) = TD (Hyb2 (m), Hyb2 (m + α · e1 )) = TD (Hyb3 (m), Hyb3 (m + α · e1 )) . 42

Proof. The first equation follows from the same argument as in Lemma 5.6 of the BB84-based protocol. Next, consider the second equation. We know that co(S) = P1 ⊕ (P/P1 ) ⊕ co(T ). In Hyb1 , a vector v is sampled uniformly from co(S), which is equivalent to sampling vker uniformly from P1 , vimg uniformly from P/P1 , and u uniformly from co(T ) in Hyb2 , and then set v = vker + vimg + u. Finally, consider the third equation. We first replace Rv[2 : k] with R(vimg + u)[2 : k] and defer the measurement of C until after the adversary outputs. Indeed, we know that Rv[2 : k] = R(vker + vimg + u)[2 : k] = Rvker [2 : k] + R(vimg + u)[2 : k] = R(vimg + u)[2 : k]. Furthermore, the deferring process does not change the distribution, since the adversary’s operation commutes with the operation on C. For relating the trace distance in Hyb3 and that in Hyb4 , we need the following lemma. Since the proof is somewhat involved, we defer the proof for the time being. Lemma 6.5. For all m ∈ Fk , the measurement outcome at Step 3 in Hyb4 (m) yields the outcome I − M with 1 − negl(λ) probability. The following Lemma follows from Lemma 6.5 and is similar to Lemma 5.8; hence, we omit the proof. Lemma 6.6. For all m ∈ Fk and α ∈ F, we have TD (Hyb3 (m), Hyb3 (m + α · e1 )) ≤ TD (Hyb4 (m), Hyb4 (m + α · e1 )) + negl(λ). Lemma 6.7. For all m ∈ Fk and α ∈ F, we have TD (Hyb4 (m), Hyb4 (m + α · e1 )) ≤ negl(λ). Proof. First three steps of Hyb4 are independent of m[1]. Hence, the challenger’s and the adversary’s joint view after Step 3 is identical between Hyb4 (m) and Hyb4 (m + α · e1 ). The measurement outcome I − M guarantees that if we apply Ui on C register and measure the register to obtain veker . Then the following holds: Either (a) ze ̸∈ S ⊥ + w or (b) ze ∈ (S + )⊥ + veker + w. Suppose we condition on the case where event (a) occurs. Then, there is no advantage between the two hybrids, since the hybrids always output ⊥ in step 4. Moreover, event (a) occurs with the same probability in both hybrids, since the adversary has no information about m[1]. Therefore, it suffices to condition on the case where event (b) occurs. Moreover, even under this condition, ρ remains identical among Hyb4 (m) and Hyb4 (m + α · e1 ). We know that veker ∈ D1 := co((S + )⊥ ) ∩ S ⊥ . Indeed, the vector in register C after Step 2 belongs to P1 . By Proposition 4.8, if we apply Ui on the register C and measure it with computational basis, the measurement outcome must belongs to D1 . Also, if the event (b) occurs, the measurement outcome, say veker , must be a unique vector such that ze − veker − w ∈ (S + )⊥ . Hence, the state after step 3 must have the form Ui† |e vker ⟩C , where veker is the unique vector defined by ze. Indeed, if event (b) occurs, I − M is a rank-one projector, and hence the C register is independent of the adversary’s state. By the extractor Theorem 4.9, we know that if we measure C register and obtain vker , then R(vker + vimg + u)[1] is uniformly random and independent of adversary’s view. Hence, checking whether b ̸= (m + Rv)[1] or b ̸= (m + Rv)[1] + α occurs with equal probability and is independent of the residual state ρ. 43

Putting everything together, we conclude the proof of Theorem 6.2. k

TD(Hyb0 (m), Hyb0 (0 )) ≤

k X

By Lemmata 6.4, 6.6 and 6.7,

TD Hyb0 0i−1 ∥m[i : k] , Hyb0 0i ∥m[i + 1 : k]

i=1

≤ k · |F| · negl(λ) = negl′ (λ), where the first inequality follows from the triangle inequality and the second inequality follows from Lemmata 6.4, 6.6 and 6.7. Note that previous hybrids and Claims are all based on “guessing” the first field element as b. We need to slightly modify all the hybrids and Claims for each i. For example, in Hyb1 , we have to replace the ith bit of (m + Rv) with b at Step 2. Also, check whether b ̸= (m + Rv) [i] at Step 3. The modification is straightforward and we omit the details. It remains to prove Lemma 6.5, which claims that the measurement result is I − M in Hyb4 with overwhelming probability. The rest of this subsection is devoted to the proof of the lemma. Proof of Lemma 6.5. We introduce the following “branch-hybrids”, Hyba3 (m) through Hybe3 (m), to argue that the projective measurement {M, I − M} inserted in Hyb4 (m) yields the outcome I − M with overwhelming probability, under the subspace-hiding security of Z(·). Hyba3 (m): This is the same as Hyb4 (m), except that Hyba3 (m) does not defer the measurement and does not perform post-selection. Moreover, the experiment stops after the measurement outcome I − M or M is obtained. 1. Sample [S, T ] uniformly at random over Fn . Hence, we have P1 = ker(R−1 |P ) with P = co(S) ∩ T (See Definition 4.6). Define a subspace S + := span (S, P1 ). Sample vectors (vimg , u, w) ← (P/P1 ) × co(T ) × co(S ⊥ ) and a field b ← F. Prepare X 1 p |vker ⟩C |Svker +vimg +u,w ⟩A . |P1 | v ∈P1 ker

2. Initialize Aλ with A, Z(S, T, u, w, b∥(m + R(vimg + u))[2 : k]). Aλ ’s output is parsed as a string ze ∈ Fn and a residual state ρ. 3. Apply U1 on register C. Measure C to obtain veker .
⊥ 4. If ze ̸∈ S ⊥ + w or ze ∈ S + + veker + w, then return I − M. Otherwise, return M. Hybb3 (m): In this hybrid, the unitary U1 is applied before sending the messages to the adversary. Besides, if [S, T ] are not successfully sampled, return M. 1. Sample [S, T ] uniformly at random over Fn . If the subspaces [S, T ] are not successfully sampled, return M.

44

2. We have P1 = ker(R−1 |P ) with P = co(S) ∩ T . Define a subspace S + := span (S, P1 ). Sample vectors (vimg , u, w) ← (P/P1 ) × co(T ) × co(S ⊥ ) and a field b ← F. Prepare X 1 p |vker ⟩C |Svker +vimg +u,w ⟩A . |P1 | v ∈P1 ker

3. Apply U1 on register C. Measure C to obtain veker . 4. Initialize Aλ with A, Z(S, T, u, w, b∥(m + R(vimg + u))[2 : k]). Aλ ’s output is parsed as a string ze ∈ Fn and a residual state ρ.
⊥ 5. If ze ̸∈ S ⊥ + w or ze ∈ S + + veker + w, then return I − M. Otherwise, return M. Hybc3 (m):

In this hybrid, Step 2 of Hybc3 computes the result of Steps 2 and 3 of Hybb3 .

1. Sample [S, T ] uniformly at random over Fn . If the subspaces [S, T ] are not successfully sampled, return M. 2. We have P1 = ker(R−1 |P ) with P = co(S) ∩ T . Define a subspace S + := span (S, P1 ). Sample vectors (vimg , u, w) ← (P/P1 ) × co(T ) × co(S ⊥ ) and a field b ← F. Prepare 1 p |P1 | · |S|

X

z·(e v

ω|F| ker

+w)

|z⟩A ,

s′ ∈S + z=s′ +vimg +u

for a uniformly random veker ← D1 := co((S + )⊥ ) ∩ S ⊥ . 3. Initialize Aλ with A, Z(S, T, u, w, b∥(m + R(vimg + u))[2 : k]). Aλ ’s output is parsed as a string ze ∈ Fn .
⊥ 4. If ze ̸∈ S ⊥ + w or ze ∈ S + + veker + w, then return I − M. Otherwise, return M. Hybd3 (m):

In this hybrid, instead of sample (vimg , u) directly, we sample a leakage ℓ and u.

1. Sample [S, T ] uniformly at random over Fn . If the subspaces [S, T ] are not successfully sampled, return M. 2. We have P1 = ker(R−1 |P ) with P = co(S) ∩ T . Define a subspace S + := span (S, P1 ). Sample a leakage ℓ ← Fk−1 and a field b ← F. Furthermore, sample vectors (u, w) ← co(T ) × co(S ⊥ ). Let vimg ∈ (P/P1 ) be the unique vector such that (m + R(vimg + u))[2 : k] = ℓ. Note that a successfully sampled [S, T ] implies the existence of vimg . Prepare 1 p |P1 | · |S|

X

z·(e v

ω|F| ker

s′ ∈S + z=s′ +vimg +u

for a uniformly random veker ← D1 := co((S + )⊥ ) ∩ S ⊥ . 45

+w)

|z⟩A ,

3. Initialize Aλ with A, Z(S, T, u, w, b∥ℓ). Aλ ’s output is parsed as a string ze ∈ Fn .
⊥ 4. If ze ̸∈ S ⊥ + w or ze ∈ S + + veker + w, then return I − M. Otherwise, return M. Hybe3 (m):

In this hybrid, Z(S, T, u, w, b∥ℓ) is replaced by a simulator S(G, T, u, x, b∥ℓ).

1. Sample [S, T ] uniformly at random over Fn . If the subspaces [S, T ] are not successfully sampled, return M. 2. We have P1 = ker(R−1 |P ) with P = co(S) ∩ T . Define a subspace S + := span (S, P1 ). Sample a leakage ℓ ← Fk−1 and a field b ← F. Furthermore, sample vectors (u, w) ← co(T ) × co(S ⊥ ). Let vimg ∈ (P/P1 ) be the unique vector such that (m + R(vimg + u))[2 : k] = ℓ. Prepare 1 p |P1 | · |S|

X

z·(e v

ω|F| ker

+w)

|z⟩A ,

s′ ∈S + z=s′ +vimg +u

for a uniformly random veker ← D1 := co((S + )⊥ ) ∩ S ⊥ . 3. Sample a subspace G uniformly at random such that S ⊥ ≤ G, and dim(G) = 3n 4 . Let x ∈ co(G) be ⊥ the unique coset such that S + w ⊂ G + x. 4. Initialize Aλ with A, S(G, T, u, x, b∥ℓ). Aλ ’s output is parsed as a string ze ∈ Fn .
⊥ 5. If ze ̸∈ S ⊥ + w or ze ∈ S + + veker + w, then return I − M. Otherwise, return M. h i h i Lemma 6.8. For all m ∈ Fk , Pr Hyba3 (m) = I − M ≥ Pr Hybb3 (m) = I − M − negl(λ). Proof. In Hybb3 , we apply the unitary U1 and measure the C register before sending the quantum state to the adversary. Since the adversary operates on different registers, the adversary’s operation commutes with the operation on C. Furthermore, by Proposition 4.4 and Definition 4.6, the hybrid output M in Step 1 with probability at most negl(λ). Lemma 6.9. For all m ∈ Fk , Hybb3 (m) = Hybc3 (m).

46

Proof. The following first term is the state at Step 2 in Hybb3 .

Apply U1

7−−−−−→ = =

X 1 p |vker ⟩ ⊗ |Svker +vimg +u,w ⟩ |P1 | v ∈P1 ker X 1 p (U1 |vker ⟩) ⊗ |Svker +vimg +u,w ⟩ |P1 | v ∈P1 ker X X 1 z·w p (U1 |vker ⟩) ⊗ ω|F| |z⟩ |P1 | · |S| v ∈P1 z∈S+v +vimg +u ker ker X 1 z·w p |z⟩ (U1 |vker ⟩) ⊗ ω|F| |P1 | · |S| s∈S vker ∈P1 z:=s+vker +vimg +u

=

X 1 p |P1 |2 · |S| ve ∈D ker

=

X 1 p |P1 |2 · |S| ve ∈D ker

Measure C

7−−−−−−→

1 p |P1 | · |S|

vker ·e vker z·w |e vker ⟩ ⊗ |z⟩ ω|F| · ω|F|

X 1

s∈S vker ∈P1 z:=s+vker +vimg +u z·(e v

X 1

ω|F| ker

+w)

|e vker ⟩C ⊗ |z⟩

s∈S vker ∈P1 z:=s+vker +vimg +u

X

z·(e v

ω|F| ker

+w)

|z⟩.

s′ ∈S + z:=s′ +vimg +u

The second equality follows from Proposition 4.8. Next, we show that the last equality holds, by showing that z · veker = vker · veker . Indeed, z · veker = (s + vker + vimg + u) · veker = vker · veker , where the second equality follows from the fact that veker ∈ co((S + )⊥ ) ∩ S ⊥ , s ∈ S, and vimg + u ∈ co(S + ). Finally, veker in the last term is uniformly sampled over D1 := co((S + )⊥ ) ∩ S ⊥ . It turns out that the final state is the state at Step 2 in Hybc3 . Lemma 6.10. For all m ∈ Fk , Hybc3 (m) = Hybd3 (m). Proof. Let P := T /S. A successfully sampled [S, T ] says that R(P ) = Fk . Let P1 := ker(R−1 |P ). We have that the linear map R−1 |(P/P1 ) : P/P1 → Fk−1 is a bijective. Hence, when m, u, ℓ are fixed, there exists a unique vector vimg ∈ (P/P1 ) such that (m + R(vimg + u))[2 : k] = ℓ. h i h i Lemma 6.11. For all m ∈ Fk , Pr Hybd3 (m) = I − M − Pr Hybe3 (m) = I − M ≤ negl(λ). h Proof. Suppose (by contradiction) that there exists a polynomial p(·) such that for infinite many λ, Pr Hybd3 = i h i 1 I − M < Pr Hybe3 = I − M − p(λ) . We obtain a contradiction from the subspace hiding property and from the fact that the experiment can be implemented within the class A . We will construct a reduction R that breaks the security of subspace-hiding. The goal of the reduction R is to simulate the experiments Hybd3 (m) and Hybe3 (m). The reduction proceeds as follows: 47

1. Receive S, T, u, w, b∥ℓ, ch from the challenger, where ch is either Zλ (S, T, u, w, b∥ℓ) or Sλ (G, T, u, x, b∥ℓ). 2. Extend the basis of T to a basis of Fn uniformly at random, which ensures that co(T ) and co(T ⊥ ) are well-defined. Furthermore, S + are defined by R, S, T . If R(T /S) ̸= Fk , the reduction returns b′ = 0; i.e., R guesses the challenge is Z(S, T, u, w, b∥ℓ). Otherwise, continue to Step 3. 3. Compute vimg ∈ (P/P1 ) subject to (m + R(vimg + u))[2 : k] = ℓ. Note that R(T /S) = Fk implies the existence of vimg . 4. Prepare the state 1 p |P1 | · |S|

X

z·(e v

ω|F| ker

+w)

|z⟩A ,

s′ ∈S + z=s′ +vimg +u

for a uniformly random veker ← D1 := co((S + )⊥ ) ∩ S ⊥ . 5. Run the remainder of experiment Hybd3 or Hybe3 (Step 4-5), except that in Step 4, Aλ ’s registers are initialized as A, ch. 6. In Step 5, if the experiment outputs M, R output b′ = 0, i.e., R guesses the challenge is Z(S, T, u, w, b∥ℓ). Otherwise, R outputs b′ = 1, i.e., R guesses the challenge is Sλ (G, T, u, x, b∥ℓ). All operations except the adversary can be implemented efficiently (This is why we say the predicate is efficiently checkable), and hence R ∈ A . If ch = Zλ (S, T, u, w, b∥ℓ), then R simulates Hybd3 and If ch = Sλ (G, T, u, x, b∥ℓ), then R simulates Hybe3 . Hence, R breaks the security of subspace-hiding with 1 advantage 2·p(λ) . Lemma 6.12. For all m ∈ Fk , Pr [Hybe3 (m) = I − M] = 1 − negl(λ). Proof. The entire view of the adversary is completely determined by the tuple (R, S + , vimg , u, veker + w, G, T, x, b∥(m + R(vimg + u))[2 : k]). Suppose (by contradiction) that Pr [Hybe3 (m) = M] ≥

1 . poly(λ)

Then, there exists an adversary Adv, given those variables, such that h  /  i Pr ze ∈ S ⊥ + w (S + )⊥ + veker + w : ze ← Adv ≥

1 , poly(λ)

(25)

where the probability is over the sampling process of Hybe3 . We will construct a new Adv′ such that h i  Pr ze ∈ S ⊥ (S + )⊥ : ze ← Adv′ ≥

1 , poly(λ)

where the probability is over the sampling process of Hybe3 . Adv′ is defined as follows: 1. Run ze ← Adv. 2. Return ze − veker − w.

48

(26)

Since veker ∈ S ⊥ , Equation (25) implies Equation (26). Next, we show that Equation (26) cannot occur except with negligible probability, which leads to a contradiction. The game defined in Equation (26) only depends on the sampling process of subspace G, S, S + , and T . We change the sampling order so that S is sampled conditioned on G, S + , and T . Under this sampling procedure, the conditional distribution of S is independent of the coset shifts determined by G, S + , and T . Therefore, the distribution of S is independent of the adversary’s view (vimg , u, veker + w, x). It is crucial to emphasize that the adversary’s view does not include veker , and this is precisely the hardness that we aim to capture. Furthermore, b∥(m + R(vimg + u))[2 : k] is independent of the sampling of S. For the rest of the proof, we can assume the adversary’s view is (R, S + , G, T ). We show that the statistical distance between the following distributions are negligible as long as dim(G⊥ ) ≥ k + Ω(λ): • DHybe3 : 1. Uniformly sample a subspace S subject to dim(S) = n2 . k 2. Uniformly sample a subspace T subject to S ≤ T , dim(T ) = 3n 4 , and R(T /S) = F .

3. Uniformly sample a subspace G subject to S ⊥ ≤ G and dim(G) = 3n 4 .
4. Define P1 := ker R−1 |(T /S) and S + := span (S, P1 ). 5. Return S + , G, T, S. • D1 : 1. Uniformly sample a subspace G⊥ subject to dim(G⊥ ) = n4 . 2. Uniformly sample a subspace S subject to G⊥ ≤ S and dim(S) = n2 . k 3. Uniformly sample a subspace T subject to S ≤ T , dim(T ) = 3n 4 , and R(T /S) = F .
4. Define P1 := ker R−1 |(T /S) and S + := span (S, P1 ).

5. Return S + , G, T, S. • D2 : 1. Uniformly sample a subspace G⊥ subject to dim(G⊥ ) = n4 and R(G⊥ ) = Fk . 2. Uniformly sample a subspace S subject to G⊥ ≤ S and dim(S) = n2 . k 3. Uniformly sample a subspace T subject to S ≤ T , dim(T ) = 3n 4 , and R(T /S) = F .
4. Define P1 := ker R−1 |(T /S) and S + := span (S, P1 ).

5. Return S + , G, T, S. • D3 : 1. Uniformly sample a subspace G⊥ subject to dim(G⊥ ) = n4 and R(G⊥ ) = Fk . 2. Uniformly sample a subspace S subject to G⊥ ≤ S and dim(S) = n2 . 3. Uniformly sample P subject to dim(P ) = n4 , R(P ) = Fk , and P ∩ S = {0}. 4. Define P1 := ker (R−1 |P ), S + := span (S, P1 ), and T := span (S, P ). 5. Return S + , G, T, S.

49

• D4 : 1. Uniformly sample a subspace G⊥ subject to dim(G⊥ ) = n4 and R(G⊥ ) = Fk . 2. Uniformly sample a subspace S subject to G⊥ ≤ S and dim(S) = n2 . 3. Uniformly sample P1 subject to R(P1 ) = span (e1 ), dim(P1 ) = n4 − k + 1, and P1 ∩ S = {0}. 4. Uniformly sample P subject to dim(P ) = n4 , ker R−1 |P = P1 , P ∩ S = {0}. 5. Define S + := span (S, P1 ) and T := span (S, P ). 6. Return S + , G, T, S. • D5 : 1. Uniformly sample a subspace G⊥ subject to dim(G⊥ ) = n4 and R(G⊥ ) = Fk . 2. Uniformly sample a subspace S subject to G⊥ ≤ S and dim(S) = n2 . 3. Uniformly sample P1 subject to R(P1 ) = span (e1 ), dim(P1 ) = n4 − k + 1, and P1 ∩ S = {0}. 4. Uniformly sample P subject to dim(P ) = n4 , ker R−1 |P = P1 , P ∩ S = {0}. 5. Define S + := span (S, P1 ) and T := span (S, P ). 6. Uniformly resample a subspace S ∗ subject to dim(S ∗ ) = n2 and G⊥ ≤ S ∗ ≤ S + . Rename S ∗ to S. 7. Return S + , G, T, S. • D6 : 1. Uniformly sample a subspace G⊥ subject to dim(G⊥ ) = n4 and R(G⊥ ) = Fk . 2. Uniformly sample a subspace S subject to G⊥ ≤ S and dim(S) = n2 . 3. Uniformly sample P1 subject to R(P1 ) = span (e1 ), dim(P1 ) = n4 − k + 1, and P1 ∩ S = {0}. 4. Uniformly sample P subject to dim(P ) = n4 , ker R−1 |P = P1 , P ∩ S = {0}. 5. Define S + := span (S, P1 ) and T := span (S, P ).
6. Uniformly resample a subspace (S ∗ )⊥ subject to dim (S ∗ )⊥ = n2 and (S + )⊥ ≤ (S ∗ )⊥ ≤ G. Rename S ∗ to S. 7. Return S + , G, T, S. Lemma 6.13. DHybe3 = D1 . Proof. By definition, S ⊥ ≤ G if and only if G⊥ ≤ S. Both distributions are identical as follows: Uniformly 3n sample S, T , and G with dimensions n2 , 3n 4 , and 4 , respectively. Resample if the following constraint do not ⊥ k holds: (i) G ≤ S ≤ T and (ii) R(T /S) = F . Lemma 6.14. If n4 ≥ k + Ω(λ), then ∆(D1 , D2 ) = negl(λ). Proof. If G⊥ is an n4 -dimensional subspace sampled uniformly at random, then R(G⊥ ) = Fk holds with overwhelming probability, whenever n4 ≥ k + Ω(λ) (see Definition 4.6). Lemma 6.15. D2 = D3 .

50

Proof. When sampling a subspace T subject to S ≤ T , we actually mean sampling linearly independent vectors {z n2 +1 , . . . , z 3n } such that their span’s intersection with S is {0} (see Definition 4.6). Hence, the two 4 distributions are identical. Lemma 6.16. D3 = D4 . Proof. Let us consider D3 . For each P , satisfying the constraint in Step 3, there exists a unique P1 defined in Step 4. We say (P, P1 ) is valid in D3 (resp. D4 ) if, given S, (P, P1 ) satisfy the constraint in Step 3 and 4 in D3 (resp. D4 ). We know that (P, P1 ) is a valid pair in D3 if and only if it is a valid pair in D4 . Indeed, this follows from the fundamental theorem of linear maps. Therefore, given S, it is sufficient to show that for each P1 , the number of choices for P such that (P, P1 ) is valid is the same (i.e., independent of P1 ). First, we define a sequence of y1 , . . . , yk−1 . For each i ∈ [k − 1], uniformly choose yi such that ( yi ̸∈ S ⊕ span (P1 , y1 , . . . , yi−1 ) R(yi ) ̸∈ span (e1 , R(y1 ), . . . , R(yi−1 )) The first constraint is well-defined as S + P1 is a direct sum. Let β and γ be a basis of S and P1 , respectively. The first constraint holds if and only if β ∪ γ ∪ {y1 , . . . , yk−1 } are linearly independent. The second constraint holds if and only if R(span (P1 , y1 , . . . , yk−1 )) = Fk . Let P = span (P1 , y1 , . . . , yk−1 ). Two constraints hold if and only if (P, P1 ) is valid. Next, we know that ( 3n dim S ⊕ span  (P1 , y1 , . . . , yi−1 ) = 4 − k+ i dim R−1 span (e1 , R(y1 ), . . . , R(yi−1 )) = n − k + i Besides, condition on the event that R(S) = Fk , the dimension of     S ⊕ span (P1 , y1 , . . . , yi−1 ) ∩ R−1 span (e1 , R(y1 ), . . . , R(yi−1 )) is 3n 4 − 2k + 2i. Hence, the number of valid yi is equal to 3n

3n

|F|n − |F| 4 −k+i − |F|n−k+i + |F| 4 −2k+2i . Therefore, the number of valid order tuples of (y1 , . . . , yk−1 ) is the same (i.e., independent of P1 ). Next, we need to show that for each valid (P, P1 ), the number of valid ordered tuples (y1 , . . . , yk−1 ) such that P = span (P1 , y1 , . . . , yk−1 ) is the same. Indeed, the only constraint of yi are ( yi ∈ P yi ̸∈ span (P1 , y1 , . . . , yi−1 ) , where the number of valid yi only depends on the dimension of P1 and P . We conclude that two distributions are identical when R(S) = Fk , which happens when R(G⊥ ) = Fk . Lemma 6.17. D4 = D5 . Proof. It is sufficient to show that, in D4 , given any valid pair (S + , G, T ), every subspace S satisfying G⊥ ≤ S ≤ S + occurs with the same probability. This condition holds provided that, given a valid (S + , G, T ), 51

1. Each valid S has the same number of P1 such that (S, P1 ) is valid. 2. Each valid pair (S, P1 ) has the same number of P such that (S, P1 , P ) is valid. 3. Each valid pair (S, P1 , P ) occurs with same probability. Here, S is called valid if G⊥ ≤ S ≤ S + ; (S, P1 ) is called valid if S is valid, R(P1 ) = span (e1 ), P1 ∩ S = {0}, and S + = span (S, P1 ). Note that dim(P1 ) = n4 − k + 1 holds directly if (S, P1 ) is valid; (S, P1 , P ) is called valid if S is valid, (S, P1 ) is valid, dim(P ) = n4 , ker R−1 |P = P1 , P ∩ S = {0}, and T = span (S, P ). We first prove the first item. Let us define some notation. We call the tuple (y1 , . . . , y n4 −k+1 ) ∈ n

Fn×( 4 −k+1) semi-valid, if it spans a P1 such that P1 ≤ ker R−1 , P1 ∩ S = {0}, and S + = span (S, P1 ); we call the tuple semi-invalid, if it spans a P1 such that P1 ≤ ker R, P1 ∩ S = {0}, and S + = span (S, P1 ). It is clear that if a tuple is semi-valid but not semi-invalid, then it is valid. We will prove the statement by the following strategy: (i) For each valid (S + , G, S), the number of semi-valid tuples is the same. (ii) For each valid (S + , G, S), the number of semi-invalid tuples is the same. (iii) For each valid P1 , the number of valid tuples, that span P1 , is the same. Now, we prove (i). For each i ∈ [ n4 − k + 1], we can only choose yi subject to
/ (span (S, y1 , . . . , yi−1 ) ∩ ker R−1 ) . yi ∈ S + ∩ ker R−1
k−1 implies R−1 (S + ) = Fk−1 implies that dim S + ∩ ker R−1 = 3n 4 − 2k + 2. Similarly, R−1 (S) = F n that dim (S ∩ ker R−1 ) = 2 − k + 1. Furthermore, dim (span (S, y1 , . . . , yi−1 ) ∩ ker R−1 ) = n2 − k + i. Hence, the number of choice of yi is n

3n

|F| 4 −2k+2 − |F| 2 −k+i , which is independent of the choice of (S + , G, S). (ii) is similar to (i) and hence we omit its proof. Next, we prove (iii). The number of choices of the tuple depends only on the dimension of P1 , which is n −k 4

Y

 n |F| 4 −k+1 − |F|i .

i=0

We conclude the proof: given any valid tuple (S + , G, S), the number of valid P1 is (i) − (ii) > 0. (iii) Next, the second term is trivial. As we only need to sample y 3n −k+2 , . . . , y 3n such that 4

4

 +   span ({yi }) ∩ S
= {0} span {yi }, S + = T   span (R({yi })) = span (e2 , . . . , ek ) . It is clear that the number of choice of ys is independent of (S, P1 ). Finally, the third item follows from the sampling process of D4 .

52

Lemma 6.18. D5 = D6 . Proof. Fix G⊥ and S + (or equivalently, fix G and (S + )⊥ ). It is clear that S satisfies G⊥ ≤ S ≤ S + if and only if S ⊥ satisfies (S + )⊥ ≤ S ⊥ ≤ G. Therefore, D5 = D6 . We conclude that (where Adv′ has the information about S + , G, and T ) h i  Pr ze ∈ S ⊥ (S + )⊥ : ze ← Adv′ DHybe

3

h i  Pr ze ∈ S ⊥ (S + )⊥ : ze ← Adv′ + negl(λ) D6 h i  ≤ max Pr ze ∈ S ⊥ (S + )⊥ + negl(λ) ze∈G\(S + )⊥ S ⊥ : (S + )⊥ <S ⊥ <G ⊥

+ ⊥

|F|dim(S )−dim((S ) ) − 1 + negl(λ) = |F|dim(G)−dim((S + )⊥ ) − 1 n n |F|( 2 )−( 4 +k−1) − 1 ≤ + negl(λ) n 3n |F|( 4 )−( 4 +k−1) − 1 n

|F| 4 −k+1 − 1 + negl(λ) n |F| 2 −k+1 − 1 = negl′ (λ),

=

when n4 > Ω(λ).

6.2

Applications of Subspace Coset State Constructions

[BGK+ 24] propose a unified approach for upgrading beyond “all-or-nothing”-type cryptographic primitives to support certified deletion. We first present their main theorem with minor modifications to align with our format. Theorem 6.19 ([BGK+ 24], Definition 6.1 and Theorem 6.5). Let λ be the security parameter. Fixed n ∈ N. Let R ∈ F1×n be the all-ones matrix, m ∈ F2 be a single bit message, and {Z 2 n o λ (·)}λ∈N be a quantum λ operation with classical input. Define the following distribution EXPA λ (m)

obtaining by running Aλ as follows.

λ∈N

over quantum states,

1. Sample [S, T ] uniformly at random over Fn2 (Definition 4.6 and ignore the subspace S + ). Next, sample (v, w) ← co(S) × co(S ⊥ ), uniformly at random. Let u ∈ co(T ) be the unique coset such that S + v ⊂ T + u. Initialize Aλ with |Sv,w ⟩, Zλ (S, T, u, w, m + Rv). 2. Aλ ’s output is parsed as a string ze ∈ Fn2 and a residual state ρ. If ze ∈ S ⊥ + w, then output ρ, and otherwise output a special symbol ⊥.

53

Let A be a class of adversaries that contains QPT algorithm. If {Zλ }λ∈N is subspace-hiding for A (Definition 6.1), then for all {Aλ }λ∈N ∈ A and for all m ∈ {0, 1},   Aλ λ TD EXPA (0), EXP (1) = negl(λ). λ λ They use Theorem 6.19 as a black box to upgrade various cryptographic schemes to support certified deletion, including blind delegation, secure software leasing, functional encryption, differing-inputs iO, and CCA-PKE. Suppose the underlying message is a string; they encrypt the message bitwise. For example, if m ∈ {0, 1}k with some k ∈ N, the construction is as follows: (i) For each i ∈ [k], do the following. Sample [Si , Ti ] uniformly at random over Fn2 , with n = λ; Sample (vi , wi ), ← co(Si ) × co(Si⊥ ) uniformly at random; Let ui ∈ co(Ti ) be the unique coset such that Si + vi ⊂ Ti + ui . (ii) Construct n o n o |(Si )vi ,wi ⟩ , Zλ (Si , Ti , ui , wi , m[i] + Rvi ) . i∈[k]

i∈[k]

To upgrade cryptographic schemes to support constant-rate certified deletion, we only need to invoke the construction and theorem in Theorem 6.2. The proof follows that of [BGK+ 24], except that Theorem 6.19 is replaced by our constant-rate version, Theorem 6.2. We explicitly describe our construction as follows: Let m ∈ Fk with some k ∈ N, the construction is as follows: (i) Sample [S, T ] uniformly at random over Fn , with n = λ + 4k. Next, sample (v, w) ← co(S) × co(S ⊥ ), uniformly at random. Let u ∈ co(T ) be the unique coset such that S + v ⊂ T + u. (ii) Construct |Sv,w ⟩, Zλ (S, T, u, w, m + Rv).

7

Publicly Verifiable Certified Deletion

In this section, we establish publicly verifiable versions of our constant-rate certified deletion theorems for BB84 (Theorem 5.2) and subspace coset states (Theorem 6.2). Under the hardness of SIS, we incorporate public verifiability via constrained signatures [Tsa17] (a.k.a., attribute-based signatures [MPR11]) while preserving constant rate. Existing approaches to publicly verifiable deletion either incur a linear loss [Por22, BKP23, BKM+ 23, KNY23, KS25] in rate or rely on strong assumptions [BGK+ 24] such as indistinguishability obfuscation. In contrast, our construction achieves constant-rate publicly verifiable certified deletion under the standard SIS assumption. We start by recalling the definition of constrained signatures. Definition 7.1 (Constrained Signatures). A constrained signature scheme (CS) with message space M and constraint class F = {f : M → {0, 1}} is a tuple of four algorithms (Setup, Constrain, Sign, Vrfy) defined as follows. • Setup(1λ ) → (vk, msk): The setup algorithm is a PPT algorithm that takes as input the security parameter 1λ and outputs a master signing key msk and a verification key vk. • Constrain(msk, f ) → sigkf : The constrain algorithm is a PPT algorithm that takes as input the master signing key msk and a constraint f ∈ F, and outputs a constrained signing key sigkf . • Sign(sigkf , m) → σ: The signing algorithm is a PPT algorithm that takes as input a constrained signing key sigkf and a message m ∈ M, and outputs a signature σ. We write Sign(sigkf , m; r) when its random tape is fixed to r. • Vrfy(vk, m, σ) → ⊤/⊥: The verification algorithm is a deterministic polynomial-time algorithm that takes as input a verification key vk, a message m ∈ M, and a signature σ, and outputs ⊤ or ⊥. 54

Correctness.

For any m ∈ M and f ∈ F such that f (m) = 1, we have   (vk, msk) ← Setup(1λ ) Pr Vrfy(vk, m, σ) = ⊤ : sigkf ← Constrain(msk, f )  ≥ 1 − negl(λ). σ ← Sign(sigkf , m)

Definition 7.2 (Function privacy). For any m ∈ M and f0 , f1 ∈ F such that f0 (m) = f1 (m) = 1, where (vk, msk) ∈ Setup(1λ ),

sigkf0 ∈ Constrain(msk, f0 ),

sigkf1 ∈ Constrain(msk, f1 ),

we require that the following distributions are statistically indistinguishable: σ0 ← Sign(sigkf0 , m)

≈s

σ1 ← Sign(sigkf1 , m).

Definition 7.3 (Selective single-key security). We say that a constrained signature scheme satisfies selective single-key security if for any stateful QPT adversary A, we have   f ← A(1λ )   (vk, msk) ← Setup(1λ )  ≤ negl(λ). Pr  Vrfy(vk, m, σ) = ⊤ ∧ f (m) = 0 :  sigkf ← Constrain(msk, f )  (m, σ) ← A(vk, sigkf ) Theorem 7.4 (Adapted from [KMY25, KLYY25]). Assuming the SIS assumption with a subexponential modulus-to-target-norm-bound ratio, there exists a constrained signature scheme that achieves selective single-key security (Definition 7.3) and function privacy (Definition 7.2), and supports constraint classes represented by Boolean circuits of fixed but arbitrary input length ℓ and depth d. Under the SIS assumption with a polynomial modulus, we obtain a scheme with the same security guarantees, where the supported function class consists of circuits of depth O(log(λ)), i.e., the NC1 circuit class.5 In both cases, the size of the public parameters is |vk| = poly(λ, ℓ, d),

|skf | = poly(λ, ℓ, d),

|σ| = poly(λ, d).

Here, we introduce a new security definition for a classical deterministic signature that we call one-time unforgeability for subset states. We then show that such a signature scheme can be constructed from constrained signatures. Definition 7.5 (One-time unforgeability for subset states). Let Sig = (Gen, Sign, Vrfy) be a classical deterministic signature scheme, λ be the security parameter, M be the message space. We also consider a class T of a pair of a subsets of the message space and coefficients. Namely, for each (T, α) ∈ T , we have T ⊆ M and α = {αm ∈ C}m∈T . For (T, α) ∈ T , we require the following. • There is an efficient and canonical representation of each (T, α) ∈ T . The description size of (T, α) should be poly(λ, log |M|). We will slightly abuse the notation and identify the set T with its description. 5 NC1 circuits can be represented by polynomial-length constant-width branching programs via Barrington’s theorem. Thus, for this special case, we may replace the generic circuit-evaluation procedure used in the construction with the branching-program evaluation algorithm of [GV15], which incurs only polynomial norm growth. Consequently, the relevant lattice parameters can be chosen polynomially bounded, yielding an instantiation with polynomial modulus.

55

P • For each (T, α) ∈ T , we have m∈T |αm |2 = 1. Furthermore, given the description of (T, α), one can efficiently generate the state X αm |m⟩. m∈T

• For each (T, α) ∈ T , there is an efficient circuit fT that takes as input m ∈ M and outputs 1 if m ∈ T and 0 otherwise. The size of fT is poly(λ, log |M|). We define the experiment EXP(1λ ) between an adversary and the challenger as follows. 1. The adversary A sends (T, α) ∈ T to the challenger. 2. The challenger runs (vk, sigk) ← Gen(1λ ). The challenger generates a quantum state |ψ⟩ by applying the map |m⟩|0 · · · 0⟩ 7→ |m⟩|Sign(sigk, m)⟩ to the state X

αm |m⟩|0 · · · 0⟩.

m∈T

The challenger sends (vk, |ψ⟩) to A. 3. The adversary A outputs a pair of messages and signature (m′ , σ ′ ) to the challenger. 4. The experiment outputs 1 if m′ ̸∈ T and Vrfy(vk, m′ , σ ′ ) = 1. Otherwise, outputs 0. We say Sig is one-time unforgeable for subset states with respect to T if, for any QPT adversary A, it holds that Pr[EXP(1λ ) = 1] = negl(λ). Construction: We construct a classical deterministic signature scheme Sig = (Gen, Sign, Vrfy) satisfying one-time unforgeability for subset states with respect to T , using a constrained signature CS.Sig = (CS.Setup, CS.Constrain, CS.Sign, CS.Vrfy) that supports a function class of F := {fT }T ∈T with message space M and randomness from R. Let H be a family of 4-wise independent hash functions with domain M and range R. • Gen(1λ ): – Run (CS.vk, CS.msk) ← CS.Setup(1λ ). – Let f=1 be a constant function that always outputs 1. Run CS.sigkf=1 ← CS.Constrain(CS.msk, f=1 ). $

– Sample a random hash h from a family of 4-wise independent functions h ← H. – Output the verification key vk = CS.vk and the signing key sigk = (h, CS.sigkf=1 ). • Sign(sigk, m): Parse the input as sigk = (h, CS.sigkf=1 ) and proceed as follows. – Run CS.σ ← CS.Sign(CS.sigkf=1 , m; h(m)), where h(m) is used as the randomness for signing. – Output σ = CS.σ. • Vrfy(vk, m, σ): Parse the input as vk = CS.vk and σ = CS.σ and proceed as follows. 56

– Output CS.Vrfy(CS.vk, m, CS.σ). The correctness of Sig follows from that of CS.Sig. Furthermore, its signing algorithm is deterministic. We prove the unforgeability theorem below. Theorem 7.6. Let CS.Sig be a constrained signature scheme with selective single-key security (Definition 7.3) and function privacy (Definition 7.2), then Sig is one-time unforgeable for subset states with respect to T (Definition 7.5). Proof. To prove the theorem, we define a sequence of hybrid distributions, corresponding to a fixed adversary A. The proof proceeds by showing that the winning probabilities of A in Hyb0 and Hyb3 differ only negligibly, and that the winning probability in Hyb3 is negligible. • Hyb0 : This is the distribution EXP(1λ ) described above. Recall that the output of the hybrid is 1 if and only if the adversary outputs m′ and CS.σ ′ such that m′ ̸∈ T and CS.Vrfy(CS.vk, m′ , CS.σ ′ ) = ⊤. • Hyb1 : This is the same as Hyb0 except that h(m) is replaced with a truly random function H(m). • Hyb2 : This is the same as Hyb1 except that at Step 2 in the experiment the challenger does the following. It defines fT such that fT (m) = 1 if and only if m ∈ T . It then runs (CS.vk, CS.msk) ← CS.Setup(1λ ) and CS.sigkfT ← CS.Constrain(CS.msk, fT ). It then generates a quantum state |ψ⟩ by applying the map |m⟩|0 · · · 0⟩ 7→ |m⟩|CS.Sign(CS.sigkfT , m; H(m))⟩ to the state X

αm |m⟩|0 · · · 0⟩.

m∈T

It finally sends (vk = CS.vk, |ψ⟩) to A. • Hyb3 : This is the same as Hyb2 except that H(m) is replaced with a 4-wise independent hash function h(m), where h ← H. First, we show that Pr[Hyb0 = 1] = Pr[Hyb1 = 1]. By a similar argument, Pr[Hyb2 = 1] = Pr[Hyb3 = 1] follows. Let O be either a 4-wise independent hash function h ← H or a truly random function H. Consider a quantum oracle algorithm that simulates hybrid Hyb0 and Hyb1 , where the oracle is set to either h(·) or H(·). The quantum oracle algorithm queries the oracle twice. Indeed, at Step 2, the algorithm works as follows: X

Query O

αm |m⟩|0 · · · 0⟩ 7−−−−−→

m∈T

X

αm |m⟩|0 · · · 0⟩|O(m)⟩

m∈T Run CS.Sign

7−−−−−−−→

X

αm |m⟩|CS.Sign(CS.sigkf , m; O(m))⟩|O(m)⟩

m∈T Query O

7−−−−−→

X

αm |m⟩|CS.Sign(CS.sigkf , m; O(m))⟩.

m∈T

Hence, Lemma 3.11 implies that Pr[Hyb0 = 1] = Pr[Hyb1 = 1]. Next, we show that |Pr[Hyb1 = 1] − Pr[Hyb2 = 1]| = negl(λ). Let |ψ1 ⟩ and |ψ2 ⟩ be the states sent to the adversary at Step 2 in Hyb1 and Hyb2 , respectively. By the function privacy (Definition 7.2) of

57

constrained signature, for any honestly generated vk, msk, CS.sigkf=1 , CS.sigkfT and any m ∈ T , the following distributions are negligibly close: $

$

CS.σm ← CS.Sign(CS.sigkf=1 , m) ≈s CS.σT,m ← CS.Sign(CS.sigkfT , m) Let O(·) and O′ (·) be the oracles that output CS.σm and CS.σT,m on input m, respectively. Here, each of CS.σm and CS.σT,m is distributed as above. P We can view |ψ1 ⟩ (resp., |ψ2 ⟩) as an answer ′ from the oracle O (resp., O ) to the single query m∈T αm |m⟩|0 . . . 0⟩. Lemma 3.12 implies that |ψ1 ⟩ and |ψ2 ⟩ are indistinguishable conditioned on fixed vk, msk, CS.sigkf=1 , CS.sigkfT . Therefore, the indistinguishability holds when averaging over vk, msk, CS.sigkf=1 , CS.sigkfT . Since Hybi ’s output is determined by (vk, T, A, |ψi ⟩) for i ∈ {1, 2}, it holds that |Pr[Hyb1 = 1] − Pr[Hyb2 = 1]| = negl(λ). From the discussion so far, we have | Pr[Hyb0 = 1] − Pr[Hyb3 = 1]| = negl(λ). Finally, it is sufficient to show that Pr[Hyb3 = 1] = negl(λ). Suppose (by contradiction) that Pr[Hyb3 = 1] is non-negligible. We then construct a QPT reduction B that breaks the selective single-key security (Definition 7.3) of the constrained signature scheme. The reduction B interacting with the adversary A in Hyb3 proceeds as follows: 1. A sends (T, α) ∈ T to B. B then submits fT to its challenger. 2. B is then given the verification key CS.vk and the signing key CS.sigkfT from its challenger, where CS.sigkfT ← CS.Constrain(msk, fT ). 3. B samples h ← H. It then computes a quantum state |ψ⟩ by applying the map |m⟩|0 · · · 0⟩ 7→ |m⟩|CS.Sign(CS.sigkfT , m; h(m))⟩ P to the state m∈T αm |m⟩|0 · · · 0⟩, which can be efficiently generated from the description of (T, α). It then sends (CS.vk, |ψ⟩) to A. 4. A outputs a pair of message and signature m′ and CS.σ ′ to B. B then outputs (m′ , σ ′ := CS.σ ′ ). Since the reduction simulates the experiment Hyb3 perfectly, its probability of breaking selective single-key security is equal to Pr[Hyb3 = 1], which is non-negligible, yielding a contradiction. Here, we discuss the instantiations. We are interested in the following two cases. Instantiation for the BB84 states To capture the case of BB84 states, we instantiate the message space M and T in Definition 7.5 with MBB := F2n and TBB defined as follows: −⟨x⊙θ̄,m⟩

TBB := {(T

x,θ

,α

x,θ

)}x∈F2n ,θ∈{0,1}2n ,

T

x,θ

2n

:= { m ∈ F

| m[i] = x[i] for all i ∈ θ1 },

x,θ αm :=

h(θ)=n

ω|F| p , |F|n

where ⊙ denotes the component-wise product over F2n , θ̄ denotes θ with all the bits flipped, and h(θ) is the Hamming weight of the string θ. We can check that each (T x,θ , αx,θ ) has efficient description by x and θ, the generation of the state −⟨x⊙θ̄,m⟩

X m∈T x,θ

x,θ αm |m⟩ =

X ω|F| p |m⟩ = QFT−θ̄ |x⟩ = (QFT−1 )⊗2n QFTθ |x⟩ n |F| m∈T x,θ 58

is possible efficiently,6 and the membership checking of T x,θ is efficient. It is easy to see that the circuit computing fT x,θ can be implemented in NC1 : We check whether mi = xi or not in parallel, which leads to the depth of O(log n + log |F|) = O(log λ). Therefore, by Theorem 7.4, the constrained signature supporting {fT x,θ }x,θ can be instantiated assuming the SIS assumption with polynomial modulus. By Theorem 7.6, we obtain a classical deterministic signature scheme satisfying one-time unforgeability for subset states with respect to TBB assuming the same assumption. By Theorem 7.4 and from the fact that the depth of fT is O(log λ), the size of the signature is fixed polynomial |σ| = poly(λ).7 Instantiation for the coset states To capture the case of coset states, we instantiate the message space M and T in Definition 7.5 with MCoS := Fn and TCoS defined as follows: ⟨m,w⟩

TCoS := {(T

v,w,S

,α

v,w,S

)}v,w∈Fn ,S≤Fn ,

T

v,w,S

:= S + v,

v,w,S αm :=

ω|F| p , |S|

where recall that S ≤ Fn means that S is a subspace of Fn . We can check that each (T v,w,S , αv,w,S ) has by v, w, and S, where S is represented by the basis of the subspace, the state P efficient description v,w,S α |m⟩ = |Sv,w ⟩ can be efficiently generated (Proposition 4.7), and the membership checking m∈T v,w,S m v,w,S of T is efficient. One can also see that the circuit computing fT v,w,S can be implemented in NC1 . To check whether m ∈ S + v, it suffices to test whether m − v ∈ S. This can be done by taking inner products between m − v and all basis vectors of S ⊥ and checking whether all of them evaluate to 0. Since inner products over F can be computed in NC1 , this membership test—and hence the computation of fT v,w,S —can be carried out in NC1 . Therefore, by Theorem 7.4, the constrained signature supporting {fT v,w,S }v,w,S can be instantiated assuming the SIS assumption with polynomial modulus. By Theorem 7.6, we obtain a classical deterministic signature scheme satisfying one-time unforgeability for subset states with respect to TCoS assuming the same assumption. By Theorem 7.4 and from the fact that the depth of fT is O(log λ), the size of the signature is fixed polynomial |σ| = poly(λ). The following theorem is our main result of this section. Theorem 7.7 (Constant-Rate Publicly Verifiable Certified Deletion for BB84 States). Let Sig = (Gen, Sign, Vrfy) be a one-time unforgeable signature scheme for subset states (Definition 7.5) with respect to TBB . Let λ ∈ N be the security parameter. Fix k, n ∈ N such that 3k + Θ(λ) ≤ 2n. Consider a family of finite prime fields {Fλ }λ∈N with polynomial bounded field sizes. Let R ∈ Fk×n be a matrix λ   n−k that is both MDS and efficiently decodable with error 2 (Definition 3.1). Let m ∈ Fkλ be a classical message and Z n o = {Zλ (·)}λ∈N be a quantum operation with classical input. Define the following distribution Aλ EXPλ (m) over quantum states, obtained by running Aλ as follows. λ∈N

2n k λ 1. Sample x ← F2n λ , a balanced θ ← {0, 1} , and r ← Fλ . Run (vk, sigk) ← Gen(1 ). Generate −1 ⊗2n a quantum state |ψ⟩ by applying a map |x⟩|0 · · · 0⟩ 7→ |x⟩|Sign(sigk, x)⟩ to (QFT ) QFTθ |x⟩. Initialize Aλ with |ψ⟩, m + Rxθ0 + r, vk, Zλ (θ, r, sigk). 6

If we were to use the standard BB84 encoding, the roles of the standard basis and the QFT basis would be reversed in our application. To keep the roles of the bases consistent with our main theorem—namely, using the standard basis for extracting a random pad and the QFT basis for deletion—we instead slightly modify the definition of the quantum state specified by (x, θ). 7 The size of the signature has polylogarithmic dependence on n. However, since we can bound poly(log n) by a fixed polynomial in λ (say, λ) for polynomially bounded n, we ignore this dependency.

59

′ ′ ′ 2. Aλ ’s output is parsed as a string x′ ∈ F2n λ and σ and a residual state ρ. If Vrfy(vk, x , σ ) = 1, then output ρ, and otherwise output a special symbol ⊥.

If Z is semantically-secure against any non-uniform QPT {Aλ }λ∈N (Definition 5.1), then for all non-uniform QPT {Aλ }λ∈N and for all m ∈ Fkλ ,   Aλ k λ TD EXPA λ (m), EXPλ (0 ) = negl(λ). Proof. We define the event Forge as Vrfy(vk, x′ , σ ′ ) = 1 but x′i ̸= xi for some i ∈ θ1 .
We define another event Forge∗ which is identical to Forge except that Aλ is initialized with Zλ θ, r, 0|sigk| . Because Sig is a one-time unforgeable signature scheme for subset states with respect to TBB , Pr[Forge∗ ] = negl(λ). Since Zλ is semantically secure, we have Pr[Forge] ≤ Pr[Forge∗ ] + negl(λ). Therefore, Pr[Forge] = negl(λ). d Aλ (m), which is identical to EXPAλ (m) except that it outputs ρ only We define another experiment EXP λ

λ

if Vrfy(vk, x′ , σ ′ ) = 1 ∧ x′i = xi for all i ∈ θ1 . Then,     d Aλ (m), EXP d Aλ (0k ) + negl(λ) = negl(λ). TD EXPAλ (m), EXPAλ (0k ) ≤ TD EXP λ

λ

λ

λ

The first inequality follows because Pr[Forge] = negl(λ). The last one holds by our main constant-rate certified deletion theorem Theorem 5.2. We construct a QPT adversary Bλ in the BB84 certified-deletion experiment in Theorem 5.2. Define a quantum operation Ze = {Zeλ }λ∈N as follows: on input (θ, r), 1. Run (vk, sigk) ← Gen(1λ ). 2. Output (vk, sigk, Zλ (θ, r, sigk)). Notice that Ze is semantically-secure as required in Theorem 5.2. Indeed, by the semantic security of Z, e r) = (vk, sigk, Zλ (θ, r, sigk)) ≈c (vk, sigk, Zλ (0, 0, sigk)) = Z(0, e 0). Z(θ, We construct Bλ as follows: 1. Receive QFTθ |x⟩, m + Rxθ0 + r, Zeλ (θ, r) from the challenger. 2. Compute |ψ⟩ by first applying (QFT−1 )⊗2n and then |x⟩|0 · · · 0⟩ 7→ |x⟩|Sign(sigk, x)⟩ to QFTθ |x⟩. 3. Send |ψ⟩, m + Rxθ0 + r, vk, Zλ (θ, r, sigk) to A. ′ 4. Receive x′ ∈ F2n λ and σ and a residual state ρ from A.

5. Check if Vrfy(vk, x′ , σ ′ ) = 1, then send x′ and ρ to the challenger. Otherwise, send x′ and ⊥ to the challenger. Since the challenger additionally checks whether x′i = xi for every i ∈ θ1 , the above simulation is d Aλ (m). Therefore, EXP d Aλ (m) ≡ EXPBλ (m), where the latter is the experiment of exactly the same as EXP λ λ λ e Hence, Theorem 5.2 instantiated with Z.   d Aλ (m), EXP d Aλ (0k ) = negl(λ) TD EXP λ λ by Theorem 5.2. 60

Discussion on the Rate By Theorem 7.7, we can add publicly verifiable deletion to various primitives. Compared to the case without the public verifiability (Theorem 5.2), we only have to add a quantum register that contains a signature Sign(sigk, x) coherently. The length of the signature can be bounded by a fixed polynomial poly(λ) using the instantiation from SIS, which does not depend on the message length k. Therefore, the above theorem does not decrease the rate at all, in asymptotic sense. Discussion on the Applications Our formulation of Theorem 7.7 follows that of [KNY23] and can be used for the same applications. In more detail, we can add PVD to various primitives, while achieving constant rate. Let us sketch how to use the theorem by taking PKE as an example. |ψ⟩, m + Rxθ0 + r, vk, Zλ (θ, r, sigk) constitutes the ciphertext of a PKE with PVD, while Zλ is an encryption algorithm of the underlying PKE (without PVD). The deletion certificate is obtained by measuring |ψ⟩ in the standard basis to obtain the deletion certificate (x′ , σ ′ ), which can be publicly verified using vk. The decryption requires a bit of work, due to the added signature: We first decrypt the ciphertext to recover sigk, r, θ. Then, we uncompute the signature register from |ψ⟩ and measure it in QFT basis on position specified by θ. Then, the message is obtained by unmasking. Theorem 7.8. Assume that there exists Z ∈ {SKE, COM, PKE, ABE, QFHE, TRE, WE} with quantum encryption and decryption (or committing) algorithms and the SIS assumption with polynomial modulus. Then there exists a constant-rate Z with publicly verifiable deletion. We also obtain an analog of Theorem 7.7 for coset states. Theorem 7.9 (Constant-Rate Publicly Verifiable Certified Deletion for Subspace Coset States). Let Sig = (Gen, Sign, Vrfy) be a one-time unforgeable signature scheme for subset states with respect to TCoS . Let λ be the security parameter. Fix k, n ∈ N such that 4k + Θ(λ) ≤ n. Consider a family of finite prime fields {Fλ }λ∈N with polynomial bounded field sizes. Let R ∈ Fk×n be a full rank matrix. Let m ∈ Fkλ be λ a classical message and o {Zλ (·)}λ∈N be a quantum operation with classical input. Define the following n Aλ distribution EXPλ (m) over quantum states, obtained by running Aλ as follows. λ∈N

1. Sample [S, T ] uniformly at random over Fnλ (Definition 4.6). Next, sample (v, w) ← co(S) × co(S ⊥ ), uniformly at random. Let u ∈ co(T ) be the unique coset such that S + v ⊂ T + u. Run (vk, sigk) ← Gen(1λ ). Generate a quantum state |ψ⟩ by applying a map |x⟩|0 · · · 0⟩ 7→ ⊥ |x⟩|Sign(sigk, x)⟩ to |Sw,−v ⟩. Initialize Aλ with |ψ⟩, m + Rv, T, u, vk, Zλ (sigk, S). 2. Aλ ’s output is parsed as a string (x′ ∈ Fnλ , σ ′ ) and a residual state ρ. If Vrfy(vk, x′ , σ ′ ) = 1, then output ρ, and otherwise output a special symbol ⊥. If {Zλ }λ∈N is semantically-secure 8 against any non-uniform QPT {Aλ }λ∈N , then for all non-uniform QPT {Aλ }λ∈N and for all m ∈ Fkλ ,   Aλ k λ TD EXPA (m), EXP (0 ) = negl(λ). λ λ 8

We only need semantic security here and no longer need subspace-hiding.

61

Proof. We define the event Forge as Vrfy(vk, x′ , σ ′ ) = 1 but x′ ∈ / S ⊥ + w. We define another event Forge∗
which is identical to Forge except that Aλ is initialized with Zλ 0|sigk| , S . Because Sig is a one-time unforgeable signature scheme for subset states with respect to TCoS , Pr[Forge∗ ] = negl(λ). Since Zλ is semantically secure, we have Pr[Forge] ≤ Pr[Forge∗ ] + negl(λ). Therefore, Pr[Forge] = negl(λ). d Aλ (m), which is identical to EXPAλ (m) except that it outputs ρ only We define another experiment EXP λ

λ

if Vrfy(vk, x′ , σ ′ ) = 1 ∧ x′ ∈ S ⊥ + w. Then,     Aλ k λ d Aλ (m), EXP d Aλ (0k ) + negl(λ) = negl(λ). TD EXPA (m), EXP (0 ) ≤ TD EXP λ λ λ λ

The first inequality follows because Pr[Forge] = negl(λ), and the last one holds by our main constant-rate subspace coset state certified deletion theorem Theorem 6.2. Formally, we construct a QPT adversary Bλ in the coset state certified-deletion experiment in Theorem 6.2. Define a quantum operation Ze = {Zeλ }λ∈N as follows: on input (S, T, u, w, m + Rv), 1. Run (vk, sigk) ← Gen(1λ ). 2. Output (vk, sigk, T, u, m + Rv, Zλ (sigk, S)). Notice that Ze is subspace-hiding as required in Theorem 6.2. Because by the semantic security of Z, Zeλ (S, T, u, w, m + Rv) = (vk, sigk, T, u, m + Rv, Zλ (sigk, S)) ≈c (vk, sigk, T, u, m + Rv, Zλ (sigk, 0)), which can be simulated by a simulator Sλ (G, T, u, x, m + Rv) that does the following: 1. (vk, sigk) ← Gen(1λ ) 2. Output (vk, sigk, T, u, m + Rv, Zλ (sigk, 0)). We construct Bλ as follows: 1. Receive |Sv,w ⟩, Zeλ (S, T, u, w, m + Rv) from the challenger. 2. Compute |ψ⟩ by first applying (QFT−1 )⊗n and then |x⟩|0 · · · 0⟩ 7→ |x⟩|Sign(sigk, x)⟩ to |Sv,w ⟩. 3. Send |ψ⟩, m + Rv, T, u, vk, Zλ (sigk, S) to A. 4. Receive x′ and σ ′ and a residual state ρ from A. 5. Check if Vrfy(vk, x′ , σ ′ ) = 1, then send x′ and ρ to the challenger. Otherwise, send x′ and ⊥ to the challenger. Since the challenger additionally checks whether x′ ∈ S ⊥ + w, the above simulation is exactly the same d Aλ (m). Therefore, EXP d Aλ (m) ≡ EXPBλ (m), where the latter is the experiment of Theorem 6.2 as EXP λ λ λ e Hence, instantiated with Z.   d Aλ (m), EXP d Aλ (0k ) = negl(λ) TD EXP λ λ by Theorem 6.2.

62

Discussion on the Applications We emphasize that, unlike the [BGK+ 24] compiler, which relies on indistinguishability obfuscation (iO) to obfuscate a subspace membership checking program in order to obtain PVD for all-or-nothing type primitives, we eliminate the need for iO. Instead, we obtain PVD for all-or-nothing type primitives, by extending the [KNY23] compiler to subspace coset states via constrained signatures. Moreover, our construction achieves constant-rate efficiency, enabled by our constant-rate certified deletion (CD) main theorem. We note that our PVD compiler for subspace-coset-state CD encodings does not extend to beyond all-or-nothing type primitives. The main obstacle is that, for some primitives such as diO-CD, FE-CD, and blind delegation, correctness requires coherent evaluation on the subspace coset state within an otherwise classical functionality. When the signing key is embedded in such a classical primitive, it is unclear how to coherently uncompute the signing unitary on the entire signed subspace coset state. For CCA-PKE, the aforementioned issue does not arise because, for correctness, the decryptor has access to the secret key. It can therefore first classically recover the signing key and then use it to uncompute the signing unitary. However, a different difficulty arises in the security definition, as it is unclear how to formulate an appropriate decryption oracle for signed ciphertexts in the CCA security game. Acknowledgements We thank the anonymous reviewers for the feedback, as well as Tyler Besselman, Nai-Hui Chia, Yu-Ching Shen, and Jhih-Wei Shih for helpful discussions. Kai-Min Chung and Wei-Hsiang Hung is supported by NSTC QC project under Grant no. NSTC 115-2119-M-001-002. Tzu-Hsiang Huang is supported in part by AFOSR, NSF 2112890, NSF CNS-2247727 and a Google Research Scholar award. This material is based upon work supported by the Air Force Office of Scientific Research under award number FA9550-23-1-0543. Shota Yamada is supported by JPMJCR22M1 and JPMJKP24U3.

References [ABKK23] Amit Agarwal, James Bartusek, Dakshita Khurana, and Nishant Kumar. A new framework for quantum oblivious transfer. LNCS, pages 363–394, 2023. (Cited on page 7.) [BF10]

Niek J Bouman and Serge Fehr. Sampling in a quantum population, and applications. In Annual Cryptology Conference, pages 724–741. Springer, 2010. (Cited on page 18.)

[BGK+ 24] James Bartusek, Vipul Goyal, Dakshita Khurana, Giulio Malavolta, Justin Raizes, and Bhaskar Roberts. Software with certified deletion. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 85–111. Springer, 2024. (Cited on page 3, 4, 5, 11, 12, 15, 16, 17, 40, 53, 54, 63.) [BI20]

Anne Broadbent and Rabib Islam. Quantum encryption with certified deletion. In Theory of Cryptography Conference, pages 92–122. Springer, 2020. (Cited on page 3, 4.)

[BK23]

James Bartusek and Dakshita Khurana. Cryptography with certified deletion. LNCS, pages 192–223, 2023. (Cited on page 3, 4, 5, 6, 8, 27, 38.)

[BKK+ 26] James Bartusek, Dakshita Khurana, Fuyuki Kitagawa, Giulio Malavolta, Ryo Nishimaki, Alexander Poremba, Michael Walter, and Takashi Yamakawa. Publicly verifiable deletion: General compilers from minimal assumptions. Journal of Cryptology, 39(3):26, 2026. (Cited on page 3.) 63

[BKM+ 23] James Bartusek, Dakshita Khurana, Giulio Malavolta, Alexander Poremba, and Michael Walter. Weakening assumptions for publicly-verifiable deletion. In Theory of Cryptography Conference, pages 183–197. Springer, 2023. (Cited on page 3, 4, 5, 54.) [BKP23]

James Bartusek, Dakshita Khurana, and Alexander Poremba. Publicly-verifiable deletion via target-collapsing functions. In Annual International Cryptology Conference, pages 99–128. Springer, 2023. (Cited on page 3, 4, 5, 54.)

[BR24]

James Bartusek and Justin Raizes. Secret sharing with certified deletion. In Annual International Cryptology Conference, pages 184–214. Springer, 2024. (Cited on page 4, 7, 9.)

[BZ13]

Dan Boneh and Mark Zhandry. Secure signatures and chosen ciphertext security in a quantum computing world. In Annual cryptology conference, pages 361–379. Springer, 2013. (Cited on page 18.)

[EC16]

European Parliament and Council of the European Union. Regulation (EU) 2016/679 of the European Parliament and of the Council of 27 April 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data, and repealing Directive 95/46/EC (General Data Protection Regulation) (Text with EEA relevance), 2016. (Cited on page 3.)

[GV15]

Sergey Gorbunov and Dhinakaran Vinayagamurthy. Riding on asymmetry: Efficient ABE for branching programs. In Tetsu Iwata and Jung Hee Cheon, editors, ASIACRYPT 2015, Part I, volume 9452 of LNCS, pages 550–574, November / December 2015. (Cited on page 55.)

[HKM+ 24] Taiga Hiroka, Fuyuki Kitagawa, Tomoyuki Morimae, Ryo Nishimaki, Tapas Pal, and Takashi Yamakawa. Certified everlasting secure collusion-resistant functional encryption, and more. LNCS, pages 434–456, 2024. (Cited on page 3.) [HMNY21] Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki, and Takashi Yamakawa. Quantum encryption with certified deletion, revisited: Public key, attribute-based, and classical communication. In International Conference on the Theory and Application of Cryptology and Information Security, pages 606–636. Springer, 2021. (Cited on page 3, 4.) [HMNY22] Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki, and Takashi Yamakawa. Certified everlasting functional encryption. Cryptology ePrint Archive, Paper 2022/969, 2022. (Cited on page 3, 4.) [KLYY25] Fuyuki Kitagawa, Jiahui Liu, Shota Yamada, and Takashi Yamakawa. A unified approach to quantum key leasing with a classical lessor. Cryptology ePrint Archive, Report 2025/1871, 2025. (Cited on page 55.) [KMY25]

Fuyuki Kitagawa, Tomoyuki Morimae, and Takashi Yamakawa. A simple framework for secure key leasing. LNCS, pages 217–247, 2025. (Cited on page 13, 55.)

[KNY23]

Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa. Publicly verifiable deletion from minimal assumptions. In Theory of Cryptography Conference, pages 228–245. Springer, 2023. (Cited on page 3, 4, 5, 12, 13, 54, 61, 63.)

[KS25]

Jonathan Katz and Benjamin Sela. Secret sharing with publicly verifiable deletion. LNCS, pages 278–304, 2025. (Cited on page 3, 5, 54.) 64

[MPR11]

Hemanta K. Maji, Manoj Prabhakaran, and Mike Rosulek. Attribute-based signatures. In Aggelos Kiayias, editor, CT-RSA 2011, volume 6558 of LNCS, pages 376–392, February 2011. (Cited on page 54.)

[Por22]

Alexander Poremba. Quantum proofs of deletion for learning with errors. Cryptology ePrint Archive, Paper 2022/295, 2022. (Cited on page 3, 4, 5, 54.)

[Tsa17]

Rotem Tsabary. An equivalence between attribute-based signatures and homomorphic signatures, and new constructions for both. In Yael Kalai and Leonid Reyzin, editors, TCC 2017, Part II, volume 10678 of LNCS, pages 489–518, November 2017. (Cited on page 13, 54.)

[Win02]

Andreas Winter. Coding theorem and strong converse for quantum channels. IEEE Transactions on Information Theory, 45(7):2481–2485, 2002. (Cited on page 18.)

[Zha12]

Mark Zhandry. Secure identity-based encryption in the quantum random oracle model. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 758–775, August 2012. (Cited on page 14, 18.)

65

Related documents

• Constant-Rate Certified Deletion#1188301
• Impossibility of perfect cheating for single-qubit position verification#617762
• Impossibility of perfect cheating for single-qubit position verification#617262
• On the Cryptographic Structure Required for Verifying Qubits#259371
• A Description of the MISTY1 Encryption Algorithm#134966