#  Publicly Verifiable Deletion from Minimal Assumptions

Fuyuki Kitagawa  NTT Social Informatics Laboratories, Tokyo, Japan
<EMAIL_ADDRESS>Ryo Nishimaki  NTT
Social Informatics Laboratories, Tokyo, Japan
<EMAIL_ADDRESS>Takashi Yamakawa  NTT
Social Informatics Laboratories, Tokyo, Japan
<EMAIL_ADDRESS>
###### Abstract

We present a general compiler to add the publicly verifiable deletion property
for various cryptographic primitives including public key encryption,
attribute-based encryption, and quantum fully homomorphic encryption. Our
compiler only uses one-way functions, or more generally hard quantum planted
problems for $\mathsf{NP}$, which are implied by one-way functions. It relies
on minimal assumptions and enables us to add the publicly verifiable deletion
property with no additional assumption for the above primitives. Previously,
such a compiler needs additional assumptions such as injective trapdoor one-
way functions or pseudorandom group actions [Bartusek-Khurana-Poremba,
ePrint:2023/370]. Technically, we upgrade an existing compiler for privately
verifiable deletion [Bartusek-Khurana, ePrint:2022/1178] to achieve publicly
verifiable deletion by using digital signatures.

###### Contents

  1. 1 Introduction
    1. 1.1 Background
    2. 1.2 Our Results
    3. 1.3 Technical Overview
    4. 1.4 More on Related Works
  2. 2 Preliminaries
    1. 2.1 Notations
    2. 2.2 Cryptographic Tools
  3. 3 Signature with One-Time Unforgeability for BB84 states
  4. 4 Certified Everlasting Lemmas
  5. 5 Instantiations
    1. 5.1 Public-Key Encryption
    2. 5.2 Other Primitives
  6. 6 Making Assumptions Minimal

##  1 Introduction

###  1.1 Background

Quantum mechanics yields new cryptographic primitives that classical
cryptography cannot achieve. In particular, the uncertainty principle enables
us to certify deletion of information. Broadbent and Islam [BI20] introduced
the notion of quantum encryption with certified deletion, where we can
generate a classical certificate for the deletion of quantum ciphertext. We
need a verification key generated along with a quantum ciphertext to check the
validity of a certificate. The root of this concept is revocable quantum time-
release encryption by Unruh [Unr15], where a sender can revoke quantum
ciphertext if a receiver returns it before a pre-determined time. Encryption
with certified deletion is useful because encryption security holds _even if
adversaries obtain a secret decryption key after they generate a valid
certificate for deletion_. After the work by Broadbent and Islam [BI20], many
works presented extended definitions and new constructions of quantum
(advanced) encryption with certified deletion [HMNY21, Por23, BK22, HKM+23,
BGG+23, BKP23]. In particular, Bartusek and Khurana [BK22], and Hiroka,
Kitagawa, Morimae, Nishimaki, Pal, and Yamakawa [HKM+23] considered certified
everlasting security, which guarantees that computationally _unbounded_
adversaries cannot obtain information about plaintext _after a valid
certificate was generated_. Several works [HMNY21, Por23, BGG+23, BKP23]
considered public verifiability, where we can reveal verification keys without
harming certified deletion security. These properties are desirable for
encryption with certified deletion in real-world applications.

In this work, we focus on cryptographic primitives with publicly verifiable
deletion (PVD) [BKP23], which satisfy certified everlasting security and
public verifiability. Known schemes based on BB84 states are privately
verifiable [BI20, HMNY21, BK22, HKM+23], where we need to keep verification
keys secret to ensure encryption security. Some schemes are publicly
verifiable [HMNY21, Por23, BGG+23, BKP23]. Public verifiability is preferable
to private verifiability since we need to keep many verification keys secret
when we generate many ciphertexts of encryption with privately verifiable
deletion. More secret keys lead to more risks. In addition, anyone can verify
deletion in cryptography with PVD.

Hiroka, Morimae, Nishimaki, and Yamakawa [HMNY21] achieved interactive public
key encryption with non-everlasting PVD from extractable witness encryption
[GKP+13], which is a strong knowledge-type assumption, and one-shot signatures
which require classical oracles [AGKZ20]. Poremba [Por23] achieved public key
encryption (PKE) and fully homomorphic encryption (FHE) with non-everlasting
PVD based on lattices. He conjectured Ajtai hash function satisfies a strong
Gaussian collapsing property and proved the security of his constructions
under the conjecture. Later, Bartusek, Khurana, and Poremba [BKP23] proved the
conjecture is true under the LWE assumption.

Bartusek, Garg, Goyal, Khurana, Malavolta, Raizes, and Roberts [BGG+23]
achieved primitive $X$ with PVD from $X$ and post-quantum secure
indistinguishability obfuscation (IO) [BGI+12] where $X\in\\{\textrm{SKE, COM,
PKE, ABE, FHE, TRE, WE}\\}$.111SKE, COM, ABE, TRE, and WE stand for secret key
encryption, commitment, attribute-based encryption, time-release encryption,
and witness encryption, respectively. Although Bartusek et al. [BGG+23] did
not mention, we can apply their transformation to SKE and COM as the results
by Bartusek and Khurana [BK22]. They also achieved functional encryption with
PVD and obfuscation with PVD, which rely on post-quantum IO. All their
constructions use subspace coset states [CLLZ21]. Bartusek et al. [BKP23]
achieved PKE (resp. COM) with PVD from injective trapdoor one-way functions
(or superposition-invertible regular trapdoor functions) or pseudorandom group
actions [HMY22] (resp. almost-regular one-way functions). They also achieved
primitive $Y$ with PVD from injective trapdoor one-way functions (or
superposition-invertible regular trapdoor functions) or pseudorandom group
actions, and primitive $Y$ where $Y\in\\{\textrm{ABE, QFHE, TRE, WE}\\}$. They
obtained these results by considering certified everlasting target-collapsing
functions as an intermediate primitive.

As we explained above, known encryption with PVD constructions need strong and
non-standard assumptions [HMNY21, BGG+23], algebraic assumptions [Por23,
BKP23], or additional assumptions [BKP23]. This status is unsatisfactory
because Bartusek and Khurana [BK22] prove that we can achieve $X$ with
_privately_ verifiable deletion222We do not abbreviate when we refer to this
type to avoid confusion. from $X$ where $X\in\\{\textrm{SKE, COM, PKE, ABE,
FHE, TRE, WE}\\}$333Although Bartusek and Khurana [BK22] did not mention, we
can apply their transformation to SKE. _without any additional assumptions_.
Thus, our main question in this work is the following.

_Can we achieve encryption with PVD from minimal assumptions?_

###  1.2 Our Results

We affirmatively answer the main question described in the previous section.
We present a general transformation from primitive $Z$ into $Z$ with PVD where
$Z\in\\{\textrm{SKE, COM, PKE, ABE, QFHE, TRE, WE}\\}$. In the transformation,
we only use one-way functions, or more generally, hard quantum planted
problems for $\mathsf{NP}$, which we introduce in this work and are implied by
one-way functions.

More specifically, we extend the certified everlasting lemma by Bartusek and
Khurana [BK22], which enables us to achieve encryption with privately
verifiable deletion, to a publicly verifiable certified everlasting lemma. We
develop an authentication technique based on (a variant of) the Lamport
signature [Lam79] to reduce our publicly verifiable certified everlasting
lemma to Bartusek and Khurana’s certified everlasting lemma.

Our new lemma is almost as versatile as Bartusek and Khurana’s lemma. It is
easy to apply it to all-or-nothing type encryption444SKE, PKE, ABE, (Q)FHE,
TRE, and WE fall into this category., where a secret key (or witness) holder
can recover the entire plaintext. One subtle issue is that we need to use QFHE
for (Q)FHE with PVD. The reason is that we need to apply an evaluation
algorithm to quantum ciphertext. Note that we can use FHE and Bartusek and
Khurana’s lemma to achieve FHE with privately verifiable deletion.

The advantages of our techniques are as follows:

  * •

For $Z^{\prime}\in\\{\textrm{SKE, COM, PKE, ABE, QFHE, TRE}\\}$, we can
convert plain $Z^{\prime}$ into $Z^{\prime}$ with PVD with no additional
assumption. For WE, we can convert it into WE with PVD additionally assuming
one-way functions (or hard quantum planted problems for $\mathsf{NP}$).555WE
does not seem to imply one-way functions. Bartusek et al. [BKP23] require
injective (or almost-regular) trapdoor one-way functions, pseudorandom group
actions, or almost-regular one-way functions for their constructions.

  * •

Our transformation is applicable even if the base scheme has quantum
encryption and decryption (or committing) algorithms.666The compilers of
[BK22, BKP23] are also applicable to schemes that have quantum encryption and
decryption (or committing) algorithms though they do not explicitly mention
it.  This means that our assumptions are minimal since $Z$ with PVD implies
both plain $Z$ with quantum encryption and decryption (or committing)
algorithms and hard quantum planted problems for $\mathsf{NP}$ for
$Z\in\\{\textrm{SKE, COM, PKE, ABE, QFHE, TRE, WE}\\}$.

  * •

