If you boil down VIFF, or any MPC program you can boil it down to 5
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
viff-devel mailing list (http://viff.dk/)