[viff-devel] The primitives of MPC

[Tord Ingolf Reistad]

If you boil down VIFF, or any MPC program you can boil it down to 5 
primitives.

These primitives are
x + y = z       Addition
x * y = z       Multiplication
-x = z          Negation
z = Share(x)    Secret sharing
z = Reveal(x)   Revealing of a secret sharing

My question is now: What are the second order primitives?

What are the basic features that, make a programmers life easy but not 
essential. I would propose the following 5:
z = f(x,y)     Function calls
for(0 to n)    A for call with a fixed number of iterations.
z = Rand(x)    Generating random values in Zp
x = y          Equation
x < y          Comparison
while( x )     A while loop on x, where x is a revealed value

The first 2 primitives are easy since they are already implemented using 
the underlying programming language.
Should creating random values be on this list? Or should it maybe be 
among the first order primitives, a basic building block of MPC.
Equation and comparison are obvious second order primitives and has been 
my research topic for many years.
The last on the list is the while loop, I have included it because I 
have seen many times that you want to compute some function, open a 
variable, check some information and then redo the function if the 
revealed value was false. This can be found when creating random values 
less than some threshold, creating RSA primes, and many other 
algorithms. Also it is not trivial to program if you want it to be 
efficient.