# Lattice-Based Quantum Advantage from Rotated Measurements

Yusuf Alnawakhtha  Joint Center for Quantum Information and Computer Science
(QuICS), 3100 Atlantic Building, University of Maryland, College Park, MD
20742, USA  Atul Mantri  Joint Center for Quantum Information and Computer
Science (QuICS), 3100 Atlantic Building, University of Maryland, College Park,
MD 20742, USA  Carl A. Miller  Joint Center for Quantum Information and
Computer Science (QuICS), 3100 Atlantic Building, University of Maryland,
College Park, MD 20742, USA  Computer Security Division, National Institute of
Standards and Technology (NIST), 100 Bureau Dr., Gaithersburg, MD 20899, USA
Daochen Wang  Joint Center for Quantum Information and Computer Science
(QuICS), 3100 Atlantic Building, University of Maryland, College Park, MD
20742, USA

###### Abstract

Trapdoor claw-free functions (TCFs) are immensely valuable in cryptographic
interactions between a classical client and a quantum server. Typically, a
protocol has the quantum server prepare a superposition of two-bit strings of
a claw and then measure it using Pauli-$X$ or $Z$ measurements. In this paper,
we demonstrate a new technique that uses the entire range of qubit
measurements from the $XY$-plane. We show the advantage of this approach in
two applications. First, building on (Brakerski et al. 2018, Kalai et al.
2022), we show an optimized two-round proof of quantumness whose security can
be expressed directly in terms of the hardness of the LWE (learning with
errors) problem. Second, we construct a one-round protocol for blind remote
preparation of an arbitrary state on the $XY$-plane up to a Pauli-$Z$
correction.

##  1 Introduction

The field of quantum cryptography has its origins [BB14, Wie83] in the idea
that quantum states can be transmitted between two parties (e.g., through free
space or through an optical fiber) to perform cryptographic tasks. Properties
of the transmitted states, including no-cloning and entanglement, are the
basis for interactive protocols that enable a new and qualitatively different
type of security. However, a recent trend in the field has shown that quantum
cryptography can be done even when quantum communication is not available. If
one or more parties involved in a protocol possess a sufficiently powerful
quantum computer, then certain cryptographic tasks can be performed — while
still taking advantage of uniquely quantum properties — using strictly
classical communication. This approach relieves the users of the difficulties
associated with reliable quantum communication, and puts the focus instead on
the problem of building a more powerful quantum computer, a goal that has seen
tremendous investments during the past several years [Nat19].

At the center of this new type of quantum cryptography are cryptographic
hardness assumptions. Certain problems, such as factoring numbers, are
believed to be difficult for classical computers but not for quantum
computers. Other problems, such as finding the shortest vector in a lattice,
are believed to be hard for both types of computers. These hardness
assumptions are used to prove soundness claims for quantum interactive
protocols.

Two of the seminal papers in quantum cryptography with classical communication
[Mah18, BCM+21] used trapdoor claw-free functions [GMR84] as the basis for
their protocol designs, and created a model that has been followed by many
other authors. A trapdoor claw-free function (TCF), roughly speaking, is a
family of triples $(f_{0},f_{1},t)$, where $f_{0}$ and $f_{1}$ are injective
functions with the same domain and same range, and $t$ is a trapdoor that
allows efficient inversion of either function. To say that this family is
_claw-free_ means that without the trapdoor $t$, it is believed to be hard for
any (quantum or classical) adversary to find values $x_{0}$ and $x_{1}$ such
that $f_{0}(x_{0})=f_{1}(x_{1})$.

The TCF construction illustrates how a cryptographic hardness assumption that
is made for both quantum and classical computers can nonetheless permit a
quantum computer to show its unique capabilities. A quantum computer can
perform an efficient process that will output a random element $y$ in the
range of $f_{0},f_{1}$ together with a _claw state_ of the form

$\ket{\psi}=\frac{1}{\sqrt{2}}\left(\left|x_{0}\right>\left|0\right>+\left|x_{1}\right>\left|1\right>\right),$
(1)

where $f_{0}(x_{0})=f_{1}(x_{1})=y$ (see section 2 of [Mah18]). If this state
is measured in the $Z$-basis, one obtains a pair $(x,c)$ such that
$f_{c}(x)=y$. Alternatively, assuming that $x_{0}$ and $x_{1}$ are expressed
as bit strings of length $\ell$, and thus $\ket{\psi}$ is an $(\ell+1)$-qubit
state, one can measure in the $X$-basis to obtain a bit string $d$ that must
satisfy

$d\cdot(x_{0}\oplus x_{1}||1)=0.$ (2)

(Here, $||$ denotes string concatenation.) This equation is significant
because we have used a quantum process to obtain information about both
$x_{0}$ and $x_{1}$, even though we have assumed that it would be impossible
for any efficient computer to recover $x_{0}$ and $x_{1}$ entirely. This fact
is the basis for using TCFs to verify that a server that one is interacting
with is able to perform quantum computation [BCM+21, KMCVY22]. The same
concept was also used in cryptographic constructions that delegate the
preparation of a quantum state to a server without revealing its classical
description [CCKW19, GV19] and in other cryptographic protocols [MV21, Mah18].

The majority of papers utilizing TCFs in their cryptographic constructions
have applied only Pauli measurements and classical operations to the state
$\left|\psi\right>$.111Two exceptions are as [GV19] and [CCKW21]. In [GV19],
the server applies Fourier transforms to the quantum state
$\left|\psi\right>$. In [CCKW21], the server applies measurements from a small
set in the $XY$-plane and the protocol only provides security against honest-
but-curious adversaries. See Section 1.2 for a comparison. What would happen
if we considered the full range of single-qubit measurements on the state
$\ket{\psi}$? We note that since single-qubit rotation gates are physically
native in some platforms (for example, ion traps [NC10, DLF+16, Mas17]),
realizing a continuous single-qubit rotation is not much more difficult than
realizing a single-qubit Clifford gate, and so this direction is a natural one
to study.

In this work, we use an infinite family of qubit measurements to prove new
performance and security claims for quantum server protocols. We discuss two
applications: proofs of quantumness and blind remote state preparation.

###  1.1 Our Contribution

#### Proof of Quantumness.

With increasing efforts in recent years towards building quantum computers,
the task of verifying the quantum behavior of such computers is particularly
important. Integer factorization, one of the oldest theoretical examples of a
quantum advantage [Sho94], is one possible approach to this kind of
verification. However, building quantum computers that are able to surpass
classical computers in factoring is experimentally difficult and a far-off
task. Hence, it is desirable to find alternative _proofs of quantumness_ 222By
proof of quantumness, we mean a specific test, administered by a classical
verifier, which an efficient quantum device can pass at a noticeably higher
rate than any efficient classical device. that are easier for a quantum
computer to perform.

The authors of [BCM+21] did groundbreaking work in this direction by offering
an interactive proof of quantumness based on the hardness of LWE (learning
with errors). Follow-up work [BKVV20, KMCVY22, KLVY22] used their technical
ideas to optimize some aspects or provide trade-offs under different
assumptions. In this work we provide a proof of quantumness that utilizes
rotated measurements on claw states (Eq. 1) to achieve some new tradeoffs. The
advantage achieved in our protocol by a quantum device is described in the
following theorem.

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

Let $\lambda$ denote the security parameter. Suppose that $n,m,q,\sigma,\tau$
are functions of $\lambda$ that satisfy the constraints given in Fig. 1 from
Section 3, and suppose that the $\textnormal{LWE}_{n,q,G(\sigma,\tau)}$
problem is hard. Then, there exists a two round interactive protocol between a
verifier and a prover such that the following holds:

  * •

For any efficient classical prover, the verifier accepts with probability at
most $\frac{3}{4}+\operatorname{\mathrm{negl}(\lambda)}$.

  * •

For any quantum prover that follows the protocol honestly, the verifier
accepts with probability at least
$\cos^{2}\left(\frac{\pi}{8}\right)-\frac{5m\sigma^{2}}{q^{2}}-\frac{m\sigma}{2\tau}$.

The protocol for this theorem is referred to as Protocol $\mathbf{Q}$ and is
given in Fig. 4. Noting that $\cos^{2}(\pi/8)>0.85>\frac{3}{4}$, we deduce
that as long as the error term
$\frac{5m\sigma^{2}}{q^{2}}+\frac{m\sigma}{2\tau}$ vanishes as
$\lambda\to\infty$, a constant gap is achieved between the best possible
quantum winning probability and the best possible classical winning
probability. In Section 3.3, we show that this vanishing condition can be
achieved while taking the modulus $q$ to be only slightly asymptotically
larger than $n^{2}\sigma$ (where the parameter $n$ is the dimension of the LWE
problem, and $\sigma$ is the noise parameter). Our approach thus allows us to
base the security of our protocol on the LWE problem for a broad range of
parameters, including parameters that are comparable to those used in post-
quantum lattice-based cryptography. (For example, in the public-key
cryptosystem in [Reg09], the modulus is taken to be on the order of $n^{2}$.)
Previous works on interactive lattice-based proofs of quantumness have tended
to use a modulus that is either very large or not explicitly given.

Our proof builds on recent work, and most directly builds on [KLVY22]. In
comparison to the proof of quantumness described in [KLVY22], our protocol
involves preparing and measuring only one TCF claw state at each iteration,
whereas the proof described in ([KLVY22], Section 4.1) requires preparing and
measuring three TCF claw states (while maintaining quantum memory throughout).
Additionally, whereas [KLVY22] requires the use of quantum homomorphic
encryption schemes proved by other authors (and does not give explicit
parameters) our proof is self-contained and directly relates the security of
our protocol to the hardness of the underlying LWE problem. At the same time,
our approach inherits the following merits from [KLVY22]: our protocol
involves only $2$ rounds of interaction, it requires only one qubit to be
stored in memory in between rounds, and it does not require any cryptographic
assumptions beyond LWE.

As far as we are aware, the combination of features in our work has not been
achieved before (see Section 1.2), and our results thus bring the community
closer to establishing the minimal requirements for a lattice-based proof of
quantumness. As experimental progress continues [ZKML+21], there is good
reason to think that these proofs of quantumness may be realizable in the near
future.

#### Remote State Preparation.

Remote state preparation (RSP) is a protocol where a computationally weak
client delegates the preparation of a quantum state to a remote server. An RSP
protocol is blind if the server does not learn a classical description of the
state in the process of preparing it [DKL12]. Recently, [CCKW19] and [GV19]
introduced blind RSP with a completely classical client, based on the
conjectured quantum hardness of the LWE problem. Blind RSP has become an
essential subroutine to _dequantize_ the quantum channel in various quantum
cryptographic applications including blind and verifiable quantum computations
[BFK09, GV19, BCC+20], quantum money [RS22], unclonable quantum encryption
[GMP22], quantum copy protection [GMP22], and proofs of quantumness [MY22].

All previous RSP protocols prepare a single-qubit state
$\frac{1}{\sqrt{2}}(\ket{0}+e^{i\theta}\ket{1})$, where $\theta$ belongs to
some fixed set $S\subseteq[0,2\pi)$. However, a common feature among all the
schemes is that either the size of $S$ must be small, or the basis determined
by $\theta$ is not fixed a priori. Therefore, a natural question in this
context is:

_Can a completely classical client delegate the preparation of arbitrary
single-qubit states to a quantum server while keeping the basis fixed?_

Ideally, we would like to achieve this task in a single round of interaction.
Note that the previous RSP protocols along with _computing on encrypted data_
protocols such as [BFK09, FBS+14] can realize this task in two rounds of
interaction. In this work, we provide a simple scheme for _deterministic_
blind RSP that achieves this task without incurring any additional cost
compared to previous _randomized_ RSP schemes. Our protocol only requires one
round of interaction to prepare any single qubit state in the $XY$-plane
(modulo a phase flip). This is particularly helpful for applications which
require a client to delegate an encrypted quantum input, as it gives the
client more control over the state being prepared. The correctness and
blindness of the protocol are summarized in the theorem below.

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

Let $\lambda$ denote the security parameter. Suppose that $n,m,q,\sigma,\tau$
are functions of the security parameter $\lambda$ that satisfy the constraints
given in Fig. 1 from Section 3 and $\tau\geq 2m\sigma$, and suppose that the
$\textnormal{LWE}_{n,q,G(\sigma,\tau)}$ problem is hard. Then there exists a
one-round client-server remote state preparation protocol such that for any
$\alpha\in\mathbb{Z}_{q}$, the client can delegate the preparation of the
state
$\ket{\alpha}=\frac{1}{\sqrt{2}}\left(\ket{0}+e^{i\,2\pi\alpha/q}\ket{1}\right)$
with the following guarantees:

  * •

If the server follows the protocol honestly, then they prepare a state
$\ket{\beta}$ such that
$\bigl{\|}\outerproduct{\alpha}{\alpha}-Z^{b}\outerproduct{\beta}{\beta}Z^{b}\bigr{\|}_{1}\leq\frac{4\pi
m\sigma}{q}$, where $\norm{\cdot}_{1}$ denotes the trace norm and
$b\in\\{0,1\\}$ is a random bit that the client can compute after receiving
the server’s response.

  * •

The server gains no knowledge of $\alpha$ from interacting with the client.

#### Additional Applications.

The techniques in this paper invite application to other cryptographic tasks,
including verifiable random number generation, semi-quantum money, and
encrypted Hamiltonian simulation. In Section 7, we discuss possible future
research directions for these three topics, and we offer some preliminary
results.

###  1.2 Related Works

#### Proof of quantumness.

The study of proofs of quantumness based on LWE was initiated by Brakerski et
al. [BCM+21] who proposed a four-message (two-round) interactive protocol
between a classical verifier and a prover. Their protocol also involves
constructing only a single TCF claw state (like in our protocol), although it
requires holding the entire claw state in memory between rounds, and it uses
an exponentially large modulus.333One effect of using an exponentially large
modulus is on hardness assumptions. If we phrase our hardness asssumptions in
terms of the shortest vector problem in a lattice, then [BCM+21] assumes the
hardness of sub-exponential approximation of the shortest vector, while in the
current work we only assume that polynomial approximation is hard. See Section
3.3. Later, [BKVV20] gave a two-message (one-round) proof of quantumness with
a simpler and more general security proof, but at the cost of requiring the
random oracle assumption. More recently, [KMCVY22] introduced a proof of
quantummness with some of the same features as [BKVV20] without the random
oracle assumption, but they require up to $6$ messages in their protocol ($3$
rounds of interaction). Both [AGKZ20] and [YZ22] present constructions of
publicly verifiable proofs of quantumness, albeit with different assumptions
or models. Further works have based proofs of quantumness on different
assumptions [MY22], optimized the depth required for implementing TCFs [LG22,
HLG21], and even achieved prototype experimental realization [ZKML+21].

The paper [KLVY22] (which is the main predecessor to this work) presented a
generic compiler that turns any non-local game into a proof of quantumness and
gave an explicit scheme that only requires $4$ messages ($2$ rounds of
interaction). These results assume the existence of a quantum fully
homomomorphic encryption scheme that satisfies certain conditions (see
Definition 2.3 in [KLVY22]), and the authors sketch proofs that two known
schemes [Mah18, Bra18] satisfy such conditions.

An alternative route to proving a result similar to Theorem 1.1 would be to
expand the proof sketches in the appendices of [KLVY22] and use them to create
a proof of quantumness with explicit parameters. However, we expect this
approach to be less optimal both in mathematical complexity and computational
complexity. Combining [KLVY22] with [Mah18] would involve an exponentially
sized modulus $q$, and would require preparing and measuring three claw-states
during a single iteration of the central protocol. Combining [KLVY22] with
[Bra18] would also require preparing three states of size similar to claw
states, and would involve performing a $q$-ary Fourier transform on each
state. In contrast, our approach involves only preparing a single-claw state
and then performing single qubit operations on it.

#### Blind RSP.

Remote state preparation over a classical channel comes in two security
flavors — blind RSP and blind-verifiable RSP (in this work, we give a protocol
for the former). Such a primitive was first introduced in [CCKW21] for honest-
but-curious adversaries. This was later extended to fully malicious
adversaries in [CCKW19], where the authors present two blind RSP protocols,
one of which allows the client to delegate the preparation of a BB84 state
$\left(\\{\ket{0},\ket{1},\ket{+},\ket{-}\\}\right)$ and the other allows the
client to delegate the preparation of one of $8$ states in the $XY$-plane. The
former protocol has the advantage of allowing the client to choose if the
server is preparing a computational $\left(\\{\ket{0},\ket{1}\\}\right)$ or a
Hadamard $\left(\\{\ket{+},\ket{-}\\}\right)$ basis state. However, it is not
clear how to generalize the scheme to prepare quantum states from a large set
while maintaining control over the choice of basis. Independently, [GV19]
gives a blind-verifiable RSP scheme that generalizes [BCM+21], where the
blindness is based on the adaptive hardcore bit property. The protocol in
[GV19] can prepare one of $10$ states: $8$ in the $XY$-plane and the two
computational basis states. There is a natural way to generalize [GV19] to
prepare states of the form $\frac{1}{\sqrt{2}}(\ket{0}+\exp(i\,2\pi
x/q)\ket{1})$ with $x,q\in\mathbb{N}$. However, the naturally generalized
protocol requires an honest quantum server to apply a Fourier transform over
$\mathbb{Z}_{q}$ on the claw state, whereas we only require the server to
perform single-qubit gates on the claw state for any $q$. Moreover, the
quantity $x$ in the prepared state is randomly chosen in [GV19] whereas our
protocol allows the client to choose $x$. More recently, [MY22] constructs an
RSP protocol from different cryptographic assumptions (full domain trapdoor
permutations); however, the blindness is only shown against classical
adversaries.

Previous RSP protocols have proven to be immensely useful in several
cryptographic applications, ranging from proofs of quantumness [MY22] and
verification of quantum computation [GV19, Zha22] to computing on encrypted
data [BCC+20, GMP22], secure two-party quantum computation [CCKM20] and more.
Finally, RSP protocols have been extended to self-testing protocols [MV21,
MTH+22, FWZ22]. A self-testing protocol characterizes not only the state
prepared but also the measurements made upon them.

##  2 Technical Overview

Our protocol involves performing rotated measurements on the claw states put
forward by [BCM+21] to steer the final qubit of the claw state into a specific
form, while keeping this form secret by hiding it using LWE. Suppose that
$n,m,q$ are positive integers. The Learning With Errors (LWE) hardness
assumption implies that if a classical client chooses a uniformly random
vector $s\in\mathbb{Z}_{q}^{n}$ and a uniformly random matrix
$A\in\mathbb{Z}_{q}^{m\times n}$, and computes $v\coloneqq As+e$ where
$e\in\mathbb{Z}_{q}^{m}$ is a small noise vector, then a quantum server cannot
recover $s$ from $(A,v)$. Following [BCM+21] the server can (for certain
parameters) nonetheless approximately prepare a superposed _claw state_ of the
form
$\ket{\gamma}=\frac{1}{\sqrt{2}}\bigl{(}\ket{x_{1}}\ket{1}+\ket{x_{0}}\ket{0}\bigr{)},$
where $x_{0}\in\mathbb{Z}_{q}^{n}$ and $x_{1}=x_{0}+s$, along with a vector
$y\in\mathbb{Z}_{q}^{m}$ which is close to both $Ax_{0}$ and $Ax_{1}$. We will
assume that $x_{0}$ and $x_{1}$ are written out in base-$2$ using little-
endian order.

