Binary file slides/slides09.pdf has changed

--- a/slides/slides09.tex	Tue Dec 03 13:38:28 2013 +0000
+++ b/slides/slides09.tex	Tue Dec 03 14:22:04 2013 +0000
@@ -387,16 +387,106 @@
 \begin{frame}[c]
 \frametitle{Other Methods for ZKPs}
 
+Essentially every NP-problem can be used for ZKPs
+
 \begin{itemize}
-\item modular logarithms (you can 
+\item modular logarithms: Alice chooses public \bl{$A$},  \bl{$B$}, \bl{$p$}; and private \bl{$x$}
+
+\begin{center}
+\bl{$A^x \equiv B\; mod\; p$}
+\end{center} 
 \end{itemize}
 
 \end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{Commitment Stage}
+
+\begin{enumerate}
+\item Alice generates \bl{$z$} random numbers \bl{$r_1$}, ..., \bl{$r_z$}, all less than \bl{$p - 1$}.
+\item Alice sends Bob for all \bl{$1..z$} 
+\begin{center}
+\bl{$h_i = A^{r_i} \;mod\; p$}
+\end{center}
+\item Bob generates random bits   \bl{$b_1$}, ..., \bl{$b_z$} by flipping a coin
+\item For each bit \bl{$b_i$}, Alice sends Bob an \bl{$s_i$} where
+
+\begin{center}
+\begin{tabular}{ll}
+\bl{$b_i = 0$}: & \bl{$s_i = r_i$}\\
+\bl{$b_i = 1$}: & \bl{$s_i = (r_i - r_j) \;mod\; (p -1)$}\\
+\end{tabular}
+\end{center}
+where \bl{$r_j$} is the lowest \bl{$j$} where \bl{$b_j = 1$}
+ 
+\end{enumerate}
+
+\end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
+\frametitle{Confirmation Stage}
+
+\begin{enumerate}
+\item For each \bl{$b_i$} Bob checks whether \bl{$s_i$} conforms to the protocol
+
+\begin{center}
+\begin{tabular}{ll}
+\bl{$b_i = 0$}: & \bl{$A^{s_i} \equiv B\;mod\;p$}\\
+\bl{$b_i = 1$}: & \bl{$A^{s_i}  \equiv h_i * h_j^{-1}  \;mod\; p$}\\
+\end{tabular}
+\end{center}\bigskip
+
+Bob was send 
+
+\begin{center}
+\bl{$r_j - r _j$},  \bl{$r_m - r _j$}, \ldots, \bl{$r_p - r _j$ \;mod \;p} 
+\end{center}
+
+where the corresponding bits were 
+\bl{$1$}; Bob does not know \bl{$r_j$}, he does not know any \bl{$r_i$} where the bit was \bl{$1$}
+\end{enumerate}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{Proving Stage}
+
+\begin{enumerate}
+\item Alice proves she knows \bl{$x$}, the discrete log of \bl{$B$}\\
+she sends
+
+\begin{center}
+\bl{$s_{z+1} = (x - r_j)$}
+\end{center}
+
+\item Bob confirms
+
+\begin{center}
+\bl{$A^{s_{z+1}} \equiv B * h_j^{-1} \;mod \; p$}
+\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})}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+ 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
 \frametitle{Random Number Generators}