Представьте, что у вас есть какие-то полезные знания — может быть, секретный рецепт или ключ к шифру. Могли бы вы доказать другу, что у вас есть это знание, не раскрывая ничего об этом? Более 30 лет назад ученые-компьютерщики доказали, что можно, если использовать так называемое доказательство с нулевым разглашением.
Для простого понимания этой идеи предположим, что вы хотите показать своему другу, что знаете, как пройти через лабиринт, не разглашая никаких подробностей о пути. Вы могли просто пройти лабиринт за отведенное время, а вашему другу было запрещено смотреть. (Ограничение по времени необходимо, потому что при наличии достаточного количества времени каждый может найти выход путем проб и ошибок.) Ваш друг будет знать, что вы можете это сделать, но он не будет знать, как это сделать.
Доказательства с нулевым разглашением полезны криптографам, работающим с секретной информацией, а также исследователям вычислительной сложности, занимающимся классификацией сложности различных задач. «Многое в современной криптографии основано на предположениях о сложности — на допущении, что определенные проблемы трудно решить, поэтому между двумя мирами всегда существовала какая-то связь», — сказал он. Клод Крепо, ученый-компьютерщик из Университета Макгилла. «Но [эти] доказательства создали целый мир связей».
Доказательства с нулевым разглашением принадлежат к категории, известной как интерактивные доказательства, поэтому, чтобы узнать, как работают первые, полезно понять последние. Первый описано в статье 1985 года ученых-компьютерщиков Шафи Голдвассер, Сильвио Микали и Чарльз Ракофф, интерактивные доказательства работают как допрос: в ходе серии сообщений одна сторона (доказывающая) пытается убедить другую (проверяющую) в истинности данного утверждения. Интерактивное доказательство должно удовлетворять двум свойствам. Во-первых, истинное утверждение всегда в конце концов убедит честного проверяющего. Во-вторых, если данное утверждение ложно, то ни один доказывающий, даже претендующий на обладание определенным знанием, не может убедить проверяющего, кроме как с пренебрежимо малой вероятностью.
Интерактивные доказательства носят вероятностный характер. Доказывающий может правильно ответить на один или два вопроса просто по счастливой случайности, поэтому требуется достаточно большое количество испытаний, все из которых доказывающий должен решить правильно, чтобы проверяющий был уверен, что доказывающий действительно знает, что утверждение верно.
Эта идея взаимодействий возникла, когда Микали и Голдвассер — в то время аспиранты Калифорнийского университета в Беркли — ломали голову над логистикой игры в покер по сети. Как все игроки могут убедиться, что когда один из них получает карту из виртуальной колоды, результат является случайным? Интерактивные доказательства могут проложить путь. Но тогда как игроки могут проверить, что весь протокол — полный набор правил — был соблюдён правильно, не раскрывая при этом руку каждого игрока?
Для достижения этой цели Микали и Гольдвассер добавили третье свойство к двум, необходимым для интерактивного доказательства: доказательство не должно ничего раскрывать о самом знании, а только правдивость утверждения. «Есть понятие прохождения протокола, в конце которого вы считаете, что [игроки в покер] не знают ничего, кроме того, что они должны знать», — сказал Голдвассер.
Рассмотрим классический пример. Алиса хочет доказать Бобу, что некоторый граф G — уникальный набор вершин (точек), соединенных ребрами (прямыми), — имеет «гамильтонов цикл». Это означает, что на графе есть путь, который проходит через каждую точку ровно один раз и заканчивается в той же точке, с которой он начался. Алиса могла бы сделать это, просто показав Бобу путь, который делает это, но, конечно, тогда он тоже знал бы путь.
Вот как Алиса может убедить Боба, что она знает о существовании такого пути, не показывая его ему. Сначала она рисует новый график, H, это не похоже G но в решающем смысле похож: у него такое же количество вершин, соединенных теми же способами. (Если G действительно имеет гамильтонов цикл, это подобие означает H тоже будет.) Затем, покрыв каждый край H с липкой лентой, она запирает H в коробке и дает коробку Бобу. Это мешает ему увидеть это напрямую, но также мешает ей изменить это. Затем Боб делает выбор: либо он может попросить Алису показать, что H действительно похож на G, или он может попросить ее показать ему гамильтонов цикл в H. Оба запроса должны быть легкими для Алисы, если предположить, что H действительно достаточно похоже на G, и что она действительно знает путь.
Конечно, даже если Алисе не известен гамильтонов цикл в G, она может попытаться одурачить Боба, рисуя графики, не похожие на G, или путем отправки графиков, путь к которым она не знает. Но после того, как они сыграют несколько раундов, вероятность того, что Алиса каждый раз обманывает Боба, становится исчезающе малой. Если она все сделает правильно, в конце концов Боб убедится, что Алиса знает гамильтонов цикл в графе G, причем Боб никогда его не видел.
После первоначальной статьи, в которой впервые были описаны такие доказательства, Микали и два математика — Одед Гольдрейх и Ави Вигдерсон — обнаружили неожиданное следствие с далеко идущими последствиями. Это связано с основной категорией задач примерно равной сложности, известной как NP. Эти задачи трудно решить, но их решения легко проверить. Трое исследователей обнаружили, что, если действительно безопасное шифрование возможно, то решение каждой задачи из NP также можно доказать с помощью доказательства с нулевым разглашением. Это исследование помогло исследователям зачать варианты доказательств с нулевым разглашением, которые вообще не требуют безопасного шифрования; они известны как интерактивные доказательства с несколькими доказательствами.
А в 1988 году Микали и др. показал что, если доказывающий и проверяющий имеют общую короткую строку случайных битов, взаимодействие не требуется. Теоретически это означало, что доказательства с нулевым разглашением не обязательно должны быть интерактивными, что означало бы, что постоянная связь между двумя сторонами не требуется. Это сделало бы их гораздо более полезными для исследователей, но только на рубеже 21-го века такие доказательства стали популярными.
«В конце 2000-х мы начали наблюдать эволюцию эффективных методов построения доказательств с нулевым разглашением», — сказал Мэтью Д. Грин, криптограф из Университета Джона Хопкинса. «Мы подошли к моменту, когда поняли: «Подождите секунду, возможно, на самом деле есть способ использовать это на практике».
Теперь доказывающий может отправить одно сообщение верификатору, при этом оба они не должны быть в сети, а исследователи могут создать очень короткое доказательство, которое можно будет быстро проверить даже для очень сложных задач. Это привело к нескольким практическим применениям, таким как возможность быстрой проверки блокчейна после транзакции криптовалюты, скрывая детали транзакции. А в 2016 году группа физиков показал как доказательства с нулевым разглашением могут помочь в ядерном разоружении: не раскрывая никаких секретов конструкции своей ядерной боеголовки, страна теперь может доказать ядерным инспекторам, является ли боеголовка активной или неактивной.
Совсем недавно достижения в области квантовых вычислений вынудили Крепо провести стресс-тестирование прошлых исследований, чтобы убедиться, что протоколы с нулевым разглашением по-прежнему жизнеспособны. В 2021 году он помог демонстрировать что интерактивные доказательства с несколькими доказательствами сохраняют свою секретность, даже когда задействованы квантовые компьютеры, но достижение того же уровня безопасности делает протокол намного медленнее. По его словам, открытие стало хорошей новостью, но по мере развития технологий возникнут новые опасения.
«Каждый тип вычислений, которые мы сможем выполнять в будущем, будет включать квантовые компьютеры», — сказал Крепо. «Поэтому, как хорошие криптографы-параноики, всякий раз, когда мы оцениваем безопасность системы, мы хотим убедиться, что наша система безопасна».
Примечание редактора: Шафи Голдвассер получил финансирование от Фонда Саймонса, который также финансирует эту работу. редакционно независимое издание. Решения Фонда Саймонса о финансировании не влияют на наше покрытие.
