# Secret Sharing with Certified Deletion

James Bartusek  UC Berkeley  Justin Raizes  Carnegie Mellon University

###### Abstract

Secret sharing allows a user to split a secret into many shares so that the
secret can be recovered if, and only if, an authorized set of shares is
collected. Although secret sharing typically does not require any
computational hardness assumptions, its security _does_ require that an
adversary cannot collect an authorized set of shares. Over long periods of
time where an adversary can benefit from multiple data breaches, this may
become an unrealistic assumption.

We initiate the systematic study of secret sharing _with certified deletion_
in order to achieve security _even against an adversary that eventually
collects an authorized set of shares_. In secret sharing with certified
deletion, a (classical) secret $s$ is split into quantum shares that can be
destroyed in a manner verifiable by the dealer.

We put forth two natural definitions of security. No-signaling security
roughly requires that if multiple non-communicating adversaries delete
sufficiently many shares, then their combined view contains negligible
information about $s$, even if the total set of corrupted parties forms an
authorized set. Adaptive security requires privacy of $s$ against an adversary
that can continuously and adaptively corrupt new shares and delete previously-
corrupted shares, as long as the total set of corrupted shares minus deleted
shares remains unauthorized.

Next, we show that these security definitions are achievable: we show how to
construct (i) a secret sharing scheme with no-signaling certified deletion for
_any monotone access structure_ , and (ii) a _threshold_ secret sharing scheme
with adaptive certified deletion. Our first construction uses Bartusek and
Khurana’s (CRYPTO 2023) 2-out-of-2 secret sharing scheme with certified
deletion as a building block, while our second construction is built from
scratch and requires several new technical ideas. For example, we
significantly generalize the “XOR extractor” of Agarwal, Bartusek, Khurana,
and Kumar (EUROCRYPT 2023) in order to obtain better seedless extraction from
certain quantum sources of entropy, and show how polynomial interpolation can
double as a high-rate randomness extractor in our context of threshold sharing
with certified deletion.

##  1 Introduction

Secret sharing [Sha79, Bla79, ISN87] is a foundational cryptographic primitive
that allows a dealer to distribute a secret $s$ among $n$ parties so that only
certain “authorized” subsets of the parties may recover the secret. A
particularly common scenario is $(k,n)$ _threshold_ secret sharing, where the
dealer splits $s$ into $n$ shares such that any $k$ of the shares can be
combined to recover the secret $s$, but any $k-1$ or fewer shares leak no
information about $s$. However, one can also consider a much more versatile
setting, in which the authorized subsets of $n$ are defined by any _monotone
access structure_ $\mathbb{S}$.111A set $\mathbb{S}$ of subsets of $[n]$ is
monotone if for any subset $S\in\mathbb{S}$, it holds that
$S^{\prime}\in\mathbb{S}$ for all supersets $S^{\prime}\supset S$. Secret
sharing schemes are ubiquitous in cryptography, and we refer the reader to
Beimel’s survey [Bei11] for a broader discussion, including several
applications.

A particularly appealing aspect of secret sharing that sets it apart from most
other cryptographic primitives is that it _doesn’t require computational
hardness assumptions_. That is, one can construct secret sharing schemes for
arbitrary monotone access structures secure against any computationally
unbounded adversary (e.g. [ISN87, BL90, LV18]).

However, the security of these schemes still rests on a stringent assumption:
over the course of the (potentially unbounded) adversary’s operation, it only
ever sees an unauthorized set of shares. This may be unacceptable for users
sharing particularly sensitive information. Even if an adversary initially may
only access a limited number of shares, over time they may be able to corrupt
more and more parties, or perhaps more and more shares become compromised
independently and are leaked into the public domain. A user who becomes
paranoid about this possibility generally has no recourse, and, worse yet,
cannot even _detect_ if an adversary has obtained access to enough shares to
reconstruct their secret.

In this work, we ask whether it is possible to strengthen the standard notion
of secret sharing security, and relax the assumption that the adversary only
ever corrupts an unauthorized set of parties. In particular:

> _Is it possible to achieve meaningful secret sharing security against
> adversaries that may eventually corrupt authorized sets of parties?_

Now, if the shares consist of only classical data, then there is no hope of
answering the above question in the affirmative. Indeed, once an adversary
obtains any share, they can make a copy and store it away. Once they’ve
collected and stored an authorized set, they’ll be able to recover the secret
due to the correctness of the secret sharing scheme.

#### Certified deletion.

On the other hand, the _uncertainty principle_ of quantum mechanics offers
some hope: if shares are encoded into quantum states, then the useful share
information may be erased by applying certain destructive measurements. Thus,
a user that is worried about an adversary eventually corrupting an authorized
set of shares may request and verify that this “deletion” operation is
performed on some set of their shares. Now, even if the adversary learns
enough shares in the future to constitute an authorized set, the already-
deleted shares will remain useless, and there is hope that the user’s secret
remains private.

Indeed, the basic idea of leveraging the uncertainty principle to perform
“certified deletion” of private information was first put forth by Broadbent
and Islam [BI20] in the context of one-time-pad encryption, and has since been
applied in several contexts throughout cryptography, e.g. [HMNY21, HMNY22,
Por23, BK23, BKM+23, HKM+24, BGK+24]. In fact, Bartusek and Khurana [BK23]
previously constructed a very limited flavor of secret sharing with certified
deletion, namely, 2-out-of-2 secret sharing where only one of the two shares
admits the possibility the deletion. Their scheme allows a user to split a
secret $s$ into a quantum share $\ket{\mathsf{sh}_{1}}$ and a classical share
$\mathsf{sh}_{2}$. If an adversary first obtains and deletes
$\ket{\mathsf{sh}_{1}}$, then obtains $\mathsf{sh}_{2}$, it will still be
unable to reconstruct the secret $s$. One can also view the original one-time-
pad encryption with certified deletion scheme of [BI20] as exactly this flavor
of 2-out-of-2 secret sharing with certified deletion, where the quantum share
is the ciphertext and the classical share is the secret key. In this work, we
show that it is possible to introduce certified deletion guarantees into more
versatile and general flavors of secret sharing, addressing several
definitional and technical issues along the way.

###  1.1 Our Results

We formulate two powerful but incomparable notions of certified deletion
security for general-purpose secret sharing schemes, and show how to construct
a scheme satisfying each definition. One of our key technical tools is a high-
rate seedless extractor from certain quantum sources of entropy that
significantly generalizes and improves upon the “XOR extractor” of [ABKK23].

#### No-signaling security.

First, we address the shortcomings of [BK23]’s security definition for 2-out-
of-2 secret sharing sketched above, and formulate a natural extension that (i)
applies to schemes for _any_ monotone access structure, and (ii) allows for
the possibility that _any_ of the shares may be deleted.

In particular, we model a scenario involving multiple non-communicating
adversaries that each individually have access to some unauthorized set of
shares. These adversaries may even share entanglement, but may not exchange
messages. Now, the user may request that some of its shares are deleted. If
the adversaries jointly delete enough shares so that the remaining undeleted
shares form an _unauthorized_ set, then we combine the views of all the
adversaries together, and require that the user’s secret remains private even
given this joint view. That is, even if a single adversarial entity is
eventually able to corrupt up to _all_ of the parties, they will still not be
able to recover the secret if enough shares have previously been deleted.222We
remark that this definition also captures adversaries that don’t end up
corrupting _all_ the shares, by imagining that there is a separate component
of the adversary that honestly deletes the uncorrupted shares.

We refer to this security notion for secret sharing schemes as _no-signaling
security_ (see Section 5 for a precise definition), emphasizing the fact that
shares must be deleted by adversaries that cannot yet pool information about
an authorized set of shares, as this would trivially allow for reconstruction
of the secret. Then, in Section 6 we show how to combine [BK23]’s simple
2-out-of-2 secret sharing scheme with any standard secret sharing scheme for
monotone access structure $\mathbb{S}$ (e.g. [ISN87, BL90, LV18]) in order to
obtain a secret sharing scheme for $\mathbb{S}$ with no-signaling security.

######  Theorem 1 (Informal).

There exists a secret sharing scheme with no-signaling certified deletion
security for any monotone access structure $\mathbb{S}$.

#### Adaptive security.

Next, we consider a particularly cunning but natural class of adversaries that
exhibit the following behavior. Suppose that initially the adversary only
obtains access to some unauthorized set of shares. At some point, the user
becomes paranoid and requests that some subset of these shares are deleted.
The adversary obliges but then continues to corrupt new parties or locate
other leaked shares. The adversary may continue to delete some of these shares
to appease the user, while continuing to work behind the scenes to mount a
long-term attack on the system. However, as long as the set of corrupted
parties minus the set of certifiably deleted shares continues to be
unauthorized, we can hope that the user’s secret remains private from such an
adversary.

Unfortunately, the notion of no-signaling security does not capture the
behavior of such an _adaptive_ adversary. That is, no-signaling security only
models adversaries that delete once, and then receive some extra information
after this single round of deletion. Thus, we formalize _adaptive security_ as
an alternative and quite strong notion of certified deletion security for
secret sharing schemes (see Section 5 for a precise definition).

Protecting against such arbitrarily adaptive adversaries turns out to be a
significant challenge. The main technical component of our work realizes a
secret sharing scheme with adaptive certified deletion security for the
specific case of threshold access structures (Section 7).

######  Theorem 2 (Informal).

There exists a threshold secret sharing scheme with adaptive certified
deletion security.

#### High-rate seedless extractors from quantum sources of entropy.

One of our technical building blocks is an improved method for seedless
extraction from certain quantum sources of entropy. Roughly, the source of
entropy comes from performing a standard basis measurement on a register that
is in superposition over a limited number of Fourier basis states.

While seedless extraction from such sources of entropy [ABKK23] has been a
crucial component in previous realizations of cryptographic primitives with
certified deletion [BK23],333See discussion thereinfor why _seedless_ as
opposed to seeded extraction is crucial. the technique had been limited to (i)
extracting from qubit registers (i.e. where data is natively represented as
superpositions of bitstrings) and (ii) extracting only a single bit of
entropy. Here, we generalize these techniques to extract from qu _dit_
registers (i.e. where data is natively represented as superpositions of
vectors over finite fields), and produce several field elements worth of
entropy, vastly improving the rate of extraction. Beyond being interesting in
its own right, it turns out that these improvements are crucial for showing
security our construction of threshold sharing with adaptive certified
deletion. Moreover, we show how these high-rate extraction techniques can be
applied to extension fields, meaning that we can represent our quantum shares
as string of qubits (as opposed to qudits), removing the need for entanglement
in our construction. We refer the reader to Section 2.3 and Section 4 for more
details.

##  2 Technical Overview

Intuitively, certified deletion for secret sharing aims to keep the secret
private from an adversary if the total set of undeleted shares they have
access to is unauthorized. One could formalize this by considering an
adversary who initially receives an unauthorized set of shares and then
deletes some of them. If the undeleted shares are still unauthorized when
combined with the shares that the adversary did not receive, then we allow the
adversary to access these remaining shares. This closely matches the
definition of encryption with certified deletion, where the adversary
initially receives and deletes a ciphertext $\mathsf{Enc}(k,m)$ encrypting
message $m$ using key $k$, and then later receives the key $k$.

However, this definition is not meaningful for all access structures. For
example, in a $k$ out of $n$ access structure where $k<n/2$, the shares that
the adversary does not start with _already_ form an authorized set on their
own, so it never makes sense to allow the adversary to access all of these
shares at once. In this section, we give an overview of two different ways to
address this definitional deficiency: no-signaling certified deletion and
adaptive certified deletion.

###  2.1 No-Signaling Certified Deletion

In no-signaling certified deletion, we address this problem by allowing the
adversary to delete from multiple sets of shares $P_{1},\dots,P_{\ell}$.
However, if $P_{1}\cup\dots\cup P_{\ell}$ contains all shares, then the
adversary as a whole gets to see every share before it generates any deletion
certificates. Thus, to prevent trivial attacks, we do not allow the adversary
to communicate across sets. However, the different parts of the adversary may
still _share entanglement_. This modification yields the no-signaling
certified deletion game $\mathsf{SS\text{-}NSCD}_{\mathbb{S}}(s)$ for secret
$s$ and access structure $\mathbb{S}$ over $n$ parties, which we describe
here.

  1. 1.

The challenger secret-splits $s$ into $n$ shares with access structure
$\mathbb{S}$.

  2. 2.

Each adversary $\mathsf{Adv}_{i}$ is initialized with one register of a shared
state $\ket{\psi}$, receives the shares in a set $P_{i}$, and produces some
set of certificates $\\{\mathsf{cert}_{j}\\}_{j\in P_{i}}$. If
$\mathsf{Adv}_{i}$ does not wish to delete share $j$, then it may set
$\mathsf{cert}_{j}=\bot$.

  3. 3.

If the total set of shares that have not been deleted is unauthorized, then
output the joint view of the adversaries. Otherwise, output $\bot$.

No-signaling certified deletion for secret sharing requires that for every
secret pair $(s_{0},s_{1})$ and every partition $P=(P_{1},\dots,P_{\ell})$ of
$[n]$, the outputs of $\mathsf{SS\text{-}NSCD}_{\mathbb{S}}(s_{0})$ and
$\mathsf{SS\text{-}NSCD}_{\mathbb{S}}(s_{1})$ have negligible trace distance.

#### Tool: 2-of-2 Secret Sharing with Certified Deletion [BK23].

Recently, Bartusek and Khurana constructed a variety of primitives with
certified deletion. One of these primitives is a secret sharing scheme which
splits a secret $s$ into a quantum share $\ket{\mathsf{sh}_{1}}$ and a
classical share $\mathsf{sh}_{2}$, along with a verification key $\mathsf{vk}$
that can be used to test the validity of deletion certificates. Given either
one of the shares, the secret is hidden. Furthermore, if an adversary given
$\ket{\mathsf{sh}_{1}}$ performs a destructive measurement that yields a valid
deletion certificate, then they will never be able to recover $s$, even if
they later obtain $\mathsf{sh}_{2}$. Note that in this scheme, only one of the
two shares can be deleted.

#### A Black-Box Compiler.

We show how to compile Bartusek and Khurana’s 2-of-2 certified deletion scheme
together with any classical secret sharing scheme into a secret sharing scheme
with no-signaling certified deletion. Notably, the compiled scheme inherits
the same access structure as the classical secret sharing scheme. Thus, one
can construct secret sharing with no-signaling certified deletion for general
access structures by using any classical secret sharing scheme for general
access structures, e.g. [ISN87, ABF+19].

As a starting point, let us first construct a scheme where only one of the
shares can be deleted.

  1. 1.

Secret split the secret $s$ into a quantum share $\ket{\mathsf{qsh}}$ and a
classical share $\mathsf{csh}$ using the 2-of-2 secret sharing scheme with
certified deletion. This also produces a verification key $\vk$.

  2. 2.

Split the 2-of-2 classical share $\mathsf{csh}$ into classical shares
$\mathsf{csh}_{1},\dots,\mathsf{csh}_{n}$ using the classical secret sharing
scheme for $\mathbb{S}$.

  3. 3.

The verification key is $\mathsf{vk}$ and the $i$’th share is
$\mathsf{csh}_{i}$. The deletable quantum share is $\ket{\mathsf{qsh}}$.

Given the quantum share and any authorized set of classical shares, $s$ can be
reconstructed by first recovering $\mathsf{csh}$ from the authorized set. On
the other hand, any adversary which attempts to delete $\ket{\mathsf{qsh}}$
with only access to an unauthorized set of classical shares has no information
about the 2-of-2 classical share $\mathsf{csh}$. Thus if they produce a valid
deletion certificate, they will have no information about $s$ even after
obtaining the rest of the classical shares, which only reveals $\mathsf{csh}$.

#### Who Deletes?

To finish the compiler, we need to enable certified deletion of _any share_.
This can be achieved by adding a step at the beginning of the compiler to
create $n$ classical shares $\mathsf{sh}_{1},\dots,\mathsf{sh}_{n}$ of $s$
with the same access structure $\mathbb{S}$. Then, the splitter can enable
certified deletion for each share $\mathsf{sh}_{i}$ by using the prior
compiler to produce a set of classical shares
$\mathsf{csh}_{i,1},\dots,\mathsf{csh}_{i,n}$, a deletable quantum share
$\ket{\mathsf{qsh}_{i}}$, and a verification key $\mathsf{vk}_{i}$. The $i$’th
share contains the deletable state $\ket{\mathsf{qsh}_{i}}$, as well as
$\\{\mathsf{csh}_{j,i}\\}_{j\in[n]}$.

Note that anyone holding share $i$ is able to delete $\mathsf{sh}_{i}$ by
deleting $\ket{\mathsf{qsh}_{i}}$, as discussed previously. If sufficiently
many shares are deleted, so that the only remaining $\mathsf{sh}_{i}$ form an
unauthorized set, then no adversary can learn anything about the secret even
after obtaining all of the remaining shares and residual states.

#### Proof of Security: Guessing Deletions.

Although the intuition is straightforward, there is a nuance in the proof of
security. When proving security, we wish to replace the deleted 2-of-2 secrets
$\mathsf{sh}_{i}$ with empty secrets $\bot$. If we could do so, then security
immediately reduces to the security of the classical $\mathbb{S}$-scheme,
since only an unauthorized set of $\mathsf{sh}_{i}$ remains. However, it is
difficult to determine which of these 2-of-2 secrets $\mathsf{sh}_{i}$ to
replace with $\bot$ when preparing the shares.

Since non-local operations commute, we could consider generating the shares
for each adversary $\mathsf{Adv}_{i}$ one at a time. For example, supposing
$\mathsf{Adv}_{1}$ operates on the set of shares $P_{1}\subset[n]$, the
experiment could initialize $\mathsf{Adv}_{1}$ with uniformly random shares,
and then for each $i\in P_{1}$, reverse-sample the shares
$\\{\mathsf{csh}_{i,j}\\}_{j\in[n]\setminus P_{1}}$ for the rest of the
adversaries to match either $\mathsf{sh}_{i}$ or $\bot$, depending on whether
or not $\mathsf{Adv}_{1}$ deleted share $i$.

Unfortunately, we cannot continue this strategy for all of the adversaries. It
may be the case that the union of $\mathsf{Adv}_{1}$ and $\mathsf{Adv}_{2}$’s
shares $P_{1}\cup P_{2}$ contains an authorized set. Thus, when initializing
$\mathsf{Adv}_{2}$, the challenger must already know whether, for each $i\in
P_{2}$, the $i$’th share of $s$ should be set to $\mathsf{sh}_{i}$ or $\bot$
(since this will be determined by $\\{\mathsf{csh}_{i,j}\\}_{j\in P_{1}\cup
P_{2}}$). This view is constructed before the adversary decides whether or not
to delete share $i$, so the only way for the challenger to do this is to guess
whether the adversary will delete share $i$ or not.

Now, guessing which shares the entire set of adversaries will delete incurs a
multiplicative exponential (in $n$) loss in security. Fortunately, Bartusek
and Khurana’s 2-of-2 scheme actually satisfies an _inverse exponential_ trace
distance between the adversary’s view of any two secrets, after deletion.
Thus, by setting the parameters carefully, we can tolerate this exponential
loss from guessing, and show that our scheme for general access structures
satisfies negligible security.