Our approach is simple. Bartusek et al. [BKP23] introduced an elegant
intermediate notion, certified everlasting target-collapsing, to achieve
cryptography with PVD. However, they use a few more intermediate notions (such
as balanced binary-measurement target-collision-resistance) for their
approach.

###  1.3 Technical Overview

As explained in Section 1.1, Bartusek and Khurana [BK22] gave a generic
compiler to add the _privately verifiable_ deletion property for various types
of encryption. Our finding is that there is a surprisingly simple way to
upgrade their compiler to achieve _publicly verifiable_ deletion by
additionally using digital signatures.

#### Notations.

For a bit string $x$, we write $x_{j}$ to mean $j$-th bit of $x$. For bit
strings $x,\theta\in\\{0,1\\}^{\ell}$, we write $\ket{x}_{\theta}$ to mean the
BB84 state $\bigotimes_{j\in[\ell]}H^{\theta_{j}}\ket{x_{j}}$ where $H$ is the
Hadamard operator.

#### Certified everlasting lemma of [BK22].

The compiler of [BK22] is based on the _certified everlasting lemma_ described
below.777For simplicity, we state a simplified version of the lemma that is
sufficient for the conversion for PKE, FHE, TRE, and WE, but not for ABE. See
Lemma 4.1 for the general version. We describe it in the dual version, where
the roles of computational and Hadamard bases are swapped for convenience. We
stress that the dual version is equivalent to the original one because they
coincide under an appropriate basis change.

Consider a family of distributions
$\\{{\mathcal{Z}(m)}\\}_{m\in\\{0,1\\}^{\lambda+1}}$ over classical strings,
such that for any $m\in\\{0,1\\}^{\lambda+1}$, the distribution
$\mathcal{Z}(m)$ is computationally indistinguishable from the distribution
$\mathcal{Z}(0^{\lambda+1})$. In other words, each distribution
$\mathcal{Z}(m)$ can be thought of as an “encryption” of the input $m$. Let
$\widetilde{\mathcal{Z}}(b)$ be an experiment between an adversary and
challenger defined as follows for $b\in\\{0,1\\}$:

  * •

The challenger samples $x,\theta\leftarrow\\{0,1\\}^{\lambda}$ and sends
$\ket{x}_{\theta}$ and
$\mathcal{Z}(\theta,b\oplus\bigoplus_{j:\theta_{j}=1}x_{j})$ to the adversary.

  * •

The adversary sends a classical string $x^{\prime}\in\\{0,1\\}^{\lambda}$ and
a quantum state $\rho$ to the challenger.

  * •

The challenger outputs $\rho$ if $x^{\prime}_{j}=x_{j}$ for all $j$ such that
$\theta_{j}=0$, and otherwise outputs a special symbol $\bot$ as the output of
the experiment.

The certified everlasting lemma states that for any QPT adversary, the trace
distance between $\widetilde{\mathcal{Z}}(0)$ and $\widetilde{\mathcal{Z}}(1)$
is negligible in $\lambda$.

The above lemma immediately gives a generic compiler to add the privately
verifiable deletion property. To encrypt a message $b\in\\{0,1\\}$, we set the
ciphertext to be
$(\ket{x}_{\theta},\mathsf{Enc}(\theta,b\oplus\bigoplus_{j:\theta_{j}=1}x_{j}))$,
where $x$ and $\theta$ are randomly chosen from $\\{0,1\\}^{\lambda}$, and
$\mathsf{Enc}$ is the encryption algorithm of the underlying scheme.888We
write $\mathsf{Enc}(\theta,b\oplus\bigoplus_{j:\theta_{j}=1}x_{j})$ to mean an
encryption of the message $(\theta,b\oplus\bigoplus_{j:\theta_{j}=1}x_{j})$
where we omit the encryption key. The decryptor first decrypts the second
component to get $(\theta,b\oplus\bigoplus_{j:\theta_{j}=1}x_{j})$, recovers
$\bigoplus_{j:\theta_{j}=1}x_{j}$ from $\ket{x}_{\theta}$ and $\theta$, and
then XORs it with $b\oplus\bigoplus_{j:\theta_{j}=1}x_{j}$ to recover $b$. To
delete the ciphertext and obtain a certificate $x^{\prime}$, we measure
$\ket{x}_{\theta}$ in the standard basis. To verify the certificate, we check
if $x^{\prime}_{j}=x_{j}$ for all $j$ such that $\theta_{j}=0$. By utilizing
the above lemma, we can see that an adversary’s internal state will not
contain any information about $b$ given the verification algorithm’s
acceptance. Therefore, the scheme offers certified everlasting security.
However, this scheme has only privately verifiable deletion because the
verification algorithm needs to know $x$ and $\theta$, which are part of the
encryption randomness that has to be hidden from the adversary.

#### Making verification public via digital signatures.

We show a publicly verifiable variant of the certified everlasting lemma by
using digital signatures. Roughly speaking, our idea is to generate a
signature for the BB84 state $\ket{x}_{\theta}$ by coherently running the
signing algorithm so that the verification of deletion can be done by the
verification of the signature, which can be done publicly. Note that the
signature does _not_ certify $\ket{x}_{\theta}$ as a quantum state. It rather
certifies its computational basis part (i.e., $x_{j}$ for $j$ such that
$\theta_{j}=0$). This is sufficient for our purpose because the verification
of deletion just checks the computational basis part.

With the above idea in mind, we modify the experiment
$\widetilde{\mathcal{Z}}(b)$ as follows:

  * •

The challenger generates a key pair $(\mathsf{vk},\mathsf{sigk})$ of a digital
signature scheme and samples $x,\theta\leftarrow\\{0,1\\}^{\lambda}$. Let
$U_{\mathsf{sign}}$ be a unitary that works as follows:

$\ket{m}\ket{0\ldots 0}\mapsto\ket{m}\ket{\mathsf{Sign}(\mathsf{sigk},m)}.$

where $\mathsf{Sign}(\mathsf{sigk},\cdot)$ is a deterministic signing
algorithm with a signing key $\mathsf{sigk}$. The challenger sends
$\mathsf{vk}$, $U_{\mathsf{sign}}\ket{x}_{\theta}\ket{0\ldots 0}$, and
$\mathcal{Z}(\mathsf{sigk},\theta,b\oplus\bigoplus_{j:\theta_{j}=1}x_{j})$ to
the adversary.

  * •

The adversary sends a classical string $x^{\prime}\in\\{0,1\\}^{\lambda}$, a
signature $\sigma$, and a quantum state $\rho$ to the challenger.

  * •

The challenger outputs $\rho$ if $\sigma$ is a valid signature for
$x^{\prime}$, and otherwise outputs a special symbol $\bot$ as the output of
the experiment.

We show that for any QPT adversary, the trace distance between
$\widetilde{\mathcal{Z}}(0)$ and $\widetilde{\mathcal{Z}}(1)$ is negligible in
$\lambda$ if we instantiate the digital signatures with an appropriate scheme
as explained later. The crucial difference from the original lemma is that the
challenger does not need to check if $x^{\prime}_{j}=x_{j}$ for all $j$ such
that $\theta_{j}=0$ and only needs to run the verification algorithm of the
digital signature scheme.

By using the above variant similarly to the original privately verifiable
construction, we obtain a generic compiler that adds publicly verifiable
deletion property. For clarity, we describe the construction below. To encrypt
a message $b\in\\{0,1\\}$, the encryption algorithm generates a key pair
$(\mathsf{vk},\mathsf{sigk})$ of the digital signature scheme, chooses
$x,\theta\leftarrow\\{0,1\\}^{\lambda}$, and outputs a ciphertext
$(U_{\mathsf{sign}}\ket{x}_{\theta},\mathsf{Enc}(\mathsf{sigk},\theta,b\oplus\bigoplus_{j:\theta_{j}=1}x_{j}))$
and a public verification key $\mathsf{vk}$. The decryptor first decrypts the
second component to get
$(\mathsf{sigk},\theta,b\oplus\bigoplus_{j:\theta_{j}=1}x_{j})$, uncompute the
signature register of the first component by using $\mathsf{sigk}$ to get
$\ket{x}_{\theta}$, recovers $\bigoplus_{j:\theta_{j}=1}x_{j}$ from
$\ket{x}_{\theta}$ and $\theta$, and then XORs it with
$b\oplus\bigoplus_{j:\theta_{j}=1}x_{j}$ to recover $b$. To delete the
ciphertext and obtain a certificate $(x^{\prime},\sigma)$, we measure
$U_{\mathsf{sign}}\ket{x}_{\theta}$ in the standard basis to get
$(x^{\prime},\sigma)$. To verify the certificate, we check if $\sigma$ is a
valid signature for $x^{\prime}$. By utilizing the above lemma, we can see
that the above scheme achieves certified everlasting security with public
verification.

#### Proof idea and instantiation of digital signatures.

