Рейтинг:5

Почему протоколы с нулевым разглашением используются для задач NP, если IP — это класс систем интерактивного доказательства, откуда они берутся?

флаг in

Как указано в заголовке, я изучаю ZKP и вижу, что это просто интерактивные системы доказательств, которые уважают свойство нулевого разглашения. Теперь, если это правда, почему они не используются для задач IP, класса сложности интерактивных систем доказательства, которые изначально были введены для них? Я имею в виду, разве механизм доказательства не интерактивен в ZKP между Prover и Verifier? Тогда почему мы говорим о задачах NP, которые противоположны интерактивным?

baro77 avatar
флаг gd
Насколько я знаю 1) доказывая ZKP для конкретной NP-полной задачи как G3C, вы доказали это для каждой NP-полной задачи (и я не знаю, существует ли нечто подобное в более широком смысле IP) 2) В криптографии задачи NP представляют большой интерес, потому что, говоря простым языком, для верификатора их трудно вычислить, но легко проверить. 3) С общей точки зрения, интерактивность в криптографии не столь желательна, потому что она вынуждает стороны быть в сети одновременно: насколько я знаю, часто варианты ZKP - это NI, полученные путем введения дополнительных моделей (например, ROM или CRS)
Geoffroy Couteau avatar
флаг cn
На самом деле существует простое сокращение от ZK для NP до ZK для всех IP (ну, не так просто, потому что оно основано на доказательстве IP = PSPACE, но легко, учитывая это доказательство). Хотя со всеми остальными пунктами согласен.
Рейтинг:11
флаг us

Причина в том, что, по существу, класс языков в $\mathcal IP$ которых нет в $\математический НП$ не может быть доказано с помощью эффективного доказывающего. Поскольку нас обычно интересует криптографический контекст с эффективными доказывающими, изучение ZK обычно фокусируется на $\математический НП$. (Обратите внимание, что при изучении сложности и часто при изучении основ криптографии нас, безусловно, интересуют неэффективные доказывающие.)

Чтобы понять, почему за пределами $\математический НП$ доказывающий не может быть эффективным, обратите внимание, что любое интерактивное доказательство с эффективным доказывающим (при наличии свидетеля) может быть эмулировано машиной, которая получает свидетеля и запускает доказательство локально, проверяя, является ли результат принятым или отклоненным. Это как раз класс языков $\mathcalMA$. Согласно стандартным предположениям о дерандомизации, $\mathcalMA = NP$. Таким образом, при этих предположениях любой язык, не $\математический НП$ можно запустить только с неэффективным прувером (даже с некоторым свидетельством). Таким образом, он представляет меньший интерес при построении протоколов и т.п.

флаг in
Большое спасибо, я принял ваш ответ. Однако я не понимаю, почему, если доказательство неэффективно или нет, это как-то влияет. Особенно, если у него есть свидетель, я всегда думал, что это важная часть. Я имею в виду, когда вы сказали, что «при этих предположениях любой язык, который не находится в NP, может работать только с неэффективным доказывающим (даже с некоторым свидетелем)», если у неэффективного доказывающего все еще есть свидетель, какое это может иметь значение для алгоритм или класс сложности, несмотря на эффективность? и почему?
Yehuda Lindell avatar
флаг us
Мы хотим, чтобы доказывающий был эффективен со свидетелем. Я хотел сказать, что если мы не находимся в NP (или фактически в MA), то доказывающий не может быть эффективным в любом случае (т. е. вы не можете сделать доказывающий эффективным, дав ему свидетельство). Отвечает ли это на ваш вопрос?
флаг in
Собственно, эту часть я понял, спасибо. Но зачем вам еще и эффективный доказывающий, если у него уже есть свидетель? Я думал, что эффективная часть заключается только в том, чтобы гарантировать более высокий уровень безопасности при анализе протокола (например, различные уровни нулевого знания, вычислительного, статистического или совершенного), но зачем нам нужна эффективность доказывающего, если он уже имеет свидетель? Разве ему не нужно просто использовать свидетеля, чтобы доказать заявление и отправить ответ верификатору? Может быть, дело в том, что для вычисления ответа на утверждение доказывающему по-прежнему нужны вычислительные мощности?
Yehuda Lindell avatar
флаг us
Извините, но мне трудно понять вопрос.Нам нужно, чтобы доказывающий был эффективным, если мы хотим использовать доказательство ZK в криптографическом протоколе, поскольку в таком контексте все стороны должны иметь полиномиальное время. Я не понимаю вашего вопроса в конце: «Разве ему не нужно просто использовать свидетеля, чтобы доказать заявление». Доказывающий действительно использует свидетеля, но это не означает, что это обязательно эффективный (т. е. полиномиальное время) процесс.
флаг in
Вот именно, значит я правильно понял. Большое спасибо, английский не мой родной язык, но теперь все понятно!

Ответить или комментировать

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