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}
|
495
|
5 |
\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015}
|
283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
6 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
7 |
\section*{Handout 6 (Zero-Knowledge Proofs)}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
8 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
9 |
Zero-knowledge proofs (short ZKP) solve a paradoxical puzzle:
|
288
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
10 |
How to convince somebody else that one knows a secret, without
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
11 |
revealing what the secret actually is? This sounds like a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
12 |
problem the Mad Hatter from Alice in Wonderland would occupy
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
13 |
himself with, but actually there some serious and not so
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
14 |
serious applications of it. For example, if you solve
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
15 |
crosswords with your friend, say Bob, you might want to
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
16 |
convince him that you found a solution for one question, but
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
17 |
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
|
18 |
might give Bob an advantage somewhere else in the crossword.
|
296
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
19 |
|
288
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
20 |
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
|
21 |
One way would be to come up with the following protocol:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
22 |
Suppose the answer is \textit{folio}. Then look up the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
23 |
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
|
24 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
25 |
\begin{quote}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
26 |
``an \textit{individual} leaf of paper or parchment, either
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
27 |
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
|
28 |
which is numbered on the recto or front side only.''
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
29 |
\end{quote}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
30 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
31 |
\noindent
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
32 |
Take the first non-small word\footnote{Let's say the, a, an,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
33 |
or, and \ldots fall into the category of small words.} in this definition,
|
283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
34 |
in this case \textit{individual}, and look up the definition
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
35 |
of this word, say
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
36 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
37 |
\begin{quote}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
38 |
``a single \textit{human} being as distinct from a group''
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
39 |
\end{quote}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
40 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
41 |
\noindent
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
42 |
In this definition take the second non-small word, that
|
283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
43 |
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
|
44 |
word. This will yield
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
45 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
46 |
\begin{quote}
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
47 |
``relating to or \textit{characteristic} of humankind''
|
283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
48 |
\end{quote}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
49 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
50 |
\noindent
|
370
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
51 |
You could go on looking up the definition of the third
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
52 |
non-small word in this definition and so on. But let us assume
|
283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
53 |
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
|
54 |
third non-article word in the last definition, that is
|
290
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
55 |
\textit{or}. Now, instead of sending to Bob the solution
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
56 |
\textit{folio}, you send to him \textit{characteristic}.
|
288
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
57 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
58 |
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
|
59 |
solved it himself, he can use the dictionary and follow the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
60 |
same ``trail'' as you did. If the final word agrees with what
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
61 |
you had sent him, he must infer you knew the solution earlier
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
62 |
than him. This protocol works like a one-way hash function
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
63 |
because \textit{characteristic} does not give any hint as to
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
64 |
what was the first word was. I leave you to think why this
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
65 |
protocol avoids small words?
|
283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
66 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
67 |
After Bob found his solution and verified that according to
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
68 |
the protocol it ``maps'' also to \textit{characteristic}, can
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
69 |
he be entirely sure no cheating is going on? Not with 100\%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
70 |
certainty. It could have been possible that he was given
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
71 |
\textit{characteristic} as the word, but it derived from a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
72 |
different word. This might seem very unlikely, but at least
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
73 |
theoretical it is a possibility. Protocols based on
|
288
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
74 |
zero-knowledge proofs will produce a similar result---they
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
75 |
give an answer that might be erroneous in a very small number
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
76 |
of cases. The point is to iterate them long enough so that the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
77 |
theoretical possibility of cheating is negligibly small.
|
283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
78 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
79 |
By the way, the authors of the paper ``Dismantling Megamos
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
80 |
Crypto: Wirelessly Lockpicking a Vehicle Immobilizer'' who
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
81 |
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
|
82 |
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
|
83 |
cars without a key; see Figure~\ref{paper}. This is very
|
370
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
84 |
similar to the method above about crosswords: They like to
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
85 |
prove that they did the work, but not giving out the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
86 |
``solution''. But this also shows what the problem with such a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
87 |
method is: yes, we can hide the secret temporarily, but if
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
88 |
somebody else wants to verify it, then the secret has to be
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
89 |
made public. Bob needs to know that \textit{folio} is the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
90 |
solution before he can verify the claim of Alice that she had
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
91 |
the solution first. Similarly with the car-crypto paper: we
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
92 |
needed to wait until September 2015 when the authors were
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
93 |
finally able to publish their findings in order to verify the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
94 |
hash. Zero-knowledge proofs, in contrast, can be immediately
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
95 |
checked, even if the secret is not public yet and perhaps
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
96 |
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
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
159 |
corresponding tunnel. This of course also does not work, since
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
160 |
Bob can make any call he wants. Consequently in order to find
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
161 |
out whether Alice cheats, Bob just needs to repeat this
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
162 |
protocol many times. Each time Alice has a chance of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
163 |
$\frac{1}{2}$ to be lucky or being found out. Iterating this
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
164 |
$n$ times means she must be right every time and when
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
165 |
cheating: the probability for this is $\frac{1}{2}^n$, number
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
166 |
that for already relatively small $n$, say 10, is incredibly
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
167 |
small.
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
168 |
|
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 |
There are some interesting observations we can make about
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
171 |
Alibaba's cave and the ZKP protocol between Alice and Bob:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
172 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
173 |
\begin{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
174 |
\item {\bf Completeness} If Alice knows the secret, Bob
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
175 |
accepts Alice ``proof'' for sure. There is no error
|
297
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
176 |
possible in that Bob thinks Alice cheats when she
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
177 |
actually knows the secret.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
178 |
\item {\bf Soundness} If Alice does not know the secret,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
179 |
Bob accepts her ``proof'' with a very small probability.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
180 |
If, as in the example above, the probability of being
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
181 |
able to hide cheating is $\frac{1}{2}$ in each round
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
182 |
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
|
183 |
for small $n$ say $> 10$ is very small indeed.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
184 |
\item {\bf Zero-Knowledge} Even if Bob accepts
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
185 |
the proof by Alice, he cannot convince anybody else.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
186 |
\end{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
187 |
|
296
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
188 |
\noindent The last property is the most interesting one.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
189 |
Assume Alice has convinced Bob that she knows the secret and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
190 |
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
|
191 |
video to convince anybody else? After a moment of thought, you
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
192 |
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
|
193 |
just made it all up and colluded by Bob telling Alice
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
194 |
beforehand which tunnel he will call. In this way it appears
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
195 |
as if all iterations of the protocol were successful, but they
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
196 |
prove nothing. If another person wants to find out whether
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
197 |
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
|
198 |
protocol again. This is actually the formal definition of a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
199 |
zero-knowledge proof: an independent observer cannot
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
200 |
distinguish between a real protocol (where Alice knows the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
201 |
secret) and a fake one (where Bob and Alice colluded).
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
202 |
|
283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
203 |
|
289
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
204 |
\subsubsection*{Using an Graph-Isomorphism Problem for ZKPs}
|
283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
205 |
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
206 |
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
|
207 |
computer science solution? It turns out we need an NP problem
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
208 |
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
|
209 |
computational very hard to generate a solution, but it is very
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
210 |
easy to check whether a given solution indeed solves the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
211 |
problem at hand.\footnote{The question whether $P = NP$ or not,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
212 |
we leave to others to speculate about.}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
213 |
|
295
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
214 |
One NP problem is the \emph{graph isomorphism problem}. It
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
215 |
essentially determines whether the following two graphs, say
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
216 |
$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
|
217 |
exactly the same.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
218 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
219 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
220 |
\begin{tabular}{c@{\hspace{8mm}}c@{\hspace{8mm}}c}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
221 |
$G_1$ & $G_2$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
222 |
\raisebox{-13mm}{\includegraphics[scale=0.4]{../pics/simple.png}} &
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
223 |
\raisebox{-13mm}{\includegraphics[scale=0.4]{../pics/simple-b.png}}&
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
224 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
225 |
\footnotesize
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
226 |
\begin{tabular}{rl}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
227 |
Graph $G_1$ & Graph $G_2$\\
|
419
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
228 |
a & 1\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
229 |
b & 6\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
230 |
c & 8\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
231 |
d & 3\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
232 |
g & 5\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
233 |
h & 2\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
234 |
i & 4\\
|
295
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
235 |
j & 7\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
236 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
237 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
238 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
239 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
240 |
\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
|
241 |
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
|
242 |
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
|
243 |
$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
|
244 |
connected to $2$, $4$ and $5$, which again correspond via the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
245 |
mapping to $h$, $i$ and $g$ respectively. Let us write
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
246 |
$\sigma$ for such a table and let us write
|
295
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
247 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
248 |
\[G_1 = \sigma(G_2)\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
249 |
|
296
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
250 |
\noindent for two isomorphic graphs ($\sigma$ being the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
251 |
isomorphism). It is actually very easy to construct two
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
252 |
isomorphic graphs: Start with an arbitrary graph, re-label the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
253 |
nodes consistently. Alice will need to do this frequently
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
254 |
for the protocol below. In order to be useful, we therefore
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
255 |
would need to consider substantially larger graphs, like
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
256 |
with thousand nodes.
|
295
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
257 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
258 |
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
|
259 |
such an isomorphism $\sigma$ between two such graphs. But she
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
260 |
can convince Bob whether she knows such an isomorphism for two
|
297
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
261 |
graphs, say $G_1$ and $G_2$, using the same idea as in the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
262 |
example with Alibaba's cave. For this Alice and Bob must
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
263 |
follow the following protocol:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
264 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
265 |
\begin{enumerate}
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
266 |
\item Alice generates an isomorphic graph $H$ which she sends
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
267 |
to Bob (in each iteration she needs to generate a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
268 |
different $H$).
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
269 |
\item
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
270 |
After receiving $H$, Bob asks Alice either for an
|
297
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
271 |
isomorphism between $G_1$ and $H$, or $G_2$ and $H$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
272 |
\item Alice and Bob repeat this procedure $n$ times.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
273 |
\end{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
274 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
275 |
\noindent In Step 1 it is important that Alice always
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
276 |
generates a fresh isomorphic graph. I let you think what
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
277 |
would happen if Alice sends out twice the same graph $H$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
278 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
279 |
As said before, this is relatively easy to generate by
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
280 |
consistently relabelling nodes. If she started from $G_1$,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
281 |
Alice will have generated
|
297
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
282 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
283 |
\begin{equation}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
284 |
H = \sigma'(G_1)\label{hiso}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
285 |
\end{equation}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
286 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
287 |
\noindent where $\sigma'$ is the isomorphism between $H$ and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
288 |
$G_1$. But she could equally have started from $G_2$. In the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
289 |
case where $G_1$ and $G_2$ are isomorphic, if $H$ is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
290 |
isomorphic with $G_1$, it will also be isomorphic with
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
291 |
$G_2$, and vice versa.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
292 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
293 |
After generating $H$, Alice sends it to Bob. The important
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
294 |
point is that she needs to ``commit'' to this $H$, therefore
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
295 |
this kind of zero-knowledge protocols are called
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
296 |
\emph{commitment protocols}. Only after receiving $H$, Bob
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
297 |
will make up his mind about which isomorphism he asks
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
298 |
for---whether between $H$ and $G_1$ or $H$ and $G_2$. For this
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
299 |
he could flip a coin, since the choice should be as
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
300 |
unpredictable for Alice as possible. Once Alice receives the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
301 |
request, she has to produce an isomorphism. If she generated
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
302 |
$H$ as shown in \eqref{hiso} and is asked for an isomorphism
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
303 |
between $H$ and $G_1$, she just sends $\sigma'$. If she had
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
304 |
been asked for an isomorphism between $H$ and $G_2$, she just
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
305 |
has to compose her secret isomorphism $\sigma$ and $\sigma'$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
306 |
The main point for the protocol is that even knowing the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
307 |
isomorphism between $H$ and $G_1$ or $H$ and $G_2$, will not
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
308 |
make the task easier to find the isomorphism between $G_1$ and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
309 |
$G_2$, which is the secret Alice tries to protect.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
310 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
311 |
In order to make it crystal clear how this protocol proceeds,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
312 |
let us give a version using our more formal notation for
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
313 |
protocols:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
314 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
315 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
316 |
\begin{tabular}{lrl}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
317 |
0) & $A \to B:$ & $G_1$ and $G_2$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
318 |
1a) & $A \to B:$ & $H_1$ \\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
319 |
1b) & $B \to A:$ & produce isomorphism $G_1 \leftrightarrow H_1$?
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
320 |
\quad(or $G_2 \leftrightarrow H_1$)\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
321 |
1c) & $A \to B:$ & requested isomorphism\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
322 |
2a) & $A \to B:$ & $H_2$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
323 |
2b) & $B \to A:$ & produce isomorphism $G_1 \leftrightarrow H_2$?
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
324 |
\quad(or $G_2 \leftrightarrow H_2$)\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
325 |
2c) & $A \to B:$ & requested isomorphism\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
326 |
& \ldots\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
327 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
328 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
329 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
330 |
\noindent As can be seen the protocol runs for some
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
331 |
agreed number of iterations. The $H_i$ Alice needs to
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
332 |
produce, need to be all distinct. I hope you now know
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
333 |
why?
|
297
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
334 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
335 |
It is also crucial that in each iteration, Alice first sends
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
336 |
$H_i$ and then Bob can decide which isomorphism he wants:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
337 |
either $G_1 \leftrightarrow H_i$ or $G_2 \leftrightarrow H_i$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
338 |
If somehow Alice can find out before she committed to $H_i$,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
339 |
she can cheat. For this assume Alice does \emph{not} know an
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
340 |
isomorphism between $G_1$ and $G_2$. If she knows which
|
370
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
341 |
isomorphism Bob will ask for she can craft $H$ in such a way
|
297
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
342 |
that it is isomorphism with either $G_1$ or $G_2$ (but it
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
343 |
cannot with both). Then in each case she would send Bob
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
344 |
a correct answer and he would come to the conclusion that
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
345 |
all is well. I let you also answer the question whether
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
346 |
such a protocol run between Alice and Bob would convince
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
347 |
a third person, say Pete.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
348 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
349 |
Since the interactive nature of the above PKZ protocol and the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
350 |
correct ordering of the messages is so important for the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
351 |
``correctness'' of the protocol, it might look surprising that
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
352 |
the same goal can also me achieved in a completely offline
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
353 |
manner. By this I mean Alice can publish all data at once, and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
354 |
then at a later time, Bob can inspect the data and come to the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
355 |
conclusion whether or not Alice knows the secret (again
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
356 |
without actually learning about the secret). For this
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
357 |
Alice has to do the following:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
358 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
359 |
\begin{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
360 |
\item Alice generates $n$ isomorphic graphs
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
361 |
$H_{1..n}$ (they need to be all distinct)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
362 |
\item she feeds the $H_{1..n}$ into a hashing function
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
363 |
(for example encoded as as matrix)
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
364 |
\item she takes the first $n$ bits of the output of the hashing
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
365 |
function:
|
297
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
366 |
whenever the output is $0$, she shows an isomorphism
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
367 |
with $G_1$; for $1$ she shows an isomorphism
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
368 |
with $G_2$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
369 |
\end{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
370 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
371 |
\noindent The reason why this works and achieves the same
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
372 |
goal as the interactive variant is that Alice has no
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
373 |
control over the hashing function. It would be
|
297
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
374 |
computationally just too hard to assemble a set of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
375 |
$H_{1..n}$ such that she can force where $0$s and $1$s
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
376 |
in the hash values are such that it would pass an external
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
377 |
test. The point is that Alice can publish all this data
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
378 |
on the comfort of her own web-page, for example, and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
379 |
in this way convince everybody who bothers to check.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
380 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
381 |
The virtue of the use of graphs and isomorphism for a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
382 |
zero-knowledge protocol is that the idea why it works
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
383 |
are relatively straightforward. The disadvantage is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
384 |
that encoding any secret into a graph-isomorphism, while
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
385 |
possible, is awkward. The good news is that in fact
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
386 |
any NP problem can be used as part of a ZKP protocol.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
387 |
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
388 |
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
389 |
\subsubsection*{Using Modular Logarithms for ZKP Protocols}
|
290
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
390 |
|
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
391 |
While information can be encoded into graph isomorphisms, it
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
392 |
is not the most convenient carrier of information. Clearly it
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
393 |
is much easier to encode information into numbers. Let us look
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
394 |
at zero-knowledge proofs that use numbers as secrets. For this
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
395 |
the underlying NP-problem is to calculate discrete logarithms.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
396 |
It can be used by choosing public numbers $A$, $B$, $p$, and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
397 |
private $x$ such that
|
297
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
398 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
399 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
400 |
$A^x \equiv B\; mod\; p$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
401 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
402 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
403 |
\noindent holds. The secret Alice tries to keep secret is $x$.
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
404 |
The point of the modular logarithm is that it is very hard
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
405 |
from the public data to calculate $x$ (for large primes).
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
406 |
Now the protocol proceeds in three stages:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
407 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
408 |
\begin{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
409 |
\item {\bf Commitment Stage}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
410 |
\begin{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
411 |
\item Alice generates $z$ random numbers $r_1, \ldots, r_z$,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
412 |
all less than $p - 1$. Alice then sends Bob for all
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
413 |
$i = 1,\ldots, z$:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
414 |
\[ h_i = A^{r_i}\; mod\; p\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
415 |
\item Bob generates $z$ random bits, say $b_1,\ldots, b_z$. He can do this
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
416 |
by flipping $z$ times a coin, for example.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
417 |
\item For each bit $b_i$, Alice sends Bob an $s_i$ where
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
418 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
419 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
420 |
\begin{tabular}{ll}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
421 |
if $b_i = 0$: & $s_i = r_i$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
422 |
if $b_i = 1$: & $s_i = (r_i - r_j) \;mod\; (p -1)$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
423 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
424 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
425 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
426 |
where $r_j$ is the lowest $j$ where $b_j = 1$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
427 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
428 |
\end{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
429 |
\end{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
430 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
431 |
\noindent For understanding the last step, let $z$ be just 4.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
432 |
We have four random values $r_i$ chosen by Alice and four
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
433 |
random bits $b_i$ chosen subsequently by Bob, for example
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
434 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
435 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
436 |
\begin{tabular}{lcccc}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
437 |
$r_i$:\; & 4 & 9 & 1 & 3\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
438 |
$b_i$:\; & 0 & 1 & 0 & 1\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
439 |
& & $\uparrow$ \\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
440 |
& & $j$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
441 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
442 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
443 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
444 |
\noindent The highlighted column is the lowest where $b_i =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
445 |
1$ (counted from the left). That means $r_j = 9$. The reason
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
446 |
for letting Alice choose the random numbers $r_1, \ldots, r_z$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
447 |
will become clear shortly. Next is the confirmation
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
448 |
phase where Bob essentially checks whether Alice has sent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
449 |
him ``correct'' $s_i$ and $h_i$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
450 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
451 |
\begin{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
452 |
\item {\bf Confirmation Stage}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
453 |
\begin{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
454 |
\item For each $b_i$ Bob checks whether $s_i$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
455 |
conform to the protocol
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
456 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
457 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
458 |
\begin{tabular}{ll}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
459 |
if $b_i = 0$: & $A^{s_i} \stackrel{?}{\equiv} h_i\;mod\;p$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
460 |
if $b_i = 1$: & $A^{s_i} \stackrel{?}{\equiv} h_i * h_j^{-1} \;mod\; p$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
461 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
462 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
463 |
\end{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
464 |
\end{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
465 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
466 |
\noindent To understand the case for $b_i = 1$, you have
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
467 |
to do the following calculation:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
468 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
469 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
470 |
\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
471 |
$A^{s_i}$ & $=$ & $A^{r_i - r_j}$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
472 |
& $=$ & $A^{r_i} * A^{-r_j}$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
473 |
& $=$ & $h_{r_i} * h_{r_j}^{-1}\;mod\;p$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
474 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
475 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
476 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
477 |
\noindent What is interesting that so far nothing has been
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
478 |
sent about $x$, which is the secret Alice has. Also notice
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
479 |
that Bob does not know $r_j$. He received
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
480 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
481 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
482 |
$r_j - r_j$, $r_m - r_j$, \ldots, $r_p - r_j \;mod \;p - 1$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
483 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
484 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
485 |
\noindent whenever his corresponding bits were $1$. So Bob
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
486 |
does not know $r_j$ and also does not know any $r_i$ where the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
487 |
bit was $1$. Information about the $x$ is sent in the next
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
488 |
stage (obviously not revealing $x$).
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
489 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
490 |
\begin{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
491 |
\item {\bf Proving Stage}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
492 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
493 |
\begin{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
494 |
\item Alice proves she knows $x$, the discrete log of $B$,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
495 |
by sending
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
496 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
497 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
498 |
$s_{z+1} = x - r_j\;mod\;p-1$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
499 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
500 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
501 |
\item Bob confirms
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
502 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
503 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
504 |
$A^{s_{z+1}} \stackrel{?}{\equiv} B * h_j^{-1} \;mod \; p$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
505 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
506 |
\end{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
507 |
\end{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
508 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
509 |
\noindent To understand the last step, you have to do the trick
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
510 |
again that
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
511 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
512 |
\[A^{s_{z+1}} = A^{x-r_j} = \ldots
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
513 |
\]
|
297
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
514 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
515 |
\noindent
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
516 |
which I leave to you.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
517 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
518 |
Now the question is how can Alice cheat? In order to cheat she
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
519 |
has to coordinate what she sends as $h_i$ in step 1 and $s_i$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
520 |
in step 3 of the commitment stage, and also what to send as
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
521 |
$s_{z+1}$ in the proving stage. For the latter of course
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
522 |
Alice does not know $x$, so she just chooses some random
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
523 |
number for $s_{z+1}$ and calculates
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
524 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
525 |
\[A^{s_{z+1}}\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
526 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
527 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
528 |
and then solves the equation
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
529 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
530 |
\[A^{s_{z+1}} \equiv B * y \;mod\;p\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
531 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
532 |
\noindent for $y$. This is easy since no logarithm needs to be
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
533 |
computed. If Alice can guess the $j$ where the first 1 will
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
534 |
appear in Bob's bit vector, then she sends the inverse of $y$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
535 |
as $h_j$ and 0 as $s_j$. However, notice that when she
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
536 |
calculates a solution for $y$ she does not know $r_j$. For this she
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
537 |
would need to calculate the modular logarithm
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
538 |
|
436
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
539 |
\[y \equiv A^{r_j}\;mod\;p\]
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
540 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
541 |
\noindent which is hard (see step 1 in the commitment stage).
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
542 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
543 |
Having settled on what $h_j$ should be, now what should Alice
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
544 |
send as the other $h_i$ and other $s_i$? If the $b_i$ happens
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
545 |
to be a 1, then the $h_i$ and other $s_i$ need to satisfy the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
546 |
test
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
547 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
548 |
\[A^{s_i} \stackrel{?}{\equiv} h_i * h_j^{-1} \;mod\; p\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
549 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
550 |
\noindent where she has already settled on the value of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
551 |
$h_j^{-1}$. Lets say she choses $s_i$ at random, then she just
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
552 |
needs to solve
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
553 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
554 |
\[A^{s_i} \equiv z * h_j^{-1} \;mod\; p\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
555 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
556 |
\noindent for $z$. Again that is easy, but it does not allow
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
557 |
us to know $r_i$, because then we would again need to solve
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
558 |
a modular logarithm problem. Let us call an $h_i$ which was
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
559 |
solved the easy way as \emph{bogus}. Alice has to produce
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
560 |
bogus $h_i$ for all bits that are going to be $1$ in advance!
|
435
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
561 |
This means she has to guess all the bits correctly. (Yes?
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
562 |
I let you think about this.)
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
563 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
564 |
Let us see what happens if she guesses wrongly: Suppose the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
565 |
bit $b_i = 1$ where she thought she will get a 0. Then she has
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
566 |
already sent an $h_i$ and $h_j$ and now must find an $s_i$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
567 |
such that
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
568 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
569 |
\[A^{s_i} \equiv h_i * h_j^{-1} \;mod\; p\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
570 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
571 |
\noindent holds. For this remember in calculating $h_i$, she
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
572 |
just chose a random $s_i$. Now she has to send a genuine one.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
573 |
But this is of course too hard. If she knew the genuine $r_i$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
574 |
and $r_j$ for $h_i$ and $h_j$, it would be easy (in this case
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
575 |
$s_i = r_i - r_j$). But she does not. So she will be found
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
576 |
out. If $b_i = 0$, but she thought she will get a 1, then
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
577 |
she has to send a $s_i$ which satisfies
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
578 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
579 |
\[A^{s_i} \equiv h_i\;mod\;p\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
580 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
581 |
\noindent Again she does not know $r_i$. So it is a too hard
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
582 |
task and she will be found out again.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
583 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
584 |
To sum up, in order for Alice to successfully cheat Bob, she
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
585 |
needs to guess \emph{all} bits correctly. She has only a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
586 |
$\frac{1}{2^z}$ chance of doing this.
|
290
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
587 |
|
357
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
588 |
\subsubsection*{Further Reading}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
589 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
590 |
Make sure you understand what NP problems
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
591 |
are.\footnote{\url{http://en.wikipedia.org/wiki/NP_(complexity)}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
592 |
They are the building blocks for zero-knowledge proofs.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
593 |
Zero-Knowldege proofs are not yet widely used in production
|
423
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
594 |
systems, but it is slowly gaining ground. One area of application
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
595 |
where they pop up is crypto currencies (for example Zerocoins
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
596 |
or how to make sure a Bitcoin exchange is solvent without
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
597 |
revealing its assets).
|
422
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
598 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
599 |
If you want to brush up on the modular logarithm problem,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
600 |
the Khan Academy has a nice video:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
601 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
602 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
603 |
\url{https://www.khanacademy.org/video/discrete-logarithm-problem}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
604 |
\end{center}
|
290
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
605 |
|
283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
606 |
\end{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
607 |
|
370
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
608 |
http://blog.cryptographyengineering.com/2014/11/zero-knowledge-proofs-illustrated-primer.html
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
609 |
|
297
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
610 |
http://btravers.weebly.com/uploads/6/7/2/9/6729909/zero_knowledge_technique.pdf
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
611 |
http://zk-ssh.cms.ac/docs/Zero_Knowledge_Prinzipien.pdf
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
612 |
http://www.wisdom.weizmann.ac.il/~oded/PS/zk-tut02v4.ps
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
613 |
|
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
614 |
socialist millionares problem
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
615 |
http://en.wikipedia.org/wiki/Socialist_millionaire
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
616 |
http://twistedoakstudios.com/blog/Post3724_explain-it-like-im-five-the-socialist-millionaire-problem-and-secure-multi-party-computation
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
617 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
618 |
|
283
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
619 |
%%% Local Variables:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
620 |
%%% mode: latex
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
621 |
%%% TeX-master: t
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
622 |
%%% End:
|