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
