Нет, конец света не наступает, но День Q наступит, и это не будет таким дорогим как предполагалось.
Создание квантового компьютера полезного масштаба, который сможет взломать одну из самых важных криптосистем — эллиптические кривые — не требует почти столько ресурсов, сколько предполагалось год или два назад, согласно выводам двух независимых белых книг. В одной из них исследователи продемонстрировали использование нейтральных атомов в качестве перестраиваемых кубитов с свободным доступом друг к другу. Они показали, что этот подход позволит квантовому компьютеру взломать 256-битное шифрование эллиптических кривых (ECC) за 10 дней при использовании в 100 раз меньше накладных расходов, чем предполагалось ранее. Во второй статье исследователи Google продемонстрировали, как можно взломать ECC, защищающий блокчейны биткойна и других криптовалют менее чем за девять минут при достижении 20-кратного снижения использования ресурсов.
Вместе взятые, эти статьи являются последним признаком того, что криптографически релевантные квантовые вычисления (CRQC) в полезном масштабе достигают значительного прогресса. Прогресс во многом обусловлен новыми квантовыми архитектурами, разработанными физиками и компьютерными учеными в попытке создать квантовые компьютеры, которые работают корректно даже при наличии ошибок, возникающих всякий раз, когда кубиты — квантовый аналог классических битов — взаимодействуют с окружающей средой. Другими ключевыми факторами являются все более эффективные алгоритмы для усиления алгоритма Шора, серии уравнений 1994 года, доказывающие, что квантовые вычисления могли бы взломать криптосистемы ECC и RSA за полиномиальное время, в частности кубическое время, намного быстрее, чем экспоненциальное время, обеспечиваемое современными классическими компьютерами.
Ни одна из статей не прошла рецензирование.
"Научное сообщество продолжает добиваться неуклонного прогресса как в физических кубитах, так и в квантовых алгоритмах, необходимых для реализации эффективного и практического CRQC", — сказал Брайан ЛаМаккиа, инженер по криптографии, который руководил переходом Microsoft на постквантовую криптографию с 2015 по 2022 год и сейчас работает в Farcaster Consulting Group. "Я не думаю, что любая из этих статей дает нам новую конкретную дату, когда у нас будет практический CRQC (который, конечно, никогда не был), но обе они предоставляют доказательства того, что мы продолжаем идти по пути к реализуемому CRQC и прогресс в направлении этой цели не замедляется."
Ловля атомов в "оптические пинцеты"
Статья, получившая наибольшее внимание, использует относительно новый подход к созданию отказоустойчивых квантовых вычислений (FTQC), который может сократить количество требуемых физических кубитов для взлома ECC в 100 раз. В отличие от более распространенных подходов, основанных на сверхпроводниках, исследователи построили физические кубиты из нейтральных атомов. Используя лазеры для охлаждения атомов, процесс улавливает отдельные атомы в плотно сфокусированные световые пучки, известные как "оптические пинцеты". Каждый пинцет захватывает один атом. Используя оптическое мультиплексирование, исследователи могут создавать большие массивы из этих захваченных атомов.
Преимущество этого подхода заключается в том, что все физические кубиты могут взаимодействовать со всеми другими физическими кубитами. Эти "нелокальные" коммуникации представляют собой значительный отход от взаимодействия кубитов в сверхпроводящих подходах, где кубиты расположены на двумерной сетке и могут взаимодействовать только с четырьмя непосредственно соседними кубитами. Способность кубитов взаимодействовать с очень удаленными кубитами делает коррекцию ошибок значительно более эффективной, поскольку нелокальная коммуникация позволяет значительно увеличить количество и тщательность проверок отказоустойчивости.
В результате этого статья исследователей — озаглавленная Алгоритм Шора возможен с использованием всего 10 000 перестраиваемых атомных кубитов — говорит, что квантовый компьютер нуждается в менее чем 30 000 физических кубитов для взлома ECC-256 за 10 дней, что на порядки более эффективно, чем предыдущие оценки. Отдельная исследовательская группа в прошлом году показала, что они могут построить массивы ловушек для нейтральных атомов, превышающие 6 000 кубитов. Вместе с достижениями в крупномасштабных квантовых операциях с высокой точностью, нейтральные атомы имеют потенциал для проведения отказоустойчивых квантовых вычислений.
"Хотя необходима значительная работа для интеграции этих достижений в полный аппарат и масштабирования размеров системы до требуемых уровней, наш анализ показывает, что надлежащим образом разработанные архитектуры на основе нейтральных атомов могут поддерживать криптографически релевантные реализации алгоритма Шора", — написали исследователи. "Этот вывод подчеркивает важность постоянных усилий по переходу широко развернутых криптографических систем на постквантовые стандарты, разработанные для защиты от квантовых атак."
Google смотрит в сторону крипто-фанатов
Отдельная статья, опубликованная исследователями Google, также показывает прогресс в использовании алгоритма Шора для взлома ECC-256, в частности над secp256k1, эллиптической кривой, которая является основой криптографии биткойна и других блокчейнов. Исследователи сказали, что они разработали улучшения алгоритма Шора, которые позволяют взломать открытый ключ адреса биткойна менее чем за 10 минут с использованием ресурсов в 20 раз меньше, чем те, которые были достигнуты в исследованиях 2003 года.
В частности, Google сказал, что скомпилировал два квантовых схемы, решающих задачу дискретного логарифма эллиптической кривой. Один требует менее 1200 логических кубитов и 90 миллионов вентилей Тоффоли, а другой нуждается в менее 1450 логических кубитах и 70 миллионах вентилях Тоффоли. Логический кубит — это отказоустойчивый кубит, закодированный с использованием сотен (или тысяч) физических кубитов. Исследователи оценивают, что их машина требует примерно 500 000 физических кубитов, половину того, что та же команда оценила в июне прошлого года как необходимую для взлома 2048-битного RSA, который имеет намного больший размер ключа. Вентиль Тоффоли — это ресурсоемкая операция, которая является ключевым фактором в определении времени, необходимого для завершения алгоритма.
В ходе, который привлекает внимание в кругах безопасности, Google не раскрывает алгоритмические улучшения, которые делают это достижение возможным. Вместо этого исследователи выпустили доказательство с нулевым разглашением, которое математически доказывает существование алгоритмического улучшения, не раскрывая его.
"Нарастающий риск того, что детальные криптоаналитические схемы могут быть использованы враждебными субъектами, требует изменения практики раскрытия информации", — объяснили авторы. "Соответственно, мы считаем, что это уже вопрос общественной ответственности поделиться уточненными оценками ресурсов при сохранении в секрете точной механики базовых атак." Исследователи, которые сказали, что консультировались с правительством США при формировании новой политики, далее сказали, что "прогресс в квантовых вычислениях достиг этапа, на котором благоразумно прекратить публикацию деталей улучшенной квантовой криптоанализа, чтобы избежать неправомерного использования."
Это движение, недавно предложенное влиятельным исследователем Скоттом Ааронсоном, является полным разворотом от строгой политики 90-дневного раскрытия, которую Google Project Zero начала два десятилетия назад и которая стала принятой нормой, определяющей исследования безопасности еще дольше. Другие исследователи уже критикуют отсутствие деталей.
"Я думаю, что это alarmist заявлять о немедленном риске безопасности из алгоритма, который требует компьютера, который не существует," сказал Мэтт Грин, профессор Университета Джона Хопкинса, изучающий криптографию. "Учитывая, что ставки здесь так низки (по той же причине) я бы классифицировал это как менее вредоносное и более гипотетическое. Я думаю, что это скорее трюк с PR, чем серьезная проблема, которую имеет кто-то."
Google также сталкивается с критикой за сосредоточение на вреде, который CRQC наносит криптовалютам — одержимость громких влиятельных лиц и текущей администрации Белого дома — вместо реализаций TLS, подписей DocuSign, цифровых сертификатов или любого другого количества более общих приложений, которые влияют на большие группы населения.
"Хотя CRQC действительно представляют угрозу для технологий на основе блокчейна, основанных на классических алгоритмах ECC, они являются только одной из многих систем в нашем современном мире, которые нуждаются в быстром переходе на PQC," сказал ЛаМаккиа, имея в виду постквантовую криптографию. "Особенно при чтении некоторых из предложенных политик в конце белой книги, я просто поражен тем, что Google сосредоточена на нормативно-правовых базах для решения проблем, которые кажутся уникальными для криптовалютного пространства (например, спасение цифровых активов) и не на общей угрозе, которую CRQC представляет для всех наших систем, которые используют криптографию открытого ключа."