9 How to convince somebody else that one knows a secret without,

     9 How to convince somebody else that one knows a secret, without

    10 revealing what the secret is? This sounds like a problem the

    10 revealing what the secret actually is? This sounds like a

    11 Mad Hatter from Alice in Wonderland would occupy himself with,

    11 problem the Mad Hatter from Alice in Wonderland would occupy

    12 but actually there some serious and not so serious

    12 himself with, but actually there some serious and not so

    13 applications of it. For example, if you solve crosswords with

    13 serious applications of it. For example, if you solve

    14 your friend, say Bob, you might want to convince him that you

    14 crosswords with your friend, say Bob, you might want to

    15 found a solution for one question, but of course you do not

    15 convince him that you found a solution for one question, but

    16 want to reveal the solution, as this might give Bob an

    16 of course you do not want to reveal the solution, as this

    17 advantage somewhere else in the crossword. So how to convince

    17 might give Bob an advantage somewhere else in the crossword.

    18 Bob that you know the answer (secret)? One way would be to

    18 So how to convince Bob that you know the answer (or a secret)?

    19 come up with the following protocol: suppose the answer is

    19 One way would be to come up with the following protocol:

    20 \textit{folio}. Then look up the definition of that word in a

    20 Suppose the answer is \textit{folio}. Then look up the

    21 dictionary. Say you find

    21 definition of \textit{folio} in a dictionary. Say you find:

    48 You could now go on to look up the definition of the third

    48 You could go on to look up the definition of the third

    53 \textit{folio}, you send to him \textit{or}. How can

    53 \textit{folio}, you send to him \textit{or}. 

    54 Bob verify that you know the solution? Well, once he solved

    54 

    55 it himself, he can use the dictionary and follow the same

    55 How can Bob verify that you know the solution? Well, once he

    56 ``trail'' as you did. It the final word agrees with what 

    56 solved it himself, he can use the dictionary and follow the

    57 you send him, he must infer you know the solution earlier

    57 same ``trail'' as you did. If the final word agrees with what

    58 than him. This protocol works like a one-way hash function 

    58 you send him, he must infer you knew the solution earlier than

    59 because \textit{or} does not give any hint as to what was

    59 him. This protocol works like a one-way hash function because

    60 the first word was. I leave you to think why this

    60 \textit{or} does not give any hint as to what was the first

    61 protocol avoids article words. 

    61 word was. I leave you to think why this protocol avoids

    62 article words. 

    65 entirely sure no cheating is going on. Not with 100\%

    66 entirely sure no cheating is going on? Not with 100\%

    66 certainty. It could have been entirely possible that

    67 certainty. It could have been entirely possible that he was

    67 he was given \textit{or} as the word but it derived

    68 given \textit{or} as the word, but it derived from an entirely

    68 from an entirely different word---this seems very unlikely,

    69 different word. This might seem very unlikely, but at

    69 but is at least theoretical a possibility. Protocols

    70 least theoretical is a possibility. Protocols based on

    70 based on zero-knowledge proofs will produce a similar

    71 zero-knowledge proofs will produce a similar result---they

    71 result---they give an answer that might be erroneous 

    72 give an answer that might be erroneous in a very small number

    72 in a very small number of cases. The point is to itterate

    73 of cases. The point is to iterate them long enough so that

    73 them long enough so that the theoretical possibility of

    74 the theoretical possibility of cheating is negligibly small. 

    74 cheating is negligibly small. 

    80 cars without a key. See Figure~\ref{paper}. This is very 

    80 cars without a key; see Figure~\ref{paper}. This is very

    81 similar to the method about crosswords. They like to prove

    81 similar to the method about crosswords: They like to prove

    82 that they did the work, but not giving out the ``solution''. 

    82 that they did the work, but not giving out the ``solution''.

    83 But this also shows what the problem with such methods

    83 But this also shows what the problem with such a method is:

    84 are: yes, we can hide the secret temporarily, but if

    84 yes, we can hide the secret temporarily, but if somebody else

    85 somebody else wants to verify it, then the secret has 

    85 wants to verify it, then the secret has to be made public. Bob

    86 to be made public. Bob needs to know that \textit{folio}

    86 needs to know that \textit{folio} is the solution before he

    87 is the solution before he can verify the claim that somebody

    87 can verify the claim that somebody else had the solution

    88 else had the solution first. Similarly with the paper:

    88 first. Similarly with the paper: we need to wait until the

    89 we need to wait until the authors are finally allowed to 

    89 authors are finally allowed to publish their findings in order

    90 publish their finding in order to verify the hash. This

    90 to verify the hash. This might happen at some point, but

    91 might happen at some point, but equally it might never

    91 equally it might never happen (what for example happens if the

    92 happen (what for example happens if the authors loose

    92 authors lose their copy of the paper because of a disk

    93 their copy of the paper because of a disk failure?).

    93 failure?). Zero-knowledge proofs, in contrast, can be

    94 Zero-knowledge proofs, in contrast, can be immediately

    94 immediately be checked, even if the secret is not public yet

    95 be checked, even if the secret is not public yet.

    95 and never will be.

   109 will surely take some time for you to digest. Therefore

   110 will surely take some time for you to digest. Therefore let us

   110 lets start with an illustrative example. The example will

   111 start with a simple illustrative example. The example will not

   111 not be perfect, but hopefully explain the gist of the ideas.

   112 be perfect, but hopefully explain the gist of the idea. The

   112 The example is called Alibaba's cave:

   113 example is called Alibaba's cave, which graphically looks as 

   114 follows:

   123 \noindent Lets have a look at the picture in Step 1:

   125 \noindent Let us have a look at the picture in Step 1: The

   124 The cave is a loop where at the end is a magic wand.

   126 cave has a tunnel which forks at some point. Both forks are

   125 The point of the magic wand is that Alice knows the

   127 connected in a loop. At the deep end of the loop is a magic

   126 secret word for how to open it. She wants to keep here

   128 wand. The point of the magic wand is that Alice knows the

   127 word secret, but wants to convince Bob that she knows it.

   129 secret word for how to open it. She wants to keep the word

   130 secret, but wants to convince Bob that she knows it.

   131 

   132 One way of course would be to let Bob follow her, but then he

   133 would also find out the secret. This does not work. So let us

   134 first fix the rules: At the beginning Alice and Bob are

   135 outside the cave. Alice goes in alone and takes either tunnel

   136 labelled $A$ in the picture, or the other one labelled $B$.

   137 She waits at the magic wand for the instructions from Bob, who

   138 also goes into the gave and observes what happens at the fork.

   139 He has no knowledge which tunnel Alice took and calls out

   140 (Step 2) that she should emerge from tunnel $A$. If she knows

   141 the problem, this will not be a problem for Alice. If she was 

   142 already in the A-segment of the tunnel, then she just comes

   143 back. If she was in the B-segment of the tunnel she will

   144 say the magic work and goes through the want to emerge

   145 from $A$ as requested by Bob.

   146 

   147 Let us have a look at the case where Alice cheats, that is not

   148 knows the secret. She would still go into the cave and use,

   149 for example the $B$-segment of the tunnel. If now Bob says she

   150 should emerge from $B$, she was lucky. But if he says she

   151 should emerge from $A$ then Alice is in trouble and Bob will

   152 find out she does not know the secret. So in order to fool Bob

   153 she needs a protocol that anticipate his call, and already go

   154 into this tunnel.