Other nice 2. order operations are bitsplitting (and also
recombination of the bits) and multiplicative inverse (works only if
you can guarantee a non-zero element)

And when you have the bits you would also like logic negation, xor, and and or.

- Sigurd

On Tue, Aug 25, 2009 at 9:22 AM, Tord Ingolf Reistad<to...@stud.ntnu.no> wrote:
> 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.
>
>
> _______________________________________________
> viff-devel mailing list (http://viff.dk/)
> viff-devel@viff.dk
> http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
>
_______________________________________________
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Reply via email to