ETSI GR QSC 006-2017 Quantum-Safe Cryptography (QSC) Limits to Quantum Computing applied to symmetric key sizes (V1 1 1)《量子安全密码 (QSC) 适用于对称密钥大小的量子计算的限制(V1 1 1)》.pdf

《ETSI GR QSC 006-2017 Quantum-Safe Cryptography (QSC) Limits to Quantum Computing applied to symmetric key sizes (V1 1 1)《量子安全密码 (QSC) 适用于对称密钥大小的量子计算的限制(V1 1 1)》.pdf》由会员分享，可在线阅读，更多相关《ETSI GR QSC 006-2017 Quantum-Safe Cryptography (QSC) Limits to Quantum Computing applied to symmetric key sizes (V1 1 1)《量子安全密码 (QSC) 适用于对称密钥大小的量子计算的限制(V1 1 1)》.pdf（14页珍藏版）》请在麦多课文档分享上搜索。

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