ETSI GR QSC 006 V1.1.1 (2017-02)

ETSI GR QSC 006 V1.1.1 (2017-02)
GROUP REPORT
Quantum-Safe Cryptography (QSC);
Limits to Quantum Computing applied to symmetric key sizes
Disclaimer

The present document has been produced and approved by the Quantum-Safe Cryptography (QSC) ETSI Industry

Specification Group (ISG) and represents the views of those members who participated in this ISG.

The present document may be made available in electronic versions and/or in print. The content of any electronic and/or

print versions of the present document shall not be modified without the prior written authorization of ETSI. In case of any

existing or perceived difference in contents between such versions and/or in print, the only prevailing document is the

print of the Portable Document Format (PDF) version kept on a specific network drive within ETSI Secretariat.

Users of the present document should be aware that the document may be subject to revision or change of status.

Information on the current status of this and other ETSI documents is available at

If you find errors in the present document, please send your comment to one of the following services:

No part may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying

The content of the PDF version shall not be modified without the written authorization of ETSI.

DECT , PLUGTESTS , UMTS and the ETSI logo are Trade Marks of ETSI registered for the benefit of its Members.

3GPP and LTE™ are Trade Marks of ETSI registered for the benefit of its Members and

GSM® and the GSM logo are Trade Marks registered and owned by the GSM Association.

Intellectual Property Rights ................................................................................................................................ 4

Foreword ............................................................................................................................................................. 4

Modal verbs terminology .................................................................................................................................... 4

Executive summary ............................................................................................................................................ 4

Introduction ........................................................................................................................................................ 4

1 Scope ........................................................................................................................................................ 6

2 References ................................................................................................................................................ 6

2.1 Normative references ......................................................................................................................................... 6

2.2 Informative references ........................................................................................................................................ 6

3 Symbols and abbreviations ....................................................................................................................... 7

3.1 Symbols .............................................................................................................................................................. 7

3.2 Abbreviations ..................................................................................................................................................... 7

4 Background .............................................................................................................................................. 8

4.1 Asymmetric cryptography and quantum computing .......................................................................................... 8

4.2 Symmetric cryptography and quantum computers ............................................................................................. 8

4.3 Number of qubits ................................................................................................................................................ 8

4.4 Outline of the present document ......................................................................................................................... 9

5 Quantum computers in 2050 .................................................................................................................... 9

5.1 Approach ............................................................................................................................................................ 9

5.2 Moore's Law ....................................................................................................................................................... 9

5.3 'Commercial' quantum computers .................................................................................................................... 10

5.4 Worst case quantum computers ........................................................................................................................ 10

5.5 An upper bound for quantum computing budgets ............................................................................................ 11

6 Key and parameter sizes ......................................................................................................................... 11

6.1 Approach .......................................................................................................................................................... 11

6.2 Symmetric keys ................................................................................................................................................ 12

6.3 Hash output lengths .......................................................................................................................................... 12

7 Conclusions ............................................................................................................................................ 13

History .............................................................................................................................................................. 14

IPRs essential or potentially essential to the present document may have been declared to ETSI. The information

pertaining to these essential IPRs, if any, is publicly available for ETSI members and non-members, and can be found

in ETSI SR 000 314: "Intellectual Property Rights (IPRs); Essential, or potentially Essential, IPRs notified to ETSI in

respect of ETSI standards", which is available from the ETSI Secretariat. Latest updates are available on the ETSI Web

Pursuant to the ETSI IPR Policy, no investigation, including IPR searches, has been carried out by ETSI. No guarantee

can be given as to the existence of other IPRs not referenced in ETSI SR 000 314 (or the updates on the ETSI Web

This Group Report (GR) has been produced by ETSI Industry Specification Group (ISG) Quantum-Safe

In the present document "should", "should not", "may", "need not", "will", "will not", "can" and "cannot" are to be

interpreted as described in clause 3.2 of the ETSI Drafting Rules (Verbal forms for the expression of provisions).

"must" and "must not" are NOT allowed in ETSI deliverables except when used in direct citation.

The present document analyses the impact of a quantum computer on symmetric cryptographic primitives. A worst-case

estimate is derived for the maximum available quantum computing power in 2050. This leads to the conclusion that

A quantum computer will require an enormous change in the cryptographic landscape [i.7]. This is why research and

standardization effort is put into finding quantum-safe asymmetric alternatives for RSA, (EC) Diffie-Hellman, and

(EC)DSA. Significant effort from industry will be put into preparing for the necessary transition to these new

However, symmetric primitives like AES, SHA-2, and SHA-3 are equally integrated into the numerous information

security solutions that exist worldwide. Since a quantum computer can also speed up attacks on symmetric primitives

[i.6], it is important to analyse how long these symmetric primitives - and their most-used key sizes - will remain

The present document studies the long-term security of symmetric primitives such as AES-256, SHA-2, and SHA-3. A

scientific approach shows that attacks cannot continue to improve at an exponential rate forever. Moore's Law may

assert that transistors become twice as small roughly every 1,5 years, but this trend cannot continue and in fact has

already stopped. While it is unknown whether a similar trend will appear for quantum computers, it is possible to put an

upper bound on the quantum computing power that could be developed in the foreseeable future. The analysis in the

present document is based on conservative assumptions and estimates. This does not result in exact dates on when each

primitive will be broken, but it does assert their security for at least a certain period of time.

The present document concludes that there are existing and widely used symmetric (AES-256) and hash primitives

(SHA-2 and SHA-3 with an output length of at least 256 bits) that will withstand quantum computer attacks until way

after 2050. It is reassuring to know that for these symmetric primitives there is no need to find and heavily scrutinize

alternatives within the next few years, like is done for the asymmetric primitives.

Note that this does not mean that there is no need to look into symmetric algorithms when it comes to the threat of a

quantum computer. On the contrary, industry does have to worry about symmetric algorithms, since there are billions of

devices in the world that rely on a symmetric cipher with a key length of 128 bits or less. Examples include mobile

communication with e.g. GSM or TETRA. Unfortunately, the calculations that are used in the present document to

assert that AES-256 will remain secure until way after 2050 cannot be used to predict when a quantum computer can

attack AES-128, or any other cipher with a short key length. Therefore, industry is advised to identify where their

products rely on smaller key and hash output lengths, and to start investigating the necessary steps for a transition to

primitives with key lengths that will withstand quantum computer attacks like the ones investigated in the present

The present document gives information on the long-term suitability of symmetric cryptographic primitives in the face

References are either specific (identified by date of publication and/or edition number or version number) or

non-specific. For specific references, only the cited version applies. For non-specific references, the latest version of the

NOTE: While any hyperlinks included in this clause were valid at the time of publication, ETSI cannot guarantee

The following referenced documents are not necessary for the application of the present document but they assist the

[i.2] Thomas Monz et al (2011): "14-Qubit Entanglement: Creation and Coherence", Phys. Rev.

[i.3] Christof Zalka: "Grover's quantum searching algorithm is optimal", Phys. Rev. A 60, 2746, 1999,

[i.4] PriceWaterhouseCoopers, The world in 2050 (February 2015): "Will the shift in global economic

NOTE: Available at www.pwc.com/gx/en/issues/the-economy/assets/world-in-2050-february-2015.pdf.

[i.6] Lov K. Grover: "A fast quantum mechanical algorithm for database search", STOC 1996,

[i.7] Peter W. Shor: "Polynomial-time algorithms for prime factorization and discrete logarithms on a

[i.8] Markus Grassl, Brandon Langenberg, Martin Roetteler, and Rainer Steinwandt (December 2015):

[i.9] Matthew Amy, Olivia Di Matteo, Vlad Gheorghiu, Michele Mosca, Alex Parent, and John

Schanck (March 2016): "Estimating the cost of generic quantum pre-image attacks on SHA-2 and

[i.10] Marc Kaplan, Gactan Leurent, Anthony Leverrier, and María Naya-Plasencia (February 2016):

[i.11] Andrey Bogdanov, Dmitry Khovratovich, and Christian Rechberger (2013): "Biclique analysis of

[i.12] Daniel J. Bernstein (May 2009): "Cost analysis of hash collisions: will quantum computers make

[i.13] Simon J. Devitt, William J. Munro, and Kae Nemoto (June 2013): "Quantum Error Correction for

[i.14] European Commission D-G for Research and Innovation: "Global Europe 2050", European Union

[i.15] Arjen K. Lenstra and Eric R. Verheul (2001): "Selecting Cryptographic Key Sizes", Journal of

[i.16] Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland

(September 2012): "Surface codes: Towards practical large-scale quantum computation", Phys.

If a large quantum computer is built, it would pose a threat to several cryptographic primitives. Most notably, RSA,

(EC) Diffie-Hellman, and (EC)DSA would be completely broken by Shor's algorithm [i.7]. Here completely broken

means that, given complete quantum control over a sufficient number of qubits, a reasonable size (O(n )) quantum

circuit can break the underlying mathematical problem in reasonable (O(n )) time for a private key of O(n) bits. This

ignores the fact that the cryptographic primitive needs to be implemented in a quantum circuit and also ignores quantum

error correction (QEC) to avoid decoherence. Both would introduce a polynomial overhead. QEC is a technique that

allows stable computation with unstable qubits. Since reading out qubits destroys their quantum properties this

technique is more involved than normal error correction techniques. QEC introduces a significant overhead in the

circuit size and computation time [i.8], [i.9]. Most types of qubits tend to be unstable so it seems likely that QEC will be

needed in a large quantum computer. For a more in-depth treatment of QEC see [i.13].

For symmetric algorithms the impact of quantum computers is less clear. A rule of thumb says that Grover's algorithm

effectively halves the key size for these algorithms [i.6]. However, the aforementioned 'polynomial overhead'

considerably increases the complexity of this algorithm: breaking a 128-bit AES key costs about 2 gates and takes the

time of 2 gate operations [i.8] rather than 2 operations predicted by the rule of thumb. Finding pre-images for SHA-2

and SHA-3 also has a considerable overhead, costing the time equivalent to 2 hash function calls for both SHA-2 and

SHA-3 [i.9], where the rule of thumb would predict 2 . The footprint of QEC further increases the number of qubits

from a few thousand to more than 10 million [i.9]. Since [i.8] attempts to minimize the number of qubits, while [i.9]

attempts to minimize the T-gate depth, different qubit and operation counts can be obtained for different

Existing symmetric algorithms might be vulnerable to other quantum attacks. For example [i.10] demonstrates that

several MAC and authenticated encryption modes can be broken with a quantum computer if an attacker has access to a

quantum implementation of the primitive and can query it with superpositions, which seems quite a strong assumption.

The present document assumes the use of algorithms that have no structural weaknesses that can be exploited by a

(quantum) adversary. This means that breaking such an algorithm is the same as solving the general search problem.

Grover's algorithm is optimal for solving the general search problem. It solves the general search problem on a set of

size N in √ time, while no quantum algorithm exists that solves this problem faster [i.3]. In addition,

implementing Grover's algorithm in parallel results in a classical time-memory trade-off: m quantum computers can

solve the general search problem in no less than / time, which can trivially be achieved by partitioning the

m problems of size N /m. The total cost of this parallel computation is so it is more efficient not

to parallelise the computation. As an example, one quantum computer could find a 256-bit AES key in about 2 time,

while 2 parallel quantum computers could find this key in about 2 time. The overall cost of the latter computation is

about 2 which is much more than the 2 cost of the single quantum computer. Nevertheless, parallelisation might

still be a sensible choice because no adversary is willing to wait longer than a few years for a decryption.