283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1 |
\documentclass{article}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
2 |
\usepackage{../style}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
3 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
4 |
\begin{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
5 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
6 |
\section*{Handout 6 (Zero-Knowledge Proofs)}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
7 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
8 |
Zero-knowledge proofs (short ZKP) solve a paradoxical puzzle:
|
288
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
9 |
How to convince somebody else that one knows a secret, without
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
10 |
revealing what the secret actually is? This sounds like a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
11 |
problem the Mad Hatter from Alice in Wonderland would occupy
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
12 |
himself with, but actually there some serious and not so
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
13 |
serious applications of it. For example, if you solve
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
14 |
crosswords with your friend, say Bob, you might want to
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
15 |
convince him that you found a solution for one question, but
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
16 |
of course you do not want to reveal the solution, as this
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
17 |
might give Bob an advantage somewhere else in the crossword.
|
296
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
18 |
|
288
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
19 |
So how to convince Bob that you know the answer (or a secret)?
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
20 |
One way would be to come up with the following protocol:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
21 |
Suppose the answer is \textit{folio}. Then look up the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
22 |
definition of \textit{folio} in a dictionary. Say you find:
|
283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
23 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
24 |
\begin{quote}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
25 |
``an \textit{individual} leaf of paper or parchment, either
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
26 |
loose as one of a series or forming part of a bound volume,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
27 |
which is numbered on the recto or front side only.''
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
28 |
\end{quote}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
29 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
30 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
31 |
Take the first non-article word in this definition,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
32 |
in this case \textit{individual}, and look up the definition
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
33 |
of this word, say
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
34 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
35 |
\begin{quote}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
36 |
``a single \textit{human} being as distinct from a group''
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
37 |
\end{quote}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
38 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
39 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
40 |
In this definition take the second non-article word, that
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
41 |
is \textit{human}, and again look up the definition of this
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
42 |
word. This will yield
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
43 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
44 |
\begin{quote}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
45 |
``relating to \textit{or} characteristic of humankind''
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
46 |
\end{quote}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
47 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
48 |
\noindent
|
288
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
49 |
You could go on to look up the definition of the third
|
283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
50 |
non-article in this definition and so on. But let us assume
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
51 |
you agreed with Bob to stop after three iterations with the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
52 |
third non-article word in the last definition, that is
|
290
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
53 |
\textit{or}. Now, instead of sending to Bob the solution
|
288
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
54 |
\textit{folio}, you send to him \textit{or}.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
55 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
56 |
How can Bob verify that you know the solution? Well, once he
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
57 |
solved it himself, he can use the dictionary and follow the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
58 |
same ``trail'' as you did. If the final word agrees with what
|
290
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
59 |
you had sent him, he must infer you knew the solution earlier than
|
288
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
60 |
him. This protocol works like a one-way hash function because
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
61 |
\textit{or} does not give any hint as to what was the first
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
62 |
word was. I leave you to think why this protocol avoids
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
63 |
articles?
|
283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
64 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
65 |
After Bob found his solution and verified that according to
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
66 |
the protocol it ``maps'' also to \textit{or}, can he be
|
288
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
67 |
entirely sure no cheating is going on? Not with 100\%
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
68 |
certainty. It could have been possible that he was
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
69 |
given \textit{or} as the word, but it derived from a
|
288
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
70 |
different word. This might seem very unlikely, but at
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
71 |
least theoretical it is a possibility. Protocols based on
|
288
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
72 |
zero-knowledge proofs will produce a similar result---they
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
73 |
give an answer that might be erroneous in a very small number
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
74 |
of cases. The point is to iterate them long enough so that
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
75 |
the theoretical possibility of cheating is negligibly small.
|
283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
76 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
77 |
By the way, the authors of the paper ``Dismantling Megamos
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
78 |
Crypto: Wirelessly Lockpicking a Vehicle Immobilizer'' who
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
79 |
were barred from publishing their results used also a hash to
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
80 |
prove they did the work and (presumably) managed to get into
|
288
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
81 |
cars without a key; see Figure~\ref{paper}. This is very
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
82 |
similar to the method about crosswords: They like to prove
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
83 |
that they did the work, but not giving out the ``solution''.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
84 |
But this also shows what the problem with such a method is:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
85 |
yes, we can hide the secret temporarily, but if somebody else
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
86 |
wants to verify it, then the secret has to be made public. Bob
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
87 |
needs to know that \textit{folio} is the solution before he
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
88 |
can verify the claim that somebody else had the solution
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
89 |
first. Similarly with the paper: we need to wait until the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
90 |
authors are finally allowed to publish their findings in order
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
91 |
to verify the hash. This might happen at some point, but
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
92 |
equally it might never happen (what for example happens if the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
93 |
authors lose their copy of the paper because of a disk
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
94 |
failure?). Zero-knowledge proofs, in contrast, can be
|
290
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
95 |
immediately checked, even if the secret is not public yet
|
296
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
96 |
and perhaps never will be.
|
283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
97 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
98 |
\begin{figure}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
99 |
\begin{center}
|
288
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
100 |
\addtolength{\fboxsep}{4mm}
|
283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
101 |
\fbox{\includegraphics[scale=0.4]{../pics/Dismantling_Megamos_Crypto.png}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
102 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
103 |
\caption{The authors of this paper used a hash in order to prove
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
104 |
later that they have managed to break into cars.\label{paper}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
105 |
\end{figure}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
106 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
107 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
108 |
\subsubsection*{ZKP: An Illustrative Example}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
109 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
110 |
The idea behind zero-knowledge proofs is not very obvious and
|
288
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
111 |
will surely take some time for you to digest. Therefore let us
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
112 |
start with a simple illustrative example. The example will not
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
113 |
be perfect, but hopefully explain the gist of the idea. The
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
114 |
example is called Alibaba's cave, which graphically looks as
|
296
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
115 |
follows:\footnote{The example is taken from an
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
116 |
article titled ``How to Explain Zero-Knowledge Protocols
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
117 |
to Your Children'' available from
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
118 |
\url{http://pages.cs.wisc.edu/~mkowalcz/628.pdf}.}
|
283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
119 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
120 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
121 |
\begin{tabular}{c@{\hspace{8mm}}c@{\hspace{8mm}}c}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
122 |
\includegraphics[scale=0.1]{../pics/alibaba1.png} &
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
123 |
\includegraphics[scale=0.1]{../pics/alibaba2.png} &
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
124 |
\includegraphics[scale=0.1]{../pics/alibaba3.png} \\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
125 |
Step 1 & Step 2 & Step 3
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
126 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
127 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
128 |
|
290
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
129 |
\noindent Let us take a closer look at the picture in Step 1:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
130 |
The cave has a tunnel which forks at some point. Both forks
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
131 |
are connected in a loop. At the deep end of the loop is a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
132 |
magic wand. The point of the magic wand is that Alice knows
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
133 |
the secret word for how to open it. She wants to keep the word
|
288
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
134 |
secret, but wants to convince Bob that she knows it.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
135 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
136 |
One way of course would be to let Bob follow her, but then he
|
296
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
137 |
would also find out the secret. So this does not work. To find
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
138 |
a solution, let us first fix the rules: At the beginning Alice
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
139 |
and Bob are outside the cave. Alice goes in alone and takes
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
140 |
either tunnel labelled $A$ in the picture, or the other tunnel
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
141 |
labelled $B$. She waits at the magic wand for the instructions
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
142 |
from Bob, who also goes into the gave and observes what
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
143 |
happens at the fork. He has no knowledge which tunnel Alice
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
144 |
took and calls out (in Step 2) that she should emerge from tunnel
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
145 |
$A$, for example. If she knows the secret for opening the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
146 |
wand, this will not be a problem for Alice. If she was already
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
147 |
in the $A$-segment of the tunnel, then she just comes back. If
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
148 |
she was in the $B$-segment of the tunnel she will say the magic
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
149 |
word and goes through the wand to emerge from $A$ as requested
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
150 |
by Bob.
|
288
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
151 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
152 |
Let us have a look at the case where Alice cheats, that is not
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
153 |
knows the secret. She would still go into the cave and use,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
154 |
for example the $B$-segment of the tunnel. If now Bob says she
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
155 |
should emerge from $B$, she is lucky. But if he says she
|
290
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
156 |
should emerge from $A$ then Alice is in trouble: Bob will find
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
157 |
out she does not actually know the secret. So in order to fool
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
158 |
Bob she needs to anticipate his call, and already go into the
|
296
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
159 |
corresponding tunnel. This of course also does not work.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
160 |
Consequently in order to find out whether Alice cheats, Bob
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
161 |
just needs to repeat this protocol many times. Each time Alice
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
162 |
has a chance of $\frac{1}{2}$ to be lucky or being found out.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
163 |
Iterating this $n$ times means she must be right every time
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
164 |
and when cheating the probability for this is $\frac{1}{2}^n$.
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
165 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
166 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
167 |
There are some interesting observations we can make about
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
168 |
Alibaba's cave and the ZKP protocol between Alice and Bob:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
169 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
170 |
\begin{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
171 |
\item {\bf Completeness} If Alice knows the secret, Bob
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
172 |
accepts Alice ``proof'' for sure. There is no error
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
173 |
possbile in that Bob thinks Alice cheats when she
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
174 |
actually knows the secret.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
175 |
\item {\bf Soundness} If Alice does not know the secret,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
176 |
Bob accepts her ``proof'' with a very small probability.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
177 |
If, as in the example above, the probability of being
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
178 |
able to hide cheating is $\frac{1}{2}$ in each round
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
179 |
it will be $\frac{1}{2}^n$ after $n$-rounds, which even
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
180 |
for small $n$ say $> 10$ is very small indeed.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
181 |
\item {\bf Zero-Knowledge} Even if Bob accepts
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
182 |
the proof by Alice, he cannot convince anybody else.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
183 |
\end{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
184 |
|
296
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
185 |
\noindent The last property is the most interesting one.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
186 |
Assume Alice has convinced Bob that she knows the secret and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
187 |
Bob filmed the whole protocol with a camera. Can he use the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
188 |
video to convince anybody else? After a moment of thought, you
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
189 |
will agree that this is not the case. Alice and Bob might have
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
190 |
just made it all up and colluded by Bob telling Alice
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
191 |
beforehand which tunnel he will call. In this way it appears
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
192 |
as if all iterations of the protocol were successful, but they
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
193 |
prove nothing. If another person wants to find out whether
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
194 |
Alice knows the secret, he or she would have to conduct the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
195 |
protocol again. This is actually the formal definition of a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
196 |
zero-knowledge proof: an independent observer cannot
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
197 |
distinguish between a real protocol (where Alice knows the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
198 |
secret) and a fake one (where Bob and Alice colluded).
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
199 |
|
283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
200 |
|
289
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
201 |
\subsubsection*{Using an Graph-Isomorphism Problem for ZKPs}
|
283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
202 |
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
203 |
Now the question is how can we translate Alibaba's cave into a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
204 |
computer science solution? It turns out we need an NP problem
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
205 |
for that. The main feature of an NP problem is that it is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
206 |
computational very hard to generate a solution, but it is very
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
207 |
easy to check whether a given solution indeed solves the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
208 |
problem at hand.\footnote{The question whether $P = NP$ or not,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
209 |
we leave to others to speculate about.}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
210 |
|
295
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
211 |
One NP problem is the \emph{graph isomorphism problem}. It
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
212 |
essentially determines whether the following two graphs, say
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
213 |
$G_1$ and $G_2$, can be moved and stretched so that they look
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
214 |
exactly the same.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
215 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
216 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
217 |
\begin{tabular}{c@{\hspace{8mm}}c@{\hspace{8mm}}c}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
218 |
$G_1$ & $G_2$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
219 |
\raisebox{-13mm}{\includegraphics[scale=0.4]{../pics/simple.png}} &
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
220 |
\raisebox{-13mm}{\includegraphics[scale=0.4]{../pics/simple-b.png}}&
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
221 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
222 |
\footnotesize
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
223 |
\begin{tabular}{rl}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
224 |
Graph $G_1$ & Graph $G_2$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
225 |
a & 1\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
226 |
b & 6\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
227 |
c & 8\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
228 |
d & 3\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
229 |
g & 5\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
230 |
h & 2\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
231 |
i & 4\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
232 |
j & 7\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
233 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
234 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
235 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
236 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
237 |
\noindent The table on the right gives a mapping of the nodes
|
296
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
238 |
of the first graph to the nodes of the second. With this
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
239 |
mapping we can check: node $a$ is connected in $G_1$ with $g$,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
240 |
$h$ and $i$. Node $a$ maps to node $1$ in $G_2$, which is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
241 |
connected to $2$, $4$ and $5$, which again correspond via the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
242 |
mapping to $h$, $i$ and $g$ respectively. Let us write
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
243 |
$\sigma$ for such a table and let us write
|
295
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
244 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
245 |
\[G_1 = \sigma(G_2)\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
246 |
|
296
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
247 |
\noindent for two isomorphic graphs ($\sigma$ being the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
248 |
isomorphism). It is actually very easy to construct two
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
249 |
isomorphic graphs: Start with an arbitrary graph, re-label the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
250 |
nodes consistently. Alice will need to do this frequently
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
251 |
for the protocol below. In order to be useful, we therefore
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
252 |
would need to consider substantially larger graphs, like
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
253 |
with thousand nodes.
|
295
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
254 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
255 |
Now the secret which Alice tries to hide is the knowledge of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
256 |
such an isomorphism $\sigma$ between two such graphs. But she
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
257 |
can convince Bob whether she knows such an isomorphism for two
|
296
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
258 |
graphs using the same idea as in the example with Alibaba's
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
259 |
cave.
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
260 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
261 |
\subsubsection*{Using Modular Arithmetic for ZKP Protocols}
|
290
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
262 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
263 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
264 |
|
283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
265 |
\end{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
266 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
267 |
%%% Local Variables:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
268 |
%%% mode: latex
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
269 |
%%% TeX-master: t
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
270 |
%%% End:
|