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