Basic principles and results of comparison of electronic signatures properties of the postquantum period based on algebraic lattices

Authors

DOI:

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

Keywords:

algebraic lattices, algorithm, electronic signature, basic parameters, post-quantum cryptography

Abstract

The paper considers post-quantum projects of the Falcon and Dilithium electronic signature standards (ES), which are finalists of the NIST USA competition. The mathematical apparatus of algebraic lattices and appropriate methods are used in their construction. In further study and comparison of these post-quantum ES draft standards, both from a theoretical and practical standpoint, it is fundamental to substantiate the requirements for parameters and keys and in general to calculate the main indicators according to the accepted conditional and unconditional criteria. In such studies, it is important to determine the sufficiency of ensuring the guarantee of their security against classical, quantum, special and error-based attacks. This can be ensured, inter alia, through a reasonable choice of the sizes of common parameters and keys, and their practical construction in accordance with the adopted security model. However, when choosing the sizes of common parameters and keys, a significant contradiction arises between the properties of the draft of the Falcon and Dilithium ES standards, So increasing the size of the general parameters and keys leads to an increase in the complexity of transformations, and vice versa. The purpose of this article consists in analysis of problematic issues of choosing the size of parameter and keys for post-quantum ES projects based on mathematical methods of Falcon and Dilithium, and features of their implementation, including implementation according to the adopted security model. Comparative analysis of the stability and complexity of the Falcon and Dilithium ES draft standards depending on the size of the parameters and keys, including for 6 and 7 security levels. Development of proposals for decisions on the adoption of national post-quantum ES standards based on the mathematical methods Falcon and Dilithium. Determining the influence of unconditional, conditional and pragmatic criteria on the advantages when deciding on the ES standardization based on Falcon and Dilithium mathematical methods, including taking into account the availability of patents and the need to obtain licenses, etc.

References

Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU. Round 3 Submissions. [Електронний ресурс]. Режим доступу: https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions.

Léo Ducas Crystals-Dilithium: Algorithm Specifications and Supporting Documentation. Round 3 Submissions. [Електронний ресурс]. Режим доступу: https://csrc.nist.gov/Projects/post-quantum-cryptography/round-3-submissions.

Gorjan Alagic NISTIR 8309 Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process / Gorjan Alagic, Jacob Alperin-Sheriff, Daniel Apon, David Cooper, Quynh Dang, John Kelsey, Yi-Kai Liu, Carl Miller, Dustin Moody, Rene Peralta, Ray Perlner, Angela Robinson, Daniel Smith-Tone. Режим доступу: https://doi.org/10.6028/NIST.IR.8309.

Chen L Report on Post-Quantum Cryptography / Chen L, Jordan S, Liu Y-K, Moody D, Peralta R, Perlner RA, Smith-Tone D // (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) 8105 (2016). Режим доступу: https://doi.org/10.6028/NIST.IR.8105.

Горбенко І. Д. Методи, методика та результати порівняльного аналізу кандидатів на постквантовий стандарт електронного підпису / І. Д. Горбенко, О. Г. Качко, М. В. Єсіна, В. А. Пономар // ХХ Ювілейна Міжнар. наук.-практ. конференція "Безпека інформації в інформаційно-телекомунікаційних системах", 22-24 травня, 2018, м. Буча. С. 96-97.

Горбенко І. Д. Генерація загальносистемних параметрів для криптосистеми Falcon для 256, 384, 512 біт безпеки / І. Д. Горбенко, С.О. Кандіи, М.В. Єсіна, Є.В. Острянська // Радіотехніка. 2020. Вип. 202. C. 57-63.

Горбенко І. Д. Методи обчислення системних параметрів для електронного підпису «Сrystals-Dilithium» 128, 256, 384 та 512 біт рівнів безпеки / І. Д. Горбенко, А. М. Олексійчук, О. Г. Качко, Ю. І. Горбенко, М. В. Єсіна, С. О. Кандіи // Радіотехніка. 2020. Вип. 202. C. 5-28.

Yesina Maryna Comparative Analysis of Key Encapsulation Mechanisms / Maryna Yesina, Mikolaj Karpinski, Volodymyr Ponomar, Yurij Gorbenko, Tomasz Gancarczyk, Uliana Iatsykovska // Proceedings of the 2019 10th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS). September 18-21, 2019, Metz, France. Volume 1. – P. 7-12.

Горбенко Ю. І. Моделі загроз щодо асиметричних криптоперетворень перспективного електронного підпису / Ю.І. Горбенко, М.В. Єсіна, В.В. Онопрієнко, Г.А. Малєєва // Радіотехніка. 2020. Вип. 202. C. 72-78.

Горбенко Ю. І. Аналіз стіийкості постквантового електронного підпису Dilithium до атак на помилки / Ю.І. Горбенко,О.С. Дроздова // Радіотехника. 2020. Вип. 202. С. 49 – 56.

Daniel J. Bernstein, Tanja Lange, Christiane Peters Attacking and defending the McEliece cryptosystem. [Електронний ресурс]. Режим доступу: https://link.springer.com/chapter/10.1007/978-3-540-88403-3_3.

Martin Albrecht, Shi Bai, Leo Ducas A Subfield Lattice Attack on Overstretched NTRU Assumptions. In Matthew Robshaw and Jonathan Katz, editors, Advances inCryptology – CRYPTO 2016, pages 153–178, Berlin, Heidelberg, 2016. Springer BerlinHeidelberg.

Paul Kirchner, Pierre-Alain Fouque Revisiting Lattice Attacks on Overstretched NTRU Parameters. In Jean-Sebastien Coron and Jesper Buus Nielsen, editors, Advancesin Cryptology – EUROCRYPT 2017, pages 3-26, Cham, 2017. Springer InternationalPublishing.

Vadim Lyubashevsky, Daniel Wichs Simple lattice trapdoor sampling from a broad class of distributions. In Jonathan Katz, editor, PKC 2015, volume 9020 of LNCS, pages 716 – 730, Gaithersburg, MD, USA, March 30 – April 1, 2015. Springer, Heidelberg, Germany.

Martin R. Albrecht On the complexity of the BKW algorithm on LWE / Martin R. Albrecht, Carlos Cid, Jean-Charles Faugère, Robert Fitzpatrick, Ludovic Perret //. Designs, Codes and Cryptography, 74: 325-354, 2015.

Ronald Cramer, Léo Ducas, Benjamin Wesolowski Short stickelberger class relations and application to ideal-SVP. In Coron and Nielsen, pages 324-348.

Avrim Blum, Adam Kalai, Hal Wasserman Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM, 50(4): 506-519, July 2003.

Квантовый компьютер. [Електронний ресурс]. Режим доступу: http://www.tadviser.ru/index.php/.

Каптьол Є. Ю. Аналіз можливостей та особливості програмування задач криптологіі на квантовому комп’ютері /Є. Ю. Каптьол, І.Д. Горбенко // Радіотехніка. 2020. Вип. 202. C. 37-48.

Горбенко Ю. І. Аналіз можливостей квантових комп’ютерів та квантових обчислень для криптоаналізу сучасних криптосистем / Ю. І. Горбенко, Р. С. Ганзя // Східно-європейський журнал передових технологій. 2014. № 1/9 (67). С. 8-15.

Vadim Lyubashevsky CRYSTALS-Dilithium. Submission to the NIST Post-Quantum Cryptography Standardization [NIS] / Vadim Lyubashevsky, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Peter Schwabe, Gregor Seiler, Damien Stehlé //, 2017. Режим доступу: https://pq-crystals.org/dilithium.

Олексійчук А. М. Обґрунтування перспективного постквантового національного стандарту електронного підпису на основі решіток / А. М. Олексійчук, В. А. Кулібаба, М. В. Єсіна, С. О. Кандій, Є. В. Острянська, І. Д. Горбенко // Радіотехніка. 2020. Вип. 200. С. 5-14.

Качко О. Г. Оптимізація алгоритму множення поліномів для NTRU – побітних алгоритмів / О. Г. Качко, Ю. І Горбенко, В. А. Пономар, М. В. Єсіна, С. О. Кандій // Радіотехніка. 2020. Вип. 200. С. 15-24.

Nick Howgrave-Graham A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. In Alfred Menezes, editor, CRYPTO 2007, volume 4622 of LNCS, pages 150–169, Santa Barbara, CA, USA, August 19-23, 2007. Springer, Heidelberg, Germany.

Published

2021-07-02

How to Cite

Gorbenko, I. ., Kachko, O. ., Potii, O. ., Oleksiychuk, A. ., Gorbenko, Y. ., Yesina, M. ., Stelnyk, I. ., & Ponomar, V. . (2021). Basic principles and results of comparison of electronic signatures properties of the postquantum period based on algebraic lattices. Radiotekhnika, 2(205), 5–21. https://doi.org/10.30837/rt.2021.2.205.01

Issue

Section

Articles