###  2.2 Adaptive Certified Deletion

Intuitively, any definition of certified deletion should allow the adversary
to eventually receive an authorized set of shares, as long as they have
previously deleted enough shares so that their total set of undeleted shares
remains unauthorized. In no-signaling certified deletion, we allowed multiple
non-communicating adversaries to delete from different unauthorized sets of
shares. That is, when $\mathsf{Adv}_{i}$ generates its set of certificates, it
only has access to a single unauthorized set $P_{i}$. However, one could also
imagine a more demanding setting where, after deleting some shares, the
adversary can adaptively corrupt _new shares_ , as long as their total set of
undeleted shares remains unauthorized. Then, they can continue deleting shares
and corrupting new shares as long as this invariant holds. This setting arises
naturally when we consider an adversary which covertly compromises shares over
a long period of time, while occasionally deleting shares to avoid revealing
the extent of the infiltration. We call this notion _adaptive certified
deletion_. It is defined using the following adaptive certified deletion game
$\mathsf{SS\text{-}ACD}_{\mathbb{S}}(s)$.

  1. 1.

The challenger splits the secret $s$ into $n$ shares with access structure
$\mathbb{S}$. The adversary starts with an empty corruption set $C$ and an
empty deletion set $D$.

  2. 2.

For as many rounds as the adversary likes, it gets to see the shares in $C$
and choose whether to corrupt or delete a new share.

Corrupt a new share. The adversary corrupts a new share $i$ by adding $i$ to
$C$. If $C\backslash D$ is authorized, the experiment immediately outputs
$\bot$.

Delete a share. The adversary outputs a certificate $\mathsf{cert}$ for a
share $i$. If $\mathsf{cert}$ is valid, add $i$ to $D$. Otherwise, the
experiment immediately outputs $\bot$.

  3. 3.

When the adversary is done, the experiment outputs its view.

Adaptive certified deletion for secret sharing requires that for every secret
pair $(s_{0},s_{1})$, the outputs of
$\mathsf{SS\text{-}ACD}_{\mathbb{S}}(s_{0})$ and
$\mathsf{SS\text{-}ACD}_{\mathbb{S}}(s_{1})$ have negligible trace distance.
In this work, we focus on the $(k,n)$ threshold access structure, where any
set of size $\geq k$ is authorized.

#### Incomparable Definitions.

We have already seen that no-signaling certified deletion does not imply
adaptive certified deletion. It is also the case that adaptive certified
deletion does not imply no-signaling certified deletion. Consider a two-part
no-signaling adversary $\mathsf{Adv}_{1}$ and $\mathsf{Adv}_{2}$ with views
$P_{1}$ and $P_{2}$. To change $(\mathsf{Adv}_{1},\mathsf{Adv}_{2})$ to an
adaptive adversary, one would need to come up with a transformation that
deletes the same shares as $(\mathsf{Adv}_{1},\mathsf{Adv}_{2})$, in the same
way. However, $\mathsf{Adv}_{1}$ might not even decide which shares to delete
until after they have seen every share in $P_{1}$. So, the new adaptive
adversary would have to corrupt all of $P_{1}$ before it can delete a single
share that $\mathsf{Adv}_{1}$ would. Similarly, it would also have to corrupt
all of $P_{2}$ before it knows which shares $\mathsf{Adv}_{2}$ would delete.
However, if $P_{1}\cup P_{2}$ is authorized, then the experiment would abort
before the new adaptive adversary gets the chance to delete shares for both
$\mathsf{Adv}_{1}$ and $\mathsf{Adv}_{2}$.

#### An Attack on the No-Signaling Construction.

Unfortunately, the previous construction actually does _not_ in general
satisfy adaptive certified deletion security. Indeed, observe that the
classical parts of each share can never be deleted. Because of this, an
adversary could, for any $i$, obtain $k$ classical shares
$\mathsf{csh}_{i,1},\dots,\mathsf{csh}_{i,k}$ that reveal $\mathsf{csh}_{i}$,
simply by corrupting and immediately deleting the first $k$ shares one-by-one.
Afterwards, the adversary will always have _both_ the classical share
$\mathsf{csh}_{i}$ and the quantum share $\ket{\mathsf{qsh}_{i}}$ when it
corrupts a new share $i$, so it can recover the underlying classical share
$\mathsf{sh}_{i}$. Now it can “delete” the $i$’th share while keeping
$\mathsf{sh}_{i}$ in its memory. Eventually, it can collect enough
$\mathsf{sh}_{i}$ in order to obtain the secret $s$.

The core problem with the no-signaling construction is the fact that it
encodes the 2-of-2 classical shares $\mathsf{csh}$ in a form which can never
be deleted. If we were to take a closer look at Bartusek and Khurana’s 2-of-2
scheme, we would observe that $\mathsf{csh}$ contains a mapping $\theta$ of
which parts of $\ket{\mathsf{qsh}}$ encode the secret (the “data indices”) and
which parts contain only dummy information used to verify certificates (the
“check indices”). Without $\theta$, there is no way to decode the secret.
Unfortunately, in order to encode $\theta$ in a deletable form, we seem to be
back where we started - we need secret sharing with adaptive certified
deletion!

#### A New Construction.

To avoid this pitfall, we take a new approach that allows the parties to
reconstruct _without knowledge of the check indices_. This removes the need to
encode $\theta$ altogether. To achieve this, we begin with Shamir’s secret
sharing [Sha79], in which the shares are evaluation points of a degree $k-1$
polynomial $f$ where $f(0)=s$. This polynomial is over some finite field
$\mathbb{K}$ with at least $n+1$ elements. A useful property of Shamir’s
secret sharing is that it has good error-correcting properties - in fact, it
also forms a Reed-Solomon code, which has the maximum possible error
correction [RS60].

To split a secret $s$, we start by constructing a polynomial $f$ where
$f(0)=s$. Each share contains some number of evaluations of $f$ encoded in the
computational basis. These evaluations are mixed with a small number of random
Fourier basis states that will aid in verifying deletion certificates. The
positions of these checks, along with the value encoded, make up the
verification key. An example share and key are illustrated here.

$\begin{array}[]{cccccccccccc}\mathsf{sh}=&\ket{f(1)}&\otimes&\ket{f(2)}&\otimes&\mathsf{QFT}\ket{r_{1}}&\otimes&\ket{f(4)}&\otimes&\mathsf{QFT}\ket{r_{2}}&\otimes&\dots\\\
\mathsf{vk}=&*&&*&&r_{1}&&*&&r_{2}&&\dots\end{array}$

When reconstructing the secret, these checks are essentially random errors in
the polynomial evaluation. By carefully tuning the degree of the polynomial
together with the number of evaluations and checks in each share, we can
ensure that any $k$ shares contain enough evaluation points to correct the
errors from the check positions, but that any $k-1$ shares do not contain
enough evaluation points to determine the polynomial. This results in $f$
being determined by slightly more than $k-1$ shares worth of evaluations.
Additionally, we slightly increase the degree of the polynomial to account for
the limited amount of information that an adversary can retain after deletion.
See Section 7 for more details.

Share deletion and certificate verification follow the established formula. To
delete a share, measure it in the Fourier basis and output the result as the
certificate. To verify the certificate, check that it matches the verification
key at the check positions.

#### Proving Adaptive Certified Deletion.

Intuitively, we want to show that after the adversary deletes a share, the
next share it corrupts gives it no additional information, no matter how many
shares the adversary has seen so far. To formalize this, we will show that the
adversary cannot distinguish between the real
$\mathsf{SS\text{-}ACD}_{(k,n)}(s)$ experiment and an experiment in which each
share is generated uniformly at random and independently of the others. Since
the first $k-1$ shares to be corrupted do not yet uniquely determine the
polynomial $f$, they already satisfy this. Thus, we can restrict our attention
to modifying the last $n-k+1$ shares to be corrupted.

It will be useful to name the shares in the order they are corrupted or
deleted. The $a$’th share to be corrupted is $c_{a}$, and the $b$’th share to
be deleted is share $d_{b}$. In the $(k,n)$ threshold case, if $c_{k-1+b}$ is
corrupted before $d_{b}$ is deleted, then $C\backslash D$ has size $k$ and is
authorized, so the experiment will abort.

#### Techniques from BK23.

We begin by recalling the techniques introduced in [BK23] to analyze 2-of-2
secret sharing with certified deletion, along with the construction. These
techniques will form the starting point of our proof. To share a single-bit
secret $s\in\\{0,1\\}$, sample random $x,\theta\leftarrow\\{0,1\\}^{\lambda}$
and output

$\mathsf{sh}_{1}=H^{\theta}\ket{x},\quad\mathsf{sh}_{2}=\left(\theta,s\oplus\bigoplus_{i:\theta_{i}=0}x_{i}\right),\quad\vk=(x,\theta),$

where $H^{\theta}$ denotes applying the Hadamard gate $H$ to the $i$’th
register for each $i:\theta_{i}=1$. Bartusek and Khurana showed that if an
adversary given $\mathsf{sh}_{1}$ produces a certificate $\mathsf{cert}$ such
that $\mathsf{cert}_{i}=x_{i}$ for every check position $i:\theta_{i}=1$, then
they cannot distinguish whether $s=0$ or $s=1$ even if they later receive
$\mathsf{sh}_{2}$. Their approach has three main steps.

  1. 1.

First, they delay the dependence of the experiment on $s$ by initializing
$\mathsf{sh}_{1}$ to be the register $\mathcal{X}$ in
$\sum_{x}\ket{x}^{\mathcal{X}}\otimes\ket{x}^{\mathcal{Y}}$. Later, the
challenger can obtain $x$ by measuring register $\mathcal{Y}$, and use it to
derive $s$.

  2. 2.

Second, they argue that if the adversary produces a valid deletion
certificate, then $\mathsf{sh}_{1}$ has been “almost entirely deleted”, in the
sense that the challenger’s copy satisfies a checkable predicate with high
probability. Intuitively, this predicate shows that the data positions
($\theta_{i}=0$) of the challenger’s copy have high joint entropy when
measured in the computational basis. To show that the predicate holds, they
use the fact that the adversary does not have $\mathsf{sh}_{2}$ in their view,
so $\mathsf{sh}_{1}$ looks uniformly random. This allows a cut-and-choose
argument where the locations of the check indices are determined _after_ the
adversary outputs its deletion certificate.

  3. 3.

Finally, they show that the challenger derives a bit $s$ that is uniformly
random and independent of the adversary’s view. This utilizes a result from
[ABKK23] which shows that XOR is a good seedless extractor for entropy sources
that satisfy the aforementioned predicate.

#### Adapting to Secret Sharing.

As a starting point, let us try to adapt these techniques to undetectably
change shares to uniformly random. For concreteness, consider the task of
switching a share $c_{k-1+b}$ to uniformly random. Although we have not yet
outlined the general proof structure, we will eventually need to perform this
task. We will use this starting point to gain insights that will help guide
the eventual proof structure.

  1. 1.

The first step is to delay the synthesis of the secret information until after
the adversary outputs a deletion certificate. In our case, we will delay
creating share $c_{k-1+b}$ until after the adversary produces a valid
certificate for share $d_{b}$.

This can be achieved by sampling the first $k-1$ corrupted shares to be
uniformly random, then using polynomial interpolation to prepare the rest of
the shares. More concretely, consider the first corrupted $k-1$ shares
$c_{1},\dots,c_{k-1}$. The challenger will prepare each of these shares
$c_{a}$ using two registers $\mathcal{C}_{c_{a}}$ and $\mathcal{S}_{c_{a}}$,
then send the share to the adversary in register $\mathcal{S}_{c_{a}}$. To
prepare the $j$’th position of $c_{a}$, the experiment challenger prepares
either a uniform superposition
$\sum_{x\in\mathbb{K}}\ket{x}^{\mathcal{C}_{c_{a},j}}$ or
$\sum_{x\in\mathbb{K}}\mathsf{QFT}\ket{x}^{\mathcal{C}_{c_{a},j}}$, depending
on whether $j$ is an evaluation position or a check position. If $j$ is an
evaluation position for share $c_{a}$, the experiment challenger copies
$\mathcal{C}_{c_{a},j}$ to $\mathcal{S}_{c_{a},j}$ in the computational basis,
yielding

$\propto\sum_{x\in\mathbb{K}}\ket{x}^{\mathcal{S}_{c_{a},j}}\otimes\ket{x}^{\mathcal{C}_{c_{a},j}},$

and otherwise it copies $\mathcal{C}_{c_{a},j}$ to $\mathcal{S}_{c_{a},j}$ in
the Fourier basis, yielding

$\propto\sum_{x\in\mathbb{K}}\mathsf{QFT}\ket{x}^{\mathcal{S}_{c_{a},j}}\otimes\mathsf{QFT}\ket{x}^{\mathcal{C}_{c_{a},j}}.$

Note that the adversary cannot determine which positions are evaluation
positions and which are check positions, since each $\mathcal{S}_{c_{a},j}$
register looks maximally mixed. Also observe that $\mathcal{C}_{c_{a}}$
contains a copy of share $c_{a}$, and the evaluation positions in the initial
$k-1$ $\mathcal{C}_{c_{a}}$ registers determine the polynomial $f$. Then, when
the adversary requests to corrupt a later share, the challenger computes the
evaluation points for that share by performing a polynomial interpolation
using its copies of the prior shares. For reasons that will become apparent
shortly, we require that share $d_{b}$ is included when interpolating
$c_{k-1+b}$. The other points may be arbitrary.

The above procedure is actually slightly simplified; since the degree of $f$
is slightly larger than the number of evaluation positions in $k-1$ shares,
the first $k-1$ shares do not quite determine $f$. To remedy this, we will
also initialize a small portion of _every_ $\mathcal{S}_{i}$ to be uniformly
random, before any interpolation takes place.

  2. 2.

Next, we will need to show that $\mathcal{C}_{d_{b}}$, which contains the
challenger’s copy of share $d_{b}$, satisfies the deletion predicate if
$\mathsf{cert}_{d_{b}}$ passes verification. This is not hard to show if
$d_{b}$ was generated uniformly at random, but it is not clear what happens if
the adversary has some information about where the check positions are in
$d_{b}$ before deleting it. The first $k-1$ shares are uniformly random in the
original experiment, so this is not a problem for any share which is deleted
before $c_{k}$ is corrupted. However, later shares depend on earlier shares,
potentially leaking information about the check positions. This will be our
first barrier to overcome.

  3. 3.

Finally, we will need to show that interpolating $c_{k-1+b}$ using
$\mathcal{C}_{d_{b}}$ produces a uniformly random value whenever
$\mathcal{C}_{d_{b}}$ satisfies the deletion predicate. In other words,
polynomial interpolation should double as a good randomness extractor from
deleted shares. Fortunately, polynomial interpolation is a matrix
multiplication, and we have intuition from the classical setting that linear
operations are good randomness extractors. Since a small amount of every share
is uniformly random “for free”, the extractor needs to produce only slightly
less than a full share’s worth of evaluations to produce $c_{k-1+b}$. This is
our second technical contribution, which we will revisit in Section 2.3.

In step two, we seem to need the evaluation points in $d_{b}$ to look like the
check positions when $d_{b}$ is deleted, i.e. they should be uniformly random
and independent of the rest of the adversary’s view. A natural approach to
ensure this is to modify the shares to uniformly random round-by-round over a
series of hybrid experiments. In hybrid $i$, the first $k-1+i$ shares to be
corrupted are uniformly random. Since $d_{i+1}$ must be deleted before
$c_{k+i}$ is corrupted (or else the experiment aborts), $d_{i+1}$ must have
been one of the uniformly random shares. Now we can apply the cut-and-choose
argument to show that $\mathcal{C}_{d_{i}}$ satisfies the deletion predicate,
thereby satisfying the extractor requirements to change $c_{k+i}$ to be
uniformly random and reach hybrid $i+1$. The first $k-1$ shares are already
uniformly random, which gives us an opening to begin making modifications in
round $k$.

Unfortunately, the strategy of modifying the shares one-by-one to be uniformly
random has a major flaw. In particular, the challenger needs to produce
additional polynomial evaluations whenever the adversary wishes to corrupt
another share, which it does via interpolation. Recall that in order to claim
that $c_{k-1+i}$ is indistinguishable from random, we apply an extractor which
uses register $\mathcal{C}_{d_{i}}$ as its source of entropy. But in order to
invoke the security of the extractor, it seems that we cannot allow the
challenger to re-use $\mathcal{C}_{d_{i}}$ when interpolating later points, as
this might leak additional information about the source to the adversary.

To get around this issue, we might require that the challenger never uses
$\mathcal{C}_{d_{i}}$ again to interpolate later points. However, the
randomness extractor outputs _less_ randomness than the size of a share.
Intuitively, this occurs because the adversary can avoid fully deleting the
source share $d_{i}$ by guessing the location of a very small number of check
positions.444One may wonder whether it is possible to instead use coset states
for the shares, which provide guarantees of _full_ deletion [BGK+24].
Unfortunately, coset states induce errors which are the sum of a small number
of uniformly random vectors. It is not clear how to correct these errors to
reconstruct the secret without prior knowledge of the underlying subspace.
However, encoding the subspace brings us back to the original problem of
secret sharing with adaptive certified deletion. Imperfect deletion limits the
entropy of the source, which in turn limits the size of the extractor output.
Now, since the challenger started with _exactly_ enough evaluations to
uniquely determine $f$, if we take away the points in $\mathcal{C}_{d_{i}}$
then there are no longer enough evaluation points remaining to create the rest
of the shares, even given the newly interpolated points.

#### Predicates First, Replacement Later.

Intuitively, the problem outlined above arises from the possibility that the
adversary receives additional information about earlier shares from the later
ones, since they are all correlated through the definition of the polynomial
$f$. Our first idea to overcome this issue is to prove that the predicate
holds for all rounds _before_ switching any shares to uniformly random. In
particular, we will consider a sequence of hybrid experiments where in the
$i$’th hybrid, the challenger performs the predicate measurement on
$\mathcal{C}_{d_{i}}$ after receiving and verifying the corresponding
certificate. If the measurement rejects, the experiment immediately aborts and
outputs $\bot$.

If we can undetectably reach the last hybrid experiment, then it is possible
to undetectably replace every share with uniform randomness by working
backwards. In the last hybrid experiment, either the predicate holds on the
challenger’s copy $\mathcal{C}_{d_{n-k+1}}$ of share $d_{n-k+1}$ or the
experiment aborts. In either case, the last share $c_{n}$ to be corrupted can
be undetectably replaced with uniform randomness. Since no further shares are
interpolated, we no longer run into the issue of re-using the randomness
source $\mathcal{C}_{d_{n-k+1}}$, allowing the challenger to safely complete
the experiment. Then, once $c_{n}$ is uniformly random, the challenger no
longer needs to interpolate shares after $c_{n-1}$, so $c_{n-1}$ can also be
replaced with uniform randomness. This argument can be continued until all
shares are replaced.

