# Unclonable Non-Interactive Zero-Knowledge

Ruta Jawale University of Illinois at Urbana-Champaign, USA.
<EMAIL_ADDRESS>Dakshita Khurana∗

###### Abstract

A non-interactive ZK (NIZK) proof enables verification of NP statements
without revealing secrets about them. However, an adversary that obtains a
NIZK proof may be able to clone this proof and distribute arbitrarily many
copies of it to various entities: this is inevitable for any proof that takes
the form of a classical string. In this paper, we ask whether it is possible
to rely on quantum information in order to build NIZK proof systems that are
impossible to clone.

We define and construct unclonable non-interactive zero-knowledge proofs (of
knowledge) for NP. Besides satisfying the zero-knowledge and proof of
knowledge properties, these proofs additionally satisfy unclonability. Very
roughly, this ensures that no adversary can split an honestly generated proof
of membership of an instance $x$ in an NP language $\mathcal{L}$ and
distribute copies to multiple entities that all obtain accepting proofs of
membership of $x$ in $\mathcal{L}$. Our result has applications to unclonable
signatures of knowledge, which we define and construct in this work; these
_non-interactively_ prevent replay attacks.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Results
      1. 1.1.1 Definitional Contributions
      2. 1.1.2 Realizations of Unclonable NIZK, and Relationship with Quantum Money
      3. 1.1.3 Applications
    2. 1.2 Related Works
  2. 2 Technical Overview
    1. 2.1 Unclonable Extractable NIZKs in the CRS Model
    2. 2.2 Unclonable Extractable NIZK in the QROM
    3. 2.3 Unclonable NIZKs imply Quantum Money Mini-Scheme
    4. 2.4 Unclonable Signatures of Knowledge
  3. 3 Preliminaries
    1. 3.1 Post-Quantum Commitments and Encryption
    2. 3.2 Sigma protocols
    3. 3.3 NIZKs in the CRS model
    4. 3.4 NIZKs in the QRO model
    5. 3.5 Quantum Money
    6. 3.6 Quantum Signature of Knowledge
  4. 4 Unclonable Non-Interactive Zero-Knowledge in the CRS Model
    1. 4.1 Simulation-Extractable Definition
    2. 4.2 Unclonability Definitions
    3. 4.3 Unclonable NIZK Implies Public-Key Quantum Money Mini-Scheme
    4. 4.4 Construction and Analysis of Unclonable NIZK from Public-Key Quantum Money
  5. 5 Unclonable NIZK in the Quantum Random Oracle Model
    1. 5.1 A Modified Sigma Protocol
    2. 5.2 Unclonability Definitions
    3. 5.3 Unclonable NIZK Implies Public-Key Quantum Money in QROM
    4. 5.4 Construction and Analysis
  6. 6 Unclonable Signatures of Knowledge
    1. 6.1 Definition
    2. 6.2 Construction
    3. 6.3 Revocable Anonymous Credentials
  7. A A Reduction Between Unclonability Definitions
    1. A.1 In the CRS model
    2. A.2 In the QRO model

##  1 Introduction

Zero-knowledge (ZK) [GMR89] proofs allow a prover to convince a verifier about
the truth of an (NP) statement, without revealing secrets about it. These are
among the most widely used cryptographic primitives, with a rich history of
study.

##### Enhancing Zero-knowledge.

ZK proofs for NP are typically defined via the simulation paradigm. A
simulator is a polynomial-time algorithm that mimics the interaction of an
adversarial verifier with an honest prover, given only the statement, i.e.,
$x\in{\mathcal{L}}$, for an instance $x$ of an $\mathsf{NP}$ language
${\mathcal{L}}$. A protocol satisfies zero-knowledge if it admits a simulator
that generates a view for the verifier, which is indistinguishable from the
real view generated by an honest prover. This captures the intuition that any
information obtained by a verifier upon observing an honestly generated proof,
could have been generated by the verifier “on its own” by running the
simulator.

Despite being widely useful and popular, there are desirable properties of
proof systems that (standard) simulation-based security does not capture. For
example, consider (distributions over) instances $x$ of an NP language
${\mathcal{L}}$ where it is hard to find an NP witness $w$ corresponding to a
given instance $x$. In an “ideal” world, given just the description of one
such NP statement $x\in{\mathcal{L}}$, it is difficult for an adversary to
find an NP witness $w$, and therefore to output any proofs of membership of
$x\in{\mathcal{L}}$. And yet, upon obtaining a single proof of membership of
$x\in{\mathcal{L}}$, it may suddenly become feasible for an adversary to make
many copies of this proof, thereby generating several correct proofs of
membership of $x\in{\mathcal{L}}$.

Unfortunately, this attack is inevitable for classical non-interactive proofs:
given any proof string, an adversary can always make multiple copies of it.
And yet, there is hope to prevent such an attack quantumly, by relying on the
no-cloning principle.

Indeed, a recent series of exciting works have combined cryptography with the
no-cloning principle to develop quantum money [Wie83, AC13, FGH+12, Zha19a,
Kan18], quantum tokens for digital signatures [BS16], quantum copy-protection
[Aar09, AP21, ALL+21, CLLZ21], unclonable encryption [Got03, BL20, AK21,
MST21, AKL+22], unclonable decryption [GZ20], one-out-of-many unclonable
security [KN23], and more. In this work, we combine zero-knowledge and
unclonability to address a question first posed by Aaronson [Aar09]:

_Can we construct unclonable quantum proofs?
How do these proofs relate to quantum money or copy-protection?_

###  1.1 Our Results

We define and construct unclonable non-interactive zero-knowledge proofs of
knowledge (NIZKPoK). We obtain a construction in the common reference string
(CRS) model, as well as one in the quantum(-accessible) random oracle model
(QROM). The CRS model allows a trusted third-party to set up a structured
string that is provided to both the prover and verifier. On the other hand,
the QROM allows both parties quantum access to a truly random function
${\mathcal{O}}$.

In what follows, we describe our contributions in more detail.

####  1.1.1 Definitional Contributions

Before discussing how we formalize the concept of unclonability for NIZKs, it
will be helpful to define hard distributions over NP instance-witness pairs.

##### Hard Distributions over Instance-Witness Pairs.

Informally, an efficiently samplable distribution over instance-witness pairs
of a language ${\mathcal{L}}$ is a “hard” distribution if given an instance
sampled randomly from this distribution, it is hard to find a witness. Then,
unclonable security requires that no adversary given an instance $x$ sampled
randomly from the distribution, together with an honestly generated proof, can
output two accepting proofs of membership of $x\in{\mathcal{L}}$.

More specifically, a hard distribution $({\mathcal{X}},{\mathcal{W}})$ over
$R_{{\mathcal{L}}}$ satisfies the following: for any polynomial-sized
(quantum) circuit family $\\{C_{\lambda}\\}_{\lambda\in\mathbb{N}}$,

$\Pr_{(x,w)\leftarrow({\mathcal{X}}_{\lambda},{\mathcal{W}}_{\lambda})}[C_{\lambda}(x)\in
R_{{\mathcal{L}}}(x)]\leq\mathsf{negl}(\lambda).$

For the sake of simplifying our subsequent discussions and definitions, let us
fix a $\mathsf{NP}$ language ${\mathcal{L}}$ with corresponding relation
${\mathcal{R}}$. Let $({\mathcal{X}},{\mathcal{W}})$ be some hard distribution
over ${\mathcal{R}}$.

##### A Weaker Definition: Unclonable Security.

For NIZKs satisfying standard completeness, soundness and ZK, we define a
simple, natural variant of unclonable security as follows. Informally, a proof
system satisfies unclonable security if, given an honest proof for an instance
and witness pair $(x,w)$ sampled from a hard distribution
$({\mathcal{X}},{\mathcal{W}})$, no adversary can produce two proofs that
verify with respect to $x$ except with negligible probability.

######  Definition 1.1.

(Unclonable Security of NIZK). A NIZK proof
$(\mathsf{Setup},\mathsf{Prove},\mathsf{Verify})$ satisfies unclonable
security if for every language $\mathcal{L}$ and every hard distribution
$(\mathcal{X},\mathcal{W})$ over $R_{\mathcal{L}}$, for every poly-sized
circuit family $\\{C_{\lambda}\\}_{\lambda\in\mathbb{N}}$,

$\Pr_{(x,w)\leftarrow(\mathcal{X}_{\lambda},\mathcal{W}_{\lambda})}\Bigg{[}\mathsf{Verify}(\mathsf{crs},x,\pi_{1})=1\bigwedge\mathsf{Verify}(\mathsf{crs},x,\pi_{2})=1\Bigg{|}\begin{subarray}{c}\mathsf{crs}\leftarrow\mathsf{Setup}(1^{\lambda})\\\
\pi\leftarrow\mathsf{Prove}(\mathsf{crs},x,w)\\\ \pi_{1},\pi_{2}\leftarrow
C_{\lambda}(x,\pi)\end{subarray}\Bigg{]}\leq\mathsf{negl}(\lambda).\vspace{-1mm}$

In the definition above, we aim to capture the intuition that one of the two
proofs output by the adversary can be the honest proof they received, but the
adversary cannot output any other correct proof for the same statement. Of
course, such a proof is easy to generate if the adversary is able to find the
witness $w$ for $x$, which is exactly why we require hardness of the
distribution $({\mathcal{X}},{\mathcal{W}})$ to make the definition non-
trivial.

We also remark that unclonable security of proofs necessitates that the proof
$\pi$ keep hidden any witnesses $w$ certifying membership of $x$ in
${\mathcal{L}}$, as otherwise an adversary can always clone the proof $\pi$ by
generating (from scratch) another proof for $x$ given the witness $w$.

##### A Stronger Definition: Unclonable Extractability.

We can further strengthen the definition above to require that any adversary
generating two (or more) accepting proofs of membership of $x\in{\mathcal{L}}$
given a single proof, must have generated one of the two proofs “from scratch”
and must therefore “know” a valid witness $w$ for $x$. This will remove the
need to refer to hard languages.

In more detail, we will say that a proof system satisfies unclonable
extractability if, from any adversary ${\mathcal{A}}$ that on input a single
proof of membership of $x\in{\mathcal{L}}$ outputs two proofs for $x$, then we
can extract a valid witness $w$ from ${\mathcal{A}}$ for at least one of these
statements with high probability. Our (still, simplified) definition of
unclonable extractability is as follows.

######  Definition 1.2 (Unclonable Extractability.).

A proof $(\mathsf{Setup},\mathsf{Prove},\mathsf{Verify})$ satisfies unclonable
security there exists a QPT extractor $\mathcal{E}$ which is an oracle-aided
circuit such that for every language ${\mathcal{L}}$ with corresponding
relation ${\mathcal{R}}_{\mathcal{L}}$ and for every non-uniform polynomial-
time quantum adversary $\mathcal{A}$, for every instance-witness pair
$(x,w)\in{\mathcal{R}}_{\mathcal{L}}$ and $\lambda=\lambda(|x|)$, such that
there is a polynomial $p(\cdot)$ satisfying:

$\Pr[\mathsf{Verify}(\mathsf{crs},x,\pi_{1})=1\bigwedge\mathsf{Verify}(\mathsf{crs},x,\pi_{2})=1\Bigg{|}\begin{subarray}{c}\mathsf{crs}\leftarrow\mathsf{Setup}(1^{\lambda})\\\
\pi\leftarrow\mathsf{Prove}(\mathsf{crs},x,w)\\\
\pi_{1},\pi_{2}\leftarrow{\mathcal{A}}_{\lambda}(\mathsf{crs},x,\pi,z)\end{subarray}\Bigg{]}\geq\frac{1}{p(\lambda)},$

there is also a polynomial $q(\cdot)$ such that

$\Pr[(x,w_{\mathcal{A}})\in{\mathcal{R}}_{\mathcal{L}}|w_{\mathcal{A}}\leftarrow\mathcal{E}^{{\mathcal{A}}}(x)]\geq\frac{1}{q(\lambda)}.$

In fact, in the technical sections, we further generalize this definition to
consider a setting where the adversary obtains an even larger number (say
$k-1$) input proofs on instances $x_{1},\ldots,x_{k-1}$, and outputs $k$ or
more proofs. Then we require the extraction of an NP witness corresponding to
any proofs that attempt to “clone” honestly generated proofs (i.e. the
adversary outputs two or more proofs w.r.t. the same instance
$x_{i}\in\\{x_{1},\ldots,x_{k-1}\\}$). All our theorem statements hold w.r.t.
this general definition. Finally, we also consider definitions and
constructions in the quantum-accessible random oracle model (QROM); these are
natural generalizations of the definitions above, so we do not discuss them
here.

We also show that the latter definition of unclonable extractability implies
the former, i.e. unclonable security. Informally, this follows because the
extractor guaranteed by the definition of extractability is able to obtain a
witness $w$ for $x$ from any adversary, which contradicts hardness of the
distribution $({\mathcal{X}},{\mathcal{W}})$. We refer the reader to Appendix
A for a formal proof of this claim.

####  1.1.2 Realizations of Unclonable NIZK, and Relationship with Quantum
Money

We obtain realizations of unclonable NIZKs in both the common reference string
(CRS) and the quantum random oracle (QRO) models, assuming public-key quantum
money mini-scheme and other (post-quantum) standard assumptions. We summarize
these results below.

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

Assuming public-key quantum money mini-scheme, public-key encryption,
perfectly binding and computationally hiding commitments, and adaptively sound
NIZK proofs for $\mathsf{NP}$, there exists an unclonable NIZKPoK scheme in
the CRS model.

######  Theorem 1.4 (Informal).

Assuming public-key quantum money mini-scheme and honest verifier zero-
knowledge proofs of knowledge (HVZKPoKs) for $\mathsf{NP}$, there exists an
unclonable NIZKPoK scheme in the QROM.

######  Theorem 1.5 (Informal).

Assuming public-key quantum money mini-scheme, public-key encryption, post-
quantum perfectly binding and computationally hiding commitments, and
simulation-sound NIZK proofs for $\mathsf{NP}$, there exists an unclonable
signature of knowledge in the CRS model.

##### Is Quantum Money necessary for Unclonable NIZKs?

Our work builds unclonable NIZKs for NP by relying on any (public-key) quantum
money scheme (mini-scheme), in conjuction with other assumptions such as NIZKs
for NP. Since constructions of public-key quantum money mini-scheme are only
known based on post-quantum indistinguishability obfuscation [AC13, Zha19b],
it is natural to wonder whether the reliance on quantum money is inherent. We
show that this is indeed the case, by proving that unclonable NIZKs in fact
imply public-key quantum money mini-scheme.

######  Theorem 1.6 (Informal).

Unclonable NIZKs for NP imply public-key quantum money mini-scheme.

####  1.1.3 Applications

Unclonable Signatures of Knowledge. A (classical) signature scheme asserts
that a message $m$ has been signed on behalf of a public key $\mathsf{pk}$.
However, in order for this signature to be authenticated, the public key
$\mathsf{pk}$ must be proven trustworthy through a certification chain rooted
at a trusted public key $\mathsf{PK}$. However, as [CL06] argue, this reveals
too much information; it should be sufficient for the recipient to only know
that _there exists_ a public key $\mathsf{pk}$ with a chain of trust from
$\mathsf{PK}$. To solve this problem, [CL06] propose _signatures of knowledge_
which allow a signer to sign _on behalf of an instance $x$ of an
$\mathsf{NP}$-hard language_ without revealing its corresponding witness $w$.
Such signatures provide an anonymity guarantee by hiding the $\mathsf{pk}$ of
the sender.

While this is ideal for many applications, anonymity presents the following
downside: a receiver cannot determine whether they were the intended recipient
of this signature. In particular, anonymous signatures are more susceptible to
_replay attacks_. Replay attacks are a form of passive attack whereby an
adversary observes a signature and retains a copy. The adversary then
leverages this signature, either at a later point in time or to a different
party, to impersonate the original signer. The privacy and financial
consequences of replay attacks are steep. They can lead to data breach attacks
which cost millions of dollars annually and world-wide [IBM23].

In this work, we construct a signature of knowledge scheme which is the first
_non-interactive_ signature in the CRS model that is _naturally secure against
replay attacks_. Non-interactive, replay attack secure signatures have seen a
lot of recent interest including a line of works in the bounded quantum
storage model [BS23b] and the quantum random oracle model [BS23a]. Our
construction is in the CRS model and relies on the hardness of $\mathsf{NP}$
problems, plausible cryptographic assumptions, and the axioms of quantum
mechanics. We accomplish this by defining _unclonable signatures of knowledge_
: if an adversary, given a signature of a message $m$ with respect to an
instance $x$, can produce two signatures for $m$ which verify with respect to
the same instance $x$, then our extractor is able to extract a witness for
$x$.

Our construction involves showing that an existing compiler can be augmented
using unclonable NIZKs to construct unclonable signatures of knowledge. The
authors of [CL06] construct signatures of knowledge from CPA secure dense
cryptosystems [SP92, SCP00] and simulation-sound NIZKs for $\mathsf{NP}$
[Sah99, SCO+01]. Signatures of knowledge are signature schemes in the CRS
model for which we associate an instance $x$ in a language ${\mathcal{L}}$.
This signature is simulatable, so there exists a simulator which can create
valid signatures without knowledge of a witness for $x$. Additionally, the
signature is extractable which means there is an extractor which is given a
trapdoor for the CRS and a signature, and is able to produce a witness for
$x$. We show that, by switching the simulation-sound NIZKs for unclonable
simulation-extractable NIZKs (and slightly modifying the compiler), we can
construct unclonable signatures of knowledge.

Relationship with Revocation. A recent exciting line of work obtains
_certified deletion_ for time-lock puzzles [Unr14], non-local games [FM18],
information-theoretic proofs of deletion with partial security [CW19],
encryption schemes [BI20, BK23], device-independent security of one-time pad
encryption with certified deletion [KT20], public-key encryption with
certified deletion [HMNY21], commitments and zero-knowledge with certified
everlasting hiding [HMNY22], and fully-homomorphic encryption with certified
deletion [Por22, BK23, BKP23, BGG+23]. While certified everlasting deletion of
secrets has been explored in the context of interactive zero-knowledge proofs
[HMNY22], there are no existing proposals for non-interactive ZK satisfying
variants of certified deletion. Our work provides a pathway to building such
proofs.

In this work, we construct a quantum _revocable anonymous credentials_
protocol by way of the hardness of $\mathsf{NP}$ problems, plausible
cryptographic assumptions, and the axioms of quantum mechanics. Our work
follows a line of work on (classical) revocation for anonymous credentials
schemes [BCC+09, CKS10, AN11].

In particular, our construction involves noting that NIZK proof systems that
are unclonable can also be viewed as supporting a form of certified
deletion/revocation, where in order to delete, an adversary must simply return
the entire proof. In other words, the (quantum) certificate of deletion is the
proof itself, and this certificate can be verified by running the NIZK
verification procedure on the proof. The unclonability guarantee implies that
an adversary cannot keep with itself or later have the ability to generate
another proof for the same instance $x$. In the other direction, in order to
offer certifiable deletion, a NIZK must necessarily be unclonable. To see why,
note that if there was an adversary who could clone the NIZK, we could use
this adversary to obtain two copies, and provably delete one of them. Even
though the challenger for the certifiable deletion game would be convinced
that its proof was deleted, we would still be left with another correct proof.

###  1.2 Related Works

This work was built upon the foundations of and novel concepts introduced by
prior literature. We will briefly touch upon some notable such results in this
section.

Unclonable Encryptions. _Unclonable encryption_ [Got03, BL20, AK21, MST21,
AKL+22] imagines an interaction between three parties in which one party
receives a quantum ciphertext and splits this ciphertext in some manner
between the two remaining parties. At some later point, the key of the
encryption scheme is revealed, yet both parties should not be able to
simultaneouly recover the underlying message. While our proof systems share
the ideology of unclonability, we do not have a similar game-based definition
of security. This is mainly due to proof systems offering more structure which
can take advantage of to express unclonability in terms of simulators and
extractors.

Signature Tokens. Prior work [BS17] defines and constructs _signature tokens_
which are signatures which involve a quantum signing token which can only be
used once before it becomes inert. The setting they consider is where a client
wishes to delegate the signing process to a server, but does not wish the
server to be able to sign more than one message. They rely on quantum money
[AC13] and the no-cloning principle to ensure the signature can only be
computed once. For our unclonable signatures of knowledge result, we focus on
the setting where a client wishes to authenticate themselves to a server and
wants to prevent an adversary from simultaneously, or later, masquerading as
them.

