Cryptanalysis of the «Vershyna» digital signature algorithm

Authors

  • Andrii Fesenko Institute of Physics and Technology, National Technical University of Ukraine ``Igor Sikorsky Kyiv Polytechnic Institute'', Ukraine
  • Yuliia Lytvynenko National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Institute of Physics and Technology, Ukraine

DOI:

https://doi.org/10.20535/tacs.2664-29132023.2.288499

Abstract

The CRYSTALS-Dilithium digital signature algorithm, which was selected as the prototype of the new «Vershyna» digital signature algorithm, is analyzed in this paper. The characteristics of the National Digital Signature Standard Project and the construction of the «Vershyna» algorithm are also presented. During the analysis of the project, the predicted number of iterations that the algorithm must perform to create the correct signature was calculated. In addition, basic theoretical information about the structure of Fiat-Shamir with aborts and its security in quantum and classical models oracle models is also provided. We obtain our own results on the resistance of the «Vershyna» algorithm to the attack without the use of a message in classical and quantum oracle models. The resistance of the «Vershyna» algorithm to a key recovery attack is based on the assumption of the hardness of the MLWE~problem, and the resistance to existential signature forgery is based on the assumption of the hardness of the MSIS~problem. In this work, the expected level of hardness of SIS~and LWE~problems is calculated, to which there are reductions from MSIS~and MLWE~problems.

Downloads

Published

2023-11-06

Issue

Vol. 5 No. 2 (2023): Theoretical and Applied Cyber Security

Section

Theoretical and cryptographic problems of cybersecurity

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).