[viff-devel] Comparison for two parties

[Ivan Bjerre Damgård]

Folks,

If the Paillier runtime is specifically designed for two parties, then  
I think there are easier ways to fill in the missing stuff than to use  
a variant of prss.

More specifically, I believe the basic sharing method in the Paillier  
case is additive sharing, mod n, I guess, where n is the modulus -  
right?

So if you want to share random unknown value, it's dead easy: A and B  
choose a random value mod n each, say xA and xB and we define that the  
shared value is
x= xA +xB mod n.

Sharing a random unknown binary value is a bit harder, because the  
standard trick where we square and open a random value will not work  
here: we cannot compute square roots mod n efficiently, not even in  
public. But for two parties and passive security, it's not soo bad: we  
can just let A and B choose bits bA, bB and compute the  XOR in shared  
form: A chooses bA and B uses 0 as his share of bA (and vice versa for  
bB). Now, with b= bA XOR bB, we just use the standard formula
[b] = [bA] + [bB] - 2[bAbB]
For active security and assuming we have actively secure  
multiplication (which probably requires commitments to shares), we can  
still let A,B choose bA, bB, but then we compute and open [bAbA -bA]  
and likewise for bB. Both results had better be 0..

This can also be used to implement XOR in general, of course.


regards, Ivan