viff

changeset 694:f22be84127b8

The source for the design talk is better kept somewhere else.
author Martin Geisler <mg@daimi.au.dk>
date Mon, 21 Apr 2008 16:21:34 +0200
parents 1d832471464f
children c8fa9ca3ac9f
files doc/design-talk/design-talk.tex doc/design-talk/example.py doc/design-talk/sample-config.ini
diffstat 3 files changed, 0 insertions(+), 403 deletions(-) [+]
line diff
     1.1 --- a/doc/design-talk/design-talk.tex	Thu Apr 17 13:55:45 2008 +0200
     1.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.3 @@ -1,367 +0,0 @@
     1.4 -\documentclass[t,noamsthm]{beamer}
     1.5 -
     1.6 -\mode<presentation>
     1.7 -{
     1.8 -  \usetheme{Goettingen}
     1.9 -  \setbeamercovered{transparent}
    1.10 -  \setbeamertemplate{navigation symbols}{}
    1.11 -}
    1.12 -
    1.13 -\usepackage[english]{babel}
    1.14 -\usepackage[latin1]{inputenc}
    1.15 -\usepackage[T1]{fontenc}
    1.16 -\usepackage{lmodern,textcomp}
    1.17 -
    1.18 -\title[VIFF]{Virtual Ideal Functionality Framework}
    1.19 -
    1.20 -\subtitle{High-Level Design Overview}
    1.21 -
    1.22 -\author{Martin Geisler}
    1.23 -
    1.24 -\institute[BRICS]{
    1.25 -  BRICS\\
    1.26 -  Department of Computer Science\\
    1.27 -  University of Aarhus
    1.28 -}
    1.29 -
    1.30 -\date{September 20th, 2007}
    1.31 -
    1.32 -% \pgfdeclareimage[height=0.5cm]{university-logo}{university-logo-filename}
    1.33 -% \logo{\pgfuseimage{university-logo}}
    1.34 -
    1.35 -% If you wish to uncover everything in a step-wise fashion, uncomment
    1.36 -% the following command: 
    1.37 -%\beamerdefaultoverlayspecification{<+->}
    1.38 -
    1.39 -\usepackage{tikz}
    1.40 -
    1.41 -\newcommand{\rulecolor}{structure!60}
    1.42 -\newcommand{\fillcolor}{structure!15}
    1.43 -
    1.44 -\tikzstyle{player}=[circle,fill=\fillcolor,draw=\rulecolor]
    1.45 -\tikzstyle{every picture}=[thick]
    1.46 -
    1.47 -
    1.48 -\usepackage{listings}
    1.49 -\lstset{
    1.50 -  language=Python,
    1.51 -  basicstyle=\footnotesize,
    1.52 -  columns=fullflexible,
    1.53 -  showstringspaces=false,
    1.54 -  frame=single,
    1.55 -  framerule=0.8pt,
    1.56 -  rulecolor=\color{\rulecolor},
    1.57 -  backgroundcolor=\color{\fillcolor}
    1.58 -}
    1.59 -\newcommand{\py}[1]{\lstinline|#1|}
    1.60 -
    1.61 -\usepackage{nath} \delimgrowth=2
    1.62 -
    1.63 -\begin{document}
    1.64 -
    1.65 -\begin{frame}
    1.66 -  \titlepage
    1.67 -\end{frame}
    1.68 -
    1.69 -%\begin{frame}{Outline}
    1.70 -%  \tableofcontents
    1.71 -%  % You might wish to add the option [pausesections]
    1.72 -%\end{frame}
    1.73 -
    1.74 -\section{Features}
    1.75 -
    1.76 -\begin{frame}{VIFF Features}
    1.77 -
    1.78 -  \begin{itemize}
    1.79 -
    1.80 -  \item API for writing secure multi-party computations
    1.81 -    \begin{itemize}
    1.82 -    \item Easy to use: \py{a + b + c} instead of \py{add(add(a, b), c)}
    1.83 -    \item Simple if you already know Python
    1.84 -    \item A custom language could be added
    1.85 -    \end{itemize}
    1.86 -
    1.87 -  \item<2-> Efficient asynchronous design
    1.88 -    \begin{itemize}
    1.89 -    \item Automatic parallelism
    1.90 -    \item Single-threaded (no locks!)
    1.91 -    \end{itemize}
    1.92 -    
    1.93 -  \item<3-> Simple architecture
    1.94 -    \begin{itemize}
    1.95 -    \item Small code base (2,500 lines)
    1.96 -    \item Few layers of abstraction\dots
    1.97 -    \item \dots but hopefully sufficiently many
    1.98 -    \end{itemize}
    1.99 -
   1.100 -  \end{itemize}
   1.101 -
   1.102 -\end{frame}
   1.103 -
   1.104 -\section{Example}
   1.105 -
   1.106 -\begin{frame}{Example MPC Calculation}
   1.107 -
   1.108 -  \begin{columns}
   1.109 -
   1.110 -    \column{0.5\textwidth}
   1.111 -
   1.112 -    \centering
   1.113 -    \begin{tikzpicture}
   1.114 -      \draw (0,0) + (90:2cm) node[player] (P1) {$P_1$}
   1.115 -                  +(210:2cm) node[player] (P2) {$P_2$}
   1.116 -                  +(330:2cm) node[player] (P3) {$P_3$};
   1.117 -
   1.118 -      \visible<1>{
   1.119 -        \draw (P1.north) node[above] {$x$};
   1.120 -        \draw (P2.south) node[below] {$y$};
   1.121 -        \draw (P3.south) node[below] {$z$};
   1.122 -      }
   1.123 -
   1.124 -      \visible<2>{
   1.125 -        \draw[->] (P1) .. controls +(75:1cm) and +(105:1cm) ..
   1.126 -          node[above,sloped] {$x_1$} (P1);
   1.127 -        \draw[->] (P1) .. controls +(230:1cm) and +(70:1cm) ..
   1.128 -          node[above,sloped] {$x_2$} (P2);
   1.129 -        \draw[->] (P1) .. controls +(-50:1cm) and +(110:1cm) ..
   1.130 -          node[above,sloped] {$x_3$} (P3);
   1.131 -
   1.132 -        \draw[->] (P2) .. controls +(50:1cm) and +(250:1cm) ..
   1.133 -          node[below,sloped] {$y_1$} (P1);
   1.134 -        \draw[->] (P2) .. controls +(225:1cm) and +(255:1cm) ..
   1.135 -          node[below,xshift=1pt] {$y_2$} (P2);
   1.136 -        \draw[->] (P2) .. controls +(10:1cm) and +(170:1cm) ..
   1.137 -          node[above,sloped] {$y_3$} (P3);
   1.138 -
   1.139 -        \draw[->] (P3) .. controls +(130:1cm) and +(-70:1cm) ..
   1.140 -          node[below,sloped] {$z_1$} (P1);
   1.141 -        \draw[->] (P3) .. controls +(-170:1cm) and +(-10:1cm) ..
   1.142 -          node[below,sloped] {$z_2$} (P2);
   1.143 -        \draw[->] (P3) .. controls +(-75:1cm) and +(-45:1cm) ..
   1.144 -          node[below,xshift=-1pt] {$z_3$} (P3);
   1.145 -      }
   1.146 -
   1.147 -      \visible<3>{
   1.148 -        \draw (P1.north) node[above] {$x_1$, $y_1$, $z_1$};
   1.149 -        \draw (P2.south) node[below,xshift=6pt] {$x_2$, $y_2$, $z_2$};
   1.150 -        \draw (P3.south) node[below,xshift=-6pt] {$x_3$, $y_3$, $z_3$};
   1.151 -      }
   1.152 -
   1.153 -      \visible<4>{
   1.154 -        \draw[<->,dashed] (P1) -- (P2);
   1.155 -        \draw[<->,dashed] (P2) -- (P3);
   1.156 -        \draw[<->,dashed] (P3) -- (P1);
   1.157 -      }
   1.158 -
   1.159 -      \visible<5-6>{
   1.160 -        \draw (P1.north) node[above] {$r_1$};
   1.161 -        \draw (P2.south) node[below] {$r_2$};
   1.162 -        \draw (P3.south) node[below] {$r_3$};
   1.163 -      }
   1.164 -
   1.165 -      \visible<6>{
   1.166 -        \draw[->] (P1) .. controls +(230:1cm) and +(70:1cm) ..
   1.167 -          node[above,sloped] {$r_1$} (P2);
   1.168 -        \draw[->] (P1) .. controls +(-50:1cm) and +(110:1cm) ..
   1.169 -          node[above,sloped] {$r_1$} (P3);
   1.170 -
   1.171 -        \draw[->] (P2) .. controls +(50:1cm) and +(250:1cm) ..
   1.172 -          node[below,sloped] {$r_2$} (P1);
   1.173 -        \draw[->] (P2) .. controls +(10:1cm) and +(170:1cm) ..
   1.174 -          node[above,sloped] {$r_2$} (P3);
   1.175 -
   1.176 -        \draw[->] (P3) .. controls +(130:1cm) and +(-70:1cm) ..
   1.177 -          node[below,sloped] {$r_3$} (P1);
   1.178 -        \draw[->] (P3) .. controls +(-170:1cm) and +(-10:1cm) ..
   1.179 -          node[below,sloped] {$r_3$} (P2);
   1.180 -      }
   1.181 -
   1.182 -      \visible<7>{
   1.183 -        \draw (P1.north) node[above] {$r$};
   1.184 -        \draw (P2.south) node[below] {$r$};
   1.185 -        \draw (P3.south) node[below] {$r$};
   1.186 -      }
   1.187 -
   1.188 -    \end{tikzpicture}
   1.189 -
   1.190 -    \column{0.5\textwidth}
   1.191 -
   1.192 -    \begin{itemize}
   1.193 -    \item<1-> Players $P_1$, $P_2$, and $P_3$
   1.194 -    \item<2-> Sharing $x$, $y$, and $z$
   1.195 -    \item<4-> Compute $r= (x+y)\cdot z$
   1.196 -    \item<6-> Opens the result $r$
   1.197 -    \end{itemize}
   1.198 -
   1.199 -  \end{columns}
   1.200 -\end{frame}
   1.201 -
   1.202 -\begin{frame}{Example VIFF Program}
   1.203 -
   1.204 -\mbox{}\vspace{-2\baselineskip}
   1.205 -
   1.206 -\begin{columns}
   1.207 -  \column{0.625\textwidth}
   1.208 -  \lstinputlisting[linerange={1-5}]{example.py}
   1.209 -  \column{0.375\textwidth}
   1.210 -  \begin{itemize}
   1.211 -  \item Import standard and VIFF modules
   1.212 -  \end{itemize}
   1.213 -\end{columns}
   1.214 -
   1.215 -\vspace{-0.75\baselineskip}
   1.216 -
   1.217 -\begin{columns}
   1.218 -  \column{0.625\textwidth}
   1.219 -  \uncover<2->{\lstinputlisting[linerange={7-9}]{example.py}}
   1.220 -  \column{0.375\textwidth}
   1.221 -  \begin{itemize}
   1.222 -  \item<2-> Load command line config
   1.223 -  \end{itemize}
   1.224 -\end{columns}
   1.225 -
   1.226 -\vspace{-0.75\baselineskip}
   1.227 -
   1.228 -\begin{columns}
   1.229 -  \column{0.625\textwidth}
   1.230 -  \uncover<3->{\lstinputlisting[linerange={11-13}]{example.py}}
   1.231 -  \column{0.375\textwidth}
   1.232 -  \begin{itemize}
   1.233 -  \item<3-> Create Runtime, do calculation
   1.234 -  \end{itemize}
   1.235 -\end{columns}
   1.236 -
   1.237 -\vspace{-0.75\baselineskip}
   1.238 -
   1.239 -\begin{columns}
   1.240 -  \column{0.625\textwidth}
   1.241 -  \uncover<4->{\lstinputlisting[linerange={15-17}]{example.py}}
   1.242 -  \column{0.375\textwidth}
   1.243 -  \begin{itemize}
   1.244 -  \item<4-> Open and print result
   1.245 -  \end{itemize}
   1.246 -\end{columns}
   1.247 -
   1.248 -\end{frame}
   1.249 -
   1.250 -\begin{frame}{Example Configuration File}
   1.251 -
   1.252 -  \lstdefinelanguage{ini}{
   1.253 -    morecomment=[l]{\#},
   1.254 -    moredelim=[s][\textbf]{[}{]},
   1.255 -    moredelim=[s][\textbf]{[[}{]]},
   1.256 -    moredelim=[s][\textbf]{[[[}{]]]}
   1.257 -  }
   1.258 -
   1.259 -  \lstinputlisting[language=ini]{sample-config.ini}
   1.260 -
   1.261 -\end{frame}
   1.262 -
   1.263 -\section{Scheduling}
   1.264 -
   1.265 -\begin{frame}{Asynchronous Design}
   1.266 -
   1.267 -  \begin{columns}
   1.268 -
   1.269 -    \column{0.3\textwidth}
   1.270 -
   1.271 -    \begin{tikzpicture}
   1.272 -      \tikzstyle{level 1}=[level distance=10mm]
   1.273 -
   1.274 -      \draw (-0.25,0) node {$r = (x+y) \cdot z$};
   1.275 -      \draw (0,-0.5) node[xshift=-0.75pt,rotate=-90] {$\rightsquigarrow$};
   1.276 -
   1.277 -      \draw (0,-1) node {open}
   1.278 -        child {node {\py{*}}
   1.279 -          child {node {\py{+}}
   1.280 -            child {node {x}}
   1.281 -            child {node {y}}
   1.282 -          }
   1.283 -          child {node {z}}};
   1.284 -    \end{tikzpicture}
   1.285 -
   1.286 -    \column{0.7\textwidth}
   1.287 -
   1.288 -    \begin{itemize}
   1.289 -    \item Entire tree is scheduled as once
   1.290 -    \item Operations wait on their operands
   1.291 -    \item Results are sent when ready
   1.292 -    \item Result is a form of ``greedy scheduling''
   1.293 -    \item Implicit synchronization, no rounds
   1.294 -    \end{itemize}
   1.295 -
   1.296 -  \end{columns}
   1.297 -
   1.298 -\end{frame}
   1.299 -
   1.300 -\begin{frame}{Greedy Scheduling}
   1.301 -  Advantages:
   1.302 -  \begin{itemize}
   1.303 -  \item At least as efficient as round-based scheduling
   1.304 -  \item No cost when adding primitives (modular design)
   1.305 -  \item Automatic parallelism
   1.306 -  \end{itemize}
   1.307 -
   1.308 -  Disadvantages:
   1.309 -  \begin{itemize}
   1.310 -  \item Not yet proven secure\dots
   1.311 -  \end{itemize}
   1.312 -\end{frame}
   1.313 -
   1.314 -
   1.315 -\section{Current Status}
   1.316 -
   1.317 -\begin{frame}{What has been Implemented?}
   1.318 -  \begin{itemize}
   1.319 -  \item Shamir sharing
   1.320 -  \item PRSS
   1.321 -  \item Opening
   1.322 -  \item Addition, multiplication, exclusive-or
   1.323 -  \item Classic SCET comparison
   1.324 -  \end{itemize}
   1.325 -\end{frame}
   1.326 -
   1.327 -
   1.328 -\begin{frame}{Assumptions}
   1.329 -  
   1.330 -  Current primitives assume:
   1.331 -  \begin{itemize}
   1.332 -  \item Fixed number of players
   1.333 -  \item Passive and static adversary
   1.334 -  \item Threshold adversary structure, $t < \frac n 2$
   1.335 -  \end{itemize}
   1.336 -
   1.337 -  
   1.338 -\end{frame}
   1.339 -
   1.340 -\section{Conclusion}
   1.341 -
   1.342 -\begin{frame}{Conclusion}
   1.343 -
   1.344 -\begin{itemize}
   1.345 -\item VIFF offers a light-weight design for doing MPC
   1.346 -\item Asynchronous design gives automatic parallelism
   1.347 -\end{itemize}
   1.348 -
   1.349 -Installation instructions, source code and more:
   1.350 -\begin{itemize}
   1.351 -\item \url{http://viff.dk/}
   1.352 -\end{itemize}
   1.353 -
   1.354 -\visible<2>{
   1.355 -  \begin{center}
   1.356 -    \bigskip
   1.357 -    \begin{tikzpicture}
   1.358 -      \draw node[rectangle,draw=\rulecolor,fill=\fillcolor,
   1.359 -        inner sep=2.5em,font=\huge\bfseries] {Questions?};
   1.360 -    \end{tikzpicture}
   1.361 -  \end{center}
   1.362 -}
   1.363 -
   1.364 -\end{frame}
   1.365 -
   1.366 -
   1.367 -
   1.368 -\end{document}
   1.369 -
   1.370 -% LocalWords:  VIFF API MPC PRSS SCET
     2.1 --- a/doc/design-talk/example.py	Thu Apr 17 13:55:45 2008 +0200
     2.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.3 @@ -1,17 +0,0 @@
     2.4 -import sys
     2.5 -from viff.field import GF
     2.6 -from viff.config import load_config
     2.7 -from viff.runtime import Runtime
     2.8 -from viff.util import dprint
     2.9 -
    2.10 -Z31 = GF(31)
    2.11 -my_id, conf = load_config(sys.argv[1])
    2.12 -my_input = Z31(int(sys.argv[2]))
    2.13 -
    2.14 -rt = Runtime(conf, my_id, 1)
    2.15 -x, y, z = rt.shamir_share(my_input)
    2.16 -result = (x + y) * z
    2.17 -
    2.18 -opened_result = rt.open(result)
    2.19 -dprint("Result: %s", opened_result)
    2.20 -rt.wait_for(opened_result)
     3.1 --- a/doc/design-talk/sample-config.ini	Thu Apr 17 13:55:45 2008 +0200
     3.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.3 @@ -1,19 +0,0 @@
     3.4 -[Player 1]
     3.5 -  host = camel09
     3.6 -  port = 7100
     3.7 -[Player 2]
     3.8 -  host = camel17
     3.9 -  port = 7200
    3.10 -[Player 3]
    3.11 -  host = camel19
    3.12 -  port = 7300
    3.13 -  [[prss_keys]]
    3.14 -    1 3 = 0x47D5B9B367DAFC9267EDF518AD5B5F396299L
    3.15 -    2 3 = 0x7EBC55E5CF1D014D081EA428B5F35FD12C64L
    3.16 -  [[prss_dealer_keys]]
    3.17 -    [[[Dealer 1]]]
    3.18 -      1 3 = 0x903039893A06800A0FA7175CED8CC17B873BL
    3.19 -      2 3 = 0x11C91354237193397589A1D1C6455F87CB79L
    3.20 -    # More PRSS keys...
    3.21 -
    3.22 -# End of config