Benchmarking the quantum cryptanalysis of symmetric, public-key and hash-based cryptographic

schemes
Vlad Gheorghiu1, 2, 3, 4, ∗ and Michele Mosca1, 2, 5, 6, 3, 4, †
1
Institute for Quantum Computing, University of Waterloo, Waterloo, ON, N2L 3G1, Canada
2
Department of Combinatorics & Optimization, University of Waterloo, Waterloo, ON, N2L 3G1, Canada
3
evolutionQ Inc., Waterloo, ON, Canada
4
softwareQ Inc., Kitchener, ON, Canada
5
Perimeter Institute for Theoretical Physics, Waterloo, ON, N2L 6B9, Canada
6
Canadian Institute for Advanced Research, Toronto, ON, M5G 1Z8, Canada
Quantum algorithms can break factoring and discrete logarithm based cryptography and weaken symmetric
cryptography and hash functions.
In order to estimate the real-world impact of these attacks, apart from tracking the development of fault-
tolerant quantum computers it is important to have an estimate of the resources needed to implement these
arXiv:1902.02332v2 [quant-ph] 7 Feb 2019

quantum attacks.
For attacking symmetric cryptography and hash functions, generic quantum attacks are substantially less
powerful than they are for today’s public-key cryptography. So security will degrade gradually as quantum
computing resources increase. At present, there is a substantial resource overhead due to the cost of fault-tolerant
quantum error correction. We provide estimates of this overhead using state-of-the-art methods in quantum
fault-tolerance. For example, recent lattice surgery methods reduced memory costs by roughly a factor of 5 over
previous methods. Future advances in fault-tolerance and in the quality of quantum hardware may reduce this
overhead further. Another part of the cost of implementing generic quantum attacks is the cost of implementing
the cryptographic functions. We use state-of-the-art optimized circuits, though further improvements in their
implementation would also reduce the resources needed to implement these attacks. To bound the potential
impact of further circuit optimizations we provide cost estimates assuming trivial-cost implementations of these
functions. These figures indicate the effective bit-strength of the various symmetric schemes and hash functions
based on what we know today (and with various assumptions on the quantum hardware), and frame the various
potential improvements that should continue to be tracked. As an example, we also look at the implications for
Bitcoin’s proof-of-work system.
For many of the currently used asymmetric (public-key) cryptographic schemes based on RSA and elliptic
curve discrete logarithms, we again provide cost estimates based on the latest advances in cryptanalysis, circuit
compilation and quantum fault-tolerance theory. These allow, for example, a direct comparison of the quantum
vulnerability of RSA and elliptic curve cryptography for a fixed classical bit strength.
This analysis provides state-of-the art snap-shot estimates of the realistic costs of implementing quantum
attacks on these important cryptographic algorithms, assuming quantum fault-tolerance is achieved using surface
code methods, and spanning a range of potential error rates. These estimates serve as a guide for gauging the
realistic impact of these algorithms and for benchmarking the impact of future advances in quantum algorithms,
circuit synthesis and optimization, fault-tolerance methods and physical error rates.

TABLE OF CONTENTS V. Bitcoin 8

I. Introduction 2 VI. Intrinsic cost of parallelized Grover’s algorithm 9

A. Searching space of size 256 9
II. Methodology 3 B. Searching space of size 264 10
A. Symmetric cryptography and hash functions 3 C. Searching space of size 2128 11
B. Public-key cryptography 4 D. Searching space of size 2256 12

III. Symmetric ciphers 4 VII. RSA schemes 12

A. AES-128 5 A. RSA-1024 12
B. AES-192 6 B. RSA-2048 13
C. AES-256 6 C. RSA-3072 13
D. RSA-4096 14
IV. Hash functions 7 E. RSA-7680 14
A. SHA-256 7 F. RSA-15360 14
B. SHA3-256 8
VIII. Elliptic curve schemes 15
A. NIST P-160 15
B. NIST P-192 15
∗ Electronic address: vlad.gheorghiu@uwaterloo.ca C. NIST P-224 16
† Electronic address: michele.mosca@uwaterloo.ca D. NIST P-256 16
 2

E. NIST P-384 16 defects and braiding techniques [5], novel lattice surgery tech-
F. NIST P-521 17 niques [6, 8, 9] reduce the spatial overhead required for imple-
menting T gates via magic state distillation by approximately
IX. Summary and conclusions 17 a factor of 5, while also modestly improving the running time.

Acknowledgments 18 In this paper we first analyze the security of symmetric

schemes and hash functions against large-scale fault-tolerant
References 19 quantum adversaries, using surface code defects and braiding
techniques. We take into account the time-space trade-offs
with parallelizing quantum search, down to the fault-tolerant
layer. Naively, one might hope that K quantum computers (or
I. INTRODUCTION
quantum “processors”, as we will call them later in the paper)
running√ in parallel reduce the number the circuit depth down
Symmetric, public-key (asymmetric) and hash-based cryp- to O( N )/K steps, similar to the classical case of distribut-
tography constitute a fundamental pillar of modern cryptog- ing a search space across K classical processors. However
raphy. Symmetric cryptography includes symmetric-key en- quantum searching does not parallelize so well, and the re-
cryption, where a shared secret key is used for both encryp- quired number
tion and decryption. Cryptographic hash functions map arbi- p of steps for parallel quantum √ searching is of
the√order O( N/K) [10]. This is a factor of K larger than
trarily long strings to strings of a fixed finite length. Currently
O( N )/K . As shown in [10], the optimal way of doing par-
deployed public-key schemes are used to establish a common
allel quantum search is to partition the search space into N/K
secret key between two remote parties. They are based on fac-
parts, and to perform independent quantum searches on each
toring large numbers or solving the discrete logarithm prob-
part.
lem over a finite group. For more details about modern cryp-
tography the interested reader can consult one of the many Secondly, we investigate the security of public-key crypto-
excellent references on the topic, e.g. [1]. graphic schemes such as RSA and ECC against quantum at-
In contrast to asymmetric schemes based on factoring or tacks, using the latest developments in theory of fault-tolerant
solving the discrete logarithm problem and which are com- quantum error correction, i.e. novel lattice surgery tech-
pletely broken by a quantum adversary via Shor’s algo- niques [6, 8, 9].
rithm [2], symmetric schemes and hash functions are less
The remainder of this paper is organized as follows. In
vulnerable to quantum attacks. The best known quantum at-
Sec. II, we provide an overview of the methodology used in
tacks against them are based on Grover’s quantum search al-
our analysis. In Sec. III we investigate the security of the AES
gorithm [3], which offers a quadratic speedup compared to
family of modern symmetric ciphers. In Sec. IV we analyze
classical brute force searching. Given a search space of size
the security of the SHA family of hash functions. In Sec. V we
N , Grover’s algorithm finds, with high probability, an element
investigate the security of Bitcoin’s [11] proof-of-work con-
x for which a certain property such as f (x) = 1 holds, for
sensus mechanism. We conclude our investigation of symmet-
some function f we know how to evaluate (assuming such √ a ric and hash-based cryptographic schemes in Sec. VI, where
solution exists). The algorithm evaluates f a total of O( N )
we evaluate the intrinsic cost of running the Grover algorithm
times. It applies√a simple operation in between the evaluations
with a trivial oracle (i.e., an oracle with a unit cost of 1 for
of f , so the O( N ) evaluations of f account for most of the
each invocation).
complexity. In contrast, any classical algorithm that evaluates
f in a similar “black-box” way requires on the order of N In the subsequent sections we analyze public-key crypto-
evaluations of f to find such an element. graphic schemes. In Sec. VII and Sec. VIII we examine
Any quantum algorithm can be mapped to a quantum cir- the most common public-key establishment schemes, such as
cuit, which can be implemented on a quantum computer. The RSA and ECC, respectively. In the subsequent sections we
quantum circuit represents what we call the “logical layer”. analyze public-key cryptographic schemes. In Sec. VII and
Such a circuit can always be decomposed in a sequence of Sec. VIII we examine the most common public-key establish-
“elementary gates”, such as Clifford gates (CNOT, Hadamard ment schemes, such as RSA and ECC, respectively. Finally
etc. [4]) augmented by a non-Clifford gate such as the T gate. we summarize our findings and conclude in Sec. IX.
Running a logical circuit on a full fault-tolerant quantum
computer is highly non-trivial. The sequence of logical gates
have to be mapped to sequences of surface code measurement
cycles (see e.g. [5] for extensive details). By far, the most
resource-consuming (in terms of number of qubits required
and time) is the T gate1 . In comparison with surface code Clifford gate is required. One such gate is the T gate. There are other
possible choices, however all of the non-Clifford gates require special tech-
niques such as magic state distillation [6, 7] and significant overhead (order
of magnitudes higher than Clifford gates) to be implemented in the surface
code. In fact, to a first order approximation, for the purpose of resource
1 Clifford gates are “cheap”, i.e. they require relatively small overhead for estimation, one can simply ignore the overhead introduced by the Clifford
implementation in the surface code, but are not universals, hence a non- gates and simply focus only on the T gates.
 3

