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

Появилась новая публикация (Daniel R. Simon), предлагающая квантовый алгоритм, взламывающий – теоретически! – криптосистемы типа ML-KEM/ML-DSA за полиномиальное время (то есть, атака предложена на задачу, лежащую в основе предположения о стойкости, в том числе, ML-KEM/ML-DSA, но подходит не только для них). Для работы алгоритма потребуется подходящий квантовый компьютер – уже этим многое сказано. Однако пока что и сама работа опубликована в статусе черновика, о чём там прямо сказано. То есть, скорее всего, – найдутся ошибки.

(У меня самого в этом направлении квантовых изысканий всё время вызывает сомнение ловкое “превращение вероятностей”, которые то идут потоком амплитуд, – это чисто квантово-механическая штука, обычно, описываемая при помощи комплексных чисел, – то вдруг становятся привычными вероятностями. Но я пока сформулировать это сомнение на более или менее понятном языке не могу, так что оставлю в скобках. Тем более, что это всё применимо и к алгоритму Шора.)

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

Что будет означать появление описания квантового алгоритма, эффективно взламывающего ML-KEM/ML-DSA и другие криптосистемы под собирательным обозначением “на решётках”? Это точно не приблизит к реальности сами универсальные квантовые компьютеры, но зато создаст вполне себе хорошее обоснование для того, чтобы либо улучшать стойкость ML-KEM/ML-DSA и прочих “решёточных” криптосистем, либо переходить на другие криптосистемы. И это будет весьма забавно: для атаки на постквантовые криптосистемы предложены новые теоретические квантовые алгоритмы, поэтому нужны суперпостквантовые криптосистемы, устойчивые и к алгоритму Шора, и к новому алгоритму “Имярек”.

Посмотрим, в общем, что там предложат. Так или иначе, но считать ML-KEM/ML-DSA неприступными – точно ещё рано.

(Update, 17/08/2026: в свежей работе (Aparna Gupte, Seyoon Ragavan, Mark Zhandry) утверждается, что квантовые алгоритмы данного типа, – как предложенный в исходной публикации, – вообще не позволяют извлечь информацию в количестве, необходимом для взлома криптосистемы.)

Адрес записки: https://dxdt.blog/2026/08/08/18839/