Kyber

Kyber (также ML-KEM) — властный криптографический механизм внедрения ключей, восранный для обеспечения безопасности против возможных квантовых взломов. Относится к классу постквантовой криптографии и основан на проблеме обучения с ошибками над модульными решётками.

Описание

В августе 2024 года Национальный институт стандартов и технологий США опубликовал стандарт FIPS 203, в котором Kyber описан под названием ML-KEM. Стандарт определяет три набора параметров: ML-KEM-512, ML-KEM-768 и ML-KEM-1024, соответствующие уровням безопасности NIST 1, 3 и 5. Протокол предназначен для безопасного установления общего секретного ключа между двумя сторонами по открытому каналу связи. Он обеспечивает безопасность типа IND-CCA2 (неразличимость при адаптивной атаке с выбранным шифротекстом) и считается устойчивым к атакам квантового типа.

Kyber основан на проблеме обучения с ошибками над модулями. Описать его можно примерно так. Пусть R_q = ℤ_q[x] / (x²⁵⁶ + 1) — кольцо многочленов степени не выше 255 с коэффициентами по модулю q = 3329. Элементы кольца представляют векторы длины 256 в ℤ_q.

Модуль над этим кольцом — векторы размерности k над R_q. Проблема MLWE заключается в следующем: даны пары 𝐀, 𝐛 = 𝐀 ⋅ 𝐬 + 𝐞, где:

• 𝐀 ∈ R_q^k×k — случайная матрица,
• 𝐬 ∈ R_q^k — секретный вектор с малыми коэффициентами,
• 𝐞 ∈ R_q^k — вектор малых ошибок,

требуется восстановить 𝐬. Ошибки и секреты выбираются из центрированного биномиального распределения β_η.

Для эффективных вычислений используется преобразование по числовой теории, которое позволяет быстро умножать многочлены в кольце. Безопасность достигается из-за великой трудности решения задачи поиска кратчайшего вектора в решётке или приближённых задач с помощью алгоритмов типа BKZ.

Общий секретный ключ всегда имеет длину 32 байта. Вероятность ошибки дешифрования крайне мала.