Acceleration of modular arithmetic in post-quantum signature schemes
Since the discovery of the Shor quantum algorithm, capable of solving factorization and discrete logarithm problems in polynomial time, post-quantum cryptographic algorithms have been actively developed. Although some of the post-quantum algorithms have already been standardized by NIST, an importan...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Joint Stock Company "Experimental Scientific and Production Association SPELS
2024-11-01
|
| Series: | Безопасность информационных технологий |
| Subjects: | |
| Online Access: | https://bit.spels.ru/index.php/bit/article/view/1718 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1846151575381213184 |
|---|---|
| author | Igor Y. Zhukov Vitaliy G. Ivanenko Irina D. Ivanova Nina D. Ivanova |
| author_facet | Igor Y. Zhukov Vitaliy G. Ivanenko Irina D. Ivanova Nina D. Ivanova |
| author_sort | Igor Y. Zhukov |
| collection | DOAJ |
| description | Since the discovery of the Shor quantum algorithm, capable of solving factorization and discrete logarithm problems in polynomial time, post-quantum cryptographic algorithms have been actively developed. Although some of the post-quantum algorithms have already been standardized by NIST, an important problem remains their lower efficiency compared to the classical cryptographic algorithms. The purpose of this work is to accelerate operations on polynomials in lattice-based post-quantum signature schemes. The research is carried out by analyzing fast multiplucation and reduction algorithms. The paper considers the Number Theoretic Transform (NTT), K-RED and Montgomery reduction algorithms. The effectiveness of the K-RED algorithm in comparison with the algorithm Montgomery is substantiated. The question of the applicability of the NTT and fast reduction algorithms in the Russian signature scheme «Kryzhovnik» and NIST algorithms Falcon and CRYSTALS-Dilithium is considered. As a result of the research, recommendations for embedding the K-RED algorithm in the reference implementations of the Falcon and CRYSTALS-Dilithium signature schemes are given, as well as the implementation in C of accelerated multiplication using the NTT and the K-RED algorithm. The results of this research can be embedded in the NIST standards FIPS 204 and FIPS 206, as well as adapted for use in other lattice-based signature schemes. |
| format | Article |
| id | doaj-art-e337fefdc64c493baded80cc6bb8c6e0 |
| institution | Kabale University |
| issn | 2074-7128 2074-7136 |
| language | English |
| publishDate | 2024-11-01 |
| publisher | Joint Stock Company "Experimental Scientific and Production Association SPELS |
| record_format | Article |
| series | Безопасность информационных технологий |
| spelling | doaj-art-e337fefdc64c493baded80cc6bb8c6e02024-11-27T09:30:13ZengJoint Stock Company "Experimental Scientific and Production Association SPELSБезопасность информационных технологий2074-71282074-71362024-11-013149910810.26583/bit.2024.4.061424Acceleration of modular arithmetic in post-quantum signature schemesIgor Y. Zhukov0Vitaliy G. Ivanenko1Irina D. Ivanova2Nina D. Ivanova3National Research Nuclear University MEPhI (Moscow Engineering Physics Institute)National Research Nuclear University MEPhI (Moscow Engineering Physics Institute)Russian University of Transport (MIIT)Russian University of Transport (MIIT)Since the discovery of the Shor quantum algorithm, capable of solving factorization and discrete logarithm problems in polynomial time, post-quantum cryptographic algorithms have been actively developed. Although some of the post-quantum algorithms have already been standardized by NIST, an important problem remains their lower efficiency compared to the classical cryptographic algorithms. The purpose of this work is to accelerate operations on polynomials in lattice-based post-quantum signature schemes. The research is carried out by analyzing fast multiplucation and reduction algorithms. The paper considers the Number Theoretic Transform (NTT), K-RED and Montgomery reduction algorithms. The effectiveness of the K-RED algorithm in comparison with the algorithm Montgomery is substantiated. The question of the applicability of the NTT and fast reduction algorithms in the Russian signature scheme «Kryzhovnik» and NIST algorithms Falcon and CRYSTALS-Dilithium is considered. As a result of the research, recommendations for embedding the K-RED algorithm in the reference implementations of the Falcon and CRYSTALS-Dilithium signature schemes are given, as well as the implementation in C of accelerated multiplication using the NTT and the K-RED algorithm. The results of this research can be embedded in the NIST standards FIPS 204 and FIPS 206, as well as adapted for use in other lattice-based signature schemes.https://bit.spels.ru/index.php/bit/article/view/1718lattices, post-quantum cryptography, reduction algorithm, multiplication of polynomials, quotient ring. |
| spellingShingle | Igor Y. Zhukov Vitaliy G. Ivanenko Irina D. Ivanova Nina D. Ivanova Acceleration of modular arithmetic in post-quantum signature schemes Безопасность информационных технологий lattices, post-quantum cryptography, reduction algorithm, multiplication of polynomials, quotient ring. |
| title | Acceleration of modular arithmetic in post-quantum signature schemes |
| title_full | Acceleration of modular arithmetic in post-quantum signature schemes |
| title_fullStr | Acceleration of modular arithmetic in post-quantum signature schemes |
| title_full_unstemmed | Acceleration of modular arithmetic in post-quantum signature schemes |
| title_short | Acceleration of modular arithmetic in post-quantum signature schemes |
| title_sort | acceleration of modular arithmetic in post quantum signature schemes |
| topic | lattices, post-quantum cryptography, reduction algorithm, multiplication of polynomials, quotient ring. |
| url | https://bit.spels.ru/index.php/bit/article/view/1718 |
| work_keys_str_mv | AT igoryzhukov accelerationofmodulararithmeticinpostquantumsignatureschemes AT vitaliygivanenko accelerationofmodulararithmeticinpostquantumsignatureschemes AT irinadivanova accelerationofmodulararithmeticinpostquantumsignatureschemes AT ninadivanova accelerationofmodulararithmeticinpostquantumsignatureschemes |