Специалисты по информатике объединили два «красивых» метода доказательства

Трое исследователей придумали, как создать доказательство, которое распространяет информацию, сохраняя её в полной тайне.

Как доказать, что что-то истинно? Для математиков ответ прост: начните с базовых предположений и шаг за шагом дойдите до вывода. ЧТД, доказательство завершено. Если где-то есть ошибка, эксперт, внимательно прочитавший доказательство, сможет её заметить. В противном случае доказательство должно быть верным. Математики придерживаются этого базового подхода уже более 2 000 лет.

Затем, в 1980-х и 1990-х годах, учёные-информатики переосмыслили, каким может быть доказательство. Они разработали головокружительное разнообразие новых подходов, и когда пыль осела, два изобретения стали особенно заметны: доказательства с нулевым знанием, которые могут убедить скептика в истинности утверждения, не раскрывая причин его истинности, и вероятностно проверяемые доказательства, которые могут убедить читателя в истинности доказательства, даже если он видит лишь несколько крошечных фрагментов.

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

Исследователям не потребовалось много времени, чтобы попробовать объединить эти два типа доказательств. В конце 1990-х годов они одержали частичную победу, используя более слабые версии каждого варианта. В течение десятилетий никто не мог объединить идеальную версию нулевого знания с идеальной версией вероятностной проверяемости.

До сегодняшнего дня. В статье, которая является кульминацией семилетней работы, Гур и два других информатика наконец объединили идеальные версии двух видов доказательств для важного класса задач.

«Это очень важный результат», — говорит Эли Бен-Сассон, информатик-теоретик и основатель компании StarkWare, которая занимается разработкой криптографических приложений доказательств с нулевым знанием. «Он решает очень старую и хорошо известную открытую проблему, которая долгое время озадачивала исследователей, в том числе и меня».

Проверьте, пожалуйста

История началась в начале 1970-х годов, когда учёные-информатики начали формально изучать сложность задач, которые они давали решать компьютерам. Многие из этих задач обладали важным свойством: если кто-то находит правильное решение, он может легко убедить скептически настроенного «проверяющего», что оно действительно правильное. Проверяющий, в свою очередь, всегда сможет обнаружить ошибку. Задачи с таким свойством относятся к классу, который исследователи называют NP.

Чтобы понять, как может работать такая проверка, рассмотрим классическую задачу NP: дана карта, разделённая на различные регионы. Можно ли заполнить её всего тремя цветами, не закрашивая никакие два соседних региона в одинаковый цвет? В зависимости от карты, эта проблема может быть как простой, так и довольно сложной. Но если вам удастся найти правильную раскраску, вы сможете доказать это, показав проверяющему правильно раскрашенную карту. Проверяющему достаточно взглянуть на каждую границу.

Десятилетие спустя два аспиранта стали первопроходцами в области математических доказательств. Шафи Голдвассер и Сильвио Микали, работающие в Калифорнийском университете в Беркли, задались вопросом, можно ли предотвратить жульничество в онлайн-игре в покер. Для этого нужно было бы каким-то образом доказать, что карты в руке каждого игрока были взяты случайно, не раскрывая при этом, что это за карты.

Гольдвассер и Микали ответили на свой вопрос утвердительно, придумав доказательство с нулевым знанием в основополагающей статье 1985 года , написанной в соавторстве с информатиком из Университета Торонто Чарльзом Рэкоффом. В следующем году Микали и ещё двое исследователей опубликовали ещё одну работу, в которой показали, что решение любой задачи класса NP может быть проверено с помощью определённого вида доказательств с нулевым знанием.

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

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

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

Как сказал Амит Сахаи , компьютерный учёный из Калифорнийского университета в Лос-Анджелесе: «Если вероятность того, что что-то окажется неверным, меньше, чем единица, делённая на количество частиц во Вселенной, то нам кажется разумным называть это доказательством».

Довольно крутые доказательства

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

Кульминацией революции доказательств стало последнее удивительное открытие: вы всё ещё можете получить всю мощь интерактивных доказательств без каких-либо взаимодействий.

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

Затем в 1992 году учёные-информатики Санджив Арора и Шмуэль Сафра определили новый класс неинтерактивных доказательств: вероятностно проверяемые доказательства (probabilistically checkable proofs, PCP). Вместе с другими исследователями они показали, что любое решение задачи NEXP может быть переписано в этой специальной форме. Хотя PCP даже длиннее обычных доказательств, они могут быть строго проверены верификатором, который читает только небольшие фрагменты. Это происходит потому, что PCP эффективно умножает и распространяет любую ошибку в обычном доказательстве. Пытаться найти ошибку в обычном доказательстве — всё равно что искать крошечную дольку джема, откусывая кусочек тоста. PCP «равномерно распределяет джем по куску хлеба», — говорит Гур. «Где бы вы ни откусили кусочек, вы всегда обнаружите джем».

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

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

«Это считается одним из главных достижений теоретической информатики», — говорит Юваль Ишай, криптограф из Техниона в Хайфе, Израиль.

Путь к теореме PCP не был простым. Исследователи начали с доказательств с нулевым знанием для NP-задач, которые использовали интерактивность и случайность. Затем они поняли, что подобные доказательства можно использовать для проверки решений гораздо более сложных задач. И наконец, они показали, что, преобразовав эти доказательства в неинтерактивные PCP, можно проверить решение за меньшее время, чем потребовалось бы для простого прочтения доказательства. Учёные-информатики чувствовали себя триумфаторами.

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

Слишком много информации

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

«Это не так просто — замаскировать то, на что они должны смотреть», — говорит Джек О’Коннор, аспирант из Кембриджа, который работал с Гуром над новым результатом. «Мы должны замаскировать это независимо от того, как они проверяют доказательство».

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

В 1997 году трое исследователей преодолели эти трудности и построили тип PCP с нулевым знанием, который работал для любой проблемы в NEXP — но за это пришлось заплатить. Им пришлось добавить нотку интерактивности в то, как проверяющий проверяет доказательство, что отличается от обычной ситуации, когда в PCP нет ничего интерактивного.

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

Абсолютный ноль

В течение следующих 20 лет несколько исследователей усовершенствовали методы, описанные в статье 1997 года, сделав PCP с нулевым знанием более полезными в криптографических приложениях. Но фундаментальные ограничения оставались. Затем в 2017 году аспирант Беркли по имени Николас Спунер (который сейчас работает в Корнельском университете) начал подозревать, что методы, которые он помогал разрабатывать для смежной проблемы, могут быть полезны и для построения идеальных PCP с нулевым знанием.

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

«Я был больше пессимистом, а он — скорее оптимистом», — говорит Гур. «Он победил».

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

Гур и Спунер работали вместе без перерыва более пяти лет, но так и не смогли разобраться в деталях. О’Коннор присоединился к команде в 2023 году, после того как троица поняла, что ключевой недостающий ингредиент можно найти в, казалось бы, не имеющей отношения к делу статье, над которой они работали вместе. После последнего совместного усилия осенью трое исследователей собрали все части воедино в своей новой работе. В результате получился идеальный PCP с нулевым знанием для всех задач подсчёта. Более того, процесс проверки этих PCP оказался совершенно неинтерактивным.

«Они преодолели сразу два препятствия», — говорит Ишай. «Я был очень впечатлён».

Счётные задачи, которые изучали Спунер, Гур и О’Коннор, относятся к классу задач под названием #P («sharp P»), которые по сложности находятся между NP и NEXP. Теперь трое исследователей намерены расширить свою новую методику и применить её ко всем проблемам NEXP, сравнив её с мощью PCP в оригинальной статье Ароры и Сафры. Это будет большим шагом к доказательству аналога оригинальной теоремы PCP, но с совершённым нулевым знанием в качестве дополнительного преимущества. Гур настроен оптимистично, поскольку их новый метод представляет собой версию метода с нулевым знанием, который сыграл ключевую роль в теореме PCP.

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

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