We prove the above publicly verifiable version by reducing it to the original
one in [BK22]. Noting that
$\mathcal{Z}(\mathsf{sigk},\theta,b\oplus\bigoplus_{j:\theta_{j}=1}x_{j})$
computationally hides $\mathsf{sigk}$ by the assumption, a straightforward
reduction works if the digital signature scheme satisfies the following
security notion which we call one-time unforgeability for BB84 states.

###### Definition 1.1 (One-time unforgeability for BB84 states (informal)).

Given $\mathsf{vk}$ and $U_{\mathsf{sign}}\ket{x}_{\theta}\ket{0\ldots 0}$ for
uniformly random $x,\theta\leftarrow\\{0,1\\}^{\lambda}$, no QPT adversary can
output $x^{\prime}\in\\{0,1\\}^{\lambda}$ and a signature $\sigma$ such that
$\sigma$ is a valid signature for $x^{\prime}$ and $x^{\prime}_{j}\neq x_{j}$
for some $j$ such that $\theta_{j}=0$ with a non-negligible probability.

It is easy to show that the Lamport signature satisfies the above property.
This can be seen as follows. Recall that a verification key of the Lamport
signature consists of $(v_{j,b})_{j\in[\lambda],b\in\\{0,1\\}}$ where
$v_{j,b}\coloneqq f(u_{j,b})$ for a one-way function $f$ and uniformly random
inputs $(u_{j,b})_{j\in[\lambda],b\in\\{0,1\\}}$, and a signature for a
message $m\in\\{0,1\\}^{\lambda}$ is
$\sigma\coloneqq(u_{j,m_{j}})_{j\in[\lambda]}$. Suppose that there is an
adversary that breaks the above property. Then, there must exist
$j\in[\lambda]$ such that $x^{\prime}_{j}\neq x_{j}$ and $\theta_{j}=0$, in
which case the input state $U_{\mathsf{sign}}\ket{x}_{\theta}\ket{0\ldots 0}$
does not have any information of $u_{j,1-x_{j}}$. On the other hand, to
generate a valid signature for $x^{\prime}$, the adversary has to find a
preimage of $v_{j,x^{\prime}_{j}}=v_{j,1-x_{j}}$. This is impossible by the
one-wayness of $f$. Thus, a digital signature scheme that satisfies one-time
unforgeability for BB84 states exists assuming the existence of one-way
functions.

#### Achieving minimal assumptions.

In the above, we explain that one-way functions are sufficient for
instantiating the digital signature scheme needed for our compiler. On the
other hand, encryption schemes with publicly verifiable deletion does not seem
to imply the existence of one-way functions because ciphertexts can be
quantum. Thus, one-way functions may not be a necessary assumption for them.
To weaken the assumption, we observe that we can use hard quantum planted
problems for $\mathsf{NP}$ instead of one-way functions in the Lamport
signature. Here, hard quantum planted problems for a $\mathsf{NP}$ language
$L$ is specified by a quantum polynomial-time sampler that samples an
instance-witness pair $(x,w)$ for the language $L$ in such a way that no QPT
adversary can find a witness for $x$ with non-negligible probability. Given
such a sampler, it is easy to see that we can instantiate the digital
signature scheme similar to the above except that $(v_{j,b},u_{j,b})$ is now
replaced with an instance-witness pair sampled by the sampler.

We observe that $Z$ with PVD implies the existence of hard quantum planted
problems for $\mathsf{NP}$ where $Z\in\\{\textrm{SKE, COM, PKE, ABE, QFHE,
TRE, WE}\\}$.999We assume that the verification algorithm of $Z$ with PVD is a
classical deterministic algorithm. If we allow it to be a quantum algorithm,
we have to consider hard quantum planted problems for $\mathsf{QCMA}$, which
are also sufficient to instantiate our compiler. This can be seen by
considering the verification key as an instance and certificate as a witness
for an $\mathsf{NP}$ language. Our construction relies on hard quantum planted
problems for $\mathsf{NP}$ and plain $Z$ with quantum encryption and
decryption (or committing) algorithms, both of which are implied by $Z$ with
PVD, and thus it is based on the minimal assumptions.

###  1.4 More on Related Works

#### Certified deletion for ciphertext with private verifiability.

Broadbent and Islam [BI20] achieved one-time SKE with privately verifiable
deletion without any cryptographic assumptions. Hiroka et al. [HMNY21]
achieved PKE and ABE with non-everlasting privately verifiable deletion. They
also achieve interactive PKE with non-everlasting privately verifiable
deletion and classical communication in the quantum random oracle model (QROM)
from the LWE assumption. However, none of their constructions satisfy
certified everlasting security. Hiroka, Morimae, Nishimaki, and Yamakawa
[HMNY22] defined certified everlasting commitment and zero-knowledge (for
$\mathsf{QMA}$) by extending everlasting security [MU10]. They achieved these
notions by using plain commitment and QROM. Bartusek and Khurana [BK22]
defined certified everlasting security for various all-or-nothing type
encryption primitives and presented a general framework to achieve certified
everlasting secure all-or-nothing type encryption and commitment with
privately verifiable deletion using BB84 states. They also studied secure
computation with everlasting security transfer. Hiroka et al. [HKM+23] also
defined and achieved certified everlasting security for various cryptographic
primitives. In particular, they defined and achieved certified everlasting
(collusion-resistant) functional encryption, garbled circuits, and compute-
and-compare obfuscation, which are outside of all-or-nothing type encryption.
Their constructions are also based on BB84 states and are privately
verifiable. They also use a signature-based authentication technique for BB84
states. However, its role is not achieving public verifiability but functional
encryption security. See the paper by Hiroka et al. [HKM+23] for the
differences between their results and Bartusek and Khurana’s results [BK22].

#### Certified deletion for keys or secure key leasing.

Kitagawa and Nishimaki [KN22] defined secret key functional encryption with
secure key leasing, where we can generate a classical certificate for the
deletion of functional keys. They achieved such a primitive with bounded
collusion-resistance from one-way functions. Agrawal, Kitagawa, Nishimaki,
Yamada, and Yamakawa [AKN+23] defined PKE with secure key leasing, where we
lose decryption capability after we return a quantum decryption key. They
achieved it from standard PKE. They also extended the notion to ABE with
secure key leasing and public key functional encryption with secure key
leasing. They achieved them from standard ABE and public key functional
encryption, respectively. Garg et al. [BGG+23] presented a public key
functional encryption with secure key leasing scheme based on IO and injective
one-way functions. Ananth, Poremba, and Vaikuntanathan [APV23] also defined
the same notion as PKE with secure key leasing (they call key-revocable PKE).
However, their definition differs slightly from that of Agrawal et al.
[AKN+23]. They also studied key-revocable FHE and PRF. They achieved them from
the LWE assumption.

#### Secure software leasing.

Ananth and La Placa [AL21] defined secure software leasing, where we lose
software functionality after we return a quantum software. They achieved
secure software leasing for a subclass of evasive functions from public key
quantum money and the LWE assumptions. After that, several works proposed
extensions, variants, and improved constructions of secure software leasing
[CMP20, BJL+21, KNY21, ALL+21].

##  2 Preliminaries

###  2.1 Notations

Here we introduce basic notations we will use in this paper.

In this paper, standard math or sans serif font stands for classical
algorithms (e.g., $C$ or $\mathsf{Gen}$) and classical variables (e.g., $x$ or
$\mathsf{pk}$). Calligraphic font stands for quantum algorithms (e.g.,
$\mathsf{Gen}$) and calligraphic font and/or the bracket notation for (mixed)
quantum states (e.g., $\mathpzc{q}$ or $\ket{\psi}$).

Let $x\leftarrow X$ denote selecting an element $x$ from a finite set $X$
uniformly at random, and $y\leftarrow A(x)$ denote assigning to $y$ the output
of a quantum or probabilistic or deterministic algorithm $A$ on an input $x$.
When $D$ is a distribution, $x\leftarrow D$ denotes sampling an element $x$
from $D$. $y\coloneqq z$ denotes that $y$ is set, defined, or substituted by
$z$. Let $[n]\coloneqq\\{1,\dots,n\\}$. Let $\lambda$ be a security parameter.
For a bit string $s\in\\{0,1\\}^{n}$, $s_{i}$ denotes the $i$-th bit of $s$.
QPT stands for quantum polynomial time. PPT stands for (classical)
probabilistic polynomial time. We say that a quantum (resp. probabilistic
classical) algorithm is efficient if it runs in QPT (resp. PPT). A function
$f:\mathbb{N}\rightarrow\mathbb{R}$ is a negligible function if for any
constant $c$, there exists $\lambda_{0}\in\mathbb{N}$ such that for any
$\lambda>\lambda_{0}$, $f(\lambda)<\lambda^{-c}$. We write
$f(\lambda)\leq{\mathsf{negl}}(\lambda)$ to denote $f(\lambda)$ being a
negligible function. The trace distance between two quantum states $\rho$ and
$\sigma$ denoted as $\mathsf{TD}(\rho,\sigma)$ is given by
$\frac{1}{2}\norm{\rho-\sigma}_{\tr}$, where
$\norm{A}_{\tr}\coloneqq\tr\sqrt{{\it A}^{\dagger}{\it A}}$ is the trace norm.

###  2.2 Cryptographic Tools

In this section, we review the cryptographic tools used in this paper.

###### Definition 2.1 (Signature).

Let $\mathcal{M}$ be a message space. A signature scheme for $\mathcal{M}$ is
a tuple of efficient algorithms $(\mathsf{Gen},\mathsf{Sign},\mathsf{Vrfy})$
where:

$\mathsf{Gen}(1^{\lambda})\rightarrow(\mathsf{vk},\mathsf{sigk})$:

The key generation algorithm takes as input the security parameter
$1^{\lambda}$ and outputs a verification key $\mathsf{vk}$ and a signing key
$\mathsf{sigk}$.

$\mathsf{Sign}(\mathsf{sigk},m)\rightarrow\sigma$:

The signing algorithm takes as input a signing key $\mathsf{sigk}$ and a
message $m\in\mathcal{M}$ and outputs a signature $\sigma$.

$\mathsf{Vrfy}(\mathsf{vk},m,\sigma)\rightarrow\top\mbox{ or }\bot$:

The verification algorithm is a deterministic algorithm that takes as input a
verification key $\mathsf{vk}$, a message $m$ and a signature $\sigma$ and
outputs $\top$ to indicate acceptance of the signature and $\bot$ otherwise.

Correctness:

For all $m\in\mathcal{M}$, $(\mathsf{vk},\mathsf{sigk})$ in the range of
$\mathsf{Gen}(1^{\lambda})$, and $\sigma\in\mathsf{Sign}(\mathsf{sigk},m)$, we
have $\mathsf{Vrfy}(\mathsf{vk},m,\sigma)=\top$.

###### Definition 2.2 (Deterministic Signature).

We say that a signature scheme
$\mathsf{SIG}=(\mathsf{Gen},\mathsf{Sign},\mathsf{Vrfy})$ is a deterministic
signature if $\mathsf{Sign}(\mathsf{sigk},\cdot)$ is a deterministic function.

###### Definition 2.3 (Public Key Encryption).

A PKE scheme is a tuple of efficient algorithms
$\mathsf{PKE}=(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$.

$\mathsf{Gen}(1^{\lambda})\rightarrow(\mathsf{pk},\mathsf{sk})$:

The key generation algorithm takes the security parameter $1^{\lambda}$ as
input and outputs a public key $\mathsf{pk}$ and a secret key $\mathsf{sk}$.

$\mathsf{Enc}(\mathsf{pk},m)\rightarrow\mathsf{ct}$:

The encryption algorithm takes $\mathsf{pk}$ and a plaintext $m\in\\{0,1\\}$
as input, and outputs a ciphertext $\mathsf{ct}$.

$\mathsf{Dec}(\mathsf{sk},\mathsf{ct})\rightarrow m^{\prime}$:

The decryption algorithm takes $\mathsf{sk}$ and $\mathsf{ct}$ as input, and
outputs a plaintext $m^{\prime}\in\mathcal{M}$ or $\bot$.

Correctness:

For any $m\in\mathcal{M}$, we have

$\displaystyle\Pr\left[m^{\prime}\neq m\
\middle|\begin{array}[]{ll}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{KeyGen}(1^{\lambda})\\\
\mathsf{ct}\leftarrow\mathsf{Enc}(\mathsf{pk},m)\\\
m^{\prime}\leftarrow\mathsf{Dec}(\mathsf{sk},\mathsf{ct})\end{array}\right]\leq{\mathsf{negl}}(\lambda).$
(4)

Semantic Security:

For any QPT $\mathpzc{A}$, we have

$\displaystyle\absolutevalue{\Pr\left[\mathpzc{A}(\mathsf{pk},\mathsf{ct})=1\
\middle|\begin{array}[]{ll}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})\\\
\mathsf{ct}\leftarrow\mathsf{Enc}(\mathsf{pk},0)\end{array}\right]-\Pr\left[\mathpzc{A}(\mathsf{pk},\mathsf{ct})=1\
\middle|\begin{array}[]{ll}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{KeyGen}(1^{\lambda})\\\
\mathsf{ct}\leftarrow\mathsf{Enc}(\mathsf{pk},1)\end{array}\right]}={\mathsf{negl}}(\lambda).$
(9)

##  3 Signature with One-Time Unforgeability for BB84 states

#### Definition.

We first provide the definition of one-time unforgeability for BB84 states.

###### Definition 3.1 (One-Time Unforgeability for BB84 states).

Let $\mathsf{SIG}=(\mathsf{Gen},\mathsf{Sign},\mathsf{Vrfy})$ be a signature
scheme. We define the experiment
$\mathsf{Exp}_{\mathsf{SIG},\mathpzc{A}}^{\mathsf{otu}\mbox{-}\mathsf{bb84}}(1^{\lambda})$
between an adversary $\mathpzc{A}$ and challenger as follows.

  1. 1.

The challenger runs
$(\mathsf{vk},\mathsf{sigk})\leftarrow\mathsf{Gen}(1^{\lambda})$ and generates
$x,\theta\leftarrow\\{0,1\\}^{\lambda}$. The challenger generates a quantum
state $\ket{\psi}$ by applying the map $\ket{m}\ket{0\ldots
0}\rightarrow\ket{m}\ket{\mathsf{Sign}(\mathsf{sigk},m)}$ to
$\ket{x}_{\theta}\otimes\ket{0\ldots 0}$. The challenger gives $\mathsf{vk}$
and $\ket{\psi}$ to $\mathpzc{A}$.

  2. 2.

$\mathpzc{A}$ outputs a pair of message and signature
$(x^{\prime},\sigma^{\prime})$ as the challenge message-signature pair to the
challenger.

  3. 3.

The experiment outputs $1$ if the followings are satisfied.

     * •

$x_{i}\neq x_{i}^{\prime}$ holds for some $i$ such that $\theta_{i}=0$.

     * •

$\mathsf{Vrfy}(\mathsf{vk},x^{\prime},\sigma^{\prime})=1$ holds.

We say $\mathsf{SIG}$ is one-time unforgeable for BB84 states if, for any QPT
adversary $\mathpzc{A}$, it holds that

$\displaystyle\mathsf{Adv}_{\mathsf{SIG},\mathpzc{A}}^{\mathsf{otu}\mbox{-}\mathsf{bb84}}(\lambda)\coloneqq\Pr[\mathsf{Exp}_{\mathsf{SIG},\mathpzc{A}}^{\mathsf{otu}\mbox{-}\mathsf{bb84}}(1^{\lambda})=1]={\mathsf{negl}}(\lambda).$
(10)

#### Construction.

We construct a classical deterministic signature scheme
$\mathsf{SIG}=(\mathsf{Gen},\mathsf{Sign},\mathsf{Vrfy})$ satisfying one-time
unforgeability for BB84 states using OWF $f$. The message space of
$\mathsf{SIG}$ is $\\{0,1\\}^{\ell}$.

$\mathsf{Gen}(1^{\lambda})$:

  * •

Generate $u_{i,b}\leftarrow\\{0,1\\}^{\lambda}$ for every $i\in[\ell]$ and
$b\in\\{0,1\\}$.

  * •

Compute $v_{i,b}\leftarrow f(u_{i,b})$ for every $i\in[\ell]$ and
$b\in\\{0,1\\}$.

  * •

Output $\mathsf{vk}:=(v_{i,b})_{i\in[\ell],b\in\\{0,1\\}}$ and
$\mathsf{sigk}:=(u_{i,b})_{i\in[\ell],b\in\\{0,1\\}}$.

$\mathsf{Sign}(\mathsf{sigk},m)$:

  * •

Parse $(u_{i,b})_{i\in[\ell],b\in\\{0,1\\}}\leftarrow\mathsf{sigk}$.

  * •

Output $(u_{i,m_{i}})_{i\in[\ell]}$.

$\mathsf{Vrfy}(\mathsf{vk},m,\sigma)$:

  * •

Parse $(v_{i,b})_{i\in[\ell],b\in\\{0,1\\}}\leftarrow\mathsf{vk}$ and
$(w_{i})_{i\in[\ell]}\leftarrow\sigma$.

  * •

Output $\top$ if $u_{i,m_{i}}=f(w_{i})$ holds for every $i\in[\ell]$ and
otherwise output $\bot$.

It is clear that $\mathsf{SIG}$ is a correct classical deterministic
signature. Also, we have the following theorem.

###### Theorem 3.2.

Assume $f$ is OWF. Then, $\mathsf{SIG}$ satisfies one-time unforgeability for
BB84 states.

###### Proof.

For a computational basis position $i\in[\lambda]$ (that is, $i$ such that
$\theta_{i}=0$), when we generate $\ket{\psi}$ by applying the map
$\ket{m}\ket{0\ldots 0}\rightarrow\ket{m}\ket{\mathsf{Sign}(\mathsf{sigk},m)}$
to $\ket{x}_{\theta}\otimes\ket{0\ldots 0}$, $\ket{\psi}$ contains only
$u_{i,b}$ and not $u_{i,1-b}$ if $x_{i}=b$. From this fact, the one-time
unforgeability of $\mathsf{SIG}$ directly follows from the security of $f$. ∎

