Постквантовая “гибридизация” криптосистем и перспективы стойкости

Криптосистемы с постквантовой стойкостью предлагается внедрять в составе гибридных схем. Именно так сделано в TLS и в браузерах: широко и давно используемая X25519 + постквантовая криптосистема Kyber, на случай, если последняя окажется нестойкой. Под “гибридной” схемой здесь подразумевается объединение секретов, независимо полученных применением одной и второй криптосистемы: ни о каком “подмешивании” шагов одной криптосистемы в другую речи нет – X25519 не влияет на стойкость Kyber и наоборот (формальная оценка стойкости гибридной схемы в целом и для разных моделей – несколько другая история, но эти детали тут не важны). Подобная “гибридизация” имеет ряд занимательных особенностей: так, постквантовая Kyber должна, очевидно, обладать и стойкостью к классическим атакам, а это означает, что она некоторым образом усиливает защиту сессий с точки зрения переспективных атак “неквантовыми методами”.

То есть, данные криптосистемы достаточно различаются математически, чтобы даже универсальная атака на X25519 не сломала, гарантированно, и Kyber. Так что, если через десять лет вариант протокола Диффи-Хеллмана (ECDH), реализуемый X25519, научатся быстро ломать, – например, для конкретных параметров, – то записанный трафик всё равно будет защищён Kyber. Естественно, это всего лишь обращение мотивации для использования X25519 вместе с Kyber, чтобы подстраховаться на случай внезапного обнаружения неустранимых дефектов в последней. Обратная схема тоже работает, но X25519 используется дольше и, возможно, лучше изучена, так что “поломка” Kyber, конечно, выглядит более вероятным событием.

Вообще, из того, что Kyber признана криптосистемой с постквантовой стойкостью и стандартизована как ML-KEM, вовсе не следует, что доказано отсутствие квантовых алгоритмов взлома Kyber; уж тем более неверно будет утверждать, что эффективность решения базовой задачи для Kyber не отличается на обычных и квантовых компьютерах. Во-первых, квантовых компьютеров пока что нет, и непонятно, как они вообще могли бы быть устроены, чтобы ломать Kyber. Во-вторых, квантовые компьютеры сами ничего “не вычисляют” в том смысле, чтобы сравнивать с “обычными” (но всякий квантовый алгоритм можно запустить и выполнить на “обычном компьютере” – времени потребуется несравнимо больше, чем хотелось бы для достижения практической полезности). В-третьих, доказывать отсутствие алгоритмов вообще непросто. Так что в случае с постквантовой стойкостью слишком многое сводится к алгоритму Шора, в его самой теоретической интерпретации, а для ML-KEM/Kyber резонно ожидать и квантовых улучшений атак тоже.

Более того, поскольку одна задача (Kyber) не переводится быстро в другую (ECDH), то можно предположить не только появление специального квантового алгоритма для эффективного взлома Kyber, но и то, что квантовый компьютер, реализующий этот алгоритм, окажется (согласно некоторой теории) построить проще, чем не менее квантовый компьютер для алгоритма Шора. А что? Теоретические аналоговые вычислители они на то и теоретические, и аналоговые, что это сейчас только различные оценки количества “квантовых элементов” для практической атаки на RSA расходятся на несколько десятичных порядков, а на следующем шаге – могут разойтись и оценки достижимости по новым и старым алгоритмам.

Адрес записки: https://dxdt.ru/2024/10/13/14060/

Похожие записки:



Далее - мнения и дискуссии

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

Написать комментарий

Ваш комментарий:

Введите ключевое слово "RSFRF" латиницей СПРАВА НАЛЕВО (<--) без кавычек: (это необходимо для защиты от спама).

Если видите "капчу", то решите её. Это необходимо для отправки комментария ("капча" не применяется для зарегистрированных пользователей). Обычно, комментарии поступают на премодерацию, которая нередко занимает продолжительное время.