sen-material: comparison slides/slides06.tex

equal deleted inserted replaced

-:b732a63c17b8
+:98403100cea7
 \begin{column}[T]{6cm}
 \begin{itemize}
 \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}
 \end{columns}
 Q: How to cut a cake into two equal slices?
 \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}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \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.5)
+\begin{textblock}{7}(1,2)
-The Alibaba cave:
+The Alibaba cave protocol:
 \end{textblock}
 \small
 \only<2>{
 \begin{textblock}{12}(2,13.3)
 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}
+\end{itemize}\bigskip
+\small
+digital currencies, smart cards, id cards
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \frametitle{Central Properties}
 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 Completeness} If Alice knows the secret, Bob
-\item \alert{\bf Soundness} If Alice does not know the secret, Bob accepts her ``proof'' with a very
+accepts Alice ``proof'' for sure.\bigskip
-small probability.
+\item \alert{\bf Soundness} If Alice does not know the secret,
-\end{itemize}
+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}
 \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.
+Finding an isomorphism between two graphs is an NP-complete
-\end{frame}}
+problem.
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\frametitle{Graph Isomorphism Protocol}
+\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 Alice and Bob repeat this procedure \bl{$n$} times
 \end{enumerate}\pause
 these are called commitment algorithms
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
+\begin{frame}[c]
-\begin{frame}[c]
+\frametitle{\Large Graph Isomorphism Protocol (2)}
-\frametitle{Graph Isomorphism Protocol (2)}
+If Alice knows the isomorphism, she can always calculate
-If Alice knows the isomorphism, she can always calculate \bl{$\sigma$}.\bigskip
+\bl{$\sigma$}.\bigskip
-If she doesn't, she can only correctly respond if Bob's
+If she doesn't, she can only correctly respond if Bob's choice
-choice of index is the same as the one she used to form \bl{$H$}. The probability
+of index is the same as the one she used to form \bl{$H$}. The
-of this happening is \bl{$\frac{1}{2}$}, so after \bl{$n$} rounds the probability of her
+probability of this happening is \bl{$\frac{1}{2}$}, so after
-always responding correctly is only \bl{$\frac{1}{2}^n$}.
+\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]
-\begin{frame}[c]
+\frametitle{Plot of $\frac{1}{2}^n$}
-\frametitle{Graph Isomorphism Protocol (3)}
+\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}}
+\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.
+Alice can publish some data that contains no data about her
-\end{frame}}
+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).
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
+\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
+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 Alice generates \bl{$n$} isomorphic graphs
-\item she feeds the \bl{$H_{1..n}$} into a hashing function (she has no control over what
+\bl{$H_{1..n}$} which she makes public
-	the output will be)
+\item she feeds the \bl{$H_{1..n}$} into a hashing function
-\item Alice takes the first \bl{$n$} bits of the output: whenever output is \bl{$0$}, she shows
+(she has no control over what the output will be)
-an isomorphism with \bl{$G_1$} ; for \bl{$1$} she shows an isomorphism with \bl{$G_2$}
+\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''\\
+\item ``grand chess master problem''\\ (person in the
-(person in the middle)\bigskip
+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}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \bl{$b_i = 0$}: & \bl{$A^{s_i} \equiv B\;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 send
+Bob was sent
 \begin{center}
 \bl{$r_j - r _j$},  \bl{$r_m - r _j$}, \ldots, \bl{$r_p - r _j$ \;mod \;p}
 \end{center}
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 \frametitle{Proving Stage}
 \begin{enumerate}
 \item Alice proves she knows \bl{$x$}, the discrete log of \bl{$B$}\\
 \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{$1$} to \bl{$2^z$}
+In order to cheat, Alice has to guess all bits in advance. She
-chance. \\
+has only \bl{$\frac{1}{2}^z$} chance.\bigskip\\
-\small\hspace{7mm}\textcolor{gray}{(explanation $\rightarrow$ \url{http://goo.gl/irL9GK})}
+\small\hspace{7mm}
-\end{frame}}
+\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 this is pretty old work (in theory); seems
+little used in practice (surprising)
-\item The most popular method to generate random numbers between \bl{$0$} and \bl{$m$} is: choose
-three integers
+\item for use in privacy the incentives are
+not yet right
-\begin{center}
-\begin{tabular}{ll}
+\item digital cash (Bitcoins are not yet good enough)
-\bl{$a$} & multiplier\\
-\bl{$c$} & increment\\
-\bl{$X_0$} & start value
-\end{tabular}
-\end{center}
-and calculate
-\begin{center}
-\bl{$X_{n+1} = (a * X_n + c) \;mod\; m$}
-\end{center}
 \end{itemize}
-\only<3->{
+\end{frame}
-\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{document}
 %%% Local Variables:
 %%% mode: latex
 %%% TeX-master: t

changeset 281	98403100cea7
parent 280	b732a63c17b8
child 282	4a0071e26cb5