At this point, rather than having the server measure $|\gamma\rangle$ in the
$X$-basis, we can go in a different direction: suppose that the client
instructs the server to measure the $k^{\text{th}}$ qubit of $|\gamma\rangle$
in the basis $(\cos\theta_{k})X+(\sin\theta_{k})Y$ where $\theta_{k}$ are real
numbers for $k=1,2,\ldots,n\lceil\log q\rceil$, and report the result as a
binary vector $u=(u_{1},\ldots,u_{n\lceil\log q\rceil}).$ Once this is done,
the state of the final remaining qubit will be
$\frac{1}{\sqrt{2}}(\left|0\right>+e^{i\phi}\left|1\right>)$, where

$\phi\coloneqq\langle\theta,[x_{0}]\rangle-\langle\theta,[x_{1}]\rangle+\langle
u,[x_{0}]\oplus[x_{1}]\rangle\cdot\pi.$

Here $\langle\cdot,\cdot\rangle$ denotes the dot product, and $[x_{0}]$ and
$[x_{1}]$ denote the base-$2$ representations of $x_{0}$ and $x_{1}$. Since
the quantum server cannot know both $x_{0}$ and $x_{1}$, they cannot compute
$\phi$ from this formula. However, if the client possesses a trapdoor to the
original matrix $A$, then they can recover $x_{0}$ and $x_{1}$ from $y$ and
compute $\phi$.

We can go further: if the client chooses a vector
$t=(t_{1},\ldots,t_{n})\in\mathbb{Z}_{q}^{n}$ and sets $\theta$ by the formula
$\theta_{(i-1)n+j}\coloneqq 2^{j}t_{i}\pi/q$ for $i\in\\{1,2,\ldots,n\\}$ and
$j\in\\{1,2,\ldots,\lceil\log q\rceil\\}$, then

$\displaystyle\phi$ $\displaystyle=$ $\displaystyle\langle
t,x_{0}-x_{1}\rangle\cdot(2\pi/q)+\langle
u,[x_{0}]\oplus[x_{1}]\rangle\cdot\pi$ $\displaystyle=$ $\displaystyle-\langle
t,s\rangle\cdot(2\pi/q)+\langle u,[x_{0}]\oplus[x_{1}]\rangle\cdot\pi.$

The server thus computes a qubit that encodes a prescribed linear function
$\langle t,s\rangle$ of $s$, modulo a possible phase flip that is known to the
client – see Section 4. At the same time, LWE-hardness guarantees that the
vector $s$ remains unknown to the server. (This can be seen an enhancement of
the approach described in subsection 1.4 in [CCKW21]. We have used a different
measurement strategy in order to gain more control over the prepared qubit.)

We summarize our two applications of this idea, starting with blind remote
state preparation (blind RSP).

#### Blind RSP.

We will denote the state that the client wants the server to prepare (modulo a
phase flip) as
$\ket{\alpha}\coloneqq\frac{1}{\sqrt{2}}\bigl{(}\ket{0}+e^{i\,2\pi\alpha/q}\ket{1}\bigr{)}$
for some $\alpha\in\mathbb{Z}_{q}$ of the client’s choice. The way we will
ensure blindness with respect to $\alpha$ is by encrypting it using Regev’s
encryption scheme, described in Section 3.4, and having the server use the
ciphertext to prepare the state. To encrypt $\alpha$ as such the client
requires, in addition to an LWE instance, a uniformly sampled random vector
$f\leftarrow\\{0,1\\}^{m}$. The client then computes $f^{\top}(As+e)+\alpha$
and sends $(A,As+e)$ and
$(a,w)\coloneqq\left(f^{\top}A,f^{\top}(As+e)+\alpha\right)$ to the server.

The server uses $(A,As+e)$ to create a claw state, which also yields the image
$y$ of the claw, and then measures the claw state using the vector
$a\in\mathbb{Z}_{q}^{n}$ as described above. Then the server rotates the final
qubit around the $Z$-axis of the Bloch sphere by $2\pi w/q$. From the
discussion above we see that the resulting state will be
$\frac{1}{\sqrt{2}}\bigl{(}\ket{0}+e^{i\beta}\ket{1}\bigr{)}$ where

$\displaystyle\beta\coloneqq$ $\displaystyle-\langle
a,s\rangle\cdot(2\pi/q)+\langle u,[x_{0}]\oplus[x_{1}]\rangle\cdot\pi+2\pi
w/q$ $\displaystyle=$ $\displaystyle-2\pi
f^{\top}As/q+2\pi\bigl{(}f^{\top}(As+e)+\alpha\bigr{)}/q+\langle
u,[x_{0}]\oplus[x_{1}]\rangle\cdot\pi$ $\displaystyle\approx$
$\displaystyle\;2\pi\alpha/q+b\cdot\pi,$

by denoting $b\coloneqq\langle u,[x]\oplus[x_{1}]\rangle$ and letting $e/q$ be
small (a more explicit calculation is provided in Section 6.1). The final
state held by the server is $Z^{b}\ket{\alpha}$, as desired. Finally, the
server sends the measurements $y$ and $u$ to the client who can use them along
with the trapdoor of $A$ to learn $b$. Note that while the client has control
over $\alpha$, they do not have control over the bit $b$ as it is a function
of the server’s measurements.

The blindness property of the protocol is derived from the security of Regev’s
encryption scheme, which is based on the hardness of LWE. The information that
the server receives during the protocol is $\left(A,As+e\right)$ and
$\bigl{(}f^{\top}A,f^{\top}(As+e)+\alpha\bigr{)}$. The first pair is the
public key in Regev’s encryption scheme and the second pair is the ciphertext
encrypting the message $\alpha$. Hence, if an adversary can guess $\alpha$ in
our RSP protocol then they can break Regev’s encryption scheme.

#### Proof of Quantumness.

Our proof of quantumness is based on the CHSH game [CHSH69], which is a game
played with a referee and two players (Charlie and David) who cannot
communicate with each other. The referee sends bits $b$ and $b^{\prime}$
chosen uniformly at random to Charlie and David respectively. Charlie and
David are required to return bits $d$ and $d^{\prime}$ to the referee, who
decides that they win if and only if $d\oplus d^{\prime}=b\wedge b^{\prime}$.

Recent work [KLVY22] has proposed a version of the nonlocal CHSH game that a
single server (Bob) can play with a classical client (Alice) to prove the
quantumness of the server. However, the protocol in [KLVY22] requires the
server to evaluate a controlled-Hadamard gate under a homomorphic encryption
scheme, which requires preparing and measuring three claw states while
maintaining qubits in quantum memory. By combining the ideas in [KLVY22] with
our RSP protocol, we obtain the following proof of quantumness protocol that
only requires preparing and measuring one claw state.

Our central protocol (Fig. 4 and Fig. 5) is roughly the following. Alice
begins by choosing bits $b$ and $b^{\prime}$ uniformly at random. Then, Alice
uses our RSP protocol to delegate to Bob the preparation of a state of the
form $(I+(-1)^{d}X)/2$ (if $b=0$) or of the form $(I+(-1)^{d}Y)/2$ (if $b=1$).
From the RSP process, Bob obtains an encryption of the bit $d$ which he sends
back to Alice for her to decrypt. Alice then sends $b^{\prime}$ to Bob, and he
measures his state in the eigenbasis of
$\frac{1}{\sqrt{2}}(X+(-1)^{b^{\prime}}Y)$ and returns the outcome bit
$d^{\prime}$ to Alice. Alice considers Bob to have won the game if and only if
$d\oplus d^{\prime}=b\wedge b^{\prime}$.

It can be seen that the distribution over $(b,b^{\prime},d,d^{\prime})$ in the
procedure described above is approximately the same as the distribution in the
nonlocal CHSH game when the two players implement the optimal quantum
strategy. Therefore, a quantum Bob can win with probability approximately
$\cos^{2}(\pi/8)\approx 0.85$ (Theorem 5.1). On the other hand, by adapting
reasoning from [KLVY22], we show that an efficient classical Bob cannot do
much better than the optimal classical winning probability for the CHSH game,
which is $0.75$ (Theorem 5.3). Therefore, with appropriate parameter choices
(see Section 3.3), a constant gap is achieved between the best possible
classical and quantum winning probabilities.

##  3 Preliminaries

Let $\mathbb{C},\mathbb{Z},\mathbb{N}$ denote, respectively, the field of
complex numbers, the ring of integers, and the set of nonnegative integers.
For any $c\in\mathbb{N}$, let $\mathbb{Z}_{c}$ denote the set
$\\{0,1,\ldots,c-1\\}$ with multiplication and addition defined modulo $c$. If
$x\in\mathbb{Z}_{c}$, then $|x|\coloneqq\min\\{x,c-x\\}.$ If
$v=(v_{1},\ldots,v_{s})$ is a vector with entries from any of
$\mathbb{C},\mathbb{Z}$, or $\mathbb{Z}_{c}$, we write
$\left\|v\right\|_{\infty}$ for the infinity norm of $v$, defined by
$\norm{v}_{\infty}\coloneqq\max_{i}|v_{i}|.$

We denote by $\\{0,1\\}^{*}$ the set of all finite-length bit strings. For
$s\in\\{0,1\\}^{*}$ and $k\in\mathbb{N}$, let $s^{k}\in\\{0,1\\}^{*}$ denote
$s$ repeated $k$ times. The symbol $||$ denotes string concatenation. We write
MAJ for the function $\textnormal{MAJ}\colon\\{0,1\\}^{*}\to\\{0,1\\}$ defined
by $\textnormal{MAJ}(s)=1$ if and only if the Hamming weight of $s$ is at
least half its length. If $a,b$ are vectors of the same length, we may write
either $\left<a,b\right>$ or $a\cdot b$ for the dot product of $a$ and $b$.

For a finite set $S$, we write $s\leftarrow S$ to mean $s$ is sampled
uniformly at random from $S$. If $\chi$ is a distribution on $S$, we write
$s\leftarrow\chi$ to mean $s$ is sampled from $S$ according to $\chi$. The
expression $\chi^{n}$ denotes the distribution of $n$-length sequences of
independent samples of $\chi$. For a set $A$, we write $D(A)$ for the set of
probability distributions on $A$.

The expression $\log$ always denotes the logarithm in base $2$. If
$k\in\mathbb{Z}_{c}$ (viewed as $\\{0,1,\ldots,c-1\\}$), then
$[k]\in\\{0,1\\}^{\lceil\log c\rceil}$ denotes the binary representation of
$k$ in little-endian order (i.e., with the least significant bits first). If
$x\in\mathbb{Z}_{c}^{d}$, then $[x]$ denotes the concatenation of
$[x_{1}],[x_{2}],\ldots,[x_{d}]$.

For any finite set $S$, the expression $\mathbb{C}^{S}$ denotes the Hilbert
space of functions from $S$ to $\mathbb{C}$. Let $L(S)$ denote the set of
linear maps from $\mathbb{C}^{S}$ to itself. A quantum state on $S$ is an
element of $L(S)$ that is trace-$1$ and positive semidefinite (i.e., a density
operator on $\mathbb{C}^{S}$). A pure quantum state on $S$ is a rank-$1$
quantum state. Any pure quantum state on $S$ can be written as
$\rho\coloneqq\outerproduct{\alpha}{\alpha}$, where $\ket{\alpha}$ is a unit
vector in $\mathbb{C}^{S}$, and we may also refer to $\ket{\alpha}$ as a pure
quantum state. The trace distance between two quantum states $\rho$ and
$\sigma$ on $S$ is defined by $\norm{\rho-\sigma}_{1}$, where
$\norm{\cdot}_{1}$ denotes the trace norm. Note that
$\norm{\outerproduct{\alpha}{\alpha}-\outerproduct{\beta}{\beta}}_{1}=2(1-\absolutevalue{\innerproduct{\alpha}{\beta}}^{2})^{1/2}$.
If $T$ is another finite set, then a quantum operation from $S$ to $T$ is a
completely positive trace-preserving map from $L(S)$ to $L(T)$.

Throughout this work, $\lambda\in\mathbb{N}$ denotes the security parameter. A
function $f\colon\mathbb{N}\to\mathbb{R}_{\geq 0}$ of $\lambda$ is negligible
if it is $O(\lambda^{-C})$ for all $C>0$.

###  3.1 Model of Quantum Computation

We define terms related to quantum algorithms. A standard way to define a
quantum circuit is as a composition of gates drawn from some specified finite
set of primitive gates. Since we are concerned here with protocols that
involve general single-qubit rotations, we will use a larger set of primitive
gates. Let $X$, $Y$, and $Z$ denote the Pauli operators

$X=\begin{bmatrix}0&1\\\ 1&0\end{bmatrix},\quad Y=\begin{bmatrix}0&-i\\\
i&0\end{bmatrix},\quad\text{and}\quad Z=\begin{bmatrix}1&0\\\
0&-1\end{bmatrix}.$ (3)

A quantum circuit is then a composition of the following primitive operations:

  1. 1.

Any single qubit gate of the form $e^{i\pi(p/q)R}$, where $p,q\in\mathbb{Z}$,
$q\neq 0$, and $R\in\\{X,Y,Z\\}$.

  2. 2.

The Toffoli gate $T\colon\left(\mathbb{C}^{2}\right)^{\otimes
3}\to\left(\mathbb{C}^{2}\right)^{\otimes 3}$, given by
$T\left|x\right>\left|y\right>\left|z\right>=\left|x\right>\left|y\right>\left|z+xy\right>$.

  3. 3.

The gate which creates a single qubit in state $\left|0\right>$.

  4. 4.

The gate which measures a single qubit in the computational basis.

If a quantum circuit is composed only of unitary gates (i.e., it does not
involve creating or measuring qubits) then we refer to it as a unitary quantum
circuit. If a quantum circuit $Q$ has $m$ input qubits, and $n$ output qubits,
and $\ell$ intermediate primitive operations, then the size of $Q$ is
$n+m+\ell$. Such a circuit determines a function from $\\{0,1\\}^{m}$ to the
set of probability distributions on $\\{0,1\\}^{n}$.

###  3.2 Learning With Errors

For any real number $s>0$, let $G(s)$ denote the discrete Gaussian probability
distribution on $\mathbb{Z}$, defined as follows: if $X$ is a random variable
distributed according to $G(s)$, and $x\in\mathbb{Z}$, then

$P(X=x)=\frac{e^{-x^{2}/(2s^{2})}}{\sum\limits_{y\in\mathbb{Z}}e^{-y^{2}/(2s^{2})}}.$
(4)

If $t>0$, let $G(s,t)$ denote the distribution obtained from $G(s)$ by
conditioning on the event $\left|X\right|\leq t$. We will need the following
lemma about $G(s)$.

######  Lemma 3.1 (Corollary 9 of [CKS20]).

Let $X$ be distributed according to $G(s)$. Then
$\operatorname{\mathrm{E}}[X]=0$ and $\operatorname{\mathrm{Var}}[X]\leq
s^{2}$. If $C\geq 0$, then $\operatorname{\mathrm{Pr}}[X\geq C]\leq
e^{-C^{2}/(2s^{2})}$.

In the following, $\chi$ denotes a probability distribution on $\mathbb{Z}$
(which in this paper will always be a Gaussian or truncated Gaussian
distribution).

The $\textnormal{LWE}_{c,d,\chi}$ Problem: Let $\mathcal{D}_{0}$ denote the
probability distribution of $(a,a\cdot
s+e)\in\mathbb{Z}_{q}^{c}\times\mathbb{Z}_{q}$, where
$a\leftarrow\mathbb{Z}_{d}^{c}$, $s\leftarrow\mathbb{Z}_{q}^{c}$, and
$e\leftarrow\chi$. Let $\mathcal{D}_{1}$ denote the probability distribution
of $(a,v)$, where $a\leftarrow\mathbb{Z}_{d}^{c}$ and
$v\leftarrow\mathbb{Z}_{d}$. Given oracle access to $\mathcal{D}_{b}$, where
$b\leftarrow\\{0,1\\}$, determine the value of $b$.

###  3.3 Parameters and assumptions

Throughout this paper, we will assume
$m=m(\lambda),n=n(\lambda),q=q(\lambda),Q=Q(\lambda),\sigma=\sigma(\lambda),\tau=\tau(\lambda)$
are real-valued functions of the security parameter $\lambda$ which satisfy
all of the conditions in Fig. 1.

Parameter list: $\begin{array}[]{rl}q:&\textnormal{modulus}\\\
Q:&\textnormal{binary length of modulus}\\\ n,m:&\textnormal{matrix
dimensions}\\\ \sigma:&\textnormal{standard deviation of Gaussian noise}\\\
\tau:&\textnormal{truncation factor for Gaussian noise}\\\ \end{array}$
Assumptions: • $\log q$ and $\log\sigma$ are polynomially bounded functions of
$\lambda$ • $\sigma\geq 1$ • $q$ is always an odd prime • $Q=\lceil\log
q\rceil$ • $n=\lambda$ • $m=n(2Q+1)$ • $\tau=q/(4mQ)$

Figure 1:  Parameters and assumptions.

The rationale for the conditions in Fig. 1 is the following.

  * •

The quantity $m$, which specifies the number of rows in the LWE matrix $A$
that we will use, needs to be sufficiently large for the single-bit encryption
algorithm in Section 3.4 to be secure and for $A$ to accommodate a trapdoor
(Section 3.5). The formula $m=n(2Q+1)$ accomplishes both purposes.

  * •

The truncation factor $\tau$ is chosen sufficiently small to allow LWE samples
involving the matrix $A$ to be inverted, using a trapdoor, with probability
$1$.

We discuss more specific parameter choices in Section 5.3.

If we say that we assume that the $\textnormal{LWE}_{n,q,G(\sigma)}$ problem
is hard for particular parameter functions
$n=n(\lambda),q=q(\lambda),\sigma=\sigma(\lambda)$, we mean that we assume
that any non-uniform quantum polynomial-time algorithm will solve the
$\textnormal{LWE}_{n,q,G(\sigma)}$ problem with probability at most
$\frac{1}{2}+\operatorname{\mathrm{negl}(\lambda)}$. Note that if
$\tau/\sigma=\omega(\log\lambda)$, then the distribution of $G(\sigma,\tau)$
is negligibly different from $G(\sigma)$ by Lemma 3.1, and so the hardness of
$\textnormal{LWE}_{n,q,G(\sigma,\tau)}$ is equivalent to the hardness of
$\textnormal{LWE}_{n,q,G(\sigma)}$.

As shown in [Reg09]444Strictly speaking, the next statement does not
immediately follow from [Reg09] because the error distributions
$\bar{\Psi}_{\alpha}$ and $\Psi_{\alpha}$ defined there do not exactly
correspond to discrete Gaussians. However, it does follow after we first apply
[Pei10, Theorem 1] to reduce $\textnormal{LWE}_{n,q,\Psi_{\sqrt{2\pi}\alpha}}$
to $\textnormal{LWE}_{n,q,G(\sigma)}$, where $\sigma=\alpha q$., we can assume
that the $\textnormal{LWE}_{n,q,G(\sigma)}$ problem is hard for
$n,q,\sigma=\alpha q$ with $\alpha\in(0,1)$ and $\alpha
q>\sqrt{2/\pi}\cdot\sqrt{n}$ if we assume that no non-uniform quantum
polynomial-time algorithm can solve the Shortest Independent Vectors Problem
(SIVP) in worst-case lattices of dimension $n$ to within an approximation
factor of $\tilde{O}(n/\alpha)$.

###  3.4 A Simple Encryption Algorithm

