1、 ETSI GR QSC 006 V1.1.1 (2017-02) 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 thos
2、e members who participated in this ISG. It does not necessarily represent the views of the entire ETSI membership. GROUP REPORT ETSI ETSI GR QSC 006 V1.1.1 (2017-02) 2 Reference DGR/QSC-006 Keywords cyber security, quantum cryptography, security ETSI 650 Route des Lucioles F-06921 Sophia Antipolis C
3、edex - FRANCE Tel.: +33 4 92 94 42 00 Fax: +33 4 93 65 47 16 Siret N 348 623 562 00017 - NAF 742 C Association but non lucratif enregistre la Sous-Prfecture de Grasse (06) N 7803/88 Important notice The present document can be downloaded from: http:/www.etsi.org/standards-search The present document
4、 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 i
5、n 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
6、 of this and other ETSI documents is available at https:/portal.etsi.org/TB/ETSIDeliverableStatus.aspx If you find errors in the present document, please send your comment to one of the following services: https:/portal.etsi.org/People/CommiteeSupportStaff.aspx Copyright Notification No part may be
7、reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying and microfilm except as authorized by written permission of ETSI. The content of the PDF version shall not be modified without the written authorization of ETSI. The copyright and the foregoing restr
8、iction extend to reproduction in all media. European Telecommunications Standards Institute 2017. All rights reserved. DECTTM, PLUGTESTSTM, UMTSTMand the ETSI logo are Trade Marks of ETSI registered for the benefit of its Members. 3GPPTM and LTE are Trade Marks of ETSI registered for the benefit of
9、its Members and of the 3GPP Organizational Partners. GSM and the GSM logo are Trade Marks registered and owned by the GSM Association. ETSI ETSI GR QSC 006 V1.1.1 (2017-02) 3 Contents Intellectual Property Rights 4g3Foreword . 4g3Modal verbs terminology 4g3Executive summary 4g3Introduction 4g31 Scop
10、e 6g32 References 6g32.1 Normative references . 6g32.2 Informative references 6g33 Symbols and abbreviations . 7g33.1 Symbols 7g33.2 Abbreviations . 7g34 Background 8g34.1 Asymmetric cryptography and quantum computing 8g34.2 Symmetric cryptography and quantum computers . 8g34.3 Number of qubits 8g34
11、.4 Outline of the present document . 9g35 Quantum computers in 2050 9g35.1 Approach 9g35.2 Moores Law . 9g35.3 Commercial quantum computers 10g35.4 Worst case quantum computers 10g35.5 An upper bound for quantum computing budgets 11g36 Key and parameter sizes . 11g36.1 Approach 11g36.2 Symmetric key
12、s 12g36.3 Hash output lengths 12g37 Conclusions 13g3History 14g3ETSI ETSI GR QSC 006 V1.1.1 (2017-02) 4 Intellectual Property Rights 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
13、 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
14、 server (https:/ipr.etsi.org/). 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 server) which are, or may be, or may
15、become, essential to the present document. Foreword This Group Report (GR) has been produced by ETSI Industry Specification Group (ISG) Quantum-Safe Cryptography (QSC). Modal verbs terminology In the present document “should“, “should not“, “may“, “need not“, “will“, “will not“, “can“ and “cannot“ a
16、re 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. Executive summary The present document analyses the impact of a quantum computer
17、 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 256-bit symmetric ciphers and hash functions will still be unbroken in 2050. Introduction A quantum computer will require an enormous
18、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 asymmet
19、ric primitives. 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 p
20、rimitives - and their most-used key sizes - will remain secure. 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. Moores Law may assert tha
21、t 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 t
22、he 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 ther
23、e 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 scr
24、utinize alternatives within the next few years, like is done for the asymmetric primitives. ETSI ETSI GR QSC 006 V1.1.1 (2017-02) 5 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 h
25、ave 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 asse
26、rt 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 investi
27、gating the necessary steps for a transition to primitives with key lengths that will withstand quantum computer attacks like the ones investigated in the present document. ETSI ETSI GR QSC 006 V1.1.1 (2017-02) 6 1 Scope The present document gives information on the long-term suitability of symmetric
28、 cryptographic primitives in the face of quantum computing. 2 References 2.1 Normative references Normative references are not applicable in the present document. 2.2 Informative references References are either specific (identified by date of publication and/or edition number or version number) or
29、non-specific. For specific references, only the cited version applies. For non-specific references, the latest version of the referenced document (including any amendments) applies. NOTE: While any hyperlinks included in this clause were valid at the time of publication, ETSI cannot guarantee their
30、long term validity. The following referenced documents are not necessary for the application of the present document but they assist the user with regard to a particular subject area. i.1 AI Impacts (March 2015): “Trends in the cost of computing“. NOTE: Available at http:/www.aiimpacts.org/trends-in
31、-the-cost-of-computing. i.2 Thomas Monz et al (2011): “14-Qubit Entanglement: Creation and Coherence“, Phys. Rev. Lett. 106, 130506. i.3 Christof Zalka: “Grovers quantum searching algorithm is optimal“, Phys. Rev. A 60, 2746, 1999, arXiv. NOTE: Available at http:/www.arxiv.org/abs/quant-ph/9711070.
32、i.4 PriceWaterhouseCoopers, The world in 2050 (February 2015): “Will the shift in global economic power continue?“. NOTE: Available at i.5 World Bank, Data: “Research and development expenditure“ (% of GDP). NOTE: Available at http:/data.worldbank.org/indicator/GB.XPD.RSDV.GD.ZS. i.6 Lov K. Grover:
33、 “A fast quantum mechanical algorithm for database search“, STOC 1996, pp 212-219, ACM 1996. i.7 Peter W. Shor: “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer“, SIAM Journal on Computing, 26(5):1484-1509, 1997. i.8 Markus Grassl, Brandon Langenberg,
34、 Martin Roetteler, and Rainer Steinwandt (December 2015): “Applying Grovers Algorithm to AES: quantum resource estimates“. 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
35、and SHA3“. i.10 Marc Kaplan, Gactan Leurent, Anthony Leverrier, and Mara Naya-Plasencia (February 2016): “Breaking symmetric cryptosystems using quantum period finding“. ETSI ETSI GR QSC 006 V1.1.1 (2017-02) 7 i.11 Andrey Bogdanov, Dmitry Khovratovich, and Christian Rechberger (2013): “Biclique anal
36、ysis of the full AES“. i.12 Daniel J. Bernstein (May 2009): “Cost analysis of hash collisions: will quantum computers make SHARCS obsolete?“. i.13 Simon J. Devitt, William J. Munro, and Kae Nemoto (June 2013): “Quantum Error Correction for Beginners“, Rep. Prog. Phys. 76 (2013) 076001, arXiv:0905.27
37、94. i.14 European Commission D-G for Research and Innovation: “Global Europe 2050“, European Union 2012, DOI: 10.2777/79992. i.15 Arjen K. Lenstra and Eric R. Verheul (2001): “Selecting Cryptographic Key Sizes“, Journal of Cryptology 14, 4, pp 255-293, Springer Berlin Heidelberg. i.16 Austin G. Fowl
38、er, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland (September 2012): “Surface codes: Towards practical large-scale quantum computation“, Phys. Rev. A 86, 032324. 3 Symbols and abbreviations 3.1 Symbols For the purposes of the present document, the following symbols apply: $ US Dollar d d
39、ays EHz exahertzh hours Hz hertz nm nanometre PHz petahertz pm picometre y years3.2 Abbreviations For the purposes of the present document, the following abbreviations apply: AES Advanced Encryption Standard DSA Digital Signature Algorithm EC Elliptic Curve EU European Union GDP Gross Domestic Produ
40、ct GSM Global System for Mobile communications MAC Message Authentication Code MIPS Million Iterations Per Second QC Quantum Computer QEC Quantum Error Correction RSA Rivest Shamir AdlemanSHA Secure Hash Algorithm TETRA Terrestrial Trunked Radio USA United States of America ETSI ETSI GR QSC 006 V1.1
41、.1 (2017-02) 8 4 Background 4.1 Asymmetric cryptography and quantum computing 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 Shors algorithm i.7. Here completely broke
42、n means that, given complete quantum control over a sufficient number of qubits, a reasonable size (O(n3) quantum circuit can break the underlying mathematical problem in reasonable (O(n3) time for a private key of O(n) bits. This ignores the fact that the cryptographic primitive needs to be impleme
43、nted 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 involv
44、ed 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. 4.2 Sym
45、metric cryptography and quantum computers For symmetric algorithms the impact of quantum computers is less clear. A rule of thumb says that Grovers algorithm effectively halves the key size for these algorithms i.6. However, the aforementioned polynomial overhead considerably increases the complexit
46、y of this algorithm: breaking a 128-bit AES key costs about 287gates and takes the time of 281gate operations i.8 rather than 264operations 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 2166hash function calls
47、for both SHA-2 and SHA-3 i.9, where the rule of thumb would predict 2128. 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
48、 and operation counts can be obtained for different implementations. 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 quan
49、tum 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. Grovers algorithm is optimal for solving the general search problem. It solves the general
