Регистрация Войти
Рейтинг:5
avatar Crypto

Является ли «Свидетель» и «Доказательство» одним и тем же, когда речь идет о нулевом знании? А "аргумент"? А "заявление"?

флаг in
Andrea Farneti

Я видел, как люди делали много различий, читая статьи о нулевом разглашении.
Я видел термин «Аргумент знания», который, кажется, используется как более слабое «Доказательство знания»: я понял, что если вы говорите о свойстве нормальной обоснованности, вы говорите о «аргументах», в то время как если вы говорите о свойство достоверности (из Proofs of Knowledge), тогда вы говорите о «доказательствах». Это правильно?

Но больше всего меня смущает то, что я видел, как термины «свидетель» и «доказательство» используются по-разному и для выражения одной и той же концепции. Я знаю, что такое свидетель (в основном, секрет Доказывающего), но я также слышал фразы:
"П не знает свидетеля, но знает доказательство"
"генерация свидетеля И генерация доказательства"
«в Zk-SNARKS лаконичность: размер доказательства намного меньше размера свидетеля».

«Проверка доказательства намного быстрее, чем прямая проверка заявления, даже при наличии свидетеля».
Эта последняя фраза действительно хаотична для меня.

Так они отличаются? Если да, то в чем разница между «доказательством» и «утверждением»?
Английский не мой родной язык, это может быть проблемой, но, пожалуйста, не могли бы вы разъяснить мне все эти термины?

225
0 + 0
Рейтинг:2
Yehuda Lindell avatar Crypto
флаг us
Yehuda Lindell

Во-первых, важно понимать, что не все используют терминологию правильно или одинаково. Таким образом, вы не найдете полной согласованности везде. Сказав это, я считаю, что в данном случае это совершенно ясно. А свидетель является очень специфическим типом доказательства. В частности, это то, что мы называем NP-доказательством того, что $х\в л$. ($\математический НП$ как класс сложности можно рассматривать по-разному. Концептуально «лучший» способ, на мой взгляд, - это класс языков, для которых утверждения имеют эффективные письменные доказательства. То есть существует (детерминированная) машина проверки с полиномиальным временем $В$ такой, что $х\в л$ тогда и только тогда, когда существует $w$ такой, что $ V (х, ш) = 1 $. Однако существует множество других способов доказательства утверждений. Во-первых, есть утверждения, которые мы доказываем, но которые не находятся в $\математический НП$. Во-вторых, мы можем доказывать NP-утверждение, но нам нужны другие свойства — например, нулевое знание. В таком случае мы используем интерактивное доказательство. Доказывающий может использовать свидетельство, но не посылает его. Наконец, могут быть случаи (например, в SNARK), когда доказательство может быть короче, чем исходный свидетель NP, и нам могут понадобиться доказательства, где время, необходимое для проверки доказательства, короче, чем время запуска. $ V (х, ш) $ и проверить это классическим способом NP, и так далее. Я надеюсь, что это ясно.

0 + 0
флаг in
Andrea Farneti
Большое спасибо Иегуда, да, это очень помогает.Я думал, что свидетель — это какой-то секрет, который позволяет доказывающему всегда эффективно генерировать доказательство, если оно у вас есть, и я думаю, что это «отчасти» правильно (может быть, не всегда эффективно), верно? Но и самого свидетеля можно рассматривать как доказательство, но НП, верно? Тогда возникает естественный вопрос: как возможно, что в таких контекстах, как SNARK, доказательство короче и быстрее, чем свидетель, если свидетель является NP-детерминированным доказательством? Что может быть быстрее этого?
0
Ответить
флаг in
Andrea Farneti
Я имею в виду, я думаю, чтобы проверить доказательство P, вам все еще нужно запустить V (x, p), как если бы вы запускали V (x, w), верно? А свидетель гораздо сильнее доказательства, так как же он может быть быстрее? Это мое единственное сомнение
0
Ответить
Yehuda Lindell avatar
флаг us
Yehuda Lindell
Подумайте о P, работающем усерднее, чтобы предоставить что-то, что проще для V. Кроме того, в отличие от NP-доказательств, мы позволяем верификатору иногда ошибаться (с низкой вероятностью), и мы также позволяем ему быть вероятностным. Эти вещи очень помогают.
0
Ответить
флаг in
Andrea Farneti
Итак, дайте мне знать, если я правильно понял, потому что трудно увидеть полное изображение: в интерактивном протоколе свидетель является доказательством, которое всегда будет принято от верификатора, поэтому, если у вас есть свидетель, вы всегда можете доказать что x находится в L с вероятностью 1, но не обязательно действительно эффективен. Вместо этого, если у вас есть доказательство, вы можете доказать, что x находится в L с определенной (довольно высокой) вероятностью. Таким образом, доказательство может быть быстрее, чем свидетель. Это правильный способ увидеть разницу между доказательством и свидетелем?
0
Ответить
Yehuda Lindell avatar
флаг us
Yehuda Lindell
Да. Единственное, что я бы сказал по-другому, это вторая половина, где я бы сослался на «систему доказательств», включающую доказывающего и проверяющего. Это отличается от свидетеля, который предоставляет аналог письменного доказательства.
0
Ответить
Рейтинг:2
baro77 avatar Crypto
флаг gd
baro77

О паре побочных тем

Я полагаю, что мы говорим об «Аргументе», когда «Доказательство» надежности зависит от вычислительных предположений: поэтому обоснованность Аргументов слабее, чем у Доказательств, но часто достаточно сильна, учитывая, что современные приложения криптографии всегда полагаются на вычислительную сложность; и аналогом является то, что, например, NP-аргументы могут быть ZK более сильным способом, чем NP-доказательства (статистически ZK против вычислительно ZK).

Суффикс «знания» используется (как для доказательств, так и для аргументов), когда доказывающий содержит информацию, которую можно извлечь. эффективно через "особую настройку" (особую по аналогии с особенной Симулятор).

Или попробуйте подумать об этом таким образом: «вкус здравости» и «знание чего-то (или незнание)» — два ортогональных свойства, так что вы можете получить «декартово произведение» комбинаций:

  1. ЗК Доказательство
  2. ЗК Аргумент
  3. ZK Доказательство знаний
  4. ZK Аргумент знания («КОВЧЕГ» в ZK-SNARK)

1 и 3 имеют более сильную(*) надежность, 2 и 4 только вычислительную; для 3 и 4 существует Экстрактор (это общепризнанный способ доказательства Знаний), который может эффективно получать информацию, хранимую доказывающим (и он не нарушает свойство ZK аналогичным образом Симулятор не нарушает надежность... останавливаясь/ перемотка и все такое..)

таким образом, Аргумент, который слабее доказательства с точки зрения надежности, может иметь более высокий уровень безопасности с нулевым разглашением (статистический), чем доказательство (вычислительный)? Я имею в виду, хорошо...но как же? Не понимаю, почему это возможно.

Если вы поймете, что «надежность» и «знание» — это два разных свойства, вы также поймете, что третье отличное свойство — это «нулевое знание», которое может зависеть от первого не так, как вы ожидаете.

Я всего лишь гик и заядлый читатель, поэтому я думаю, вы могли бы легко получить много лучших объяснений, чем мои, однако я хочу предложить вам главу 4 книги Одеда Голдрейха «Основы криптографии», том 1 ... действительно проницательно ...

(*) не только на статистическом «уровне», в Доказательствах достоверность доказывается логическим выводом из контекста и аксиом, поэтому обычные «классические/стандартные» демонстрации

0 + 0
флаг in
Andrea Farneti
Итак, в основном, когда вы говорите о свойстве надежности на вычислительном уровне, вы используете термин Аргумент, в то время как если вы определяете экстрактор знаний и доказываете, что свидетель существует, вы говорите о доказательствах... Или, может быть, вы говорите о доказательствах даже без Извлекатели знаний, а только свойство надежности на статистическом уровне безопасности? Кроме этого, таким образом, Аргумент, который слабее доказательства с точки зрения надежности, может иметь более сильный уровень безопасности с нулевым разглашением (статистический), чем доказательство (вычислительный)? Я имею в виду, хорошо... но как же так? Не понимаю, почему это возможно.
0
Ответить
baro77 avatar
флаг gd
baro77
Я попытался ответить комментарием, но мне нужно было больше места, поэтому я отредактировал свой предыдущий ответ.
0
Ответить
флаг in
Andrea Farneti
Большое вам спасибо, я дал лучший ответ Иегуде, потому что этот ответ был главным, что мне нужно, чтобы очистить свой разум, но даже ваш был очень полезен. Раньше я не очень хорошо понимал разницу между аргументом и доказательством, но теперь я знаю, так много разных терминов, которые нужно выучить, чтобы действительно понять нулевое знание ... Я дал вам голос!
0
Ответить
baro77 avatar
флаг gd
baro77
Ты поступил правильно! :) Иегуда не только известен в отрасли, но и принадлежит к группе профессионалов/профессоров, которые жертвуют часть своего времени здесь, в сообществе: поэтому предлагая таблетки своей преподавательской деятельности вне официального канала университетских занятий, а также: не общие и достойные похвалы, помогающие распространять качественные знания. Так что спасибо ему и другим (теперь я помню @GeoffroyCouteau, но наверняка скучаю и по многим другим). Что касается меня, я только учусь, как и вы, и попытка ответить помогает мне консолидировать понятия: спасибо за голосование!
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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