One-shot Signatures. The authors of [AGKZ20] introduce the notion of _one-shot
signatures_ which extend the concept of signature tokens to a scenario where
the client and server only exchange classical information to create a one-use
quantum signature token. They show that these signatures can be plausibly
constructed in the CRS model from post-quantum indistinguishability
obfuscation. Unless additional measures for security, which we discussed in
our applications section, are employed, classical communication can be easily
copied and replayed at a later point. In contrast, we prevent an adversary
from simultaneously, or later, authenticating with the client’s identity.

Post-quantum Fiat-Shamir. Our QROM results are heavily inspired by the recent
post-quantum Fiat-Shamir result [LZ19] which proves the post-quantum security
of NIZKs in the compressed quantum(-accessible) random oracle model
(compressed QROM). These classical NIZKs are the result of applying Fiat-
Shamir to post-quantum sigma protocols which are HVZKPoKs. We further extend,
and crucially rely upon, their novel proof techniques to prove extractability
(for PoK) and programmability (for ZK) to achieve extractability and
programmability for some protocols which output quantum proofs.

##  2 Technical Overview

In this section, we give a high-level overview of our construction and the
techniques underlying our main results.

###  2.1 Unclonable Extractable NIZKs in the CRS Model

Our construction assumes the existence of public-key encryption, classical bit
commitments where honestly generated commitment strings are perfectly binding,
along with

  * •

Public-key quantum money mini-scheme (which is known assuming post-quantum
$i\mathcal{O}$ [Zha19b]). At a high level, public-key quantum money mini-
scheme consists of two algorithms: $\mathsf{Gen}$ and $\mathsf{Ver}$.
$\mathsf{Gen}$ on input a security parameter, outputs a quantum banknote
$\ket{\$}$ along with a classical serial number $s$. $\mathsf{Ver}$ is public,
takes a quantum money banknote, and outputs either a classical serial number
$s$, or $\bot$ indicating that its input is an invalid banknote. The security
guarantee is that no efficient adversary given an honest banknote $\ket{\$}$
can output two notes $\ket{\$_{1}}$ and $\ket{\$_{2}}$ that both pass the
verification and have serial numbers equal to that of $\ket{\$}$.

  * •

Post-quantum NIZKs for NP, which are known assuming the post-quantum hardness
of LWE. These satisfy (besides completeness) (1) soundness, i.e., no efficient
prover can generate accepting proofs for false NP statements, and (2) zero-
knowledge, i.e., the verifier obtains no information from an honestly
generated proof beyond what it could have generated on its own given the NP
statement itself.

Construction. Given these primitives, the algorithms
$(\mathsf{Setup},\mathsf{Prove},\mathsf{Verify})$ of the unclonable
extractable NIZK are as follows.

Setup$(1^{\lambda})$: The setup algorithm samples a public key $\mathsf{pk}$,
the common reference string $\mathsf{crs}$ of a classical (post-quantum) NIZK
for NP, along with a perfectly binding, computationally hiding classical
commitment to $0^{\lambda}$ with uniform randomness $t$, i.e.
$c=\mathsf{Com}(0^{\lambda};t)$. It outputs $(\mathsf{pk},\mathsf{crs},c)$.

Prove: Given the CRS $(\mathsf{pk},\mathsf{crs},c)$, instance $x$ and witness
$w$, output $(\ket{\$},s,ct,\pi)$ where

  * •

The state $\ket{\$}\leftarrow\mathsf{Gen}$ is generated as a quantum banknote
with associated serial number $s$.

  * •

The ciphertext $ct=\mathsf{Enc}_{\mathsf{pk}}(w;u)$ is an encryption of the
witness $w$ with randomness $u$.

  * •

The proof string $\pi$ is a (post-quantum) NIZK for the following statement
using witness $(w,u)$:

$\textsf{EITHER }\left(\exists w,u:ct=\mathsf{Enc}_{\mathsf{pk}}(w;u)\wedge
R_{L}(x,w)=1\right)\textsf{ OR }\left(\exists
r:c=\mathsf{Com}(s;r)\right),\vspace{-1mm}$

where we recall that $\mathsf{pk}$ and $c$ were a part of the CRS output by
the Setup algorithm.

Verify: Given CRS $(\mathsf{pk},\mathsf{crs},c)$, instance $x$ and proof
$(\ket{\$},s,ct,\pi)$, check that (1) $\mathsf{Ver}(\ket{\$})$ outputs $s$ and
(2) $\pi$ is an accepting NIZK proof of the statement above.

Analysis. Completeness, soundness/proof of knowledge and ZK for this
construction follow relatively easily, so we focus on unclonable
extractability in this overview. Recall that unclonable extractability
requires that no adversary, given an honestly generated proof for
$x\in\mathcal{L}$, can split this into two accepting proofs for
$x\in\mathcal{L}$ (as long as it is hard to find a witness for $x$). Towards a
contradiction, suppose an adversary splits a proof into 2 accepting proofs
$(\ket{\$_{1}},s_{1},ct_{1},\pi_{1})$, $(\ket{\$_{2}},s_{2},ct_{2},\pi_{2})$.
Then,

  * •

If $s_{1}=s_{2}=s$, the adversary given one bank note with serial number $s$
generated two valid banknotes $\ket{\$}_{1}$ and $\ket{\$}_{2}$ that both have
the same serial number $s$. This contradicts the security of quantum money.

  * •

Otherwise, there is a bit $b$ such that $s_{b}\neq s$. Then, consider an
indistinguishable hybrid where the adversary obtains a simulated proof
generated without witness $w$ as follows: (1) sample quantum banknote
$\ket{\$}$ with serial number $s$, (2) sample public key $\mathsf{pk}$ along
with secret key $\mathsf{sk}$, (3) generate $c=\mathsf{Com}(s;t)$,
$ct=\mathsf{Enc}_{\mathsf{pk}}(0;u)$, (4) generate proof $\pi$ using witness
$t$ (since $c=\mathsf{Com}(s;t)$) instead of using witness $w$. Send common
reference string $(\mathsf{pk},\mathsf{crs},c)$ and proof
$(\ket{\$},s,ct,\pi)$ to the adversary. Now, the proof that the adversary
generates with $s_{b}\neq s$ must contain
$\mathsf{ct}_{b}=\mathsf{Enc}_{\mathsf{pk}}(w;u)$, since $c$ being generated
as a commitment to $s\neq s_{b}$ along with the perfect binding property
implies that $(\not\exists r:c=\mathsf{Com}(s_{b};r))$. That is, given
instance $x$, the adversary can be used to compute a witness $w$ for $x$ by
decrypting ciphertext $\mathsf{ct}_{b}$, thereby contradicting unclonable
extractability.

Having constructed unclonable extractable arguments in the CRS model, in the
next section, we analyze a construction of unclonable extractable arguments in
the QROM.

###  2.2 Unclonable Extractable NIZK in the QROM

We now turn our attention to the QRO setting in which we demonstrate a
protocol which is provably unclonable. Our construction assumes the existence
of public-key quantum money mini-scheme and a _post-quantum sigma protocol for
NP_. A sigma protocol $(\mathsf{P},\mathsf{V})$ is an interactive three-
message honest-verifier protocol: the prover sends a commitment message, the
verifier sends a uniformly random challenge, and the prover replies by opening
its commitment at the locations specified by the random challenge.

Construction. The algorithms $(\textsc{Prove},\textsc{Verify})$ of the
unclonable extractable NIZK in the QROM are as follows.

Prove: Given an instance $x$ and witness $w$, output
$(\ket{\$},s,\alpha,\beta,\gamma)$ where

  * •

The quantum banknote $\ket{\$}$ is generated alongside associated serial
number $s$.

  * •

$\mathsf{P}$ is run to compute the sigma protocol’s commitment message as
$\alpha$ given $(x,w)$ as input.

  * •

The random oracle is queried on input $(\alpha,s,x)$ in order to obtain a
challenge $\beta$.

  * •

$\mathsf{P}$ is run, given as input $(x,w,\alpha,\beta)$ and its previous
internal state, to compute the sigma protocol’s commitment openings as
$\gamma$.

Verify: Given instance $x$ and proof $(\ket{\$},s,\alpha,\beta,\gamma)$, check
that (1) the quantum money verifier accepts $(\ket{\$},s)$, (2) the random
oracle on input $(\alpha,s,x)$ outputs $\beta$, and (3) $\mathsf{V}$ accepts
the transcript $(\alpha,\beta,\gamma)$ with respect to $x$.

Analysis. Since the completeness, proof of knowledge and zero-knowledge
properties are easy to show, we focus on unclonable extractability. Suppose an
adversary was able to provide two accepting proofs
$\pi_{1}=(\ket{\$_{1}},s_{1},\alpha_{1},\beta_{1},\gamma_{1})$ and
$\pi_{2}=(\ket{\$_{2}},s_{2},\alpha_{2},\beta_{2},\gamma_{2})$ for an instance
$x$ for which it received an honestly generated proof
$\pi=(\ket{\$},s,\alpha,\beta,\gamma)$. Then,

  * •

Suppose $s_{1}=s_{2}=s$. In this case, the adversary given one bank note with
serial number $s$ generated two valid banknotes $\ket{\$}_{1}$ and
$\ket{\$}_{2}$ that both have the same serial number $s$. This contradicts the
security of quantum money.

  * •

Otherwise, there is a bit $b\in[1,2]$ such that $s_{b}\neq s$. By the zero-
knowledge property of the underlying HVZK sigma protocol, this event also
occurs when the proof $\pi$ that the adversary is given is replaced with a
simulated proof. Specifically, we build a reduction that locally programs the
random oracle at location $(\alpha,s,x)$ in order to generate a simulated
proof for the adversary. Since the adversary’s own proof for $s_{b}\neq s$ is
generated by making a distinct query $(\alpha_{b},s_{b},x)\neq(\alpha,s,x)$,
the programming on $(\alpha,s,x)$ does not affect the knowledge extractor for
the adversary’s proof, which simply rewinds the (quantum) random oracle to
extract a witness for $x$, following [LZ19]. This allows us to obtain a
contradiction, showing that our protocol must be unclonable.

###  2.3 Unclonable NIZKs imply Quantum Money Mini-Scheme

Finally, we discuss why unclonable NIZKs satisfying even the weaker definition
of unclonable security (i.e., w.r.t. hard distributions) imply public-key
quantum money mini-scheme. Given an unclonable NIZK, we build a public-key
quantum money mini-scheme as follows.

Construction. Let $({\mathcal{X}},{\mathcal{W}})$ be a hard distribution over
a language ${\mathcal{L}}\in\mathsf{NP}$. Let
$\Pi=(\mathsf{Setup},\mathsf{Prove},\mathsf{Verify})$ be an unclonable NIZK
protocol for ${\mathcal{L}}$.

Gen$(1^{\lambda})$: Sample $(x,w)\leftarrow({\mathcal{X}},{\mathcal{W}})$,
$\mathsf{crs}\leftarrow\mathsf{Setup}(1^{\lambda},x)$, and an unclonable NIZK
proof $\pi$ as $\mathsf{Prove}(\mathsf{crs},x,w)$. Output quantum banknote
$\ket{\$}=\pi$, and associated serial number $s=(\mathsf{crs},x)$.

Ver$(\ket{\$},s)$: Given a quantum banknote $\ket{\$}$ and a classical serial
number $s$ as input, parse $\ket{\$}=\pi$ and $s=(\mathsf{crs},x)$, and output
the result of $\mathsf{Verify}(\mathsf{crs},x,\pi)$.

Analysis. The correctness of the quantum money scheme follows from the
completeness of the unclonable NIZK $\Pi$. We will now argue that this quantum
money scheme is unforgeable. Suppose an adversary ${\mathcal{A}}$ given a
quantum banknote and classical serial number $(\ket{\$},s)$ was able to output
two banknotes $(\ket{\$_{0}},\ket{\$_{1}})$ both of which are accepted with
respect to $s$. We can use ${\mathcal{A}}$ to define a reduction to the
uncloneability of our NIZK $\Pi$ as follows:

  * •

The NIZK uncloneability challenger outputs a hard instance-witness pair
$(x,w)$, a common reference string $\mathsf{crs}$, and an unclonable NIZK
$\pi$ to the reduction.

  * •

The reduction outputs a banknote $(\ket{\$},s)$ to the adversary, where
$\ket{\$}=\pi$ and $s=(\mathsf{crs},x)$. It receives two quantum banknotes
$(\ket{\$_{0}},\ket{\$_{1}})$ from ${\mathcal{A}}$, and finally outputs two
proofs $(\pi_{0},\pi_{1})$ where $\pi_{0}=\ket{\$_{0}}$ and
$\pi_{1}=\ket{\$_{1}}$.

If ${\mathcal{A}}$ succeeds in breaking unforgeability, then the quantum money
verifier accepts both banknotes $(\ket{\$}_{0}=\pi_{0},\ket{\$}_{1}=\pi_{1})$,
with respect to the same serial number $s=(\mathsf{crs},x)$. By syntax of the
verification algorithm, this essentially means that both proofs
$(\pi_{0},\pi_{1})$ are accepting proofs for membership of the same instance
$x\in{\mathcal{L}}$, w.r.t. $\mathsf{crs}$, leading to a break in the
unclonability of NIZK.

###  2.4 Unclonable Signatures of Knowledge

Informally, a signature of knowledge has the following property: if an
adversary, given a signature of a message $m$ with respect to an instance $x$,
can produce two signatures for $m$ which verify with respect to the same
instance $x$, then the adversary must know (and our extractor will be able to
extract) a witness for $x$.

We obtain unclonable signatures of knowledge assuming the existence of an
unclonable extractable _simulation-extractable_ NIZK for $\mathsf{NP}$.
Simulation-extractability states that an adversary which is provided any
number of simulated proofs for instance and witness pairs of their choosing,
cannot produce an accepting proof $\pi$ for an instance $x$ which they have
not queried before and where extraction fails to find an accepting witness
$w$. Our unclonable extractable NIZK for $\mathsf{NP}$ in the CRS model can,
with some extra work, be upgraded to simulation-extractable.

We informally describe the construction of signatures of knowledge from such a
NIZK below.

Construction. Let $(\mathsf{Setup},\mathsf{P},\mathsf{V})$ be non-interactive
simulation-extractable, adaptive multi-theorem computational zero-knowledge,
unclonable-extractable protocol for $\mathsf{NP}$. Let ${\mathcal{R}}$ be the
$\mathsf{NP}$ relation corresponding to ${\mathcal{L}}$.

Setup: The setup algorithm samples a common reference string $\mathsf{crs}$ of
an unclonable-extractable simulation-extractable NIZK for $\mathsf{NP}$. It
outputs $\mathsf{crs}$.

Sign: Given the CRS $\mathsf{crs}$, instance $x$, witness $w$, and message
$m$, output signature $\pi$ where

  * •

The proof string $\pi$ is an unclonable-extractable simulation-extractable
NIZK with tag $m$ using witness $w$ of the following statement:

$\vspace{-2mm}\left(\exists w:(x,w)\in{\mathcal{R}}\right).$

Verify: Given CRS $\mathsf{crs}$, instance $x$, message $m$, and signature
$\pi$, check that $\pi$ is an accepting NIZK proof with tag $m$ of the
statement above.

Analysis. The simulatability (extractability) property follows from the zero-
knowledge (resp. simulation-extractability) properties of the NIZK. Suppose an
adversary ${\mathcal{A}}$ given a signature $\sigma$ was able to forge two
signatures $\sigma_{1}=\pi_{1}$ and $\sigma_{2}=\pi_{2}$, and, yet, our
extractor was to fail to extract a witness $w$ from ${\mathcal{A}}$. Then,

  * •

Either both proofs $\pi_{1}$ and $\pi_{2}$ are accepting proofs for membership
of the same instance w.r.t. $\mathsf{crs}$. However, this contradicts the
unclonability of the NIZK.

  * •

Otherwise there exists a proof $\pi_{i}$ (where $i\in\\{1,2\\}$) for an
instance which ${\mathcal{A}}$ has not previously seen a proof for. We can
switch to a hybrid where our signatures contain simulated proofs for the NIZK.
But now, we have that the verifier accepts a proof for an instance which
${\mathcal{A}}$ has not seen a simulated proof for and, yet, we cannot extract
a witness from ${\mathcal{A}}$. This contradicts the simulation extractability
of the NIZK.

##### Roadmap.

In Section LABEL:sec:crscons, we define and construct unclonable NIZKs in the
CRS model, and in Section 5, in the QROM. Along the way, we also show that
unclonable NIZKs imply quantum money (in the CRS and QRO model respectively).
Later, we show how to define and construct unclonable signatures of knowledge
from unclonable NIZKs in the CRS model.

##  3 Preliminaries

###  3.1 Post-Quantum Commitments and Encryption

######  Definition 3.1 (Post-Quantum Commitments).

$\mathsf{Com}$ is a post-quantum commitment scheme if it has the following
syntax and properties.

Syntax.

  * •

$c\leftarrow\mathsf{Com}(m;r)$: The polynomial-time algorithm $\mathsf{Com}$
on input a message $m$ and randomness $r\in{\\{0,1\\}}^{r(\lambda)}$ outputs
commitment a $c$.

Properties.

  * •

Perfectly Binding: For every $\lambda\in\mathbb{N}^{+}$ and every
$m,m^{\prime},r,r^{\prime}$ such that $m\neq m^{\prime}$,

$\mathsf{Com}(m;r)\neq\mathsf{Com}(m^{\prime};r^{\prime}).$

  * •

Computational Hiding: There exists a negligible function
$\mathsf{negl}(\cdot)$ for every unbounded-size quantum circuit
${\mathcal{D}}$, every sufficiently large $\lambda\in\mathbb{N}^{+}$, and
every $m,m^{\prime}$,

$\left|\Pr_{\begin{subarray}{c}r\stackrel{{\scriptstyle\mathclap{\mbox{\text{\tiny\$}}}}}{{\leftarrow}}{\\{0,1\\}}^{r(\lambda)},\>c\leftarrow\mathsf{Com}(m;r)\end{subarray}}[{\mathcal{D}}(c)=1]-\Pr_{\begin{subarray}{c}r\stackrel{{\scriptstyle\mathclap{\mbox{\text{\tiny\$}}}}}{{\leftarrow}}{\\{0,1\\}}^{r(\lambda)},\>c^{\prime}\leftarrow\mathsf{Com}(m^{\prime};r)\end{subarray}}[{\mathcal{D}}(c^{\prime})=1]\right|\leq\mathsf{negl}(\lambda).$

######  Theorem 3.2 (Post-Quantum Commitment).

[LS19] Assuming the polynomial quantum hardness of LWE, there exists a non-
interactive commitment with perfect binding and computational hiding
(Definition 3.1).

######  Definition 3.3 (Post-Quantum Public-Key Encryption).

$(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ is a post-quantum public-key
encryption scheme if it has the following syntax and properties.

Syntax.

  * •

$(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})$: The
polynomial-time algorithm $\mathsf{Gen}$ on input security parameter
$1^{\lambda}$ outputs a public key $\mathsf{pk}$ and a secret key
$\mathsf{sk}$.

  * •

$c\leftarrow\mathsf{Enc}(\mathsf{pk},m;r)$: The polynomial-time algorithm
$\mathsf{Enc}$ on input a public key $\mathsf{pk}$, message $m$ and randomness
$r\in{\\{0,1\\}}^{r(\lambda)}$ outputs a ciphertext $c$.

  * •

$m\leftarrow\mathsf{Dec}(\mathsf{sk},c)$: The polynomial-time algorithm
$\mathsf{Dec}$ on input a secret key $\mathsf{sk}$ and a ciphertext $c$
outputs a message $m$.

Properties.

  * •

Perfect Correctness: For every $\lambda\in\mathbb{N}^{+}$ and every $m,r$,

$\Pr_{\begin{subarray}{c}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})\end{subarray}}[\mathsf{Dec}(\mathsf{sk},\mathsf{Enc}(\mathsf{pk},m;r))=m]=1.$

  * •

