Не так давно мы публиковали новость о возможном квантовом взломе алгоритма RSA

Руководитель научной группы «Квантовые информационные технологии» РКЦ Алексей Федоров дал по этому поводу комментарий. После чего Алексей и его коллеги опубликовали статью «Подводные камни сублинейного алгоритма факторизации на основе QAOA», в которой объяcнили, почему они считают подобные выводы преждевременными: https://arxiv.org/abs/2303.04656

Приводим целиком комментарий Алексея Федорова:

А был ли взлом? Пристальный взгляд на громкий анонс о квантовом взломе алгоритма RSA

В конце 2022 года была опубликована работа [1], в которой заявлялось о достижении сублинейной оценки для алгоритма факторизации. Основываясь на классическом методе факторизации Шнорра [2] (не путать с квантовым алгоритмом Шора [3]), авторы использовали квантовое ускорение для приближенного получения результатов одного из его этапов – решения задачи поиска короткого вектора в решетке (SVP) небольшой размерности – что позволило им сделать сенсационное заявление о том, что для факторизации числа требуется меньше кубитов, чем его длина, а также квантовые схемы меньшей глубины, чем считалось ранее (см., например, [4]). Работоспособность метода была продемонстрирована на примере 48-битового числа RSA и 10-кубитного квантового компьютера. В итоге исследователи делают вывод, что для факторизации 2048-битового числа достаточно 372 физических кубитов.

Неудивительно, что некоторые СМИ уже “хоронят” современную асимметричную криптографию, а заодно и постквантовые криптосистемы, основанные на SVP – ведь компания IBM уже анонсировала готовность 433-кубитового квантового процессора Osprey [5].

Мы, однако, считаем этот вывод преждевременным ввиду следующих обстоятельств.

1) Метод Шнорра до сих пор не имеет корректной оценки сложности. Предполагается, что она является экспоненциальной, причем основная трудоемкость сосредоточена не в решении SVP, а в наборе достаточного количества таких задач (как в методе решета числового поля для факторизации требуется набор достаточного количества соотношений).

2) Отсюда следует, что метод по всей видимости Шнорра не масштабируется на числа RSA, реально использующиеся в современной криптографии.

3) Метод из [1] позволяет получить лишь приближенное решение SVP, которое относительно легко скорректировать для небольших чисел и решеток малой размерности, но практически невозможно для реально используемых параметров криптосистем.

4) Метод Шнорра не переносится на криптосистемы на эллиптических кривых (ГОСТ 34.10-2018).

5) Квантовая часть алгоритма основывается на подходе quantum approximate optimization algorithm (QAOA), который имеет сложности со сходимостью (как отмечают авторы: “However, the touch-size is an ideal basic situation, the QAOA usually works more than one layer and deeper circuit required. Besides, the quantum speedup is unknown, it is still a long way to break RSA quantumly”).

Хотя метод из [1], по всей видимости, не ведет к мгновенному взлому существующих криптоалгоритмов — появление новых классических и квантовых алгоритмов криптоанализа является важным аргументом на пути к внедрению постквантовой криптографии.

[1] https://arxiv.org/pdf/2212.12372.pdf

[2] https://eprint.iacr.org/2021/933

[3] https://arxiv.org/abs/quant-ph/9508027

[4] https://arxiv.org/abs/1905.09749

[5] https://newsroom.ibm.com/2022-11-09-IBM-Unveils-400-Qubit-Plus-Quantum-Processor-and-Next-Generation-IBM-Quantum-System-Two

Источник: newsroom.ibm.com

Комментарии: