HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

Zero-knowledge proof: Abstract example

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
knowledgeabstractexamplezeroproof

Problem

So I was reading about ZKP on wikipedia, the abstract example in summary goes like this:


Peggy wants to prove to Victor that she knows the secret to a door inside a cave that connect A and B together (see diagram) without revealing the secret word to Victor.






  • Peggy takes a random entry not know to Victor



  • Victor shouts to Peggy to come out of path A or B (randomly choosen)



  • and so it follows that she must know the secret word in order to come out of the path that Victor chooses without revealing to Victor the secret word. Victor builds confidences the more times this is done.




However, why is Victor not allowed to see which path Peggy chooses to enter from? As this does not reveal any extra information about what the secret word is.

Why can't Victor see which way she enters and asks her to demonstrate the 4 possibilities, that is:

  • Enter from A and exit from A



  • Enter from A and exit from B



  • Enter from B and exit from A



  • Enter from B and exit from B

Solution

I believe this is done to illustrate two things.

(i)
The small probability, that $P$eggy ($P$rover) might be lying. If she really does not know the magic word and $V$ictor ($V$erifier) sees her taking Path $A$, he would always ask her to come back via path $B$, thus the probability of $P$ succeeding when cheating is $0$.

However, $ZKP$s usually involve a small chance of $P$ succeeding while cheating, which is illustrated by $V$ not seeing the path $P$ takes to get to the magic door.

(ii) $V$ does not learn the secret. If $V$ stands at the crossroad of the paths $A$ and $B$, while $P$ walks to the magic door to say her magic word, it might be conceivable for $V$ to be able to hear $P$ saying her secret word. The only way to make sure that $V$ does not learn the magic word, is for him to wait outside of the cave, until $P$ has chosen a path.

Context

StackExchange Computer Science Q#59375, answer score: 7

Revisions (0)

No revisions yet.