To undetectably transition from hybrid $i$ to hybrid $i+1$, we must show that
the predicate measurement returns success with high probability on
$\mathcal{C}_{d_{i+1}}$. This is not hard to show for shares which are deleted
_before_ the $k$’th share is corrupted, because the deleted shares must be one
of the shares which were generated uniformly at random. However, it is not
clear how to show for shares which are deleted _after_ the $k$’th share is
corrupted, since this seems to require replacing $c_{k}$ with uniform
randomness, which brings us back to our previous problem.

#### Chaining Deletions via Truncated Experiments.

Our second insight is the observation that the result of a measurement made
when $d_{i}$ is deleted _is independent of later operations_. Thus, when
arguing about the probability that the predicate measurement accepts on
$\mathcal{C}_{d_{i}}$, it is sufficient to argue about the truncated
experiment that ends immediately after the predicate measurement on
$\mathcal{C}_{d_{i}}$. Crucially, the adversary cannot corrupt share $c_{k+i}$
in the truncated experiment without causing the experiment to abort due to
$|C\backslash D|\geq k$. Instead, $c_{k-1+i}$ is the last share that can be
corrupted. This prevents the catastrophic re-use of $\mathcal{C}_{d_{i}}$
after share $c_{k-1+i}$ is constructed.

Let us assume that we have already shown that the deletion predicate
measurement accepts on $\mathcal{C}_{d_{i}}$ with high probability; for
example, this clearly holds for $d_{1}$, which must be corrupted before
$c_{k}$ is corrupted. How likely it is to accept on $\mathcal{C}_{d_{i+1}}$?
Say the deletion predicate measurement accepts on $\mathcal{C}_{d_{i}}$. Then
we can invoke the extractor to undetectably replace share $c_{k-1+i}$ with
uniform randomness in the truncated game, since no further shares are
corrupted before the game ends. We can use similar logic to replace each of
the first $k-1+i$ shares to be corrupted in the truncated game. At this point,
the adversary has no choice but to delete a uniformly random share as
$d_{i+1}$, so we can apply a cut-and-choose argument to show that the
predicate holds with high probability on $\mathcal{C}_{d_{i+1}}$ This argument
can be repeated inductively to show that the predicate holds in each of the
polynomially many rounds.

#### Recap of the First Challenge.

In summary, the first challenge to address in proving adaptive certified
deletion is the possibility of later shares leaking information about prior
shares through the re-use of $\mathcal{C}_{d_{b}}$ in interpolation. This
prevents directly replacing each share with uniform randomness. To sidestep
this issue, we first argue that every $\mathcal{C}_{d_{b}}$ is a good source
of entropy using a series of games which end after $d_{b}$ is deleted. Then
even if $\mathcal{C}_{d_{b}}$ is used to interpolate both share $c_{k-1+b}$
and $c_{k+b}$, we can rely on the entropy from $\mathcal{C}_{d_{b+1}}$ to mask
its re-usage when interpolating $c_{k+b}$.

###  2.3 High Rate Seedless Extractors from Quantum Sources of Entropy

The final task to finish the proof of adaptive certified deletion security in
the previous section is to show that polynomial interpolation is a good
randomness extractor for entropy sources formed by deleted shares. Although
polynomial interpolation arises quite naturally in our construction, there are
additional technical reasons why it would be difficult to design a
construction for adaptive certified deletion using existing extractors.

If we were to design a scheme using a _seeded_ extractor, as done in [BI20],
then every deletion would need to be independent of the seed to avoid the
entropy source depending on the seed. However, as we saw with the no-signaling
construction, safely encoding the seed seems to already require secret sharing
with adaptive certified deletion. [BK23] makes use of the seedless XOR
extractor developed by [ABKK23] to avoid a similar problem. Unfortunately, the
XOR extractor produces only a single bit from a relatively large input. In the
case of threshold secret sharing, the extractor must use the randomness
produced by deleting a single share to extract an output which is only
slightly smaller than a full share.

To address this need, we give a new family of seedless randomness extractors
for quantum entropy sources with high rate. These constructions have
connections to linear error-correcting codes and may be of independent
interest.

#### A Family of Extractors.

The input of the extractor is a vector of $M$ elements of a finite field
$\mathbb{F}$, and the output is a vector of $m$ elements of $\mathbb{F}$. The
source consists of a register $\mathcal{X}$ which may be arbitrarily entangled
with a side-information register $\mathcal{A}$. If the register $\mathcal{X}$
is in superposition over Fourier basis vectors with Hamming weight
$\leq(M-m)/2$ in $\mathbb{F}$, then we can argue that the output
$\mathsf{Extract}(\mathcal{X})$ is uniformly random, even given
$\mathcal{A}$.555The Hamming weight over a (potentially non-binary) finite
field is being the number of nonzero entries in the vector.

The extractor family consists of matrices $R\in\mathbb{F}^{m\times M}$ such
that every set of $m$ columns of $R$ are linearly independent. In other words,
$R$ is a parity check matrix for a linear error-correcting code with distance
at least $m$. An extractor $R$ is applied by coherently multiplying $R$ with
the source register $\mathcal{X}$ in the computational basis and writing the
result to the output register.

#### Application to Polynomial Interpolation.

This family generalizes both the XOR extractor and polynomial interpolation.
The XOR extractor can be represented as the all-ones matrix with one row. Each
column is non-zero, so the extractor can produce a one-bit output. In the case
of polynomial interpolation, we can write the linear interpolation operator
for a polynomial $f$ as a matrix $R$ with $\mathsf{deg}(f)+1$ columns and a
number of rows equal to the number of points being interpolated. $R$ is a sub-
matrix of a parity check matrix for a Reed-Solomon code, so it falls into the
new extractor family. In fact, our result shows that any subset of columns in
a polynomial interpolation matrix forms a good randomness extractor for an
appropriate randomness source. When interpolating a share $c_{k-1+b}$, we can
write the interpolation matrix as $R=[R_{1}|R_{2}]$, where $R_{2}$ is applied
to $d_{b}$ and $R_{1}$ is applied to the other points $x$ on the polynomial.
Then the new share is $c_{k-1+b}=R_{1}x+R_{2}d_{b}$. If $d_{b}$ has satisfies
the deletion predicate, then our extractor result shows that $R_{2}d_{b}$ is
uniformly random. Thus, the newly interpolated share $c_{b}$ is also uniformly
random.

#### Removing Entanglement.

A downside of using polynomials for secret sharing is that each evaluation
point exists in field $\mathbb{F}$ whose size scales with the total number of
distinct points that must be defined on the polynomial. For example,
$\mathbb{F}$ might be $\mathbb{Z}_{p}$ for some prime $p>nt$, where $t$ is the
number of evaluations per share. Using the approach outlined so far, each
check position must be encoded in the Fourier basis over the same field
$\mathbb{K}$. However, a logical $\mathbb{Z}_{p}$-qudit requires
$\lceil\log_{2}(nt+1)\rceil$ qubits, which must all be entangled to produce a
Fourier basis element of $\mathbb{Z}_{p}$.

We show how to remove the entanglement of the construction to only use single-
qubit states, either in the Hadamard basis or in the computational basis. We
modify the construction by setting the field $\mathbb{F}$ to be the binary
extension field with $2^{\lceil\log_{2}(nt+1)\rceil}$ elements, so that each
check position consists of $\lceil\log_{2}(nt+1)\rceil$ qubits. Then, we
_individually_ set each of these qubits to be a random Hadamard basis element.
The other parts of the construction remain the same. Note that computational
basis vectors over $\mathbb{F}$ can be encoded as a tuple of computational
basis qubits.

Proving the security of this modification requires an expansion of the
extractor theorem to allow general finite fields $\mathbb{F}$, which may have
$p^{k}$ elements for some prime $p$ and $k\geq 1$. A Fourier basis element for
such a field is obtained by applying the quantum Fourier transform over the
additive group of $\mathbb{F}$, which is $\mathbb{Z}_{p}^{k}$. In particular,
a Fourier basis element of $\mathbb{F}$ consists of $k$ Fourier basis elements
of $\mathbb{Z}_{p}$. In the case where $p=2$, these are single-qubit Hadamard
basis elements.

We emphasize that the _only_ change is to modify how Fourier basis elements
are defined by allowing general finite fields; both the extractor family and
the Hamming weight requirement remain the same (i.e. they are still defined
with respect to $\mathbb{F}$, _not_ $\mathbb{Z}_{p}$). To gain intuition about
the usefulness of this statement, let us consider its application in our
secret-sharing construction. Ideally, an honest deleter would measure each
qubit of its share in the Hadamard basis. However, since the dealer can only
verify check positions, which each consist of $\lceil\log_{2}(nt+1)\rceil$
qubits, we can only prove a bound on the Hamming weight of the deleted state
over $\lceil\log_{2}(nt+1)\rceil$-sized chunks, which corresponds to
$\mathbb{F}$. This matches the entropy source requirements of the theorem. On
the other hand, the polynomial that the secret is encoded in is also over
$\mathbb{F}$, so polynomial interpolation must take place over $\mathbb{F}$.
This matches the extractor family.

###  2.4 Open Problems

Although our results significantly strengthen secret sharing to resist new
classes of attacks, we have only scratched the surface of an area with many
fascinating open problems. We mention a few of them here.

  * •

Adaptive Certified Deletion for General Access Structures. Against adaptive
attacks, we construct a secret sharing scheme for the special case of
threshold access structures. Is it possible to construct one for _general
access structures_?

  * •

Stronger Definitions. We prove the security of our schemes against _either_
“distributed” attacks (i.e. no-signaling security) _or_ adaptive attacks. Can
we (i) formulate natural security definitions that capture both types of
attacks, and (ii) prove the security of secret sharing schemes under such all-
encompassing definitions?

  * •

Public Verification. The question of publicly verifiable certificates for
encryption with certified deletion has seen significant progress recently
[HMNY21, Por23, BKP23, BGK+24, KNY23]. However, the techniques used seem to
require the use of a classical secret to decode the plaintext. For secret
sharing with certified deletion, this secret would need to also be encoded in
a manner that can be certifiably deleted, as mentioned in Section 2.2. Is it
possible to construct secret sharing with _publicly verifiable_ certificates
of deletion?

  * •

Other Threshold Primitives. Aside from secret sharing, there are many other
primitives which use thresholds or other access structures. For example, in
threshold signatures, any $k$ members may non-interactively sign messages
under a secret key split between $n$ parties [DF90]. Is it possible to
construct _threshold signatures or other threshold primitives_ with certified
deletion?

  * •

High Rate Commitments with Certified Deletion. A commitment with certified
deletion allows the committed message to be certifiably and information-
theoretically deleted [HMNY22, BK23]. However, current approaches either work
in the random oracle model or require $\Theta(\lambda)$ qubits to commit to a
single bit. Our new high-rate extractor (Theorem 3) provides a promising start
to reduce the commitment overhead. Unfortunately, the proof technique
pioneered by [BK23] for the plain model requires guessing the committed
message, which incurs a security loss that is exponential in the size of the
message. Is it possible to overcome this difficulty and construct commitments
with certified deletion that have are _not much larger than the committed
message_?

##  3 Preliminaries

###  3.1 Quantum Computation

For any set $S$, an $S$-qudit is a quantum state in the Hilbert space spanned
by $\\{\ket{s}:s\in S\\}$. A quantum register $\mathcal{X}$ contains some
number of qubits. $\ket{x}^{\mathcal{X}}$ denotes a quantum state $\ket{x}$
stored in register $\mathcal{X}$. A classical operation $f$ can be applied to
a quantum register $\mathcal{X}$ using the map

$\ket{x}^{\mathcal{X}}\otimes\ket{y}^{\mathcal{Y}}\mapsto\ket{x}^{\mathcal{X}}\otimes\ket{y+f(x)}^{\mathcal{Y}}$

We denote the application of this operation as $\mathcal{Y}\leftarrow
f(\mathcal{X})$.

######  Lemma 1 (Gentle Measurement [Win99]).

Let $\rho^{X}$ be a quantum state and let $(\Pi,\mathbb{I}-\Pi)$ be a
projective measurement on $X$ such that $\mathsf{Tr}(\Pi\rho)\geq 1-\delta$.
Let

$\rho^{\prime}=\frac{\Pi\rho\Pi}{\mathsf{Tr}[\Pi\rho]}$

be the state after applying $(\Pi,\mathbb{I}-\Pi)$ to $\rho$ and post-
selecting on obtaining the first outcome. Then
$\mathsf{TD}(\rho,\rho^{\prime})\leq 2\sqrt{\delta}$.

#### Quantum Fourier Transform over Finite Groups.

Let $G$ be a finite cyclic group and let $\omega_{|G|}\coloneqq\exp(\frac{2\pi
i}{|G|})$ be a primitive $|G|$’th root of unity. Let $\mathcal{X}$ be a
register containing a $G$-qudits. The quantum Fourier transform (QFT) over $G$
applied to $\mathcal{X}$ is the operation

$\ket{x}^{\mathcal{X}}\mapsto\sum_{y\in
G}\omega_{|G|}^{xy}\ket{y}^{\mathcal{X}}$

Any Abelian group $H$ may be decomposed as a product of cyclic groups
$G_{1}\times\dots\times G_{k}$. The QFT over $H$ is the tensor of the QFTs on
each of these groups. For example, if $H=G^{k}$, then the QFT over $H$ is
given by the operation

$\ket{x}^{\mathcal{X}}\mapsto\sum_{y\in G^{k}}\omega_{|G|}^{x\cdot
y}\ket{y}^{\mathcal{X}}$

When we consider taking a QFT over a finite field, we technically mean taking
the QFT over its additive group. For example, if $\mathbb{F}$ has order
$p^{k}$ for some prime $p$, then its additive group is $\mathbb{Z}_{p}^{k}$
and the QFT is the mapping above, where $G=\mathbb{Z}_{p}$.

Fourier transforms are closely related to roots of unity. An $n$’th root of
unity $\omega$ is an element of $\mathbb{C}$ such that $\omega^{n}=1$.
$\omega$ is a _primitive_ $n$’th root of unity if $\omega^{k}\neq 1$ for every
$k\in[n-1]$. The following claim about the summation of roots of unity will be
useful.

######  Claim 1.

Let $G$ be a cyclic group and let $\omega\neq 1$ be an $|G|$’th root of unity.
Then

$\sum_{x\in G}\omega^{x}=0$

###### Proof.

$\displaystyle\omega\sum_{x\in G}\omega^{x}$ $\displaystyle=\sum_{x\in
G}\omega^{1+x}$ (1) $\displaystyle=\sum_{z\in G}\omega^{z}$ (2)

where $z=1+x\in G$. Since $\omega\neq 1$ by definition, this can only be the
case if $\sum_{x\in G}\omega^{x}=0$. ∎

###  3.2 Statistics

######  Claim 2.

[Hoeffding’s Inequality [Hoe94]] Let $X_{1},\dots,X_{n}$ be Boolean
independent random variables. Let $\mu=\mathbb{E}[\sum_{i=1}^{n}X_{i}]$. Then
for every $\delta>0$,

$\Pr\left[\left|\sum_{i=1}^{n}X_{i}-\mu]\right|\geq\delta\right]\leq
2\exp\left(\frac{-2\delta^{2}}{n}\right)$

###  3.3 Polynomials and Reed-Solomon Codes

We give some useful facts about polynomials over finite fields and the related
Reed-Solomon error-correcting code.

#### Interpolation.

Lagrange interpolation gives a method of finding every point on a degree $d$
polynomial $f$ over any field $\mathbb{K}$, given any $d+1$ points on $f$
[LM01]. In particular, for every degree $d$, there is a linear operation
$\mathsf{Interpolate}_{d}(Y,X)$ that takes in a set of $d+1$ pairs $(x,f(x))$
and outputs $f(y)$ for each $y\in Y$. The operation to find a set of $s$
points is described by a matrix $R\in\mathbb{K}^{s\times(d+1)}$.

######  Fact 1.

Let $R\in\mathbb{K}^{s\times(d+1)}$ be an interpolation matrix for a degree
$d$ polynomial. Then any $s$ columns of $R$ are linearly independent.

###### Proof.

Consider the matrix $P=[R|-I_{s}]$. It suffices to show that any $s$ columns
of $P$ are linearly independent. Observe that $Py=0$ if and only if $y_{i}$
lies on the unique degree $d$ polynomial defined by $y_{1},\dots,y_{d+1}$ for
every $i\in[d+2,d+1+s]$. Assume, for the sake of contradiction, that some set
of $s$ columns of $P$ were linearly dependent. Then there exists a $y$ with
exactly $s$ non-zero values such that $Py=0$. Since $y$ is in the kernel of
$P$, it consists of $d+1+s$ evaluations of a degree $d$ polynomial. However,
this would imply the existence of a degree $d$ polynomial with $d+1+s-s=d+1$
zeros, which does not exist. ∎

#### Reed-Solomon Codes.

A Reed-Solomon code is a error correcting code based on polynomials over a
finite field $\mathbb{K}$ [RS60]. Given a message $m\in\mathbb{K}^{d}$, it
encodes $m$ as a polynomial $f$ with degree $d+1$, then outputs $s$
evaluations of $f$ as the codeword. For finite field $\mathbb{K}$ and degree
$d$, there exists an efficient correction procedure
$\mathsf{Correct}_{\mathbb{K},d}(X)$ which attempts to recover a polynomial
$f$ using a noisy set of evaluation points $X$, e.g. [WB86, Gao03]. If $X$ has
size $s$ and there are $<(s-d+1)/2$ pairs $(x,y)\in X$ such that $y\neq f(x)$,
then $\mathsf{Correct}_{\mathbb{K},d}(X)$ outputs $f$.

###  3.4 Secret Sharing

#### Classical secret sharing.

We introduce the standard notion of a secret sharing scheme, which allows one
party to distribute a classical secret $s$ among $n$ parties, such that only
certain subsets of parties have the ability to reconstruct the secret $s$. An
access structure $\mathbb{S}\subseteq\mathcal{P}([n])$ for $n$ parties is a
monotonic set of sets, i.e. if $S\in\mathbb{S}$ and $S^{\prime}\supset S$,
then $S^{\prime}\in\mathbb{S}$. Any set of parties $S\in\mathbb{S}$ is
authorized to access the secret. Secret sharing for general monotone access
structures was first introduced by [ISN87].

######  Definition 1 (Secret Sharing for Monotone Access Structures).

A secret sharing scheme is specified by a monotone access structure
$\mathbb{S}$ over $n$ parties, and consists of two classical algorithms:

  * •

$\mathsf{Split}_{\mathbb{S}}(s)$ is a randomized algorithm that takes in a
secret $s$, and outputs $n$ shares $\mathsf{sh}_{1},\dots,\mathsf{sh}_{n}$.

  * •

$\mathsf{Reconstruct}_{\mathbb{S}}(\\{\mathsf{sh}_{i}\\}_{i\in P})$ is a
deterministic algorithm that takes in a set of shares
$\\{\mathsf{sh}_{i}\\}_{i\in P}$ for some $P\subseteq[n]$, and outputs either
$s$ or $\bot$.

The scheme should satisfy the following notions of correctness and security.

  * •

Correctness. For all subsets $P\subseteq[n]$ such that there exists
$S\in\mathbb{S}$ such that $P\subseteq S$,

$\Pr\left[\mathsf{Reconstruct}(\\{\mathsf{sh}_{i}\\}_{i\in
P})=s:(\mathsf{sh}_{1},\dots,\mathsf{sh}_{n})\leftarrow\mathsf{Split}_{\mathbb{S}}(s)\right]=1.$

  * •

