# Revocable Cryptography from Learning with Errors

Prabhanjan<EMAIL_ADDRESS>
UCSB  Alexander<EMAIL_ADDRESS>
Caltech  Vinod<EMAIL_ADDRESS>
MIT

###### Abstract

Quantum cryptography leverages unique features of quantum information in order
to construct cryptographic primitives that are oftentimes impossible
classically. In this work, we build on the no-cloning principle of quantum
mechanics and design cryptographic schemes with _key-revocation capabilities_.
We consider schemes where secret keys are represented as quantum states with
the guarantee that, once the secret key is successfully revoked from a user,
they no longer have the ability to perform the same functionality as before.

We define and construct several fundamental cryptographic primitives with key-
revocation capabilities, namely pseudorandom functions, secret-key and public-
key encryption, and even fully homomorphic encryption, assuming the quantum
subexponential hardness of the learning with errors problem. Central to all
our constructions is our approach for making the Dual-Regev encryption scheme
(Gentry, Peikert and Vaikuntanathan, STOC 2008) revocable.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Contributions in More Detail
    2. 1.2 Overview
      1. 1.2.1 Applications
    3. 1.3 Related Work
  2. 2 Preliminaries
    1. 2.1 Quantum Computing
    2. 2.2 Lattices and Cryptography
  3. 3 Quantum Discrete Gaussian Sampling for $q$-ary Lattices
    1. 3.1 Gaussian Superpositions
    2. 3.2 Algorithm: GenGauss
    3. 3.3 Algorithm: QSampGauss
  4. 4 Quantum Goldreich-Levin Theorem for Large Fields
    1. 4.1 Post-Quantum Reductions and Quantum Rewinding
    2. 4.2 Goldreich-Levin Theorems for Large Fields
  5. 5 Definition: Key-Revocable Public-Key Encryption
    1. 5.1 Security Definition
    2. 5.2 Key-Revocable Public-Key Fully Homomorphic Encryption
    3. 5.3 From Single-Bit to Multi-Bit Security
  6. 6 Key-Revocable Dual-Regev Encryption
    1. 6.1 Construction
    2. 6.2 Simultaneous Search-to-Decision Reduction with Quantum Auxiliary Input
    3. 6.3 Distinct Pair Extraction
    4. 6.4 Proof of Theorem 6.1
  7. 7 Key-Revocable Fully Homomorphic Encryption
    1. 7.1 Construction
    2. 7.2 Proof of Theorem 7.1
  8. 8 Revocable Pseudorandom Functions
    1. 8.1 Definition
    2. 8.2 Security
    3. 8.3 Construction

##  1 Introduction

Quantum computing presents exciting new opportunities for cryptography, using
remarkable properties of quantum information to construct cryptographic
primitives that are unattainable classically. At the heart of quantum
cryptography lies the _no-cloning principle_ [WZ82, Die82] of quantum
information which stipulates that it is fundamentally impossible to copy an
unknown quantum state. Indeed, Wiesner [Wie83] in his seminal work from the
1970s, used the no-cloning principle to construct a quantum money scheme,
wherein quantum states are used to construct banknotes that can be verified to
be authentic (using a secret key) but cannot be counterfeited. Ever since this
watershed moment, and especially so in the recent years, a wide variety of
primitives referred to as unclonable primitives have been studied and
constructed in the context of encryption [Got02, BL20, BI20a, GZ20], digital
signatures [LLQZ22] and pseudorandom functions [CLLZ21].

##### Our Work: Revocable Cryptography.

Delegation and recovation of privilege are problems of great importance in
cryptography. Indeed, the problem of revocation in the context of digital
signatures and certificates in the classical world is a thorny problem [Stu95,
Riv98]. In this work, we undertake a systematic study of revocable (quantum)
cryptography which allows us to delegate and revoke privileges in the context
of several fundamental cryptographic primitives. This continues a recent line
of work in quantum cryptography dealing with revoking (or certifiably
deleting) states such as quantum ciphertexts or simple quantum programs
[Unr13, BI20a, GZ20, AL21, HMNY21, Por22, BK22].

As a motivating example, consider the setting of an employee at a company who
takes a vacation and wishes to authorize a colleague to perform certain tasks
on her behalf, tasks that involve handling sensitive data. Since the sensitive
data is (required to be) encrypted, the employee must necessarily share her
decryption keys with her colleague. When she returns from vacation, she would
like to have her decryption key back; naturally, one would like to ensure that
her colleague should not be able to decrypt future ciphertexts (which are
encrypted under the same public key) once the key is “returned”. Evidently, if
the decryption key is a classical object, this is impossible to achieve.

In revocable (quantum) cryptography, we associate a cryptographic
functionality, such as decryption using a secret key, with a quantum state in
such a way that a user can compute this functionality if and only if they are
in possession of the quantum state. We then design a revocation algorithm
which enables the user to certifiably return the quantum state to the owner.
Security requires that once the user returns the state (via our revocation
algorithm), they should not have the ability to evaluate the functionality
(e.g. decrypt ciphertexts) anymore. We refer to this new security notion as
revocation security.

Another, possibly non-obvious, application is to detecting malware attacks.
Consider a malicious party who hacks into an electronic device and manages to
steal a user’s decryption keys. If cryptographic keys are represented by
classical bits, it is inherently challenging to detect _phishing attacks_ that
compromise user keys. For all we know, the intruder could have stolen the
user’s decryption keys without leaving a trace. Indeed, a few years ago,
decryption keys which were used to protect cell-phone communications [Int15]
were successfully stolen by spies without being detected. With revocable
cryptography, a malicious user successfully stealing a user key would
invariably revoke the decryption capability from the user. This latter event
can be detected.

##### Our Results in a Nutshell.

We construct revocable cryptographic objects under standard cryptographic
assumptions. Our first main result constructs a key-revocable public-key
encryption scheme, and our second main result constructs a key-revocable
pseudorandom function. We obtain several corollaries and extensions, including
key-revocable secret-key encryption and key-revocable fully homomorphic
encryption. In all these primitives, secret keys are represented as quantum
states that retain the functionality of the original secret keys. We design
revocation procedures and guarantee that once a user successfully passes the
procedure, they cannot compute the functionality any more.

All our constructions are secure under the quantum sub-exponential hardness of
learning with errors. At the heart of all of our contributions, is our result
that the dual-Regev public-key encryption scheme [GPV07] satisfies revocation
security.

##### Related Notions.

There are several recent notions in quantum cryptography that are related to
revocability. Of particular relevance is the stronger notion of copy-
protection introduced by Aaronson [Aar09]. Breaking the revocable security of
a task gives the adversary a way to make two copies of a (possibly different)
state both of which are capable of computing the same functionality. Thus,
uncloneability is a stronger notion. However, the only known constructions of
copy-protection [CLLZ21, LLQZ22] rely on the heavy hammer of post-quantum
secure indistinguishability obfuscation for which there are no known
constructions based on well-studied assumptions. Our constructions, in
contrast, rely on the post-quantum hardness of the standard learning with
errors problem. Another related notion is the significantly weaker definition
of secure software leasing [AL21] which guarantees that once the quantum state
computing a functionality is returned, the honest evaluation algorithm cannot
compute the original functionality. Yet another orthogonal notion is that of
certifiably deleting ciphertexts, originating from the works of Unruh [Unr13]
and Broadbent and Islam [BI20a]. In contrast, our goal is to delegate and
revoke cryptographic capabilities enabled by private keys. For detailed
comparisons, we refer the reader to Section 1.3.

###  1.1 Our Contributions in More Detail

We present our results in more detail below. First, we introduce the notion of
key-revocable public-key encryption. Our main result is that dual-Regev
public-key encryption scheme [GPV07] satisfies revocation security. After
that, we study revocation security in the context of fully homomorphic
encryption and pseudorandom functions.

##### Key-Revocable Public-Key Encryption.

We consider public-key encryption schemes where the decryption key, modeled as
a quantum state, can be delegated to a third party and can later be revoked
[GZ20]. The syntax of a key-revocable public-key scheme (Definition 5.1) is as
follows:

  * •

$\mathsf{KeyGen}(1^{\lambda})$: this is a setup procedure which outputs a
public key $\mathsf{PK}$, a master secret key $\mathsf{MSK}$ and a decryption
key $\rho_{\mathsf{SK}}$. While the master secret key is typically a classical
string, the decryption key is modeled as a quantum state. (The use cases of
$\mathsf{MSK}$ and $\rho_{\mathsf{SK}}$ are different, as will be evident
below.)

  * •

$\mathsf{Enc}(\mathsf{PK},x)$: this is the regular classical encryption
algorithm which outputs a ciphertext $\mathsf{CT}$.

  * •

$\mathsf{Dec}(\rho_{\mathsf{SK}},\mathsf{CT})$: this is a quantum algorithm
which takes as input the quantum decryption key $\rho_{\mathsf{SK}}$ and a
classical ciphertext, and produces a plaintext.

  * •

$\mathsf{Revoke}(\mathsf{PK},\mathsf{MSK},\sigma)$: this is the revocation
procedure that outputs $\mathsf{Valid}$ or $\mathsf{Invalid}$. If $\sigma$
equals the decryption key $\rho_{\mathsf{SK}}$, then $\mathsf{Revoke}$ is
expected to output $\mathsf{Valid}$ with high probability.

After the decryption key is returned, we require that the sender loses its
ability to decrypt ciphertexts. This is formalized as follows (see Definition
5.3): conditioned on revocation being successful, the adversary should not be
able to predict whether it is given an encryption of a message versus uniform
distribution over the ciphertext space with probability better than444The
definition is intentionally formulated as a 1-bit unpredictability game; this
is inspired by the notion of _uncloneable-indistinguishable security_
considered by Broadbent and Lord [BL20]. Unlike the traditional cryptography
literature, in this setting, 1-bit unpredictability is not equivalent to
computational indistinguishability; the reason being that we also incorporate
whether revocation is successful in the security experiment. We leave the
investigation of indistinguishability-based definitions for future works.
$\frac{1}{2}+\mathsf{negl}(\lambda)$. We prove the following in Theorem 6.1.

######  Theorem 1.1 (Informal).

Assuming that the $\mathsf{LWE}$ and $\mathsf{SIS}$ problems with
subexponential modulus are hard against quantum adversaries running in
subexponential time (see Section 2.2), there exists a key-revocable public-key
encryption scheme.

Due to the quantum reduction from $\mathsf{SIS}$ to $\mathsf{LWE}$ [SSTX09],
the two assumptions are, in some sense, equivalent. Therefore, we can in
principle rely on the subexponential hardness of $\mathsf{LWE}$ alone.

Our work improves upon prior work [GZ20, CLLZ21] which requires the existence
of post-quantum indistinguishability obfuscation and post-quantum one-way
functions [BGI+12, CV22].

##### Key-Revocable Fully Homomorphic Encryption.

We go beyond the traditional public-key setting and design the first fully
homomorphic encryption (FHE) scheme [Gen09, BV14a] with key-revocation
capabilities. Our construction is based on a variant of the (leveled) FHE
scheme of Gentry, Sahai and Waters [GSW13], which we extend to a key-revocable
encryption scheme using Gaussian superpositions. The syntax of a key-revocable
FHE scheme is the same as in the key-revocable public-key setting from before
(Definition 5.1), except for the additional algorithm Eval which is the same
as in a regular FHE scheme. We prove the following in Theorem 7.1.

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

Assuming that the $\mathsf{LWE}$ and $\mathsf{SIS}$ problems with
subexponential modulus are hard against quantum adversaries running in
subexponential time (see Section 2.2), there exists a key-revocable (leveled)
fully homomorphic encryption scheme.

We prove the theorem by invoking the security of our key-revocable dual-Regev
public-key encryption scheme in Section 6.

##### (Key-)Revocable Pseudorandom Functions.

We consider other cryptographic primitives with key-revocation capabilities
that go beyond decryption functionalities; specifically, we introduce the
notion of _key-revocable_ pseudorandom functions (PRFs) with the following
syntax:

  * •

$\mathsf{Gen}(1^{\lambda})$: outputs a PRF key $k$, a quantum key $\rho_{k}$
and a master secret key $\mathsf{MSK}$.

  * •

${\sf PRF}(k;x)$: on key $k$ and input $x$, output a value $y$. This is a
deterministic algorithm.

  * •

${\sf Eval}(\rho_{k},x)$: on input a state $\rho_{k}$ and an input $x$, output
a value $y$.

  * •

$\mathsf{Revoke}(\mathsf{MSK},\sigma)$: on input verification $\mathsf{MSK}$
and state $\sigma$, outputs $\mathsf{Valid}$ or $\mathsf{Invalid}$.

After the quantum key $\rho_{k}$ is successfully returned, we require that the
sender loses its ability to evaluate the ${\sf PRF}$. This is formalized as
follows (see Definition 8.3): any efficient adversary can simultaneously pass
the revocation phase and succeed in predicting the output of a pseudorandom
function on a challenge input $x^{*}$ versus uniform with probability at most
$\frac{1}{2}+\mathsf{negl}(\lambda)$. In fact, we consider a more general
definition where the adversary receives many challenge inputs instead of just
one challenge input.

We give the first construction of key-revocable pseudorandom functions (PRFs)
from standard assumptions. Previous schemes implicit in [CLLZ21] either
require indistinguishability obfuscation, or considered weaker notions of
revocable PRFs in the form of _secure software leasing_ [AL21, KNY21], which
merely prevents the possiblity of _honestly_ evaluating the PRF once the key
is revoked.

Since in the context of pseudorandom functions, it is clear what is being
revoked, we instead simply call the notion revocable pseudorandom functions.

######  Theorem 1.3 (Informal).

Assuming that the $\mathsf{LWE}$ and $\mathsf{SIS}$ problems with
subexponential modulus are hard against quantum adversaries running in
subexponential time (see Section 2.2), there exist key-revocable pseudorandom
functions.

Revocable pseudorandom functions immediately give us key-revocable (many time
secure) secret-key encrypton schemes.

##### Discussion: Unclonable Cryptography from LWE.

Over the years, the existence of many fundamental cryptographic primitives
such as pseudorandom functions [BPR12], fully homomorphic encryption [BV14],
attribute-based encryption [BGG+14] and succinct argument systems [CJJ22] have
been based on the existence of learning with errors. In fact, as far as we
know, there are only a few foundational primitives remaining
(indistinguishability obfuscation is one such example) whose existence is not
(yet) known to be based on learning with errors.

This situation is quite different in the world of unclonable cryptography.
Most of the prominent results have information-theoretic guarantees but
restricted functionalities [BI20a, BL20] or are based on the existence of
post-quantum indistinguishability obfuscation [Zha21, CLLZ21]. While there are
works [KNY21a] that do propose lattice-based constructions of unclonable
primitives, there are still many primitives, such as quantum money and quantum
copy-protection, whose feasibility we would like to establish based on the
existence of learning with errors. We hope that our work presents new toolkits
towards building more unclonable primitives from $\mathsf{LWE}$.

###  1.2 Overview

We now give a technical overview of our constructions and their high level
proof ideas. We begin with the key-revocable public-key encryption
construction. A natural idea would be to start with Regev’s public-key
encryption scheme [Reg05] and then upgrade the scheme to be key-revocable.
However, natural attempts to associate an unclonable quantum state with the
decryption key fail and thus, we instead look at the Dual-Regev public-key
encryption scheme and make it key-revocable. We describe the scheme below.

##### Key-Revocable Dual-Regev Public-Key Encryption.

Our first construction is based on the _Dual-Regev_ public-key encryption
scheme [GPV07] and makes use of Gaussian superpositions which serve as a
quantum decryption key. We give an overview of 2 below.

  * •

$\mathsf{KeyGen}(1^{n})$: sample a matrix
$\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$ along with a _short trapdoor basis_
$\mathsf{td}_{\mathbf{A}}$. To generate the decryption key, we employ the
following procedure555In Section 3.2, this is formalized as the procedure
${\sf GenGauss}$ (see Algorithm 1).: Using the matrix $\mathbf{A}$ as input,
first create a Gaussian superposition of short vectors in
$\mathbb{Z}^{m}\cap(-\frac{q}{2},\frac{q}{2}]^{m}$, denoted by666Note that the
state is not normalized for convenience.

$\ket{\psi}=\sum_{\mathbf{x}\in\mathbb{Z}_{q}^{m}}\rho_{\sigma}(\mathbf{x})\ket{\mathbf{x}}\otimes\ket{\mathbf{A}\cdot\mathbf{x}\
(\mathrm{mod}\ q)}$

where $\rho_{\sigma}(\mathbf{x})=\exp(-\pi\|\mathbf{x}\|^{2}/\sigma^{2})$ is
the Gaussian measure, for some $\sigma>0$. Next, measure the second register
which partially collapses the superposition and results in the _coset state_