In Section 5 we will make use of a single-bit encryption algorithm which is
very similar to the original lattice-based encryption algorithm proposed by
Regev in [Reg09]. This algorithm is shown in Fig. 2, and consists of three
algorithms: Gen (key generation), Encrypt, and Decrypt. Essentially, the
public key is an LWE matrix $(A,v)\coloneqq(A,As+e)$, where $s$ is a secret
vector and $e$ is a Gaussian noise vector. Given a random bit $b$, a
ciphertext $ct$ is computed by summing up a random subset of the rows of
$[A|v]$ and then adding a quantity (dependent on $b$) to the last coordinate
of the sum. There is one important and unique feature of Protocol $K$: rather
than adding $b\lfloor q/2\rfloor$ to the final coordinate of the ciphertext
(which would optimize decoding) we add $b\lfloor q/4\rfloor$ instead, which
will aid us in Section 5.

$K=(\textnormal{Gen}_{K},\textnormal{Encrypt}_{K},\textnormal{Decrypt}_{K})$ •
$\textnormal{Gen}_{K}()$ samples vectors
$s\leftarrow\mathbb{Z}_{q}^{n},e\leftarrow G(\sigma,\tau)^{m}$, samples a
matrix $A\leftarrow\mathbb{Z}_{q}^{m\times n}$, computes $v\coloneqq As+e$,
and returns $(pk,s)$, where $pk\coloneqq(A,v).\\\ $ •
$\textnormal{Encrypt}_{K}(pk,b)$ samples $f\leftarrow\\{0,1\\}^{m}$, computes
$a\coloneqq f^{\top}A$ and $w\coloneqq f^{\top}v+b\lfloor q/4\rfloor$, and
returns $ct$, where $ct\coloneqq(a,w).$ • $\textnormal{Decrypt}_{K}(sk,ct)$
computes $\ell\coloneqq\langle a,s\rangle-w,$ and returns $1$ if
$|\ell+\lfloor q/4\rfloor|\leq|\ell|$, and returns $0$ otherwise.

Figure 2: The single-bit public-key encryption algorithm $K$. $pk$ is the
public key, $s$ is the secret key, $b$ is the message, and $ct$ is the
ciphertext.

The following result asserts the IND-CPA security (that is, security against
chosen-plaintext attacks) for Protocol $K$. The proof is standard and is given
in Appendix B.

######  Proposition 3.2.

If the $\textnormal{LWE}_{n,q,G(\sigma,\tau)}$ problem is hard, then for any
non-uniform quantum polynomial-time algorithm $\mathcal{B}$, we have
$\operatorname{\mathrm{Pr}}[b^{\prime}=b]\leq\frac{1}{2}+\operatorname{\mathrm{negl}(\lambda)}$,
where the probability is over
$pk\leftarrow\textnormal{Gen}_{K}(),b\leftarrow\\{0,1\\},ct\leftarrow\textnormal{Encrypt}_{K}(pk,b),$
and $b^{\prime}\leftarrow\mathcal{B}(pk,ct)$.

###  3.5 Trapdoors for LWE matrices

Both of the applications in this paper will rely on trapdoors for LWE samples.
The following is a slightly modified version of Theorem 2 from [MP12]. (The
main difference is that we bound the noise vector using the infinity-norm
rather than the Euclidean norm.)

######  Proposition 3.3.

There is a probabilistic polynomial-time algorithm $\textnormal{GenTrap}()$
and a deterministic polynomial-time algorithm $\textnormal{Invert}(A,v,t)$
satisfying the following.

  1. 1.

$\textnormal{GenTrap}()$ accepts no input and returns a pair $(A,t)$, where
$A$ is an $m\times n$ matrix with entries in $\mathbb{Z}_{q}$. The matrix $A$
is within statistical distance $nQ2^{-n/2}$ from a uniformly random matrix.

  2. 2.

Given a pair $(A,t)$ obtained from $\textnormal{GenTrap}()$ and vectors
$s\in\mathbb{Z}_{q}^{n}$ and $e\in\mathbb{Z}_{q}^{m}$ satisfying
$\left\|e\right\|_{\infty}\leq 2\tau$, the algorithm
$\textnormal{Invert}(A,As+e,t)$ returns the value $s$.

###### Proof.

See Appendix C. ∎

We make note of the following, which is an easy consequence of Proposition
3.3.

######  Proposition 3.4.

If $(A,t)$ is a sample obtained from $\textnormal{GenTrap}()$, then for any
nonzero vector $v\in\mathbb{Z}_{q}^{n}$, we must have
$\left\|Av\right\|_{\infty}>4\tau$.

###### Proof.

Suppose that $v\neq 0$ were such that $\left\|Av\right\|_{\infty}\leq 4\tau$.
Then, we can find vectors $e,e^{\prime}$ of infinity norm less than or equal
to $2\tau$ such that $Av=e+e^{\prime}$. We have

$0=\textnormal{Invert}(A,0+e,t)=\textnormal{Invert}(A,Av-e^{\prime},t)=v,$ (5)

which is a contradiction. ∎

$J=(\textnormal{Gen}_{J},\textnormal{Encrypt}_{J},\textnormal{Decrypt}_{J})$ •
$\textnormal{Gen}_{J}()$ samples $s\leftarrow\mathbb{Z}_{q}^{n},e\leftarrow
G(\sigma,\tau)^{m}$, $(A,t)\leftarrow\textnormal{GenTrap}()$, computes
$v\coloneqq As+e$, and returns $(pk,s,t)$, where $pk\coloneqq(A,v).\\\ $ The
algorithms $\textnormal{Encrypt}_{J}$ and $\textnormal{Decrypt}_{J}$ are the
same as the algorithms $\textnormal{Encrypt}_{K}$ and
$\textnormal{Decrypt}_{K}$ in Fig. 2.

Figure 3: The single-bit public-key encryption algorithm $J$.

For the results in Section 5, it will be important to have a version of the
encryption algorithm from Fig. 2 that has a trapdoor for the encoding matrix
$A$. See Fig. 3. (Only the $\textnormal{Gen}()$ algorithm is different. The
trapdoor is not used for encryption or decryption.) The following proposition
follows directly from Propositions 3.2 and 3.3.

######  Proposition 3.5.

If the $\textnormal{LWE}_{n,q,G(\sigma,\tau)}$ problem is hard, then for any
non-uniform quantum polynomial-time algorithm $\mathcal{B}$, we have
$\operatorname{\mathrm{Pr}}[b^{\prime}=b]\leq\frac{1}{2}+\operatorname{\mathrm{negl}(\lambda)}$,
where the probability is over
$pk\leftarrow\textnormal{Gen}_{J}(),b\leftarrow\\{0,1\\},ct\leftarrow\textnormal{Encrypt}_{J}(pk,b),$
and $b^{\prime}\leftarrow\mathcal{B}(pk,ct)$.

##  4 Rotated Measurements on Generalized GHZ States

The purpose of this section is to prove Proposition 4.2, which shows how
rotated measurements behave when applied to states that generalize GHZ states
[GHZ89], defined below.

######  Definition 4.1 (Generalized GHZ state).

Let $d$ be a positive integer. A generalized GHZ state on $d+1$ qubits is a
state of the form

$\frac{1}{\sqrt{2}}(\ket{x}\ket{1}+\ket{y}\ket{0}),$ (6)

where $x,y\in\\{0,1\\}^{d}$.

Given any sequence of real numbers $\theta_{1},\ldots,\theta_{n}$, we make use
of an associated sequence of real numbers $r_{1},\ldots,r_{nQ}$ defined by

$\begin{array}[]{lllllllll}r_{1}=\theta_{1}&&r_{2}=2\theta_{1}&&r_{3}=4\theta_{1}&&\ldots&&r_{Q}=2^{Q-1}\theta_{1}\\\
r_{Q+1}=\theta_{2}&&r_{Q+2}=2\theta_{2}&&r_{Q+3}=4\theta_{2}&&\ldots&&r_{2Q}=2^{Q-1}\theta_{2}\\\
\vdots&&\vdots&&\vdots&&\ddots&&\vdots\\\
r_{nQ-Q+1}=\theta_{n}&&r_{nQ-Q+2}=2\theta_{n}&&r_{nQ-Q+3}=4\theta_{n}&&\ldots&&r_{nQ}=2^{Q-1}\theta_{n}.\end{array}$
(7)

######  Proposition 4.2.

Let $x,y\in\mathbb{Z}_{q}^{n}$, let $\ket{\psi}$ denote the $(nQ+1)$-qubit
generalized GHZ state

$\ket{\psi}\coloneqq\frac{1}{\sqrt{2}}\bigl{(}\ket{[x]}\otimes\ket{1}+\ket{[y]}\otimes\ket{0}\bigr{)},$
(8)

and let $\theta_{1},\ldots,\theta_{n}\in\mathbb{Z}\cdot(2\pi/q)$. Let
$r_{1},\ldots,r_{nQ}$ be the sequence defined in Eq. 7. Suppose that for each
$i\in\\{1,2,\ldots,nQ\\}$, the $i^{\text{th}}$ qubit of $\ket{\psi}$ is
measured in the eigenbasis of

$(\cos r_{i})X+(\sin r_{i})Y$ (9)

and that the outcome is $(-1)^{u_{i}}\in\\{-1,1\\}$. Then the state of the
remaining qubit is
$\frac{1}{\sqrt{2}}\bigl{(}\ket{0}+e^{i\theta}\ket{1}\bigr{)},$ where

$\theta\coloneqq\sum_{i=1}^{n}(y_{i}-x_{i})\theta_{i}+\pi\sum_{i=1}^{n}\sum_{j=1}^{Q}([y_{i}]_{j}-[x_{i}]_{j})u_{(i-1)Q+j}.$
(10)

###### Proof.

The eigenvectors of the matrix in Eq. 9 are given by

$\ket{+_{r_{i}}}\coloneqq\frac{1}{\sqrt{2}}(\ket{0}+e^{ir_{i}}\ket{1})\quad\text{and}\quad\ket{-_{r_{i}}}\coloneqq\frac{1}{\sqrt{2}}(\ket{0}-e^{ir_{i}}\ket{1}),$
(11)

where $\ket{+_{r_{i}}}$ is the $+1$ eigenvector and $\ket{-_{r_{i}}}$ is the
$-1$ eigenvector. For a string $s\in\\{0,1\\}^{nQ}$ and
$t\in\\{1,2,\ldots,nQ\\}$, let $s_{\geq t}$ denote the suffix of $s$ starting
at index $t$ (when $t>\absolutevalue{s}$, $s_{\geq t}$ denotes the empty
string). Define $\phi_{t}$ by

$\phi_{t}\coloneqq\begin{cases}\sum_{j=1}^{t-1}([y]_{j}-[x]_{j})(r_{j}+\pi
u_{j})&\text{if $t>1$},\\\ 0&\text{if $t=1$}.\end{cases}$ (12)

We want to show that measuring the first qubit of the $nQ-t+2$ qubit state

$\ket{\psi_{t}}\coloneqq\frac{1}{\sqrt{2}}\bigl{(}e^{i\phi_{t}}\ket{[x]_{\geq
t}}\ket{1}+\ket{[y]_{\geq t}}\ket{0}\bigr{)}$

in the eigenbasis of $\cos(\theta_{t})X+\sin(\theta_{t})Y$ yields the state
$\ket{\psi_{t+1}}$. The description of the post-measurement state is given by

$\displaystyle\frac{1}{\sqrt{2}}\bra{\pm_{r_{t}}}_{1}(e^{i\phi_{t}}\ket{[x]_{\geq
t}}\ket{1}+\ket{[y]_{\geq t}}\ket{0})$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}(e^{i\phi_{t}}\innerproduct{\pm_{r_{t}}}{[x]_{t}}\ket{[x]_{\geq{t+1}}}\ket{1}+\innerproduct{\pm_{r_{t}}}{[y]_{t}}\ket{[y]_{\geq
t+1}}\ket{0})$ (13) $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(e^{-i[y]_{t}\left(r_{t}+\pi
u_{t}\right)}\ket{[y]_{\geq
t+1}}\ket{0}+e^{i\phi_{t}}e^{-i[x]_{t}\left(r_{t}+\pi
u_{t}\right)}\ket{[x]_{\geq{t+1}}}\ket{1}\right)$ (14) $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\ket{[y]_{\geq
t+1}}\ket{0}+e^{i\left(\phi_{t}+\left([y]_{t}-[x]_{t}\right)\left(r_{t}+\pi
u_{t}\right)\right)}\ket{[x]_{\geq{t+1}}}\ket{1}\right)$ (15) $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}\left(\ket{[y]_{\geq
t+1}}\ket{0}+e^{i\phi_{t+1}}\ket{[x]_{\geq{t+1}}}\ket{1}\right).$ (16)

Since $\ket{\psi_{1}}=\ket{\psi}$, then after performing all of the $nQ$
measurements described in the proposition statement we are left with the state
$\ket{\psi_{nQ+1}}$. It remains to show that $\phi_{nQ+1}=\theta$:

$\displaystyle\phi_{nQ+1}=$
$\displaystyle\sum\limits_{j=1}^{nQ}([y]_{j}-[x]_{j})(r_{j}+\pi u_{j})$ (17)
$\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{Q}([y_{i}]_{j}-[x_{i}]_{j})(r_{(i-1)Q+j}+\pi
u_{(i-1)Q+j})$ (18) $\displaystyle=$
$\displaystyle\Bigl{(}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{Q}([y_{i}]_{j}-[x_{i}]_{j})2^{j-1}\theta_{i}\Bigr{)}+\Bigl{(}\pi\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{Q}([y_{i}]_{j}-[x_{i}]_{j})u_{(i-1)Q+j}\Bigr{)}$
(19) $\displaystyle=$
$\displaystyle\Bigl{(}\sum\limits_{i=1}^{n}(y_{i}-x_{i})\theta_{i}\Bigr{)}+\Bigl{(}\pi\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{Q}([y_{i}]_{j}-[x_{i}]_{j})u_{(i-1)Q+j}\Bigr{)}=\theta.$
(20)

This completes the proof. ∎

##  5 An Optimized Proof of Quantumness

This section constructs a proof of quantumness based on the assumed hardness
of the LWE problem. Our central protocol in this section, Protocol
$\mathbf{Q}$ in Fig. 4, follows the form of the CHSH protocol from [KLVY22],
although [KLVY22] uses a quantum homomomorphic encryption scheme and we
instead use the encryption scheme $J$ from Fig. 3. First the single prover is
given an encrypted version of the first input bit $b$, and returns an
encrypted version of the first output bit $d$ (steps 1–2). Then, the prover is
given the second input bit $b^{\prime}$ as plaintext and returns $d^{\prime}$
(steps 3–4). Finally, the verifier decrypts $d$ (step 5) and scores the result
(step 6).

Protocol Q: 1. Alice samples $(pk=(A,v),s,t)\leftarrow\textnormal{Gen}_{J}()$,
$b\leftarrow\\{0,1\\}$, and computes
$ct=(a,w)\leftarrow\textnormal{Encrypt}_{J}(pk,b).$ Alice broadcasts $(pk,ct)$
to Bob. 2. Bob returns a pair $(y,u)$ where $y\in\mathbb{Z}_{q}^{m}$ and
$u\in\\{0,1\\}^{nQ}$. 3. Alice samples $b^{\prime}\leftarrow\\{0,1\\}$ and
broadcasts $b^{\prime}$ to Bob. 4. Bob returns a bit $d^{\prime}$. 5. Alice
computes $x_{0}\coloneqq\textnormal{Invert}(A,y,t)$ and
$x_{1}\coloneqq\textnormal{Invert}(A,y+v,t)$ and $d\coloneqq
u\cdot([x_{0}]\oplus[x_{1}]).$ (21) 6. If $d\oplus d^{\prime}=b\wedge
b^{\prime}$, then Bob succeeds. If $d\oplus d^{\prime}\neq b\wedge
b^{\prime}$, then Bob fails.

Figure 4: The proof of quantumness protocol, including the behavior of the
verifier (Alice).

###  5.1 Completeness

The ideal behavior for the prover (Bob) is given in Fig. 5. The primary
difference between Bob’s strategy in Fig. 5 in comparison to [BCM+21, KMCVY22,
KLVY22] is the use of rotated measurements to compute $u$.

Step 2. Bob prepares the state
$\ket{\phi}\coloneqq\frac{1}{\sqrt{2q^{n}(2\tau+1)^{m}}}\sum_{x\in\mathbb{Z}_{q}^{n}}\hskip
7.22743pt\sum_{c\in\\{0,1\\}}\hskip
7.22743pt\sum_{\begin{subarray}{c}g\in\mathbb{Z}_{q}^{m}\\\
\left\|g\right\|_{\infty}\leq\tau\end{subarray}}\ket{x}\ket{c}\ket{Ax-cv+g}$
(22) Bob measures the third register of this state to obtain a state of the
form $\left|\psi\right>\left|y\right>$. Bob computes $r_{1},\ldots,r_{nQ}$ via
the formulas $r_{(i-1)Q+j}\coloneqq 2^{j}\pi a_{i}/q\quad\text{ for
}i\in\\{1,\ldots,n\\},j\in\\{1,\ldots,Q\\},$ (23) and measures the $k$th qubit
of $\left|\psi\right>$ in the eigenbasis of $(\cos r_{k})X+(\sin r_{k})Y$ (24)
to obtain outcomes $(-1)^{u_{1}},(-1)^{u_{2}},\ldots,(-1)^{u_{nQ}}$. Bob
rotates the remaining qubit (which we denote by $L$) by the unitary operator
$\ket{0}\mapsto\ket{0},\ket{1}\mapsto e^{2\pi iw/q}\ket{1}$. Bob broadcasts
$(y,u_{1},\ldots,u_{nQ})$ to Alice. Step 4. Bob sets
$\xi=(-1)^{b^{\prime}}(\pi/4)$, measures $L$ in the eigenbasis of
$(\cos\xi)X+(\sin\xi)Y,$ (25) obtains outcome $(-1)^{d^{\prime}}$, and
broadcasts $d^{\prime}$ to Alice.

Figure 5: The behavior of an honest quantum prover in Protocol Q in Fig. 4.

The optimal quantum score for the ordinary CHSH game is
$\cos^{2}(\pi/8)=(1/2+\sqrt{2}/4)$. The next theorem implies that an honest
quantum prover will approach that score, provided that certain ratios between
the parameters $q,m,\sigma$ and $\tau$ vanish as $\lambda$ tends to infinity.

######  Theorem 5.1.

If Alice and Bob follow the process given in Figs. 4 and 5, then

$\operatorname{\mathrm{Pr}}[\textnormal{success}]\geq\cos^{2}\left(\frac{\pi}{8}\right)-\frac{5m\sigma^{2}}{q^{2}}-\frac{m\sigma}{2\tau}.$
(26)

###### Proof.

Let $T\coloneqq\\{e\in\mathbb{Z}_{q}\mid|e|\leq\tau\\}$. Consider the map
$S\colon\mathbb{Z}_{q}^{n}\times\\{0,1\\}\times T^{m}\to\mathbb{Z}_{q}^{m}$
defined by $S(x,c,g)=Ax-cv+g$.

Proposition 3.4 implies that any $y$ can have at most one pre-image in the set

$\mathbb{Z}_{q}^{n}\times\\{0\\}\times T^{m}$ (27)

and at most one pre-image in the set

$\mathbb{Z}_{q}^{n}\times\\{1\\}\times T^{m}.$ (28)

Moreover, when $y$ has two pre-images $(x_{0}^{\prime},0,g_{0})$ and
$(x_{1}^{\prime},1,g_{1})$ under $S$, we have

  1. 1.

$x_{0}^{\prime}=x_{0}$ by Proposition 3.3 since
$\norm{Ax_{0}^{\prime}-y}_{\infty}=\norm{g_{0}}_{\infty}\leq\tau$.

  2. 2.

$x_{1}^{\prime}=x_{1}$ by Proposition 3.3 since
$\norm{Ax_{1}^{\prime}-(y+v)}_{\infty}=\norm{g_{1}}_{\infty}\leq\tau$.

  3. 3.

