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