SPDZ- How to do secure equality comparison

Question

The SPDZ paper explains how the SPDZ protocol can be used to find the sum/product of secret values and find the sum/product of a secret and a non-secret value (page 6).

The paper seems to say that from this you can do any other operation. How would you use this to do secure equality comparison between a secret and a non-secret value?

The Array Lookup section of the Bristol SPDZ implementation tutorial shows that their implementation has a way of securely evaluating whether a secret value equals a non-secret value to get a secret result. This is heavily used in Array lookups so one would hope it is an efficient operation. How did they implement this? It doesn't seem to be in the paper.

Answer 1

To test whether a secret value $[x]$ is zero, where $x \in [0,2^k-1]$, SPDZ uses the following blueprint, based on the method of Catrina and de Hoogh:

• Take a secret preprocessed value $[r]$, where $r$ is uniformly random in $[0, 2^{k+s}-1]$, along with shares of the first $k$ bits of $r$, $[r_0], \dots, [r_{k-1}]$
• Open $c = x + r$, let $c_0,\dots,c_{k-1}$ be its $k$ least sig. bits
• For $i=0,\dots,k-1$, compute $[d_i] = c_i + [r_i] - 2c_i[r_i]$
• Output $1 - OR([d_0], \dots, [d_{k-1}])$

This requires the modulus $p > 2^{k+s}$, where $s$ is a statistical security parameter (typically 40), ensuring that $x+r$ does not overflow or leak information on $x$.

Note that $d_i$ is computed to be the XOR of $c_i$ and $r_i$. If $x=0$ then the first $k$ bits of $c$ are equal to the first $k$ bits of $r$, so $d_i$ are all zero and the output is 1. Otherwise 0 is output, as required.

Compute the OR in the last step can be done naively with $k-1$ multiplications in $O(\log k)$ rounds. There are also some tricks to do it in a constant number of rounds described in the paper linked above.

Answer 2

One way of doing this is to subtract the non-secret value from the secret value (in the secure computation) and to test that the result is 0. There are a number of ways of testing 0; generically, you can generate a shared unknown random value, multiply it with the value you want to test and then open. If the opened value is 0 then you know that you started with 0. Otherwise, it's a random value and reveals nothing (since the shared random value is unknown to all parties and so masks the original value).