Towards security recommendations for public-key infrastructures for production environments in the post-quantum era

EPJ Quantum Technology - Tập 8 - Trang 1-19 - 2021
Sergey E. Yunakovsky1,2, Maxim Kot1,2, Nikolay Pozhar1,2, Denis Nabokov1,2, Mikhail Kudinov1,2, Anton Guglya1,2, Evgeniy O. Kiktenko1,2, Ekaterina Kolycheva3, Alexander Borisov3, Aleksey K. Fedorov1,2
1QApp, Moscow, Russia
2Russian Quantum Center, Moscow, Russia
3Bosch Corp. Sector Res. & Adv. Eng., Saint Petersburg, Russia

Tóm tắt

Quantum computing technologies pose a significant threat to the currently employed public-key cryptography protocols. In this paper, we discuss the impact of the quantum threat on public key infrastructures (PKIs), which are used as a part of security systems for protecting production environments. We analyze security issues of existing models with a focus on requirements for a fast transition to post-quantum solutions. Although our primary focus is on the attacks with quantum computing, we also discuss some security issues that are not directly related to the used cryptographic algorithms but are essential for the overall security of the PKI. We attempt to provide a set of security recommendations regarding the PKI from the viewpoints of attacks with quantum computers.

Tài liệu tham khảo

Adams C, Lloyd S. Understanding PKI: concepts, standards, and deployment considerations. 2nd ed. Reading: Addison-Wesley; 2002.

Rivest RL, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Commun ACM. 1978;21:120.

Diffie W, Hellman ME. New directions in cryptography. IEEE Trans Inf Theory. 1976;22:644.

Shor PW. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J Comput. 1997;26:1484–509.

Grover LK. A fast quantum mechanical algorithm for database search. In: Proceedings of 28th annual ACM symposium on the theory of computing. New York, USA. 1996. p. 212.

See Report by Digicert: Are you ready for the quantum leap?

Wallden P, Kashefi E. Cyber security in the quantum era. Commun ACM. 2019;62:120.

Bernstein DJ, Lange T. Post-quantum cryptography. Nature. 2017;549:188.

Landrock P. PKI, past, present and future. In: Proceedings of the IEE seminar on quantum cryptography: secure communications for business (Ref. No. 2005/11310) 2005.

Höglund J, Lindemer S, Furuhed M, Raza S. PKI4IoT: towards public key infrastructure for the Internet of Things. Comput Secur. 2020;89:101658.

Yong Y, Yu L. Security considerations based on PKI/CA in manufacturing grid. Wuhan Univ J Nat Sci. 2006;11:1414.

Hanke M. Embedded PKI in industrial facilities. In: Proceedings of the ISSE/SECURE 2007 securing electronic business processes: highlights of the information security solutions Europe/SECURE 2007 conference. Wiesbaden: Vieweg; 2007. p. 347–54.

Mulholland J, Mosca M, Braun J. The day the cryptography dies. IEEE Secur Priv. 2017;15:14–21.

Mavroeidis V, Vishi K, Zych MD, Jøsang A. The impact of quantum computing on present cryptography. Int J Adv Comput Sci Appl. 2018;9:405.

Griffiths RB, Niu C-S. Semiclassical Fourier transform for quantum computation. Phys Rev Lett. 1996;76:3228. arXiv:quant-ph/9511007.

Zalka C. Shor’s algorithm with fewer (pure) qubits. quant-ph/0601097 (2006).

Fowler AG, Mariantoni M, Martinis JM, Cleland AN. Surface codes: towards practical large-scale quantum computation. Phys Rev A. 2012;86:032324. arXiv:1208.0928.

Ekerå M, Håstad J. Quantum algorithms for computing short discrete logarithms and factoring RSA integers. Lecture notes in computer science (LNCS). vol. 10346. Berlin: Springer; 2017. p. 347.

Gidney C, Fowler AG. Flexible layout of surface code computations using AutoCCZ states. arXiv:1905.08916 (2019).

Gidney C, Ekerå M. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. arXiv:1905.09749 (2019).

Arute F, Arya K, Babbush R, Bacon D, Bardin JC, Barends R, Biswas R, Boixo S, Brandao FGSL, Buell DA et al.. Quantum supremacy using a programmable superconducting processor. Nature (London). 2019;574:505.

Gouzien E, Sangouard N. Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory. arXiv:2103.06159.

Anschuetz ER, Olson JP, Aspuru-Guzik A, Cao Y. Variational quantum factoring. Lect Notes Comput Sci. 2019;11413:74.

Gisin N, Ribordy G, Tittel W, Zbinden H. Quantum cryptography. Rev Mod Phys. 2002;74:145.

Scarani V, Bechmann-Pasquinucci H, Cerf NJ, Dušek M, Lütkenhaus N, Peev M. The security of practical quantum key distribution. Rev Mod Phys. 2009;81:1301.

https://www.idquantique.com/quantum-safe-security/overview/.

https://goqrate.com.

Chen Y-A, Zhang Q, Chen T-Y, Cai W-Q, Liao S-K, Zhang J, Chen K, Yin J, Ren J-G, Chen Z, Han S-L, Yu Q, Liang K, Zhou F, Yuan X, Zhao M-S, Wang T-Y, Jiang X, Zhang L, Liu W-Y, Li Y, Shen Q, Cao Y, Lu C-Y, Shu R, Wang J-Y, Li L, Liu N-L, Xu F, Wang X-B, Peng C-Z, Pan J-W. An integrated space-to-ground quantum communication network over 4600 kilometres. Nature (London). 2021;589:214.

Lo H-K, Curty M, Tamaki K. Secure quantum key distribution. Nat Photonics. 2014;8:595–604.

Diamanti E, Lo H-K, Yuan Z. Practical challenges in quantum key distribution. npj Quantum Inf. 2016;2:16025.

Regev O. On lattices, learning with errors, random linear codes, and cryptography. J ACM. 2009;56:40.

Hanrot G, Stehle D. Improved analysis of Kannan’s shortest lattice vector algorithm. Lect Notes Comput Sci. 2007;4622:170.

Micciancio D, Goldwasser S. Complexity of lattice problems: a cryptographic perspective. Berlin: Springer; 2002.

Regev O. The learning with errors problem. In: Proceedings of the IEEE 25th annual conference on computational complexity. 2010. p. 191–204.

Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings. Lect Notes Comput Sci. 2010;6110:1.

Naehrig M, Alkim E, Bos J, Ducas L, Easterbrook K, LaMacchia B, Longa P, Mironov I, Nikolaenko V, Peikert C, Raghunathan A, Stebila D. FrodoKEM. https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions. Accessed 05 Aug 2020.

Schwabe P, Avanzi R, Bos J, Ducas L, Kiltz E, Lepoint T, Lyubashevsky V, Schanck JM, Seiler G, Stehle D. CRYSTALS-KYBER. https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions. Accessed 05 Aug 2020.

Albrecht MR, Player R, Scott S. On the concrete hardness of learning with errors. J Math Cryptol. 2015;9:169.

Kirchner P, Fouque P-A. An improved BKW algorithm for LWE with applications to cryptography and lattices. Lect Notes Comput Sci. 2015;9215:43.

Arora S, Ge R. New algorithms for learning in presence of errors. Lect Notes Comput Sci. 2011;6755:403.

Schnorr CP, Euchner M. Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math Program. 1994;66:181.

Chen Y, Nguyen PQ. BKZ 2.0: better lattice security estimates. Lect Notes Comput Sci. 2011;7073:1.

Alkim E, Avanzi R, Bos J, Ducas L, de la Piedra, Pöppelmann T, Schwabe P, Stebila D. NewHope. https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions. Accessed 05 Aug 2020.

Lyubashevsky V, et al. CRYSTALS-Dilithium. https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions. Accessed 05 Aug 2020.

Patarin J. Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms. Lect Notes Comput Sci. 1996;1070:33.

Faugère JC, Joux A. Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases. Lect Notes Comput Sci. 2003;2729:44.

Beullens W, Preneel B. Field lifting for smaller UOV public keys. Lect Notes Comput Sci. 2017;10698:227.

Casanova A, Faugère J-C, Macario-Rat G, Patarin J, Perret L, Ryckeghem J. GeMSS: a Great Multivariate Short Signature. https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions. Accessed 05 Aug 2020.

Beullens W, Preneel B, Szepieniec A, Vercauteren F. LUOV. https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions. Accessed 05 Aug 2020.

Ding J, et al. Rainbow. https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions. Accessed 05 Aug 2020.

Jao D, De Feo L. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. Lect Notes Comput Sci. 2011;7071:19.

Costello C, Jao D, Longa P, Naehrig M, Renes J, Urbanik D. Efficient compression of SIDH public keys. Lect Notes Comput Sci. 2016;10210:679–706.

Costello C, Longa P, Naehrig M. Efficient algorithms for supersingular isogeny Diffie-Hellman. Lect Notes Comput Sci. 2016;9814:572.

Koziel B, Azarderakhsh R, Mozaffari Kermani M, Jao D. Post-quantum cryptography on FPGA based on isogenies on elliptic curves. IEEE Trans Circuits Syst I, Regul Pap. 2017;64:86.

Galbraith SD. Constructing isogenies between elliptic curves over finite fields. LMS J Comput Math. 1999;2:118.

Delfs C, Galbraith SD. Computing isogenies between supersingular elliptic curves over \(\mathbb{F}_{p}\). Des Codes Cryptogr. 2016;78:425.

Zhang S. Promised and distributed quantum search computing and combinatorics. Lect Notes Comput Sci. 2005;3595:430.

Tani S. An improved claw finding algorithm using quantum walk. Lect Notes Comput Sci. 2007;4708:536.

Berlekamp E, McEliece R, van Tilborg H. On the inherent intractability of certain coding problems (corresp.). IEEE Trans Inf Theory. 1978;24:384.

Alekhnovich M. More on average case vs approximation complexity. In: Proceedings of the 44th annual IEEE symposium on foundations of computer science. 2003. p. 298–307.

May A, Ozerov I. On computing nearest neighbors with applications to decoding of binary linear codes. Lect Notes Comput Sci. 2015;9056:203.

Becker A, Joux A, May A, Meurer A. Decoding random binary linear codes in \(2^{n}/20\): how \(1+1 = 0\) improves information set decoding. Lect Notes Comput Sci. 2012;7237:520.

Bernstein DJ. Grover vs. McEliece. Lect Notes Comput Sci. 2010;6061:73.

Drucker N, Gueron S, Kostic D. Fast polynomial inversion for post quantum QC-MDPC cryptography. Lect Notes Comput Sci. 2020;12161:110.

Huelsing A, Butin D, Gazdag S, Rijneveld J, Mohaisen A. XMSS: eXtended Merkle Signature Scheme, RFC 8391 (2018).

McGrew D, Curcio M, Fluhrer S. Leighton-Micali Hash-Based Signatures, RFC 8554 (2019).

Buchmann J, Dahmen E, Hülsing A. XMSS – a practical forward secure signature scheme based on minimal security assumptions. Lect Notes Comput Sci. 2011;7071:117.

Bernstein DJ, Hülsing A, Kölbl S, Niederhagen R, Rijneveld J, Schwabe P. SPHINCS+. https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions. Accessed 05 Aug 2020.

Hülsing A, Rijneveld J, Song F. Mitigating multi-target attacks in hash-based signatures. Lect Notes Comput Sci. 2016;9614:387.

Bernstein DJ, Hülsing A. Decisional second-preimage resistance: when does SPR imply PRE? Lect Notes Comput Sci. 2019;11923:32.

Rogaway P, Shrimpton T. Cryptographic hash-function basics: definitions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance. Lect Notes Comput Sci. 2004;3017:371.

Kudinov M, Kiktenko E, Fedorov A. Official Comments (Round 3) – SPHINCS+. https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/official-comments/Sphincs-Plus-round3-official-comment.pdf. Accessed 05 Aug 2020.

Chase M, et al. The picnic signature scheme. https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions. Accessed 05 Aug 2020.

Kabanov IS, Yunusov RR, Kurochkin YV, Fedorov AK. Practical cryptographic strategies in the post-quantum era. AIP Conf Proc. 2018;1936:020021.

Wang LJ, Zhang KY, Wang JY, Cheng J, Yang YH, Tang SB, Yan D, Tang YL, Liu Z, Yu Y, Zhang Q, Pan JW. Experimental authentication of quantum key distribution with post-quantum cryptography. arXiv:2009.04662 (2020).

NIST. Post-Quantum Cryptography Standardization Webpage. https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization.

Alagic G, et al. Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process. https://csrc.nist.gov/publications/detail/nistir/8309/final. Accessed 05 Aug 2020.

Kiktenko EO, Kudinov MA, Fedorov AK. Detecting brute-force attacks on cryptocurrency wallets. arXiv:1904.06943 (2019).

Fedorov AK, Kiktenko EO, Lvovsky AI. Quantum computers put blockchain security at risk. Nature. 2018;563:465.

https://csrc.nist.gov/publications/detail/fips/140/2/final.

Coppersmith D. In: Proceedings of the EUROCRYPT 1996: advances in cryptology – EUROCRYPT ‘96. 1996. p. 178–89.

Thông tin
Thông tin xuất bản

EPJ Quantum Technology

Tập 8

1-19

Thông tin tác giả