$x_{1}^{\prime}=x_{0}^{\prime}+s$ by Proposition 3.4 since
$\norm{A(x_{1}^{\prime}-(x_{0}^{\prime}+s))}_{\infty}\leq
2\tau+\norm{v-As}_{\infty}\leq 3\tau$.

Let $U_{0}$ denote the set of all values of $y\in\mathbb{Z}_{q}^{m}$ that have
a pre-image under $S$ in (27) and let $U_{1}$ denote the set of all values of
$y\in\mathbb{Z}_{q}^{m}$ that have a pre-image under $S$ in set (28). A simple
counting argument shows that, conditioned on the value of $e\coloneqq
v-As\in\mathbb{Z}_{q}^{m}$, we have

$\operatorname{\mathrm{Pr}}[y\in U_{0}\cap U_{1}\mid
e]=\frac{\prod_{i=1}^{m}(2\tau+1-|e_{i}|)}{(2\tau+1)^{m}}.$ (29)

Therefore we have the following, in which we apply Lemma A.2.

$\displaystyle\operatorname{\mathrm{Pr}}[y\in U_{0}\cap U_{1}]$
$\displaystyle=E\left[\frac{\prod_{i=1}^{m}(2\tau+1-|e_{i}|)}{(2\tau+1)^{m}}\Bigm{|}e\leftarrow
G(\sigma,\tau)^{m}\right]$
$\displaystyle=E\left[\prod_{i=1}^{m}\left(1-\frac{|e_{i}|}{(2\tau+1)^{m}}\right)\Bigm{|}e\leftarrow
G(\sigma,\tau)^{m}\right]$ $\displaystyle\geq
E\left[1-\sum_{i=1}^{m}\frac{|e_{i}|}{(2\tau+1)}\Bigm{|}e\leftarrow
G(\sigma,\tau)^{m}\right]$
$\displaystyle=1-\frac{E\bigl{[}\sum_{i=1}^{m}|e_{i}|\mid e\leftarrow
G(\sigma,\tau)^{m}\bigr{]}}{(2\tau+1)}$ $\displaystyle\geq
1-\frac{m\sigma}{2\tau+1}\geq 1-\frac{m\sigma}{2\tau}.$ (30)

The following lemma upper bounds the probability of failure when $y\in
U_{0}\cap U_{1}$.

######  Lemma 5.2.

If Alice and Bob follow the process in Figs. 4 and 5, then

$\operatorname{\mathrm{Pr}}[\textnormal{failure}\mid y\in U_{0}\cap
U_{1}]\leq\sin^{2}\left(\frac{\pi}{8}\right)+\frac{5m\sigma^{2}}{q^{2}}+\frac{1}{q}.$
(31)

###### Proof.

When $y\in U_{0}\cap U_{1}$, by arguments made earlier in the proof, we have

$\ket{\psi}=\frac{1}{\sqrt{2}}(\ket{x_{1}}\ket{1}+\ket{x_{0}}\ket{0}),$ (32)

where $x_{1}=x_{0}+s$.

After Bob measures qubits $1,2,\ldots,nQ$ of $\ket{\psi}$ to obtain outcomes

$(-1)^{u_{1}},(-1)^{u_{2}},\ldots,(-1)^{u_{nQ}},$ (33)

the remaining qubit $L$ (by Proposition 4.2) is in state
$\frac{1}{\sqrt{2}}\bigl{(}\ket{0}+e^{i\theta}\ket{1}\bigr{)},$ where

$\displaystyle\theta$ $\displaystyle\coloneqq\frac{2\pi
a\cdot(x_{0}-x_{1})}{q}+\pi([x_{0}]-[x_{1}])\cdot(u_{1},\ldots,u_{nQ})$ (34)
$\displaystyle=-\frac{2\pi(a\cdot
s)}{q}+\pi([x_{0}]\oplus[x_{1}])\cdot(u_{1},\ldots,u_{nQ})\mod{2\pi}.$

Bob then rotates this state by the unitary operator
$\ket{0}\mapsto\ket{0},\ket{1}\mapsto e^{i\,2\pi w/q}\ket{1}$, where $w=a\cdot
s+f^{\top}e+b\lfloor q/4\rfloor$, to obtain the state
$\frac{1}{\sqrt{2}}\bigl{(}\ket{0}+e^{i\beta}\ket{1}\bigr{)},$ where
$\beta\coloneqq\frac{2\pi(f^{\top}e+b\lfloor
q/4\rfloor)}{q}+\pi([x_{0}]\oplus[x_{1}])\cdot(u_{1},\ldots,u_{nQ})$.

Measuring this qubit with the observable $(\cos\gamma)X+(\sin\gamma)Y$, for
any $\gamma\in\mathbb{R}$, yields outcome $+1$ with probability
$\cos^{2}((\gamma-\beta)/2)$ and outcome $-1$ with probability
$\sin^{2}((\gamma-\beta)/2)$. We therefore obtain the following formula for
the failure probability:

$\displaystyle\operatorname{\mathrm{Pr}}[\textnormal{failure}\mid y\in
U_{0}\cap U_{1}]$ (35)
$\displaystyle=\frac{1}{4}\operatorname{\mathrm{E}}\Biggl{[}\sin^{2}\left(\frac{\pi
f^{\top}e}{q}-\frac{\pi}{8}\right)+\sin^{2}\left(\frac{\pi
f^{\top}e}{q}+\frac{\pi}{8}\right)$
$\displaystyle\quad+\sin^{2}\left(\frac{\pi(f^{\top}e+\lfloor
q/4\rfloor)}{q}-\frac{\pi}{8}\right)+\cos^{2}\left(\frac{\pi(f^{\top}e+\lfloor
q/4\rfloor)}{q}+\frac{\pi}{8}\right)\Biggr{]},$

where the expectation is over $e\leftarrow G(\sigma,\tau)^{m}$ and
$f\leftarrow\\{0,1\\}^{m}$. For the rest of this proof, we consider all
expectations to be over the conditions $e\leftarrow G(\sigma,\tau)^{m}$ and
$f\leftarrow\\{0,1\\}^{m}$.

We can obtain an upper bound on the above expression for
$\operatorname{\mathrm{Pr}}[\textnormal{failure}]$ by replacing both instances
of $\lfloor q/4\rfloor$ with $q/4$, and adding a term at the end of the
expression to account for any increase that these replacements may cause.
Since the derivative of $\sin^{2}(\cdot)$ is always between $-1$ and $1$,
inserting the term $(1/q)$ suffices. Therefore,

$\displaystyle\operatorname{\mathrm{Pr}}[\textnormal{failure}\mid y\in
U_{0}\cap U_{1}]$
$\displaystyle\leq\frac{1}{4}E\Biggl{[}\sin^{2}\left(\frac{\pi
f^{\top}e}{q}-\frac{\pi}{8}\right)+\sin^{2}\left(\frac{\pi
f^{\top}e}{q}+\frac{\pi}{8}\right)$ (36)
$\displaystyle+\sin^{2}\left(\frac{\pi
f^{\top}e}{q}+\frac{\pi}{8}\right)+\cos^{2}\left(\frac{\pi
f^{\top}e}{q}+\frac{3\pi}{8}\right)\Biggr{]}+\frac{1}{q}$
$\displaystyle=4\cdot\frac{1}{4}E\Biggl{[}\sin^{2}\left(\frac{\pi
f^{\top}e}{q}+\frac{\pi}{8}\right)\Biggr{]}+\frac{1}{q}.$

Using Lemma A.4, we get that

$\operatorname{\mathrm{Pr}}[\textnormal{failure}\mid y\in U_{0}\cap
U_{1}]\leq\sin^{2}\left(\frac{\pi}{8}\right)+\sin\left(\frac{\pi}{4}\right)E\biggl{[}\frac{\pi
f^{\top}e}{q}\biggr{]}+E\Biggl{[}\left(\frac{\pi
f^{\top}e}{q}\right)^{2}\Biggr{]}+\frac{1}{q}.$ (37)

It is clear that $\operatorname{\mathrm{E}}[f^{\top}e]=0$, while

$\operatorname{\mathrm{E}}[(f^{\top}e)^{2}]=\sum_{i=1}^{m}\operatorname{\mathrm{E}}[(f_{i}e_{i})^{2}]=\sum_{i=1}^{m}\frac{1}{2}\operatorname{\mathrm{E}}[e_{i}^{2}]\leq
m\sigma^{2}/2,$ (38)

where the first equality follows from Lemma A.5 and the last inequality
follows from Lemma A.1.

Therefore,

$\operatorname{\mathrm{Pr}}[\textnormal{failure}\mid y\in U_{0}\cap
U_{1}]\leq\sin^{2}\left(\frac{\pi}{8}\right)+\frac{\pi^{2}\sigma^{2}m}{2q^{2}}+\frac{1}{q}\leq\sin^{2}\left(\frac{\pi}{8}\right)+\frac{5\sigma^{2}m}{q^{2}}+\frac{1}{q},$
(39)

as desired. ∎

Now we conclude the proof of Theorem 5.1. When the event $(y\in U_{0}\cap
U_{1})$ does not occur, Bob merely measures a computational basis state on
$nQ+1$ qubits using $nQ+1$ observables of the form
$(\cos\gamma)X+(\sin\gamma)Y$. Therefore, the bits $u_{1},\ldots,u_{nQ}$ and
$d^{\prime}$ that Bob returns to Alice are distributed uniformly at random,
and Bob thus succeeds at Protocol $\mathbf{Q}$ with probability $1/2$.
Therefore, by Lemma 5.2 and inequality (30), the overall probability that Bob
fails in the protocol is upper bounded by

$\sin^{2}\left(\frac{\pi}{8}\right)+\frac{5m\sigma^{2}}{q^{2}}+\frac{1}{q}+\frac{1}{2}\cdot\frac{m\sigma}{2\tau}.$
(40)

Since $\tau\leq q/4$ and $m\sigma\geq 1$, we can combine the last two summands
above to obtain

$\operatorname{\mathrm{Pr}}[\textnormal{failure}]\leq\sin^{2}\left(\frac{\pi}{8}\right)+\frac{5m\sigma^{2}}{q^{2}}+\frac{m\sigma}{2\tau},$
(41)

which implies the desired result. ∎

###  5.2 Soundness

The goal of this subsection is to put an upper bound on the probability that a
classical prover could succeed at Protocol Q in Fig. 4. We model the behavior
of a classical prover in Fig. 6. Bob responds to Alice’s queries in two rounds
using efficient classical algorithms while holding a private register $p$ in
memory between the two rounds.

Step 2. Bob receives input $(pk,ct)$ and computes
$(y,u,p)\leftarrow\textnormal{FirstResponse}(pk,ct),$ where FirstResponse is a
non-uniform probabilistic polynomial-time algorithm.
Step 4. Bob receives $b^{\prime}$ from Alice and computes
$d^{\prime}\leftarrow\textnormal{SecondResponse}(b^{\prime},p),$ where
SecondResponse is a non-uniform probabilistic polynomial-time algorithm.

Figure 6: A model of a classical adversary for Protocol Q in Fig. 4. The
register $p$ denotes internal memory held by the adversary between the rounds
of communication.

######  Theorem 5.3.

Suppose that the $\textnormal{LWE}_{n,q,G(\sigma,\tau)}$ problem is hard. If
Alice and Bob follow the process in Figs. 4 and 6, then

$\operatorname{\mathrm{Pr}}[\textnormal{success}]\leq\frac{3}{4}+\operatorname{\mathrm{negl}(\lambda)}.$
(42)

Our proof method comes from subsection 3.1 of [KLVY22]. We first make the
following elementary observation. Suppose that $T()$ is a non-uniform
probabilistic polynomial-time algorithm that outputs a single bit, and that
one wishes to optimally guess the output of $T()$. Clearly, the highest
probability with which this can be done is
$\kappa\coloneqq\max\left\\{\xi,1-\xi\right\\},$ where $\xi$ denotes the
expected value of $T()$. Consider the following procedure, which uses the
majority function (see Section 3).

  1. 1.

Sample $z_{1},z_{2},\ldots,z_{\lambda}\leftarrow T()$.

  2. 2.

Output $\textnormal{MAJ}(z_{1},z_{2},\ldots,z_{\lambda})$.

The Chernoff bound implies that if $z$ is obtained from this procedure and
$z^{\prime}\leftarrow T()$ is a new sample, then $P(z=z^{\prime})$ is within
$\exp(-\Omega(\lambda^{1/2}))$ of the optimal guessing probability $\kappa$.

###### Proof of Theorem 5.3.

Suppose, for the sake of contradiction, that there exists a classical
adversary

$\mathcal{A}=(\textnormal{FirstResponse},\textnormal{SecondResponse})$

that achieves a success probability at Protocol $\mathbf{Q}$ that is non-
negligibly higher than $\frac{3}{4}$. Consider Experiment $\mathbf{C}$, shown
in Fig. 7, in which two parties play a modified version of the CHSH game. The
Referee encrypts the first input bit $b$ using the scheme from Figure 3, and
transmits the resulting encryption to both Charlie and David while also giving
Charlie the trapdoor $t$. Then, Charlie and David play the CHSH game by doing
a simulation of the behavior of the adversary $\mathcal{A}$. The winning
probability in Experiment $\mathbf{C}$ is the same as the success probability
for $\mathcal{A}$ in Protocol $\mathbf{Q}$.

Experiment $\mathbf{C}$: Participants: Referee, Charlie, David 1. Referee
chooses input bits $b,b^{\prime}\leftarrow\\{0,1\\}$. She computes
$(pk,s,t)\leftarrow\textnormal{Gen}_{J}()$ and
$ct\leftarrow\textnormal{Encrypt}_{J}(pk,b)$ and sends $(pk,ct)$ to Charlie
and David. The referee also sends the trapdoor $t$ to Charlie. 2. David
computes $(y,u,p)\leftarrow\textnormal{FirstResponse}(pk,ct)$ and shares
$(y,u,p)$ with Charlie. 3. Referee transmits $b$ to Charlie and transmits
$b^{\prime}$ to David. 4. David computes
$d^{\prime}\leftarrow\textnormal{SecondResponse}(b^{\prime},p)$ and transmits
$d^{\prime}$ back to the Referee. 5. Charlie computes
$x_{0}\coloneqq\textnormal{Invert}(A,y,t)$ and
$x_{1}\coloneqq\textnormal{Invert}(A,y-v,t)$ and
$d=u\cdot([x_{0}]\oplus[x_{1}]).$ (43) Charlie transmits $d$ to the Referee.
6. If $d\oplus d^{\prime}=b\wedge b^{\prime}$, then Charlie and David win; if
not, they lose.

Figure 7: Two players (Charlie and David) play a modified version of the CHSH
game using procedures FirstResponse and SecondResponse from Fig. 6.

Note that if at step 5 Charlie was able to optimally guess the output of the
probabilistic algorithm SecondResponse, then he could compute the output $d$
that maximizes their winning probability. Since this strategy would have the
largest winning probability, we know that the winning probability of
Experiment $\mathbf{C}$ must be bounded above by it. Now consider Experiment
$\mathbf{C}^{\prime}$, shown in Fig. 8, which has two changes from Experiment
$\mathbf{C}$. First, Charlie is not given the trapdoor $t$ at step 1. Also, at
step 5, rather than attempt to compute the output bit $d$ directly, Charlie
performs sampling to estimate the response $d$ that will maximize Charlie and
David’s winning probability. The winning probability in Experiment
$\mathbf{C}^{\prime}$ can be at most negligibly lower (specifically, no more
than $\exp(-\Omega(\lambda^{1/2}))$ lower) than that where Charlie is able to
optimally guess the output of SecondResponse, and thus it is at most
negligible lower than the winning probability in Experiment $\mathbf{C}$.
Therefore, the winning probability in Experiment $\mathbf{C}^{\prime}$ is also
non-negligibly higher than $\frac{3}{4}$.

Experiment $\mathbf{C}^{\prime}$: Participants: Referee, Charlie, David 1.
Referee chooses input bits $b,b^{\prime}\leftarrow\\{0,1\\}$. She computes
$(pk,s,t)\leftarrow\textnormal{Gen}_{J}()$ and
$ct\leftarrow\textnormal{Encrypt}_{J}(pk,b)$ and sends $(pk,ct)$ to Charlie
and David. 2. David computes
$(y,u,p)\leftarrow\textnormal{FirstResponse}(pk,ct)$ and shares $(y,u,p)$ with
Charlie. 3. Referee transmits $b$ to Charlie and transmits $b^{\prime}$ to
David. 4. David computes
$d^{\prime}\leftarrow\textnormal{SecondResponse}(b^{\prime},p)$ and transmits
$d^{\prime}$ back to the Referee. 5. Charlie samples
$b^{\prime}_{1},\ldots,b^{\prime}_{\lambda}\leftarrow\\{0,1\\}$, samples
$d^{\prime}_{k}\leftarrow\textnormal{SecondResponse}(b^{\prime}_{k},p)$ for
each $k\in\\{1,2,\ldots,\lambda\\}$, and computes
$d\coloneqq\textnormal{MAJ}\left\\{d^{\prime}_{k}\oplus(b\wedge
b^{\prime}_{k})\mid k\in\\{1,2,\ldots,\lambda\\}\right\\}.$ (44) Charlie
transmits $d$ to the referee. 6. If $d\oplus d^{\prime}=b\wedge b^{\prime}$,
then Charlie and David win; if not, they lose.

Figure 8: Experiment $\mathbf{C}^{\prime}$ is the same as Experiment
$\mathbf{C}$, except for steps 1 and 5.

Lastly, let Experiment $\mathbf{C}^{\prime\prime}$ denote a modified version
of the Experiment $\mathbf{C}^{\prime}$ in which, at step 1, the Referee
generates $ct$ via the procedure $ct\leftarrow\textnormal{Encrypt}_{J}(pk,0)$
instead of $ct\leftarrow\textnormal{Encrypt}_{J}(pk,b)$. In Experiment
$\mathbf{C}^{\prime\prime}$, Charlie and David are playing the original
version of the CHSH game, in which both must compute their own outputs without
any information about the other player’s inputs. In this case, we know that
Charlie and David cannot win with probability more than $\frac{3}{4}$.
Therefore, the winning probabilities in Protocol $\mathbf{C}^{\prime}$ and
Protocol $\mathbf{C}^{\prime\prime}$ are non-negligibly different. But this is
a contradiction because it provides an efficient way to distinguish the
probability distributions

$[(b,ct,pk)\mid(pk,s,t)\leftarrow\textnormal{Gen}_{J}(),b\leftarrow\\{0,1\\},ct\leftarrow\textnormal{Encrypt}_{J}(pk,b)]$
(45)

and

$[(b,ct,pk)\mid(pk,s,t)\leftarrow\textnormal{Gen}_{J}(),b\leftarrow\\{0,1\\},ct\leftarrow\textnormal{Encrypt}_{J}(pk,0)]$
(46)

which violates Proposition 3.5. ∎

###  5.3 Parameter Choices

Let $c,\epsilon$ be constant positive real numbers, and let the functions
$q=q(\lambda)$ and $\sigma=\sigma(\lambda)$ be such that $\sigma$ is equal to
$n^{c}$ and $q$ is an odd prime number between $n^{2+\epsilon}\sigma$ and
$2n^{2+\epsilon}\sigma$. (See Fig. 1 for the definitions of the other
parameters.) Then,

$q=\Theta(n^{2+\epsilon+c}),\quad Q=\Theta(\log n),\quad m=\Theta(n\log
n),\quad\tau=\Theta(n^{1+c+\epsilon}/(\log n)^{2}).$

