# Cryptanalysis of Three Quantum Money Schemes

Andriyan Bilyk Ryerson University<EMAIL_ADDRESS>Javad Doliskani
Ryerson University<EMAIL_ADDRESS>Zhiyong Gong Ryerson
University<EMAIL_ADDRESS>
###### Abstract

We investigate the security assumptions behind three public-key quantum money
schemes. Aaronson and Christiano proposed a scheme based on hidden subspaces
of the vector space $\mathbb{F}_{2}^{n}$ in 2012. It was conjectured by Pena
et al in 2015 that the hard problem underlying the scheme can be solved in
quasi-polynomial time. We confirm this conjecture by giving a polynomial time
quantum algorithm for the underlying problem. Our algorithm is based on
computing the Zariski tangent space of a random point in the hidden subspace.

Zhandry proposed a scheme based on multivariate hash functions in 2017. We
give a polynomial time quantum algorithm for cloning a money state with high
probability. Our algorithm uses the verification circuit of the scheme to
produce a banknote from a given serial number.

Kane, Sharif and Silverberg proposed a scheme based on quaternion algebras in
2021. The underlying hard problem in their scheme is cloning a quantum state
that represents an eigenvector of a set of Hecke operators. We give a
polynomial time quantum reduction from this hard problem to a linear algebra
problem. The latter problem is much easier to understand, and we hope that our
reduction opens new avenues to future cryptanalyses of this scheme.

##  1 Introduction

The first quantum money scheme was proposed by Wiesner [28] around 1970. The
idea was to represent banknotes using quantum states which, by the laws of
quantum mechanics, would be impossible to copy. Wiesner’s scheme, which is
nowadays called a private-key quantum money scheme, worked as follows. The
bank generates a pair $(s,\rho_{s})$ consisting of a classical serial number
$s$ and a quantum state $\rho_{s}$, and stores $s$ along with a classical
description of $\rho_{s}$ in a database. Without access to the database, no
algorithm would be able to copy $\rho_{s}$ with non-negligible probability.
Therefore, only the issuing bank would be able to verify the banknotes.
Although this scheme is information-theoretically secure, it suffers major
drawbacks in terms of practicality: First, the issuing bank has to maintain a
huge database containing classical descriptions of every banknote ever
produced. Second, only the bank can verify a banknote, and therefore the users
have to take the money back to the bank for every transaction.

Subsequent efforts to address the drawbacks of Wiesner’s scheme led to the
idea of public-key quantum money. The first formal treatment of public-key
quantum money was given by Aaronson [1]. Intuitively, in such a scheme, a
banknote can be verified by everyone, using a publicly known algorithm, but
cannot be copied by anyone. The first explicit construction of public-key
quantum money, which was based on stabilizer states, was given in [1]. The
construction was later proved to be insecure by Lutomirski et al. [19].

Public-key quantum money cannot be information-theoretically secure, it has to
be based on a computational assumption. There have been many attempts at
building a secure public-key quantum money scheme. Farhi et al. [11] proposed
a scheme based on knot theory. A banknote in their scheme consists of a
quantum state $\rho_{s}$ representing a superposition of certain grid
diagrams, and serial number $s$ which is the Alexander polynomial of the grids
in $\rho_{s}$. A banknote is verified using a procedure based on a classical
Markov chain.

Aaronson and Christiano [3] proposed a scheme based on hidden subspaces of the
vector space $\mathbb{F}_{2}^{n}$. In their scheme, a banknote consists of a
quantum state $\rho_{s}$ that is a uniform superposition of elements in a
random linear subspace $A_{s}\subset\mathbb{F}_{2}^{n}$ of dimension $n/2$,
and a serial number $s$ that provides membership oracles for $A_{s}$ and the
orthogonal complement $A_{s}^{\perp}$. The verification of a banknote is done
using a projection operator built from the membership oracles for $A_{s}$ and
$A_{s}^{\perp}$.

Zhandry [30] adapted the idea proposed in [19] to give a construction of
public-key quantum money based on multivariate hash functions. In their
scheme, even the issuing bank cannot reproduce the same banknote. A bank note
in their scheme consists of a quantum state that is a uniform superposition of
the preimages of a random output $y$ of a hash function, and a serial number
which is the point $y$. To be able to verify banknotes, a restricted class of
hash functions are used. The verification is done using the quantum Fourier
transform and computing the ranks of matrices in a certain superposition.

Kane, Sharif and Silverberg [14] proposed a completely different construction
for public-key quantum money based on quaternion algebras. There exists a set
of commuting operators, called Hecke operators, on the space of modular forms.
The Hecke operators are Hermitian, and therefore the space of modular forms
has a basis consisting of simultaneous eigenvectors for these operators. A
banknote in this scheme consists of a quantum state $\rho_{s}$ that is an
eigenstate of the Hecke operators, and a serial number $s$ that is a set of
eigenvalues corresponding to $\rho_{s}$ and a certain set of Hecke operators.
The verification of a banknote is done using phase estimation.

###  1.1 Previous cryptanalysis

Unfortunately, the security of all proposed public-key quantum money schemes
to this date have been based on ad hoc/nonstandard computational assumptions.
However, there has been a limited number of attempts, many of which were not
convincing, at cryptanalyzing these assumption. As mentioned above, the
public-key quantum money scheme of [1] was broken by Lutomirski et al. [19]
who presented two attacks that worked in different parameter regimes. Their
first attack was classical and used only the description of the verification
circuit, while their second attack was a quantum algorithm that could generate
banknotes that were different from the intended banknotes but could pass
verification with non-negligible probability.

Pena et al. [21] presented an attack on the scheme [3], but their attack was
not on the original parameters. In particular, the explicit construction
proposed in [3] is defined over $\mathbb{F}_{2}$, but the attack presented in
[21] is only efficient if the scheme was defined over $\mathbb{F}_{p}$ for a
larger prime $p$. Pena et al. conjectured that for $p=2$ their algorithm would
run in quasi-polynomial time. Their attack is entirely classical and uses only
the serial number given in the banknote.

Roberts [23] proposed an attack on the assumption underlying the scheme of
[30] for a certain parameter regime. However, as discussed in a later version
of [30], the attack does not make the system insecure. Moreover, the hardness
assumption behind the scheme could be modified in a way that renders the
attack useless.

###  1.2 This work

In this paper, we carry out cryptanalysis on the following three schemes:

  * •

Aaronson and Christiano [3]. As mentioned above, this scheme is based on
hidden subspaces of the vector space $\mathbb{F}_{2}^{n}$. The hard problem
behind this scheme is to recover a secret linear subspace of
$\mathbb{F}_{2}^{n}$ from the the set of common roots of a set of random
polynomials over $\mathbb{F}_{2}$. The previous attack, carried out by Pena et
al. [21], against this scheme uses the Gröbner basis algorithm. Their attack
is only effective if the scheme was defined over $\mathbb{F}_{p}$ for larger
$p$, instead of $\mathbb{F}_{2}$. It was conjectured in [21] that there exists
a quasi-polynomial time algorithm for the original scheme over
$\mathbb{F}_{2}$.

We give a polynomial time quantum algorithm for the case $\mathbb{F}_{2}$. Our
attack is geometric, it uses the fact that a linear variety is isomorphic to
its Zariski tangent space at any point. In particular, the subspace hidden by
a set of polynomials can be viewed as a linear variety $Y$ included in an
affine variety $X$. We show that one can recover the hidden subspace by simply
computing the kernel of the Jacobian matrix of $X$ at a random point of the
subspace $Y$. Such a random point is obtained by measuring a money state.

  * •

Zhandry [30]. This scheme is based on Multivariate Hash Functions. There are
different versions of the paper [30] that give slightly different formulations
of the scheme, but the underlying hardness assumptions can all be stated using
the idea of multi-collision of multivariate polynomial hash functions. We will
focus on the version [29], in which the hardness assumption is directly stated
using quadratic forms.

We give a polynomial time quantum algorithm, using which one can obtain
arbitrarily many copies of a given banknote. Our algorithm uses the
verification circuit of the scheme to produce a certain superposition of
“bolts”. A measurement on this superposition then produces a copy of the money
state with high probability. The ability to produce arbitrarily many copies of
the money state comes from the fact the measurement outcome $y^{\prime}$ can
be compared against the given serial number $y$. If $y^{\prime}=y$ then
desired money state has been produced, otherwise the whole process is
repeated.

  * •

Kane, Sharif and Silverberg [14]. This scheme is based on quaternion algebras.
There have not been any attempts at cryptanalyzing this scheme yet, partly
because of the mathematics involved which is rather nontrivial. The underlying
hard problem in this scheme is simply cloning the money state which is an
eigenstate of the set of all Hecke operators.

Although we have not been able to break this scheme, we give a polynomial time
quantum reduction from the underlying hard problem to the problem of inverting
a certain matrix $A$. Our algorithm is based on a deep connection between
ideal classes in a rational quaternion algebra and the space of modular forms
of weight $2$ over the complex numbers. The connection is provided by the
theory of Theta series. The matrix $A$ is highly structured, with entries the
representation numbers of explicit quaternary quadratic forms. In other words,
$A$ can be described by a set of polynomials of degree two in four variables.
To work with this matrix, one does not need to know much about the theory
behind the scheme. We believe that this reduction is an important first step
toward an effective cryptanalysis of this scheme, and opens interesting new
avenues for future attacks.

##  2 Preliminaries

##### Quantum computation.

For a detailed treatment on quantum information we refer the reader to [27]. A
register in this paper can contain a classical or a quantum state. The
classical state of a register $\mathsf{X}$ is described by a finite alphabet
$\Sigma$. An example alphabet used in this paper is
$\Sigma=\mathbb{F}_{2}^{n}$. The quantum state of $\mathsf{X}$ is described by
the set of density operators $\mathrm{D}(\mathcal{X})$ where $\mathcal{X}$ is
the complex Euclidean space $\mathbb{C}^{\Sigma}$.

We will also represent quantum states using unit vectors in $\mathcal{X}$,
which are called pure states. We will use the Dirac notation when describing
unit vectors. In particular, a unit column vector $x\in\mathcal{X}$ is written
as $\lvert x\rangle$, and the row vector $x^{*}$, which is the conjugate
transpose of $x$, is written as $\langle x\rvert$. The quantum state of the
register $\mathsf{X}$ can then be written as

$\sum_{x\in\Sigma}\alpha_{x}\lvert
x\rangle,\quad\sum_{x\in\Sigma}\lvert\alpha_{x}\rvert^{2}=1.$

The trace distance between two quantum states $\rho$ and $\sigma$ is defined
by $\lVert\rho-\sigma\rVert_{1}$ where $\lVert
A\rVert_{1}=\operatorname{Tr}\sqrt{A^{*}A}$ is the trace norm of linear
operators. For pure states $\lvert\psi\rangle$ and $\lvert\phi\rangle$ the
distance is computed using

$\lVert\lvert\psi\rangle\langle\psi\rvert-\lvert\phi\rangle\langle\phi\rvert\rVert_{1}=2\sqrt{1-\lvert\langle\psi|\phi\rangle\rvert^{2}}.$

For quantum state $\rho_{i}$ and $\sigma_{i}$, $i=1,2$

$\lVert\rho_{1}\otimes\rho_{2}-\sigma_{1}\otimes\sigma_{2}\rVert_{1}\leq\lVert\rho_{1}-\sigma_{1}\rVert_{1}+\lVert\rho_{2}-\sigma_{2}\rVert_{1}.$

##### Public-key quantum money.

Following the definition in [3], a public-key quantum money scheme consists of
three algorithms:

  * •

$\mathsf{Gen}$. Takes as input a security parameter $\kappa$, and generates a
key pair $(k_{\text{pri}},k_{\text{pub}})$ in probabilistic polynomial time
(in $\kappa$). Here, $k_{\text{pri}}$ is the private key and $k_{\text{pub}}$
is the public key.

  * •

$\mathsf{Bank}$. Takes as input a private key $k_{\text{pri}}$, and generates
a banknote in probabilistic polynomial time.

  * •

$\mathsf{Ver}$. Takes as input the public key $k_{\text{pub}}$ and a banknote,
and outputs either ‘accept’ or ‘reject’.

A banknote, denoted by $\lvert\$\rangle$, usually consists of a pair
$(s,\rho_{s})$ where $s$ is a binary string and $\rho_{s}$ is a mixed quantum
state. The string $s$ is called the serial number, and the state $\rho_{s}$ is
called the money state.

The notion of security for a quantum money scheme is best explained using an
adversary-challenger game. The goal for an adversary $A$ is to produce a copy
of a valid banknote without having access to the private key. Consider the
following game played by $A$ and a challenger. The challenger calls
$\mathsf{Bank}$ to generate a banknote $\lvert\$\rangle=(s,\rho_{s})$, and
sends the banknote to $A$. $A$ generates two alleged banknotes
$\lvert\$_{1}\rangle=(s_{1},\rho_{s_{1}})$ and
$\lvert\$_{2}\rangle=(s_{2},\rho_{s_{2}})$ where $\rho_{s_{1}}$ and
$\rho_{s_{2}}$ are allowed to be entangled. The challenger accepts if and only
if $\mathsf{Ver}$ accepts both $\lvert\$_{1}\rangle$ and $\lvert\$_{2}\rangle$
and $s_{1}=s_{2}=s$. A quantum money scheme
$(\mathsf{Gen},\mathsf{Bank},\mathsf{Ver})$ is said to be secure if for any
polynomial time quantum adversary $A$, the challenger accepts in the above
experiment with probability negligible in $\kappa$.

##  3 Quantum Money From Hidden Subspaces

In this section, we investigate the security of the quantum money scheme
proposed by Aaronson and Christiano [3], which is based on hidden linear
subspaces of $\mathbb{F}_{2}^{n}$.

###  3.1 The quantum money scheme

Let $n=\kappa$ where $\kappa$ is the security parameter. The $n$-qubit money
state in this scheme is a uniform superposition

$\lvert A\rangle=\frac{1}{2^{n/4}}\sum_{x\in A}\lvert x\rangle,$

where $A\subset\mathbb{F}_{2}^{n}$ is a random linear subspace of dimension
$n/2$. The bank generates such a state by choosing a set of $n/2$ random and
linearly independent elements of $\mathbb{F}_{2}^{n}$ and building a
superposition from their linear combinations. The state $\lvert A\rangle$ is
then verified by querying to classical oracles $U_{A}$ and $U_{A^{\perp}}$
where $A^{\perp}$ is the orthogonal complement of $A$. These oracles are
membership oracles. More precisely, for $x\in\mathbb{F}_{2}^{n}$

$U_{A}\lvert x\rangle=\begin{cases}-\lvert x\rangle&\text{if }x\in A,\\\
\lvert x\rangle&\text{otherwise}.\end{cases}$

The oracle $U_{A^{\perp}}$ is defined similarly. Using these oracles we can
build projectors $\mathbb{P}_{A}$ and $\mathbb{P}_{A^{\perp}}$ onto the basis
elements of $A$ and $A^{\perp}$, respectively. The verification process works
by first projecting onto $A$, then applying the $n$-qubit Hadamard transform
$H^{\otimes n}$, then projecting on $A^{\perp}$ and finally applying another
$H^{\otimes n}$. So the verification algorithm can be written as
$V_{A}:=H^{\otimes n}\mathbb{P}_{A^{\perp}}H^{\otimes n}\mathbb{P}_{A}$. It
can be shown that $V_{A}=\lvert A\rangle\langle A\rvert$, i.e., $V_{A}$ is
just a projector onto $A$. This means that the verification algorithm accepts
a state $\lvert\psi\rangle$ with probability
$\lvert\langle\psi|A\rangle\rvert^{2}$.

In the above scheme, the following algorithms are publicly accessible.

$\mathsf{G}(r)$:

takes a random $r\in\\{0,1\\}^{n}$ as input. Outputs a set of random linearly
independent elements $\\{y_{1},\dots,y_{n/2}\\}$ for a subspace
$A_{r}\subset\mathbb{F}_{2}^{n}$, and a serial number $s_{r}$.

$\mathsf{H}(s)$:

checks if $s$ is a valid serial number.

$\mathsf{T}(r)$:

takes an input of the form $\lvert s\rangle\lvert x\rangle$ and applies
$U_{A_{r}}$ to $\lvert x\rangle$ if $s$ is a valid serial number.

$\mathsf{T}^{\perp}(r)$:

similar to $\mathsf{T}(r)$ but with $U_{A_{r}}$ replaced by
$U_{A_{r}^{\perp}}$.

The $\mathsf{Bank}$ and $\mathsf{Ver}$ algorithms are then defined as follows:

$\mathsf{Bank}$

calls $\mathsf{G}(r)$ for a uniformly random $r\in\\{0,1\\}^{n}$ to receive a
pair $(s_{r},A_{r})$, and outputs a banknote $\lvert\$_{r}\rangle=\lvert
s_{r}\rangle\lvert A_{r}\rangle$.

$\mathsf{Ver}$

takes as input a banknote $\cent$, and uses $\mathsf{H}$ to check if $\cent$
is of the form $(s,\rho)$ for a valid serial number $s$. If $s$ is valid then
it uses $\mathsf{T}$ and $\mathsf{T}^{\perp}$ to compute $V_{A}(\rho)$, and
outputs ‘accept’ if and only if $V_{A}$ outputs ‘accepts’.

Assuming black box access to the oracles $U_{A}$ and $U_{A^{\perp}}$, it was
proved in [3] that a counterfeiter needs at least
$\Omega(\sqrt{\epsilon}2^{n/4})$ queries to prepare a state $\rho$ such that
$\langle A\rvert^{\otimes 2}\rho\lvert A\rangle^{\otimes 2}\geq\epsilon$.
However, there has been no provably secure instantiation of these oracles to
this date.

The first instantiation of $U_{A}$ and $U_{A^{\perp}}$ was proposed in the
same paper [3], which was based on multivariate polynomials. The idea is to
“obfuscate” the subspace $A$ using a set of polynomials
$p_{1},\dots,p_{m}\in\mathbb{F}_{2}[x_{1},\dots,x_{n}]$. More precisely, let
$I_{d,A}$ be the set of polynomials of degree $d$ in
$\mathbb{F}_{2}[x_{1},\dots,x_{n}]$ that vanish on $A$. Then the polynomials
$p_{i}$ are selected uniformly at random from $I_{d,A}$. For a large enough
$m$, the polynomials $p_{1},\dots,p_{m}$ uniquely determine $A$ with
overwhelming probability. This means for all $v\in A$ we will have
$p_{1}(v)=\cdots=p_{m}(v)=0$, and for any $v\notin A$ we will have
$p_{k}(v)\neq 0$ for at least one $1\leq k\leq m$ with overwhelming
probability. This is proved in the following lemma.

######  Lemma 3.1 ([3, Lemma 29]).

Let $A\subseteq\mathbb{F}_{2}^{n}$ be a linear subspace and let $\beta>1$ be a
constant. For any set of polynomials $p_{1},\dots,p_{\beta n}\in I_{d,A}$
selected uniformly at random, define
$Z=\\{v\in\mathbb{F}_{2}^{n}:p_{i}(v)=0\text{ for all }1\leq i\leq\beta n\\}$.
Then $A\subseteq Z$, and $\Pr[A=Z]=1-2^{-\Omega(n)}$.

One can sample uniformly at random from $I_{d,A}$ in time $O(n^{d})$ which is
polynomial when $d$ is a constant. An immediate consequence of Lemma 3.1 is
that the set of random polynomials $p_{1},\dots,p_{\beta n}$ can be
effectively used as a membership oracle for $A$. Therefore, the banknote
$(s_{r},\lvert A_{r}\rangle)$, which can be generated efficiently by the bank,
consists of a superposition over the random subspace $A_{r}$ and the list of
polynomials $s_{r}=\\{p_{i}\\}_{1\leq i\leq\beta n}$ corresponding to $A_{r}$.
The hardness assumption underlying the quantum money scheme of [3] is based on
the following problem:

######  Problem 3.2.

Let $d\geq 3$ be a constant integer and $\beta>1$ a real number. Let
$A\subset\mathbb{F}_{2}^{n}$ be a random linear subspace of dimension $n/2$
and let $p_{1},\dots,p_{\beta n}\in I_{d,A}$ be selected uniformly at random.
Given the banknote $(s,\lvert A\rangle)$, where $s=\\{p_{i}\\}_{1\leq
i\leq\beta n}$, recover a set of generators for $A$.

A noisy version of Problem 3.2 was also introduced in [3], but was later shown
to be quantum polynomial time equivalent to the noiseless version [2, Section
9.6]. In this paper, we give a quantum polynomial time algorithm for Problem
3.2. Our idea is based on computing the Zariski tangent space of the variety
described by the set of polynomials $s$.

###  3.2 Background

In this section, we review some basic facts about tangent spaces in algebraic
geometry. Let $X$ be a scheme, and let $x\in X$ be any point. Let
$\kappa(x)=\mathscr{O}_{X,x}/\mathfrak{m}_{x}$ be the residue field at $x$,
where $\mathscr{O}_{X,x}$ is the local ring at $x$ and $\mathfrak{m}_{x}$ is
the maximal ideal of $\mathscr{O}_{X,x}$. Then
$\mathfrak{m}_{x}/\mathfrak{m}_{x}^{2}$ is a vector space over $\kappa(x)$.
The Zariski tangent space of $X$ in $x$ is defined as the dual vector space

$T_{x}X=(\mathfrak{m}_{x}/\mathfrak{m}_{x}^{2})^{\vee}.$

The following are standard in algebraic geometry, but include some
explanations for the sake of completeness.

######  Fact 3.3.

If $Y\subseteq X$ is a closed subscheme, and $y\in Y$, then $T_{y}Y\subseteq
T_{y}X$. This is because the morphism

$\mathfrak{m}_{y}/\mathfrak{m}_{y}^{2}\rightarrow\mathfrak{m}_{x}/\mathfrak{m}_{x}^{2}$

of $\kappa(y)$-vector spaces, where $\mathfrak{m}_{y}$ is the maximal ideal of
$\mathscr{O}_{Y,y}$, is surjective. Therefore, the dual morphism is injective.

######  Fact 3.4.

For closed subschemes $Y,Z\subseteq X$ and a point $y\in Y\cap Z$, we have
$T_{y}(Y\cap Z)=T_{y}Y\cap T_{y}Z$. Here, $Y\cap Z$ is the scheme-theoretic
intersection. Locally, we can replace $X$ with a $\operatorname{Spec}(A)$, for
a ring $A$, so that $Y$ and $Z$ are described by some ideals $I,J\subset A$.
Then the intersection $Y\cap Z$ is $\operatorname{Spec}A/(I+J)$, and the above
statement can be proved using straightforward commutative algebra.

Let $k$ be a field. By a $k$-variety $X$ we mean a reduced separated scheme of
finite type over $k$. In this paper, we are interested in affine varieties,
i.e., in schemes of the form $X=\operatorname{Spec}k[T_{1},\dots,T_{n}]/I$
where $I=(f_{1},\dots,f_{m})$ is an ideal in the polynomial ring
$k[T_{1},\dots,T_{n}]$. A $k$-variety is called linear if it is defined by the
intersection of hyperplanes. Therefore, $X$ is linear when the defining
polynomials $f_{1},\dots,f_{m}$ all have degree one. A point $x\in X$ is
called a $k$-valued point if $\kappa(x)=k$. When $X$ is affine, the Zariski
tangent space at a $k$-valued point $x$ can be computed using the Jacobian
matrix at $x$. The Jacobian matrix of the set of polynomials
$f_{1},\dots,f_{m}$ at $x$ is defined as

$J_{f_{1},\dots,f_{m}}(x)=\begin{bmatrix}\dfrac{\partial f_{1}}{\partial
T_{1}}(x)&\cdots&\dfrac{\partial f_{1}}{\partial T_{n}}(x)\\\
\vdots&\ddots&\vdots\\\ \dfrac{\partial f_{m}}{\partial
T_{1}}(x)&\cdots&\dfrac{\partial f_{m}}{\partial T_{n}}(x)\end{bmatrix},$

where the derivatives $\partial f_{i}/\partial T_{j}$ are formal derivatives.

For the affine variety $X$ defined by the ideal $I$ as above, the tangent
space $T_{x}X$ at the point $x=(x_{1},\dots,x_{n})\in X$ is the linear variety
defined by the coordinates of the vector

$J_{f_{1},\dots,f_{m}}(x)\begin{bmatrix}T_{1}-x_{1}\\\ \vdots\\\
T_{n}-x_{n}\end{bmatrix}.$ (1)

In other words, letting

$g_{i}=\sum_{j=1}^{n}\frac{\partial f_{i}}{\partial T_{j}}(x)(T_{j}-x_{j}),$

the space $T_{x}X$ is defined as the zero set of the ideal
$(g_{1},\dots,g_{m})$. It follows from the above that

######  Fact 3.5.

