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

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

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

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

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

Специфика системы, а значит и класс сложности языков, которые она может распознавать, зависит от того, какие ограничения накладываются на верификатора, а также какие возможности ему предоставлены — например, большинство интерактивных систем доказательства критически зависят от способности верификатора делать случайный выбор. Это также зависит от характера обмениваемых сообщений — сколько их и что они могут содержать. Было обнаружено, что интерактивные системы доказательства имеют некоторые важные последствия для традиционных классов сложности, определенных с использованием только одной машины. Основными классами сложности, описывающими интерактивные системы доказательства, являются 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 , напротив, называется протоколом частной монеты .

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

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

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

ИС

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

QIP

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

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

Интерактивные системы доказательств могут не только решать проблемы, которые, как считается, не относятся к NP , но и при предположениях о существовании односторонних функций , доказывающий может убедить проверяющего в решении, даже не предоставляя проверяющему информацию о решении. Это важно, когда проверяющему нельзя доверять полное решение. Сначала кажется невозможным, что проверяющий может быть убежден в существовании решения, когда проверяющий не видел сертификата, но такие доказательства, известные как доказательства с нулевым разглашением, на самом деле считаются существующими для всех проблем в NP и ценными в криптографии . Доказательства с нулевым разглашением были впервые упомянуты в оригинальной статье 1985 года по IP Голдвассера, Микали и Ракоффа для конкретных языков теории чисел. Однако степень их мощности была показана Одедом Голдрайхом , Сильвио Микали и Ави Вигдерсоном . ^[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 доказывающими и полиномиально большим числом раундов может быть преобразована в эквивалентную систему всего с 2 доказывающими и постоянным числом раундов. ^[14]

ПЦП

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

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

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

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

• Машина Оракула
• Доказательство знания

Ссылки

1. Голдрайх, Одед (2002), Нулевое разглашение двадцать лет спустя после его изобретения , ECCC  TR02-063.
2. Ласло Бабай. Теория групп обмена на случайность. Труды семнадцатого ежегодного симпозиума по теории вычислений , ACM. 1985.
3. Голдвассер, С.; Микали, С.; Ракофф, К. (1989). «Сложность знаний интерактивных систем доказательства» (PDF) . SIAM Journal on Computing . 18 (1): 186–208. doi :10.1137/0218012. ISSN  1095-7111.Расширенная аннотация Архивировано 23.06.2006 на Wayback Machine
4. Шафи Голдвассер и Майкл Сипсер. Частные монеты против публичных монет в интерактивных системах доказательств. Архивировано 27 января 2005 г. в Wayback Machine . Труды ACM STOC'86 , стр. 58–68. 1986.
5. Ласло Бабай и Шломо Моран . Игры Артура–Мерлина: рандомизированная система доказательств и иерархия классов сложности. Журнал компьютерных и системных наук , 36: стр. 254–276. 1988.
6. O. Goldreich, S. Micali, A. Wigderson. Доказательства, которые не дают ничего, кроме своей достоверности. Journal of the ACM , том 38, выпуск 3, стр. 690–728. Июль 1991 г.
7. Ади Шамир. IP = PSPACE. Журнал ACM , том 39, выпуск 4, стр. 869–877. Октябрь 1992 г.
8. Цуёси Ито; Хиротада Кобаяши; Джон Ватроус (2010). «Квантовые интерактивные доказательства со слабыми границами ошибок». arXiv : 1012.4427v2 [quant-ph].
9. Джейн, Рахул; Цзи, Чжэнфэн; Упадхай, Сарвагья; Ватроус, Джон (2010). «QIP = PSPACE». STOC '10: Труды 42-го симпозиума ACM по теории вычислений . ACM. С. 573–582. ISBN 978-1-4503-0050-6.
10. Ааронсон, С. (2010). "QIP = PSPACE прорыв". Сообщения ACM . 53 (12): 101. doi :10.1145/1859204.1859230. S2CID  34380788.
11. Рассел Импальяццо, Моти Юнг: Прямые вычисления с минимальным знанием. CRYPTO 1987: 40-51 [1]
12. M. Ben-or, Shafi Goldwasser, J. Kilian и A. Wigderson. Интерактивные доказательства с несколькими доказательствами: как устранить предположения о неразрешимости. Труды 20-го симпозиума ACM по теории вычислений , стр. 113–121. 1988.
13. Ласло Бабай; Л. Фортноу; К. Лунд (1991). «Недетерминированное экспоненциальное время имеет двухдоказательные интерактивные протоколы. Вычислительная сложность». стр. 3–40. Архивировано из оригинала 8 февраля 2007 г.
14. Бен-Ор, Майкл; Голдвассер, Шафи; Килиан, Джо; Видгерсон, Ави (1988). "Интерактивные доказательства с несколькими доказательствами: как устранить неразрешимость" (PDF) . Труды двадцатого ежегодного симпозиума ACM по теории вычислений - STOC '88 . стр. 113–131. doi :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). Введение в теорию вычислений . PWS Publishing. ISBN 978-0-534-94728-6.Раздел 10.4: Интерактивные системы доказательств, стр. 354–366.
• Христос Пападимитриу (1993). Computational Complexity (1-е изд.). Эддисон Уэсли. ISBN 978-0-201-53082-7.Раздел 19.2: Игры против природы и интерактивные протоколы, стр. 469–480.

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

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