##  4 Certified Everlasting Lemmas

In this section, we first review the certified everlasting lemma by Bartusek
and Khurana [BK22], which provides cryptography with privately verifiable
deletion. Next, we present our new certified everlasting lemma, which provides
cryptography with PVD.

###### Lemma 4.1 (Certified Everlasting Lemma [BK22]).

Let $\\{\mathcal{Z}_{\lambda}(\cdot,\cdot,\cdot)\\}_{\lambda\in\mathbb{N}}$ be
an efficient quantum operation with three arguments: a $\lambda$-bit string
$\theta$, a bit $\beta$, and a quantum register
${\color[rgb]{.5,.5,.5}{\mathsf{A}}}$. For any QPT $\mathpzc{B}$, consider the
following experiment $\widetilde{\mathcal{Z}}_{\lambda}^{\mathpzc{B}}(b)$ over
quantum states, obtained by running $\mathpzc{B}$ as follows.

  * •

Sample $x,\theta\leftarrow\\{0,1\\}^{\lambda}$ and initialize $\mathpzc{B}$
with
$\mathcal{Z}_{\lambda}(\theta,b\oplus\bigoplus_{i:\theta_{i}=1}x_{i},\ket{x}_{\theta})$.

  * •

$\mathpzc{B}$’s output is parsed as a string
$x^{\prime}\in\\{0,1\\}^{\lambda}$ and a residual state on register
${\color[rgb]{.5,.5,.5}{\mathsf{B}}}$.

  * •

If $x_{i}=x^{\prime}_{i}$ for all $i$ such that $\theta_{i}=0$, output
${\color[rgb]{.5,.5,.5}{\mathsf{B}}}$, and otherwise output a special symbol
$\bot$.

Assume that for any QPT $\mathpzc{A}$, $\theta\in\\{0,1\\}^{\lambda}$,
$\beta\in\\{0,1\\}$, and an efficiently samplable state
$\ket{\psi}^{{\color[rgb]{.5,.5,.5}{\mathsf{A,C}}}}$ on registers
${\color[rgb]{.5,.5,.5}{\mathsf{A}}}$ and
${\color[rgb]{.5,.5,.5}{\mathsf{C}}}$, we have

$\absolutevalue{\Pr[\mathpzc{A}(\mathcal{Z}_{\lambda}(\theta,\beta,{\color[rgb]{.5,.5,.5}{\mathsf{A}}}),{\color[rgb]{.5,.5,.5}{\mathsf{C}}})=1]-\Pr[\mathpzc{A}(\mathcal{Z}_{\lambda}(0^{\lambda},\beta,{\color[rgb]{.5,.5,.5}{\mathsf{A}}}),{\color[rgb]{.5,.5,.5}{\mathsf{C}}})=1]}\leq{\mathsf{negl}}(\lambda).$

Then, for any QPT $\mathpzc{B}$, we have

$\mathsf{TD}(\widetilde{\mathcal{Z}}_{\lambda}^{\mathpzc{B}}(0),\widetilde{\mathcal{Z}}_{\lambda}^{\mathpzc{B}}(1))\leq{\mathsf{negl}}(\lambda).$

######  Remark 4.2.

Besides notational differences, the above lemma has the following differences
from the original lemma by [BK22].

  * •

We focus on QPT adversaries $\mathpzc{A}$ and $\mathpzc{B}$, though the
original lemma by [BK22] captures more general classes of adversaries.

  * •

The roles of computational basis position and Hadamard basis position in
$\widetilde{\mathcal{Z}}_{\lambda}^{\mathpzc{A}_{\lambda}^{\prime}}(b)$ are
switched.

We can upgrade Lemma 4.1 to a publicly verifiable one by using signatures with
one-time unforgeability for BB84 state introduced in Section 3.

###### Lemma 4.3 (Publicly Verifiable Certified Everlasting Lemma).

Let $\mathsf{SIG}=(\mathsf{Gen},\mathsf{Sign},\mathsf{Vrfy})$ be a signature
scheme satisfying one-time unforgeability for BB84 states. Let
$\\{\mathcal{Z}_{\lambda}(\cdot,\cdot,\cdot,\cdot,\cdot)\\}_{\lambda\in\mathbb{N}}$
be an efficient quantum operation with five arguments: a verification key
$\mathsf{vk}$ and a signing key $\mathsf{sigk}$ of $\mathsf{SIG}$, a
$\lambda$-bit string $\theta$, a bit $\beta$, and a quantum register
${\color[rgb]{.5,.5,.5}{\mathsf{A}}}$. For any QPT $\mathpzc{B}$, consider the
following experiment $\widetilde{\mathcal{Z}}_{\lambda}^{\mathpzc{B}}(b)$ over
quantum states, obtained by running $\mathpzc{B}$ as follows.

  * •

Sample $x,\theta\leftarrow\\{0,1\\}^{\lambda}$ and generate
$(\mathsf{vk},\mathsf{sigk})\leftarrow\mathsf{Gen}(1^{\lambda})$. Generate a
quantum state $\ket{\psi}$ by applying the map $\ket{m}\ket{0\ldots
0}\rightarrow\ket{m}\ket{\mathsf{Sign}(\mathsf{sigk},m)}$ to
$\ket{x}_{\theta}\otimes\ket{0\ldots 0}$. Initialize $\mathpzc{B}$ with
$\mathcal{Z}_{\lambda}(\mathsf{vk},\mathsf{sigk},\theta,b\oplus\bigoplus_{i:\theta_{i}=1}x_{i},\ket{\psi})$.

  * •

$\mathpzc{B}$’s output is parsed as a pair of strings
$(x^{\prime},\sigma^{\prime})$ and a residual state on register
${\color[rgb]{.5,.5,.5}{\mathsf{B}}}$.

  * •

If $\mathsf{Vrfy}(\mathsf{vk},x^{\prime},\sigma^{\prime})=\top$, output
${\color[rgb]{.5,.5,.5}{\mathsf{B}}}$, and otherwise output a special symbol
$\bot$.

Assume that for any QPT $\mathpzc{A}$, key pair $(\mathsf{vk},\mathsf{sigk})$
of $\mathsf{SIG}$, $\theta\in\\{0,1\\}^{\lambda}$, $\beta\in\\{0,1\\}$, and an
efficiently samplable state
$\ket{\psi}^{{\color[rgb]{.5,.5,.5}{\mathsf{A,C}}}}$ on registers
${\color[rgb]{.5,.5,.5}{\mathsf{A}}}$ and
${\color[rgb]{.5,.5,.5}{\mathsf{C}}}$, we have

$\displaystyle\absolutevalue{\Pr[\mathpzc{A}(\mathcal{Z}_{\lambda}(\mathsf{vk},\mathsf{sigk},\theta,\beta,{\color[rgb]{.5,.5,.5}{\mathsf{A}}}),{\color[rgb]{.5,.5,.5}{\mathsf{C}}})=1]-\Pr[\mathpzc{A}(\mathcal{Z}_{\lambda}(\mathsf{vk},0^{\ell_{\mathsf{sigk}}},\theta,\beta,{\color[rgb]{.5,.5,.5}{\mathsf{A}}}),{\color[rgb]{.5,.5,.5}{\mathsf{C}}})=1]}$
$\displaystyle\leq{\mathsf{negl}}(\lambda),\textrm{~{}~{}~{}~{}and}$ (11)
$\displaystyle\absolutevalue{\Pr[\mathpzc{A}(\mathcal{Z}_{\lambda}(\mathsf{vk},\mathsf{sigk},\theta,\beta,{\color[rgb]{.5,.5,.5}{\mathsf{A}}}),{\color[rgb]{.5,.5,.5}{\mathsf{C}}})=1]-\Pr[\mathpzc{A}(\mathcal{Z}_{\lambda}(\mathsf{vk},\mathsf{sigk},0^{\lambda},\beta,{\color[rgb]{.5,.5,.5}{\mathsf{A}}}),{\color[rgb]{.5,.5,.5}{\mathsf{C}}})=1]}$
$\displaystyle\leq{\mathsf{negl}}(\lambda).$ (12)

Then, for any QPT $\mathpzc{B}$, we have

$\mathsf{TD}(\widetilde{\mathcal{Z}}_{\lambda}^{\mathpzc{B}}(0),\widetilde{\mathcal{Z}}_{\lambda}^{\mathpzc{B}}(1))\leq{\mathsf{negl}}(\lambda).$

###### Proof.

We first define the following event $\mathtt{Forge}$.

$\mathtt{Forge}$:

For $(x^{\prime},\sigma^{\prime})$ output by $\mathpzc{B}$ in
$\widetilde{\mathcal{Z}}^{\mathpzc{B}}_{\lambda}(b)$, the followings are
satisfied.

  * •

