
diff -r b732a63c17b8 -r 98403100cea7 slides/slides06.tex
--- a/slides/slides06.tex	Tue Nov 04 00:41:34 2014 +0000
+++ b/slides/slides06.tex	Tue Nov 04 11:56:24 2014 +0000
@@ -48,7 +48,7 @@
 \item (I learned) jamming the closing 
   signal
 \item relay signals\pause
-\item use diagnostic port to program 
+\item use the diagnostic port to program 
   blank keys 
 \end{itemize}
 \end{column}
@@ -135,7 +135,10 @@
 
 \begin{center}
 \includegraphics[scale=0.15]{../pics/cake.jpg}
-\end{center}
+\end{center}\pause\bigskip
+
+Solves the problem of communication when both parties
+distrust each other,
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
@@ -153,8 +156,8 @@
 \end{tabular}
 \end{center}
 
-\begin{textblock}{7}(1,2.5)
-The Alibaba cave:
+\begin{textblock}{7}(1,2)
+The Alibaba cave protocol:
 \end{textblock}
 
 \small
@@ -186,7 +189,10 @@
       the idea is to force users to prove, using a
       zero-knowledge proof, that their behaviour is correct
       according to the protocol
-\end{itemize}
+\end{itemize}\bigskip
+
+\small
+digital currencies, smart cards, id cards
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
 
@@ -198,16 +204,20 @@
 Zero-knowledge proof protocols should satisfy:\bigskip
 
 \begin{itemize}
-\item \alert{\bf Completeness} If Alice knows the secret, Bob accepts Alice ``proof'' for sure.\bigskip
-\item \alert{\bf Soundness} If Alice does not know the secret, Bob accepts her ``proof'' with a very 
-small probability.
-\end{itemize}
+\item \alert{\bf Completeness} If Alice knows the secret, Bob
+      accepts Alice ``proof'' for sure.\bigskip
+\item \alert{\bf Soundness} If Alice does not know the secret,
+      Bob accepts her ``proof'' with a very small probability.
+
+\item \alert{\bf Zero-Knowledge} Even if Bob accepts
+      the proof by Alice, he cannot convince anybody else.
+
+\end{itemize} 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 \frametitle{Graph Isomorphism}
 
@@ -217,14 +227,15 @@
 \end{tabular}
 \end{center}
 
-Finding an isomorphism between two graphs is an NP complete problem.
-\end{frame}}
+Finding an isomorphism between two graphs is an NP-complete
+problem.
+
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{Graph Isomorphism Protocol}
+\frametitle{\Large Graph Isomorphism Protocol}
 
 Alice starts with knowing an isomorphism \bl{$\sigma$} between graphs \bl{$G_1$} and \bl{$G_2$}\medskip
 
@@ -237,28 +248,58 @@
 
 these are called commitment algorithms
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
    
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{Graph Isomorphism Protocol (2)}
+\frametitle{\Large Graph Isomorphism Protocol (2)}
 
-If Alice knows the isomorphism, she can always calculate \bl{$\sigma$}.\bigskip
+If Alice knows the isomorphism, she can always calculate
+\bl{$\sigma$}.\bigskip
 
- If she doesn't, she can only correctly respond if Bob's 
- choice of index is the same as the one she used to form \bl{$H$}. The probability 
- of this happening is \bl{$\frac{1}{2}$}, so after \bl{$n$} rounds the probability of her 
- always responding correctly is only \bl{$\frac{1}{2}^n$}.
+If she doesn't, she can only correctly respond if Bob's choice
+of index is the same as the one she used to form \bl{$H$}. The
+probability of this happening is \bl{$\frac{1}{2}$}, so after
+\bl{$n$} rounds the probability of her always responding
+correctly is only \bl{$\frac{1}{2}^n$}.
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
+\begin{frame}[t]
+\frametitle{Plot of $\frac{1}{2}^n$}
+
+\begin{center}
+\begin{tikzpicture}
+\begin{axis}[
+    enlargelimits=true,
+    xtick={0,1,...,10},
+    xmax=11,
+    ymax=1.1,
+    ytick={0,0.1,...,1.1},
+    scaled ticks=false,
+    axis lines=left,
+    width=11cm,
+    height=7cm]
+\addplot[blue,mark=*, mark options={fill=white}] 
+   coordinates {
+     (0, 1) (1, 0.5) (2, 0.25) (3, 0.125) 
+     (4, 0.0625) (5, 0.03125) (6, 0.015625)
+     (7, 0.0078125) (8, 0.00390625)
+     (9, 0.001953125) (10, 0.0009765625)
+   };
+\end{axis}
+\end{tikzpicture}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{Graph Isomorphism Protocol (3)}
+\frametitle{\Large Graph Isomorphism Protocol (3)}
 
 Why is the GI-protocol zero-knowledge?\bigskip\pause
 
@@ -270,51 +311,55 @@
 and therefore participation in such a communication does not
 increase Bob's capability to perform any computation.
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
-   
-   
-   
+      
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 \frametitle{Non-Interactive ZKPs}
 
