Methods for calculating system parameters for electronic signature "Crystals-Dilithium" 128, 256, 384 and 512 bits of security levels

Authors

  • І.Д. Горбенко
  • А.М. Олексійчук
  • О.Г. Качко
  • Ю.І. Горбенко
  • М.В. Єсіна
  • С.О. Кандій

DOI:

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

Keywords:

algebraic lattice, attacks, security, system-wide parameters, security model, threat model, violator model, signature, polynomial, Dilithium

Abstract

Globally, the efforts of a significant number of crypto-theorists, mathematicians and cryptologists-practitioners are focused on the NIST PQC open competition. One of the main tasks of the competition consists in development and adoption of a post-quantum ES standard or standards. The finalists of the second stage of the NIST competition were three ES mechanisms – CRYSTALS-DILITHIUM, Falcon and Rainbow. In addition, three alternative candidates were identified that require more detailed research. In general, a comprehensive analysis of the finalists is an important task for cryptologists in the global cryptocommunity. Moreover, security, i.e. bringing the cryptographic stability of two finalist candidates, to the ES standard – CRYSTALS-DILITHIUM and Falcon, is based on problems in the theory and practice of algebraic lattices. The EP Dilithium method (scheme) is based on the approach called "Fiat-Shamir Interruptions". The essence of the CRYSTALS-DILITHIUM ES algorithm is considered in the article. A detailed analysis of possible attacks on the algorithm and the mechanisms of their implementation is also carried out. Models of violator, threats and security are considered and analyzed. The main definitions of ES security models are provided. The main design elements of the mechanism of perspective post-quantum ES Dilithium are described in the generalized form. General estimations of the ES Dilithium security level are given. The substantiation and essence of models of threats, violator and security are given. The stability of the ES Dilithium algorithm is investigated. The purpose of the article is to substantiate a security model, classification, primary analysis and assessment of known attacks on the CRYSTALS-DILITHIUM EP cryptosystem, to establish restrictions and develop practical algorithms for calculating (generating) system-wide parameters to ensure 128, 256, 384 and 512 bits of security relative to classical and 64, 128, 192 and 256 bits relative to quantum cryptanalysis.

References

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

Gorjan Alagic Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process. NISTIR 8309 / 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 // 22 July 2020. Режим доступу: https://doi.org/10.6028/NIST.IR.8309.

ЕП Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler and Damien Stehlé CRYSTALS-Dilithium: Algorithm Specifications and Supporting Documentation. Access mode: https://pq-crystals.org/dilithium/data/dilithium-specification.pdf.

Post-Quantum Cryptography. Round 2 Submissions. [Електронний ресурс]. Режим доступу: https://csrc.nist.gov/Projects/post-quantum-cryptography/round-2-submissions.

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

ISCI’2019: Information Security in Critical Infrastructures. Collective monograph. Edited by Ivan D. Gorbenko and Alexandr A. Kuznetsov. ASC Academic Publishing, USA, 2019. 445 p.

Gorbenko Ivan The problem of cryptographic transformations standardization and the state of its solution / Ivan Gorbenko, Olena Kachko, Oleksandr Kuznetsov, Yurii Gorbenko, Maryna Yesina // VII Міжнар. наук.-техн. конф. “Захист інформації і безпека інформаційних систем” : Праці Науково-технічної конференції, 30–31 травня 2019 р. Львів : Нац. ун-т “Львівська політехніка”, 2019. С. 84-85.

Горбенко І. Д. Порівняння, оцінювання, дослідження можливості використання та переваг постквантових алгоритмів / І. Д. Горбенко, В. А. Пономар, М. В. Єсіна // Правове, нормативне та метрологічне забезпечення системи захисту інформації в Україні. Київ : Нац. техн. ун-т України "Київський політехнічний інститут імені Ігоря Сікорського", 2017. Вип. 2(34). С. 9-32.

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

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

Горбенко І. Д., Постквантова криптографія та механізми її реалізації / І. Д. Горбенко, О. О. Кузнецов, О. В. Потій, Ю. І. Горбенко, Р. С., Ганзя, В. А. Пономар // Радиотехника. 2017. Вып. 186. С. 32–52.

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

Vadim Lyubashevsky. Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In ASIACRYPT, pages 598–616, 2009.

Vadim Lyubashevsky. Lattice signatures without trapdoors. In EUROCRYPT, pages 738–755, 2012.

Tim Güneysu, Vadim Lyubashevsky, and Thomas Pöppelmann. Practical lattice-based cryptography: A signature scheme for embedded systems. In CHES, pages 530–547, 2012.

Eike Kiltz, Vadim Lyubashevsky, and Christian Schaffner. A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model. Cryptology ePrint Archive, Report 2017/916, 2017. Access mode: https://eprint.iacr.org/2017/916.

Lyubashevsly V (2009) Fiat-Shamir with aborts: Applications to Lattice and Factoring-Based Signatures. International Conference on the Theory and Application of Cryptology and Information Security – ASIACRYPT (Springer), pp. 598-616. https://doi.org/10.1007/978-3-642-10366-7_35.

Don J, Fehr S, Majenz C, Schaffner C (2019) Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model. Annual International Cryptology Conference – CRYPTO (Springer), p. 356-383. https://doi.org/10.1007/978-3-030-26951-7_13.

Єсіна М. В. Моделі безпеки постквантових криптографічних примітивів / М. В. Єсіна // Міжнародний науковий симпозіум “Питання оптимізації обчислень (ПОО-XLVІ)”, 2019 р. Математичне на комп’ютерне моделювання. Серія: Технічні науки. Вип. 19. С. 49-55.

