Постквантовые криптосистемы: открытые вопросы и существующие решения. Криптосистемы на решётках

Постквантовая криптография является актуальной областью теоретических и прикладных исследований, включающей в себя разработку и анализ методов криптографической защиты информации, применяемых в условиях широкого использования квантовых вычислений. В работе приведён обзор основных подходов к построению постквантовых криптографических систем, используемых в настоящее время. Подробно рассмотрено направление, в рамках которого предлагаются криптосистемы, стойкость которых основывается на вычислительной трудности ряда задач из теории решёток, представлен сложностной статус данных задач. Приведено описание и характеристики некоторых известных криптосистем, стойкость которых основана на сложности таких задач, как задача нахождения кратчайшего вектора, задача обучения с ошибками, а также их вариаций. Разобраны основные подходы к решению задач из теории решёток, лежащие в основе атак на соответствующие криптосистемы. В частности, приведены теоретические оценки времени работы и объёма используемой памяти для известных алгоритмов редукции и просеивания решёток. Табл. 6, ил. 1, библогр. 93.