RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2023, том 30, выпуск 4, страницы 46–90 (Mi da1334)

Эта публикация цитируется в 4 статьях

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

Е. С. Малыгинаab, А. В. Куценкоb, С. А. Новосёловa, Н. С. Колесниковa, А. О. Бахаревb, И. С. Хильчукb, А. С. Шапоренкоb, Н. Н. Токареваba

a Балтийский федеральный университет им. И. Канта, ул. Александра Невского, 14, 236041 Калининград, Россия
b Новосибирский гос. университет, ул. Пирогова, 2, 630090 Новосибирск, Россия

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

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

УДК: 519.7

Статья поступила: 04.05.2023
Переработанный вариант: 28.07.2023
Принята к публикации: 20.08.2023

DOI: 10.33048/daio.2023.30.771


 Англоязычная версия: Journal of Applied and Industrial Mathematics, 2023, 17:4, 767–790


© МИАН, 2024