Substantiation of promising post-quantum national lattice-based electronic signature standard

Authors

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

DOI:

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

Keywords:

electronic signature, post-quantum standard, algebraic lattices

Abstract

An important feature of the post-quantum period in cryptography is the significant uncertainty about the input data for cryptanalysis and counteracting the capabilities of quantum computers, their mathematical and software, and the application of quantum cryptanalysis to existing cryptoprotocols and cryptotransformations. Mathematical electronic signature (ES) methods have been selected as the main methods in the work, which have undergone significant analysis and substantiation in the process of extensive research by cryptologists and mathematicians at the highest level. The article analyzes the existing electronic signature algorithms based on the lattices of stage 2 of the NIST competition. The possibility of using the post-quantum electronic signature mechanism based on algebraic lattices as the post-quantum national electronic signature standard is considered. It is proposed to use the post-quantum Сrystals-Dilithium algorithm as such electronic signature algorithm. The article considers this algorithm and substantiates the possibility of its application. The algorithm parameters and rules for their construction are considered. The differences and features of safe implementation of the algorithm in comparison with stage 1 are analyzed. The analysis is conducted and it is concluded that the Crystals-Dilithium algorithm can be taken as one of the candidates for the development of a national electronic signature standard using cryptographic algorithms, standardized in Ukraine, such as the hashing function described in DSTU 7564:2014. According to the authors of the article, the post-quantum period national standard of Ukraine should include at least 3 algorithms based on different types of mathematical transformations, which are recognized by the world cryptographic community as those that can provide the necessary level of stability in the conditions of quantum cryptanalysis.

References

Donald Knuth The Art of Computer Programming, volume 2. Addison-Wesley, 3 edition, 1997. P. 145.

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

Bos J.W., Costello C., Ducas L. [et all] Frodo: take of the ring! Practical, quantum-secure key exchange from LWE // Proc. of ACM CCS 16, ACM Press, Okt. 2006. P. 1006-1018.

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

Rueckert M., Schneider M. Estimating the security of lattice-based cryptosystems // Cryptology ePrint Ar-chive, Report 2010/137, http://eprint.iacr.org/2010/0137.

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

Rachel Player. Parameter selectionin lattice-based cryptography.

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

Shi Bai and Steven D. Galbraith. Lattice decoding attacks on binary LWE.In Willy Susilo and Yi Mu, edi-tors, ACISP 14, vol. 8544 of LNCS, p. 322–337. Springer, Heidelberg, July 2016.

Sanjeev Arora and Rong Ge. New algorithms for learning in presence of errors.In Luca Aceto, Monika Henzinger, and Jiri Sgall, editors, ICALP 2011, Part I, vol. 6755 of LNCS, p. 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. http://eprint.iacr.org/2014/1018.

Martin R. Albrecht, Carlos Cid, Jean-Charles Faugère, Robert Fitzpatrick, andLudovic 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 switch-ing for the BKW algorithm on LWE. In Hugo Krawczyk, editor,PKC 2014, vol. 8383 of LNCS, p. 429–445. Springer,Heidelberg, March 2014.

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

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

НДР «Визначення напрямків розвитку математичних методів та дослідження перспектив їх за-стосування для створення сучасних та перспективних криптографічних алгоритмів та протоколів» (Шифр «Скіл»). Т. 9. «Проект стандарту електронного підпису на алгребраїчній решітці для постквантового періоду». Харків, 2018. 127 с.

Daniel J. Bernstein, Daira Hopwood, Andreas Hülsing, Tanja Lange, Ruben Niederhagen, Louiza Papa-christodoulou, Michael Schneider, Peter Schwabe and Zooko Wilcox-O’Hearn. SPHINCS: Practical stateless hash-based signatures. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part I, vol. 9056 of LNCS, p. 368–397, Sofia, Bulgaria, April 26–30, 2015. Springer, Heidelberg, Germany.

ДСТУ 8961:2019 Інформаційні технології. Криптографічний захист інформації. Алгоритми асиметричного шифрування та інкапсуляції ключів.

Ducas L., Lepoint T., Lyubachevsky V. [et all] CRYSTALS – Dilithium: digital sygnatures from module lattices / https://cryptojedi.org/papers/dilithium-20170617.pdf.

Alkim E., Ducas L., Poeppelmann T., Schwabe P. Post-quantum key exchange – a new hope / http://cryptojedi.org/papers/#newhope, 2016.

Bos J.W., Costello C., Ducas L. [et all]. Frodo: take of the ring! Practical, quantum-secure key exchange from LWE // Proc. of ACM CCS 16, ACM Press, Okt. 2006, P. 1006-1018.

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

Post-Quantum Cryptography [Electronic resource]. Access mode: https://csrc.nist.gov/projects/post-quantum-cryptography.

Горбенко Ю. І. Аналіз шляхів розвитку криптографії після появи квантових комп’ютерів / Ю. І. Горбенко. Р. С. Ганзя // Комп’ютерні системи та мережі : Вісник нац. ун-ту «Львівська політехніка». 2014. № 806. С. 40–49.

Damien Stehlé and Ron Steinfeld. Making NTRU as secure as worst-case problems over ideal lattices. In Kenneth G. Paterson, editor, EUROCRYPT 2011, volume 6632 of LNCS, pages 27–47, Tallinn, Estonia, May 15–19, 2011. Springer, Heidelberg, Germany.

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

ДСТУ 7564:2014 Інформаційні технології. Криптографічний захист інформації. Функція гешуван-ня.

How to Cite

Олексійчук, А., Кулібаба, В., Єсіна, М., Кандій, С., Острянська, Є., & Горбенко, І. (2020). Substantiation of promising post-quantum national lattice-based electronic signature standard. Radiotekhnika, 1(200), 5–14. https://doi.org/10.30837/rt.2020.1.200.01

Issue

Section

Articles