Privacy. There exists a randomized algorithm $\mathsf{Sim}$ such that for all
subsets $P\subseteq[n]$ such that for all $S\in\mathbb{S}$, $P\not\subseteq
S$, and any $s$,

$\left\\{\\{\mathsf{sh}_{i}\\}_{i\in
P}:(\mathsf{sh}_{1},\dots,\mathsf{sh}_{n})\leftarrow\mathsf{Split}_{\mathbb{S}}(s)\right\\}\equiv\left\\{\\{\mathsf{sh}_{i}\\}_{i\in
P}:\\{\mathsf{sh}_{i}\\}_{i\in P}\leftarrow\mathsf{Sim}(P)\right\\}.$

#### 2-out-of-2 secret sharing with certified deletion

Now, we recall the definition of 2-out-of-2 secret sharing _with certified
deletion_ as defined by [BK23]. A 2-out-of-2 secret sharing scheme is a very
special case of secret sharing where the secret is split into two shares such
that both shares together determine the secret, but either share individually
cannot be used to recover the secret.

######  Definition 2 (2-out-of-2 Secret Sharing with Certified Deletion).

We augment the standard notion of secret sharing to include a deletion
algorithm $\mathsf{Delete}_{2\text{-}2}$ and a verification algorithm
$\mathsf{Verify}_{2\text{-}2}$. We also specify that one share is quantum and
the other share is classical. Finally, we introduce a security parameter
$1^{\lambda}$, since our deletion security guarantee will be statistical
rather than perfect.

  * •

$\mathsf{Split}_{2\text{-}2}(1^{\lambda},s)$ is a quantum algorithm that takes
in the security parameter $1^{\lambda}$, a secret $s$, and outputs a quantum
share $\ket{\mathsf{sh}_{1}}$, a classical share $\mathsf{sh}_{2}$, and a
classical verification key $\vk$.

  * •

$\mathsf{Reconstruct}_{2\text{-}2}(\ket{\mathsf{sh}_{1}},\mathsf{sh}_{2})$ is
a quantum algorithm that takes in two shares and outputs the secret $s$.

  * •

$\mathsf{Delete}_{2\text{-}2}(\ket{\mathsf{sh}_{1}})$ is a quantum algorithm
that takes in a quantum share $\ket{\mathsf{sh}_{1}}$ and outputs a deletion
certificate $\mathsf{cert}$.

  * •

$\mathsf{Verify}_{2\text{-}2}(\vk,\mathsf{cert})$ is a classical algorithm
that takes in a verification key $\vk$ and a deletion certificate
$\mathsf{cert}$ and outputs either $\top$ or $\bot$.

Beyond satisfying the standard secret sharing notions of correctness and
privacy (Definition 1) for the 2-out-of-2 access structure, the scheme should
satisfy the following properties.

  * •

Deletion correctness. For all $\lambda\in\mathbb{N}$ and $s$,

$\Pr\left[\mathsf{Verify}_{2\text{-}2}(\vk,\mathsf{cert})=\top:\begin{array}[]{r}(\ket{\mathsf{sh}_{1}},\mathsf{sh}_{2})\leftarrow\mathsf{Split}_{2\text{-}2}(1^{\lambda},s)\\\
\mathsf{cert}\leftarrow\mathsf{Delete}_{2\text{-}2}(\ket{\mathsf{sh}_{1}})\end{array}\right]=1.$

  * •

Certified deletion security. Let $\mathsf{Adv}$ be an adversary, $s$ be a
secret, and define the experiment
$2\mathsf{SS\text{-}NSCD}(1^{\lambda},\mathsf{Adv},s)$ as follows:

    * –

Sample
$(\ket{\mathsf{sh}_{1}},\mathsf{sh}_{2},\vk)\leftarrow\mathsf{Split}_{2\text{-}2}(1^{\lambda},s)$.

    * –

Run
$(\mathsf{cert},\mathcal{R})\leftarrow\mathsf{Adv}(1^{\lambda},\ket{\mathsf{sh}_{1}})$,
where $\mathcal{R}$ is an arbitrary output register.

    * –

If $\mathsf{Verify}_{2\text{-}2}(\vk,\mathsf{cert})=\top$, output
$(\mathcal{R},\mathsf{sh}_{2})$, and otherwise output $\bot$.

Then, for any unbounded adversary $\mathsf{Adv}$ and any pair of secrets
$s_{0},s_{1}$, it holds that

$\mathsf{TD}\left[2\mathsf{SS\text{-}NSCD}(1^{\lambda},\mathsf{Adv},s_{0}),2\mathsf{SS\text{-}NSCD}(1^{\lambda},\mathsf{Adv},s_{1})\right]=2^{-\Omega(\lambda)}.$

[BK23] showed the existence of a 2-out-of-2 secret sharing scheme with
certified deletion satisfying the above definition. Notice that our certified
deletion security definition requires a trace distance of
$2^{-\Omega(\lambda)}$. While the theorem from [BK23] only states a bound of
$\negl$, a quick inspection of their proof establishes that they in fact show
a bound of $2^{-\Omega(\lambda)}$.

##  4 High-Rate Seedless Quantum Extractors

In this section, we study seedless extraction of large amounts of entropy from
a quantum source. The source of entropy comes from applying a quantum Fourier
transform to a state which is “almost” a computational basis state. In
particular, the source register $\mathcal{X}$ is in superposition over vectors
with low Hamming weight, and may be arbitrarily entangled with a register
$\mathcal{A}$ that contains side-information about the source. Previously,
[ABKK23] showed that the XOR function perfectly extracts a single bit of
entropy in this setting. However, in order to extract multiple bits of
entropy, they resorted to the use of a random oracle. We also remark that the
case of _seeded_ extraction has been well-studied by, e.g. [RK05, DFL+09,
BF10].

We describe a general class of extractors that produces multiple truly random
elements of any finite field $\mathbb{F}$, even conditioned on the side-
information register $\mathcal{A}$. In the case where the finite field has
order $p^{k}$ for a prime $p$, we show that a large amount of entropy is
generated even when the quantum Fourier transform is applied by interpreting
each element $x\in\mathbb{F}_{p^{k}}$ as a vector
$\mathbf{x}\in\mathbb{F}_{p}^{k}$ and applying the transform mod $p$ to each
index (as opposed to applying the transform mod $p^{k}$ directly to the field
element). This feature allows the source to be prepared using less
entanglement in our eventual application to secret sharing.

#### Notation.

The Hamming weight $h_{\mathbb{F}}(\mathbf{v})$ of a vector
$\mathbf{v}\in\mathbb{F}^{M}$ over a finite field $\mathbb{F}$ is its number
of non-zero positions. We denote vectors $\mathbf{v}$ and matrices
$\mathbf{R}$ using bold font. Since we will be working with elements which can
be interpreted as elements of two different fields, we use
$(\cdot)_{\mathbb{F}}$ to denote that the contents of the parentheses should
be interpreted as elements and operations over $\mathbb{F}$. For example,
$(x+y)_{\mathbb{F}}$ denotes addition of $x$ and $y$ inside the field
$\mathbb{F}$. If $\mathbf{x},\mathbf{y}\in\mathbb{F}^{k}$, then
$(\mathbf{x}+\mathbf{y})_{\mathbb{F}}$ denotes vector addition. For an
extension field $\mathbb{K}$ of $\mathbb{F}$, a scalar $x\in\mathbb{K}$ can
also be interpreted as a vector $\mathbf{x}\in\mathbb{F}^{k}$. In this case,
for $x,y\in\mathbb{K}$, $(\mathbf{x}\cdot\mathbf{y})_{\mathbb{F}}$ produces a
scalar in $\mathbb{F}$. If an element can be interpreted as either a vector or
a scalar, we bold it depending on the context of the first operation applied;
for example, $(x\mathbf{y})_{\mathbb{K}}$ or
$(\mathbf{x}\cdot\mathbf{z})_{\mathbb{F}}$ for $x\in\mathbb{K}$,
$\mathbf{y}\in\mathbb{K}^{n}$, and $\mathbf{z}\in\mathbb{F}^{k}$.

######  Theorem 3.

Let $\mathbb{F}$ be a finite field of order $p^{k}$. Let
$X=\mathcal{X}_{1},\dots,\mathcal{X}_{M}$ be a register containing $M$
$\mathbb{F}$-qudits, and consider any quantum state

$\ket{\gamma}^{\mathcal{A},\mathcal{X}}=\sum_{\mathbf{u}\in\mathbb{F}^{M}:h_{\mathbb{F}}(\mathbf{u})<\frac{M-m}{2}}\ket{\psi_{\mathbf{u}}}^{\mathcal{A}}\otimes\ket{\mathbf{u}+\mathbf{w}}^{\mathcal{X}}$

for some integer $m\leq M$ and some fixed string
$\mathbf{w}\in\mathbb{F}^{M}$. Let $\mathbf{R}\in\mathbb{F}^{m\times M}$ be a
matrix such that every set of $m$ columns of $\mathbf{R}$ are linearly
independent.

Let $\rho^{\mathcal{A},\mathcal{Y}}$ be the mixed state that results from the
following procedure:

  1. 1.

Apply a quantum Fourier transform over $\mathbb{F}$’s additive group
$\mathbb{Z}_{p}^{k}$ to each register $\mathcal{X}_{i}$. In other words,
interpret $\mathcal{X}_{i}$ as a sequence of registers
$\mathcal{X}_{i,1},\dots,\mathcal{X}_{i,k}$ containing
$\mathbb{Z}_{p}$-qudits, then apply a quantum Fourier transform mod $p$ to
each $\mathcal{X}_{i,j}$.

  2. 2.

Initialize a fresh register $\mathcal{Y}$, and apply the isometry
$\ket{\mathbf{x}}^{\mathcal{X}}\mapsto\ket{\mathbf{x}}^{\mathcal{X}}\otimes\ket{\mathbf{Rx}}^{\mathcal{Y}}$.

  3. 3.

Trace out register $\mathcal{X}$.

Then

$\rho^{\mathcal{A},\mathcal{Y}}=\mathsf{Tr}^{X}[\ket{\gamma}\bra{\gamma}]\otimes\left(\frac{1}{|\mathbb{F}|^{m}}\sum_{\mathbf{y}\in\mathbb{F}^{m}}\ket{\mathbf{y}}\bra{\mathbf{y}}\right).$

######  Remark 1.

As an example, consider $\mathbb{F}$ to be the field with $2^{n}$ elements.
Note that for the source, the Hamming weight is taken over the larger field
$\mathbb{F}$, but the quantum Fourier transform is done over the individual
qubits, which in this case makes it just a Hadamard gate. The extractor $R$
operates over $\mathbb{F}$ and produces an output in $\mathbb{F}^{m}$.

###### Proof.

First, we apply the Fourier transform to $\ket{\gamma}$ to obtain

$\sqrt{|\mathbb{F}|^{-M}}\sum_{\mathbf{u}\in\mathbb{F}^{M}:h_{\mathbb{F}}(\mathbf{u})<\frac{M-m}{2}}\ket{\psi_{\mathbf{u}}}^{\mathcal{A}}\otimes\sum_{\mathbf{x}\in\mathbb{F}^{M}}\omega_{p}^{((\mathbf{u}+\mathbf{w})_{\mathbb{F}}\cdot\mathbf{x})_{\mathbb{Z}_{p}}}\ket{\mathbf{x}}^{\mathcal{X}},$

where $\omega_{p}$ is a primitive $p$’th root of unity. Next, after applying
the extractor, but before tracing out $\mathcal{X}$, the state becomes

$\displaystyle\sqrt{|\mathbb{F}|^{-M}}\sum_{\mathbf{x}\in\mathbb{F}^{M}}\left(\sum_{\mathbf{u}\in\mathbb{F}^{M}:h_{\mathbb{F}}(\mathbf{u})<\frac{M-m}{2}}\omega_{p}^{((\mathbf{u}+\mathbf{w})_{\mathbb{F}}\cdot\mathbf{x})_{\mathbb{Z}_{p}}}\ket{\psi_{\mathbf{u}}}^{\mathcal{A}}\right)\otimes\ket{\mathbf{x}}^{\mathcal{X}}\otimes\ket{\mathbf{R}\mathbf{x}}^{\mathcal{Y}}$
(3)
$\displaystyle\coloneqq\sqrt{|\mathbb{F}|^{-M}}\sum_{\mathbf{x}\in\mathbb{F}^{M}}\ket{\phi_{\mathbf{x}}}^{\mathcal{A}}\otimes\ket{\mathbf{x}}^{\mathcal{X}}\otimes\ket{\mathbf{R}\mathbf{x}}^{\mathcal{Y}}.$
(4)

Since the additive group of $\mathbb{F}$ is $\mathbb{Z}_{p}^{k}$, for every
$\mathbf{u},\mathbf{w}\in\mathbb{F}^{M}$ and
$\mathbf{x}\in\mathbb{Z}_{p}^{kM}$, we have

$((\mathbf{u}+\mathbf{w})_{\mathbb{F}}\cdot\mathbf{x})_{\mathbb{Z}_{p}}=((\mathbf{u}+\mathbf{w})_{\mathbb{Z}_{p}^{k}}\cdot\mathbf{x})_{\mathbb{Z}_{p}}=((\mathbf{u}+\mathbf{w})\cdot\mathbf{x})_{\mathbb{Z}_{p}}.$

Tracing out register $\mathcal{X}$ yields

$\displaystyle\rho^{\mathcal{A},\mathcal{Y}}$
$\displaystyle=|\mathbb{F}|^{-M}\sum_{\mathbf{x}\in\mathbb{F}^{M}}\ket{\phi_{\mathbf{x}}}\bra{\phi_{\mathbf{x}}}\otimes\ket{\mathbf{R}\mathbf{x}}\bra{\mathbf{R}\mathbf{x}}$
(5)
$\displaystyle=|\mathbb{F}|^{-M}\sum_{\begin{subarray}{c}\mathbf{y}\in\mathbb{F}^{m}\\\
\mathbf{x}\in\mathbb{F}^{M}:(\mathbf{R}\mathbf{x})_{\mathbb{F}}=\mathbf{y}\end{subarray}}\ket{\phi_{\mathbf{x}}}\bra{\phi_{\mathbf{x}}}\otimes\ket{\mathbf{y}}\bra{\mathbf{y}}$
(6)
$\displaystyle=|\mathbb{F}|^{-M}\sum_{\begin{subarray}{c}\mathbf{y}\in\mathbb{F}^{m}\\\
\mathbf{x}\in\mathbb{F}^{M}:(\mathbf{R}\mathbf{x})_{\mathbb{F}}=\mathbf{y}\end{subarray}}\left(\sum_{\begin{subarray}{c}\mathbf{u}_{1},\mathbf{u}_{2}\in\mathbb{F}^{M}:\\\
h_{\mathbb{F}}(\mathbf{u}_{1}),h_{\mathbb{F}}(\mathbf{u}_{2})\leq\frac{M-m}{2}\end{subarray}}\omega_{p}^{((\mathbf{u}_{1}+\mathbf{w})\cdot\mathbf{x})_{\mathbb{Z}_{p}}}\overline{\omega_{p}^{((\mathbf{u}_{2}+\mathbf{w})\cdot\mathbf{x})_{\mathbb{Z}_{p}}}}\ket{\phi_{\mathbf{u}_{1}}}\bra{\phi_{\mathbf{u}_{2}}}\right)\otimes\ket{\mathbf{y}}\bra{\mathbf{y}}$
(7)
$\displaystyle=\sum_{\begin{subarray}{c}\mathbf{u}_{1},\mathbf{u}_{2}\in\mathbb{F}^{M}:\\\
h_{\mathbb{F}}(\mathbf{u}_{1}),h_{\mathbb{F}}(\mathbf{u}_{2})\leq\frac{M-m}{2}\end{subarray}}\ket{\phi_{\mathbf{u}_{1}}}\bra{\phi_{\mathbf{u}_{2}}}\otimes\left(|\mathbb{F}|^{-M}\sum_{\mathbf{y}\in\mathbb{F}^{m}}\ket{\mathbf{y}}\bra{\mathbf{y}}\sum_{\mathbf{x}\in\mathbb{F}^{M}:(\mathbf{R}\mathbf{x})_{\mathbb{F}}=\mathbf{y}}\omega_{p}^{((\mathbf{u}_{1}+\mathbf{w})\cdot\mathbf{x}-(\mathbf{u}_{2}+\mathbf{w})\cdot\mathbf{x})_{\mathbb{Z}_{p}}}\right)$
(8)
$\displaystyle=\sum_{\begin{subarray}{c}\mathbf{u}_{1},\mathbf{u}_{2}\in\mathbb{F}^{M}:\\\
h_{\mathbb{F}}(\mathbf{u}_{1}),h_{\mathbb{F}}(\mathbf{u}_{2})\leq\frac{M-m}{2}\end{subarray}}\ket{\phi_{\mathbf{u}_{1}}}\bra{\phi_{\mathbf{u}_{2}}}\otimes\left(|\mathbb{F}|^{-M}\sum_{\mathbf{y}\in\mathbb{F}^{m}}\ket{\mathbf{y}}\bra{\mathbf{y}}\sum_{\mathbf{x}\in\mathbb{F}^{M}:(\mathbf{R}\mathbf{x})_{\mathbb{F}}=\mathbf{y}}\omega_{p}^{((\mathbf{u}_{1}-\mathbf{u}_{2})\cdot\mathbf{x})_{\mathbb{Z}_{p}}}\right).$
(9)

Next, we apply 3, proven below, to show that every
$\ket{\phi_{\mathbf{u}_{1}}}\bra{\phi_{\mathbf{u}_{2}}}$ term where
$\mathbf{u}_{1}\neq\mathbf{u}_{2}$ has coefficient 0. To see this, consider
any such $\mathbf{u}_{1},\mathbf{u}_{2}$ and the value
$\mathbf{u}=(\mathbf{u}_{1}-\mathbf{u}_{2})_{\mathbb{Z}_{p}}=(\mathbf{u}_{1}-\mathbf{u}_{2})_{\mathbb{F}}$.
Condition 1 is satisfied by $\mathbf{u}$ since
$\mathbf{u}_{1}\neq\mathbf{u}_{2}$. Condition 2 is satisfied since
$h_{\mathbb{F}}(\mathbf{u})\leq
h_{\mathbb{F}}(\mathbf{u}_{1})+h_{\mathbb{F}}(\mathbf{u}_{2})\leq M-m$, so
there are at least $m$ indices of $\mathbf{u}$ which are zero. Finally,
condition 3 is satisfied since any $m$ columns of $R$ are linearly
independent.

Finally, noting that if $\mathbf{u}_{1}=\mathbf{u}_{2}$, then the coefficient
of
$\ket{\phi_{\mathbf{u}_{1}}}\bra{\phi_{\mathbf{u}_{1}}}\otimes\ket{\mathbf{y}}\bra{\mathbf{y}}$
is the number of solutions to
$(\mathbf{R}\mathbf{x})_{\mathbb{F}}=\mathbf{y}$, which is
$|\mathbb{F}|^{M-m}$, we conclude that

$\displaystyle\rho^{\mathcal{A},\mathcal{Y}}$
$\displaystyle=\sum_{\mathbf{u}\in\mathbb{F}^{M}:h_{\mathbb{F}}(\mathbf{u})\leq\frac{M-m}{2}}\ket{\phi_{\mathbf{u}}}\bra{\phi_{\mathbf{u}}}\otimes\left(|\mathbb{F}|^{-m}\sum_{\mathbf{y}\in\mathbb{F}^{m}}\ket{\mathbf{y}}\bra{\mathbf{y}}\right)$
(10)
$\displaystyle=\mathsf{Tr}^{X}[\ket{\gamma}\bra{\gamma}]\otimes\left(|\mathbb{F}|^{-m}\sum_{\mathbf{y}\in\mathbb{F}^{m}}\ket{\mathbf{y}}\bra{\mathbf{y}}\right).$
(11)

∎

######  Claim 3.

Let $\mathbf{u}\in\mathbb{F}^{M}$ and $\mathbf{y}\in\mathbb{F}^{m}$, and
suppose that

  1. 1.

$\mathbf{u}_{i}\neq 0$ for some index $i$.

  2. 2.

There exists a set $J\subseteq[0,\dots,M-1]$ of size $m$ such that for every
$j\in J$, $\mathbf{u}_{j}=0$.

  3. 3.

The submatrix $\mathbf{R}_{J}$ consisting of the columns of $\mathbf{R}$
corresponding to $J$ has full rank.

Then

$\sum_{\mathbf{x}\in\mathbb{F}^{M}:(\mathbf{R}\mathbf{x})_{\mathbb{F}}=\mathbf{y}}\omega_{p}^{(\mathbf{u}\cdot\mathbf{x})_{\mathbb{Z}_{p}}}=0.$

######  Remark 2.

We note that in the case that $\mathbb{F}=\mathbb{F}_{p}$, then the above
expression actually holds for any
$\mathbf{u}\notin\mathsf{rowspan}(\mathbf{R})$, which follows from a standard
argument. The three conditions above do imply that
$\mathbf{u}\notin\mathsf{rowspan}(\mathbf{R})$, but are more restrictive. We
take advantage of the extra restrictions in order to prove that the expression
holds even in the case where $\mathbb{F}$ is an extension field of
$\mathbb{F}_{p}$.

###### Proof.

Our strategy will be to partition the affine subspace
$S_{\mathbf{y}}=\\{\mathbf{x}\in\mathbb{F}^{M}:(\mathbf{R}\mathbf{x})_{\mathbb{F}}=\mathbf{y}\\}$
into parallel lines, and then claim that the sum over each line is $0$.

To begin, define a vector $\mathbf{z}\in\mathbb{F}^{M}$ so that

  * •

$\mathbf{z}_{i}=1$,

  * •

$\mathbf{z}_{j}=0$ for all $j\notin J\cup\\{i\\}$, and

  * •

$(\mathbf{R}\mathbf{z})_{\mathbb{F}}=0^{m}$,

which is possible because the $m\times m$ submatrix $\mathbf{R}_{J}$ has full
rank. By construction, we have that for any $c\in\mathbb{F}$,

$(\mathbf{u}\cdot(c\mathbf{z})_{\mathbb{F}})_{\mathbb{Z}_{p}}=\left(\mathbf{u}_{i}\cdot(c\mathbf{z}_{i})_{\mathbb{F}}+\sum_{j\in
J}\mathbf{u}_{j}\cdot(c\mathbf{z}_{j})_{\mathbb{F}}+\sum_{j\notin
J\cup\\{i\\}}\mathbf{u}_{j}\cdot(0)_{\mathbb{F}}\right)_{\mathbb{Z}_{p}}=(\mathbf{u}_{i}\cdot\mathbf{c})_{\mathbb{Z}_{p}},$
(12)

where note that in the final expression, $\mathbf{u}_{i}$ and $\mathbf{c}$ are
interpreted as vectors in $\mathbb{Z}_{p}^{k}$.

Now, fix any $\mathbf{x}\in S_{\mathbf{y}}$ and $c\in\mathbb{F}$. Then we have
that $(\mathbf{x}+c\mathbf{z})_{\mathbb{F}}\in S_{\mathbf{y}}$, since
$(\mathbf{R}(\mathbf{x}+c\mathbf{z}))_{\mathbb{F}}=\mathbf{y}+0$. Therefore,
we can partition $S_{\mathbf{y}}$ into one-dimensional cosets (lines) of the
form $\\{\mathbf{x}+c\mathbf{z}\\}_{c\in\mathbb{F}}$.

We now show that the sum over any particular coset is $0$, i.e. that for any
$\mathbf{x}\in S_{\mathbf{y}}$,

$\sum_{c\in\mathbb{F}}\omega_{p}^{(\mathbf{u}\cdot(\mathbf{x}+c\mathbf{z})_{\mathbb{F}})_{\mathbb{Z}_{p}}}=0.$

Since the additive group of $\mathbb{F}$ is $\mathbb{Z}_{p}^{k}$, by Eq. 12 we
have that

$\displaystyle(\mathbf{u}\cdot(\mathbf{x}+c\mathbf{z})_{\mathbb{F}})_{\mathbb{Z}_{p}}$
$\displaystyle=(\mathbf{u}\cdot\mathbf{x}+\mathbf{u}\cdot(c\mathbf{z})_{\mathbb{F}})_{\mathbb{Z}_{p}}$
$\displaystyle=(\mathbf{u}\cdot\mathbf{x}+\mathbf{u}_{i}\cdot\mathbf{c})_{\mathbb{Z}_{p}}$

We now view $\mathbf{u}_{i}\in\mathbb{F}$ as a vector
$\mathbf{u}_{i}=u_{i,0},\ \dots,\ u_{i,k-1}\in\mathbb{Z}_{p}^{k}.$ In
particular, since $\mathbf{u}_{i}\neq 0$, there exists an index $t$ such that
$u_{k,t}\neq 0\in\mathbb{Z}_{p}$. By also interpreting
$\mathbf{c}\in\mathbb{F}$ as an element of $\mathbb{Z}_{p}^{k}$, we can
decompose it as
$\mathbf{c}=(\mathbf{c^{\prime}}+c_{t}\mathbf{e}_{t})_{\mathbb{Z}_{p}}$, where
$\mathbf{c^{\prime}}\in\mathbb{Z}_{p}^{k}$ is such that
$\mathbf{c}^{\prime}_{t}=0$, where $c_{t}\in\mathbb{Z}_{p}$, and where
$\mathbf{e_{t}}\in\mathbb{Z}_{p}^{k}$ is the $t$’th standard basis vector.
Therefore

$(\mathbf{u}\cdot(\mathbf{x}+c\mathbf{z})_{\mathbb{F}})_{\mathbb{Z}_{p}}=(\mathbf{u}\cdot\mathbf{x}+\mathbf{u}_{i}\cdot\mathbf{c^{\prime}}+u_{i,t}c_{t})_{\mathbb{Z}_{p}}.$

Since $u_{i,t}\neq 0$ and $\omega_{p}$ is a primitive $p$’th root of unity, we
know that $\omega_{p}^{u_{i,t}}\neq 1$ is a $p$’th root of unity. Therefore by
1,

$\displaystyle\sum_{c\in\mathbb{F}}\omega_{p}^{(\mathbf{u}\cdot(\mathbf{x}+\mathbf{c}\mathbf{z})_{\mathbb{F}})_{\mathbb{Z}_{p}}}$
$\displaystyle=\sum_{\mathbf{c^{\prime}}\in\mathbb{Z}_{p}^{k}:\mathbf{c}^{\prime}_{t}=0}\omega_{p}^{(\mathbf{u}\cdot\mathbf{x}+\mathbf{u}_{i}\cdot\mathbf{\mathbf{c}^{\prime}})_{\mathbb{Z}_{p}}}\cdot\sum_{c_{t}\in\mathbb{Z}_{p}}\left(\omega_{p}^{u_{i,t}}\right)^{c_{t}}$
(13)
$\displaystyle=\sum_{\mathbf{c}^{\prime}\in\mathbb{Z}_{p}^{k}:\mathbf{c}^{\prime}_{t}=0}\omega_{p}^{(\mathbf{u}\cdot\mathbf{x}+\mathbf{u}_{i}\cdot\mathbf{c}^{\prime})_{\mathbb{Z}_{p}}}\cdot
0$ (14) $\displaystyle=0.$ (15)

∎

##  5 Definitions of Secret Sharing with Certified Deletion

A secret sharing scheme with certified deletion augments the syntax of a
secret sharing scheme with additional algorithms to delete shares and verify
deletion certificates. We define it for general access structures. As
described in Section 3.4, an access structure
$\mathbb{S}\subseteq\mathcal{P}([n])$ for $n$ parties is a monotonic set of
sets, i.e. if $S\in\mathbb{S}$ and $S^{\prime}\supset S$, then
$S^{\prime}\in\mathbb{S}$. Any set of parties $S\in\mathbb{S}$ is authorized
to access the secret. A simple example of an access structure is the threshold
structure, where any set of at least $k$ parties is authorized to access the
secret. We denote this access structure as $(k,n)$.

######  Definition 3 (Secret Sharing with Certified Deletion).

A secret sharing scheme with certified deletion is specified by a monotone
access structure $\mathbb{S}$ over $n$ parties, and consists of four
algorithms:

  * •

$\mathsf{Split}_{\mathbb{S}}(1^{\lambda},s)$ takes in a secret $s$, and
outputs $n$ share registers $\mathcal{S}_{1},\dots,\mathcal{S}_{n}$ and a
verification key $\mathsf{vk}$.

  * •

$\mathsf{Reconstruct}_{\mathbb{S}}(\\{S_{i}\\}_{i\in P})$ takes in set of
share registers for some $P\subseteq[n]$, and outputs either $s$ or $\bot$.

  * •

$\mathsf{Delete}_{\mathbb{S}}(\mathcal{S}_{i})$ takes in a share register and
outputs a certificate of deletion $\mathsf{cert}$.

  * •

$\mathsf{Verify}_{\mathbb{S}}(\mathsf{vk},i,\mathsf{cert})$ takes in the
verification key $\mathsf{vk}$, an index $i$, and a certificate of deletion
$\mathsf{cert}$, and outputs either $\top$ (indicating accept) or $\bot$
(indicating reject).

######  Definition 4 (Correctness of Secret Sharing with Certified Deletion).

A secret sharing scheme with certified deletion must satisfy two correctness
properties:

  * •

Reconstruction Correctness. For all $\lambda\in\mathbb{N}$ and all sets
$S\in\mathbb{S}$,

$\Pr\left[\mathsf{Reconstruct}_{\mathbb{S}}(\\{\mathcal{S}_{i}\\}_{i\in
S}):(\mathcal{S}_{1},\dots,\mathcal{S}_{n},\mathsf{vk})\leftarrow\mathsf{Split}_{\mathbb{S}}(1^{\lambda},s)\right]=1.$

  * •

Deletion Correctness. For all $\lambda\in\mathbb{N}$ and all $i\in[n]$,

$\Pr\left[\mathsf{Verify}_{\mathbb{S}}(\vk,i,\mathsf{cert})=\top:\begin{array}[]{r}(\mathcal{S}_{1},\dots,\mathcal{S}_{n},\mathsf{vk})\leftarrow\mathsf{Split}_{\mathbb{S}}(1^{\lambda},s)\\\
\mathsf{cert}\leftarrow\mathsf{Delete}_{\mathbb{S}}(\mathcal{S}_{i})\end{array}\right]=1.$

The standard notion of security for secret sharing requires that no set of
unauthorized shares $S\notin\mathbb{S}$ reveals any information about the
secret (see Section 3.4). We next present our notion of _no-signaling
certified deletion security_. Here, the shares are partitioned into
unauthorized sets, and different parts of the adversary operate on each
partition, potentially deleting some number of shares from each. The different
parts of the adversary are allowed to share entanglement, but are not allowed
to signal. If the adversaries jointly produce a valid certificate for at least
one share from every authorized set, then we require that the joint residual
state of _all_ of the adversaries contains no (or negligible) information
about the secret. Observe that this notion of security is at least as strong
as the standard notion of security for secret sharing (if we relax to
statistical rather than perfect security). Indeed, if the standard notion does
not hold, and thus there is some unauthorized set $S$ that leaks information
about the secret, then the adversary would be able to win the certified
deletion game by honestly deleting every share except for those in $S$.

######  Definition 5 (No-Signaling Certified Deletion Security for Secret
Sharing).

Let $P=(P_{1},\dots,P_{\ell})$ be a partition of $[n]$, let $\ket{\psi}$ be an
$\ell$-part state on registers $\mathcal{R}_{1},\dots,\mathcal{R}_{\ell}$, and
let $\mathsf{Adv}=(\mathsf{Adv}_{1},\dots,\mathsf{Adv}_{\ell})$ be an
$\ell$-part adversary. Define the experiment
$\mathsf{SS\text{-}NSCD}_{\mathbb{S}}(1^{\lambda},P,\ket{\psi},\mathsf{Adv},s)$
as follows:

  1. 1.

Sample
$(\mathcal{S}_{1},\dots,\mathcal{S}_{n},\vk)\leftarrow\mathsf{Split}_{\mathbb{S}}(1^{\lambda},s)$.

  2. 2.

For each $t\in[\ell]$, run $(\\{\mathsf{cert}_{i}\\}_{i\in
P_{t}},\mathcal{R}_{t}^{\prime})\leftarrow\mathsf{Adv}_{t}(\\{\mathcal{S}_{i}\\}_{i\in
P_{t}},\mathcal{R}_{t})$, where $\mathcal{R}_{t}^{\prime}$ is an arbitrary
output register.

  3. 3.

If for all $S\in\mathbb{S}$, there exists $i\in S$ such that
$\mathsf{Verify}_{\mathbb{S}}(\vk,i,\mathsf{cert}_{i})=\top$, then output
$(\mathcal{R}^{\prime}_{1},\dots,\mathcal{R}^{\prime}_{\ell})$, and otherwise
output $\bot$.

A secret sharing scheme for access structure $\mathbb{S}$ has no-signaling
certified deletion security if for any “admissible” partition
$P=(P_{1},\dots,P_{\ell})$ (i.e. for all $P_{t}\in P$ and $S\in\mathbb{S}$,
$P_{t}\not\subseteq S$), any $\ell$-part state $\ket{\psi}$, any (unbounded)
$\ell$-part adversary $\mathsf{Adv}$, and any pair of secrets $s_{0},s_{1}$,

$\mathsf{TD}[\mathsf{SS\text{-}NSCD}_{\mathbb{S}}(1^{\lambda},P,\ket{\psi},\mathsf{Adv},s_{0}),\
\mathsf{SS\text{-}NSCD}_{\mathbb{S}}(1^{\lambda},P,\ket{\psi},\mathsf{Adv},s_{1})]=\negl.$

Next, we present an alternative definition which allows the adversary to start
by corrupting some unauthorized set, and then continue to adaptively delete
some shares and corrupt new parties, as long as the total set of parties
corrupted minus the set of shares deleted is unauthorized. Similarly to the
previous definition, adaptive certified deletion for secret sharing subsumes
the standard notion of security for secret sharing.

######  Definition 6 (Adaptive Certified Deletion for Secret Sharing).

Let $\mathsf{Adv}$ be an adversary with internal register $\mathcal{R}$ which
is initialized to a state $\ket{\psi}$, let $\mathbb{S}$ be an access
structure, and let $s$ be a secret. Define the experiment
$\mathsf{SS\text{-}ACD}_{\mathbb{S}}(1^{\lambda},\ket{\psi},\mathsf{Adv},s)$
as follows:

  1. 1.

Sample
$(\mathcal{S}_{1},\dots,\mathcal{S}_{n},\mathsf{vk})\leftarrow\mathsf{Split}_{\mathbb{S}}(1^{\lambda},s)$.
Initialize the corruption set $C=\emptyset$ and the deleted set $D=\emptyset$.

  2. 2.

In each round $i$, the adversary may do one of three things:

    1. (a)

End the experiment by outputting a register
$\mathcal{R}\leftarrow\mathsf{Adv}(\\{\mathcal{S}_{j}\\}_{j\in
C},\mathcal{R})$.

    2. (b)

Delete a share by outputting a certificate $\mathsf{cert}_{i}$, an index
$j_{i}\in[n]$, and register
$(\mathsf{cert}_{i},j_{i},\mathcal{R})\leftarrow\mathsf{Adv}(\\{\mathcal{S}_{j}\\}_{j\in
C},\mathcal{R})$. When the adversary chooses this option, if
$\mathsf{Verify}_{\mathbb{S}}(\mathsf{vk},j_{i},\mathsf{cert}_{i})$ outputs
$\top$, then add $j_{i}$ to $D$. Otherwise, immediately abort the experiment
and output $\bot$.

    3. (c)

Corrupt a new share by outputting an index $j_{i}\in[n]$ and register
$(j_{i},\mathcal{R})\leftarrow\mathsf{Adv}(\\{\mathcal{S}_{j}\\}_{j\in
C},\mathcal{R})$. When the adversary chooses this option, add $j_{i}$ to $C$.
If $C\backslash D\in\mathbb{S}$, immediately abort the experiment and output
$\bot$.

  3. 3.

Output $\mathcal{R}$, unless the experiment has already aborted.

A secret sharing scheme for access structure $\mathbb{S}$ has adaptive
certified deletion security if for any (unbounded) adversary $\mathsf{Adv}$,
any state $\ket{\psi}$, and any pair of secrets $(s_{0},s_{1})$,

$\mathsf{TD}[\mathsf{SS\text{-}ACD}_{\mathbb{S}}(1^{\lambda},\ket{\psi},\mathsf{Adv},s_{0}),\
\mathsf{SS\text{-}ACD}_{\mathbb{S}}(1^{\lambda},\ket{\psi},\mathsf{Adv},s_{1})]=\negl$

It will also be convenient to establish some notation for the order of the
corrupted and deleted shares. Let $c_{a}$ be the $a$’th share to be corrupted
(i.e. added to $C$) and let $d_{b}$ be the $b$’th share to be deleted (i.e.
added to $D$).

##  6 Secret Sharing with No-Signaling Certified Deletion

In this section, we’ll show how to combine any classical secret sharing scheme
$(\mathsf{CSplit}_{\mathbb{S}},\mathsf{CReconstruct}_{\mathbb{S}})$
(Definition 1) for access structure $\mathbb{S}\in\mathcal{P}([n])$ with a
2-out-of-2 secret sharing scheme with certified deletion
$(\mathsf{Split}_{2\text{-}2},\allowbreak\mathsf{Reconstruct}_{2\text{-}2},\allowbreak\mathsf{Delete}_{2\text{-}2},\allowbreak\mathsf{Verify}_{2\text{-}2})$
(Definition 2) in order to obtain a secret sharing scheme for $\mathbb{S}$
that satisfies no-signaling certified deletion security (Definition 5).

#### $\underline{\mathsf{Split}_{\mathbb{S}}(1^{\lambda},s)}$

  * •

Sample
$(\mathsf{sh}_{1},\dots,\mathsf{sh}_{n})\leftarrow\mathsf{CSplit}_{\mathbb{S}}(s)$.

  * •