$\ket{\psi_{\mathbf{y}}}=\sum_{\begin{subarray}{c}\mathbf{x}\in\mathbb{Z}_{q}^{m}:\\\
\mathbf{A}\mathbf{x}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\rho_{\sigma}(\mathbf{x})\ket{\mathbf{x}}$

for some outcome $\mathbf{y}\in\mathbb{Z}_{q}^{n}$. Finally, we let
$\ket{\psi_{\bf y}}$ be the decryption key $\rho_{\mathsf{SK}}$,
$({\mathbf{A}},{\mathbf{y}})$ be the public key $\mathsf{PK}$, and we let the
trapdoor $\mathsf{td}_{\mathbf{A}}$ serve as the master secret key
$\mathsf{MSK}$.

  * •

$\mathsf{Enc}(\mathsf{PK},\mu)$: to encrypt a bit $\mu\in{\\{0,1\\}}$, sample
a random string ${\mathbf{s}}\xleftarrow{\$}\mathbb{Z}_{q}^{n}$ together with
discrete Gaussian errors ${\mathbf{e}}\in\mathbb{Z}^{m}$ and
$e^{\prime}\in\mathbb{Z}$, and output the (classical) ciphertext $\mathsf{CT}$
given by

$\mathsf{CT}=(\mathbf{s}^{\intercal}\mathbf{A}+\mathbf{e}^{\intercal},\mathbf{s}^{\intercal}\mathbf{y}+e^{\prime}+\mu\cdot\lfloor\frac{q}{2}\rfloor)\,\,\,\in\mathbb{Z}_{q}^{m}\times\mathbb{Z}_{q}.$

  * •

$\mathsf{Dec}(\rho_{\mathsf{SK}},\mathsf{CT})$: to decrypt a ciphertext
$\mathsf{CT}$ using the decryption key
$\rho_{\mathsf{SK}}=\ket{\psi_{\mathbf{y}}}$, first apply the unitary
$U:\ket{\mathbf{x}}\ket{0}\rightarrow\ket{\mathbf{x}}\ket{\mathsf{CT}\cdot(-\mathbf{x},1)^{\intercal}}$
on input $\ket{\psi_{\mathbf{y}}}\ket{0}$, and then measure the second
register in the computational basis. Because $\ket{\psi_{\mathbf{y}}}$ is a
superposition of short vectors ${\mathbf{x}}$ subject to
${\mathbf{A}}\cdot{\mathbf{x}}={\mathbf{y}}\ (\mathrm{mod}\ q)$, we obtain an
approximation of $\mu\cdot\lfloor\frac{q}{2}\rfloor$ from which we can recover
$\mu$.777For approriate choices of parameters, decryption via rounding
succeeds at outputting $\mu$ with overwhelming probability and hence we can
invoke the _Almost as Good as New Lemma_ [Aar16] to recover the original state
$\ket{\psi_{\mathbf{y}}}$.

  * •

$\mathsf{Revoke}(\mathsf{PK},\mathsf{MSK},\rho)$: to verify the returned state
$\rho$ given as input the public key $(\mathbf{A},\mathbf{y})$ and master
secret key $\mathsf{td}_{{\mathbf{A}}}$, apply the projective measurement
$\\{|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|,I-|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\\}$
onto $\rho$. Output $\mathsf{Valid}$, if the measurement succeeds, and output
$\mathsf{Invalid}$, otherwise.

##### Implementing revocation, efficiently.

Note that performing a projective measurement onto a fixed Gaussian state
$\ket{\psi_{\mathbf{y}}}$ is, in general, computationally infeasable. In fact,
if it were to be possible to efficiently perform this projection using just
$(\mathbf{A},\mathbf{y})$ then such a procedure can be used to solve the short
integer solution ($\mathsf{SIS}$) problem. Fortunately, we additionally have
the trapdoor for $\mathbf{A}$ at our disposal to perform the projection.

One of our contributions is to design a _quantum discrete Gaussian sampler for
$q$-ary lattices_888In Section 3.3, this is formalized as the procedure
QSampGauss (see Algorithm 2). which, given as input
$({\mathbf{A}},\mathbf{y},\mathsf{td}_{{\mathbf{A}}},\sigma)$, implements a
unitary that efficiently prepares the Gaussian superposition
$\ket{\psi_{\mathbf{y}}}$ from scratch with access to the trapdoor
$\mathsf{td}_{{\mathbf{A}}}$. At a high level, our Gaussian sampler can be
thought of as an explicit quantum reduction from the _inhomogenous_
$\mathsf{SIS}$ problem [Ajt96] to the search variant of the $\mathsf{LWE}$
problem (see Section 3.3).

##### Proving security: Initial challenges.

Let us first discuss some high level ideas behind proving the security of the
above constrution. We would like to prove that if the above scheme is insecure
then we can use this adverary to contradict some well-known computational
assumption. That is, there exists an adversary who can simultaneously pass the
revocation successfully and also predict whether it receives a ciphertext or a
uniform element from the ciphertext space. Towards designing such a reduction,
an initial attempt would be to use the predictor, predicting an encryption of
a valid message versus uniform, to break some computational assumption.
Indeed, since the ciphertexts look like samples from the learning with error
distribution, we might be tempted to directly invoke $\mathsf{LWE}$ to prove
this. Unfortunately, this argument is flawed! For all we know, the adversary
could be doing the following: given the state $\ket{\psi_{\mathbf{y}}}$, it
clones it, returns the cloned version and, then uses the original copy to
distinguish encryption of a valid message versus uniform. In this case, the
predictor is running the decryption algorithm honestly and thus it is not
feasible to use such an adversary to break learning with errors.

This suggests that perhaps we can argue that a computational adversary cannot
clone the state $\ket{\psi_{\mathbf{y}}}$. Indeed, if it clones then we should
be able to measure the two copies separately and use the two measurement
outcomes to come up with a short solution in the kernel of $\mathbf{A}$.
However, it is not clear if the adversary needs to clone the state in order
for it to succeed. Perhaps it did not clone the state and yet was able to
distinguish a valid ciphertext versus uniform ciphertext. For all we know, the
adversary could have been successful in breaking $\mathsf{LWE}$.

Since it is not feasible to detect which case we are in (cloning adversary or
$\mathsf{LWE}$ distinguisher), it is important that the reduction needs to use
the fact that the adversary simultaneously returns the original state and at
the same time, violates the 1-bit unpredictability experiment to break some
computational assumption.

##### Insight: Reduction to SIS.

Our goal is to use the state returned by the adversary and the one bit
prediction to break some computational problem. It should seem suspicious
whether such a reduction is even possible: after all the adversary is
returning the state we gave them! how could this possibly help? Our main
insight is the observation that while the adversary does return the state we
give them, the only way it can succeed in the prediction is if it retains
useful information about the state. If we could somehow extract this
information from the adversary then using the extracted information alongside
the returned state, we can hopefully break some computational assumption. For
instance, suppose we can extract a short vector $\mathbf{x}$ such that
$\mathbf{A}\cdot\mathbf{x}=\mathbf{y}\ (\mathrm{mod}\ q)$ then we can measure
the returned state to hopefully get another short vector $\mathbf{x}^{\prime}$
such that $\mathbf{A}\cdot\mathbf{x}^{\prime}=\mathbf{y}\ (\mathrm{mod}\ q)$
and from this, we can recover a short solution in the kernel of $\mathbf{A}$.

Even if for a moment we disregard the issue of being able to extract
$\mathbf{x}$ from the adversary, there are still some important missing pieces
in the above template:

  * •

Firstly, measuring the returned state should give a vector different from
$\mathbf{x}$ with non-negligible probability. In order to prove this, we need
to argue that the squared ampltidue of every term is bounded away from 1. We
prove this statement (Lemma 2.7) holds as long as $\mathbf{A}$ is full rank.

  * •

Secondly, the reduction to $\mathsf{SIS}$ would only get as input $\mathbf{A}$
and not a trapdoor for $\mathbf{A}$. This means that it will no longer be
possible for the reduction to check if the state returned by the adversary is
valid. But we observe that instead of first verifying whether the returned
state is valid and then measuring in the computational basis, we could instead
skip verification and just measure the state in the computational basis; this
is implicit in the analysis in the proof of Lemma 6.9.

  * •

Finally, the adversary could have entangled the returned state with its
residual state in such a way that measuring the returned state gives the same
vector $\mathbf{x}$ as the one extracted from the adversary. In the same
analysis in the proof of Lemma 6.9, we prove that even if the adversary
entangles its state with the returned state, with non-negligible probability
we get two distinct short vectors mapping $\mathbf{A}$ to $\mathbf{y}$.

All that is left is to argue that it is possible to extract $\mathbf{x}$ from
the adversary while simultaneously verifying whether the returned state is
correct or not. To show that we can indeed extract another short pre-image
from the adversary’s quantum side information, we prove what we call a
_simultaneous search-to-decision reduction with quantum auxiliary input_ with
respect to the Dual-Regev scheme (see Theorem 6.3). This constitutes the main
technical result of this work.

##### Main contribution: Simultaneous search-to-decision reduction.

Informally, our theorem says the following: any successful Dual-Regev
distinguisher with access to quantum side information Aux (which depends on
the decryption key) can be converted into a successful extractor that finds a
key on input Aux – even conditioned on $\mathsf{Revoke}$ succeeding on the
seperate register $R$. We now present some intuition behind our proof.

Suppose there exists a successful Dual-Regev predictor $\mathcal{D}$ (as part
of the adversary $\mathcal{A}$) that, given side information Aux, can predict
whether it is given
$(\mathbf{s}^{\intercal}\mathbf{A}+\mathbf{e}^{\intercal},\mathbf{s}^{\intercal}\mathbf{y}+e^{\prime})$
versus uniform $(\mathbf{u},r)\in\mathbb{Z}_{q}^{m}\times\mathbb{Z}_{q}$ with
advantage $\epsilon$.

Resorting to Weak Revocation: We first make an observation about the
revocation security experiment.

Suppose after checking if the revoked state is correct, we then apply another
procedure called WeakRevoke and only proceed if even WeakRevoke succeeds. We
define WeakRevoke as follows: measure the state in the computational basis and
only accept if the result is a short vector $\mathbf{x}\in\mathbb{Z}_{q}^{m}$
that maps $\mathbf{A}$ to $\mathbf{y}$. We claim that this modified security
experiment is identical to the original revocation security experiment. The
reason being that once the revocation succeeds, the resulting state is a
Gaussian superposition of short vectors mapping $\mathbf{A}$ to $\mathbf{y}$.
Thus, measuring this state will result in a short vector mapping $\mathbf{A}$
to $\mathbf{y}$. Putting this succinctly, if the revocation security
experiment succeeds then WeakRevoke will always succeed. From here on, we will
work with the modified experiment.

First notice that dropping the revocation procedure can only increase the
success probability of the predictor. We will show that even if in the case
when the revocation procedure dropped (but WeakRevoke is still applied), the
probability that the predictor succeeds is negligibly close to $1/2$. This
will in turn prove that the predictor in the original revocation experiment
can only succeed with probability negligibly close to $1/2$. The reason we
consider an alternate world where revocation is not applied is because we need
the trapdoor in order to perform revocation and this will interfere in
invoking computational assumptions to do the hybrids.

Inspired by techniques from the _leakage resilience_ literature [DGT+10], we
now make the following observation. Letting
$\mathbf{y}=\mathbf{A}\cdot\mathbf{x}_{0}\ (\mathrm{mod}\ q)$, for some
Gaussian vector $\mathbf{x}_{0}$ with distribution proportional to
$\rho_{\sigma}(\mathbf{x}_{0})$, the former sample can be written as
$(\mathbf{s}^{\intercal}\mathbf{A}+\mathbf{e}^{\intercal},(\mathbf{s}^{\intercal}\mathbf{A}+\mathbf{e}^{\intercal})\cdot\mathbf{x}_{0}+e^{\prime})$.
Here, we assume a _noise flooding_ regime in which the noise magnitude of
$e^{\prime}$ is significantly larger than that of
$\mathbf{e}^{\intercal}\cdot\mathbf{x}_{0}$. Because the distributions are
statistically close, the distinguisher $\mathcal{D}$ must succeed at
distinguishing the sample from uniform with probability negligibly close to
$\epsilon$. Finally, we hope to invoke the $\mathsf{LWE}$ assumption and claim
that the same distinguishing advantage persists, even if we replace
$(\mathbf{s}^{\intercal}\mathbf{A}+\mathbf{e}^{\intercal})$ with a random
string $\mathbf{u}\in\mathbb{Z}_{q}^{m}$.

However, we run into an issue! the reduction to $\mathsf{LWE}$ needs to be
able to efficiently generate the auxiliary input Aux handed to the predictor,
while simultaneously producing a Gaussian vector $\mathbf{x}_{0}$ such that
$\mathbf{A}\cdot\mathbf{x}_{0}=\mathbf{y}\ (\mathrm{mod}\ q)$. Unfortunately,
this is only possible if the reduction can itself violate the $\mathsf{SIS}$
assumption, since the ability to produce both a superposition
$\ket{\psi_{\mathbf{y}}}$ of pre-images and a single pre-image
$\mathbf{x}_{0}$ would allow one to obtain a collision for $\mathbf{y}$.

Reduction to Goldreich-Levin: Assuming the existence of a quantum Goldreich-
Levin theorem for the field $\mathbb{Z}_{q}$, one could then convert
$\mathcal{D}$ into an extractor that extracts ${\mathbf{x}_{0}}$ with high
probability. Prior to our work, a quantum Goldreich-Levin theorem was only
known for $\mathbb{Z}_{2}$ [AC02, CLLZ21]. In particular, it is unclear how to
extend prior work towards higher order fields $\mathbb{Z}_{q}$ because the
interference pattern in the analysis of the quantum extractor does not seem to
generalize beyond the case when $q=2$. Instead, we do the following. We start
with the _classical_ Goldreich-Levin theorem for finite fields due to Dodis et
al. [DGT+10] and then upgrade it to quantum Goldreich-Levin for finite fields
using a recent work by Bitansky, Brakerski and Kalai. [BBK22]. This allows us
to obtain the first quantum Goldreich-Levin theorem for large fields, which we
prove in Section 4. Specifically, we can show that a distinguisher
$\mathcal{D}$ that, given auxiliary input Aux, can distinguish between
$(\mathbf{u},\mathbf{u}^{\intercal}\mathbf{x}_{0})$ and $(\mathbf{u},r)$ with
advantage $\epsilon$ can be converted into a quantum extractor that can
extract ${\mathbf{x}_{0}}$ given Aux in time $\mathrm{poly}(1/\varepsilon,q)$
with probability at least $\mathrm{poly}(\varepsilon,1/q)$.

Bringing back (strong) Revocation: To complete the security proof behind our
key-revocable Dual-Regev scheme, we need to show something _stronger_ ;
namely, we need to argue that the Goldreich-Levin extractor succeeds on input
Aux – even conditioned on the fact that $\mathsf{Revoke}$ outputs
$\mathsf{Valid}$ when applied on a separate register $R$ (which may be
entangled with Aux). The fact that revocation is taken into account introduces
further technical challenges. First, it is unclear how to use the proof idea
from before since we cannot rely on a _collapsed_ version of
$\ket{\psi_{\mathbf{y}}}$ in order to generate Aux. In fact, any attempt of
measuring $\ket{\psi_{\mathbf{y}}}$ would immediately force $\mathsf{Revoke}$
to reject. Second, it is unclear how to invoke the $\mathsf{LWE}$ assumption
in the presence of a trapdoor $\mathsf{td}_{\mathbf{A}}$ which is used by
$\mathsf{Revoke}$ for the purpose of revocation.

To overcome these issues, we exploit the fact that our notion of revocation
security is defined with respect to _$1$ -bit unpredictability_; in other
words, we assume that $\mathcal{D}$ succeeds at predicting $b$ when
participating in $\mathsf{Expt}^{\mathcal{A}}(1^{n},b)$ with probability
$\frac{1}{2}+\varepsilon$ given access to side information Aux. Consider the
following hypothetical hybrid distribution in which $\mathcal{D}$ receives as
input $(\mathbf{u},\mathbf{u}^{\intercal}\mathbf{x}_{0})$ for a random
$\mathbf{u}$ and Gaussian error $\mathbf{x}_{0}$, and where Aux is computed on
input $\ket{\psi_{\mathbf{y}}}$ with respect to
$\mathbf{y}=\mathbf{A}\cdot\mathbf{x}_{0}\ (\mathrm{mod}\ q)$. Note that in
this scenario $\mathbf{x}_{0}$ is sampled first, whereas
$\ket{\psi_{\mathbf{y}}}$ is later generated from scratch using our procedure
QSampGauss999This requires the trapdoor $\mathsf{td}_{\mathbf{A}}$ for the
matrix $\mathbf{A}$ (see Algorithm 2). A simple argument shows that, if
$\mathcal{D}$ succeeds at predicting $b$, where $b=0$ corresponds to the Dual-
Regev distribution and $b=1$ corresponds to the uniform distribution with
probability $\frac{1}{2}+\epsilon$, for some $\epsilon=1/\mathrm{poly}(n)$,
then $\mathcal{D}$ must either be able to predict Dual-Regev distribution
versus the hybrid distribution with advantage $1/\mathrm{poly}(n)$, or uniform
distribution versus hybrid distribution with advantage $1/\mathrm{poly}(n)$.
In the former case, we can easily show that the prediction advantage is
negligible by first ignoring the condition that $\mathsf{Revoke}$ succeeds
(and thus, avoiding using the trapdoor $\mathsf{td}_{\mathbf{A}}$) and then
invoking $\mathsf{LWE}$ using the previous proof template101010Because we are
dealing with $1$-bit unpredictability, the distinguishing advantage of
$\mathcal{D}$ can only increase if we remove the conditioning on
$\mathsf{Revoke}$ succeeding. This fact is not true if we had instead dealt
with computational indistinguishability.. Finally, in the latter case when
$\mathcal{D}$ distinguishes between the uniform distribution and the hybrid
distribution with advantage $1/\mathrm{poly}(n)$ this precisely corresponds to
the setting of quantum Goldreich-Levin, which means that we can successfully
extract.

####  1.2.1 Applications

We leverage our result of key-revocable Dual-Regev encryption to get key-
revocable fully homomorphic encryption and revocable pseudorandom functions.

##### Key-Revocable Dual-Regev Fully Homomorphic Encryption.

Our first application of our result on key-revocable public-key encryption
concerns fully homomorphic encryption schemes. We extend our key-revocable
Dual-Regev scheme towards a (leveled) $\mathsf{FHE}$ scheme in 3 by using the
DualGSW variant of the (leveled) $\mathsf{FHE}$ scheme by Gentry, Sahai and
Waters [GSW13, Mah18].

To encrypt a bit $\mu\in{\\{0,1\\}}$ with respect to the public-key
$(\mathbf{A},\mathbf{y})$, sample a matrix
$\mathbf{S}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n\times
N}$ together with a Gaussian error matrix $\mathbf{E}\in\mathbb{Z}^{m\times
N}$ and row vector $\mathbf{e}\in\mathbb{Z}^{N}$, and output the ciphertext

$\mathsf{CT}=\left[\begin{subarray}{c}\mathbf{A}^{\intercal}\mathbf{S}+\mathbf{E}\vspace{1mm}\\\
\hline\cr\vspace{1mm}\\\
\mathbf{y}^{\intercal}\mathbf{S}+\mathbf{e}\end{subarray}\right]+\mu\cdot\mathbf{G}\
(\mathrm{mod}\ q)\,\in\,\mathbb{Z}_{q}^{(m+1)\times N}.$

Here, $\mathbf{G}$ is the _gadget matrix_ which converts a binary vector in
into its field representation over $\mathbb{Z}_{q}$. As before, the decryption
key consists of a Gaussian superposition $\ket{\psi_{\mathbf{y}}}$ of pre-
images of $\mathbf{y}$.

Note that the DualGSW ciphertext can be thought of as a column-wise
concatenation of $N$-many independent Dual-Regev ciphertexts. In Theorem 7.1,
we prove the security of our construction by invoking the security of our key-
revocable Dual-Regev scheme.

##### Revocable Pseudorandom Functions.

Our next focus is on leveraging the techniques behind key-revocable public-key
encryption to obtain revocable pseudorandom functions. To recall, revocation
security of pseudorandom functions stipulates the following: any efficient
adversary after revoking the quantum state that enables it to evaluate
pseudorandom functions cannot predict whether it receives pseudorandom outputs
on many challenge inputs versus strings picked uniformly at random with
probability better than $\frac{1}{2}+\mathsf{negl}(\lambda)$. An astute reader
might notice that revocation security does not even imply the traditional
pseudorandomness guarantee! Hence, we need to additionally impose the
requirement that a revocable pseudorandom function should also satisfy the
traditional pseudorandomness guarantee.

Towards realizing a construction satisfying our definitions, we consider the
following template:

  1. 1.

First show that there exists a $\mu$-revocable pseudorandom function, for
$\mu=1$. Here, $\mu$-revocation security refers to the adversary receiving
$\mu$ challenge inputs after revocation.

  2. 2.

Next, we show that any 1-revocable pseudorandom function also satisfies the
stronger revocation security where there is no a priori bound on the number of
challenge inputs received by the adversary.

  3. 3.

Finally, we show that we can generically upgrade any revocable PRF to also
satisfy the traditional pseudorandomness property.

The second bullet is proven using a hybrid argument. The third bullet is
realized by combining a revocable $\mathsf{PRF}$ with a post-quantum secure
$\mathsf{PRF}$ (not necessarily satisfying revocation security).

Hence, we focus the rest of our attention on proving the first bullet.

1-revocation security. We start with the following warmup construction. The
secret key $k$ comprises of matrices $\mathbf{A},\\{{\bf S}_{i,0},{\bf
S}_{i,1}\\}_{i\in[\ell],b\in\\{0,1\\}}$, where
$\mathbf{A}\xleftarrow{\$}\mathbb{Z}_{q}^{n\times m}$,${\bf
S}_{i,b}\in\mathbb{Z}_{q}^{n\times n}$ such that all ${\bf S}_{i,b}$ are
sampled from some error distribution and the output of the pseudorandom
function on $x$ is denoted to be $\lfloor\sum_{i\in[\ell]}{\bf
S}_{i,x_{i}}\mathbf{A}\rceil_{p}$, where $q\gg p$.

In addition to the regular key $k$, we also need to generate a quantum key
$\rho_{k}$ such that given $\rho_{k}$ and any input $x$, we can efficiently
compute ${\sf PRF}(k,x)$. Moreover, $\rho_{k}$ can be revoked such that any
efficient adversary after revocation loses the ability to evaluate the
pseudorandom function. To enable the generation of $\rho_{k}$, we first modify
the above construction. We generate $\mathbf{y}\in\mathbb{Z}_{q}^{n}$ and
include this as part of the key. The modified pseudorandom function, on input
$x$, outputs $\lfloor\sum_{i\in[\ell]}{\bf S}_{i,x_{i}}\mathbf{y}\rceil_{p}$.
We denote $\sum_{i\in[\ell]}{\bf S}_{i,x_{i}}={\bf S}_{x}$ and with this new
notation, the output of the pseudorandom function is denoted by
$\lfloor\sum_{i\in[\ell]}{\bf S}_{x}\mathbf{y}\rceil_{p}$.

With this modified construction, we describe the elements as part of the
quantum key $\rho_{k}$:

  * •

For every $i\in[\ell]$, include ${\bf S}_{i,b}\mathbf{A}+{\bf E}_{i,b}$ in
$\rho_{k}$, where $i\in[\ell]$ and $b\in\\{0,1\\}$. We sample ${\bf S}_{i,b}$
and ${\bf E}_{i,b}$ from a discrete Gaussian distribution with appropriate
standard deviation $\sigma>0$.

  * •

Include $\ket{\psi_{\mathbf{y}}}$ which, as defined in the key-revocable Dual-
Regev construction, is a Gaussian superposition of short solutions mapping
$\mathbf{A}$ to $\mathbf{y}$.

To evaluate on an input $x$ using $\rho_{k}$, compute $\sum_{i}{\bf
S}_{i,x_{i}}\mathbf{A}+{\bf E}_{i,x_{i}}$ and then using the state
$\ket{\psi_{\mathbf{y}}}$, map this to $\sum_{i}{\bf
S}_{i,x_{i}}\mathbf{y}+{\bf E}_{i,x_{i}}$. Finally, perform the rounding
operation to get the desired result.

Our goal is to show that after the adversary revokes
$\ket{\psi_{\mathbf{y}}}$, on input a challenge input $x^{*}$ picked uniformly
at random, it cannot predict whether it has received
$\lfloor\sum_{i\in[N]}{\bf S}_{i,x_{i}^{*}}\mathbf{y}\rceil_{p}$ or a
uniformly random vector in $\mathbb{Z}_{p}^{n}$.

Challenges in proving security: We would like to argue that when the state
$\ket{\psi_{\mathbf{y}}}$ is revoked, the adversary loses the ability to
evaluate the pseudorandom function. Unfortunately, this is not completely
true. For all we know, the adversary could have computed the pseudorandom
function on many inputs of its choice before the revocation phase and it could
leverage this to break the security after revocation. For instance, suppose
say the input is of length $O(\log\lambda)$ then in this case, the adversary
could evaluate the pseudorandom function on all possible inputs before
revocation. After revocation, on any challenge input $x^{*}$, the adversary
can then successfully predict whether it receives a pseudorandom output or a
uniformly chosen random output. Indeed, a pseudorandom function with
$O(\log\lambda)$-length input is learnable and hence, there should be no hope
of proving it to be key-revocable. This suggests that, at the very least, we
need to explicitly incorporate the fact that $x^{*}$ is of length
$\omega(\log\lambda)$, and more importantly, should have enough entropy, in
order to prove security.

Our insight: Our insight is to reduce the security of revocable pseudorandom
function to the security of key-revocable Dual-Regev public-key encryption. At
a high level, our goal is to set up the parameters in such a way that the
following holds:

  * •

$(\mathbf{A},\mathbf{y})$, defined above, is set to be the public key
corresponding to the Dual-Regev public-key encryption scheme,

  * •

$\ket{\psi_{\mathbf{y}}}$, which is part of the pseudorandom function key, is
set to be the decryption key of the Dual Regev scheme,

  * •

Suppose that the challenge ciphertext, denoted by $\mathsf{CT}^{*}$, comprises
of two parts: $\mathsf{CT}^{*}_{1}\in\mathbb{Z}_{q}^{n\times m}$ and
$\mathsf{CT}^{*}_{2}\in\mathbb{Z}_{q}^{n}$. Note that if
$\mathsf{CT}_{1}^{*}\approx{\bf s}^{\intercal}\mathbf{A}$ and
$\mathsf{CT}_{2}^{*}\approx{\bf s}^{\intercal}\mathbf{y}$, for some
$\mathsf{LWE}$ secret vector ${\bf s}$, then $\mathsf{CT}_{1}^{*}$ can be
mapped onto $\mathsf{CT}^{*}_{2}$ using the state $\ket{\psi_{\mathbf{y}}}$.
We use $\mathsf{CT}^{*}_{1}$ to set the challenge input $x^{*}$ in such a way
that $\mathsf{CT}^{*}_{2}$ is the output of the pseudorandom function on
$x^{*}$. This implicitly resolves the entropy issue we discussed above; by the
semantic security of Dual-Regev, there should be enough entropy in
$\mathsf{CT}_{1}^{*}$ which translates to the entropy of $x^{*}$.

It turns our goal is quite ambitious: in particular, it is unclear how to set
up the parameters in such that the output of the pseudorandom function on $x$
is exactly $\mathsf{CT}^{*}_{2}$. Fortunately, this will not be a deterrant,
we can set up the parameters such that the output is
$\approx\mathsf{CT}_{2}^{*}+\mathbf{u}$, where $\mathbf{u}$ is a vector that
is known to reduction.

Once we set up the parameters, we can then reduce the security of revocable
pseudorandom functions to revocable Dual Regev.

Implementation details: So far we established the proof template should work
but the implementation details of the proof need to be fleshed out. Firstly,
we set up the parameters in such a way that $\ell=nm\lceil\log q\rceil$. This
means that there is a bijective function mapping
$[n]\times[m]\times[\lceil\log q\rceil]$ to $[\ell]$. This means that the
quantum key $\rho_{k}$ can be alternately viewed as follows:

  * •

For every $i\in[n],j\in[m],\tau\in[\lceil\log q\rceil],b\in\\{0,1\\}$, include
${\bf S}_{b}^{(i,j,\tau)}\mathbf{A}+{\bf E}_{b}^{(i,j,\tau)}$ in $\rho_{k}$.
We sample ${\bf S}_{b}^{(i,j,\tau)}$ and ${\bf E}_{b}^{(i,j,\tau)}$ from a
discrete Gaussian with appropriate standard deviation $\sigma>0$.

The output of the pseudorandom function on input $x$ can now be interpreted as

$\left\lceil\sum_{\begin{subarray}{c}i\in[n],j\in[m]\\\ \tau\in[\lceil\log
q\rceil]\end{subarray}}{\bf S}^{(i,j,\tau)}_{x_{i}}\mathbf{y}\right\rceil_{p}$

Next, we modify $\rho_{k}$ as follows: instead of generating, ${\bf
S}_{b}^{(i,j,\tau)}\mathbf{A}+{\bf E}_{b}^{(i,j,\tau)}$, we instead generate
${\bf S}_{b}^{(i,j,\tau)}\mathbf{A}+{\bf E}_{b}^{(i,j,\tau)}+{\sf
M}^{(i,j,k)}_{b}$, for any set of matrices $\\{{\sf M}^{(i,j,\tau)}_{b}\\}$.
The change should be undetectable to a computationally bounded adversary,
thanks to the quantum hardness of learning with errors. In the security proof,
we set up the challenge input $x^{*}$ in such a way that summing up the
matrices ${\sf M}_{x^{*}_{i}}^{(i,j,\tau)}$ corresponds to
$\mathsf{CT}_{1}^{*}$, where $\mathsf{CT}_{1}^{*}$ is part of the key-
revocable Dual-Regev challenge ciphertext as discussed above. With this
modification, when $\rho_{k}$ is evaluated on $x^{*}$, we get an output that
is close to $\mathsf{CT}_{2}^{*}+{\bf u}$, where ${\bf
u}\approx\sum_{i\in[n],j\in[m],\tau\in[\lceil\log(q)\rceil]}\mathbf{y}$ is
known to the reduction (discussed above) that violates the security of key-
revocable Dual-Regev scheme.

###  1.3 Related Work

##### Copy-Protection.

Of particular relevance to our work is the foundational notion of copy-
protection introduced by Aaronson [Aar09]. Informally speaking, a copy-
protection scheme is a compiler that transforms programs into quantum states
in such a way that using the resulting states, one can run the original
program. Yet, the security guarantee stipulates that any adversary given one
copy of the state cannot produce a bipartite state wherein both parts compute
the original program.

While copy-protection is known to be impossible for arbitrary unlearnable
functions [AL21, AK22], identifying interesting functionalities for which
copy-protection is feasible has been an active research direction [CMP20,
AKL+22, AKL23]. Of particular significance is the problem of copy-protecting
cryptographic functionalities, such as decryption and signing functionalities.
Coladangelo et al. [CLLZ21] took the first step in this direction and showed
that it is feasible to copy-protect decryption functionalities and
pseudorandom functions assuming the existence of post-quantum
indistinguishability obfuscation. While a very significant first step, the
assumption of post-quantum iO is unsatisfactory: there have been numerous
post-quantum iO candidate proposals [BMSZ16, CVW18, BDGM20, DQV+21, GP21,
WW21], but not one of them have been based on well-studied assumptions111111We
remark that, there do exist post-quantum-insecure iO schemes based on well-
founded assumptions [JLS21]..

Our work can be viewed as copy-protecting cryptographic functionalities based
on learning with errors under a weaker yet meaningful security guarantee.

##### Secure Software Leasing.

Another primitive relavent to revocable cryptography is secure software
leasing [AL21]. The notion of secure software leasing states that any program
can be compiled into a functionally equivalent program, represented as a
quantum state, in such a way that once the compiled program is returned
back121212Acording to the terminology of [AL21], this refers to finite term
secure software leasing., the honest evaluation algorithm on the residual
state cannot compute the original functionality. Key-revocable encryption can
be viewed as secure software leasing for decryption algorithms. However,
unlike secure software leasing, key-revocable encryption satisfies a much
stronger security guarantee, where there is no restriction on the adversary to
run honestly after returning back the software. Secure leasing for different
functionalities, namely, point functions [CMP20, BJL+21], evasive functions
[AL21, KNY21a] and pseudorandom functions [ALL+21] have been studied by recent
works.

##### Encryption Schemes with Revocable Ciphertexts.

Unruh [Unr13] proposed a (private-key) quantum timed-release encryption scheme
that is _revocable_ , i.e. it allows a user to _return_ the ciphertext of a
quantum timed-release encryption scheme, thereby losing all access to the
data. Unruh’s scheme uses conjugate coding [Wie83, BB84] and relies on the
_monogamy of entanglement_ in order to guarantee that revocation necessarily
erases information about the plaintext. Broadbent and Islam [BI20a] introduced
the notion of _certified deletion_ 131313This notion is incomparable with
another related notion called unclonable encryption [BL20, AK21, AKL+22],
which informally guarantees that it should be infeasible to clone quantum
ciphertexts without losing information about the encrypted message. and
constructed a private-key quantum encryption scheme with the aforementioned
feature which is inspired by the quantum key distribution protocol [BB84,
TL17]. In contrast with Unruh’s [Unr13] notion of revocable quantum
ciphertexts which are eventually returned and verified, Broadbent and Islam
[BI20a] consider certificates which are entirely classical. Moreover, the
security definition requires that, once the certificate is successfully
verified, the plaintext remains hidden even if the secret key is later
revealed.

Using a hybrid encryption scheme, Hiroka, Morimae, Nishimaki and Yamakawa
[HMNY21a] extended the scheme in [BI20] to both public-key and attribute-based
encryption with certified deletion via _receiver non-committing_ encryption
[JL00, CFGN96]. As a complementary result, the authors also gave a public-key
encryption scheme with certified deletion which is _publicly verifiable_
assuming the existence of one-shot signatures and extractable witness
encryption. Using _Gaussian superpositions_ , Poremba [Por22] proposed _Dual-
Regev_ -based public-key and fully homomorphic encryption schemes with
certified deletion which are publicly verifiable and proven secure assuming a
_strong Gaussian-collapsing conjecture_ — a strengthening of the collapsing
property of the Ajtai hash. Bartusek and Khurana [BK22] revisited the notion
of certified deletion and presented a unified approach for how to generically
convert any public-key, attribute-based, fully-homomorphic, timed-release or
witness encryption scheme into an equivalent quantum encryption scheme with
certified deletion. In particular, they considered a stronger notion called
_certified everlasting security_ which allows the adversary to be
computationally unbounded once a valid deletion certificate is submitted.

## Acknowledgements

P.A. thanks Fatih Kaleoglu for insightful discussions.

This work was done (in part) while the authors were visiting the Simons
Institute for the Theory of Computing. P.A. is supported by a research gift
from Cisco. A.P. is partially supported by AFOSR YIP (award number
FA9550-16-1-0495), the Institute for Quantum Information and Matter (an NSF
Physics Frontiers Center; NSF Grant PHY-1733907) and by a grant from the
Simons Foundation (828076, TV).

##  2 Preliminaries

Let $\lambda\in\mathbb{N}$ denote the security parameter throughout this work.
We assume that the reader is familiar with the fundamental cryptographic
concepts.

###  2.1 Quantum Computing

For a comprehensive background on quantum computation, we refer to [NC11,
Wil13]. We denote a finite-dimensional complex Hilbert space by $\mathcal{H}$,
and we use subscripts to distinguish between different systems (or registers).
For example, we let $\mathcal{H}_{A}$ be the Hilbert space corresponding to a
system $A$. The tensor product of two Hilbert spaces $\mathcal{H}_{A}$ and
$\mathcal{H}_{B}$ is another Hilbert space denoted by
$\mathcal{H}_{AB}=\mathcal{H}_{A}\otimes\mathcal{H}_{B}$. Let
$\mathcal{L}(\mathcal{H})$ denote the set of linear operators over
$\mathcal{H}$. A quantum system over the $2$-dimensional Hilbert space
$\mathcal{H}=\mathbb{C}^{2}$ is called a _qubit_. For $n\in\mathbb{N}$, we
refer to quantum registers over the Hilbert space
$\mathcal{H}=\big{(}\mathbb{C}^{2}\big{)}^{\otimes n}$ as $n$-qubit states.
More generally, we associate _qudits_ of dimension $d\geq 2$ with a
$d$-dimensional Hilbert space $\mathcal{H}=\mathbb{C}^{d}$. For brevity, we
write $\mathcal{H}_{d}^{n}=\mathcal{H}_{d}^{\otimes n}$, where
$\mathcal{H}_{d}$ is $d$-dimensional. We use the word _quantum state_ to refer
to both pure states (unit vectors $\ket{\psi}\in\mathcal{H}$) and density
matrices $\rho\in\mathcal{D}(\mathcal{H)}$, where we use the notation
$\mathcal{D}(\mathcal{H)}$ to refer to the space of positive semidefinite
matrices of unit trace acting on $\mathcal{H}$. Occasionally, we consider
_subnormalized states_ , i.e. states in the space of positive semidefinite
operators over $\mathcal{H}$ with trace norm not exceeding $1$.

The _trace distance_ of two density matrices
$\rho,\sigma\in\mathcal{D}(\mathcal{H)}$ is given by

$\operatorname{TD}(\rho,\sigma)=\frac{1}{2}\mathrm{Tr}\left[\sqrt{(\rho-\sigma)^{\dagger}(\rho-\sigma)}\right].$

Let $q\geq 2$ be a modulus and $n\in\mathbb{N}$ and let
$\omega_{q}=e^{\frac{2\pi i}{q}}\in\mathbb{C}$ denote the primitive $q$-th
root of unity. The $n$-qudit _$q$ -ary quantum Fourier transform_ over the
ring $\mathbb{Z}_{q}^{n}$ is defined by the operation,

$\mathsf{FT}_{q}:\quad\ket{\mathbf{x}}\quad\mapsto\quad\sqrt{q^{-n}}\displaystyle\sum_{\mathbf{y}\in\mathbb{Z}_{q}^{n}}\omega_{q}^{\langle\mathbf{x},\mathbf{y}\rangle}\ket{\mathbf{y}},\quad\quad\forall\mathbf{x}\in\mathbb{Z}_{q}^{n}.$

The $q$-ary quantum Fourier transform is _unitary_ and can be efficiently
performed on a quantum computer for any modulus $q\geq 2$ [HH00].

A quantum channel
$\Phi:\mathcal{L}(\mathcal{H}_{A})\rightarrow\mathcal{L}(\mathcal{H}_{B})$ is
a linear map between linear operators over the Hilbert spaces
$\mathcal{H}_{A}$ and $\mathcal{H}_{B}$. Oftentimes, we use the compact
notation $\Phi_{A\rightarrow B}$ to denote a quantum channel between
$\mathcal{L}(\mathcal{H}_{A})$ and $\mathcal{L}(\mathcal{H}_{B})$. We say that
a channel $\Phi$ is _completely positive_ if, for a reference system $R$ of
arbitrary size, the induced map $I_{R}\otimes\Phi$ is positive, and we call it
_trace-preserving_ if $\mathrm{Tr}[\Phi(X)]=\mathrm{Tr}[X]$, for all
$X\in\mathcal{L}(\mathcal{H})$. A quantum channel that is both completely
positive and trace-preserving is called a quantum $\mathsf{CPTP}$ channel.

A polynomial-time _uniform_ quantum algorithm (or $\mathsf{QPT}$ algorithm) is
a polynomial-time family of quantum circuits given by
$\mathcal{C}=\\{C_{\lambda}\\}_{\lambda\in\mathbb{N}}$, where each circuit
$C\in\mathcal{C}$ is described by a sequence of unitary gates and
measurements; moreover, for each $\lambda\in\mathbb{N}$, there exists a
deterministic polynomial-time Turing machine that, on input $1^{\lambda}$,
outputs a circuit description of $C_{\lambda}$. Similarly, we also define
(classical) probabilistic polynomial-time $(\mathsf{PPT})$ algorithms. A
quantum algorithm may, in general, receive (mixed) quantum states as inputs
and produce (mixed) quantum states as outputs. Occasionally, we restrict
$\mathsf{QPT}$ algorithms implicitly; for example, if we write
$\Pr[\mathcal{A}(1^{\lambda})=1]$ for a $\mathsf{QPT}$ algorithm
$\mathcal{A}$, it is implicit that $\mathcal{A}$ is a $\mathsf{QPT}$ algorithm
that outputs a single classical bit.

A polynomial-time _non-uniform_ quantum algorithm is a family
$\\{(C_{\lambda},\nu_{\lambda})\\}_{\lambda\in\mathbb{N}}$, where
$\\{C_{\lambda}\\}_{\lambda\in\mathbb{N}}$ is a polynomial-size (not
necessarily uniformly generated) family of circuits where, for each
$\lambda\in\mathbb{N}$, a subset of input qubits to $C_{\lambda}$ consists of
a polynomial-size auxiliary density matrix $\nu_{\lambda}$. We use the
following notion of indistinguishability of quantum states in the presence of
auxiliary inputs.

######  Definition 2.1 (Indistinguishability of ensembles of quantum states,
[Wat05]).

Let $p:\mathbb{N}\rightarrow\mathbb{N}$ be a polynomially bounded function,
and let $\rho_{\lambda}$ and $\sigma_{\lambda}$ be $p(\lambda)$-qubit quantum
states. We say that $\\{\rho_{\lambda}\\}_{\lambda\in\mathbb{N}}$ and
$\\{\sigma_{\lambda}\\}_{\lambda\in\mathbb{N}}$ are quantum computationally
indistinguishable ensembles of quantum states, denoted by
$\rho_{\lambda}\approx_{c}\sigma_{\lambda}\,,$ if, for any $\mathsf{QPT}$
distinguisher $\mathcal{D}$ with single-bit output, any polynomially bounded
$q:\mathbb{N}\rightarrow\mathbb{N}$, any family of $q(\lambda)$-qubit
auxiliary states $\\{\nu_{\lambda}\\}_{\lambda\in\mathbb{N}}$, and every
$\lambda\in\mathbb{N}$,

$\big{|}\Pr[\mathcal{D}(\rho_{\lambda}\otimes\nu_{\lambda})=1]-\Pr[\mathcal{D}(\sigma_{\lambda}\otimes\nu_{\lambda})=1]\big{|}\leq\mathsf{negl}(\lambda)\,.$

###  2.2 Lattices and Cryptography

Let $n,m,p,q\in\mathbb{N}$ be positive integers. The rounding operation for
$q\geq p\geq 2$ is the function

$\lfloor\cdot\rfloor_{p}\,\,:\,\,\mathbb{Z}_{q}\rightarrow\mathbb{Z}_{p}\,\,:\,\,x\mapsto\lfloor(p/q)\cdot
x\rfloor\ (\mathrm{mod}\ p).$

A lattice $\Lambda\subset\mathbb{R}^{m}$ is a discrete subgroup of
$\mathbb{R}^{m}$. Given a lattice $\Lambda\subset\mathbb{R}^{m}$ and a vector
$\mathbf{t}\in\mathbb{R}^{m}$, we define the coset with respect to vector
$\mathbf{t}$ as the lattice shift
$\Lambda-\mathbf{t}=\\{\mathbf{x}\in\mathbb{R}^{m}:\,\mathbf{x}+\mathbf{t}\in\Lambda\\}$.
Note that many different shifts $\mathbf{t}$ can define the same coset. The
_dual_ of a lattice $\Lambda\subset\mathbb{R}^{m}$, denoted by $\Lambda^{*}$,
is the lattice of all $y\in\mathbb{R}^{m}$ that satisfy
$\langle\mathbf{y},\mathbf{x}\rangle\in\mathbb{Z}$, for every
$\mathbf{x}\in\Lambda$. In other words, we let

$\Lambda^{*}=\left\\{\mathbf{y}\in\mathbb{R}^{m}\,:\,\langle\mathbf{y},\mathbf{x}\rangle\in\mathbb{Z},\text{
for all }\mathbf{x}\in\Lambda\right\\}.$

In this work, we mainly consider _$q$ -ary lattices_ $\Lambda$ that that
satisfy $q\mathbb{Z}^{m}\subseteq\Lambda\subseteq\mathbb{Z}^{m}$, for some
integer modulus $q\geq 2$. Specifically, we consider the lattice generated by
a matrix $\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$ for some $n,m\in\mathbb{N}$
that consists of all vectors which are perpendicular to the rows of
$\mathbf{A}$, namely

$\Lambda_{q}^{\bot}(\mathbf{A})=\\{\mathbf{x}\in\mathbb{Z}^{m}:\,\mathbf{A}\cdot\mathbf{x}=\mathbf{0}\
(\mathrm{mod}\ q)\\}.$

For any _syndrome_ $\mathbf{y}\in\mathbb{Z}_{q}^{n}$ in the column span of
$\mathbf{A}$, we also consider the coset
$\Lambda_{q}^{\mathbf{y}}(\mathbf{A})$ given by

$\Lambda_{q}^{\mathbf{y}}(\mathbf{A})=\\{\mathbf{x}\in\mathbb{Z}^{m}:\,\mathbf{A}\cdot\mathbf{x}=\mathbf{y}\
(\mathrm{mod}\ q)\\}=\Lambda_{q}^{\bot}(\mathbf{A})+\mathbf{c},$

where $\mathbf{c}\in\mathbb{Z}^{m}$ is an arbitrary integer solution to the
equation $\mathbf{A}\mathbf{c}=\mathbf{y}\ (\mathrm{mod}\ q)$.

We use the following facts due to Gentry, Peikert and Vaikuntanathan [GPV07].

######  Lemma 2.2 ([GPV07], Lemma 5.1).

Let $n\in\mathbb{N}$ and let $q\geq 2$ be a prime modulus with $m\geq 2n\log
q$. Then, for all but a $q^{-n}$ fraction of
$\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$, the subset-sums of the columns of
$\mathbf{A}$ generate $\mathbb{Z}_{q}^{n}$. In other words, a uniformly random
matrix
$\mathbf{A}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n\times
m}$ is full-rank with overwhelming probability.

##### Gaussian Distribution.

The _Gaussian measure_ $\rho_{\sigma}$ with parameter $\sigma>0$ is defined as

$\displaystyle\rho_{\sigma}(\mathbf{x})=\exp(-\pi\|\mathbf{x}\|^{2}/\sigma^{2}),\quad\,\,\forall\mathbf{x}\in\mathbb{R}^{m}.$

Let $\Lambda\subset\mathbb{R}^{m}$ be a lattice and let
$\mathbf{t}\in\mathbb{R}^{m}$. We define the _Gaussian mass_ of
$\Lambda-\mathbf{t}$ as the quantity

$\displaystyle\rho_{\sigma}(\Lambda-\mathbf{t})=\sum_{\mathbf{y}\in\Lambda}\rho_{\sigma}(\mathbf{y}-\mathbf{t}).$

The _discrete Gaussian distribution_ $D_{\Lambda-\mathbf{t},\sigma}$ assigns
probability proportional to $e^{-\pi\|\mathbf{x}-\mathbf{t}\|^{2}/\sigma^{2}}$
to every lattice point $\mathbf{x}\in\Lambda$. In other words, we have

$D_{\Lambda-\mathbf{t},\sigma}(\mathbf{x})=\frac{\rho_{\sigma}(\mathbf{x}-\mathbf{t})}{\rho_{\sigma}(\Lambda-\mathbf{t})},\quad\,\,\forall\mathbf{x}\in\Lambda.$

The following lemma follows from [PR06, Lemma 2.11] and [GPV07, Lemma 5.3].

######  Lemma 2.3.

Let $n\in\mathbb{N}$ and let $q$ be a prime with $m\geq 2n\log q$. Let
$\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$ be a matrix whose columns generate
$\mathbb{Z}_{q}^{n}$. Let $\mathbf{y}\in\mathbb{Z}_{q}^{n}$ be arbitrary.
Then, for any $\sigma\geq\omega(\sqrt{\log m})$, there exists a negligible
function $\varepsilon(m)$ such that

$D_{\Lambda_{q}^{\mathbf{y}}(\mathbf{A}),\sigma}(\mathbf{x})\,\leq\,2^{-m}\cdot\frac{1+\varepsilon}{1-\varepsilon},\quad\quad\forall\,\mathbf{x}\in\Lambda_{q}^{\bot}(\mathbf{A}).$

Let
$\mathcal{B}^{m}(\mathbf{0},r)=\\{\mathbf{x}\in\mathbb{R}^{m}\,:\,\|\mathbf{x}\|\leq
r\\}$ denote the $m$-dimensional ball of radius $r>0$. We use of the following
tail bound for the Gaussian mass of a lattice [Ban93, Lemma 1.5 (ii)].

######  Lemma 2.4.

For any $m$-dimensional lattice $\Lambda$, shift
$\mathbf{t}\in\mathbb{R}^{m}$, $\sigma>0$ and $c\geq(2\pi)^{-\frac{1}{2}}$ it
holds that

$\rho_{\sigma}\left((\Lambda-\mathbf{t})\setminus\mathcal{B}^{m}(\mathbf{0},c\sqrt{m}\sigma)\right)\leq(2\pi
ec^{2})^{\frac{m}{2}}e^{-\pi c^{2}m}\rho_{\sigma}(\Lambda).$

In addition, we also make use of the following tail bound for the discrete
Gaussian which follows from [MR04, Lemma 4.4] and [GPV07, Lemma 5.3].

######  Lemma 2.5.

Let $n\in\mathbb{N}$ and let $q$ be a prime with $m\geq 2n\log q$. Let
$\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$ be a matrix whose columns generate
$\mathbb{Z}_{q}^{n}$. Let $\mathbf{y}\in\mathbb{Z}_{q}^{n}$ be arbitrary.
Then, for any $\sigma\geq\omega(\sqrt{\log m})$, there exists a negligible
function $\varepsilon(m)$ such that

$\Pr_{\mathbf{x}\sim
D_{\Lambda_{q}^{\mathbf{y}}(\mathbf{A}),\sigma}}\Big{[}\|\mathbf{x}\|>\sigma\sqrt{m}\Big{]}\leq
2^{-m}\cdot\frac{1+\varepsilon}{1-\varepsilon}.$

Given a modulus $q\in\mathbb{N}$ and $\sigma\in(0,q/2\sqrt{m})$, the
_truncated_ discrete Gaussian distribution $D_{\mathbb{Z}_{q}^{m},\sigma}$
over $\mathbb{Z}^{m}\cap(-\frac{q}{2},\frac{q}{2}]^{m}$ with support
$\\{\mathbf{x}\in\mathbb{Z}_{q}^{m}:\|\mathbf{x}\|\leq\sigma\sqrt{m}\\}$ is
the density function defined below:

$D_{\mathbb{Z}_{q}^{m},\sigma}(\mathbf{x})=\frac{\rho_{\sigma}(\mathbf{x})}{\displaystyle\sum_{\mathbf{z}\in\mathbb{Z}_{q}^{m},\|\mathbf{z}\|\leq\sigma\sqrt{m}}\rho_{\sigma}(\mathbf{z})}.$

Finally, we recall the following _noise flooding_ property.

######  Lemma 2.6 ([BCM+21], Lemma 2.4).

Let $q$ be a modulus, $m\in\mathbb{N}$ and $\sigma>0$. Then, for
$\mathbf{e}_{0}\in\mathbb{Z}^{m}$,

$\|D_{\mathbb{Z}_{q}^{m},\sigma}-(D_{\mathbb{Z}_{q}^{m},\sigma}+\mathbf{e}_{0})\|_{\mathsf{TV}}\leq
2\cdot\Big{(}1-e^{\frac{-2\pi\sqrt{m}\|\mathbf{e}_{0}\|}{\sigma}}\Big{)}.$

We use the following technical lemma on the min-entropy of the truncated
discrete Gaussian distribution, which we prove below.

######  Lemma 2.7.

Let $n\in\mathbb{N}$ and let $q$ be a prime with $m\geq 2n\log q$. Let
$\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$ be a matrix whose columns generate
$\mathbb{Z}_{q}^{n}$. Then, for any $\sigma\geq\omega(\sqrt{\log m})$, there
exists a negligible $\varepsilon(m)$ such that

