--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/slides/slides06-zkp-old.tex-bak Sat Sep 23 14:19:09 2017 +0100
@@ -0,0 +1,505 @@
+\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:
+