Indistinguishability under Chosen-Plaintext (IND-CPA) Secure: There exists a
negligible function $\mathsf{negl}(\cdot)$ such that for every polynomial-size
quantum circuit ${\mathcal{A}}=({\mathcal{A}}_{0},{\mathcal{A}}_{1})$ and
every sufficiently large $\lambda\in\mathbb{N}^{+}$

$\left|\Pr_{\begin{subarray}{c}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})\\\
(m_{0},m_{1},\zeta)\leftarrow{\mathcal{A}}_{0}(1^{\lambda},\mathsf{pk})\\\
c\leftarrow\mathsf{Enc}(\mathsf{pk},m_{0})\end{subarray}}[{\mathcal{A}}_{1}(1^{\lambda},c,\zeta)=1]-\Pr_{\begin{subarray}{c}(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})\\\
(m_{0},m_{1},\zeta)\leftarrow{\mathcal{A}}_{0}(1^{\lambda},\mathsf{pk})\\\
c\leftarrow\mathsf{Enc}(\mathsf{pk},m_{1})\end{subarray}}[{\mathcal{A}}_{1}(1^{\lambda},c,\zeta)=1]\right|\leq\mathsf{negl}(\lambda).$

###  3.2 Sigma protocols

######  Definition 3.4 (Post-Quantum Sigma Protocol for $\mathsf{NP}$).

[LZ19] Let $\mathsf{NP}$ relation ${\mathcal{R}}$ with corresponding language
${\mathcal{L}}$ be given such that they can be indexed by a security parameter
$\lambda\in\mathbb{N}$.

$\Pi=(\mathsf{P}=(\mathsf{P}.\mathsf{Com},\mathsf{P}.\mathsf{Prove}),\mathsf{V}=(\mathsf{V}.\mathsf{Ch},\mathsf{V}.\mathsf{Ver}))$
is a post-quantum sigma protocol if it has the following syntax and
properties.

Syntax. The input $1^{\lambda}$ is left out when it is clear from context.

  * •

$(\alpha,\mathsf{st})\leftarrow\mathsf{P}.\mathsf{Com}(1^{\lambda},x,w)$: The
probabilistic polynomial-size circuit $\mathsf{P}.\mathsf{Com}$ on input an
instance and witness pair $(x,w)\in{\mathcal{L}}_{\lambda}$ outputs a
commitment $\alpha$ and an internal prover state $\mathsf{st}$.

  * •

$\beta\leftarrow\mathsf{V}.\mathsf{Ch}(1^{\lambda},x,\alpha)$: The
probabilistic polynomial-size circuit $\mathsf{V}.\mathsf{Ch}$ on input an
instance $x$ outputs a uniformly random challenge $\beta$.

  * •

$\gamma\leftarrow\mathsf{P}.\mathsf{Prove}(1^{\lambda},x,w,\mathsf{st},\beta)$:
The probabilistic polynomial-size circuit $\mathsf{P}.\mathsf{Prove}$ on input
an instance and witness pair $(x,w)\in{\mathcal{L}}_{\lambda}$, an internal
prover state $\mathsf{st}$, and a challenge $\beta$ outputs the partial
opening (to $\alpha$ as indicated by $\beta$) $\gamma$.

  * •

$\mathsf{V}.\mathsf{Ver}(1^{\lambda},x,\alpha,\beta,\gamma)\in{\\{0,1\\}}$:
The probabilistic polynomial-size circuit $\mathsf{V}.\mathsf{Ver}$ on input
an instance $x$, a commitment $\alpha$, a challenge $\beta$, and a partial
opening $\gamma$ outputs $1$ iff $\gamma$ is a valid opening to $\alpha$ at
locations indicated by $\beta$.

Properties.

  * •

Perfect Completeness. For every $\lambda\in\mathbb{N}$ and every
$(x,w)\in{\mathcal{R}}_{\lambda}$,

$\Pr_{\begin{subarray}{c}(\alpha,\mathsf{st})\leftarrow\mathsf{P}.\mathsf{Com}(x,w)\\\
\beta\leftarrow\mathsf{V}.\mathsf{Ch}(x,\alpha)\\\
\gamma\leftarrow\mathsf{P}.\mathsf{Prove}(x,w,\mathsf{st},\beta)\end{subarray}}[\mathsf{V}.\mathsf{Verify}(x,\alpha,\beta,\gamma)=1]=1$

  * •

Computational Honest-Verifier Zero-Knowledge with Quantum Simulator. There
exists a quantum polynomial-size circuit $\mathsf{Sim}$ and a negligible
function $\mathsf{negl}(\cdot)$ such that for every polynomial-size quantum
circuit ${\mathcal{D}}$, every sufficiently large $\lambda\in\mathbb{N}$, and
every $(x,w)\in{\mathcal{R}}_{\lambda}$,

$\left|\Pr_{\begin{subarray}{c}(\alpha,\mathsf{st})\leftarrow\mathsf{P}.\mathsf{Com}(x,w)\\\
\beta\leftarrow\mathsf{V}.\mathsf{Ch}(x,\alpha)\\\
\gamma\leftarrow\mathsf{P}.\mathsf{Prove}(x,w,\mathsf{st},\beta)\end{subarray}}[{\mathcal{D}}(x,\alpha,\beta,\gamma)=1]-\Pr_{\begin{subarray}{c}(\alpha,\beta,\gamma)\leftarrow\mathsf{Sim}(1^{\lambda},x)\end{subarray}}[{\mathcal{D}}(x,\alpha,\beta,\gamma)=1]\right|\leq\mathsf{negl}(\lambda).$

  * •

Proof of Knowledge with Quantum Extractor. There exists an oracle-aided
quantum polynomial-size circuit $\mathsf{Ext}$, a constant $c$, a polynomial
$p(\cdot)$, and negligible functions $\mathsf{negl}_{0}(\cdot)$,
$\mathsf{negl}_{1}(\cdot)$ such that for every polynomial-size quantum circuit
${\mathcal{A}}=({\mathcal{A}}_{0},{\mathcal{A}}_{1})$ where

    * –

${\mathcal{A}}_{0}(x)$ is a unitary $U_{x}$ followed by a measurement and

    * –

${\mathcal{A}}_{1}(x,\ket{\mathsf{st}},\beta)$ is a unitary $V_{x,\beta}$ onto
the state $\ket{\mathsf{st}}$ followed by a measurement,

and every $x$ with associated $\lambda\in\mathbb{N}$ satisfying

$\Pr_{\begin{subarray}{c}(\alpha,\ket{\mathsf{st}})\leftarrow{\mathcal{A}}_{0}(x)\\\
\beta\leftarrow{\\{0,1\\}}^{\lambda}\\\
\gamma\leftarrow{\mathcal{A}}_{1}(x,\ket{\mathsf{st}},\beta)\end{subarray}}[\mathsf{V}.\mathsf{Ver}(x,\alpha,\beta,\gamma)=1]\geq\mathsf{negl}_{0}(\lambda)$

we have

$\displaystyle\Pr[(x,\mathsf{Ext}^{{\mathcal{A}}(x)}(x))\in{\mathcal{R}}_{\lambda}]\geq\frac{1}{p(\lambda)}\cdot\left(\Pr_{\begin{subarray}{c}(\alpha,\ket{\mathsf{st}})\leftarrow{\mathcal{A}}_{0}(x)\\\
\beta\leftarrow{\\{0,1\\}}^{\lambda}\\\
\gamma\leftarrow{\mathcal{A}}_{1}(x,\ket{\mathsf{st}},\beta)\end{subarray}}[\mathsf{V}.\mathsf{Ver}(x,\alpha,\beta,\gamma)=1]-\mathsf{negl}_{0}(\lambda)\right)^{c}-\mathsf{negl}_{1}(\lambda).$

When we say $\mathsf{Ext}$ has oracle access to ${\mathcal{A}}(x)$, we mean
that $\mathsf{Ext}$ has oracle access to both unitaries $U_{x},V_{x,\beta}$
and their inverses $U_{x}^{\dagger},V_{x,\beta}^{\dagger}$.

  * •

Unpredictable Commitment. There exists a negligible function
$\mathsf{negl}(\cdot)$ such that for every sufficiently large
$\lambda\in\mathbb{N}$ and every $(x,w)\in{\mathcal{R}}_{\lambda}$,

$\Pr_{\begin{subarray}{c}(\alpha,\mathsf{st})\leftarrow\mathsf{P}.\mathsf{Com}(x,w)\\\
(\alpha^{\prime},\mathsf{st}^{\prime})\leftarrow\mathsf{P}.\mathsf{Com}(x,w)\end{subarray}}[\alpha=\alpha^{\prime}]\leq\mathsf{negl}(\lambda).$

We note that the unpredictable commitment property in the definition above may
appear to be an unusual requirement, but this property is w.l.o.g. for post
quantum sigma protocols as shown in [LZ19]. In particular, any sigma protocol
which does not have unpredictable commitments, can be modified into one that
does: the prover can append a random string $r$ to the end of their commitment
message $\alpha$, and the verifier can ignore this appended string $r$ when
they perform their checks.

###  3.3 NIZKs in the CRS model

We consider the common reference string model.

######  Definition 3.5 (Post-Quantum (Quantum) NIZK for $\mathsf{NP}$ in the
CRS Model).

Let $\mathsf{NP}$ relation ${\mathcal{R}}$ with corresponding language
${\mathcal{L}}$ be given such that they can be indexed by a security parameter
$\lambda\in\mathbb{N}$.

$\Pi=(\mathsf{Setup},\mathsf{P},\mathsf{V})$ is a non-interactive post-quantum
(quantum) zero-knowledge argument for $\mathsf{NP}$ in the CRS model if it has
the following syntax and properties.

Syntax. The input $1^{\lambda}$ is left out when it is clear from context.

  * •

$\mathsf{crs}\leftarrow\mathsf{Setup}(1^{\lambda})$: The probabilistic
polynomial-size circuit $\mathsf{Setup}$ on input $1^{\lambda}$ outputs a
common reference string $\mathsf{crs}$.

  * •

$\pi\leftarrow\mathsf{P}(1^{\lambda},\mathsf{crs},x,w)$: The probabilistic
(quantum) polynomial-size circuit $\mathsf{P}$ on input a common reference
string $\mathsf{crs}$ and instance and witness pair
$(x,w)\in{\mathcal{R}}_{\lambda}$, outputs a proof $\pi$.

  * •

$\mathsf{V}(1^{\lambda},\mathsf{crs},x,\pi)\in{\\{0,1\\}}$: The probabilistic
(quantum) polynomial-size circuit $\mathsf{V}$ on input a common reference
string $\mathsf{crs}$, an instance $x$, and a proof $\pi$ outputs $1$ iff
$\pi$ is a valid proof for $x$.

Properties.

  * •

Perfect Completeness. For every $\lambda\in\mathbb{N}$ and every
$(x,w)\in{\mathcal{R}}_{\lambda}$,

$\Pr_{\begin{subarray}{c}\mathsf{crs}\leftarrow\mathsf{Setup}(1^{\lambda})\\\
\pi\leftarrow\mathsf{P}(\mathsf{crs},x,w)\end{subarray}}[\mathsf{V}(\mathsf{crs},x,\pi)=1]=1.$

  * •

Adaptive Computational Soundness. There exists a negligible function
$\mathsf{negl}(\cdot)$ such that for every polynomial-size quantum circuit
${\mathcal{A}}$ and every sufficiently large $\lambda\in\mathbb{N}$,

$\Pr_{\begin{subarray}{c}\mathsf{crs}\leftarrow\mathsf{Setup}(1^{\lambda})\\\
(x,\pi)\leftarrow{\mathcal{A}}(\mathsf{crs})\end{subarray}}[\mathsf{V}(x,\mathsf{crs},\pi)=1\>\land\>x\not\in{\mathcal{L}}_{\lambda}]\leq\mathsf{negl}(\lambda).$

  * •

Adaptive Computational Zero-Knowledge. There exists a probabilistic (quantum)
polynomial-size circuit $\mathsf{Sim}=(\mathsf{Sim}_{0},\mathsf{Sim}_{1})$ and
a negligible function $\mathsf{negl}(\cdot)$ such that for every polynomial-
size quantum circuit ${\mathcal{A}}$, every polynomial-size quantum circuit
${\mathcal{D}}$, and every sufficiently large $\lambda\in\mathbb{N}$,

$\left|\Pr_{\begin{subarray}{c}\mathsf{crs}\leftarrow\mathsf{Setup}(1^{\lambda})\\\
(x,w,\zeta)\leftarrow{\mathcal{A}}(\mathsf{crs})\\\
\pi\leftarrow\mathsf{P}(\mathsf{crs},x,w)\end{subarray}}[{\mathcal{D}}(\mathsf{crs},x,\pi,\zeta)=1]-\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})\\\
(x,w,\zeta)\leftarrow{\mathcal{A}}(\mathsf{crs})\\\
\pi\leftarrow\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},x)\end{subarray}}[{\mathcal{D}}(\mathsf{crs},x,\pi,\zeta)=1]\right|\leq\mathsf{negl}(\lambda).$

######  Theorem 3.6 (Post-Quantum NIZK argument for $\mathsf{NP}$ in the CRS
Model).

[PS19] Assuming the polynomial quantum hardness of LWE, there exists a non-
interactive adaptively computationally sound, adaptively computationally zero-
knowledge argument for $\mathsf{NP}$ in the common reference string model
(Definition 3.5).

######  Definition 3.7 (Post-Quantum (Quantum) Simulation-Sound NIZK for
$\mathsf{NP}$ in CRS Model).

Let $\mathsf{NP}$ relation ${\mathcal{R}}$ with corresponding language
${\mathcal{L}}$ be given such that they can be indexed by a security parameter
$\lambda\in\mathbb{N}$.

$\Pi=(\mathsf{Setup},\mathsf{P},\mathsf{V})$ is a post-quantum (quantum) non-
interactive simulation-sound, adaptive multi-theorem computational zero-
knowledge protocol for $\mathsf{NP}$ in the CRS model if it has the following
syntax and properties.

  * •

$\Pi$ is a post-quantum (quantum) non-interactive zero-knowledge argument for
$\mathsf{NP}$ in the CRS model (Definition 3.5).

  * •

Adaptive Multi-Theorem Computational Zero-Knowledge. [FLS90] There exists a
probabilistic (quantum) polynomial-size circuit
$\mathsf{Sim}=(\mathsf{Sim}_{0},\mathsf{Sim}_{1})$ 111$\mathsf{Sim}_{1}$
ignores the second term (a witness $w$) in the queries it receives from
${\mathcal{A}}$. and a negligible function $\mathsf{negl}(\cdot)$ such that
for every polynomial-size quantum circuit ${\mathcal{A}}$, every polynomial-
size quantum circuit ${\mathcal{D}}$, and every sufficiently large
$\lambda\in\mathbb{N}$,

$\left|\Pr_{\begin{subarray}{c}\mathsf{crs}\leftarrow\mathsf{Setup}(1^{\lambda})\end{subarray}}[{\mathcal{A}}^{\mathsf{P}(\mathsf{crs},\cdot,\cdot)}(\mathsf{crs})=1]-\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})\end{subarray}}[{\mathcal{A}}^{\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},\cdot)}(\mathsf{crs})=1]\right|\leq\mathsf{negl}(\lambda).$

  * •

Simulation Soundness. [Sah99, SCO+01] Let
$\mathsf{Sim}=(\mathsf{Sim}_{0},\mathsf{Sim}_{1})$ be the simulator given by
the adaptive multi-theorem computational zero-knowledge property. There exists
a negligible function $\mathsf{negl}(\cdot)$ such that for every oracle-aided
polynomial-size quantum circuit ${\mathcal{A}}$ and every sufficiently large
$\lambda\in\mathbb{N}$,

$\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})\\\
(x,\pi)\leftarrow{\mathcal{A}}^{\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},\cdot)}(\mathsf{crs})\end{subarray}}[\mathsf{V}(\mathsf{crs},x,\pi)=1\wedge
x\not\in Q\wedge x\not\in{\mathcal{L}}]\leq\mathsf{negl}(\lambda),$

where $Q$ is the list of queries from ${\mathcal{A}}$ to $\mathsf{Sim}_{1}$.

######  Remark 3.1.

In Definition 3.7, adaptive multi-theorem computational zero-knowledge implies
adaptive computational zero-knowledge.

######  Remark 3.2.

As defined in Definition 3.7, a simulation-sound zero-knowledge protocol has
adaptive computational soundness (Definition 3.5).

######  Theorem 3.8 (Simulation Sound Compiler).

[SCO+01] Given one-way functions and a single-theorem NIZK proof system for
$\mathsf{NP}$, then there exists a non-interactive simulation sound,
adaptively multi-theorem computationally zero-knowledge proof for
$\mathsf{NP}$ in the common reference string model (Definition 3.7).

######  Corollary 3.9 (Post-Quantum Simulation Sound NIZK for $\mathsf{NP}$).

Assuming the polynomial quantum hardness of LWE, there exists a post-quantum
non-interactive simulation sound, adaptively multi-theorem computationally
zero-knowledge proof for $\mathsf{NP}$ in the common reference string model
(Definition 3.7).

###### Proof.

This follows from Theorem 3.6 and Theorem 3.8. ∎

###  3.4 NIZKs in the QRO model

We now consider the quantum random oracle model. For sake of completeness, we
briefly outline a definition for a quantum random oracle.

######  Definition 3.10.

A quantum random oracle ${\mathcal{O}}$ is a random function which support
quantum queries and allows for the following accesses:

  * •

Query Access. On input a message, ${\mathcal{O}}$ outputs a uniformly random
value. This is the usual access provided. When quantum access may be invoked,
we denote the oracle as $\ket{{\mathcal{O}}}$.

  * •

Programmability Access. Given programmability access, ${\mathcal{O}}$ can be
set to output a specified value on a specified input. An arbitrary number of
distinct points can be programmed.

  * •

Extractability Access. Given extractability access, specific queries to
$\ket{{\mathcal{O}}}$ can be read.

######  Definition 3.11 ((Quantum) Post-Quantum NIZKPoK for $\mathsf{NP}$ in
QROM).

[LZ19] Let ${\mathcal{O}}$ be a random oracle. Let $\mathsf{NP}$ relation
${\mathcal{R}}$ with corresponding language ${\mathcal{L}}$ be given such that
they can be indexed by a security parameter $\lambda\in\mathbb{N}$.

$\Pi=(\mathsf{P},\mathsf{V})$ is a (quantum) non-interactive zero-knowledge
proof of knowledge protocol with respect to a random oracle if it has the
following syntax and properties.

Syntax. The input $1^{\lambda}$ is left out when it is clear from context.

  * •

$\pi\leftarrow\mathsf{P}^{\mathcal{O}}(1^{\lambda},x,w)$: The random oracle-
aided (quantum) probabilistic polynomial-size circuit $\mathsf{P}$ on input an
instance and witness pair $(x,w)\in{\mathcal{R}}_{\lambda}$, outputs a proof
$\pi$.

  * •

$\mathsf{V}^{\mathcal{O}}(1^{\lambda},x,\pi)\in{\\{0,1\\}}$: The random
oracle-aided (quantum) probabilistic polynomial-size circuit $\mathsf{V}$ on
input an instance $x$ and a proof $\pi$, outputs $1$ iff $\pi$ is a valid
proof for $x$.

Properties.

  * •

Perfect Completeness. For every $\lambda\in\mathbb{N}$ and every
$(x,w)\in{\mathcal{R}}_{\lambda}$,

$\Pr_{\begin{subarray}{c}{\mathcal{O}}\\\
\pi\leftarrow\mathsf{P}^{\mathcal{O}}(x,w)\end{subarray}}[\mathsf{V}^{\mathcal{O}}(x,\pi)=1]=1.$

  * •

Zero-Knowledge with Quantum Simulator. There exists a quantum polynomial-size
circuit $\mathsf{Sim}$ which ignores its second input and a negligible
function $\mathsf{negl}(\cdot)$ such that for every oracle-aided polynomial-
size quantum circuit ${\mathcal{D}}$ which is limited to making queries
$(x,\omega)\in{\mathcal{R}}_{\lambda}$ on input $1^{\lambda}$, and every
sufficiently large $\lambda\in\mathbb{N}$,

$\left|\Pr[{\mathcal{D}}^{\mathsf{Sim},\ket{{\mathcal{O}}_{\mathsf{Sim}}}}(1^{\lambda})=1]-\Pr_{\mathcal{O}}[{\mathcal{D}}^{\mathsf{P}^{\mathcal{O}},\ket{{\mathcal{O}}}}(1^{\lambda})=1]\right|\leq\mathsf{negl}(\lambda)$

where $\mathsf{Sim}$ simulates the random oracle
$\ket{{\mathcal{O}}_{\mathsf{Sim}}}$.

  * •

Proof of Knowledge with Quantum Extractor. There exists an oracle-aided
quantum polynomial-size circuit extractor $\mathsf{Ext}$ that simulates a
random oracle $\ket{{\mathcal{O}}_{\mathsf{Ext}}}$, a constant $c$, a
polynomial $p(\cdot)$, and negligible functions $\mathsf{negl}_{0}(\cdot)$,
$\mathsf{negl}_{1}(\cdot)$ such that for every polynomial-size quantum circuit
${\mathcal{A}}$ and every $x$ with associated $\lambda\in\mathbb{N}$
satisfying

$\Pr_{\begin{subarray}{c}{\mathcal{O}}\\\
\pi\leftarrow{\mathcal{A}}^{\ket{{\mathcal{O}}}}(x)\end{subarray}}[\mathsf{V}^{\mathcal{O}}(x,\pi)=1]\geq\mathsf{negl}_{0}(\lambda)$

we have

$\displaystyle\Pr[(x,\mathsf{Ext}^{{\mathcal{A}}^{\ket{{\mathcal{O}}_{\mathsf{Ext}}}}(x)}(x))\in{\mathcal{R}}_{\lambda}]\geq\frac{1}{p(\lambda)}\cdot\left(\Pr_{\begin{subarray}{c}{\mathcal{O}}\\\
\pi\leftarrow{\mathcal{A}}^{\ket{{\mathcal{O}}}}(x)\end{subarray}}[\mathsf{V}^{\mathcal{O}}(x,\pi)=1]-\mathsf{negl}_{0}(\lambda)\right)^{c}-\mathsf{negl}_{1}(\lambda).$

######  Theorem 3.12 (NIZKPoK in QROM [Unr17, LZ19]).

Let $\Pi$ be a post-quantum sigma protocol (Definition 3.4). The Fiat-Shamir
heuristic applied to $\Pi$ yields a classical post-quantum NIZKPoK in the QROM
(Definition 3.11).

###  3.5 Quantum Money

######  Definition 3.13 (Public Key Quantum Money Mini-Scheme).

[AC13, Zha19b] $(\mathsf{Gen},\mathsf{Ver})$ is a public key quantum money
scheme if it has the following syntax and properties.

Syntax.

  * •

$(\ket{\$},s)\leftarrow\mathsf{Gen}(1^{\lambda})$: The quantum polynomial-time
algorithm $\mathsf{Gen}$ on input security parameter $1^{\lambda}$ outputs a
quantum banknote $\ket{\$}$ along with a classical serial number $s$.

  * •

$\mathsf{Ver}(\ket{\$},s)\in{\\{0,1\\}}$: The quantum polynomial-time
algorithm $\mathsf{Ver}$ on input a quantum banknote $\ket{\$}$ and a
classical serial number $s$ outputs $1$ or $0$.

Properties.

  * •

Perfect Correctness: For every $\lambda\in\mathbb{N}^{+}$,

$\Pr_{(\ket{\$},s)\leftarrow\mathsf{Gen}(1^{\lambda})}[\mathsf{Ver}(\ket{\$},s)=1]=1.$

  * •

Unforgeable: There exists a negligible function $\mathsf{negl}(\cdot)$ such
that for every sufficiently large $\lambda\in\mathbb{N}^{+}$ and every
polynomial-size quantum circuit ${\mathcal{A}}$,

$\Pr_{\begin{subarray}{c}(\ket{\$},s)\leftarrow\mathsf{Gen}(1^{\lambda})\\\
(\ket{\$_{0}},s_{0},\ket{\$_{1}},s_{1})\leftarrow{\mathcal{A}}(\ket{\$},s)\end{subarray}}[s_{0}=s_{1}=s\>\land\>\mathsf{Ver}(\ket{\$_{0}},s_{0})=1\>\land\>\mathsf{Ver}(\ket{\$_{1}},s_{1})=1]\leq\mathsf{negl}(\lambda).$

  * •

Unpredictable Serial Numbers: There exists a negligible function
$\mathsf{negl}(\cdot)$ such that for every sufficiently large
$\lambda\in\mathbb{N}$,

$\Pr_{\begin{subarray}{c}(\ket{\$},s)\leftarrow\mathsf{Gen}(1^{\lambda})\\\
(\ket{\$^{\prime}},s^{\prime})\leftarrow\mathsf{Gen}(1^{\lambda})\end{subarray}}[s=s^{\prime}]\leq\mathsf{negl}(\lambda).$

######  Remark 3.3 (Unpredictable Serial Numbers).

The unpredictable serial numbers property follows, w.l.o.g., from
unforgeability. We will briefly outline the reduction. Say that $\mathsf{Gen}$
produced two quantum banknotes $\ket{\$}$ and $\ket{\$^{\prime}}$ which had
the same serial number $s$ with noticeable probability. Then an adversary
${\mathcal{A}}$ that receives $(\ket{\$},s)$ from $\mathsf{Gen}$ could run
$\mathsf{Gen}$ again to produce $(\ket{\$^{\prime}},s)$ with noticeable
probability. This means that ${\mathcal{A}}$ would have produced two quantum
banknotes $\ket{\$}$ and $\ket{\$^{\prime}}$ which $\mathsf{Verify}$ would
accept with respect to the same serial number that ${\mathcal{A}}$ received,
$s$.

######  Theorem 3.14 (Quantum Money from Subspace Hiding Obfuscation [AC13,
Zha19b]).

If injective one-way functions and post-quantum iO exist, then public-key
quantum money exists (Definition 3.13).

######  Definition 3.15 (Public Key Quantum Money Mini-Scheme in QROM).

$(\mathsf{Gen},\mathsf{Ver})$ is a public key quantum money scheme with
respect to a quantum random oracle ${\mathcal{O}}$ if it has the following
syntax and properties.

Syntax.

  * •

$(\ket{\$},s)\leftarrow\mathsf{Gen}^{\mathcal{O}}(1^{\lambda})$: The random
oracle-aided quantum polynomial-time algorithm $\mathsf{Gen}$ on input a
security parameter $1^{\lambda}$ outputs a quantum banknote $\ket{\$}$ along
with a classical serial number $s$.

  * •

$\mathsf{Ver}^{\mathcal{O}}(\ket{\$},s)\in{\\{0,1\\}}$: The random oracle-
aided quantum polynomial-time algorithm $\mathsf{Ver}$ on input a quantum
banknote $\ket{\$}$ and a classical serial number $s$ outputs $1$ or $0$.

Properties.

  * •

Perfect Correctness: For every $\lambda\in\mathbb{N}^{+}$,

$\Pr_{(\ket{\$},s)\leftarrow\mathsf{Gen}^{\mathcal{O}}(1^{\lambda})}[\mathsf{Ver}^{\mathcal{O}}(\ket{\$},s)=1]=1.$

  * •

Unforgeable: There exists a negligible function $\mathsf{negl}(\cdot)$ such
that for every sufficiently large $\lambda\in\mathbb{N}^{+}$ and every random
oracle-aided polynomial-size quantum circuit ${\mathcal{A}}$,

$\Pr_{\begin{subarray}{c}(\ket{\$},s)\leftarrow\mathsf{Gen}^{\mathcal{O}}(1^{\lambda})\\\
(\ket{\$_{0}},s_{0},\ket{\$_{1}},s_{1})\leftarrow{\mathcal{A}}^{\mathcal{O}}(\ket{\$},s)\end{subarray}}[s_{0}=s_{1}=s\>\land\>\mathsf{Ver}^{\mathcal{O}}(\ket{\$_{0}},s_{0})=1\>\land\>\mathsf{Ver}^{\mathcal{O}}(\ket{\$_{1}},s_{1})=1]\leq\mathsf{negl}(\lambda).$

  * •

Unpredictable Serial Numbers: There exists a negligible function
$\mathsf{negl}(\cdot)$ such that for every sufficiently large
$\lambda\in\mathbb{N}$,

$\Pr_{\begin{subarray}{c}(\ket{\$},s)\leftarrow\mathsf{Gen}^{\mathcal{O}}(1^{\lambda})\\\
(\ket{\$^{\prime}},s^{\prime})\leftarrow\mathsf{Gen}^{\mathcal{O}}(1^{\lambda})\end{subarray}}[s=s^{\prime}]\leq\mathsf{negl}(\lambda).$

The unpredicable serial number property is w.l.o.g., just as above.

###  3.6 Quantum Signature of Knowledge

######  Definition 3.16 (Quantum SimExt-secure Signature [CL06]).

Let $\mathsf{NP}$ relation ${\mathcal{R}}$ with corresponding language
${\mathcal{L}}$ be given such that they can be indexed by a security parameter
$\lambda\in\mathbb{N}$. Let a message space ${\mathcal{M}}$ be given such that
it can be indexed by a security parameter $\lambda\in\mathbb{N}$.

$(\mathsf{Setup},\mathsf{Sign},\mathsf{Verify})$ is a SimExt-secure quantum
signature of knowledge of a witness with respect to ${\mathcal{L}}$ and
${\mathcal{M}}$ if it has the following syntax and properties.

Syntax. The input $1^{\lambda}$ is left out when it is clear from context.

  * •

$(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Setup}(1^{\lambda})$: The
probabilistic polynomial-time algorithm $\mathsf{Setup}$ on input
$1^{\lambda}$ outputs a common reference string $\mathsf{crs}$ and a trapdoor
$\mathsf{td}$.

  * •

$\sigma\leftarrow\mathsf{Sign}(1^{\lambda},\mathsf{crs},x,w,m)$: The
polynomial-time quantum algorithm $\mathsf{Sign}$ on input a common reference
string $\mathsf{crs}$, an instance and witness pair
$(x,w)\in{\mathcal{R}}_{\lambda}$, and a message
$m\in{\mathcal{M}}_{\lambda}$, outputs a signature $\sigma$.

  * •

$\mathsf{Verify}(1^{\lambda},\mathsf{crs},x,m,\sigma)\in{\\{0,1\\}}$: The
polynomial-time quantum algorithm $\mathsf{Verify}$ on input a common
reference string $\mathsf{crs}$, an instance $x$, a message
$m\in{\mathcal{M}}_{\lambda}$, and a signature $\sigma$, outputs $1$ iff
$\sigma$ is a valid signature of $m$ with respect to $\mathsf{crs}$,
${\mathcal{R}}_{\lambda}$, and $x$.

Properties.

  * •

Correctness: For every sufficiently large $\lambda\in\mathbb{N}$, every
$(x,w)\in{\mathcal{R}}_{\lambda}$, and every $m\in{\mathcal{M}}_{\lambda}$,

$\Pr_{\begin{subarray}{c}\mathsf{crs}\leftarrow\mathsf{Setup}(1^{\lambda})\\\
\sigma\leftarrow\mathsf{Sign}(\mathsf{crs},x,w,m)\end{subarray}}[\mathsf{Verify}(\mathsf{crs},x,m,\sigma)=1]=1.$

  * •

Simulation: There exists a quantum polynomial-size circuit simulator
$\mathsf{Sim}=(\mathsf{Sim}_{0},\mathsf{Sim}_{1})$, where $\mathsf{Sim}_{1}$
ignores its second query input (a witness $w$), and a negligible function
$\mathsf{negl}(\cdot)$ such that for every polynomial-size quantum circuit
${\mathcal{A}}$ and every sufficiently large $\lambda\in\mathbb{N}$,

$\left|\Pr_{(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})}[{\mathcal{A}}^{\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},\cdot,\cdot)}(\mathsf{crs})=1]-\Pr_{\begin{subarray}{c}\mathsf{crs}\leftarrow\mathsf{Setup}(1^{\lambda})\end{subarray}}[{\mathcal{A}}^{\mathsf{Sign}(\mathsf{crs},\cdot,\cdot,\cdot)}(\mathsf{crs})=1]\right|\leq\mathsf{negl}(\lambda).$

  * •

Extraction: Let $\mathsf{Sim}=(\mathsf{Sim}_{0},\mathsf{Sim}_{1})$ be the
simulator given by the simulation property. There exists a quantum polynomial-
size circuit $\mathsf{Ext}$ and a negligible function $\mathsf{negl}(\cdot)$
such that for every oracle-aided polynomial-size quantum circuit
${\mathcal{A}}$ and every sufficiently large $\lambda\in\mathbb{N}$,

$\displaystyle\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})\\\
(x,m,\sigma)\leftarrow{\mathcal{A}}^{\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},\cdot,\cdot)}(\mathsf{crs})\\\
w\leftarrow\mathsf{Ext}(\mathsf{crs},\mathsf{td},x,m,\sigma)\end{subarray}}\left[\mathsf{Verify}(\mathsf{crs},x,m,\sigma)=1\wedge(x,m)\not\in
Q\wedge(x,w)\not\in{\mathcal{R}}_{\lambda}\right]\leq\mathsf{negl}(\lambda)$

where $Q$ is the list of queries from ${\mathcal{A}}$ to $\mathsf{Sim}_{1}$.

##  4 Unclonable Non-Interactive Zero-Knowledge in the CRS Model

###  4.1 Simulation-Extractable Definition

######  Definition 4.1 (Post-Quantum (Quantum) Simulation-Extractable NIZK for
$\mathsf{NP}$ in CRS Model).

Let $\mathsf{NP}$ relation ${\mathcal{R}}$ with corresponding language
${\mathcal{L}}$ be given such that they can be indexed by a security parameter
$\lambda\in\mathbb{N}$.

$\Pi=(\mathsf{Setup},\mathsf{P},\mathsf{V})$ is a post-quantum (quantum) non-
interactive simulation-extractable zero-knowledge argument for $\mathsf{NP}$
in the CRS model if it has the following syntax and properties.

  * •

$\Pi$ is a post-quantum (quantum) non-interactive simulation sound, adaptive
multi-theorem computational zero-knowledge argument for $\mathsf{NP}$ in the
CRS model (Definition 3.7).

  * •

Simulation Extractability. Let
$\mathsf{Sim}=(\mathsf{Sim}_{0},\mathsf{Sim}_{1})$ be the simulator given by
the adaptive multi-theorem computational zero-knowledge property. There exists
a (quantum) polynomial-time circuit $\mathsf{Ext}$ and a negligible function
$\mathsf{negl}(\cdot)$ such that for every oracle-aided polynomial-size
quantum circuit ${\mathcal{A}}$ and every $\lambda\in\mathbb{N}$,

$\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})\\\
(x,\pi)\leftarrow{\mathcal{A}}^{\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},\cdot)}(\mathsf{crs})\\\
w\leftarrow\mathsf{Ext}(\mathsf{crs},\mathsf{td},x,\pi)\end{subarray}}[\mathsf{V}(\mathsf{crs},x,\pi)=1\wedge
x\not\in Q\wedge(x,w)\not\in{\mathcal{R}}]\leq\mathsf{negl}(\lambda),$

where $Q$ is the list of queries from ${\mathcal{A}}$ to $\mathsf{Sim}_{1}$.

######  Remark 4.1.

As defined in Definition 4.1, a simulation-extractable zero-knowledge protocol
has simulation soundness [Sah99, SCO+01], is a proof of knowledge, and has
adaptive computational soundness (Definition 3.5).

Simulation-Extractable Non-Interactive ZK for ${\mathcal{L}}\in\mathsf{NP}$

Let $\Pi=(\mathsf{Setup},\mathsf{P},\mathsf{V})$ be a non-interactive
simulation sound, adaptively multi-theorem computationally zero-knowledge
protocol for $\mathsf{NP}$, and $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ be
a post-quantum perfectly correct, IND-CPA secure encryption scheme. Let
${\mathcal{R}}$ be the relation with respect to ${\mathcal{L}}\in\mathsf{NP}$.

Setup$(1^{\lambda})$: Compute
$(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Gen}(1^{\lambda})$, and
$(\mathsf{crs}_{\Pi},\mathsf{td}_{\Pi})\leftarrow\Pi.\mathsf{Setup}(1^{\lambda})$.
Output
$(\mathsf{crs}=(\mathsf{pk},\mathsf{crs}_{\Pi}),\mathsf{td}=(\mathsf{sk},\mathsf{td}_{\Pi}))$.

Prove$(\mathsf{crs},x,w)$:

  * •

Compute $\mathsf{ct}=\mathsf{Enc}(\mathsf{pk},w;r)$ for $r$ sampled uniformly
at random.

  * •

Let $x_{\Pi}=(\mathsf{pk},x,\mathsf{ct})$ be an instance of the following
language ${\mathcal{L}}_{\Pi}$:

$\\{(\mathsf{pk},x,\mathsf{ct})\>:\>\exists(w,r)\>:\>\mathsf{ct}=\mathsf{Enc}(\mathsf{pk},w;r)\>\wedge\>(x,w)\in{\mathcal{R}}\\}.$

  * •

Compute proof
$\pi_{\Pi}\leftarrow\Pi.\mathsf{P}(\mathsf{crs}_{\Pi},x_{\Pi},(w,r))$ for
language ${\mathcal{L}}_{\Pi}$.

  * •

Output $\pi=(\mathsf{ct},\pi_{\Pi})$.

Verify$(\mathsf{crs},x,\pi)$:

  * •

Output $\Pi.\mathsf{V}(\mathsf{crs}_{\Pi},x_{\Pi},\pi_{\Pi})$.

Figure 1: Unclonable Non-Interactive Quantum Protocol for
${\mathcal{L}}\in\mathsf{NP}$

######  Theorem 4.2 (Post-Quantum Simulation-Extractable NIZK for
$\mathsf{NP}$ in the CRS Model).

Let $\mathsf{NP}$ relation ${\mathcal{R}}$ with corresponding language
${\mathcal{L}}$ be given.

Let $\Pi=(\mathsf{Setup},\mathsf{P},\mathsf{V})$ be a non-interactive post-
quantum simulation sound, adaptively multi-theorem computationally zero-
knowledge protocol for $\mathsf{NP}$ (Definition 3.7). Let
$(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ be a post-quantum perfectly
correct, IND-CPA secure encryption scheme (Definition 3.3).

$(\mathsf{Setup},\mathsf{P},\mathsf{V})$ as defined in Figure 1 will be a non-
interactive post-quantum simulation-extractable, adaptively multi-theorem
computationally zero-knowledge argument for ${\mathcal{L}}$ in the common
reference string model (Definition 4.1).

###### Proof.

Perfect Completeness. Completeness follows from the perfect completeness of
$\Pi$.

Adaptively Multi-theorem Computationally Zero-Knowledge. Let
$\Pi.\mathsf{Sim}=(\Pi.\mathsf{Sim}_{0},\Pi.\mathsf{Sim}_{1})$ be the adaptive
multi-theorem computationally zero-knowledge simulator of $\Pi$. We define
$\mathsf{Sim}_{0}$ with oracle access to $\Pi.\mathsf{Sim}_{0}$ as follows:
[2em]2em _Input_ : $1^{\lambda}$.

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

(2) Send $1^{\lambda}$ to $\Pi.\mathsf{Sim}_{0}$. Receive
$(\mathsf{crs}_{\Pi},\mathsf{td}_{\Pi})$ from $\Pi.\mathsf{Sim}_{0}$.

(3) Output
$(\mathsf{crs}=(\mathsf{pk},\mathsf{crs}_{\Pi}),\mathsf{td}=(\mathsf{sk},\mathsf{td}_{\Pi}))$.
We define $\mathsf{Sim}_{1}$ with oracle access to $\Pi.\mathsf{Sim}_{1}$ as
follows: [2em]2em _Input_ : $\mathsf{crs}=(\mathsf{pk},\mathsf{crs}_{\Pi})$,
$\mathsf{td}=(\mathsf{sk},\mathsf{td}_{\Pi})$, $x$.

(1) Compute $\mathsf{ct}=\mathsf{Enc}(\mathsf{pk},0;r)$ for $r$ sampled
uniformly at random.

(2) Define $x_{\Pi}=(\mathsf{pk},x,\mathsf{ct})$.

(3) Send $(\mathsf{crs}_{\Pi},\mathsf{td}_{\Pi},x_{\Pi})$ to
$\Pi.\mathsf{Sim}_{1}$. Receive $\pi_{\Pi}$.

(4) Output $\pi=(\mathsf{ct},\pi_{\Pi})$.

Let a polynomial $p(\cdot)$ and an oracle-aided polynomial-size quantum
circuit ${\mathcal{A}}$ be given such that

$\left|\Pr_{\begin{subarray}{c}\mathsf{crs}\leftarrow\mathsf{Setup}(1^{\lambda})\end{subarray}}[{\mathcal{A}}^{\mathsf{P}(\mathsf{crs},\cdot,\cdot)}(\mathsf{crs})=1]-\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})\end{subarray}}[{\mathcal{A}}^{\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},\cdot)}(\mathsf{crs})=1]\right|\geq\frac{1}{p(\lambda)}.$
(1)

We will first switch the honest proofs for simulated proofs, using the
adaptive multi-theorem zero-knowledge of $\Pi$. Later, we will see how we can
switch the encryption of a valid witness to an encryption of $0$, by using the
security of the encryption scheme.

Towards this end, we define an intermediary circuit
${\mathcal{B}}=({\mathcal{B}}_{0},{\mathcal{B}}_{1})$ which encrypts a valid
witness, but provides simulated proofs through $\Pi.\mathsf{Sim}_{1}$. We
define ${\mathcal{B}}_{0}$ to be equivalent to $\mathsf{Sim}_{0}$. We define
${\mathcal{B}}_{1}$ with oracle access to $\Pi.\mathsf{Sim}_{1}$ as follows:
[2em]2em _Input_ : $\mathsf{crs}=(\mathsf{pk},\mathsf{crs}_{\Pi})$,
$\mathsf{td}=(\mathsf{sk},\mathsf{td}_{\Pi})$, $x$, $w$.

(1) Compute $\mathsf{ct}=\mathsf{Enc}(\mathsf{pk},w;r)$ for $r$ sampled
uniformly at random.

(2) Define $x_{\Pi}=(\mathsf{pk},x,\mathsf{ct})$.

(3) Send $(\mathsf{crs}_{\Pi},\mathsf{td}_{\Pi},x_{\Pi})$ to
$\Pi.\mathsf{Sim}_{1}$. Receive $\pi_{\Pi}$.

(4) Output $\pi=(\mathsf{ct},\pi_{\Pi})$.

######  Claim 4.3.

There exists a negligible function $\mathsf{negl}(\cdot)$ such that for every
oracle-aided polynomial-size quantum circuit ${\mathcal{A}}$,

$\left|\Pr_{\begin{subarray}{c}\mathsf{crs}\leftarrow\mathsf{Setup}(1^{\lambda})\end{subarray}}[{\mathcal{A}}^{\mathsf{P}(\mathsf{crs},\cdot,\cdot)}(\mathsf{crs})=1]-\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow{\mathcal{B}}_{0}(1^{\lambda})\end{subarray}}[{\mathcal{A}}^{{\mathcal{B}}_{1}(\mathsf{crs},\mathsf{td},\cdot,\cdot)}(\mathsf{crs})=1]\right|\leq\mathsf{negl}(\lambda).$

We will later see a proof of Claim 4.3. For now, assuming that this claim
holds, by Equation 2, this claim, and a union bound, there exists a polynomial
$p^{\prime}(\cdot)$ such that

$\left|\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow{\mathcal{B}}_{0}(1^{\lambda})\end{subarray}}[{\mathcal{A}}^{{\mathcal{B}}_{1}(\mathsf{crs},\mathsf{td},\cdot,\cdot)}(\mathsf{crs})=1]-\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})\end{subarray}}[{\mathcal{A}}^{\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},\cdot)}(\mathsf{crs})=1]\right|\geq\frac{1}{p^{\prime}(\lambda)}.$

We define a series of intermediary hybrids starting from encrypting all real
witnesses to encrypting all zeros. The first intermediary hybrid switches the
encryption sent in the last query from an encryption of a witness to an
encryption of $0$. We continue switching the encryption in the second to last
query and so on, until we’ve switched the first proof that the adversary
makes.

Let $q(\cdot)$ be a polynomial denoting the maximum number of queries that
${\mathcal{A}}$ makes. By a union bound and Equation 2, there must exist a
hybrid indexed by $i$ (where we switch the ciphertext in the $i$th proof from
encrypting a witness to encrypting $0$) where ${\mathcal{A}}$ first
distinguishes between the two ciphertexts with advantage
$1/(p^{\prime}(\lambda)q(\lambda))$. That is,

$\left|\Pr_{\begin{subarray}{c}\mathsf{crs}\leftarrow\mathsf{Setup}(1^{\lambda})\end{subarray}}[{\mathcal{A}}^{\mathsf{Sim}_{1}^{(i+1)}(\mathsf{crs},\cdot,\cdot)}(\mathsf{crs})=1]-\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Setup}(1^{\lambda})\end{subarray}}[{\mathcal{A}}^{\mathsf{Sim}_{1}^{(i)}(\mathsf{crs},\mathsf{td},\cdot)}(\mathsf{crs})=1]\right|\geq\frac{1}{p^{\prime}(\lambda)q(\lambda)}.$
(2)

where $\mathsf{Sim}^{(j)}_{1}$ is a stateful algorithm which sends real proofs
for the first $j-1$ queries and sends simulated proofs for the remaining
queries.

We can use ${\mathcal{A}}$ to define a reduction that breaks the IND-CPA
security of the encryption scheme as follows: [2em]2em Reduction: to IND-CPA
of encryption scheme given oracle access to ${\mathcal{A}}$,
$\mathsf{Sim}_{0}$, and $\mathsf{Sim}_{1}$.

Hardwired with: $i$.

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

(2) Compute
$(\mathsf{crs}_{\Pi},\mathsf{td}_{\Pi})\leftarrow\Pi.\mathsf{Sim}_{0}(1^{\lambda})$.

(3) Define $\mathsf{crs}=(\mathsf{pk},\mathsf{crs}_{\Pi})$ and
$\mathsf{td}=(\mathsf{sk},\mathsf{td}_{\Pi})$.

(4) Send $\mathsf{crs}$ to ${\mathcal{A}}$.

(5) On the first $i-1$ queries $(x,w)$ from ${\mathcal{A}}$: send
$\pi\leftarrow{\mathcal{B}}_{0}(\mathsf{crs},x,w)$ to ${\mathcal{A}}$.

(6) On the $i$th query $(x,w)$ from ${\mathcal{A}}$: send $(w,0)$ to the
challenger, receive $\mathsf{ct}$ from the challenger, define
$x_{\Pi}=(\mathsf{pk},x,\mathsf{ct})$, send
$(\mathsf{crs}_{\Pi},\mathsf{td}_{\Pi},x_{\Pi})$ to $\Pi.\mathsf{Sim}_{1}$,
receive $\pi_{\Pi}$ from $\Pi.\mathsf{Sim}_{1}$, and send
$\pi=(\mathsf{ct},\pi_{\Pi})$ to ${\mathcal{A}}$.

(7) On any queries $(x,w)$ after the $i$th: send
$\pi\leftarrow\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},x)$ to
${\mathcal{A}}$.

(8) Output the result of ${\mathcal{A}}$. The view of ${\mathcal{A}}$ matches
that of $\mathsf{Sim}_{1}^{(i+1)}$ or $\mathsf{Sim}_{1}^{(i)}$. As such, this
reduction should have the same advantage at breaking the IND-CPA security of
the encryption scheme. We reach a contradiction. Now, all that remains to
prove that our earlier claim holds.

###### Proof of Claim 4.3.

Let a polynomial $p(\cdot)$ and an oracle-aided polynomial-size quantum
circuit ${\mathcal{A}}$ be given such that

$\left|\Pr_{\begin{subarray}{c}\mathsf{crs}\leftarrow\mathsf{Setup}(1^{\lambda})\end{subarray}}[{\mathcal{A}}^{\mathsf{P}(\mathsf{crs},\cdot,\cdot)}(\mathsf{crs})=1]-\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow{\mathcal{B}}_{0}(1^{\lambda})\end{subarray}}[{\mathcal{A}}^{{\mathcal{B}}_{1}(\mathsf{crs},\mathsf{td},\cdot,\cdot)}(\mathsf{crs})=1]\right|\geq\frac{1}{p(\lambda)}.$

We define a reduction to the multi-theorem zero-knowledge property of $\Pi$ as
follows: [2em]2em Reduction: to multi-theorem zero-knowledge of $\Pi$ given
oracle access to ${\mathcal{A}}$.

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

(2) Receive (real or simulated) $\mathsf{crs}_{\Pi}$ from the challenger.

(3) Send $\mathsf{crs}=(\mathsf{pk},\mathsf{crs}_{\Pi})$ to ${\mathcal{A}}$.

(4) On query $(x,w)$ from ${\mathcal{A}}$: compute
$\mathsf{ct}=\mathsf{Enc}(\mathsf{pk},w;r)$ for $r$ samples uniformly at
random, send $x_{\Pi}=(\mathsf{pk},x,\mathsf{ct})$ to the challenger, receive
(real or simulated) $\pi_{\Pi}$ from the challenger, send
$\pi=(\mathsf{ct},\pi_{\Pi})$ to ${\mathcal{A}}$.

(5) Output the result of ${\mathcal{A}}$. The view of ${\mathcal{A}}$ matches
that of $\mathsf{Setup}$ and $\mathsf{P}$ or ${\mathcal{B}}_{0}$ and
${\mathcal{B}}_{1}$. As such, this reduction should have the same advantage at
breaking the multi-theorem zero-knowledge property of $\Pi$. We reach a
contradiction, hence our claim must be true. ∎

This concludes our proof. Hence our protocol must be multi-theorem zero-
knowledge.

Simulation Extractable. Let
$\Pi.\mathsf{Sim}=(\Pi.\mathsf{Sim}_{0},\Pi.\mathsf{Sim}_{1})$ be the adaptive
multi-theorem computationally zero-knowledge simulator of $\Pi$. Let
$\mathsf{Sim}=(\mathsf{Sim}_{0},\mathsf{Sim}_{1})$ be the simulator, with
oracle access to $\Pi.\mathsf{Sim}$, as defined in the proof that Figure 1 is
adaptive multi-theorem computational zero-knowledge. We define $\mathsf{Ext}$
as follows: [2em]2em _Input_ :
$\mathsf{crs}=(\mathsf{pk},\mathsf{crs}_{\Pi})$,
$\mathsf{td}=(\mathsf{sk},\mathsf{td}_{\Pi})$, $x$,
$\pi=(\mathsf{ct},\pi_{\Pi})$.

(1) Output $\mathsf{Dec}(\mathsf{sk},\mathsf{ct})$ as $w$.

Let a polynomial $p(\cdot)$ and an oracle-aided polynomial-size quantum
circuit ${\mathcal{A}}$ be given such that

$\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})\\\
(x,\pi)\leftarrow{\mathcal{A}}^{\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},\cdot)}(\mathsf{crs})\\\
w\leftarrow\mathsf{Ext}(\mathsf{crs},\mathsf{td},x,\pi)\end{subarray}}[\mathsf{V}(\mathsf{crs},x,\pi)=1\wedge
x\not\in Q\wedge(x,w)\not\in{\mathcal{R}}]\geq\frac{1}{p(\lambda)},$

where $Q$ is the list of queries from ${\mathcal{A}}$ to $\mathsf{Sim}_{1}$.
Since $\mathsf{V}$ accepts the output of ${\mathcal{A}}$, then
$\Pi.\mathsf{V}$ must accept $(\mathsf{crs}_{\Pi},x_{\Pi},\pi_{\Pi})$. Since
$x\not\in Q$, then $x_{\Pi}$ which contains $x$ must not have been sent as a
query to $\Pi.\mathsf{Sim}_{1}$. By the definition of $\mathsf{Ext}$ and the
perfect correctness of the encryption scheme,
$x_{\Pi}\not\in{\mathcal{L}}_{\Pi}$. Hence, we have that

$\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})\\\
(x,\pi)\leftarrow{\mathcal{A}}^{\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},\cdot)}(\mathsf{crs})\\\
w\leftarrow\mathsf{Ext}(\mathsf{crs},\mathsf{td},x,\pi)\end{subarray}}[\Pi.\mathsf{V}(\mathsf{crs}_{\Pi},x_{\Pi},\pi_{\Pi})=1\wedge
x_{\Pi}\not\in Q_{\Pi}\wedge
x_{\Pi}\not\in{\mathcal{L}}_{\Pi}]\geq\frac{1}{p(\lambda)},$

where $Q_{\Pi}$ is the list of queries, originating from ${\mathcal{A}}$, that
$\mathsf{Sim}_{1}$ makes to $\Pi.\mathsf{Sim}_{1}$. We define a reduction to
the simulation soundness property of $\Pi$ as follows: [2em]2em Reduction: to
simulation soundness of $\Pi$ given oracle access to ${\mathcal{A}}$.

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

(2) Receive $\mathsf{crs}_{\Pi}$ from the challenger.

(3) Send $\mathsf{crs}=(\mathsf{pk},\mathsf{crs}_{\Pi})$ to ${\mathcal{A}}$.

(4) On query $x$ from ${\mathcal{A}}$: compute
$\mathsf{ct}=\mathsf{Enc}(\mathsf{pk},0;r)$ for $r$ samples uniformly at
random, send $x_{\Pi}=(\mathsf{pk},x,\mathsf{ct})$ to the challenger, receives
$\pi_{\Pi}$ from the challenger, send $\pi=(\mathsf{ct},\pi_{\Pi})$ to
${\mathcal{A}}$.

(5) Receive $(x,\pi=(\mathsf{ct},\pi_{\Pi}))$ from ${\mathcal{A}}$. Define
$x_{\Pi}=(\mathsf{pk},x,\mathsf{ct})$.

(6) Output $(x_{\Pi},\pi_{\Pi})$. The view of ${\mathcal{A}}$ matches that of
$\mathsf{Sim}_{0}$ and $\mathsf{Sim}_{1}$. As such, this reduction should have
the same advantage at breaking the simulation soundness property of $\Pi$. We
reach a contradiction, hence our protocol must be simulation extractable. ∎

######  Corollary 4.4 (Post-Quantum Simulation-Extractable NIZK for
$\mathsf{NP}$ in the CRS Model).

Assuming the polynomial quantum hardness of LWE, there exists a simulation-
extractable, adaptively multi-theorem computationally zero-knowledge argument
for $\mathsf{NP}$ in the common reference string model (Definition 4.1).

###### Proof.

This follows from Corollary 3.9 and Theorem 4.2. ∎

###  4.2 Unclonability Definitions

We consider two definitions of unclonability for NIZKs. The first one,
motivated by simplicity, informally guarantees that no adversary given
honestly proofs for “hard” instances is able to output more than one accepting
proof for the same instance.

######  Definition 4.5 ((Quantum) Hard Distribution).

Let an $\mathsf{NP}$ relation ${\mathcal{R}}$ be given.
$({\mathcal{X}},{\mathcal{W}})$ is a (quantum) hard distribution over
${\mathcal{R}}$ if the following properties hold.

  * •

Syntax. $({\mathcal{X}},{\mathcal{W}})$ is indexable by a security parameter
$\lambda\in\mathbb{N}$. For every choice of $\lambda\in\mathbb{N}$, the
support of $({\mathcal{X}}_{\lambda},{\mathcal{W}}_{\lambda})$ is over
instance and witness pairs $(x,w)$ such that $x\in{\mathcal{L}}$,
$|x|=\lambda$, and $(x,w)\in{\mathcal{R}}$.

  * •

Hardness. For every polynomial-sized (quantum) circuit family
${\mathcal{A}}=\\{{\mathcal{A}}_{\lambda}\\}_{\lambda\in\mathbb{N}}$,

$\Pr_{(x,w)\leftarrow({\mathcal{X}}_{\lambda},{\mathcal{W}}_{\lambda})}[(x,{\mathcal{A}}_{\lambda}(x))\in{\mathcal{R}}]\leq\mathsf{negl}(\lambda).$

######  Definition 4.6.

(Unclonable Security for Hard Instances). A proof
$(\mathsf{Setup},\mathsf{P},\mathsf{V})$ satisfies unclonable security for a
language $\mathcal{L}$ with corresponding relation
${\mathcal{R}}_{\mathcal{L}}$ if for every polynomial-sized quantum circuit
family $\\{C_{\lambda}\\}_{\lambda\in\mathbb{N}}$, and for every hard
distribution
$\\{\mathcal{X}_{\lambda},\mathcal{W}_{\lambda}\\}_{\lambda\in\mathbb{N}}$
over ${\mathcal{R}}_{\mathcal{L}}$, there exists a negligible function
$\mathsf{negl}(\cdot)$ such that for every $\lambda\in\mathbb{N}$,

$\Pr_{(x,w)\leftarrow(\mathcal{X}_{\lambda},\mathcal{W}_{\lambda})}\Bigg{[}\mathsf{V}(\mathsf{crs},x,\pi_{1})=1\bigwedge\mathsf{V}(\mathsf{crs},x,\pi_{2})=1\Bigg{|}\begin{subarray}{c}\mathsf{crs}\leftarrow\mathsf{Setup}(1^{\lambda})\\\
\pi\leftarrow\mathsf{P}(\mathsf{crs},x,w)\\\ \pi_{1},\pi_{2}\leftarrow
C_{\lambda}(x,\pi)\end{subarray}\Bigg{]}\leq\mathsf{negl}(\lambda).$

We will now strengthen this definition to consider a variant where from any
adversary ${\mathcal{A}}$ that on input a single proof of membership of
$x\in{\mathcal{L}}$ outputs two proofs for $x$, we can extract a valid witness
$w$ for $x$ with high probability. In fact, we can further generalize this
definition to a setting where the adversary obtains an even larger number (say
$k-1$) input proofs on instances $x_{1},\ldots,x_{k-1}$, and outputs $k$ or
more proofs. Then we require the extraction of an NP witness corresponding to
any proofs that are duplicated (i.e. two or more proofs w.r.t. the same
instance $x_{i}\in\\{x_{1},\ldots,x_{k-1}\\}$). We write this definition
below.

######  Definition 4.7 ($(k-1)\text{-to-}k$-Unclonable Extractable NIZK).

Let security parameter $\lambda\in\mathbb{N}$ and $\mathsf{NP}$ relation
${\mathcal{R}}$ with corresponding language ${\mathcal{L}}$ be given. Let
$\Pi=(\mathsf{Setup},\mathsf{P},\mathsf{V})$ be given such that
$\mathsf{Setup},\mathsf{P}$ and $\mathsf{V}$ are $\mathsf{poly}(\lambda)$-size
quantum algorithms. We have that for any $(x,w)\in{\mathcal{R}}$,
$(\mathsf{crs},\mathsf{td})$ is the output of $\mathsf{Setup}$ on input
$1^{\lambda}$, $\mathsf{P}$ receives an instance and witness pair $(x,w)$
along with $\mathsf{crs}$ as input and outputs $\pi$, and $\mathsf{V}$
receives an instance $x$, $\mathsf{crs}$, and proof $\pi$ as input and outputs
a value in ${\\{0,1\\}}$.

$\Pi$ is a non-interactive $(k-1)\text{-to-}k$-unclonable zero-knowledge
quantum protocol for language ${\mathcal{L}}$ if the following holds:

  * •

$\Pi$ is a quantum non-interactive zero-knowledge protocol for language
${\mathcal{L}}$ (Definition 3.5).

  * •

$(k-1)\text{-to-}k$-Unclonable with Extraction: There exists an oracle-aided
polynomial-size quantum circuit ${\mathcal{E}}$ such that for every
polynomial-size quantum circuit ${\mathcal{A}}$, for every tuple of $k-1$
instance-witness pairs
$(x_{1},\omega_{1}),\ldots,(x_{k-1},\omega_{k-1})\in{\mathcal{R}}$, for every
$x$ where we define

    * –

${\mathcal{I}}\subseteq[k-1]$ such that $|{\mathcal{I}}|\geq 1$, $x_{i}=x$ for
all $i\in{\mathcal{I}}$, and $x_{\iota}\neq x$ for all
$\iota\not\in{\mathcal{I}}$, and

    * –

${\mathcal{J}}\subseteq[k]$ such that
$|{\mathcal{J}}|\geq\max\\{2,|{\mathcal{I}}|\\}$, $x_{j}=x$ for all
$j\in{\mathcal{J}}$, and $x_{\iota}\neq x$ for $\iota\not\in{\mathcal{J}}$,

such that there is a polynomial $p(\cdot)$ where

$\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Setup}(1^{\lambda})\\\
\forall\iota\in[k-1],\>\pi_{\iota}\leftarrow\mathsf{P}(\mathsf{crs},x_{\iota},w_{\iota})\\\
\\{\widetilde{x_{\iota}},\widetilde{\pi_{\iota}}\\}_{\iota\in[k]}\leftarrow{\mathcal{A}}(\mathsf{crs},\\{x_{\iota},\pi_{\iota}\\}_{\iota\in[k-1]})\end{subarray}}\left[\bigwedge_{\iota\in{\mathcal{J}}}\mathsf{V}(\mathsf{crs},x,\widetilde{\pi_{\iota}})=1\right]\geq\frac{1}{p(\lambda)},$

then there is also a polynomial $q(\cdot)$ such that

$\Pr_{w\leftarrow{\mathcal{E}}^{\mathcal{A}}(x_{1},\ldots,x_{k-1},x,{\mathcal{I}},{\mathcal{J}})}\left[(x,w)\in{\mathcal{R}}\right]\geq\frac{1}{q(\lambda)}.$

We describe a useful lemma to compare our two definitions.

######  Lemma 4.8.

Let $\Pi=(\mathsf{Setup},\mathsf{P},\mathsf{V})$ be a
$1\text{-to-}2$-unclonable with extraction, non-interactive zero-knowledge
quantum protocol (Definition 4.7). Then, $\Pi$ satisfies Definition 4.6.

For a proof of Lemma 4.8, we refer to Appendix A.

###  4.3 Unclonable NIZK Implies Public-Key Quantum Money Mini-Scheme

Public-Key Quantum Money Mini-Scheme

Let $({\mathcal{X}},{\mathcal{W}})$ be a hard distribution over a language
${\mathcal{L}}\in\mathsf{NP}$. Let
$\Pi=(\mathsf{Setup},\mathsf{P},\mathsf{V})$ be an unclonable non-interactive
zero-knowledge protocol for ${\mathcal{L}}$.

Gen$(1^{\lambda})$: Sample a hard instance-witness pair
$(x,w)\leftarrow({\mathcal{X}},{\mathcal{Y}})$, a common reference string
$\mathsf{crs}\leftarrow\mathsf{Setup}(1^{\lambda},x)$, and a proof
$\pi\leftarrow\mathsf{P}(\mathsf{crs},x,w)$. Output
$(\ket{\$}=\pi,s=(\mathsf{crs},x))$.

Verify$(\ket{\$},s)$: Parse $\ket{\$}=\pi$ and $s=(\mathsf{crs},x)$. Output
$\mathsf{V}(\mathsf{crs},x,\pi)$.

Figure 2: Public-Key Quantum Money Mini-Scheme from an Unclonable Non-
Interactive Quantum Protocol

######  Theorem 4.9.

Let $({\mathcal{X}},{\mathcal{W}})$ be a hard distribution over a language
${\mathcal{L}}\in\mathsf{NP}$. Let
$\Pi=(\mathsf{Setup},\mathsf{P},\mathsf{V})$ satisfy Definition 4.6. Then
$(\mathsf{Setup},\mathsf{P},\mathsf{V})$ implies a public-key quantum money
scheme mini-scheme (Definition 3.13) as described in Figure 2.

###### Proof.

Perfect Correctness. This follows directly from the perfect completeness of
$\Pi$.

Unforgeability. Let $p(\cdot)$ be a polynomial and ${\mathcal{A}}$ be a
quantum polynomial-time adversary such that for an infinite number of
$\lambda\in\mathbb{N}^{+}$,

$\Pr_{\begin{subarray}{c}(\ket{\$},s)\leftarrow\mathsf{Gen}(1^{\lambda})\\\
(\ket{\$_{0}},s_{0},\ket{\$_{1}},s_{1})\leftarrow{\mathcal{A}}(\ket{\$},s)\end{subarray}}[s_{0}=s_{1}=s\>\land\>\mathsf{Ver}(\ket{\$_{0}},s_{0})=1\>\land\>\mathsf{Ver}(\ket{\$_{1}},s_{1})=1]\geq\frac{1}{p(\lambda)}.$

We construct a reduction that breaks the uncloneability definition. The
challenger samples a hard instance-witness pair
$(x,w)\leftarrow({\mathcal{X}},{\mathcal{Y}})$, a common reference string
$\mathsf{crs}\leftarrow\mathsf{Setup}(1^{\lambda},x)$, and a proof
$\pi\leftarrow\mathsf{P}(\mathsf{crs},x,w)$. The challenger then forwards
$(\mathsf{crs},x,\pi)$ to the reduction. The reduction then sets
$\ket{\$}=\pi$ and $s=(\mathsf{crs},x)$. The reduction sends $(\ket{\$},s)$ to
the adversary ${\mathcal{A}}$ who returns back
$(\ket{\$_{0}},s_{0},\ket{\$_{1}},s_{1})$. The reduction then parses and sets
$\pi_{i}=\ket{\$_{i}}$ for $i\in\\{0,1\\}$. The reduction then sends $\pi_{0}$
and $\pi_{1}$ back to the challenger.

When the serial numbers are the same, $s=s_{0}=s_{1}$, we have that the common
reference string and instance will be the same for all the proofs
$\pi,\pi_{0},\pi_{1}$. The quantum money state can be parsed as the proof as
shown in the construction. When the verification algorithm of the quantum
money algorithm accepts both quantum money states $\ket{\$_{0}}$ and
$\ket{\$_{1}}$ with respect to $s$, we know that that $\mathsf{V}$ would
accept both proofs $\pi_{0}$ and $\pi_{1}$ with respect to $(\mathsf{crs},x)$.
As such, we will have that the advantage that ${\mathcal{A}}$ has at breaking
the unforgeability of our quantum money scheme directly translates to the
advantage of the reduction at breaking the uncloneability of $\Pi$. ∎

###  4.4 Construction and Analysis of Unclonable NIZK from Public-Key Quantum
Money

Unclonable Non-Interactive ZK for ${\mathcal{L}}\in\mathsf{NP}$

Let $\Pi=(\mathsf{Setup},\mathsf{P},\mathsf{V})$ be a non-interactive
simulation-extractable, adaptively multi-theorem computationally zero-
knowledge protocol for $\mathsf{NP}$, $\mathsf{Com}$ be a post-quantum
perfectly binding, computationally hiding commitment scheme, and
$(\mathsf{NoteGen},\mathsf{Ver})$ be a public-key quantum money scheme. Let
${\mathcal{R}}$ be the relation with respect to ${\mathcal{L}}\in\mathsf{NP}$.

Setup$(1^{\lambda})$: Sample the common reference string
$(\mathsf{crs}_{\Pi},\mathsf{td}_{\Pi})\leftarrow\Pi.\mathsf{Setup}(1^{\lambda})$,
and $s^{*},r^{*}$ uniformly at random. Define $c=\mathsf{Com}(s^{*};r^{*})$
and output
$(\mathsf{crs}=(\mathsf{crs}_{\Pi},c),\mathsf{td}=\mathsf{td}_{\Pi})$.

Prove$(\mathsf{crs},x,w)$:

  * •

Compute a quantum note and associated serial number
$(\ket{\$},s)\leftarrow\mathsf{NoteGen}$.

  * •

Let $x_{\Pi}=(c,x,s)$ be an instance of the following language
${\mathcal{L}}_{\Pi}$:

$\\{(c,x,s)\>:\>\exists
z\>:\>(x,z)\in{\mathcal{R}}\>\vee\>c=\mathsf{Com}(s;z)\\}.$

  * •

Compute proof
$\pi_{\Pi}\leftarrow\Pi.\mathsf{P}(\mathsf{crs}_{\Pi},x_{\Pi},w)$ for language
${\mathcal{L}}_{\Pi}$.

  * •

Output $\pi=(\ket{\$},s,\pi_{\Pi})$.

Verify$(\mathsf{crs},x,\pi)$:

  * •

Check that $\mathsf{Ver}(\ket{\$},s)$ outputs $1$ and that
$\Pi.\mathsf{V}(\mathsf{crs}_{\Pi},x_{\Pi},\pi_{\Pi})$ outputs $1$.

  * •

If both checks pass, output $1$. Otherwise, output $0$.

Figure 3: Unclonable Non-Interactive Quantum Protocol for
${\mathcal{L}}\in\mathsf{NP}$

######  Theorem 4.10.

Let $k(\cdot)$ be a polynomial. Let $\mathsf{NP}$ relation ${\mathcal{R}}$
with corresponding language ${\mathcal{L}}$ be given.

Let $(\mathsf{NoteGen},\mathsf{Ver})$ be a public-key quantum money mini-
scheme (Definition 3.13) and $\mathsf{Com}$ be a post-quantum commitment
scheme (Definition 3.1). Let $\Pi=(\mathsf{Setup},\mathsf{P},\mathsf{V})$ be a
non-interactive post-quantum simulation-extractable, adaptive multi-theorem
computational zero-knowledge protocol for $\mathsf{NP}$ (Definition 4.1).

$(\mathsf{Setup},\mathsf{P},\mathsf{V})$ as defined in Figure 3 will be a non-
interactive quantum simulation-extractable, adaptive multi-theorem
computationally zero-knowledge, and $(k-1)$-to-$k$-unclonable with extraction
protocol for ${\mathcal{L}}$ in the common reference string model (Definition
4.7).

###### Proof.

Perfect Completeness. Completeness follows from perfect correctness of the
public key quantum money scheme, and perfect completeness of $\Pi$.

Adaptive Multi-Theorem Computational Zero-Knowledge. Let
$\Pi.\mathsf{Sim}=(\Pi.\mathsf{Sim}_{0},\Pi.\mathsf{Sim}_{1})$ be the adaptive
multi-theorem computationally zero-knowledge simulator of $\Pi$. We define
$\mathsf{Sim}_{0}$ with oracle access to $\Pi.\mathsf{Sim}_{0}$ as follows:
[2em]2em _Input_ : $1^{\lambda}$.

(1) Send $1^{\lambda}$ to $\Pi.\mathsf{Sim}_{0}$. Receive
$(\mathsf{crs}_{\Pi},\mathsf{td}_{\Pi})$ from $\Pi.\mathsf{Sim}_{0}$.

(2) Sample $s^{*},r^{*}$ uniformly at random. Define
$c=\mathsf{Com}(s^{*};r^{*})$.

(3) Output $\mathsf{crs}=(\mathsf{crs}_{\Pi},c)$ and
$\mathsf{td}=\mathsf{td}_{\Pi}$. We define $\mathsf{Sim}_{1}$ with oracle
access to $\Pi.\mathsf{Sim}_{1}$ as follows: [2em]2em _Input_ :
$\mathsf{crs}=(\mathsf{crs}_{\Pi},c)$, $\mathsf{td}=\mathsf{td}_{\Pi}$, $x$.

(1) Sample $(\ket{\$},s)\leftarrow\mathsf{NoteGen}(1^{\lambda})$.

(2) Define $x_{\Pi}=(c,x,s)$. Send
$(\mathsf{crs}_{\Pi},\mathsf{td}_{\Pi},x_{\Pi})$ to $\Pi.\mathsf{Sim}_{1}$.
Receive $\pi_{\Pi}$ from $\Pi.\mathsf{Sim}_{1}$.

(3) Output $\pi=(\ket{\$},s,\pi_{\Pi})$.

Let a polynomial $p(\cdot)$ and an oracle-aided polynomial-size quantum
circuit ${\mathcal{A}}$ be given such that

$\left|\Pr_{\begin{subarray}{c}\mathsf{crs}\leftarrow\mathsf{Setup}(1^{\lambda})\end{subarray}}[{\mathcal{A}}^{\mathsf{P}(\mathsf{crs},\cdot,\cdot)}(\mathsf{crs})=1]-\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})\end{subarray}}[{\mathcal{A}}^{\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},\cdot)}(\mathsf{crs})=1]\right|\geq\frac{1}{p(\lambda)}.$

We define a reduction to the multi-theorem zero-knowledge property of $\Pi$ as
follows: [2em]2em Reduction: to zero-knowledge of $\Pi$ given oracle access to
${\mathcal{A}}$.

(1) Receive (real or simulated) $\mathsf{crs}_{\Pi}$ from the challenger.

(2) Sample $s^{*},r^{*}$ uniformly at random. Define
$c=\mathsf{Com}(s^{*};r^{*})$ and $\mathsf{crs}=(\mathsf{crs}_{\Pi},c)$.

(3) Send $\mathsf{crs}$ to ${\mathcal{A}}$.

(4) On query $(x,w)$ from ${\mathcal{A}}$: sample
$(\ket{\$},s)\leftarrow\mathsf{NoteGen}(1^{\lambda})$, define
$x_{\Pi}=(c,x,s)$ and $w_{\Pi}=w$, send $(x_{\Pi},w_{\Pi})$ to the challenger,
receive (real or simulated) $\pi_{\Pi}$ from the challenger, define
$\pi=(\ket{\$},s,\pi_{\Pi})$, send $\pi$ to ${\mathcal{A}}$.

(5) Output the result of ${\mathcal{A}}$. The view of ${\mathcal{A}}$ matches
that of our protocol in Figure 3 or $\mathsf{Sim}_{0}$ and $\mathsf{Sim}_{1}$.
As such, this reduction should have the same advantage at breaking the
adaptive multi-theorem computational zero-knowledge property of $\Pi$. We
reach a contradiction, hence our protocol must be multi-theorem zero-
knowledge.

Simulation-Extractability. Let
$\Pi.\mathsf{Sim}=(\Pi.\mathsf{Sim}_{0},\Pi.\mathsf{Sim}_{1})$ be the adaptive
multi-theorem computationally zero-knowledge simulator of $\Pi$. Let
$\Pi.\mathsf{Ext}$ be the simulation-extraction extractor of $\Pi$ with
respect to $\Pi.\mathsf{Sim}$. Let
$\mathsf{Sim}=(\mathsf{Sim}_{0},\mathsf{Sim}_{1})$ be the simulator, with
oracle access to $\Pi.\mathsf{Sim}$, as defined in the proof that Figure 3 is
adaptive multi-theorem computational zero-knowledge. We define $\mathsf{Ext}$
with oracle access to $\Pi.\mathsf{Ext}$ as follows: [2em]2em _Input_ :
$\mathsf{crs}=(\mathsf{crs}_{\Pi},c)$, $\mathsf{td}=\mathsf{td}_{\Pi}$, $x$,
$\pi=(\ket{\$},s,\pi_{\Pi})$.

(1) Define $x_{\Pi}=(c,x,s)$. Send
$(\mathsf{crs}_{\Pi},\mathsf{td}_{\Pi},x_{\Pi},\pi_{\Pi})$ to
$\Pi.\mathsf{Ext}$. Receive $w_{\Pi}$ from $\Pi.\mathsf{Ext}$.

(2) Output $w_{\Pi}$ as $w$.

Let a polynomial $p(\cdot)$ and an oracle-aided polynomial-size quantum
circuit ${\mathcal{A}}$ be given such that

$\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})\\\
(x,\pi)\leftarrow{\mathcal{A}}^{\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},\cdot)}(\mathsf{crs})\\\
w\leftarrow\mathsf{Ext}(\mathsf{crs},\mathsf{td},x,\pi)\end{subarray}}[\mathsf{V}(\mathsf{crs},x,\pi)=1\wedge
x\not\in Q\wedge(x,w)\not\in{\mathcal{R}}]\geq\frac{1}{p(\lambda)},$

where $Q$ is the list of queries from ${\mathcal{A}}$ to $\mathsf{Sim}_{1}$.
Since $\mathsf{Sim}_{1}$ forwards oracle queries to $\Pi.\mathsf{Sim}_{1}$
which contain any query it receives from ${\mathcal{A}}$, we know that
$x_{\Pi}\not\in Q_{\Pi}$ where $Q_{\Pi}$ is the list of queries from
$\mathsf{Sim}_{1}$ to $\Pi.\mathsf{Sim}_{1}$. Furthermore, since $\mathsf{V}$
accepts the output $\pi$ from ${\mathcal{A}}$, then $\Pi.\mathsf{V}$ must
accept the proof $\pi_{\Pi}$. As such, we have that

$\displaystyle\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})\\\
(x,\pi)\leftarrow{\mathcal{A}}^{\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},\cdot)}(\mathsf{crs})\\\
w\leftarrow\mathsf{Ext}(\mathsf{crs},\mathsf{td},x,\pi)\end{subarray}}[\Pi.\mathsf{V}(\mathsf{crs}_{\Pi},x_{\Pi},\pi_{\Pi})=1\wedge
x_{\Pi}\not\in
Q_{\Pi}\wedge(x,w)\not\in{\mathcal{R}}]\geq\frac{1}{p(\lambda)}.$ (3)

However, we make the following claim which is in direct contradiction with
Equation 3.

######  Claim 4.11.

Let $\mathsf{Ext}$ be as defined earlier, in the current proof of simulation-
extractability. There exists a negligible function $\mathsf{negl}(\cdot)$ such
that for every polynomial-size quantum circuit ${\mathcal{B}}$,

$\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})\\\
(x,\pi)\leftarrow{\mathcal{B}}^{\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},\cdot)}(\mathsf{crs})\\\
w\leftarrow\mathsf{Ext}(\mathsf{crs},\mathsf{td},x,\pi)\end{subarray}}[\Pi.\mathsf{V}(\mathsf{crs}_{\Pi},x_{\Pi},\pi_{\Pi})=1\wedge
x_{\Pi}\not\in
Q_{\Pi}\wedge(x,w)\not\in{\mathcal{R}}]\leq\mathsf{negl}(\lambda)$

where $Q$ is the list of queries from ${\mathcal{B}}$ to $\mathsf{Sim}_{1}$.

###### Proof of Claim 4.11.

We proceed by contradiction. Let a polynomial $p(\cdot)$ and an oracle-aided
polynomial-size quantum circuit ${\mathcal{B}}$ be given such that

$\displaystyle\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})\\\
(x,\pi)\leftarrow{\mathcal{B}}^{\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},\cdot)}(\mathsf{crs})\\\
w\leftarrow\mathsf{Ext}(\mathsf{crs},\mathsf{td},x,\pi)\end{subarray}}[\Pi.\mathsf{V}(\mathsf{crs}_{\Pi},x_{\Pi},\pi_{\Pi})=1\wedge
x_{\Pi}\not\in
Q_{\Pi}\wedge(x,w)\not\in{\mathcal{R}}]\geq\frac{1}{p(\lambda)}$ (4)

where $Q$ is the list of queries from ${\mathcal{B}}$ to $\mathsf{Sim}_{1}$.
Given Equation 4, we may be in one of the two following cases: either the
extractor $\Pi.\mathsf{Ext}$ extracts $w_{\Pi}$ from ${\mathcal{B}}$ such that
$(x_{\Pi},w_{\Pi})\not\in{\mathcal{R}}_{\Pi}$, or the extractor
$\Pi.\mathsf{Ext}$ extracts $w_{\Pi}$ from ${\mathcal{B}}$ such that
$(x_{\Pi},w_{\Pi})\in{\mathcal{R}}_{\Pi}$. We consider these two scenarios
separately and show that each reaches a contradiction.

Scenario One

Say that the extractor $\Pi.\mathsf{Ext}$ extracts $w_{\Pi}$ from
${\mathcal{B}}$ such that $(x_{\Pi},w_{\Pi})\not\in{\mathcal{R}}_{\Pi}$. By
applying a union bound to Equation 5, we have that this event could happen
with at least $1/2p(\lambda)$ probability. Symbolically,

$\displaystyle\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})\\\
(x,\pi)\leftarrow{\mathcal{B}}^{\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},\cdot)}(\mathsf{crs})\\\
w\leftarrow\mathsf{Ext}(\mathsf{crs},\mathsf{td},x,\pi)\end{subarray}}[\Pi.\mathsf{V}(\mathsf{crs}_{\Pi},x_{\Pi},\pi_{\Pi})=1\wedge
x_{\Pi}\not\in
Q_{\Pi}\wedge(x_{\Pi},w_{\Pi})\not\in{\mathcal{R}}_{\Pi}]\geq\frac{1}{2p(\lambda)}.$
(5)

By using the advantage of ${\mathcal{B}}$ in this game, we can show a
reduction that breaks the simulation-extractability of $\Pi$. We will now
outline this reduction. [2em]2em Reduction: to simulation-extractability of
$\Pi$ given oracle access to ${\mathcal{B}}$.

(1) Receive $\mathsf{crs}_{\Pi}$ from the challenger.

(2) Sample $s^{*},r^{*}$ uniformly at random. Define
$c=\mathsf{Com}(s^{*};r^{*})$.

(3) Define $\mathsf{crs}=(\mathsf{crs}_{\Pi},c)$ and
$\mathsf{td}=\mathsf{td}_{\Pi}$. Send $\mathsf{crs}$ to ${\mathcal{B}}$.

(4) On query $x$ from ${\mathcal{B}}$: sample
$(\ket{\$},s)\leftarrow\mathsf{NoteGen}(1^{\lambda})$, define
$x_{\Pi}=(c,x,s)$, send $x_{\Pi}$ to the challenger, receive $\pi_{\Pi}$ from
the challenger, define $\pi=(\ket{\$},s,\pi_{\Pi})$, and send $\pi$ to
${\mathcal{B}}$.

(5) Receive $(x,\pi=(\ket{\$},s,\pi_{\Pi}))$ from ${\mathcal{B}}$. Define
$x_{\Pi}=(c,x,s)$.

(6) Output $(x_{\Pi},\pi_{\Pi})$. Given the event in Equation 5 holds, then
the reduction will return an accepting proof $\pi_{\Pi}$ for an instance
$x_{\Pi}$ which it has not previously queried on and, yet, the extraction
$\Pi.\mathsf{Ext}$ will fail. With advantage $1/2p(\lambda))$, the reduction
will succeed at breaking simulation-extractability of $\Pi$, thus reaching a
contradiction.

Scenario Two

Alternatively, say that the extractor $\Pi.\mathsf{Ext}$ extracts $w_{\Pi}$
from ${\mathcal{B}}$ such that $(x_{\Pi},w_{\Pi})\in{\mathcal{R}}_{\Pi}$. By
applying a union bound to Equation 3, we have that this event could happen
with at least $1/2p(\lambda)$ probability. In summary, we have that

$\displaystyle\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})\\\
(x,\pi)\leftarrow{\mathcal{B}}^{\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},\cdot)}(\mathsf{crs})\\\
w\leftarrow\mathsf{Ext}(\mathsf{crs},\mathsf{td},x,\pi)\end{subarray}}[\Pi.\mathsf{V}(\mathsf{crs}_{\Pi},x_{\Pi},\pi_{\Pi})=1\wedge
x_{\Pi}\not\in
Q_{\Pi}\wedge(x,w)\not\in{\mathcal{R}}\wedge(x_{\Pi},w_{\Pi})\in{\mathcal{R}}_{\Pi}]\geq\frac{1}{2p(\lambda)}.$
(6)

Since $\mathsf{Ext}$ outputs $w=w_{\Pi}$, by the definition of
${\mathcal{L}}_{\Pi}$ and the perfect binding of $\mathsf{Com}$, we must have
that ${\mathcal{B}}$ has found an opening to the commitment $c$ in the crs,
that is that $s=s^{*}$ and $w_{\Pi}=r^{*}$. We can use ${\mathcal{B}}$ to
break the hiding of the commitment. We will now outline this reduction.
[2em]2em Reduction: to hiding of $\mathsf{Com}$ given oracle access to
${\mathcal{B}}$.

(1) Compute
$(\mathsf{crs}_{\Pi},\mathsf{td}_{\Pi})\leftarrow\Pi.\mathsf{Sim}_{0}(1^{\lambda})$
from the challenger.

(2) Sample $s_{0},s_{1}$ uniformly at random. Send $(s_{0},s_{1})$ to the
challenger. Receive $c$.

(3) Define $\mathsf{crs}=(\mathsf{crs}_{\Pi},c)$ and
$\mathsf{td}=\mathsf{td}_{\Pi}$. Send $\mathsf{crs}$ to ${\mathcal{B}}$.

(4) On query $x$ from ${\mathcal{B}}$: compute
$\pi\leftarrow\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},x)$, and send $\pi$ to
${\mathcal{B}}$.

(5) Receive $(x,\pi=(\ket{\$},s,\pi_{\Pi}))$ from ${\mathcal{B}}$.

(6) Compute $w\leftarrow\mathsf{Ext}(\mathsf{crs},\mathsf{td},x,\pi)$.

(7) If $s=s_{b}$ for $b\in{\\{0,1\\}}$, then output $b$. Else, output $s_{b}$
for $b$ chosen uniformly at random. Given the event in Equation 5 holds, then
the reduction will, with advantage $1/q(\lambda)$ for some polynomial
$q(\cdot)$, succeed at breaking the hiding of $\mathsf{Com}$, thus reaching a
contradiction. ∎

Since Equation 3 directly contradicts Claim 4.11 which we have proven, then we
have reached a contradiction. Therefore, the protocol must be simulation
extractable.

Unclonable Extractability. Let
$\Pi.\mathsf{Sim}=(\Pi.\mathsf{Sim}_{0},\Pi.\mathsf{Sim}_{1})$ be the adaptive
multi-theorem computationally zero-knowledge simulator of $\Pi$. Let
$\Pi.\mathsf{Ext}$ be the simulation-extraction extractor of $\Pi$ with
respect to $\Pi.\mathsf{Sim}$. Let
$\mathsf{Sim}=(\mathsf{Sim}_{0},\mathsf{Sim}_{1})$ be the simulator, with
oracle access to $\Pi.\mathsf{Sim}$, as defined in the proof that Figure 3 is
adaptive multi-theorem computational zero-knowledge. Let $\mathsf{Ext}$ be the
extractor, based on $\mathsf{Sim}$, as defined in the proof that Figure 3 is
simulation-extractable. We define ${\mathcal{E}}$ with oracle access to
$\mathsf{Sim}$, $\mathsf{Ext}$, and some ${\mathcal{A}}$ as follows: [2em]2em
_Hardwired_ : $x_{1},\ldots,x_{k-1}$, $x$, ${\mathcal{I}}$, ${\mathcal{J}}$

(1) Send $1^{\lambda}$ to $\mathsf{Sim}_{0}$. Receive
$(\mathsf{crs},\mathsf{td})$ from $\mathsf{Sim}_{0}$.

(2) For $\iota\in[k-1]$: send $(\mathsf{crs},\mathsf{td},x_{\iota})$ to
$\mathsf{Sim}_{1}$, and receive $\pi_{\iota}$ from $\mathsf{Sim}_{1}$.

(3) Send $(\mathsf{crs},\\{x_{\iota},\pi_{\iota}\\}_{\iota\in[k-1]})$ to
${\mathcal{A}}$. Receive
$\\{\widetilde{x_{\iota}},\widetilde{\pi_{\iota}}\\}_{\iota\in[k]}$ from
${\mathcal{A}}$.

(4) Define $j^{\prime}$ uniformly at random from ${\mathcal{J}}$.

(5) Output
$\mathsf{Ext}(\mathsf{crs},\mathsf{td},\widetilde{x_{j^{\prime}}},\widetilde{\pi_{j^{\prime}}})$
and $w$.

Let ${\mathcal{A}}$, $(x_{1},w_{1}),\ldots,(x_{k-1},w_{k-1})\in{\mathcal{R}}$,
$x$, ${\mathcal{I}}\subseteq[k-1]$, ${\mathcal{J}}\subseteq[k]$, polynomial
$p(\cdot)$, and negligible function $\mathsf{negl}_{1}(\cdot)$ be given such
that the verifier $\mathsf{V}$ accepts all proofs which ${\mathcal{A}}$
outputs indexed by ${\mathcal{I}}$, and the extractor ${\mathcal{E}}$ is
unable to extract a valid witness. Restated more formally, that is that both

$\displaystyle\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Setup}(1^{\lambda})\\\
\forall\iota\in[k-1],\>\pi_{\iota}\leftarrow\mathsf{P}(\mathsf{crs},x_{\iota},w_{\iota})\\\
\\{\widetilde{x_{\iota}},\widetilde{\pi_{\iota}}\\}_{\iota\in[k]}\leftarrow{\mathcal{A}}(\mathsf{crs},\\{x_{\iota},\pi_{\iota}\\}_{\iota\in[k-1]})\end{subarray}}\left[\bigwedge_{\iota\in{\mathcal{J}}}\mathsf{V}(\mathsf{crs},x,\widetilde{\pi_{\iota}})=1\right]\geq\frac{1}{p(\lambda)},\text{
and}$ (7)
$\displaystyle\Pr_{w\leftarrow{\mathcal{E}}^{\mathcal{A}}(x_{1},\ldots,x_{k-1},x,{\mathcal{I}},{\mathcal{J}})}\left[(x,w)\in{\mathcal{R}}\right]\leq\mathsf{negl}_{1}(\lambda).$
(8)

Given Equation 7, we may be in one of the two following cases: either
${\mathcal{A}}$ generate two accepting proofs which have the same serial
number as an honestly generated proof, or ${\mathcal{A}}$ does not. We
consider these two scenarios separately and show that each reaches a
contradiction.

Scenario One

Say that ${\mathcal{A}}$ generates two accepting proofs which have the same
serial number as an honestly generated proof. By applying a union bound to
Equation 7, we have that this event could happen with at least $1/2p(\lambda)$
probability. Symbolically,

$\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Setup}(1^{\lambda})\\\
\forall\iota\in[k-1],\>\pi_{\iota}\leftarrow\mathsf{P}(\mathsf{crs},x_{\iota},w_{\iota})\\\
\\{\widetilde{x_{\iota}},\widetilde{\pi_{\iota}}\\}_{\iota\in[k]}\leftarrow{\mathcal{A}}(\mathsf{crs},\\{x_{\iota},\pi_{\iota}\\}_{\iota\in[k-1]})\end{subarray}}\left[\bigwedge_{\iota\in{\mathcal{J}}}\mathsf{V}(\mathsf{crs},x,\widetilde{\pi_{\iota}})=1\>\bigwedge\>\exists
i\in{\mathcal{I}}\>\>\exists j,\ell\in{\mathcal{J}}\text{ s.t.
}s_{i}=\widetilde{s_{j}}=\widetilde{s_{\ell}}\right]\geq\frac{1}{2p(\lambda)}.$
(9)

Through a hybrid argument, we can fix indices $i\in{\mathcal{I}}$ and
$j,\ell\in{\mathcal{J}}$ which gives us the same event with an advantage of
$1/(2k^{3}p(\lambda))$. By using the advantage of ${\mathcal{A}}$ in this
game, we can show a reduction that breaks the unforgeability of the quantum
money scheme. We will now outline this reduction. [2em]2em Reduction: to
unforgeability of quantum money scheme given oracle access to ${\mathcal{A}}$
and ${\mathcal{O}}$.

_Hardwired with_ : $(x_{1},w_{1}),\ldots,(x_{k-1},w_{k-1})$, $x$,
${\mathcal{I}}$, ${\mathcal{J}}$, $i,j,\ell$.

(1) Compute $(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Setup}(1^{\lambda})$
where $\mathsf{crs}=(\mathsf{crs}_{\Pi},c)$.

(2) Receive $(\ket{\$},s)\leftarrow\mathsf{NoteGen}$ from the challenger.

(3) Define $\ket{\$}_{\ell}=\ket{\$}$, $s_{\ell}=s$, and
$x_{\Pi}=(c,x_{\ell},s_{\ell})$. Compute
$\pi_{\Pi,\ell}\leftarrow\Pi.\mathsf{P}(\mathsf{crs}_{\Pi},x_{\Pi},w_{\ell})$.
Define $\pi_{\ell}=(\ket{\$}_{\ell},s_{\ell},\pi_{\Pi,\ell})$.

(4) Define $\pi_{\iota}\leftarrow\mathsf{P}(\mathsf{crs},x_{\iota},w_{\iota})$
for $\iota\in[k-1]\setminus\\{\ell\\}$.

(5) Send $\\{x_{\iota},\pi_{\iota}\\}_{\iota\in[k-1]}$ to ${\mathcal{A}}$.

(6) Receive
$\\{\widetilde{x_{\iota}},\widetilde{\pi_{\iota}}\\}_{\iota\in[k]}$ from
${\mathcal{A}}$. Parse
$\widetilde{\pi_{i}}=(\widetilde{\ket{\$_{i}}},\widetilde{s_{i}},\widetilde{\pi_{\Pi,i}})$
and
$\widetilde{\pi_{j}}=(\widetilde{\ket{\$_{j}}},\widetilde{s_{j}},\widetilde{\pi_{\Pi,j}})$.

(7) Send $(\widetilde{\ket{\$_{i}}},\widetilde{\ket{\$_{j}}})$ to the
challenger. Given the event in Equation 9 holds (for the afore mentioned fixed
indices), then the reduction will return two quantum money states with the
same serial number as the challenger sent. With advantage
$1/(2k^{3}p(\lambda))$, the reduction will succeed at breaking unforgeability
of the quantum money scheme, thus reaching a contradiction.

Scenario Two

Alternatively, say that ${\mathcal{A}}$ does not generate two accepting proofs
which have the same serial number as an honestly generated proof. By the
pigeon-hole principle, this means that ${\mathcal{A}}$ generates an accepting
proof with a serial number which is not amongst the ones it received. By
applying a union bound to Equation 7, we have that this event could happen
with at least $1/2p(\lambda)$ probability. In summary, we have that

$\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Setup}(1^{\lambda})\\\
\forall\iota\in[k-1],\>\pi_{\iota}\leftarrow\mathsf{P}(\mathsf{crs},x_{\iota},w_{\iota})\\\
\\{\widetilde{x_{\iota}},\widetilde{\pi_{\iota}}\\}_{\iota\in[k]}\leftarrow{\mathcal{A}}(\mathsf{crs},\\{x_{\iota},\pi_{\iota}\\}_{\iota\in[k-1]})\end{subarray}}\left[\bigwedge_{\iota\in{\mathcal{J}}}\mathsf{V}(\mathsf{crs},x,\widetilde{\pi_{\iota}})=1\>\bigwedge\>\exists
j\in{\mathcal{J}}\text{ s.t.
}\widetilde{s_{j}}\not\in\\{s_{\iota}\\}_{\iota\in[k-1]}\right]\geq\frac{1}{2p(\lambda)}.$
(10)

Through an averaging argument, we can fix index $j\in{\mathcal{J}}$ which
gives us the same event with an advantage of $1/(2kp(\lambda))$. We will now
switch to a hybrid where we provide ${\mathcal{A}}$ with simulated proofs at
indices ${\mathcal{I}}$.

######  Claim 4.12.

There exists a polynomial $q(\cdot)$ such that

$\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})\\\
\forall\iota\in[k-1],\>\pi_{\iota}\leftarrow\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},x_{\iota})\\\
\\{\widetilde{x_{\iota}},\widetilde{\pi_{\iota}}\\}_{\iota\in[k]}\leftarrow{\mathcal{A}}(\mathsf{crs},\\{x_{\iota},\pi_{\iota}\\}_{\iota\in[k-1]})\end{subarray}}\left[\left(\bigwedge_{\iota\in{\mathcal{J}}}\mathsf{V}(\mathsf{crs},x,\widetilde{\pi_{\iota}})=1\right)\>\bigwedge\>\widetilde{s_{j}}\not\in\\{s_{\iota}\\}_{\iota\in[k-1]}\right]\geq\frac{1}{q(\lambda)}.$
(11)

We will later see a proof of Claim 4.12. For now, assuming that this claim
holds, by the definition of ${\mathcal{E}}$, Equation 8, and Equation 11,
there exists a polynomial $q^{\prime}(\cdot)$ such that

$\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})\\\
\forall\iota\in[k-1],\>\pi_{\iota}\leftarrow\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},x_{\iota})\\\
\\{\widetilde{x_{\iota}},\widetilde{\pi_{\iota}}\\}_{\iota\in[k]}\leftarrow{\mathcal{A}}(\mathsf{crs},\\{x_{\iota},\pi_{\iota}\\}_{\iota\in[k-1]})\\\
b^{\prime}\stackrel{{\scriptstyle\mathclap{\mbox{\text{\tiny\$}}}}}{{\leftarrow}}{\mathcal{J}}\\\
w\leftarrow\mathsf{Ext}(\mathsf{crs},\mathsf{td},\widetilde{x_{b^{\prime}}},\widetilde{\pi_{b^{\prime}}})\end{subarray}}\left[\left(\bigwedge_{\iota\in{\mathcal{J}}}\mathsf{V}(\mathsf{crs},x,\widetilde{\pi_{\iota}})=1\right)\>\wedge\>\widetilde{s_{j}}\not\in\\{s_{\iota}\\}_{\iota\in[k-1]}\>\wedge\>(x,w)\not\in{\mathcal{R}}\right]\geq\frac{1}{q^{\prime}(\lambda)}.$

We will additionally have that $j^{\prime}=j$ with advantage at least
$1/(kq^{\prime}(\lambda))$. Since $\mathsf{V}$ accepts $\widetilde{\pi_{j}}$
with respect to $x$, $\Pi.\mathsf{V}$ must accept $\widetilde{\pi_{\Pi,j}}$
with respect to $\widetilde{x_{\Pi,j}}=(c,x,\widetilde{s_{j}})$. Since
$\widetilde{s_{j}}\not\in\\{s_{\iota}\\}_{\iota\in[k-1]}$, we have that
$\Pi.\mathsf{Sim}_{1}$, through $\mathsf{Sim}_{1}$, has not previously
received $\widetilde{x_{\Pi,j}}$ as a query. As such, we have that

$\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})\\\
\forall\iota\in[k-1],\>\pi_{\iota}\leftarrow\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},x_{\iota})\\\
\\{\widetilde{x_{\iota}},\widetilde{\pi_{\iota}}\\}_{\iota\in[k]}\leftarrow{\mathcal{A}}(\mathsf{crs},\\{x_{\iota},\pi_{\iota}\\}_{\iota\in[k-1]})\\\
w\leftarrow\mathsf{Ext}(\mathsf{crs},\mathsf{td},\widetilde{x_{j}},\widetilde{\pi_{j}})\end{subarray}}[\Pi.\mathsf{V}(\mathsf{crs}_{\Pi},\widetilde{x_{\Pi,j}},\widetilde{\pi_{\Pi,j}})=1\wedge\widetilde{x_{\Pi,}}\not\in
Q_{\Pi}\wedge(x,w)\not\in{\mathcal{R}}]\geq\frac{1}{kq^{\prime}(\lambda)}.$
(12)

We now define ${\mathcal{B}}$ with oracle access to ${\mathcal{A}}$ and
$\mathsf{Sim}_{1}$ 222Here, ${\mathcal{B}}$ is given oracle access to
$\mathsf{Sim}_{1}$ which has the terms $(\mathsf{crs},\mathsf{td})$ fixed by
the output of $\mathsf{Sim}_{0}$.: [2em]2em _Hardwired_ :
$x_{1},\ldots,x_{k-1}$, $j$

_Input_ : $\mathsf{crs}$

(1) For $\iota\in[k-1]$: send $x_{\iota}$ to $\mathsf{Sim}_{1}$, and receive
$\pi_{\iota}$ from $\mathsf{Sim}_{1}$.

(2) Send $(\mathsf{crs},\\{x_{\iota},\pi_{\iota}\\}_{\iota\in[k-1]})$ to
${\mathcal{A}}$. Receive
$\\{\widetilde{x_{\iota}},\widetilde{\pi_{\iota}}\\}_{\iota\in[k]}$ from
${\mathcal{A}}$.

(3) Output $(\widetilde{x_{j}},\widetilde{\pi_{j}})$. Given that the event in
Equation 13 holds, then ${\mathcal{B}}$ contradicts Claim 4.11. Thus, all that
remains to be proven is Claim 4.12.

###### Proof of Claim 4.12.

We proceed by contradiction. Let $\mathsf{negl}(\cdot)$ be a negligible
function such that

$\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})\\\
\forall\iota\in[k-1],\>\pi_{\iota}\leftarrow\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},x_{\iota})\\\
\\{\widetilde{x_{\iota}},\widetilde{\pi_{\iota}}\\}_{\iota\in[k]}\leftarrow{\mathcal{A}}(\mathsf{crs},\\{x_{\iota},\pi_{\iota}\\}_{\iota\in[k-1]})\end{subarray}}\left[\left(\bigwedge_{\iota\in{\mathcal{J}}}\mathsf{V}(\mathsf{crs},x,\widetilde{\pi_{\iota}})=1\right)\>\bigwedge\>\widetilde{s_{j}}\not\in\\{s_{\iota}\\}_{\iota\in[k-1]}\right]\leq\mathsf{negl}(\lambda).$
(13)

By Equation 10 and Equation 13, there exists a polynomial $q^{*}(\cdot)$ such
that

$\displaystyle\left|\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Setup}(1^{\lambda})\\\
\forall\iota\in[k-1],\>\pi_{\iota}\leftarrow\mathsf{P}(\mathsf{crs},x_{\iota},w_{\iota})\\\
\\{\widetilde{x_{\iota}},\widetilde{\pi_{\iota}}\\}_{\iota\in[k]}\leftarrow{\mathcal{A}}(\mathsf{crs},\\{x_{\iota},\pi_{\iota}\\}_{\iota\in[k-1]})\end{subarray}}\left[\left(\bigwedge_{\iota\in{\mathcal{J}}}\mathsf{V}(\mathsf{crs},x,\widetilde{\pi_{\iota}})=1\right)\>\bigwedge\>\widetilde{s_{j}}\not\in\\{s_{\iota}\\}_{\iota\in[k-1]}\right]\right.$
$\displaystyle\left.-\Pr_{\begin{subarray}{c}(\mathsf{crs},\mathsf{td})\leftarrow\mathsf{Sim}_{0}(1^{\lambda})\\\
\forall\iota\in[k-1],\>\pi_{\iota}\leftarrow\mathsf{Sim}_{1}(\mathsf{crs},\mathsf{td},x_{\iota})\\\
\\{\widetilde{x_{\iota}},\widetilde{\pi_{\iota}}\\}_{\iota\in[k]}\leftarrow{\mathcal{A}}(\mathsf{crs},\\{x_{\iota},\pi_{\iota}\\}_{\iota\in[k-1]})\end{subarray}}\left[\left(\bigwedge_{\iota\in{\mathcal{J}}}\mathsf{V}(\mathsf{crs},x,\widetilde{\pi_{\iota}})=1\right)\>\bigwedge\>\widetilde{s_{j}}\not\in\\{s_{\iota}\\}_{\iota\in[k-1]}\right]\right|\geq\frac{1}{q^{*}(\lambda)}.$
(14)

By using the advantage of ${\mathcal{A}}$ in this game, we can show a
reduction that breaks the multi-theorem zero-knowledge of Figure 3. We will
now outline this reduction. [2em]2em Reduction: to multi-theorem zero-
knowledge of our protocol given oracle access to ${\mathcal{A}}$.

_Hardwired_ : $(x_{1},w_{1}),\ldots,(x_{k-1},w_{k-1})$, $j$

(1) Receive (real or simulated) $\mathsf{crs}$ from the challenger.

(2) For $\iota\in[k-1]$: send $(x_{\iota},w_{\iota})$ to the challenger, and
receive (real or simulated) $\pi_{\iota}$ from the challenger.

(3) Send $(\mathsf{crs},\\{x_{\iota},\pi_{\iota}\\}_{\iota\in[k-1]})$ to
${\mathcal{A}}$. Receive
$\\{\widetilde{x_{\iota}},\widetilde{\pi_{\iota}}\\}_{\iota\in[k]}$ from
${\mathcal{A}}$.

(4) Parse
$\widetilde{\pi_{b}}=(\widetilde{\ket{\$_{b}}},\widetilde{s_{b}},\widetilde{\pi_{\Pi,b}})$.

(5) Output
$\left(\bigwedge_{\iota\in{\mathcal{J}}}\mathsf{V}(\mathsf{crs},x,\widetilde{\pi_{\iota}})=1\right)\>\bigwedge\>\widetilde{s_{j}}\not\in\\{s_{\iota}\\}_{\iota\in[k-1]}$.
Given that ${\mathcal{A}}$ is able to change its output dependent on which of
the two worlds in Equation 14 that it is in, then the reduction will be able
to distinguish between receiving honest proofs or simulated proofs. With
advantage $1/q^{*}(\lambda)$, the reduction will succeed at breaking the
adaptive multi-theorem computational zero-knowledge of our protocol, thus
reaching a contradiction. ∎

By completing the proofs of our claim, we have concluding the proof of our
theorem statement. ∎

######  Corollary 4.13.

Assuming the polynomial quantum hardness of LWE, injective one-way functions
exist, and post-quantum iO exists, there exists a non-interactive adaptive
knowledge sound, adaptive computationally zero-knowledge, and
$(k-1)$-to-$k$-unclonable with extraction protocol for $\mathsf{NP}$ in the
common reference string model (Definition 4.7).

###### Proof.

This follows from Theorem 3.2, Corollary 4.4, Theorem 3.14, and Theorem 4.10.
∎

We have thus shown that Figure 3 is an unclonable NIZK PoK in the CRS model as
defined according to our proposed unclonability definition, Definition 4.7.

In the upcoming sections, we will consider unclonable proof systems in the
QROM.

##  5 Unclonable NIZK in the Quantum Random Oracle Model

###  5.1 A Modified Sigma Protocol

We will begin by introducing a slightly modified sigma protocol. In the coming
sections, our construction will involve applying Fiat-Shamir to this modified
protocol.

######  Theorem 5.1.

Let a post-quantum sigma protocol with unpredictable commitments $\Pi$ be
given (see Definition 3.4). Let ${\mathcal{R}}_{\Pi}$ be an $\mathsf{NP}$
relation. Let
${\mathcal{R}}=\\{((x,{\mathcal{S}}),w)\>:\>(x,w)\in{\mathcal{R}}_{\Pi}\land{\mathcal{S}}\neq\emptyset\\}$.
We argue that the following protocol will be a post-quantum sigma protocol
with unpredictable commitments (see Definition 3.4):

  * •

$\mathsf{P}.\mathsf{Com}(1^{\lambda},(x,{\mathcal{S}}),w)$: Sends
$(x,\alpha,s)$ to $\mathsf{V}$ where
$(\alpha,\mathsf{st})\leftarrow\Pi.\mathsf{P}.\mathsf{Com}(1^{\lambda},x,w)$
and $s$ is sampled from ${\mathcal{S}}$.

  * •

$\mathsf{V}.\mathsf{Ch}(1^{\lambda},(x,{\mathcal{S}}),(x,\alpha,s))$: Sends
$\beta$ to $\mathsf{P}$ where
$\beta\leftarrow\Pi.\mathsf{V}.\mathsf{Ch}(1^{\lambda},x,\alpha)$.

  * •

$\mathsf{P}.\mathsf{Com}(1^{\lambda},(x,{\mathcal{S}}),w,\mathsf{st},\beta)$:
Sends $\gamma$ to $\mathsf{V}$ where
$\gamma\leftarrow\Pi.\mathsf{P}.\mathsf{Prove}(1^{\lambda},x,w,\mathsf{st},\beta)$.

  * •

$\mathsf{V}.\mathsf{Ver}(1^{\lambda},(x,{\mathcal{S}}),(x,\alpha,s),\beta,\gamma)$:
Outputs $1$ iff $s\in\mathsf{Support}({\mathcal{S}})$ and
$\Pi.\mathsf{V}.\mathsf{Ver}(1^{\lambda},x,\alpha,\beta,\gamma)=1$.

###### Proof.

Perfect completeness This follows directly from the perfect completeness of
$\Pi$.

Proof of Knowledge with Quantum Extractor. Let $\Pi.\mathsf{Ext}$ be the proof
of knowledge quantum extractor for $\Pi$. Let constant $c_{\Pi}$, polynomial
$p_{\Pi}(\cdot)$, and negligible functions
$\mathsf{negl}_{0,\Pi}(\cdot),\mathsf{negl}_{1,\Pi}(\cdot)$ be given such that
for any quantum
${\mathcal{A}}_{\Pi}=({\mathcal{A}}_{0,\Pi},{\mathcal{A}}_{1,\Pi})$ where

  * •

${\mathcal{A}}_{0,\Pi}(x)$ is a unitary $U_{x}$ followed by a measurement and

  * •

${\mathcal{A}}_{1,\Pi}(x),\ket{\mathsf{st}},\beta)$ is a unitary $V_{x,\beta}$
onto the state $\ket{\mathsf{st}}$ followed by a measurement,

and any $x$ with associated $\lambda\in\mathbb{N}$ satisfying

$\Pr_{\begin{subarray}{c}(\alpha,\ket{\mathsf{st}})\leftarrow{\mathcal{A}}_{0,\Pi}(x)\\\
\beta\leftarrow{\\{0,1\\}}^{\lambda}\\\
\gamma\leftarrow{\mathcal{A}}_{1,\Pi}(x,\ket{\mathsf{st}},\beta)\end{subarray}}[\Pi.\mathsf{V}.\mathsf{Ver}(x,\alpha,\beta,\gamma)=1]\geq\mathsf{negl}_{0,\Pi}(\lambda)$
(15)

we have

$\displaystyle\Pr[(x,\Pi.\mathsf{Ext}^{{\mathcal{A}}_{\Pi}(x)}(x))\in{\mathcal{R}}_{\Pi}]$
$\displaystyle\geq\frac{1}{p(\lambda)}\cdot\left(\Pr_{\begin{subarray}{c}(\alpha,\ket{\mathsf{st}})\leftarrow{\mathcal{A}}_{0,\Pi}(x)\\\
\beta\leftarrow{\\{0,1\\}}^{\lambda}\\\
\gamma\leftarrow{\mathcal{A}}_{1,\Pi}(x,\ket{\mathsf{st}},\beta)\end{subarray}}[\Pi.\mathsf{V}.\mathsf{Ver}(x,\alpha,\beta,\gamma)=1]-\mathsf{negl}_{0,\Pi}(\lambda)\right)^{c_{\Pi}}-\mathsf{negl}_{1,\Pi}(\lambda).$

We define $\mathsf{Ext}$ 333An extractor whose local code is implementable as
a simple unitary which allows for straightforward rewinding. with oracle-
access to $\Pi.\mathsf{Ext}$ and some ${\mathcal{A}}$ as follows: [2em]2em
_Input_ : $x$, ${\mathcal{S}}$.

(1) Given $(x,\alpha,s)$ from ${\mathcal{A}}_{\Pi}$: send $\alpha$ to
$\Pi.\mathsf{Ext}$, receive $\beta$ from $\Pi.\mathsf{Ext}$, and send $\beta$
to ${\mathcal{A}}_{\Pi}$.

(2) Upon receiving $\gamma$ from ${\mathcal{A}}_{\Pi}$: send $\gamma$ to
$\Pi.\mathsf{Ext}$.

(3) Output the result of $\Pi.\mathsf{Ext}$ as $w$.

We define the following set of parameters: $c=c_{\Pi}$,
$p(\cdot)=p_{\Pi}(\cdot)$,
$\mathsf{negl}_{0}(\cdot)=\mathsf{negl}_{0,\Pi}(\cdot)$ and
$\mathsf{negl}_{1}(\cdot)=\mathsf{negl}_{1,\Pi}(\cdot)$.

Let polynomial-size quantum circuit
${\mathcal{A}}=({\mathcal{A}}_{0},{\mathcal{A}}_{1})$ and $(x,{\mathcal{S}})$
be given such that

$\Pr_{\begin{subarray}{c}((x,\alpha,s),\ket{\mathsf{st}})\leftarrow{\mathcal{A}}_{0}(x,{\mathcal{S}})\\\
\beta\leftarrow{\\{0,1\\}}^{\lambda}\\\
\gamma\leftarrow{\mathcal{A}}_{1}((x,{\mathcal{S}}),\ket{\mathsf{st}},\beta)\end{subarray}}[\mathsf{V}.\mathsf{Ver}((x,{\mathcal{S}}),(x,\alpha,s),\beta,\gamma)=1]\geq\mathsf{negl}_{0}(\lambda).$

We now define
${\mathcal{A}}_{\Pi}=({\mathcal{A}}_{0,\Pi},{\mathcal{A}}_{1,\Pi})$ with
oracle-access to ${\mathcal{A}}$. ${\mathcal{A}}_{0,\Pi}$ is hardwired with
${\mathcal{S}}$, takes input $x$, sends $(x,{\mathcal{S}})$ to
${\mathcal{A}}_{0}$, receives $((x,\alpha,s),\ket{\mathsf{st}})$ from
${\mathcal{A}}_{0}$, and outputs $(\alpha,\ket{\mathsf{st}})$.
${\mathcal{A}}_{1,\Pi}$ is hardwired with ${\mathcal{S}}$, takes input
$(x,\ket{\mathsf{st}},\beta)$, sends
$((x,{\mathcal{S}}),\ket{\mathsf{st}},\beta)$ to ${\mathcal{A}}_{1}$, receives
$\gamma$ from ${\mathcal{A}}_{1}$, outputs $\gamma$. By the structure of our
proof and definition of our verifier, this means that

$\displaystyle\Pr_{\begin{subarray}{c}(\alpha,\ket{\mathsf{st}})\leftarrow{\mathcal{A}}_{0,\Pi}^{{\mathcal{A}}_{0}}(x,{\mathcal{S}})\\\
\beta\leftarrow{\\{0,1\\}}^{\lambda}\\\
\gamma\leftarrow{\mathcal{A}}_{1,\Pi}^{{\mathcal{A}}_{1}}((x,{\mathcal{S}}),\ket{\mathsf{st}},\beta)\end{subarray}}[\Pi.\mathsf{V}.\mathsf{Ver}(x,\alpha,\beta,\gamma)=1]$
$\displaystyle\geq\Pr_{\begin{subarray}{c}((x,\alpha,s),\ket{\mathsf{st}})\leftarrow{\mathcal{A}}_{0}(x,{\mathcal{S}})\\\
\beta\leftarrow{\\{0,1\\}}^{\lambda}\\\
\gamma\leftarrow{\mathcal{A}}_{1}((x,{\mathcal{S}}),\ket{\mathsf{st}},\beta)\end{subarray}}[\mathsf{V}.\mathsf{Ver}((x,{\mathcal{S}}),(x,\alpha,s),\beta,\gamma)=1]\geq\mathsf{negl}_{0}(\lambda)$

which satisfies the constraint in Equation 15. This means we have, when
combined with our definition of $\mathsf{Ext}$, that

$\displaystyle\Pr[((x,{\mathcal{S}}),\mathsf{Ext}^{{\mathcal{A}}(x,{\mathcal{S}})}(x,{\mathcal{S}}))\in{\mathcal{R}}]=\Pr[(x,\Pi.\mathsf{Ext}^{{\mathcal{A}}_{\Pi}(x,{\mathcal{S}})}(x))\in{\mathcal{R}}_{\Pi}]$
$\displaystyle\geq\frac{1}{p_{\Pi}(\lambda)}\cdot\left(\Pr_{\begin{subarray}{c}((x,\alpha,s),\ket{\mathsf{st}})\leftarrow{\mathcal{A}}_{0,\Pi}^{{\mathcal{A}}_{0}}(x,{\mathcal{S}})\\\
\beta\leftarrow{\\{0,1\\}}^{\lambda}\\\
\gamma\leftarrow{\mathcal{A}}_{1,\Pi}^{{\mathcal{A}}_{1}}((x,{\mathcal{S}}),\ket{\mathsf{st}},\beta)\end{subarray}}[\Pi.\mathsf{V}.\mathsf{Ver}(x,\alpha,\beta,\gamma)=1]-\mathsf{negl}_{0,\Pi}(\lambda)\right)^{c_{\Pi}}-\mathsf{negl}_{1,\Pi}(\lambda)$
$\displaystyle\geq\frac{1}{p_{\Pi}(\lambda)}\cdot\left(\Pr_{\begin{subarray}{c}((x,\alpha,s),\ket{\mathsf{st}})\leftarrow{\mathcal{A}}_{0}(x,{\mathcal{S}})\\\
\beta\leftarrow{\\{0,1\\}}^{\lambda}\\\
\gamma\leftarrow{\mathcal{A}}_{1}((x,{\mathcal{S}}),\ket{\mathsf{st}},\beta)\end{subarray}}[\mathsf{V}.\mathsf{Ver}((x,{\mathcal{S}}),(x,\alpha,s),\beta,\gamma)=1]-\mathsf{negl}_{0,\Pi}(\lambda)\right)^{c_{\Pi}}-\mathsf{negl}_{1,\Pi}(\lambda)$
$\displaystyle\geq\frac{1}{p(\lambda)}\cdot\left(\Pr_{\begin{subarray}{c}((x,\alpha,s),\ket{\mathsf{st}})\leftarrow{\mathcal{A}}_{0}(x,s)\\\
\beta\leftarrow{\\{0,1\\}}^{\lambda}\\\
\gamma\leftarrow{\mathcal{A}}_{1}((x,s),\ket{\mathsf{st}},\beta)\end{subarray}}[\mathsf{V}.\mathsf{Ver}((x,s),(x,\alpha,s),\beta,\gamma)=1]-\mathsf{negl}_{0}(\lambda)\right)^{c}-\mathsf{negl}_{1}(\lambda).$

Thus showing that our protocol is a proof of knowledge protocol.

Computational Honest-Verifier Zero-Knowledge with Quantum Simulator. Let
$\Pi.\mathsf{Sim}$ be the computational honest-verifier zero-knowledge quantum
simulator for $\Pi$. We define $\mathsf{Sim}$ with oracle access to
$\Pi.\mathsf{Sim}$ as follows: [2em]2em _Input_ : $x$, ${\mathcal{S}}$.

(1) Compute $(\alpha,\beta,\gamma)\leftarrow\Pi.\mathsf{Sim}(1^{\lambda},x)$.

(2) Sample $s$ from ${\mathcal{S}}$.

(3) Output $((x,\alpha,s),\beta,\gamma)$. Let a polynomial $p(\cdot)$, a
polynomial-size quantum circuit ${\mathcal{D}}$, $\lambda\in\mathbb{N}$, and
$((x,{\mathcal{S}}),w)\in{\mathcal{R}}$ be given such that

$\displaystyle\left|\Pr_{\begin{subarray}{c}((x,\alpha,s),\mathsf{st})\leftarrow\mathsf{P}.\mathsf{Com}((x,{\mathcal{S}}),w)\\\
\beta\leftarrow\mathsf{V}.\mathsf{Ch}((x,{\mathcal{S}}),(x,\alpha,s))\\\
\gamma\leftarrow\mathsf{P}.\mathsf{Prove}((x,{\mathcal{S}}),w,\mathsf{st},\beta)\end{subarray}}[{\mathcal{D}}((x,{\mathcal{S}}),(x,\alpha,s),\beta,\gamma)=1]\right.$
$\displaystyle\left.-\Pr_{\begin{subarray}{c}((x,\alpha,s),\beta,\gamma)\leftarrow\mathsf{Sim}(1^{\lambda},(x,{\mathcal{S}}))\end{subarray}}[{\mathcal{D}}((x,{\mathcal{S}}),(x,\alpha,s),\beta,\gamma)=1]\right|\geq\frac{1}{p(\lambda)}.$

We define a reduction to the zero-knowledge property of $\Pi$ as follows:
[2em]2em Reduction: to zero-knowledge of $\Pi$ given oracle access to
${\mathcal{D}}$.

Hardwired with: $x$, ${\mathcal{S}}$.

(1) Receive (real or simulated) $(\alpha,\beta,\gamma)$ from the challenger.

(2) Sample $s$ from ${\mathcal{S}}$.

(3) Send $((x,\alpha,s),\beta,\gamma)$ to ${\mathcal{D}}$. Receive $b$ from
${\mathcal{D}}$.

(4) Output $b$. When the challenger sends a real (or simulated) proof for
$\Pi$, the reduction generates a proof that is identical to the real (resp.
simulated) proof. As such, this reduction preserves the distinguishing
advantage of ${\mathcal{D}}$. This reaches a contradiction against the zero-