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

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