\documentclass[dvipsnames,14pt,t]{beamer}
\usepackage{../slides}
\usepackage{../graphics}

\setmonofont[Scale=.88]{Consolas}
\newfontfamily{\consolas}{Consolas}

\hfuzz=220pt 

% beamer stuff 
\newcommand{\bl}[1]{\textcolor{blue}{#1}}  
\renewcommand{\slidecaption}{SEN 06, King's College London}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{%
  \begin{tabular}{@ {}c@ {}}
  \\
  \LARGE Security Engineering (6)\\[-3mm] 
  \end{tabular}}\bigskip\bigskip\bigskip

  \normalsize
  \begin{center}
  \begin{tabular}{ll}
  Email:  & christian.urban at kcl.ac.uk\\
  Office: & N7.07 (North Wing, Bush House)\\
  Slides: & KEATS (also homework is there)\\
  \end{tabular}
  \end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Hashes for History}

Q: What is the hash for?

\begin{center}
\includegraphics[scale=0.4]{../pics/Dismantling_Megamos_Crypto.png}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Checking Solutions}

How can you check somebody's solution without revealing the solution?\pause\bigskip

Alice and Bob solve crosswords. Alice knows the answer for 21D (folio) but doesn't 
want to tell Bob.\medskip

You use an English  dictionary:

\begin{itemize}
\item folio \onslide<4->{$\stackrel{1}{\rightarrow}$ individual }
                \onslide<5->{$\stackrel{2}{\rightarrow}$ human}
                \onslide<6->{$\stackrel{3}{\rightarrow}$ or \ldots}
\only<3>{
\begin{quote}
``an \alert{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}}
\only<4>{
\begin{quote}
``a single \alert{human} being as distinct from a group''
\end{quote}}
\only<5>{
\begin{quote}
``relating to \alert{or} characteristic of humankind''
\end{quote}}
\end{itemize}\bigskip\bigskip

\only<7->{
this is essentially a hash function...but Bob can only check once he has also found the solution
}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Zero-Knowledge Proofs}

Two remarkable properties of \alert{Zero-Knowledge 
Proofs}:\bigskip

\begin{itemize}

\item Alice only reveals the fact that she knows a secret, not
      the secret itself (meaning she can convince Bob that she
      knows the secret, but does not give it to him).\bigskip
\item Having been convinced, Bob cannot use the evidence in
      order to convince Carol that Alice knows the secret.

\end{itemize}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Interactive Protocols}

Q: How to cut a cake into two equal slices?

\begin{center}
\includegraphics[scale=0.15]{../pics/cake.jpg}
\end{center}\pause\bigskip

\small
Solves the problem of communication when both parties
distrust each other.

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{The Idea}

\begin{center}
\begin{tabular}{l@{\hspace{10mm}}r}
\\[-10mm]
\raisebox{10mm}{\large 1.} & \includegraphics[scale=0.1]{../pics/alibaba1.png}\\
\raisebox{10mm}{\large 2.} & \includegraphics[scale=0.1]{../pics/alibaba2.png}\\
\raisebox{10mm}{\large 3.} & \includegraphics[scale=0.1]{../pics/alibaba3.png}
\end{tabular}
\end{center}

\begin{textblock}{7}(1,2)
The Alibaba cave protocol:
\end{textblock}

\small
\only<2>{
\begin{textblock}{12}(2,13.3)
Even if Bob has a hidden camera, a recording will not be
convincing to anyone else (Alice and Bob could have made it
all up).
\end{textblock}}
\only<3>{
\begin{textblock}{12}(2,13.3)
Even worse, an observer present at the experiment would not be
convinced.
\end{textblock}}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Applications of ZKPs}

\begin{itemize}
\item authentication, where one party wants to prove its
      identity to a second party via some secret information,
      but doesn't want the second party to learn anything
      about this secret\bigskip
\item to enforce honest behaviour while maintaining privacy:
      the idea is to force users to prove, using a
      zero-knowledge proof, that their behaviour is correct
      according to the protocol
\end{itemize}\bigskip

\small
digital currencies, smart cards, id cards
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Central Properties}

Zero-knowledge proof protocols should satisfy:\bigskip

\begin{itemize}
\item \alert{\bf Completeness} If Alice knows the secret, Bob
      accepts Alice's ``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}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Graph Isomorphism}
\mbox{}\\[-20mm]\mbox{}

\begin{center}
\begin{tabular}{@{}ccc}
\raisebox{-18mm}{\includegraphics[scale=0.4]{../pics/simple.png}} &
\raisebox{-18mm}{\includegraphics[scale=0.4]{../pics/simple-b.png}}&

\footnotesize
\begin{tabular}{rl}
Graph A	& Graph B\\
Graph $G_1$	& Graph $G_2$\\
a  & 1\\
b  & 6\\
c  & 8\\
d  & 3\\
g  & 5\\
h  & 2\\
i  & 4\\
j  & 7\\
\end{tabular}
\end{tabular}
\end{center}

Finding an isomorphism between two graphs is an NP problem.

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\begin{center}
\includegraphics[scale=0.8]{../pics/graphs.png}
\end{center}

Creating a new isomorphic graph is easy; finding an
isomorphism is hard; checking an isomorphism is easy again

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{\Large Graph Isomorphism Protocol}

Alice starts with knowing an isomorphism \bl{$\sigma$} between graphs \bl{$G_1$} and \bl{$G_2$}\medskip

\begin{enumerate}
\item Alice generates an isomorphic graph \bl{$H$} which she sends to Bob 
\item Bob asks either for an isomorphism between \bl{$G_1$} and \bl{$H$}, or
\bl{$G_2$} and \bl{$H$}	
\item Alice and Bob repeat this procedure \bl{$n$} times	
\end{enumerate}\pause

these are called commitment algorithms

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{\Large Graph Isomorphism Protocol (2)}

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$}.

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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{\Large Graph Isomorphism Protocol (3)}

Why is the GI-protocol zero-knowledge?\bigskip\pause

A: We can generate a fake transcript of a conversation, which 
cannot be distinguished from a ``real'' conversation.\bigskip

Anything Bob can compute using the information obtained from
the transcript can be computed using only a forged transcript
and therefore participation in such a communication does not
increase Bob's capability to perform any computation.

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
      
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Non-Interactive ZKPs}

This is amazing: This can all be done ``offline'': 
\bigskip

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

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

\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$}
\end{enumerate}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Problems of ZKPs}

\begin{itemize}
\item ``grand chess master problem''\\ (person in the
      middle again)\bigskip

\item Alice can have multiple identities; once she committed a
      fraud with one, she stops using one 
\end{itemize}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Other Methods for ZKPs}

Essentially every NP-problem can be used for ZKPs

\begin{itemize}
\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 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}
\bl{$r_j - r_j$},  \bl{$r_m - r_j$}, \ldots, \bl{$r_p - r_j \;mod \;p - 1$} 
\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}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

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

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

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Take Home Points}

\begin{itemize}
\item this is pretty old work (in theory); seems
  little used in practice (surprising)\bigskip

\item for use in privacy, the incentives are
  not yet right\bigskip

\item most likely applied with digital cash 
  (Bitcoins are not yet good enough, Zerocoins)

\end{itemize}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




\end{document}

%%% Local Variables:  
%%% mode: latex
%%% TeX-master: t
%%% End: