Исследователи доказали, что безопасное квантовое шифрование возможно в мире, где нет сложных проблем.
Допустим, вы хотите отправить личное сообщение, провести тайное голосование или надёжно подписать документ. Если вы выполняете любую из этих задач на компьютере, то для обеспечения безопасности ваших данных вы полагаетесь на шифрование. Это шифрование должно выдерживать атаки взломщиков, работающих на своих собственных компьютерах, поэтому современные методы шифрования основаны на предположениях о том, какие математические задачи компьютерам сложно решать.
Но когда в 1980-х годах криптографы заложили математические основы этого подхода к информационной безопасности, несколько исследователей обнаружили, что вычислительная сложность — не единственный способ защитить секреты. Оказалось, что квантовая теория, изначально разработанная для понимания физики атомов, глубоко связана с информацией и криптографией. Исследователи нашли способ обеспечить безопасность нескольких конкретных криптографических задач непосредственно на основе законов физики. Но эти задачи были странными исключениями — для всех остальных, казалось, не существовало альтернативы классическому вычислительному подходу.
К концу тысячелетия исследователи квантовой криптографии думали, что на этом история закончилась. Но всего за несколько последних лет в этой области произошёл ещё один сейсмический сдвиг.
«Произошла перестройка того, что мы считаем возможным в квантовой криптографии», — говорит Генри Юэнь, теоретик квантовой информации из Колумбийского университета.
В ряде недавних работ исследователи показали, что большинство криптографических задач могут быть безопасно решены даже в гипотетических мирах, где практически все вычисления просты. Всё, что имеет значение, — это сложность особой вычислительной задачи, касающейся самой квантовой теории.
«Необходимые ограничения могут быть намного, намного, намного слабее», — говорит Ферми Ма, квантовый криптограф из Института теории вычислений Саймонса в Беркли, Калифорния. «Это даёт нам новое представление о вычислительной сложности как таковой».
Это сообщение самоуничтожится
История началась в конце 1960-х годов, когда аспирант физического факультета по имени Стивен Визнер задумался о разрушительном характере измерений в квантовой теории. Измерьте любую систему, управляемую правилами квантовой физики, и вы измените квантовое состояние, которое математически описывает её конфигурацию. Это нарушение квантовых измерений было помехой для большинства физиков. Визнер, придерживавшийся неортодоксального информационно-центричного взгляда на квантовую теорию, задался вопросом, можно ли сделать её полезной. Возможно, этот эффект могл бы служить формой встроенной защиты конфиденциальных данных от взлома.
Но идеи Визнера слишком сильно опережали своё время, и он покинул академические круги после окончания аспирантуры. К счастью, он успел обсудить свои идеи со своим другом и коллегой-физиком Чарльзом Беннетом, который в течение десяти лет безуспешно пытался заинтересовать этой темой других. Наконец, в 1979 году Беннетт встретил учёного-компьютерщика Жиля Брассара, плавая у берегов Пуэрто-Рико, куда он прибыл на конференцию. Вместе они написали новаторскую работу, в которой описали новый подход к решению важной криптографической задачи. Их протокол был основан на квантовом нарушении измерений и не требовал никаких предположений о сложности тех или иных вычислительных задач.
«Сама природа квантовой информации кажется в какой-то степени криптографической», — говорит Ма.
Прорыв Беннетта и Брассарда вселил в исследователей оптимизм, что подобные квантовые трюки могут обеспечить идеальную безопасность и для других криптографических задач. Исследователи сосредоточились в основном на задаче под названием «битовая схема обязательств» (БСО), которая полезна сама по себе, а также является ключевым компонентом большинства продвинутых криптографических протоколов.
Чтобы понять основную идею, лежащую в основе битовой схемы обязательств, представьте себе игру для двух игроков, в которой вы должны тайно принять решение, которое впоследствии будет раскрыто. Один из способов сделать это — записать решение на листке бумаги и положить его в запечатанный конверт. Таким образом, вы не сможете изменить своё решение позже, а ваш соперник не сможет преждевременно подсмотреть результат.
А теперь представьте, что вы играете в ту же игру онлайн. Чтобы сделать обман невозможным, вам нужно запечатать решение в своего рода цифровой конверт, который ни один из игроков не сможет открыть в одиночку. Вот тут-то и приходит на помощь криптография. В 1981 году учёный-первопроходец Мануэль Блюм создал первый протокол битовых обязательств — способ построения эффективно невзламываемых конвертов, состоящих из сложных вычислительных задач.
Но насколько сложна эта сложность? Исследователи в области теории сложности вычислений изучают множество различных видов трудных задач, и не все из них полезны для криптографов. Битовые обязательства и все другие криптографические протоколы опираются на задачи из класса, который теоретики сложности называют «NP», чья определяющая особенность заключается в лёгкости проверки того, является ли решение кандидата правильным.
К сожалению, исследователям не удалось доказать, что ни одна из NP-задач не является по-настоящему сложной. Возможно, существует некая хитрая процедура или алгоритм для решения даже тех задач, которые кажутся самыми сложными. Если это так, то вся классическая криптография будет сломана.
Такие соображения оживили поиски квантовых гарантий безопасности. Но в 1997 году в двух работах было доказано, что схемы битовых обязательств никогда не смогут быть полностью безопасными, если они будут основаны исключительно на законах квантовой физики. Из этих работ следовало, что почти для всех криптографических задач необходима некоторая вычислительная стойкость.
Это было последнее слово о теоретических основах квантовых битовых схем обязательств, имевшее вес в течение почти 25 лет. Затем, в 2021 году, статья аспиранта Уильяма Кречмера заставила исследователей столкнуться с вопросом, который никто и не думал задавать. Допустим, вычислительная стойкость действительно необходима для битовых схем обязательств и большинства других форм криптографии — но какого именно рода стойкость?
Ответ оказался более странным, чем кто-либо предполагал.
Консультация с оракулами
Статья 2021 года появилась в результате попыток Кречмера понять конкретную версию проблемы, которая концептуально звучит просто: насколько трудно различить, или дискриминировать два квантовых состояния, которые выглядят поверхностно похожими? Кречмер, который сейчас является постдокторским исследователем в Институте Саймонса, изначально заинтересовался этой проблемой по причинам, не имеющим никакого отношения к БСО.
«Криптография даже не попала в поле моего зрения», — говорит он.
Проблема дискриминации была интересна отчасти потому, что было непонятно, как описать её на привычном математическом языке». Теоретики сложности традиционно изучают проблемы с различными возможными входами, представленными строками битов, или 0 и 1. Например, в задаче разложения больших чисел на простые множители эта строка представляет собой число, которое нужно разложить.
Даже после того, как исследователи начали изучать возможности использования квантовой физики для вычислений, они продолжали фокусироваться на таких проблемах с «классическим входом». Типичные квантовые алгоритмы начинают с обычной классической битовой строки, а затем обрабатывают её с помощью квантовых хитростей. Но в задачах с «квантовым входом», подобных задаче Кречмера, входными данными являются не битовые строки, а квантовые состояния, которые так же легко нарушаются при вычислениях, как и при измерениях.
«Язык, на котором мы описывали квантовые вычисления в традиционной теории сложности, не позволяет напрямую говорить об этих проблемах», — говорит Юэнь.
Сначала Кречмер думал, что ему просто нужно перевести проблему на более стандартный язык, но не мог понять, как это сделать. Поэтому он поступил так, как часто поступают теоретики сложности, когда находятся в отчаянии: он обратился к оракулу.
В теории сложности термин «оракул» относится к гипотетическому устройству, которое может мгновенно решить определённую задачу. Компьютер, имеющий доступ к оракулу, может решить другие задачи более легко, обращаясь к последнему на промежуточном шаге алгоритма. Конечно, в реальном мире оракулов не существуют, но их изучение помогает теоретикам сложности понять взаимосвязь между уровнями сложности различных задач.
Кречмер задался вопросом, какой оракул может облегчить различение двух квантовых состояний – это так называемая проблема различения квантовых состояний. Он решил начать со специального оракула, который увеличил бы мощность обычных квантовых алгоритмов, использующих квантовые трюки для решения задач с классическими битовыми строками на входе. Такие алгоритмы могут решать некоторые слишком сложные для классических алгоритмов задачи, например, факторизацию больших чисел, но они не всесильны — многие другие проблемы им не под силу.
Доступ к оракулу Кречмера позволил бы таким алгоритмам решать некоторые задачи с классическим входом, слишком трудные для настоящих квантовых компьютеров. Кретчмер полагал, что это будет излишним, но, к своему удивлению, он доказал, что проблема дискриминации состояний всё ещё может поставить в тупик эти усовершенствованные квантовые алгоритмы.
«Я был действительно очарован статьёй Уильяма», — сказал Луовен Цянь, аспирант, изучающий криптографию в Бостонском университете. «Я действительно думал, что она должна быть неверной, потому что она настолько контринтуитивна».
Цянь, Юэнь и другие вскоре доказали, что если проблема дискриминации состояний Кретчмера действительно трудна, то безопасные схемы квантовых БСО будут возможны. Это, в свою очередь, означало бы безопасность для множества более продвинутых криптографических протоколов. Сфера применения квантовой криптографии оказалась гораздо шире, чем предполагали исследователи 1990-х годов, и всё сводилось к сложности одной проблемы.
Насколько сложным это может быть?
Результат Кретчмер получил, но с одной большой оговоркой — чтобы доказательство работало, ему пришлось полагаться на необычного оракула, к которому могли обращаться только квантовые алгоритмы. Возможно, более привычный оракул упростил бы проблему дискриминации состояний, а значит, сделал бы невозможной безопасную квантовую передачу битов? В 2022 году Кречмер и Цянь начали работать вместе, чтобы выяснить, что они могут сказать об оракуле, понятном всем: таком, который мог бы мгновенно решить любую NP-задачу. В мире, где есть такие оракулы, вся классическая криптография была бы невозможна.
Вскоре Кречмер понял, что проблема дискриминации состояний математически связана с внешне отличающейся проблемой в квантовой теории сложности, и заручился помощью двух экспертов в этой области, теоретиков сложности Авишая Таля и Макранда Синхи. «Уильям был в роли менеджера, а мы — подрядчиками», — говорит Таль.
Работая вместе, четверо исследователей быстро доказали, что проблема дискриминации состояний Кречмера может оказаться неразрешимой даже для компьютеров, способных обращаться к этому NP-оракулу. Это означает, что практически вся квантовая криптография может оставаться безопасной, даже если все проблемы, лежащие в основе классической криптографии, окажутся простыми. Классическая криптография и квантовая криптография все больше казались двумя совершенно разными мирами.
Результат привлёк внимание Ма, и он начал размышлять, как далеко он может продвинуть начатое Кретчмером направление работы. Может ли квантовая криптография оставаться безопасной даже с более необычными оракулами — такими, которые могут мгновенно решать вычислительные проблемы, гораздо более сложные, чем проблемы NP? «Проблемы NP — это не самые сложные классические проблемы, о которых можно вспомнить», — говорит Дакшита Хурана, криптограф из Иллинойского университета в Урбане-Шампейне. «Есть задачи и посложнее».
Вместе с Алексом Ломбарди, криптографом из Принстонского университета, и Джоном Райтом, исследователем квантовых вычислений из Калифорнийского университета в Беркли, Ма начал «мозговой штурм», как лучше подойти к этому вопросу. «Это было так увлекательно и так захватывающе, что мой интерес к задаче немедленно проснулся», — говорит Райт.
Поразмыслив над вопросом некоторое время и ничего не добившись, Ма предложил им рассмотреть самый крайний случай: оракул, который мог бы мгновенно решить любую вычислительную задачу с классическими входными данными. Сюда вошли бы все проблемы, которые традиционно изучают теоретики сложности, даже те, которые, как известно, неразрешимы в реальном мире.
«Мне это показалось немного безумным», — говорит Ломбарди.
Но вопрос оказался удивительно плодотворным. Проработав над ним почти год, они наконец опубликовали поразительный результат. Ни один алгоритм, которому разрешено обратиться к этому всемогущему оракулу ровно один раз, не сможет различить два квантовых состояния, что необходимо для подрыва схемы квантового обязательства по передаче битов.
Ограничение алгоритмов одним запросом — не столь серьёзное ограничение, как может показаться, поскольку квантовые алгоритмы могут эффективно просить оракула решить несколько задач одновременно, используя явление, называемое суперпозицией. Алгоритмы, которые могут делать несколько запросов последовательно, могут быть более мощными, потому что они могут использовать ответы оракула на предыдущие запросы, чтобы решить, что спросить в следующий раз. Вопрос о том, являются ли эти алгоритмы столь же ограниченными, остаётся открытым.
Статья Ма, Ломбарди и Райта важна и по другой причине. Пока трое исследователей бились над своей проблемой, они поняли, что она тесно связана с крупной открытой проблемой, поставленной 16 годами ранее теоретиком сложности Скоттом Ааронсоном и математиком Грегом Купербергом, о сложности преобразования одного квантового состояния в другое. Новая работа стала первым значительным шагом к решению этого вопроса.
«Это очень сильный результат, а также очень удивительный», — сказал Томоюки Моримаэ, исследователь квантовой криптографии в Институте теоретической физики Юкавы в Киото.
Ряд недавних результатов свидетельствует о том, что безобидно звучащая проблема различения двух квантовых состояний не просто трудна, а практически немыслимо трудна — далеко за пределами досягаемости обычных квантовых алгоритмов и даже более экзотических. Это хорошая новость для криптографии, но она также имеет более широкие последствия для вычислительных задач, входными данными которых являются квантовые состояния. Традиционная теория сложности, похоже, не в состоянии решить эти проблемы. Для их истинного понимания может потребоваться радикально новая теоретическая база.
«Чувствуется, что в поведении квантовой информации есть что-то принципиально иное», — говорит Андреа Коладанджело, квантовый криптограф из Университета Вашингтона. «У неё явно есть связи, выходящие за рамки криптографии».
