Математические методы криптографии

Современные парадигмы построения схем цифровой подписи на решётках

А. Г. Леевик^ab, Е. С. Малыгина^ac, Е. М. Мельничук^a, Д. А. Набоков<sup>a

a</sup> ООО «КуАпп», г. Москва, Россия
^b Университет ИТМО, г. Санкт-Петербург, Россия
^c Международный научно-образовательный математический центр НГУ, Новосибирский государственный университет, г. Новосибирск, Россия

Аннотация: Ввиду возникновения угрозы нарушения стойкости криптографических алгоритмов с помощью квантового вычислителя большую популярность обрело направление постквантовой криптографии — нового раздела, включающего алгоритмы и протоколы, эффективно противостоящие атакам с помощью квантового компьютера. Теория решёток на сегодняшний день является перспективным направлением постквантовой криптографии. Одними из первых криптосистем на решетках были GGH и NTRU. В их основе лежит задача о поиске ближайшего вектора решётки, а отличие схем заключается в построении решёток. На основе криптосистем GGH и NTRU была предложена схема цифровой подписи NTRUSign, взявшая лучшее у них. Другой подход к построению подписи появился в 2008 г., в его основе лежит парадигма Hash-and-Sign, а подпись для сообщения вырабатывается с помощью лазейки. Годом позже В. Любашевским был предложен ещё один подход к построению подписи на решетках. Он заключается в использовании преобразования Фиата — Шамира, однако в силу специфики решёток алгоритм формирования подписи выдаёт корректную подпись с некоторой вероятностью, поскольку в целях безопасности используется выборка отбраковки. В данной работе представлен обзор существующих парадигм построения схем цифровых подписей на решётках, а также криптографических схем, построенных на рассматриваемых парадигмах. Проведён сравнительный анализ схем, определены преимущества и недостатки каждого из подходов, определены наилучшие условия их применения.

Ключевые слова: постквантовая криптография, теория решёток, цифровая подпись на базе решёток.

УДК: 519.7

DOI: 10.17223/20710410/67/2