If $X$ is a linear $k$-variety and $x\in X$ is a $k$-valued point, then
$T_{x}X=X$.

###  3.3 Cryptanalysis

In this section, we give a polynomial time quantum algorithm for Problem 3.2.
We are given a banknote $(s,\lvert A\rangle)$ where
$A\subset\mathbb{F}_{2}^{n}$ is a random linear subspace of dimension $n/2$,
and $s$ is a set of polynomials $p_{1},\dots,p_{m}\in I_{d,A}$, where $m=\beta
n$, $\beta>1$. The first step is to measure the state $\lvert A\rangle$ to
obtain uniformly random element $x\in A$. So now we have two pieces of
classical information: the set of polynomials $\\{p_{i}\\}$ and a uniformly
random $x\in A$.

Geometrically, the subspace $A$ is the set of $\mathbb{F}_{2}$-valued points
in a linear variety $Y$ given by an ideal $(H_{1},\dots,H_{n/2})$ with
$H_{i}$’s homogeneous linear polynomials. It follows from (1) and Fact 3.5
that $T_{x}Y=Y$. In fact, since the $H_{i}$ are homogeneous, we have

$Y=\ker J_{H_{1},\dots,H_{n/2}}(x).$

Define the ideal $I=(p_{1},\dots,p_{m})$, and let
$X=\operatorname{Spec}\mathbb{F}_{2}[T_{1},\dots,T_{n}]/I$. By Lemma 3.1, we
can safely assume that the varieties $Y$ and $X$ have the same set of
$\mathbb{F}_{2}$-valued points. If we define
$X_{i}=\operatorname{Spec}\mathbb{F}_{2}[T_{1},\dots,T_{n}]/(p_{i})$ then
$X=X_{1}\cap\cdots\cap X_{m}$.

Since $p_{i}\in I_{d,A}$, we have $Y\subseteq X_{i}$ for all $i=1,\dots,m$,
and therefore, by Fact 3.3,

$Y=T_{x}Y\subseteq T_{x}X_{i},\quad i=1,\dots,m.$

From this and Fact 3.4 we obtain

$Y\subseteq T_{x}X_{1}\cap\cdots\cap T_{x}X_{m}=T_{x}X.$ (2)

We prove that equality holds in (2) with high probability.

######  Proposition 3.6.

We have $\Pr[Y=T_{x}X]=1-2^{-\Omega(n)}$ in (2).

###### Proof.

Note that the tangent space $T_{x}X_{i}$ is given by the points on the
hyperplane $h_{i}=\sum_{j=1}^{n}(\partial p_{i}/\partial
T_{j})(x)(T_{j}-x_{j})$. Since $Y\subseteq T_{x}X_{i}$, we have $h_{i}\in
I_{1,A}$. We first prove the following claim.

Claim. For any $v\notin A$, exactly half of the elements in $I_{1,A}$ vanish
at $v$.

The claim can be proved using the same trick as in the proof of Lemma 3.1.
More precisely, there exists a $w=(w_{1},\dots,w_{n})\in A^{\perp}$ such that
$w\cdot v=1$, so for every $h\in I_{1,A}$ we also have
$\tilde{h}=h+w_{1}T_{1}+\cdots+w_{n}T_{n}\in I_{1,A}$. The claim now follows
from the fact that exactly one of the $h$ and $\tilde{h}$ vanish at $v$.

Suppose, for now, that the hyperplanes $T_{x}X_{i}$, or equivalently the
$w_{i}$, are uniformly random among the hyperplanes containing $Y$. Let
$v\notin A$. Then it follows from the above claim that $v\in
T_{x}X_{1}\cap\cdots\cap T_{x}X_{m}$ with probability $2^{-m}$, which prove
the proposition. So it remains to prove that the hyperplanes $w_{i}\in
I_{1,A}$ are uniformly random when the $p_{i}\in I_{d,A}$ are uniformly
random. Define the mapping

$\begin{array}[]{rrll}D_{x}:&I_{d,A}&\longrightarrow&I_{1,A}\\\
&f&\longmapsto&\displaystyle\sum_{j=1}^{n}\frac{\partial f}{\partial
T_{j}}(x)(T_{j}-x_{j}).\end{array}$

Since translation by a point of $A$ preserves $I_{d,A}$ and $I_{1,A}$, we may
assume that $x$ is the origin. In that case, the mapping $D_{x}$ sends a
polynomial $f\in I_{d,A}$ to its linear part. That means if we write $f=g+h$
where $\deg(h)\leq 1$ then $D_{x}(f)=h\in I_{1,A}$. Now if $f$ is uniformly
random then every monomial of $f$ is uniformly random (among the monomials
vanishing on $A$) and therefore, the linear part of $f$ is also uniformly
random. ∎

To summarize, the hidden subspace can be recovered using the following
algorithm.

1.A banknote $(s,\lvert A\rangle)$

2.A set of generators for the subspace $A$

3.Measure the state $\lvert A\rangle$ to obtain a uniformly random $x\in A$.

4.Compute the Jacobian matrix $J_{s}(x)$ of the set of polynomials $s$ at $x$.

5.Return a set of generators for the kernel of $J_{s}(x)$.

###  3.4 Example

To explain the idea of the algorithm of Section 3.3, we give a concrete step-
by-step example of the computation. The example is generated randomly over the
space $\mathbb{F}_{2}^{8}$, so $n=8$. Let $A\subset\mathbb{F}_{2}^{8}$ be a
random linear subspace of dimension $n/2=4$ generated by the rows of the
following random full rank $4\times 8$ matrix:

$A=\mathrm{Img}\begin{bmatrix}1&0&0&0&1&1&0&0\\\ 0&1&0&0&1&0&1&0\\\
0&0&1&0&1&0&1&1\\\ 0&0&0&1&1&0&0&1\end{bmatrix}.$

Then $A$ is the set of $\mathbb{F}_{2}$-valued points of the linear variety
given by the ideal $(H_{1},H_{2},H_{3},H_{4})$ where

$\displaystyle H_{1}(T)$ $\displaystyle=T_{1}+T_{6}$ $\displaystyle H_{2}(T)$
$\displaystyle=T_{2}+T_{5}+T_{6}+T_{8}$ $\displaystyle H_{3}(T)$
$\displaystyle=T_{3}+T_{5}+T_{6}+T_{7}+T_{8}$ $\displaystyle H_{4}(T)$
$\displaystyle=T_{4}+T_{5}+T_{6}+T_{7}$

If we set $\beta=9/8$ then $m=\beta n=9$. Let $p_{1},p_{2},\dots,p_{9}\in
I_{3,A}$ be the following polynomials chosen uniformly at random.

$p_{1}(T)=$ |  $T_{1}T_{3}^{2}+T_{2}T_{3}^{2}+T_{1}^{2}T_{4}+T_{1}T_{3}T_{5}+T_{2}T_{4}T_{5}+T_{2}T_{3}T_{6}+T_{3}^{2}T_{6}+T_{1}T_{4}T_{6}+T_{3}T_{5}T_{6}+T_{2}T_{3}T_{7}+T_{2}T_{3}T_{8}+T_{1}T_{5}T_{8}+T_{2}T_{5}T_{8}+T_{4}T_{5}T_{8}+T_{5}^{2}T_{8}+T_{4}T_{7}T_{8}+T_{6}T_{7}T_{8}+T_{7}^{2}T_{8}+T_{1}T_{2}+T_{1}T_{5}+T_{1}T_{6}+T_{2}T_{6}+T_{5}T_{6}+T_{6}^{2}+T_{1}T_{8}+T_{6}T_{8}+T_{2}+T_{5}+T_{6}+T_{8}$
---|---
$p_{2}(T)=$ |  $T_{1}T_{3}T_{4}+T_{1}T_{3}T_{5}+T_{3}T_{4}T_{5}+T_{4}T_{5}^{2}+T_{1}T_{3}T_{6}+T_{3}^{2}T_{6}+T_{3}T_{5}T_{6}+T_{4}T_{5}T_{6}+T_{1}T_{6}^{2}+T_{3}T_{6}^{2}+T_{6}^{3}+T_{1}T_{3}T_{7}+T_{4}T_{5}T_{7}+T_{3}T_{6}T_{7}+T_{2}T_{5}T_{8}+T_{4}T_{5}T_{8}+T_{5}^{2}T_{8}+T_{3}T_{6}T_{8}+T_{5}T_{6}T_{8}+T_{3}T_{7}T_{8}+T_{5}T_{7}T_{8}+T_{6}T_{7}T_{8}+T_{7}^{2}T_{8}+T_{5}T_{8}^{2}+T_{7}T_{8}^{2}+T_{1}T_{2}+T_{2}T_{6}+T_{4}T_{6}+T_{5}T_{6}+T_{6}^{2}+T_{6}T_{7}+T_{1}T_{8}+T_{6}T_{8}+T_{3}+T_{5}+T_{6}+T_{7}+T_{8}$
$p_{3}(T)=$ |  $T_{2}T_{3}T_{5}+T_{3}T_{5}^{2}+T_{2}^{2}T_{6}+T_{1}T_{5}T_{6}+T_{2}T_{5}T_{6}+T_{3}T_{5}T_{6}+T_{4}T_{5}T_{6}+T_{5}^{2}T_{6}+T_{2}T_{6}^{2}+T_{2}T_{5}T_{7}+T_{5}^{2}T_{7}+T_{1}T_{6}T_{7}+T_{6}^{2}T_{7}+T_{3}T_{7}^{2}+T_{5}T_{7}^{2}+T_{6}T_{7}^{2}+T_{7}^{3}+T_{3}T_{5}T_{8}+T_{2}T_{6}T_{8}+T_{5}T_{7}T_{8}+T_{7}^{2}T_{8}+T_{4}T_{6}+T_{5}T_{6}+T_{6}^{2}+T_{6}T_{7}+T_{3}+T_{5}+T_{6}+T_{7}+T_{8}$
$p_{4}(T)=$ |  $T_{1}T_{2}T_{4}+T_{1}T_{2}T_{5}+T_{2}T_{5}^{2}+T_{3}T_{5}^{2}+T_{1}^{2}T_{6}+T_{1}T_{2}T_{6}+T_{1}T_{5}T_{6}+T_{2}T_{6}^{2}+T_{1}T_{2}T_{7}+T_{3}T_{4}T_{7}+T_{4}T_{5}T_{7}+T_{5}^{2}T_{7}+T_{4}T_{6}T_{7}+T_{4}T_{7}^{2}+T_{3}^{2}T_{8}+T_{3}T_{5}T_{8}+T_{1}T_{6}T_{8}+T_{2}T_{6}T_{8}+T_{3}T_{6}T_{8}+T_{5}T_{6}T_{8}+T_{6}^{2}T_{8}+T_{3}T_{7}T_{8}+T_{4}T_{7}T_{8}+T_{3}T_{8}^{2}+T_{6}T_{8}^{2}+T_{3}T_{5}+T_{5}^{2}+T_{5}T_{6}+T_{4}T_{7}+T_{6}T_{7}+T_{7}^{2}+T_{5}T_{8}$
$p_{5}(T)=$ |  $T_{2}^{3}+T_{2}T_{3}^{2}+T_{2}T_{3}T_{4}+T_{1}T_{4}^{2}+T_{2}T_{4}^{2}+T_{4}^{3}+T_{2}^{2}T_{5}+T_{1}T_{2}T_{6}+T_{2}^{2}T_{6}+T_{4}^{2}T_{6}+T_{1}T_{5}T_{6}+T_{1}T_{6}^{2}+T_{1}T_{2}T_{7}+T_{4}^{2}T_{7}+T_{1}T_{5}T_{7}+T_{1}T_{6}T_{7}+T_{4}T_{7}^{2}+T_{5}T_{7}^{2}+T_{6}T_{7}^{2}+T_{7}^{3}T_{2}^{2}T_{8}+T_{2}T_{3}T_{8}+T_{4}^{2}T_{8}+T_{1}T_{5}T_{8}+T_{3}T_{6}T_{8}+T_{1}T_{8}^{2}$
$p_{6}(T)=$ |  $T_{1}T_{3}^{2}+T_{2}^{2}T_{4}+T_{2}T_{4}T_{5}+T_{1}T_{3}T_{6}+T_{2}T_{4}T_{6}+T_{3}T_{5}T_{6}+T_{1}T_{3}T_{7}+T_{4}T_{5}T_{7}+T_{5}^{2}T_{7}+T_{5}T_{6}T_{7}+T_{5}T_{7}^{2}+T_{1}T_{3}T_{8}+T_{2}T_{4}T_{8}+T_{3}T_{8}^{2}+T_{5}T_{8}^{2}+T_{6}T_{8}^{2}+T_{7}T_{8}^{2}+T_{8}^{3}+T_{1}T_{3}+T_{2}T_{6}+T_{1}T_{7}+T_{2}T_{8}+T_{5}T_{8}+T_{6}T_{8}+T_{8}^{2}$
$p_{7}(T)=$ |  $T_{1}^{2}T_{2}+T_{3}^{3}+T_{2}^{2}T_{5}+T_{2}T_{3}T_{5}+T_{3}^{2}T_{5}+T_{4}^{2}T_{5}+T_{2}T_{5}^{2}+T_{1}T_{2}T_{6}+T_{1}T_{3}T_{6}+T_{3}^{2}T_{6}+T_{2}T_{5}T_{6}+T_{2}T_{6}^{2}+T_{3}T_{6}^{2}+T_{5}T_{6}^{2}+T_{6}^{3}+T_{3}T_{6}T_{7}+T_{3}T_{7}^{2}+T_{3}^{2}T_{8}+T_{2}T_{5}T_{8}+T_{3}T_{5}T_{8}+T_{4}T_{5}T_{8}+T_{6}^{2}T_{8}+T_{3}T_{7}T_{8}+T_{4}T_{7}T_{8}+T_{5}T_{7}T_{8}+T_{6}T_{7}T_{8}+T_{7}^{2}T_{8}+T_{1}T_{4}+T_{4}T_{6}+T_{1}T_{8}+T_{6}T_{8}$
$p_{8}(T)=$ |  $T_{1}T_{2}T_{3}+T_{2}T_{4}^{2}+T_{2}T_{3}T_{5}+T_{4}^{2}T_{5}+T_{3}T_{5}^{2}+T_{2}T_{3}T_{6}+T_{4}^{2}T_{6}+T_{3}T_{5}T_{6}+T_{2}T_{5}T_{7}+T_{5}^{2}T_{7}+T_{5}T_{6}T_{7}+T_{4}T_{7}^{2}+T_{5}T_{7}^{2}+T_{6}T_{7}^{2}+T_{7}^{3}+T_{4}^{2}T_{8}+T_{3}T_{5}T_{8}+T_{2}T_{6}T_{8}+T_{3}T_{6}T_{8}+T_{1}T_{7}T_{8}+T_{5}T_{7}T_{8}+T_{3}T_{5}+T_{5}^{2}+T_{5}T_{6}+T_{3}T_{7}+T_{6}T_{7}+T_{7}^{2}+T_{5}T_{8}+T_{7}T_{8}$
$p_{9}(T)=$ |  $T_{1}T_{4}^{2}+T_{3}T_{4}^{2}+T_{1}T_{4}T_{5}+T_{2}T_{4}T_{5}+T_{4}^{2}T_{5}+T_{4}T_{5}^{2}+T_{1}T_{4}T_{6}+T_{4}^{2}T_{6}+T_{4}T_{5}T_{6}+T_{1}^{2}T_{7}+T_{2}T_{3}T_{7}+T_{1}T_{4}T_{7}+T_{3}T_{4}T_{7}+T_{4}^{2}T_{7}+T_{2}T_{5}T_{7}+T_{3}T_{5}T_{7}+T_{4}T_{5}T_{7}+T_{5}^{2}T_{7}+T_{1}T_{6}T_{7}+T_{2}T_{6}T_{7}+T_{3}T_{6}T_{7}+T_{5}T_{6}T_{7}+T_{2}T_{7}^{2}+T_{3}T_{7}^{2}+T_{5}T_{7}^{2}+T_{1}T_{2}T_{8}+T_{4}^{2}T_{8}+T_{4}T_{5}T_{8}+T_{5}T_{6}T_{8}+T_{6}^{2}T_{8}+T_{2}T_{7}T_{8}+T_{1}T_{8}^{2}$

Let $x=(0,1,0,1,0,0,1,1)\in A$ be a uniformly random element, which is
obtained by measuring the given money state. Evaluating the Jacobian
$J_{p_{1},\dots,p_{9}}$ at $x$ gives

$J_{p_{1},\dots,p_{9}}(x)=\begin{bmatrix}0&1&0&1&0&0&1&1\\\ 0&0&0&0&0&0&0&0\\\
0&0&0&0&0&0&0&0\\\ 0&0&1&1&0&0&0&1\\\ 1&0&0&0&0&1&0&0\\\ 1&0&1&0&1&0&1&1\\\
0&0&0&1&1&1&1&0\\\ 1&1&1&1&1&0&0&0\\\ 0&0&0&0&0&0&0&0\end{bmatrix}$

Now, the kernel of the above matrix gives us the subspace $A$.

##  4 Quantum Money From Multivariate Hash Functions

In this section, we investigate the security of the quantum money scheme
proposed in [29], which is based on multivariate hash functions. The hash
functions used in this scheme are defined as follows. Let $m$ and $n$ be
positive integers such that $m>n$. Define $\mathcal{A}=\\{\bm{A}_{i}\\}_{1\leq
i\leq n}$ where each $\bm{A}_{i}\in\mathbb{F}_{2}^{m\times m}$ is an upper
triangular matrix. The hash function corresponding to $\mathcal{A}$ is defined
by

$\begin{array}[]{rrll}f_{\mathcal{A}}:&\mathbb{F}_{2}^{m}&\longrightarrow&\mathbb{F}_{2}^{n}\\\
&x&\longmapsto&(x^{T}\bm{A}_{1}x,\dots,x^{T}\bm{A}_{n}x).\end{array}$

The function $f_{\mathcal{A}}$ is not collision resistant [9], and in fact it
is not hard to find collisions when the matrices $\bm{A}_{i}$ are random upper
triangular.

The hardness assumption underlying this scheme is instead based on the multi-
collision resistance of $f_{\mathcal{A}}$. Let us briefly define what that
means. A set of $k+1$ points of $\mathbb{F}_{2}^{m}$ is called non-affine if
they form a $k$-dimensional affine space. A function $f$ is said to be
$(k+1)$-non-affine multi-collision resistant ($(k+1)$-NAMCR) if it is hard to
find $k+1$ non-affine colliding inputs for $f$. The assumption is that for
$k=\operatorname{poly}(n)$, $m<(k+1/2)n$ and random upper triangular
$\bm{A}_{i}$, the function $f_{\mathcal{A}}$ is $2(k+1)$-NAMCR.

###  4.1 The quantum money scheme

In the following, we briefly explain the quantum money scheme of [29]. The
public parameters of the scheme are:

  * •

The integers $m,n$. We set $n=\kappa$ where $\kappa$ is the security
parameter. For the verification to work we can take $k=2n$ and $m=kn=2n^{2}$.

  * •

The hash function $f_{\mathcal{A}}$. The upper triangular matrices in
$\mathcal{A}=\\{\bm{A}_{i}\\}_{1\leq i\leq n}$ are generated uniformly at
random.

A banknote in this scheme consists of a pair
$(y,\lvert\text{\Lightning}_{y}\rangle)$ where
$\lvert\text{\Lightning}_{y}\rangle$, called a bolt, is the money state and
$y\in\mathbb{F}_{2}^{n}$ is the serial number. The bolt
$\lvert\text{\Lightning}_{y}\rangle$ is a product of states where each state
is a superposition of all $x\in\mathbb{F}_{2}^{m}$ such that
$f_{\mathcal{A}}(x)=y$. More precisely,

$\lvert\text{\Lightning}_{y}\rangle\propto\lvert\text{\Lightning}_{y}^{\prime}\rangle^{\otimes(k+1)},\quad\text{where
}\lvert\text{\Lightning}_{y}^{\prime}\rangle\propto\sum_{x:f_{\mathcal{A}}(x)=y}\lvert
x\rangle.$

We refer the reader to [29] for the details of how a bolt is generated. Since
we will use the verification circuit in our attack, we include some details
here. To verify a bolt, one needs to only verify each of the states
$\lvert\text{\Lightning}_{y}^{\prime}\rangle$ independently. The verification
of an alleged banknote $\lvert\psi\rangle$ proceeds in two steps: first, the
state $\lvert\psi\rangle$ is projected onto the span of the states
$\\{\lvert\text{\Lightning}_{z}^{\prime}\rangle\\}_{z\in\mathbb{F}_{2}^{n}}$.
Then the function $f_{\mathcal{A}}$ is computed into an auxiliary register and
measured. The result of the measurement is then compared against $y$ to
determine the validity of the banknote.

The states
$\\{\lvert\text{\Lightning}_{z}^{\prime}\rangle\\}_{z\in\mathbb{F}_{2}^{n}}$
are orthogonal and span a linear subspace $B\subset\mathbb{C}^{2^{m}}$ of
dimension $2^{n}$. To project onto $B$, a different set of basis states of $B$
are used.

######  Fact 4.1 ([29]).

Define the set of states

$\lvert\phi_{r}\rangle=\frac{1}{2^{m/2}}\sum_{x\in\mathbb{F}_{2}^{m}}(-1)^{r\cdot
f_{\mathcal{A}}(x)}\lvert x\rangle,\quad r\in\mathbb{F}_{2}^{n}.$

Then the states $\\{\lvert\text{\Lightning}_{z}^{\prime}\rangle\\}$ and
$\\{\lvert\phi_{r}\rangle\\}$ span the same subspace $B$.

Therefore, to project onto $B$ we need to project onto the span of the states
$\lvert\phi_{r}\rangle$. It is easy to prepare $\lvert\phi_{r}\rangle$ given
$r$. Conversely, it was shown in [29] that one can recover $r$ given the state
$\lvert\phi_{r}\rangle$. We record this result for sake of later reference.

######  Theorem 4.2 ([29]).

There is a polynomial time quantum algorithm that, given the state
$\lvert\phi_{r}\rangle$, computes $r$ with overwhelming probability.

The verification procedure can now be summarized as follows. Given the input
state $\lvert\psi\rangle$, write
$\lvert\psi\rangle=\sum_{r}\alpha_{r}\lvert\phi_{r}\rangle+\lvert\psi_{1}\rangle$
where $\lvert\psi_{1}\rangle$ is orthogonal to $B$. Then compute $r$ into an
auxiliary register to obtain the state $\sum_{r}\alpha_{r}\lvert
r\rangle\lvert\phi_{r}\rangle+\lvert\psi_{2}\rangle$ for some state
$\lvert\phi_{2}\rangle$. Now uncompute the second register to obtain the state
$\sum_{r}\alpha_{r}\lvert r\rangle\lvert 0\rangle+\lvert\psi_{3}\rangle$ for
some state $\lvert\phi_{3}\rangle$. The verification algorithm then measures
the second register. If the measurement outcome is not zero the algorithm
outputs ‘reject’. Otherwise, the post-measurement state is
$\sum_{r}\alpha_{r}\lvert r\rangle\lvert 0\rangle$, and the algorithm computes
$\lvert\phi_{r}\rangle$ into the second register to obtain the state
$\sum_{r}\alpha_{r}\lvert r\rangle\lvert\phi_{r}\rangle$, and uncomputes $r$
to obtain the state $\sum_{r}\alpha_{r}\lvert\phi_{r}\rangle$. Note that this
state is now the projection of the original state $\lvert\psi\rangle$ onto
$B$. Finally, the algorithm computes $f_{\mathcal{A}}$ into another register
and measures that register. If the measurement outcome is not equal to $y$,
the algorithm outputs ‘reject’, otherwise it outputs ‘accept’.

###  4.2 Cryptanalysis

In this section, we propose a polynomial time quantum algorithm that given a
nonzero serial number $y\in\mathbb{F}_{2}^{n}$, generates a copy of the state

$\lvert\text{\Lightning}_{y}^{\prime}\rangle=\frac{1}{\sqrt{C_{y}}}\sum_{x:f_{\mathcal{A}}(x)=y}\lvert
x\rangle,$

where $C_{y}=\\#\\{x\in\mathbb{F}_{2}^{m}:f_{\mathcal{A}}(x)=y\\}$, with
probability $1$. We start by noting that [29]

$C_{0}\lvert\text{\Lightning}_{0}^{\prime}\rangle+C_{y}\lvert\text{\Lightning}_{y}^{\prime}\rangle\propto\sum_{r:r\cdot
y=0}\lvert\phi_{r}\rangle.$ (3)

Let $\lvert\psi_{y}\rangle$ be the normalized quantum state proportional to
the state (3). Then $\lvert\psi_{y}\rangle$ is a uniform superposition over
the elements of $X_{y}=\\{x\in\mathbb{F}_{2}^{m}:f_{\mathcal{A}}(x)=0\text{ or
}y\\}$, i.e.,