The lower bound (26) from the previous completeness theorem for Protocol
$\mathbf{Q}$ then satisfies

$\displaystyle\cos^{2}\left(\frac{\pi}{8}\right)-\frac{5m\sigma^{2}}{q^{2}}-\frac{m\sigma}{2\tau}$
$\displaystyle\geq$
$\displaystyle\cos^{2}\left(\frac{\pi}{8}\right)-O\left(\frac{(n\log
n)(n^{2c})}{n^{4+2c+2\epsilon}}\right)-O\left(\frac{(n\log
n)(n^{c})}{n^{1+c+\epsilon}(\log n)^{-2}}\right)$ $\displaystyle=$
$\displaystyle\cos^{2}\left(\frac{\pi}{8}\right)-O\left(\frac{\log
n}{n^{3+2\epsilon}}\right)-O\left(\frac{(\log n)^{3}}{n^{\epsilon}}\right),$

which tends to $\cos^{2}(\pi/8)$ as $n$ tends to infinity. Meanwhile, assuming
that $\textnormal{LWE}_{n,q,G(\sigma)}$ is hard (noting that $G(\sigma,\tau)$
is negligibly different from $G(\sigma)$ with these parameters), the upper
bound in inequality (42) applies and tends to $\frac{3}{4}$ as $n$ tends to
infinity. Therefore, a constant gap is achieved between the best quantum
success probability and our upper bound on the classical success probability.

##  6 Blind Single-Qubit State Preparation

This section constructs Protocol P in Fig. 9 which allows a classical client
to instruct a quantum server to prepare a single-qubit state
$\frac{1}{\sqrt{2}}Z^{b}(\ket{0}+e^{i\,2\pi\alpha/q}\ket{1})$, where
$\alpha\in\mathbb{Z}_{q}$ and $b\in\\{0,1\\}$. Here, $\alpha$ is chosen by the
client but kept hidden from the server while $b$ is a random bit that depends
on the server’s measurement outcomes. The client can compute $b$ after
receiving the server’s response.

To prepare the desired state in a secure manner, a classical client, Alice,
interacts with the quantum server, Bob, in the following way. First, Alice
sends an encoding of the (partial) classical description of the quantum state
to Bob. As in Section 5, we use ideas from the LWE-based public key encryption
scheme introduced by Regev [Reg09] to design an encoding. Upon receiving the
public key and the encoded message, Bob performs a quantum circuit and a
series of measurements on the resulting state to steer the final qubit as
described in Section 4. Bob rotates the last qubit, according to the
information sent by Alice, to prepare the desired state up to a Pauli-$Z$ pad.
The Pauli-$Z$ padding is partially determined by the measurement outcomes on
Bob’s end. Finally, Bob sends the measurement outcomes to Alice and she
computes the full classical description of the prepared state. Namely, Bob’s
message allows Alice to learn $b$.

Throughout this section, we assume $\tau\geq 2m\sigma$, which is required to
bound the completeness error of Protocol P. In terms of the parameters
$n,q,\sigma$, this means we require $q/\sigma\geq 8n^{2}(2\lceil\log
q\rceil+1)^{2}\lceil\log q\rceil$ (see Fig. 1), which can be satisfied for,
e.g., $q=\Omega(n^{3})$ and $\sigma=O(1)$.

Protocol P: Input: Alice: $\alpha\in\mathbb{Z}_{q}$. Output: Alice: classical
description of $\ket{\alpha,b}$ (Eq. 49). Bob: $\ket{\beta}$ (Eq. 48). 1.
Alice samples $(A,t)\leftarrow\textnormal{GenTrap}()$,
$s\leftarrow\mathbb{Z}_{q}^{n},e\leftarrow G(\sigma,\tau)^{m}$, and
$f\leftarrow\\{0,1\\}^{m}$. Then Alice broadcasts $(A,v)\coloneqq(A,As+e)$ and
$(a,w)\coloneqq(f^{\top}A,f^{\top}v-\alpha)$ to Bob. 2. Bob prepares the state
$\displaystyle\ket{\phi}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}\sqrt{q^{n}(2\tau+1)^{m}}}\sum_{\begin{subarray}{c}x\in\mathbb{Z}_{q}^{n}\end{subarray}}\hskip
7.22743pt\sum_{c\in\\{0,1\\}}\hskip
7.22743pt\sum_{\begin{subarray}{c}g\in\mathbb{Z}_{q}^{m}\\\
\left\|g\right\|_{\infty}\leq\tau\end{subarray}}\ket{x}\ket{c}\left|Ax-
cv+g\right>,$ (47) Bob measures the third register of $\ket{\phi}$ to obtain a
state of the form $\ket{\psi}\ket{y}$. Note that $\ket{\psi}$ is an
$(nQ+1)$-qubit state. Bob computes $r_{(i-1)Q+j}\coloneqq 2^{j}\pi a_{i}/q$
for all $i\in[n]$, $j\in[Q]$, and $r\coloneqq 2\pi w/q$. For each $i\in[nQ]$,
Bob measures the $i$th qubit of the state $\ket{\psi}$ in the eigenbasis of
$(\cos r_{i})X+(\sin r_{i})Y$ and obtains outcome $(-1)^{u_{i}}$. Let
$\ket{\psi^{\prime}}$ denote the state of the last (unmeasured) qubit of
$\ket{\psi}$. Bob prepares $\ket{\beta}\coloneqq\begin{bmatrix}1&0\\\
0&e^{-ir}\end{bmatrix}\ket{\psi^{\prime}}.$ (48) Bob broadcasts the vector
$y\in\mathbb{Z}_{q}^{m}$ and the bit string $u\in\\{0,1\\}^{nQ}$ to Alice. 3.
Alice computes whether $y$ belongs to the set $\\{Ax+g\mid
x\in\mathbb{Z}_{q}^{n},g\in\mathbb{Z}_{q}^{m},\norm{g}_{\infty}\leq\tau\\}\cap\\{Ax-v+g\mid
x\in\mathbb{Z}_{q}^{n},g\in\mathbb{Z}_{q}^{m},\norm{g}_{\infty}\leq\tau\\}.$
If not, Alice aborts. Otherwise, Alice computes
$x_{0}\coloneqq\textnormal{Invert}(A,y,t)\in\mathbb{Z}_{q}^{n}$,
$x_{1}\coloneqq x_{0}+s\in\mathbb{Z}_{q}^{n}$,
$z\coloneqq[x_{0}]\oplus[x_{1}]\in\\{0,1\\}^{nQ}$, and $b\coloneqq z\cdot
u\in\\{0,1\\}$. Finally, Alice computes the classical description of the
single-qubit state $\ket{\alpha,b}\coloneqq
Z^{b}\,\frac{1}{\sqrt{2}}(\ket{0}+e^{i\,2\pi\alpha/q}\ket{1}).$ (49)

Figure 9: The $2$-message blind remote state preparation protocol, including
the behavior of the client (Alice) and an honest server (Bob).

###  6.1 Completeness

The purpose of this subsection is to prove Theorem 6.2 which shows that the
state $\ket{\beta}$ produced by Protocol P in Fig. 9 is close to the state
$\ket{\alpha,b}$, whose classical description is held by Alice. We first prove
a technical lemma.

######  Lemma 6.1.

If Alice and Bob follow the process in Fig. 9, then

$\operatorname{\mathrm{E}}[\norm{e}_{1}\mid\textup{no abort}]\leq 2m\sigma,$
(50)

where the expectation is over the distribution on $(A,t,s,e,f,y)$ defined by
Fig. 9.

###### Proof.

Since $e\leftarrow G(\sigma,\tau)^{m}$, by Lemma A.2, we have that
$\operatorname{\mathrm{E}}[\norm{e}_{1}]=\operatorname{\mathrm{E}}[\sum_{i=1}^{m}\absolutevalue{e_{i}}]\leq
m\sigma$. But,

$\displaystyle\operatorname{\mathrm{E}}[\norm{e}_{1}]$
$\displaystyle=\operatorname{\mathrm{E}}[\norm{e}_{1}\mid\text{abort}]\operatorname{\mathrm{Pr}}[\textup{abort}]+\operatorname{\mathrm{E}}[\norm{e}_{1}\mid\text{no
abort}]\operatorname{\mathrm{Pr}}[\textup{no abort}]$ (51)
$\displaystyle\geq\operatorname{\mathrm{E}}[\norm{e}_{1}\mid\text{no
abort}]\operatorname{\mathrm{Pr}}[\textup{no abort}]$
$\displaystyle\geq\Bigl{(}1-\frac{m\sigma}{2\tau}\Bigr{)}\operatorname{\mathrm{E}}[\norm{e}_{1}\mid\text{no
abort}],$

where the last inequality uses inequality (30) from Section 5.

Therefore, as $\tau\geq 2m\sigma$, we obtain
$\operatorname{\mathrm{E}}[\norm{e}_{1}\mid\text{no abort}]\leq
m\sigma(1-\frac{1}{4})^{-1}\leq 2m\sigma$, as required. ∎

######  Theorem 6.2.

If Alice and Bob follow the process given in Fig. 9, then the expected trace
distance between $\ket{\alpha,b}$ and $\ket{\beta}$, conditioned on Alice not
aborting, satisfies

$\operatorname{\mathrm{E}}[\norm{\outerproduct{\alpha,b}{\alpha,b}-\outerproduct{\beta}{\beta}}_{1}\mid\textup{no
abort}]\leq\frac{4\pi m\sigma}{q},$ (52)

where the expectation is over the distribution on $(A,t,s,e,f,y)$ defined by
Fig. 9.

###### Proof.

Throughout this proof, we use the notation defined in Fig. 9. In step 3, by
using arguments similar to those in our proof of Theorem 5.1, we see that

$\ket{\psi}=\frac{1}{\sqrt{2}}\bigl{(}\ket{x_{1}}\ket{1}+\ket{x_{0}}\ket{0}\bigr{)},$
(53)

where $x_{0},x_{1}\in\mathbb{Z}_{q}^{n}$ and $x_{1}=x_{0}+s$, when Alice does
not abort.

Then, using Proposition 4.2, we see that
$\ket{\psi^{\prime}}=\frac{1}{\sqrt{2}}\bigl{(}\ket{0}+e^{i\theta}\ket{1}\bigr{)}$,
where

$\displaystyle\theta\coloneqq$ $\displaystyle\frac{2\pi
a\cdot(x_{0}-x_{1})}{q}+\pi([x_{0}]-[x_{1}])u=-\frac{2\pi a\cdot s}{q}+\pi
b\mod 2\pi.$ (54)

Then, since $r\coloneqq 2\pi w/q=2\pi(a\cdot s+f^{\top}e+\alpha)/q$, we deduce

$\displaystyle\ket{\beta}\coloneqq\begin{bmatrix}1&0\\\
0&e^{ir}\end{bmatrix}\ket{\psi^{\prime}}=Z^{b}\frac{1}{\sqrt{2}}(\ket{0}+e^{i\phi}\ket{1}),$
(55)

where $\phi\coloneqq\frac{2\pi f^{\top}e}{q}+\frac{2\pi\alpha}{q}$.

Therefore, the trace distance between $\ket{\alpha,b}$ and $\ket{\beta}$ is

$\norm{\outerproduct{\alpha,b}{\alpha,b}-\outerproduct{\beta}{\beta}}_{1}=2(1-\absolutevalue{\innerproduct{\alpha,b}{\beta}}^{2})^{1/2}=2\absolutevalue{\sin(\frac{1}{2}\cdot\frac{2\pi
f^{\top}e}{q})}\leq\frac{2\pi\absolutevalue{f^{\top}e}}{q},$ (56)

where the last inequality uses Lemma A.3. Therefore,

$\displaystyle\operatorname{\mathrm{E}}[\norm{\outerproduct{\alpha,b}{\alpha,b}-\outerproduct{\beta}{\beta}}_{1}\mid\textup{no
abort}]$ $\displaystyle\leq$
$\displaystyle\operatorname{\mathrm{E}}\Biggl{[}\frac{2\pi\absolutevalue{f^{\top}e}}{q}\Biggm{|}\textup{no
abort}\Biggr{]}\leq\frac{2\pi}{q}\operatorname{\mathrm{E}}\bigl{[}\norm{e}_{1}\bigm{|}\textup{no
abort}\bigr{]}\leq\frac{4\pi m\sigma}{q},$

where the last inequality uses Lemma 6.1, as desired. ∎

###  6.2 Blindness

The purpose of this subsection is to prove Theorem 6.3, which shows that a
non-uniform quantum polynomial-time adversary can compute the value of
$\alpha$ in Protocol P in Fig. 9 with at most negligible advantage over random
guessing. In other words, such an adversary is blind to the value of $\alpha$.
Intuitively, this is because the value $(a,w)=(f^{\top}A,f^{\top}v+\alpha)$
sent by Alice in her first message can be seen as an encryption of
$\alpha\in\mathbb{Z}_{q}$ under the public key $(A,v)$.

To state Theorem 6.3, we define the following distributions. For
$x\in\mathbb{Z}_{q}$, we define $\mathcal{D}_{x}$ to be the distribution on
$\mathbb{Z}_{q}^{m\times
n}\times\mathbb{Z}_{q}^{m}\times\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}$ such
that an element $(A,v,a,w)$ is sampled as follows:

  1. 1.

$(A,t)\leftarrow\textnormal{GenTrap}()$,

  2. 2.

$v\coloneqq As+e$, where $s\leftarrow\mathbb{Z}_{q}^{n}$ and $e\leftarrow
G(\sigma,\tau)^{m}$,

  3. 3.

$a\coloneqq f^{\top}A$, where $f\leftarrow\\{0,1\\}^{m}$, and

  4. 4.

$w\coloneqq f^{\top}v+x$.

We define $\tilde{\mathcal{D}}_{x}$ to be the same as $\mathcal{D}_{x}$ except
with the first step replaced by $A\leftarrow\mathbb{Z}_{q}^{m\times n}$. We
define $\mathcal{D}$ to be the distribution on $\mathbb{Z}_{q}^{m\times
n}\times\mathbb{Z}_{q}^{m}\times\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}$ such
that an element $(A,v,a,w)$ is sampled as follows:

$A\leftarrow\mathbb{Z}_{q}^{m\times n},\quad
v\leftarrow\mathbb{Z}_{q}^{n},\quad
a\leftarrow\mathbb{Z}_{q}^{n},\quad\text{and}\quad w\leftarrow\mathbb{Z}_{q}.$
(57)

We can now state and prove Theorem 6.3. The proof is essentially the same as
that of Proposition 3.2 but we include it for completeness.

######  Theorem 6.3 (Blindness with respect to $\alpha$).

Let $\textnormal{Guess}\colon\mathbb{Z}_{q}^{m\times
n}\times\mathbb{Z}_{q}^{m}\times\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}\to
D(\mathbb{Z}_{q})$ be a non-uniform quantum polynomial-time algorithm. Suppose
that the $\textnormal{LWE}_{n,q,G(\sigma,\tau)}$ problem is hard. Then for all
$x,y\in\mathbb{Z}_{q}$, we have

$\displaystyle|\operatorname{\mathrm{Pr}}[\textnormal{Guess}(A,v,a,w)=x\mid(A,v,a,w)\leftarrow\mathcal{D}_{y}]$
(58)
$\displaystyle\quad-\operatorname{\mathrm{Pr}}[\textnormal{Guess}(A,v,a,w)=x\mid(A,v,a,w)\leftarrow\mathcal{D}]|\leq\operatorname{\mathrm{negl}(\lambda)}.$

###### Proof.

For two real functions of $\lambda$, $a=a(\lambda)$ and $b=b(\lambda)$, we
write $a\simeq b$ to mean
$\absolutevalue{a-b}\leq\operatorname{\mathrm{negl}(\lambda)}$. Then, we have

$\displaystyle\quad\operatorname{\mathrm{Pr}}[\textnormal{Guess}(A,v,a,w)=x\mid(A,v,a,w)\leftarrow\mathcal{D}_{y}]$
$\displaystyle\simeq\operatorname{\mathrm{Pr}}[\textnormal{Guess}(A,v,a,w)=x\mid(A,v,a,w)\leftarrow\tilde{\mathcal{D}}_{y}]$
$\displaystyle\simeq\operatorname{\mathrm{Pr}}\Bigl{[}\textnormal{Guess}(A,v,a,w)=x\Bigm{|}\begin{subarray}{c}A\leftarrow\mathbb{Z}_{q}^{m\times
n},\,v\leftarrow\mathbb{Z}_{q}^{n},\,f\leftarrow\\{0,1\\}^{m},\\\
a=f^{\top}A,\,w=f^{\top}v+y\end{subarray}\Bigr{]}$
$\displaystyle\simeq\operatorname{\mathrm{Pr}}[\textnormal{Guess}(A,v,a,w)=x\mid
A\leftarrow\mathbb{Z}_{q}^{m\times
n},v\leftarrow\mathbb{Z}_{q}^{n},a\leftarrow\mathbb{Z}_{q}^{n},u\leftarrow\mathbb{Z}_{q},w=u+y]$
$\displaystyle=\operatorname{\mathrm{Pr}}[\textnormal{Guess}(A,v,a,w)=x\mid(A,v,a,w)\leftarrow\mathcal{D}],$

where the first approximation follows from Proposition 3.3 (under our
parameter settings in Fig. 1), the second approximation follows from the LWE
hardness assumption and Guess being a non-uniform quantum polynomial-time
algorithm, and the third approximation follows from the leftover hash lemma
(see Lemma 2.1 in [AP11]). The theorem follows by the triangle inequality. ∎

##  7 Future Directions

The technique of applying rotated measurements to a claw-state seems to yield
a higher degree of control in cryptographic protocols, and it invites
applications to tasks beyond proofs of quantumness and remote state
preparation. In this section, we sketch initial steps towards three additional
applications.

#### Verifiable Randomness.

Proofs of quantumness are naturally connected to protocols for verifiable
randomness. The paper [BCM+21] proved that certified randomness can be
generated by a classical verifier and a quantum prover using only classical
communication. The subsequent paper [MVV22] improved the rate of randomness
generation. In Appendix D, we take a step in the same direction by proving the
following one-shot randomness expansion result.

######  Theorem 7.1.

Suppose that the $\textnormal{LWE}_{n,q,G(\sigma,\tau)}$ problem is hard.
Suppose that Bob’s behavior in Protocol $\mathbf{Q}$ (Fig. 4) is such that
$H_{min}(d^{\prime}\mid pk,ct,b^{\prime}=0)\leq\delta$, where $\delta$ is a
positive real constant. Then,
$\Pr[\textnormal{success}]\leq\frac{3}{4}+O(\sqrt{\delta})+\operatorname{\mathrm{negl}(\lambda)}$.

The above theorem implies that if Bob achieves a score that is non-negligibly
above $\frac{3}{4}$, then his output $d^{\prime}$ on input $b^{\prime}=0$ must
contain new randomness (conditioned on all of the information received from
Alice). The proof of Theorem 7.1 is an adapted form of the rewinding argument
used to prove Theorem 5.3. This result suggests trying to incorporate more
techniques from [BCM+21] to prove a multi-shot randomness expansion result. A
possible next step would be to prove a version of Theorem 7.1 expressed in
terms of Renyi entropy rather than min-entropy. We expect that a randomness
expansion result could be proved in the same parameter range described in
subsection 5.3, thus offering a potential advantage over [BCM+21, MVV22]
(which use an exponentially large modulus).

#### Semi-Quantum Money.

