\item Imagine you have an completely innocent email message,

      like birthday wishes to your grandmother? Why should you

      still encrypt this message and your grandmother take the

      effort to decrypt it?\bigskip 

      \small  

      (Hint: The answer has nothing to do with preserving the

      privacy of your grandmother and nothing to do with

      keeping her birthday wishes super-secret. Also nothing to

      do with you and grandmother testing the latest

      encryption technology, nor just for the sake of it.)

\end{itemize}

\includegraphics[scale=0.6]{../pics/escher.jpg}

\frametitle{Interlock Protocol}

Protocol between a car \bl{$C$} and a key transponder \bl{$T$}:\bigskip 

\begin{enumerate}

\item \bl{$C$} generates a random number \bl{$N$}

\item \bl{$C$} calculates \bl{$(F,G) = \{N\}_K$}

\item \bl{$C \to T$}: \bl{$N, F$}\bigskip

\item \bl{$T$} calculates \bl{$(F',G') = \{N\}_K$}

\item \bl{$T$} checks that \bl{$F = F'$}

\item \bl{$T \to C$}: \bl{$N, G'$}

\item \bl{$C$} checks that \bl{$G = G'$}

\end{enumerate}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Zero-Knowledge Proofs}

Essentially every NP-problem can be used for ZKPs\bigskip

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

\begin{center}

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

\end{center} 

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Modular Arithmetic}

It is easy to calculate

\begin{center}

\large\bl{$\alt<1>{?}{10} \equiv 46\; mod\; 12$}

\end{center}\bigskip\pause 

A: \bl{$10$}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Modular Logarithm}

Ordinary, non-modular logarithms: 

\begin{center}\large

\begin{tabular}{ll}

& \bl{$10^? = 17$}\bigskip\\\pause

$\Rightarrow$ & \bl{$log_{10} 17 = 1.2304489\ldots$}\\\pause

$\Rightarrow$ & \bl{$10^{1.2304489} = 16.999999$}\\\pause

\end{tabular}

\end{center}

Conclusion: \bl{$1.2304489$} is very close to the \emph{true}

solution

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Modular Logarithm}

In contrast, modular logarithms behave much differently:

\begin{center}\large

\bl{$2^? \equiv 88319671\;\; mod\;\; 97330327$}\bigskip\\\pause

\end{center}\pause

Lets say I found \bl{$28305819$}\ldots I try

\begin{center}\large

\bl{$2^{28305819} \equiv 88032151\;\; mod\;\; 97330327$}\bigskip\\\pause

\end{center}\pause

I could be tempted to try \bl{$28305820$}\ldots\pause

but the real\\

\mbox{}\hfill answer is \bl{12314}.

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\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}\bigskip

\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$} with \bl{$b_j = 1$}

\end{enumerate}

\only<2>{

\begin{textblock}{7}(7.9,3.9)

\begin{bubble}[5cm]\small

\begin{center}

  \begin{tabular}{lcccc}

  Alice \bl{$r_i$}:\; & \bl{4} & \bl{9} & \bl{1} & \bl{3}\\ 

  Bob \bl{$b_i$}:\; & \bl{0} & \bl{1} & \bl{0} & \bl{1}\\

  & & \bl{$\uparrow$} \\

  & & \bl{$j$}

  \end{tabular}             

  \end{center}    

\end{bubble}

\end{textblock}}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\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 h_i\;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 sent

\begin{center}

\begin{tabular}{l}

\bl{$h_1, \ldots, h_z$},\\

\bl{$r_1 - r_j$},  \bl{$r_2 - r_j$}, \ldots, \bl{$r_z - r_j \;\;mod \;p - 1$} 

\end{tabular}

\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}

\only<2>{

\begin{textblock}{7}(7.9,1)

\begin{bubble}[5cm]\small

\begin{center}

\bl{\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}

$A^{s_i}$ & $=$ & $A^{r_i - r_j}$\\ 

          & $=$ & $A^{r_i} * A^{-r_j}$\\

          & $=$ & $h_{r_i} * h_{r_j}^{-1}\;mod\;p$   

\end{tabular}}

\end{center}    

\end{bubble}

\end{textblock}}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\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{$\frac{1}{2}^z$} chance of doing so.\bigskip\\

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\tikzset{alt/.code args={<#1>#2#3#4}{%

  \alt<#1>{\pgfkeysalso{#2}}{\pgfkeysalso{#3}} % \pgfkeysalso doesn't change the path

}}

\begin{frame}[t]

\frametitle{Buffer Overflow Attacks}

\begin{itemize}

\item the problem arises from the way C/C++ organises its function calls\\[-8mm]\mbox{}

\end{itemize}

\begin{center}

\begin{tikzpicture}[scale=1]

%\draw[black!10,step=2mm] (0,0) grid (9,4);

%\draw[black!10,thick,step=10mm] (0,0) grid (9,4);

\node at (0.5,4.5) {\small\begin{tabular}{l}main\\[-2mm] prog.\end{tabular}};

\draw[line width=0mm, white, alt=<2->{fill=red}{fill=blue}] (0,2.5) rectangle (1,3.8);

\draw[line width=0mm, white, alt=<9->{fill=red}{fill=blue}] (0,0.2) rectangle (1,0.5);

\draw[line width=1mm, alt=<3->{fill=yellow}{fill=blue}] (0,2.0) rectangle (1,2.5);

\draw[line width=1mm, alt=<6->{fill=red}{fill=blue}] (0,1.0) rectangle (1,2.0);

\draw[line width=1mm, alt=<7->{fill=yellow}{fill=blue}] (0,0.5) rectangle (1,1.0);

\draw[line width=1mm] (0,0) -- (0,4);

\draw[line width=1mm] (1,0) -- (1,4);

\node at (3.5,3.5) {\small\begin{tabular}{l}fact(n)\end{tabular}};

\draw[line width=1mm, alt=<{4-5,8}>{fill=red}{fill=blue}] (3,1.0) rectangle (4,3.0);

\onslide<3-4>{\draw[->, line width=1mm,red] (1,2.3) to node [above,sloped,midway] {n=4} (3,3);}

\onslide<5>{\draw[<-, line width=1mm,red] (1,2.3) to node [above,sloped,midway] {res=24} (3,1);}

\onslide<7-8>{\draw[->, line width=1mm,red] (1,0.8) to node [above,sloped,midway] {n=3} (3,3);}

\onslide<9>{\draw[<-, line width=1mm,red] (1,0.8) to node [above,sloped,midway] {res=6} (3,1);}

\node at (7.75,3.9) {\small\begin{tabular}{l}stack\end{tabular}};

\draw[line width=1mm] (7,3.5) -- (7,0.5) -- (8.5,0.5) -- (8.5,3.5);

\onslide<3,4,7,8>{

\node at (7.75, 1.4) {ret};

\draw[line width=1mm] (7,1.1) -- (8.5,1.1);

\node at (7.75, 2.0) {sp};

\draw[line width=1mm] (7,2.3) -- (8.5,2.3);

}

\onslide<3,4>{

\node at (7.75, 0.8) {4};

\draw[line width=1mm] (7,1.7) -- (8.5,1.7);

}

\onslide<7,8>{

\node at (7.75, 0.8) {3};

\draw[line width=1mm] (7,1.7) -- (8.5,1.7);

}

\end{tikzpicture}

\end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\begin{center}

\begin{tikzpicture}[scale=1]

%\draw[black!10,step=2mm] (0,0) grid (9,4);

%\draw[black!10,thick,step=10mm] (0,0) grid (9,4);

\node at (0.5,4.5) {\small\begin{tabular}{l}main\\[-2mm] prog.\end{tabular}};

\draw[line width=0mm, white, alt=<2->{fill=red}{fill=blue}] (0,2.5) rectangle (1,3.8);

\draw[line width=1mm, white, fill=blue] (0,1.0) rectangle (1,2.0);

\draw[line width=1mm, alt=<3->{fill=yellow}{fill=blue}] (0,2.0) rectangle (1,2.5);

\draw[line width=1mm] (0,0) -- (0,4);

\draw[line width=1mm] (1,0) -- (1,4);

\node at (3.5,3.5) {\small\begin{tabular}{l}fact(n)\end{tabular}};

\draw[line width=0mm, alt=<{4-}>{red, fill=red}{blue, fill=blue}] (3,2.8) rectangle (4,3.0);

\draw[line width=0mm, alt=<{5-}>{red, fill=red}{blue, fill=blue}] (3,2.8) rectangle (4,2.0);

\draw[line width=0mm, alt=<{7-}>{red, fill=red}{blue, fill=blue}] (3,2.0) rectangle (4,1.0);

\draw[line width=1mm] (3,1.0) rectangle (4,3.0);

\onslide<3->{\draw[->, line width=1mm,red] (1,2.3) to node [above,sloped,midway] {n=4} (3,3);}

\onslide<5->{\draw[<-, line width=2mm,red] (4,2) to node [above,sloped,midway] 

{\begin{tabular}{l}user\\[-1mm] input\end{tabular}} (6,2);}

\onslide<8->{\draw[<-, line width=1mm,red] (1,-2) to (3,1);}

\node at (7.75,3.9) {\small\begin{tabular}{l}stack\end{tabular}};

\draw[line width=1mm] (7,3.5) -- (7,-0.1) -- (8.5,-0.1) -- (8.5,3.5);

\onslide<3->{

\node at (7.75, 0.2) {4};

\draw[line width=1mm,alt=<6->{fill=red}{fill=white}] (7,0.5) rectangle (8.5,1.1);

\node at (7.75, 0.8) {\alt<6->{@a\#}{ret}};

\draw[line width=1mm,alt=<6->{fill=red}{fill=white}] (7,1.1) rectangle (8.5,1.7);

\node at (7.75, 1.4) {\alt<6->{!?w;}sp};

}

\onslide<4->{

\draw[line width=1mm,fill=red] (7,1.7) rectangle (8.5,3.0);

\node[white] at (7.75, 2.4) {buffer};

}

\end{tikzpicture}

\end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\begin{itemize}

\item Imagine you have an completely innocent email message,

      like birthday wishes to your grandmother? Why should you

      still encrypt this message and your grandmother take the

      effort to decrypt it?\bigskip 

      \small  

      (Hint: The answer has nothing to do with preserving the

      privacy of your grandmother and nothing to do with

      keeping her birthday wishes super-secret. Also nothing to

      do with you and grandmother testing the latest

      encryption technology, nor just for the sake of it.)