OPTIMIZATION OF COMPUTATIONS OVER POLYNOMIALS IN POST-QUANTUM SIGNATURE SCHEME
Voprosy kiberbezopasnosti · 2024
Цель исследования: ускорение операции проверки подписи в постквантовых криптографических системах путем применения к вычислениям над полиномами быстрых алгоритмов.Методы исследования: сравнительный анализ принятых к стандартизации постквантовых алгоритмов, математическое моделирование операции проверки подписи, оптимизация путем синтеза быстрых алгоритмов.Результаты исследования: на основании коммуникационных затрат, стойкости к атакам полным перебором, используемых парадигм и примитивов, и производительности на маломощных устройствах определены области применения схемы подписи Falcon, вследствие чего обоснована важность оптимизации данного алгоритма.Приведено математическое описание задачи, обосновывающей криптостойкость алгоритма Falcon, и определены ресурсоемкие операции над полиномами, применяемые в данной задаче.Рассмотрены алгоритмы, использующиеся для оптимизации операции проверки подписи в эталонной реализации схемы Falcon, и приведено обоснование их неэффективности при внедрении Falcon в маломощные устройства.Предложен метод оптимизации путем синтеза быстрых алгоритмов вычисления числового теоретического преобразования и быстрого алгоритма приведения целого числа по модулю.На основании данного метода разработана реализация оптимизационного алгоритма на языке Си.Практическая значимость: предложенный метод оптимизации не использует архитектурные особенности среды, на которой тестируется данный алгоритм подписи, и не требует хранения дополнительных предвычисленных значений, благодаря чему может иметь широкое применение в различных областях.Разработанная реализация оптимизационного алгоритма на основе предложенного метода оптимизации может быть внедрена в эталонную реализацию схемы Falcon.