Set $\kappa=\max\\{\lambda,n\\}^{2}$, and for each $i\in[n]$, sample
$(\ket{\mathsf{qsh}_{i}},\mathsf{csh}_{i},\vk_{i})\leftarrow\mathsf{Split}_{2\text{-}2}(1^{\kappa},\mathsf{sh}_{i})$.

  * •

For each $i\in[n]$, sample
$(\mathsf{csh}_{i,1},\dots,\mathsf{csh}_{i,n})\leftarrow\mathsf{CSplit}_{\mathbb{S}}(\mathsf{csh}_{i})$.

  * •

Set $\vk=(\vk_{1},\dots,\vk_{n})$, and initialize register $\mathcal{S}_{i}$
to $\ket{\mathsf{qsh}_{i}},\\{\mathsf{csh}_{j,i}\\}_{j\in[n]}.$

#### $\underline{\mathsf{Reconstruct}_{\mathbb{S}}(\\{\mathcal{S}_{i}\\}_{i\in
P})}$

  * •

Parse each register $\mathcal{S}_{i}$ as
$\ket{\mathsf{qsh}_{i}},\\{\mathsf{csh}_{j,i}\\}_{j\in[n]}.$

  * •

For each $i\in P$, compute
$\mathsf{csh}_{i}\leftarrow\mathsf{CReconstruct}_{\mathbb{S}}(\\{\mathsf{csh}_{i,j}\\}_{j\in
P})$, and output $\bot$ if the result is $\bot$.

  * •

For each $i\in P$, compute
$\mathsf{sh}_{i}\leftarrow\mathsf{Reconstruct}_{2\text{-}2}(\ket{\mathsf{qsh}_{i}},\mathsf{csh}_{i})$.

  * •

Output
$s\leftarrow\mathsf{CReconstruct}_{\mathbb{S}}(\\{\mathsf{sh}_{i}\\}_{i\in
P})$.

#### $\underline{\mathsf{Delete}_{\mathbb{S}}(\mathcal{S}_{i})}$

  * •

Parse $\mathcal{S}_{i}$ as
$\ket{\mathsf{qsh}_{i}},\\{\mathsf{csh}_{j,i}\\}_{j\in[n]}$ and output
$\mathsf{cert}\leftarrow\mathsf{Delete}_{2\text{-}2}(\ket{\mathsf{qsh}_{i}})$.

#### $\underline{\mathsf{Verify}_{\mathbb{S}}(\vk,i,\mathsf{cert})}$

  * •

Parse $\vk=(\vk_{1},\dots,\vk_{n})$ and output
$\mathsf{Verify}_{2\text{-}2}(\vk_{i},\mathsf{cert})$.

Figure 1: Secret sharing with no-signaling certified deletion security for any
access structure $\mathbb{S}$.

######  Theorem 4.

The construction given in Fig. 1 satisfies no-signaling certified deletion
security (Definition 5).

###### Proof.

Let $\mathsf{Adv}=(\mathsf{Adv}_{1},\dots,\mathsf{Adv}_{\ell})$ be any
$\ell$-part adversary that partitions the shares using an admissible partition
$P=(P_{1},\dots,P_{\ell})$ and is initialized with the $\ell$-part state
$\ket{\psi}$ on registers $\mathcal{R}_{1},\dots,\mathcal{R}_{\ell}$. Let
$s_{0},s_{1}$ be any two secrets, and assume for contradiction that

$\mathsf{TD}[\mathsf{SS\text{-}NSCD}_{\mathbb{S}}(1^{\lambda},P,\ket{\psi},\mathsf{Adv},s_{0}),\
\mathsf{SS\text{-}NSCD}_{\mathbb{S}}(1^{\lambda},P,\ket{\psi},\mathsf{Adv},s_{1})]=\mathsf{nonnegl}(\lambda).$

Now, for $s\in\\{s_{0},s_{1}\\}$, define a hybrid $\mathcal{H}_{1}(s)$ as
follows.

$\mathcal{H}_{1}(s)$

  1. 1.

Sample $C\leftarrow\mathcal{P}([n])$.

  2. 2.

Sample
$(\mathsf{sh}_{1},\dots,\mathsf{sh}_{n})\leftarrow\mathsf{CSplit}_{\mathbb{S}}(s)$.

  3. 3.

Set $\kappa=\max\\{\lambda,n\\}^{2}$, and for each $i\in[n]$, sample
$(\ket{\mathsf{qsh}_{i}},\mathsf{csh}_{i},\vk_{i})\leftarrow\mathsf{Split}_{2\text{-}2}(1^{\kappa},\mathsf{sh}_{i})$.

  4. 4.

For each $i\in[n]$, sample
$(\mathsf{csh}_{i,1},\dots,\mathsf{csh}_{i,n})\leftarrow\mathsf{CSplit}_{\mathbb{S}}(\mathsf{csh}_{i})$.

  5. 5.

Set $\vk=(\vk_{1},\dots,\vk_{n})$, and initialize register $\mathcal{S}_{i}$
to $\ket{\mathsf{qsh}_{i}},\\{\mathsf{csh}_{j,i}\\}_{j\in[n]}.$

  6. 6.

For each $t\in[\ell]$, run $(\\{\mathsf{cert}_{i}\\}_{i\in
P_{t}},\mathcal{R}^{\prime}_{t})\leftarrow\mathsf{Adv}_{t}(\\{\mathcal{S}_{i}\\}_{i\in
P_{t}},\mathcal{R}_{t})$.

  7. 7.

Let
$C^{*}\coloneqq\\{i:\mathsf{Verify}_{2\text{-}2}(\vk_{i},i,\mathsf{cert}_{i})=\top\\}$.
Output $(\mathcal{R}^{\prime}_{1},\dots,\mathcal{R}^{\prime}_{\ell})$ if
$C=C^{*}$ and $[n]\setminus C^{*}\notin\mathbb{S}$, and otherwise output
$\bot$.

That is, $\mathcal{H}_{1}(s)$ is the same as
$\mathsf{SS\text{-}NSCD}_{\mathbb{S}}(1^{\lambda},P,\ket{\psi},\mathsf{Adv},s)$
except that $\mathcal{H}_{1}(s)$ makes a uniformly random guess $C$ for the
subset of shares for which the adversary produces a valid deletion
certificate, and aborts if this guess is incorrect.

######  Claim 4.

$\mathsf{TD}\left[\mathcal{H}_{1}(s_{0}),\mathcal{H}_{1}(s_{1})\right]=\mathsf{nonnegl}(\lambda)\cdot
2^{-n}.$

###### Proof.

This follows directly from the fact that $\mathcal{H}_{1}(s)$’s guess for $C$
is correct with probability $1/2^{n}$, and, conditioned on the guess being
correct, $\mathcal{H}_{1}(s)$ is identical to
$\mathsf{SS\text{-}NSCD}_{\mathbb{S}}(1^{\lambda},P,\ket{\psi},\mathsf{Adv},s)$.
∎

Now, for $s\in\\{s_{0},s_{1}\\}$ and $k\in[0,\dots,n]$, define a sequence of
hybrids $\mathcal{H}_{2,k}(s)$ as follows.

$\mathcal{H}_{2,k}(s)$

  1. 1.

Sample $C\leftarrow\mathcal{P}([n])$.

  2. 2.

Sample
$(\mathsf{sh}_{1},\dots,\mathsf{sh}_{n})\leftarrow\mathsf{CSplit}_{\mathbb{S}}(s)$.

  3. 3.

Set $\kappa=\max\\{\lambda,n\\}^{2}$ and for each $i\in[n]$, if $i\leq k$ and
$i\in C$, sample
$(\ket{\mathsf{qsh}_{i}},\mathsf{csh}_{i},\vk_{i})\leftarrow\mathsf{Split}_{2\text{-}2}(1^{\kappa},\bot)$,
and otherwise sample
$(\ket{\mathsf{qsh}_{i}},\mathsf{csh}_{i},\vk_{i})\leftarrow\mathsf{Split}_{2\text{-}2}(1^{\kappa},\mathsf{sh}_{i})$.

  4. 4.

For each $i\in[n]$, sample
$(\mathsf{csh}_{i,1},\dots,\mathsf{csh}_{i,n})\leftarrow\mathsf{CSplit}_{\mathbb{S}}(\mathsf{csh}_{i})$.

  5. 5.

Set $\vk=(\vk_{1},\dots,\vk_{n})$, and initialize register $\mathcal{S}_{i}$
to $\ket{\mathsf{qsh}_{i}},\\{\mathsf{csh}_{j,i}\\}_{j\in[n]}$.

  6. 6.

For each $t\in[\ell]$, run $(\\{\mathsf{cert}_{i}\\}_{i\in
P_{t}},\mathcal{R}^{\prime}_{t})\leftarrow\mathsf{Adv}_{t}(\\{\mathcal{S}_{i}\\}_{i\in
P_{t}},\mathcal{R}_{t})$.

  7. 7.

Let
$C^{*}\coloneqq\\{i:\mathsf{Verify}_{2\text{-}2}(\vk_{i},i,\mathsf{cert}_{i})=\top\\}$.
Output $(\mathcal{R}^{\prime}_{1},\dots,\mathcal{R}^{\prime}_{\ell})$ if
$C=C^{*}$ and $[n]\setminus C^{*}\notin\mathbb{S}$, and otherwise output
$\bot$.

First, note that $\mathcal{H}_{1}(s_{0})=\mathcal{H}_{2,0}(s_{0})$ and
$\mathcal{H}_{1}(s_{1})=\mathcal{H}_{2,0}(s_{1})$. Next, we show the following
claim.

######  Claim 5.

$\mathcal{H}_{2,n}(s_{0})\equiv\mathcal{H}_{2,n}(s_{1})$.

###### Proof.

In each experiment, if the output is not $\bot$, then we know that
$[n]\setminus C$ is an unauthorized set. Moreover, the experiments do not
depend on the information $\\{\mathsf{sh}_{i}\\}_{i\in C}$. Thus, the claim
follows by the perfect privacy of
$(\mathsf{CSplit}_{\mathbb{S}},\mathsf{CReconstruct}_{\mathbb{S}})$, which
implies that

$\displaystyle\\{\\{\mathsf{sh}_{i}\\}_{i\in
C\setminus[n]}:(\mathsf{sh}_{1},\dots,\mathsf{sh}_{n})\leftarrow\mathsf{CSplit}_{\mathbb{S}}(s_{0})\\}$
$\displaystyle~{}~{}~{}~{}\equiv\\{\\{\mathsf{sh}_{i}\\}_{i\in
C\setminus[n]}:(\mathsf{sh}_{1},\dots,\mathsf{sh}_{n})\leftarrow\mathsf{CSplit}_{\mathbb{S}}(s_{1})\\}.$

∎

Finally, we show the following claim.

######  Claim 6.

For $s\in\\{s_{0},s_{1}\\}$ and $k\in[n]$, it holds that
$\mathsf{TD}\left[\mathcal{H}_{2,k-1}(s),\mathcal{H}_{2,k}(s)\right]=2^{-\Omega(\kappa)}.$

###### Proof.

The only difference between these hybrids is that if $k\in C$, we switch
$\mathsf{sh}_{k}$ to $\bot$ in the third step. So, suppose that $k\in C$, and
consider the following reduction to the certified deletion security
(Definition 2) of
$(\mathsf{Split}_{2\text{-}2},\allowbreak\mathsf{Reconstruct}_{2\text{-}2},\allowbreak\mathsf{Delete}_{2\text{-}2},\allowbreak\mathsf{Verify}_{2\text{-}2})$.
This experiment is parameterized by a bit $b$ which determines which one of
two secrets the certified deletion challenger will share.

  * •

The reduction samples $C\leftarrow\mathcal{P}([n])$ and
$(\mathsf{sh}_{1},\dots,\mathsf{sh}_{n})\leftarrow\mathsf{CSplit}_{\mathbb{S}}(s)$,
and sends $\\{\mathsf{sh}_{k},\bot\\}$ to the challenger.

  * •

The challenger samples
$(\ket{\mathsf{qsh}_{k}},\mathsf{csh}_{k},\vk_{k})\leftarrow\mathsf{Split}_{2\text{-}2}(1^{\kappa},\mathsf{sh}_{k})$
if $b=0$ or
$(\ket{\mathsf{qsh}_{k}},\mathsf{csh}_{k},\vk_{k})\leftarrow\mathsf{Split}_{2\text{-}2}(1^{\kappa},\bot)$
if $b=1$, and sends $\ket{\mathsf{qsh}_{k}}$ to the reduction.

  * •

For each $i\in[n]\setminus\\{k\\}$, if $i<k$ and $i\in C$, the reduction
samples
$(\ket{\mathsf{qsh}_{i}},\mathsf{csh}_{i},\vk_{i})\leftarrow\mathsf{Split}_{2\text{-}2}(1^{\kappa},\bot)$,
and otherwise samples
$(\ket{\mathsf{qsh}_{i}},\mathsf{csh}_{i},\vk_{i})\leftarrow\mathsf{Split}_{2\text{-}2}(1^{\kappa},\mathsf{sh}_{i})$.

  * •

Let $t^{*}\in[\ell]$ be such that $k\in P_{t^{*}}$. For each
$i\in[n]\setminus\\{k\\}$, the reduction samples
$(\mathsf{csh}_{i,1},\dots,\mathsf{csh}_{i,n})\leftarrow\mathsf{CSplit}_{\mathbb{S}}(\mathsf{csh}_{i})$.
Next, the reduction samples $\\{\mathsf{csh}_{k,i}\\}_{i\in
P_{t^{*}}}\leftarrow\mathsf{Sim}(P_{t^{*}})$, where $\mathsf{Sim}$ is the
simulator guaranteed by the privacy of
$(\mathsf{CSplit}_{\mathbb{S}},\mathsf{CReconstruct}_{\mathbb{S}})$.

  * •

For each $i\in P_{t^{*}}$, initialize register $\mathcal{S}_{i}$ to
$\ket{\mathsf{qsh}_{i}},\\{\mathsf{csh}_{j,i}\\}_{j\in[n]}$.

  * •

The reduction runs $(\\{\mathsf{cert}_{i}\\}_{i\in
P_{t^{*}}},\mathcal{R}^{\prime}_{t^{*}})\leftarrow\mathsf{Adv}_{t^{*}}(\\{\mathcal{S}_{i}\\}_{i\in
P_{t^{*}}},\mathcal{R}_{t^{*}})$, and sends $\mathsf{cert}_{k}$ to the
challenger.

  * •

The challenger checks whether
$\mathsf{Verify}_{2\text{-}2}(\vk_{k},\mathsf{cert}_{k})=\top$. If so, the
challenger returns $\mathsf{csh}_{k}$, and otherwise the experiment aborts and
outputs $\bot$.

  * •

The reduction samples $\\{\mathsf{csh}_{k,i}\\}_{i\in[n]\setminus P_{t^{*}}}$
conditioned on the joint distribution of
$(\mathsf{csh}_{k,1},\dots,\mathsf{csh}_{k,n})$ being identical to
$\mathsf{CSplit}_{\mathbb{S}}(\mathsf{csh}_{k})$. This is possible due to the
guarantee of $\mathsf{Sim}(P_{t^{*}})$, that is,

$\displaystyle\left\\{\\{\mathsf{csh}_{k,i}\\}_{i\in
P_{t^{*}}}:(\mathsf{csh}_{k,1},\dots,\mathsf{csh}_{k,n})\leftarrow\mathsf{CSplit}_{\mathbb{S}}(\mathsf{csh}_{k})\right\\}$
$\displaystyle~{}~{}~{}~{}\equiv\left\\{\\{\mathsf{csh}_{k,i}\\}_{i\in
P_{t^{*}}}:\\{\mathsf{csh}_{k,i}\\}_{i\in
P_{t^{*}}}\leftarrow\mathsf{Sim}(P_{t^{*}})\right\\}.$

  * •

For each $i\in[n]\setminus P_{t^{*}}$, the reduction initializes register
$\mathcal{S}_{i}$ to
$\ket{\mathsf{qsh}_{i}},\\{\mathsf{csh}_{j,i}\\}_{j\in[n]}$.

  * •

For each $t\in[\ell]\setminus\\{t^{*}\\}$, run $(\\{\mathsf{cert}_{i}\\}_{i\in
P_{t}},\mathcal{R}^{\prime}_{t})\leftarrow\mathsf{Adv}_{t}(\\{\mathcal{S}_{i}\\}_{i\in
P_{t}},\mathcal{R}_{t})$.

  * •

Let
$C^{*}\coloneqq\\{i:\mathsf{Verify}_{2\text{-}2}(\vk_{i},i,\mathsf{cert}_{i})=\top\\}$.
The reduction outputs
$(\mathcal{R}^{\prime}_{1},\dots,\mathcal{R}^{\prime}_{\ell})$ if $C=C^{*}$
and $[n]\setminus C^{*}\notin\mathbb{S}$, and otherwise outputs $\bot$.

Observe that in the case $b=0$, the output of this experiment is identical to
$\mathcal{H}_{2,k-1}(s)$ while if $b=1$, the output of this experiment is
identical to $\mathcal{H}_{2,k}(s)$. Thus, the claim follows from the
certified deletion security of
$(\mathsf{Split}_{2\text{-}2},\mathsf{Reconstruct}_{2\text{-}2},\mathsf{Delete}_{2\text{-}2},\mathsf{Verify}_{2\text{-}2})$.

∎

Thus, by combining 5 and 6, we have that

$\mathsf{TD}\left[\mathcal{H}_{1}(s_{0}),\mathcal{H}_{1}(s_{1})\right]=2n\cdot
2^{-\Omega(\kappa)}\leq 2^{-\Omega(\\{\max\\{\lambda,n\\}^{2}\\})}.$

However, this violates 4, since

$2^{-\Omega(\\{\max\\{\lambda,n\\}^{2}\\})}<\mathsf{nonnegl}(\lambda)\cdot
2^{-n},$

which completes the proof.

∎

##  7 Threshold Secret Sharing with Adaptive Certified Deletion

In this section, we show how to construct a secret sharing scheme for
threshold access structures that satisfies adaptive certified deletion
(Definition 6).

###  7.1 Construction

Our construction is given in Figure 3, which uses a set of parameters
described in Figure 2. We provide some intuition about the parameter settings
here.

The secret is encoded in a polynomial $f$ of degree $p$. For security, we need
$p$ to be at least as large as the number of points of $f$ that the adversary
can learn. At most, the adversary can hold up to $k-1$ intact shares and the
residual states of $n-k+1$ deleted shares. Each of the $k-1$ intact shares
contains $t^{\prime}$ evaluations of $f$. Additionally, the adversary may
retain some small amount of information about each of the deleted shares. We
upper bound the retained information by a parameter $\ell$ for each share.
This gives the adversary a maximum of

$(k-1)t^{\prime}+(n-k+1)\ell$

evaluations of $f$, which becomes the minimum safe setting for $p$.