$\lvert\psi_{y}\rangle=\frac{1}{\sqrt{\\#X_{y}}}\sum_{x\in X_{y}}\lvert
x\rangle.$

Suppose there is a quantum algorithm $Q$ that, given $y$, can efficiently
prepare $\lvert\psi_{y}\rangle$. To generate a copy of
$\lvert\text{\Lightning}_{y}^{\prime}\rangle$, perform the following steps.
Call $Q$ to get a copy of $\lvert\psi_{y}\rangle$. Compute $f_{\mathcal{A}}$
into an extra register to obtain the state

$\frac{1}{\sqrt{\\#X_{y}}}\sum_{x\in X_{y}}\lvert x\rangle\lvert
f_{\mathcal{A}}(x)\rangle=\frac{1}{\sqrt{\\#X_{y}}}(\sqrt{C_{0}}\lvert\text{\Lightning}_{0}^{\prime}\rangle\lvert
0\rangle+\sqrt{C_{y}}\lvert\text{\Lightning}_{y}^{\prime}\rangle\lvert
y\rangle),$ (4)

and measure the second register. If the measurement outcome is equal to $y$
then we are done, otherwise repeat the process from the beginning.

The probability of obtaining the state
$\lvert\text{\Lightning}_{y}^{\prime}\rangle$ is $C_{y}/\\#X_{y}$.
Heuristically, the ratio $C_{y}/\\#X_{y}$ is as large as a constant. In other
words, there is no reason that $C_{0}$ is much larger or smaller than $C_{y}$
for any other $y\in\mathbb{F}_{2}^{n}$. We argue, with a little help from
algebraic geometry, that this is indeed the case. The function
$f_{\mathcal{A}}$ defines a morphism between two affine spaces
$f_{\mathcal{A}}:\mathbb{A}_{\mathbb{F}_{2}}^{m}\rightarrow\mathbb{A}_{\mathbb{F}_{2}}^{n}$
where
$\mathbb{A}_{\mathbb{F}_{2}}^{m}=\operatorname{Spec}\mathbb{F}_{2}[T_{1},\dots,T_{m}]$,
and similarly for $\mathbb{A}_{\mathbb{F}_{2}}^{n}$. Since both
$\mathbb{A}_{\mathbb{F}_{2}}^{m}$ and $\mathbb{A}_{\mathbb{F}_{2}}^{m}$ are
geometrically irreducible, and since $0$ is the generic point of these spaces,
it follows from the fibre dimension theorem [12, Chapter 14 ] that $\dim
f_{\mathcal{A}}^{-1}(0)=\dim\mathbb{A}_{\mathbb{F}_{2}}^{m}-\dim\mathbb{A}_{\mathbb{F}_{2}}^{n}=m-n$111Here,
the dimension is the geometric dimension not the vector space dimension. We
also have that for every $y\in\mathbb{F}_{2}^{n}$, all irreducible components
of $f_{\mathcal{A}}^{-1}(y)$ have dimension at least $\dim
f_{\mathcal{A}}^{-1}(0)$. Now, by the Lang-Weil theorem [18], [22, Section
7.7], for any $y\in\mathbb{F}_{2}^{n}$ it holds that
$\\#f_{\mathcal{A}}^{-1}(y)(\mathbb{F}_{2})=O(2^{\dim
f_{\mathcal{A}}^{-1}(y)})$ where the constant depends on $f_{\mathcal{A}}$ but
not on $y$. This means the ratio

$\frac{C_{y}}{\\#X_{y}}=\frac{\\#f_{\mathcal{A}}^{-1}(y)}{\\#f_{\mathcal{A}}^{-1}(y)+\\#f_{\mathcal{A}}^{-1}(0)}$

is bounded below by a constant with overwhelming probability over the
randomness of $\mathcal{A}$.

It only remains to show that algorithm $Q$ exists. The input to the algorithm
is an element $y\in\mathbb{F}_{2}^{n}$ and the output is the state (3). The
algorithm proceeds as follows. First, compute a basis for the space
$\\{r\in\mathbb{F}_{2}^{n}:r\cdot y=0\\}$. This can be efficiently done
classically. Then using this basis, generate the superposition

$\frac{1}{\sqrt{2^{n-1}}}\sum_{r:r\cdot y=0}\lvert r\rangle.$ (5)

Next, compute $\lvert\phi_{r}\rangle$ into another register to obtain the
state

$\frac{1}{\sqrt{2^{n-1}}}\sum_{r:r\cdot y=0}\lvert
r\rangle\lvert\phi_{r}\rangle.$ (6)

Using Theorem 4.2, uncompute $r$ and discard the first register. This produces
the state

$\lvert\psi_{y}\rangle=\frac{1}{\sqrt{C}}\sum_{r:r\cdot
y=0}\lvert\phi_{r}\rangle,$ (7)

for an appropriate normalization constant $C$. The above algorithm is
summarized as follows.

1.A serial number $y\in\mathbb{F}_{2}^{n}$

2.A bolt $\lvert\text{\Lightning}_{y}^{\prime}\rangle$

3.Compute a set $G$ of generators for the kernel linear map $r\mapsto r\cdot
y$.

4.Using $G$ prepare the superposition (5).

5.Compute $\lvert\phi_{r}\rangle$ into another register to obtain the state
(6).

6.Uncompute $r$ and discard the first register to obtain the state (7).

7.Compute $f_{\mathcal{A}}$ into an extra register to obtain the state (4).

8.Measure the second register. If the measurement outcome is equal to $y$ then
return the post-measurement state. Otherwise, go to Step 4.

##  5 Quantum Money from Quaternion Algebras

In this section, we investigate the security of the quantum money scheme
proposed in [14], which is based on quaternion algebras. The hard problem
underlying this scheme is copying a quantum state that is encoding an
eigenform of the Hecke operators. We give a reduction from this problem to a
linear algebra problem, namely inverting a matrix with entries the
representation numbers of quaternary quadratic forms. We believe that the
latter problem is more suitable, and much more accessible, for future
cryptanalysis.

Informally, the idea of our reduction is as follows. Suppose the quantum state
to be copied is given by $\lvert\phi\rangle=\sum\alpha_{I}\lvert I\rangle$
where the sum is over the set $\\{I\\}_{I\in\operatorname{Cl}(\mathcal{O})}$
of representatives of the left ideal classes of a maximal order $\mathcal{O}$
in a quaternion algebra. Let $M$ be the formal abelian group with basis
$\operatorname{Cl}(\mathcal{O})$. For a fixed
$J\in\operatorname{Cl}(\mathcal{O})$, based on a morphism from $M$ to the
space of modular forms we obtain the identity

$f(q)=\sum_{I\in\operatorname{Cl}(\mathcal{O})}\frac{\alpha_{I}}{\alpha_{J}}\Theta_{I,J}(q),$

where the left hand side is the modular form corresponding to the formal sum
$\sum_{I\in\operatorname{Cl}(\mathcal{O})}\alpha_{I}[I]$, and the
$\Theta_{I,J}$ are theta series corresponding to the ideals $I,J$. By equating
the coefficients of different powers of $q$ in both sides of the above
identity, we form a system of linear equations. The entries of the coefficient
matrix $A$ associated with this system are the representation numbers from the
theta series $\Theta_{I,J}$. The dimension of the system is equal to the size
of the set $\operatorname{Cl}(\mathcal{O})$ which is exponentially large. We
show that if one is able to approximate the operation $A^{-1}$ then one can
make arbitrary many copies of $\lvert\phi\rangle$.

###  5.1 Background

In this section, we review the minimal necessary background in modular forms
and quaternion algebras, and set up some notations, for the following
sections. Our main references for modular forms are [8, 17, 24]. For a
comprehensive treatment of quaternion algebras we refer the reader to [26].

####  5.1.1 Modular forms.

Let $\mathbb{H}=\\{z\in\mathbb{C}:\mathrm{Im}(z)>0\\}$ be the complex upper
half plane, and let $\mathrm{SL}_{2}(\mathbb{Z})$ be the special linear group
over the integers. For $\gamma=\begin{bmatrix}a&b\\\
c&d\end{bmatrix}\in\mathrm{SL}_{2}(\mathbb{Z})$ and $z\in\mathbb{H}$ define
$\gamma z=(az+b)/(cz+d)$, which defines a group action on $\mathbb{H}$. For
any integer $N>0$ denote by $\Gamma(N)$ the kernel of the projection
$\mathrm{SL}_{2}(\mathbb{Z})\rightarrow\mathrm{SL}_{2}(\mathbb{Z}/N\mathbb{Z})$.
A congruence subgroup of $\mathrm{SL}_{2}(\mathbb{Z})$ of level $N$ is any
subgroup $\Gamma$ containing $\Gamma(N)$. In this paper, we are particularly
interested in the congruence subgroup

$\Gamma_{0}(N)=\left\\{\begin{bmatrix}a&b\\\
c&d\end{bmatrix}\in\mathrm{SL}_{2}(\mathbb{Z}):\begin{bmatrix}a&b\\\
c&d\end{bmatrix}\equiv\begin{bmatrix}*&*\\\
0&*\end{bmatrix}\pmod{N}\right\\}.$

The weight-$k$ operator $[\gamma]_{k}$ on the functions
$f\in\operatorname{Hom}(\mathbb{H},\mathbb{C})$ is defined by
$(f[\gamma]_{k})(\tau)=(cz+d)^{-k}f(\gamma z)$. This is also a group action on
$\operatorname{Hom}(\mathbb{H},\mathbb{C})$ since
$f[\gamma_{1}\gamma_{2}]_{k}=(f[\gamma_{1}]_{k})[\gamma_{2}]_{k}$.

A weakly modular function of weight $k$ with respect to a congruence subgroup
$\Gamma$ is a meromorphic function $f:\mathbb{H}\rightarrow\mathbb{C}$ such
that $f[\gamma]_{k}=f$ for all $\gamma\in\Gamma$. Define the extended upper
half plane $\mathbb{H}^{*}$ by adding the set of rational points of the
projective line to $\mathbb{H}$, i.e.,
$\mathbb{H}^{*}=\mathbb{H}\cup\mathbb{P}^{1}(\mathbb{Q})$. A modular form of
weight $k$ with respect to $\Gamma$ is a weakly modular function
$f:\mathbb{H}\rightarrow\mathbb{C}$ that is holomorphic on $\mathbb{H}^{*}$.
Every modular form $f$ has a Fourier expansion

$f(z)=\sum_{n=0}^{\infty}a_{n}q^{n},\quad q(z)=e^{2\pi iz}$

called the $q$-expansion of $f$. If $a_{0}=0$ in the $q$-expansion of $f$, we
say that $f$ is a cuspform.

####  5.1.2 Quaternion algebras.

Let $F$ be a field of characteristic $\neq 2$. An $F$-algebra $B$ is called a
quaternion algebra if $B$ has a basis $1,i,j,k$ as an $F$-vector space such
that $i^{2}=a,j^{2}=b$ and $k=ij=-ji$ for some $a,b\in F^{\times}$. There is
an involution operation ${}^{-}:B\rightarrow B$ defined by $t+xi+yj+zk\mapsto
t-xi-yj-zk$. The reduced trace $\mathrm{trd}:B\rightarrow F$ and the reduced
norm $\mathrm{nrd}:B\rightarrow F$ are defined by
$\operatorname{trd}(\alpha)=\alpha+\overline{\alpha}$ and
$\operatorname{nrd}(\alpha)=\alpha\overline{\alpha}$. For $F=\mathbb{Q}$, a
quaternion algebra $B$ is said to be ramified at a prime $p$ if the completion
$B\otimes_{\mathbb{Q}}\mathbb{Q}_{p}$ is a division ring, otherwise $B$ is
unramified at $p$. In this paper, we are interested in the quaternion algebra
$B$ over $\mathbb{Q}$, denoted by $\mathcal{B}_{p,\infty}$, that is ramified
at a single primes $p$ and at $\infty$.

A $\mathbb{Z}$-lattice $I\subseteq\mathcal{B}_{p,\infty}$ of rank $4$ is
called a fractional ideal. A $\mathbb{Z}$-order (or simply an order)
$\mathcal{O}\subset\mathcal{B}_{p,\infty}$ is a fractional ideal that is also
a ring. A maximal order is an order that is not properly contained in another
order. For a fractional ideal $I\subseteq\mathcal{B}_{p,\infty}$ define

$\mathcal{O}_{L}(I)=\\{\alpha\in\mathcal{B}_{p,\infty}:\alpha I\subseteq
I\\}.$

Then $\mathcal{O}_{L}(I)$ is also an order and is called the left order of
$I$. The right order of $I$ is defined similarly by
$\mathcal{O}_{R}(I)=\\{\alpha\in\mathcal{B}_{p,\infty}:I\alpha\subseteq I\\}$.
An ideal $I$ is invertible if there is another ideal $I^{\prime}$ such that
$II^{\prime}=\mathcal{O}_{L}(I)=\mathcal{O}_{R}(I^{\prime})$ and
$I^{\prime}I=\mathcal{O}_{L}(I^{\prime})=\mathcal{O}_{R}(I)$. We denote the
inverse of $I$, if it exists, by $I^{-1}$. The reduced norm of an ideal $I$ is
a $\mathbb{Z}$-submodule of $\mathbb{Q}$ generated by the set
$\\{\operatorname{nrd}(\alpha):\alpha\in I\\}$. The inverse of $I$ can also be
written as $I^{-1}=\overline{I}\operatorname{nrd}(I)^{-1}$ where
$\overline{I}=\\{\overline{\alpha}:\alpha\in I\\}$ is the involution of $I$.
For an order $\mathcal{O}\subseteq\mathcal{B}_{p,\infty}$, A left fractional
$\mathcal{O}$-ideal is a fractional ideal $I$ such that
$\mathcal{O}\subseteq\mathcal{O}_{L}(I)$. Right fractional
$\mathcal{O}$-ideals are defined similarly.

Two fractional ideals $I,J$ are said to be in the same right class if
$I=\alpha J$ for some $\alpha\in\mathcal{B}_{p,\infty}^{\times}$, in which
case we write $I\sim_{R}J$. The relation $\sim_{R}$ defines an equivalence
relation on the set of fractional ideals, and a class of an ideal $I$ is
denoted by $[I]_{R}$. Left equivalence classes are defined similarly. For an
order $\mathcal{O}\subset\mathcal{B}_{p,\infty}$, the right class set of
$\mathcal{O}$ is defined as the isomorphism classes of invertible right
$\mathcal{O}$-ideals, i.e.,

$\operatorname{Cl}_{R}(\mathcal{O})=\\{[I]_{R}:I\text{ an invertible
}\mathcal{O}\text{-ideal}\\}.$

Since the mapping $I\mapsto\overline{I}$ defines a bijection between left and
right classes we often simply write $\operatorname{Cl}(\mathcal{O})$ instead
of $\operatorname{Cl}_{R}(\mathcal{O})$.

####  5.1.3 Hecke operators.

Denote by $M_{k}(\Gamma_{0}(N))$ the space of modular forms of weight $k$ with
respect to the subgroup $\Gamma_{0}(N)$, and denote by $S_{k}(\Gamma_{0}(N))$
the space of cuspforms of weight $k$ with respect to $\Gamma_{0}(N)$. For an
integer $n$ with $(n,N)=1$, the $n$-th Hecke operator on
$M_{k}(\Gamma_{0}(N))$ is the linear operator

$\begin{array}[]{rrll}T_{n}:&M_{k}(\Gamma_{0}(N))&\longrightarrow&M_{k}(\Gamma_{0}(N))\\\
&f(z)&\longmapsto&\displaystyle\frac{1}{n^{k-1}}\sum_{\begin{subarray}{c}ad=n\\\
0\leq
b<d\end{subarray}}\frac{1}{d^{k}}f\left(\frac{az+b}{d}\right)\end{array}$

We will always assume that $(n,N)=1$, since this is what we are interested in,
and also the theory is a bit simpler in this case. From the definition, we see
that $T_{n}$ preserves the subspace $S_{k}(\Gamma_{0}(N))$. The Hecke
operators for $M_{k}(\Gamma_{0}(N))$ satisfy

$\displaystyle T_{mn}$ $\displaystyle=T_{m}T_{n}$ $\displaystyle(m,n)=1,$ (8)
$\displaystyle T_{p^{r+1}}$ $\displaystyle=T_{p^{r}}T_{p}-p^{k-1}T_{p^{r-1}}$
$\displaystyle p\text{ prime}.$

For a modular form $f$, let $a_{n}(f)$ be the $n$-th coefficient of the
$q$-expantion of $f$. Then for $f\in M_{k}(\Gamma_{0}(N))$ and prime $p$ we
have

$a_{n}(T_{p}f)=\begin{cases}a_{np}(f)+p^{k-1}a_{n/p}(f)&\text{if }p\mid n,\\\
a_{np}(f)&\text{if }p\nmid n.\end{cases}$ (9)

It follows that for coprime integers $m,n$ we have $a_{m}(T_{n}f)=a_{mn}(f)$,
and in particular, $a_{1}(T_{n}f)=a_{n}(f)$. Define
$\mathbb{T}:=\mathbb{Z}[\\{T_{n}\\}_{n\geq 1}]$, the algebra generated by all
the Hecke operators. Then $\mathbb{T}$ is a commutative ring called the Hecke
algebra. Since $\mathbb{T}$ is commutative, there are elements $f\in
S_{k}(\Gamma_{0}(N))$ that are simultaneous eigenvectors for all element in
$\mathbb{T}$. In particular, for any such $f$ we have $T_{n}f=\lambda_{n}f$
for some $\lambda_{n}\in\mathbb{C}^{\times}$. We refer to such $f$ as an
eigenfunction. If $f$ is normalized, i.e., $a_{1}(f)=1$, it is called an
eigenform. The coefficient of the $q$-expansion of an eigenform satisfy
important identities induced by (8). More precisely, let
$f=\sum_{n}a_{n}q^{n}$ be an eigenform, and assume $T_{n}f=\lambda_{n}f$. Then
we have $a_{n}=\lambda_{n}$, and using (8) we obtain

$\displaystyle a_{mn}$ $\displaystyle=a_{m}a_{n}$ $\displaystyle(m,n)=1,$ (10)
$\displaystyle a_{p^{r+1}}$ $\displaystyle=a_{p^{r}}a_{p}-p^{k-1}a_{p^{r-1}}$
$\displaystyle p\text{ prime}.$

Let $d\mu(z)=dxdy/y^{2}$, $z=x+iy\in\mathbb{H}$ be the hyperbolic measure, and
let $V_{\Gamma_{0}(N)}$ be volume of the modular curve $X(\Gamma_{0}(N)))$
with respect to $d\mu(z)$. The space $S_{k}(\Gamma_{0}(N))$ can be made into
an inner product space using the Petersson inner product

$\langle
f,g\rangle=\frac{1}{V_{\Gamma_{0}(N)}}\int_{X(\Gamma_{0}(N))}f(z)\overline{g(z)}(\mathrm{Im}(z))^{k}d\mu(z).$

The Hecke operators $T_{n}$ are Hermitian with respect to this inner product,
i.e., $\langle T_{n}f,g\rangle=\langle f,T_{n}g\rangle$. This means there
exists a basis of $S_{k}(\Gamma_{0}(N))$ consisting of Hecke eigenforms.

One can also define a set of Hecke operators on ideal classes of a quaternion
order as follows. Let $\mathcal{O}\subset\mathcal{B}_{p,\infty}$ be an order
and let $\operatorname{Cl}(\mathcal{O})$ be the (right) class set of
$\mathcal{O}$. Define the formal divisor group

$M=\bigoplus_{I\in\operatorname{Cl}(\mathcal{O})}\mathbb{Z}.[I]$ (11)

For an integer $n>0$, $n\neq p$, the $n$-th Hecke operator on $M$ is defined
by

$\begin{array}[]{rrll}T_{n}:&M&\longrightarrow&M\\\
&[I]&\longmapsto&\displaystyle\sum_{\begin{subarray}{c}J\subseteq I\\\
\operatorname{nrd}(JI^{-1})=n\end{subarray}}[J],\end{array}$

where the sum is over all invertible right $\mathcal{O}$-ideals contained in
$I$. In the basis of the ideal classes in $\operatorname{Cl}(\mathcal{O})$,
the Hecke operator $T_{n}$ is represented by the Brandt matrix $B(n)$ which
can be explicitly computed as follows. Let
$h=\\#\operatorname{Cl}(\mathcal{O})$ be the class number of $\mathcal{O}$,
and fix a set $I_{1},I_{2},\dots,I_{h}$ of representatives of the ideal
classes in $\operatorname{Cl}(\mathcal{O})$. Let
$\mathcal{O}_{i}=\mathcal{O}_{L}(I_{i})$, and let $w_{i}$ be the number of
units in $\mathcal{O}_{i}$. The $n$-th Brandt matrix is defined by

$B(n)_{ij}=\frac{1}{w_{i}}\\#\\{\alpha\in
I_{j}I_{i}^{-1}:\operatorname{nrd}(\alpha)=n\operatorname{nrd}(I_{j}I_{i}^{-1})\\}.$
(12)

The Hecke operators $T_{n}$ also satisfy the relations (8). Moreover, we can
define an inner product on $M$ with respect to which the $T_{n}$ are
Hermitian: $\langle[I_{i}],[I_{j}]\rangle=\delta_{i,j}w_{i}/2$ where
$\delta_{i,j}=1$ if $i=j$, and $\delta_{i,j}=0$ otherwise. We will also call
this inner product the Petersson inner product. Similar to the case of modular
forms, there is a set of elements of
$M_{\mathbb{R}}=M\otimes_{\mathbb{Z}}\mathbb{R}$ that are simultaneous
eigenvectors for all Hecke operators. We also call these element Hecke
eigenforms. The element

$\phi_{E}=\sum_{j=1}^{h}2w_{j}^{-1}[I_{j}]$

of $M_{\mathbb{R}}$ is called the Eisenstein eigenform. We have
$T_{n}\phi_{E}=\sigma^{\prime}(n)$, where $\sigma^{\prime}(n)=\sum_{d\mid
n,(p,d)=1}d$. The sub-$\mathbb{T}$-module of $M_{\mathbb{R}}$ orthogonal to
$\phi_{E}$ is called the space of cuspforms. For any cuspform
$\phi=\sum_{j=1}^{h}\alpha_{j}[I_{j}]$ we have $\sum_{j=1}^{h}\alpha_{j}=0$.

###  5.2 The quantum money scheme

Let us briefly review the quantum money scheme presented in [14]. The
parameters of the scheme are fixed as follows:

  * •

A prime $p\in O(2^{\kappa})$ where $\kappa$ is the security parameter.

  * •

The quaternion algebra $\mathcal{B}_{p,\infty}$ over $\mathbb{Q}$ ramified at
$p$ and $\infty$.

  * •

A maximal order $\mathcal{O}\subset\mathcal{B}_{p,\infty}$ of discriminant
$p$.

  * •

A set of Hecke operators $T_{n_{j}}$ where
$n_{j}=\operatorname{poly}(\kappa)$, $1\leq j\leq s$ and
$s=\operatorname{poly}(\kappa)$.

Let $I_{1},I_{2},\dots,I_{d}$ be distinct representatives of the ideal classes
in $\operatorname{Cl}(\mathcal{O})$, where
$d=\\#\operatorname{Cl}(\mathcal{O})$. In the above specific setup we have
$d=\lfloor p/12\rfloor$. Let $M$ be the formal divisor group on
$\operatorname{Cl}(\mathcal{O})$ defined in (11). For simplicity, we will let
$M_{\mathbb{C}}$ denote $M\otimes_{\mathbb{Z}}\mathbb{C}$. Let
$\\{\phi_{i}\\}_{1\leq i\leq d}$ be a set of eigenforms in $M_{\mathbb{C}}$
that are a basis of $M_{\mathbb{C}}$, and let
$\\{\lvert\phi_{i}\rangle\\}_{1\leq i\leq d}$ be the corresponding quantum
states. This means that for $\phi_{i}=\sum_{i}\alpha_{i}[I_{i}]$, we have

$\lvert\phi_{i}\rangle=\frac{1}{\sqrt{\alpha}}\sum_{j=1}^{d}\alpha_{j}\lvert
I_{j}\rangle$

where $\alpha^{2}=\sum_{j}\lvert\alpha_{j}\rvert^{2}$. A banknote in the
quantum money scheme consists of

  1. 1.

A money state of the form $\lvert\phi_{i}\rangle\lvert\phi_{i}\rangle$ for
some $1\leq i\leq d$,

  2. 2.

A serial number, which is a tuple $(b_{j})_{1\leq j\leq s}$ of approximate
eigenvalues of the $T_{n_{j}}$ corresponding to the eigenform $\phi_{i}$.

  3. 3.

A classical digital signature of the serial number $(b_{j})_{1\leq j\leq s}$.

The verification of a banknote is done by

  1. 1.

Verifying the signature of the serial number

  2. 2.

Using phase estimation on the operators $e^{iT_{n_{j}}}$ and the eigenstate
$\lvert\phi_{i}\rangle$ to recover an approximate serial number and compare
against $(b_{j})_{1\leq j\leq s}$.

It takes more than a few pages to give a precise account on the implementation
of the above scheme. Here, we briefly explain two main points.

Hamiltonian simulation.

To prepare an eigenstate $\lvert\phi_{i}\rangle$ we start from the uniform
superposition
$\lvert\phi\rangle=\sum_{I\in\operatorname{Cl}(\mathcal{O})}\lvert I\rangle$
(normalization omitted). Then we use phase estimation on the operators
$U_{j}=e^{iT_{n_{j}}}$ to project onto an eigenstate $\lvert\phi_{i}\rangle$.
Since the matrices of the operators $T_{n_{j}}$ are sparse, standard
Hamiltonian simulation techniques can be used to implement the unitaries
$U_{j}$. However, for an integer $t>0$, the cost of simulating
$U_{j}^{t}=e^{iT_{n_{j}}t}$ depends linearly on $t$. More precisely, the
simulation cost depends linearly on $st\lVert T_{n_{j}}\rVert_{\max}$ [4],
where $s$ is the sparsity degree of $T_{n_{j}}$, i.e., the maximum number of
nonzero entries in any row, and $\lVert T_{n_{j}}\rVert_{\max}$ is the largest
entry of $T_{n_{j}}$ in absolute value. This means, using phase estimation, we
can approximate the eigenvalues of the $T_{n_{j}}$ only to accuracy
$1/\operatorname{poly}(\kappa)$.

Projecting onto an eigenstate.

To be able to project onto a single eigenstate, we cannot use only one of the
$T_{n_{j}}$, since in that case we would need an exponentially accurate phase
estimation. However, if we run a polynomially accurate phase estimation for
all the $T_{n_{j}}$, we might be able to project onto a random eigenstate
$\lvert\phi_{i}\rangle$. For this to hold, one needs to make some heuristic
assumptions on the distribution of the eigenvalues of the Heck operators. Such
distributions are already studied in the literature [13, 20, 5], but a formal
treatment of the running time of the above projection based on these
distributions is nontrivial.

###  5.3 Cryptanalysis

In this section, we analyze the assumption behind the scheme in Section 5.2.
We use the connection between quaternion orders and modular forms to translate
the problem to the space of modular forms. The connection is provided by the
theory of theta series.

####  5.3.1 From quaternions to modular forms.

Let $m=2k>0$ be an integer and let $Q:\mathbb{Z}^{m}\rightarrow\mathbb{Z}$ be
an integral positive definite quadratic form. The theta series associated to
$Q$ is a function $\Theta_{Q}:\mathbb{H}\rightarrow\mathbb{C}$ defined by

$\Theta_{Q}(z)=\sum_{x\in\mathbb{Z}^{m}}q^{Q(x)}=\sum_{n=0}^{\infty}r_{Q}(n)q^{n},\quad
q=e^{2\pi iz}.$

The integers $r_{Q}(n)=\\#\\{x\in\mathbb{Z}^{m}:Q(x)=n\\}$ are called the
representation numbers of $Q$. Now, let
$\mathcal{O}\subset\mathcal{B}_{p,\infty}$ be a maximal order as in Section
5.2. For any two ideals $I_{i},I_{j}\subseteq\mathcal{O}$ define the mapping

$\begin{array}[]{rrll}Q_{i,j}:&I_{j}I_{i}^{-1}&\longrightarrow&\mathbb{Z}\\\
&\alpha&\longmapsto&\displaystyle\operatorname{nrd}(\alpha)\operatorname{nrd}(I_{i}I_{j}^{-1})\end{array}$
(13)

This is a positive definite quadratic form. Using these quadratic forms we can
define the morphism

$\begin{array}[]{rrll}\Theta:&M_{\mathbb{C}}\times
M_{\mathbb{C}}&\longrightarrow&M_{2}(\Gamma_{0}(p))\\\
&([I_{i}],[I_{j}])&\longmapsto&\displaystyle\sum_{\alpha\in
I_{j}I_{i}^{-1}}q^{Q_{i,j}(\alpha)}=1+2\sum_{n=1}^{\infty}\langle
T_{n}[I_{i}],[I_{j}]\rangle q^{n},\end{array}$

where $q=e^{2\pi iz}$, $z\in\mathbb{H}$. The last equality follows from the
definition of Brandt matrices (12). Eichler [10] proved that the spaces
$M_{\mathbb{C}}$ and $M_{2}(\Gamma_{0}(p))$ are isomorphic as Hecke modules,
see also [15, 16]. More precisely,

######  Theorem 5.1 (Eichler).

The map $T_{n}\mapsto T_{n}$ of Hecke operators over $M_{\mathbb{C}}$ and
$M_{2}(\Gamma_{0}(p))$ defines an isomorphism of Hecke algebras. Moreover, the
morphism $\Theta$ defines a nondegenrate Hecke bilinear map,

$\Theta(T_{n}[I_{i}],[I_{j}])=\Theta([I_{i}],T_{n}[I_{j}])=T_{n}\Theta([I_{i}],[I_{j}]),$

such that the traces of $T_{n}$ on $M_{\mathbb{C}}$ and $T_{n}$ on
$M_{2}(\Gamma_{0}(p))$ agree.

If we fix one of the arguments of $\Theta$ we get a homomorphism
$M_{\mathbb{C}}\rightarrow M_{2}(\Gamma_{0}(p))$. The following lemma explain
what the image of $\Theta$ is for some specific arguments.

######  Lemma 5.2.

Let $\phi=\sum_{j=1}^{d}\alpha_{j}[I_{j}]$ be an eigenform. Then for any
integer $1\leq k\leq d$ the modular form $\Theta([I_{k}],\phi)$ is a Hecke
eigenfunction. Moreover, $\Theta([I_{k}],\phi)\neq 0$ if and only if
$\alpha_{k}\neq 0$.

###### Proof.

The first part follows from Theorem 5.1. More precisely, for any $k$ and $n$

$T_{n}\Theta([I_{k}],\phi)=\Theta([I_{k}],T_{n}\phi)=\Theta([I_{k}],\lambda_{n}\phi)=\lambda_{n}\Theta([I_{k}],\phi).$

For the second part, expanding $\Theta([I_{k}],\phi)$ gives

$\displaystyle\Theta([I_{k}],\phi)$
$\displaystyle=\Theta\bigg{(}[I_{k}],\sum_{j=1}^{d}\alpha_{j}[I_{j}]\bigg{)}$
$\displaystyle=\sum_{j=1}^{d}\alpha_{j}\Theta([I_{k}],[I_{j}])$
$\displaystyle(\text{by linearity of }\Theta)$
$\displaystyle=\sum_{j=1}^{d}\alpha_{j}\Big{(}1+2\sum_{n=1}^{\infty}\langle
T_{n}[I_{k}],[I_{j}]\rangle q^{n}\Big{)}$ $\displaystyle(\text{by
definition})$
$\displaystyle=\sum_{j=1}^{d}\alpha_{j}+2\sum_{n=1}^{\infty}\langle
T_{n}[I_{k}],\phi\rangle q^{n}$ $\displaystyle(\text{by linearity of
}\langle\,,\rangle)$ (14)

If $\phi$ is the Eisenstein eigenform $\phi_{E}$ then $\alpha_{k}\neq 0$ and
$\langle T_{n}[I_{k}],\phi\rangle=\sigma^{\prime}(n)\alpha_{k}\neq 0$, so
$\Theta([I_{k}],\phi)\neq 0$ and the statement is true. So assume that $\phi$
is a cuspform. If $\alpha_{k}=0$ then

$\langle
T_{n}[I_{k}],\phi\rangle=\langle[I_{k}],T_{n}\phi\rangle=\lambda_{n}\langle[I_{k}],\phi\rangle=\lambda_{n}\alpha_{k}=0$
(15)

for all $n\geq 1$. It follows from (14) and (15) that
$\Theta([I_{k}],\phi)=0$. If $\alpha_{k}\neq 0$ then
$\langle[I_{k}],\phi\rangle\neq 0$ and again we see from (14) that
$\Theta([I_{k}],\phi)\neq 0$. ∎

A direct consequence of Lemma 5.2 is that the dimension of the image of the
homomorphism $\Theta([I_{k}],-):M_{\mathbb{C}}\rightarrow
M_{2}(\Gamma_{0}(p))$ depends on the coefficients
$\langle[I_{k}],\phi_{j}\rangle$ being zero or not for different eigenforms
$\phi_{j}$. In fact, using the technique in [25], one can prove that

$\dim_{\mathbb{C}}\Theta([I_{k}],M_{\mathbb{C}})=\lvert\Sigma(k)\rvert$

where $\Sigma(k)=\\{j:\langle[I_{k}],\phi_{j}\rangle\neq 0\\}$. Therefore, one
would expect that for a random $1\leq k\leq d$,
$\langle[I_{k}],\phi\rangle\neq 0$ with high probability, or equivalently,
that $\dim_{\mathbb{C}}\Theta([I_{k}],M_{\mathbb{C}})$ is not too small. We
now outline our reduction.

####  5.3.2 The reduction

Suppose we are given the quantum state

$\lvert\phi\rangle=\frac{1}{\sqrt{\alpha}}\sum_{j=1}^{d}\alpha_{j}\lvert
I_{j}\rangle$

which represents a random eigenform $\phi=\sum_{j=1}^{d}\alpha_{j}[I_{j}]$.
Since $\phi_{j}$ is random, it is a cuspform with overwhelming probability.
For a random $k$, we assume, by the above remarks, that $\alpha_{k}\neq 0$.
Let $f(q)=\Theta([I_{k}],\phi)/\alpha_{k}\in M_{2}(\Gamma_{0}(p))$. Then, by
Lemma 5.2, $f(q)$ is a Hecke eigenfunction. A closer look at (14) shows that
$f(q)$ is in fact an eigenform with eigenvalues the same as the eigenvalues of
$\phi$. Therefore, we have the identity

$f(q)=\sum_{j=1}^{d}\frac{\alpha_{j}}{\alpha_{k}}\Theta([I_{k}],[I_{j}])$ (16)

of modular forms. Let $f(q)=\sum_{n=1}^{\infty}a_{n}q^{n}$ so that
$a_{1},a_{2},\dots$ are the eigenvalues of $f$. The idea is to build a system
of linear equations, where $\alpha_{j}$ are the unknowns, by equating the
coefficients of $q^{n}$ on both sides of (16) for different values of $n$. For
any $n\geq 1$ we get an equation

$a_{n}=\frac{\alpha_{1}}{\alpha_{k}}\langle
T_{n}[I_{k}],[I_{1}]\rangle+\frac{\alpha_{2}}{\alpha_{k}}\langle
T_{n}[I_{k}],[I_{2}]\rangle+\cdots+\frac{\alpha_{d}}{\alpha_{k}}\langle
T_{n}[I_{k}],[I_{d}]\rangle.$ (17)

Let $n_{1},n_{2},\dots,n_{d}$ be a set of positive integers. Gathering linear
equations of the form (17) for all the $n_{i}$ we obtain a system

$A\bm{\alpha}=\bm{a}$ (18)

where $\bm{a}$ is the column vector
$[a_{n_{1}},a_{n_{2}},\dots,a_{n_{d}}]^{T}$, $\bm{\alpha}$ is the column
vector
$[\alpha_{1}/\alpha_{k},\alpha_{2}/\alpha_{2},\dots,\alpha_{d}/\alpha_{k}]^{T}$
and the matrix $A=(\langle T_{n_{i}}[I_{k}],[I_{j}]\rangle)_{i,j}$. The
quantum state representing the vectors $\bm{a}$ and $\bm{\alpha}$ are

$\displaystyle\lvert\bm{a}\rangle$
$\displaystyle=\frac{1}{\sqrt{\sum_{j=1}^{d}a_{n_{j}}^{2}}}\sum_{j=1}^{d}a_{n_{j}}\lvert
j\rangle\text{ and}$ $\displaystyle\lvert\bm{\alpha}\rangle$
$\displaystyle=\frac{1}{\sqrt{\sum_{j=1}^{d}\alpha_{j}^{2}/\alpha_{k}^{2}}}\sum_{j=1}^{d}\frac{\alpha_{j}}{\alpha_{k}}\lvert
I_{j}\rangle=\frac{1}{\sqrt{\alpha}}\sum_{j=1}^{d}\alpha_{j}\lvert
I_{j}\rangle=\lvert\phi\rangle,$

respectively. Suppose there is a quantum algorithm $\mathcal{A}$ that can
efficiently approximate the operation $A^{-1}$. Then one could compute an
approximate copy of $\lvert\phi\rangle$ as
$\lvert\phi\rangle=A^{-1}\lvert\bm{a}\rangle$. Therefore, assuming access to
$\mathcal{A}$, the problem is reduced to the following

######  Problem 5.3.

Generate (an approximation of) the state $\lvert\bm{a}\rangle$ for an
appropriate choice of distinct integers $n_{1},n_{2},\dots,n_{d}$.

The main obstacle to solving Problem 5.3 is that since $d$ is exponentially
large, the $n_{i}$ will be exponentially large as $i$ becomes large regardless
of which set of the $n_{i}$ we choose. Recall that $a_{n}$ is an eigenvalue of
$\lvert\phi\rangle$ for any $n\geq 1$. The best classical algorithm for
computing $a_{n}$ has complexity $\operatorname{poly}(p\log n)$ [6], which is
polynomial in $\log n$ but exponential in $\log p=O(\kappa)$, where $\kappa$
is the security parameter. Another possible approach is to use phase
estimation to directly compute $a_{n}$, since we know that

$e^{iT_{n}}\lvert\phi\rangle=e^{ia_{n}}\lvert\phi\rangle.$

This would also fail because of the following reason. It is known that $\lvert
a_{n}\rvert\leq\sigma_{0}(n)\sqrt{n}$ [7], where $\sigma_{0}(n)$ is the number
of positive divisors of $n$. However, the value $\lvert a_{n}\rvert$ can be
exponentially large in $\kappa$. This means we need to perform phase
estimation with exponential accuracy. But we can only simulate $e^{iT_{n}t}$
for time $t$ that is bounded by $\operatorname{poly}(\kappa)$.

To solve this problem, the idea is to use phase estimation but for a specific
set of integers $n_{i}$ such that we can exploit the relations (10) between
the $a_{n_{i}}$’s. More precisely, let $s=\lceil\log d\rceil$ and let
$C=\\{\ell_{1},\ell_{2},\dots,\ell_{s}\\}$ be a set $s$ distinct primes of
size $\operatorname{poly}(\kappa)$, say the first $s$ primes
$2,3,5,\dots,\ell_{s}$. Then we choose the $n_{i}$ to be the set

$\\{n_{i}\\}_{1\leq i\leq
d}:=\\{\ell_{1}^{b_{1}}\ell_{2}^{b_{2}}\cdots\ell_{s}^{b_{s}}:(b_{1},\dots,b_{s})\in\\{0,1\\}^{s}\\}.$
(19)

Explicitly, if $j=b_{1}b_{2}\cdots b_{s}$ is the binary representation of $j$
then we set $n_{j}=\ell_{1}^{b_{1}}\ell_{2}^{b_{2}}\cdots\ell_{s}^{b_{s}}$.

######  Theorem 5.4.

Given the quantum state $\lvert\phi\rangle$ representing an eigenform $\phi$,
let $f(q)=\sum_{n=1}^{\infty}a_{n}q^{n}$ be the modular form, defined by (16),
that corresponds to $\phi$. Let $\\{n_{i}\\}_{1\leq i\leq d}$ be the set of
integers defined in (19), and let

$\lvert\bm{a}\rangle=\frac{1}{\sqrt{\sum_{j=1}^{d}a_{n_{j}}^{2}}}\sum_{j=1}^{d}a_{n_{j}}\lvert
j\rangle.$

For any constant $c>0$, there is a polynomial time quantum algorithm that can
prepare a state $\lvert\tilde{\bm{a}}\rangle$ such that
$\lVert\lvert\bm{a}\rangle\langle\bm{a}\rvert-\lvert\tilde{\bm{a}}\rangle\langle\tilde{\bm{a}}\rvert\rVert_{1}\leq
1/\kappa^{c}$.

###### Proof.

For any prime $\ell\in C$ we can use phase estimation on the operator
$e^{iT_{\ell}}$ and the eigenstate $\lvert\phi\rangle$ to compute an
approximate eigenvalue $\tilde{a}_{\ell}$ such that $\lvert
a_{\ell}-\tilde{a}_{\ell}\rvert\leq 1/s\kappa^{c}$. Now, using the single
qubit operation

$\tilde{R}_{\ell}=\frac{1}{\sqrt{1+\smash[b]{\tilde{a}_{\ell}^{2}}}}\begin{bmatrix}1&-\tilde{a}_{\ell}\\\
\tilde{a}_{\ell}&1\end{bmatrix}$

we can generate the single qubit state

$\lvert\tilde{\psi}_{\ell}\rangle:=\tilde{R}_{\ell}\lvert
0\rangle=\frac{1}{\sqrt{1+\smash[b]{\tilde{a}_{\ell}^{2}}}}(\lvert
0\rangle+\tilde{a}_{\ell}\lvert 1\rangle).$

Tensoring these states together for all $\ell\in C$ we obtain the state
$\lvert\tilde{\bm{a}}\rangle:=\bigotimes_{\ell\in
C}\lvert\tilde{\psi}_{\ell}\rangle$. Now, for any $n_{j}$ we can write
$n_{j}=\ell_{1}^{b_{1}}\ell_{2}^{b_{2}}\cdots\ell_{s}^{b_{s}}$ where
$b_{1}b_{2}\cdots b_{s}$ is the binary representation of $j$. Therefore, using
the relations (10) we have $a_{n_{j}}=a_{\ell_{1}}^{b_{1}}\cdots
a_{\ell_{s}}^{b_{s}}$. So we can rewrite the state $\lvert\bm{a}\rangle$ as

$\displaystyle\lvert\bm{a}\rangle$
$\displaystyle=\bigg{(}\prod_{j=1}^{s}(1+a_{\ell}^{2})\bigg{)}^{-1/2}\sum_{(b_{1},\dots,b_{s})\in\\{0,1\\}^{s}}a_{\ell_{1}}^{b_{1}}\cdots
a_{\ell_{s}}^{b_{s}}\lvert b_{1},\dots,b_{s}\rangle$
$\displaystyle=\bigotimes_{\ell\in
C}\frac{1}{\sqrt{1+\smash[b]{a_{\ell}^{2}}}}(\lvert 0\rangle+a_{\ell}\lvert
1\rangle)$

Let $\lvert\psi_{\ell}\rangle=(\lvert 0\rangle+a_{\ell}\lvert
1\rangle)/\sqrt{1+\smash[b]{a_{\ell}^{2}}}$. Then

$\lVert\lvert\psi_{\ell}\rangle\langle\psi_{\ell}\rvert-\lvert\tilde{\psi}_{\ell}\rangle\langle\tilde{\psi}_{\ell}\rvert\rVert_{1}=\sqrt{1-\lvert\langle\psi_{\ell}|\tilde{\psi}_{\ell}\rangle\rvert^{2}}\leq\frac{1}{s\kappa^{c}},$

and we have

$\displaystyle\lVert\lvert\bm{a}\rangle\langle\bm{a}\rvert-\lvert\tilde{\bm{a}}\rangle\langle\tilde{\bm{a}}\rvert\rVert_{1}$
$\displaystyle=\bigg{\lVert}\bigotimes_{\ell\in
C}\lvert\psi_{\ell}\rangle\langle\psi_{\ell}\rvert-\bigotimes_{\ell\in
C}\lvert\tilde{\psi}_{\ell}\rangle\langle\tilde{\psi}_{\ell}\rvert\bigg{\rVert}_{1}$
$\displaystyle\leq\sum_{\ell\in
C}\lVert\lvert\psi_{\ell}\rangle\langle\psi_{\ell}\rvert-\lvert\tilde{\psi}_{\ell}\rangle\langle\tilde{\psi}_{\ell}\rvert\rVert_{1}$
$\displaystyle\leq\frac{1}{\kappa^{c}}\qed$

## References

  * [1] Scott Aaronson.  Quantum copy-protection and quantum money.  In 2009 24th Annual IEEE Conference on Computational Complexity, pages 229–242. IEEE, 2009.
  * [2] Scott Aaronson.  The complexity of quantum states and transformations: from quantum money to black holes.  arXiv preprint arXiv:1607.05256, 2016.
  * [3] Scott Aaronson and Paul Christiano.  Quantum money from hidden subspaces.  In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 41–60, 2012.
  * [4] Dominic W Berry, Andrew M Childs, and Robin Kothari.  Hamiltonian simulation with nearly optimal dependence on all parameters.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 792–809. IEEE, 2015.
  * [5] Sam Chow and Alexandru Ghitza.  Distinguishing newforms.  International Journal of Number Theory, 11(03):893–908, 2015.
  * [6] Jean-Marc Couveignes and Bas Edixhoven.  Computational aspects of modular forms and Galois representations.  Princeton University Press, 2011.
  * [7] Pierre Deligne.  La conjecture de Weil. I.  Publications Mathématiques de l’Institut des Hautes Études Scientifiques, 43(1):273–307, 1974.
  * [8] Fred Diamond and Jerry Michael Shurman.  A first course in modular forms, volume 228.  Springer, 2005.
  * [9] Jintai Ding and Bo-Yin Yang.  Multivariates polynomials for hashing.  In International Conference on Information Security and Cryptology, pages 358–371. Springer, 2007.
  * [10] Martin Eichler.  The basis problem for modular forms and the traces of the hecke operators.  In Modular functions of one variable I, pages 75–152. Springer, 1973.
  * [11] Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, and Peter Shor.  Quantum money from knots.  In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 276–289, 2012.
  * [12] Ulrich Görtz and Torsten Wedhorn.  Algebraic Geometry I: Schemes.  Springer, 2010.
  * [13] Sanoli Gun, M Ram Murty, and Purusottam Rath.  Summation methods and distribution of eigenvalues of hecke operators.  Functiones et Approximatio Commentarii Mathematici, 39(2):191–204, 2008.
  * [14] Daniel M. Kane, Shahed Sharif, and Alice Silverberg.  Quantum money from quaternion algebras.  arXiv:2109.12643, 2021.
  * [15] David R Kohel.  Computing modular curves via quaternions, 1999.
  * [16] David R Kohel.  Hecke module structure of quaternions.  In Class Field Theory–Its Centenary and Prospect, pages 177–195. Mathematical Society of Japan, 2001.
  * [17] Serge Lang.  Introduction to modular forms, volume 222.  Springer Science & Business Media, 2012.
  * [18] Serge Lang and André Weil.  Number of points of varieties in finite fields.  American Journal of Mathematics, 76(4):819–827, 1954.
  * [19] Andrew Lutomirski, Scott Aaronson, Edward Farhi, David Gosset, Avinatan Hassidim, Jonathan Kelner, and Peter Shor.  Breaking and making quantum money: toward a new quantum cryptographic protocol.  arXiv preprint arXiv:0912.3825, 2009.
  * [20] M Ram Murty and Kaneenika Sinha.  Effective equidistribution of eigenvalues of hecke operators.  Journal of Number Theory, 129(3):681–714, 2009.
  * [21] Marta Conde Pena, Jean-Charles Faugère, and Ludovic Perret.  Algebraic cryptanalysis of a quantum money scheme the noise-free case.  In IACR International Workshop on Public Key Cryptography, pages 194–213. Springer, 2015.
  * [22] Bjorn Poonen.  Rational points on varieties, volume 186.  American Mathematical Soc., 2017.
  * [23] Bhaskar Roberts.  Security analysis of quantum lightning.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 562–567. Springer, 2021.
  * [24] William A Stein.  Modular forms, a computational approach, volume 79.  American Mathematical Soc., 2007.
  * [25] Kennichi Sugiyama.  On the space of theta functions for a prime level.  Comment. Math. Univ. St. Pauli, 67(1):65–81, 2019.
  * [26] John Voight.  Quaternion algebras.  Springer Nature, 2021.
  * [27] John Watrous.  The theory of quantum information.  Cambridge University Press, 2018.
  * [28] Stephen Wiesner.  Conjugate coding.  ACM Sigact News, 15(1):78–88, 1983.
  * [29] Mark Zhandry.  Quantum lighning never strikes the same state twice, 11 2017.  https://eprint.iacr.org/2017/1080/20171110:155027.
  * [30] Mark Zhandry.  Quantum lightning never strikes the same state twice.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 408–438. Springer, 2019.