Безопасность Zero знаний доказательство производительности - PullRequest
Новая
       9

Безопасность Zero знаний доказательство производительности

0 голосов
/ 12 мая 2019

Я недавно научился изучать безопасность доказательств с нулевым знанием.

Из Википедии кажется, что наиболее популярным примером является пещера Али-Баба. У меня есть вопрос о безопасности доказательства с нулевым разглашением для пещеры Али-Бабы.

Во время процесса проверки Prover предоставит значение 

e = [0,1 ...]

И e будет иметь решение либо left, либо right в зависимости от 0 или 1. И согласно длине списка e этот процесс, как говорят, имеет сложность безопасности O(2 ^ n). Однако существует только два пути, и в зависимости от значения e значение секретного ключа не изменяется в направлениях A и B. Поэтому разве безопасность этого алгоритма не должна быть просто O(2)?

1 Ответ

0 голосов
/ 26 июня 2019

Пещера Али-Бабы включает в себя следующий сценарий:

  1. Пегги выбирает случайный путь (A или B) без какой-либо информации от Виктора.
  2. Виктор спрашивает (кричит,в пещере) Пегги, чтобы выйти из пещеры с одного из двух концов (А или В), не зная пути входа, выбранного Пегги.
  3. Пегги выходит по пути, выбранному Виктором.

Для одного доказательства это имеет ту же вероятность, что и случайный случай: если мы назовем P_in путь, куда вошла Пегги, и V_out путь, на который Виктор просит Пегги выйти,

  • Если P_in = V_out, то Пегги может тривиально выйти из пещеры, не зная, как открыть дверь внутрь.
  • Если P_in != V_out, тогда Пегги нужно знать ключ, чтобы перейти с одной стороны пещеры.к другому.

У нас есть следующие равновероятные сценарии:

  • P_in = A, V_out = A
  • P_in = A, V_out = B
  • P_in = B, V_out = A
  • P_in = B, V_out = B

ОниЭто равновероятно, потому что Пегги выбирает случайно, а Виктор выбирает случайно, не зная, что выбрала Пегги (это часть с нулевым знанием).

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

Однако, если Виктор неоднократно просит Пегги войти в пещеру, вероятности увеличиваются.То есть P_in#1 = V_out#1 = 50%;но P_in#2 = V_out#2 = 50% (само по себе), что означает из-за условной вероятности (при условии, что события независимы), что для того, чтобы оба раза выйти из пещеры случайным образом: 

P(P_in#1 = V_out#1 /\ P_in#2 = V_out#2) = 1/2 * 1/2 = 1/4

ВероятностьПегги, зная, что ключ теперь повышен до 3/4: 

P( (P_in#1 != V_out#1 /\ P_in#2 == V_out#2)
|| (P_in#1 == V_out#1 /\ P_in#2 != V_out#2)
|| (P_in#1 != V_out#1 /\ P_in#2 != V_out#2)) =

P( ((P_in#1 != V_out#1 || P_in#1 == V_out#1) /\ P_in#2 == V_out#2)
|| P_in#1 != V_out#1 /\ P_in#2 != V_out#2) =

P( P_in#2 == V_out#2
|| (P_in#1 != V_out#1 /\ P_in#2 != V_out#2)) = 1/2 + (1/2 * 1/2) = 3/4

Причина экспоненциальной сложности заключается в том, что одиночный отказ вызывает недоверие, в то же время накапливая "серию побед"Случайный случай экспоненциально сложен.Таким образом, с учетом предыдущих вероятностей вы получаете O(2 ^ n), так как вы получаете «раз два» сложность при каждой попытке.

...