V. Shoup On Formal Models for Secure Key Exchange, Theory of Cryptography Library, 1999. [Електронний ресурс]. Режим доступу: http://philby.ucsd.edu/cryptolib/1999/9912.html.

M. Bellare, R. Canetti, H. Krawczyk A modular approach to the design and analysis of authentication and key-exchange protocols. 30th STOC 1998.

Privacy for Code-Based Encryption in the Standard Model. In: Lange T., Takagi T. (eds) Post-Quantum Cryptography. PQCrypto 2017. Lecture Notes in Computer Science, vol 10346. Springer, Cham.

M. Bellare, A. Boldyreva, A. Desai, D. Pointcheval Key-privacy in public-key encryption. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248. Р. 566–582. Springer, Heidelberg (2001). doi:10.1007/3-540-45682-1.

Державна служба спеціального зв’язку та захисту інформації України. Наказ від 20.07.2007 №141 «Положення про порядок розроблення, виробництва та експлуатації засобів криптографічного захисту конфіденційної та відкритої інформації з використанням електронного цифрового підпису» № 862/14129.

Закон України «Про основні засади забезпечення кібербезпеки України» // Відомості Верховної Ради (ВВР). 2017. № 45. Ст. 403.

Закон України «Про електронні довірчі послуги» // Відомості Верховної Ради (ВВР), 2017. № 45. Ст. 400).

Закон України "Про захист інформації в інформаційно-телекомунікаційних системах".

Закон України "Про захист персональних даних.

Горбенко Ю. І. Методи побудування та аналізу криптографічних систем : монографія. Харків : Форт, 2015. 959 с.

Горбенко І. Д. Прикладна криптологія: Монографія / Горбенко І. Д., Горбенко Ю. І. 2-ге вид. Харків : Форт, 2012. 868 с.

Albrecht M.R., Goepfert F., Virdia F., Wunderer T. Revisiting the expected cost of solwing uSVP and applications to LWE // Cryptology ePrint Archive, Report 2017/815. Access mode: http://eprint.iacr.org/2017/815.

Albrecht M.R., Player R., Scott S. On the concrete hardness of learning with errors // Cryptology ePrint Archive, Report 2015/046. Access mode: http://eprint.iacr.org/2015/046.

Rachel Player Parameter selection in lattice-based cryptography. Access mode: https://pure.royalholloway.ac.uk/portal/files/29983580/2018playerrphd.pdf.

Gottfried Herold, Elena Kirshanova and Alexander May. On the asymptotic complexity of solving LWE // Designs, Codes and Cryptography, Jan 2017.

Shi Bai and Steven D. Galbraith. Lattice decoding attacks on binary LWE // Willy Susilo and Yi Mu, editors, ACISP 14, vol. 8544 of LNCS, pages 322–337. Springer, Heidelberg, July 2011.

Sanjeev Arora and Rong Ge. New algorithms for learning in presence of errors // Luca Aceto, Monika Henzinger, and Jiri Sgall, editors, ICALP 2011, Part I, vol. 6755 of LNCS, pages 403–415. Springer, Heidelberg, July 2011.

Martin R. Albrecht, Carlos Cid, Jean-Charles Faugère, and Ludovic Perret. Algebraic algorithms for LWE. Cryptology ePrint Archive, Report 2014/1018, 2014. Access mode: http://eprint.iacr.org/2014/1018.

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

Martin R. Albrecht, Jean-Charles Faugère, Robert Fitzpatrick, and Ludovic Perret. Lazy modulus switching for the BKW algorithm on LWE // Hugo Krawczyk, editor, PKC 2014, vol. 8383 of LNCS, pages 429–445. Springer, Heidelberg, March 2014.

Richard Lindner and Chris Peikert. Better key sizes (and attacks) for LWE-based encryption // Aggelos Kiayias, editor, CT-RSA 2011, vol. 6558 of LNCS, pages 319–339. Springer, Heidelberg, February 2011.

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

Leon Groot Bruinderink1 and Peter Pessl2 . Differential Fault Attacks on Deterministic Lattice Signatures.

Lyubachevsky V., Ducas L., Kiltz E. [et all]. CRYSTALS–Dilithium. Techn. rep. NIST (2017). [Electronic resource]. Access mode: https://crc.nist.gov./projects/post-quantum-cryptogtraphy/ round-1-submissions.

Albrecht M.R., Goepfert F., Virdia F., Wunderer T. Revisiting the expected cost of solwing uSVP and applications to LWE // Cryptology ePrint Archive, Report 2017/815. Access mode: http://eprint.iacr.org/2017/815.

Peikert C., How (not) to instanaite Ring-LWE // Cryptology ePrintAchive 2016/351, 2016.

Горбенко І. Д. Особливості побудування та аналіз електронних підписів 5 рівня безпеки для постквантового періоду на основі алгебраїчних решіток / І. Д. Горбенко, О. Г. Качко, А. М. Олексійчук, Ю. І. Горбенко, В. П. Звєрєв, М. В. Єсіна, В. А. Пономар // Прикладная радиоэлектроника. Харьков : ХНУРЭ, 2019. Т. 18, № 3, 4. С. 123–136.

Downloads

How to Cite

Горбенко, І., Олексійчук, А., Качко, О., Горбенко, Ю., Єсіна, М., & Кандій, С. (2020). Methods for calculating system parameters for electronic signature "Crystals-Dilithium" 128, 256, 384 and 512 bits of security levels. Radiotekhnika, 3(202), 5–28. https://doi.org/10.30837/rt.2020.3.202.01

Issue

No. 202 (2020): Radiotekhnika

Section

Articles

License

Authors who publish with this journal agree to the following terms:

1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).