Each share will also include a number of “check positions”, which contain
Fourier basis states that are used for verification of deletion. The number of
check positions $r$ and upper bound $\ell$ are set roughly so that with
overwhelming probability, the adversary can retain no more than $\ell$
evaluations of $f$ when it deletes a share (more precisely, the adversary may
retain a _superposition_ over potentially different sets of $\ell$
evaluations). The reader may find it useful to think of $\ell$ as being the
maximum number of unexamined positions in a classical string $x$ when an
adversary successfully creates a string $y$ that matches $x$ on $r$ random
verification indices. Finally, the total size $t$ of each share is set so that
$k$ shares contain less than $(kt-p)/2$ check positions, which is the maximum
number of errors that can be corrected in $kt$ evaluations of a polynomial of
degree $p$ (see Section 3.3).

The construction in Figure 3 uses the following parameters.666The parameters
provided here are slightly looser than necessary, to facilitate easier
inspection. We present a tighter set of parameters in Figure 4.

  * •

Each share consists of $t$ total $\mathbb{K}$-registers, where

$t=(k+1)r\left(1+\frac{(n-k+1)\log(\lambda)}{\lambda}\right)+1$

  * •

A share is divided into $r$ check indices and $t^{\prime}=t-r$ data indices,
where

$r=(\lambda+(n-k+1)\log(\lambda))^{2}$

  * •

$\ell$ intuitively represents an upper bound on the amount of information
which is not destroyed when an adversary generates a valid deletion
certificate for a share.

$\ell=t\frac{\log(\lambda)}{\sqrt{r}}$

See the proof of Lemma 3 for a more precise usage of $\ell$.

  * •

The secret will be encoded in a polynomial of degree

$p=(k-1)t^{\prime}+(n-k+1)\ell$

Figure 2: Parameters for Secret Sharing with Adaptive Certified Deletion

Parameters: Let $\mathbb{F}_{2}$ be the binary field and let $\mathbb{K}$ be
the field with $2^{\lceil\log_{2}(nt+1)\rceil}$ elements. See Figure 2 for
descriptions and settings of the parameters $t$, $t^{\prime}$, $r$, $\ell$,
and $p$.

#### $\underline{\mathsf{Split}_{(k,n)}(1^{\lambda},s)}$

  * •

Sample a random polynomial $f$ with coefficients in $\mathbb{K}$ and degree
$p$ such that $f(0)=s$.

  * •

For each $i\in[n]$:

    1. 1.

Sample a random set of indices $J_{i}\subset[t]$ of size $t^{\prime}=t-r$.

    2. 2.

For each $j\in J_{i}$, set $\ket{\psi_{i,j}}=\ket{f(it+j)}$. These are the
$t^{\prime}$ data positions.

    3. 3.

For each $j\in[t]\backslash J_{i}$, sample a uniform element
$y_{i,j}\leftarrow\mathbb{K}$ and set
$\ket{\psi_{i,j}}=H^{\otimes\lceil\log_{2}(n+1)\rceil}\ket{y_{i,j}}$. These
are the $r$ check positions.

    4. 4.

Initialize register $\mathcal{S}_{i}$ to
$\bigotimes_{j=1}^{t}\ket{\psi_{i,j}}$.

  * •

Set $\vk=\\{J_{i},\\{y_{i,j}\\}_{j\in[t]\backslash J_{i}}\\}_{i\in[n]}$.

####
$\underline{\mathsf{Reconstruct}_{(k,n)}(1^{\lambda},\\{\mathcal{S}_{i}\\}_{i\in
P})}$

  * •

If $|P|<k$, output $\bot$. Otherwise, set $P^{\prime}$ to be any $k$ shares in
$P$.

  * •

For each $i\in P^{\prime}$, measure $\mathcal{S}_{i}$ in the computational
basis to obtain $y_{i}=(y_{i,1},\dots,y_{i,t})\in\mathbb{K}^{t}$.

  * •

Compute $f\leftarrow\mathsf{Correct}_{\mathbb{K},p}(\\{(it+j,y_{i,j})\\}_{i\in
P^{\prime},j\in[t]})$, as defined in Section 3.3.

  * •

Output $f(0)$.

#### $\underline{\mathsf{Delete}_{(k,n)}(1^{\lambda},\mathcal{S}_{i})}$

  * •

Parse $\mathcal{S}_{i}$ as a sequence of $t\lceil\log_{2}(n+1)\rceil$ single
qubit registers, measure each qubit register in Hadamard basis and output the
result $\mathsf{cert}$.

####
$\underline{\mathsf{Verify}_{(k,n)}(1^{\lambda},\mathsf{vk},i,\mathsf{cert})}$

  * •

Parse $\mathsf{vk}=\\{J_{i},\\{y_{i,j}\\}_{j\in[t]\backslash
J_{i}}\\}_{i\in[n]}$, and parse $\mathsf{cert}\in\mathbb{K}^{t}$ as a sequence
of $t$ elements of $\mathbb{K}$. Output $\top$ if $\mathsf{cert}_{j}=y_{i,j}$
for every $j\in J_{i}$, and $\bot$ otherwise.

Figure 3: Construction for Secret Sharing with Adaptive Certified Deletion

######  Theorem 5.

There exists secret sharing for threshold access structures which satisfies
adaptive certified deletion.

###### Proof.

The construction is given in Figure 3. Deletion correctness is apparent from
inspection of the construction. We prove reconstruction correctness in Lemma 2
and adaptive certified deletion security in Lemma 3. ∎

######  Lemma 2.

The construction in Figure 3 using parameters from Figure 2 has reconstruction
correctness.

###### Proof.

The set $\\{(it+j,y_{i,j})\\}_{i\in P^{\prime},j\in[t]}$ contains $kt$ pairs
which were obtained by measuring $k$ shares. As mentioned in Section 3.3, if
all but $e<(kt-p)/2$ of these pairs $(it+j,y_{i,j})$ satisfy
$y_{i,j}=f(it+j)$, then $\mathsf{Correct}_{\mathbb{K},p}$ recovers the
original polynomial $f$, where $f(0)=s$. The only points which do not satisfy
this are the check positions, of which there are $r$ per share, for a total of
$kr$. Therefore for correctness, we require that

$\displaystyle 2kr$ $\displaystyle<kt-p$ (16)
$\displaystyle=kt-(k-1)(t-r)-(n-k+1)\ell$ (17)
$\displaystyle=t+(k-1)r-(n-k+1)\ell$ (18)

Therefore $t-(n-k+1)\ell>(k+1)r$. Substituting
$\ell=t\frac{\log(\lambda)}{\sqrt{r}}$ yields

$t\left(1-(n-k+1)\frac{\log(\lambda)}{\sqrt{r}}\right)>(k+1)r$ (19)
$\displaystyle t$
$\displaystyle>(k+1)r\frac{1}{1-(n-k+1)\frac{\log(\lambda)}{\sqrt{r}}}$ (20)
$\displaystyle=(k+1)r\frac{\sqrt{r}}{\sqrt{r}-(n-k+1)\log(\lambda)}$ (21)
$\displaystyle=(k+1)r\left(1+\frac{(n-k+1)\log(\lambda)}{\sqrt{r}-(n-k+1)\log(\lambda)}\right)$
(22)
$\displaystyle=(k+1)r\left(1+\frac{(n-k+1)\log(\lambda)}{\lambda+(n-k+1)\log(\lambda)-(n-k+1)\log(\lambda)}\right)$
(23) $\displaystyle=(k+1)r\left(1+\frac{(n-k+1)\log(\lambda)}{\lambda}\right)$
(24)

Note that Equation 20 requires that
$\left(1-(n-k+1)t\frac{\log(\lambda)}{\sqrt{r}}\right)>0$. Since the number of
check positions is $r=(\lambda+(n-k+1)\log(\lambda))^{2}$, we have

$\displaystyle 1-(n-k+1)\frac{\log(\lambda)}{\lambda+(n-k+1)\log(\lambda)}$
$\displaystyle>1-\frac{(n-k+1)\log(\lambda)}{(n-k+1)\log(\lambda)}=0$ (25)

Finally, observe that the choice of parameters in the construction satisfies
these constraints. ∎

###  7.2 Proof of Security

Recall that $c_{a}$ is the $a$’th share to be corrupted (i.e. added to $C$)
and $d_{b}$ is the $b$’th share to be deleted (i.e. added to $D$). Observe
that if $c_{k-1+b}$ is corrupted before $d_{b}$ is deleted, then $C\backslash
D$ has size $\geq k$ and is authorized, so $\mathsf{SS\text{-}ACD}_{(k,n)}$
would abort.

######  Lemma 3.

The construction in Figure 3 using parameters from Figure 2 satisfies adaptive
certified deletion for threshold secret sharing.

We begin by defining a projector which will be useful for reasoning about how
many data indices were _not_ destroyed when an adversary produces a valid
certificate for a share $i$. A certificate $\mathsf{cert}_{i}$ for share $i$
can be parsed as $t$ elements $\mathsf{cert}_{i,1},\dots,\mathsf{cert}_{t,i}$
of $\mathbb{K}$. Denote
$\mathsf{cert}_{i}^{\prime}=(\mathsf{cert}_{i,j})_{j\in J_{i}}$ to be the
subtuple of elements belonging to data indices. For any certificate
$\mathsf{cert}$, we define the projector777This projector defines the
“deletion predicate” mentioned in the technical overview (Section 2.2).

$\Pi_{\mathsf{cert}}=\sum_{\mathbf{u}\in\mathbb{K}^{t^{\prime}}:h_{\mathbb{K}}(\mathbf{u})<\ell/2}H^{\otimes
t^{\prime}\lceil\log_{2}(n+1)\rceil}\ket{\mathbf{u}+\mathbf{\mathsf{cert}}^{\prime}}\bra{\mathbf{u}+\mathbf{\mathsf{cert}}^{\prime}}H^{\otimes
t^{\prime}\lceil\log_{2}(n+1)\rceil}$

Note that $H$ is the Hadamard gate, i.e. it implements a quantum Fourier
transform over the binary field $\mathbb{F}_{2}$, and that the Hamming weight
is taken over $\mathbb{K}$.

Let $\mathsf{Adv}$ be any adversary which is initialized with a state
$\ket{\psi}$ on register $\mathcal{R}$. For $s\in\\{s_{0},s_{1}\\}$, define
the following $n-k+3$ hybrid experiments, where $\mathcal{H}_{0}(s)$ is the
original $\mathsf{SS\text{-}ACD}(1^{\lambda},\ket{\psi},\mathsf{Adv},s)$
experiment.

$\mathcal{H}_{1}(s)$

In $\mathcal{H}_{1}(s)$, we sample the shares lazily using polynomial
interpolation.

  1. 1.

For each share $i$, sample the set of data indices $J_{i}\subset[t]$. Then for
every share $i$ and every check position $j\in[t]\backslash J_{i}$, sample the
check position $\ket{\psi_{i,j}}$ as in $\mathcal{H}_{0}(s)$.

  2. 2.

For each share $i$, divide the data indices $J_{i}$ into a left set
$J_{i}^{L}$ of size $\ell$ and a right set $J_{i}^{R}$ of size
$t^{\prime}-\ell$. For each $j\in J_{i}^{L}$, sample
$f(it+j)\leftarrow\mathbb{K}$ uniformly at random.

  3. 3.

Until $k-1$ shares are corrupted, i.e. $|C|=k-1$, run
$\mathsf{Adv}(\\{S_{j}\\}_{j\in C},\mathcal{R})$ as in
$\mathsf{SS\text{-}ACD}$, with the following exception. Whenever
$\mathsf{Adv}$ corrupts a new share by outputting $(c_{a},\mathcal{R})$,
finish preparing share $c_{a}$ by sampling $f(c_{a}t+j)\leftarrow\mathbb{K}$
uniformly at random for every $j\in J_{c_{i}}^{R}$.

At the end of this step, exactly $p=(k-1)t^{\prime}+(n-k+1)\ell$ points of $f$
have been determined, in addition to $f(0)=s$. This uniquely determines $f$.

  4. 4.

Continue to run $\mathsf{Adv}(\\{S_{j}\\}_{j\in C},\mathcal{R})$ as in
$\mathsf{SS\text{-}ACD}$, with the following exception. Whenever
$\mathsf{Adv}$ corrupts a new share by outputting $(c_{k-1+b},\mathcal{R})$,
finish preparing $c_{k-1+b}$ by interpolating the points in
$J_{c_{k-1+b}}^{R}$ using share $d_{b}$ and any other set of $p-t^{\prime}$
points that have already been determined on $f$. Specifically, let

$\mathsf{Int}_{k-1+b}\subset\\{0\\}\cup\bigcup_{m\in C}\\{mt+j:j\in
J_{m}\\}\cup\bigcup_{m\notin C}\\{mt+j:j\in J_{m}^{L}\\}$

be any set of $p+1$ indices to be used in the interpolation, such that

$\\{d_{b}t+j:j\in J_{d_{b}}\\}\subset\mathsf{Int}_{k-1+b}$

For each $j\in J_{c_{k-1+b}}^{R}$, compute

$f(c_{k-1+b}t+j)\leftarrow\mathsf{Interpolate}_{p}\left(c_{k-1+b}t+j,\\{(m,f(m)):m\in\mathsf{Int}_{k-1+b}\\}\right)$

See Section 3.3 for the definition of $\mathsf{Interpolate}$.

Note that if $\mathsf{SS\text{-}ACD}$ does not abort in a round, $|C\backslash
D|\leq k-1$. In the round where $\mathsf{Adv}$ corrupts $c_{k-1+i}$,
$|C|=k-1+i$, so $d_{i}$ has already been determined.

$\mathcal{H}_{2}(s)$

In $\mathcal{H}_{2}(s)$, we purify the share sampling using a register
$\mathcal{C}=(\mathcal{C}_{1},\dots,\mathcal{C}_{n})$ which is held by the
challenger. The challenger will maintain a copy of share $i$ in register
$\mathcal{C}_{i}=(\mathcal{C}_{i,1},\dots,\mathcal{C}_{i,t})$. Both
$\mathcal{S}$ and $\mathcal{C}$ are initialized to $\ket{0}$ at the beginning
of the experiment.

  1. 1.

For each share $i$, sample the set of data indices $J_{i}\subset[t]$. Then for
every share $i$ and every check position $j\in[t]\backslash J_{i}$, prepare
the state

$\propto\sum_{y\in\mathbb{K}}\ket{y}^{\mathcal{S}_{i,j}}\otimes\ket{y}^{\mathcal{C}_{i,j}}$

Measure $\mathcal{C}_{i,j}$ in the Hadamard basis to obtain $y_{i,j}$ for the
verification key.

  2. 2.

Divide each $J_{i}$ into $J_{i}^{L}$ and $J_{i}^{R}$ as in
$\mathcal{H}_{1}(s)$. For each $j\in J_{i}^{L}$, prepare the state

$\propto\sum_{y\in\mathbb{K}}\ket{y}^{\mathcal{S}_{i,j}}\otimes\ket{y}^{\mathcal{C}_{i,j}}$

  3. 3.

Until $k-1$ shares are corrupted, i.e. $|C|=k-1$, run
$\mathsf{Adv}(\\{S_{j}\\}_{j\in C},\mathcal{R})$ as in
$\mathsf{SS\text{-}ACD}$, with the following exception. Whenever
$\mathsf{Adv}$ corrupts a new share by outputting $(c_{a},\mathcal{R})$, for
every $j\in J_{c_{a}}^{R}$ prepare the state

$\propto\sum_{y\in\mathbb{K}}\ket{y}^{\mathcal{S}_{c_{a},j}}\otimes\ket{y}^{\mathcal{C}_{c_{a},j}}$

  4. 4.

Continue to run $\mathsf{Adv}(\\{S_{j}\\}_{j\in C},\mathcal{R})$ as in
$\mathsf{SS\text{-}ACD}$, with the following exception whenever $\mathsf{Adv}$
corrupts a new share by outputting $(c_{k-1+b},\mathcal{R})$. Let
$\mathsf{Int}_{k-1+b}$ be the set of indices to be used in interpolation for
share $c_{k-1+b}$, as in $\mathcal{H}_{1}(s)$. For each $j\in J_{c_{k-1+b}}$,
compute

$\mathcal{C}_{c_{k-1+b},j}\leftarrow\mathsf{Interpolate}_{p}\left(c_{k-1+b}t+j,\left(mt+j,\mathcal{S}_{m,j}\right)_{mt+j\in\mathsf{Int}_{k-1+b}}\right)$

Finally, copy $\mathcal{C}_{c_{k-1+b},j}$ into $\mathcal{S}_{c_{k-1+b},j}$ in
the computational basis, i.e. perform a controlled NOT operation with source
register $\mathcal{C}_{c_{k-1+b},j}$ and target register
$\mathcal{S}_{c_{k-1+b},j}$.

We emphasize that the timing of initializing each $\mathcal{S}_{i,j}$ is the
same as in $\mathcal{H}_{1}(s)$. Note that since $\mathcal{H}_{2}(s)$ outputs
either $\bot$ or $\mathsf{Adv}$’s view, register $\mathcal{C}$ never appears
in the output of the experiment.

$\mathcal{H}_{2+i}(s)$ for $i\in[n-k+1]$

The only difference between $\mathcal{H}_{2+i}$ and $\mathcal{H}_{3+i}$ is
that when the $i$’th share $d_{i}$ is deleted in $\mathcal{H}_{3+i}$ (i.e. $D$
reaches size $i$), the challenger performs a “deletion predicate” measurement
on register $\mathcal{C}_{d_{i}}$. Specifically, let $\mathsf{cert}_{d_{i}}$
be the certificate output by $\mathsf{Adv}$ for share $d_{i}$. Immediately
after verifying $\mathsf{cert}_{d_{i}}$ and adding $d_{i}$ to $D$, the
challenger measures the data positions in register $\mathcal{C}_{d_{i}}$ (i.e.
register $(\mathcal{C}_{d_{i},j})_{j\in J_{d_{i}}}$) with respect to the
binary projective measurement
$\\{\Pi_{\mathsf{cert}_{k+i}},I-\Pi_{\mathsf{cert}_{k+i}}\\}$. If the
measurement result is “reject” (i.e. $I-\Pi_{\mathsf{cert}_{k+i}}$),
immediately output $\bot$ in the experiment. The difference between
$\mathcal{H}_{2}$ and $\mathcal{H}_{3}$ is the same, for $i=1$.

In addition to hybrids $\mathcal{H}_{0}$ through $\mathcal{H}_{3+n-k}$, we
define a set of simulated experiments. Each $\mathsf{Sim}_{i}$ will be useful
for reasoning about hybrid $\mathcal{H}_{2+i}$. $\mathsf{Sim}_{i}$ is similar
to $\mathcal{H}_{2+i}$ except that all of the shares are randomized, whereas
in $\mathcal{H}_{2+i}$, shares corrupted after $c_{k-1+i}$ are interpolated.

$\mathsf{Sim}_{i}$ for $i\in[n-k+1]$

Run the $\mathsf{SS\text{-}ACD}(1^{\lambda},\ket{\psi},\mathsf{Adv},s)$
experiment, with the following exceptions.

  * •

Do _not_ initialize
$(\mathcal{S}_{1},\dots,\mathcal{S}_{n},\mathsf{vk})\leftarrow\mathsf{Split}_{\mathbb{S}}(1^{\lambda},s)$
in step 1.

  * •

Whenever $\mathsf{Adv}$ corrupts a new share by outputting
$(c_{a},\mathcal{R})$, prepare the state

$\propto\sum_{\mathbf{y}\in\mathbb{K}^{t}}\ket{\mathbf{y}}^{\mathcal{S}_{c_{a}}}\otimes\ket{\mathbf{y}}^{\mathcal{C}_{c_{a}}}$

Then, sample the set of data indices $J_{c_{a}}\subset[t]$ of size
$t^{\prime}$ and for each check index $j\in[t]\backslash J_{c_{a}}$ measure
$\mathcal{C}_{c_{a},j}$ in the Hadamard basis to obtain $y_{a,j}$ for the
verification key.

  * •

For the first $i$ deletions $d_{b}$ where $b\leq i$, immediately after the
challenger verifies $\mathsf{cert}_{d_{b}}$ and adds $d_{b}$ to $D$, it
measures the data positions in register $\mathcal{C}_{d_{b}}$ with respect to
the binary projective measurement
$\\{\Pi_{\mathsf{cert}_{d_{b}}},I-\Pi_{\mathsf{cert}_{d_{b}}}\\}$. If the
measurement result is “reject”, immediately output $\bot$ in the experiment.

######  Claim 7.

For every secret $s$,

$\mathsf{TD}[\mathcal{H}_{0}(s),\mathcal{H}_{2}(s)]=0$

###### Proof.

It is sufficient to show that
$\mathsf{TD}[\mathcal{H}_{0}(s),\mathcal{H}_{1}(s)]=0$ and
$\mathsf{TD}[\mathcal{H}_{1}(s),\mathcal{H}_{2}(s)]=0$. The former is true by
the correctness of polynomial interpolation (see Section 3.3). To see the
latter, observe that steps 1, 2, and 3 in $\mathcal{H}_{2}(s)$ are equivalent
to sampling a uniformly random state (in _any_ basis) in register
$\mathcal{S}_{i,j}$ by preparing a uniform superposition over the basis
elements in $\mathcal{S}_{i,j}$, then performing a delayed measurement from
$\mathcal{S}_{i,j}$ to $\mathcal{C}_{i,j}$ in that basis. Observe that steps
1, 2, and 3 in $\mathcal{H}_{1}(s)$ also sample uniformly random states in
$\mathcal{S}_{i,j}$. Now consider step 4. In $\mathcal{H}_{2}(s)$, step 4
performs a (classical) polynomial interpolation using copies of points
$(it+j,f(it+j))$ that are obtained by measuring $\mathcal{S}_{i,j}$. This is
equivalent to directly interpolating using $\mathcal{S}_{i,j}$ if
$\mathcal{S}_{i,j}$ contained a computational basis state, which is the case
in $\mathcal{H}_{1}(s)$. ∎

We show that $\mathcal{H}_{2}$ has negligible trace distance from
$\mathcal{H}_{3+n-k}$ in 9. To prove 9, we will need an additional fact which
we show in 8. 8 will also show that the final hybrid $\mathcal{H}_{3+n-k}$ has
zero trace distance from $\mathsf{Sim}_{n-k+1}$, which is independent of the
secret $s$.

Let $\mathcal{H}_{i}[c_{a}](s)$ denote the truncated game where
$\mathcal{H}_{i}(s)$ is run until the end of the round where the $a$’th
corruption occurs, i.e. when $|C|$ reaches $a$. At this point,
$\mathcal{H}_{i}[c_{a}](s)$ outputs the adversary’s register $\mathcal{R}$ and
the set of corrupted registers $\\{\mathcal{S}_{j}\\}_{j\in C}$, unless the
game has ended earlier (e.g. from an abort).888The truncated version of the
game outputs both the set of corrupted registers and $\mathcal{R}$, while the
full version only outputs $\mathcal{R}$. In the full version, the adversary
can move whatever information it wants into $\mathcal{R}$. However, the
truncated game ends early, so the adversary may not have done this when the
game ends. Outputting the corrupted registers directly ensures that they
appear in the output in some form if the game does not abort. Let
$\mathcal{H}_{i}[d_{b}](s)$ similarly represent the truncated game where
$\mathcal{H}_{i}(s)$ is run until the end of the round where the $b$’th
deletion occurs, i.e. when $|D|$ reaches $b$. Define $\mathsf{Sim}_{i}[c_{a}]$
and $\mathsf{Sim}_{i}[d_{b}]$ similarly.

Observe that after the $n$’th corruption in any hybrid experiment, the rest of
the challenger’s actions in the experiment is independent of the secret $s$.
Therefore for every hybrid $\mathcal{H}_{i}$ and every pair of secrets
$(s_{0},s_{1})$,

$\mathsf{TD}[\mathcal{H}_{i}[c_{n}](s_{0}),\mathcal{H}_{i}[c_{n}](s_{1})]=\mathsf{TD}[\mathcal{H}_{i}(s_{0}),\mathcal{H}_{i}(s_{1})]$

######  Claim 8.

For every $i\in[0,n-k+1]$ and every secret $s$,

$\mathsf{TD}[\mathcal{H}_{2+i}[c_{k-1+i}](s),\mathsf{Sim}_{i}[c_{k-1+i}]]=0$

Combining this claim with the previous observation about the relation of a
truncated experiment to its full version, it is clear that

$\displaystyle\mathsf{TD}[\mathcal{H}_{3+n-k}(s_{0}),\mathcal{H}_{3+n-k}(s_{1})]$
$\displaystyle=\mathsf{TD}[\mathcal{H}_{3+n-k}[c_{n}](s_{0}),\mathcal{H}_{3+n-k}[c_{n}](s_{1})]$
$\displaystyle=\mathsf{TD}[\mathsf{Sim}_{n-k+1}[c_{n}],\mathsf{Sim}_{n-k+1}[c_{n}]]$
$\displaystyle=0$

By 9, we have

$\mathsf{TD}[\mathcal{H}_{2}(s_{0}),\mathcal{H}_{2}(s_{1})]\leq\mathsf{TD}[\mathcal{H}_{3+n-k}(s_{0}),\mathcal{H}_{3+n-k}(s_{1})]+\negl$

Therefore, combining claims 7, 8, and 9, we have

$\displaystyle\mathsf{TD}[\mathcal{H}_{0}(s_{0}),\mathcal{H}_{0}(s_{1})]$
$\displaystyle\leq\mathsf{TD}[\mathcal{H}_{3+n-k}(s_{0}),\mathcal{H}_{3+n-k}(s_{1})]+\negl$
$\displaystyle\leq 0+\negl$

which completes the proof. All that remains is to prove 8, and 9.

###### Proof of 8..

We proceed via induction. This is clearly true for $i=0$, since the first
$k-1$ shares to be corrupted are prepared as maximally mixed states in both
$\mathcal{H}_{2}(s)$ and $\mathsf{Sim}$.

Before addressing the case of $i>0$, we define some notation for our specific
application of interpolation. When preparing a share $c_{k-1+i}$ after it is
corrupted, the challenger interpolates evaluations of $f$ into a register

$\mathcal{C}_{c_{k-1+i}}^{R}\coloneqq(\mathcal{C}_{c_{k-1+i},j})_{j\in
J_{c_{k-1+i}}^{R}}$

$\mathcal{C}_{c_{k-1+i}}^{R}$ consists of the right data positions of share
$c_{k-1+i}$ and contains $t^{\prime}-\ell$ $\mathbb{K}$-qudits. To do the
interpolation, the challenger uses evaluations of $f$ contained in registers

$\mathcal{C}_{d_{i}}^{\prime}\coloneqq(\mathcal{C}_{d_{i},j})_{j\in
J_{d_{i}}}$

and some other registers which we group as $\mathcal{I}$.
$\mathcal{C}_{d_{i}}^{\prime}$ consists of the data positions in share $d_{i}$
and contains $t^{\prime}$ $\mathbb{K}$-qudits. Since polynomial interpolation
is a linear operation over $\mathbb{K}$, the system immediately after
$c_{k-1+i}$ is prepared can be described as a state

$\sum_{\begin{subarray}{c}\mathbf{x_{1}}\in\mathbb{K}^{t^{\prime}}\\\
\mathbf{x_{2}}\in\mathbb{K}^{d-t^{\prime}}\end{subarray}}\alpha_{\mathbf{x_{1}},\mathbf{x_{2}}}\ket{\mathbf{x_{1}}}^{\mathcal{C}_{d_{i}}^{\prime}}\otimes\ket{\mathbf{x_{2}}}^{\mathcal{I}}\otimes\ket{\mathbf{\mathbf{R_{1}}}\mathbf{x_{1}}+\mathbf{R_{2}}\mathbf{x_{2}}}^{\mathcal{C}_{c_{k-1+i}}^{R}}\otimes\ket{\mathbf{R_{1}}\mathbf{x_{1}}+\mathbf{R_{2}}\mathbf{x_{2}}}^{\mathcal{S}_{c_{k-1+i}}^{R}}\otimes\ket{\phi_{\mathbf{x_{1}},\mathbf{x_{2}}}}^{\mathcal{C}^{\prime},\mathcal{S}^{\prime},\mathcal{R}}$

where $\mathbf{R_{1}}\in\mathbb{K}^{(t^{\prime}-\ell)\times t^{\prime}}$ and
$\mathbf{R_{2}}\in\mathbb{K}^{(t^{\prime}-\ell)\times(d+1-t^{\prime})}$ are
submatrices of the interpolation transformation, where
$\mathcal{S}_{c_{k-1+i}}^{R}$ contains the copy of the evaluations in
$\mathcal{C}_{c_{k-1+i}}^{R}$, where $\mathcal{C}^{\prime}$ and
$\mathcal{S}^{\prime}$ respectively consist of the unmentioned registers of
$\mathcal{C}$ and $\mathcal{S}$, and where $\mathcal{R}$ is the adversary’s
internal register.

Now we will show that the claim holds for $i+1$ if it holds for $i$. Define
the following hybrid experiments.

  * •

$\mathcal{H}_{3+i}[c_{k+i}]$: Recall that the only difference between
$\mathcal{H}_{2+i}$ and $\mathcal{H}_{3+i}$ is an additional measurement made
in the same round that the $(i+1)$’th share is deleted, i.e. when $|D|$
reaches $i+1$.

  * •

$\mathcal{H}_{3+i}^{\prime}[c_{k+i}]$: The only difference from
$\mathcal{H}_{3+i}[c_{k+i}]$ occurs when the adversary requests to corrupt
share $c_{k+i}$. When this occurs, the challenger prepares the right data
positions of share $c_{k+i}$ as the state

$\propto\sum_{\mathbf{y}\in\mathbb{K}^{t^{\prime}}}\ket{\mathbf{y}}^{\mathcal{C}_{c_{k+i}}^{R}}\otimes\ket{\mathbf{y}}^{\mathcal{S}_{c_{k+i}}^{R}}$

  * •

$\mathsf{Sim}_{i}[c_{k+i}]$: The only difference from
$\mathcal{H}_{3+i}^{\prime}[c_{k+i}]$ is that $\mathsf{Sim}_{i}[c_{k+i}]$ is
run until $c_{k+i}$ is corrupted, then the experiment is finished according to
$\mathcal{H}_{3+i}^{\prime}[c_{k+i}]$.

We first show that $\mathcal{H}_{3+i}^{\prime}[c_{k+i}]$ and
$\mathsf{Sim}_{i}[c_{k+i}]$ are close. By the inductive hypothesis,

$\mathsf{TD}[\mathcal{H}_{2+i}[c_{k-1+i}](s),\mathsf{Sim}_{i-1}[c_{k-1+i}]]=0$

Note that $\mathcal{H}_{2+i}(s)$ and $\mathcal{H}^{\prime}_{3+i}(s)$ are
identical until the $(i+1)$’th deletion $d_{i+1}$. Similarly,
$\mathsf{Sim}_{i-1}$ and $\mathsf{Sim}_{i}$ are identical until the $(i+1)$’th
deletion. Therefore

$\mathsf{TD}[\mathcal{H}^{\prime}_{3+i}[d_{i}](s),\mathsf{Sim}_{i}[d_{i}]]=0$

Finally, observe that if the experiment does not abort, then $d_{i}$ is
deleted before $c_{k+i}$ is corrupted (otherwise $|C\backslash D|=k$ during
some round). Because of this, $\mathcal{H}_{3+i}^{\prime}[c_{k+i}]$ and
$\mathsf{Sim}[c_{k+i}]$ behave identically after the round where $d_{i}$ is
corrupted. Therefore

$\mathsf{TD}[\mathcal{H}_{3+i}^{\prime}[c_{k+i}],\mathsf{Sim}[c_{k+i}]]=0$

It remains to be shown that

$\mathsf{TD}[\mathcal{H}_{3+i}[c_{k+i}],\mathcal{H}_{3+i}^{\prime}[c_{k+i}]]=0$

The only difference between $\mathcal{H}_{3+i}[c_{k+i}]$ and
$\mathcal{H}_{3+i}^{\prime}[c_{k+i}]$ is at the end of the last round, where
$c_{k+i}$ is corrupted.999In the definition of the $\mathsf{SS\text{-}ACD}$
experiment, the corruption set $C$ is updated in between adversarial access to
the corrupted registers, which occur once at the beginning of each round. The
truncated game outputs according to the updated $C$, including
$\mathcal{S}_{c_{k+i}}$. If the experiment reaches the end of this round
without aborting, then $d_{i}$ has already been corrupted, since otherwise at
some point $|C\backslash D|=k$. Furthermore, the deletion predicate
measurement on $\mathcal{C}_{d_{i}}$ must have accepted or else the experiment
also would have aborted. It is sufficient to prove that the two experiments
have $0$ trace distance conditioned on not aborting.

In $\mathcal{H}_{3+i}^{\prime}[c_{k+i}]$, if the experiment does not abort
then its end state (after tracing out the challenger’s $\mathcal{C}$ register)
is

$\sum_{\begin{subarray}{c}\mathbf{x_{1}}\in\mathbb{K}^{t^{\prime}}\\\
\mathbf{x_{2}}\in\mathbb{K}^{d-t^{\prime}}\\\
x_{3}\in\mathbb{K}^{t^{\prime}-\ell}\end{subarray}}|\alpha_{\mathbf{x_{1}},\mathbf{x_{2}}}|^{2}\ket{x_{3}}\bra{x_{3}}^{\mathcal{S}_{c_{k-1+i}}^{R}}\otimes\mathsf{Tr}^{\mathcal{C}^{\prime}}\left[\ket{\phi_{\mathbf{x_{1}},\mathbf{x_{2}}}}\bra{\phi_{\mathbf{x_{1}},\mathbf{x_{2}}}}^{\mathcal{C}^{\prime},\mathcal{S}^{\prime},\mathcal{R}}\right]$

We now calculate the end state of $\mathcal{H}_{3+i}^{\prime}[c_{k+i}]$,
conditioned on it not aborting. In this case, the challenger for
$\mathcal{H}_{3+i}^{\prime}[c_{k+i}]$ prepares the next corrupted register
$\mathcal{S}_{c_{k+i}}$ by a polynomial interpolation which uses registers
$\mathcal{C}_{d_{i}}$ and $\mathcal{I}$. The deletion predicate measurement on
$\mathcal{C}_{d_{i}}$ must have accepted to avoid an abort, so before
performing the interpolation, the state of the system is of the form

$\ket{\gamma}^{A,C^{\prime},\mathsf{Int}_{2},C_{d_{k+i}}}=\sum_{\mathbf{u}\in\mathbb{K}^{t^{\prime}}:h_{\mathbb{K}}(u)<\ell/2}\alpha_{\mathbf{u}}\ket{\psi_{\mathbf{u}}}^{\mathcal{S},\mathcal{C}^{\prime},\mathcal{I}}\otimes
H^{\otimes
t^{\prime}\lceil\log_{2}(n+1)\rceil}\ket{\mathbf{u}+\mathbf{\mathsf{cert}}_{k+i}}^{\mathcal{C}_{d_{i}}}$

We will apply Theorem 3 with input size $t^{\prime}$ and output size
$t^{\prime}-\ell$ to show that share $d_{i}$ contributes uniform randomness to
the preparation of $c_{k+i}$. Observe that $\mathcal{C}_{d_{i}}$ contains
$t^{\prime}$ $\mathbb{K}$-qudits and the interpolation target
$\mathcal{C}_{c_{k+i}}^{R}$ contains $t^{\prime}-\ell$ $\mathbb{K}$-qudits.
Furthermore, $[R_{1}|R_{2}]\in\mathbb{K}^{(t^{\prime}-\ell)\times(d+1)}$ is an
interpolation matrix for a polynomial of degree $p$. By 1, any
$t^{\prime}-\ell$ columns of $[R_{1}|R_{2}]$ are linearly independent. In
particular, any $t^{\prime}-\ell$ columns of $R_{1}$ are linearly independent.
Finally, note that $(t^{\prime}-(t^{\prime}-\ell))/2=\ell/2$. Therefore by
Theorem 3, the state of the system after preparing register
$\mathcal{C}_{c_{k+i}}^{R}$ and tracing out $\mathcal{C}_{d_{i}}$ when the
experiment ends at the end of this round is

$\sum_{\mathbf{x_{3}}\in\mathbb{K}^{t^{\prime}-\ell}}\mathsf{Tr}^{\mathcal{C}_{d_{i}}}\left[\ket{\gamma_{\mathbf{x_{3}}}}\bra{\gamma_{\mathbf{x_{3}}}}^{\mathcal{C},\mathcal{S},\mathcal{R}}\right]$

where

$\ket{\gamma_{\mathbf{x_{3}}}}=\sum_{\begin{subarray}{c}\mathbf{x_{1}}\in\mathbb{K}^{t^{\prime}}\\\
\mathbf{x_{2}}\in\mathbb{K}^{d-t^{\prime}}\end{subarray}}\alpha_{\mathbf{x_{1}},\mathbf{x_{2}}}\ket{\mathbf{x_{1}}}^{\mathcal{C}_{d_{i}}}\otimes\ket{\mathbf{x_{2}}}^{\mathcal{I}}\otimes\ket{\mathbf{x_{3}}+\mathbf{R_{2}}\mathbf{x_{2}}}^{\mathcal{C}_{c_{k+i}}}\otimes\ket{\mathbf{x_{3}}+\mathbf{R_{2}}\mathbf{x_{2}}}^{\mathcal{S}_{c_{k+i}}}\otimes\ket{\varphi_{\mathbf{x_{1}},\mathbf{x_{2}}}}^{\mathcal{C}^{\prime},\mathcal{S}^{\prime},\mathcal{R}}$

After this round, $\mathcal{H}_{3+i}[c_{k+i}]$ ends and register $\mathcal{C}$
is traced out. This yields the state

$\displaystyle\sum_{\mathbf{x_{3}}\in\mathbb{K}^{t^{\prime}-\ell}}\mathsf{Tr}^{\mathcal{C}}\left[\ket{\gamma_{\mathbf{x_{3}}}}\bra{\gamma_{\mathbf{x_{3}}}}^{\mathcal{C},\mathcal{S},\mathcal{R}}\right]$
$\displaystyle\quad=\sum_{\begin{subarray}{c}\mathbf{x_{1}}\in\mathbb{K}^{t^{\prime}}\\\
\mathbf{x_{2}}\in\mathbb{K}^{d-t^{\prime}}\\\