Comparison of security arguments of promising key encapsulation mechanisms

Authors

DOI:

https://doi.org/10.30837/rt.2022.3.210.02

Keywords:

post-quantum cryptography, algebraic lattices, DSTU 8961:2019 , CRYSTALS-Kyber, FrodoKEM, ROM, QROM, core-SVP

Abstract

The study of key encapsulation mechanisms on algebraic lattices is one of the important directions in modern post-quantum cryptography, since many mechanisms are already either standardized (ANSI X.9.98, DSTU 8961:2019 "Skelya") or are promising candidates for standardization (CRYSTALS-Kyber, FrodoKEM). The purpose of this work is to compare the security arguments of DSTU 8961:2019 "Skelya", CRYSTALS-Kyber, FrodoKEM key encapsulation mechanisms. The paper provides a comparison of theoretical evidence in the idealized random oracle (ROM) and quantum random oracle (QROM) models, as well as a comparison of specific values ​of security parameters in the core-SVP model, which is, in fact, a standard for lattice cryptography. Since all three key encapsulation mechanisms are based on different complex problems (NTRU, Module-LWE, LWE), a comparison of complex lattice theory problems and a comparison of their security arguments are additionally given. The strengths and weaknesses of the considered key encapsulation mechanisms are shown, and areas of research that require more detailed attention are highlighted.

References

NIST Post-Quantum Cryptography Standartization Project : веб сайт. URL: https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization

CRYSTALS Kyber: a CCA-secure module-lattice-based KEM / Leo Ducas., and other. // URL: https://eprint.iacr.org/2017/634.pdf

ДСТУ 8961:2019 Інформаційні технології. Криптографічний захист інформації. Алгоритми асиметричного шифрування та інкапсуляції ключів // URL: http://online.budstandart.com/ua/catalog/doc-page.html?id_doc=88056

FrodoKEM. Learning With Errors Key Encapsulation Algorithm Specifications. And Supporting Documentation. / Leo Ducas., and other // URL: https://frodokem.org/files/FrodoKEM-specification-20210604.pdf

M. Toorani Security Protocols in a Nutshell // URL: https://arxiv.org/abs/1605.09771

Katz, Jonathan; Lindell, Yehuda (2007). Introduction to Modern Cryptography: Principles and Protocols.

Chakraborty, Debrup; Rodríguez-Henríquez., Francisco (2008). Çetin Kaya Koç (ed.). Cryptographic Engineering. p. 340. ISBN 9780387718170.

Möller, Bodo (2004). A Public-Key Encryption Scheme with Pseudo-random Ciphertexts // Computer Security – ESORICS 2004. Lecture Notes in Computer Science. Vol. 3193. pp. 335–351.

M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway. Relations among notions of security for public-key encryption schemes. // Advances in Cryptology – CRYPTO’98, ser. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 1998, vol. 1462, pp. 26–45. [Online]. Available: http://dx.doi.org/10.1007/BFb0055718

Canetti R., Goldreich O., Halevi S. The random oracle methodology, revisited // 30th symposium on theory of computing. STOC, 1998. P. 209–218.

Boneh D., Dagdelen O., Fischlin M., Lehmann A., Schaffner C., Zhandry M (2011). Random oracles in a quantum world. Advances in Cryptology – ASIACRYPT 2011, eds Lee DH, Wang X (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 41–69.

P. W. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer // URL: https://arxiv.org/abs/quant-ph/9508027

Горбенко І. Д., Горбенко Ю. І. Прикладна криптологія. Теорія. Практика. Застосування : монографія. Харків : Форт, 2012. 880 с.

Goldreich O. Foundations of Cryptography : Vol. 1. Cambridge University Press, 2000. 392 p.

O. Regev. On lattices, learning with errors, random linear codes, and cryptography// ACM, 56(6):1–40, 2009. Preliminary version in STOC 2005.

Classical Hardness of Learning with Errors / Chris Peikert, Oded Regev, and other // URL: http://perso.ens-lyon.fr/damien.stehle/downloads/LWE.pdf

Thijs Laarhoven, J. V. D. Pol, B. D. Weger Solving Hard Lattice Problems and the Security of Lattice-Based Cryptosystems // URL: http://deweger.xs4all.nl/papers/%5B51%5DLvdPdW-Kolkata%5B2012%5D.pdf

Обзор LWE на структурированых решетках.

Vaikuntanathan V. Advanced Topics in Cryptography: Lattices : веб сайт. URL: https://people.csail.mit.edu/vinodv/6876-Fall2015/

Kirsten Eisenträger, Sean Hallgren, Alexei Kitaev, and Fang Song. A quantum algorithm for computing the unit group of an arbitrary degree number field. In STOC ’14 Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 293–302. ACM, 2014. http://www.personal.psu. edu/kxe8/unitgroup.pdf. 31

Ronald Cramer, Léo Ducas, and Benjamin Wesolowski. Short Stickelberger class relations and application to Ideal-SVP. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in Cryptology – EUROCRYPT 2017, volume 10210 of LNCS, pages 324–348. Springer, 2017. https: //eprint.iacr.org/2016/885. 31, 35

Yang Wang, Mingqiang Wang Module-LWE versus Ring-LWE, Revisited // URL: https://eprint.iacr.org/2019/930

A. Langlois, D. Stehlé. Worst-Case to Average-Case Reductions for Module Lattices // URL: https://perso.ens-lyon.fr/damien.stehle/downloads/MSIS.pdf

Martin R. Albrecht, A. Deo. Large Modulus Ring-LWE ≥ Module-LWE // URL: https://eprint.iacr.org/2017/612.pdf

Joan Bruna, Oded Regev, Min Jae Song, Yi Tang. Continuous LWE // URL: https://arxiv.org/abs/2005.09595

Hoffstein J., Pipher J., Silverman J.H. NTRU: a ring based public key cryptosystem // Algorithmic Nuber Theory, Third International Symposium, Portland, Oregon, USA, June 21 – 25, 1998. Proceedings. Springer, 1998. P. 267 – 288.

Proovable NTRU.

Micheli G., Heninger N., Shani B. Characterizing overstretched NTRU attacks Journal of Mathematical Cryptology. 2020. Vol 14, Is 1. P. 110-119.

American National Standard X9.98-2010. Lattice-based polynomial public key encryption algorithm, Part 1: key establishment, Part 2: data encryption. 2010.

I.D. Gorbenko. Calculation of general parameters for NTRU Prime Ukraine of 6-7 levels of stability / I. D. Gorbenko, A. N. Alekseychuk, O. Kachko ,M. Yesina, I. V. Stelnik, S. Kandy,V. A. Bobukh // Telecommunications and Radio Engineering. 78(4):327-340.

I.D. Gorbenko. Methods of building general parameters and keys for ntru prime ukraine of 5th-7th levels of stability. product form / I. D. Gorbenko, Yu. I. Gorbenko, O. Kachko ,M. Yesina, I. V. Stelnik, S. Kandy // Telecommunications and Radio Engineering. 78(7):579-594.

Wunderer Th. Revising the hibrid attack: improved analysis and refined security estimates // URL: http://eprint.iacr.org/2016/733.

Player R. Parameter selectionin lattice-based cryptography. URL: https://pure.royalholloway.ac.uk/portal/files/29983580/2018playerrphd.pdf

Jianwei Li, Phong Q. Nguyen. A Complete Analysis of the BKZ Lattice Reduction Algorithm // URL: https://eprint.iacr.org/2020/1237.pdf

J.Felderhoff, A. Pellet-Mary, D.Stehl. On Module Unique-SVP and NTRU // URL: https://eprint.iacr.org/2022/1203.pdf.

Published

2022-09-28

How to Cite

Gorbenko, Y. ., & Kandii, S. . (2022). Comparison of security arguments of promising key encapsulation mechanisms. Radiotekhnika, 3(210), 22–36. https://doi.org/10.30837/rt.2022.3.210.02

Issue

Section

Articles