Вычислительные методы в дискретной математике

Исследование алгоритма $k$-просеивания для решения задачи нахождения кратчайшего вектора в решётке

А. О. Бахарев<sup>ab

a</sup> Новосибирский государственный университет
^b АО «НПК «Криптонит»

Аннотация: Квантовые вычисления активно развиваются в последние десятилетия: увеличивается количество кубитов, с которыми оперирует квантовый компьютер, и снижается вероятность вычислительных ошибок. Поэтому возникает необходимость в разработке и анализе постквантовых криптосистем — криптосистем, устойчивых к атакам с использованием квантового компьютера. Одним из основных подходов к построению таких криптосистем является теория решёток. В данном подходе стойкость большинства криптосистем сводится к решению задачи нахождения кратчайшего вектора в решётке (SVP). В работе приводятся результаты анализа алгоритма $8$-просеивания для решения SVP. Предлагается новый компромисс между временем работы и количеством используемой памяти алгоритма $8$-просеивания. Приводится сравнение с известными алгоритмами $k$-просеивания. На отрезке $(2^{0{,}157n}, 2^{0{,}189n})$ используемой памяти предложенный алгоритм имеет минимальное время работы среди известных алгоритмов $k$-просеивания.

Ключевые слова: теория решёток, $k$-просеивание, SVP, постквантовая криптография.

УДК: 519.7

DOI: 10.17223/2226308X/17/41