By Джей Лю опубликовано 18 окт 2022
Широко распространено мнение, что квантовые компьютеры не смогут нанести серьезного вреда нашим системам безопасности еще как минимум 15 лет. Ожидается, что именно тогда будут доступны полномасштабные отказоустойчивые квантовые компьютеры, способные запустить алгоритм Шора для взлома RSA за разумное время. Что ж, реальность гораздо мрачнее: реальные угрозы квантовой безопасности гораздо более непосредственны, скорее всего, в течение пяти лет.
Вы можете спросить: «Правда? Как же так?"
Эти краткосрочные угрозы безопасности будут исходить от эвристических алгоритмов, работающих на подверженных ошибкам квантовых устройствах эпохи NISQ, в которой мы уже живем сегодня.
Используя алгоритм Шора, для факторизации 2048-битного числа RSA требуется 100,000 10 отказоустойчивых кубитов, работающих в течение 20 дней, или 8 млн кубитов NISQ в течение XNUMX часов. Поскольку у нас не будет таких крупномасштабных квантовых компьютеров по крайней мере десять лет, мы можем почувствовать, что у нас есть много времени, чтобы подготовиться.
Но используя сегодняшние устройства NISQ, мы в Zapata Computing придумали эвристический алгоритм под названием Вариационный квантовый факторинг (VQF, запатентовано), который, по нашим оценкам, может вычислить 2048-битное число RSA примерно с 6,000 кубитов NISQ в течение одного часа. Основываясь на опубликованных дорожных картах продуктов ведущих компаний, занимающихся квантовыми компьютерами, ожидается, что квантовые компьютеры NISQ такого масштаба будут доступны в течение пяти лет.
Думаю об этом. Угроза квантовой безопасности намного более непосредственна, чем кажется большинству.
Что ж, вы можете задаться вопросом: «Что такое эвристический алгоритм и почему в данном случае он намного мощнее, чем алгоритм Шора, когда дело доходит до взлома номера RSA?»
Пионер вычислительной сложности и обладатель премии Тьюринга Стивен Кук дал этому хорошее определение:
" эвристический алгоритм это тот, который предназначен для решения проблемы более быстрым и эффективным способом, чем традиционные методы, жертвуя оптимальностью, точностью, точностью или полнотой ради скорости».
Другими словами, эвристический алгоритм не является математически полным или доказанным в теории, но он работает на практике. Хорошо известным примером эвристического алгоритма являются нейронные сети, которые доказали свою исключительную эффективность в таких приложениях, как распознавание лиц, несмотря на отсутствие математических доказательств того, что он должен работать. Более того, он становится все более точным и мощным по мере разработки лучших сверточных нейронных сетей.
Наш алгоритм VQF является еще одним примером. В отличие от алгоритма Шора, это гибридный алгоритм, использующий как квантовые, так и классические компьютеры. В частности, он отображает проблему факторинга в задачу комбинаторной оптимизации, использует классические компьютеры для предварительной обработки и применяет хорошо известный алгоритм квантовой приближенной оптимизации (QAOA). Этот подход значительно сократил количество кубитов, необходимых для факторизации большого числа.
Угроза NISQ намного ближе, чем угроза PQC
В то время как большинство усилий в академических кругах, стандартизированных органах и фирмах по безопасности сосредоточены на смягчении угроз безопасности эпохи постквантовой криптографии (PQC), через десять или более лет ожидаемые угрозы от алгоритмов Шора работают в полном масштабе, отказоустойчивые квантовые технологии компьютеры, алгоритм VQF показал осуществимость краткосрочных угроз безопасности от эвристических алгоритмов, работающих на квантовых компьютерах в эпоху NISQ, в которой мы уже живем сегодня.
Мы внимательно изучаем этот вопрос и разговариваем с крупными предприятиями, правительствами и организациями. Это угроза квантовой кибербезопасности, которая их больше всего беспокоит.
С нашей глубокой лабораторией квантовых ученых и нашим Программная платформа Orquestra® Работая на квантовых компьютерах, мы разработали набор инструментов и услуг, которые помогут вам лучше подготовиться к угрозам безопасности эпохи NISQ и позже, включая исследования, оценку, тестирование, оценку и проверку.
Давайте начнем сегодня.
Джей Лю, вице-президент по продуктам Zapata Computing
