refresh.tex (31780B)
1 2 \begin{frame}{Giving change} 3 \note[item]{Taler issues digital cash using blind signatures, where each 4 signature conveys the respective coin a particular value.} 5 It would be inefficient to pay EUR 100 with 1 cent coins! 6 \note[item]{We want to avoid cryptographic expenses linear in the amount being paid!} 7 \begin{itemize} 8 \item Denomination key represents value of a coin. 9 \item Exchange may offer various denominations. 10 \item Wallet may not have exact change! 11 \item Must be able to pay given sufficient total funds. 12 \end{itemize}\pause 13 Key goals: 14 \begin{itemize} 15 \item maintain unlinkability 16 \item maintain taxability of transactions 17 \end{itemize}\pause 18 Method: 19 \begin{itemize} 20 \item Contract can specify to pay {\em partial value} of a coin. 21 \item Allow wallet to obtain {\em unlinkable change}. 22 \end{itemize} 23 \note[item]{Thus we need a way to get change, but doing so must not void our security 24 assurances, specifically unlinkability (and anonymity) for the payer, and income 25 transparency for the payee.} 26 \note[item]{The high-level approach for getting change is pretty simple: when paying 27 with a coin, the (EdDSA) coin signature can specify that not the full value of the coin 28 is to be spent, but only a fraction. The exchange then allows a wallet to request 29 change by creating a second signature using the partially spent coin's private (EdDSA) 30 key over a change request with fresh (blinded) digital coins that total up to the 31 amount of change that is due.} 32 \end{frame} 33 34 35 \begin{frame}{Unique Signatures} 36 \vfill 37 \begin{minipage}{8cm} 38 \begin{itemize} 39 \item Some public key operations depend on a nonce or ``random'' value 40 \begin{itemize} 41 \item Ex.: DSA/ECDSA (signing) 42 \item[+] same plaintext, different ciphertext 43 \item[-] security may break on nonce-reuse 44 \end{itemize} 45 \item Generating the nonce deterministically by hashing all inputs 46 (see also: Fiat-Shamir transformation) can make these algorithms 47 {\bf deterministic} 48 \begin{itemize} 49 \item Ex.: EdDSA 50 \end{itemize} 51 \item If only one form of a valid signature exists and the verifier 52 can check this, a signature is {\bf unique}. 53 \begin{itemize} 54 \item Ex.: RSA, Verifiable Random Func. 55 \end{itemize} 56 \end{itemize} 57 \end{minipage} 58 \begin{minipage}{4cm} 59 {\small Unique signatures:} 60 \begin{center} 61 \includegraphics[width=0.5\textwidth]{ecollect.jpeg} 62 63 $=$ 64 65 \includegraphics[width=0.5\textwidth]{unisig.pdf} 66 \end{center} 67 \end{minipage} 68 \vfill 69 \note[item]{Before we can introduce the change protocol, we need to consider that 70 not all cryptographic signatures are unique.} 71 \note[item]{Following modern approach to e-collecting, we will use the image on 72 the right to illustrate {\bf unique} signatures.} 73 \note[item]{Replacing random inputs or nonces with hashes is a common trick to 74 make signature algorithms deterministic, but not usually unique.} 75 \end{frame} 76 77 78 \begin{frame}{Verifiable Random Functions} 79 Micali, Rabin, \& Vadhan (1999) proposed verifiable random functions. 80 81 \vfill 82 83 Let $M$ be some input. 84 \begin{itemize} 85 \item $(sk,pk) := VRF_{keygen}()$ 86 \item {\em Verifier} picks $M$ 87 \item $(v,p) := VRF_{sign}(M, sk)$ 88 \item $v$ is deterministic, unpredictable and high-entropy 89 for any $M$ and $sk$, and $(v,p)$ can only be computed with $sk$ 90 \item $VRF_{verify}(M, pk, v, p)$ returns true only if $v$ was computed correctly 91 \item $sk$ cannot be derived from $M$, $pk$, $v$ and $p$ 92 \end{itemize} 93 \vfill 94 \note[item]{A VRF is equivalent to a unique signature: only 95 the signer can produce it, the verifier can check but not compute it. 96 The only differences are that with a unique signature 97 usually the signer picks $M$, and the signature is not 98 then hashed to produced pseudo-random data. But one can 99 always use a unique signature to construct a VRF and vice-versa.} 100 \end{frame} 101 102 103 104 \begin{frame}{Straw-man solution} 105 \begin{minipage}{7.5cm} 106 {\small Given partially spent private coin key $c_{old}$:} 107 \begin{enumerate} 108 % \item Let $C_{old} := c_{old}G$ (as before) 109 \item Pick random $c_{new} \mod o$ private key 110 \item Compute $C_{new} := c_{new}G$ public key 111 \item Pick random $b_{new}$ 112 \item Compute $f_{new} := FDH(C_{new})$, $m < n$. 113 \item Transmit $f'_{new} := f_{new} b_{new}^e \mod n$ 114 \end{enumerate} 115 ... and sign request for change with $c_{old}$. 116 \end{minipage} 117 \begin{minipage}{3cm} 118 \begin{tikzpicture} 119 \tikzstyle{def} = [node distance= 1.5em and 0.5em, inner sep=0em, outer sep=.3em]; 120 \node (blinded) [def, draw=none]{\includegraphics[width=0.15\textwidth]{blinded.pdf}}; 121 \node (planchet) [def, draw=none, above left= of blinded] {\includegraphics[width=0.15\textwidth]{planchet.pdf}}; 122 \node (cnew) [def, draw=none, above= of planchet] {$c_{new}$}; 123 \node (bnew) [def, draw=none, above right= of blinded] {$b_{new}$}; 124 \node (dice1) [def, draw=none, above = of cnew]{\includegraphics[width=0.2\textwidth]{dice.pdf}}; 125 \node (dice2) [def, draw=none, above = of bnew]{\includegraphics[width=0.2\textwidth]{dice.pdf}}; 126 \node (exchange) [def, draw, below =of blinded]{Exchange}; 127 128 \tikzstyle{C} = [color=black, line width=1pt] 129 130 \draw [<-, C] (cnew) -- (dice1) node [midway, above, sloped] (TextNode) {}; 131 \draw [<-, C] (planchet) -- (cnew) node [midway, above, sloped] (TextNode) {}; 132 \draw [<-, C] (bnew) -- (dice2) node [midway, above, sloped] (TextNode) {}; 133 \draw [<-, C] (blinded) -- (planchet) node [midway, above, sloped] (TextNode) {}; 134 \draw [<-, C] (blinded) -- (bnew) node [midway, above, sloped] (TextNode) {}; 135 \draw [<-, C] (exchange) -- (blinded) node [midway, right] (TextNode) {{\small transmit}}; 136 \end{tikzpicture} 137 \end{minipage} 138 \note[item]{A straw-man solution is one that does not work, but still could be useful to illuminate the issue.} 139 \note[item]{Here, the protocol allows users to obtain change ($c_{new}$) by signing the request for 140 change (the envelope) with an old coin $c_{old}$ that has some residual value from a previous 141 purchase (that signature is not shown).} 142 \note[item]{{\bf Problem}: Owner of $c_{new}$ may differ from owner of $c_{old}$ breaks income-transparency / enables 143 tax evasion!} 144 \end{frame} 145 146 147 \begin{frame}{Customer: Transfer setup (UNISIG)} \label{page:transfersetup} 148 \begin{minipage}{7.5cm} 149 {\small Given partially spent private coin key $c_{old}$:} 150 \begin{enumerate} 151 \item Let $C_{old} := c_{old}G$ (as before) 152 \item Create random nonce $t$ 153 \item Compute unique signature $X := UNISIG_{c_{old}}(t)$ 154 \item Derive $c_{new}$ and $b_{new}$ from $X$ using HKDF 155 \item Compute $C_{new} := c_{new}G$ 156 \item Compute $f_{new} := FDH(C_{new})$ 157 \item Transmit $f_{new}' := f_{new} b_{new}^e$ 158 \end{enumerate} 159 \end{minipage} 160 \begin{minipage}{3cm} 161 \begin{tikzpicture} 162 \tikzstyle{def} = [node distance= 1.5em and 0.5em, inner sep=0em, outer sep=.3em]; 163 \node (t) [def, draw=none] at (0,0) {$t$}; 164 \node (dice) [def, draw=none, above = of t]{\includegraphics[width=0.2\textwidth]{dice.pdf}}; 165 \node (X) [def, draw=none, below left=of t]{\includegraphics[width=0.2\textwidth]{unisig.pdf}}; 166 \node (d) [def, draw=none, above left= of X] {$c_{old}$}; 167 \node (cp) [def, draw=none, below left= of X] {$c_{new}$}; 168 \node (bp) [def, draw=none, below right= of X] {$b_{new}$}; 169 \node (blinded) [def, draw=none, below right=of cp]{\includegraphics[width=0.15\textwidth]{blinded.pdf}}; 170 \node (exchange) [def, draw, below =of blinded]{Exchange}; 171 172 \tikzstyle{C} = [color=black, line width=1pt] 173 174 \draw [<-, C] (X) -- (d) node [midway, above, sloped] (TextNode) {}; 175 \draw [<-, C] (X) -- (t) node [midway, above, sloped] (TextNode) {}; 176 \draw [<-, C] (t) -- (dice) node [midway, above, sloped] (TextNode) {}; 177 \draw [<-, C] (cp) -- (X) node [midway, above, sloped] (TextNode) {}; 178 \draw [<-, C] (bp) -- (X) node [midway, above, sloped] (TextNode) {}; 179 \draw [<-, C] (blinded) -- (cp) node [midway, above, sloped] (TextNode) {}; 180 \draw [<-, C] (blinded) -- (bp) node [midway, above, sloped] (TextNode) {}; 181 \draw [<-, C] (exchange) -- (blinded) node [midway, right] (TextNode) {{\small transmit}}; 182 \end{tikzpicture} 183 \end{minipage} 184 \note[item]{In this construction, we {\em derive} the blinding factor $b_{new}$ and 185 the private key of the new coin $c_{new}$ from the DH of the $c_{old}$ and a newly 186 created transfer key $t$. Note that it is a bit unusual but perfectly find that 187 we here have {\bf both} private keys to compute the DH.} 188 \note[item]{The resulting blinded public key of the new coin 189 (public key derivation and blinding are elided to keep the diagram concise) is 190 then signed with $c_{old}$ to request change.} 191 \note[item]{This approach has an obvious problem: from the perspective of the 192 Exchange, we cannot even tell that the user followed this procedure as the 193 resulting request with the blinded coin is indistinguishable from the previous 194 construction.} 195 \end{frame} 196 197 198 \begin{frame}{Cut-and-Choose} 199 \begin{minipage}{3cm} 200 \begin{tikzpicture} 201 \tikzstyle{def} = [node distance= 1.5em and 0.05em, inner sep=0em, outer sep=.3em]; 202 \node (t) [def, draw=none] at (0,0) {$t_1$}; 203 \node (dice) [def, draw=none, above = of t]{\includegraphics[width=0.2\textwidth]{dice.pdf}}; 204 \node (dh) [def, draw=none, below left=of t]{\includegraphics[width=0.2\textwidth]{unisig.pdf} ($X_1$)}; 205 \node (d) [def, draw=none, above left= of dh] {$c_{old}$}; 206 \node (cp) [def, draw=none, below left= of dh] {$c_{new,1}$}; 207 \node (bp) [def, draw, below right= of dh, draw=none, align=left] {$\hspace{-1.5em}b_{new,1}$}; 208 \node (blinded) [def, draw=none, below right=of cp]{\includegraphics[width=0.15\textwidth]{blinded.pdf}}; 209 \node (exchange) [def, draw, below =of blinded]{Exchange}; 210 211 \tikzstyle{C} = [color=black, line width=1pt] 212 213 \draw [<-, C] (t) -- (dice) node [midway, above, sloped] (TextNode) {}; 214 \draw [<-, C] (dh) -- (d) node [midway, above, sloped] (TextNode) {}; 215 \draw [<-, C] (dh) -- (t) node [midway, above, sloped] (TextNode) {}; 216 \draw [<-, C] (cp) -- (dh) node [midway, above, sloped] (TextNode) {}; 217 \draw [<-, C] (bp) -- (dh) node [midway, above, sloped] (TextNode) {}; 218 \draw [<-, C] (blinded) -- (cp) node [midway, above, sloped] (TextNode) {}; 219 \draw [<-, C] (blinded) -- (bp) node [midway, above, sloped] (TextNode) {}; 220 \draw [<-, C] (exchange) -- (blinded) node [midway, right] (TextNode) {{\small transmit}}; 221 \end{tikzpicture} 222 \end{minipage} 223 \hfill 224 \begin{minipage}{3cm} 225 \begin{tikzpicture} 226 \tikzstyle{def} = [node distance= 1.5em and 0.05em, inner sep=0em, outer sep=.3em]; 227 \node (t) [def, draw=none] at (0,0) {$t_2$}; 228 \node (dice) [def, draw=none, above = of t]{\includegraphics[width=0.2\textwidth]{dice.pdf}}; 229 \node (dh) [def, draw=none, below left=of t]{\includegraphics[width=0.2\textwidth]{unisig.pdf} ($X_2$)}; 230 \node (d) [def, draw=none, above left= of dh] {$c_{old}$}; 231 \node (cp) [def, draw=none, below left= of dh] {$c_{new,2}$}; 232 \node (bp) [def, draw, below right= of dh, draw=none, align=left] {$\hspace{-1.5em}b_{new,2}$}; 233 \node (blinded) [def, draw=none, below right=of cp]{\includegraphics[width=0.15\textwidth]{blinded.pdf}}; 234 \node (exchange) [def, draw, below =of blinded]{Exchange}; 235 236 \tikzstyle{C} = [color=black, line width=1pt] 237 238 \draw [<-, C] (t) -- (dice) node [midway, above, sloped] (TextNode) {}; 239 \draw [<-, C] (dh) -- (d) node [midway, above, sloped] (TextNode) {}; 240 \draw [<-, C] (dh) -- (t) node [midway, above, sloped] (TextNode) {}; 241 \draw [<-, C] (cp) -- (dh) node [midway, above, sloped] (TextNode) {}; 242 \draw [<-, C] (bp) -- (dh) node [midway, above, sloped] (TextNode) {}; 243 \draw [<-, C] (blinded) -- (cp) node [midway, above, sloped] (TextNode) {}; 244 \draw [<-, C] (blinded) -- (bp) node [midway, above, sloped] (TextNode) {}; 245 \draw [<-, C] (exchange) -- (blinded) node [midway, right] (TextNode) {{\small transmit}}; 246 \end{tikzpicture} 247 \end{minipage} 248 \hfill 249 \begin{minipage}{3cm} 250 \begin{tikzpicture} 251 \tikzstyle{def} = [node distance= 1.5em and 0.05em, inner sep=0em, outer sep=.3em]; 252 \node (t) [def, draw=none] at (0,0) {$t_3$}; 253 \node (dice) [def, draw=none, above = of t]{\includegraphics[width=0.2\textwidth]{dice.pdf}}; 254 \node (dh) [def, draw=none, below left=of t]{\includegraphics[width=0.2\textwidth]{unisig.pdf} ($X_3$)}; 255 \node (d) [def, draw=none, above left= of dh] {$c_{old}$}; 256 \node (cp) [def, draw=none, below left= of dh] {$c_{new,3}$}; 257 \node (bp) [def, draw, below right= of dh, draw=none, align=left] {$\hspace{-1.5em}b_{new,3}$}; 258 \node (blinded) [def, draw=none, below right=of cp]{\includegraphics[width=0.15\textwidth]{blinded.pdf}}; 259 \node (exchange) [def, draw, below =of blinded]{Exchange}; 260 261 \tikzstyle{C} = [color=black, line width=1pt] 262 263 \draw [<-, C] (t) -- (dice) node [midway, above, sloped] (TextNode) {}; 264 \draw [<-, C] (dh) -- (d) node [midway, above, sloped] (TextNode) {}; 265 \draw [<-, C] (dh) -- (t) node [midway, above, sloped] (TextNode) {}; 266 \draw [<-, C] (cp) -- (dh) node [midway, above, sloped] (TextNode) {}; 267 \draw [<-, C] (bp) -- (dh) node [midway, above, sloped] (TextNode) {}; 268 \draw [<-, C] (blinded) -- (cp) node [midway, above, sloped] (TextNode) {}; 269 \draw [<-, C] (blinded) -- (bp) node [midway, above, sloped] (TextNode) {}; 270 \draw [<-, C] (exchange) -- (blinded) node [midway, right] (TextNode) {{\small transmit}}; 271 \end{tikzpicture} 272 \end{minipage} 273 \note[item]{This DH-construction thus obviously does not work, so in the usual 274 approach of an insane person, we don't just do it once, but three times 275 using three different transfer keys $t_1$, $t_2$, and $t_3$ instead of just $t$.} 276 \note[item]{Now, before you decide that we have just gone mad, this is actually 277 a well-known technique called {\bf cut-and-choose}. Here, we do a protocol 278 step multiple times to basically be able to {\bf burn} some of these iterations 279 to {\bf prove} our honesty.} 280 \note[item]{There are also {\bf non-interactive} cut-and-choose protocols, but 281 this one is a simple interactive one.} 282 \end{frame} 283 284 285 \begin{frame}{Exchange: Choose!} 286 \begin{center} 287 \item Exchange sends back random $\gamma \in \{ 1, 2, 3 \}$ to the customer. 288 \end{center} 289 \note[item]{This is the typical interaction: the Exchange picks one of the 290 three at random, basically deciding on which iterations to challenge the 291 wallet's honesty.} 292 \note[item]{$\gamma$ primarily needs to be {\bf unpredictable} for the wallet.} 293 \note[item]{Note that the protocol has a security parameter $\kappa=3$, and 294 so the wallet could guess correctly in $\frac{1}{3}$ of the cases. Usually 295 in security we would think of this to be way too low, and you will see much 296 higher values in other cut-and-choose protocols. But, we will see why 297 $\kappa=3$ is actually enough for GNU Taler!} 298 \end{frame} 299 300 301 \begin{frame}{Customer: Reveal} 302 \vfill 303 \begin{enumerate} 304 \item If $\gamma = 1$, send $\langle t_2, X_2 \rangle$, $\langle t_3, X_3 \rangle$ to exchange 305 \item If $\gamma = 2$, send $\langle t_1, X_1 \rangle$, $\langle t_3, X_3 \rangle$ to exchange 306 \item If $\gamma = 3$, send $\langle t_1, X_1 \rangle$, $\langle t_2, X_2 \rangle$ to exchange 307 \end{enumerate} 308 \vfill 309 \note[item]{So given the $\gamma$ challenge value, the wallet 310 has to send back the $t_i$ values for $i\not=\gamma$.} 311 \end{frame} 312 313 314 \begin{frame}{Exchange: Verify ($\gamma = 2$)} 315 \begin{minipage}{3cm} 316 \begin{tikzpicture} 317 \tikzstyle{def} = [node distance= 1.5em and 0.5em, inner sep=0em, outer sep=.3em]; 318 \node (h) [def, draw=none] at (0,0) {$t_1$}; 319 \node (dh) [def, draw=none, below left=of h]{\includegraphics[width=0.2\textwidth]{univerify.pdf}}; 320 \node (d) [def, draw=none, above left= of dh] {$C_{old}$}; 321 \node (cp) [def, draw=none, below left= of dh] {$c_{new,1}$}; 322 \node (bp) [def, draw=none, below right= of dh] {$b_{new,1}$}; 323 \node (blinded) [def, draw=none, below right=of cp]{\includegraphics[width=0.15\textwidth]{blinded.pdf}}; 324 325 \tikzstyle{C} = [color=black, line width=1pt] 326 327 \draw [<-, C] (dh) -- (d) node [midway, above, sloped] (TextNode) {}; 328 \draw [<-, C] (dh) -- (h) node [midway, above, sloped] (TextNode) {}; 329 \draw [<-, C] (cp) -- (dh) node [midway, above, sloped] (TextNode) {}; 330 \draw [<-, C] (bp) -- (dh) node [midway, above, sloped] (TextNode) {}; 331 \draw [<-, C] (blinded) -- (cp) node [midway, above, sloped] (TextNode) {}; 332 \draw [<-, C] (blinded) -- (bp) node [midway, above, sloped] (TextNode) {}; 333 \end{tikzpicture} 334 \end{minipage} 335 \hfill 336 \begin{minipage}{3cm} 337 \ 338 \end{minipage} 339 \hfill 340 \begin{minipage}{3cm} 341 \begin{tikzpicture} 342 \tikzstyle{def} = [node distance= 1.5em and 0.5em, inner sep=0em, outer sep=.3em]; 343 \node (h) [def, draw=none] at (0,0) {$t_3$}; 344 \node (dh) [def, draw=none, below left=of h]{\includegraphics[width=0.2\textwidth]{univerify.pdf}}; 345 \node (d) [def, draw=none, above left= of dh] {$C_{old}$}; 346 \node (cp) [def, draw=none, below left= of dh] {$c_{new,3}$}; 347 \node (bp) [def, draw=none, below right= of dh] {$b_{new,3}$}; 348 \node (blinded) [def, draw=none, below right=of cp]{\includegraphics[width=0.15\textwidth]{blinded.pdf}}; 349 350 \tikzstyle{C} = [color=black, line width=1pt] 351 352 \draw [<-, C] (dh) -- (d) node [midway, above, sloped] (TextNode) {}; 353 \draw [<-, C] (dh) -- (h) node [midway, above, sloped] (TextNode) {}; 354 \draw [<-, C] (cp) -- (dh) node [midway, above, sloped] (TextNode) {}; 355 \draw [<-, C] (bp) -- (dh) node [midway, above, sloped] (TextNode) {}; 356 \draw [<-, C] (blinded) -- (cp) node [midway, above, sloped] (TextNode) {}; 357 \draw [<-, C] (blinded) -- (bp) node [midway, above, sloped] (TextNode) {}; 358 \end{tikzpicture} 359 \end{minipage} 360 \note[item]{Given those two values the exchange can {\bf validate} the 361 construction as it can compute the DH from the {\bf transfer private keys} $t_i$ 362 and the {\bf coin public key} $C_{old}$.} 363 \note[item]{If the result matches with the original request from the wallet, 364 the exchange has established that with $\frac{2}{3}$ probability the wallet 365 made an honest request for change following the prescribed construction.} 366 \note[item]{If the wallet is unable (or unwilling) to produce the required 367 $t_i$ values, or if the resulting blinded values do not match, the entire 368 change is forfeit, and the customer looses their money.} 369 \note[item]{Thus, trying to cheat on income-transparency is punished with 370 what amounts to a {\bf 66.67\% tax}. Thus, a security level of $\kappa$ 371 is sufficient as long as the {\em effective} income tax (after deductions, 372 on the full income) is below $\frac{\kappa - 1}{\kappa}$. 373 Taler always uses $\kappa=3$.} 374 \end{frame} 375 376 377 \begin{frame}{Exchange: Blind sign change (RSA)} 378 \begin{minipage}{5cm} 379 \begin{enumerate} 380 \item Take $f_{new,\gamma}'$. 381 \item Compute \\ 382 $s' := f_{new,\gamma}'^d \mod n$. 383 \item Return signature $s'$. 384 \end{enumerate} 385 \end{minipage} 386 \begin{minipage}{5cm} 387 \begin{tikzpicture} 388 \tikzstyle{def} = [node distance= 2em and 0.5em, inner sep=0em, outer sep=.3em]; 389 \node (hammer) [def, draw=none] at (0,0) {\includegraphics[width=0.15\textwidth]{hammer.pdf}}; 390 \node (signed) [def, draw=none, below left=of hammer]{\includegraphics[width=0.2\textwidth]{sign.pdf}}; 391 \node (blinded) [def, draw=none, above left=of signed]{\includegraphics[width=0.15\textwidth]{blinded.pdf}}; 392 \node (customer) [node distance=4em and 0.5em, draw, below =of signed]{Customer}; 393 \tikzstyle{C} = [color=black, line width=1pt] 394 395 \draw [<-, C] (signed) -- (hammer) node [midway, above, sloped] (TextNode) {}; 396 \draw [<-, C] (signed) -- (blinded) node [midway, above, sloped] (TextNode) {}; 397 \draw [<-, C] (customer) -- (signed) node [midway, right] (TextNode) {{\small transmit}}; 398 \end{tikzpicture} 399 \end{minipage} 400 \note[item]{If the customer's request did follow the DH-construction, the exchange takes the 401 third envelope, the one where $t_\gamma$ was not disclosed, and signs this one to issue the 402 change.} 403 \end{frame} 404 405 406 \begin{frame}{Customer: Unblind change (RSA)} 407 \vfill 408 \begin{minipage}{7cm} 409 \begin{enumerate} 410 \item Receive $s'$. 411 \item Compute $s := s' b_{new,\gamma}^{-1} \mod n$. 412 \end{enumerate} 413 \end{minipage} 414 \begin{minipage}{5cm} 415 \begin{tikzpicture} 416 \tikzstyle{def} = [node distance= 2em and 0.5em, inner sep=0em, outer sep=.3em]; 417 \node (b) [def, draw=none] at (0,0) {$b_{new,\gamma}$}; 418 \node (coin) [def, draw=none, below left=of b]{\includegraphics[width=0.2\textwidth]{coin.pdf}}; 419 \node (signed) [def, draw=none, above left=of coin]{\includegraphics[width=0.15\textwidth]{sign.pdf}}; 420 \tikzstyle{C} = [color=black, line width=1pt] 421 422 \draw [<-, C] (coin) -- (b) node [midway, above, sloped] (TextNode) {}; 423 \draw [<-, C] (coin) -- (signed) node [midway, above, sloped] (TextNode) {}; 424 \end{tikzpicture} 425 \end{minipage} 426 \vfill 427 \note[item]{As with the ordinary blind-signature based withdraw, the customer can 428 then unblind the signature and has a valid coin.} 429 \note[item]{Without knowledge of $c_{old}$ or $t_\gamma$, the coins derived from this 430 process are indistinguishable from coins that were withdrawn directly from an account.} 431 \note[item]{Most importantly, without knowledge of $t_\gamma$ or $c_{old}$, 432 the $c_{new}$ is unlinkable to $c_{old}$.} 433 \end{frame} 434 435 \begin{frame}{Exchange: Allow linking change} 436 \begin{minipage}{5cm} 437 \begin{center} 438 Given $C_{old}$ 439 440 \vspace{1cm} 441 442 return $t_\gamma$ and 443 \begin{equation*} 444 s := s' b_{new,\gamma}^{-1} \mod n. 445 \end{equation*} 446 \end{center} 447 \end{minipage} 448 \begin{minipage}{5cm} 449 \begin{tikzpicture} 450 \tikzstyle{def} = [node distance= 3em and 0.5em, inner sep=0.5em, outer sep=.3em]; 451 \node (co) [def, draw=none] at (0,0) {$C_{old}$}; 452 \node (T) [def, draw=none, below left=of co]{$t_\gamma$}; 453 \node (sign) [def, draw=none, below right=of co]{\includegraphics[width=0.15\textwidth]{sign.pdf}}; 454 \node (customer) [def, draw, below right=of T] {Customer}; 455 456 \tikzstyle{C} = [color=black, line width=1pt] 457 458 \draw [<-, C] (T) -- (co) node [midway, above, sloped] (TextNode) {}; 459 \draw [<-, C] (sign) -- (co) node [midway, above, sloped] (TextNode) {}; 460 \draw [<-, C] (customer) -- (T) node [midway, above, sloped] (TextNode) {link}; 461 \draw [<-, C] (customer) -- (sign) node [midway, above, sloped] (TextNode) {link}; 462 \end{tikzpicture} 463 \end{minipage} 464 \note[item]{But, how does this address the issue that $c_{old}$ may have a different 465 owner from $c_{new,\gamma}$? Well, so far it does not! In principle, the envelope can 466 easily be constructed by someone who was not the original owner of $c_{old}$.} 467 \note[item]{So how does this help? Well, the exchange has one more sub-protocol, 468 which is the {\bf link} protocol. Given the old coin's public key, $C_{old}$, 469 it returns $t_\gamma$, the {\bf public transfer key}, and the blind signature 470 over the new coin that was rendered as change.} 471 \note[item]{Note that this is a request that the owner of $c_{old}$ can always 472 trivially make, as they know $C_{old}$.} 473 \note[item]{So how does that help?} 474 \end{frame} 475 476 477 \begin{frame}{Customer: Link (threat!)} 478 \begin{minipage}{6.5cm} 479 \begin{enumerate} 480 \item Have $c_{old}$. 481 \item Obtain $T_\gamma$, $s$ from exchange 482 \item Compute $X_\gamma = UNISIG_{c_{old}}(t_\gamma)$ 483 \item Derive $c_{new,\gamma}$ and $b_{new,\gamma}$ from $X_\gamma$ 484 \item Unblind $s := s' b_{new,\gamma}^{-1} \mod n$ 485 \end{enumerate} 486 \end{minipage} 487 \begin{minipage}{6.5cm} 488 \begin{tikzpicture} 489 \tikzstyle{def} = [node distance= 0.75em and 1em, inner sep=0em, outer sep=.3em]; 490 \node (T) [def, draw=none] at (0,0) {$t_\gamma$}; 491 \node (exchange) [def, inner sep=0.5em, draw, above left=of T] {Exchange}; 492 \node (signed) [def, draw=none, below left=of T]{\includegraphics[width=0.15\textwidth]{sign.pdf}}; 493 \node (dh) [def, draw=none, below right=of T]{\includegraphics[width=0.2\textwidth]{unisig.pdf} ($X_\gamma$)}; 494 \node (bp) [def, draw=none, below left= of dh] {$b_{new,\gamma}$}; 495 \node (co) [def, draw=none, above right= of dh] {$c_{old}$}; 496 \node (cp) [def, draw=none, below right= of dh] {$c_{new,\gamma}$}; 497 \node (coin) [def, draw=none, below left = of bp]{\includegraphics[width=0.2\textwidth]{coin.pdf}}; 498 \node (psign) [def, node distance=1.5em and 0em, draw=none, below = of cp]{\includegraphics[width=0.2\textwidth]{planchet-sign.pdf}}; 499 500 \tikzstyle{C} = [color=black, line width=1pt] 501 502 \draw [<-, C] (dh) -- (co) node [midway, above, sloped] (TextNode) {}; 503 \draw [<-, C] (dh) -- (T) node [midway, above, sloped] (TextNode) {}; 504 \draw [<-, C] (cp) -- (dh) node [midway, above, sloped] (TextNode) {}; 505 \draw [<-, C] (bp) -- (dh) node [midway, above, sloped] (TextNode) {}; 506 \draw [<-, C] (coin) -- (signed) node [midway, above, sloped] (TextNode) {}; 507 \draw [<-, C] (coin) -- (bp) node [midway, above, sloped] (TextNode) {}; 508 \draw [<-, C] (T) -- (exchange) node [midway, above, sloped] (TextNode) {link}; 509 \draw [<-, C] (signed) -- (exchange) node [midway, below, sloped] (TextNode) {link}; 510 \draw [<-, C, double] (psign) -- (cp) node [midway, below, sloped] (TextNode) {}; 511 \end{tikzpicture} 512 \end{minipage} 513 \note[item]{Well, given these two values, the owner of the original $c_{old}$ can 514 {\bf again} compute the UNISIG (from $c_{old}$ and $t_\gamma$), and then 515 also derive $c_{new,\gamma}$ and also unblind the exchange's signature using $b_{new,\gamma}$.} 516 \note[item]{As a result, the owner of the old coin can always compute the change, 517 and thus is effectively {\bf also} always an owner of the change rendered!} 518 \note[item]{Thus, we have {\bf reduced} the possibility of abusing the change 519 protocol for a transaction that would result in a {\bf mutually exclusive transfer 520 of ownership} to the case where the ownership of the change is {\bf shared}.} 521 \note[item]{But, we previously explained that {\bf sharing} is not something we can 522 or would care to prevent, so the change protocol does not weaken income transparency.} 523 \end{frame} 524 525 526 \begin{frame}{VRF vs. Dold'19 with Diffie-Hellman (ECDH)} 527 VRF/unique signatures are {\em slightly} stronger than required! 528 529 \begin{minipage}{7cm} 530 \begin{enumerate} 531 \item Create private keys $c,t \mod o$ 532 \item Define $C = cG$ 533 \item Define $T = tG$ 534 \item Compute DH \\ $cT = c(tG) = t(cG) = tC$ 535 \item Sign $T$ with EdDSA: 536 DH is unique, with EdDSA we have a signature, 537 $t$ allows verifier to check! 538 \end{enumerate} 539 \end{minipage} 540 \begin{minipage}{5cm} 541 \begin{center} 542 \begin{tikzpicture} 543 \tikzstyle{def} = [node distance= 2em and 0.5em, inner sep=0em, outer sep=.3em]; 544 \node (t) [def, draw=none] at (0,0) {$t$}; 545 \node (ct) [def, draw=none, below left=of b]{\includegraphics[width=0.2\textwidth]{dh.pdf}}; 546 \node (c) [def, draw=none, above left= of ct] {$c$}; 547 \tikzstyle{C} = [color=black, line width=1pt] 548 549 \draw [<-, C] (ct) -- (c) node [midway, above, sloped] (TextNode) {}; 550 \draw [<-, C] (ct) -- (t) node [midway, above, sloped] (TextNode) {}; 551 \end{tikzpicture} 552 \end{center} 553 \end{minipage} 554 \end{frame} 555 556 557 \begin{frame}{Transfer setup with ECDH-based Refresh} 558 \begin{minipage}{7.5cm} 559 {\small Given partially spent private coin key $c_{old}$:} 560 \begin{enumerate} 561 \item Let $C_{old} := c_{old}G$ (as before) 562 \item Create random private transfer key $t \mod o$ 563 \item Compute $T := tG$ 564 \item Compute $X := c_{old}(tG) = t(c_{old}G) = tC_{old}$ 565 \item Derive $c_{new}$ and $b_{new}$ from $X$ 566 \item Compute $C_{new} := c_{new}G$ 567 \item Compute $f_{new} := FDH(C_{new})$ 568 \item Transmit $f_{new}' := f_{new} b_{new}^e$ 569 \end{enumerate} 570 \end{minipage} 571 \begin{minipage}{3cm} 572 \begin{tikzpicture} 573 \tikzstyle{def} = [node distance= 1em and 0.5em, inner sep=0em, outer sep=.3em]; 574 \node (t) [def, draw=none] at (0,0) {$t$}; 575 \node (dice) [def, draw=none, above = of t]{\includegraphics[width=0.2\textwidth]{dice.pdf}}; 576 \node (dh) [def, draw=none, below left=of b]{\includegraphics[width=0.2\textwidth]{ct.pdf}}; 577 \node (d) [def, draw=none, above left= of dh] {$c_{old}$}; 578 \node (cp) [def, draw=none, below left= of dh] {$c_{new}$}; 579 \node (bp) [def, draw=none, below right= of dh] {$b_{new}$}; 580 \node (blinded) [def, draw=none, below right=of cp]{\includegraphics[width=0.15\textwidth]{blinded.pdf}}; 581 \node (exchange) [node distance=1.5em and 0.5em, draw, below =of blinded]{Exchange}; 582 583 \tikzstyle{C} = [color=black, line width=1pt] 584 585 \draw [<-, C] (dh) -- (d) node [midway, above, sloped] (TextNode) {}; 586 \draw [<-, C] (dh) -- (t) node [midway, above, sloped] (TextNode) {}; 587 \draw [<-, C] (t) -- (dice) node [midway, above, sloped] (TextNode) {}; 588 \draw [<-, C] (cp) -- (dh) node [midway, above, sloped] (TextNode) {}; 589 \draw [<-, C] (bp) -- (dh) node [midway, above, sloped] (TextNode) {}; 590 \draw [<-, C] (blinded) -- (cp) node [midway, above, sloped] (TextNode) {}; 591 \draw [<-, C] (blinded) -- (bp) node [midway, above, sloped] (TextNode) {}; 592 \draw [<-, C] (exchange) -- (blinded) node [midway, right] (TextNode) {{\small transmit}}; 593 \end{tikzpicture} 594 \end{minipage} 595 \note[item]{This is the Dold'19 replacement for slide~\pageref{page:transfersetup}.} 596 \end{frame} 597 598 599 \begin{frame}{Refresh protocol summary} 600 \begin{itemize} 601 \item Customer asks exchange to convert old coin to new coin 602 \item Protocol ensures new coins can be recovered from old coin 603 \item[$\Rightarrow$] New coins are owned by the same entity! 604 \end{itemize} 605 Thus, the refresh protocol allows: 606 \begin{itemize} 607 \item To give unlinkable change. 608 \item To give refunds to an anonymous customer. 609 \item To expire old keys and migrate coins to new ones. 610 \item To handle protocol aborts. 611 \end{itemize} 612 \noindent 613 \begin{center} 614 { \bf 615 Transactions via refresh are equivalent to {\em sharing} a wallet. } 616 \end{center} 617 \note[item]{In Taler, the overall protocol is called the {\bf refresh} protocol, 618 not the {\bf change} protocol, as it has uses beyond getting unlinkable change.} 619 \note[item]{A merchant can grant a refund to an anonymous 620 customer by telling the exchange to nullify the original deposit. Then 621 the anonymous owner of the original coin can obtain the refund 622 via the refresh protocol.} 623 \note[item]{If a coin is about to expire (because the exchange 624 only accepts deposits for a certain denomination key for a limited amount of time), 625 the refresh protocol can be used to obtain fresh coins, signed with the current 626 denomination key. This is like rolling over to a fresh series of bank notes.} 627 \note[item]{Finally, we can handle situations where the customer did try to spend 628 digital cash, but then the message was lost, say due to a power outage, before 629 the transaction was actually completed. But, the customer might not be sure that 630 nobody else saw the public key of the coin! So, to ensure that transactions 631 remain unlinkable (and that the merchant cannot deposit the coin later), the 632 wallet can again use the refresh protocol.} 633 \end{frame}