$\max_{\mathbf{y}\in\mathbb{Z}_{q}^{n}}\,\,\max_{\begin{subarray}{c}\mathbf{x}\in\mathbb{Z}_{q}^{m},\,\|\mathbf{x}\|\leq\sigma\sqrt{m}\\\
\mathbf{A}\mathbf{x}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\left\\{\frac{\rho_{\sigma}(\mathbf{x})}{\displaystyle\sum_{\begin{subarray}{c}\mathbf{z}\in\mathbb{Z}_{q}^{m},\|\mathbf{z}\|\leq\sigma\sqrt{m}\\\
\mathbf{A}\mathbf{z}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\rho_{\sigma}(\mathbf{z})}\right\\}\,\,\leq\,\,2^{-m+1}\cdot\frac{1+\varepsilon}{1-\varepsilon}.$

###### Proof.

Suppose that $\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$ is a matrix whose
columns generate $\mathbb{Z}_{q}^{n}$, i.e. $\mathbf{A}$ is full-rank. Then,

$\displaystyle\max_{\mathbf{y}\in\mathbb{Z}_{q}^{n}}\,\max_{\begin{subarray}{c}\mathbf{x}\in\mathbb{Z}_{q}^{m},\,\|\mathbf{x}\|\leq\sigma\sqrt{m}\\\
\mathbf{A}\mathbf{x}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\left\\{\frac{\rho_{\sigma}(\mathbf{x})}{\displaystyle\sum_{\begin{subarray}{c}\mathbf{z}\in\mathbb{Z}_{q}^{m},\|\mathbf{z}\|\leq\sigma\sqrt{m}\\\
\mathbf{A}\mathbf{z}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\rho_{\sigma}(\mathbf{z})}\right\\}$
$\displaystyle\leq\quad\max_{\mathbf{y}\in\mathbb{Z}_{q}^{n}}\sup_{\mathbf{x}\in\Lambda_{q}^{\bot}(\mathbf{A})}D_{\Lambda_{q}^{\mathbf{y}}(\mathbf{A}),\sigma}(\mathbf{x})$
$\displaystyle\quad+\max_{\mathbf{y}\in\mathbb{Z}_{q}^{n}}\max_{\begin{subarray}{c}\mathbf{x}\in\mathbb{Z}_{q}^{m},\,\|\mathbf{x}\|\leq\sigma\sqrt{m}\\\
\mathbf{A}\mathbf{x}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\left|\frac{\rho_{\sigma}(\mathbf{x})}{\displaystyle\sum_{\begin{subarray}{c}\mathbf{z}\in\mathbb{Z}_{q}^{m},\|\mathbf{z}\|\leq\sigma\sqrt{m}\\\
\mathbf{A}\mathbf{z}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\rho_{\sigma}(\mathbf{z})}-\frac{\rho_{\sigma}(\mathbf{x})}{\displaystyle\sum_{\begin{subarray}{c}\mathbf{z}\in\mathbb{Z}^{m}\\\
\mathbf{A}\mathbf{z}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\rho_{\sigma}(\mathbf{z})}\right|$
$\displaystyle\leq\quad\max_{\mathbf{y}\in\mathbb{Z}_{q}^{n}}\sup_{\mathbf{x}\in\Lambda_{q}^{\bot}(\mathbf{A})}D_{\Lambda_{q}^{\mathbf{y}}(\mathbf{A}),\sigma}(\mathbf{x})$
$\displaystyle\quad+\max_{\mathbf{y}\in\mathbb{Z}_{q}^{n}}\max_{\begin{subarray}{c}\mathbf{x}\in\mathbb{Z}_{q}^{m},\,\|\mathbf{x}\|\leq\sigma\sqrt{m}\\\
\mathbf{A}\mathbf{x}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\frac{\rho_{\sigma}(\mathbf{x})}{\displaystyle\sum_{\begin{subarray}{c}\mathbf{z}\in\mathbb{Z}_{q}^{m},\|\mathbf{z}\|\leq\sigma\sqrt{m}\\\
\mathbf{A}\mathbf{z}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\rho_{\sigma}(\mathbf{z})}\cdot\frac{\rho_{\sigma}(\Lambda_{q}^{\mathbf{y}}(\mathbf{A})\setminus\mathcal{B}^{m}(\mathbf{0},\sigma\sqrt{m}))}{\rho_{\sigma}(\Lambda_{q}^{\mathbf{y}}(\mathbf{A}))}$

where
$B^{m}(\mathbf{0},r)=\\{\mathbf{x}\in\mathbb{R}^{m}\,:\,\|\mathbf{x}\|\leq
r\\}$. Using the fact that

$\frac{\rho_{\sigma}(\mathbf{x})}{\displaystyle\sum_{\begin{subarray}{c}\mathbf{z}\in\mathbb{Z}_{q}^{m},\|\mathbf{z}\|\leq\sigma\sqrt{m}\\\
\mathbf{A}\mathbf{z}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\rho_{\sigma}(\mathbf{z})}\,\,\leq\,\,1,$

for $\mathbf{x}\in\mathbb{Z}_{q}^{m}$ with $\mathbf{A}\mathbf{x}=\mathbf{y}\
(\mathrm{mod}\ q)$, and the fact that

$\Pr_{\mathbf{v}\sim
D_{\Lambda_{q}^{\mathbf{y}}(\mathbf{A}),\sigma}}\Big{[}\|\mathbf{v}\|>\sigma\sqrt{m}\Big{]}=\frac{\rho_{\sigma}(\Lambda_{q}^{\mathbf{y}}(\mathbf{A})\setminus\mathcal{B}^{m}(\mathbf{0},\sigma\sqrt{m}))}{\rho_{\sigma}(\Lambda_{q}^{\mathbf{y}}(\mathbf{A}))}$

we get that

$\displaystyle\max_{\mathbf{y}\in\mathbb{Z}_{q}^{n}}\,\max_{\begin{subarray}{c}\mathbf{x}\in\mathbb{Z}_{q}^{m},\,\|\mathbf{x}\|\leq\sigma\sqrt{m}\\\
\mathbf{A}\mathbf{x}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\left\\{\frac{\rho_{\sigma}(\mathbf{x})}{\displaystyle\sum_{\begin{subarray}{c}\mathbf{z}\in\mathbb{Z}_{q}^{m},\|\mathbf{z}\|\leq\sigma\sqrt{m}\\\
\mathbf{A}\mathbf{z}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\rho_{\sigma}(\mathbf{z})}\right\\}$
$\displaystyle\leq\max_{\mathbf{y}\in\mathbb{Z}_{q}^{n}}\left\\{\sup_{\mathbf{x}\in\Lambda_{q}^{\bot}(\mathbf{A})}D_{\Lambda_{q}^{\mathbf{y}}(\mathbf{A}),\sigma}(\mathbf{x})+\Pr_{\mathbf{v}\sim
D_{\Lambda_{q}^{\mathbf{y}}(\mathbf{A}),\sigma}}\Big{[}\|\mathbf{v}\|>\sigma\sqrt{m}\Big{]}\right\\}.$

Because $\sigma\geq\omega(\sqrt{\log m})$, the claim then follows from Lemma
2.3 and Lemma 2.5.

∎

##### The Short Integer Solution problem.

The _Short Integer Solution_ ($\mathsf{SIS}$) problem was introduced by Ajtai
[Ajt96] in his seminal work on average-case lattice problems.

######  Definition 2.8 (Short Integer Solution problem, [Ajt96]).

Let $n,m\in\mathbb{N}$, $q\geq 2$ be a modulus and let $\beta>0$ be a
parameter. The Short Integer Solution problem $(\mathsf{SIS}_{n,q,\beta}^{m})$
problem is to find a short solution $\mathbf{x}\in\mathbb{Z}^{m}$ with
$\|\mathbf{x}\|\leq\beta$ such that $\mathbf{A}\cdot\mathbf{x}=\mathbf{0}\
(\mathrm{mod}\ q)$ given as input a matrix
$\mathbf{A}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n\times
m}$.

Micciancio and Regev [MR07] showed that the $\mathsf{SIS}$ problem is, on the
average, as hard as approximating worst-case lattice problems to within small
factors. Subsequently, Gentry, Peikert and Vaikuntanathan [GPV07] gave an
improved reduction showing that, for parameters $m=\mathrm{poly}(n)$,
$\beta=\mathrm{poly}(n)$ and prime $q\geq\beta\cdot\omega(\sqrt{n\log q})$,
the average-case $\mathsf{SIS}_{n,q,\beta}^{m}$ problem is as hard as
approximating the shortest independent vector problem $(\mathsf{SIVP})$
problem in the worst case to within a factor
$\gamma=\beta\cdot\tilde{O}(\sqrt{n})$. We assume that
$\mathsf{SIS}_{n,q,\beta}^{m}$, for $m=\Omega(n\log q)$, $\beta=2^{o(n)}$ and
$q=2^{o(n)}$, is hard against quantum adversaries running in time
$\mathrm{poly}(q)$ with success probability $\mathrm{poly}(1/q)$.

##### The Learning with Errors problem.

The _Learning with Errors_ problem was introduced by Regev [Reg05] and serves
as the primary basis of hardness of post-quantum cryptosystems. The problem is
defined as follows.

######  Definition 2.9 (Learning with Errors problem, [Reg05]).

Let $n,m\in\mathbb{N}$ be integers, let $q\geq 2$ be a modulus and let
$\alpha\in(0,1)$ be a noise ratio parameter. The (decisional) Learning with
Errors $(\mathsf{LWE}_{n,q,\alpha q}^{m})$ problem is to distinguish between
the following samples

$(\mathbf{A}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n\times
m},\mathbf{s}^{\intercal}\mathbf{A}+\mathbf{e}^{\intercal}\ (\mathrm{mod}\
q))\quad\text{ and
}\quad(\mathbf{A}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n\times
m},\mathbf{u}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{m}),\,\,$

where
$\mathbf{s}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n}$
is a uniformly random vector and where $\mathbf{e}\sim
D_{\mathbb{Z}^{m},\alpha q}$ is a discrete Gaussian error vector. We rely on
the quantum $\mathsf{LWE}_{n,q,\alpha q}^{m}$ assumption which states that the
samples above are computationally indistinguishable for any $\mathsf{QPT}$
algorithm.

As shown in [Reg05], the $\mathsf{LWE}_{n,q,\alpha q}^{m}$ problem with
parameter $\alpha q\geq 2\sqrt{n}$ is at least as hard as approximating the
shortest independent vector problem $(\mathsf{SIVP})$ to within a factor of
$\gamma=\widetilde{O}(n/\alpha)$ in worst case lattices of dimension $n$. In
this work we assume the subexponential hardness of $\mathsf{LWE}_{n,q,\alpha
q}^{m}$ which relies on the worst case hardness of approximating short vector
problems in lattices to within a subexponential factor. We assume that the
$\mathsf{LWE}_{n,q,\alpha q}^{m}$ problem, for $m=\Omega(n\log q)$,
$q=2^{o(n)}$, $\alpha=1/2^{o(n)}$, is hard against quantum adversaries running
in time $\mathrm{poly}(q)$. We note that this parameter regime implies
$\mathsf{SIS}_{n,q,\beta}^{m}$ [SSTX09].

##### Trapdoors for lattices.

We use the following _trapdoor_ property for the $\mathsf{LWE}$ problem.

######  Theorem 2.10 ([MP11], Theorem 5.1).

Let $n,m\in\mathbb{N}$ and $q\in\mathbb{N}$ be a prime with $m=\Omega(n\log
q)$. There exists a randomized algorithms with the following properties:

  * •

$\mathsf{GenTrap}(1^{n},1^{m},q)$: on input $1^{n},1^{m}$ and $q$, returns a
matrix $\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$ and a trapdoor
$\mathsf{td}_{\mathbf{A}}$ such that the distribution of $\mathbf{A}$ is
negligibly (in the parameter $n$) close to uniform.

  * •

$\mathsf{Invert}(\mathbf{A},\mathsf{td}_{\mathbf{A}},\mathbf{b})$: on input
$\mathbf{A}$, $\mathsf{td}_{\mathbf{A}}$ and
$\mathbf{b}=\mathbf{s}^{\intercal}\cdot\mathbf{A}+\mathbf{e}^{\intercal}\
(\mathrm{mod}\ q)$, where $\|\mathbf{e}\|\leq q/(C_{T}\sqrt{n\log q})$ and
$C_{T}>0$ is a universal constant, returns $\mathbf{s}$ and $\mathbf{e}$ with
overwhelming probability over
$(\mathbf{A},\mathsf{td}_{\mathbf{A}})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)$.

##  3 Quantum Discrete Gaussian Sampling for $q$-ary Lattices

In this section, we review some basic facts about Gaussian superpositions and
present our _quantum discrete Gaussian sampler_ which is used to revoke the
decryption keys for our schemes.

###  3.1 Gaussian Superpositions

In this section, we review some basic facts about _Gaussian superpositions_.
Given $q\in\mathbb{N}$, $m\in\mathbb{N}$ and
$\sigma\in(\sqrt{2m},q/\sqrt{2m})$, we consider Gaussian superpositions over
$\mathbb{Z}^{m}\cap(-\frac{q}{2},\frac{q}{2}]^{m}$ of the form

$\ket{\psi}=\sum_{\mathbf{x}\in\mathbb{Z}_{q}^{m}}\rho_{\sigma}(\mathbf{x})\ket{\mathbf{x}}.$

Note that the state $\ket{\psi}$ is not normalized for convenience and ease of
notation. The tail bound in Lemma 2.4 implies that (the normalized variant of)
$\ket{\psi}$ is within negligible trace distance of a _truncated_ discrete
Gaussian superposition $\ket{\tilde{\psi}}$ with support
$\\{\mathbf{x}\in\mathbb{Z}_{q}^{m}:\|\mathbf{x}\|\leq\sigma\sqrt{\frac{m}{2}}\\}$,
where

$\ket{\tilde{\psi}}=\sum_{\mathbf{x}\in\mathbb{Z}_{q}^{m}}\sqrt{D_{\mathbb{Z}_{q}^{m},\frac{\sigma}{\sqrt{2}}}(\mathbf{x})}\,\ket{\mathbf{x}}=\left(\sum_{\mathbf{z}\in\mathbb{Z}_{q}^{m},\|\mathbf{z}\|\leq\sigma\sqrt{\frac{m}{2}}}\rho_{\frac{\sigma}{\sqrt{2}}}(\mathbf{z})\right)^{-\frac{1}{2}}\sum_{\mathbf{x}\in\mathbb{Z}_{q}^{m}:\|\mathbf{x}\|\leq\sigma\sqrt{\frac{m}{2}}}\rho_{\sigma}(\mathbf{x})\ket{\mathbf{x}}.$

In this work, we consider Gaussian superpositions with parameter
$\sigma=\Omega(\sqrt{m})$ which can be efficiently implemented using standard
quantum state preparation techniques; for example using _quantum rejection
sampling_ and the _Grover-Rudolph algorithm_ [GR02, Reg05, Bra18, BCM+21].

##### Gaussian coset states.

Our key-revocable encryption schemes in Section 6 and Section 7 rely on
Gaussian superpositions over $\mathbf{x}\in\mathbb{Z}_{q}^{m}$ subject to a
constraint of the form $\mathbf{A}\cdot\mathbf{x}=\mathbf{y}\ (\mathrm{mod}\
q)$, for some matrix $\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$ and image
$\mathbf{y}\in\mathbb{Z}_{q}^{n}$. In Algorithm 1, we give a procedure called
$\mathsf{GenGauss}$ that, on input $\mathbf{A}$ and $\sigma>0$, generates a
Gaussian superposition state of the form

$\ket{\psi_{\mathbf{y}}}=\sum_{\begin{subarray}{c}\mathbf{x}\in\mathbb{Z}_{q}^{m}:\\\
\mathbf{A}\mathbf{x}=\mathbf{y}\end{subarray}}\rho_{\sigma}(\mathbf{x})\ket{\mathbf{x}},$

for some $\mathbf{y}\in\mathbb{Z}_{q}^{n}$ which is statistically close to
uniform whenever $m\geq 2n\log q$ and $\sigma\geq\omega(\sqrt{\log m})$.
Because $\ket{\psi_{\mathbf{y}}}$ corresponds to a (truncated) Gaussian
superposition over a particular lattice coset,

$\Lambda_{q}^{\mathbf{y}}(\mathbf{A})=\\{\mathbf{x}\in\mathbb{Z}^{m}:\mathbf{A}\cdot\mathbf{x}=\mathbf{y}\
(\mathrm{mod}\ q)\\},$

of the $q$-ary lattice
$\Lambda_{q}^{\bot}(\mathbf{A})=\\{\mathbf{x}\in\mathbb{Z}^{m}:\,\mathbf{A}\cdot\mathbf{x}=\mathbf{0}\
(\mathrm{mod}\ q)\\}$, we refer to it as a _Gaussian coset state_.

###  3.2 Algorithm: GenGauss

The state preparation procedure $\mathsf{GenGauss}(\mathbf{A},\sigma)$ is
defined as follows.

Input: Matrix $\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$ and parameter
$\sigma=\Omega(\sqrt{m})$.

Output: Gaussian state $\ket{\psi_{\mathbf{y}}}$ and
$\mathbf{y}\in\mathbb{Z}_{q}^{n}$.

1

2Prepare a Gaussian superposition in system $X$ with parameter $\sigma>0$:
$\ket{\psi}_{XY}=\sum_{\mathbf{x}\in\mathbb{Z}_{q}^{m}}\rho_{\sigma}(\mathbf{x})\ket{\mathbf{x}}_{X}\otimes\ket{\mathbf{0}}_{Y}.$

3 Apply the unitary
$U_{\mathbf{A}}:\ket{\mathbf{x}}\ket{\mathbf{0}}\rightarrow\ket{\mathbf{x}}\ket{\mathbf{A}\cdot\mathbf{x}\
(\mathrm{mod}\ q)}$ on systems $X$ and $Y$:
$\ket{\psi}_{XY}=\sum_{\mathbf{x}\in\mathbb{Z}_{q}^{m}}\rho_{\sigma}(\mathbf{x})\ket{\mathbf{x}}_{X}\otimes\ket{\mathbf{A}\cdot\mathbf{x}\
(\mathrm{mod}\ q)}_{Y}.$

4 Measure system $Y$ in the computational basis, resulting in the state
$\ket{\psi_{\mathbf{y}}}_{XY}=\sum_{\begin{subarray}{c}\mathbf{x}\in\mathbb{Z}_{q}^{m}:\\\
\mathbf{A}\mathbf{x}=\mathbf{y}\end{subarray}}\rho_{\sigma}(\mathbf{x})\ket{\mathbf{x}}_{X}\otimes\ket{\mathbf{y}}_{Y}.$

Output the state $\ket{\psi_{\mathbf{y}}}$ in system $X$ and the outcome
$\mathbf{y}\in\mathbb{Z}_{q}^{n}$ in system $Y$.

Algorithm 1 $\mathsf{GenGauss}(\mathbf{A},\sigma)$

###  3.3 Algorithm: QSampGauss

Recall that, in Algorithm 1, we gave a procedure called
$\mathsf{GenGauss}(\mathbf{A},\sigma)$ that prepares a Gaussian coset state
$\ket{\psi_{\mathbf{y}}}$, for a randomly generated
$\mathbf{y}\in\mathbb{Z}_{q}^{n}$. In general, however, generating a specific
Gaussian coset state on input $(\mathbf{A},\mathbf{y})$ requires a _short
trapdoor basis_ $\mathsf{td}_{\mathbf{A}}$ for the matrix $\mathbf{A}$. This
task can be thought of as a quantum analogue of the _discrete Gaussian
sampling problem_ [GPV07], where the goal is to output a sample
$\mathbf{x}\sim D_{Z^{m},\sigma}$ such that
$\mathbf{A}\cdot\mathbf{x}=\mathbf{y}\ (\mathrm{mod}\ q)$ on input
$(\mathbf{A},\mathbf{y})$ and $\sigma>0$.

In Algorithm 2, we give a procedure called $\mathsf{QSampGauss}$ which, on
input $(\mathbf{A},\mathsf{td}_{\mathbf{A}},\mathbf{y},\sigma)$ generates a
specific Gaussian coset state $\ket{\psi_{\mathbf{y}}}$ of the form

$\ket{\psi_{\mathbf{y}}}=\sum_{\begin{subarray}{c}\mathbf{x}\in\mathbb{Z}_{q}^{m}\\\
\mathbf{A}\mathbf{x}=\mathbf{y}\end{subarray}}\rho_{\sigma}(\mathbf{x})\,\ket{\mathbf{x}}.$

Our procedure $\mathsf{SampGauss}$ in Algorithm 2 can be thought of as an
explicit quantum reduction from $\mathsf{ISIS}_{n,q,\sigma\sqrt{m/2}}^{m}$ to
$\mathsf{LWE}_{n,q,q/\sqrt{2}\sigma}^{m}$ which is inspired by the quantum
reduction of Stehlé et al. [SSTX09] which reduces $\mathsf{SIS}$ to
$\mathsf{LWE}$. To obtain the aforementioned reduction, one simply needs to
replace the procedure
$\mathsf{Invert}(\mathbf{A},{\mathsf{td}_{\mathbf{A}}},\cdot)$ in Step $4$ in
Algorithm 2 with a solver for the $\mathsf{LWE}_{n,q,q/\sqrt{2}\sigma}^{m}$
problem.

In Theorem 3.2, we prove the correctness of Algorithm 2. As a technical
ingredient, we rely on a _duality lemma_ [Por22] that characterizes the
Fourier transform of a Gaussian coset state in terms of its dual state. Note
that $\ket{\psi_{\mathbf{y}}}$ corresponds to a Gaussian superposition over a
lattice coset,

$\Lambda_{q}^{\mathbf{y}}(\mathbf{A})=\\{\mathbf{x}\in\mathbb{Z}^{m}:\mathbf{A}\cdot\mathbf{x}=\mathbf{y}\
(\mathrm{mod}\ q)\\},$

of the $q$-ary lattice
$\Lambda_{q}^{\bot}(\mathbf{A})=\\{\mathbf{x}\in\mathbb{Z}^{m}:\,\mathbf{A}\cdot\mathbf{x}=\mathbf{0}\
(\mathrm{mod}\ q)\\}$. Here, the _dual_ of $\Lambda_{q}^{\bot}(\mathbf{A})$
satisfies $q\cdot\Lambda_{q}^{\bot}(\mathbf{A})^{*}=\Lambda_{q}(\mathbf{A})$,
where $\Lambda_{q}(\mathbf{A})$ corresponds to the lattice generated by
$\mathbf{A}^{\intercal}$, i.e.

$\Lambda_{q}(\mathbf{A})=\\{\mathbf{z}\in\mathbb{Z}^{m}:\,\mathbf{z}=\mathbf{A}^{\intercal}\cdot\mathbf{s}\
(\mathrm{mod}\ q),\text{ for some }\mathbf{s}\in\mathbb{Z}^{n}\\}.$

The following lemma relates the Fourier transform of $\ket{\psi_{\mathbf{y}}}$
with a superposition of $\mathsf{LWE}$ samples with respect to a matrix
$\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$ and a phase which depends on
$\mathbf{y}$. In other words, the resulting state can be thought of as a
superposition of Gaussian balls around random lattice vectors in
$\Lambda_{q}(\mathbf{A})$.

######  Lemma 3.1 ([Por22], Lemma 16).

Let $m\in\mathbb{N}$, $q\geq 2$ be a prime and
$\sigma\in(\sqrt{2m},q/\sqrt{2m})$. Let $\mathbf{A}\in\mathbb{Z}_{q}^{n\times
m}$ be a matrix whose columns generate $\mathbb{Z}_{q}^{n}$ and let
$\mathbf{y}\in\mathbb{Z}_{q}^{n}$ be arbitrary. Then, the $q$-ary quantum
Fourier transform of the (normalized variant of the) Gaussian coset state

$\ket{\psi_{\mathbf{y}}}=\sum_{\begin{subarray}{c}\mathbf{x}\in\mathbb{Z}_{q}^{m}\\\
\mathbf{A}\mathbf{x}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\rho_{\sigma}(\mathbf{x})\ket{\mathbf{x}}$

is within negligible (in $m\in\mathbb{N}$) trace distance of the (normalized
variant of the) Gaussian state

$\ket{\hat{\psi}_{\mathbf{y}}}=\sum_{\mathbf{s}\in\mathbb{Z}_{q}^{n}}\sum_{\mathbf{e}\in\mathbb{Z}_{q}^{m}}\rho_{q/\sigma}(\mathbf{e})\,\omega_{q}^{-\langle\mathbf{s},\mathbf{y}\rangle}\ket{\mathbf{s}^{\intercal}\mathbf{A}+\mathbf{e}^{\intercal}\
(\mathrm{mod}\ q)}.$

The procedure
$\mathsf{QSampGauss}(\mathbf{A},\mathsf{td}_{\mathbf{A}},\mathbf{y},\sigma)$
is defined as follows.

Input: Matrix $\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$, a trapdoor
$\mathsf{td}_{\mathbf{A}}$, an image $\mathbf{y}\in\mathbb{Z}_{q}^{n}$ and
parameter $\sigma=O(\frac{q}{\sqrt{m}})$.

Output: Gaussian state $\ket{\psi_{\mathbf{y}}}$.

1

2Prepare the following superposition with parameter $q/\sigma>0$:
$\sum_{\mathbf{s}\in\mathbb{Z}_{q}^{n}}\ket{\mathbf{s}}\otimes\sum_{\mathbf{e}\in\mathbb{Z}_{q}^{m}}\rho_{q/\sigma}(\mathbf{e})\ket{\mathbf{e}}\otimes\ket{\mathbf{0}}$

3

4Apply the generalized Pauli operator $\mathbf{Z}_{q}^{-\mathbf{y}}$ on the
first register, resulting in the state
$\sum_{\mathbf{s}\in\mathbb{Z}_{q}^{n}}\omega_{q}^{-\langle\mathbf{s},\mathbf{y}\rangle}\ket{\mathbf{s}}\otimes\sum_{\mathbf{e}\in\mathbb{Z}_{q}^{m}}\rho_{q/\sigma}(\mathbf{e})\ket{\mathbf{e}}\otimes\ket{\mathbf{0}}$

5

6Apply the unitary
$U_{\mathbf{A}}:\ket{\mathbf{s}}\ket{\mathbf{e}}\ket{\mathbf{0}}\rightarrow\ket{\mathbf{s}}\ket{\mathbf{e}}\ket{\mathbf{s}^{\intercal}\mathbf{A}+\mathbf{e}^{\intercal}\
(\mathrm{mod}\ q)}$, resulting in the state
$\sum_{\mathbf{s}\in\mathbb{Z}_{q}^{n}}\sum_{\mathbf{e}\in\mathbb{Z}_{q}^{m}}\rho_{q/\sigma}(\mathbf{e})\,\omega_{q}^{-\langle\mathbf{s},\mathbf{y}\rangle}\ket{\mathbf{s}}\ket{\mathbf{e}}\ket{\mathbf{s}^{\intercal}\mathbf{A}+\mathbf{e}^{\intercal}\
(\mathrm{mod}\ q)}$

7 Coherently run
$\mathsf{Invert}(\mathbf{A},{\mathsf{td}_{\mathbf{A}}},\cdot)$ on the third
register in order to uncompute the first and the second register, resulting in
a state that is close in trace distance to the following state:
$\sum_{\mathbf{s}\in\mathbb{Z}_{q}^{n}}\sum_{\mathbf{e}\in\mathbb{Z}_{q}^{m}}\rho_{q/\sigma}(\mathbf{e})\,\omega_{q}^{-\langle\mathbf{s},\mathbf{y}\rangle}\ket{0}\ket{0}\ket{\mathbf{s}^{\intercal}\mathbf{A}+\mathbf{e}^{\intercal}\
(\mathrm{mod}\ q)}$

Discard the first two registers. Apply the (inverse) quantum Fourier transform
and output the resulting state.

Algorithm 2
$\mathsf{QSampGauss}(\mathbf{A},\mathsf{td}_{\mathbf{A}},\mathbf{y},\sigma)$

Let us now prove the correctness of Algorithm 2.

######  Theorem 3.2 (Quantum Discrete Gaussian Sampler).

Let $n\in\mathbb{N}$, $q$ be a prime with $m\geq 2n\log q$ and
$\sigma\in(\sqrt{2m},q/\sqrt{2m})$. Let
$(\mathbf{A},\mathsf{td}_{\mathbf{A}})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)$
be sampled as in Theorem 2.10 and let $\mathbf{y}\in\mathbb{Z}_{q}^{n}$ be
arbitrary. Then, with overwhelming probability,
$\mathsf{QSampGauss}(\mathbf{A},\mathsf{td}_{\mathbf{A}},\mathbf{y},\sigma)$
in Algorithm 2 outputs a state which is within negligible trace distance of
the (normalized variant of the) state,

$\ket{\psi_{\mathbf{y}}}=\sum_{\begin{subarray}{c}\mathbf{x}\in\mathbb{Z}_{q}^{m}\\\
\mathbf{A}\mathbf{x}=\mathbf{y}\ (\mathrm{mod}\
q)\end{subarray}}\rho_{\sigma}(\mathbf{x})\ket{\mathbf{x}}.$

###### Proof.

From Lemma 2.2 and Theorem 2.10, it follows that
$(\mathbf{A},\mathsf{td}_{\mathbf{A}})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)$
yields a matrix $\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$ be a matrix whose
columns generate $\mathbb{Z}_{q}^{n}$ with overwhelming probability. Moreover,
since $\sigma\in(\sqrt{2m},q/\sqrt{2m})$, the inversion procedure
$\mathsf{Invert}(\mathbf{A},{\mathsf{td}_{\mathbf{A}}},\cdot)$ from Theorem
2.10 in Step $4$ in Algorithm 2 succeeds with overwhelming probability at
generating the Gaussian state

$\ket{\hat{\psi}_{\mathbf{y}}}=\sum_{\mathbf{s}\in\mathbb{Z}_{q}^{n}}\sum_{\mathbf{e}\in\mathbb{Z}_{q}^{m}}\rho_{q/\sigma}(\mathbf{e})\,\omega_{q}^{-\langle\mathbf{s},\mathbf{y}\rangle}\ket{\mathbf{s}^{\intercal}\mathbf{A}+\mathbf{e}^{\intercal}\
(\mathrm{mod}\ q)}$

Applying the (inverse) quantum Fourier transform $\mathsf{FT}_{q}^{\dagger}$,
the claim then follows from Lemma 3.1. ∎

##  4 Quantum Goldreich-Levin Theorem for Large Fields

In this section, we give a proof of the first quantum Goldreich-Levin theorem
for large fields $\mathbb{Z}_{q}$.

###  4.1 Post-Quantum Reductions and Quantum Rewinding

We first review some recent work by Bitansky, Brakerski and Kalai [BBK22] that
enables us to convert a wide range of classical reductions into post-quantum
reductions (which allow for quantum auxiliary input) in a constructive manner.
We first review some basic terminology from [BBK22].

Let $\lambda\in\mathbb{N}$ be a parameter. A _non-interactive assumption_
$\mathsf{P}=(\mathsf{G},\mathsf{V},c)$ with respect to a set of polynomials
$d(\lambda),n(\lambda)$ and $m(\lambda)$ is characterized as follows:

  * •

The generator $\mathsf{G}$ takes as input $1^{\lambda}$ and
$r\in{\\{0,1\\}}^{d}$, and returns $x\in{\\{0,1\\}}^{n}$.

  * •

The verifier $\mathsf{V}$ takes as input $1^{\lambda}$ and
$(r,y)\in{\\{0,1\\}}^{d}\times{\\{0,1\\}}^{m}$, and returns a single bit
output.

  * •

$c(\lambda)$ is the threshold associated with the assumption.

Given a (possibly randomized) _solver_ , we characterize the _advantage_ in
solving an assumption $\mathsf{P}$ in terms of the absolute distance between
the solving probability (or, _value_) and the threshold $c$; for example, for
a _decision assumption_ $\mathsf{P}$ (with $m=1$) we characterize the value in
solving $\mathsf{P}$ in terms of $\frac{1}{2}+\varepsilon$, where the
threshold is given by $c(\lambda)=\frac{1}{2}$ and $\varepsilon>0$ is
corresponds to the _advantage_. We say that a reduction is _black-box_ if it
is oblivious to the representation and inner workings of the solver that is
being used. Moreover, we say that a reduction is _non-adaptive_ if all queries
to the solver are known ahead of time. We use the following theorem.

######  Theorem 4.1 ([BBK22], adapted from Theorem 7.1).

Let $\lambda\in\mathbb{N}$ be a parameter. Suppose there exists a classical
non-adaptive black-box reduction from solving a non-interactive assumption
$\mathsf{Q}$ to solving a non-interactive decision assumption $\mathsf{P}$
which has advantage $\varepsilon$ and runs in time $T$. Then, there exists a
quantum reduction from solving $\mathsf{Q}$ to quantumly solving $\mathsf{P}$
which runs in time $\mathrm{poly}(\lambda,T,1/\varepsilon)$ and has advantage
$\mathrm{poly}(1/\lambda,1/T,\varepsilon)$.

###  4.2 Goldreich-Levin Theorems for Large Fields

The following result is implicit in the work of Dodis et al. [DGT+10].

######  Theorem 4.2 (Classical Goldreich-Levin Theorem for Large Fields,
[DGT+10], Theorem 1).

Let $q$ be a prime and $m\in\mathbb{N}$. Let $\sigma\in(0,q/\sqrt{m})$ and let
$H=\\{\mathbf{x}\in\mathbb{Z}_{q}^{m}\,:\,\|\mathbf{x}\|\leq\sigma\sqrt{m}\\}$
be a subset of $\mathbb{Z}_{q}^{m}$. Let
$\mathsf{aux}:H\rightarrow{\\{0,1\\}}^{*}$ be any (possibly randomized)
auxiliary information. Suppose there exists a distinguisher $\mathcal{D}$
which runs in time $T(\mathcal{D})$ such that

$\displaystyle\vline\,\Pr\left[\mathcal{D}\big{(}\mathbf{r},\mathbf{x}^{\intercal}\mathbf{r},\mathsf{aux}(\mathbf{x})\big{)}=1\,:\,\begin{subarray}{c}\mathbf{r}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{m}\\\
\mathbf{x}\sim
D_{\mathbb{Z}_{q}^{m},\sigma}\end{subarray}\right]-\Pr\left[\mathcal{D}\big{(}\mathbf{r},u,\mathsf{aux}(\mathbf{x})\big{)}=1\,:\,\begin{subarray}{c}\mathbf{r}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{m},\,u\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}\\\
\mathbf{x}\sim
D_{\mathbb{Z}_{q}^{m},\sigma}\end{subarray}\right]\,\vline=\varepsilon.$

Then, there exists a (classical) non-adaptive black-box extractor
$\mathcal{E}$ whose running time is given by
$T(\mathcal{E})=T(\mathcal{D})\cdot\mathrm{poly}(m,\sigma,1/\varepsilon)$ and
succeeds with probability at least

$\Pr\Big{[}\mathcal{E}\big{(}\mathsf{aux}(\mathbf{x})\big{)}=\mathbf{x}\,\,:\,\,\mathbf{x}\sim
D_{\mathbb{Z}_{q}^{m},\sigma}\Big{]}\geq\Omega\left(\frac{\varepsilon^{3}}{m\cdot
q^{2}}\right).$

Using the constructive post-quantum reduction from Theorem 4.1, we can convert
Theorem 4.2 into a quantum Goldreich-Levin Theorem for finite fields, and
obtain the following.

######  Theorem 4.3 (Quantum Goldreich-Levin Theorem for Large Fields).

Let $q$ be a prime and $m\in\mathbb{N}$. Let $\sigma\in(0,q/\sqrt{m})$ and let
$\Phi:\mathcal{L}(\mathcal{H}_{q}^{m})\rightarrow\mathcal{L}(\mathcal{H}_{\textsc{Aux}})$
be any $\mathsf{CPTP}$ map with auxiliary system $\mathcal{H}_{\textsc{Aux}}$.
Suppose there exists a distinguisher $\mathcal{D}$ which runs in time
$T(\mathcal{D})$ such that

$\displaystyle\Bigg{|}\Pr\left[\mathcal{D}\big{(}\mathbf{r},\mathbf{x}^{\intercal}\mathbf{r},\mathsf{aux}(\mathbf{x})\big{)}=1\,:\,\begin{subarray}{c}\mathbf{r}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{m}\\\
\mathbf{x}\sim D_{\mathbb{Z}_{q}^{m},\sigma}\\\
\mathsf{aux}(\mathbf{x})\leftarrow\Phi(|\mathbf{x}\rangle\langle\mathbf{x}|)\end{subarray}\right]-\Pr\left[\mathcal{D}\big{(}\mathbf{r},u,\mathsf{aux}(\mathbf{x})\big{)}=1\,:\,\begin{subarray}{c}\mathbf{r}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{m},\,u\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}\\\
\mathbf{x}\sim D_{\mathbb{Z}_{q}^{m},\sigma}\\\
\mathsf{aux}(\mathbf{x})\leftarrow\Phi(|\mathbf{x}\rangle\langle\mathbf{x}|)\end{subarray}\right]\Bigg{|}=\varepsilon.$

Then, there exists a quantum extractor $\mathcal{E}$ that runs in time
$T(\mathcal{E})=\mathrm{poly}(m,T(\mathcal{D}),\sigma,q,1/\varepsilon)$ with

$\Pr\Big{[}\mathcal{E}\big{(}\mathsf{aux}(\mathbf{x})\big{)}=\mathbf{x}\,\,:\,\,\begin{subarray}{c}\mathbf{x}\sim
D_{\mathbb{Z}_{q}^{m},\sigma}\\\
\mathsf{aux}(\mathbf{x})\leftarrow\Phi(|\mathbf{x}\rangle\langle\mathbf{x}|)\end{subarray}\Big{]}\,\geq\,\mathrm{poly}\big{(}1/m,1/T(\mathcal{D}),1/\sigma,1/q,\varepsilon\big{)}.$

###### Proof.

The proof follows immediately by combining Theorem 4.2 and Theorem 4.1. ∎

##  5 Definition: Key-Revocable Public-Key Encryption

Let us now give a formal definition of key-revocable public-key encryption
schemes.

######  Definition 5.1 (Key-Revocable Public-Key Encryption).

A key-revocable public-key encryption scheme consists efficient algorithms
$\left(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec},\mathsf{Revoke}\right)$,
where $\mathsf{Enc}$ is a $\mathsf{PPT}$ algorithm and
$\mathsf{KeyGen},\mathsf{Dec}$ and $\mathsf{Revoke}$ are $\mathsf{QPT}$
algorithms defined as follows:

  * •

$\mathsf{KeyGen}(1^{\lambda})$: given as input a security parameter $\lambda$,
output a public key $\mathsf{PK}$, a master secret key $\mathsf{MSK}$ and a
quantum decryption key $\rho_{\mathsf{SK}}$.

  * •

$\mathsf{Enc}(\mathsf{PK},x)$: given a public key $\mathsf{PK}$ and plaintext
$x\in\\{0,1\\}^{\ell}$, output a ciphertext $\mathsf{CT}$.

  * •

$\mathsf{Dec}(\rho_{\mathsf{SK}},\mathsf{CT})$: given a decryption key
$\rho_{\mathsf{SK}}$ and ciphertext $\mathsf{CT}$, output a message $y$.

  * •

$\mathsf{Revoke}\left(\mathsf{PK},\mathsf{MSK},\sigma\right)$: given as input
a master secret key $\mathsf{MSK}$, a public key $\mathsf{PK}$ and quantum
state $\sigma$, output $\mathsf{Valid}$ or $\mathsf{Invalid}$.

##### Correctness of Decryption.

For every $x\in\\{0,1\\}^{\ell}$, the following holds:

${\sf Pr}\left[x\leftarrow\mathsf{Dec}(\rho_{\mathsf{SK}},\mathsf{CT})\ :\
\begin{subarray}{c}(\mathsf{PK},\mathsf{MSK},\rho_{\mathsf{SK}})\leftarrow\mathsf{KeyGen}(1^{\lambda})\\\
\ \\\
\mathsf{CT}\leftarrow\mathsf{Enc}(\mathsf{PK},x)\end{subarray}\right]\geq
1-\nu(\lambda),$

where $\nu(\cdot)$ is a negligible function.

##### Correctness of Revocation.

The following holds:

${\sf
Pr}\left[\mathsf{Valid}\leftarrow\mathsf{Revoke}\left(\mathsf{PK},\mathsf{MSK},\rho_{\mathsf{SK}}\right)\
:\
(\mathsf{PK},\mathsf{MSK},\rho_{\mathsf{SK}})\leftarrow\mathsf{KeyGen}(1^{\lambda})\right]\geq
1-\nu(\lambda),$

where $\nu(\cdot)$ is a negligible function.

######  Remark 5.2.

Using the well-known “Almost As Good As New Lemma” [Aar16], the procedure
$\mathsf{Dec}$ can be purified to obtain another quantum circuit
$\widetilde{\mathsf{Dec}}$ such that
$\widetilde{\mathsf{Dec}}(\rho_{\mathsf{SK}},\mathsf{CT})$ yields
$(x,\rho_{\mathsf{SK}}^{\prime})$ with probability at least $1-\nu(\lambda)$
and moreover, $\mathsf{CT}$ is an encryption of $x$ and
$\operatorname{TD}(\rho_{\mathsf{SK}}^{\prime},\rho_{\mathsf{SK}})\leq\nu^{\prime}(\lambda)$
with $\nu^{\prime}(\lambda)$ is another negligible function.

###  5.1 Security Definition

Let
$\Sigma=\left(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec},\mathsf{Revoke}\right)$
be a key-revocable public-key encryption scheme. We consider the following
security experiment, defined below.

$\mathsf{Expt}_{\Sigma}^{\mathcal{A}}\left(1^{\lambda},b\right)$:
Initialization Phase: • The challenger runs
$(\mathsf{PK},\mathsf{MSK},\rho_{\mathsf{SK}})\leftarrow\mathsf{KeyGen}(1^{\lambda})$
and sends $(\mathsf{PK},\rho_{\mathsf{SK}})$ to $\mathcal{A}$. Revocation
Phase: • The challenger sends the message REVOKE to $\mathcal{A}$. • The
adversary $\mathcal{A}$ returns a state $\sigma$. • The challenger aborts if
$\mathsf{Revoke}(\mathsf{PK},\mathsf{MSK},\sigma)$ outputs $\mathsf{Invalid}$.
Guessing Phase: • $\mathcal{A}$ submits a plaintext $x\in\\{0,1\\}^{\ell}$ to
the challenger. • If $b=0$: The challenger sends
$\mathsf{CT}\leftarrow\mathsf{Enc}(\mathsf{PK},x)$ to $\mathcal{A}$. Else, if
$b=1$, the challenger sends $\mathsf{CT}\xleftarrow{\$}{\mathcal{C}}$, where
${\mathcal{C}}$ is the ciphertext space of $\ell$ bit messages. • Output
$b_{\mathcal{A}}$ if the output of $\mathcal{A}$ is $b_{\mathcal{A}}$.
---
Figure 1: Security Experiment

######  Definition 5.3.

A key-revocable public-key encryption scheme
$\Sigma=\left(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec},\mathsf{Revoke}\right)$
is secure if, for every $\mathsf{QPT}$ adversary $\mathcal{A}$, the following
holds:

$\Pr\left[b\leftarrow\mathsf{Expt}_{\Sigma}^{\mathcal{A}}(1^{\lambda},b)\ :\
b\xleftarrow{\$}\\{0,1\\}\right]\leq\frac{1}{2}+\mathsf{negl}(\lambda),$

where $\mathsf{Expt}_{\Sigma}^{\mathcal{A}}(1^{\lambda},b)$ is as defined in
Figure 1.

######  Remark 5.4.

In the traditional setting, 1-bit unpredictability and computational
indistinguishability are equivalent in the following sense: if there are two
distributions $D_{0}$ and $D_{1}$ such that an efficient adversary can
distinguish these two distributions with advantage $\epsilon$ then the same
adversary can predict $D_{0}$ versus $D_{1}$ with probability
$\frac{1}{2}+\frac{\epsilon}{2}$.

This observation no longer applies to the above setting where we
simultaneously need to consider the success probability of $\mathsf{Revoke}$.
As a result, our definition is incomparable with a variant of the above
definition where we instead require the adversary to distinguish a valid
ciphertext versus uniform.

##### Hybrid Lemma.

We present a hybrid lemma for 1-bit unpredictability below. This lemma will be
useful in applications where we can employ hybrid argument in a similar vein
as done in the computational indistinguishability setting.

######  Lemma 5.5 (Hybrid Lemma for $1$-Bit Unpredictability).

Suppose there exists a sequence of hybrid experiments
$\mathsf{H}_{1},\dots,\mathsf{H}_{k}$ such that any $\mathsf{QPT}$ predictor
$\mathcal{A}$ can predict $\mathsf{H}_{i}$ versus $\mathsf{H}_{i+1}$ with
advantage at most $\epsilon_{i}$. Then, $\mathcal{A}$ can only predict hybrid
$\mathsf{H}_{1}$ versus $\mathsf{H}_{k}$ with advantage of at most
$\sum_{i=1}^{k-1}\epsilon_{i}$.

###### Proof.

Let $\mathcal{A}$ be a $\mathsf{QPT}$ adversary and suppose that for
$i\in[k-1]$:

$\frac{1}{2}{\sf Pr}[0\leftarrow\mathsf{H}_{i}^{\mathcal{A}}]+\frac{1}{2}{\sf
Pr}[1\leftarrow\mathsf{H}_{i+1}^{\mathcal{A}}]=\frac{1}{2}+\epsilon_{i}.$

We give a proof by induction. First, note that the base case for $k=2$ follows
immediately by the definition of $\epsilon_{1}$. Now fix an arbitrary $k\geq
2$, and suppose that $\mathcal{A}$ can predict hybrid $\mathsf{H}_{1}$ versus
$\mathsf{H}_{k}$ with advantage at most $\sum_{i=1}^{k-1}\epsilon_{i}$. In
other words, by the induction hypothesis we have

$\frac{1}{2}{\sf Pr}[0\leftarrow\mathsf{H}_{1}^{\mathcal{A}}]+\frac{1}{2}{\sf
Pr}[1\leftarrow\mathsf{H}_{k}^{\mathcal{A}}]=\frac{1}{2}+\sum_{i=1}^{k-1}\epsilon_{i}.$

Suppose also that

$\frac{1}{2}{\sf Pr}[0\leftarrow\mathsf{H}_{k}^{\mathcal{A}}]+\frac{1}{2}{\sf
Pr}[1\leftarrow\mathsf{H}_{k+1}^{\mathcal{A}}]=\frac{1}{2}+\epsilon_{k}.$

By taking the sum of the two equations above, we get

$\displaystyle\frac{1}{2}{\sf
Pr}[0\leftarrow\mathsf{H}_{1}^{\mathcal{A}}]+\frac{1}{2}{\sf
Pr}[1\leftarrow\mathsf{H}_{k}^{\mathcal{A}}]+\frac{1}{2}{\sf
Pr}[0\leftarrow\mathsf{H}_{k}^{\mathcal{A}}]+\frac{1}{2}{\sf
Pr}[1\leftarrow\mathsf{H}_{k+1}^{\mathcal{A}}]=1+\sum_{i=1}^{k}\epsilon_{i}.$

Using the identity ${\sf Pr}[0\leftarrow\mathsf{H}_{k}^{\mathcal{A}}]+{\sf
Pr}[1\leftarrow\mathsf{H}_{k}^{\mathcal{A}}]=1$, we obtain the desired
identity for $k+1$:

$\frac{1}{2}{\sf Pr}[0\leftarrow\mathsf{H}_{1}^{\mathcal{A}}]+\frac{1}{2}{\sf
Pr}[1\leftarrow\mathsf{H}_{k+1}^{\mathcal{A}}]=\frac{1}{2}+\sum_{i=1}^{k}\epsilon_{i}.$

This proves the claim. ∎

###  5.2 Key-Revocable Public-Key Fully Homomorphic Encryption

A key-revocable public-key fully homomorphic encryption scheme defined for a
class of functions ${\mathcal{F}}$, in addition to
$(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec},\mathsf{Revoke})$, consists of the
following PPT algorithm:

  * •

${\sf Eval}(\mathsf{PK},f,\mathsf{CT})$: on input a public key $\mathsf{PK}$,
function $f\in{\mathcal{F}}$, ciphertext $\mathsf{CT}$, outputs another
ciphertext $\mathsf{CT}^{\prime}$.

######  Remark 5.6.

Sometimes we allow $\mathsf{KeyGen}$ to additionally take as input different
parameters associated with the implementations of the functions in
${\mathcal{F}}$. For example, we allow $\mathsf{KeyGen}$ to take as input a
parameter $L$ in such a way that all the parameters in the system depend on
$L$ and moreover, the homomorphic evaluation is only supported on circuits (in
${\mathcal{F}}$) of depth at most $L$.

##### Correctness of Evaluation and Decryption.

For every $f\in{\mathcal{F}}$ with $\ell$-bit inputs, every
$x\in\\{0,1\\}^{\ell}$, the following holds:

${\sf
Pr}\left[f(x)\leftarrow\mathsf{Dec}(\rho_{\mathsf{SK}},\mathsf{CT}^{\prime})\
:\
\begin{subarray}{c}(\mathsf{PK},\mathsf{MSK},\rho_{\mathsf{SK}})\leftarrow\mathsf{KeyGen}(1^{\lambda})\\\
\ \\\ \mathsf{CT}\leftarrow\mathsf{Enc}(\mathsf{PK},x)\\\ \ \\\
\mathsf{CT}^{\prime}\leftarrow{\sf
Eval}(\mathsf{PK},f,\mathsf{CT})\end{subarray}\right]\geq 1-\nu(\lambda),$

where $\nu(\cdot)$ is a negligible function.

##### Correctness of Revocation.

Defined as before.

##### Security.

Defined as before (Definition 5.3).

###  5.3 From Single-Bit to Multi-Bit Security

Consider the following transformation from a single-bit key-revocable public-
key encryption scheme to a multi-bit scheme. While such a transformation was
known for indistinguishability-based encryption schemes, we show that the same
transformation also works in the 1-bit unpredictability setting.

######  Construction 1 (Single-Bit to Multi-Bit Transformation).

Let
$\Sigma=\left(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec},\mathsf{Revoke}\right)$
be a single-bit key-revocable public-key encryption scheme. Then, for
$k\in\mathbb{N}$, we define the corresponding multi-bit transformation
$\Sigma^{k}=\left(\mathsf{KeyGen}^{k},\mathsf{Enc}^{k},\mathsf{Dec}^{k},\mathsf{Revoke}^{k}\right)$
as follows:

  * •

$\mathsf{KeyGen}^{k}(1^{\lambda})$: given as input a security parameter
$\lambda$, run $\mathsf{KeyGen}(1^{\lambda})$ to output a public key
$\mathsf{PK}$, a master secret key $\mathsf{MSK}$ and a quantum decryption key
$\rho_{\mathsf{SK}}$.

  * •

$\mathsf{Enc}^{k}(\mathsf{PK},x)$: given a public key $\mathsf{PK}$ and
plaintext $x\in\\{0,1\\}^{k}$, output the ciphertext

$\mathsf{CT}=\left(\mathsf{Enc}(\mathsf{PK},x_{1}),\dots,\mathsf{Enc}(\mathsf{PK},x_{k})\right).$

  * •

$\mathsf{Dec}^{k}(\rho_{\mathsf{SK}},\mathsf{CT})$: given a decryption key
$\rho_{\mathsf{SK}}$ and a ciphertext
$\mathsf{CT}=\mathsf{CT}_{1},\dots,\mathsf{CT}_{k}$, decrypt each of the
ciphertexts separately by running the purified variant141414See Remark 5.2. of
$\mathsf{Dec}$ and re-using the key.

  * •

$\mathsf{Revoke}^{k}\left(\mathsf{PK},\mathsf{MSK},\sigma\right)$: given as
input a master secret key $\mathsf{MSK}$, a public key $\mathsf{PK}$ and
quantum state $\sigma$, run
$\mathsf{Revoke}\left(\mathsf{PK},\mathsf{MSK},\sigma\right)$ to output
$\mathsf{Valid}$ or $\mathsf{Invalid}$.

The following claim follows immediately from the “Almost As Good As New Lemma”
[Aar16] mentioned in Remark 5.2.

######  Claim 5.7.

Let $\lambda\in\mathbb{N}$ be the security parameter. If
$\Sigma=\left(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec},\mathsf{Revoke}\right)$
satisfies correctness of decryption and revocation, then so does $\Sigma^{k}$
in 1 for any $k=\mathrm{poly}(\lambda)$.

Finally, we show the following.

######  Claim 5.8.

Let $\lambda\in\mathbb{N}$ be the security parameter. If
$\Sigma=\left(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec},\mathsf{Revoke}\right)$
is a secure key-revocable public-key encryption scheme, then so is
$\Sigma^{k}$ in 1 for any $k=\mathrm{poly}(\lambda)$.

###### Proof.

Let $\lambda\in\mathbb{N}$ and $k=\mathrm{poly}(\lambda)$. Let $\mathcal{A}$
be a $\mathsf{QPT}$ adversary and suppose that

$\Pr\left[b\leftarrow\mathsf{Expt}_{\Sigma^{k}}^{\mathcal{A}}(1^{\lambda},b)\
:\ b\xleftarrow{\$}\\{0,1\\}\right]=\frac{1}{2}+\epsilon(\lambda),$

for some $\varepsilon(\lambda)$ with respect to
$\mathsf{Expt}_{\Sigma^{k}}^{\mathcal{A}}(1^{\lambda},b)$ in Figure 1. We show
that $\varepsilon(\lambda)$ is negligible.

For $i\in[k]$, we now consider the following sequence of intermediate hybrid
experiments $\mathsf{H}_{i}^{\mathcal{A}}$ defined in Figure 2, where
$\mathsf{H}_{1}=\mathsf{Expt}_{\Sigma^{k}}^{\mathcal{A}}(1^{\lambda},0)$ and
$\mathsf{H}_{k}=\mathsf{Expt}_{\Sigma^{k}}^{\mathcal{A}}(1^{\lambda},1)$.
Because the single-bit scheme $\Sigma$ is secure, there exist negligible
functions $\epsilon_{i}(\lambda)$ such that for each $i\in[k-1]$,

$\frac{1}{2}{\sf
Pr}[0\leftarrow\mathsf{H}_{i}^{\mathcal{A}}(1^{\lambda})]+\frac{1}{2}{\sf
Pr}[1\leftarrow\mathsf{H}_{i+1}^{\mathcal{A}}(1^{\lambda})]=\frac{1}{2}+\epsilon_{i}(\lambda).$

Using Lemma 5.5, we get that
$\epsilon(\lambda)\leq\sum_{i=1}^{k-1}\epsilon_{i}(\lambda)\leq\mathsf{negl}(\lambda)$.
This proves the claim.

$\mathsf{H}_{i}^{\mathcal{A}}\left(1^{\lambda}\right)$: Initialization Phase:
• The challenger runs
$(\mathsf{PK},\mathsf{MSK},\rho_{\mathsf{SK}})\leftarrow\mathsf{KeyGen}^{k}(1^{\lambda})$
and sends $(\mathsf{PK},\rho_{\mathsf{SK}})$ to $\mathcal{A}$. Revocation
Phase: • The challenger sends the message REVOKE to $\mathcal{A}$. • The
adversary $\mathcal{A}$ returns a state $\sigma$. • The challenger aborts if
$\mathsf{Revoke}^{k}(\mathsf{PK},\mathsf{MSK},\sigma)$ outputs
$\mathsf{Invalid}$. Guessing Phase: • $\mathcal{A}$ submits a plaintext
$x\in\\{0,1\\}^{k}$ to the challenger. • The challenger samples
$C_{1},\dots,C_{i-1}\xleftarrow{\$}{\mathcal{C}}$, where ${\mathcal{C}}$ is
the space of all ciphertexts of single-bit messages, and sends the following
to $\mathcal{A}$: CT= (C_1,C_2,…, C_i-1,Enc(PK,x_i),…Enc(PK,x_k)).  • Output
$b_{\mathcal{A}}$ if the output of $\mathcal{A}$ is $b_{\mathcal{A}}$.
---
Figure 2: The hybrid experiment
$\mathsf{H}_{i}^{\mathcal{A}}\left(1^{\lambda}\right)$.

∎

##  6 Key-Revocable Dual-Regev Encryption

In this section, we present the first construction of key-revocable public-key
encryption from standard assumptions. Our construction involves making the
Dual Regev public-key encryption of Gentry, Peikert and Vaikuntanathan [GPV07]
key revocable.

###  6.1 Construction

We define our Dual-Regev construction below.

######  Construction 2 (Key-Revocable Dual-Regev Encryption).

Let $n\in\mathbb{N}$ be the security parameter and $m\in\mathbb{N}$. Let
$q\geq 2$ be a prime and let $\alpha,\beta,\sigma>0$ be parameters. The key-
revocable public-key scheme
$\mathsf{RevDual}=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec},\mathsf{Revoke})$
consists of the following $\mathsf{QPT}$ algorithms:

  * •

$\mathsf{KeyGen}(1^{\lambda})\rightarrow(\mathsf{PK},\rho_{\mathsf{SK}},\mathsf{MSK}):$
sample $(\mathbf{A}\in\mathbb{Z}_{q}^{n\times
m},\mathsf{td}_{\mathbf{A}})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)$ and
generate a Gaussian superposition
$(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)$
with

$\ket{\psi_{\mathbf{y}}}\,\,=\sum_{\begin{subarray}{c}\mathbf{x}\in\mathbb{Z}_{q}^{m}\\\
\mathbf{A}\mathbf{x}=\mathbf{y}\end{subarray}}\rho_{\sigma}(\mathbf{x})\,\ket{\mathbf{x}},$

for some $\mathbf{y}\in\mathbb{Z}_{q}^{n}$. Output
$\mathsf{PK}=(\mathbf{A},\mathbf{y})$,
$\rho_{\mathsf{SK}}=\ket{\psi_{\mathbf{y}}}$ and
$\mathsf{MSK}=\mathsf{td}_{\mathbf{A}}$.

  * •

$\mathsf{Enc}(\mathsf{PK},\mu)\rightarrow\mathsf{CT}:$ to encrypt a bit
$\mu\in{\\{0,1\\}}$, sample a random vector
$\mathbf{s}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n}$
and errors $\mathbf{e}\sim D_{\mathbb{Z}^{m},\,\alpha q}$ and $e^{\prime}\sim
D_{\mathbb{Z},\,\beta q}$, and output the ciphertext pair

$\mathsf{CT}=\left(\mathbf{s}^{\intercal}\mathbf{A}+\mathbf{e}^{\intercal}\
(\mathrm{mod}\
q),\mathbf{s}^{\intercal}\mathbf{y}+e^{\prime}+\mu\cdot\lfloor\frac{q}{2}\rfloor\
(\mathrm{mod}\ q)\right)\in\mathbb{Z}_{q}^{m}\times\mathbb{Z}_{q}.$

  * •

$\mathsf{Dec}(\rho_{\mathsf{SK}},\mathsf{CT})\rightarrow{\\{0,1\\}}:$ to
decrypt $\mathsf{CT}$, apply the unitary
$U:\ket{\mathbf{x}}\ket{0}\rightarrow\ket{\mathbf{x}}\ket{\mathsf{CT}\cdot(-\mathbf{x},1)^{\intercal}}$
on input $\ket{\psi_{\mathbf{y}}}\ket{0}$, where
$\rho_{\mathsf{SK}}=\ket{\psi_{\mathbf{y}}}$, and measure the second register
in the computational basis. Output $0$, if the measurement outcome is closer
to $0$ than to $\lfloor\frac{q}{2}\rfloor$, and output $1$, otherwise.

  * •

$\mathsf{Revoke}(\mathsf{MSK},\mathsf{PK},\rho)\rightarrow\\{\top,\bot\\}$: on
input $\mathsf{td}_{\mathbf{A}}\leftarrow\mathsf{MSK}$ and
$(\mathbf{A},\mathbf{y})\leftarrow\mathsf{PK}$, apply the measurement
$\\{\ket{\psi_{\mathbf{y}}}\\!\bra{\psi_{\mathbf{y}}},I-\ket{\psi_{\mathbf{y}}}\\!\bra{\psi_{\mathbf{y}}}\\}$
onto the state $\rho$ using the procedure
$\mathsf{QSampGauss}(\mathbf{A},\mathsf{td}_{\mathbf{A}},\mathbf{y},\sigma)$
in Algorithm 2. Output $\top$, if the measurement is successful, and output
$\bot$ otherwise.

##### Correctness of Decryption.

Follows from the correctness of Dual-Regev public-key encryption.

##### Correctness of Revocation.

Follows from Theorem 3.2.

Let us now prove the security of our key-revocable Dual-Regev construction.

######  Theorem 6.1.

Let $n\in\mathbb{N}$ and $q$ be a prime modulus with $q=2^{o(n)}$ and $m\geq
2n\log q$, each parameterized by the security parameter
$\lambda\in\mathbb{N}$. Let $\sigma\in(\sqrt{2m},q/\sqrt{2m})$ and let
$\alpha,\beta\in(0,1)$ be noise ratios chosen such that
$\beta/\alpha=2^{o(n)}$ and $1/\alpha=2^{o(n)}\cdot\sigma$. Then, assuming the
subexponential hardness of the $\mathsf{LWE}_{n,q,\alpha q}^{m}$ and
$\mathsf{SIS}_{n,q,\sigma\sqrt{2m}}^{m}$ problems, the scheme
$\mathsf{RevDual}=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec},\mathsf{Revoke})$
in 2 is a secure key-revocable public-key encryption scheme according to
Definition 5.3.

######  Remark 6.2.

Note that our construction only handles 1-bit messages. However, we can apply
the transformation in Definition 5.3 to obtain a key-revocable public-key
encryption scheme for multi-bit messages.

##### Guide for proving Theorem 6.1.

  * •

The first step towards proving Theorem 6.1 is the simultaneous search-to-
decision reduction (Section 6.2). Here, we show how to extract a short vector
mapping $\mathbf{A}$ to $\mathbf{y}$ from an efficient adversary who has a
non-negligible advantage in Definition 5.3.

  * •

Next, we exploit the search-to-reduction to extract two distinct short vectors
mapping $\mathbf{A}$ to $\mathbf{y}$. This is proven in Section 6.3.

  * •

Finally, we put all the pieces together in Section 6.4 and show how to use the
result in Section 6.3 to break the SIS assumption.

###  6.2 Simultaneous Search-to-Decision Reduction with Quantum Auxiliary
Input

In this section, we prove our main technical theorem.

######  Theorem 6.3 (Simultaneous Search-to-Decision Reduction with Quantum
Auxiliary Input).

Let $n\in\mathbb{N}$ and $q$ be a prime modulus with $q=2^{o(n)}$ and let
$m\geq 2n\log q$, each parameterized by the security parameter
$\lambda\in\mathbb{N}$. Let $\sigma\in(\sqrt{2m},q/\sqrt{2m})$ and let
$\alpha,\beta\in(0,1)$ be noise ratios with $\beta/\alpha=2^{o(n)}$ and
$1/\alpha=2^{o(n)}\cdot\sigma$. Let
$\mathcal{A}=\\{(\mathcal{A}_{\lambda,\mathbf{A}},\nu_{\lambda})\\}_{\lambda\in\mathbb{N}}$
be any non-uniform quantum algorithm consisting of a family of polynomial-
sized quantum circuits

$\Bigg{\\{}\mathcal{A}_{\lambda,\mathbf{A}}:\mathcal{L}(\mathcal{H}_{q}^{m}\otimes\mathcal{H}_{B_{\lambda}})\allowbreak\rightarrow\mathcal{L}(\mathcal{H}_{R_{\lambda}}\otimes\mathcal{H}_{\textsc{aux}_{\lambda}})\Bigg{\\}}_{\mathbf{A}\in\mathbb{Z}_{q}^{n\times
m}}$

and a family of polynomial-sized advice states
$\nu_{\lambda}\in\mathcal{D}(\mathcal{H}_{B_{\lambda}})$ which are independent
of $\mathbf{A}$. Then, assuming the quantum hardness of
$\mathsf{LWE}_{n,q,\alpha q}^{m}$, the following holds for every
$\mathsf{QPT}$ predictor $\mathcal{D}$: Suppose there exists
$\varepsilon(\lambda)=1/\mathrm{poly}(\lambda)$ such that for
$\mathsf{SearchToDecisionExpt}^{\mathcal{A},\mathcal{D}}(1^{\lambda},b)$ in
Figure 5:

$\displaystyle{\sf
Pr}\left[b\leftarrow\mathsf{SearchToDecisionExpt}^{\mathcal{A},\mathcal{D}}(1^{\lambda},b)\,:\,b\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}{\\{0,1\\}}\right]=\frac{1}{2}+\varepsilon(\lambda).$

