dxdt.blog: занимательный интернет-журнал

Часто попадаются фразы, что, например, алгоритм ML-KEM – это алгоритм, “стойкий к подбору на квантовом компьютере”. Вопрос, конечно, терминологический, но попробуем разобраться, почему такая формулировка (“стойкий к подбору”) – не верная, и почему так писать нежелательно.

Более или менее строгое определение: “ML-KEM, теоретически, обладает стойкостью к взлому при помощи алгоритма Шора”.

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

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

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

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

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

Адрес записки: https://dxdt.blog/2026/05/17/18231/