$x_{i}\neq x_{i}^{\prime}$ holds for some $i$ such that $\theta_{i}=0$.

  * •

$\mathsf{Vrfy}(\mathsf{vk},x^{\prime},\sigma^{\prime})=\top$ holds.

We also define the event $\mathtt{Forge}^{*}$ in the same way as
$\mathtt{Forge}$ except that $\mathpzc{B}$ is initialized with
$\mathcal{Z}_{\lambda}(\mathsf{vk},0^{\ell_{\mathsf{sigk}}},\theta,b\oplus\bigoplus_{i:\theta_{i}=1}x_{i},\ket{\psi})$.
From Equation 11, we have
$\Pr[\mathtt{Forge}]=\Pr[\mathtt{Forge}^{*}]+{\mathsf{negl}}(\lambda)$. Also,
from the one-time unforgeability for BB84 states, we have
$\Pr[\mathtt{Forge}^{*}]={\mathsf{negl}}(\lambda)$. Thus, we obtain
$\Pr[\mathtt{Forge}]={\mathsf{negl}}(\lambda)$.

We define $\widehat{\mathcal{Z}}_{\lambda}^{\mathpzc{B}}(b)$ as the experiment
defined in the same way as
$\widetilde{\mathcal{Z}}_{\lambda}^{\mathpzc{B}}(b)$ except that the
experiment outputs the register ${\color[rgb]{.5,.5,.5}{\mathsf{B}}}$ if and
only if $x_{i}=x^{\prime}_{i}$ holds for all $i$ such that $\theta_{i}=0$.
Since $\Pr[\mathtt{Forge}]={\mathsf{negl}}(\lambda)$, if
$\mathsf{Vrfy}(\mathsf{vk},x^{\prime},\sigma^{\prime})=\top$ holds, then
$x_{i}=x_{i}^{\prime}$ holds for all $i$ such that $\theta_{i}=0$, except
negligible probability. Thus, we have

$\displaystyle\mathsf{TD}(\widetilde{\mathcal{Z}}_{\lambda}^{\mathpzc{B}}(0),\widetilde{\mathcal{Z}}_{\lambda}^{\mathpzc{B}}(1))\leq\mathsf{TD}(\widehat{\mathcal{Z}}_{\lambda}^{\mathpzc{B}}(0),\widehat{\mathcal{Z}}_{\lambda}^{\mathpzc{B}}(1))+{\mathsf{negl}}(\lambda).$
(13)

From Equation 12 and Lemma 4.1, we have
$\mathsf{TD}(\widetilde{\mathcal{Z}}_{\lambda}^{\mathpzc{B}}(0),\widetilde{\mathcal{Z}}_{\lambda}^{\mathpzc{B}}(1))={\mathsf{negl}}(\lambda)$.
This completes the proof. ∎

##  5 Instantiations

We can apply Lemma 4.3 to various cryptographic primitives.

###  5.1 Public-Key Encryption

First, we show how to apply Lemma 4.3 to PKE and obtain PKE with PVD.

#### Definition.

We define PKE with publicly verifiable deletion (PKE-PVD).

###### Definition 5.1 (PKE with Publicly Verifiable Deletion).

A PKE scheme with publicly verifiable deletion is a tuple of efficient
algorithms
$\mathsf{PKE}\textrm{-}\mathsf{PVD}=(\mathsf{Gen},\mathpzc{Enc},\mathpzc{Dec},\mathpzc{Del},\mathsf{Vrfy})$.

$\mathsf{Gen}(1^{\lambda})\rightarrow(\mathsf{pk},\mathsf{sk})$:

The key generation algorithm takes the security parameter $1^{\lambda}$ as
input and outputs a public key $\mathsf{pk}$ and a secret key $\mathsf{sk}$.

$\mathpzc{Enc}(\mathsf{pk},m)\rightarrow(\mathsf{vk},\mathpzc{ct})$:

The encryption algorithm takes $\mathsf{pk}$ and a plaintext $m\in\\{0,1\\}$
as input, and outputs a verification key $\mathsf{vk}$ and a ciphertext
$\mathpzc{ct}$.

$\mathpzc{Dec}(\mathsf{sk},\mathpzc{ct})\rightarrow m^{\prime}$:

The decryption algorithm takes $\mathsf{sk}$ and $\mathpzc{ct}$ as input, and
outputs a plaintext $m^{\prime}\in\mathcal{M}$ or $\bot$.

$\mathpzc{Del}(\mathpzc{ct})\rightarrow\mathsf{cert}$:

The deletion algorithm takes $\mathpzc{ct}$ as input and outputs a
certification $\mathsf{cert}$.

$\mathsf{Vrfy}(\mathsf{vk},\mathsf{cert})\rightarrow\top$ or $\bot$:

The verification algorithm is a deterministic algorithm that takes
$\mathsf{vk}$ and $\mathsf{cert}$ as input, and outputs $\top$ or $\bot$.

Decryption Correctness:

For any $m\in\mathcal{M}$, we have

$\displaystyle\Pr\left[m^{\prime}\neq m\
\middle|\begin{array}[]{ll}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{KeyGen}(1^{\lambda})\\\
(\mathsf{vk},\mathpzc{ct})\leftarrow\mathpzc{Enc}(\mathsf{pk},m)\\\
m^{\prime}\leftarrow\mathpzc{Dec}(\mathsf{sk},\mathpzc{ct})\end{array}\right]\leq{\mathsf{negl}}(\lambda).$
(17)

Verification Correctness:

For any $m\in\mathcal{M}$, we have

$\displaystyle\Pr\left[\mathsf{Vrfy}(\mathsf{vk},\mathsf{cert})=\bot\
\middle|\begin{array}[]{ll}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{KeyGen}(1^{\lambda})\\\
(\mathsf{vk},\mathpzc{ct})\leftarrow\mathpzc{Enc}(\mathsf{pk},m)\\\
\mathsf{cert}\leftarrow\mathpzc{Del}(\mathpzc{ct})\end{array}\right]\leq{\mathsf{negl}}(\lambda).$
(21)

Semantic Security:

For any QPT $\mathpzc{A}$, we have

$\displaystyle\absolutevalue{\Pr\left[\mathpzc{A}(\mathsf{pk},\mathsf{vk},\mathpzc{ct})=1\
\middle|\begin{array}[]{ll}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})\\\
(\mathsf{vk},\mathpzc{ct})\leftarrow\mathpzc{Enc}(\mathsf{pk},0)\end{array}\right]-\Pr\left[\mathpzc{A}(\mathsf{pk},\mathsf{vk},\mathpzc{ct}_{1})=1\
\middle|\begin{array}[]{ll}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{KeyGen}(1^{\lambda})\\\
(\mathsf{vk},\mathpzc{ct})\leftarrow\mathpzc{Enc}(\mathsf{pk},1)\end{array}\right]}={\mathsf{negl}}(\lambda).$
(26)

###### Definition 5.2 (Certified Deletion Security for PKE-PVD).

Let
$\mathsf{PKE}\textrm{-}\mathsf{PVD}=(\mathsf{Gen},\mathpzc{Enc},\mathpzc{Dec},\allowbreak\mathpzc{Del},\mathsf{Vrfy})$
be a PKE-PVD scheme. We consider the following security experiment
$\mathsf{Exp}_{\mathsf{PKE}\textrm{-}\mathsf{PVD},\mathpzc{A}}^{\mathsf{cert}\mbox{-}\mathsf{del}}(\lambda,b)$
against a QPT adversary $\mathpzc{A}$.

  1. 1.

The challenger computes
$(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})$, and sends
$\mathsf{pk}$ to $\mathpzc{A}$.

  2. 2.

The challenger computes
$(\mathsf{vk},\mathpzc{ct})\leftarrow\mathpzc{Enc}(\mathsf{pk},b)$, and sends
$\mathsf{vk}$ and $\mathpzc{ct}$ to $\mathpzc{A}$.

  3. 3.

At some point, $\mathpzc{A}$ sends $\mathsf{cert}$ and its internal state
$\rho$ to the challenger.

  4. 4.

The challenger computes $\mathsf{Vrfy}(\mathsf{vk},\mathsf{cert})$. If the
outcome is $\top$, the challenger outputs $\rho$ and otherwise outputs $\bot$.

We say that $\mathsf{PKE}\textrm{-}\mathsf{PVD}$ satisfies certified deletion
security if for any QPT $\mathpzc{A}$, it holds that

$\displaystyle\mathsf{TD}(\mathsf{Exp}_{\mathsf{PKE}\textrm{-}\mathsf{PVD},\mathpzc{A}}^{\mathsf{cert}\mbox{-}\mathsf{del}}(\lambda,0),\mathsf{Exp}_{\mathsf{PKE}\textrm{-}\mathsf{PVD},\mathpzc{A}}^{\mathsf{cert}\mbox{-}\mathsf{del}}(\lambda,1))\leq{\mathsf{negl}}(\lambda).$
(27)

######  Remark 5.3.

We define PKE-PVD and the certified deletion security for it as the plaintext
space of PKE-PVD is $\\{0,1\\}$ by default. We can generalize them into one
for the plaintext space $\\{0,1\\}^{\ell}$ for any polynomial $\ell$. Also,
such a multi-bit plaintext PKE-PVD can be constructed from a single-bit
plaintext PKE-PVD by the standard hybrid argument.

#### Construction.

We construct a PKE-PVD scheme
$\mathsf{PKE}\textrm{-}\mathsf{PVD}=(\mathsf{Gen},\mathpzc{Enc},\mathpzc{Dec},\mathpzc{Del},\mathsf{Vrfy})$
for the plaintext space $\\{0,1\\}$. The building blocks are as follows.

  * •

A public-key encryption scheme
$\mathsf{PKE}=\mathsf{PKE}.(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$.

  * •

A deterministic signature
$\mathsf{SIG}=\mathsf{SIG}.(\mathsf{Gen},\mathsf{Sign},\mathsf{Vrfy})$.

$\mathsf{Gen}(1^{\lambda})$:

  * •

Output
$(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{PKE}.\mathsf{Gen}(1^{\lambda})$.

$\mathpzc{Enc}(\mathsf{pk},m\in\\{0,1\\})$:

  * •

Generate $x,\theta\leftarrow\\{0,1\\}^{\lambda}$ and generate
$(\mathsf{vk},\mathsf{sigk})\leftarrow\mathsf{SIG}.\mathsf{Gen}(1^{\lambda})$.
Generate a quantum state $\ket{\psi}$ by applying the map $\ket{m}\ket{0\ldots
0}\rightarrow\ket{m}\ket{\mathsf{SIG}.\mathsf{Sign}(\mathsf{sigk},m)}$ to
$\ket{x}_{\theta}\otimes\ket{0\ldots 0}$.

  * •

Generate
$\mathsf{pke}.\mathsf{ct}\leftarrow\mathsf{PKE}.\mathsf{Enc}(\mathsf{pk},(\mathsf{sigk},\theta,m\oplus\bigoplus_{i:\theta_{i}=1}x_{i}))$.

  * •

Output $\mathsf{vk}$ and
$\mathpzc{ct}:=(\ket{\psi},\mathsf{pke}.\mathsf{ct})$.

$\mathpzc{Dec}(\mathsf{sk},\mathpzc{ct})$:

  * •

Parse $\mathpzc{ct}$ into a quantum states $\rho$ and classical bit string
$\mathsf{pke}.\mathsf{ct}$.

  * •

Compute
$(\mathsf{sigk},\theta,\beta)\leftarrow\mathsf{PKE}.\mathsf{Dec}(\mathsf{sk},\mathsf{pke}.\mathsf{ct})$.

  * •

Apply the map $\ket{m}\ket{0\ldots
0}\rightarrow\ket{m}\ket{\mathsf{SIG}.\mathsf{Sign}(\mathsf{sigk},m)}$ to
$\rho$, measure the first $\lambda$ qubits of the resulting state in Hadamard
basis, and obtain $\bar{x}$.

  * •

Output $m\leftarrow\beta\oplus\bigoplus_{i:\theta_{i}=1}\bar{x}_{i}$.

$\mathpzc{Del}(\mathpzc{ct})$:

  * •

Parse $\mathpzc{ct}$ into a quantum state $\rho$ and a classical string
$\mathsf{pke}.\mathsf{ct}$.

  * •

Measure $\rho$ in the computational basis and obtain $x^{\prime}$ and
$\sigma^{\prime}$.

  * •

Output $(x^{\prime},\sigma^{\prime})$.

$\mathsf{Vrfy}(\mathsf{vk},\mathsf{cert})$:

  * •

Parse $(z^{\prime},\sigma^{\prime})\leftarrow\mathsf{cert}$.

  * •

Output the result of
$\mathsf{SIG}.\mathsf{Vrfy}(\mathsf{vk},z^{\prime},\sigma^{\prime})$.

We see that $\mathsf{PKE}\textrm{-}\mathsf{PVD}$ satisfies decryption
correctness and verification correctness if $\mathsf{SIG}$ and $\mathsf{PKE}$
satisfy their correctness notions. Also, the semantic security of
$\mathsf{PKE}\textrm{-}\mathsf{PVD}$ immediately follows from that of
$\mathsf{PKE}$. Also, we have the following theorem.

###### Theorem 5.4.

Assume $\mathsf{SIG}$ satisfies one-time unforgeability for BB84 states and
$\mathsf{PKE}$ satisfies semantic security. Then,
$\mathsf{PKE}\textrm{-}\mathsf{PVD}$ satisfies certified deletion security.

###### Proof.

We define
$\mathcal{Z}_{\lambda}(\mathsf{vk},\mathsf{sigk},\theta,\beta,{\color[rgb]{.5,.5,.5}{\mathsf{A}}})$
be an efficient quantum process such that it generates
$(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})$ and outputs
$(\mathsf{pk},\mathsf{vk},\mathsf{Enc}(\mathsf{pk},(\mathsf{sigk},\theta,\beta))$.
Then, from the semantic security of $\mathsf{PKE}$, for any QPT $\mathpzc{A}$,
key pair $(\mathsf{vk},\mathsf{sk})$ of $\mathsf{SIG}$,
$\theta\in\\{0,1\\}^{\lambda}$, $\beta\in\\{0,1\\}$, and an efficiently
samplable state $\ket{\psi}^{{\color[rgb]{.5,.5,.5}{\mathsf{A,C}}}}$ on
registers ${\color[rgb]{.5,.5,.5}{\mathsf{A}}}$ and
${\color[rgb]{.5,.5,.5}{\mathsf{C}}}$, we have

$\displaystyle\absolutevalue{\Pr[\mathpzc{A}(\mathcal{Z}_{\lambda}(\mathsf{vk},\mathsf{sigk},\theta,\beta,{\color[rgb]{.5,.5,.5}{\mathsf{A}}}),{\color[rgb]{.5,.5,.5}{\mathsf{C}}})=1]-\Pr[\mathpzc{A}(\mathcal{Z}_{\lambda}(\mathsf{vk},0^{\ell_{\mathsf{sigk}}},\theta,\beta,{\color[rgb]{.5,.5,.5}{\mathsf{A}}}),{\color[rgb]{.5,.5,.5}{\mathsf{C}}})=1]}$
$\displaystyle\leq{\mathsf{negl}}(\lambda),\textrm{~{}~{}~{}~{}and}$ (28)
$\displaystyle\
\absolutevalue{\Pr[\mathpzc{A}(\mathcal{Z}_{\lambda}(\mathsf{vk},\mathsf{sigk},\theta,\beta,{\color[rgb]{.5,.5,.5}{\mathsf{A}}}),{\color[rgb]{.5,.5,.5}{\mathsf{C}}})=1]-\Pr[\mathpzc{A}(\mathcal{Z}_{\lambda}(\mathsf{vk},\mathsf{sigk},0^{\lambda},\beta,{\color[rgb]{.5,.5,.5}{\mathsf{A}}}),{\color[rgb]{.5,.5,.5}{\mathsf{C}}})=1]}$
$\displaystyle\leq{\mathsf{negl}}(\lambda).$ (29)

Then, the certified deletion security of $\mathsf{PKE}\textrm{-}\mathsf{PVD}$
follows from Lemma 4.3. ∎

In Section 3, we show that a deterministic signature scheme with one-time
unforgeability for BB84 states is implied by OWF that is implied by a PKE
scheme. Thus, we obtain the following theorem.

###### Theorem 5.5.

Assume that there exists PKE. Then, there exists PKE-PVD.

###  5.2 Other Primitives

By combining Lemma 4.3 with other types of primitives instead of PKE, we
immediately obtain them with publicly verifiable deletion. That is, we
instantiate $\mathcal{Z}_{\lambda}$ in Lemma 4.3 with these primitives.
Formally, we have the following theorem.

###### Theorem 5.6.

If there exists

$Z^{\prime}\in\\{\textrm{SKE, COM, PKE, ABE, QFHE, TRE}\\},$

then, there exists $Z^{\prime}$ with publicly verifiable deletion. If there
exist WE and one-way functions, then there exists WE with publicly verifiable
deletion.

######  Remark 5.7.

We additionally assume one-way functions for the case of WE since WE is
unlikely to imply one-way functions while any of $Z^{\prime}\in\\{\textrm{SKE,
COM, PKE, ABE, QFHE, TRE}\\}$ implies them.

We omit the definitions of these primitives (with publicly verifiable
deletion) and refer the reader to [BK22, BKP23] for them.101010The definitions
in [BK22] only consider privately verifiable deletion, but it is
straightforward to extend them to ones with publicly verifiable deletion.

##  6 Making Assumptions Minimal

In Section 5, we show that $Z\in\\{\textrm{SKE, COM, PKE, ABE, QFHE, TRE,
WE}\\}$ (and one-way functions in the case of $Z=\text{WE}$) imply $Z$ with
publicly verifiable deletion. However, $Z$ with publicly verifiable deletion
does not seem to imply either of plain (classical) $Z$ or one-way functions in
general. In this section, we explain how to weaken the assumptions to minimal
ones implied by $Z$ with publicly verifiable deletion.

First, we observe that our compiler works even if we start with
$Z\in\\{\textrm{SKE, COM, PKE, ABE, QFHE, TRE, WE}\\}$ that has quantum
encryption and decryption (or committing) algorithms. Second, we observe our
compiler works even if the underlying digital signature scheme has a quantum
key generation algorithm since the quantum encryption algorithm runs it.
Moreover, such a digital signature scheme with a quantum key generation
algorithm that satisfies one-time security for BB84 states can be constructed
from hard quantum planted problems for $\mathsf{NP}$ defined below.

###### Definition 6.1 (Hard Quantum Planted Problem for $\mathsf{NP}$).

A quantum polynomial-time algorithm $\mathpzc{G}$ is a sampler for an
$\mathsf{NP}$ relation
$\mathcal{R}\subseteq\\{0,1\\}^{\ast}\times\\{0,1\\}^{\ast}$ if, for every
$n$, $\mathpzc{G}(1^{n})$ outputs a pair $(x,w)$ such that
$(x,w)\in\mathcal{R}$ with probability $1$. We say that the quantum planted
problem corresponding to $(\mathpzc{G},\mathcal{R})$ is hard if, for every QPT
$\mathpzc{A}$, it holds that

$\Pr[(x,\mathpzc{A}(x))\in\mathcal{R}\mid(x,w)\leftarrow\mathpzc{G}(1^{n})]\leq{\mathsf{negl}}(n).$

It is clear that the construction in Section 3 works using hard quantum
planted problems for $\mathsf{NP}$ instead of one-way functions where input-
output pairs of the one-way function are replaced with witness-instance pairs
of the $\mathsf{NP}$ problem if we allow the key generation algorithm of the
signature scheme to be quantum. Combining the above observations, we obtain
the following theorem.

###### Theorem 6.2.

Assume that there exists

$Z\in\\{\textrm{SKE, COM, PKE, ABE, QFHE, TRE, WE}\\}$

with quantum encryption and decryption (or committing) algorithms and hard
quantum planted problems for $\mathsf{NP}$. Then, there exists $Z$ with
publicly verifiable deletion.

The assumption in the above theorem is minimal since

  1. 1.

$Z$ with quantum encryption and decryption (or committing) algorithms is
immediately implied by $Z$ with publicly verifiable deletion by simply
ignoring the deletion and verification algorithms, and

  2. 2.

Hard quantum planted problems for $\mathsf{NP}$ are implied by $Z$ with
publicly verifiable deletion by regarding the verification key and certificate
as instance and certificate, respectively.

######  Remark 6.3.

In the second item above, we assume that the verification algorithm of $Z$
with publicly verifiable deletion is a classical deterministic algorithm. If
it is allowed to be a quantum algorithm, we need to consider hard quantum
planted problems for $\mathsf{QCMA}$ instead of $\mathsf{NP}$. The
construction in Section 3 works with such problems if we allow the
verification algorithm to be quantum. Thus, the minimality of the assumption
holds in this setting as well.

## References

  * [AGKZ20] Ryan Amos, Marios Georgiou, Aggelos Kiayias, and Mark Zhandry.  One-shot signatures and applications to hybrid quantum/classical authentication.  In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, 52nd ACM STOC, pages 255–268. ACM Press, June 2020.
  * [AKN+23] Shweta Agrawal, Fuyuki Kitagawa, Ryo Nishimaki, Shota Yamada, and Takashi Yamakawa.  Public key encryption with secure key leasing.  IACR Cryptol. ePrint Arch., page 264, 2023.  Eurocrypt 2023 (to appear).
  * [AL21] Prabhanjan Ananth and Rolando L. La Placa.  Secure software leasing.  In Anne Canteaut and François-Xavier Standaert, editors, EUROCRYPT 2021, Part II, volume 12697 of LNCS, pages 501–530. Springer, Heidelberg, October 2021.
  * [ALL+21] Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry, and Ruizhe Zhang.  New approaches for quantum copy-protection.  In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part I, volume 12825 of LNCS, pages 526–555, Virtual Event, August 2021. Springer, Heidelberg.
  * [APV23] Prabhanjan Ananth, Alexander Poremba, and Vinod Vaikuntanathan.  Revocable cryptography from learning with errors.  Cryptology ePrint Archive, Report 2023/325, 2023.  https://eprint.iacr.org/2023/325.
  * [BGG+23] James Bartusek, Sanjam Garg, Vipul Goyal, Dakshita Khurana, Giulio Malavolta, Justin Raizes, and Bhaskar Roberts.  Obfuscation and outsourced computation with certified deletion.  Cryptology ePrint Archive, Report 2023/265, 2023.  https://eprint.iacr.org/2023/265.
  * [BGI+12] Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang.  On the (im)possibility of obfuscating programs.  Journal of the ACM, 59(2):6:1–6:48, 2012.
  * [BI20] Anne Broadbent and Rabib Islam.  Quantum encryption with certified deletion.  In Rafael Pass and Krzysztof Pietrzak, editors, TCC 2020, Part III, volume 12552 of LNCS, pages 92–122. Springer, Heidelberg, November 2020.
  * [BJL+21] Anne Broadbent, Stacey Jeffery, Sébastien Lord, Supartha Podder, and Aarthi Sundaram.  Secure software leasing without assumptions.  In Kobbi Nissim and Brent Waters, editors, TCC 2021, Part I, volume 13042 of LNCS, pages 90–120. Springer, Heidelberg, November 2021\.
  * [BK22] James Bartusek and Dakshita Khurana.  Cryptography with certified deletion.  Cryptology ePrint Archive, Report 2022/1178, 2022.  https://eprint.iacr.org/2022/1178.
  * [BKP23] James Bartusek, Dakshita Khurana, and Alexander Poremba.  Publicly-verifiable deletion via target-collapsing functions.  IACR Cryptol. ePrint Arch., page 370, 2023.
  * [CLLZ21] Andrea Coladangelo, Jiahui Liu, Qipeng Liu, and Mark Zhandry.  Hidden cosets and applications to unclonable cryptography.  In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part I, volume 12825 of LNCS, pages 556–584, Virtual Event, August 2021. Springer, Heidelberg.
  * [CMP20] Andrea Coladangelo, Christian Majenz, and Alexander Poremba.  Quantum copy-protection of compute-and-compare programs in the quantum random oracle model.  Cryptology ePrint Archive, Report 2020/1194, 2020.  https://eprint.iacr.org/2020/1194.
  * [GKP+13] Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, and Nickolai Zeldovich.  How to run turing machines on encrypted data.  In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages 536–553. Springer, Heidelberg, August 2013.
  * [HKM+23] Taiga Hiroka, Fuyuki Kitagawa, Tomoyuki Morimae, Ryo Nishimaki, Tapas Pal, and Takashi Yamakawa.  Certified everlasting secure collusion-resistant functional encryption, and more.  Cryptology ePrint Archive, Report 2023/236, 2023.  https://eprint.iacr.org/2023/236.
  * [HMNY21] Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki, and Takashi Yamakawa.  Quantum encryption with certified deletion, revisited: Public key, attribute-based, and classical communication.  In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT 2021, Part I, volume 13090 of LNCS, pages 606–636. Springer, Heidelberg, December 2021.
  * [HMNY22] Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki, and Takashi Yamakawa.  Certified everlasting zero-knowledge proof for QMA.  In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part I, volume 13507 of LNCS, pages 239–268. Springer, Heidelberg, August 2022.
  * [HMY22] Minki Hhan, Tomoyuki Morimae, and Takashi Yamakawa.  From the hardness of detecting superpositions to cryptography: Quantum public key encryption and commitments.  Cryptology ePrint Archive, Report 2022/1375, 2022.  https://eprint.iacr.org/2022/1375.
  * [KN22] Fuyuki Kitagawa and Ryo Nishimaki.  Functional encryption with secure key leasing.  In Shweta Agrawal and Dongdai Lin, editors, ASIACRYPT 2022, Part IV, volume 13794 of LNCS, pages 569–598. Springer, Heidelberg, December 2022.
  * [KNY21] Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa.  Secure software leasing from standard assumptions.  In Kobbi Nissim and Brent Waters, editors, TCC 2021, Part I, volume 13042 of LNCS, pages 31–61. Springer, Heidelberg, November 2021\.
  * [Lam79] Leslie Lamport.  Constructing digital signatures from a one-way function.  Technical Report SRI-CSL-98, SRI International Computer Science Laboratory, October 1979.
  * [MU10] Jörn Müller-Quade and Dominique Unruh.  Long-term security and universal composability.  Journal of Cryptology, 23(4):594–671, October 2010.
  * [Por23] Alexander Poremba.  Quantum proofs of deletion for learning with errors.  In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 of LIPIcs, pages 90:1–90:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
  * [Unr15] Dominique Unruh.  Revocable quantum timed-release encryption.  J. ACM, 62(6):49:1–49:76, 2015.