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