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

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

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

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

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

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

Фон

Каждая интерактивная система доказательства определяет формальный язык строк . Надежность системы доказательств относится к тому свойству, что ни один доказывающий не может заставить проверяющего принять неверное утверждение, за исключением некоторой небольшой вероятности. Верхняя граница этой вероятности называется ошибкой надежности системы доказательства. Более формально, для каждого доказывающего и каждого : ${\displaystyle L}$ ${\displaystyle y\not \in L}$ ${\displaystyle ({\tilde {\mathcal {P}}})}$ ${\displaystyle y\not \in L}$

${\displaystyle \Pr[(\perp ,({\text{accept}}))\gets ({\tilde {\mathcal {P}}})(y)\leftrightarrow ({\mathcal {V}})(y)]<\epsilon .}$

для некоторых . Пока ошибка достоверности ограничена полиномиальной долей потенциального времени работы верификатора (т. е. ), всегда возможно усиливать надежность до тех пор, пока ошибка достоверности не станет пренебрежимо малой функцией относительно времени работы верификатора. Это достигается путем повторения доказательства и принятия его только в том случае, если все доказательства подтвердятся. После повторений ошибка корректности снизится до . ^[1] ${\displaystyle \epsilon \ll 1}$ ${\displaystyle \epsilon \leq 1/\mathrm {poly} (|y|)}$ ${\displaystyle \ell }$ ${\displaystyle \epsilon }$ ${\displaystyle \epsilon ^{\ell }}$

Классы интерактивных доказательств

НП

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ИП

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

QIP

Если мы позволяем элементам системы использовать квантовые вычисления , система называется квантовой интерактивной системой доказательства , а соответствующий класс сложности называется QIP . ^[8] Ряд результатов завершился прорывом 2010 года, который QIP = PSPACE . ^{[9] [10]}

Ноль знаний

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

МИП

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

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

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

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

PCP

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

Существует ряд легко доказуемых результатов о различных классах PCP . ‍ ‍ , класс машин с полиномиальным временем без случайности, но с доступом к сертификату, - это просто NP . ‍ ‍ класс машин с co- RP . Первым крупным результатом Ароры и Сафры было то, что ‍ ‍ ; Иными словами, если верификатор в протоколе NP вынужден выбирать только ‍ ‍ биты подтверждающего сертификата для просмотра, это не будет иметь никакого значения, пока он имеет ‍ ‍ случайные биты для использования. ^[15] ${\displaystyle {\mathsf {PCP}}(0,{\mathsf {poly}})}$ ${\displaystyle {\mathsf {PCP}}({\mathsf {poly}},0)}$ ${\displaystyle {\mathsf {PCP}}(\log ,\log )={\mathsf {NP}}}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$

Более того, теорема PCP утверждает, что количество доступов к доказательству можно свести к постоянному значению. То есть . ${\displaystyle {\mathsf {NP}}={\mathsf {PCP}}(\log ,O(1))}$^[16] Они использовали эту ценную характеристику NP , чтобы доказать, что алгоритмы аппроксимации не существуют для оптимизационных версий некоторых NP-полных задач, если только P = NP . Такие проблемы сейчас изучаются в области, известной как сложность аппроксимации .

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

• машина Oracle
• Доказательство знаний

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

1. Гольдрейх, Одед (2002), «Нулевое знание» через двадцать лет после его изобретения , ECCC  TR02-063 ..
2. Ласло Бабай. Теория торговых групп ради случайности. Труды семнадцатого ежегодного симпозиума по теории вычислений , ACM. 1985.
3. Гольдвассер, С.; Микали, С.; Ракофф, К. (1989). «Сложность знаний интерактивных систем доказательства» (PDF) . SIAM Journal по вычислительной технике . 18 (1): 186–208. дои : 10.1137/0218012. ISSN  1095-7111.Расширенное резюме
4. Шафи Голдвассер и Майкл Сипсер. Частные монеты и публичные монеты в интерактивных системах доказательств. Материалы ACM STOC'86 , стр. 58–68. 1986.
5. Ласло Бабай и Шломо Моран . Игры Артура-Мерлина: рандомизированная система доказательств и иерархия классов сложности. Журнал компьютерных и системных наук , 36: стр. 254–276. 1988.
6. О. Гольдрейх, С. Микали, А. Вигдерсон. Доказательства, которые не дают ничего, кроме своей достоверности. Журнал АКМ , том 38, выпуск 3, стр.690–728. Июль 1991 года.
7. Ади Шамир. IP = PSPACE. Журнал АКМ , том 39, выпуск 4, стр.869–877. Октябрь 1992 года.
8. Цуёси Ито; Хиротада Кобаяши; Джон Уотрус (2010). «Квантовые интерактивные доказательства со слабыми границами ошибок». arXiv : 1012.4427v2 [квант-ph].
9. Джайн, Рахул; Цзи, Чжэнфэн; Упадхьяй, Сарвагья; Уотрус, Джон (2010). «QIP = PSPACE». STOC '10: Материалы 42-го симпозиума ACM по теории вычислений . АКМ. стр. 573–582. ISBN 978-1-4503-0050-6.
10. Ааронсон, С. (2010). «QIP = прорыв PSPACE». Коммуникации АКМ . 53 (12): 101. дои :10.1145/1859204.1859230. S2CID  34380788.
11. Рассел Импальяццо, Моти Юнг: Прямые вычисления с минимальными знаниями. КРИПТО 1987: 40-51 [1]
12. М. Бен-ор, Шафи Голдвассер, Дж. Килиан и А. Вигдерсон. Интерактивные доказательства с несколькими доказательствами: как устранить неразрешимые предположения. Материалы 20-го симпозиума ACM по теории вычислений , стр. 113–121. 1988.
13. Ласло Бабай; Л. Фортноу; К. Лунд (1991). «Недетерминированное экспоненциальное время имеет интерактивные протоколы с двумя доказывающими. Вычислительная сложность». стр. 3–40. Архивировано из оригинала 8 февраля 2007 года.
14. Бен-Ор, Майкл; Гольдвассер, Шафи; Килиан, Джо; Видгерсон, Ави (1988). «Интерактивные доказательства с несколькими доказательствами: как устранить неполадки» (PDF) . Материалы двадцатого ежегодного симпозиума ACM по теории вычислений - STOC '88 . стр. 113–131. дои : 10.1145/62212.62223. ISBN 0897912640. S2CID  11008365. Архивировано из оригинала (PDF) 13 июля 2010 года . Проверено 17 ноября 2022 г.
15. Санджив Арора и Шмуэль Сафра . Вероятностная проверка доказательств: новая характеристика NP. Журнал ACM , том 45, выпуск 1, стр. 70–122. Январь 1998 года.
16. Санджив Арора, К. Лунд, Р. Мотвани, М. Судан и М. Сегеди. Проверка доказательства и сложность задач аппроксимации. Материалы 33-го симпозиума IEEE по основам информатики, стр. 13–22. 1992.

Учебники

• Арора, Санджив; Барак, Боаз, «Теория сложности: современный подход», Cambridge University Press, март 2009 г.
• Майкл Сипсер (1997). Введение в теорию вычислений . Издательство ПВС. ISBN 978-0-534-94728-6.Раздел 10.4: Интерактивные системы доказательств, стр. 354–366.
• Христос Пападимитриу (1993). Вычислительная сложность (1-е изд.). Эддисон Уэсли. ISBN 978-0-201-53082-7.Раздел 19.2: Игры против природы и интерактивные протоколы, стр. 469–480.

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

• Декстер Козен. Интерактивные доказательства. CS682 Конспекты лекций, весна 2004 г. Департамент компьютерных наук Корнелльского университета.
• Зоопарк сложности :
  • МА, МА', МАЭКСП, МАЭ
  • AM, AMEXP, AM пересекаются со-AM, AM[полилог], coAM, BP•NP
  • QMA, QMA+, QMA(2), QMAlog, QMAM
  • IP, MIP, IPP, QIP, QIP(2), compIP, frIP
  • PCP(r(n),q(n))
• Ларри Гоник. «Доказательство положительное?». Комикс об интерактивных системах доказательств.