II. METHODOLOGY

A. Symmetric cryptography and hash functions

The methodology, sketched in Fig. 1 and Fig. 2, follows the

same lines as the one described in great detail in our earlier
paper [12], which we refer the interested reader to for more
details.

Classical query model

Run Grover's algorithm

Logical layer
FIG. 2. Grover searching with an oracle for f : {0, 1}k → {0, 1}k .
Generate and optimize reversible circuits The algorithm makes b π4 2N/2 c calls to G, the Grover iteration, or,
if parallelized on K processors, b π4 2N/(2K) c calls to G. The Grover
iteration has two subroutines. The first, Ug , implements the predicate
g : {0, 1}k → {0, 1} that maps x to 1 if and only if f (x) = y. Each
Fault tolerant layer call to Ug involves two calls to a reversible implementation of f and
one call to a comparison circuit that checks whether f (x) = y.
Embed reversible circuits into error
correcting codes; estimate resources. reducing the security parameter2 by at most 1 and decreasing
the spatial overhead by at most a factor of 5. Therefore when
estimating the security of symmetric and hash-based crypto-
Physical layer graphic schemes we use surface code defects and braiding
techniques.
For each cryptographic primitive, we display four plots, in
Determine physical resources (time,
the following order:
qubits, code cycles).
1. We plot the total number of surface code cycles per
CPU (where a CPU is a quantum computer capable of
FIG. 1. Analyzing an attack against a symmetric cryptographic func-
tion with a fault-tolerant quantum adversary. Our resource estima- executing a single instance of Grover’s quantum search
tion methodology takes into account several of the layers between algorithm) as a function of the number of CPUs. We
the high level description of an algorithm and the physical hardware directly tie the quantum security parameter to the to-
required for its execution. Our approach is modular should assump- tal number of surface code cycles (see [12] for more
tions about any of these layers change, and hence it allows one to details). We also add to the plot the theoretical lower
calculate the impact of improvements in any particular layer. bound achievable by quantum search in the cases of:
a) considering the oracle a black box of unit cost (lower
line), and b) considering the oracle as composed of ideal
We assume a surface-code based fault-tolerant architec- quantum gates, each of unit cost (upper line). Note that
ture [5], using Reed-Muller distillation schemes [13]. For the difference between b) and a) represents the intrin-
each scheme we vary the possible physical error rates per gate sic cost of logical overhead (i.e. the overhead intro-
from 10−4 to 10−7 . We believe that this range of physical duced by treating the oracle as a logical circuit and not
error rates is wide enough to cover both first generation quan- a blackbox), whereas the difference between the upper
tum computers as well as more advanced future machines. In lines and b) represents the intrinsic cost introduced by
comparison to surface code defects and braiding methods [5], the fault-tolerant layer.
lattice surgery techniques [6, 8, 9] mostly impact the physical
2. We plot the total wall-time per CPU (i.e. how long will
footprint of the fault-tolerant layer required to run a specific
quantum algorithm, reducing the distillation overhead by ap-
proximately a factor of 5. The temporal overhead (i.e. the
number of surface code cycles) is reduced less drastically. For 2 The security parameter is defined as the logarithm base two of the number
this reason, lattice surgery has less significant effects in esti- of fundamental operations (in our case surface code cycles) required to
mating the security of symmetric schemes or hash functions, break the scheme.
 4

the whole computation take on a parallel quantum ar- and obtain an analytical closed-form formula for the relation
chitecture) as a function of the number of CPUs. The between the time and the number of qubits required to attack
horizontal dashed line represents the one-year time line, the scheme, in the form
i.e. the x coordinate of the intersection point between
the “Total time per CPU” line and the one-year time line
provides the number of processors required to break the
system within one year (in log2 units). y(x) = αx3 + βx2 + γx + δ, (1)

3. We plot the total physical footprint (number of qubits) where y represents logarithm base 2 of the number of qubits
per CPU, as a function of the number of CPUs. and x represents the logarithm base 2 of the time (in seconds).
For example, the quantity
4. Finally we plot the total physical footprint (number of
qubits) of all quantum search machines (CPUs) running
in parallel. y (log2 (24 × 3600)) ≈ y(16.3987) (2)

In the following sections we proceed to analyze symmetric

represents how many qubits are required to break the scheme
ciphers (AES, Sec. III), hash functions (SHA-256, SHA3-256,
in one day (24 hours) for a fixed physical error rate per gate
Sec. IV, Bitcoin’s hash function, Sec. V), and finally the min-
pg , assuming a surface code cycle time of 200ns. Note that the
imal resources required for running Grover’s algorithm with
computation time scales linearly with the surface code cycle
a trivial oracle VI (e.g. the identity gate) on search spaces of
time, e.g. a 1000ns surface code cycle time will result in a
various sizes.
computation that is 5 times longer than a 200ns surface code
Note that in some ranges of the plots from sec-
cycle time. Therefore, for a specific cryptographic scheme for
tions III, IV, VI and V the total physical footprint increases
which we plotted the space/time tradeoffs using a surface code
slightly with the number of processors, which may seem
cycle time of 200ns and a fixed physical error rate per gate pg ,
counter-intuitive. This happens due to the fact that with more
the number of qubits required to break a specific scheme in a
processors the required code distances decrease, and in some
time t using an alternative surface code cycle time tc is given
instances one can pipeline more magic states factories in par-
by
allel into the surface code, which in effect causes an increase
in the overall physical footprint. Note that the total time per
CPU is monotonically decreasing, as parallelizing distilleries   
does not increase the wall time. For more details see [12]. 200ns
y log2 t , (3)
tc

B. Public-key cryptography
where t is expressed in seconds and tc is expressed in nanosec-
onds.
Most of the recent progress in quantum cryptanalysis is re-
We assume a surface code cycle time of 200ns, in confor-
lated to the fault-tolerant layer in Fig. 1. New methods and
mance with [5]. For each scheme we analyze, we compare its
techniques based on surface code lattice surgery [6, 8, 9] al-
security using the more conservative (and realistic in the short
low a significant decrease of the overall footprint (number of
term) pg = 10−3 and also the more optimistic pg = 10−5 .
qubits, or space) taken by the quantum computation, and also
Note that assuming the more optimistic assumption from a
a relatively modest decrease in time, in comparison with meth-
quantum computing perspective is the more conservative as-
ods based on surface code defects and braiding [5, 13].
sumption from a cybersecurity perspective.
We consider the best up-to-date optimized logical quantum
circuits for attacking RSA and ECC public-key schemes [14– Furthermore, in this analysis, we are reporting the full phys-
17] then perform a physical footprint resource estimation ical footprint, including the memory required for magic state
analysis using lattice surgery techniques. We remark that the distillation. Using present-day techniques, the memory re-
overall time required to run the algorithm depends on the level quired for generating these generic input states accounts for
of parallelization for the magic state factories3 . a substantial fraction of the total memory cost and thus we
For each public-key cryptogrpric scheme, we analyze the are including these in the total cost estimate and will track the
space/time tradeoffs and plot the results on a double logarith- impact of improved methods.
mic scale. We fit the data using a third degree polynomial4

III. SYMMETRIC CIPHERS

3 Every T gate in the circuit must be implemented by a specialized magic
state factory, each of which occupies a significant physical footprint. One
can implement more magic states in parallel if one is willing to increase Below we analyze the security of AES family of symmet-
the physical footprint of the computation. ric ciphers against large-scale fault-tolerant quantum adver-
4 A third degree polynomial fits the data very precisely, providing a coeffi- saries. We used the highly optimized logical circuits produced
cient of determination R2 greater than 0.997. in [18].
 5

A. AES-128
AES-128
70
p_g=1e-4
p_g=1e-5
60 p_g=1e-6

Total time per CPU (seconds, log2)

p_g=1e-7
1 year
50

40

AES-128 30

100 20
Total surface code cycles (log2) per CPU

90 10

80
0 20 40 60 80 100 120
70 CPUs (log2)

60
p_g=1e-4 FIG. 4. AES-128 block cipher. Required time per processor, as a
50 p_g=1e-5 function of the number of processors (log2 scale). The horizontal
p_g=1e-6
40 p_g=1e-7 dotted line indicates one year. The x-axis is deliberately extended
Ideal Grover (non-black-box) to show the necessary number of CPUs for a total time of one year.
Theoretical lower bound (black-box)
30 Thus the figure shows that it would take, with the stated assump-
0 10 20 30 40 50 60
CPUs (log2) tions, over 280 parallel quantum searches to break AES-128 in a
year. Similar remarks to the above hold for the remaining plots in
this manuscript.
FIG. 3. AES-128 block cipher. Required surface clock cycles per
processor, as a function of the number of processors (log2 scale). AES-128
1e7
The bottom brown line (theoretical lower bound, black box) repre- p_g=1e-4
sents the minimal number of queries required by Grover’s algorithm, p_g=1e-5
2.5 p_g=1e-6
the cost function being the total number of queries to a black-box p_g=1e-7
Total physical footprint per CPU

oracle, each query assumed to have unit cost, and a completely error-
2.0
free circuit. The purple line (ideal grover, non-black-box) takes into
consideration the structure of the oracle, the cost function being the
1.5
total number of gates in the circuit, each gate having unit cost; the
quantum circuit is assumed error-free as well. Both brown and ma-
1.0
genta lines are displayed only for comparisons; for both of them, the
y axis should be interpreted as number of logical queries (operations,
0.5
respectively). The curves above the purple line show the overhead in-
troduced by fault tolerance (in terms of required surface code cycles,
0.0
each surface code cycle assumed to have unit cost). More optimiza- 0 10 20 30 40 50 60
tion at the logical layer will shift the purple line down, whereas more CPUs (log2)
optimization at the fault-tolerant layer will move the upper curves
closer to the purple line. Similar remarks to the above hold for the FIG. 5. AES-128 block cipher. Physical footprint (physical qubits)
remaining plots in this manuscript. per processor, as a function of the number of processors (log2 scale).

AES-128
90
p_g=1e-4
p_g=1e-5
80 p_g=1e-6
p_g=1e-7
Total physical footprint (log2)

For example, the plots in Fig. 3 tells us that if we have 250 70

quantum computers running Grover’s algorithm in parallel, 60

with no physical errors, then it would take about 263 gate calls
(where the purple line intersects the vertical line at 50), where 50

we assume each gate to have unit cost. Still with no errors, a 40

trivial cost for implementing the cryptographic function (ora-
cle) would bring the cost down to about 238 oracle calls per 30

quantum computer. Keeping the actual function implementa- 20

tion, but adding the fault-tolerant layer with a physical error 0 10 20 30 40 50 60
CPUs (log2)
rate of 10−7 (with appropriate assumptions and using state-
of-the-art quantum error correction) pushes the cost up to
around 276 surface code cycles per quantum computer (where FIG. 6. AES-128 block cipher. Total physical footprint (physical
now each code cycle is assumed to have unit cost). Simi- qubits), as a function of the number of processors (log2 scale). Note
lar remarks hold for the remaining plots in this manuscript. that the qubits are not correlated across processors.
 6

B. AES-192
AES-192
90 p_g=1e-4
p_g=1e-5
80 p_g=1e-6
p_g=1e-7

Total physical footprint (log2)

AES-192 70
140
60
130
Total surface code cycles (log2) per CPU

120 50

110 40

100 30

90
p_g=1e-4 20
p_g=1e-5 0 10 20 30 40 50 60
80 p_g=1e-6 CPUs (log2)
p_g=1e-7
70 Ideal Grover (non-black-box)
Theoretical lower bound (black-box) FIG. 10. AES-192 block cipher. Total physical footprint (physical
60
0 10 20 30 40 50 60 qubits), as a function of the number of processors (log2 scale). Note
CPUs (log2)
that the qubits are not correlated across processors.

FIG. 7. AES-192 block cipher. Required surface clock cycles per

processor, as a function of the number of processors (log2 scale).
C. AES-256

AES-192
100 p_g=1e-4 AES-256
p_g=1e-5
p_g=1e-6 170
Total time per CPU (seconds, log2)

80 p_g=1e-7
Total surface code cycles (log2) per CPU

1 year 160

60 150

140
40
130

20 120 p_g=1e-4
p_g=1e-5
110 p_g=1e-6
p_g=1e-7
0
100 Ideal Grover (non-black-box)
0 25 50 75 100 125 150 175 Theoretical lower bound (black-box)
CPUs (log2)
0 10 20 30 40 50 60
CPUs (log2)
FIG. 8. AES-192 block cipher. Required time per processor, as a
function of the number of processors (log2 scale). FIG. 11. AES-256 block cipher. Required surface clock cycles per
processor, as a function of the number of processors (log2 scale).

1e8 AES-192 AES-256

p_g=1e-4 p_g=1e-4
0.8 p_g=1e-5 p_g=1e-5
p_g=1e-6 120 p_g=1e-6
Total time per CPU (seconds, log2)

p_g=1e-7 p_g=1e-7
Total physical footprint per CPU

100 1 year
0.6
80

0.4 60

40
0.2
20

0.0 0
0 10 20 30 40 50 60 0 50 100 150 200 250
CPUs (log2) CPUs (log2)

FIG. 9. AES-192 block cipher. Physical footprint (physical qubits) FIG. 12. AES-256 block cipher. Required time per processor, as a
per processor, as a function of the number of processors (log2 scale). function of the number of processors (log2 scale).
 7

A. SHA-256
1e8 AES-256
p_g=1e-4
1.75 p_g=1e-5
p_g=1e-6
1.50 p_g=1e-7 SHA-256
Total physical footprint per CPU

170
1.25
160

Total surface code cycles (log2) per CPU

1.00
150
0.75
140
0.50
130
0.25
120 p_g=1e-4
0.00 p_g=1e-5
0 10 20 30 40 50 60 110 p_g=1e-6
CPUs (log2) p_g=1e-7
100 Ideal Grover (non-black-box)
Theoretical lower bound (black-box)
FIG. 13. AES-256 block cipher. Physical footprint (physical qubits) 0 10 20 30 40 50 60
per processor, as a function of the number of processors (log2 scale). CPUs (log2)

FIG. 15. SHA-256 cryptographic hash function. Required surface

clock cycles per processor, as a function of the number of processors
AES-256 (log2 scale).
90 p_g=1e-4
p_g=1e-5
p_g=1e-6
80 p_g=1e-7 SHA-256
Total physical footprint (log2)

p_g=1e-4
70 p_g=1e-5
120 p_g=1e-6
Total time per CPU (seconds, log2)

60 p_g=1e-7
100 1 year
50
80
40
60
30
40
0 10 20 30 40 50 60
CPUs (log2) 20

0
FIG. 14. AES-256 block cipher. Total physical footprint (physical 0 50 100 150 200 250
CPUs (log2)
qubits), as a function of the number of processors (log2 scale). Note
that the qubits are not correlated across processors.
FIG. 16. SHA-256 cryptographic hash function. Required time per
processor, as a function of the number of processors (log2 scale).

1e7 SHA-256
p_g=1e-4
5 p_g=1e-5
p_g=1e-6
p_g=1e-7
Total physical footprint per CPU

IV. HASH FUNCTIONS 1

0
0 10 20 30 40 50 60
CPUs (log2)

In this section we study the effect of parallelized Grover

attacks on the SHA-256 [19] snd SHA3-256 [20] family of FIG. 17. SHA-256 cryptographic hash function. Physical footprint
hash functions. We used the highly optimized logical circuits (physical qubits) per processor, as a function of the number of pro-
produced in [12]. cessors (log2 scale).
 8

SHA-256 1e8 SHA3-256

90 p_g=1e-4 p_g=1e-4
p_g=1e-5 p_g=1e-5
80 p_g=1e-6 p_g=1e-6
p_g=1e-7 4 p_g=1e-7

Total physical footprint per CPU

Total physical footprint (log2)

70
3
60

50 2

40
1
30

20 0
0 10 20 30 40 50 60 0 10 20 30 40 50 60
CPUs (log2) CPUs (log2)

FIG. 18. SHA-256 cryptographic hash function. Total physical foot- FIG. 21. SHA3-256 cryptographic hash function. Physical footprint
print (physical qubits), as a function of the number of processors (physical qubits) per processor, as a function of the number of pro-
(log2 scale). Note that the qubits are not correlated across proces- cessors (log2 scale).
sors.
SHA3-256
90 p_g=1e-4
B. SHA3-256 p_g=1e-5
p_g=1e-6
80 p_g=1e-7

Total physical footprint (log2)

70
SHA3-256
170
60
160
Total surface code cycles (log2) per CPU

50
150
40
140
30
130

120 0 10 20 30 40 50 60
p_g=1e-4 CPUs (log2)
p_g=1e-5
110 p_g=1e-6
p_g=1e-7
100 Ideal Grover (non-black-box) FIG. 22. SHA3-256 cryptographic hash function. Total physical
Theoretical lower bound (black-box) footprint (physical qubits), as a function of the number of processors
0 10 20 30 40 50 60 (log2 scale). Note that the qubits are not correlated across processors.
CPUs (log2)

FIG. 19. SHA3-256 cryptographic hash function. Required surface

clock cycles per processor, as a function of the number of processors
(log2 scale).
V. BITCOIN
SHA3-256
p_g=1e-4
120 p_g=1e-5 In this section we analyze the security of Bitcoin’s [11]
p_g=1e-6
proof-of-work protocol, which is based on finding a hash5
Total time per CPU (seconds, log2)

100 p_g=1e-7
1 year
pre-image which that starts with a certain number of zeros.
80
The latter is dynamically adjusted by the protocol so that
60 the problem is on average solved by the whole network in
10 minutes. Currently, it takes around 275 classical hash-
40 ing operations [21] for finding a desired hash pre-image suc-
20
cessfully via brute-force search with specialized hardware.

0 50 100 150 200 250

CPUs (log2)

5 The hash function being used by the protocol is H(x) := SHA-256(SHA-

FIG. 20. SHA3-256 cryptographic hash function. Required time per
processor, as a function of the number of processors (log2 scale). 256(x).
 9

SHA-256-Bitcoin SHA-256-Bitcoin
p_g=1e-4
70 80 p_g=1e-5
Total surface code cycles (log2) per CPU

p_g=1e-6
60 70 p_g=1e-7

Total physical footprint (log2)

50 60

40
50
30
p_g=1e-4 40
p_g=1e-5
20
p_g=1e-6 30
p_g=1e-7
10 Ideal Grover (non-black-box)
Theoretical lower bound (black-box) 20
0 10 20 30 40 50 60 0 10 20 30 40 50 60
CPUs (log2) CPUs (log2)

FIG. 23. Bitcoin’s cryptographic hash function H(x) := SHA- FIG. 26. Bitcoin’s cryptographic hash function H(x) := SHA-
256(SHA-256(x)). Required surface clock cycles per processor, as a 256(SHA-256(x)). Total physical footprint (physical qubits), as a
function of the number of processors (log2 scale). function of the number of processors (log2 scale). Note that the
qubits are not correlated across processors.

SHA-256-Bitcoin
40 p_g=1e-4
p_g=1e-5
p_g=1e-6
35
Total time per CPU (seconds, log2)

p_g=1e-7
1 year VI. INTRINSIC COST OF PARALLELIZED GROVER’S
30 ALGORITHM
25

20 More efficient quantum implementations of AES and SHA

15
imply more efficient cryptanalysis. In this section, we aim to
bound how much further optimized implementations of these
10 cryptographic functions could help. We do so by assuming a
5 trivial cost of 1 for each function evaluation.
0 10 20 30 40 50 60
CPUs (log2)

FIG. 24. Bitcoin’s cryptographic hash function H(x) := SHA-

256(SHA-256(x)). Required time per processor, as a function of the
number of processors (log2 scale). A. Searching space of size 256

1e6 SHA-256-Bitcoin Minimal Grover 56 bits

8 55
p_g=1e-4
p_g=1e-5 50
7
Total surface code cycles (log2) per CPU

p_g=1e-6
p_g=1e-7 45
Total physical footprint per CPU

6
40
5
35
4
30
3
25 p_g=1e-4
2 p_g=1e-5
20 p_g=1e-6
1 p_g=1e-7
15 Ideal Grover (non-black-box)
0 Theoretical lower bound (black-box)
0 10 20 30 40 50 60 0 5 10 15 20 25 30
CPUs (log2) CPUs (log2)

FIG. 25. Bitcoin’s cryptographic hash function H(x) := SHA- FIG. 27. Running Grover’s algorithm with a trivial oracle, for a
256(SHA-256(x)). Physical footprint (physical qubits) per proces- searching space of size 256 . Required surface clock cycles per pro-
sor, as a function of the number of processors (log2 scale). cessor, as a function of the number of processors (log2 scale).
 10

B. Searching space of size 264

Minimal Grover 56 bits
25

Minimal Grover 64 bits

Total time per CPU (seconds, log2)

20

55

Total surface code cycles (log2) per CPU

15
50

45
10

p_g=1e-4 40
p_g=1e-5
5 35
p_g=1e-6
p_g=1e-7
30 p_g=1e-4
1 year
0 p_g=1e-5
0 5 10 15 20 25 30 25 p_g=1e-6
CPUs (log2) p_g=1e-7
20 Ideal Grover (non-black-box)
Theoretical lower bound (black-box)
FIG. 28. Running Grover’s algorithm with a trivial oracle, for a 0 5 10 15 20 25 30
CPUs (log2)
searching space of size 256 . Required time per processor, as a func-
tion of the number of processors (log2 scale). The dotted horizontal
line indicates one year. FIG. 31. Running Grover’s algorithm with a trivial oracle, for a
searching space of size 264 . Required surface clock cycles per pro-
cessor, as a function of the number of processors (log2 scale).
1e6 Minimal Grover 56 bits
2.00 p_g=1e-4
p_g=1e-5 Minimal Grover 64 bits
1.75 p_g=1e-6 25.0
p_g=1e-7
Total physical footprint per CPU

1.50 Total time per CPU (seconds, log2) 22.5

1.25 20.0

1.00 17.5

0.75 15.0

0.50 12.5

10.0 p_g=1e-4
0.25 p_g=1e-5
7.5 p_g=1e-6
p_g=1e-7
0 5 10 15 20 25 30
CPUs (log2) 5.0 1 year
0 5 10 15 20 25 30
CPUs (log2)
FIG. 29. Running Grover’s algorithm with a trivial oracle, for a
searching space of size 256 . Physical footprint (physical qubits) per
FIG. 32. Running Grover’s algorithm with a trivial oracle, for a
processor, as a function of the number of processors (log2 scale).
searching space of size 264 . Required time per processor, as a func-
tion of the number of processors (log2 scale).
Minimal Grover 56 bits
50
p_g=1e-4 1e6 Minimal Grover 64 bits
p_g=1e-5 3.0 p_g=1e-4
45 p_g=1e-6 p_g=1e-5
p_g=1e-7 p_g=1e-6
Total physical footprint (log2)

2.5 p_g=1e-7
40
Total physical footprint per CPU

35 2.0

30 1.5

25 1.0

20 0.5

0 5 10 15 20 25 30
CPUs (log2) 0.0
0 5 10 15 20 25 30
CPUs (log2)

FIG. 30. Running Grover’s algorithm with a trivial oracle, for

a searching space of size 256 . Total physical footprint (physical FIG. 33. Running Grover’s algorithm with a trivial oracle, for a
qubits), as a function of the number of processors (log2 scale). Note searching space of size 264 . Physical footprint (physical qubits) per
that the qubits are not correlated across processors. processor, as a function of the number of processors (log2 scale).
 11

FIG. 36. Running Grover’s algorithm with a trivial oracle, for a

Minimal Grover 64 bits
searching space of size 2128 . Required time per processor, as a func-
50 p_g=1e-4
p_g=1e-5 tion of the number of processors (log2 scale).
45 p_g=1e-6
p_g=1e-7
Total physical footprint (log2)

40

35

30

25

20

0 5 10 15 20 25 30 Minimal Grover 128 bits

CPUs (log2) 1e7
3.5 p_g=1e-4
p_g=1e-5
3.0 p_g=1e-6
FIG. 34. Running Grover’s algorithm with a trivial oracle, for p_g=1e-7

Total physical footprint per CPU

a searching space of size 264 . Total physical footprint (physical 2.5
qubits), as a function of the number of processors (log2 scale). Note
that the qubits are not correlated across processors. 2.0

1.5

1.0

0.5
C. Searching space of size 2128
0.0
0 10 20 30 40 50 60
CPUs (log2)
Minimal Grover 128 bits
FIG. 37. Running Grover’s algorithm with a trivial oracle, for a
90
searching space of size 2128 . Physical footprint (physical qubits) per
Total surface code cycles (log2) per CPU

80
processor, as a function of the number of processors (log2 scale).

70

60

p_g=1e-4
50
p_g=1e-5
p_g=1e-6
40 p_g=1e-7
Ideal Grover (non-black-box)
Theoretical lower bound (black-box)
30
0 10 20 30 40 50 60
CPUs (log2)

Minimal Grover 128 bits

FIG. 35. Running Grover’s algorithm with a trivial oracle, for a p_g=1e-4
searching space of size 2128 . Required surface clock cycles per pro- p_g=1e-5
80 p_g=1e-6
cessor, as a function of the number of processors (log2 scale). p_g=1e-7
Total physical footprint (log2)

70

Minimal Grover 128 bits 60

p_g=1e-4
p_g=1e-5 50
50 p_g=1e-6
Total time per CPU (seconds, log2)

p_g=1e-7
1 year 40
40
30
30
20
0 10 20 30 40 50 60
20 CPUs (log2)

10
FIG. 38. Running Grover’s algorithm with a trivial oracle, for a
searching space of size 2128 . Total physical footprint (physical
0 qubits), as a function of the number of processors (log2 scale). Note
0 20 40 60 80 100
CPUs (log2) that the qubits are not correlated across processors.
 12

D. Searching space of size 2256

Minimal Grover 256 bits
90 p_g=1e-4
p_g=1e-5
p_g=1e-6
Minimal Grover 256 bits 80 p_g=1e-7

Total physical footprint (log2)

160 70
Total surface code cycles (log2) per CPU

150 60

140 50

130 40

120 30
p_g=1e-4
p_g=1e-5
110 20
p_g=1e-6 0 10 20 30 40 50 60
p_g=1e-7 CPUs (log2)
100 Ideal Grover (non-black-box)
Theoretical lower bound (black-box)
0 10 20 30 40 50 60 FIG. 42. Running Grover’s algorithm with a trivial oracle, for a
CPUs (log2)
searching space of size 2256 . Total physical footprint (physical
qubits), as a function of the number of processors (log2 scale). Note
FIG. 39. Running Grover’s algorithm with a trivial oracle, for a that the qubits are not correlated across processors.
searching space of size 2256 . Required surface clock cycles per pro-
cessor, as a function of the number of processors (log2 scale).

Minimal Grover 256 bits

120 p_g=1e-4 VII. RSA SCHEMES
p_g=1e-5
p_g=1e-6
Total time per CPU (seconds, log2)

100 p_g=1e-7
1 year In the following section we compute the space/time trade-
80
offs for attacking public-key cryptographic schemes based
on factoring large numbers, namely RSA-1024, RSA-2048,
60
RSA-3072, RSA-4096, RSA-7680 and RSA-15360. For each
scheme, we plot the space/time tradeoff points then fit it with
40 a third degree polynomial, for pg = 10−3 and pg = 10−5 ,
respectively.
20

0 25 50 75 100 125 150 175 200

CPUs (log2)

A. RSA-1024
FIG. 40. Running Grover’s algorithm with a trivial oracle, for a
searching space of size 2256 . Required time per processor, as a func-
tion of the number of processors (log2 scale).

1e8 Minimal Grover 256 bits

p_g=1e-4
p_g=1e-5
2.0 p_g=1e-6
p_g=1e-7
Total physical footprint per CPU

1.5

1.0

0.5
FIG. 43. RSA-1024 space/time tradeoffs with physical error rate per
0.0
gate pg = 10−3 . The scale is logarithmic (base 2). Approximately
0 10 20 30 40 50 60 y(16.3987) ≈ 3.01 × 107 physical qubits are required to break the
CPUs (log2)
scheme in one day (24 hours). The number of T gates in the circuit is
3.01 × 1011 , the corresponding number of logical qubits is 2050, and
FIG. 41. Running Grover’s algorithm with a trivial oracle, for a the total number of surface code cycles is 5.86 × 1013 . The quantity
searching space of size 2256 . Physical footprint (physical qubits) per R2 represents the coefficient of determination (closer to 1, better the
processor, as a function of the number of processors (log2 scale). fitting). The classical security parameter is approximately 80 bits.
 13

FIG. 46. RSA-2048 space/time tradeoffs with physical error rate per
gate pg = 10−5 . The scale is logarithmic (base 2). Approximately
y(16.3987) ≈ 9.78 × 106 physical qubits are required to break the
scheme in one day (24 hours). The number of T gates in the circuit is
2.41 × 1012 , the corresponding number of logical qubits is 4098, and
the total number of surface code cycles is 2.35 × 1014 . The classical
security parameter is approximately 112 bits.

FIG. 44. RSA-1024 space/time tradeoffs with physical error rate per
gate pg = 10−5 . The scale is logarithmic (base 2). Approximately
y(16.3987) ≈ 2.14 × 106 physical qubits are required to break the
scheme in one day (24 hours). The number of T gates in the circuit is
3.01 × 1011 , the corresponding number of logical qubits is 2050, and
the total number of surface code cycles is 2.93 × 1013 . The classical C. RSA-3072
security parameter is approximately 80 bits.

B. RSA-2048

FIG. 47. RSA-3072 space/time tradeoffs with physical error rate per
gate pg = 10−3 . The scale is logarithmic (base 2). Approximately
y(16.3987) ≈ 6.41 × 108 physical qubits are required to break the
scheme in one day (24 hours). The number of T gates in the circuit is
8.12 × 1012 , the corresponding number of logical qubits is 6146, and
the total number of surface code cycles is 1.58 × 1015 . The classical
security parameter is approximately 128 bits.

FIG. 45. RSA-2048 space/time tradeoffs with physical error rate per
gate pg = 10−3 . The scale is logarithmic (base 2). Approximately
y(16.3987) ≈ 1.72 × 108 physical qubits are required to break the
scheme in one day (24 hours). The number of T gates in the circuit is
2.41 × 1012 , the corresponding number of logical qubits is 4098, and
the total number of surface code cycles is 4.69 × 1014 . The classical
security parameter is approximately 112 bits.

FIG. 48. RSA-3072 space/time tradeoffs with physical error rate per
gate pg = 10−5 . The scale is logarithmic (base 2). Approximately
y(16.3987) ≈ 2.55 × 107 physical qubits are required to break the
scheme in one day (24 hours). The number of T gates in the circuit is
8.12 × 1012 , the corresponding number of logical qubits is 6146, and
the total number of surface code cycles is 7.91 × 1014 . The classical
security parameter is approximately 128 bits.
 14

D. RSA-4096 FIG. 51. RSA-7680 space/time tradeoffs with physical error rate per
gate pg = 10−3 . The scale is logarithmic (base 2). Approximately
y(16.3987) ≈ 7.70 × 1010 physical qubits are required to break the
scheme in one day (24 hours). The number of T gates in the circuit
is 1.27 × 1014 , the corresponding number of logical qubits is 15362,
and the total number of surface code cycles is 2.64 × 1016 . The
classical security parameter is approximately 192 bits.

FIG. 49. RSA-4096 space/time tradeoffs with physical error rate per
gate pg = 10−3 . The scale is logarithmic (base 2). Approximately
y(16.3987) ≈ 1.18 × 109 physical qubits are required to break the
scheme in one day (24 hours). The number of T gates in the circuit is
1.92 × 1013 , the corresponding number of logical qubits is 8194, and
the total number of surface code cycles is 3.75 × 1015 . The classical
security parameter is approximatively approximately 156 bits. FIG. 52. RSA-7680 space/time tradeoffs with physical error rate per
gate pg = 10−5 . The scale is logarithmic (base 2). Approximately
y(16.3987) ≈ 7.41 × 109 physical qubits are required to break the
scheme in one day (24 hours). The number of T gates in the circuit
is 1.27 × 1014 , the corresponding number of logical qubits is 15362,
and the total number of surface code cycles is 2.47 × 1016 . The
classical security parameter is approximately 192 bits.

FIG. 50. RSA-4096 space/time tradeoffs with physical error rate per
gate pg = 10−5 . The scale is logarithmic (base 2). Approximately
y(16.3987) ≈ 5.70 × 107 physical qubits are required to break the
scheme in one day (24 hours). The number of T gates in the circuit is F. RSA-15360
1.92 × 1013 , the corresponding number of logical qubits is 8194, and
the total number of surface code cycles is 1.88 × 1015 . The classical
security parameter is approximatively approximately 156 bits.

E. RSA-7680

FIG. 53. RSA-15360 space/time tradeoffs with physical error rate per
gate pg = 10−3 . The scale is logarithmic (base 2). Approximately
y(16.3987) ≈ 4.85 × 1012 physical qubits are required to break the
scheme in one day (24 hours). The number of T gates in the circuit
is 1.01 × 1015 , the corresponding number of logical qubits is 30722,
and the total number of surface code cycles is 2.24 × 1017 . The
classical security parameter is approximately 256 bits.
 15

FIG. 54. RSA-15360 space/time tradeoffs with physical error rate per FIG. 56. NIST P-160 elliptic curve space/time tradeoffs with phys-
gate pg = 10−5 . The scale is logarithmic (base 2). Approximately ical error rate per gate pg = 10−5 . The scale is logarithmic (base
y(16.3987) ≈ 7.64 × 1010 physical qubits are required to break the 2). Approximately y(16.3987) ≈ 1.38 × 106 physical qubits are
scheme in one day (24 hours). The number of T gates in the circuit required to break the scheme in one day (24 hours). The number of
is 1.01 × 1015 , the corresponding number of logical qubits is 30722, T gates in the circuit is 2.08 × 1011 , the corresponding number of
and the total number of surface code cycles is 1.98 × 1017 . The logical qubits is 1466, and the total number of surface code cycles is
classical security parameter is approximately 256 bits. 2.03 × 1013 . The classical security parameter is 80 bits.

VIII. ELLIPTIC CURVE SCHEMES

In the following section we compute the space/time trade- B. NIST P-192

offs for attacking public-key cryptographic schemes based on
solving the discrete logarithm problem in finite groups gen-
erated over elliptic curves, namely NIST P-160, NIST P-
192, NIST P-224, NIST P-256, NIST P-384 and NIST P-
521. For each scheme, we plot the space/time tradeoff points
then fit it with a third degree polynomial, for pg = 10−3
and pg = 10−5 , respectively. We used the logical circuits
from [14].

A. NIST P-160

FIG. 57. NIST P-192 space/time tradeoffs with physical error rate
per gate pg = 10−3 . The scale is logarithmic (base 2). Approx-
imately y(16.3987) ≈ 3.37 × 107 physical qubits are required to
break the scheme in one day (24 hours). The number of T gates in
the circuit is 3.71×1011 , the corresponding number of logical qubits
is 1754, and the total number of surface code cycles is 7.23 × 1013 .
The classical security parameter is 96 bits.

FIG. 55. NIST P-160 elliptic curve space/time tradeoffs with phys-
ical error rate per gate pg = 10−3 . The scale is logarithmic (base
2). Approximately y(16.3987) ≈ 1.81 × 107 physical qubits are
required to break the scheme in one day (24 hours). The number of
T gates in the circuit is 2.08 × 1011 , the corresponding number of
logical qubits is 1466, and the total number of surface code cycles is
4.05 × 1013 . The classical security parameter is 80 bits.
 16

FIG. 58. NIST P-192 space/time tradeoffs with physical error rate D. NIST P-256
per gate pg = 10−5 . The scale is logarithmic (base 2). Approx-
imately y(16.3987) ≈ 2.18 × 106 physical qubits are required to
break the scheme in one day (24 hours). The number of T gates in
the circuit is 3.71×1011 , the corresponding number of logical qubits
is 1754, and the total number of surface code cycles is 3.62 × 1013 .
The classical security parameter is 96 bits.

FIG. 61. NIST P-256 elliptic curve space/time tradeoffs with phys-
ical error rate per gate pg = 10−3 . The scale is logarithmic (base
C. NIST P-224 2). Approximately y(16.3987) ≈ 6.77 × 107 physical qubits are
required to break the scheme in one day (24 hours). The number of
T gates in the circuit is 8.82 × 1011 , the corresponding number of
logical qubits is 2330, and the total number of surface code cycles is
1.72 × 1014 . The classical security parameter is 128 bits.

FIG. 59. NIST P-224 elliptic curve space/time tradeoffs with phys-
ical error rate per gate pg = 10−3 . The scale is logarithmic (base
2). Approximately y(16.3987) ≈ 4.91 × 107 physical qubits are FIG. 62. NIST P-256 elliptic curve space/time tradeoffs with phys-
required to break the scheme in one day (24 hours). The number of ical error rate per gate pg = 10−5 . The scale is logarithmic (base
T gates in the circuit is 5.90 × 1011 , the corresponding number of 2). Approximately y(16.3987) ≈ 4.64 × 106 physical qubits are
logical qubits is 2042, and the total number of surface code cycles is required to break the scheme in one day (24 hours). The number of
1.15 × 1014 . The classical security parameter is 112 bits. T gates in the circuit is 8.82 × 1011 , the corresponding number of
logical qubits is 2330, and the total number of surface code cycles is
8.60 × 1013 . The classical security parameter is 128 bits.

E. NIST P-384

FIG. 60. NIST P-224 elliptic curve space/time tradeoffs with phys-
ical error rate per gate pg = 10−5 . The scale is logarithmic (base
2). Approximately y(16.3987) ≈ 3.24 × 106 physical qubits are
required to break the scheme in one day (24 hours). The number of
T gates in the circuit is 5.90 × 1011 , the corresponding number of
logical qubits is 2042, and the total number of surface code cycles is
5.75 × 1013 . The classical security parameter is 112 bits.
 17

FIG. 63. NIST P-384 elliptic curve space/time tradeoffs with phys-
ical error rate per gate pg = 10−3 . The scale is logarithmic (base
2). Approximately y(16.3987) ≈ 2.27 × 108 physical qubits are
required to break the scheme in one day (24 hours). The number of
T gates in the circuit is 3.16 × 1012 , the corresponding number of
logical qubits is 3484, and the total number of surface code cycles is
6.17 × 1014 . The classical security parameter is 192 bits.

FIG. 66. NIST P-521 elliptic curve space/time tradeoffs with phys-
ical error rate per gate pg = 10−5 . The scale is logarithmic (base
2). Approximately y(16.3987) ≈ 2.30 × 107 physical qubits are
required to break the scheme in one day (24 hours). The number of
T gates in the circuit is 7.98 × 1012 , the corresponding number of
logical qubits is 4719, and the total number of surface code cycles is
7.78 × 1014 . The classical security parameter is 256 bits.

FIG. 64. NIST P-384 elliptic curve space/time tradeoffs with phys-
ical error rate per gate pg = 10−5 . The scale is logarithmic (base IX. SUMMARY AND CONCLUSIONS
2). Approximately y(16.3987) ≈ 1.28 × 107 physical qubits are
required to break the scheme in one day (24 hours). The number of
T gates in the circuit is 3.16 × 1012 , the corresponding number of We analyzed the security of several widely used symmet-
logical qubits is 3484, and the total number of surface code cycles is ric ciphers and hash functions against parallelized quantum
3.08 × 1014 . The classical security parameter is 192 bits. adversaries. We computed the security parameter, wall-time
and physical footprint for each cryptographic primitive. Our
attack model was based on a brute force searching via a par-
allelized version of Grover’s algorithm, assuming a surface-
code fault-tolerant architecture based on defects and braiding
techniques.
It is worth noting that throughout we are assuming that
brute-force search where we treat the cryptographic function
as a black-box is essentially the optimal attack against SHA
and AES, which is currently believed to be the case.
Some symmetric key algorithms are susceptible in a model
F. NIST P-521 that permits “superposition attacks” [22]. In most realistic in-
stances, these attacks are not practical, however they do shed
light on the limitations of certain security proof methods in
a quantum context, and remind us that we shouldn’t take for
granted that non-trivial attacks on symmetric key cryptogra-
phy may be possible. For example, very recently, there have
been several cryptanalysis results [23] and [24] that attempt to
reduce breaking some symmetric algorithms to solving a sys-
tem of non-linear equations. Solving these non-linear equa-
tions is then attacked using a modified version of the quantum
linear equation solver algorithm [25]. The results are heavily
dependent on the condition number of the non-linear system,
which turns to be hard to compute (it is not known for most
ciphers and hash functions such as AES or SHA). Provided
the condition number is relatively small, then one may get an
FIG. 65. NIST P-521 elliptic curve space/time tradeoffs with phys- advantage compared to brute-force Grover search. However
ical error rate per gate pg = 10−3 . The scale is logarithmic (base at this time it is not clear whether this is indeed the case, and
2). Approximately y(16.3987) ≈ 6.06 × 108 physical qubits are we do not have large-scale quantum computers to experiment
required to break the scheme in one day (24 hours). The number of with.
T gates in the circuit is 7.98 × 1012 , the corresponding number of The quantum security parameter (based on our assumptions
logical qubits is 4719, and the total number of surface code cycles is of using state-of-the-art algorithms and fault-tolerance meth-
1.56 × 1015 . The classical security parameter is 256 bits. ods) for symmetric and hash-based cryptographic schemes
 18

is summarized in Table I. For more details about space/time Name nq Tc scc s

tradeoffs achievable via parallelization of Grover’s algorithm P-160 1.81 × 107 2.08 × 1011 4.05 × 1013 80
please see the corresponding Sec. III, Sec. IV and Sec. V, re- P-192 3.37 × 107 3.71 × 1011 7.23 × 1013 96
spectively. P-224 4.91 × 107 5.90 × 1011 1.15 × 1014 112
P-256 6.77 × 107 8.82 × 1011 1.72 × 1014 128
Name qs
P-384 2.27 × 108 3.16 × 1012 6.17 × 1014 192
AES-128 106
P-521 6.06 × 108 7.92 × 1012 1.56 × 1015 260
AES-192 139
AES-256 172 TABLE III. The total physical footprint (nq) required to break the
SHA-256 166 ECC schemes in 24 hours, together with the required number of T
SHA3-256 167 gates (T c), the corresponding number of surface code cycles (scc),
and the corresponding classical security parameter (s). We assume a
Bitcoin’s PoW 75
very conservative physical error rate per gate pg = 10−3 , more likely
to be achievable by the first generations of fault-tolerant quantum
TABLE I. Quantum security parameter (qs) for the AES family of
computers.
ciphers, SHA family of hash functions, and Bitcoin, assuming a con-
servative physical error rate per gate pg = 10−4 .

We also analyzed the security of asymmetric (public-key)

cryptography, in particular RSA and ECC, in the light of new
improvements in fault-tolerant quantum error correction based
on surface code lattice surgery techniques. We computed the classical security.
space/time tradeoff required to attack every scheme, using
physical error rates of 10−3 and 10−5 , respectively. We fit-
ted the data with a third degree polynomial, which resulted Recent developments in the theory of fault-tolerant quan-
in an analytical formula of the number of qubits required to tum error correction have great impact on evaluating the ef-
break the scheme as a function of time. fective strength of cryptographic schemes against quantum at-
The total number of physical qubits required to break the tacks, as the fault-tolerant layer of a quantum computation is
RSA schemes in 24 hours, together with the required number the most resource-intensive part of running a quantum algo-
of T gates, corresponding number of surface code cycles and rithm. Therefore, monitoring the advances in the theory of
corresponding classical security parameter is summarized in quantum error correction is of crucial importance when esti-
Table II. For more details about possible space/time tradeoffs mating the strength (or weakness) of a cryptographic scheme
please see the corresponding Section VII of the manuscript. against a quantum adversary. This work serves as a bench-
The total number of physical qubits required to break the mark against which the impact of future advances can be com-
ECC schemes in 24 hours, together with the required num- pared.
ber of T gates, corresponding number of surface code cy-
cles and corresponding classical security parameter is sum-
marized in in Table III. For more details about possible
space/time tradeoffs please see the corresponding Section VIII
of the manuscript. As observed before in [14], breaking
RSA schemes demands more quantum resources in compar-
ison with elliptic curve-based schemes, for the same level of

Name nq Tc scc s
RSA-1024 3.01 × 107 3.01 × 1011 5.86 × 1013 80
RSA-2048 1.72 × 108 2.41 × 1012 4.69 × 1014 112
RSA-3072 6.41 × 108 8.12 × 1012 1.58 × 1015 128
RSA-4096 1.18 × 109 1.92 × 1013 3.75 × 1015 156 ACKNOWLEDGMENTS
RSA-7680 7.70 × 1010 1.27 × 1014 2.64 × 1016 192
RSA-15360 4.85 × 1012 1.01 × 1015 2.24 × 1017 256

TABLE II. The total physical footprint (nq) required to break the Most of this work is based on research supported by the
RSA schemes in 24 hours, together with the required number of T Global Risk Institute for its members. We also acknowledge
gates (T c), the corresponding number of surface code cycles (scc), support from NSERC and CIFAR. IQC and the Perimeter In-
and the corresponding classical security parameter (s). We assume a stitute are supported in part by the Government of Canada
very conservative physical error rate per gate pg = 10−3 , more likely and the Province of Ontario. Vlad Gheorghiu thanks Austin
to be achievable by the first generations of fault-tolerant quantum Fowler for helpful discussions and clarifications regarding lat-
computers. tice surgery methods.
 19

[1] J. Katz and Y. Lindell, Introduction to Modern Cryptography discrete logarithms,” (2017), arXiv:1706.06752 [quant-ph],
(Chapman & Hall/Crc Cryptography and Network Security Se- 1706.06752.
ries) (Chapman & Hall/CRC, 2007). [15] A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Mar-
[2] P. W. Shor, SIAM Journal on Computing 26, 1484 (1997). golus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter,
[3] L. K. Grover, Phys. Rev. Lett. 79, 325 (1997). Phys. Rev. A 52, 3457 (1995).
[4] M. A. Nielsen and I. L. Chuang, Quantum Computation and [16] S. A. Cuccaro, T. G. Draper, S. A. Kutin, and D. P. Moulton,
Quantum Information, 5th ed. (Cambridge University Press, arXiv preprint quant-ph/0410184 (2004).
Cambridge, 2000). [17] S. Beauregard, Quantum Info. Comput. 3, 175 (2003).
[5] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cle- [18] M. Grassl, B. Langenberg, M. Roetteler, and R. Steinwandt,
land, Phys. Rev. A 86, 032324 (2012). in Post-Quantum Cryptography, edited by T. Takagi (Springer
[6] C. Horsman, A. G. Fowler, S. Devitt, and R. V. Meter, New International Publishing, Cham, 2016) pp. 29–43.
Journal of Physics 14, 123011 (2012). [19] NIST, “Federal information processing standards publi-
[7] S. Bravyi and J. Haah, Phys. Rev. A 86, 052329 (2012). cation 180-2,” (2002), see also the Wikipedia entry
[8] A. G. Fowler and C. Gidney, “Low overhead quantum compu- http://en.wikipedia.org/wiki/SHA-2.
tation using lattice surgery,” (2018), arXiv:1808.06709 [quant- [20] NIST, “Federal information processing standards pub-
ph]. lication 202,” (2015), see also the Wikipedia entry
[9] D. Litinski, “A Game of Surface Codes: Large-Scale Quantum http://en.wikipedia.org/wiki/SHA-3.
Computing with Lattice Surgery,” (2018), arXiv:1808.02892 [21] “Bitcoin difficulty (online),” https://bitcoinwisdom.
[quant-ph], 1808.02892. com/bitcoin/difficulty.
[10] C. Zalka, “Grover’s quantum searching algorithm is optimal,” [22] M. Kaplan, G. Leurent, A. Leverrier, and M. Naya-Plasencia,
E-print arXiv:quant-ph/9711070. “Breaking symmetric cryptosystems using quantum period
[11] S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” finding,” E-print arXiv:1602.05973 [quant-ph].
(2009). [23] Y.-A. Chen and X.-S. Gao, “Quantum Algorithms for Boolean
[12] M. Amy, O. Di Matteo, V. Gheorghiu, M. Mosca, A. Parent, Equation Solving and Quantum Algebraic Attack on Cryptosys-
and J. Schanck, in Selected Areas in Cryptography – SAC 2016, tems,” (2017), arXiv:1712.06239 [quant-ph].
edited by R. Avanzi and H. Heys (Springer International Pub- [24] Y.-A. Chen, X.-S. Gao, and C.-M. Yuan, “Quantum Algorithms
lishing, Cham, 2017) pp. 317–337. for Optimization and Polynomial Systems Solving over Finite
[13] A. G. Fowler, S. J. Devitt, and C. Jones, Scientific Reports 3, Fields,” (2018), arXiv:1802.03856 [quant-ph].
1939 EP (2013). [25] A. W. Harrow, A. Hassidim, and S. Lloyd, Phys. Rev. Lett. 103,
[14] M. Roetteler, M. Naehrig, K. M. Svore, and K. Lauter, 150502 (2009).
“Quantum resource estimates for computing elliptic curves