nullcon.tex (13333B)
1 \pdfminorversion=3 2 \documentclass[fleqn,xcolor={usenames,dvipsnames,table}]{beamer} 3 \usepackage{amsmath} 4 \usepackage{multimedia} 5 \usepackage[utf8]{inputenc} 6 \usepackage{framed,color,ragged2e} 7 \usepackage[absolute,overlay]{textpos} 8 \definecolor{shadecolor}{rgb}{0.8,0.8,0.8} 9 \usetheme{boxes} 10 \setbeamertemplate{navigation symbols}{} 11 \usepackage{graphicx} 12 \usepackage{listings} 13 \usepackage{tikz} 14 \usetikzlibrary[positioning] 15 \usetikzlibrary{patterns} 16 \usetikzlibrary{arrows,decorations.markings,fit} 17 \usetikzlibrary{shapes} 18 \usepackage{eurosym} 19 \usepackage{url} 20 \usepackage[normalem]{ulem} 21 \usepackage{listings} 22 \usepackage{adjustbox} 23 24 % CSS 25 \lstdefinelanguage{CSS}{ 26 basicstyle=\ttfamily\scriptsize, 27 keywords={color,background-image:,margin,padding,font,weight,display,position,top,left,right,bottom,list,style,border,size,white,space,min,width, transition:, transform:, transition-property, transition-duration, transition-timing-function}, 28 sensitive=true, 29 morecomment=[l]{//}, 30 morecomment=[s]{/*}{*/}, 31 morestring=[b]', 32 morestring=[b]", 33 alsoletter={:}, 34 alsodigit={-} 35 } 36 37 % JavaScript 38 \lstdefinelanguage{JavaScript}{ 39 basicstyle=\ttfamily\scriptsize, 40 morekeywords={typeof, new, true, false, catch, function, return, null, catch, switch, var, if, in, while, do, else, case, break}, 41 morecomment=[s]{/*}{*/}, 42 morecomment=[l]//, 43 morestring=[b]", 44 morestring=[b]' 45 } 46 47 \lstdefinelanguage{HTML5}{ 48 basicstyle=\ttfamily\scriptsize, 49 language=html, 50 sensitive=true, 51 alsoletter={<>=-}, 52 morecomment=[s]{<!-}{-->}, 53 tag=[s], 54 otherkeywords={ 55 % General 56 >, 57 % Standard tags 58 <!DOCTYPE, 59 </html, <html, <head, <title, </title, <style, </style, <link, </head, <meta, />, 60 % body 61 </body, <body, 62 % Divs 63 </div, <div, </div>, 64 % Paragraphs 65 </p, <p, </p>, 66 % scripts 67 </script, <script, 68 % More tags... 69 <canvas, /canvas>, <svg, <rect, <animateTransform, </rect>, </svg>, <video, <source, <iframe, </iframe>, </video>, <image, </image> 70 }, 71 ndkeywords={ 72 % General 73 =, 74 % HTML attributes 75 charset=, src=, id=, width=, height=, style=, type=, rel=, href=, 76 % SVG attributes 77 fill=, attributeName=, begin=, dur=, from=, to=, poster=, controls=, x=, y=, repeatCount=, xlink:href=, 78 % CSS properties 79 margin:, padding:, background-image:, border:, top:, left:, position:, width:, height:, 80 % CSS3 properties 81 transform:, -moz-transform:, -webkit-transform:, 82 animation:, -webkit-animation:, 83 transition:, transition-duration:, transition-property:, transition-timing-function:, 84 } 85 } 86 87 \lstdefinelanguage{JavaScript}{ 88 basicstyle=\ttfamily\scriptsize, 89 keywords={typeof, new, true, false, catch, function, return, null, catch, switch, var, if, in, while, do, else, case, break, for}, 90 keywordstyle=\color{blue}\bfseries, 91 ndkeywords={class, export, boolean, throw, implements, import, this}, 92 ndkeywordstyle=\color{darkgray}\bfseries, 93 identifierstyle=\color{black}, 94 sensitive=false, 95 comment=[l]{//}, 96 morecomment=[s]{/*}{*/}, 97 commentstyle=\color{purple}\ttfamily, 98 stringstyle=\color{red}\ttfamily, 99 morestring=[b]', 100 morestring=[b]" 101 } 102 103 \usetikzlibrary{shapes,arrows} 104 \usetikzlibrary{positioning} 105 \usetikzlibrary{calc} 106 107 \title{GNU Anastasis} 108 \subtitle{Privacy-preserving Distributed Key backup and recovery} 109 110 \author[C. Grothoff]{B. Alp, V. Mohan, C. Grothoff, B. Pena, F. Dold} 111 \date{8.4.2022} 112 \institute{Anastasis SARL} 113 114 115 \begin{document} 116 117 \justifying 118 119 \begin{frame} 120 \begin{center} 121 \LARGE {\bf GNU} 122 % \includegraphics[width=0.66\textwidth]{logo-2017-fr.pdf} 123 \includegraphics[scale=0.5]{logo.png} 124 125 \vfill 126 {\small Nullcon 2022, Berlin} 127 128 \vspace{1cm} 129 {\small funded by} 130 \includegraphics[height=0.3cm]{ngi_ledger.pdf} 131 \includegraphics[height=0.3cm]{bandiera_stelle.png} 132 \vfill 133 \end{center} 134 \begin{textblock*}{6cm}(.5cm,7.7cm) % {block width} (coords) 135 {\Large {\bf \href{https://anastasis.lu/}{anastasis.lu}}} \\ 136 \href{https://twitter.com/anastasis-sarl}{anastasis-sarl@twitter} 137 \end{textblock*} 138 139 % Substitute based on who is giving the talk! 140 \begin{textblock*}{6cm}(6.7cm,7.7cm) % {block width} (coords) 141 {\hfill %{\Large {\bf Florian Dold \&} \\ 142 \hfill {\bf Christian Grothoff} \\ 143 \hfill grothoff@anastasis.lu } 144 \end{textblock*} 145 146 \end{frame} 147 148 \section{Introduction} 149 150 \begin{frame}{The Problem Illustrated} 151 \begin{center} 152 \includegraphics[width=0.9\textwidth]{motivation.pdf} 153 \end{center} 154 \end{frame} 155 156 \section{Shamir} 157 158 \begin{frame}{Problem: Availability (1/3)} 159 \vfill 160 \begin{center} 161 If you give one person a secret, it may get lost. 162 \end{center} 163 \vfill \pause 164 \begin{center} 165 $\Rightarrow$ So give it to more than one person! 166 \end{center} 167 \vfill 168 \end{frame} 169 170 \begin{frame}{Problem: Confidentiality (2/3)} 171 \vfill 172 \begin{center} 173 If you give many entities a secret, it may get disclosed. 174 \end{center} 175 \vfill \pause 176 \begin{center} 177 $\Rightarrow$ So give them only a key share! 178 \end{center} 179 \vfill 180 \end{frame} 181 182 \begin{frame}{Problem: Scalability (3/3)} 183 \vfill 184 If you want $k$ out of $n$ entities to coordinate to 185 recover a secret, there are 186 \begin{equation} 187 \left( {n \atop k} \right) = \frac{n!}{k!(n-k)!} 188 \end{equation} 189 combinations to consider. 190 \vfill \pause 191 \begin{center} 192 $\Rightarrow$ Use polynominals! 193 \end{center} 194 \vfill 195 \end{frame} 196 197 198 \begin{frame}{Polynominals} 199 \vfill 200 \begin{minipage}{7cm} 201 A polynominal of degree $k$ is fully determined by $k+1$ data points 202 \begin{equation*} 203 (x_{0},y_{0}),\ldots ,(x_{j},y_{j}),\ldots ,(x_{k},y_{k}), 204 \end{equation*} 205 where no two $x_j$ may be identical. 206 \end{minipage} 207 \begin{minipage}{5cm} 208 \includegraphics[width=4cm]{polynominal.png} 209 \end{minipage} 210 \vfill 211 \end{frame} 212 213 214 \begin{frame}{Lagrange Interpolation} 215 \vfill 216 The interpolation polynominal in the Lagrange form is: 217 \begin{equation*} 218 L(x):=\sum _{j=0}^{k}y_{j}\ell_{j}(x) 219 \end{equation*} 220 where 221 \begin{equation} 222 \ell_{j}(x):=\prod _{\begin{smallmatrix}0\leq m\leq k\\m\neq j\end{smallmatrix}}{\frac {x-x_{m}}{x_{j}-x_{m}}}={\frac {(x-x_{0})}{(x_{j}-x_{0})}}\cdots {\frac {(x-x_{j-1})}{(x_{j}-x_{j-1})}}{\frac {(x-x_{j+1})}{(x_{j}-x_{j+1})}}\cdots {\frac {(x-x_{k})}{(x_{j}-x_{k})}} 223 \end{equation} 224 for $0 \leq j \leq k$. 225 \vfill 226 \end{frame} 227 228 229 \begin{frame}{Practical Considerations} 230 \begin{itemize} 231 \item Our secrets will typically be integers. Calculations with floating points are {\em messy}. 232 \item[$\Rightarrow$] Use finite field arithmetic, not $\mathbb R$. 233 \end{itemize} 234 \end{frame} 235 236 237 238 \begin{frame}{Real world scalability} 239 \vfill 240 \begin{center} 241 \begin{tabular}{l||r|r|r|r|r|r} 242 n / k & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \hline 243 1 & 1 & 2 & 3 & 4 & 5 & 6 \\ 244 2 & & 1 & 3 & 6 & 10 & 15 \\ 245 3 & & & 1 & 4 & 10 & 20 \\ 246 4 & & & & 1 & 5 & 15 \\ 247 5 & & & & & 1 & 6 \\ 248 6 & & & & & & 1 \\ 249 \end{tabular} 250 \end{center} 251 Other values: \\ 252 \begin{itemize} 253 \item $\left( {10 \atop 5 } \right) = 252$ 254 \item $\left( {20 \atop 10 } \right) = 184756$ 255 \item $\left( {30 \atop 15 } \right) = 155117520$ 256 \item $\left( {100 \atop 50 } \right) \approx 10^{29}$ 257 \end{itemize} 258 \vfill 259 \end{frame} 260 261 262 \begin{frame}{Scalability Problem?} 263 \vfill 264 \begin{center} 265 How many people do you have to share your secrets with? 266 \end{center} 267 \vfill 268 \begin{center} 269 How many people realistically participate in recovery? 270 \end{center} 271 \vfill 272 \end{frame} 273 274 275 \section{Anastasis} 276 277 \begin{frame}{} 278 \begin{center} 279 \includegraphics[width=1\textwidth]{technically.pdf} 280 \end{center} 281 \end{frame} 282 283 \begin{frame}{} 284 \begin{center} 285 \includegraphics[width=1\textwidth]{what.pdf} 286 \end{center} 287 \end{frame} 288 289 \section{Design} 290 291 \begin{frame}{Preliminaries} 292 \begin{center} 293 \includegraphics[width=1\textwidth]{identity.pdf} 294 \end{center} 295 \end{frame} 296 297 298 \begin{frame}{Adversary Model} 299 \begin{center} 300 \includegraphics[width=1\textwidth]{adversary.pdf} 301 \end{center} 302 \end{frame} 303 304 305 \begin{frame}{Overview} 306 \begin{center} 307 \includegraphics[width=1\textwidth]{overview.pdf} 308 \end{center} 309 \end{frame} 310 311 312 \begin{frame}{Simplified Process Flow} 313 \framesubtitle{Step 1: Core Secret} 314 \begin{center} 315 \includegraphics[width=1\textwidth]{step1.pdf} 316 \end{center} 317 \end{frame} 318 319 \begin{frame}{Simplified Process Flow} 320 \framesubtitle{Step 2: Split Core Secret} 321 \begin{center} 322 \includegraphics[width=1\textwidth]{step2.pdf} 323 \end{center} 324 \end{frame} 325 326 \begin{frame}{Simplified Process Flow} 327 \framesubtitle{Step 3: User Identification} 328 \begin{center} 329 \includegraphics[width=1\textwidth]{step3.pdf} 330 \end{center} 331 \end{frame} 332 333 \begin{frame}{Simplified Process Flow} 334 \framesubtitle{Step 4: Key Derivation} 335 \begin{center} 336 \includegraphics[width=1\textwidth]{step4.pdf} 337 \end{center} 338 \end{frame} 339 340 \begin{frame}{Simplified Process Flow} 341 \framesubtitle{Step 5: Encrypt Parts} 342 \begin{center} 343 \includegraphics[width=1\textwidth]{step5.pdf} 344 \end{center} 345 \end{frame} 346 347 \begin{frame}{Simplified Process Flow} 348 \framesubtitle{Step 6: Add Truth} 349 \begin{center} 350 \includegraphics[width=1\textwidth]{step6.pdf} 351 \end{center} 352 \end{frame} 353 354 \begin{frame}{Simplified Process Flow} 355 \framesubtitle{Step 7: Encrypt Truth} 356 \begin{center} 357 \includegraphics[width=1\textwidth]{step7.pdf} 358 \end{center} 359 \end{frame} 360 361 \begin{frame}{Simplified Process Flow} 362 \framesubtitle{Step 8: Store Data} 363 \begin{center} 364 \includegraphics[width=1\textwidth]{step8.pdf} 365 \end{center} 366 \end{frame} 367 368 369 \begin{frame}{Simplified Process Flow} 370 \framesubtitle{Step 9: User Identification} 371 \begin{center} 372 \includegraphics[width=1\textwidth]{step3.pdf} 373 \end{center} 374 \end{frame} 375 376 \begin{frame}{Simplified Process Flow} 377 \framesubtitle{Step 10: Key Derivation} 378 \begin{center} 379 \includegraphics[width=1\textwidth]{step4.pdf} 380 \end{center} 381 \end{frame} 382 383 \begin{frame}{Simplified Process Flow} 384 \framesubtitle{Step 11: Provide Key} 385 \begin{center} 386 \includegraphics[width=1\textwidth]{step11.pdf} 387 \end{center} 388 \end{frame} 389 390 \begin{frame}{Simplified Process Flow} 391 \framesubtitle{Step 12: Decrypt Truth} 392 \begin{center} 393 \includegraphics[width=1\textwidth]{step12.pdf} 394 \end{center} 395 \end{frame} 396 397 \begin{frame}{Simplified Process Flow} 398 \framesubtitle{Step 13: Authentication} 399 \begin{center} 400 \includegraphics[width=1\textwidth]{step13.pdf} 401 \end{center} 402 \end{frame} 403 404 \begin{frame}{Simplified Process Flow} 405 \framesubtitle{Step 14: Receive Parts} 406 \begin{center} 407 \includegraphics[width=1\textwidth]{step14.pdf} 408 \end{center} 409 \end{frame} 410 411 \begin{frame}{Simplified Process Flow} 412 \framesubtitle{Step 15: Decrypt Parts} 413 \begin{center} 414 \includegraphics[width=1\textwidth]{step15.pdf} 415 \end{center} 416 \end{frame} 417 418 \begin{frame}{Simplified Process Flow} 419 \framesubtitle{Step 16: Reassembly} 420 \begin{center} 421 \includegraphics[width=1\textwidth]{step16.pdf} 422 \end{center} 423 \end{frame} 424 425 \begin{frame}{Simplifications} 426 \framesubtitle{The previous illustrations make various simplifications} 427 \begin{center} 428 \includegraphics[width=1\textwidth]{simplifications.pdf} 429 \end{center} 430 \end{frame} 431 432 \section{Demonstration} 433 434 \begin{frame}{Demonstration} 435 \begin{center} 436 Demo. 437 \end{center} 438 \end{frame} 439 440 \section{Architecture} 441 442 \begin{frame}{Software architecture overview} 443 \framesubtitle{\url{https://git.taler.net/anastasis.git}} 444 \noindent 445 \begin{center} 446 {\bf Anastasis is a protocol.} 447 \end{center} 448 449 The software consists of three components: 450 \begin{description} 451 \item[anastasis] Backend and client libraries (C) 452 \item[anastasis-gtk] Gtk+ front-end (C) 453 \item[anastasis-ts] Alternative front-end (TS) 454 \end{description} 455 Major dependencies include: 456 \begin{description} 457 \item[GNU Taler] Privacy-preserving payments (C/TS) 458 \item[Postgres] Backend database (C) 459 \item[libeufin] Alternative access to banking infrastructure (Kotlin) 460 \item[GNUnet] Various utility functions (C) 461 \item[GNU MHD] HTTP server library (C) 462 \end{description} 463 \end{frame} 464 465 466 \section{Installation} 467 468 \begin{frame}[fragile]{Binary installation instructions} 469 \framesubtitle{\url{https://docs.anastasis.lu/}} 470 Debian 11: 471 {\small 472 \begin{verbatim} 473 # echo 'deb https://deb.taler.net/apt/debian/ bullseye main'\ 474 > /etc/apt/sources.list/taler.list 475 # wget -O - https://taler.net/taler-systems.gpg.key |\ 476 apt-key add - 477 # apt update 478 # apt install anastasis-gtk 479 \end{verbatim} 480 } 481 Ubuntu 20.04: 482 {\small 483 \begin{verbatim} 484 # echo 'deb https://deb.taler.net/apt/ubuntu/ focal-fossa main'\ 485 > /etc/apt/sources.list/taler.list 486 # wget -O - https://taler.net/taler-systems.gpg.key |\ 487 apt-key add - 488 # apt update 489 # apt install anastasis-gtk 490 \end{verbatim} 491 } 492 \end{frame} 493 494 495 \begin{frame}{Do you have any questions?} 496 \framesubtitle{\url{https://anastasis.lu/}} 497 \vfill 498 References: 499 \begin{enumerate} 500 \item{Dennis Neufeld and Dominik Meister. 501 {\em Anastasis: Password-less key recovery via multi-factormulti-party authentication}. 502 {\bf BFH, 2020}.} 503 \item{David Chaum, Christian Grothoff and Thomas Moser. 504 {\em How to Issue a Central Bank Digital Currency}. 505 {\bf Swiss National Bank Working Papers, 3/2021}} 506 \item{Florian Dold. 507 {\em The GNU Taler System: Practical and Provably Secure Electronic Payments}. 508 {\bf University of Rennes 1}, 2019.} 509 \end{enumerate} 510 \end{frame} 511 512 513 \end{document}