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

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