45 \begin{quote} |
45 \begin{quote} |
46 ``relating to \textit{or} characteristic of humankind'' |
46 ``relating to \textit{or} characteristic of humankind'' |
47 \end{quote} |
47 \end{quote} |
48 |
48 |
49 \noindent |
49 \noindent |
50 You could go on to look up the definition of the third |
50 You could go on looking up the definition of the third |
51 non-article in this definition and so on. But let us assume |
51 non-article in this definition and so on. But let us assume |
52 you agreed with Bob to stop after three iterations with the |
52 you agreed with Bob to stop after three iterations with the |
53 third non-article word in the last definition, that is |
53 third non-article word in the last definition, that is |
54 \textit{or}. Now, instead of sending to Bob the solution |
54 \textit{or}. Now, instead of sending to Bob the solution |
55 \textit{folio}, you send to him \textit{or}. |
55 \textit{folio}, you send to him \textit{or}. |
78 By the way, the authors of the paper ``Dismantling Megamos |
78 By the way, the authors of the paper ``Dismantling Megamos |
79 Crypto: Wirelessly Lockpicking a Vehicle Immobilizer'' who |
79 Crypto: Wirelessly Lockpicking a Vehicle Immobilizer'' who |
80 were barred from publishing their results used also a hash to |
80 were barred from publishing their results used also a hash to |
81 prove they did the work and (presumably) managed to get into |
81 prove they did the work and (presumably) managed to get into |
82 cars without a key; see Figure~\ref{paper}. This is very |
82 cars without a key; see Figure~\ref{paper}. This is very |
83 similar to the method about crosswords: They like to prove |
83 similar to the method above about crosswords: They like to |
84 that they did the work, but not giving out the ``solution''. |
84 prove that they did the work, but not giving out the |
85 But this also shows what the problem with such a method is: |
85 ``solution''. But this also shows what the problem with such a |
86 yes, we can hide the secret temporarily, but if somebody else |
86 method is: yes, we can hide the secret temporarily, but if |
87 wants to verify it, then the secret has to be made public. Bob |
87 somebody else wants to verify it, then the secret has to be |
88 needs to know that \textit{folio} is the solution before he |
88 made public. Bob needs to know that \textit{folio} is the |
89 can verify the claim that somebody else had the solution |
89 solution before he can verify the claim of Alice that she had |
90 first. Similarly with the paper: we need to wait until the |
90 the solution first. Similarly with the car-crypto paper: we |
91 authors are finally allowed to publish their findings in order |
91 need to wait until the authors are finally allowed to publish |
92 to verify the hash. This might happen at some point, but |
92 their findings in order to verify the hash. This might happen |
93 equally it might never happen (what for example happens if the |
93 at some point, but equally it might never happen (what for |
94 authors lose their copy of the paper because of a disk |
94 example happens if the authors lose their copy of the paper |
95 failure?). Zero-knowledge proofs, in contrast, can be |
95 because of a disk failure?). Zero-knowledge proofs, in |
96 immediately checked, even if the secret is not public yet |
96 contrast, can be immediately checked, even if the secret is |
97 and perhaps never will be. |
97 not public yet and perhaps never will be. |
98 |
98 |
99 \begin{figure} |
99 \begin{figure} |
100 \begin{center} |
100 \begin{center} |
101 \addtolength{\fboxsep}{4mm} |
101 \addtolength{\fboxsep}{4mm} |
102 \fbox{\includegraphics[scale=0.4]{../pics/Dismantling_Megamos_Crypto.png}} |
102 \fbox{\includegraphics[scale=0.4]{../pics/Dismantling_Megamos_Crypto.png}} |
329 $H_i$ and then Bob can decide which isomorphism he wants: |
329 $H_i$ and then Bob can decide which isomorphism he wants: |
330 either $G_1 \leftrightarrow H_i$ or $G_2 \leftrightarrow H_i$. |
330 either $G_1 \leftrightarrow H_i$ or $G_2 \leftrightarrow H_i$. |
331 If somehow Alice can find out before she committed to $H_i$, |
331 If somehow Alice can find out before she committed to $H_i$, |
332 she can cheat. For this assume Alice does \emph{not} know an |
332 she can cheat. For this assume Alice does \emph{not} know an |
333 isomorphism between $G_1$ and $G_2$. If she knows which |
333 isomorphism between $G_1$ and $G_2$. If she knows which |
334 isomorphism Bob will ask for she can craft $H$ ins such a way |
334 isomorphism Bob will ask for she can craft $H$ in such a way |
335 that it is isomorphism with either $G_1$ or $G_2$ (but it |
335 that it is isomorphism with either $G_1$ or $G_2$ (but it |
336 cannot with both). Then in each case she would send Bob |
336 cannot with both). Then in each case she would send Bob |
337 a correct answer and he would come to the conclusion that |
337 a correct answer and he would come to the conclusion that |
338 all is well. I let you also answer the question whether |
338 all is well. I let you also answer the question whether |
339 such a protocol run between Alice and Bob would convince |
339 such a protocol run between Alice and Bob would convince |
405 are.\footnote{\url{http://en.wikipedia.org/wiki/NP_(complexity)}} They |
405 are.\footnote{\url{http://en.wikipedia.org/wiki/NP_(complexity)}} They |
406 are the building blocks for zero-knowledge proofs. |
406 are the building blocks for zero-knowledge proofs. |
407 |
407 |
408 \end{document} |
408 \end{document} |
409 |
409 |
|
410 http://blog.cryptographyengineering.com/2014/11/zero-knowledge-proofs-illustrated-primer.html |
|
411 |
410 http://btravers.weebly.com/uploads/6/7/2/9/6729909/zero_knowledge_technique.pdf |
412 http://btravers.weebly.com/uploads/6/7/2/9/6729909/zero_knowledge_technique.pdf |
411 http://zk-ssh.cms.ac/docs/Zero_Knowledge_Prinzipien.pdf |
413 http://zk-ssh.cms.ac/docs/Zero_Knowledge_Prinzipien.pdf |
412 http://www.wisdom.weizmann.ac.il/~oded/PS/zk-tut02v4.ps |
414 http://www.wisdom.weizmann.ac.il/~oded/PS/zk-tut02v4.ps |
413 |
415 |
414 socialist millionares problem |
416 socialist millionares problem |