Quantum money was first introduced in the seminal paper by [Wie83] and has
seen many iterations since. More recently, Radian and Sattath have proposed a
semi-quantum money scheme [RS22] where the bank is completely classical. They
show that any “strong 1-of-2 puzzle” can be made into a private semi-quantum
money scheme and give a construction of a strong 1-of-2 puzzle. Informally, a
1-of-2 puzzle is a four-tuple of algorithms $(G,O,S,V)$ that can be used in
the following interactive protocol between a classical referee R and a quantum
player P.

  1. 1.

R samples $(p,k)\leftarrow G(1^{\lambda})$ and sends “puzzle” $p$ to P but not
its “key” $k$.

  2. 2.

P samples $(o,\rho)\leftarrow O(p)$, where $o$ is a classical “obligation”
string and $\rho$ is a quantum state, and sends $o$ to R.

  3. 3.

R samples $b^{\prime}\leftarrow\\{0,1\\}$ and sends $b^{\prime}$ to P.

  4. 4.

P computes $d^{\prime}\coloneqq S(p,o,\rho,b^{\prime})$ and sends $d^{\prime}$
to R.

  5. 5.

R computes $V(p,k,o,b^{\prime},d^{\prime})\in\\{0,1\\}$ and says P succeeds if
it equals $1$.

The completeness of a 1-of-2 puzzle is P’s optimal success probability. The
soundness error of a 1-of-2 puzzle is the optimal probability of succeeding
given both $b^{\prime}=0$ _and_ $b^{\prime}=1$ under the same obligation. A
strong 1-of-2 puzzle is a 1-of-2 puzzle with completeness 1 and soundness
error 0.

A formal definition of a 1-of-2 puzzle is given in Appendix E. Under that
definition, we construct a 1-of-2 puzzle $\mathbf{Z}$ in Fig. 10 that is based
on Protocol $\mathbf{Q}$ (Fig. 4). We give the soundness and completeness
error of $\mathbf{Z}$ in Proposition 7.2 and defer its proof to Appendix E.

1-of-2 puzzle $\mathbf{Z}=(G,O,S,V)$ • $G$. On receiving security parameter
$1^{\lambda}$ as input, set parameters according to Fig. 1. Sample
$(pk=(A,v),s,t)\leftarrow\textnormal{Gen}_{J}()$ and $b\leftarrow\\{0,1\\}$.
Compute $ct=(a,w)\leftarrow\textnormal{Encrypt}_{J}(pk,b)$. Output
$(p=(pk,ct),k=(s,t,b))$. • $O$. On receiving $p=(pk=(A,v),ct=(a,w))$ as input,
follow step 2 of Fig. 5 and output $(o=(y,u_{1},\cdots,u_{nQ}),\rho=L)$. •
$S$. On receiving $(p,o,L,b^{\prime})$ as input, follow step 4 of Fig. 5 and
output $d^{\prime}$. • $V$. On receiving $p=(pk=(A,v),ct=(a,w))$, $k=(s,t,b)$,
$o=(y,u_{1},\cdots,u_{nQ})$, $b^{\prime}$, $d^{\prime}$ as input, follow step
5 of Fig. 4 to obtain $d=d(p,k,o)$. Output 1 if $d\oplus d^{\prime}=b\wedge
b^{\prime}$, otherwise output 0.

Figure 10: A 1-of-2 puzzle $\mathbf{Z}$ constructed from Protocol
$\mathbf{Q}$.

######  Proposition 7.2.

Suppose that the $\textnormal{LWE}_{n,q,G(\sigma,\tau)}$ problem is hard. Then
$\mathbf{Z}=(G,O,S,V)$ defined in Fig. 10 is a 1-of-2 puzzle with completeness
$\cos^{2}\left(\frac{\pi}{8}\right)-\frac{5m\sigma^{2}}{q^{2}}-\frac{m\sigma}{2\tau}$
and soundness error $\frac{1}{2}+\operatorname{\mathrm{negl}(\lambda)}$.

As shown in [RS22, Proof of Theorem 2], to convert our 1-of-2 puzzle
$\mathbf{Z}$ in Fig. 10 into a private semi-quantum money scheme, it suffices
to convert it into a strong 1-of-2 puzzle. [RS22, Corollary 21] gives a way of
converting a 1-of-2 puzzle with completeness _1_ and soundness error equal to
a constant less than 1 into a strong 1-of-2 puzzle via parallel repetition.
However, their method does not immediately apply in our setting because our
completeness is not 1. We conjecture instead that _threshold_ parallel
repetition can be used to convert $\mathbf{Z}$ (or any 1-of-2 puzzle with a
constant gap between its soundness error and completeness) into a strong
1-of-2 puzzle. We give a precise formulation of our conjecture in Appendix E.

The main benefit of using our 1-of-2 puzzle construction is the size of the
resulting quantum money state. In [RS22], the size of the money state in their
semi-quantum money scheme is equal to the size of the quantum state $\rho$
produced by the obligation algorithm $O$ of the strong 1-of-2 puzzle. Their
construction of a strong 1-of-2 puzzle is based on the parallel repetition of
a 1-of-2 puzzle where the $\rho$ produced by $O$ is a _claw state_. On the
other hand, in our construction, the strong 1-of-2 puzzle is a (threshold)
parallel repetition of a 1-of-2 puzzle where each $\rho$ produced by $O$ is a
_single qubit_. It is crucial to minimize the size of quantum money states
since they need to be stored and protected against decoherence for long
periods of time before transactions.

#### Hamiltonian simulation with encryption.

While the results in this paper have focused on the preparation of single
qubits, they invite extensions to other types of quantum operations. We
briefly sketch an approach that would enable a limited class of unitary
operations on quantum registers of arbitrary size.555We thank Honghao Fu for
helping us with the details in this subsection.

Suppose that $w$ is a register, and let $W=\mathbb{C}^{w}$. Suppose that $P$
is a Hermitian projection operator on $W$ such that there exists a
polynomially sized unitary quantum circuit $U\colon W\to\mathbb{C}^{2}\otimes
W$ which maps $v\mapsto\left|0\right>\otimes v$ for all $v$ in the null space
of $P$, and maps $v\mapsto\left|1\right>\otimes v$ for all $v$ in the support
of $P$.

Suppose that Bob possesses register $w$ in state $\ell\in W$, and Alice wishes
to have Bob apply the operation $e^{itP}$ to $w$ for some real value $t$
($0\leq t<2\pi$), without revealing the value of $t$ to Bob. Alice chooses
$\alpha\in\mathbb{Z}_{q}$ so that $\alpha/q\approx t$ and executes the first
step of Protocol $\mathbf{P}$ (Fig. 9). Bob applies the quantum circuit $U$ to
obtain a joint state
$\ell^{\prime}=\left|0\right>\otimes\ell_{0}+\left|1\right>\otimes\ell_{1}$ of
a pair of registers $(\zeta,w)$, where $\zeta$ is a qubit register and
$P\ell_{0}=0$, $P\ell_{1}=\ell_{1}$. Then, Bob constructs the following state,
which is the same as state (47) in Protocol $\mathbf{P}$ except for the
addition of a fourth register ($w$):

$\ket{\phi}\coloneqq\frac{1}{\sqrt{2}\sqrt{q^{n}(2\tau+1)^{m}}}\sum_{\begin{subarray}{c}x\in\mathbb{Z}_{q}^{n}\end{subarray}}\hskip
7.22743pt\sum_{c\in\\{0,1\\}}\hskip
7.22743pt\sum_{\begin{subarray}{c}g\in\mathbb{Z}_{q}^{m}\\\
\|g\|_{\infty}\leq\tau\end{subarray}}\ket{x}\ket{c}\ket{Ax-
cv+g}\ket{\ell_{c}}.$

Alice and Bob then follow the remaining steps of Protocol $\mathbf{P}$, and
Bob approximately obtains either the state

$\frac{1}{\sqrt{2}}\bigl{(}\ket{0}\ket{\ell_{0}}+e^{i\,t}\ket{1}\ket{\ell_{1}}\bigr{)}\quad\text{or}\quad\frac{1}{\sqrt{2}}\bigl{(}\ket{0}\ket{\ell_{0}}-e^{i\,t}\ket{1}\ket{\ell_{1}}\bigr{)}.$
(59)

Lastly, Bob applies the reverse quantum circuit $U^{-1}$ to approximately
obtain either $e^{itP}\ell$ or $e^{i(t+\pi)P}\ell$.

At this point, Bob has successfully carried out the unitary operator $e^{itP}$
(modulo a possible reflection $(\mathbb{I}-P)/2$) without knowing the value of
$t$. This approach is easily generalizable with $P$ replaced by any Hermitian
operator $H$ that has only two eigenvalues. A natural next step would be to
explore whether a similar procedure could be carried out for arbitrary
Hermitian operators $H$.

## Acknowledgements

We thank Gorjan Alagic, Alexandru Cojocaru, and Yi-Kai Liu for useful
discussions and comments on an earlier version of this work. Y.A. acknowledges
support from the Crown Prince International Scholarship Program and the
Arabian Gulf University. A.M acknowledges support from the U.S. Army Research
Office under Grant Number W911NF-20-1-0015 and AFOSR MURI project “Scalable
Certification of Quantum Computing Devices and Networks”. D.W. acknowledges
support from the Army Research Office (grant W911NF-20-1-0015); the Department
of Energy, Office of Science, Office of Advanced Scientific Computing
Research, Accelerated Research in Quantum Computing program; and the National
Science Foundation (grant DMR-1747426). This paper is partly a contribution of
the National Institute of Standards and Technology.

## References

  * [AGKZ20] Ryan Amos, Marios Georgiou, Aggelos Kiayias, and Mark Zhandry.  One-shot signatures and applications to hybrid quantum/classical authentication.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 255–268, 2020.  iacr:2020/107.  doi:10.1145/3357713.3384304.
  * [AP11] Joël Alwen and Chris Peikert.  Generating shorter bases for hard random lattices.  Theory of Computing Systems, 48(3):535--553, 2011.  iacr:2008/521.  doi:10.1007/s00224-010-9278-3.
  * [BB14] Charles H. Bennett and Gilles Brassard.  Quantum cryptography: Public key distribution and coin tossing.  Theoretical Computer Science, 560:7--11, 2014.  arXiv:2003.06557.  doi:10.1016/j.tcs.2014.05.025.
  * [BCC+20] Christian Badertscher, Alexandru Cojocaru, Léo Colisson, Elham Kashefi, Dominik Leichtle, Atul Mantri, and Petros Wallden.  Security limitations of classical-client delegated quantum computing.  In International Conference on the Theory and Application of Cryptology and Information Security, pages 667--696, 2020.  arXiv:2007.01668.  doi:10.1007/978-3-030-64834-3_23.
  * [BCM+21] Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, and Thomas Vidick.  A cryptographic test of quantumness and certifiable randomness from a single quantum device.  J. ACM, 68(5), August 2021.  arXiv:1804.00640.  doi:10.1145/3441309.
  * [BFK09] Anne Broadbent, Joseph Fitzsimons, and Elham Kashefi.  Universal blind quantum computation.  In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS), pages 517--526, 2009.  arXiv:0807.4154.  doi:10.1109/FOCS.2009.36.
  * [BKVV20] Zvika Brakerski, Venkata Koppula, Umesh Vazirani, and Thomas Vidick.  Simpler proofs of quantumness.  In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), pages 8:1--8:14, 2020.  arXiv:2005.04826.  doi:10.4230/LIPIcs.TQC.2020.8.
  * [Bra18] Zvika Brakerski.  Quantum FHE (almost) as secure as classical.  In Annual International Cryptology Conference, pages 67--95, 2018\.  iacr:2018/338.  doi:10.1007/978-3-319-96878-0_3.
  * [CCKM20] Michele Ciampi, Alexandru Cojocaru, Elham Kashefi, and Atul Mantri.  Secure two-party quantum computation over classical channels, 2020.  arXiv:2010.07925.
  * [CCKW19] Alexandru Cojocaru, Léo Colisson, Elham Kashefi, and Petros Wallden.  QFactory: classically-instructed remote secret qubits preparation.  In International Conference on the Theory and Application of Cryptology and Information Security, pages 615--645, 2019.  arXiv:1904.06303.  doi:10.1007/978-3-030-34578-5_22.
  * [CCKW21] Alexandru Cojocaru, Léo Colisson, Elham Kashefi, and Petros Wallden.  On the possibility of classical client blind quantum computing.  Cryptography, 5(1):3, 2021.  arXiv:1802.08759.  doi:10.3390/cryptography5010003.
  * [CHSH69] John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt.  Proposed experiment to test local hidden-variable theories.  Physical Review Letters, 23(15):880, 1969.  doi:10.1103/PhysRevLett.23.880.
  * [CKS20] Clément L Canonne, Gautam Kamath, and Thomas Steinke.  The Discrete Gaussian for Differential Privacy.  In Advances in Neural Information Processing Systems, volume 33, pages 15676--15688, 2020.  arXiv:2004.00010.
  * [DKL12] Vedran Dunjko, Elham Kashefi, and Anthony Leverrier.  Blind quantum computing with weak coherent pulses.  Physical Review Letters, 108(20):200502, 2012.  arXiv:1108.5571.  doi:10.1103/PhysRevLett.108.200502.
  * [DLF+16] S. Debnath, N. M. Linke, C. Figgatt, K. A. Landsman, K. Wright, and C. Monroe.  Demonstration of a small programmable quantum computer with atomic qubits.  Nature, 536(7614):63--66, 2016.  arXiv:1603.04512.  doi:10.1038/nature18648.
  * [FBS+14] Kent A. G. Fisher, Anne Broadbent, L. K. Shalm, Z. Yan, Jonathan Lavoie, Robert Prevedel, Thomas Jennewein, and Kevin J. Resch.  Quantum computing on encrypted data.  Nature Communications, 5(1):1--7, 2014.  arXiv:1309.2586.  doi:10.1038/ncomms4074.
  * [FWZ22] Honghao Fu, Daochen Wang, and Qi Zhao.  Computational self-testing of multi-qubit states and measurements, 2022\.  arXiv:2201.13430.
  * [GHZ89] Daniel M. Greenberger, Michael A. Horne, and Anton Zeilinger.  Going Beyond Bell’s Theorem, pages 69--72.  Springer Netherlands, Dordrecht, 1989.  arXiv:0712.0921.  doi:10.1007/978-94-017-0849-4_10.
  * [GMP22] Alexandru Gheorghiu, Tony Metger, and Alexander Poremba.  Quantum cryptography with classical communication: parallel remote state preparation for copy-protection, verification, and more, 2022.  arXiv:2201.13445.
  * [GMR84] S. Goldwasser, S. Micali, and R. L. Rivest.  A ‘‘paradoxical’’ solution to the signature problem.  In Proceedings of the 25th IEEE Symposium on Foundations of Computer Science (FOCS), pages 441--448, 1984.  doi:10.1109/SFCS.1984.715946.
  * [GV19] Alexandru Gheorghiu and Thomas Vidick.  Computationally-secure and composable remote state preparation.  In Proceedings of the 60th IEEE Symposium on Foundations of Computer Science (FOCS), pages 1024--1033, 2019.  arXiv:1904.06320.  doi:10.1109/FOCS.2019.00066.
  * [HLG21] Shuichi Hirahara and François Le Gall.  Test of quantumness with small-depth quantum circuits.  In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), 2021.  arXiv:2105.05500.  doi:10.4230/LIPIcs.MFCS.2021.59.
  * [IJK09] Russell Impagliazzo, Ragesh Jaiswal, and Valentine Kabanets.  Chernoff-type direct product theorems.  Journal of Cryptology, 22(1):75--92, 2009.  doi:10.1007/s00145-008-9029-7.
  * [KLVY22] Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang.  Quantum advantage from any non-local game, 2022.  arXiv:2203.15877v1.
  * [KMCVY22] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani, and Norman Y. Yao.  Classically verifiable quantum advantage from a computational Bell test.  Nature Physics, 18(8):918--924, 2022.  arXiv:2104.00687.  doi:10.1038/s41567-022-01643-7.
  * [LG22] Zhenning Liu and Alexandru Gheorghiu.  Depth-efficient proofs of quantumness.  Quantum, 6:807, 2022.  arXiv:2107.02163.  doi:10.22331/q-2022-09-19-807.
  * [Mah18] Urmila Mahadev.  Classical homomorphic encryption for quantum circuits.  In Proceedings of the 59th IEEE Symposium on Foundations of Computer Science (FOCS), pages 332--338, 2018.  arXiv:1708.02130.  doi:10.1109/FOCS.2018.00039.
  * [Mas17] Dmitri Maslov.  Basic circuit compilation techniques for an ion-trap quantum machine.  New Journal of Physics, 19(2):023035, 2017.  arXiv:1603.07678.  doi:10.1088/1367-2630/aa5e47.
  * [MP12] Daniele Micciancio and Chris Peikert.  Trapdoors for lattices: Simpler, tighter, faster, smaller.  In Advances in Cryptology -- EUROCRYPT 2012, pages 700--718, 2012\.  iacr:2011/501.  doi:10.1007/978-3-642-29011-4_41.
  * [MTH+22] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa, and Seiichiro Tani.  Computational self-testing for entangled magic states.  Physical Review A, 106:L010601, 2022.  arXiv:2111.02700.  doi:10.1103/PhysRevA.106.L010601.
  * [MV21] Tony Metger and Thomas Vidick.  Self-testing of a single quantum device under computational assumptions.  Quantum, 5:544, 2021.  arXiv:2001.09161.  doi:10.22331/q-2021-09-16-544.
  * [MVV22] Urmila Mahadev, Umesh Vazirani, and Thomas Vidick.  Efficient certifiable randomness from a single quantum device, 2022.  arXiv:2204.11353.
  * [MY22] Tomoyuki Morimae and Takashi Yamakawa.  Proofs of quantumness from trapdoor permutations, 2022.  arXiv:2208.12390.
  * [Nat19] National Academies of Sciences, Engineering, and Medicine.  Quantum Computing: Progress and Prospects.  The National Academies Press, 2019.  doi:10.17226/25196.
  * [NC10] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information: 10th Anniversary Edition.  Cambridge University Press, 2010.
  * [Pei10] Chris Peikert.  An efficient and parallel gaussian sampler for lattices.  In Advances in Cryptology -- CRYPTO 2010, pages 80--97, 2010.  iacr:2010/088.  doi:10.1007/978-3-642-14623-7_5.
  * [Reg09] Oded Regev.  On lattices, learning with errors, random linear codes, and cryptography.  J. ACM, 56(6), 2009.  doi:10.1145/1568318.1568324.
  * [RS22] Roy Radian and Or Sattath.  Semi-quantum money.  Journal of Cryptology, 35(2), 2022.  arXiv:1908.08889.  doi:10.1007/s00145-021-09418-8.
  * [Sho94] Peter W. Shor.  Algorithms for quantum computation: discrete logarithms and factoring.  In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science (FOCS), pages 124--134, 1994.  arXiv:quant-ph/9508027.  doi:10.1109/SFCS.1994.365700.
  * [Wie83] Stephen Wiesner.  Conjugate coding.  SIGACT News, 15(1):78--88, 1983.
  * [Win99] A. Winter.  Coding theorem and strong converse for quantum channels.  IEEE Transactions on Information Theory, 45(7):2481--2485, 1999\.  doi:10.1109/18.796385.
  * [YZ22] Takashi Yamakawa and Mark Zhandry.  Verifiable quantum advantage without structure, 2022.  arXiv:2204.02063.
  * [Zha22] Jiayu Zhang.  Classical verification of quantum computations in linear time, 2022.  arXiv:2202.13997.
  * [ZKML+21] Daiwei Zhu, Gregory D. Kahanamoku-Meyer, Laura Lewis, Crystal Noel, Or Katz, Bahaa Harraz, Qingfeng Wang, Andrew Risinger, Lei Feng, Debopriyo Biswas, Laird Egan, Alexandru Gheorghiu, Yunseong Nam, Thomas Vidick, Umesh Vazirani, Norman Y. Yao, Marko Cetina, and Christopher Monroe.  Interactive protocols for classically-verifiable quantum advantage, 2021\.  arXiv:2112.05156.

