viff

changeset 699:acfa9aa5bd59

Added overview document.
author Martin Geisler <mg@daimi.au.dk>
date Tue, 22 Apr 2008 08:38:25 +0200
parents 50bf10e379e0
children 4df225223500
files doc/index.txt doc/overview.txt
diffstat 2 files changed, 98 insertions(+), 0 deletions(-) [+]
line diff
     1.1 --- a/doc/index.txt	Tue Apr 22 08:34:05 2008 +0200
     1.2 +++ b/doc/index.txt	Tue Apr 22 08:38:25 2008 +0200
     1.3 @@ -11,6 +11,7 @@
     1.4  .. toctree::
     1.5     :maxdepth: 2
     1.6  
     1.7 +   overview
     1.8     glossary
     1.9  
    1.10  
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/doc/overview.txt	Tue Apr 22 08:38:25 2008 +0200
     2.3 @@ -0,0 +1,97 @@
     2.4 +
     2.5 +Overview
     2.6 +========
     2.7 +
     2.8 +VIFF allows you to write a program which will interact with other
     2.9 +programs in order to execute a joint computation. This is called a
    2.10 +multi-party computation, MPC for short.
    2.11 +
    2.12 +The programs will implement what we call a virtual :term:`ideal
    2.13 +functionality` (IF). The idea is that the behavior of the programs
    2.14 +should be indistinguishable from the behavior of programs interacting
    2.15 +with a so-called ideal functionality. An ideal functionality is a
    2.16 +player that cannot be corrupted, also known as a trusted third party
    2.17 +(TTP).
    2.18 +
    2.19 +Interacting with an IF is easy: all players give their inputs to the
    2.20 +IF, which computes the results. The results are then distributed to
    2.21 +the correct players. The inputs and the results are sent over secure
    2.22 +channels, and since the IF cannot be corrupted, this ideal protocol
    2.23 +must be secure.
    2.24 +
    2.25 +In the real world there is no IF, but VIFF allows you to implement a
    2.26 +virtual ideal functionality. The behavior of a bunch of programs using
    2.27 +VIFF is indistinguishable from program running in the ideal world. It
    2.28 +is indistinguishable in the sense that everything that can happen in
    2.29 +the real world protocol could happen in the ideal world too. And since
    2.30 +no attacks can occur in the ideal world, no attacks can occur in the
    2.31 +real world as well. Such a multi-party computation (MPC) is called a
    2.32 +secure multi-party computation (SMPC).
    2.33 +
    2.34 +Security Assumptions
    2.35 +--------------------
    2.36 +
    2.37 +Please note that like all cryptographic systems, VIFF is only secure
    2.38 +as long as certain assumptions are fulfilled. These assumptions
    2.39 +include:
    2.40 +
    2.41 +- The adversary can only corrupt up to a certain threshold of the
    2.42 +  total number of players. The threshold will normally be 1/2 of the
    2.43 +  players, so for three players, at most one player may be corrupted
    2.44 +  (there must be an honest majority).
    2.45 +
    2.46 +- The adversary is computationally bounded. The protocols used by VIFF
    2.47 +  rely on certain computational hardness assumptions, and therefore
    2.48 +  only polynomial time adversaries are allowed.
    2.49 +
    2.50 +- The adversary is passive. Being passive means that the adversary
    2.51 +  only monitors the network traffic, but still follows the protocol.
    2.52 +  We plan to add support for active (Byzantine) adversaries in a
    2.53 +  future version.
    2.54 +
    2.55 +The precise assumptions for each protocol will eventually be included
    2.56 +in the documentation for the corresponding method, but this has not
    2.57 +yet been done.
    2.58 +
    2.59 +Architecture
    2.60 +------------
    2.61 +
    2.62 +VIFF consists of several modules. The :mod:`viff.runtime` module
    2.63 +contains the :class:`Runtime <viff.runtime.Runtime>` and :class:`Share
    2.64 +<viff.runtime.Share>` classes, in which the main functionality is
    2.65 +implemented. The :mod:`viff.field` module contains implementations of
    2.66 +finite fields --- these are the values inside the shares. Other
    2.67 +modules provide support functions.
    2.68 +
    2.69 +Layers
    2.70 +""""""
    2.71 +
    2.72 +The main functionality in VIFF is implemented in the :class:`Runtime
    2.73 +<viff.runtime.Runtime>` class. This class offers methods to do
    2.74 +addition, multiplication, etc. These methods operate on :class:`Share
    2.75 +<viff.runtime.Share>` instances.
    2.76 +
    2.77 +Shares hold either :class:`GFElement <viff.field.GF>` or :class:`GF256
    2.78 +<viff.field.GF256>` elements and are created from the
    2.79 +:meth:`shamir_share <viff.runtime.Runtime.shamir_share>` or
    2.80 +:meth:`prss_share <viff.runtime.Runtime.prss_share>` :class:`Runtime
    2.81 +<viff.runtime.Runtime>` methods. Shares overload the standard
    2.82 +arithmetic operators, so you can write ``a + b - c * d`` with four
    2.83 +shares, and it will be translated correctly into the appropriate
    2.84 +method calls on the :class:`Runtime <viff.runtime.Runtime>` associated
    2.85 +with the shares.
    2.86 +
    2.87 +A field element contain the concrete value on which we do
    2.88 +calculations. This is just a normal Python (long) integer. The value
    2.89 +is wrapped in an object that will keep track of doing modulo
    2.90 +reductions as appropriate.
    2.91 +
    2.92 +So in a nutshell, VIFF has these layers:
    2.93 +
    2.94 +- Top-level layer for application programs: There you manipulate
    2.95 +  Python integers or :class:`viff.runtime.Share` instances.
    2.96 +
    2.97 +- Runtime layer: The runtime deals with Python integers or shares.
    2.98 +
    2.99 +- Field elements: Deals with arithmetic over Python integers, but with
   2.100 +  modulo reductions as needed.