# HG changeset patch # User Christian Urban # Date 1415102184 0 # Node ID 98403100cea7aad0dc507516abe86b4b49450048 # Parent b732a63c17b8e9a196588cdd6807d8f18937450b updated diff -r b732a63c17b8 -r 98403100cea7 slides/slides06.pdf Binary file slides/slides06.pdf has changed diff -r b732a63c17b8 -r 98403100cea7 slides/slides06.tex --- 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{ \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{ \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{ \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{ +\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{ \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{ \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{ \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{ \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{ \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: