Интерактивная система доказательств - Interactive proof system

Общее представление протокола интерактивного доказательства.

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

Все интерактивные системы проверки предъявляют два требования:

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

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

НП

Класс сложности NP можно рассматривать как очень простую систему доказательств. В этой системе верификатор - это детерминированная машина с полиномиальным временем ( P- машина). Протокол:

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

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

Протоколы Артура-Мерлина и Мерлина-Артура

Хотя NP можно рассматривать как использование взаимодействия, только в 1985 году концепция вычислений через взаимодействие была задумана (в контексте теории сложности) двумя независимыми группами исследователей. Один подход, предложенный Ласло Бабаи , опубликовавшим «Теорию торговых групп для случайности», определил иерархию классов Артура – ​​Мерлина ( AM ). В этой презентации Артур (проверяющий) представляет собой вероятностную машину с полиномиальным временем, в то время как Мерлин (проверяющий) имеет неограниченные ресурсы.

Класс MA, в частности, является простым обобщением описанного выше взаимодействия NP, в котором верификатор является вероятностным, а не детерминированным. Кроме того, вместо того, чтобы требовать, чтобы верификатор всегда принимал действительные сертификаты и отклонял недействительные сертификаты, он является более снисходительным:

  • Полнота: если строка находится на языке, проверяющий должен иметь возможность выдать сертификат так, чтобы проверяющий примет его с вероятностью не менее 2/3 (в зависимости от случайного выбора проверяющего).
  • Правильность: если строка не на языке, никакой проверяющий, даже злонамеренный, не сможет убедить проверяющего принять строку с вероятностью, превышающей 1/3.

Эта машина потенциально более мощная, чем обычный протокол взаимодействия NP , и сертификаты не менее практичны для проверки, поскольку алгоритмы BPP рассматриваются как абстрактные практические вычисления (см. BPP ).

Протокол публичных монет против протокола приватных монет

В публичном протоколе монет случайные выборы, сделанные верификатором, становятся общедоступными. Они остаются закрытыми в частном протоколе монет.

На той же конференции, где Бабай определил свою систему доказательств для MA , Шафи Гольдвассер , Сильвио Микали и Чарльз Ракофф опубликовали статью, определяющую интерактивную систему доказательств IP [ f ( n )]. Он имеет те же машины, что и протокол MA , за исключением того, что f ( n ) раундов разрешены для ввода размера n . В каждом раунде верификатор выполняет вычисления и передает сообщение доказывающему, а доказывающий выполняет вычисления и передает информацию обратно верификатору. В конце верификатор должен принять решение. Например, в протоколе IP [3] последовательность будет VPVPVPV, где V - ход проверяющего, а P - ход проверяющего.

В протоколах Артура-Мерлина Бабай определил аналогичный класс AM [ f ( n )], который допускал f ( n ) раундов, но наложил на машину одно дополнительное условие: верификатор должен показать доказывающему все случайные биты, которые он использует в своих вычисление. В результате верификатор не может ничего «скрыть» от доказывающего, потому что доказывающий достаточно мощный, чтобы моделировать все, что делает верификатор, если он знает, какие случайные биты он использовал. Это называется протоколом публичных монет , потому что случайные биты («подбрасывания монет») видны обеим машинам. IP подход называется частной монетой протокол по контрасту.

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

В 1986 году Голдвассер и Сипсер показали, что, возможно, удивительно, что способность верификатора скрывать подбрасывание монеты от доказывающего, в конце концов, приносит мало пользы в том смысле , что публичный монетный протокол Артура-Мерлина с двумя дополнительными раундами может распознавать все те же языки. В результате протоколы публичных и частных монет примерно эквивалентны. Фактически, как показал Бабай в 1988 году, AM [ k ] = AM для всех констант k , поэтому IP [ k ] не имеет преимущества перед AM .

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

IP

Частные монеты могут быть бесполезны, но полезны дополнительные раунды взаимодействия. Если мы позволим машине вероятностного верификатора и всемогущей доказывающей стороне взаимодействовать в течение полиномиального числа раундов, мы получим класс проблем, называемый IP . В 1992 году Ади Шамир в одном из центральных результатов теории сложности показал, что IP равно PSPACE , классу задач, разрешимых с помощью обычной детерминированной машины Тьюринга в полиномиальном пространстве.

QIP

Если мы разрешаем элементам системы использовать квантовые вычисления , система называется квантовой интерактивной системой доказательства , а соответствующий класс сложности называется QIP . Серия результатов завершилась в 2010 году прорывом, согласно которому QIP = PSPACE .

Нулевое знание

Интерактивные системы доказательства могут не только решать проблемы, не относящиеся к NP , но и при предположении о существовании односторонних функций доказывающая сторона может убедить проверяющего в решении, даже не сообщая проверяющему информацию о решении. Это важно, когда верификатору нельзя доверять полное решение. Сначала кажется невозможным, чтобы верификатор мог быть убежден в том, что существует решение, когда верификатор не видел сертификата, но такие доказательства, известные как доказательства с нулевым разглашением , на самом деле считаются существующими для всех проблем в NP и ценными в криптография . Доказательства с нулевым разглашением впервые были упомянуты в оригинальной статье 1985 года об интеллектуальной собственности Голдвассером, Микали и Ракоффом, но степень их силы была показана Одедом Голдрайхом , Сильвио Микали и Ави Вигдерсон .

MIP

Одной из целей разработчиков IP было создание максимально мощной интерактивной системы доказательства, и поначалу казалось, что ее нельзя сделать более мощной, не сделав верификатор более мощным и непрактичным. Goldwasser et al. преодолели это в своей книге 1988 г. «Интерактивные доказательства с несколькими доказывающими устройствами: как удалить допущения о неразрешимости», в которых определяется вариант IP, называемый MIP, в котором есть два независимых доказывающих. Два проверяющих не могут общаться, если проверяющий начал посылать им сообщения. Точно так же, как легче определить, лжет ли преступник, если его и его партнера допрашивают в разных комнатах, значительно легче обнаружить злонамеренного доказывающего, пытающегося обманом заставить проверяющего принять строку не на языке, если есть другой доказывающий, который может перепроверьте с.

Фактически, это настолько полезно, что Бабай, Фортноу и Лунд смогли показать, что MIP = NEXPTIME , класс всех задач, решаемых недетерминированной машиной за экспоненциальное время , очень большой класс. NEXPTIME содержит PSPACE и, как полагают, строго содержит PSPACE. Добавление постоянного количества дополнительных доказывающих устройств сверх двух не позволяет распознавать другие языки. Этот результат проложил путь к знаменитой теореме PCP , которую можно рассматривать как "уменьшенную" версию этой теоремы.

MIP также обладает полезным свойством, заключающимся в том, что доказательства с нулевым разглашением для каждого языка в NP могут быть описаны без предположения об односторонних функциях, которые должен выполнять IP . Это имеет отношение к разработке доказуемо нерушимых криптографических алгоритмов. Более того, протокол MIP может распознавать все языки в IP только за постоянное количество раундов, а если добавлен третий доказывающий, он может распознавать все языки в NEXPTIME за постоянное количество раундов, снова демонстрируя свою власть над IP .

Известно, что для любого константы k MIP-система с k доказывающими и полиномиально большим количеством раундов может быть превращена в эквивалентную систему только с 2 доказывающими и постоянным количеством раундов.

PCP

В то время как разработчики IP рассматривали обобщения интерактивных систем доказательства Бабая, другие рассматривали ограничения. Очень полезной интерактивной системой проверки является PCP ( f ( n ), g ( n )), которая является ограничением MA, где Артур может использовать только f ( n ) случайных битов и может проверять только g ( n ) бит сертификата доказательства. отправлено Мерлином (по сути, с использованием произвольного доступа ).

Существует ряд легко подтверждаемых результатов о различных классах PCP . , класс машин с полиномиальным временем без случайности, но с доступом к сертификату, - это просто NP . , класс машин с полиномиальным временем с доступом к полиномиально множеству случайных битов - это co- RP . Первым важным результатом Ароры и Сафры было то, что PCP (log, log) = NP ; Другими словами, если проверяющий в протоколе NP ограничен выбирать только биты проверочного сертификата для просмотра, это не будет иметь никакого значения, если у него есть случайные биты для использования.

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

Смотрите также

Рекомендации

Учебники

внешние ссылки