diff -r 98ae49ffc262 -r 62985f147c85 slides/slides06-zkp-old.tex
--- a/slides/slides06-zkp-old.tex	Tue Sep 26 12:03:24 2017 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,505 +0,0 @@
-\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: & S1.27 (1st floor Strand Building)\\
-  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: 
-