Then, there exists a quantum extractor $\mathcal{E}$ that takes as input
$\mathbf{A}$, $\mathbf{y}$ and system Aux of the state
$\rho_{R,\mathbf{\textsc{Aux}}}$ and outputs a short vector in the coset
$\Lambda_{q}^{\mathbf{y}}(\mathbf{A})$ in time
$\mathrm{poly}(\lambda,m,\sigma,q,1/\varepsilon)$ such that

$\displaystyle\Pr\left[\begin{subarray}{c}\left(\mathsf{Revoke}(\mathbf{A},\mathsf{td}_{\mathbf{A}},\mathbf{y},\cdot)\otimes\mathcal{E}(\mathbf{A},\mathbf{y},\cdot)\right)(\rho_{R,\mathbf{\textsc{Aux}}})=(\top,\mathbf{x})\vspace{1mm}\\\
\bigwedge\vspace{0.1mm}\\\
{\mathbf{x}}\,\,\in\,\,\Lambda_{q}^{\mathbf{y}}(\mathbf{A})\,\cap\,\mathcal{B}^{m}(\mathbf{0},\sigma\sqrt{\frac{m}{2}})\end{subarray}\,:\,\begin{subarray}{c}(\mathbf{A},\mathsf{td}_{\mathbf{A}})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)\\\
(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)\\\
\rho_{R,\mathbf{\textsc{Aux}}}\leftarrow\mathcal{A}_{\lambda,\mathbf{A}}(|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\otimes\nu_{\lambda})\end{subarray}\right]\geq\mathrm{poly}\big{(}1/\lambda,1/m,1/\sigma,1/q,\varepsilon\big{)}.$

${\sf lwe}.{\sf Dist}^{\mathcal{A},\mathcal{D}}\left(1^{\lambda}\right)$: 1.
Sample
$(\mathbf{A},\mathsf{td}_{\mathbf{A}})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)$.
2. Generate
$(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)$.
3. Generate
$\rho_{R,\,\mathbf{\textsc{Aux}}}\leftarrow\mathcal{A}_{\lambda,\mathbf{A}}(|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\otimes\nu_{\lambda})$.
4. Sample
$\mathbf{s}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n},\mathbf{e}\sim
D_{\mathbb{Z}^{m},\alpha q}$ and $e^{\prime}\sim D_{\mathbb{Z},\beta q}$. 5.
Generate
$\rho_{R,\mathbf{\textsc{Aux}}}\leftarrow\mathcal{A}_{\lambda,\mathbf{A}}(|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\otimes\nu_{\lambda})$.
6. Run $\mathsf{Revoke}(\mathbf{A},\mathsf{td}_{\mathbf{A}},\mathbf{y},\cdot)$
on system $R$. If it outputs $\top$, continue. Otherwise, output
$\mathsf{Invalid}$. 7. Run
$b^{\prime}\leftarrow\mathcal{D}(\mathbf{A},\mathbf{y},\mathbf{s}^{\intercal}\mathbf{A}+\mathbf{e}^{\intercal},\mathbf{s}^{\intercal}\mathbf{y}+e^{\prime},\cdot)$
on system Aux. Output $b^{\prime}$.
---
Figure 3: The distribution ${\sf lwe}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}\left(1^{\lambda}\right)$. ${\sf unif}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}\left(1^{\lambda}\right)$: 1. Sample
$(\mathbf{A},\mathsf{td}_{\mathbf{A}})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)$.
2. Generate
$(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)$.
3. Generate
$\rho_{R,\mathbf{\textsc{Aux}}}\leftarrow\mathcal{A}_{\lambda,\mathbf{A}}(|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\otimes\nu_{\lambda})$.
4. Sample
$\mathbf{u}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{m}$
and
$r\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}$.
5. Run $\mathsf{Revoke}(\mathbf{A},\mathsf{td}_{\mathbf{A}},\mathbf{y},\cdot)$
on system $R$. If it outputs $\top$, continue. Otherwise, output
$\mathsf{Invalid}$. 6. Run
$b^{\prime}\leftarrow\mathcal{D}(\mathbf{A},\mathbf{y},\mathbf{u},r,\cdot)$ on
system Aux. Output $b^{\prime}$.
---
Figure 4: The distribution ${\sf unif}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}\left(1^{\lambda}\right)$.
$\mathsf{SearchToDecisionExpt}^{\mathcal{A},\mathcal{D}}\left(1^{\lambda},b\right)$:
• If $b=0$: output ${\sf lwe}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}\left(1^{\lambda}\right)$ defined in Figure 3.
• If $b=1$: output ${\sf unif}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}\left(1^{\lambda}\right)$ defined in Figure 4.
---
Figure 5: The experiment
$\mathsf{SearchToDecisionExpt}^{\mathcal{A},\mathcal{D}}\left(1^{\lambda},b\right)$.

###### Proof.

Let
$\mathcal{A}=\\{(\mathcal{A}_{\lambda,\mathbf{A}},\nu_{\lambda})\\}_{\lambda\in\mathbb{N}}$
be a non-uniform quantum algorithm and let $\mathcal{D}$ be any $\mathsf{QPT}$
distinguisher. Let ${\sf lwe}.{\sf Dist}^{\mathcal{A},\mathcal{D}}$ and ${\sf
unif}.{\sf Dist}^{\mathcal{A},\mathcal{D}}$ be the two distributions from
Figure 3 and Figure 4, respectively. By assumption, we have that there exists
a function $\varepsilon(\lambda)=1/\mathrm{poly}(\lambda)$ such that

$\displaystyle{\sf
Pr}\left[b\leftarrow\mathsf{SearchToDecisionExpt}^{\mathcal{A},\mathcal{D}}(1^{\lambda},b)\,:\,b\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}{\\{0,1\\}}\right]$
$\displaystyle=\frac{1}{2}{\sf Pr}[0\leftarrow{\sf lwe}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]+\frac{1}{2}{\sf
Pr}[1\leftarrow{\sf unif}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]\,=\,\frac{1}{2}+\varepsilon(\lambda).$

We define the following procedure.

$\mathsf{WeakRevoke}(\mathbf{A},\mathbf{y},\rho)$: Input:
$\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$ and
$\mathbf{y}\in\mathbb{Z}_{q}^{n}$ and $\rho\in L(\mathcal{H}_{R})$.
---
Output: A vector $\mathbf{x}_{0}\in\mathbb{Z}_{q}^{m}$ or $\bot$.
Procedure: 1. Measure $\rho$ in the computational basis with outcome
$\mathbf{x}_{0}$. 2. If
$\mathbf{x}_{0}\in\Lambda_{q}^{\mathbf{y}}(\mathbf{A})\cap\mathcal{B}^{m}(\mathbf{0},\sigma\sqrt{\frac{m}{2}})$,
output $\mathbf{x}_{0}$. Else, output $\bot$.
Figure 6: The procedure $\mathsf{WeakRevoke}(\mathbf{A},\mathbf{y},\rho)$.

Consider ${\sf hyb}_{0}.{\sf Dist}$ defined in Figure 7 and suppose that the
following holds:

$\displaystyle\frac{1}{2}{\sf Pr}[0\leftarrow{\sf lwe}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]+\frac{1}{2}{\sf
Pr}[1\leftarrow{\sf hyb}_{0}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]$
$\displaystyle=\frac{1}{2}+\delta_{1}(\lambda),\,\,\,\text{ and }$
$\displaystyle\frac{1}{2}{\sf Pr}[1\leftarrow{\sf unif}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]+\frac{1}{2}{\sf
Pr}[0\leftarrow{\sf hyb}_{0}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]$
$\displaystyle=\frac{1}{2}+\delta_{2}(\lambda)$

for some functions $\delta_{1}(\lambda)$ and $\delta_{2}(\lambda)$.

${\sf hyb}_{0}.{\sf Dist}^{\mathcal{A},\mathcal{D}}\left(1^{\lambda}\right)$:
1. Sample
$(\mathbf{A},\mathsf{td}_{\mathbf{A}})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)$.
2. Sample
$\mathbf{u}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{m}$
and $e^{\prime}\sim D_{\mathbb{Z},\beta q}$. 3. Run
$(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)$.
4. Generate
$\rho_{R,\mathbf{\textsc{Aux}}}\leftarrow\mathcal{A}_{\lambda,\mathbf{A}}(|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\otimes\nu_{\lambda})$.
5. Run $\mathsf{Revoke}(\mathbf{A},\mathsf{td}_{\mathbf{A}},\mathbf{y},\cdot)$
on system $R$. If it outputs $\top$, continue. Otherwise, output
$\mathsf{Invalid}$. 6. Run $\mathsf{WeakRevoke}(\mathbf{A},\mathbf{y},\cdot)$
on system $R$. If it outputs a short vector
$\mathbf{x}_{0}\in\mathbb{Z}_{q}^{m}$, continue. Otherwise, output
$\mathsf{Invalid}$. 7. Run
$b^{\prime}\leftarrow\mathcal{D}(\mathbf{A},\mathbf{y},\mathbf{u},\mathbf{u}^{\intercal}\mathbf{x}_{0}+e^{\prime},\cdot)$
on system Aux. Output $b^{\prime}$.
---
Figure 7: The distribution ${\sf hyb}_{0}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}\left(1^{\lambda}\right)$.

We claim that one of the following must hold: either $\delta_{1}(\lambda)\geq
1/\mathrm{poly}(\lambda)$ or $\delta_{2}(\lambda)\geq
1/\mathrm{poly}(\lambda)$. This is easily seen as follows. First, by taking
the sum of the two expression above, we get

$\displaystyle\frac{1}{2}{\sf Pr}[0\leftarrow{\sf lwe}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]+\frac{1}{2}{\sf
Pr}[1\leftarrow{\sf hyb}_{0}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]$
$\displaystyle\quad\quad+\frac{1}{2}{\sf Pr}[1\leftarrow{\sf unif}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]+\frac{1}{2}{\sf
Pr}[0\leftarrow{\sf hyb}_{0}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]$ $\displaystyle=\,\,$
$\displaystyle\frac{1}{2}+\delta_{1}(\lambda)+\frac{1}{2}+\delta_{2}(\lambda).$

Second, we use that ${\sf Pr}[0\leftarrow{\sf hyb}_{0}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]+{\sf Pr}[1\leftarrow{\sf
hyb}_{0}.{\sf Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]=1$ to obtain
$\delta_{1}(\lambda)+\delta_{2}(\lambda)=\epsilon(\lambda)$, which implies
that either $\delta_{1}(\lambda)\geq 1/\mathrm{poly}(\lambda)$ or
$\delta_{2}(\lambda)\geq 1/\mathrm{poly}(\lambda)$.

Next, we prove the following:

######  Claim 6.4.

Assuming the hardness of $\mathsf{LWE}_{n,q,\alpha q}^{m}$, it holds that
$\delta_{1}\leq\mathsf{negl}(\lambda)$. In other words,

$\frac{1}{2}{\sf Pr}[0\leftarrow{\sf lwe}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]+\frac{1}{2}{\sf
Pr}[1\leftarrow{\sf hyb}_{0}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]\leq\frac{1}{2}+\mathsf{negl}(\lambda).$

###### Proof.

We consider two hypothetical distributions, denoted by $\widetilde{{\sf
lwe}}.{\sf Dist}$ (Figure 8) and $\widetilde{{\sf hyb}}.{\sf Dist}$ (Figure
9), which are the same as ${\sf lwe}.{\sf Dist}$ and ${\sf hyb}.{\sf Dist}$,
except that the procedure $\mathsf{Revoke}$ is not performed in the
experiment.

$\widetilde{{\sf lwe}}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}\left(1^{\lambda}\right)$: 1. Sample
$(\mathbf{A},\mathsf{td}_{\mathbf{A}})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)$.
2. Generate
$(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)$.
3. Generate
$\rho_{R,\,\mathbf{\textsc{Aux}}}\leftarrow\mathcal{A}_{\lambda,\mathbf{A}}(|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\otimes\nu_{\lambda})$.
4. Sample
$\mathbf{s}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n},\mathbf{e}\sim
D_{\mathbb{Z}^{m},\alpha q}$ and $e^{\prime}\sim D_{\mathbb{Z},\beta q}$. 5.
Generate
$\rho_{R,\mathbf{\textsc{Aux}}}\leftarrow\mathcal{A}_{\lambda,\mathbf{A}}(|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\otimes\nu_{\lambda})$.
6. Run $\mathsf{WeakRevoke}(\mathbf{A},\mathbf{y},\cdot)$ on system $R$. If it
outputs a short vector $\mathbf{x}_{0}\in\mathbb{Z}_{q}^{m}$, continue.
Otherwise, output $\mathsf{Invalid}$. 7. Run
$b^{\prime}\leftarrow\mathcal{D}(\mathbf{A},\mathbf{y},\mathbf{s}^{\intercal}\mathbf{A}+\mathbf{e}^{\intercal},\mathbf{s}^{\intercal}\mathbf{y}+e^{\prime},\cdot)$
on system Aux. Output $b^{\prime}$.
---
Figure 8: The distribution $\widetilde{{\sf lwe}}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}\left(1^{\lambda}\right)$. $\widetilde{{\sf
hyb}}_{0}.{\sf Dist}^{\mathcal{A},\mathcal{D}}\left(1^{\lambda}\right)$: 1.
Sample
$(\mathbf{A},\mathsf{td}_{\mathbf{A}})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)$.
2. Sample
$\mathbf{u}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{m}$
and $e^{\prime}\sim D_{\mathbb{Z},\beta q}$. 3. Run
$(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)$.
4. Generate
$\rho_{R,\mathbf{\textsc{Aux}}}\leftarrow\mathcal{A}_{\lambda,\mathbf{A}}(|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\otimes\nu_{\lambda})$.
5. Run $\mathsf{WeakRevoke}(\mathbf{A},\mathbf{y},\cdot)$ on system $R$. If it
outputs a short vector $\mathbf{x}_{0}\in\mathbb{Z}_{q}^{m}$, continue.
Otherwise, output $\mathsf{Invalid}$. 6. Run
$b^{\prime}\leftarrow\mathcal{D}(\mathbf{A},\mathbf{y},\mathbf{u},\mathbf{u}^{\intercal}\mathbf{x}_{0}+e^{\prime},\cdot)$
on system Aux. Output $b^{\prime}$.
---
Figure 9: The distribution $\widetilde{{\sf hyb}}_{0}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}\left(1^{\lambda}\right)$.

Using the fact that dropping $\mathsf{Revoke}$ can only increase the success
probability151515This can be reasoned as follows. We can consider an alternate
but equivalent experiment where we first apply Revoke, followed by WeakRevoke.
The reason why this is equivalent is because if Revoke succeeds then
WeakRevoke always succeeds. Using the fact that both Revoke and WeakRevoke
commute, we can instead consider an alternate experiment where we first apply
WeakRevoke followed by Revoke. Now, it can be seen that dropping Revoke can
only increase the success probability. , we get

$\displaystyle\frac{1}{2}{\sf Pr}[0\leftarrow\widetilde{{\sf lwe}}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]+\frac{1}{2}{\sf
Pr}[1\leftarrow\widetilde{{\sf hyb}}_{0}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]$
$\displaystyle\geq\,\,\frac{1}{2}{\sf Pr}[0\leftarrow{\sf lwe}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]+\frac{1}{2}{\sf
Pr}[1\leftarrow{\sf hyb}_{0}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}(1^{\lambda})]\,=\,\frac{1}{2}+\delta_{1}(\lambda).$

To prove the claim it is sufficient to show that the two distributions
$\widetilde{{\sf lwe}}.{\sf Dist}$ and $\widetilde{{\sf hyb}}_{0}.{\sf Dist}$
are computationally indistinguishable assuming the hardness of
$\mathsf{LWE}_{n,q,\alpha q}^{m}$, i.e.

$\left\\{\widetilde{{\sf lwe}}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}\right\\}\approx_{c}\left\\{\widetilde{{\sf
hyb}}_{0}.{\sf Dist}^{\mathcal{A},\mathcal{D}}\right\\}.$

Here, we invoke the following fact: suppose $D_{0}$ and $D_{1}$ are two
distributions. Any QPT adversary $\mathcal{A}$ can predict $b$ when given a
sample from $D_{b}$, where $b\xleftarrow{\$}\\{0,1\\}$, with probability
$\frac{1}{2}+\frac{\varepsilon}{2}$ if and only if $\mathcal{A}$ can
distinguish $D_{0}$ and $D_{1}$ with probability $\varepsilon$.

We consider the following hybrid distributions, where we highlight changes in
red.

$\mathsf{H}_{0}$: This is the distribution $\widetilde{{\sf lwe}}.{\sf
Dist}^{\mathcal{A},\mathcal{D}}$:

  1. 1.

Sample $(\mathbf{A}\in\mathbb{Z}_{q}^{n\times
m},\mathsf{td}_{\mathbf{A}})\leftarrow\mathsf{GenTrap}(1^{n},1^{m},q)$.

  2. 2.

Sample
$\mathbf{s}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n}$,
$\mathbf{e}\sim D_{\mathbb{Z}^{m},\alpha q}$ and $e^{\prime}\sim
D_{\mathbb{Z},\beta q}$.

  3. 3.

Generate a Gaussian superposition
$(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)$
with parameter $\sigma>0$.

  4. 4.

Run
$\mathcal{A}_{\lambda,\mathbf{A}}(|\psi_{\mathbf{y}}\rangle\langle\psi_{\mathbf{y}}|\otimes\nu_{\lambda})$
to generate a state $\rho_{R,\mathbf{\textsc{aux}}}$ in systems $R$ and aux.

  5. 5.

Run $\mathsf{WeakRevoke}(\mathbf{A},\mathbf{y},\cdot)$ on system $R$ to obtain
$\mathbf{x}_{0}\in\Lambda_{q}^{\mathbf{y}}(\mathbf{A})\,\cap\,\mathcal{B}^{m}(\mathbf{0},\sigma\sqrt{\frac{m}{2}})$
or $\bot$. If the output is $\bot$, output $\mathsf{Invalid}$. Else, run
$b^{\prime}\leftarrow\mathcal{D}(\mathbf{A},\mathbf{y},\mathbf{s}^{\intercal}\mathbf{A}+\mathbf{e}^{\intercal},\mathbf{s}^{\intercal}\mathbf{y}+e^{\prime},\rho_{\textsc{aux}})$
on the reduced state $\rho_{\mathbf{\textsc{aux}}}$ and then output
$b^{\prime}$.

$\mathsf{H}_{1}$: This is the following distribution:

  1. 1.

Sample a random matrix
$\mathbf{A}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n\times
m}$.

  2. 2.

Sample
$\mathbf{s}\raisebox{-1.0pt}{$\,\xleftarrow{\raisebox{-1.0pt}{$\scriptscriptstyle\$$}}\,$}\mathbb{Z}_{q}^{n}$,
$\mathbf{e}\sim D_{\mathbb{Z}^{m},\alpha q}$ and $e^{\prime}\sim
D_{\mathbb{Z},\beta q}$.

  3. 3.

Generate a Gaussian superposition
$(\ket{\psi_{\mathbf{y}}},\mathbf{y})\leftarrow\mathsf{GenGauss}(\mathbf{A},\sigma)$
with parameter $\sigma>0$.

  4. 4.

Run