Пост-квантовая криптография

Наверняка, многие, кто так или иначе связан с IT, слышали о том, что квантовый компьютер легко взламывает современные методы криптографии с открытым ключом. Существует множество разрозненных мнений о том, насколько скоро появится квантовый компьютер, способный «взломать» ключи той длины, которой мы пользуемся сегодня — 4096 бит RSA модуль или 256 бит подгруппа для Диффи-Хэллмана.

И всё же Агенство стандартизации NIST решило готовить сани летом и в 2018 году запустило конкурс на лучшие пост-квантовые примитивы. С предложенными кандидатами на пост-квантовую эру мы и познакомимся.

Предисловие

Современная криптография с открытым ключом (TLS, SSH, IpSec, Signal) основана на сложности факторизации больших чисел (RSA) и/или сложности вычисления дискретного логарифма (Диффи-Хэллман). В 1994 году Шор предложил квантовый алгоритм, решающий обе задачи за полиномиальное (от длины входных данных) время.

В терминологии криптоанализа такой алгоритм классифицируется как «тотальный взлом». Современные квантовые компьютеры не обладают мощностями, а именно количеством кубит, достаточными для решения этих задач в интересных для криптографии параметрах.

Сложно предсказать, когда мы получим квантовый компьютер, который сможет проводить вычисления с несколькими тысячами кубит. На всякий случай криптографы подготовили альтернативные криптографические примитивы, (предположительно) стойкие к атакам на квантовый компьютер.

Пост-квантовые решения

А именно, место теоретико-числовых задач (таких как факторизация, дискретный логарифм) могут занять:

I. Сложные задачи на евклидовых решетках

А именно, задача нахождения короткого вектора: по данному базису найти кратчайший ненулевой элемент решетки, определенной как

Плюсы решеток: сравнительно небольшие размеры ключей, быстрые алгоритмы генерации ключей, шифрования/дешифрования, наличие алгоритмов и для цифровой подписи, и для обмена ключами. Недостатки: плохая изученность сложности задачи короткого вектора решетки для эффективных схемах

Примеры: Frodo, New Hope, Crystals-Kyber, NTRU (для шифрования), Crypstals-Dilithium, Falcon (для цифровой подписи)

II. Сложные задачи из теории кодирования

Задача декодирования спрашивает, по данной матрице вектору и весовому значению найти вектор e, т.ч. He = s и

Плюсы задач теории кодирования: простота понимания, реализации; несколько десятилетий криптоанализа Недостатки: большие размеры ключа и, следовательно, более медленные операции. Отсутствие алгоритма подписи

Примеры: McEliece

III. Сложные задачи на многомерных полиномах

Найти решение (как правило, разряженное) системы уравнений от многих переменных над

Рисунок взят из презентации Albrecht Petzoldt, PQCrypto 2018

Плюсы: малый размер подписи Недостатки: сравнительно большой ключ, отсутствие алгоритма шифрования Примеры: MQDSS

IV. Задача вычисления изогении между абелевыми многообразиями

По двум (эллиптическим) кривым найти изогению определённой степени Рисунок сделан W.Castryk в этом посте

Плюсы: малые размеры ключей Недостатки: сравнительно мало изученная задача, длительные алгоритмы обмена ключами, подписи еще более неэффективные Примеры: SIKE, CSIDH

V. Задача нахождения коллизий хэш-функции

По сути, усложнение одноразовой подписи Лампорта

Рисунок взят из презентации Andreas Huelsing

Плюсы: небольшие ключи Недостатки: только подпись, сравнительно большой размер подписи

Примеры: SHINCS

Есть вопросы? Пишите в комментариях!