# HG changeset patch # User Christian Urban # Date 1415350890 0 # Node ID 045e6ea001327092f3f5ab9b1862e37e38b89431 # Parent 71f52ad510c2c76f582f03d49979c7d9e5d634a3 updated diff -r 71f52ad510c2 -r 045e6ea00132 handouts/ho06.pdf Binary file handouts/ho06.pdf has changed diff -r 71f52ad510c2 -r 045e6ea00132 handouts/ho06.tex --- a/handouts/ho06.tex Fri Nov 07 00:27:25 2014 +0000 +++ b/handouts/ho06.tex Fri Nov 07 09:01:30 2014 +0000 @@ -49,13 +49,13 @@ non-article in this definition and so on. But let us assume you agreed with Bob to stop after three iterations with the third non-article word in the last definition, that is -\textbf{or}. Now, instead of sending to Bob the solution +\textit{or}. Now, instead of sending to Bob the solution \textit{folio}, you send to him \textit{or}. How can Bob verify that you know the solution? Well, once he solved it himself, he can use the dictionary and follow the same ``trail'' as you did. If the final word agrees with what -you send him, he must infer you knew the solution earlier than +you had sent him, he must infer you knew the solution earlier than him. This protocol works like a one-way hash function because \textit{or} does not give any hint as to what was the first word was. I leave you to think why this protocol avoids @@ -91,7 +91,7 @@ equally it might never happen (what for example happens if the authors lose their copy of the paper because of a disk failure?). Zero-knowledge proofs, in contrast, can be -immediately be checked, even if the secret is not public yet +immediately checked, even if the secret is not public yet and never will be. \begin{figure} @@ -122,11 +122,11 @@ \end{tabular} \end{center} -\noindent Let us have a look at the picture in Step 1: The -cave has a tunnel which forks at some point. Both forks are -connected in a loop. At the deep end of the loop is a magic -wand. The point of the magic wand is that Alice knows the -secret word for how to open it. She wants to keep the word +\noindent Let us take a closer look at the picture in Step 1: +The cave has a tunnel which forks at some point. Both forks +are connected in a loop. At the deep end of the loop is a +magic wand. The point of the magic wand is that Alice knows +the secret word for how to open it. She wants to keep the word secret, but wants to convince Bob that she knows it. One way of course would be to let Bob follow her, but then he @@ -137,24 +137,28 @@ She waits at the magic wand for the instructions from Bob, who also goes into the gave and observes what happens at the fork. He has no knowledge which tunnel Alice took and calls out -(Step 2) that she should emerge from tunnel $A$. If she knows -the problem, this will not be a problem for Alice. If she was -already in the A-segment of the tunnel, then she just comes -back. If she was in the B-segment of the tunnel she will -say the magic work and goes through the want to emerge -from $A$ as requested by Bob. +(Step 2) that she should emerge from tunnel $A$, for example. +If she knows the secret for opening the wand, this will not be +a problem for Alice. If she was already in the A-segment of +the tunnel, then she just comes back. If she was in the +B-segment of the tunnel she will say the magic work and goes +through the wand to emerge from $A$ as requested by Bob. Let us have a look at the case where Alice cheats, that is not knows the secret. She would still go into the cave and use, for example the $B$-segment of the tunnel. If now Bob says she should emerge from $B$, she was lucky. But if he says she -should emerge from $A$ then Alice is in trouble and Bob will -find out she does not know the secret. So in order to fool Bob -she needs a protocol that anticipate his call, and already go -into this tunnel. +should emerge from $A$ then Alice is in trouble: Bob will find +out she does not know the secret. So in order to fool Bob she +needs to anticipate his call, and already go into this tunnel. +This of course also does not work. \subsubsection*{Using an Graph-Isomorphism Problem for ZKPs} +\subsubsection*{Using Modular Arithmetic for ZKP} + + + \end{document} %%% Local Variables: