protocol-basics.tex (11475B)
1 \section{Protocol Basics} 2 3 \begin{frame} 4 \vfill 5 \begin{center} 6 {\bf Protocol Basics} 7 \end{center} 8 \vfill 9 \end{frame} 10 11 12 \begin{frame}[plain] 13 \begin{tikzpicture}[remember picture,overlay] 14 \node[anchor=south west, inner sep=0pt] at (current page.south west) {% 15 \movie[height = \paperheight, width = \paperwidth, poster, showcontrols] {BFH Bachelor's thesis video}{cs-movie.mp4}% 16 }; 17 \end{tikzpicture} 18 \end{frame} 19 20 21 \begin{frame}{How does it work?} 22 We use a few ancient constructions: 23 \begin{itemize} 24 \item Cryptographic hash function (1989) 25 \item Blind signature (1983) 26 \item Schnorr signature (1989) 27 \item Diffie-Hellman key exchange (1976) or Unique signatures (1977) or VRF (1999) % 1977: RSA 28 \item Cut-and-choose zero-knowledge proof (1985) 29 \end{itemize} 30 But of course we use modern instantiations. 31 \end{frame} 32 33 34 \begin{frame}{Definition: Taxability} 35 We say Taler is taxable because: 36 \begin{itemize} 37 \item Merchant's income is visible from deposits. 38 \item Hash of contract is part of deposit data. 39 \item State can trace income and enforce taxation. 40 \end{itemize}\pause 41 Limitations: 42 \begin{itemize} 43 \item withdraw loophole 44 \item {\em sharing} coins among family and friends 45 \end{itemize} 46 \end{frame} 47 48 49 \begin{frame}{Exchange setup: Create a denomination key (RSA)} 50 \begin{minipage}{6cm} 51 \begin{enumerate} 52 \item Generate random primes $p,q$. 53 \item Compute $n := pq$, $\phi(n) = (p-1)(q-1)$ 54 \item Pick small $e < \phi(n)$ such that 55 $d := e^{-1} \mod \phi(n)$ exists. 56 \item Publish public key $(e,n)$. 57 \end{enumerate} 58 \end{minipage} 59 \begin{minipage}{6cm} 60 \begin{tikzpicture} 61 \tikzstyle{def} = [node distance=1em and 1em, inner sep=0em, outer sep=.3em]; 62 \node (origin) at (0,0) {\includegraphics[width=0.2\textwidth]{dice.pdf}}; 63 \node (primes) [draw=none, below = of origin] at (0,0) {$(p, q)$}; 64 \node (seal) [def, draw=none, below left=of primes]{\includegraphics[width=0.15\textwidth]{seal.pdf}}; 65 \node (hammer) [def, draw=none, below right=of primes]{\includegraphics[width=0.15\textwidth]{hammer.pdf}}; 66 67 \tikzstyle{C} = [color=black, line width=1pt] 68 69 \draw [<-, C] (primes) -- (origin) node [midway, above, sloped] (TextNode) {}; 70 \draw [<-, C] (seal) -- (primes) node [midway, above, sloped] (TextNode) {}; 71 \draw [<-, C] (hammer) -- (primes) node [midway, above, sloped] (TextNode) {}; 72 \end{tikzpicture} 73 % \includegraphics[width=0.4\textwidth]{seal.pdf} 74 \end{minipage} 75 \end{frame} 76 77 78 \begin{frame}{Merchant: Create a signing key (EdDSA)} 79 \begin{minipage}{6cm} 80 \begin{itemize} 81 \item Generate random number $m \mod o$ as private key 82 \item Compute public key $M := mG$ 83 \end{itemize} 84 \end{minipage} 85 \begin{minipage}{6cm} 86 \begin{tikzpicture} 87 \tikzstyle{def} = [node distance= 1em and 1em, inner sep=0em, outer sep=.3em]; 88 \node (origin) at (0,0) {\includegraphics[width=0.2\textwidth]{dice.pdf}}; 89 \node (m) [draw=none, below = of origin] at (0,0) {$m$}; 90 \node (seal) [draw=none, below=of m]{M}; 91 \tikzstyle{C} = [color=black, line width=1pt] 92 93 \draw [<-, C] (m) -- (origin) node [midway, above, sloped] (TextNode) {}; 94 \draw [<-, C] (seal) -- (primes) node [midway, above, sloped] (TextNode) {}; 95 \end{tikzpicture} 96 \end{minipage} 97 \parbox[t]{3cm}{{\bf Capability:} $m \Rightarrow$ } 98 \raisebox{\dimexpr-\height+\baselineskip}{\includegraphics[width=0.1\textwidth]{merchant-sign.pdf}} 99 \end{frame} 100 101 102 \begin{frame}{Customer: Create a planchet (EdDSA)} 103 \begin{minipage}{8cm} 104 \begin{itemize} 105 \item Generate random number $c \mod o$ as private key 106 \item Compute public key $C := cG$ 107 \end{itemize} 108 \end{minipage} 109 \begin{minipage}{4cm} 110 \begin{tikzpicture} 111 \tikzstyle{def} = [node distance= 1em and 1em, inner sep=0em, outer sep=.3em]; 112 \node (origin) at (0,0) {\includegraphics[width=0.2\textwidth]{dice.pdf}}; 113 \node (c) [draw=none, below = of origin] at (0,0) {$c$}; 114 \node (planchet) [draw=none, below=of c]{\includegraphics[width=0.4\textwidth]{planchet.pdf}}; 115 \tikzstyle{C} = [color=black, line width=1pt] 116 117 \draw [<-, C] (c) -- (origin) node [midway, above, sloped] (TextNode) {}; 118 \draw [<-, C] (planchet) -- (c) node [midway, above, sloped] (TextNode) {}; 119 \end{tikzpicture} 120 \end{minipage} 121 \parbox[t]{3cm}{{\bf Capability:} $c \Rightarrow$ } 122 \raisebox{\dimexpr-\height+\baselineskip}{\includegraphics[width=0.1\textwidth]{planchet-sign.pdf}} 123 \end{frame} 124 125 126 \begin{frame}{Customer: Blind planchet (RSA)} 127 \begin{minipage}{6cm} 128 \begin{enumerate} 129 \item Obtain public key $(e,n)$ 130 \item Compute $f := FDH(C)$, $f < n$. 131 \item Generate random blinding factor $b \in \mathbb Z_n$ 132 \item Transmit $f' := f b^e \mod n$ 133 \end{enumerate} 134 \end{minipage} 135 \begin{minipage}{6cm} 136 \begin{tikzpicture} 137 \tikzstyle{def} = [node distance= 2em and 0.5em, inner sep=0em, outer sep=.3em]; 138 \node (origin) at (0,0) {\includegraphics[width=0.2\textwidth]{dice.pdf}}; 139 \node (b) [def, draw=none, below = of origin] at (0,-0.2) {$b$}; 140 \node (blinded) [def, draw=none, below right=of b]{\includegraphics[width=0.2\textwidth]{blinded.pdf}}; 141 \node (planchet) [def, draw=none, above right=of blinded]{\includegraphics[width=0.15\textwidth]{planchet.pdf}}; 142 \node (exchange) [node distance=4em and 0.5em, draw, below =of blinded]{Exchange}; 143 \tikzstyle{C} = [color=black, line width=1pt] 144 145 \draw [<-, C] (b) -- (origin) node [midway, above, sloped] (TextNode) {}; 146 \draw [<-, C] (blinded) -- (planchet) node [midway, above, sloped] (TextNode) {}; 147 \draw [<-, C] (blinded) -- (b) node [midway, above, sloped] (TextNode) {}; 148 \draw [<-, C] (exchange) -- (blinded) node [midway, right] (TextNode) {{\small transmit}}; 149 \end{tikzpicture} 150 \end{minipage} 151 \end{frame} 152 153 154 \begin{frame}{Exchange: Blind sign (RSA)} 155 \begin{minipage}{6cm} 156 \begin{enumerate} 157 \item Receive $f'$. 158 \item Compute $s' := f'^d \mod n$. 159 \item Send signature $s'$. 160 \end{enumerate} 161 \end{minipage} 162 \begin{minipage}{6cm} 163 \begin{tikzpicture} 164 \tikzstyle{def} = [node distance= 2em and 0.5em, inner sep=0em, outer sep=.3em]; 165 \node (hammer) [def, draw=none] at (0,0) {\includegraphics[width=0.15\textwidth]{hammer.pdf}}; 166 \node (signed) [def, draw=none, below left=of hammer]{\includegraphics[width=0.2\textwidth]{sign.pdf}}; 167 \node (blinded) [def, draw=none, above left=of signed]{\includegraphics[width=0.15\textwidth]{blinded.pdf}}; 168 \node (customer) [node distance=4em and 0.5em, draw, below =of signed]{Customer}; 169 \tikzstyle{C} = [color=black, line width=1pt] 170 171 \draw [<-, C] (signed) -- (hammer) node [midway, above, sloped] (TextNode) {}; 172 \draw [<-, C] (signed) -- (blinded) node [midway, above, sloped] (TextNode) {}; 173 \draw [<-, C] (customer) -- (signed) node [midway, right] (TextNode) {{\small transmit}}; 174 \end{tikzpicture} 175 \end{minipage} 176 \end{frame} 177 178 179 \begin{frame}{Customer: Unblind coin (RSA)} 180 \begin{minipage}{6cm} 181 \begin{enumerate} 182 \item Receive $s'$. 183 \item Compute $s := s' b^{-1} \mod n$ % \\ 184 % ($(f')^d = (f b^e)^d = f^d b$). 185 \end{enumerate} 186 \end{minipage} 187 \begin{minipage}{6cm} 188 \begin{tikzpicture} 189 \tikzstyle{def} = [node distance= 2em and 0.5em, inner sep=0em, outer sep=.3em]; 190 \node (b) [def, draw=none] at (0,0) {$b$}; 191 \node (coin) [def, draw=none, below left=of b]{\includegraphics[width=0.2\textwidth]{coin.pdf}}; 192 \node (signed) [def, draw=none, above left=of coin]{\includegraphics[width=0.15\textwidth]{sign.pdf}}; 193 \tikzstyle{C} = [color=black, line width=1pt] 194 195 \draw [<-, C] (coin) -- (b) node [midway, above, sloped] (TextNode) {}; 196 \draw [<-, C] (coin) -- (signed) node [midway, above, sloped] (TextNode) {}; 197 \end{tikzpicture} 198 \end{minipage} 199 \end{frame} 200 201 202 \begin{frame}{Customer: Build shopping cart} 203 \begin{center} 204 \begin{tikzpicture} 205 \tikzstyle{def} = [node distance= 1em and 1em, inner sep=0em, outer sep=.3em]; 206 \node (origin) [draw=none] at (0,0) {\includegraphics[width=0.15\textwidth]{cart.pdf}}; 207 \node (merchant) [node distance=4em and 0.5em, draw, below =of origin]{\includegraphics[width=0.15\textwidth]{shop.pdf}}; 208 \tikzstyle{C} = [color=black, line width=1pt]; 209 \draw [<-, C] (merchant) -- (origin) node [midway, right] (TextNode) {{\small transmit}}; 210 \end{tikzpicture} 211 \end{center} 212 \end{frame} 213 214 215 \begin{frame}{Merchant: Propose contract (EdDSA)} 216 \begin{minipage}{6cm} 217 \begin{enumerate} 218 \item Complete proposal $D$. 219 \item Send $D$, $EdDSA_m(D)$ 220 \end{enumerate} 221 \end{minipage} 222 \begin{minipage}{6cm} 223 \begin{tikzpicture} 224 \tikzstyle{def} = [node distance=1.5em and 0.5em, inner sep=0em, outer sep=.3em]; 225 \node (cart) [def, draw=none] at (0,0) {\includegraphics[width=0.15\textwidth]{cart.pdf}}; 226 \node (proposal) [def, draw=none, below right=of cart]{\includegraphics[width=0.3\textwidth]{merchant_propose.pdf}}; 227 \node (customer) [node distance=4em and 0.5em, draw, below =of proposal]{Customer}; 228 \tikzstyle{C} = [color=black, line width=1pt]; 229 \node (sign) [def, draw=none, above right=of proposal] {$m$}; 230 \tikzstyle{C} = [color=black, line width=1pt] 231 232 \draw [<-, C] (proposal) -- (sign) node [midway, above, sloped] (TextNode) {}; 233 \draw [<-, C] (proposal) -- (cart) node [midway, above, sloped] (TextNode) {}; 234 \draw [<-, C] (customer) -- (proposal) node [midway, right] (TextNode) {{\small transmit}}; 235 \end{tikzpicture} 236 \end{minipage} 237 \end{frame} 238 239 240 \begin{frame}{Customer: Spend coin (EdDSA)} 241 \begin{minipage}{6cm} 242 \begin{enumerate} 243 \item Receive proposal $D$, $EdDSA_m(D)$. 244 \item Send $s$, $C$, $EdDSA_c(D)$ 245 \end{enumerate} 246 \end{minipage} 247 \begin{minipage}{6cm} 248 \begin{tikzpicture} 249 \tikzstyle{def} = [node distance=1.3em and 0.4em, inner sep=0em, outer sep=.3em]; 250 \node (proposal) [def, draw=none] at (0,0) {\includegraphics[width=0.15\textwidth]{merchant_propose.pdf}}; 251 \node (contract) [def, draw=none, below right=of cart]{\includegraphics[width=0.3\textwidth]{contract.pdf}}; 252 \node (c) [def, draw=none, above=of contract] {$c$}; 253 \node (merchant) [node distance=4em and 0.5em, draw, below=of contract]{Merchant}; 254 \node (coin) [def, draw=none, right=of contract]{\includegraphics[width=0.2\textwidth]{coin.pdf}}; 255 \tikzstyle{C} = [color=black, line width=1pt] 256 257 \draw [<-, C] (contract) -- (c) node [midway, above, sloped] (TextNode) {}; 258 \draw [<-, C] (contract) -- (proposal) node [midway, above, sloped] (TextNode) {}; 259 \draw [<-, C] (merchant) -- (contract) node [midway, left] (TextNode) {{\small transmit}}; 260 \draw [<-, C] (merchant) -- (coin) node [midway, right] (TextNode) {{\small transmit}}; 261 \end{tikzpicture} 262 \end{minipage} 263 \end{frame} 264 265 266 \begin{frame}{Merchant and Exchange: Verify coin (RSA)} 267 \begin{minipage}{6cm} 268 \begin{equation*} 269 s^e \stackrel{?}{\equiv} FDH(C) \mod n 270 \end{equation*} 271 \end{minipage} 272 \begin{minipage}{6cm} 273 \begin{minipage}{0.2\textwidth} 274 \includegraphics[width=\textwidth]{coin.pdf} 275 \end{minipage} 276 $\stackrel{?}{\Leftrightarrow}$ 277 \begin{minipage}{0.2\textwidth} 278 \includegraphics[width=\textwidth]{seal.pdf} 279 \end{minipage} 280 \end{minipage} 281 \vfill 282 The exchange does not only verify the signature, but also 283 checks that the coin was not double-spent. 284 \vfill 285 \pause 286 \begin{center} 287 {\bf Taler is an online payment system.} 288 \end{center} 289 \vfill 290 \end{frame}