УСКОРЕНИЕ МОДУЛЬНОЙ АРИФМЕТИКИ В ПОСТКВАНТОВЫХ СХЕМАХ ПОДПИСИ

Игорь Ю. Жуков, Виталий Г. Иваненко, Ирина Д. Иванова, Нина Д. Иванова

Аннотация


С момента открытия квантового алгоритма Шора, способного за полиномиальное время решить задачи факторизации и дискретного логарифмирования, в мире ведется активная разработка постквантовых криптографических алгоритмов. Хотя некоторые из постквантовых алгоритмов уже стандартизированы NIST, важной проблемой остается их меньшая эффективность в сравнении с классическими криптографическими алгоритмами, используемыми в настоящее время. Целью данной работы является ускорение операций над полиномами в постквантовых схемах подписи, основанных на теории решеток. Исследование проводится путем анализа быстрых алгоритмов умножения полиномов и алгоритмов приведения чисел по модулю. В работе рассмотрены числовое теоретическое преобразование (NTT), применяемое для ускорения умножения полиномов в конечных полях, и используемые им алгоритмы приведения по модулю K-RED и Монтгомери. Обоснована эффективность алгоритма K-RED в сравнении с алгоритмом Монтгомери, используемым в эталонных реализациях постквантовых схем подписи. Рассмотрен вопрос применимости преобразования NTT и быстрых алгоритмов приведения чисел по модулю для внедрения в состав российской схемы подписи «Крыжовник» и американских алгоритмов Falcon и CRYSTALS-Dilithium. В результате исследования приведены рекомендации по встраиванию алгоритма K-RED в эталонные реализации схем подписи Falcon и CRYSTALS-Dilithium, а также осуществлена реализация на языке Си ускоренного умножения полиномов в конечных полях при помощи преобразования NTT и алгоритма K-RED. Результаты настоящего исследования могут быть внедрены в стандарты NIST постквантовых схем подписи FIPS 204 и FIPS 206, а также адаптированы для использования в иных схемах подписи, основанных на теории решеток и использующих факторкольца.


Ключевые слова


теория решеток, постквантовая криптография, приведение числа по модулю, умножение полиномов, факторкольцо.

Полный текст:

PDF

Литература


1. Allende M. et al. Quantum-resistance in blockchain networks. Scientific Reports. 2023, v. 13, no. 1, p. 5664.
DOI: http://dx.doi.org/10.1038/s41598-023-32701-6.

2. Raavi M. et al. Security Comparisons and Performance Analyses of Post-Quantum Signature Algorithms. Lecture Notes in Computer Science. 2021, v. 12727, 24 p.
DOI: http://dx.doi.org/10.1007/978-3-030-78375-4_17.

3. Киршанова Е.А. и др. Проект стандартизации постквантовой цифровой подписи. Прикладная дискретная математика. Приложение. 2020, № 13, с. 44–51.
DOI: http://dx.doi.org/10.17223/2226308X/13/14.

4. Ducas L. et al. Finding short integer solutions when the modulus is small. Annual International Cryptology Conference. 2023, p. 150–176. DOI: http://dx.doi.org/10.1007/978-3-031-38548-3_6.

5. Alkim E. et al. Polynomial Multiplication in NTRU Prime: Comparison of Optimization Strategies on Cortex-M4. (2020). IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021(1), р. 217–238.
DOI: http://dx.doi.org/10.46586/tches.v2021.i1.217-238.

6. Liang Z., Zhao Y. Number theoretic transform and its applications in lattice-based cryptosystems: A survey. arXiv preprint arXiv:2211.13546. 2022. – 35 p.
DOI: http://dx.doi.org/10.48550/arXiv.2211.13546.

7. Becker H. et al. Polynomial multiplication on embedded vector architectures. Cryptology ePrint Archive. 2021. – 29 p. URL: https://eprint.iacr.org/2021/998 (дата обращения: 06.09.2024).

8. Nguyen T.H., Pham C.K., Hoang T.T. A high-efficiency modular multiplication digital signal processing for lattice-based post-quantum cryptography. Cryptography. 2023, v. 7, no. 4, p. 46.
DOI: http://dx.doi.org/10.3390/cryptography7040046.

9. Liang Z. et al. Number Theoretic Transform: Generalization, Optimization, Concrete Analysis and Applications. International Conference on Information Security and Cryptology. 2020, p. 415–432.
DOI: http://dx.doi.org/10.1007/978-3-030-71852-7_28.

10. Basso A., Roy S. S. Optimized Polynomial Multiplier Architectures for Post-Quantum KEM Saber. 58th ACM/IEEE Design Automation Conference (DAC). 2021, p. 1285–1290.
DOI: http://dx.doi.org/10.1109/DAC18074.2021.9586219.

11. Ishida T. et al. A Proposal of Solving NTRU Equation Using Matrix Representation Instead of Recursive Operation. 2023 Eleventh International Symposium on Computing and Networking Workshops (CANDARW). 2023, p. 227–231.
DOI: http://dx.doi.org/10.1109/CANDARW60564.2023.00045.

12. Pornin T. Improved Key Pair Generation for Falcon, BAT and Hawk. Cryptology ePrint Archive. 2023. – 10 p. URL: https://eprint.iacr.org/2023/290 (дата обращения: 06.09.2024).

13. Satriawan A., Syafalni I., Mareta R., Anshori I., Shalannanda W. and Barra A. Conceptual Review on Number Theoretic Transform and Comprehensive Review on Its Implementations. IEEE Access, v. 11, p. 70288–70316, 2023.
DOI: http://dx.doi.org/10.1109/ACCESS.2023.3294446.

14. Bisheh-Niasar M., Azarderakhsh R. and Mozaffari-Kermani M. High-Speed NTT-based Polynomial Multiplication Accelerator for Post-Quantum Cryptography. IEEE 28th Symposium on Computer Arithmetic (ARITH), Lyngby, Denmark. 2021, p. 94–101.
DOI: http://dx.doi.org/10.1109/ARITH51176.2021.00028.

15. Li M., Tian J., Hu X., Cao Y. and Wang Z. High-Speed and Low-Complexity Modular Reduction Design for CRYSTALS-Kyber. IEEE Asia Pacific Conference on Circuits and Systems (APCCAS), Shenzhen, China. 2022, p. 1–5.
DOI: http://dx.doi.org/10.1109/APCCAS55924.2022.10090253.




DOI: http://dx.doi.org/10.26583/bit.2024.4.06

Ссылки

  • На текущий момент ссылки отсутствуют.


Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.