# HG changeset patch # User Christian Urban # Date 1415188865 0 # Node ID 40511897fcc46a568ca6b8a07bcf3333bed56012 # Parent 4a0071e26cb506773297312d24a865bd7eac1dff updated diff -r 4a0071e26cb5 -r 40511897fcc4 handouts/ho03.pdf Binary file handouts/ho03.pdf has changed diff -r 4a0071e26cb5 -r 40511897fcc4 handouts/ho03.tex --- a/handouts/ho03.tex Tue Nov 04 12:35:41 2014 +0000 +++ b/handouts/ho03.tex Wed Nov 05 12:01:05 2014 +0000 @@ -3,7 +3,6 @@ \usepackage{../langs} \usepackage{../graphics} \usepackage{../data} -\usetikzlibrary{patterns,decorations.pathreplacing} \begin{document} diff -r 4a0071e26cb5 -r 40511897fcc4 handouts/ho04.pdf Binary file handouts/ho04.pdf has changed diff -r 4a0071e26cb5 -r 40511897fcc4 handouts/ho04.tex --- a/handouts/ho04.tex Tue Nov 04 12:35:41 2014 +0000 +++ b/handouts/ho04.tex Wed Nov 05 12:01:05 2014 +0000 @@ -2,8 +2,6 @@ \usepackage{../style} \usepackage{../langs} -\usetikzlibrary{patterns,decorations.pathreplacing} - \begin{document} \section*{Handout 4 (Access Control)} diff -r 4a0071e26cb5 -r 40511897fcc4 handouts/ho05.pdf Binary file handouts/ho05.pdf has changed diff -r 4a0071e26cb5 -r 40511897fcc4 handouts/ho05.tex --- a/handouts/ho05.tex Tue Nov 04 12:35:41 2014 +0000 +++ b/handouts/ho05.tex Wed Nov 05 12:01:05 2014 +0000 @@ -1,7 +1,6 @@ \documentclass{article} \usepackage{../style} \usepackage{../langs} -\usetikzlibrary{patterns,decorations.pathreplacing} \begin{document} @@ -808,8 +807,8 @@ An article in The Guardien from 2013 reveals how GCHG and the NSA at a G20 Summit in 2009 sniffed emails from Internet cafes, monitored phone -calls from delegates and attempted to listen on Russians phone calls -which were transmitted via satelite links: +calls from delegates and attempted to listen on phone calls which were made +by Russions and which were transmitted via satelite links: \begin{center} \url{http://www.theguardian.com/uk/2013/jun/16/gchq-intercepted-communications-g20-summits} diff -r 4a0071e26cb5 -r 40511897fcc4 handouts/ho06.pdf Binary file handouts/ho06.pdf has changed diff -r 4a0071e26cb5 -r 40511897fcc4 handouts/ho06.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/handouts/ho06.tex Wed Nov 05 12:01:05 2014 +0000 @@ -0,0 +1,135 @@ +\documentclass{article} +\usepackage{../style} + +\begin{document} + +\section*{Handout 6 (Zero-Knowledge Proofs)} + +Zero-knowledge proofs (short ZKP) solve a paradoxical puzzle: +How to convince somebody else that one knows a secret without, +revealing what the secret is? This sounds like a problem the +Mad Hatter from Alice in Wonderland would occupy himself with, +but actually there some serious and not so serious +applications of it. For example, if you solve crosswords with +your friend, say Bob, you might want to convince him that you +found a solution for one question, but of course you do not +want to reveal the solution, as this might give Bob an +advantage somewhere else in the crossword. So how to convince +Bob that you know the answer (secret)? One way would be to +come up with the following protocol: suppose the answer is +\textit{folio}. Then look up the definition of that word in a +dictionary. Say you find + +\begin{quote} +``an \textit{individual} leaf of paper or parchment, either +loose as one of a series or forming part of a bound volume, +which is numbered on the recto or front side only.'' +\end{quote} + +\noindent +Take the first non-article word in this definition, +in this case \textit{individual}, and look up the definition +of this word, say + +\begin{quote} +``a single \textit{human} being as distinct from a group'' +\end{quote} + +\noindent +In this definition take the second non-article word, that +is \textit{human}, and again look up the definition of this +word. This will yield + +\begin{quote} +``relating to \textit{or} characteristic of humankind'' +\end{quote} + +\noindent +You could now go on to look up the definition of the third +non-article in this definition and so on. But let us assume +you agreed with Bob to stop after three iterations with the +third non-article word in the last definition, that is +\textbf{or}. Now, instead of sending to Bob the solution +\textit{folio}, you send to him \textit{or}. How can +Bob verify that you know the solution? Well, once he solved +it himself, he can use the dictionary and follow the same +``trail'' as you did. It the final word agrees with what +you send him, he must infer you know the solution earlier +than him. This protocol works like a one-way hash function +because \textit{or} does not give any hint as to what was +the first word was. I leave you to think why this +protocol avoids article words. + +After Bob found his solution and verified that according to +the protocol it ``maps'' also to \textit{or}, can he be +entirely sure no cheating is going on. Not with 100\% +certainty. It could have been entirely possible that +he was given \textit{or} as the word but it derived +from an entirely different word---this seems very unlikely, +but is at least theoretical a possibility. Protocols +based on zero-knowledge proofs will produce a similar +result---they give an answer that might be erroneous +in a very small number of cases. The point is to itterate +them long enough so that the theoretical possibility of +cheating is negligibly small. + +By the way, the authors of the paper ``Dismantling Megamos +Crypto: Wirelessly Lockpicking a Vehicle Immobilizer'' who +were barred from publishing their results used also a hash to +prove they did the work and (presumably) managed to get into +cars without a key. See Figure~\ref{paper}. This is very +similar to the method about crosswords. They like to prove +that they did the work, but not giving out the ``solution''. +But this also shows what the problem with such methods +are: yes, we can hide the secret temporarily, but if +somebody else wants to verify it, then the secret has +to be made public. Bob needs to know that \textit{folio} +is the solution before he can verify the claim that somebody +else had the solution first. Similarly with the paper: +we need to wait until the authors are finally allowed to +publish their finding in order to verify the hash. This +might happen at some point, but equally it might never +happen (what for example happens if the authors loose +their copy of the paper because of a disk failure?). +Zero-knowledge proofs, in contrast, can be immediately +be checked, even if the secret is not public yet. + +\begin{figure} +\begin{center} +\fbox{\includegraphics[scale=0.4]{../pics/Dismantling_Megamos_Crypto.png}} +\end{center} +\caption{The authors of this paper used a hash in order to prove +later that they have managed to break into cars.\label{paper}} +\end{figure} + + +\subsubsection*{ZKP: An Illustrative Example} + +The idea behind zero-knowledge proofs is not very obvious and +will surely take some time for you to digest. Therefore +lets start with an illustrative example. The example will +not be perfect, but hopefully explain the gist of the ideas. +The example is called Alibaba's cave: + +\begin{center} +\begin{tabular}{c@{\hspace{8mm}}c@{\hspace{8mm}}c} +\includegraphics[scale=0.1]{../pics/alibaba1.png} & +\includegraphics[scale=0.1]{../pics/alibaba2.png} & +\includegraphics[scale=0.1]{../pics/alibaba3.png} \\ +Step 1 & Step 2 & Step 3 +\end{tabular} +\end{center} + +\noindent Lets have a look at the picture in Step 1: +The cave is a loop where at the end is a magic wand. +The point of the magic wand is that Alice knows the +secret word for how to open it. She wants to keep here +word secret, but wants to convince Bob that she knows it. + + +\end{document} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: t +%%% End: diff -r 4a0071e26cb5 -r 40511897fcc4 slides/slides06.pdf Binary file slides/slides06.pdf has changed diff -r 4a0071e26cb5 -r 40511897fcc4 slides/slides06.tex --- a/slides/slides06.tex Tue Nov 04 12:35:41 2014 +0000 +++ b/slides/slides06.tex Wed Nov 05 12:01:05 2014 +0000 @@ -503,10 +503,11 @@ \item this is pretty old work (in theory); seems little used in practice (surprising)\bigskip -\item for use in privacy the incentives are +\item for use in privacy, the incentives are not yet right\bigskip -\item digital cash (Bitcoins are not yet good enough) +\item most likely applied with digital cash + (Bitcoins are not yet good enough) \end{itemize}