\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