\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}{APP 06, King's College London}\begin{document}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\begin{frame}[t]\frametitle{% \begin{tabular}{@ {}c@ {}} \\ \LARGE Access Control and \\[-3mm] \LARGE Privacy Policies (6)\\[-6mm] \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{Problems with Key Fobs}\begin{columns}\begin{column}[T]{4cm}\includegraphics[scale=0.4]{../pics/car-standard.jpg}\end{column}\begin{column}[T]{6cm} \begin{itemize}\item (I learned) jamming the closing signal\item relay signals\pause\item use the diagnostic port to program blank keys \end{itemize}\end{column}\end{columns}\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\bigskipAlice and Bob solve crosswords. Alice knows the answer for 21D (folio) but doesn't want to tell Bob.\medskipYou 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\smallSolves the problem of communication when both partiesdistrust 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 beconvincing to anyone else (Alice and Bob could have made itall up).\end{textblock}}\only<3>{\begin{textblock}{12}(2,13.3)Even worse, an observer present at the experiment would not beconvinced.\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\smalldigital 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 ``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\\0 & 0\\1 & 3\\2 & 1\\3 & 2\\4 & 5\\5 & 4\\\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 anisomorphism 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}\pausethese 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$}.\bigskipIf she doesn't, she can only correctly respond if Bob's choiceof index is the same as the one she used to form \bl{$H$}. Theprobability of this happening is \bl{$\frac{1}{2}$}, so after\bl{$n$} rounds the probability of her always respondingcorrectly 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\pauseA: We can generate a fake transcript of a conversation, which cannot be distinguished from a ``real'' conversation.\bigskipAnything Bob can compute using the information obtained fromthe transcript can be computed using only a forged transcriptand therefore participation in such a communication does notincrease 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'': \bigskipAlice can publish some data that contains no data about hersecret, but this data can be used to convince anyone of thesecret's existence (whether Alice knows it, must beestablished my other means).\end{frame}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\begin{frame}[c]\frametitle{Non-Interactive ZKPs (2)}Alice starts with knowing an isomorphism \bl{$\sigma$} betweengraphs \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 B\;mod\;p$}\\\bl{$b_i = 1$}: & \bl{$A^{s_i} \equiv h_i * h_j^{-1} \;mod\; p$}\\\end{tabular}\end{center}\bigskipBob was sent\begin{center}\bl{$r_j - r _j$}, \bl{$r_m - r _j$}, \ldots, \bl{$r_p - r _j$ \;mod \;p} \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\pauseIn order to cheat, Alice has to guess all bits in advance. Shehas only \bl{$\frac{1}{2}^z$} chance.\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)\end{itemize}\end{frame}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\end{document}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: