# Quantum Key Leasing for PKE and FHE with a Classical Lessor

Orestis Chardouvelis  Vipul Goyal  NTT Research  Aayush Jain  Jiahui Liu
Massachusetts Institute of Technology

(today)

In this work, we consider the problem of secure key leasing, also known as
revocable cryptography (Agarwal et. al. Eurocrypt’ 23, Ananth et. al. TCC’
23), as a strengthened security notion to its predecessor put forward in
Ananth et. al. Eurocrypt’ 21. This problem aims to leverage unclonable nature
of quantum information to allow a lessor to lease a quantum key with
reusability for evaluating a functionality. Later, the lessor can request the
lessee to provably delete the key and then the lessee will be completely
deprived of the capability to evaluate the function. In this work, we
construct a secure key leasing scheme to lease a decryption key of a
(classical) public-key, homomorphic encryption scheme from standard lattice
assumptions. Our encryption scheme is exactly identical to the (primal)
version of Gentry-Sahai-Waters homomorphic encryption scheme with a carefully
chosen public key matrix. We achieve strong form of security where:

  * •

The entire protocol (including key generation and verification of deletion)
uses merely classical communication between a _classical lessor (client)_ and
a quantum lessee (server).

  * •

Assuming standard assumptions, our security definition ensures that every
computationally bounded quantum adversary could only simultaneously provide a
valid classical deletion certificate and yet distinguish ciphertexts with at
most some negligible probability.

Our security relies on subexponential time hardness of learning with errors
assumption with subexponential noise to modulus ratio. Our scheme is the first
scheme to be based on a standard assumption and satisfying the two properties
mentioned above.

The main technical novelty in our work is the design of an FHE scheme that
enables us to apply elegant analyses done in the context of classical
verification of quantumness from LWE (Brakerski et. al.(FOCS’18, JACM’21) and
its parallel amplified version in Radian et. al.(AFT’21)) to the setting of
secure leasing. This connection to classical verification of quantumness leads
to a modular construction and arguably simpler proofs than previously known.
An important technical component we prove along the way is an amplified
quantum search-to-decision reduction: we design an extractor that uses a
quantum distinguisher (who has an internal quantum state) for decisional LWE,
to extract secrets with success probability amplified to almost one. This
technique might be of independent interest.

##  1 Introduction

Quantum information, through principles such as the _no-cloning theorem_ ,
offers excititng possibilities for which there are no classical counterparts.
An active area of research are primitives such as copy protection [Aar09] and
quantum money [Wie83], which simply can’t be realized classically.

Copy protection, a task that captures a wide variety of unlconability related
tasks, is aimed at leveraging the power of unclonable quantum information to
prevent piracy of software functionalities. However, constructions of quantum
copy protection have turned out to be notoriously hard – in fact, it is shown
to be impossible in general [AP21] and only exist relative to structured
oracles [ALL+20] if we aim at a generic scheme secure for all copy-protectable
functions. Only a handful of functions are known to be copy-protectable
without using oracles in the construction, but either they are built from from
very strong, less-standard cryptographic assumptions (e.g. post-quantum iO)
[CLLZ21, LLQZ22] or the functionalities are very limited (point functions)
[CMP20, BJL+21].

Meaningful relaxations to copy protection come in the form of primitives that
allow revocation of the quantum software via proofs of "destruction” of the
quantum functionality after use. Thus, if the revocation or proof verifies, a
computationally bounded user is deprived of any ability to evaluate the
function in any meaningful ways.

In this work, we consider one such recent notion of secure key leasing
[AKN+23], also called key-revocable cryptography in the literature [APV23].
This notion is inspired by secure software leasing in [AP21], but possesses
significantly stronger security guarantees 111Our security notion is
_stronger_ and has more applicability than the previous, similar primitive
called secure software leasing (SSL) [AP21]. In SSL the adversarial lessee is
only semi-malicious, while in [AKN+23, APV23] and our work it is fully
malicious. See section 1.2 for detailed discussions..

In secure key leasing, a lessor (also called the client) leases a quantum
state to a lessee (also called the server). The quantum state might allow the
server to obtain a capability to compute an advanced classical function, such
as decryption (in case of public-key encryption with secure key leasing), or
PRF evaluation, for polynomially many times.

At a later point in time, the lessor may ask the lessee to return or destroy
the key for reasons such as lessee’s subscription expiring or the
lessor(client) deciding to use another server. The notion of secure key
leasing allows the lessee to “delete" the quantum key and create a deletion
certificate which can be verified by the lessor. Once the deletion certificate
is sent to the lessor and verified, the security guarantee says that the
lessee provably loses the associated capability. This must hold even if the
lessee is fully malicious and may make arbitrary attempts to copy the quantum
state or learn the underlying classical functionality before the deletion. A
number of recent papers have studied the notion of secure key leasing for
primitives like PKE, FE, FHE and PRF [APV23, AKN+23], in the context of a
quantum lessor and quantum lessee with quantum communication. While the notion
of secure software leasing is interesting on its own, remarkly it has also
found an application in the seemingly unrelated context of _leakage or
intrusion detection_ [ÇGLR23] where an adversary breaks into a machine to
steal a secret key and one would like to detect if such an attack happened.

Secure key leasing is a uniquely quantum phonomenon which is enabled by the
no-cloning theorem, clearly impossible in the classical setting. Therefore,
some quantum capabilities are necessary to enable it. However, a natural
question is: _to what extent are quantum capabilities necessary? Do both the
client and the server need quantum capabilities? Do we require quantum
communication in addition to quantum computation?_ As discussed in [Shm22,
CHV23], even in the future where full scale quantum computer come into the
household and every user can maintain quantum memory, setting up large-scale
end-to-end quantum communication is still expensive and lossy. Moreover,
having a client operating only on classical resources and delegating the
quantum work to a server is desirable in almost all sorts of circumstances.

A recent beautiful work of Ananth, Poremba, and Vaikuntanathan [APV23] used
the dual Regev cryptosystem to build primitives such as public-key encryption
(PKE), fully-homomorphic encryption (FHE), and pseudo random functions (PRFs)
with key revocation. While their basic constructions require quantum
communication as well as a quantum certificate of deletion, they can extend
their constructions to achieve classical deletion certificates [APV23] as
well. However a key limitation is their work is that the security only holds
either based on an unproven conjecture, or only against an adversarial server
(leasee) which outputs a valid deletion certificate with probability
negligibly close to 1. Proving security against general adversaries based on
standard assumptions was left as an open problem. In addition, in both works
[AKN+23, APV23], the client and the server must have both quantum capabilities
and quantum communication is also necessary in the key generation process.
This leads to the following natural open problem:

_Can we build secure leasing for unlearnable functions e.g. PKE decryption,
FHE decryption, and other cryptographic functionalities with a completely
classical lessor/client? and more desirably, from standard assumptions?_

If so, this would lead to constructions which require only bare minimum
quantum infrastructure needed in our setting.

###  1.1 Our Results

We answer all the above questions affirmatively thus settling the open problem
from [APV23]. We obtain the following results:

######  Theorem 1.1.

(Informal) Assuming the post-quantum subexponental hardness of Learning-with-
Errors, there exists a secure key leasing scheme for PKE and FHE with a
completely classical lessor/client.

More specifically, from LWE, we can achieve secure leasing for FHE decryption
circuit with following properties:

  1. 1.

The key generation is a one-message protocol with a single classical message
from the lessor to lessee.

  2. 2.

Upon being asked to delete the key, the lessee will produce a classical
certificate, and send it to the client. The client will perform a classical
verification algorithm on the certificate.

  3. 3.

As natural in the definition for secure key leasing of classical PKE, the
encryption is a public, classical procedure. The decryption can be done
quantumly (on the lessee/server’s side) or classically (on the lessor/client’s
side)

A key contribution of our work is to connect our problem to classically
verifiable proof of quantumness [BCM+21]. The latter is a well developed
research direction with beautiful ideas. This connection allows us to design
modular constructions and write proofs of security that are arguably simpler,
thanks to a number of technical ideas that we could rely on the literature in
classical verification of quantum computation.

To show the security of our construction, we prove along the way a quantum
search-to-decision reduction for LWE that extracts the secret _with the
success probability boosted to almost 1_.

######  Theorem 1.2 (Informal).

Given a quantum distinguisher with an auxiliary quantum state, that
distinguishes LWE samples from random with inverse polynomial probability for
some arbitrary secret, there exists an extractor running in time polynomial
(in the the secret size, the distinguisher’s time and inverse its advantage)
that produces the secret with probability negligibly close to 1.

To the best of our knowledge, this is the first search-to-decision reduction
with an almost-perfect search when using quantum algorithms with auxiliary
quantum states. To prove the above theorem, we rely on a measurement
implementation on the distinguisher’s quantum state [Zha20, ALL+20] and make
new observations about this measurement procedure, by aligning its properties
with the features required by the classical LWE search-to-decision reduction
by Regev [Reg05a].

We believe this technique and the new observations made maybe of independent
interest.

###  1.2 Comparison with Related Works

##### Secure Key Leasing/Revocable PKE: Comparison with Existing Works

Previously, secure circuit leasing for PKE was achieved in [AKN+23]. [AKN+23]
achieved it by a clean compiler from any PKE scheme. But they need quantum
communication and quantum computation on the lessor’s side throughout the
protocol, and there is no easy, generic way to turn their scheme into one with
classical leaser with classical communication.

A similar result on revocable PKE, FHE and PRF to [APV23] was shown by the
concurrent work from LWE with interesting ideas from quantum money combined
with dual Regev PKE. However, they need new conjectures for enabling the
security proof where adversaries only have inverse polynomial probability of
revocation, otherwise they can only handle a weaker security where the
adversary has to pass the revocation with probability almost 1 [APV23].
Whereas we achieve the stronger definition, i.e. adversaries only need to pass
the revocation test with noticeable probability, from LWE alone. Moreover,
they also need the lessor to prepare the quantum key and send the key via a
quantum channel.

Our techniques also differ greatly from the above works. Our main insight is
to manipulate the primitives used in the classical verification of quantum
computation protocol and turning it into an FHE scheme from LWE that supports
leasing.

##### Secure Software Leasing:

SSL, short for Secure Software Leasing in [AP21] is another relaxation of
quantum copy protection. It is a weaker security notion than the notion
studied in this work, even though bearing a similar name. In SSL, after
revocation/deletion, one tests whether the leftover state of the adversary
function correctly, using the leaser’s circuit. In other words, in SSL, the
pirate can be arbitrarily malicious in copying the function, but the free-
loaders of the pirated programs are semi-honest by following the authentic
software’s instructions. In our work, we allow the adversarial state to be run
by any adversarial circuit; as long as it gives the correct output, we count
it as a successful attack., i.e. both the pirate and free-loaders can have
arbitrary malicious behaviors.

We defer more related works and discussions on SSL to Section 2.2.

##### Post-quantum LWE Search-to-Decision Reduction with Quantum Auxiliary
Input

[BBK22] showed a general method to lift classical reductions to post-quantum
reductions for a class of primitives satisfying certain constraints. Even
though the classical search-to-decision reduction for LWE fit into the
framework required in the above lifting theorem, our proof roadmap requires a
stronger statement than the one shown in [BBK22].To the best of our knowledge,
there is no generic or black-box method to amplify the reduction in [BBK22]
for our use. Besides, our techniques differ from [BBK22] in that we do not
perform the more involved "state repair" procedure used by [BBK22], which was
inspired by [CMSZ22]. Therefore, we believe our techniques may be of
independent interest and can shed light on new observations in quantum
reductions.

Another work [STHY23] presents a quantum LWE search to decision reduction
(with the possibility of amplification) but their quantum distinguisher is
simply a unitary that does not have an auxiliary state. Therefore, it is
incomparable to our techniques. Our reduction is more general and more
challenging to achieve due to the potentially destructible auxiliary quantum
state.

##  2 Technical Overview

We start by recalling the definition of Public-Key Encryption with Secure Key
Leasing (also referred to as $\mathsf{PKESKL}$ from here on). (Levelled)
homomorphic encryption with secure key leasing is defined analogously. In a
$\mathsf{PKESKL}$ scheme with classical leaser, we have algorithms
($\mathsf{Setup}$,$\mathsf{KeyGen}$, $\mathsf{Enc}$, $\mathsf{Dec}$,
$\mathsf{Del}$, $\mathsf{VerDel}$). The $\mathsf{Setup}$ algorithm (to be run
by the lessor) takes in a security parameter and outputs a classical master
public-key $\mathsf{mpk}$ and a classical trapdoor $\mathsf{td}$. The
$\mathsf{KeyGen}$ algorithm (to be run by the lessee) takes input
$\mathsf{mpk}$ and outputs a classical public-key $\mathsf{pk}$ and a quantum
secret key $\rho_{\mathsf{sk}}$. $\mathsf{Enc}$ is defined in a usual way, it
is a classical procedure that takes as input the key $\mathsf{pk}$ and a bit
$\mu$ and produces a ciphertext $\mathsf{ct}$. The quantum procedure
$\mathsf{Dec}$ takes as input a ciphertext $\mathsf{ct}$ and the state
$\rho_{\mathsf{sk}}$ and should produce the message that was encrypted.
Moreover, the decryption should keep the state $\rho_{\mathsf{sk}}$
statistically close to the initial state as long as the decrypted ciphertext
were not malformed. Then, the deletion algorithm $\mathsf{Delete}$ should take
in the state $\rho_{\mathsf{sk}}$ and produce a classical certificate
$\mathsf{cert}$. Finally, the certificate can be verified by the classical
algorithm $\mathsf{VerDel}$ using $\mathsf{pk}$, and the trapdoor
$\mathsf{td}$ as other inputs. Conclusively, our scheme will allow the
generation of key $\rho_{\mathsf{sk}}$ by a protocol involving merely
classical effort on the part of a client (lessor) and quantum effort from the
server (lessee).

Our security requirement is also fairly intuitive. In the security game, the
challenger generates a classical $\mathsf{mpk}$ along with a trapdoor
$\mathsf{td}$ and gives $\mathsf{mpk}$ to a quantum polynomial time attacker
$\mathcal{A}$. $\mathcal{A}$ generates a quantum decryption key
$\rho_{\mathsf{sk}}$ and its associated public key $\mathsf{pk}$.
$\mathcal{A}$ publishes its $\mathsf{pk}$. The challenger then asks
$\mathcal{A}$ to provide a certificate $\mathsf{cert}$. The game aborts if
$\mathsf{cert}$ does not verify. However, if the certificate verifies, we
require that $\mathcal{A}$ should not be able to distinguish an encryption of
$0$ from an encryption of $1$ with a non-negligible probability. We formalize
this by requiring that after the step of successful verification of
certificate, an adversary outputs a quantum state $\rho_{\mathsf{Delete}}$ as
a adversarial quantum decyrptor.

Checking a quantum state ’s success probability can be difficult due to its
destructible and unclonable nature. To check if this state is a good
decryptor, we define a special binary-outcome projective measurement, called
Threshold Implementation, ${\sf TI}_{\frac{1}{2}+\gamma}$ (from [Zha20,
ALL+20]). This measurement projects the state $\rho_{\mathsf{Delete}}$ onto
the subspace of all possible states that are good at distinguishing
ciphertexts with probability at least $\frac{1}{2}+\gamma$. If ${\sf
TI}_{\frac{1}{2}+\gamma}$ outputs $1$ on $\rho_{\mathsf{Delete}}$ with some
noticeable probability, it implies that a noticeable "fraction" of the quantum
states can distinguish ciphertexts with probability at least $1/2+\gamma$.

Passing the ${\sf TI}_{1/2+\gamma}$ test combined with handing in a valid
certificate, we consider such an adversary to be successful.

The definitions are inspired from the framework introduced by Zhandry
[Zha20](see Section 8.2,Section 5 for details) and will imply the past PKE-SKL
definition used in [AKN+23, APV23]. As we will discuss later, defining the
security via Threshold Implementation also assists us in our security proof.

We then start by describing the ideas to build a PKE scheme first. These ideas
can be lifted to build a (levelled) FHE scheme. Below, we show a series of
ideas leading up to our final scheme.

##### Starting Point: Regev PKE.

Our starting point is a public-key encryption due to Regev [Reg05a], which is
also the basis of many FHE schemes such as the BV scheme [BV11], and the GSW
scheme [GSW13]. In Regev PKE, the public key consists of a matrix
$\mathbf{A}\in\mathbb{Z}^{n\times m}_{q}$ where $m=\Omega(n\cdot\log q)$,
along with $m$ LWE samples $\mathbf{b}=\mathbf{s}\mathbf{A}+\mathbf{e}\mod q$
where $\mathbf{s}\leftarrow\mathbb{Z}^{1\times n}_{q}$ is a randomly chosen
and $\mathbf{e}$ is a discrete Gaussian distributed error with some parameter
$\sigma\ll q$. The classical secret key is simply the secret vector
$\mathbf{s}$ for the LWE sample.

To encrypt a message $\mu\in\\{0,1\\}$, one samples a binary random vector
$\mathbf{r}\in\mathbb{Z}^{m\times 1}_{q}$. Encryptor then computes
$\mathsf{ct}=(\mathsf{ct}_{1},\mathsf{ct}_{2})$ where
$\mathsf{ct}_{1}=(\mathbf{A}\cdot\mathbf{r}$,
$\mathsf{ct}_{2}=\mathbf{b}\cdot\mathbf{r}+\mu\cdot\lceil\frac{q}{2}\rceil)$.
Observe that the correctness follows from the fact that
$\mathbf{b}\cdot\mathbf{r}\approx\mathbf{s}\cdot\mathbf{A}\cdot\mathbf{r}$,
where $\approx$ means that they are close to each other in the $\ell_{2}$
norm, since $\mathbf{r}$ and $\mathbf{e}$ are both low-norm. The security
follows from the fact that due to LWE, $\mathbf{b}$ is pseudorandom.
Therefore, one can apply leftover hash lemma argument to that $\mu$ is hidden.
We want to turn this into a scheme that supports leasing. Namely, instead of
having the secret key $\mathbf{s}$, we would like to have it encoded as a
quantum state that somehow encodes $\mathbf{s}$ and (say) another hidden value
(for the deletion certificate) so that it’s computationally hard for an
attacker to produce both? Unfortunately, it’s not so clear how to make things
work if the scheme has exactly one key $\mathbf{s}$.

##### Two Key Regev PKE.

Our next idea is to modify the Regev style PKE scheme to work with two secret
keys $\mathbf{s}_{0},\mathbf{s}_{1}$ instead. The public-key would now consist
of a matrix $\mathbf{A}$ along with two LWE samples
$\mathbf{b}_{0}=\mathbf{s}_{0}\mathbf{A}+\mathbf{e}_{0}$ and
$\mathbf{b}_{1}=\mathbf{s}_{1}\mathbf{A}+\mathbf{e}_{1}$. To generate an
encryption of $\mu\in\\{0,1\\}$ one outputs
$\mathsf{ct}=(\mathsf{ct}^{\prime},\mathsf{ct}_{0},\mathsf{ct}_{1})$ where
$\mathsf{ct}^{\prime}=\mathbf{A}\mathbf{r}$,
$\mathsf{ct}_{i}=\mathbf{b}_{i}\mathbf{r}+\mu\cdot\lceil\frac{q}{2}\rceil$ for
$i\in\\{0,1\\}$. Observe that now the ciphertext $\mathsf{ct}$ could be
decrypted using either of the two secret vectors $\mathbf{s}_{0}$ and
$\mathbf{s}_{1}$. This gives us the following idea: perhaps one could encode
the secret key as a superposition of the two keys,
$\rho_{\mathsf{sk}}=\ket{0,\mathbf{s}_{0}}+\ket{1,\mathbf{\mathbf{s}_{1}}}$
(ignoring normalization). Observe that using such a state one could decrypt
any honestly generated ciphertext without disturbing the state.

What is a good candidate for a deletion certificate? Naturally, in order to
delete the secret information in the computational basis, a deletion
certificate could be a measurement in the Hadamard basis, giving a string
$\mathbf{d}$ and a value
$\alpha=\langle\mathbf{d},\mathbf{s}_{0}\oplus\mathbf{s}_{1}\rangle$. We could
perhaps hope that if an algorithm supplies the measurement outcome in the
Hadamard basis correctly with overwhelming probability, then it would destroy
information on the two secret keys.

How would one analyze such a scheme? The hope would be to arrive at a
contradiction from such an adversary. Assuming that such an adversary outputs
$(\alpha,\mathbf{d})$ with overwhelming probability and conditioned on that
distinguishes encryptions of $0$ from $1$ with inverse polynomial probability,
we would hope to extract one of the secrets $\mathbf{s}_{0}$ or
$\mathbf{s}_{1}$ with inverse polynomial probability, from the adversary’s
internal quantum state. Simultaneously, we also have obtained the string
$(\alpha,\mathbf{d})$ from the certificate handed in. We would like to argue
that no efficient adversary is able to produce both a secret vector and a
string $(\alpha,\mathbf{d})$. While this is often a reasonable property,
subtleties can come in when combined with other structures of our encryption
scheme. We instead turn to a very similar setting that has been extensively
analyzed in prior works in context of classical proof of quantumness and
certified randomness [BCM+21]. This will save us the effort of reinventing the
wheel.

##### Inspiration from Classical Verification of Quantum Computation.

Let us now recall the very similar setting in [BCM+21] which constructed
proofs of quantumness from LWE. They build _Noisy Claw-free Trapdoor families
(NTCF)_ from LWE and show that a related task above is hard. Without going
into the unnecessary semantics, we describe the setting relevant to us.

Consider the following game: The challenger samples $\mathbf{A}$ and an LWE
sample $\mathbf{k}=\mathbf{s}\mathbf{A}+\mathbf{e}\mod q$ where $\mathbf{s}$
is (say) binary random secret $\mathbf{s}$ and $\mathbf{e}$ is chosen from a
discrete Gaussian distribution with parameter $\sigma$. For any such sample,
there exists a BQP algorithm that could sample a vector
$\mathbf{y}=\mathbf{x}_{0}\mathbf{A}+\mathbf{e}^{\prime}$ where
$\mathbf{e}^{\prime}$ chosen from discrete Gaussian with parameter
$\sigma^{\prime}\gg\sigma$ (by a superpolynomial factor), along with a special
state ${\sf\rho_{\mathsf{sk}}}$. The state is of the form
${\sf\rho_{\mathsf{sk}}}=\ket{(0,\mathbf{x}_{0})}+\ket{(1,\mathbf{x}_{1})}$
where $\mathbf{x}_{1}=\mathbf{s}-\mathbf{x}_{0}$. Measuring this state yields
either $\mathbf{x}_{0}$ so that $\mathbf{x}_{0}\mathbf{A}\approx\mathbf{y}$ or
$\mathbf{x}_{1}$ so that $\mathbf{x}_{1}\mathbf{A}$ is close to
$\mathbf{y}-\mathbf{k}$. On the other hand if we measured in the Hadamard
basis we will again obtain $(\mathbf{d},\alpha)$ for a random string
$\mathbf{d}$ so that
$\alpha=\langle\mathbf{d},\mathbf{x}_{0}\oplus\mathbf{x}_{1}\rangle$ 222In the
actual protocol, $\alpha$ is not equal to
$\langle\mathbf{d},\mathbf{s}\rangle$ where
$\mathbf{s}=\mathbf{x}_{0}\oplus\mathbf{x}_{1}$. In fact, we first apply a
binary decomposition to $\mathbf{x}_{0},\mathbf{x}_{1}$ and then measure in
Hadamard basis. i.e. we have
$\alpha=\langle\mathbf{d},\mathcal{J}(\mathbf{x}_{0})\oplus\mathcal{J}(\mathbf{x}_{1})\rangle\mod
2$, where $\mathcal{J}$ is the invertible binary decomposition function. Such
a binary decomposition is needed for the security proof of the NTCF to go
through in [BCM+21].

The test of quantumness asks an efficient quantum algorithm to produce a valid
LWE sample $\mathbf{y}=\mathbf{x}_{0}\mathbf{A}+\mathbf{e^{\prime}}$ of the
kind above and based on a random challenge produce either one of
$(\mathbf{x}_{0},\mathbf{x}_{1})$ for $b\in\\{0,1\\}$ or a “valid" tuple
$(\mathbf{d},\alpha)$ as above.

This above protocol has a quantum correctness and a classical soundness, which
we omit discussions due to irrelevance. However, to enable capabilities such
as certified randomness/verification of quantum computation[Mah18], they show
a more advanced soundness property against quantum provers. That is, even a
BQP adversary cannot _simultaneously_ produce these responses (the
"computational response" for $b=0$, and the "Hadamard response" for $b=1$),
assuming quantum security of LWE.

In short, we conclude the properties we need from the NTCF-based protocol: any
QPT algorithm, given $\mathbf{A}$ and
$\mathbf{k}=\mathbf{s}\mathbf{A}+\mathbf{e}$, can produce a valid LWE sample
$\mathbf{x}_{0}\mathbf{A}+\mathbf{e}^{\prime}\approx\mathbf{x}_{0}\mathbf{A}+\mathbf{e}^{\prime}+\mathbf{k}=\mathbf{y}$
. If it is asked to output _either_ , (1) one of
$\mathbf{x}_{0},\mathbf{x}_{1}$, _or_ , (2) a non-trivial pair
$(\mathbf{d},\alpha)$ such that
$\alpha=\langle\mathbf{d},\mathcal{J}(\mathbf{x}_{0})\oplus\mathcal{J}(\mathbf{x}_{1})\rangle$,
it can do so with probability 1. However, if it is asked to output _both_ (1)
and (2) at once for the same $\mathbf{y}$, it cannot achieve so with
probability noticeably higher than trivial guessing for one of them.

##### From Noisy Trapdoor Claw-free Families to Our Scheme.

Now we gradually approach a scheme similar to the two-key Regev PKE scheme
which can benefit from the NTCF security properties described above. The idea
is that we have a public key $\mathbf{A}$, an LWE sample
$\mathbf{k}=\mathbf{s}\mathbf{A}+\mathbf{e}$ where $\mathbf{s}$ is a random
binary secret and $\mathbf{e}$ is Gaussian distributed exactly like the
distribution used for proof of quantumness. Along with $\mathbf{k}$, the
public key also consists of an LWE sample
$\mathbf{y}=\mathbf{x}_{0}\mathbf{A}+\mathbf{e}^{\prime}$ chosen as per the
distribution in the proof of quantumness again. The client manintains a
trapdoor $\mathsf{td}$: $\mathsf{td}$ consists of a trapdoor matrix
$\mathbf{T}$ of $\mathbf{A}$ that can be generated at the same time as
sampling $\mathbf{A}$ (recall that $\mathsf{td}$ will be used to verify the
deletion certificate later). The leased decryption state $\rho_{\mathsf{sk}}$
is the superposition $\ket{0,x_{0}}+\ket{1,x_{1}}$ where
$\mathbf{x}_{1}=\mathbf{x}_{0}-\mathbf{s}$.

To encrypt a bit $\mu$, one samples a random binary string $\mathbf{r}$ and
computes a ciphertext
$\mathsf{ct}=(\mathsf{ct}_{1},\mathsf{ct}_{2},\mathsf{ct}_{3})$ where
$\mathsf{ct}_{1}=\mathbf{A}\mathbf{r}$, $\mathsf{ct}_{2}=\mathbf{k}\mathbf{r}$
and $\mathsf{ct}_{3}=\mathbf{y}\mathbf{r}+\mu\lceil\frac{q}{2}\rceil$. Observe
that the ciphertext can be decrypted by both $\mathbf{x}_{0}$ or
$\mathbf{x}_{1}$. This is because $\mathsf{ct}_{3}-\mathbf{x}_{0}\mathbf{A}$
is close to $\mu\lceil\frac{q}{2}\rceil$ and similarly,
$-\mathsf{ct}_{2}+\mathsf{ct}_{3}+\mathbf{x}_{1}\mathbf{A}$ is also close to
$\mu\lceil\frac{q}{2}\rceil$. Thus, there is a way to decrypt a ciphertext
cohenrently without disturbing the state $\rho_{\mathsf{sk}}$, by the gentle
measurement lemma [Aar04]. Accordingly, we set the deletion certificate to be
the string $(\alpha,\mathbf{d})$ to use the property of NTCF.

##### Security: First Attempt

We first discuss a very weak definition of security which the above simple
scheme (almost) satisfies already. In this definition, a successful BQP
adversary provides a deletion certificate that’s valid with probability
$1-\mathsf{negl}$ for some negligible $\mathsf{negl}$ and then conditioned on
that distinguishes ciphertexts with a noticable probability. One observation
is that given a decryptor that’s capable of distinguishing encryptions of zero
from encryptions of one, must also enable distinguishing ciphertexts of zero
of the form $(\mathsf{ct}_{1},\mathsf{ct}_{2},\mathsf{ct}_{3})$ where
$\mathsf{ct}_{1}=\mathbf{A}\cdot\mathbf{r}$,
$\mathsf{ct}_{2}=\mathbf{k}\cdot\mathbf{r}$ and
$\mathsf{ct}_{3}=\mathbf{y}\cdot\mathbf{r}$ from truly random strings with a
noticable probabilty. This means that this distinguisher distinguishes samples
of the form $(\mathbf{A}\mathbf{r},\mathbf{k}\mathbf{r},\mathbf{y}\mathbf{r})$
from random. Since $\mathbf{k}$ is pseudorandom due to LWE it must also
distinguish $(\mathbf{A}\mathbf{r},\mathbf{k}\mathbf{r},\mathbf{y}\mathbf{r})$
from random where $\mathbf{k}$ is chosen at random. Observe that
$\mathbf{y}=\mathbf{x}_{0}\mathbf{A}+\mathbf{e}^{\prime}$,
$\mathbf{y}\mathbf{r}=\mathbf{x}_{0}\mathbf{A}\mathbf{r}+\mathbf{e}^{\prime}\mathbf{r}$.
Given that $\mathbf{e}^{\prime}\mathbf{r}$ losses information on $\mathbf{r}$,
and $\mathbf{A},\mathbf{k}$ are now chosen at random one can appeal to LHL to
show that such a distinguisher should distinguish between
$(\mathsf{ct}_{1},\mathsf{ct}_{2},\mathsf{ct}_{3})$ generated as
$(\mathbf{a},u,\langle\mathbf{x}_{0},\mathbf{a}\rangle+\mathbf{e}^{\prime}\mathbf{r})$
from random, where $\mathbf{a}\in\mathbb{Z}^{n\times 1}_{q}$ and
$u\in\mathbb{Z}_{q}$ are random.

Together $(\mathsf{ct}_{1},\mathsf{ct}_{3})$ are now almost distributed as an
LWE sample in $\mathbf{x}_{0}$. If we have a quantum search to decision
reduction for LWE using the quantum distinguisher (with an internal state), we
should be able to extract $\mathbf{x}_{0}$ efficiently giving rise to a
contradiction. That is, this reduction would have produced a valid
$(\alpha,\mathbf{d})$ with overwhelming probability and conditioned on that
$\mathbf{x}_{0}$ with inverse polynomial probability (something ruled out by
the NTCF in [BCM+21]).

In this work, we construct a post-quantum (quantum) reduction that runs in
time polynomial in $(B,n,\frac{1}{\epsilon},\log q,T_{\mathcal{A}})$ where
$\epsilon$ is the distinguishing advantage of an adversary that distinguishes
samples LWE in a fixed secret from random samples and recovers that secret
with probability polynomial in $\epsilon$333While we can also obtain such a
reduction directly from plugging in Theorem 7.1 in [BBK22], as we will discuss
later, their reduction’s success probability is not sufficient in our proof of
the standard security. . Above $B$ is the bound on the coordinates of
$\mathbf{x}_{0}$ which we will set to be slightly superpolynomial and
$T_{\mathcal{A}}$ is the running time of the adversary.

There is a minor flaw in the above argument that can be fixed. The
distribution $(\mathsf{ct}_{1},\mathsf{ct}_{2},\mathsf{ct}_{3})$ formed as
$(\mathbf{A}\mathbf{r},\mathbf{k}\mathbf{r},\mathbf{y}\mathbf{r})$ does not
behave statistically close to
$(\mathbf{a},u,\langle\mathbf{a},\mathbf{x}_{0}\rangle+e)$ for truly random
$\mathbf{a},u$ and an error $e$ sampled according to LWE distribution. The
reason for that is that if we consider
$\mathbf{y}\mathbf{r}=\mathbf{x}_{0}\mathbf{A}\mathbf{r}+\mathbf{e}^{\prime}\mathbf{r}$,
the error $e=\mathbf{e}^{\prime}\mathbf{r}$ might not behave as an
statistically independent discrete Gaussian. To fix this issue, we modify our
encryption algorithm to have a smudging noise $\mathbf{e}^{\prime\prime}$ with
superpolynomially larger parameter $\sigma^{\prime\prime}\gg\sigma$ and
construct $(\mathsf{ct}_{1},\mathsf{ct}_{2},\mathsf{ct}_{3})$ as
$(\mathbf{A}\mathbf{r},\mathbf{k}\mathbf{r},\mathbf{y}\mathbf{r}+\mathbf{e}^{\prime\prime}+\mu\lceil\frac{q}{2}\rceil)$.
With this smudging $\mathbf{e}^{\prime}\mathbf{r}$ can now be drowned by
$\mathbf{e}^{\prime\prime}$ effectively now behaving as a fresh LWE sample in
$\mathbf{x}_{0}$ with slightly larger noise. Accordingly, we design our
search-to-decision reduction to also work for samples statistically-close to
LWE versus samples close to random, as opposed to the simple case of real LWE
versus truly random.

##### Stronger Security from Parallel Repetition

While the scheme above gives rise to a PKE scheme satisfying a weak but a non-
trivial security guarantee, such a definition is not really enough. It might
be possible that an adversary simply guesses the correct certificate
$(\alpha,\mathbf{d})$ by picking $\mathbf{d}$ randomly and choosing $\alpha$
at random as well. With $\frac{1}{2}$ probability, this adversary might be
right in producing a valid certificate. Since its state is still preserved, it
could continue to successfully decrypt all ciphertexts (moreover, it could
simply measure the state in the standard basis and keep a classical key). We’d
like to achieve a stronger definition where even if the certificate passes
with a noticable probability, upon successful passing, the advantage should
not be non-negligible.

Our main idea there is that one could create $\lambda$ independent instances
of the scheme where one encrypts secret sharing of the bit $\mu$ where
$\lambda$ is the security parameter. The idea is that now the public key would
consist of $\lambda$ indepdent matrices $\mathbf{A}_{i}$, $\lambda$ indepdent
binary secret LWE samples
$\mathbf{k}_{i}=\mathbf{s}_{i}\mathbf{A}_{i}+\mathbf{e}_{i}$ along with
$\mathbf{y}_{i}\approx\mathbf{x}_{i,0}\mathbf{A}_{i}+\mathbf{e}^{\prime}_{i}$
for $i\in[\lambda]$. The deletion certificate would consist of $\lambda$
vectors $(\alpha_{i},\mathbf{d}_{i})$ and each of them are indepdently
verified. The hope again is that if one is able to distinguish encryptions of
$0$ from encryptions of $1$, then such an adversary should essentially be able
to distinguish for each component $i\in[\lambda]$. We could use this to
exctract all $\\{\mathbf{x}_{i,b_{i}}\\}_{i\in[\lambda]}$($b_{i}=0$ or 1).
Then, we can appeal to the results from the parallel repetition variant of the
game used for proofs of quantumness. This variant has been studied in [RS19].
The soundness property ensures that it is computationally hard to come up with
noticable probability valid responses
$\\{(\alpha_{i},\mathbf{d}_{i})\\}_{i\in[\lambda]}$ and
$\\{\mathbf{x}_{i,b_{i}}\\}_{i\in[\lambda]}$($b_{i}=0$ or 1) for all indices.

##### Lifting the Scheme to Support Homomorphism

The above idea could work however, we would have to examine a lot of care to
extract the secrets $\\{\mathbf{x}_{b_{i},i}\\}_{i\in[\lambda]}$ as a quantum
state can evolve over time. At this point, we move to directly construct a
(levelled) FHE scheme. The structural properties of our levelled FHE scheme
would solve two problems in one shot. It will not only yield as an FHE scheme,
but will also simplify our analysis.

To lift to FHE, we take inspiration for the GSW scheme [GSW13]. In the GSW
scheme, the public key consists of a pseudorandom LWE matrix
$\mathbf{B}\in\mathbb{Z}^{N\times M}_{q}$ where $M=\Omega(N\log q)$ such that
there exists one secret vector $\mathbf{s}\in\mathbb{Z}^{1\times N}_{q}$ so
that $\mathbf{s}\mathbf{B}$ is small norm. Such matrices can be generated by
sampling first $N-1$ rows at random and the last row generated as an LWE
sample with the coefficient being the first $N-1$ rows. The encryption of a
bit $\mu$ is of the form $\mathbf{B}\mathbf{R}+\mu\mathbf{G}$ where
$\mathbf{R}$ is a small norm random binary matrix and $\mathbf{G}$ is a
special gadget matrix [MP12]. The consequence of this is that
$\mathbf{B}\mathbf{R}$ behaves essentially like a random LWE sample with the
same secret vector as $\mathbf{B}$ and one could argue security by appealing
to LHL. We omit a description of why the ciphertext could be homomorphically
computed on (one could refer to either [GSW13] or our technical sections).

To lift to such an FHE scheme, we work with a specially chosen $\mathbf{B}$.
We choose it as:

$\displaystyle\mathbf{B}=\begin{bmatrix}\mathbf{k}_{1}=\mathbf{s}_{1}\mathbf{A}_{1}+\mathbf{e}_{1}\\\
\mathbf{A}_{1}\\\ \cdots\\\ \cdots\\\
\mathbf{k}_{\lambda}=\mathbf{s}_{\lambda}\mathbf{A}_{\lambda}+\mathbf{e}_{\lambda}\\\
\mathbf{A}_{\lambda}\\\
\sum_{i\in[\lambda]}\mathbf{y}_{i}=\sum_{i\in[\lambda]}\mathbf{x}_{i,0}\mathbf{A}_{i}+\mathbf{e}^{\prime}_{i}\end{bmatrix}$

Observe that there are many vectors $\mathbf{v}$ so that
$\mathbf{v}\mathbf{B}$ is small norm. This is crucial because we would like
the ciphertexts to be decryptable using a secret key
$\rho_{\mathsf{sk}}=\otimes_{i}^{\lambda}\rho_{\mathsf{sk},i}$ where
$\rho_{\mathsf{sk},i}=\ket{(0,\mathbf{x}_{i,0})}+\ket{(1,\mathbf{x}_{1,i})}$.
The idea is that $\mathbf{x}_{0,i}\mathbf{A}_{i}$ is close to $\mathbf{y}_{i}$
and similarly $\mathbf{k}_{i}-\mathbf{x}_{1,i}\mathbf{A}_{i}$ is also close to
$\mathbf{y}_{i}$. Thus, $\mathbf{B}$ can be decrypted by viewing
${\sf\rho_{\mathsf{sk}}}$ as a vector we can perform a GSW-like decryption in
superposition, with a gentle measurement on the final output.

For security, we consider the structure of the ciphertext
$\mathsf{ct}=\mathbf{B}\mathbf{R}+\mu\mathbf{G}$, the term
$\mathbf{B}\mathbf{R}$ is of the form:

$\displaystyle\mathbf{B}\mathbf{R}=\begin{bmatrix}\mathbf{s}_{1}\mathbf{A}_{1}\mathbf{R}+\mathbf{e}_{1}\mathbf{R}\\\
\mathbf{A}_{1}\mathbf{R}\\\ \cdots\\\ \cdots\\\
\mathbf{s}_{\lambda}\mathbf{A}_{\lambda}\mathbf{R}+\mathbf{e}_{\lambda}\mathbf{R}\\\
\mathbf{A}_{\lambda}\mathbf{R}\\\
\sum_{i\in[\lambda]}\mathbf{y}_{i}\mathbf{R}=\sum_{i\in[\lambda]}\mathbf{x}_{i,0}\mathbf{A}_{i}\mathbf{R}+\mathbf{e}^{\prime}_{i}\mathbf{R}\end{bmatrix}$

Our intuition to extract $\mathbf{x}_{i,0}$(w.l.o.g. or $\mathbf{x}_{i,1}$)
for all $i\in[\lambda]$ is as follows. First we observe that it will suffice
to devise an extractor that will succeed with high probability in the case
when $\mathbf{k}_{i}$ is chosen to be random as opposed to be pseudorandom due
to LWE. If we are able to do that, we should be able to extract
$\mathbf{x}_{i,b_{i}}$ with similar probability in the world where the
$\mathbf{k}_{i}$’s are pseudorandom due to LWE security.

To realize our relaxed goal, we observe that the last row
$\sum_{i\in[\lambda]}\mathbf{y}_{i}\mathbf{R}$ is close to a linear equation
of the form:

$\displaystyle\sum_{i\in[\lambda]}\mathbf{y}_{i}\mathbf{R}\approx\sum_{i\in[\lambda]}\mathbf{x}_{i,0}\mathbf{V}_{i}$

where $\mathbf{V}_{i}=\mathbf{A}_{i}\mathbf{R}$. Thus, we modify our
encryption algorithm to have smudging noise.

After we modify the encryption algorithm to compute
$\mathbf{B}\mathbf{R}+\mathbf{E}+\mu\mathbf{G}$ where $\mathbf{E}$ is zero
everywhere else except the last row containing discrete Gaussian with
parameter $\sigma^{\prime\prime}$ superpolnomially more than the norm of
$\mathbf{e}^{\prime}_{i}\mathbf{R}$, we make a nice observation: the last row
of $\mathbf{B}\mathbf{R}+\mathbf{E}$ would now be distributed as an LWE
sample: in terms of the secret
$(\mathbf{x}_{1,b_{1}},\mathbf{x}_{2,b_{2}},\ldots,\mathbf{x}_{\lambda,b_{\lambda}})$($b_{i}=0\text{
or }1$) with the coefficient vector
$[\mathbf{V}^{\top}_{1},\ldots,\mathbf{V}^{\top}_{\lambda}]^{\top}$. Now we
could appeal the LHL to replace
$\\{(\mathbf{A}_{i}\mathbf{R},\mathbf{V}_{i}\mathbf{R},\mathbf{k}_{i}\mathbf{R})\\}_{i\in[\lambda]}$
to completely random and the last row by a fresh sample with error according
to discrete Gaussian in parameter $\sigma^{\prime\prime}$, with the long
secret
$((\mathbf{x}_{1,b_{1}},\mathbf{x}_{2,b_{2}},\ldots,\mathbf{x}_{\lambda,b_{\lambda}})$
and random coefficient vector
$[\mathbf{V}^{\top}_{1},\ldots,\mathbf{V}^{\top}_{\lambda}]^{\top}$. If an
adversary now distinguish such ciphertexts from random, we should be able to
extract the entire long secret vector in one shot
$(\mathbf{x}_{1,b_{1}},\mathbf{x}_{2,b_{2}},\ldots,\mathbf{x}_{\lambda,b_{\lambda}})$
using our proposed quantum search-to-decision reduction.

##### Completely Classical Communication and Classical Lessor

Our protocol comes with classical lessor and classical communication for free.
We observe that from the property of the underlying NTCF-based protocol, the
lessor only has to run $\mathsf{Setup}$ and sends the classical
$\mathsf{mpk}=\\{\mathbf{A},\mathbf{s}\mathbf{A}+\mathbf{e}\\}$(naturally
extended to parallel-repeated case) to the lessee. The lessee can prepare its
own quantum key given $\mathsf{mpk}$ by preparing a superposition of
$\sum_{b,\mathbf{x},\mathbf{e}^{\prime}}\ket{b,\mathbf{x}_{b}}\ket{\mathbf{y}=\mathbf{x}_{b}\mathbf{A}+\mathbf{e}^{\prime}+b\cdot\mathbf{s}\mathbf{A}}$
by sampling $\mathbf{e}^{\prime}$ on its own. It then measures the
$\mathbf{y}$-register to obtain a public key $\mathbf{y}$ and a quantum
decryption key of the form $\ket{0,\mathbf{x}_{0}}+\ket{1,\mathbf{x}_{1}}$.
Working with the properties of NTCF (shown in [BCM+21]), the security of our
scheme will be guaranteed even for maliciously generated $\mathbf{y}$.

###  2.1 Detailed Overview on Security Proof: Reduction to NTCF and the Use of
Search-to-Decision Reduction for LWE

##### Proof Outline

We now go into slight more details about our high level proof strategy. Recall
that in the security game, a successful attacker would first need to output a
valid deletion certifiacte (which we denote by the event $\mathsf{CertPass}$)
along with that it must produce a state $\rho_{\mathsf{delete}}$ for which our
test of good decryptor $\mathsf{TI}_{\frac{1}{2}+\gamma}$ for some noticable
$\gamma$ passes with invere-polynomial probability. Namely
$\mathsf{TI}_{\frac{1}{2}+\gamma}(\rho_{\mathsf{delete}})=1$ with inverse
polynomial probability. We call this event $\mathsf{GoodDecryptor}$. It must
hold that $\Pr[\mathsf{GoodDecryptor}\wedge\mathsf{CertPass}]$ is noticable
for such successful attacker. Since we are guaranteed that there is a
noticable chance of overlap of the two events, our hope is that our extraction
procedure would extract $\\{\mathbf{x}_{0,i}\\}$ just with enough probability
to induce a noticable probability overlap between $\mathsf{CertPass}$ and
successful extraction causing our reduction to win the parallel repetion game
of Radian et. al. We call the event when the extraction holds as
$\mathsf{ExtractionOccurs}$.

At this point it is tempting to think of a search-to-decision classical
reduction for LWE and compile it to a quantum-reduction via known menthods
such as the one by Bitansky et. al. [BBK22]. Unfortunately, we don’t have a
citable theorem from this work to use directly444As discussed in Section 1.2,
in fact all existing works on post-quantum LWE search-to-decision reductions
are not directly applicable to our setting.. We need precise bounds on the
probability of success, and the running time for the extraction.

Let us briefly explain the story: for the extraction to occur we would need to
move to a world where $\mathbf{k}_{i}$’s are switched with random. While this
won’t change the probability of $\mathsf{GoodDecryptor}$ by a non-negligible
amount due to LWE security, in this hybrid deletion certificates will no
longer exist. We could infer from there using reductions compiled using
[BBK22]) that $\mathsf{ExtractionOccurs}$ with probability $\frac{1}{{\sf
poly}(\lambda)}$ for some polynomial ${\sf poly}$. This probability of
extraction will still be the same (up to a negligible loss) if we went back to
the world where $\\{\mathbf{k}_{i}\\}$ are again from the LWE distribution.
However, we can’t infer from this that the event of
$\mathsf{ExtractionOccurs}$ overlaps with $\mathsf{CertPass}$. A similar issue
was encountered by Ananth et. al. [APV23]. To address this issue the [APV23]
had to rely on new conjectures.

To address this issue, we devise a high probability search-to-decision
reduction that extracts (in the world where $\mathbf{k}_{i}$’s are random)
with probability $1-\mathsf{negl}(\lambda)$ whenever $\mathsf{GoodDecryptor}$
holds. Thus when we switch $\mathbf{k}_{i}$’s with LWE, due to LWE security,
$\mathsf{ExtractionOccurs}$ also succeeds with all but negligible security
whenever $\mathsf{GoodDecryptor}$ holds. Since we are guaranteed that there is
a noticeable overlap between $\mathsf{GoodDecryptor}$ and $\mathsf{CertPass}$,
this implies a noticeable overlap between $\mathsf{CertPass}$ and
$\mathsf{ExtractionOccurs}$.

##### Threshold Implementation

Before going into more technical details, we briefly describe the properties
of the measurement we perform on the adversarial decryptor state to test if it
succeeds on distinguishing ciphertexts with high enough probability. We will
leverage the properties of this measurement in our security proofs.

Threshold Implementation (and its related efficient measurement
implementations in Section 5) is a powerful technique by Zhandry (which is
further inspired by Mariott-Watrous’s work on QMA amplification [MW05]) used
in a number of recent works [CLLZ21, ALL+20, CMSZ22, LLQZ22].

The Threshold Implementation ${\sf TI}_{\gamma+1/2}$ has the following
properties and relations to our security:

  1. 1.

We will call $\rho$ a good decryptor if we ${\sf TI}_{\gamma+1/2}$ applied on
$\rho$ outputs 1.

  2. 2.

For a successful adversary in our game, it must produce a good decryptor
$\rho$ with probability $p$ for some noticeable $p$ (apart from giving a valid
certificate).

  3. 3.

For the remaining state $\rho^{\prime}$ after performing the above ${\sf
TI}_{\gamma+1/2}$, given the outcome being 1, applying the same ${\sf
TI}_{\gamma+1/2}$ on $\rho^{\prime}$ will yield outcome 1 with probability 1.

The above statement basically says that the measurement ${\sf
TI}_{\gamma+1/2}$ is projective and it "preserves" the advantage of the
quantum distinguisher’s state.

##### Ideas from Classical Search-to-Decision Reduction

Our quantum search-to-decision reduction the quanis inspired by Regev’s search
to decision reduction [Reg05b]. We now describe the setup of our reduction. We
consider a simpler setup than in our technical section (which is a bit
specific to our setting).

The adversary gets as input an LWE sample of the form
$(\mathbf{A},\mathbf{x}\mathbf{A}+\mathbf{e}\mod p)$ where $\mathbf{x}$ is
arbitrary secret with bounded norm $B$,
$\mathbf{A}\leftarrow\mathbb{Z}^{n\times m}_{p}$ for large enough
$m=\Omega(n\log p)$, $\mathbf{e}$ is Gaussian distributed with parameter
$\sigma$. The reduction has a quantum state $\rho$ that has an inverse
polynomial weight on vectors that enables distinguishing samples
$(\mathbf{A}^{\prime},\mathbf{x}\mathbf{A}^{\prime}+\mathbf{e}^{\prime}\mod
p)$ for randomly chosen $\mathbf{A}^{\prime}\in\mathbb{Z}^{n\times m}_{p}$ and
error $\mathbf{e}^{\prime}$ sampled according to discrete Gaussian with
parameter $\sigma^{\prime}$ superpolynomially larger than $\sigma$ from truly
random with probability $\frac{1}{2}+\gamma$.

We first describe the classical intuition and then describe how to lift that
intution to the quantum setting. Classically, we can consider recovering
$\mathsf{x}$ coordinate by coordinate. Say the first coordinate
$x_{1}\in[-B,B]$, we could choose a total of $2B$ guesses. For each guess $g$,
we could consider the process of generating samples as:

  * •

Sample a matrix $\mathbf{C}\in\mathbb{Z}^{n\times m}_{p}$ so that it is random
subject to the bottom $n-1$ rows are $0$.

  * •

Sample $\mathbf{R}$ to be a random binary matrix $\\{0,1\\}^{m\times m}$.

  * •

Set $\mathbf{A}^{\prime}=\mathbf{A}\mathbf{R}+\mathbf{C}$ and
$\mathbf{b}^{\prime}=(\mathbf{x}\mathbf{A}+\mathbf{e})\mathbf{R}+\mathbf{v}+\mathbf{e}^{\prime}$
where $\mathbf{v}$ is the guess $g$ times the first (and the only non-zero)
row of $\mathbf{C}$. Here $\mathbf{e}^{\prime}$ is generated from the discrete
Gaussian vector with parameter $\sigma^{\prime}$.

If our guess was correct, the sample that we end up producing
$(\mathbf{A}^{\prime},\mathbf{b}^{\prime})$ is distributed statistically close
to the distribution for the distinguishing problem (LWE with secret
$\mathbf{x}$). This is because $\mathbf{e}^{\prime}+\mathbf{e}\mathbf{R}$ due
to noise flodding is within ${\sf poly}(m)\cdot\frac{\sigma}{\sigma^{\prime}}$
statistical distance. Similarly, $\mathbf{A}^{\prime}$ due to LHL is within
$q^{-n}$ statistical distance from uniform if $m$ is sufficiently large. This
means that the distribution is within $\eta={\sf
poly}(m)\frac{\sigma}{\sigma^{\prime}}$ statistical distance from the relevant
distinguishing problem.

On the other hand, if the guess is incorrect, then one can observe that the
distribution produces samples that are within similar statistical distance
$\eta={\sf poly}(m)\cdot\frac{\sigma}{\sigma^{\prime}}$ from truly random
distribution.

Thus, if the guess is correct, a classical adversary can distinguish the above
distribution from random with probability at least
$\frac{1}{2}+\gamma-O(\eta)$, and likewise if the guess is incorrect the
maximum distinguishing probability is $\frac{1}{2}+O(\eta)$. We could
therefore test the adversary by making roughly ${\sf
poly}(\frac{1}{\gamma},\log\delta)$ calls to the distinguisher to guarantee
the guess is correct with probability $1-\delta$. Setting $\delta=p^{-n}$, the
reduction will extract $\mathbf{x}$ in time that’s polynomial in $B,n,m,\log
p,\frac{1}{\gamma}$ (bound on $\mathbf{x}$’s norm).

##### Our Quantum Search to Decision Reduction

Moving to the quantum setting, we have to address a number of challenges. If
we use our state to distinguish and LWE sample from random in the way above,
the state could get destructed preventing us from doing repetitions. In
particular, the classical reduction needs to run the distinguisher many times
over randomized inputs and "measure" its outcome to obtain useful information,
which seems implausible when using a quantum distinguisher.

To overcome these issue, we will leverage the properties of Threshold
Implementation. We make a key observation that the procedure where we
repeatedly create samples according to our guess $g$ and check on the
distinguisher’s output distribution to get an estimate on whether $g$ is
correct, can happen "inside" the measurement procedure ${\sf TI}$.

Suppose we have efficient projective measurements ${\sf
TI}_{g,1/2+\gamma}=({\sf TI}_{g,1/2+\gamma},\mathbf{I}-{\sf
TI}_{g,1/2+\gamma})$ for various guesses $g$. ${\sf TI}_{g,1/2+\gamma}$
projects the state $\rho$ onto vectors that distinguish the above distribution
made from the guess $g$ above from truly random with probability $1/2+\gamma$.
For simplicity, we call it ${\sf TI}_{g}$. from now on.

We define two other projections ${\sf TI}_{{\sf LWE}}$ and ${\sf TI}_{{\sf
unif}}$:

  * •

${\sf TI}_{\sf LWE}$ projects onto distinguishers good at distinguishing the
ciphertexts in our scheme from uniform random samples with probability at
least $1/2+\gamma$. (Intuitively, these are distinguishers for "noisy" LWE
instances versus uniform random)

  * •

${\sf TI}_{\sf unif}$ projects onto distinguishers good at distinguishing
uniform radnom samples from uniform random samples with probability at least
$1/2+\gamma$.

Our goal is to show that $\Pr[\mathsf{ExtractionOccurs}]\geq\Pr[{\sf TI}_{{\sf
LWE}}(\rho)=1]-\mathsf{negl}(\lambda)$. Thus it suffices to consider a world
where ${\sf TI}_{{\sf LWE}}(\rho)=1$ already happens and show that
$\Pr[\mathsf{ExtractionOccurs}]\geq 1-\mathsf{negl}(\lambda)$ in this world.
$\rho^{\prime}$ is the post measurement state.

We now make the following observations, by recalling the properties of ${\sf
TI}$:

  * •

Let $\rho^{\prime}$ be the state we get post measurement of ${\sf
TI}_{g_{i},1/2+\gamma}(\rho)\to 1$.

  * •

We start working with the state $\rho^{\prime}$ at the beginning of our
extraction algorithm.

  * •

Recall that by the projective property of ${\sf TI}$, given that outcome is
$1$, we have $\mathsf{Pr}[{\sf TI}_{{\sf LWE}},\ (\rho^{\prime})]=1$.

  * •

We start with the first entry of $\mathbf{x}$ and pick the smallest possible
value as our guess $g$ for this entry.

  * •

As we have discussed in the classical setting, when the guess $g$ is correct,
we get to create samples statistically close to LWE samples; when the guess
$g$ is incorrect, we get to create samples close to uniform random. Combining
these with properties of ${\sf TI}_{g}$ for distributionally close
measurements, we can show that:

    * –

When the guess is correct: If we apply projection ${\sf TI}_{g}$ on it for a
correct guess $g$, we will have $\Pr[{\sf TI}_{g}(\rho^{\prime})=1]$
overwhelmingly close to $1$. In this setting, we are statistically close to
measuring the original ${\sf TI}_{\sf LWE}$. That is, if a distinguisher can
distinguish between (noisy) LWE versus real random. We will therefore get
output $1$ with overwhelming probability as a consequence of ${\sf TI}$ being
a projection.

We can then assign $g$ to the entry of $\mathbf{x}$ we are guessing for, and
move on to the next entry.

    * –

When the guess is incorrect: If we apply projection ${\sf TI}_{g}$ on it for
an incorrect guess $g$, we will have $\Pr[(\mathbf{I}-{\sf
TI}_{g})(\rho^{\prime})=1]=\Pr[{\sf TI}_{g}(\rho^{\prime})=0]$ overwhelmingly
close to $1$. In this case, we are statistically close to measuring ${\sf
TI}_{\sf unif}$, i.e. asking the distinguisher to distinguish between uniform
vs. uniform. Clearly, no distinguisher can distinguish with noticeable
advantage $\gamma$. Therefore ${\sf TI}_{\sf unif}$ will output 0 for all
possible states.

We then move on to perform ${\sf TI}_{g}$ with the next possible value of $g$.

A key observation is that, in both cases above, because we obtain a certain
measurement outcome with overwhelming probability, we can apply the gentle
measurement lemma [Aar04], we can recover back to a state very close to
$\rho^{\prime}$. Thus, we could find out $\mathbf{x}$ entry by entry while
keeping our quantum state almost intact.

However, ${\sf TI}$ is not an efficient measurement and we need to make the
above procedure efficient. Fortunately, the work of Zhandry [Zha20], showed
how to replace ${\sf TI}$ by an efficient, appproximate projection. These
approximate projections induce an error of their own, but are very easy to
account for. Moreover, the fact that ${\sf TI}$ implicitly performs
amplification that can be analyzed by concentration bounds analogous to the
repetitions used in the classical reduction, is even easier to observe when we
look into its efficient implementation algorithm (see Section 5.0.1).

In the end, we further materialize our approach with some proper choice of
parameters so that the errors will not accumulate on distinguisher’s state to
a degree that affects the algorithm’s performance. Conclusively, the exact
reduction in our scheme works if the number of guesses are superpolynomially
lesser than $\frac{1}{\eta}$. See details in Section 11. On the other hand, if
we consider a clean setting where our input distributions are real LWE versus
truly uniform, our reduction works for any subexponential number of guesses
(Appendix E).

###  2.2 More on Related Works

We addtionally discuss some other related works.

##### Quantum Copy Protection

[Aar09] first built copy-protection for all unlearnable functions based on a
quantum oracle. [ALL+20] showed a construction for all unlearnable functions
based on a classical oracle. [CLLZ21, LLQZ22] showed copy protection for
signatures, decryption and PRF evaluation in the plain model. [CMP20, AKL+22]
constructed copy-protection for point functions and compute-and-compare
functions in QROM, the latter improving the security of the former.

Regarding the negative results: [AP21] demonstrated that it is impossible to
have a copy-protection scheme for all unlearnable circuits in the plain model,
assuming LWE and quantum FHE.

##### More on Secure Software Leasing

[ALL+20] observed that under a definition essentially equivalent to infinite-
term SSL, namely copy-detection, one could obtain a black-box construction for
infinite-term SSL from watermarking and public-key quantum money. [KNY21]
constructed finite-term SSL for PRFs and compute-and-compare functions from
(subexponential) LWE, with similar observations.

[BJL+21, CMP20] constructed secure software leasing for point functions and
compute-and-compare functions; [BJL+21] is information-theoretically secure
and [CMP20] is secure under QROM. They both used a stronger version of finite-
term SSL security: while the vendor will honestly check the returned state
from the adversary, the adversary can execute the leftover half of its
bipartite state maliciously, i.e., not following the instructions in the
evaluation algorithm. SSL security of this stronger finite-term variant is
only known for point/compute-and-compare functions up till now.

##### Unclonable Encryption and Certified Deletion

Unclonable encryption is studied in [GC01, BL19, AK21, AKL+22]. It is an
encryption scheme where the ciphertext is encoded in quantum information, so
that the adversary cannot split it into two copies that can both decrypt when
given a (classical) decryption key.

Certified deletion of ciphertext is studied in various works [BI20, Por22,
HMNY21, BK23, BGG+23], where the ciphertext is also encoded in a quantum state
and given to a server. When asked by the client to delete, the server must
provide a proof of deletion of the ciphertext. This bears some similarity to
our setting. But note the major difference is that in the certified deletion
of ciphertext setting, we need to show that the server no longer has
information about the encrypted message(a bit string), while in our setting we
need to show the server is deprived of a functionality. Therefore, the results
and techniques in secure key leasing and certified deletion of ciphertext are
most of the time incomparable.

##  3 Acknowledgement

Orestis Chardouvelis and Aayush Jain were supported by gifts from CyLab of CMU
and Google. Jiahui Liu was supported by DARPA under Agreement No.
HR00112020023, NSF CNS-2154149 and a Simons Investigator award.

We thank Qipeng Liu, Mark Zhandry and the authors of [APV23] for helpful
discussions.

##  4 Preliminaries

###  4.1 Quantum Information an Computation

We refer the reader to [NC02] for a reference of basic quantum information and
computation concepts.

A quantum system $Q$ is defined over a finite set $B$ of classical states. In
this work we will consider $B=\\{0,1\\}^{n}$. A pure state over $Q$ is a unit
vector in $\mathbb{C}^{|B|}$, which assigns a complex number to each element
in $B$. In other words, let $|\phi\rangle$ be a pure state in $Q$, we can
write $|\phi\rangle$ as:

$|\phi\rangle=\sum_{x\in B}\alpha_{x}|x\rangle$

where $\sum_{x\in B}|\alpha_{x}|^{2}=1$ and $\\{|x\rangle\\}_{x\in B}$ is
called the “computational basis” of $\mathbb{C}^{|B|}$. The computational
basis forms an orthonormal basis of $\mathbb{C}^{|B|}$.

Given two quantum systems $R_{1}$ over $B_{1}$ and $R_{2}$ over $B_{2}$, we
can define a product quantum system $R_{1}\otimes R_{2}$ over the set
$B_{1}\times B_{2}$. Given $|\phi_{1}\rangle\in R_{1}$ and
$|\phi_{2}\rangle\in R_{2}$, we can define the product state
$|\phi_{1}\rangle\otimes|\phi_{2}\rangle\in R_{1}\otimes R_{2}$.

We assume a quantum computer can implement any unitary transformation (by
using these basic gates, Hadamard, phase, CNOT and $\frac{\pi}{8}$ gates),
especially the following two unitary transformations:

  * •

Classical Computation: Given a function $f:X\to Y$, one can implement a
unitary $U_{f}$ over $\mathbb{C}^{|X|\cdot|Y|}\to\mathbb{C}^{|X|\cdot|Y|}$
such that for any $|\phi\rangle=\sum_{x\in X,y\in Y}\alpha_{x,y}|x,y\rangle$,

$U_{f}|\phi\rangle=\sum_{x\in X,y\in Y}\alpha_{x,y}|x,y\oplus f(x)\rangle$

Here, $\oplus$ is a commutative group operation defined over $Y$.

  * •

Quantum Fourier Transform: Let $N=2^{n}$. Given a quantum state
$|\phi\rangle=\sum_{i=0}^{2^{n}-1}x_{i}|i\rangle$, by applying only $O(n^{2})$
basic gates, one can compute $|\psi\rangle=\sum_{i=0}^{2^{n}-1}y_{i}|i\rangle$
where the sequence $\\{y_{i}\\}_{i=0}^{2^{n}-1}$ is the sequence achieved by
applying the classical Fourier transform ${\sf QFT}_{N}$ to the sequence
$\\{x_{i}\\}_{i=0}^{2^{n}-1}$:

$y_{k}=\frac{1}{\sqrt{N}}\sum_{i=0}^{2^{n}-1}x_{i}\omega_{n}^{ik}$

where $\omega_{n}=e^{2\pi i/N}$, $i$ is the imaginary unit.

One property of QFT is that by preparing $|0^{n}\rangle$ and applying ${\sf
QFT}_{2}$ to each qubit, $\left({\sf QFT}_{2}|0\rangle\right)^{\otimes
n}=\frac{1}{\sqrt{2^{n}}}\sum_{x\in\\{0,1\\}^{n}}|x\rangle$ which is a uniform
superposition over all possible $x\in\\{0,1\\}^{n}$.

######  Lemma 4.1 (Almost As Good As New(Gentle Measurement) Lemma [Aar04]).

Suppose a binary-outcome POVM measurement $({\mathcal{P}},{\mathcal{Q}})$ on a
mixed state $\rho$ yields a particular outcome with probability $1-\epsilon$.
Then after the measurement, one can recover a state $\tilde{\rho}$ such that
$\left\lVert\tilde{\rho}-\rho\right\rVert_{\mathrm{tr}}\leq\sqrt{\epsilon}$.
Here $\lVert\cdot\rVert_{\mathrm{tr}}$ is the trace distance.

##  5 Preliminaries: Testing Quantum Adversaries

In this section, we include several definitions about measurements, which are
relevant to testing whether quantum adversaries are successful in the security
games of Section 8. Part of this section is taken verbatim from [ALL+20]. As
this section only pertains directly to our security definitions for secure key
leasing schemes, the reader can skip ahead, and return to this section when
reading Section 8.

In classical cryptographic security games, the challenger typically gets some
information from the adversary and checks if this information satisfies
certain properties. However, in a setting where the adversary is required to
return _quantum_ information to the challenger, classical definitions of
“testing” whether a quantum state returned by the adversary satisfies certain
properties may result in various failures as discussed in [Zha20], as this
state may be in a superposition of “successful” and “unsuccessful”
adversaries, most likely unclonable and destructible by the classical way of
"testing" its success.

In short, we need a way to test the success probability of an adversarial
quantum state analogous to what happens classically, where the test does not
completely destruct the adversary’s state. Instead, the state after the test
has its success probability preserved in some sense. Such a procedure allows
us to do multiple measurements on the state without rendering it useless, and
thus facilitates quantum reductions.

##### Projective Implementation

Motivated by the discussion above, [Zha20] (inspired by [MW05]) formalizes a
new measurement procedure for testing a state received by an adversary. We
will be adopting this procedure when defining security of secure key leasing
schemes in Section Section 8. Consider the following procedure as a binary
POVM ${\mathcal{P}}$ acting on an alleged-copy-protected program $\rho$:
sample a uniformly random input $x$, evaluates the copy-protected program on
$x$, and checks if the output is correct. In a nutshell, the new procedure
consists of applying an appropriate projective measurement which _measures_
the success probability of the tested state $\rho$ under ${\mathcal{P}}$, and
to output “accept” if the success probability is high enough. Of course, such
measurement will not be able extract the exact success probability of $\rho$,
as this is impossible from we have argued in the discussion above. Rather, the
measurement will output a success probability from a finite set, such that the
expected value of the output matches the true success probability of $\rho$.
We will now describe this procedure in more detail.

The starting point is that a POVM specifies exactly the probability
distribution over outcomes $\\{0,1\\}$ (“success” or “failure”) on any copy-
protected program, but it does not uniquely determine the post-measurement
state. Zhandry shows that, for any binary POVM ${\mathcal{P}}=(P,I-P)$, there
exists a particularly nice implementation of ${\mathcal{P}}$ which is
projective, and such that the post-measurement state is an eigenvector of $P$.
In particular, Zhandry observes that there exists a projective measurement
${\mathcal{E}}$ which _measures_ the success probability of a state with
respect to ${\mathcal{P}}$. More precisely,

  * •

${\mathcal{E}}$ outputs a _distribution_ $D$ of the form $(p,1-p)$ from a
finite set of distribution over outcomes $\\{0,1\\}$. (we stress that
${\mathcal{E}}$ actually outputs a distribution).

  * •

The post-measurement state upon obtaining outcome $(p,1-p)$ is an
_eigenvector_ (or a mixture of eigenvectors) of $P$ with eigenvalue $p$.

A measurement ${\mathcal{E}}$ which satisfies these properties is the
measurement in the common eigenbasis of $P$ and $I-P$ (such common eigenbasis
exists since $P$ and $I-P$ commute).

Note that since ${\mathcal{E}}$ is projective, we are guaranteed that applying
the same measurement twice will yield the same outcome. Thus, what we obtain
from applying ${\mathcal{E}}$ is a state with a “well-defined” success
probability with respect to ${\mathcal{P}}$: we know exactly how good the
leftover program is with respect to the initial testing procedure
${\mathcal{P}}$.

Formally, to complete the implementation of ${\mathcal{P}}$, after having
applied ${\mathcal{E}}$, one outputs the bit $1$ with probability $p$, and the
bit $0$ with probability $1-p$. This is summarized in the following
definition.

######  Definition 5.1 (Projective Implementation of a POVM).

Let ${\mathcal{P}}=(P,Q)$ be a binary outcome POVM. Let ${\mathcal{D}}$ be a
finite set of distributions $(p,1-p)$ over outcomes $\\{0,1\\}$. Let
${\mathcal{E}}=\\{E_{p}\\}_{(p,1-p)\in{\mathcal{D}}}$ be a projective
measurement with index set ${\mathcal{D}}$. Consider the following measurement
procedure:

  * (i)

Apply the projective measurement ${\mathcal{E}}$ and obtain as outcome a
distribution $(p,1-p)$ over $\\{0,1\\}$;

  * (ii)

Output a bit according to this distribution, i.e. output $1$ w.p $p$ and
output $0$ w.p $1-p$.

We say the above measurement procedure is a projective implementation of
${\mathcal{P}}$, which we denote by ${\sf ProjImp}({\mathcal{P}})$, if it is
equivalent to ${\mathcal{P}}$ (i.e. it produces the same probability
distribution over outcomes).

Zhandry shows that any binary POVM has a projective implementation, as in the
previous definition.

######  Lemma 5.2 (Adapted from Lemma 1 in [Zha20]).

Any binary outcome POVM $\mathcal{P}=(P,Q)$ has a projective implementation
${\sf ProjImp}({\mathcal{P}})$.

Moreover, if the outcome is a distribution $(p,1-p)$ when measuring under
${\mathcal{E}}$, the collapsed state $\rho^{\prime}$ is a mixture of
eigenvectors of $P$ with eigenvalue $p$, and it is also a mixture of
eigenvectors of $Q$ with eigenvalue $1-p$.

As anticipated, the procedure that we will eventually use to test a state
received from the adversary will be to:

  * (i)

_Measure_ the success probability of the state,

  * (ii)

Accept if the outcome is large enough.

As you may guess at this point, we will employ the projective measurement
${\mathcal{E}}$ defined previously for step $(i)$. We call this variant of the
projective implementation a _threshold implementation_.

##### Threshold Implementation

The concept of threshold implementation of a POVM was proposed by Zhandry, and
formalized by Aaronson, Liu, Liu, Zhandry and Zhang [ALL+20]. The following is
a formal definition.

######  Definition 5.3 (Threshold Implementation).

Let ${\mathcal{P}}=(P,Q)$ be a binary POVM. Let ${\sf ProjImp}({\mathcal{P}})$
be a projective implementation of ${\mathcal{P}}$, and let ${\mathcal{E}}$ be
the projective measurement in the first step of ${\sf ProjImp}({\mathcal{P}})$
(using the same notation as in Definition 5.1). Let $\gamma>0$. We refer to
the following measurement procedure as a _threshold implementation_ of
${\mathcal{P}}$ with parameter $\gamma$, and we denote is as ${\sf
TI}_{\gamma}({\mathcal{P}})$.

  * •

Apply the projective measurement ${\mathcal{E}}$, and obtain as outcome a
vector $(p,1-p)$;

  * •

Output a bit according to the distribution $(p,1-p)$: output $1$ if
$p\geq\gamma$, and $0$ otherwise.

For simplicity, for any quantum state $\rho$, we denote by
$\operatorname{Tr}[{\sf TI}_{\gamma}({\mathcal{P}})\,\rho]$ the probability
that the threshold implementation applied to $\rho$ outputs $\mathbf{1}$.
Thus, whenever ${\sf TI}_{\gamma}({\mathcal{P}})$ appears inside a trace
$\operatorname{Tr}$, we treat ${\sf TI}_{\gamma}({\mathcal{P}})$ as a
projection onto the $1$ outcome (i.e. the space spanned by eigenvectors of $P$
with eigenvalue at least $\gamma$).

Similarly to Lemma 5.2, we have the following lemma.

######  Lemma 5.4.

Any binary outcome POVM $\mathcal{P}=(P,Q)$ has a threshold implementation
${\sf TI}_{\gamma}({\mathcal{P}})$ for any $\gamma$.

In this work, we are interested in threshold implementations of POVMs with a
particular structure. These POVMs represent a challenger’s test of a quantum
state received from an adversary in a security game (like the POVM described
earlier for testing whether a program evaluates correctly on a uniformly
random input). These POVMs have the following structure:

  * •

Sample a projective measurement from a set of projective measurements
$\mathcal{I}$, according to some distribution $D$ over $\mathcal{I}$.

  * •

Apply this projective measurement.

We refer to POVMs of this form as _mixtures of projective measurements_. The
following is a formal definition.

######  Definition 5.5 (Collection and Mixture of Projective Measurements).

Let $\mathcal{R}$, $\mathcal{I}$ be sets. Let $\\{(P_{i},Q_{i})\\}_{i\in I}$
be a collection of binary projective measurements $(P_{i},Q_{i}))$ over the
same Hilbert space ${\mathcal{H}}$ where ${\mathcal{P}}_{i}$ corresponds to
output 0, and ${\mathcal{Q}}_{i}$ corresponds to output 1. We will assume we
can efficiently measure the ${\mathcal{P}}_{i}$ for superpositions of $i$,
meaning we can efficiently perform the following projective measurement over
${\mathcal{I}}\otimes{\mathcal{H}}$:

$\displaystyle(\sum_{i}\ket{i}\bra{i}\otimes
P_{i},\sum_{i}\ket{i}\bra{i}\otimes Q_{i})$ (1)

Let ${\mathcal{D}}:\mathcal{R}\rightarrow\mathcal{I}$ be some distribution.
The _mixture of projective measurements_ associated to $\mathcal{R}$,
$\mathcal{I},{\mathcal{D}}$ and $\\{(P_{i},Q_{i})\\}_{i\in I}$ is the binary
POVM ${\mathcal{P}}_{\mathcal{D}}=(P_{\mathcal{D}},Q_{\mathcal{D}})$ defined
as follows:

$\displaystyle P_{D}=\sum_{i\in\cal
I}\Pr[i\leftarrow{\mathcal{D}}(R)]\,P_{i},\,\,\,\,\,\text{
}\,\,\,\,\,Q_{\mathcal{D}}=\sum_{i\in\cal
I}\Pr[i\leftarrow{\mathcal{D}}(R)]\,Q_{i},$ (2)

In other words, ${\mathcal{P}}_{D}$ is implemented in the following way:
sample randomness $r\leftarrow{\mathcal{R}}$, compute the index $i=D(r)$, and
apply the projective measurement $(P_{i},Q_{i})$. Thus, for any quantum state
$\rho$, $\operatorname{Tr}[P_{D}\rho]$ is the probability that a projective
measurement $(P_{i},Q_{i})$, sampled according to the distribution induced by
$D$, applied to $\rho$ outputs $1$.

##### Example

To further explain the above definition, we consider a concrete example: when
the input quantum state $\rho$ is supposedly a decryptor for an encryptions
with respect to public key $\mathsf{pk}$, and our goal is to measure if $\rho$
can distinguish between encryption of message 0 and message 1.

The distribution ${\mathcal{D}}$ is the distribution over all randomness used
to encrypt a message and the coin flip $b$ to decide which ciphertext to feed
to the adversary. For a ciphertext $\mathsf{ct}_{i}\leftarrow{\mathcal{D}}$,
${\mathcal{P}}_{\mathsf{ct}_{i}}$ is the measurement that runs the adversary
$\rho$ on $\mathsf{ct}_{i}$ and tests if the outcome $b^{\prime}=b$.

##### Purifying Mixtures of Projection

We next define the purified version of the above operations, called Controlled
Projections:

######  Definition 5.6 (Controlled Projective Measurements).

Let ${\mathcal{P}}=\\{{\mathcal{P}}_{i}=(P_{i},Q_{i})\\},i\in{\mathcal{I}}$ be
a collection of projective measurements over ${\mathcal{H}}$. Let
${\mathcal{D}}$ a distribution with random coin set ${\mathcal{R}}$. We will
abuse notation and let ${\mathcal{R}}$ also denote the
$|{\mathcal{R}}|$-dimensional Hilbert space. The controlled projection is the
measurement: ${\sf CProj}_{{\mathcal{P}},{\mathcal{D}}}=({\sf
CProj}^{0}_{{\mathcal{P}},{\mathcal{D}}},{\sf
CProj}^{1}_{{\mathcal{P}},{\mathcal{D}}})$ where:

$\displaystyle{\sf
CProj}^{0}_{{\mathcal{P}},{\mathcal{D}}}=\sum_{r\in{\mathcal{R}}}\ket{r}\bra{r}\otimes
P_{{\mathcal{D}}(r)},{\sf
CProj}^{1}_{{\mathcal{P}},{\mathcal{D}}}=\sum_{r\in{\mathcal{R}}}\ket{r}\bra{r}\otimes
Q_{{\mathcal{D}}(r)}$

${\sf CProj}_{{\mathcal{P}},{\mathcal{D}}}$ can be implemented using the
measurement $(\sum_{i}\ket{i}\bra{i}\otimes
P_{i},\sum_{i}\ket{i}\bra{i}\otimes Q_{i})$. First, initialize control
registers ${\mathcal{I}}$ to $0$. Then perform the map
$\ket{r}\ket{i}\to\ket{r}\ket{i\oplus{\mathcal{D}}(r)}$ to the
${\mathcal{R}}\otimes{\mathcal{I}}$ registers. Next, apply the mixture of
projective measurements assumed in Equation 1. Finally, perform the map
$\ket{r}\ket{i}\to\ket{r}\ket{i\oplus{\mathcal{D}}(r)}$ again to uncompute the
control registers, and discard the control registers.

####  5.0.1 Approximating Threshold Implementation

_Projective_ and _threshold_ implementations of POVMs are unfortunately not
efficiently computable in general.

However, they can be approximated if the POVM is a mixture of projective
measurements, as shown by Zhandry [Zha20], using a technique first introduced
by Marriott and Watrous [MW05] in the context of error reduction for quantum
Arthur-Merlin games.

##### The Uniform Test

Before we describe the ${\sf ATI}$ algorithm, we define the projection on
register ${\mathcal{R}}$ that tests if it is a superposition with each
$r\in{\mathcal{R}}$ weighted according to the distribution ${\mathcal{D}}$
555The distribution ${\mathcal{D}}$ used in ${\sf CProj}$ can in fact be an
arbitrary distribution, instead of uniform. Without loss of generality, we can
use a uniform test ${\sf IsUniform}$ and map each $r$ to an arbitrary
distribution ${\mathcal{D}}(r)$ as specified in Definition 5.6.: ${\sf
IsUniform}=(\ket{\mathbf{1}_{\mathcal{R}}}\bra{\mathbf{1}_{\mathcal{R}}},\mathcal{I}-\ket{\mathbf{1}_{\mathcal{R}}}\bra{\mathbf{1}_{\mathcal{R}}})$
where:

$\displaystyle\ket{\mathbf{1}_{\mathcal{R}}}=\frac{1}{\sqrt{|{\mathcal{R}}|}}\sum_{r\in{\mathcal{R}}}\ket{r}$

##### The Algorithm ${\sf ATI}$

We present the algorithm ${\sf
ATI}_{{\mathcal{P}},{\mathcal{D}},\gamma}^{\epsilon,\delta}$ using the syntax
from [Zha20]:

Our algorithm is parameterized by a distribution ${\mathcal{D}}$, collection
of projective measurements ${\mathcal{P}}$, and real values
$0<\epsilon,\delta,\gamma\leq 1$, and is denoted as ${\sf
ATI}_{{\mathcal{P}},{\mathcal{D}},\gamma}^{\epsilon,\delta}$.

On input a quantum state $\ket{\psi}$ over Hilbert space ${\mathcal{H}}$: 1.
Initialize a state $\ket{\mathbf{1}_{\mathcal{R}}}\ket{\psi}$. 2. Initialize a
classical list $L:=(1)$. 3. Repeat the following loop a total of
$T=\frac{\ln(4/\delta)}{\epsilon^{2}}$ times: (a) Apply ${\sf
CProj}_{{\mathcal{P}},{\mathcal{D}}}$ to register
${\mathcal{R}}\otimes{\mathcal{H}}$. Let $b_{2i-1}$ be the measurement outcome
and set $L:=(L,b_{2i-1})$. (b) Apply ${\sf IsUniform}$ to register
${\mathcal{R}}$. Let $b_{2i}$ be the measurement outcome and set
$L:=(L,b_{2i})$. 4. Let $t$ be the number of index $i$ such that
$b_{i-1}=b_{i}$ in the list $L=(0,b_{1},...,b_{2T})$, and $\tilde{p}:=t/2T$.
5. If $b_{2T}=0$, repeat the loop again until $b_{2i}=1$. 6. Discard the
${\mathcal{R}}$ register. 7. Output 1 if $\tilde{p}\geq\gamma$ and 0
otherwise.

##### ATI Properties

We will make use of the following lemma from a subsequent work of Aaronson et
al. [ALL+20].

######  Lemma 5.7 (Corollary 1 in [ALL+20]).

For any $\epsilon,\delta,\gamma\in(0,1)$, any collection of projective
measurements ${\mathcal{P}}=\\{(P_{i},Q_{i})\\}_{i\in\mathcal{I}}$, where
$\mathcal{I}$ is some index set, and any distribution $D$ over $\mathcal{I}$,
there exists a measurement procedure ${\sf
ATI}^{\epsilon,\delta}_{{\mathcal{P}},D,\gamma}$ that satisfies the following:

  1. 1.

${\sf ATI}^{\epsilon,\delta}_{{\mathcal{P}},D,\gamma}$ implements a binary
outcome measurement. For simplicity, we denote the probability of the
measurement outputting $\mathbf{1}$ on $\rho$ by $\operatorname{Tr}[{\sf
ATI}^{\epsilon,\delta}_{{\mathcal{P}},D,\gamma}\,\rho]$.

  2. 2.

For all quantum states $\rho$, $\operatorname{Tr}[{\sf
ATI}^{\epsilon,\delta}_{{\mathcal{P}},D,\gamma-\epsilon}\,\rho]\geq\operatorname{Tr}[{\sf
TI}_{\gamma}({\mathcal{P}}_{D})\,\rho]-\delta$.

  3. 3.

For all quantum states $\rho$, let $\rho^{\prime}$ be the post-measurement
state after applying ${\sf ATI}^{\epsilon,\delta}_{{\mathcal{P}},D,\gamma}$ on
$\rho$, and obtaining outcome $1$. Then, $\operatorname{Tr}[{\sf
TI}_{\gamma-2\epsilon}({\mathcal{P}}_{D})\,\rho^{\prime}]\geq 1-2\delta$.

  4. 4.

The expected running time is $T_{{\mathcal{P}},D}\cdot{\sf
poly}(1/\epsilon,1/(\log\delta))$, where $T_{{\mathcal{P}},D}$ is the combined
running time of sampling according to $D$, of mapping $i$ to $(P_{i},Q_{i})$,
and of implementing the projective measurement $(P_{i},Q_{i})$.

Intuitively the corollary says that if a quantum state $\rho$ has weight $p$
on eigenvectors with eigenvalues at least $\gamma$, then the measurement ${\sf
ATI}^{\epsilon,\delta}_{{\mathcal{P}},D,\gamma}$ will produce with probability
at least $p-\delta$ a post-measurement state which has weight $1-2\delta$ on
eigenvectors with eigenvalues at least $\gamma-2\epsilon$. Moreover, the
running time for implementing ${\sf
ATI}^{\epsilon,\delta}_{{\mathcal{P}},D,\gamma}$ is proportional to ${\sf
poly}(1/\epsilon,1/(\log\delta))$, which is a polynomial in $\lambda$ as long
as $\epsilon$ is any inverse polynomial and $\delta$ is any inverse sub-
exponential function.

#####  ${\sf TI}$ and ${\sf ATI}$ For Computationally/Statistically
Indistinguishable Distributions

The following theorems will be used in the proof of security for our SKL
encryption scheme in Section 10.

Informally, the lemma states the following. Let ${\mathcal{P}}_{D_{0}}$ and
${\mathcal{P}}_{D_{1}}$ be two mixtures of projective measurements, where
$D_{0}$ and $D_{1}$ are two computationally indistinguishable distributions.
Let $\gamma,\gamma^{\prime}>0$ be inverse-polynomially close. Then for any
(efficiently constructible) state $\rho$, the probabilities of obtaining
outcome $1$ upon measuring ${\sf TI}_{\gamma}({\mathcal{P}}_{D_{0}})$ and
${\sf TI}_{\gamma^{\prime}}({\mathcal{P}}_{D_{1}})$ respectively are
negligibly close.

######  Theorem 5.8 (Theorem 6.5 in [Zha20]).

Let $\gamma>0$. Let ${\mathcal{P}}$ be a collection of projective measurements
indexed by some set $\cal I$. Let $\rho$ be an efficiently constructible mixed
state, and let $D_{0},D_{1}$ be two efficiently sampleable and computationally
indistinguishable distributions over $\cal I$. For any inverse polynomial
$\epsilon$, there exists a negligible function $\delta$ such that

$\displaystyle\operatorname{Tr}[{\sf
TI}_{\gamma-\epsilon}({\mathcal{P}}_{D_{1}})\rho]\geq\operatorname{Tr}[{\sf
TI}_{\gamma}({\mathcal{P}}_{D_{0}})\rho]-\delta\,,$

where ${\mathcal{P}}_{D_{i}}$ is the mixture of projective measurements
associated to ${\mathcal{P}}$ and $D_{i}$.

######  Corollary 5.9 (Corollary 6.9 in [Zha20]).

Let $\rho$ be an efficiently constructible, potentially mixed state, and let
${\mathcal{D}}_{0},{\mathcal{D}}_{1}$ be two computationally indistinguishable
distributions. Then for any inverse polynomial $\epsilon$ and any function
$\delta$, there exists a negligible $\mathsf{negl}(\cdot)$ such that:

$\operatorname{Tr}[{\sf
ATI}_{{\mathcal{D}}_{1},{\mathcal{P}},\gamma-3\epsilon}^{\epsilon,\delta}(\rho)]\geq\operatorname{Tr}[{\sf
ATI}_{{\mathcal{D}}_{0},{\mathcal{P}},\gamma}^{\epsilon,\delta}(\rho)]-2\delta-\mathsf{negl}(\lambda)$

Unfortunately these above two theorems do not possess precise enough error
parameters for our use in some settings. We additionally show a theorem with
more precise parameters for two statistically close distributions.

######  Theorem 5.10.

let ${\mathcal{D}}_{0},{\mathcal{D}}_{1}$ be two statistically-close
distributions over ${\mathcal{R}}$, with distance $\eta$. Then for any inverse
polynomial $\epsilon$ and any function $\delta$, it holds that:

$\operatorname{Tr}[{\sf
ATI}_{{\mathcal{D}}_{1},{\mathcal{P}},\gamma-\epsilon}^{\epsilon,\delta}(\rho)]\geq\operatorname{Tr}[{\sf
ATI}_{{\mathcal{D}}_{0},{\mathcal{P}},\gamma}^{\epsilon,\delta}(\rho)]-O({\sf
poly}(1/\epsilon,1/\log\delta)\cdot(\frac{1}{|{\mathcal{R}}|}+\eta))$

Since we work with $|{\mathcal{R}}|$ with exponential size, we will assume
$\frac{1}{|{\mathcal{R}}|}$ to be suppressed when we use the theoreom.

We refer the proof or the above theorem to Section C.2

##  6 Lattice Preliminaries

In this section, we recall some of the notations and concepts about lattice
complexity problems and lattice-based cryptography that will be useful to our
main result.

###  6.1 General definitions

A _lattice_ $\mathcal{L}$ is a discrete subgroup of $\mathbb{R}^{m}$, or
equivalently the set

$\mathcal{L}(\mathbf{b}_{1},\dots,\mathbf{b}_{n})=\left\\{\sum_{i=1}^{n}x_{i}\mathbf{b}_{i}~{}:~{}x_{i}\in\mathbb{Z}\right\\}$

of all integer combinations of $n$ linearly independent vectors
$\mathbf{b}_{1},\dots,\mathbf{b}_{n}\in\mathbb{R}^{m}$. Such
$\mathbf{b}_{i}$’s form a _basis_ of $\mathcal{L}$.

The lattice $\mathcal{L}$ is said to be _full-rank_ if $n=m$. We denote by
$\lambda_{1}(\mathcal{L})$ the first minimum of $\mathcal{L}$, defined as the
length of a shortest non-zero vector of $\mathcal{L}$.

##### Discrete Gaussian and Related Distributions

For any $s>0$, define

$\rho_{s}(\mathbf{x})=\exp(-\pi\|\mathbf{x}\|^{2}/s^{2})$

for all $\mathbf{x}\in\mathbb{R}^{n}$. We write $\rho$ for $\rho_{1}$. For a
discrete set $S$, we extend $\rho$ to sets by $\rho_{s}(S)=\sum_{\mathbf{x}\in
S}\rho_{s}(\mathbf{x})$. Given a lattice $\mathcal{L}$, the _discrete
Gaussian_ $\mathcal{D}_{\mathcal{L},s}$ is the distribution over $\mathcal{L}$
such that the probability of a vector $\mathbf{y}\in\mathcal{L}$ is
proportional to $\rho_{s}(\mathbf{y})$:

$\Pr_{X\leftarrow\mathcal{D}_{\mathcal{L},s}}[X=\mathbf{y}]=\frac{\rho_{s}(\mathbf{y})}{\rho_{s}(\mathcal{L})}.$

Using standard subgaussian tail-bounds, one can show we can show the following
claim.

######  Claim 6.1.

Let $m\in\mathbb{N}$, $\sigma>0$, then it holds that:

$\Pr_{\mathbf{e}\leftarrow\mathcal{D}_{\mathbb{Z}^{m},\sigma}}[\|\mathbf{e}\|>m\sigma]<\exp(-\tilde{\Omega}(m)).$

The following is Theorem 4.1 from [GPV07] that shows an efficient algorithm to
sample from the discrete Gaussian.

Now we recall the Learning with Errors (LWE) distribution.

######  Definition 6.2.

Let $\sigma=\sigma(n)\in(0,1)$. For $\mathbf{s}\in\mathbb{Z}_{p}^{n}$, the LWE
distribution $A_{\mathbf{s},p,\sigma}$ over
$\mathbb{Z}_{p}^{n}\times\mathbb{Z}_{p}$ is sampled by independently choosing
$\mathbf{a}$ uniformly at random from $\mathbb{Z}_{p}^{n}$, and
$e\leftarrow\mathcal{D}_{\mathbb{Z},\sigma}$, and outputting
$\left(\mathbf{a},\langle\mathbf{a},\mathbf{s}\rangle+e\mod p\right)$. The LWE
assumption $\mathsf{LWE}_{n,m,\sigma,p}$ states that $m$ samples from
$A_{\mathbf{s},p,\sigma}$ for a randomly chosen
$\mathbf{s}\leftarrow\mathbb{Z}^{n}_{p}$ are indistinguishable from $m$ random
vectors $\mathbb{Z}^{n+1}_{p}$.

###  6.2 Trapdoor Sampling for LWE

We will need the following definition of a lattice trapdoor [GPV07, MP13,
Vai20]. For $\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$, we define the rank $m$
lattice

$\mathcal{L}^{\bot}(\mathbf{A})=\\{\mathbf{z}\in\mathbb{Z}^{m}\>:\>\mathbf{A}\mathbf{z}=\mathbf{0}\pmod{q}\\}\;.$

A lattice trapdoor for $\mathbf{A}$ is a set of short linearly independent
vectors in $\mathcal{L}^{\bot}(\mathbf{A})$.

######  Definition 6.3.

A matrix $\mathbf{T}\in\mathbb{Z}^{m\times m}$ is a $\beta$-good lattice
trapdoor for a matrix $\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$ if

  1. 1.

$\mathbf{A}\mathbf{T}=\mathbf{0}\pmod{q}$.

  2. 2.

For each column vector $\mathbf{t}_{i}$ of $\mathbf{T}$,
$\|\mathbf{t}_{i}\|_{\infty}\leq\beta$.

  3. 3.

$\mathbf{T}$ has rank $m$ over $\mathbb{R}$.

######  Theorem 6.4.

[GPV07, MP13] There is an efficient algorithm $\mathsf{GenTrap}$ that, on
input $1^{n},q,m=\Omega(n\log q)$, outputs a matrix $\mathbf{A}$ distributed
statistically close to uniformly on $\mathbb{Z}_{q}^{n\times m}$, and a
$O(m)$-good lattice trapdoor $\mathbf{T}$ for $\mathbf{A}$.

Moreover, there is an efficient algorithm $\mathsf{INVERT}$ that, on input
$(\mathbf{A},\mathbf{T})$ and $\mathbf{s}^{\top}\mathbf{A}+\mathbf{e}^{\top}$
where $\lVert\mathbf{e}\rVert\leq q/(C_{T}\sqrt{n\log q})$ and $C_{T}$ is a
universal constant, returns $\mathbf{s}$ and $\mathbf{e}$ with overwhelming
probability over
$(\mathbf{A},\mathbf{T})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)$.

######  Lemma 6.5.

[Noise Smudging, [DGTK+10] Let $y,\sigma>0$. Then, the statistical distance
between the distribution ${\mathcal{D}}_{\mathbb{Z},\sigma}$ and
${\mathcal{D}}_{\mathbb{Z},\sigma+y}$ is at most $y/\sigma$.

######  Lemma 6.6.

(Leftover Hash Lemma(SIS version))

The leftover hash lemma says that if $m=\Omega(n\log q)$, then if you sample
$\mathbf{A}\leftarrow\mathbb{Z}_{q}^{n\times
m},\mathbf{x}\leftarrow\\{0,1\\}^{m}$ and
$\mathbf{y}\leftarrow\mathbb{Z}^{m}_{q}$, we have:

$(\mathbf{A},\mathbf{A}\cdot\mathbf{x})\approx_{q^{-n}}(\mathbf{A},\mathbf{y}))$

###  6.3 Structural Properties of GSW Homomorphic Encryption

Our scheme will build upon the GSW levelled FHE construction [GSW13]. We
recall its structure here, for more details refer to [GSW13]. In GSW scheme,
the public keys consists of matrix $\mathbf{B}\in\mathbb{Z}^{n\times m}_{q}$
where $m=\Omega(n\log q)$. This matrix is pseudorandom due to LWE. The secret
key is a vector $\mathbf{s}\in\mathbb{Z}^{1\times n}_{q}$ such that
$\mathbf{s}\cdot\mathbf{B}=\mathbf{e}$ for a small norm error vector
$\mathbf{e}$. Such matrices can be constructed easily using the LWE
assumption.

For any such matrix $\mathbf{B}$, to encrypt a bit $\mu\in\\{0,1\\}$, the
encryption algorithm produces a ciphertext
$\mathsf{ct}\in\mathbb{Z}^{n\times\lceil n\log q\rceil}_{q}$ as follows.
Sample a random matrix $\mathbf{R}$ to be a random small norm (where for
instance each entry is chosen independently from $\\{+1,-1\\})$. Then we
compute $\mathsf{ct}=\mathbf{B}\mathbf{R}+\mu\mathbf{G}$ where $\mathbf{G}$ is
the Gadget matrix [MP13]:
$\mathbf{G}=[\mathbf{I}\otimes[2^{0},2^{1},\cdots,2^{\lceil\log
q\rceil-1}]\|\mathbf{0}^{m\times(m-n\lceil\log
q\rceil)}]\in\mathbb{Z}^{n\times m}$ and $\mathbf{I}$ is the $n\times n$
identity. $\mathbf{G}$ converts a binary representation of a vector back to
its original vector representation over the field $\mathbb{Z}_{q}$; the
associated (non-linear) inverse operation $\mathbf{G}^{-1}$ converts vectors
in $Z_{q}$ to their binary representation.

Note that $\mathbf{B}\mathbf{R}$ is once again an LWE matrix in the same
secret $\mathbf{s}$ and satisfies $\mathbf{s}\mathbf{B}\mathbf{R}$ is low norm
therefore $\mathbf{s}\mathsf{ct}\approx\mathbf{s}\mu\mathbf{G}$ which could be
used to learn $\mu$.

One can compute NAND operation as follows. Say we have
$\mathsf{ct}_{1}=\mathbf{B}\mathbf{R}_{1}+\mu_{1}\mathbf{G}$ and
$\mathsf{ct}_{2}=\mathbf{B}\mathbf{R}_{2}+\mu_{2}\mathbf{G}$. One can compute
the bit-decomposition of $\mathsf{ct}_{2}$, $\mathbf{G}^{-1}(\mathsf{ct}_{2})$
that simply expands out $\mathsf{ct}_{2}$ component wise by replacing every
coordinate of $\mathsf{ct}_{2}$ by a its binary decomposition vector of size
$\lceil\log_{2}q\rceil$. Observe that $\mathbf{G}^{-1}(\mathsf{ct}_{2})$ is a
low norm matrix in $\mathbb{Z}^{\lceil n\log q\rceil\times\lceil n\log
q\rceil}_{p}$ Then, one can compute
$\mathsf{ct}_{\times}=\mathsf{ct}_{1}\mathbf{G}^{-1}(\mathsf{ct}_{2})$. This
yields a ciphertext
$\mathsf{ct}_{\times}=\mathbf{B}(\mathbf{R}_{1}\mathbf{G}^{-1}(\mathsf{ct}_{2})+\mu_{1}\mathbf{R}_{2})+\mu_{1}\mu_{2}\mathbf{G}$.
Observe that the randomness
$(\mathbf{R}_{1}\mathbf{G}^{-1}(\mathsf{ct}_{2})+\mu_{1}\mathbf{R}_{2})$ is
small norm and the invariant is still maintained. Finally to compute NAND
operation one simply outputs
$\mathsf{ct}_{\mathsf{NAND}}=\mathbf{G}-\mathsf{ct}_{\times}$ yielding a
ciphertext encryption $1-\mu_{1}\mu_{2}$.

The security proof follows form the fact that by LHL, $\mathbf{B}\mathbf{R}$
is random provided $\mathbf{B}$ is chosen at random. By the security of LWE,
$\mathbf{B}$ is pseudorandom therefore $\mathbf{B}\mathbf{R}$ is also
pseudorandom.

##  7 Preliminaries: Noisy Claw Free Trapdoor Families

###  7.1 Noisy Trapdoor Claw-Free Families

The following definition of NTCF families is taken verbatim from [BCM+21,
Definition 6]. For a more detailed exposition of the definition, we refer the
readers to the prior work.

######  Definition 7.1 (NTCF family).

Let $\lambda$ be a security parameter. Let $\mathcal{X}$ and $\mathcal{Y}$ be
finite sets. Let $\mathcal{K}_{\mathcal{F}}$ be a finite set of keys. A family
of functions

$\mathcal{F}=\big{\\{}f_{k,b}:\mathcal{X}\rightarrow\mathcal{D}_{\mathcal{Y}}\big{\\}}_{k\in\mathcal{K}_{\mathcal{F}},b\in\\{0,1\\}}$

is called a _noisy trapdoor claw free (NTCF) family_ if the following
conditions hold:

  1. 1.

Efficient Function Generation. There exists an efficient probabilistic
algorithm $\textrm{GEN}_{\mathcal{F}}$ which generates a key
$k\in\mathcal{K}_{\mathcal{F}}$ together with a trapdoor $t_{k}$:

$(k,t_{k})\leftarrow\textrm{GEN}_{\mathcal{F}}(1^{\lambda}).$

  2. 2.

Trapdoor Injective Pair. For all keys $k\in\mathcal{K}_{\mathcal{F}}$ the
following conditions hold.

    1. (a)

Trapdoor: There exists an efficient deterministic algorithm
$\textrm{INV}_{\mathcal{F}}$ such that for all $b\in\\{0,1\\}$,
$x\in\mathcal{X}$ and $y\in\mathsf{SUPP}(f_{k,b}(x))$,
$\textrm{INV}_{\mathcal{F}}(t_{k},b,y)=x$. Note that this implies that for all
$b\in\\{0,1\\}$ and $x\neq x^{\prime}\in\mathcal{X}$,
$\mathsf{SUPP}(f_{k,b}(x))\cap\mathsf{SUPP}(f_{k,b}(x^{\prime}))=\emptyset$.

    2. (b)

Injective pair: There exists a perfect matching
$\mathcal{R}_{k}\subseteq\mathcal{X}\times\mathcal{X}$ such that
$f_{k,0}(x_{0})=f_{k,1}(x_{1})$ if and only if
$(x_{0},x_{1})\in\mathcal{R}_{k}$.

  3. 3.

Efficient Range Superposition. For all keys $k\in\mathcal{K}_{\mathcal{F}}$
and $b\in\\{0,1\\}$ there exists a function
$f^{\prime}_{k,b}:\mathcal{X}\to\mathcal{D}_{\mathcal{Y}}$ such that the
following hold.

    1. (a)

For all $(x_{0},x_{1})\in\mathcal{R}_{k}$ and
$y\in\mathsf{SUPP}(f^{\prime}_{k,b}(x_{b}))$,
INV${}_{\mathcal{F}}(t_{k},b,y)=x_{b}$ and INV${}_{\mathcal{F}}(t_{k},b\oplus
1,y)=x_{b\oplus 1}$.

    2. (b)

There exists an efficient deterministic procedure CHKF that, on input $k$,
$b\in\\{0,1\\}$, $x\in\mathcal{X}$ and $y\in\mathcal{Y}$, returns $1$ if
$y\in\mathsf{SUPP}(f^{\prime}_{k,b}(x))$ and $0$ otherwise. Note that CHKF is
not provided the trapdoor $t_{k}$.

    3. (c)

For every $k$ and $b\in\\{0,1\\}$,

$\mathbb{E}_{x\leftarrow_{U}\mathcal{X}}\big{[}H^{2}(f_{k,b}(x),f^{\prime}_{k,b}(x))\big{]}\leq\mu(\lambda),$

for some negligible function $\mu(\cdot)$. Here $H^{2}$ is the Hellinger
distance. Moreover, there exists an efficient procedure SAMPF that on input
$k$ and $b\in\\{0,1\\}$ prepares the state

$\frac{1}{\sqrt{|\mathcal{X}|}}\sum_{x\in\mathcal{X},y\in\mathcal{Y}}\sqrt{(f^{\prime}_{k,b}(x))(y)}\ket{x}\ket{y}.$

  4. 4.

Adaptive Hardcore Bit. For all keys $k\in\mathcal{K}_{\mathcal{F}}$ the
following conditions hold, for some integer $w$ that is a polynomially bounded
function of $\lambda$.

    1. (a)

For all $b\in\\{0,1\\}$ and $x\in\mathcal{X}$, there exists a set
$G_{k,b,x}\subseteq\\{0,1\\}^{w}$ such that
$\Pr_{d\leftarrow_{U}\\{0,1\\}^{w}}[d\notin G_{k,b,x}]$ is negligible, and
moreover there exists an efficient algorithm that checks for membership in
$G_{k,b,x}$ given $k,b,x$ and the trapdoor $t_{k}$.

    2. (b)

There is an efficiently computable injection
$\mathcal{J}:\mathcal{X}\to\\{0,1\\}^{w}$, such that $\mathcal{J}$ can be
inverted efficiently on its range, and such that the following holds. If

$\displaystyle H_{k}$
$\displaystyle=\big{\\{}(b,x_{b},d,d\cdot(\mathcal{J}(x_{0})\oplus\mathcal{J}(x_{1})))\,|\;b\in\\{0,1\\},(x_{0},x_{1})\in\mathcal{R}_{k},d\in
G_{k,0,x_{0}}\cap G_{k,1,x_{1}}\big{\\}},$ $\displaystyle\overline{H}_{k}$
$\displaystyle=\\{(b,x_{b},d,c)\,|\;(b,x,d,c\oplus 1)\in H_{k}\big{\\}},$

then for any quantum polynomial-time procedure $\mathcal{A}$ there exists a
negligible function $\mu(\cdot)$ such that

$\left|\Pr_{(k,t_{k})\leftarrow\textrm{GEN}_{\mathcal{F}}(1^{\lambda})}[\mathcal{A}(k)\in
H_{k}]-\Pr_{(k,t_{k})\leftarrow\textrm{GEN}_{\mathcal{F}}(1^{\lambda})}[\mathcal{A}(k)\in\overline{H}_{k}]\right|\leq\mu(\lambda).$

###  7.2 (Extended) NTCF from LWE

######  Theorem 7.2 ([BCM+21, Theorem 4.1] [Mah18, Theorem 9.2]).

Assuming the post-quantum hardness of ${\sf LWE}_{n,m,q,B_{L}}$, (extended)
NTCF families exist.

The following construction description is mostly taken verbatim from [Mah18].

####  7.2.1 Parameter Choice

Let $\lambda$ be the security parameter. All other parameters are functions of
$\lambda$. Let $q\geq 2$ be a prime integer. Let $\ell,n,m,w\geq 1$ be
polynomially bounded functions of $\lambda$ and $B_{L},B_{V},B_{P}$ be
Gaussian parameters, $B_{X},B_{S}$ be norm bounds, such that the following
conditions hold:

  1. 1.

$n=\Omega(\ell\log q)$ and $m=\Omega(n\log q)$

  2. 2.

$w=n\lceil\log q\rceil$.

  3. 3.

$B_{P}=\frac{q}{2C_{T}\sqrt{mn\log q}}$ where $C_{T}$ is the constant in
theorem 6.4.

  4. 4.

$2\sqrt{n}\leq B_{L}\leq B_{V}\leq B_{P}\leq B_{X}$

  5. 5.

The ratios $\frac{B_{V}}{B_{L}}$, $\frac{B_{P}}{B_{V}}$,
$\frac{B_{P^{\prime}}}{B_{P}}$, $\frac{B_{X}}{B_{S}}$ are all super-polynomial
in $\lambda$.

  6. 6.

We denote $[B_{X}]$ as all integer taking values
$[-B_{X},-B_{X}+1\cdots,B_{X}-1,B_{X}]$. Similarly for $B_{S}$. $B_{S}$ can in
fact be $\\{0,1\\}$.

####  7.2.2 Noisy Trapdoor claw-Free Families (2-to-1 Mode)

Let Let $\mathcal{X}=\mathbb{Z}^{n}_{q}$ and $\mathcal{Y}=\mathbb{Z}^{m}_{q}$
. The key space is $\mathbb{Z}^{n\times m}_{q}\times\mathbb{Z}^{m}_{q}$. For
$b\in\\{0,1\\}$, $\mathbf{x}\in\mathcal{X}$ and key
$k=(\mathbf{A},\mathbf{s}\mathbf{A}+\mathbf{e})$ where
$(\mathbf{A},\mathsf{td}_{A})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)$,
$\mathbf{s}\leftarrow\mathbb{Z}_{q}^{n},\mathbf{e}\leftarrow{\mathcal{D}}_{\mathbb{Z}_{q}^{m},B_{L}}$,
the density $f_{k,b}(x)$ is defined as:

$\displaystyle\forall\mathbf{y}\in\mathcal{Y}:(f_{k,b}(\mathbf{x}))(\mathbf{y})={\mathcal{D}}_{\mathbb{Z}^{m}_{q},B_{P}}(\mathbf{y}-\mathbf{x}^{\top}\mathbf{A}-b\cdot\mathbf{s}^{\top}\mathbf{A})$

It follows that:

$\displaystyle\mathrm{SUPP}(f_{0,k}(\mathbf{x}))=\\{\mathbf{y}=\mathbf{x}\mathbf{A}+\mathbf{e}^{\prime}|\lVert\mathbf{e}^{\prime}\rVert\leq
B_{P}\sqrt{m}\\}$
$\displaystyle\mathrm{SUPP}(f_{1,k}(\mathbf{x}))=\\{\mathbf{y}=\mathbf{x}\mathbf{A}+\mathbf{e}^{\prime}+\mathbf{s}\mathbf{A}|\lVert\mathbf{e}^{\prime}\rVert\leq
B_{P}\sqrt{m}\\}$

$(\mathbf{x}_{0},\mathbf{x}_{1})$ will be an injective pair such that
$f_{0,k}(\mathbf{x}_{0})=f_{1,k}(\mathbf{x}_{1})$ if and only if
$\mathbf{x}_{0}=\mathbf{x}_{1}+\mathbf{s}$.

####  7.2.3 Noisy Trapdoor Injective Families (Injective Mode)

We now describe the trapdoor injective functions, or informally, the
"injective mode" of trapdoor claw-free functions. Let Let
$\mathcal{X}=\mathbb{Z}^{n}_{q}$ and $\mathcal{Y}=\mathbb{Z}^{m}_{q}$. The key
space is $\mathbb{Z}^{n\times m}_{q}\times\mathbb{Z}^{m}_{q}$.

For $b\in\\{0,1\\}$, $\mathbf{x}\in\mathcal{X}$ and key
$k=(\mathbf{A},\mathbf{u})$, where
$(\mathbf{A},\mathsf{td}_{A})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)$,
$\mathbf{u}$ is sampled uniformly random up to the condition that there _does
not_ exist $\mathbf{s},\mathbf{e}$ such that
$\mathbf{s}^{\top}\mathbf{A}+\mathbf{e}^{\top}=\mathbf{u}$ and
$\lVert\mathbf{e}\rVert\leq\frac{q}{C_{T}\sqrt{n\log q}}$, which happens with
all but negligible probability.

The density $g_{k,b}(x)$ is defined as:

$\displaystyle\forall\mathbf{y}\in\mathcal{Y}:(g_{k,b}(\mathbf{x}))(\mathbf{y})={\mathcal{D}}_{\mathbb{Z}^{m}_{q},B_{P}}(\mathbf{y}-\mathbf{x}\mathbf{A}-b\cdot\mathbf{u})$

The injective trapdoor functions $g_{b,k}$ looks like follows:

$\displaystyle\mathrm{SUPP}(g_{0,k}(\mathbf{x}))=\\{\mathbf{y}=\mathbf{x}^{\top}\mathbf{A}+\mathbf{e}^{\prime}|\lVert\mathbf{e}^{\prime}\rVert\leq
B_{P}\sqrt{m}\\}$
$\displaystyle\mathrm{SUPP}(g_{1,k}(\mathbf{x}))=\\{\mathbf{y}=\mathbf{x}\mathbf{A}+\mathbf{e}^{\prime}+\mathbf{u}|\lVert\mathbf{e}^{\prime}\rVert\leq
B_{P}\sqrt{m}\\}$

$\mathrm{SUPP}(g_{0,k}(\mathbf{x}))$ and $\mathrm{SUPP}(g_{1,k}(\mathbf{x}))$
are disjoint as long as $B_{P}\leq\frac{q}{2C_{T}\sqrt{mn\log q}}$.

There is also an inversion function $\mathsf{INV}$ in the injective mode:
$\mathsf{INV}(\mathsf{td},\mathbf{y})\to\mathbf{x}$ will give some unique
$\mathbf{x}$ on input $(\mathsf{td},\mathbf{y})$.

######  Lemma 7.3.

[Mah18] The 2-to-1 mode and injective mode are computationally
indistinguishable by ${\sf LWE}_{n,m,q,B_{L}}$.

####  7.2.4 Efficient Range Preparation for NTCF with Small LWE Secrets

We refer the reader to Section 4.3 of [BCM+21] for a detailed description of
$\mathrm{SAMP}_{\sf LWE}$ procedure to efficiently prepapre the claw state:
$(\ket{0,\mathbf{x}_{0}}+\ket{1,\mathbf{x}_{1}}),y$. We describe it here
briefly for the sake of coherence in presentation.

In order for our security parameters in the reduction to go through, we
deviate slightly from the exact parameters on $\mathcal{X}$ and $\mathbf{s}$
in [BCM+21]. We work with small secrets $\mathcal{X}=[B_{X}]^{n}$ and
$\mathbf{s}\in[B_{S}]^{n}$.

At the first step, the procedure creates the following superposition:

$\sum_{\mathbf{e}^{\prime}\in\mathbb{Z}_{q}^{m}}\sqrt{{\mathcal{D}}_{\mathbb{Z}_{q},B_{P}}(\mathbf{e}^{\prime})}\ket{\mathbf{e}^{\prime}}$

In step 2 of $\mathrm{SAMP}_{\sf LWE}$, we prepare uniform superposition of
$\mathbf{x}\in[B_{X}]$.

$\frac{1}{\sqrt{2|B_{X}|^{n}}}\sum_{b\in\\{0,1\\},\mathbf{x},\mathbf{e}^{\prime}}\sqrt{{\mathcal{D}}_{\mathbb{Z}_{q},B_{P}}(\mathbf{e}^{\prime})}\ket{b,\mathbf{x}}\ket{\mathbf{e}^{\prime}}$

The rest of the steps are the same. In step 3, we apply the key
$(\mathbf{A},\mathbf{u})$, controlled by the bit $b$ to indicate whether to
use $\mathbf{u}$, where $\mathbf{u}=\mathbf{s}\mathbf{A}+\mathbf{e}$ in the
2-to-1 setting and $\mathbf{u}\xleftarrow{\$}\mathbb{Z}_{q}^{m}$ in the
injective mode. We get a state:

$\frac{1}{\sqrt{2|B_{X}|^{n}}}\sum_{b\in\\{0,1\\},\mathbf{x},\mathbf{e}^{\prime}}\sqrt{{\mathcal{D}}_{\mathbb{Z}_{q},B_{P}}(\mathbf{e}^{\prime})}\ket{b,\mathbf{x}}\ket{\mathbf{e}^{\prime}}\ket{\mathbf{x}\mathbf{A}+\mathbf{e}^{\prime}+b\cdot\mathbf{u}}$

Next, we uncompute the register containing $\mathbf{e}^{\prime}$ using the
information in register containing $\mathbf{x}$, the key
$(\mathbf{A},\mathbf{u})$ and the last register.

It is easy to observe that the efficient range preparation in [BCM+21] Section
4.3 and acquirance of the claw state also works in our setting with our choice
of parameters having $B_{X}/B_{S}$ superpolynomially large, or simply letting
$B_{S}=\\{0,1\\}$ and $B_{X}$ a superpolynomial.

With probability $(1-\mathsf{negl}(\lambda))$, when one measures the image
register to obtain a value $\mathbf{y}$, we will obtain the state
$\frac{1}{\sqrt{2}}(\ket{0,\mathbf{x}_{0}}+\ket{1,\mathbf{x}_{1}})$ where
$f_{0,k}(\mathbf{x}_{0})=f_{1,k}(\mathbf{x}_{1})=\mathbf{y}$

###  7.3 Parallel Repetition of An NTCF-based Protocol

We first define the single-instance game from [RS19]. The game is abstracted
as a "1-of-2" puzzle with "2-of-2 soundness", where the verifier randomly asks
the prover to output a preimage $\mathbf{x}\in\mathcal{X}$ or an adaptive
hardcore bit for the same image $\mathbf{y}\in\mathcal{Y}$.

######  Definition 7.4 (1-of-2 Puzzle from NTCF [RS19]).

The protocol proceeds as follows, using the notations from Section 7.1.

  * •

The verifier samples a key
$(k,\mathsf{td})\leftarrow\mathsf{GEN}_{\mathcal{F}}(1^{\lambda})$ and send
$k$ to the prover. The verifier keeps the trapdoors $\mathsf{td}$

  * •

The prover sends back a committed image value $\mathbf{y}$.

  * •

The verifier samples a random bit $\delta\in\\{0,1\\}$ and sends $\delta$ to
the prover.

  * •

If $\delta=0$, the prover sends back some $\mathbf{x}\in\mathcal{X}$; else if
$b=1$, the prover sends back a string $(c,\mathbf{d})$.

  * •

The verifier does the following checks on each $(\mathbf{y},\mathbf{x})$ or
$(\mathbf{y},c,\mathbf{d})$:

    * –

When $\delta=0$: Check
$\mathbf{x}\in\mathsf{INV}(\mathsf{td},b\in\\{0,1\\},\mathbf{y})$ 666This step
can also be performed publicly using $CHK_{\mathcal{F}}$..

    * –

When $\delta=1$: Find both $\mathbf{x}_{0},\mathbf{x}_{1}$ using
$\mathsf{INV}(\mathsf{td},b\in\\{0,1\\},\mathbf{y})$. Check if
$c=\mathbf{d}\cdot(\mathcal{J}(\mathbf{x}_{0})\oplus\mathcal{J}(\mathbf{x}_{1}))$.

[RS19] showed the following property for the above protocol using the LWE-
based NTCF from [BCM+21].

1-of-2 Completeness: Any BQP prover will answer one of the challenges for
$\delta=0$ or $\delta=1$ with probability 1.

2-of-2 Soundness: The 2-of-2 soundness error in the above protocol is the
probability that a prover can provide both the 1-challenge answer $\mathbf{x}$
and the 0-challenge answer $(c,\mathbf{d})$ correctly.

The above protocol has 2-of-2 soundness $1/2$ for any BQP prover [RS19,
BCM+21].

##### Parallel Repitition

We now describe a special type of parallel-repeated protocol based on the
NTCF. In this protocol, we only consider the "2-of-2" setting: the verifier
samples multiple keys independently; for every single key, the verifier simply
asks the prover to provide both the answer to the 0-challenge and the answer
to the 1-challenge.

Its parallel repetition soundness was shown in [RS19].

######  Definition 7.5 (Parallel-Repeated 2-of-2 NTCF-protocol)).

The protocol proceeds as follows, using the notations from Section 7.1.

  * •

The verifier samples $\ell$ number of keys
$(k_{i},\mathsf{td}_{i})\leftarrow\mathsf{GEN}_{\mathcal{F}}(1^{\lambda}),i\in[\ell]$
independently and send $\\{k_{i}\\}_{i\in[\ell]}$ to the prover. The verifier
keeps the trapdoors $\\{\mathsf{td}_{i}\\}_{i\in[\ell]}$

  * •

The prover sends back $\ell$ tuple of values
$\\{(\mathbf{y}_{i},\mathbf{x}_{i},c_{i},\mathbf{d}_{i})\\}_{i\in[\ell]}$.

  * •

The verifier does the following checks on each
$(\mathbf{y}_{i},\mathbf{x}_{i},c_{i},\mathbf{d}_{i})$ for $i\in[\ell]$:

    * –

Find both $\mathbf{x}_{i,0},\mathbf{x}_{i,1}$ using
$\mathsf{INV}(\mathsf{td}_{i},b\in\\{0,1\\},\mathbf{y}_{i})$.

    * –

Check if
$c_{i}=\mathbf{d}_{i}\cdot(\mathcal{J}(\mathbf{x}_{i,0})\oplus\mathcal{J}(\mathbf{x}_{i,1}))$.

  * •

If all the checks pass, the verifier outputs 1; else outputs 0.

######  Theorem 7.6 (Parallel Repetition Soundness of NTCF-based Protocol,
[RS19] Theorem 15 rephrased).

The above protocol has soundness $(1-\mathsf{negl}(\ell))$ for any BQP prover.

######  Remark 7.7.

Note that in our construction Section 9.2 we let the verifier further check if
$\mathbf{y}_{i},\mathbf{x}_{i}$ are well-formed. This will not affect the
above soundness because it only puts more restrictions on the
prover/adversary.

######  Remark 7.8.

In this work, we only need the soundness to use the above simple protocol
where we require the adversary to produce both the "preimage answer" and the
"adaptive hardcore bit answer" at the same time. Clearly, the "completeness"
of the above protocol is not well-defined, but we omit this property in our
setting.

We do not need the more complicated version of repetition in [Mah18] studied
in [CCY20, AF16].

##  8 Secure Key Leasing with Classical Communication: Definition

###  8.1 Secure Key Leasing PKE with Classical Lessor

######  Definition 8.1 (Public Key Encryption with Classcal Leaser).

A PKE with secure key leasing with a classical vendor consists of the
algorithms ($\mathsf{Setup}$, $\mathsf{KeyGen}$, $\mathsf{Enc}$,
$\mathsf{Dec}$, $\mathsf{Delete}$, $\mathsf{VerDel}$) defined as follows:

$\mathsf{Setup}(1^{\lambda})$: take input a security parameter $\lambda$,
output a (classical) master public key $\mathsf{mpk}$ and a (classical)
trapdoor $\mathsf{td}$.

$\mathsf{KeyGen}(1^{\lambda})$: take as input a (classical) public key
$\mathsf{mpk}$, output a quantum decryption key $\rho_{\mathsf{sk}}$ and a
classical public key $\mathsf{pk}$.

$\mathsf{Enc}(\mathsf{pk},\mu)$: given a public key $\mathsf{pk}$ and a
plaintext $\mu\in\\{0,1\\}$, output a ciphertext $\mathsf{ct}$.

$\mathsf{Dec}(\rho_{\mathsf{sk}},\mathsf{ct})$: given a quantum state
$\rho_{\mathsf{pk}}$ and a ciphertext $\mathsf{ct}$, output a message $\mu$
and the state $\rho_{\mathsf{sk}}^{\prime}$

$\mathsf{Delete}(\rho_{\mathsf{sk}})$: given the quantum state
$\rho_{\mathsf{sk}}$, output a classical deletion certificate $\mathsf{cert}$

$\mathsf{VerDel}(\mathsf{pk},\mathsf{td},\mathsf{cert})$: given a public key
$\mathsf{pk}$, a classical certificate $\mathsf{cert}$ and the trapdoor
$\mathsf{td}$, output $\mathsf{Valid}$ or $\mathsf{Invalid}$.

We refer the readers to Appendix A on a few side comments and remarks about
the definition.

##### Correctness

A PKE Scheme with secure quantum key leasing
($\mathsf{Setup},\mathsf{KeyGen}$, $\mathsf{Enc}$, $\mathsf{Dec}$,
$\mathsf{Delete}$, $\mathsf{VerDel}$) satisfies correctness if the following
hold.

Decryption Correctness: There exists a negligible function
$\mathsf{negl}(\cdot)$, for all $\lambda\in\mathbb{N}$, for all
$\mu\in\mathcal{M}$:

$\Pr\left[\mathsf{Dec}(\rho_{\mathsf{sk}},\mathsf{ct})=\mu:\begin{matrix}(\mathsf{mpk},\mathsf{td})\leftarrow\mathsf{Setup}(1^{\lambda})\\\
(\mathsf{pk},\rho_{\mathsf{sk}})\leftarrow\mathsf{KeyGen}(\mathsf{mpk})\\\
\mathsf{ct}\leftarrow\mathsf{Enc}(\mathsf{pk},\mu)\end{matrix}\right]\geq
1-\mathsf{negl}(\lambda)$

##### Reusability

the above decryption correctness should hold for an arbitrary polynomial
number of uses.

##### Verifying Deletion Correctness

: There exists a negligible function $\mathsf{negl}(\cdot)$, for all
$\lambda\in\mathbb{N}$:

$\Pr\left[\mathsf{Valid}\leftarrow\mathsf{VerDel}(\mathsf{pk},\mathsf{td},\mathsf{cert}):\begin{matrix}(\mathsf{mpk},\mathsf{td})\leftarrow\mathsf{Setup}(1^{\lambda})\\\
(\mathsf{pk},\rho_{\mathsf{sk}})\leftarrow\mathsf{KeyGen}(\mathsf{mpk})\\\
\mathsf{cert}\leftarrow\mathsf{Delete}(\rho_{\mathsf{sk}})\end{matrix}\right]\geq
1-\mathsf{negl}(\lambda)$

##### IND-SKL-PKE Security

We give a "classical friendly" security definition same as the one used in
[APV23, AKN+23], except that we have a classical leaser.

Then in the next subsection Section 8.2, we will then present a "strong"
security definition in the following section, section 8.2. The latter is the
one we will actually use in the proof and will imply the following IND-PKE-SKL
security.

######  Definition 8.2 (IND-PKE-SKL Security(Classical Client)).

where the experiment $\text{IND-PKE-
SKL}(\mathcal{A},1^{\lambda},b\in\\{0,1\\})$ between a challenger and the
adversary $\mathcal{A}$ is defined as follows:

  * •

The challenger runs
$\mathsf{Setup}(1^{\lambda})\to(\mathsf{mpk},\mathsf{td})$. It sends
$\mathsf{mpk}$ to the adversary $\mathcal{A}$. $\mathcal{A}$ computes
$(\mathsf{pk},\rho_{\mathsf{sk}})\leftarrow\mathsf{KeyGen}(\mathsf{mpk})$ and
publishes $\mathsf{pk}$.

  * •

The challenger requests that $\mathcal{A}$ runs the deletion algorithm
$\mathsf{Delete}$. $\mathcal{A}$ returns a deletion certificate
$\mathsf{cert}$.

  * •

The challenger runs $\mathsf{VerDel}(\mathsf{pk},\mathsf{td},\mathsf{cert})$
and continues if $\mathsf{VerDel}(\mathsf{pk},\mathsf{td},\mathsf{cert})$
outputs $\mathsf{Valid}$; else the challenger outputs $\bot$ and aborts.

  * •

$\mathcal{A}$ submits a plaintext $\mu\in\\{0,1\\}^{\ell}$ to the challenger.

  * •

The challenger flips a bit $b\xleftarrow{\$}\\{0,1\\}$.

  * •

If $b=0$, the challenger sends back the ciphertext
$\mathsf{ct}\leftarrow\mathsf{Enc}(\mathsf{pk},\mu)$. If $b=1$ the challenger
sends a random ciphertext from the possible space of all ciphertexts for of
$\ell$-bit messages, $\mathsf{ct}\xleftarrow{\$}\mathcal{C}$

  * •

Output $\mathcal{A}$’s guess for the bit b, b’.

A PKE Scheme with Secure Key Leasing and fully classical communication
($\mathsf{Setup},\mathsf{KeyGen}$, $\mathsf{Enc}$, $\mathsf{Dec}$,
$\mathsf{Delete}$, $\mathsf{VerDel}$) is secure if, for every $\mathsf{QPT}$
adversary $\mathcal{A}$ if there exists negligible functions
$\mathsf{negl}(\cdot)$ such that one of the following holds for all
$\lambda\in\mathbb{N}$:

$\displaystyle\lvert\Pr\left[\text{IND-PKE-
SKL}(\mathcal{A},1^{\lambda},b=0)=1\right]-\Pr\left[\text{IND-PKE-
SKL}(\mathcal{A},1^{\lambda},b=1)=1\right]\rvert\leq\mathsf{negl}(\lambda)$

######  Remark 8.3.

Regarding the security in Definition 8.2: In other words, in order to win, the
adversary $\mathcal{A}$ needs to do both of the following for some noticeable
$\epsilon_{1},\epsilon_{2}$:

  1. 1.

$\lvert\Pr\left[\text{IND-PKE-
SKL}(\mathcal{A},1^{\lambda},b=0)=1\right]-\Pr\left[\text{IND-PKE-
SKL}(\mathcal{A},1^{\lambda},b=1)=1\right]\rvert\geq\epsilon_{1}(\lambda)$ and

  2. 2.

$\Pr[\text{IND-PKE-
SKL}(\mathcal{A},1^{\lambda},b\in\\{0,1\\})\neq\bot]\geq\epsilon_{2}(\lambda)$

We need the second inequality above to hold because in the case where
$\Pr[\text{IND-PKE-SKL}(\mathcal{A},1^{\lambda},b\in\\{0,1\\})=\bot]\geq
1-\mathsf{negl}_{2}(\lambda)$,for some negligible $\mathsf{negl}_{2}(\cdot)$,
the probabilities $\Pr\left[\text{IND-PKE-
SKL}(\mathcal{A},1^{\lambda},b=0)=1\right]$ and $\Pr\left[\text{IND-PKE-
SKL}(\mathcal{A},1^{\lambda},b=1)=1\right]$ will also have negligible
difference.

###  8.2 Strong SKL-PKE PKE Security: Threshold Implementation Version

In this section, we define a security notion we call Strong SKL-PKE, which is
described via the measurement ${\sf TI}$ in Section 5. We show that it implies
the regular security notion in the previous section.

To define the strong security/implementable security, we first define what it
means to test the success probability of a quantum decryptor.

######  Definition 8.4 (Testing a quantum decryptor).

Let $\gamma\in[0,1]$. Let $\mathsf{pk}$ be a public key and $\mu$ be a
message. We refer to the following procedure as a test for a $\gamma$-good
quantum decryptor with respect to $\mathsf{pk}$ and $\mu$ used in the
following sampling procedure:

  * •

The procedure takes as input a quantum decryptor $\rho$.

  * •

Let $\mathcal{P}=(P,I-P)$ be the following mixture of projective measurements
(in terms of Definition 5.5) acting on some quantum state $\rho$:

    * –

Compute $\mathsf{ct}_{0}\leftarrow\mathsf{Enc}(\mathsf{pk},\mu)$, the
encryption of message $\mu\in\\{0,1\\}$.

    * –

Compute $\mathsf{ct}_{1}\leftarrow\mathcal{C}$, a random ciphertext from the
possible space of all ciphertexts for 1-bit messages.

    * –

Sample a uniform $b\leftarrow\\{0,1\\}$.

    * –

Run the quantum decryptor $\rho$ on input $\mathsf{ct}_{b}$. Check whether the
outcome is $b$. If so, output $1$, otherwise output $0$.

  * •

Let ${\sf TI}_{1/2+\gamma}({\mathcal{P}})$ be the threshold implementation of
${\mathcal{P}}$ with threshold value $\frac{1}{2}+\gamma$, as defined in
Definition 5.3. Run ${\sf TI}_{1/2+\gamma}({\mathcal{P}})$ on $\rho$, and
output the outcome. If the output is $1$, we say that the test passed,
otherwise the test failed.

By Lemma 5.4, we have the following corollary.

######  Corollary 8.5 ($\gamma$-good Decryptor).

Let $\gamma\in[0,1]$. Let $\rho$ be a quantum decryptor. Let ${\sf
TI}_{1/2+\gamma}({\mathcal{P}})$ be the test for a $\gamma$-good decryptor
defined above. Then, the post-measurement state conditioned on output $1$ is a
mixture of states which are in the span of all eigenvectors of $P$ with
eigenvalues at least $1/2+\gamma$.

Now we are ready to define the strong $\gamma$-anti-piracy game.

######  Definition 8.6 ($\gamma$-Strong Secure Key Leasing Security Game).

Let $\lambda\in\mathbb{N}^{+}$, and $\gamma\in[0,1]$. The strong $\gamma$-PKE-
SKL game is the following game between a challenger and an adversary
$\mathcal{A}$.

  1. 1.

The challenger runs
$\mathsf{Setup}(1^{\lambda})\to(\mathsf{mpk},\mathsf{td})$. It sends
$\mathsf{mpk}$ to the adversary $\mathcal{A}$. $\mathcal{A}$ computes
$(\mathsf{pk},\rho_{\mathsf{sk}})\leftarrow\mathsf{KeyGen}(\mathsf{mpk})$ and
publishes $\mathsf{pk}$.

  2. 2.

The challenger requests that $\mathcal{A}$ runs the deletion algorithm
$\mathsf{Delete}({\sf\rho_{\mathsf{sk}}})$. $\mathcal{A}$ returns a deletion
certificate $\mathsf{cert}$ to the challenger.

  3. 3.

The challenger runs $\mathsf{VerDel}(\mathsf{pk},\mathsf{td},\mathsf{cert})$
and continues if $\mathsf{VerDel}(\mathsf{pk},\mathsf{td},\mathsf{cert})$
returns $\mathsf{Valid}$; else it outputs $\bot$ and aborts, if
$\mathsf{VerDel}(\mathsf{pk},\mathsf{td},\mathsf{cert})$ returns
$\mathsf{Invalid}$.

  4. 4.

$\mathcal{A}$ outputs a message $\mu$ and a (possibly mixed) state
$\rho_{\mathsf{Delete}}$ as a quantum decryptor.

  5. 5.

The challenger runs the test for a $\gamma$-good decryptor on
$\rho_{\mathsf{Delete}}$ with respect to $\mathsf{pk}$ and $\mu$. The
challenger outputs $1$ if the test passes, otherwise outputs $0$.

We denote by $\sf{StrongSKL}(1^{\lambda},\gamma,\mathcal{A})$ a random
variable for the output of the game.

######  Definition 8.7 (Strong PKE-SKL Security).

Let $\gamma:\mathbb{N}^{+}\rightarrow[0,1]$. A secure key leasing scheme
satisfies strong $\gamma$-SKL security, if for any QPT adversary
$\mathcal{A}$, there exists a negligible function $\mathsf{negl}(\cdot)$ such
that for all $\lambda\in\mathbb{N}$:

$\displaystyle\Pr\left[b=1,b\leftarrow\sf{StrongSKL}(1^{\lambda},\gamma(\lambda),\mathcal{A})\right]\leq\mathsf{negl}(\lambda)$
(3)

Next, we show that the strong PKE-SKL definition(Definition 8.7) implies the
IND-PKE-SKL definition(Definition 8.2).

######  Claim 8.8.

