А был ли взлом? Пристальный взгляд на громкий анонс о квантовом взломе алгоритма 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

Умер Юрий Манин

7 января скончался выдающийся математик Юрий Иванович Манин (16 февраля 1937 – 7 января 2023). Он был одним из основоположников некоммутативной алгебраической геометрии, теории квантовых вычислений и квантовой информатики. Именно в книге Юрия Манина «Вычислимое и невычислимое» возникла идея использования квантовых состояний для обработки информации — концепция квантовых вычислений.

Юрий Иванович – выпускник и профессор кафедры высшей алгебры (по 1992 год) механико-математического факультета МГУ, заслуженный профессор Математического института Макса Планка (Бонн), профессор Северо-западного университета (США), член-корреспондент РАН, член Королевской академии наук Нидерландов, Гёттингенской академии наук, академии «Леопольдина», Французской академии наук, Американской академии искусств и наук и Папской академии наук (Ватикан), почётный доктор Сорбонны, Университета Осло и Уорикского университета.

#Дайджест за 6-10 марта 2023 г.

#УИИ #кванты #исследование #квантовыйкомпьютер

📌УИИ совместно с РКЦ проверяет гипотезу квантового ускорения взлома достаточно длинных RSA-ключей с помощью современных квантовых компьютеров

В конце декабря 2022 года группа китайских исследователей продемонстрировала возможность взлома достаточно длинных RSA-ключей с помощью современных квантовых компьютеров и квантово-ускоренного варианта метода Шнорра (не путать с квантовым алгоритмом Шора) факторизации целых чисел, впервые предложенном в 2021 году (Schnorr C. P. Fast Factoring Integers by SVP Algorithms).

В работе китайских исследователей «Factoring integers with sublinear resources on a superconducting quantum processor» говорится о первом в истории взломе 48-битного ключа системой всего из 10 сверхпроводящих кубитов.

Согласно высказанным в статье предположениям, для взлома ключа RSA-2048 потребуется не более 372 кубитов, что уже скоро будет возможно для современных квантовых компьютеров — таких, как представила в ноябре 2022 года IBM.

Это может означать, что RSA, на котором построены сегодня почти все системы, передающие и хранящие конфиденциальную информацию, скоро уйдет в прошлое.
 
Именно на проверку этого предложенного способа взлома RSA-ключей и были направлены усилия на первом этапе работы Управления исследований и инноваций и Российского квантового центра.

Полностью подтвердить корректность предложенного китайскими учёными подхода к квантовому ускорению алгоритма факторизации Шнорра пока не удалось.

Это может быть следствием использования для нашего эксперимента квантового симулятора вместо физического квантового вычислителя, погрешностями в эксперименте и, возможно, какими-то «недосказанностями» в исследуемой статье о приведённых там путях взлома RSA.
 
На втором этапе наше исследование будет направлено на восстановление корректного описания алгоритма и определение возможности его масштабирования.

Журнал The New Yorker опубликовал интересную популярную статью Стивена Витта «Изменившая мир гонка за разработку квантового компьютера»: Такое устройство могло бы помочь решить проблему изменения климата и нехватки продовольствия или сломать Интернет. Доберутся ли США или Китай до этого первыми?

В статье красивым языком описано становление квантовых вычислений как области технологий, за которую в мире ведется гонка и борьба. Всем интересно какая платформа в итоге станет лидирующей и более перспективной. В состав персонажей входят такие ведущие ученые как Хартмут Невен, Питер Шор, Джон Клаузер, Марисса Джустина, Алексей Китаев и другие.
Прекрасно передана историческая перспектива развития квантовой гонки.

Автор очень поэтично описывает рождение квантовой механики, перебегая к литературным эпитетам:
«Представьте себе два камешка, брошенных в безмятежное озеро. Когда камни ударяются о поверхность, они создают концентрическую рябь, которая, сталкиваясь, создает сложные интерференционные узоры. В начале двадцатого века физики, изучающие поведение электронов, обнаружили аналогичные закономерности волнообразной интерференции в субатомном мире. Это открытие привело к моменту кризиса, поскольку при других условиях те же самые электроны вели себя скорее как отдельные точки пространства, называемые частицами. Вскоре, что многие считают самым причудливым научным результатом всех времен, физики поняли, что поведение электрона больше как частицы или волны зависит от того, наблюдает ли кто-то его или нет. Возникла область квантовой механики.»

Полную версию статьи Стивена Витта можно прочитать по ссылке:
https://www.newyorker.com/magazine/2022/12/19/the-world-changing-race-to-develop-the-quantum-computer?fbclid=IwAR2YYYw6FvGvRV1-2eZQt_c1JzBR4KKojJdAhsDe0C1GelY2oKR-a6oHmlg&mibextid=Zxz2cZ
______________

The New Yorker magazine published an interesting engaging popular article by Stephen Witt «The World-Changing Race to Develop the Quantum Computer»:
Such a device could help address climate change and food scarcity, or break the Internet. Will the U.S. or China get there first?

The article deals with issues related to the development of quantum computing in the field of technology. Everyone is wondering which platform will eventually turn into a more promising one. The colorful cast of characters includes Hartmut Neven, Peter Shor, John Clauser, Marissa Giustina, Alexei Kitaev and others.
The historical perspective of the development of the quantum race is perfectly conveyed.

The author very poetically describes the birth of quantum mechanics, using epithets:
«Imagine two pebbles thrown into a placid lake. As the stones hit the surface, they create concentric ripples, which collide to produce complicated patterns of interference. In the early twentieth century, physicists studying the behavior of electrons found similar patterns of wavelike interference in the subatomic world. This discovery led to a moment of crisis, since, under other conditions, those same electrons behaved more like individual points in space, called particles. Soon, in what many consider the most bizarre scientific result of all time, the physicists realized that whether an electron behaved more like a particle or more like a wave depended on whether or not someone was observing it. The field of quantum mechanics was born.»

You can read the full article by Steven Witt here:
https://www.newyorker.com/magazine/2022/12/19/the-world-changing-race-to-develop-the-quantum-computer?fbclid=IwAR2YYYw6FvGvRV1-2eZQt_c1JzBR4KKojJdAhsDe0C1GelY2oKR-a6oHmlg&mibextid=Zxz2cZ

Image credit: The New Yorker.

Проект «TIME 2030» отметил квантовые вычисления в инновациях как область, которая изменит наш мир заголовком «Квантовые вычисления изменят наш мир».

TIME 2030 это:
«Следующее десятилетие, вероятно, определит, останется ли планета пригодной для проживания людей. TIME 2030 — десятилетний проект, который будет отмечать наш прогресс на пути к устойчивому и справедливому миру.»

А сам журнал «TIME» в выпуске за февраль 2023 поместил на обложку номера сверхпроводниковый квантовый компьютер. Интересно, что в феврале 2014 года журнал «TIME» уже размещали фотографию устройства квантового отжига D-Wave с заголовком в статье «Квантовый поиск революционного компьютера».

О том, какие проблемы смогут решить квантовые компьютеры (и какие проблемы они создадут), вы можете прочесть в интересной статье Чарли Кэмпбелла:
https://time.com/6249784/quantum-computing-revolution/?mibextid=Zxz2cZ

______

The «TIME 2030» project highlighted quantum computing in innovation as an area that will change our world with the noscript «Quantum Computing Will Transform Our World».

TIME 2030 is:
«The next decade will likely determine whether the planet will remain fit for human habitation. TIME 2030, a decade long project will be marking our progress towards a sustainable and equitable world.»

And «TIME» magazine in the February 2023 placed a superconducting quantum computer on the cover of the issue. Interestingly, in February 2014, «TIME» magazine already featured a photo of a D-Wave quantum annealing device with the noscript in the article «The Quantum Quest for a Revolutionary Computer»

You can read about what problems quantum computers can solve (and what problems they will create) in an interesting article by Charlie Campbell:
https://time.com/6249784/quantum-computing-revolution/?mibextid=Zxz2cZ

Images credit: TIMES.

Интересный подкаст известного физика-теоретика в области квантовых вычислений Джона Прескилла, в котором они с ведущим Лоуренсом Крауссом обсудили будущее области квантовых вычислений, ее текущее состояние, проблемы и возможности.

«John Preskill: From the Early Universe to the Future of Quantum Computing»:
https://www.youtube.com/watch?app=desktop&v=Y6ilk3WA9Zw&fbclid=IwAR1b9QdgNvlhyYa5Wtl7qhPw-NXNd4XXCvPeiV-lRaCI6YFMt5OWqCSHgsU&mibextid=Zxz2cZ

An interesting podcast by John Preskill, theoretical physicist spearheading the field of Quantum Computing, in which he and host Lawrence Krauss discussed the future of the field, its current state, and challenges and opportunities.

Продолжим эту неделю интересных роликов о квантовых вычислениях и квантовых компьютерах!

Увлекательное видео «Quantum Computers, explained with MKBHD» во всеми любимом формате vlog. В нем вы узнаете что такое квантовый компьютер? Почему важны квантовые вычисления? А еще проведут интересную аналогию с квантовой видеоигрой. А также можно увидеть как же выглядит квантовый компьютер на сверхпроводящей платформе.
_____

Let's continue this week of interesting videos about quantum computing and quantum computers!

Fascinating video "Quantum Computers, explained with MKBHD" in everyone's favorite vlog format. In it you will learn what is a quantum computer? Why is quantum computing important? They will also draw an interesting analogy with a quantum video game. And you can also see what a quantum computer looks like on a superconducting platform.

https://youtu.be/e3fz3dqhN44

«Новый алгоритм закрывает окно квантового превосходства»:
Случайная выборка цепочек (random circuit sampling), популярный метод демонстрации мощности квантовых компьютеров, не масштабируется, если ошибки не проверяются.

С таким заголовком вышла одна обзорная статья в популярном интернет-издании Quanta Magazine.

В статье, размещенной на сервере препринтов arxiv.org (https://arxiv.org/abs/2211.03999), группа ученых сделала важный шаг к доказательству того, что исправление ошибок необходимо для устойчивого квантового преимущества при случайной выборке цепей — специальной задачи, которую Google использовал для демонстрации квантового превосходства. Авторы статьи сделали это, разработав классический алгоритм, который может имитировать эксперименты со случайной выборкой цепей при наличии ошибок.

В экспериментах со случайной выборкой цепей начинают с массива кубитов. Затем случайным образом манипулируют этими кубитами с помощью операций, называемых квантовыми вентилями. Некоторые вентили приводят к запутыванию пар кубитов, то есть они имеют общее квантовое состояние и не могут быть описаны отдельно. Повторяющиеся последовательности квантовых вентилей переводят состояние кубитов в более сложное запутанное состояние.

Чтобы узнать об этом квантовом состоянии необходимо измерить все кубиты в массиве. Это приводит к тому, что их коллективное квантовое состояние схлопывается до случайной строки обычных битов — 0 и 1. Количество возможных результатов быстро растет вместе с количеством кубитов в массиве: с 53 кубитами, как в эксперименте Google, получается почти 10 квадриллионов. И не все строки будут одинаково вероятны. метод случайной выборки цепей означает многократное повторение таких измерений для построения распределения вероятностей, лежащего в основе результатов.

Вопрос о квантовом преимуществе заключается здесь в следующем: сложно ли сымитировать такое распределение вероятностей с помощью классического алгоритма, не использующего никакой запутанности?


В статье Google 2019 года (https://www.nature.com/articles/s41586-019-1666-5) исследователи доказали, что для безошибочных квантовых схем ответ положительный, но в работе не учитывались последствия ошибок, вызванных несовершенными вентилями. Это оставило открытым случай квантового преимущества для метода случайной выборки схемы без исправления ошибок.

Авторы статьи 2022 года вывели классический алгоритм моделирования выборки случайных цепей и доказали, что время его выполнения является полиномиальной функцией времени, необходимого для проведения соответствующего квантового эксперимента. Полученный ими результат устанавливает теоретическую связь между скоростью классического и квантового подходов к случайной выборке цепей.

Результат предполагает, что случайная выборка схем не даст квантового преимущества по строгим стандартам теории вычислительной сложности. В то же время это иллюстрирует тот факт, что полиномиальные алгоритмы, которые теоретики называют эффективными по сложности, на практике не обязательно работают быстро. Новый классический алгоритм становится все медленнее по мере уменьшения частоты ошибок, а при низкой частоте ошибок, достигнутой в экспериментах по квантовому превосходству, он слишком медленный, чтобы его можно было использовать на практике. Без ошибок он вообще ломается, поэтому этот результат не противоречит ничему, что знали исследователи о том, как сложно классически моделировать случайную выборку схем в идеальном, безошибочном случае. Серхио Бойшо, физик, возглавляющий исследование Google в области квантового превосходства, говорит, что считает эту статью «больше хорошим подтверждением случайной выборки цепей, чем чем-то еще».

Однако все исследователи согласны: новый алгоритм подчеркивает, насколько решающей будет коррекция квантовых ошибок для развития квантовых вычислений в будущем.