391 \item modular logarithms (you can 

   393 \item modular logarithms: Alice chooses public \bl{$A$},  \bl{$B$}, \bl{$p$}; and private \bl{$x$}

   394 

   395 \begin{center}

   396 \bl{$A^x \equiv B\; mod\; p$}

   397 \end{center} 

   395 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   401 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   402 

   403 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   404 \mode<presentation>{

   405 \begin{frame}[c]

   406 \frametitle{Commitment Stage}

   407 

   408 \begin{enumerate}

   409 \item Alice generates \bl{$z$} random numbers \bl{$r_1$}, ..., \bl{$r_z$}, all less than \bl{$p - 1$}.

   410 \item Alice sends Bob for all \bl{$1..z$} 

   411 \begin{center}

   412 \bl{$h_i = A^{r_i} \;mod\; p$}

   413 \end{center}

   414 \item Bob generates random bits   \bl{$b_1$}, ..., \bl{$b_z$} by flipping a coin

   415 \item For each bit \bl{$b_i$}, Alice sends Bob an \bl{$s_i$} where

   416 

   417 \begin{center}

   418 \begin{tabular}{ll}

   419 \bl{$b_i = 0$}: & \bl{$s_i = r_i$}\\

   420 \bl{$b_i = 1$}: & \bl{$s_i = (r_i - r_j) \;mod\; (p -1)$}\\

   421 \end{tabular}

   422 \end{center}

   423 where \bl{$r_j$} is the lowest \bl{$j$} where \bl{$b_j = 1$}

   424  

   425 \end{enumerate}

   426 

   427 \end{frame}}

   428 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   429 

   430 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   431 \mode<presentation>{

   432 \begin{frame}[c]

   433 \frametitle{Confirmation Stage}

   434 

   435 \begin{enumerate}

   436 \item For each \bl{$b_i$} Bob checks whether \bl{$s_i$} conforms to the protocol

   437 

   438 \begin{center}

   439 \begin{tabular}{ll}

   440 \bl{$b_i = 0$}: & \bl{$A^{s_i} \equiv B\;mod\;p$}\\

   441 \bl{$b_i = 1$}: & \bl{$A^{s_i}  \equiv h_i * h_j^{-1}  \;mod\; p$}\\

   442 \end{tabular}

   443 \end{center}\bigskip

   444 

   445 Bob was send 

   446 

   447 \begin{center}

   448 \bl{$r_j - r _j$},  \bl{$r_m - r _j$}, \ldots, \bl{$r_p - r _j$ \;mod \;p} 

   449 \end{center}

   450 

   451 where the corresponding bits were 

   452 \bl{$1$}; Bob does not know \bl{$r_j$}, he does not know any \bl{$r_i$} where the bit was \bl{$1$}

   453 \end{enumerate}

   454 

   455 \end{frame}}

   456 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   457 

   458 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   459 \mode<presentation>{

   460 \begin{frame}[c]

   461 \frametitle{Proving Stage}

   462 

   463 \begin{enumerate}

   464 \item Alice proves she knows \bl{$x$}, the discrete log of \bl{$B$}\\

   465 she sends

   466 

   467 \begin{center}

   468 \bl{$s_{z+1} = (x - r_j)$}

   469 \end{center}

   470 

   471 \item Bob confirms

   472 

   473 \begin{center}

   474 \bl{$A^{s_{z+1}} \equiv B * h_j^{-1} \;mod \; p$}

   475 \end{center}

   476 \end{enumerate}\bigskip\pause

   477 

   478 In order to cheat, Alice has to guess all bits in advance. She has only \bl{$1$} to \bl{$2^z$}

   479 chance. \\

   480 \small\hspace{7mm}\textcolor{gray}{(explanation $\rightarrow$ \url{http://goo.gl/irL9GK})}

   481 

   482 \end{frame}}

   483 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   484 

   485