47 \noindent |
47 \noindent |
48 You could go on to look up the definition of the third |
48 You could go on to look up the definition of the third |
49 non-article in this definition and so on. But let us assume |
49 non-article in this definition and so on. But let us assume |
50 you agreed with Bob to stop after three iterations with the |
50 you agreed with Bob to stop after three iterations with the |
51 third non-article word in the last definition, that is |
51 third non-article word in the last definition, that is |
52 \textbf{or}. Now, instead of sending to Bob the solution |
52 \textit{or}. Now, instead of sending to Bob the solution |
53 \textit{folio}, you send to him \textit{or}. |
53 \textit{folio}, you send to him \textit{or}. |
54 |
54 |
55 How can Bob verify that you know the solution? Well, once he |
55 How can Bob verify that you know the solution? Well, once he |
56 solved it himself, he can use the dictionary and follow the |
56 solved it himself, he can use the dictionary and follow the |
57 same ``trail'' as you did. If the final word agrees with what |
57 same ``trail'' as you did. If the final word agrees with what |
58 you send him, he must infer you knew the solution earlier than |
58 you had sent him, he must infer you knew the solution earlier than |
59 him. This protocol works like a one-way hash function because |
59 him. This protocol works like a one-way hash function because |
60 \textit{or} does not give any hint as to what was the first |
60 \textit{or} does not give any hint as to what was the first |
61 word was. I leave you to think why this protocol avoids |
61 word was. I leave you to think why this protocol avoids |
62 article words. |
62 article words. |
63 |
63 |
89 authors are finally allowed to publish their findings in order |
89 authors are finally allowed to publish their findings in order |
90 to verify the hash. This might happen at some point, but |
90 to verify the hash. This might happen at some point, but |
91 equally it might never happen (what for example happens if the |
91 equally it might never happen (what for example happens if the |
92 authors lose their copy of the paper because of a disk |
92 authors lose their copy of the paper because of a disk |
93 failure?). Zero-knowledge proofs, in contrast, can be |
93 failure?). Zero-knowledge proofs, in contrast, can be |
94 immediately be checked, even if the secret is not public yet |
94 immediately checked, even if the secret is not public yet |
95 and never will be. |
95 and never will be. |
96 |
96 |
97 \begin{figure} |
97 \begin{figure} |
98 \begin{center} |
98 \begin{center} |
99 \addtolength{\fboxsep}{4mm} |
99 \addtolength{\fboxsep}{4mm} |
120 \includegraphics[scale=0.1]{../pics/alibaba3.png} \\ |
120 \includegraphics[scale=0.1]{../pics/alibaba3.png} \\ |
121 Step 1 & Step 2 & Step 3 |
121 Step 1 & Step 2 & Step 3 |
122 \end{tabular} |
122 \end{tabular} |
123 \end{center} |
123 \end{center} |
124 |
124 |
125 \noindent Let us have a look at the picture in Step 1: The |
125 \noindent Let us take a closer look at the picture in Step 1: |
126 cave has a tunnel which forks at some point. Both forks are |
126 The cave has a tunnel which forks at some point. Both forks |
127 connected in a loop. At the deep end of the loop is a magic |
127 are connected in a loop. At the deep end of the loop is a |
128 wand. The point of the magic wand is that Alice knows the |
128 magic wand. The point of the magic wand is that Alice knows |
129 secret word for how to open it. She wants to keep the word |
129 the secret word for how to open it. She wants to keep the word |
130 secret, but wants to convince Bob that she knows it. |
130 secret, but wants to convince Bob that she knows it. |
131 |
131 |
132 One way of course would be to let Bob follow her, but then he |
132 One way of course would be to let Bob follow her, but then he |
133 would also find out the secret. This does not work. So let us |
133 would also find out the secret. This does not work. So let us |
134 first fix the rules: At the beginning Alice and Bob are |
134 first fix the rules: At the beginning Alice and Bob are |
135 outside the cave. Alice goes in alone and takes either tunnel |
135 outside the cave. Alice goes in alone and takes either tunnel |
136 labelled $A$ in the picture, or the other one labelled $B$. |
136 labelled $A$ in the picture, or the other one labelled $B$. |
137 She waits at the magic wand for the instructions from Bob, who |
137 She waits at the magic wand for the instructions from Bob, who |
138 also goes into the gave and observes what happens at the fork. |
138 also goes into the gave and observes what happens at the fork. |
139 He has no knowledge which tunnel Alice took and calls out |
139 He has no knowledge which tunnel Alice took and calls out |
140 (Step 2) that she should emerge from tunnel $A$. If she knows |
140 (Step 2) that she should emerge from tunnel $A$, for example. |
141 the problem, this will not be a problem for Alice. If she was |
141 If she knows the secret for opening the wand, this will not be |
142 already in the A-segment of the tunnel, then she just comes |
142 a problem for Alice. If she was already in the A-segment of |
143 back. If she was in the B-segment of the tunnel she will |
143 the tunnel, then she just comes back. If she was in the |
144 say the magic work and goes through the want to emerge |
144 B-segment of the tunnel she will say the magic work and goes |
145 from $A$ as requested by Bob. |
145 through the wand to emerge from $A$ as requested by Bob. |
146 |
146 |
147 Let us have a look at the case where Alice cheats, that is not |
147 Let us have a look at the case where Alice cheats, that is not |
148 knows the secret. She would still go into the cave and use, |
148 knows the secret. She would still go into the cave and use, |
149 for example the $B$-segment of the tunnel. If now Bob says she |
149 for example the $B$-segment of the tunnel. If now Bob says she |
150 should emerge from $B$, she was lucky. But if he says she |
150 should emerge from $B$, she was lucky. But if he says she |
151 should emerge from $A$ then Alice is in trouble and Bob will |
151 should emerge from $A$ then Alice is in trouble: Bob will find |
152 find out she does not know the secret. So in order to fool Bob |
152 out she does not know the secret. So in order to fool Bob she |
153 she needs a protocol that anticipate his call, and already go |
153 needs to anticipate his call, and already go into this tunnel. |
154 into this tunnel. |
154 This of course also does not work. |
155 |
155 |
156 \subsubsection*{Using an Graph-Isomorphism Problem for ZKPs} |
156 \subsubsection*{Using an Graph-Isomorphism Problem for ZKPs} |
|
157 |
|
158 \subsubsection*{Using Modular Arithmetic for ZKP} |
|
159 |
|
160 |
157 |
161 |
158 \end{document} |
162 \end{document} |
159 |
163 |
160 %%% Local Variables: |
164 %%% Local Variables: |
161 %%% mode: latex |
165 %%% mode: latex |