Publication: УСКОРЕНИЕ МОДУЛЬНОЙ АРИФМЕТИКИ В ПОСТКВАНТОВЫХ СХЕМАХ ПОДПИСИ
Дата
2024
Авторы
Жуков, И. Ю.
Иваненко, В. Г.
Иванова, И. Д.
Иванова, Н. Д.
Journal Title
Journal ISSN
Volume Title
Издатель
НИЯУ МИФИ
Аннотация
С момента открытия квантового алгоритма Шора, способного за полиномиальное время решить задачи факторизации и дискретного логарифмирования, в мире ведется активная разработка постквантовых криптографических алгоритмов. Хотя некоторые из постквантовых алгоритмов уже стандартизированы NIST, важной проблемой остается их меньшая эффективность в сравнении с классическими криптографическими алгоритмами, используемыми в настоящее время. Целью данной работы является ускорение операций над полиномами в постквантовых схемах подписи, основанных на теории решеток. Исследование проводится путем анализа быстрых алгоритмов умножения полиномов и алгоритмов приведения чисел по модулю. В работе рассмотрены числовое теоретическое преобразование (NTT), применяемое для ускорения умножения полиномов в конечных полях, и используемые им алгоритмы приведения по модулю K-RED и Монтгомери. Обоснована эффективность алгоритма K-RED в сравнении с алгоритмом Монтгомери, используемым в эталонных реализациях постквантовых схем подписи. Рассмотрен вопрос применимости преобразования NTT и быстрых алгоритмов приведения чисел по модулю для внедрения в состав российской схемы подписи «Крыжовник» и американских алгоритмов Falcon и CRYSTALS-Dilithium. В результате исследования приведены рекомендации по встраиванию алгоритма K-RED в эталонные реализации схем подписи Falcon и CRYSTALS-Dilithium, а также осуществлена реализация на языке Си ускоренного умножения полиномов в конечных полях при помощи преобразования NTT и алгоритма K-RED. Результаты настоящего исследования могут быть внедрены в стандарты NIST постквантовых схем подписи FIPS 204 и FIPS 206, а также адаптированы для использования в иных схемах подписи, основанных на теории решеток и использующих факторкольца.
Описание
Ключевые слова
факторкольцо , умножение полиномов , приведение числа по модулю , постквантовая криптография , теория решеток
Цитирование
ЖУКОВ, Игорь Ю. и др. УСКОРЕНИЕ МОДУЛЬНОЙ АРИФМЕТИКИ В ПОСТКВАНТОВЫХ СХЕМАХ ПОДПИСИ. Безопасность информационных технологий, [S.l.], т. 31, № 4, с. 99–108, 2024. ISSN 2074-7136. URL: https://bit.spels.ru/index.php/bit/article/view/1718. DOI: http://dx.doi.org/10.26583/bit.2024.4.06