Исследование Google показало, что современная криптография уязвима перед квантовыми компьютерами

[Ippolitovich]

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

 

Квантовый компьютер с миллионом кубитов пока представляется скорее фантастикой, нежели реальностью. Однако темпы прогресса в этой области требуют уже сейчас начать переход к мерам безопасности, устойчивым к квантовым технологиям. Исследование, проведённое для Google Крейгом Гидни (Craig Gidney) подробно описывает будущие атаки с применением квантовых компьютеров и призывает мировое ИТ-сообщество уже сейчас готовиться к постквантовому миру.

Выводы Гидни являются результатом достижений как в квантовых алгоритмах, так и в методах исправления ошибок. С тех пор как Питер Шор в 1994 году открыл, что квантовые компьютеры могут факторизовать большие числа гораздо эффективнее классических компьютеров, учёные стремились точно определить, какая конфигурация квантового оборудования потребуется для взлома реального шифрования.

 

Последняя работа Гидни основана на недавних алгоритмических прорывах, таких как использование приближенного модульного возведения в степень, которое значительно сокращает количество требуемых логических кубитов. Исследование также включает более плотную модель для хранения кубитов с исправленными ошибками, используя такие методы, как «коды с ярмовой поверхностью» (yoked surface codes) и «выращивание магического состояния» (magic state cultivation) для сокращения требуемых ресурсов.

Гипотетическая машина, располагающая миллионом кубитов, для взлома 2048-битных ключей шифрования RSA должна будет работать непрерывно в течение пяти дней, поддерживать чрезвычайно низкий уровень ошибок и координировать миллиарды логических операций без перерыва. Современные квантовые компьютеры работают только с сотнями или тысячами кубитов, что намного меньше отметки в миллион кубитов. Например, IBM Condor и Google Sycamore с 1121 и 53 кубитами соответственно иллюстрируют текущие возможности квантовых вычислений.

 

Компания D-Wave недавно представила самый мощный в мире квантовый компьютер — систему Advantage2 с более чем 4400 кубитами. Как и все предыдущие системы D-Wave (за исключением компьютеров первых поколений), Advantage2 будет доступна только через облако. Поставки физических систем клиентам начнутся позже — с платформ, насчитывающих не менее 7000 кубитов, время которых ещё не пришло.

 

20 мая компания NVIDIA объявила об открытии Глобального центра исследований и разработок для бизнеса в области искусственного интеллекта на базе квантовых технологий (Global Research and Development Center for Business by Quantum-AI Technology, G-QuAT). На этой площадке размещена система ABCI-Q — крупнейший в мире исследовательский суперкомпьютер, предназначенный для квантовых исследований. Система интегрирована с тремя квантовыми компьютерами.

Крупные компании, разрабатывающие квантовое оборудование, планируют масштабировать свои компьютеры до уровня миллиона кубитов в течение следующего десятилетия. IBM в партнёрстве с Токийским и Чикагским университетами собираются построить квантовый компьютер на 100 000 кубитов к 2033 году. Компания Quantinuum заявила о цели по созданию полностью отказоустойчивого универсального квантового компьютера Apollo к концу 2020-х годов.

 

Последствия появления следующего поколения квантовых компьютеров для информационной безопасности крайне болезненны. RSA и аналогичные криптографические системы лежат в основе большей части защищённых коммуникаций в мире, от банковского дела до цифровых подписей. Результаты исследования Гидни подтверждают срочность перехода на постквантовую криптографию (PQC) — новые стандарты, разработанные для противостояния атакам квантовых компьютеров. В прошлом году Национальный институт стандартов и технологий США опубликовал алгоритмы PQC и рекомендовал поэтапно отказаться от уязвимых систем после 2030 года.

Новые стандарты должны стать важным элементом криптографической защиты данных. Предыдущие стандарты криптографии NIST, разработанные в 1970-х годах, используются практически во всех устройствах, включая интернет-маршрутизаторы, телефоны и ноутбуки. Руководитель группы криптографии NIST Лили Чен (Lily Chen) уверена в необходимости массовой миграции с RSA на новые методы шифрования: «Сегодня криптография с открытым ключом используется везде и во всех устройствах, наша задача — заменить протокол в каждом устройстве, что нелегко».

Поэтому эксперты по безопасности в различных отраслях призывают серьёзно относиться к угрозе, исходящей от квантовых компьютеров. Новые схемы шифрования основаны на понимании сильных и слабых сторон квантовых вычислений, так как квантовые компьютеры превосходят классические лишь в достаточно узком спектре задач. К квантово-устойчивым криптографическим методам относятся:

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

 

Исследование Гидни подчёркивает важность упреждающего планирования. Оно также напоминает о вечном соревновании «снаряда и брони» — по мере развития технологий развиваются и методы их взлома. Улучшения алгоритмов и лучшая интеграция оборудования и программного обеспечения продолжают снижать барьеры для потенциальных злоумышленников.