##  Appendix A Mathematical Lemmas

######  Lemma A.1.

For any $\sigma\in\mathbb{N},\tau>0$,

$\operatorname{\mathrm{E}}[X^{2}\mid X\leftarrow
G(\sigma,\tau)]\leq\sigma^{2}.$ (60)

###### Proof.

For notational convenience, for $x\in\mathbb{Z}$, we write

$\operatorname{\mathrm{Pr}}_{1}[x]\coloneqq\Pr[x\leftarrow
G(\sigma)]\quad\text{and}\quad\operatorname{\mathrm{Pr}}_{2}[x]\coloneqq\Pr[x\leftarrow
G(\sigma,\tau)].$ (61)

We also write

$\quad
Z\coloneqq\sum_{x\in\mathbb{Z}:\absolutevalue{x}\leq\tau}\operatorname{\mathrm{Pr}}_{1}[x]\quad\text{and}\quad
L\coloneqq\operatorname{\mathrm{E}}[X^{2}\mid X\leftarrow G(\sigma,\tau)].$
(62)

Note that $L$ is the quantity we need to upper bound and

$L=\sum_{x\in\mathbb{Z}:\absolutevalue{x}\leq\tau}x^{2}\operatorname{\mathrm{Pr}}_{2}[x]=\sum_{x\in\mathbb{Z}:\absolutevalue{x}\leq\tau}x^{2}\frac{\operatorname{\mathrm{Pr}}_{1}[x]}{Z}\leq\tau^{2}.$
(63)

We upper bound $L$ as follows.

$\displaystyle L$ $\displaystyle=L(1-Z)+LZ$
$\displaystyle\leq\tau^{2}(1-Z)+\sum_{x\in\mathbb{Z}:\absolutevalue{x}\leq\tau}x^{2}\operatorname{\mathrm{Pr}}_{1}[x]$
(by Eq. 63)
$\displaystyle=\tau^{2}\sum_{x\in\mathbb{Z}:\absolutevalue{x}>\tau}\operatorname{\mathrm{Pr}}_{1}[x]+\sum_{x\in\mathbb{Z}:\absolutevalue{x}\leq\tau}x^{2}\operatorname{\mathrm{Pr}}_{1}[x]$
$\displaystyle\leq\sum_{x\in\mathbb{Z}:\absolutevalue{x}>\tau}x^{2}\operatorname{\mathrm{Pr}}_{1}[x]+\sum_{x\in\mathbb{Z}:\absolutevalue{x}\leq\tau}x^{2}\operatorname{\mathrm{Pr}}_{1}[x]$
$\displaystyle=\sum_{x\in\mathbb{Z}}x^{2}\operatorname{\mathrm{Pr}}_{1}[x]$
$\displaystyle=\operatorname{\mathrm{E}}[X^{2}\mid X\leftarrow G(\sigma)],$

but, by Lemma 3.1, we have

$\operatorname{\mathrm{E}}[X^{2}\mid X\leftarrow
G(\sigma)]=\operatorname{\mathrm{Var}}[X\mid X\leftarrow
G(\sigma)]\leq\sigma^{2}.$ (64)

Therefore, $L\leq\sigma^{2}$, as required. ∎

######  Lemma A.2.

For any $\sigma\in\mathbb{N},\tau>0$,

$\operatorname{\mathrm{E}}[\,\left|X\right|\mid X\leftarrow
G(\sigma,\tau)]\leq\sigma.$ (65)

###### Proof.

This lemma follows immediately from Lemma A.1. We have

$\operatorname{\mathrm{E}}[\,\left|X\right|\mid X\leftarrow
G(\sigma,\tau)]\leq\sqrt{\operatorname{\mathrm{E}}[\absolutevalue{X}^{2}\mid
X\leftarrow G(\sigma,\tau)]}\leq\sigma,$ (66)

as desired. ∎

######  Lemma A.3.

The following inequality holds for any real value t: $\left|\sin
t\right|\leq\left|t\right|$.

###### Proof.

We have
$\sin^{2}t=\int_{0}^{t}\int_{0}^{s}2\cos(2r)\mathop{}\\!\mathrm{d}r\mathop{}\\!\mathrm{d}s\leq\int_{0}^{t}\int_{0}^{s}2(1)\mathop{}\\!\mathrm{d}r\mathop{}\\!\mathrm{d}s=t^{2}$.
∎

######  Lemma A.4.

The following inequality holds for any real values $t,s$:

$\sin^{2}(t+s)\leq\sin^{2}s+t\sin(2s)+t^{2}.$ (67)

###### Proof.

Let $f(x)=\sin^{2}(x+s)$. We have $f(0)=\sin^{2}s$, $f^{\prime}(0)=\sin 2s$,
and $f^{\prime\prime}(x)=2\cos(2x+2s)$. If we let

$g(x)=\sin^{2}s+x\sin 2s+x^{2},$ (68)

then $g(0)=f(0),$ $g^{\prime}(0)=f^{\prime}(0)$, and $g^{\prime\prime}(x)\geq
f^{\prime\prime}(x)$ for all $x$, which yields $g(x)\geq f(x)$ for all $x$ as
desired. ∎

######  Lemma A.5.

Suppose that $X_{1},\ldots,X_{\ell}$ are independent real-valued random
variables and that
$\operatorname{\mathrm{E}}[X_{1}]=\operatorname{\mathrm{E}}[X_{2}]=\ldots=\operatorname{\mathrm{E}}[X_{\ell-1}]=0$.
Then,

$\operatorname{\mathrm{E}}[(X_{1}+\ldots+X_{\ell})^{2}]=\operatorname{\mathrm{E}}[X_{1}^{2}]+\operatorname{\mathrm{E}}[X_{2}^{2}]+\ldots+\operatorname{\mathrm{E}}[X_{\ell}^{2}].$
(69)

###### Proof.

We have

$\operatorname{\mathrm{E}}[(X_{1}+\ldots+X_{\ell})^{2}]=\sum_{i}\operatorname{\mathrm{E}}[X_{i}^{2}]+\sum_{i\neq
j}\operatorname{\mathrm{E}}[X_{i}]\operatorname{\mathrm{E}}[X_{j}].$ (70)

All terms in the second summation are clearly zero. ∎

##  Appendix B Proof of Proposition 3.2

Let $\textnormal{Gen}^{\prime}()$ denote an algorithm that merely outputs a
uniformly random pair $pk=(A,v)$ and does not output a secret key. By the LWE
assumption,

$\operatorname{\mathrm{Pr}}[b^{\prime}=b\mid
pk\leftarrow\textnormal{Gen}_{K}(),b\leftarrow\\{0,1\\},ct\leftarrow\textnormal{Encrypt}_{K}(pk,b),b^{\prime}\leftarrow\mathcal{B}(pk,ct)]$
(71)

is negligibly different from

$\operatorname{\mathrm{Pr}}[b^{\prime}=b\mid
pk\leftarrow\textnormal{Gen}^{\prime}(),b\leftarrow\\{0,1\\},ct\leftarrow\textnormal{Encrypt}_{K}(pk,b),b^{\prime}\leftarrow\mathcal{B}(pk,ct)]$

Meanwhile, the leftover hash lemma (see Lemma 2.1 in [AP11]) implies that the
distribution of $(A,v,f^{\top}A,f^{\top}v)$, when
$f\in\\{0,1\\}^{m},A\in\mathbb{Z}_{q}^{m\times n},v\in\mathbb{Z}_{q}^{m}$ are
all sampled uniformly, is itself negligibly close to uniform. Therefore the
quantity in Eq. 71 is also negligibly close to

$\operatorname{\mathrm{Pr}}[b^{\prime}=b\mid
pk\leftarrow\textnormal{Gen}^{\prime}(),ct\leftarrow\mathbb{Z}_{q}^{n+1},b\leftarrow\\{0,1\\},b^{\prime}\leftarrow\mathcal{B}(pk,ct)].$

Since $ct$ and $pk$ are independent of $b$ in this expression, the quantity
above is obviously equal to $\frac{1}{2}$. This completes the proof.

##  Appendix C Trapdoors for LWE matrices

###### Proof of Proposition 3.3.

Our proof is essentially the same as the proof in [MP12]. The main difference
is that we use the infinity norm, rather than the Euclidean norm, to bound
error vectors. We define $\textnormal{GenTrap}()$ as follows.

Algorithm $\textnormal{GenTrap}()$:

  1. 1.

Let

$g=\left[\begin{array}[]{c}1\\\ 2\\\ 4\\\ \vdots\\\ 2^{Q-1}\end{array}\right]$
(72)

and let $G$ be the $nQ\times n$ matrix

$G=\left[\begin{array}[]{ccccc}g\\\ &g\\\ &&g\\\ &&&\ddots\\\
&&&&g\end{array}\right].$ (73)

  2. 2.

Sample a matrix $M\in\mathbb{Z}_{q}^{(Q+1)n\times n}$ with entries chosen
uniformly from $\mathbb{Z}_{q}$, and a matrix
$N\in\mathbb{Z}_{q}^{Qn\times(Q+1)n}$ with entries chosen uniformly from
$\\{0,1\\}$. Let

$A=\left[\begin{array}[]{c}G+NM\\\ \hline\cr M\end{array}\right].$ (74)

  3. 3.

Let $t=N$. Return $(A,t)$.

∎

By the leftover hash lemma (see Lemma 2.1 in [AP11]) if
$z\in\\{0,1\\}^{(Q+1)n}$ is chosen uniformly at random, then the distribution
of

$\left[\begin{array}[]{c}M\\\ \hline\cr\\\\[-10.0pt]
z^{\top}M\end{array}\right]$

is within statistical distance $2^{-n/2}$ from uniformly random. Iterating
this fact, we find that the matrix

$\left[\begin{array}[]{c}M\\\ \hline\cr NM\end{array}\right]$

is within statistical distance $nQ2^{-n/2}$ from uniformly random, and the
same applies to the matrix $A$. This proves the first claim of Proposition
3.3.

We sketch a method for the Invert algorithm (see [MP12] for more details). The
algorithm Invert receives as input the matrix $A$, a vector $v\coloneqq As+e$
where $e$ satisfies $\left\|e\right\|_{\infty}\leq 2\tau$, and the trapdoor
matrix $N$. Let $v_{1}$ denote the vector consisting of the first $Qn$ entries
of $v$, and let $v_{2}$ denote the vector consisting of the remaining entries
of $v$. We have

$v_{1}=(G+NM)s+e_{1}\quad\text{and}\quad v_{2}=Ms+e_{2},$ (75)

where $e_{1},e_{2}$ have infinity norm upper bounded by $2\tau$. Letting

$v^{\prime}\coloneqq v_{1}-Nv_{2},$ (76)

we find

$v^{\prime}=Gs+(e_{1}-Ne_{2}).$ (77)

Let $e^{\prime}\coloneqq e_{1}-Ne_{2}$. Then, $v^{\prime}=Gs+e^{\prime}$, and
$\left\|e^{\prime}\right\|_{\infty}\leq 2\tau+(Q+1)n(2\tau)<q/(2Q)$. Let

$S\coloneqq\left[\begin{array}[]{cccccc}2&-1&&&&\\\ &2&-1&&&\\\ &&\ddots&&&\\\
&&&2&-1\\\
\left[q\right]_{1}&\left[q\right]_{2}&\left[q\right]_{3}&\cdots&\left[q\right]_{Q}\end{array}\right]$
(78)

and let $Y$ be the $Q^{2}\times Q^{2}$ matrix which consists of $Q$ diagonal
blocks, each equal to $S$. Then, $YG=0$, and therefore if we compute
$w\coloneqq Yv^{\prime}$, we have

$w=Y(Gs+e^{\prime})=Ye^{\prime}.$ (79)

Since each entry of $e^{\prime}$ has absolute value less than $q/(2Q)$ and
each row of $Y$ has trace-norm less than or equal to $Q$, the equation
$Ye^{\prime}=w$ can be solved for $e^{\prime}$ simply by inverting the matrix
Y over the real numbers. Then, we compute $Gs=v^{\prime}-e^{\prime}$ and
recover $s$. If no solution exists, we assume that Invert returns the vector
$0^{n}$.

##  Appendix D Verifiable Randomness

We recall that for any classical state $\gamma$ of a pair of registers
$(\chi,\omega)$, the min-entropy of $\chi$ conditioned on $\omega$ is defined
by

$\displaystyle H_{min}(\chi\mid\omega)_{\gamma}:=-\log K,$ (80)

where $K$ denotes the optimal probability with which a (computationally
unlimited) party who possesses the register $\omega$ can guess the value of
$\chi$.

In this section, we will prove Theorem 7.1. We assume, without loss of
generality, that Bob’s behavior has the form shown in Fig. 11. We first prove
the following lemma, which can be thought of as a form of the gentle
measurement lemma (see, e.g., Lemma 9 in [Win99]).

Step 2. Bob receives input $(pk,ct)$ and computes
$(y,u,p)\leftarrow\textnormal{FirstResponse}(pk,ct),$ where
$\textnormal{FirstResponse}()$ is a non-uniform polynomially-sized quantum
circuit.
Step 4. Bob receives $b^{\prime}$ from Alice and computes $(x,r)\leftarrow
U_{b^{\prime}}(p),$ where $U_{0}$ and $U_{1}$ are unitary polynomially-sized
quantum circuits and $x$ is a qubit register. Bob measures the register $x$
and stores the result in the classical register $d^{\prime}$.

Figure 11: A model of a quantum adversary for Protocol Q in Fig. 4. The
register $p$ may be in a quantum state after Step 2. We require that the
circuits $U_{0}$ and $U_{1}$ are unitary circuits (i.e., involving no creation
of registers or measurements).

######  Lemma D.1.

Let $\zeta$ be a qubit register and let $c$ be a classical register. Let
$\rho$ be a classical-quantum state of $(c,\zeta)$, let $\rho^{\prime}$ be the
state that is obtained from $\rho$ by measuring $\zeta$ in the computational
basis, and suppose that

$\displaystyle H_{min}(\zeta\mid c)_{\rho^{\prime}}$ $\displaystyle\leq$
$\displaystyle\epsilon.$ (81)

Then,

$\displaystyle\left\|\rho-\rho^{\prime}\right\|_{1}$ $\displaystyle\leq$
$\displaystyle O(\sqrt{\epsilon}).$ (82)

###### Proof.

In the case in which $c$ is a trivial register, we can write $\rho$ in the
form

$\displaystyle\rho$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cc}\alpha&\beta\\\
\overline{\beta}&\gamma\end{array}\right]$ (85)

with $\left|\beta\right|^{2}\leq\alpha\gamma$. Since $\max\\{\alpha,\gamma\\}$
is lower bounded by $1-2^{-\epsilon}=1-O(\epsilon)$ by assumption, we have

$\displaystyle\left\|\rho-\rho^{\prime}\right\|_{1}$ $\displaystyle=$
$\displaystyle\left\|\left[\begin{array}[]{cc}0&\beta\\\
\overline{\beta}&0\end{array}\right]\right\|_{1}$ (88) $\displaystyle=$
$\displaystyle 2\left|\beta\right|$ (89) $\displaystyle\leq$
$\displaystyle\sqrt{(1-O(\epsilon))O(\epsilon)}$ (90) $\displaystyle\leq$
$\displaystyle O(\sqrt{\epsilon}).$ (91)

The general case follows from the concavity of the square root function. ∎

###### Proof of Theorem 7.1.

We consider the experiments shown in Figures 12–15. The probability that Bob
succeeds in Protocol $\mathbf{Q}$ is the average of the following four
quantities:

  * •

The probability that $d=d^{\prime}$ in Experiment $\mathbf{T}_{0}$.

  * •

The probability that $d\neq d^{\prime}$ in Experiment $\mathbf{T}_{1}$.

  * •

The probability that $d=d^{\prime}_{0}$ in Experiment $\mathbf{R}_{0}$.

  * •

The probability that $d=d^{\prime}_{0}$ in Experiment $\mathbf{R}_{1}$.

We are therefore interested in proving bounds on these four quantities.

Experiment $\mathbf{T}_{0}$: 1. Let $b:=0$. 2. Compute
$(pk,s,t)\leftarrow\textnormal{Gen}_{J}()$ and
$ct\leftarrow\textnormal{Encrypt}_{J}(pk,b)$. 3. Compute
$(y,u,p)\leftarrow\textnormal{FirstResponse}(pk,ct)$. 4. Compute
$x_{0}\coloneqq\textnormal{Invert}(A,y,t)$ and
$x_{1}\coloneqq\textnormal{Invert}(A,y+v,t)$ and $d\coloneqq
u\cdot([x_{0}]\oplus[x_{1}]).$ (92) 5. Compute $(x,r)\leftarrow U_{1}(p)$. 6.
Let $b^{\prime}:=1$. Measure the qubit $x$ in the computational basis, and
store the result in a bit register $d^{\prime}$.

Figure 12: A version of the encrypted CHSH game with specific inputs:
$b=0,b^{\prime}=1$.

Experiment $\mathbf{T}_{1}$: 1. Let $b:=1$. Steps $2-6$ are the same as in
Experiment $\mathbf{T}_{1}$.

Figure 13: A version of the encrypted CHSH game with specific inputs:
$b=1,b^{\prime}=1$.

Experiment $\mathbf{R}_{0}$: 1. Let $b:=0$. 2. Compute
$(pk,s,t)\leftarrow\textnormal{Gen}_{J}()$ and
$ct\leftarrow\textnormal{Encrypt}_{J}(pk,b)$. 3. Compute
$(y,u,p)\leftarrow\textnormal{FirstResponse}(pk,ct)$. 4. Compute
$x_{0}\coloneqq\textnormal{Invert}(A,y,t)$ and
$x_{1}\coloneqq\textnormal{Invert}(A,y+v,t)$ and $d\coloneqq
u\cdot([x_{0}]\oplus[x_{1}]).$ (93) 5. Compute $(x,r)\leftarrow U_{0}(p)$. 6.
Measure the qubit $x$ in the computational basis, and store the result in a
bit register $d^{\prime}_{0}$. 7. Compute $p\leftarrow U_{0}^{-1}(x,r)$. 8.
Compute $(x,r)\leftarrow U_{1}(p)$. 9. Measure the qubit $x$ in the
computational basis, and store the result in a bit register $d^{\prime}_{1}$.
10. Compute $b^{\prime}\leftarrow\\{0,1\\}$ and $d^{\prime}:=d^{\prime}_{b}$.

Figure 14: A rewinding experiment using the procedures from Fig. 11.

Experiment $\mathbf{R}_{1}$: 1. Let $b:=1$. Steps $2-10$ are the same as in
Experiment $\mathbf{R}_{0}$.

Figure 15: A modified version of Experiment $\mathbf{R}_{0}$. The only
difference is that $ct$ is an encryption of the bit $1$ instead of $0$.

We begin by considering Experiments $\mathbf{R}_{0}$ and $\mathbf{R}_{1}$. Let
$C_{0}$ denote the probability of the event $d^{\prime}_{0}\neq
d^{\prime}_{1}$ in Experiment $\mathbf{R}_{0}$, and let $C_{1}$ denote the
probability of the same event in Experiment $\mathbf{R}_{1}$. Note that the
quantities $C_{0}$ and $C_{1}$ must be at most negligibly different, since
otherwise one could use the procedure in Steps 3-10 of Experiment
$\mathbf{R}_{0}$ to distinguish between an encryption of $b=0$ and an
encryption of $b=1$ with non-negligible probability, thus violating
Proposition 3.5.

For Experiment $\mathbf{R}_{0}$, we have

$\textnormal{Pr}_{\mathbf{R}_{0}}[d=d^{\prime}_{0}]+\textnormal{Pr}_{\mathbf{R}_{0}}[d=d^{\prime}_{1}]\leq
2-\textnormal{Pr}_{\mathbf{R}_{0}}[d^{\prime}_{0}\neq
d^{\prime}_{1}]=2-C_{0},$ (94)

Similarly, for Experiment $\mathbf{R}_{1}$, we have

$\textnormal{Pr}_{\mathbf{R}_{1}}[d=d^{\prime}_{0}]+\textnormal{Pr}_{\mathbf{R}_{1}}[d\neq
d^{\prime}_{1}]\leq
2-\textnormal{Pr}_{\mathbf{R}_{1}}[d^{\prime}_{0}=d^{\prime}_{1}]=1+C_{1}.$
(95)

Note that in Experiment $\mathbf{R}_{0}$, Lemma D.1 implies that the state of
$(pk,ct,d,b,p)$ immediately before Step 5 is within trace distance
$O(\sqrt{\delta})$ of the state of $(pk,ct,d,b,p)$ immediately before Step 8.
Comparing Experiment $\mathbf{R}_{0}$ and Experiment $\mathbf{T_{0}}$, we find
that

$\displaystyle\left|\textnormal{Pr}_{\mathbf{R}_{0}}[d=d^{\prime}_{1}]-\textnormal{Pr}_{\mathbf{T}_{0}}[d=d^{\prime}]\right|$
$\displaystyle\leq$ $\displaystyle O(\sqrt{\delta}).$ (96)

By similar reasoning,

$\displaystyle\left|\textnormal{Pr}_{\mathbf{R}_{1}}[d\neq
d^{\prime}_{1}]-\textnormal{Pr}_{\mathbf{T}_{1}}[d\neq d^{\prime}]\right|$
$\displaystyle\leq$ $\displaystyle O(\sqrt{\delta}).$ (97)

Therefore, the probability of success in Protocol $\mathbf{Q}$ is upper
bounded as follows:

$\displaystyle\frac{1}{4}\left(\textnormal{Pr}_{\mathbf{T}_{0}}[d=d^{\prime}]+\textnormal{Pr}_{\mathbf{R}_{0}}[d=d^{\prime}_{0}]+\textnormal{Pr}_{\mathbf{R}_{1}}[d=d^{\prime}_{0}]+\textnormal{Pr}_{\mathbf{T}_{1}}[d\neq
d^{\prime}]\right)$ $\displaystyle\leq$
$\displaystyle\frac{1}{4}\left(\textnormal{Pr}_{\mathbf{R}_{0}}[d=d^{\prime}_{1}]+\textnormal{Pr}_{\mathbf{R}_{0}}[d=d^{\prime}_{0}]+\textnormal{Pr}_{\mathbf{R}_{1}}[d=d^{\prime}_{0}]+\textnormal{Pr}_{\mathbf{R}_{1}}[d\neq
d^{\prime}_{1}]+O(\sqrt{\delta})\right)$ $\displaystyle\leq$
$\displaystyle\frac{3}{4}+(C_{1}-C_{0})/2+O(\sqrt{\delta})$
$\displaystyle\leq$
$\displaystyle\frac{3}{4}+\operatorname{\mathrm{negl}(\lambda)}+O(\sqrt{\delta}),$

as desired. ∎

##  Appendix E Semi-quantum money

The formal definition of a 1-of-2 puzzle is as follows.

######  Definition E.1 (1-of-2 puzzle [RS22, Definition 12]).

A 1-of-2 puzzle is a four-tuple of efficient algorithms $(G,O,S,V)$: the
puzzle generator $G$, an obligation algorithm $O$, a 1-of-2 solver $S$, and a
verification algorithm $V$. $G$ is a classical randomized algorithm, $V$ is a
classical deterministic algorithm, and $O$ and $S$ are quantum algorithms.

  1. 1.

$G$ receives security parameter $1^{\lambda}$ as input and outputs a random
puzzle $p$ and verification key $v$: $(p,k)\leftarrow G(1^{\lambda})$.

  2. 2.

$O$ receives a puzzle $p$ as input and outputs a classical string $o$ called
the obligation string and a quantum state $\rho$: $(o,\rho)\leftarrow O(p)$.

  3. 3.

$S$ receives $p,o,\rho$ and a bit $b\in\\{0,1\\}$ as input and outputs a
classical string $a$: $a\leftarrow S(p,o,\rho,b)$.

  4. 4.

$V$ receives $p,k,o,b,a$ as input and outputs $0$ or $1$:
$V(p,k,o,b,a)\in\\{0,1\\}$.

Completeness. Let $\eta\colon\mathbb{N}\to[0,1]$. We say that a 1-of-2 puzzle
has completeness $\eta$ if there exists a negligible function
$\operatorname{\mathrm{negl}(\lambda)}$ such that

$\operatorname{\mathrm{Pr}}[V(p,k,o,b,a)=1]\geq\eta(\lambda)-\operatorname{\mathrm{negl}(\lambda)},$
(98)

where the probability is over $(p,k)\leftarrow G(1^{\lambda})$,
$(o,\rho)\leftarrow O(p)$, $b\leftarrow\\{0,1\\}$, and $a\leftarrow
S(p,o,\rho,b)$.

Soundness (hardness). Let $h\colon\mathbb{N}\to[0,1]$. We say that the 1-of-2
puzzle $Z$ has soundness error $h$ if for any
$\operatorname{\mathrm{poly}(\lambda)}$-time quantum algorithm $T$, there
exists a negligible function $\operatorname{\mathrm{negl}(\lambda)}$ such that

$\operatorname{\mathrm{Pr}}[V(p,k,o,0,a_{0})=V(p,k,o,1,a_{1})=1]\leq
h(\lambda)+\operatorname{\mathrm{negl}(\lambda)},$ (99)

where the probability is over $(p,k)\leftarrow G(1^{\lambda})$ and
$(o,a_{0},a_{1})\leftarrow T(p)$.

We now prove Proposition 7.2, which is restated below for convenience.

######  Proposition E.2.

Suppose that the $\textnormal{LWE}_{n,q,G(\sigma,\tau)}$ problem is hard. Then
$\mathbf{Z}=(G,O,S,V)$ defined in Fig. 10 is a 1-of-2 puzzle with completeness
$\cos^{2}\left(\frac{\pi}{8}\right)-\frac{5m\sigma^{2}}{q^{2}}-\frac{m\sigma}{2\tau}$
and soundness error $\frac{1}{2}+\operatorname{\mathrm{negl}(\lambda)}$.

###### Proof.

To prove correctness, observe that the probability of success of the player in
$\mathbf{Z}$ is the same as the probability of success of the honest prover in
the proof of quantumness protocol $\mathbf{Q}$. This is because $G$ is simply
Alice’s actions in the first round of $\mathbf{Q}$, $O$ and $S$ are Bob’s
actions in the first and second rounds of interaction in Protocol $\mathbf{Q}$
respectively, and $V$ is the scoring function of Protocol $\mathbf{Q}$.
Additionally the challenge bit $b^{\prime}$ is sampled uniformly randomly in
both settings. Hence, Theorem 5.1 implies that the completeness of
$\mathbf{Z}$ is
$\cos^{2}\left(\frac{\pi}{8}\right)-\frac{5m\sigma^{2}}{q^{2}}-\frac{m\sigma}{2\tau}$.

We now prove soundness. Let $T$ be a
$\operatorname{\mathrm{poly}(\lambda)}$-time quantum algorithm which receives
a puzzle $p$ as input and outputs $(o,a_{0},a_{1})$, where $o$ is the
obligation string and $a_{0}$ and $a_{1}$ are single bits. Showing the
soundness claimed in the proposition is equivalent to showing

$\Pr[V(p,k,o,0,a_{0})=V(p,k,o,1,a_{1})=1]\leq\frac{1}{2}+\operatorname{\mathrm{negl}(\lambda)},$
(100)

where the probability is over $(p,k)\leftarrow G(1^{\lambda})$ and
$(o,a_{0},a_{1})\leftarrow T(p)$.

Assume for the sake of contradiction that

$\Pr[V(p,k,o,0,a_{0})=V(p,k,o,1,a_{1})=1]>\frac{1}{2}+\mu(\lambda),$ (101)

where the probability is over $(p,k)\leftarrow G(1^{\lambda})$ and
$(o,a_{0},a_{1})\leftarrow T(p)$, and $\mu$ is some non-negligible function.

We can use $T$ to construct a $\operatorname{\mathrm{poly}(\lambda)}$-time
algorithm $B$ that breaks Regev’s encryption scheme as follows.

  1. 1.

$B$. Input: $(pk,ct)$.

  2. 2.

$(o,a_{0},a_{1})\leftarrow T(p=(pk,ct))$

  3. 3.

Output: $a_{0}\oplus a_{1}$.

Now, we have

$\displaystyle\operatorname{\mathrm{Pr}}[B(pk,ct)=b\mid
pk\leftarrow\textnormal{Gen}_{J}(),b\leftarrow\\{0,1\\},ct\leftarrow\textnormal{Encrypt}_{J}(pk,b)]$
$\displaystyle=$ $\displaystyle\operatorname{\mathrm{Pr}}\Bigl{[}a_{0}\oplus
a_{1}=b\bigm{|}\begin{subarray}{c}pk\leftarrow\textnormal{Gen}_{J}(),b\leftarrow\\{0,1\\},ct\leftarrow\textnormal{Encrypt}_{J}(pk,b),\\\
(o,a_{0},a_{1})\leftarrow T(pk,ct)\end{subarray}\Bigr{]}$ $\displaystyle=$
$\displaystyle\operatorname{\mathrm{Pr}}\Bigl{[}a_{0}\oplus
a_{1}=b\bigm{|}(p=(pk,ct),k=(s,t,b))\leftarrow
G(1^{\lambda}),(o,a_{0},a_{1})\leftarrow T(pk,ct)\Bigr{]}$ $\displaystyle\geq$
$\displaystyle\operatorname{\mathrm{Pr}}\Bigl{[}a_{0}=d(p,k,o)\text{ and
}a_{1}=d(p,k,o)\oplus b\bigm{|}(p,k)\leftarrow
G(1^{\lambda}),(o,a_{0},a_{1})\leftarrow T(p)\Bigr{]}$ $\displaystyle=$
$\displaystyle\Pr[V(p,k,o,0,a_{0})=V(p,k,o,1,a_{1})=1\mid(p,k)\leftarrow
G(1^{\lambda}),(o,a_{0},a_{1})\leftarrow T(p)]$ $\displaystyle>$
$\displaystyle\frac{1}{2}+\mu(\lambda),$

where the first line follows from the definition of $B$, the second line
follows from the definition of $G$, we recall the definition of $d(p,k,o)$
from Fig. 10 in the third line, the fourth line follows from the definition of
$V$, and the last line is our assumption in Eq. 101.

But $B$ is a $\operatorname{\mathrm{poly}(\lambda)}$-time algorithm because
$T$ is a $\operatorname{\mathrm{poly}(\lambda)}$-time algorithm. Therefore,
the last inequality contradicts Proposition 3.5 under the LWE hardness
assumption made in the statement of the proposition. Therefore, Eq. 100 must
hold and the soundness of $\mathbf{Z}$ follows.

∎

It is straightforward to convert $\mathbf{Z}$ into a strong 1-of-2 puzzle —
and hence a semi-quantum money scheme via [RS22] — assuming the following
technical conjecture which shows that the soundness error decays exponentially
with the number of repeats $\ell\in\mathbb{N}$ in threshold parallel
repetition. This conjecture is known to hold with the word “quantum”
(emphasized) replaced by “randomized”, see [IJK09, Theorem 1.1].666In [IJK09,
Theorem 1.1], the result is stated for a weakly verifiable puzzle instead of a
1-of-2 puzzle. However, the two types of puzzles have equivalent hardness, see
[RS22, Fact 19].

######  Conjecture 1.

There exist constants $c_{1},c_{2}>0$ such that the following holds.

Let $\ell\in\mathbb{N}$, $\gamma>0$, and $\mathbf{Z}=(G,O,S,V)$ be a 1-of-2
puzzle. Suppose that $\mathbf{Z}$ is $\frac{1}{2}$-hard, i.e., for any
$\operatorname{\mathrm{poly}(\lambda)}$-time _quantum_ algorithm $T$, there
exists a negligible function $\operatorname{\mathrm{negl}(\lambda)}$ such that

$\operatorname{\mathrm{Pr}}[V(p,k,o,0,a_{0})=V(p,k,o,1,a_{1})=1]\leq\frac{1}{2}+\operatorname{\mathrm{negl}(\lambda)},$
(102)

where the probability is over $(p,k)\leftarrow G(1^{\lambda})$ and
$(o,a_{0},a_{1})\leftarrow T(p)$.

Then, for any $\operatorname{\mathrm{poly}(\lambda)}$-time _quantum_ algorithm
$\bar{T}$, we have

$\displaystyle\operatorname{\mathrm{Pr}}\bigl{[}\bigl{|}\\{i\in[\ell]\mid
V(p_{i},k_{i},o_{i},0,a_{0,i})=V(p_{i},k_{i},o_{i},1,a_{1,i})=1\\}\bigr{|}\bigr{]}\geq(1+\gamma)\ell/2]$
(103) $\displaystyle\leq$
$\displaystyle\frac{c_{1}}{\gamma}\exp(-c_{2}\,\gamma^{2}\,\ell),$

where the probability is over $(p_{i},k_{i})\leftarrow G(1^{\lambda})$ for all
$i\in[\ell]$ and

$(o_{1},\dots,o_{\ell},a_{0,1},\dots,a_{0,\ell},a_{1,1},\dots,a_{1,\ell})\leftarrow\bar{T}(p_{1},\dots,p_{\ell},k_{1},\dots,k_{\ell}).$

We now show that the following 1-of-2 puzzle $\mathbf{Z}^{\ell}$ defined from
$\mathbf{Z}$ is a strong 1-of-2 puzzle assuming Conjecture 1.

######  Definition E.3 (Threshold parallel repetition of 1-of-2 puzzle
$\mathbf{Z}$).

Let $\mathbf{Z}=(G,O,S,V)$ be the 1-of-2 puzzle defined in Fig. 10. Let
$\ell=\lambda\in\mathbb{N}$ and $\alpha\in(3/4,\cos^{2}(\pi/8))$. We define
the 1-of-2 puzzle $\mathbf{Z}^{\ell}=(G^{\ell},O^{\ell},S^{\ell},V^{\ell})$ as
follows.

  1. 1.

$G^{\ell}$ receives security parameter $1^{\lambda}$ as input and runs
$G(1^{\lambda})$ $\ell$ times to sample $\ell$ random puzzles and their
verification keys:

$((p_{1},\dots,p_{\ell}),(k_{1},\dots,k_{\ell}))\leftarrow
G^{n}(1^{\lambda}),$

where $(p_{i},v_{i})\leftarrow G(1^{\lambda})$ for all $i\in[\ell]$.

  2. 2.

$O^{\ell}$ receives $\ell$ puzzles as input and outputs $\ell$ obligation
strings and $\ell$ quantum states:

$((o_{1},\dots,o_{\ell}),(\rho_{1}\otimes\dots\otimes\rho_{\ell}))\leftarrow
O^{\ell}(p_{1},\dots,p_{\ell}),$

where $(o_{i},\rho_{i})\leftarrow O(p_{i})$ for all $i\in[\ell]$.

  3. 3.

$S^{\ell}$ receives $\ell$ puzzles, $\ell$ obligation strings, $\ell$ quantum
states, and a single bit $b\in\\{0,1\\}$ as input and outputs $\ell$ classical
strings:

$(a_{1},\dots,a_{\ell})\leftarrow
S^{n}((p_{1},\dots,p_{\ell}),(o_{1},\dots,o_{\ell}),\rho_{1}\otimes\dots\otimes\rho_{\ell},b),$

where $a_{i}\leftarrow S(p_{i},o_{i},\rho_{i},b)$ for all $i\in[\ell]$.

  4. 4.

$V^{\ell}$ receives $\ell$ puzzles, $\ell$ keys, $\ell$ obligation strings, a
single bit $b\in\\{0,1\\}$, and $\ell$ answer strings as input and outputs $0$
or $1$:

$V^{\ell}((p_{1},\dots,p_{\ell}),(k_{1},\dots,k_{\ell}),(o_{1},\dots,o_{\ell}),b,(a_{1},\dots,a_{\ell}))\in\\{0,1\\}$

is equal to 1 if and only if

$\bigl{|}\\{i\in[\ell]\mid
V(p_{i},k_{i},o_{i},b,a_{i})=1\\}\bigr{|}\geq\alpha\ell.$ (104)

The definition of $\mathbf{Z}^{\ell}$ is the same as [RS22, Definition 14]
except the verification algorithm $V^{\ell}$ checks whether the number of
successes exceeds a threshold, see Eq. 104.

Using $\alpha<\cos^{2}(\pi/8)$, a simple Chernoff bound implies that
$\mathbf{Z}^{\ell}$ has completeness 1. Using $\alpha>3/4$, so that
$\gamma\coloneqq 4\alpha-3>0$, we can show that $\mathbf{Z}^{\ell}$ has
soundness error $0$ assuming Conjecture 1 as follows. Let $\bar{T}$ be a
$\operatorname{\mathrm{poly}(\lambda)}$-time quantum algorithm, then

$\displaystyle\operatorname{\mathrm{Pr}}[V^{\ell}(p,k,o,0,a_{0})=V^{\ell}(p,k,o,1,a_{1})=1]$
$\displaystyle=$ $\displaystyle\operatorname{\mathrm{Pr}}\bigl{[}\forall
b\in\\{0,1\\},\bigl{|}\\{i\in[\ell]\mid
V(p_{i},k_{i},o_{i},b,a_{i})=1\\}\bigr{|}\geq\alpha\ell\bigr{]}$
$\displaystyle\leq$
$\displaystyle\operatorname{\mathrm{Pr}}\bigl{[}\bigl{|}\\{i\in[\ell]\mid
V(p_{i},k_{i},o_{i},0,a_{0,i})=V(p_{i},k_{i},o_{i},1,a_{1,i})=1\\}\bigr{|}\geq(2\alpha-1)\ell\bigr{]}$
$\displaystyle=$
$\displaystyle\operatorname{\mathrm{Pr}}\bigl{[}\bigl{|}\\{i\in[\ell]\mid
V(p_{i},k_{i},o_{i},0,a_{0,i})=V(p_{i},k_{i},o_{i},1,a_{1,i})=1\\}\bigr{|}\geq(1+\gamma)\ell/2\bigr{]}$
$\displaystyle\leq$
$\displaystyle\frac{c_{1}}{\gamma}\exp(-c_{2}\,\gamma^{2}\ell)$
$\displaystyle\leq$ $\displaystyle\operatorname{\mathrm{negl}(\lambda)},$

where all probabilities are over
$(p=(p_{1},\dots,p_{\ell}),k=(k_{1},\dots,k_{\ell}))\leftarrow
G^{\ell}(1^{\lambda})$ and
$(o=(o_{1},\dots,o_{\ell}),a_{0}=(a_{0,1},\dots,a_{0,\ell}),a_{1}=(a_{1,1},\dots,a_{1,\ell}))\leftarrow\bar{T}(p,k)$,
the second-to-last line follows from Conjecture 1, and the last line uses
$\ell=\lambda$.