Криптографы открыли новую основу для квантовой секретности.

Исследователи доказали, что надежное квантовое шифрование возможно в мире, где нет сложных задач. Комментарий Сохранить статью Прочитать позже

Введение

Допустим, вы хотите отправить личное сообщение, проголосовать тайно или подписать документ в безопасном режиме. Выполняя любую из этих задач на компьютере, вы полагаетесь на шифрование для защиты своих данных. Это шифрование должно выдерживать атаки криптографов с использованием собственных компьютеров, поэтому современные методы шифрования основаны на предположениях о том, какие математические задачи трудно решить компьютерам.

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

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

«Произошло переосмысление наших представлений о возможностях квантовой криптографии», — сказал Генри Юэн, теоретик квантовой информации из Колумбийского университета.

В ряде недавних работ исследователи показали, что большинство криптографических задач можно безопасно решить даже в гипотетических мирах, где практически все вычисления просты. Всё, что имеет значение, — это сложность конкретной вычислительной задачи, связанной с самой квантовой теорией.

«Необходимые допущения могут быть намного, намного, намного слабее», — сказал Ферми Ма, квантовый криптограф из Института теории вычислений имени Саймонса в Беркли, штат Калифорния. «Это дает нам новое понимание самой вычислительной сложности».

Это сообщение самоуничтожится.

История начинается в конце 1960-х годов, когда аспирант-физик Стивен Виснер начал размышлять о разрушительной природе измерений в квантовой теории. Измерив любую систему, подчиняющуюся правилам квантовой физики, вы измените квантовое состояние, которое математически описывает её конфигурацию. Это квантовое возмущение измерений было препятствием для большинства физиков. Виснер, придерживавшийся неортодоксального информационно-центричного взгляда на квантовую теорию, задался вопросом, можно ли использовать её в полезных целях. Возможно, она могла бы служить своего рода встроенной защитой от несанкционированного доступа к конфиденциальным данным.

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

«Сама природа квантовой информации кажется в некоторой степени криптографической», — сказал Ма.

Прорыв Беннета и Брассара вселил в исследователей оптимизм, что аналогичные квантовые методы могут обеспечить идеальную безопасность для других криптографических задач. Исследователи сосредоточились в основном на задаче, называемой «фиксация бита», которая полезна сама по себе и является ключевым компонентом большинства передовых криптографических протоколов.

Чтобы понять основную идею, лежащую в основе фиксации битов, представьте себе игру для двух игроков, в которой вы должны принять секретное решение, которое впоследствии будет раскрыто. Один из способов сделать это — записать решение на листке бумаги и положить его в запечатанный конверт. Таким образом, вы не сможете изменить свое решение позже, а ваш противник не сможет преждевременно подсмотреть результат.

Теперь представьте, что вы играете в ту же игру онлайн. Чтобы сделать мошенничество невозможным, вам нужно запечатать решение в своего рода цифровой конверт, который ни один из игроков не сможет открыть самостоятельно. Вот тут-то и пригодится криптография. В 1981 году пионер компьютерных наук Мануэль Блюм разработал первый протокол подтверждения битов — способ создания практически невзламываемых конвертов из сложных вычислительных задач.

Но насколько сложны сложные задачи? Исследователи в области теории вычислительной сложности изучают множество различных типов сложных задач, и не все из них полезны для криптографов. Задачи фиксации битов и все другие криптографические протоколы основаны на задачах класса, который теоретики сложности называют «NP», определяющей особенностью которых является простота проверки правильности предлагаемого решения.

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

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

На протяжении почти 25 лет это было последним словом в теоретических основах квантовых битовых обязательств. Затем, в 2021 году, статья аспиранта Уильяма Кречмера побудила исследователей столкнуться с вопросом, который никто не задавал. Вычислительная сложность, очевидно, необходима для битовых обязательств и большинства других форм криптографии, но какой именно вид сложности?

Ответ оказался гораздо более странным, чем кто-либо предполагал.

Консультирующие оракулы

Статья 2021 года появилась в результате попыток Кречмера понять конкретную версию проблемы, которая на первый взгляд кажется простой: насколько сложно различить или отличить два квантовых состояния, которые внешне похожи? Кречмер, который сейчас является постдокторантом в Институте Саймонса, изначально заинтересовался этой проблемой по причинам, не имеющим ничего общего с фиксацией битов.

«Криптография даже не входила в сферу моих интересов», — сказал он.

Проблема различения была интересна отчасти потому, что даже не было ясно, как описать её, используя привычный математический язык. Теоретики сложности традиционно изучают задачи с различными возможными входными данными, представленными строками битов, или нулями и единицами. Например, в задаче разложения больших чисел на простые множители эта строка представляет собой число, которое нужно разложить на множители.

Даже после того, как исследователи начали изучать возможности применения квантовой физики в вычислениях, они продолжали фокусироваться на таких задачах с «классическими входными данными». Типичные квантовые алгоритмы начинаются с обычной классической битовой строки, а затем обрабатывают её с помощью квантовых уловок. Но в задачах с «квантовыми входными данными», подобных задаче Кречмера, входными данными являются не битовые строки, а квантовые состояния, которые так же легко нарушаются вычислениями, как и измерениями.

«Язык, с помощью которого мы описываем квантовые вычисления в традиционной теории сложности, не позволяет напрямую говорить об этих проблемах», — сказал Юэн.

Сначала Кречмер думал, что ему просто нужно перевести проблему на более стандартный язык, но он не мог понять, как это сделать. Поэтому он поступил так, как часто поступают теоретики сложности в отчаянии: он обратился к оракулу.

В теории сложности термин «оракул» обозначает гипотетическое устройство, способное мгновенно решить конкретную задачу. Компьютер, имеющий доступ к оракулу, может легче решать другие задачи, обращаясь к нему в качестве промежуточного шага в алгоритме. Конечно, в реальном мире оракулов не существует, но их изучение помогает теоретикам сложности понять взаимосвязь между уровнями сложности различных задач.

Кречмер задался вопросом, какой оракул мог бы облегчить различение двух квантовых состояний — так называемую проблему различения состояний. Он решил начать со специального оракула, который бы повысил мощность обычных квантовых алгоритмов, тех, которые используют квантовые приемы для решения задач с классическими входными битовыми строками. Такие алгоритмы могут решать некоторые задачи, слишком сложные для классических, например, разложение больших чисел на множители, но они не всемогущи — многие другие задачи находятся за пределами их досягаемости.

Доступ к оракулу Кречмера позволил бы таким алгоритмам решать некоторые задачи с классическими входными данными, слишком сложные для реальных квантовых компьютеров. Кречмер предполагал, что это будет излишним, но, к своему удивлению, он доказал, что проблема различения состояний все еще может поставить в тупик эти усовершенствованные квантовые алгоритмы.

«Меня очень заинтересовала статья Уильяма, — сказала Луовэнь Цянь, аспирантка, изучающая криптографию в Бостонском университете. — Я даже подумала, что она должна быть неверной, потому что она настолько противоречит здравому смыслу».

Цянь, Юэн и другие вскоре доказали, что если проблема различения состояний Кречмера действительно сложна, то возможны надежные схемы квантовой фиксации битов. Это, в свою очередь, подразумевало бы безопасность множества более сложных криптографических протоколов. Область применения квантовой криптографии оказалась гораздо шире, чем предполагали исследователи в 1990-х годах, и все сводилось к сложности одной проблемы.

Насколько это может быть сложно?

Результат Кречмера сопровождался одним важным условием — для того, чтобы доказательство работало, ему пришлось полагаться на необычный оракул, к которому могли обращаться только квантовые алгоритмы. Возможно, более знакомый оракул упростил бы его задачу различения состояний и, следовательно, сделал бы невозможным надежное подтверждение квантовых битов? В 2022 году Кречмер и Цянь начали работать вместе, чтобы выяснить, что они могут доказать об оракуле, понятном каждому: о таком, который мог бы мгновенно решить любую NP-задачу. В мире с такими оракулами вся классическая криптография была бы невозможна.

Кречмер вскоре понял, что проблема дискриминации со стороны государства математически связана с внешне отличающейся проблемой в квантовой теории сложности, и он заручился помощью двух экспертов в этой области, теоретиков сложности Авишая Таля и Макранда Синхи. «Уильям был скорее менеджером, а мы были подрядчиками», — сказал Таль.

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

Результат привлёк внимание Ма, и он начал задумываться, насколько далеко он сможет продвинуть начатое Кречмером направление исследований. Сможет ли квантовая криптография оставаться безопасной даже с более сложными оракулами — такими, которые могли бы мгновенно решать вычислительные задачи, намного более сложные, чем задачи класса NP? «Задачи класса NP — это не самые сложные классические задачи, которые можно себе представить», — сказала Дакшита Хурана, криптограф из Университета Иллинойса в Урбана-Шампейн. «Существуют задачи, выходящие за эти рамки».

Ма начал обдумывать наилучший подход к этому вопросу вместе с Алексом Ломбарди, криптографом из Принстонского университета, и Джоном Райтом, исследователем квантовых вычислений из Калифорнийского университета в Беркли. «Это было настолько захватывающе и настолько поразительно, что меня сразу же затянуло», — сказал Райт.

После долгих раздумий и безуспешных попыток найти решение, Ма предложил рассмотреть наиболее крайний случай: оракул, способный мгновенно решить любую вычислительную задачу с классическими входными данными. Это включало бы все проблемы, которые традиционно изучали теоретики сложности, даже те, которые, как известно, неразрешимы в реальном мире.

«Мне это показалось немного безумным», — сказал Ломбарди.

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

Ограничение алгоритмов одним запросом является менее строгим ограничением, чем может показаться, поскольку квантовые алгоритмы могут эффективно запрашивать у оракула решение нескольких задач одновременно, используя явление, называемое суперпозицией. Алгоритмы, способные выполнять несколько запросов последовательно, могут быть более мощными, поскольку они могут использовать ответы оракула на предыдущие запросы, чтобы решить, что спросить дальше. Остается открытым вопрос, обладают ли эти алгоритмы аналогичными ограничениями.

Статья Ма, Ломбарди и Райта имела важное значение и по другой причине. В процессе решения своей проблемы три исследователя поняли, что она тесно связана с крупной нерешенной проблемой, поставленной 16 лет назад теоретиком сложности Скоттом Ааронсоном и математиком Грегом Купербергом, о сложности преобразования одного квантового состояния в другое. Новая статья стала первым значительным шагом к решению этого вопроса.

«Это очень убедительный и одновременно очень неожиданный результат», — сказал Томоюки Моримаэ, исследователь в области квантовой криптографии из Института теоретической физики Юкавы в Киото.

Ряд последних результатов свидетельствует о том, что, казалось бы, безобидная проблема различения двух квантовых состояний не просто сложна, а почти невообразимо сложна — она находится далеко за пределами возможностей обычных квантовых алгоритмов и даже более экзотических. Это хорошая новость для криптографии, но она также имеет более широкие последствия для вычислительных задач, входными данными которых являются квантовые состояния. Традиционная теория сложности, похоже, не способна решить эти проблемы. Для их истинного понимания может потребоваться принципиально новая теоретическая основа.

«Создается впечатление, что в поведении квантовой информации есть нечто принципиально иное, — говорит Андреа Коладанджело, квантовый криптограф из Вашингтонского университета. — Неизбежно, что существуют связи, выходящие за рамки криптографии».

Примечание редактора: Скотт Ааронсон является членом консультативного совета журнала Quanta Magazine. Его работа упоминалась в этой статье, но он не принимал участия в редакционном процессе. Кроме того, Институт теории вычислительной техники им. Саймонса был создан благодаря гранту Фонда Саймонса, который также финансирует это независимое издание. Решения Фонда Саймонса о финансировании не влияют на наши публикации.

Источник: www.quantamagazine.org