-
+This is amazing: This can all be done ``offline'': 
 \bigskip
-This is amazing: Alison can publish some data that contains no data about her secret,
-but this data can be used to convince anyone of the secret's existence.
-\end{frame}}
+
+Alice can publish some data that contains no data about her
+secret, but this data can be used to convince anyone of the
+secret's existence (whether Alice knows it, must be
+established my other means).
+
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 \frametitle{Non-Interactive ZKPs (2)}
 
-Alice starts with knowing an isomorphism \bl{$\sigma$} between graphs \bl{$G_1$} and \bl{$G_2$}\medskip
+Alice starts with knowing an isomorphism \bl{$\sigma$} between
+graphs \bl{$G_1$} and \bl{$G_2$}\medskip
 
 \begin{enumerate}
-\item Alice generates \bl{$n$} isomorphic graphs \bl{$H_{1..n}$} which she makes public 
-\item she feeds the \bl{$H_{1..n}$} into a hashing function (she has no control over what
-	the output will be)
-\item Alice takes the first \bl{$n$} bits of the output: whenever output is \bl{$0$}, she shows 
-an isomorphism with \bl{$G_1$} ; for \bl{$1$} she shows an isomorphism with \bl{$G_2$}
+\item Alice generates \bl{$n$} isomorphic graphs
+      \bl{$H_{1..n}$} which she makes public 
+\item she feeds the \bl{$H_{1..n}$} into a hashing function
+      (she has no control over what the output will be)
+\item Alice takes the first \bl{$n$} bits of the output:
+      whenever output is \bl{$0$}, she shows an isomorphism
+      with \bl{$G_1$} ; for \bl{$1$} she shows an isomorphism
+      with \bl{$G_2$}
 \end{enumerate}
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 \frametitle{Problems of ZKPs}
 
 \begin{itemize}
-\item ``grand chess master problem''\\ 
-(person in the middle)\bigskip
+\item ``grand chess master problem''\\ (person in the
+      middle again)\bigskip
 
-\item Alice can have multiple identities; once she committed a fraud she stops using one
+\item Alice can have multiple identities; once she committed a
+      fraud with one, she stops using one 
 \end{itemize}
 
 \end{frame}}
@@ -380,7 +425,7 @@
 \end{tabular}
 \end{center}\bigskip
 
-Bob was send 
+Bob was sent
 
 \begin{center}
 \bl{$r_j - r _j$},  \bl{$r_m - r _j$}, \ldots, \bl{$r_p - r _j$ \;mod \;p} 
@@ -394,7 +439,6 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 \frametitle{Proving Stage}
 
@@ -413,58 +457,35 @@
 \end{center}
 \end{enumerate}\bigskip\pause
 
-In order to cheat, Alice has to guess all bits in advance. She has only \bl{$1$} to \bl{$2^z$}
-chance. \\
-\small\hspace{7mm}\textcolor{gray}{(explanation $\rightarrow$ \url{http://goo.gl/irL9GK})}
+In order to cheat, Alice has to guess all bits in advance. She
+has only \bl{$\frac{1}{2}^z$} chance.\bigskip\\
 
-\end{frame}}
+\small\hspace{7mm}
+\textcolor{gray}{(explanation $\rightarrow$ \url{http://goo.gl/irL9GK})}
+
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
 
- 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{Random Number Generators}
+\frametitle{Take Home Points}
 
 \begin{itemize}
-\item Computers are deterministic. How do they generate random numbers?\bigskip\pause
-
-\item The most popular method to generate random numbers between \bl{$0$} and \bl{$m$} is: choose
-three integers
+\item this is pretty old work (in theory); seems
+  little used in practice (surprising)
 
-\begin{center}
-\begin{tabular}{ll}
-\bl{$a$} & multiplier\\
-\bl{$c$} & increment\\
-\bl{$X_0$} & start value
-\end{tabular}
-\end{center}
+\item for use in privacy the incentives are
+  not yet right
 
-and calculate
+\item digital cash (Bitcoins are not yet good enough)
 
-\begin{center}
-\bl{$X_{n+1} = (a * X_n + c) \;mod\; m$}
-\end{center}
 \end{itemize}
 
-\only<3->{
-\begin{textblock}{7}(10,2)
-\begin{tikzpicture}
-\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] 
-{\begin{minipage}{3.8cm}
-\begin{tabular}{ll|l}
-\bl{$m =$}    & \bl{$16$} & \bl{$16$}\\
-\bl{$X_0 =$} &  \bl{$1$} & \bl{$1$}\\
-\bl{$a = $}    & \bl{$5$} & \bl{$5$}\\
-\bl{$c =$}     & \bl{$1$} & \bl{$0$}\\
-\end{tabular} 
-\end{minipage}};
-\end{tikzpicture}
-\end{textblock}}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
 \end{document}
 
 %%% Local Variables:  




