Теоретически, квантовая физика может обойти сложные математические проблемы, лежащие в основе современного шифрования. Новое доказательство показывает, как это сделать. Комментарий Сохранить статью Прочитать позже
Исследователи восстанавливают фундамент башни криптографии.
Введение
Сложные задачи обычно не приветствуются. Но криптографы их обожают. Это потому, что определенные сложные математические задачи лежат в основе безопасности современного шифрования. Любой хитрый способ их решения обречет на провал большинство форм криптографии.
Несколько лет назад исследователи обнаружили принципиально новый подход к шифрованию, в котором отсутствует эта потенциальная уязвимость. Этот подход использует особенности квантовой физики. Но в отличие от более ранних схем квантового шифрования, которые работали лишь для нескольких специальных задач, новый подход может решать гораздо более широкий круг задач. И он может сработать, даже если все проблемы, лежащие в основе обычной «классической» криптографии, окажутся легко решаемыми.
Однако это поразительное открытие основывалось на нереалистичных предположениях. Результат оказался «скорее подтверждением концепции», — сказал Ферми Ма, исследователь в области криптографии из Института теории вычислений имени Саймонса в Беркли, штат Калифорния. — «Это не утверждение о реальном мире».
Теперь в новой статье двух криптографов проложен путь к квантовой криптографии без этих нелепых предположений. «В этой статье говорится, что если верны некоторые другие предположения, то квантовая криптография должна существовать», — сказал Ма.
Небесный замок
Современную криптографию можно представить как башню, состоящую из трех основных частей. Первая часть — это скальная основа, расположенная глубоко под башней, которая состоит из сложных математических задач. Вторая часть — это сама башня, в которой находятся конкретные криптографические протоколы, позволяющие отправлять личные сообщения, подписывать цифровые документы, проводить тайное голосование и многое другое.
Между этими крайностями, обеспечивая безопасность повседневных приложений за счет математической основы, находится фундамент, состоящий из строительных блоков, называемых односторонними функциями. Именно они отвечают за асимметрию, присущую любой схеме шифрования. «Это односторонняя схема, потому что вы можете зашифровать сообщения, но не можете их расшифровать», — сказал Марк Чжандри, криптограф из NTT Research.
В 1980-х годах исследователи доказали, что криптография, построенная на основе односторонних функций, обеспечит безопасность для множества различных задач. Но спустя десятилетия они всё ещё не уверены, что основа достаточно прочна, чтобы её поддерживать. Проблема в том, что эта основа состоит из особых сложных задач — технически известных как NP-задачи — отличительной особенностью которых является то, что легко проверить правильность любого из возможных решений. (Например, разложение числа на простые множители — это NP-задача: её сложно решить для больших чисел, но легко проверить.)
Многие из этих проблем кажутся по своей сути сложными, но специалисты по информатике пока не смогли это доказать. Если кто-то откроет гениальный алгоритм для быстрого решения самых сложных NP-задач, фундамент рухнет, и вся башня обрушится.
К сожалению, вы не можете просто перенести свою башню в другое место. Фундамент башни — односторонние функции — может опираться только на основу из NP-задач.
Для построения более сложных систем криптографам потребовался бы новый фундамент, не состоящий из односторонних функций. Это казалось невозможным до недавнего времени, пока исследователи не поняли, что в этом может помочь квантовая физика.
Всё началось с работы 2021 года аспиранта Уильяма Кречмера, которая привлекла внимание к странной проблеме, касающейся свойств квантовых систем. Исследователи вскоре показали, что проблема Кречмера может заменить односторонние функции в качестве основы для новой системы криптографических протоколов. В следующем году Кречмер и другие доказали, что этот альтернативный подход может работать даже без сложных NP-проблем. Внезапно показалось, что можно построить гораздо более прочную криптографическую крепость.
Но где же его построить? Квантовая проблема, которую Кречмер использовал в качестве основы, включала гипотетические вычислительные устройства, называемые оракулами, способные мгновенно отвечать на конкретные вопросы. Оракулы могут быть полезными теоретическими инструментами, но в действительности они не существуют. Доказательства Кречмера были подобны чертежу для строительства небесного замка. Можно ли было перенести его на Землю?
Второй Фонд
Осенью 2022 года этот вопрос привлёк внимание Дакшиты Хураны, криптографа из Университета Иллинойса в Урбана-Шампейн и компании NTT Research. Хурана и её аспирант Кабир Томер поставили перед собой задачу построить новую башню криптографии. Первым шагом стало создание нового фундамента с использованием квантовых строительных блоков вместо классических односторонних функций. Затем ей нужно было доказать, что этот новый фундамент может поддерживать башню из других криптографических протоколов. После того как она доказала, что фундамент может поддерживать башню, ей нужно было найти прочное основание для всей конструкции — фундамент из реальных задач, которые кажутся даже сложнее, чем NP-задачи, используемые в классической криптографии.
Дакшита Хурана поставил перед собой задачу найти математические строительные блоки, которые могли бы заменить односторонние функции в качестве основы для квантовой криптографии.
На первом этапе Хурана и Томер сосредоточились на квантовой версии односторонней функции, называемой генератором одностороннего состояния, которая удовлетворяла трем свойствам, делающим односторонние функции полезными. Во-первых, функция должна работать быстро, чтобы можно было легко сгенерировать криптографический замок и соответствующий ключ для его открытия для каждого сообщения, которое вы хотите отправить. Во-вторых, каждый замок должен быть надежным, и для его взлома без подходящего ключа должны потребоваться значительные усилия. Наконец, каждый замок должен быть легко открываемым с помощью подходящего ключа.
Ключевое различие заключалось в природе замков. Классические односторонние функции создают математические замки, состоящие из битов — нулей и единиц, которые хранят информацию в классическом компьютере. Квантовые генераторы односторонних состояний, напротив, создают замки, состоящие из единиц квантовой информации, называемых кубитами. Эти квантовые замки потенциально могут оставаться надежными, даже если все классические замки легко взломать. Хурана и Томер надеялись начать с этой новой квантовой основы и построить на ней башню криптографических протоколов. «Это оказалось довольно сложно», — сказал Хурана. «Мы застряли на много-много месяцев».
К июлю 2023 года Хурана была почти на девятом месяце беременности и планировала взять отпуск по уходу за ребенком. У Томера закончились идеи. «Я гораздо более пессимистичен, чем Дакшита, — сказал он. — Она всегда верит, что все получится».
Затем они совершили прорыв. Решающим шагом стало определение еще одного математического строительного блока, который служил чем-то вроде подвального этажа: структуры, которая соединяла бы фундамент односторонних генераторов состояний с башней криптографических протоколов. Когда Хурана и Томер определили, какими свойствами должен обладать этот строительный блок, они обнаружили, что он напоминает одностороннюю функцию с загадочным сочетанием квантовых и классических характеристик. Как и в обычной односторонней функции, замки и ключи были сделаны из классических битов, но процедура генерации этих замков и ключей могла выполняться только на квантовом компьютере. Еще более странным было то, что новый строительный блок удовлетворял первым двум определяющим свойствам односторонних функций, но не третьему: было легко генерировать замки и ключи, и любой замок было трудно взломать. Но ключ не мог легко открыть свой замок.
Хурана и Томер назвали эти загадочные новые строительные блоки односторонними головоломками. Интуитивно трудно представить, как они могут быть полезны: какой смысл в ключе, который никогда нельзя использовать? Но два криптографа показали, что односторонние головоломки в сочетании с другими квантовыми уловками фактически позволят создавать многие криптографические протоколы. Если можно сгенерировать замки и ключи, которые в принципе подходят друг к другу, то не имеет значения, насколько неэффективна процедура разблокировки.
Кабир Томер и Хурана связали новые квантовые строительные блоки с реальными задачами, более сложными, чем те, которые используются в классической криптографии.
«Достаточно просто знать, что существует алгоритм, который может быть сколь угодно медленным», — сказал Кречмер, ныне научный сотрудник Института Саймонса. «Это очень удивительно».
Получив недостающий элемент, они быстро завершили проверку 4 августа. Дочь Хураны родилась всего несколько дней спустя.
Постоянная запись
К ноябрю Хурана вернулась к работе и была готова приступить ко второму этапу своего плана. Она и Томер показали, что многие виды криптографии могут быть построены на основе односторонних головоломок, а односторонние головоломки, в свою очередь, могут быть построены на новом квантовом фундаменте, состоящем из односторонних генераторов состояний. Следующим шагом в их первоначальном плане было соединение этого квантового фундамента с новой основой — некоторым относительно непреодолимым набором математических задач, которые еще более сложны, чем задачи в NP.
Но, столкнувшись с этой задачей, Хурана и Томер решили применить более прямой подход: забыть об односторонних генераторах состояний и вместо этого напрямую привязать односторонние головоломки к математической основе.
С одной стороны, это казалось странным выбором. Односторонние головоломки были математическими диковинками, которые Хурана и Томер использовали на промежуточном этапе своего доказательства.
Однако у односторонних головоломок были некоторые преимущества. Во-первых, хотя они и квантовые, создаваемые ими замки и ключи являются классическими. Хурана считал, что это может облегчить их связь с основами классической математики. Кроме того, односторонние головоломки генерируют ключи, которые слишком громоздки, чтобы фактически открывать замки. Это может облегчить их связь с задачами настолько сложными, что даже проверка решений кажется безнадежно трудной.
Но какие конкретные задачи подошли бы? У Хураны был один кандидат: вычисление определенной комбинации элементов в таблице чисел, называемой матрицей. Эта задача, известная как задача о матричной перманентности, чрезвычайно сложна для решения для больших матриц, и нет простого способа проверить правильность вычисления. Задача о матричной перманентности также обладает другими особыми математическими свойствами, которые привлекают криптографов.
«Это была бы прекрасная задача для построения криптографии», — сказал Хурана.
Проблема перманентности матрицы также связана с другой проблемой, которую квантовые компьютеры могут легко решить, но классические компьютеры, по-видимому, не могут. Исследователи работают над доказательством этого преимущества квантовых вычислений в точном теоретическом смысле. Хурана и Томер показали, что такое доказательство также позволит им построить надежные односторонние головоломки — и, следовательно, всю башню квантовой криптографии — поверх проблемы перманентности.
«Они смогли это сделать, опираясь на эти хорошо изученные предположения, — сказал Кречмер. — Я был очень рад это видеть».
Своим новым результатом Хурана и Томер фактически свели две открытые проблемы к одной. Если исследователи завершат доказательство того, что квантовые компьютеры действительно превосходят классические в решении конкретной задачи, это автоматически поставит квантовую криптографию на гораздо более прочную теоретическую основу, чем практически любой вид классической криптографии.
К сожалению, в ближайшее время вы не сможете использовать новый подход Хураны и Томера для отправки секретных сообщений. Несмотря на недавний прогресс, технология квантовых вычислений еще недостаточно зрела, чтобы воплотить их идеи на практике. Между тем, другие исследователи разработали методы квантовой криптографии, которые можно было бы использовать раньше, хотя потребуется дополнительная работа, чтобы установить их истинную безопасность.
Квантовая криптография уже преподнесла немало сюрпризов, и исследователи лишь недавно начали изучать ее возможности. «Мы просто пытаемся понять эту новую картину, которая на самом деле существовала все это время», — сказал Жандри.
Источник: www.quantamagazine.org
