Группа исследователей из Китая продемонстрировала технику, которая в теории может взломать самые распространенные способы обеспечения цифровой конфиденциальности с помощью элементарного квантового компьютера.
Исследователи сообщают, что техника сработала в ходе небольшой демонстрации, но другие специалисты скептически относятся к тому, что эту процедуру можно масштабировать, чтобы превзойти обычные компьютеры в решении задачи. Тем не менее они предупреждают, что статья, опубликованная в конце прошлого месяца в электронном архиве arXiv, напоминает нам об уязвимости личных данных в интернете.
Известно, что квантовые компьютеры представляют собой потенциальную угрозу для существующих систем шифрования, однако эта технология все еще находится в зачаточном состоянии. Как правило, исследователи прогнозируют, что пройдет много лет, прежде чем квантовые компьютеры смогут взламывать криптографические ключи (строки символов, используемые в алгоритме шифрования для защиты данных) быстрее, чем обычные компьютеры.
В 1990-х годах исследователи поняли, что квантовые компьютеры могут использовать особенности физики для выполнения задач, которые кажутся недоступными для «классических» компьютеров. Питер Шор, математик, работающий сейчас в Массачусетском технологическом институте в Кембридже, в 1994 году показал, как можно применить явления квантовой суперпозиции и квантовой интерференции, чтобы разложить натуральные числа на простые, которые не могут быть разделены без остатка.
Алгоритм Шора позволил бы квантовому компьютеру экспоненциально быстрее, чем классическому, взломать систему шифрования, основанную на больших простых числах (так называемую систему Ривест-Шамир-Адлеман, или RSA, по инициалам ее изобретателей), а также некоторые другие популярные методы криптографии, которые в настоящее время защищают конфиденциальность и безопасность в интернете. Но для этого нужен квантовый компьютер с гораздо большей мощностью, чем имеющиеся прототипы. Вычислительная мощность квантового компьютера измеряется в квантовых битах, или кубитах. Исследователи говорят, что для взлома RSA может потребоваться миллион или более кубитов. Самый большой квантовый компьютер на сегодня (Osprey, о создании которого IBM объявила в ноябре) имеет 433 кубита.
Новый подход
Шицзе Вэй из Пекинской академии квантовых информационных наук и его сотрудники пошли другим путем, чтобы обойти RSA, основываясь не на алгоритме Шора, а на схеме Шнорра, процессе факторизации натуральных чисел, разработанном математиком Клаусом Шнорром в Университете Гете во Франкфурте, Германия, в 1990-х годах. Схема Шнорра была разработана для работы на классическом компьютере, но команда Вэя реализовала часть процесса на квантовом компьютере, используя процедуру, называемую алгоритмом квантовой приближенной оптимизации, или QAOA.
В статье, которая пока не прошла рецензирование, авторы утверждают, что их алгоритм может взломать надежные ключи RSA (числа с более чем 600 десятичными цифрами) используя всего 372 кубита. Гуйлу Лонг, физик из Университета Цинхуа в Пекине, в письме в Nature от имени своей команды предупредил, что одного количества кубитов недостаточно, и что существующие квантовые машины все еще слишком подвержены ошибкам, чтобы успешно выполнять такие большие вычисления: «простое увеличение числа кубитов без снижения частоты ошибок не поможет».
Профессор Научно-технического университета Китая в Хэфэе Чао-Янг Лу, разрабатывающий квантовые компьютеры, считает, что для запуска алгоритма QAOA на таком маломощном процессоре потребуется, чтобы каждый из 372 кубитов работал без ошибок 99,9999% времени. Современные кубиты не обеспечивают точность 99,9%.
Команда продемонстрировала эту технику на квантовом компьютере с 10 кубитами для вычисления 15-значного числа 261,980,999,226,229 (оно делится на два простых: 15,538,213 × 16,860,433). Исследователи говорят, что это самое большое число, которое на сегодняшний день было вычислено с помощью квантового компьютера, хотя оно намного меньше, чем ключи шифрования, используемые современными веб-браузерами.
Спорное мнение
Проблема в том, что никто не знает, делает ли QAOA факторизацию больших чисел быстрее, чем просто запуск классического алгоритма Шнорра на ноутбуке. «Следует отметить, что квантовое ускорение алгоритма неясно», — пишут авторы. Другими словами, хотя алгоритм Шора гарантированно эффективно взломает шифр, когда (и если) появится достаточно большой квантовый компьютер, метод, основанный на оптимизации, может работать на машине гораздо меньшей мощности, но при этом есть вероятность, что задача никогда не будет завершена.
Мишель Моска, математик из Университета Ватерлоо в Канаде, также отмечает, что QAOA — не первый известный квантовый алгоритм, способный факторизовать целые числа, используя небольшое количество кубитов. Он и его команда уже описали такой алгоритм в 2017 году.
Другие исследователи высказывают недовольство тем, что, хотя последняя работа может быть достоверной, предостережение относительно скорости появляется только в самом конце. «Это одна из работ о квантовых вычислениях за последние 25 лет, которая в наибольшей степени вводит нас в заблуждение», — написал в своем блоге теоретик квантовых вычислений Скотт Ааронсон из Техасского университета в Остине.
В своем электронном письме Лонг сообщил, что он и его соавторы планируют внести изменения в статью и перенесут оговорку выше. «Мы приветствуем экспертную оценку и общение с учеными всего мира», — говорится в заявлении.
Даже если техника, основанная на методе Шнорра, не взломает интернет, квантовые компьютеры могут в конечном итоге сделать это, запустив алгоритм Шора. Исследователи безопасности заняты разработкой ряда альтернативных криптографических систем, называемых пост-квантовыми или квантово-безопасными, которые, как считается, с меньшей вероятностью поддадутся квантовой атаке. Однако в будущем исследователи могут обнаружить более совершенные квантовые алгоритмы, которые смогут победить эти системы, что приведет к катастрофическим последствиям.
«Доверие к цифровым инфраструктурам рухнет, — объясняет Моска. — Мы внезапно переключимся с управления квантово-безопасной системой на кризисное управление. Как ни крути, довольно неприглядная картина».