|
1 \documentclass{article} |
|
2 \usepackage{../style} |
|
3 |
|
4 \begin{document} |
|
5 |
|
6 \section*{Handout 6 (Zero-Knowledge Proofs)} |
|
7 |
|
8 Zero-knowledge proofs (short ZKP) solve a paradoxical puzzle: |
|
9 How to convince somebody else that one knows a secret without, |
|
10 revealing what the secret is? This sounds like a problem the |
|
11 Mad Hatter from Alice in Wonderland would occupy himself with, |
|
12 but actually there some serious and not so serious |
|
13 applications of it. For example, if you solve crosswords with |
|
14 your friend, say Bob, you might want to convince him that you |
|
15 found a solution for one question, but of course you do not |
|
16 want to reveal the solution, as this might give Bob an |
|
17 advantage somewhere else in the crossword. So how to convince |
|
18 Bob that you know the answer (secret)? One way would be to |
|
19 come up with the following protocol: suppose the answer is |
|
20 \textit{folio}. Then look up the definition of that word in a |
|
21 dictionary. Say you find |
|
22 |
|
23 \begin{quote} |
|
24 ``an \textit{individual} leaf of paper or parchment, either |
|
25 loose as one of a series or forming part of a bound volume, |
|
26 which is numbered on the recto or front side only.'' |
|
27 \end{quote} |
|
28 |
|
29 \noindent |
|
30 Take the first non-article word in this definition, |
|
31 in this case \textit{individual}, and look up the definition |
|
32 of this word, say |
|
33 |
|
34 \begin{quote} |
|
35 ``a single \textit{human} being as distinct from a group'' |
|
36 \end{quote} |
|
37 |
|
38 \noindent |
|
39 In this definition take the second non-article word, that |
|
40 is \textit{human}, and again look up the definition of this |
|
41 word. This will yield |
|
42 |
|
43 \begin{quote} |
|
44 ``relating to \textit{or} characteristic of humankind'' |
|
45 \end{quote} |
|
46 |
|
47 \noindent |
|
48 You could now go on to look up the definition of the third |
|
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 |
|
51 third non-article word in the last definition, that is |
|
52 \textbf{or}. Now, instead of sending to Bob the solution |
|
53 \textit{folio}, you send to him \textit{or}. How can |
|
54 Bob verify that you know the solution? Well, once he solved |
|
55 it himself, he can use the dictionary and follow the same |
|
56 ``trail'' as you did. It the final word agrees with what |
|
57 you send him, he must infer you know the solution earlier |
|
58 than him. This protocol works like a one-way hash function |
|
59 because \textit{or} does not give any hint as to what was |
|
60 the first word was. I leave you to think why this |
|
61 protocol avoids article words. |
|
62 |
|
63 After Bob found his solution and verified that according to |
|
64 the protocol it ``maps'' also to \textit{or}, can he be |
|
65 entirely sure no cheating is going on. Not with 100\% |
|
66 certainty. It could have been entirely possible that |
|
67 he was given \textit{or} as the word but it derived |
|
68 from an entirely different word---this seems very unlikely, |
|
69 but is at least theoretical a possibility. Protocols |
|
70 based on zero-knowledge proofs will produce a similar |
|
71 result---they give an answer that might be erroneous |
|
72 in a very small number of cases. The point is to itterate |
|
73 them long enough so that the theoretical possibility of |
|
74 cheating is negligibly small. |
|
75 |
|
76 By the way, the authors of the paper ``Dismantling Megamos |
|
77 Crypto: Wirelessly Lockpicking a Vehicle Immobilizer'' who |
|
78 were barred from publishing their results used also a hash to |
|
79 prove they did the work and (presumably) managed to get into |
|
80 cars without a key. See Figure~\ref{paper}. This is very |
|
81 similar to the method about crosswords. They like to prove |
|
82 that they did the work, but not giving out the ``solution''. |
|
83 But this also shows what the problem with such methods |
|
84 are: yes, we can hide the secret temporarily, but if |
|
85 somebody else wants to verify it, then the secret has |
|
86 to be made public. Bob needs to know that \textit{folio} |
|
87 is the solution before he can verify the claim that somebody |
|
88 else had the solution first. Similarly with the paper: |
|
89 we need to wait until the authors are finally allowed to |
|
90 publish their finding in order to verify the hash. This |
|
91 might happen at some point, but equally it might never |
|
92 happen (what for example happens if the authors loose |
|
93 their copy of the paper because of a disk failure?). |
|
94 Zero-knowledge proofs, in contrast, can be immediately |
|
95 be checked, even if the secret is not public yet. |
|
96 |
|
97 \begin{figure} |
|
98 \begin{center} |
|
99 \fbox{\includegraphics[scale=0.4]{../pics/Dismantling_Megamos_Crypto.png}} |
|
100 \end{center} |
|
101 \caption{The authors of this paper used a hash in order to prove |
|
102 later that they have managed to break into cars.\label{paper}} |
|
103 \end{figure} |
|
104 |
|
105 |
|
106 \subsubsection*{ZKP: An Illustrative Example} |
|
107 |
|
108 The idea behind zero-knowledge proofs is not very obvious and |
|
109 will surely take some time for you to digest. Therefore |
|
110 lets start with an illustrative example. The example will |
|
111 not be perfect, but hopefully explain the gist of the ideas. |
|
112 The example is called Alibaba's cave: |
|
113 |
|
114 \begin{center} |
|
115 \begin{tabular}{c@{\hspace{8mm}}c@{\hspace{8mm}}c} |
|
116 \includegraphics[scale=0.1]{../pics/alibaba1.png} & |
|
117 \includegraphics[scale=0.1]{../pics/alibaba2.png} & |
|
118 \includegraphics[scale=0.1]{../pics/alibaba3.png} \\ |
|
119 Step 1 & Step 2 & Step 3 |
|
120 \end{tabular} |
|
121 \end{center} |
|
122 |
|
123 \noindent Lets have a look at the picture in Step 1: |
|
124 The cave is a loop where at the end is a magic wand. |
|
125 The point of the magic wand is that Alice knows the |
|
126 secret word for how to open it. She wants to keep here |
|
127 word secret, but wants to convince Bob that she knows it. |
|
128 |
|
129 |
|
130 \end{document} |
|
131 |
|
132 %%% Local Variables: |
|
133 %%% mode: latex |
|
134 %%% TeX-master: t |
|
135 %%% End: |