--- a/slides/slides06.tex Tue Nov 04 00:41:34 2014 +0000
+++ b/slides/slides06.tex Tue Nov 04 11:56:24 2014 +0000
@@ -48,7 +48,7 @@
\item (I learned) jamming the closing
signal
\item relay signals\pause
-\item use diagnostic port to program
+\item use the diagnostic port to program
blank keys
\end{itemize}
\end{column}
@@ -135,7 +135,10 @@
\begin{center}
\includegraphics[scale=0.15]{../pics/cake.jpg}
-\end{center}
+\end{center}\pause\bigskip
+
+Solves the problem of communication when both parties
+distrust each other,
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -153,8 +156,8 @@
\end{tabular}
\end{center}
-\begin{textblock}{7}(1,2.5)
-The Alibaba cave:
+\begin{textblock}{7}(1,2)
+The Alibaba cave protocol:
\end{textblock}
\small
@@ -186,7 +189,10 @@
the idea is to force users to prove, using a
zero-knowledge proof, that their behaviour is correct
according to the protocol
-\end{itemize}
+\end{itemize}\bigskip
+
+\small
+digital currencies, smart cards, id cards
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -198,16 +204,20 @@
Zero-knowledge proof protocols should satisfy:\bigskip
\begin{itemize}
-\item \alert{\bf Completeness} If Alice knows the secret, Bob accepts Alice ``proof'' for sure.\bigskip
-\item \alert{\bf Soundness} If Alice does not know the secret, Bob accepts her ``proof'' with a very
-small probability.
-\end{itemize}
+\item \alert{\bf Completeness} If Alice knows the secret, Bob
+ accepts Alice ``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}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
\frametitle{Graph Isomorphism}
@@ -217,14 +227,15 @@
\end{tabular}
\end{center}
-Finding an isomorphism between two graphs is an NP complete problem.
-\end{frame}}
+Finding an isomorphism between two graphs is an NP-complete
+problem.
+
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{Graph Isomorphism Protocol}
+\frametitle{\Large Graph Isomorphism Protocol}
Alice starts with knowing an isomorphism \bl{$\sigma$} between graphs \bl{$G_1$} and \bl{$G_2$}\medskip
@@ -237,28 +248,58 @@
these are called commitment algorithms
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{Graph Isomorphism Protocol (2)}
+\frametitle{\Large Graph Isomorphism Protocol (2)}
-If Alice knows the isomorphism, she can always calculate \bl{$\sigma$}.\bigskip
+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$}.
+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}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
+\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{Graph Isomorphism Protocol (3)}
+\frametitle{\Large Graph Isomorphism Protocol (3)}
Why is the GI-protocol zero-knowledge?\bigskip\pause
@@ -270,51 +311,55 @@
and therefore participation in such a communication does not
increase Bob's capability to perform any computation.
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
\frametitle{Non-Interactive ZKPs}
-
+This is amazing: This can all be done ``offline'':
\bigskip
-This is amazing: Alison 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.
-\end{frame}}
+
+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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\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
+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$}
+\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}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
\frametitle{Problems of ZKPs}
\begin{itemize}
-\item ``grand chess master problem''\\
-(person in the middle)\bigskip
+\item ``grand chess master problem''\\ (person in the
+ middle again)\bigskip
-\item Alice can have multiple identities; once she committed a fraud she stops using one
+\item Alice can have multiple identities; once she committed a
+ fraud with one, she stops using one
\end{itemize}
\end{frame}}
@@ -380,7 +425,7 @@
\end{tabular}
\end{center}\bigskip
-Bob was send
+Bob was sent
\begin{center}
\bl{$r_j - r _j$}, \bl{$r_m - r _j$}, \ldots, \bl{$r_p - r _j$ \;mod \;p}
@@ -394,7 +439,6 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
\frametitle{Proving Stage}
@@ -413,58 +457,35 @@
\end{center}
\end{enumerate}\bigskip\pause
-In order to cheat, Alice has to guess all bits in advance. She has only \bl{$1$} to \bl{$2^z$}
-chance. \\
-\small\hspace{7mm}\textcolor{gray}{(explanation $\rightarrow$ \url{http://goo.gl/irL9GK})}
+In order to cheat, Alice has to guess all bits in advance. She
+has only \bl{$\frac{1}{2}^z$} chance.\bigskip\\
-\end{frame}}
+\small\hspace{7mm}
+\textcolor{gray}{(explanation $\rightarrow$ \url{http://goo.gl/irL9GK})}
+
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{Random Number Generators}
+\frametitle{Take Home Points}
\begin{itemize}
-\item Computers are deterministic. How do they generate random numbers?\bigskip\pause
-
-\item The most popular method to generate random numbers between \bl{$0$} and \bl{$m$} is: choose
-three integers
+\item this is pretty old work (in theory); seems
+ little used in practice (surprising)
-\begin{center}
-\begin{tabular}{ll}
-\bl{$a$} & multiplier\\
-\bl{$c$} & increment\\
-\bl{$X_0$} & start value
-\end{tabular}
-\end{center}
+\item for use in privacy the incentives are
+ not yet right
-and calculate
+\item digital cash (Bitcoins are not yet good enough)
-\begin{center}
-\bl{$X_{n+1} = (a * X_n + c) \;mod\; m$}
-\end{center}
\end{itemize}
-\only<3->{
-\begin{textblock}{7}(10,2)
-\begin{tikzpicture}
-\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm]
-{\begin{minipage}{3.8cm}
-\begin{tabular}{ll|l}
-\bl{$m =$} & \bl{$16$} & \bl{$16$}\\
-\bl{$X_0 =$} & \bl{$1$} & \bl{$1$}\\
-\bl{$a = $} & \bl{$5$} & \bl{$5$}\\
-\bl{$c =$} & \bl{$1$} & \bl{$0$}\\
-\end{tabular}
-\end{minipage}};
-\end{tikzpicture}
-\end{textblock}}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
\end{document}
%%% Local Variables: