Processes and methods of selection of system-wide parameters of perspective algorithm of electronic signature based on algebraic lattices
Keywords:system-wide parameters, post-quantum electronic signature algorithms, algebraic lattices, hashing functions, cryptographic stability.
AbstractAn important feature of the transition and post-quantum period is the application of new mathematical methods to counteract quantum cryptanalysis. The world cryptographic community pays special attention to the open competition for the post-quantum standard of electronic signature. The problem is to prove the stability of new mathematical methods for the synthesis of transformations such as electronic signature, in particular with the use of algebraic lattices. The existing algorithms of electronic signature of the 2nd stage of the NIST competition are analyzed. Among the selected candidates for the EP 2 standard, 3 of the 3 algorithms are based on algebraic lattices, CRYSTALS-DILITHIUM and FALCON. The NIST has issued a statement saying that it is most likely that one of the algorithms will be chosen due to the same mathematical basis used in both algorithms. The main attacks on electronic signature algorithms based on the problem of learning with errors, as well as the parameters of the EP Dilithium algorithm, which affect the stability and complexity of transformations, are considered. Methods for generating system-wide parameters of stability levels of 512 bits of classical and 256 bits of quantum security, as well as the protection of the algorithm againstfrom attacks by third-party channels are considered. The dependence of the time of electronic signature production on the keys is analyzed. The results of calculations for the level of stability 512/256 are given, and also recommendations on the choice of system-wide parameters are given. The results of the 2nd stage of the NIST competition of post quantum cryptographic algorithms, as well as the prospects of standardization of transformations such as electronic signature at the 3rd stage are considered. Conclusions are made about the need for a more detailed study of attacks on algorithms based on the problem of learning with errors, as well as the importance of generating system-wide parameters of higher levels.
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. Access mode: http://csrc.nist.gov/publications/drafts/nistir-8105/nistir_8105_draft.pdf.
Gottfried Herold, Elena Kirshanova, and Alexander May. On the asymptotic complexity of solving LWE // Designs, Codes and Cryptography, Jan 2017.
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. Electronic resource. Access mode: https://csrc.nist.gov/Projects/post-quantum-cryptography/round-2-submissions.
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.
Rachel Player. Parameter selection in lattice-based cryptography. Access mode: https://pure.royalholloway.ac.uk/portal/files/29983580/2018playerrphd.pdf.
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, volume 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, volume 8383 of LNCS, pages 429–445. Springer, Heidelberg, March 2014.
Vadim Lyubashevsky. Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures // 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.
Горбенко І. Д., Постквантова криптографія та механізми її реалізації / І. Д. Горбенко, О. О. Кузнецов, О. В. Потій, Ю. І. Горбенко, Р. С., Ганзя, В. А. Пономар // Радиотехника. 2017. Вип. 186. С. 32–52.
Кулібаба В.А., Перспективні методи та системи критптографічного захисту інформації / О.М. Олексійчук, В.А. Кулібаба, М.В. Єсіна, С. О. Кандій, Є.В. Острянська, І.Д. Горбенко // Радіотехніка. 2020. Вип. 200. С. 5-13.
How to Cite
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).