[viff-devel] The primitives of MPC

[Mikkel Krøigård]

I think it deserves to be mentioned that you can do conditional  
statements on secret values in some cases. A simple case is easy to  
implement with the other primitives, but then of course you can be  
annoying and start nesting them.


Citat af Sigurd Torkel Meldgaard <stm at cs.au.dk>:

> 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<tordr at 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 at viff.dk
>> http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
>>
> _______________________________________________
> viff-devel mailing list (http://viff.dk/)
> viff-devel at viff.dk
> http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
>