Suppose a secure key leasing scheme satisfies strong $\gamma$-SKL security
(Definition 8.7) for any inverse polynomial $\gamma$, then it also satisfies
IND-PKE-SKL security (Definition 8.2).

###### Proof.

We refer the reader to appendix A for the proof. ∎

##  9 Secure Key Leasing with Classical Lessor/Client: Construction

###  9.1 Parameters

We present our parameters requirements for the following construction. All the
parameters are the same as in Section 7.2.1, with a few new paramters added.

Let $\lambda$ be the security parameter. All other parameters are functions of
$\lambda$. Let $q\geq 2$ be a prime integer. Let $\ell,k,n,m,w\geq 1$ be
polynomially bounded functions of $\lambda$ and
$B_{L},B_{V},B_{P},B_{P^{\prime}}$ be Gaussian parameters and $B_{X},B_{S}$
are norm parameters such that the following conditions hold:

  1. 1.

$n=\Omega(\ell\log q)$ and $m=\Omega(n\log q)$

  2. 2.

$k$ can be set to $\lambda$.

  3. 3.

$w=\lceil n\log q\rceil$.

  4. 4.

$B_{P}=\frac{q}{2C_{T}\sqrt{mn\log q}}$ where $C_{T}$ is the constant in
Theorem 6.4.

  5. 5.

$2\sqrt{n}\leq B_{L}\leq B_{V}\leq B_{P}\leq B_{X}\leq B_{P^{\prime}}$

  6. 6.

The ratios $\frac{B_{V}}{B_{L}}$, $\frac{B_{P}}{B_{V}}$,
$\frac{B_{P^{\prime}}}{B_{P}}$, $\frac{B_{X}}{B_{S}}$, and
$\frac{B_{P^{\prime}}}{B_{X}^{2}\cdot B_{P}}$ are super-polynomial in
$\lambda$.

  7. 7.

$B_{P^{\prime}}\cdot m^{d}\leq q$ where $d$ is the depth of the circuit in FHE
evaluation, to be further discussed in Appendix B.

  8. 8.

We denote $[B_{X}]$ as all integer taking values $[-B_{X},\cdots,B_{X}]$.
Similarly for $B_{S}$. We can also simply take $B_{S}:=\\{0,1\\}$ in our
scheme.

###  9.2 Scheme Construction

We first present our construction for a secure key leasing protocol. How the
protocol works with a classical client comes naturally with our defintion in
Definition 8.2. Nevertheless, we provide a protocol description in Appendix D.

  * •

$\mathsf{Setup}(1^{\lambda})$: On input the security parameter $1^{\lambda}$,
the $\mathsf{Setup}$ algorithm works as follows:

    * –

Sample $k=k(\lambda)$ matrices $\mathbf{A}_{i}\in\mathbb{Z}_{q}^{n\times m}$
along with their trapdoors $\mathsf{td}_{i}$ using the procedure
$\mathsf{GenTrap}(1^{n},1^{m},q)$(Theorem 6.4):
$(\mathbf{A}_{i},\mathsf{td}_{i})\xleftarrow{\$}\mathsf{GenTrap}(1^{n},1^{m},q),\\\
\forall i\in[k]$.

    * –

Sample $\mathbf{s}_{i}\xleftarrow{\$}[B_{s}]^{n},\forall i\in[k]$ and
$\mathbf{e}_{i}\xleftarrow{\$}D_{\mathbb{Z}_{q}^{1\times m},B_{V}},,\forall
i\in[k]$.

    * –

Output
$\mathsf{mpk}=\\{f_{i,0},f_{i,1}\\}_{i=1}^{k}=\\{(\mathbf{A}_{i},\mathbf{s}_{i}\mathbf{A}_{i}+\mathbf{e}_{i})\\}_{i=1}^{k}$
and the trapdoor $\mathsf{td}=\\{\mathsf{td}_{i}\\}_{i=1}^{k}$.

  * •

$\mathsf{KeyGen}$($\mathsf{mpk}$):

    * –

Take in
$\mathsf{mpk}=\\{f_{i,0},f_{i,1}\\}_{i=1}^{k}=\\{(\mathbf{A}_{i},\mathbf{s}_{i}\mathbf{A}_{i}+\mathbf{e}_{i})\\}_{i=1}^{k}$
.

    * –

Prepare the quantum key of the form
$\rho_{\mathsf{sk}}=\bigotimes_{i=1}^{k}\left(\frac{1}{\sqrt{2}}(\ket{0,\mathbf{x}_{i,0}}+\ket{1,\mathbf{x}_{i,1}})\right)$
along with $\\{\mathbf{y}_{i}\\}_{i\in[k]}$ where
$\mathbf{y}_{i}=f_{i,0}(\mathbf{x}_{0,i})=f_{i,1}(\mathbf{x}_{1,i})$ for each
$i\in[k]$, according to the procedure in Section 7.2.4.

Note that
$f_{i,b}(\mathbf{x}_{b,i})=\mathbf{x}_{b,i}\mathbf{A}_{i}+\mathbf{e}_{i}^{\prime}+b_{i}\cdot\mathbf{s}_{i}\mathbf{A}_{i},\;\mathbf{e}_{i}^{\prime}\xleftarrow{\$}D_{Z_{q}^{m},B_{P}};\mathbf{x}_{i,b_{i}}\in[B_{X}]^{n},\forall
i\in[k]$.

    * –

Output public key
$\mathsf{pk}=\\{(\mathbf{A}_{i},\mathbf{s}_{i}\mathbf{A}_{i}+\mathbf{e}_{i},\mathbf{y}_{i})\\}_{i=1}^{k}$
and quantum decryption key ${\sf\rho_{\mathsf{sk}}}$.

  * •

$\mathsf{Enc}(\mathsf{pk},\mu)$: On input a public key
$\mathsf{pk}=\\{(\mathbf{A}_{i},\mathbf{s}_{i}\mathbf{A}_{i}+\mathbf{e}_{i},\mathbf{y}_{i})\\}_{i=1}^{k}$
and a plaintext $\mu\in\\{0,1\\}$ the algorithm samples
$\mathbf{R}\xleftarrow{\$}\\{0,1\\}^{m\times m}$ and computes a ciphertext as
follows:

$\displaystyle\mathsf{ct}=\begin{bmatrix}\mathbf{s}_{1}\mathbf{A}_{1}+\mathbf{e}_{1}\\\
\mathbf{A}_{1}\\\ \cdots\\\ \cdots\\\
\mathbf{s}_{k}\mathbf{A}_{k}+\mathbf{e}_{k}\\\ \mathbf{A}_{k}\\\
\sum_{i\in[k]}\mathbf{y}_{i}\end{bmatrix}\cdot\mathbf{R}+\mathbf{E}+\mu\cdot\mathbf{G}_{(n+1)k+1}$

where $\mathbf{G}_{(n+1)k+1}$ is the gadget matrix of dimensions
$(nk+k+1)\times m$.

$\mathbf{E}\in\mathbb{Z}_{q}^{\left(nk+k+1\right)\times m}$ is a matrix with
all rows having $\mathbf{0}^{m}$ except the last row being
$\mathbf{e}^{\prime\prime}$, where
$\mathbf{e}^{\prime\prime}\leftarrow{\mathcal{D}}_{\mathbb{Z}_{q}^{m},B_{P^{\prime}}}$.

Output $\mathsf{ct}$.

  * •

Dec$({\sf\rho_{\mathsf{sk}}},\mathsf{ct})$: On quantum decryption key
$\rho_{\mathsf{sk}}=\bigotimes_{i=1}^{k}\left(\frac{1}{\sqrt{2}}(\ket{0,\mathbf{x}_{i,0}}+\ket{1,\mathbf{x}_{i,1}})\right)$
and a ciphertext $\mathsf{ct}\in\mathbb{Z}_{q}^{(nk+k+1)\times m}$, the
decryption is performed in a coherent way as follows.

    * –

View the key as a vector of dimension $1\times(n+1)k$; pad the key with one-
bit of classical information, the value -1 at the end, to obtain a vector with
dimension $1\times(nk+k+1)$:

$\displaystyle\begin{bmatrix}\frac{1}{\sqrt{2}}((\ket{0,\mathbf{x}_{1,0})}+\ket{(1,\mathbf{x}_{1,1})})|\cdots|\frac{1}{\sqrt{2}}(\ket{(0,\mathbf{x}_{k,0})}+\ket{(1,\mathbf{x}_{k,1}}))|\ket{-1}\end{bmatrix}$
$\displaystyle=\frac{1}{\sqrt{2^{k}}}\sum_{\mathbf{b}_{j}\in\\{0,1\\}^{k}}\lvert\mathbf{b}_{j,1},\mathbf{x}_{1,\mathbf{b}_{j,1}},\cdots,\mathbf{b}_{j,k},\mathbf{x}_{k,\mathbf{b}_{j,k}}\rangle\ket{-1}$

Denote this above vector by $\mathbf{sk}$.

    * –

Compute
$(-\mathbf{sk})\cdot\mathsf{ct}\cdot\mathbf{G}^{-1}(\mathbf{0}^{nk+k}|\lfloor\frac{q}{2}\rfloor)$
coherently and write the result on an additional empty register
$\mathsf{work}$ (a working register other than the one holding $\mathbf{sk}$).

    * –

Make the following computation in another additional register $\mathsf{out}$:
write $\mu^{\prime}=0$ if the outcome in the previous register of the above
computation is less than $\frac{q}{4}$; write $\mu^{\prime}=1$ otherwise.
Uncompute the $\mathsf{work}$ register in the previous step using
$\mathbf{sk}$ and $\mathsf{ct}$. Measure the final $\mathsf{out}$ register and
output the measurement outcome.

  * •

Delete($\rho_{\mathsf{sk}}$):

    * –

For convenience, we name the register holding state
$\frac{1}{\sqrt{2}}(\ket{0,\mathbf{x}_{i,0}}+\ket{1,\mathbf{x}_{i,1}})$ in
$\rho_{\mathsf{sk}}$ as register $\mathsf{reg_{i}}$.

    * –

For each register $\mathsf{reg_{i}},i\in[k]$: apply invertible function
${\mathcal{J}}:\mathcal{X}\to\\{0,1\\}^{w}$ where ${\mathcal{J}}(x)$ returns
the binary decomposition of $x$. Since it is invertible, we can uncompute the
original $\mathbf{x}_{i,b_{i}}$’s in $\mathsf{reg_{i}}$ and leave only
$\ket{0,{\mathcal{J}}(\mathbf{x}_{i,0})}+\ket{1,{\mathcal{J}}(\mathbf{x}_{i,1})}$.

    * –

Apply a quantum Fourier transform over $\mathbb{F}_{2}$ to all $k(w+1)$ qubits
in registers $\\{\mathsf{reg}_{i}\\}_{i\in[k]}$

    * –

measure in computational basis to obtain a string
$(c_{1},\mathbf{d}_{1},\cdots,c_{k},\mathbf{d}_{k})\in\\{0,1\\}^{wk+k}$.

  * •

VerDel($\mathsf{td},\mathsf{pk},\mathsf{cert}$): On input a deletion
certificate $\mathsf{cert}\\{c_{i},\mathbf{d}_{i}\\}_{i=1}^{n}$, public key
$\mathsf{pk}=\\{f_{i,0},f_{i,1},\mathbf{y}_{i}\\}_{i\in k}$ and the trapdoor
$\mathsf{td}=\\{\mathsf{td}_{i}\\}_{i\in k}$.

    * –

Compute
$\mathbf{x}_{i,b_{i}}\leftarrow\mathsf{INV}(\mathsf{td}_{i},b,\mathbf{y}_{i})$
for both $b=0,1$.

    * –

Check if $\mathbf{x}_{i,b_{i}}\in[B_{X}]^{n}$ for all
$i\in[k],b_{i}\in\\{0,1\\}$. If not, output $\mathsf{Invalid}$. If yes,
continue.

    * –

Check if
$\lVert\mathbf{y}_{i}-\mathbf{x}_{i,b_{i}}-b_{i}\cdot\mathbf{s}_{i}\mathbf{A}_{i}\rVert\leq
B_{P}\sqrt{m}$, for all $i\in[k],b_{i}\in\\{0,1\\}$. If not, output
$\mathsf{Invalid}$. If yes, continue.

    * –

Output $\mathsf{Valid}$ if
$c_{i}=\mathbf{d}_{i}\cdot({\mathcal{J}}(\mathbf{x}_{i,0})\oplus{\mathcal{J}}(\mathbf{x}_{i,1})(\mod
2)),\forall i\in[k]$ and $\mathsf{Invalid}$ otherwise.

We defer the proof on correctness to Section 9.3 and the security proof to
Section 10.

###  9.3 Correctness

##### Decryption Correctness

The above scheme satisfies decryption correctness.

###### Proof.

Note that we can write out the entire quantum key as
${\sf\rho_{\mathsf{sk}}}=\frac{1}{\sqrt{2^{k}}}\sum_{\mathbf{b}_{j}\in\\{0,1\\}^{k}}\lvert\mathbf{b}_{j,1},\mathbf{x}_{k,\mathbf{b}_{j,1}},\cdots,\mathbf{b}_{j,k},\mathbf{x}_{1,\mathbf{b}_{j,k}}\rangle$
By applying the decryption procedure, we will have:

$\displaystyle=\frac{1}{\sqrt{2^{k}}}\sum_{\mathbf{b}_{j}\in\\{0,1\\}^{k}}\lvert\mathbf{b}_{j,1},\mathbf{x}_{1,\mathbf{b}_{j,1}},\cdots,\mathbf{b}_{j,k},\mathbf{x}_{k,\mathbf{b}_{j,k}}\rangle\lvert(-\sum_{i\in[k]}(\mathbf{x}_{i,\mathbf{b}_{j,i}}\mathbf{A}_{i}+\mathbf{b}_{j,i}(\mathbf{s}_{i}\mathbf{A}_{i}+\mathbf{e}_{i}))+\sum_{i\in[k]}\mathbf{y}_{i})$
$\displaystyle\cdot\mathbf{R}\mathbf{G}^{-1}(\mathbf{0}|\lfloor\frac{q}{2}\rfloor)+\mathbf{e}^{\prime\prime}\cdot\mathbf{G}^{-1}(\mathbf{0}|\lfloor\frac{q}{2}\rfloor)+\mathbf{sk}\cdot\mu\mathbf{G}\mathbf{G}^{-1}(\mathbf{0}|\lfloor\frac{q}{2}\rfloor)\rangle_{\sf
work}\ket{0}_{\sf out}$
$\displaystyle=\frac{1}{\sqrt{2^{k}}}\sum_{\mathbf{b_{j}}\in(\\{0,1\\}^{k}}\lvert\mathbf{b}_{j,1},\mathbf{x}_{1,\mathbf{b}_{j,1}},\cdots,\mathbf{b}_{j,k},\mathbf{x}_{k,\mathbf{b}_{j,k}}\rangle\lvert((\sum_{i\in[k]}-\mathbf{b}_{j,i}\cdot\mathbf{e}_{i}+\mathbf{e}_{i}^{\prime})\cdot\mathbf{R}+\mathbf{e}^{\prime\prime})\mathbf{G}^{-1}(\mathbf{0}|\lfloor\frac{q}{2}\rfloor)+\lfloor\frac{q}{2}\rfloor\cdot\mu\rangle_{\sf
work}\ket{0}_{\sf out}$
$\displaystyle=\frac{1}{\sqrt{2^{k}}}\sum_{\mathbf{b_{j}}\in(\\{0,1\\}^{k}}\lvert\mathbf{b}_{j,1},\mathbf{x}_{1,\mathbf{b}_{j,1}},\cdots,\mathbf{b}_{j,k},\mathbf{x}_{k,\mathbf{b}_{j,k}}\rangle\ket{\mu}_{\sf
out}\text{ (round, write on ${\sf out}$ and uncompute ${\sf work}$)}$

∎

Since we have
$\lVert\sum_{i}(\mathbf{e}_{i}^{\prime}+\mathbf{e}_{i})\rVert\leq
k\cdot\sqrt{m}\cdot
B_{P},\lVert\mathbf{e}^{\prime\prime}\rVert\leq\sqrt{m}\cdot B_{P^{\prime}}$
and
$\lVert(\sum_{i\in[k]}(\mathbf{b}_{i}\cdot\mathbf{e}_{i}^{\prime}+\mathbf{e}_{i})\cdot\mathbf{R}+\mathbf{e}^{\prime\prime})\mathbf{G}^{-1}(\mathbf{0}|\lfloor\frac{q}{2}\rfloor)\rVert\leq\frac{q}{4}$
for all support $\mathbf{b}_{j}\in\\{0,1\\}^{k}$ in the final outcome, we will
obtain $\mu$ with all but negligible probability, for all support in the above
state. We can write the final output for $\mu$ in the third (rightmost)
register and use $\mathsf{ct}$ to uncompute the second register and recover
${\sf\rho_{\mathsf{sk}}}$.

##### Reusability

Reusability of the decryption key follows from correctness and the gentle
measurement lemma [Aar18].

##### Deletion Verification Correctness

The first two steps in $\mathsf{VerDel}$ will pass for any honestly prepared
$\\{\mathbf{y}_{i}\\}_{i\in[k]}$ with $(1-\mathsf{negl}(\lambda))$
probability.

The $\mathsf{Delete}$ procedure will operate on the state $\rho_{\mathsf{sk}}$
as follows. For each
$\frac{1}{\sqrt{2}}(\ket{0,\mathbf{x}_{i,0}}+\ket{1,\mathbf{x}_{i,1}})$,
$i\in[k]$, the $\mathsf{Delete}$ procedure will turn the state into:

$\displaystyle\frac{1}{\sqrt{2}}\sum\ket{0,{\mathcal{J}}(\mathbf{x}_{i,0})}+\ket{1,{\mathcal{J}}(\mathbf{x}_{i,1})}\text{
after applying ${\mathcal{J}}(\cdot)$ and uncomputing $\mathbf{x}_{i,b_{i}}$
register}$
$\displaystyle\to\frac{1}{\sqrt{2^{w+2}}}\sum_{\mathbf{d}_{i},b,u}(-1)^{\mathbf{d}\cdot{\mathcal{J}}(x_{i,b})\oplus
ub}\ket{u}\ket{\mathbf{d}_{i}}\text{ after QFT}$
$\displaystyle=\frac{1}{\sqrt{2^{w}}}\sum_{\mathbf{d}_{i}\in\\{0,1\\}^{w}}(-1)^{\mathbf{d}_{i}\cdot{\mathcal{J}}(\mathbf{x}_{i,0})}\ket{\mathbf{d}_{i}\cdot({\mathcal{J}}(\mathbf{x}_{i,0})\oplus{\mathcal{J}}(\mathbf{x}_{i,1}))}\ket{\mathbf{d}_{i}}$

A measurement in the computational basis will give us result
($c_{i}=\mathbf{d}_{i}\cdot({\mathcal{J}}(\mathbf{x}_{i,0})\oplus{\mathcal{J}}(\mathbf{x}_{i,1})),\mathbf{d}_{i}$),
for any $i\in[k]$. Correctness of deletion verification thus follows.

######  Remark 9.1.

Note that in our construction, using $\mathsf{td}$ one can also decrypt. It is
easy to define a decryption procedure using $\mathsf{td}$ by the
$\mathsf{INV(\mathsf{td},b,\mathbf{y})}$-procedure in Section 7.2. We omit the
details here.