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 wrap: on
line diff
--- a/doc/index.txt	Tue Apr 22 08:34:05 2008 +0200
+++ b/doc/index.txt	Tue Apr 22 08:38:25 2008 +0200
@@ -11,6 +11,7 @@
 .. toctree::
    :maxdepth: 2
 
+   overview
    glossary
 
 
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doc/overview.txt	Tue Apr 22 08:38:25 2008 +0200
@@ -0,0 +1,97 @@
+
+Overview
+========
+
+VIFF allows you to write a program which will interact with other
+programs in order to execute a joint computation. This is called a
+multi-party computation, MPC for short.
+
+The programs will implement what we call a virtual :term:`ideal
+functionality` (IF). The idea is that the behavior of the programs
+should be indistinguishable from the behavior of programs interacting
+with a so-called ideal functionality. An ideal functionality is a
+player that cannot be corrupted, also known as a trusted third party
+(TTP).
+
+Interacting with an IF is easy: all players give their inputs to the
+IF, which computes the results. The results are then distributed to
+the correct players. The inputs and the results are sent over secure
+channels, and since the IF cannot be corrupted, this ideal protocol
+must be secure.
+
+In the real world there is no IF, but VIFF allows you to implement a
+virtual ideal functionality. The behavior of a bunch of programs using
+VIFF is indistinguishable from program running in the ideal world. It
+is indistinguishable in the sense that everything that can happen in
+the real world protocol could happen in the ideal world too. And since
+no attacks can occur in the ideal world, no attacks can occur in the
+real world as well. Such a multi-party computation (MPC) is called a
+secure multi-party computation (SMPC).
+
+Security Assumptions
+--------------------
+
+Please note that like all cryptographic systems, VIFF is only secure
+as long as certain assumptions are fulfilled. These assumptions
+include:
+
+- The adversary can only corrupt up to a certain threshold of the
+  total number of players. The threshold will normally be 1/2 of the
+  players, so for three players, at most one player may be corrupted
+  (there must be an honest majority).
+
+- The adversary is computationally bounded. The protocols used by VIFF
+  rely on certain computational hardness assumptions, and therefore
+  only polynomial time adversaries are allowed.
+
+- The adversary is passive. Being passive means that the adversary
+  only monitors the network traffic, but still follows the protocol.
+  We plan to add support for active (Byzantine) adversaries in a
+  future version.
+
+The precise assumptions for each protocol will eventually be included
+in the documentation for the corresponding method, but this has not
+yet been done.
+
+Architecture
+------------
+
+VIFF consists of several modules. The :mod:`viff.runtime` module
+contains the :class:`Runtime <viff.runtime.Runtime>` and :class:`Share
+<viff.runtime.Share>` classes, in which the main functionality is
+implemented. The :mod:`viff.field` module contains implementations of
+finite fields --- these are the values inside the shares. Other
+modules provide support functions.
+
+Layers
+""""""
+
+The main functionality in VIFF is implemented in the :class:`Runtime
+<viff.runtime.Runtime>` class. This class offers methods to do
+addition, multiplication, etc. These methods operate on :class:`Share
+<viff.runtime.Share>` instances.
+
+Shares hold either :class:`GFElement <viff.field.GF>` or :class:`GF256
+<viff.field.GF256>` elements and are created from the
+:meth:`shamir_share <viff.runtime.Runtime.shamir_share>` or
+:meth:`prss_share <viff.runtime.Runtime.prss_share>` :class:`Runtime
+<viff.runtime.Runtime>` methods. Shares overload the standard
+arithmetic operators, so you can write ``a + b - c * d`` with four
+shares, and it will be translated correctly into the appropriate
+method calls on the :class:`Runtime <viff.runtime.Runtime>` associated
+with the shares.
+
+A field element contain the concrete value on which we do
+calculations. This is just a normal Python (long) integer. The value
+is wrapped in an object that will keep track of doing modulo
+reductions as appropriate.
+
+So in a nutshell, VIFF has these layers:
+
+- Top-level layer for application programs: There you manipulate
+  Python integers or :class:`viff.runtime.Share` instances.
+
+- Runtime layer: The runtime deals with Python integers or shares.
+
+- Field elements: Deals with arithmetic over Python integers, but with
+  modulo reductions as needed.