\renewcommand{\slidecaption}{APP 09, King's College London, 3 December 2013}

  \normalsize

  Office: & S1.27 (1st floor Strand Building)\\

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

hash functions...but Bob can only check once he has also the solution

}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{Zero-Knowledge Proofs}

Two remarkable properties:\bigskip

\begin{itemize}

\item Alice only reveals the fact that she knows a secret.\bigskip

\item Having been convinced, Bob cannot use the evidence in order to convince Carol.

\end{itemize}

\frametitle{\begin{tabular}{@{}c@{}}The Idea\end{tabular}}

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

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

\frametitle{Graph Isomorphism}

\begin{center}

\begin{tabular}{l@{\hspace{10mm}}r}

\includegraphics[scale=0.8]{pics/graphs.png}\\

\end{tabular}

\end{center}

Finding an isomorphism between two graphs is an NP complete problem.

\frametitle{Graph Isomorphism Protocol}

Alice starts with knowing an isomorphism 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

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

\frametitle{Non-Interactive ZKPs}

\bigskip

This is amazing: Alison can publish some data that contains no data about her secret,

but can be used to convince anyone of the secret's existence.

\frametitle{Problems of ZKPs}

\bigskip

This is amazing: Alison can publish some data that contains no data about her secret,

but can be used to convince anyone of the secret's existence.

\frametitle{Random Number Generators}