Новий квантовий алгоритм поки що не може зламати всі системи шифрування, але це не привід для самозаспокоєння.
Група дослідників із Китаю продемонструвала техніку, яка в теорії може зламати найпоширеніші способи забезпечення цифрової конфіденційності за допомогою елементарного квантового комп’ютера.
Дослідники повідомляють, що техніка спрацювала під час невеликої демонстрації, але інші фахівці скептично ставляться до того, що цю процедуру можна масштабувати, щоб перевершити звичайні комп’ютери у вирішенні завдання. Проте вони попереджають, що стаття, опублікована наприкінці минулого місяця в електронному архіві 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 років, яка найбільшою мірою вводить нас в оману, – написав у своєму блозі теоретик квантових обчислень Скотт Ааронсон з Техаського університету в Остіні.
У своєму електронному листі Лонг повідомив, що він і його співавтори планують внести зміни в статтю і перенесуть застереження вище. “Ми вітаємо експертну оцінку і спілкування з ученими всього світу”, – йдеться в заяві.
Навіть якщо техніка, заснована на методі Шнорра, не зламає інтернет, квантові комп’ютери можуть зрештою зробити це, запустивши алгоритм Шора. Дослідники безпеки зайняті розробкою низки альтернативних криптографічних систем, які називають пост-квантовими або квантово-безпечними, які, як вважається, з меншою ймовірністю піддадуться квантовій атаці. Однак у майбутньому дослідники можуть виявити більш досконалі квантові алгоритми, які зможуть перемогти ці системи, що призведе до катастрофічних наслідків.
Довіра до цифрових інфраструктур впаде, – пояснює Моска. – Ми раптово переключимося з управління квантово-безпечною системою на кризове управління. Як не крути, досить неприваблива картина.
