ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА. ПРИЛОЖЕНИЕ
Архив статей журнала
Квантовые вычисления активно развиваются в последние десятилетия: увеличивается количество кубитов, с которыми оперирует квантовый компьютер, и снижается вероятность вычислительных ошибок. Поэтому возникает необходимость в разработке и анализе постквантовых криптосистем - криптосистем, устойчивых к атакам с использованием квантового компьютера. Одним из основных подходов к построению таких криптосистем является теория решёток. В данном подходе стойкость большинства криптосистем сводится к решению задачи нахождения кратчайшего вектора в решётке (SVP). В работе приводятся результаты анализа алгоритма 8-просеивания для решения SVP. Предлагается новый компромисс между временем работы и количеством используемой памяти алгоритма 8-просеивания. Приводится сравнение с известными алгоритмами k-просеивания. На отрезке (20-155n, 20-189n) используемой памяти предложенный алгоритм имеет минимальное время работы среди известных алгоритмов k-просеивания.
Приводятся результаты анализа схемы VKO и комбинированной схемы VKO+подпись в моделях обобщённой группы и биективного случайного оракула. Получена верхняя оценка сложности задачи различения выхода схемы VKO от случайной равновероятной строки (в эвристике обобщенной группы), а также показано, что возможности получения подписи сообщений по алгоритму genGOST не даёт никакой дополнительной информации противнику в этой задаче (в эвристике биективного случайного оракула).