|
Equality testing with secret shared result.
Assumes p = 3 mod 4, returns a secret sharing of 1 if share_x ==
share_y and 0 otherwise.
This is the probabilistic method based on quadratic reciprocity
described in: "Constant-Round Multiparty Computation for Interval
Test, Equality Test, and Comparison" by Takashi Nishide and Kazuo
Ohta, and fails with probability 1/(2**k) where k is set to the security
parameter of the runtime.
TODO: Make it work for any prime-modulo, the b's should be in {y,1}
where y is a non-square modulo p.
TODO: Make the final "and"ing of the x's more efficient as
described in the paper.
|