3
$\begingroup$

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 less-than comparison?

The Bristol SPDZ implementation tutorial program (line 19) shows that their implementation has a way of securely comparing two secret values to get a secret result. How did they implement this? It doesn't seem to be in the paper.

$\endgroup$
  • $\begingroup$ The very short answer is "its complicated". I do not remember the exact details but this paper explains one method to such a comparison kodu.ut.ee/~lipmaa/papers/lt13/improvedEqAndGT.pdf . This is just one method, I am sure there are others. $\endgroup$ – Guut Boy Nov 11 '16 at 8:06
4
$\begingroup$

The way this is currently done within SPDZ is using a primitive which allows to truncate a secret shared value $[s]$ by a publicly known power of $2$.

You can see the code here.

In SPDZ, $k$ bit integers are in range $(-2^{k-1},2^{k-1})$. They are represented as $x \mapsto x$ mod $p$. So every number $x \in [2^{k-1},2^{k})$ is considered a negative number.

From a high level overview if we have the truncation, we can compute $[a] < [b]$ as a secret value:

  1. Assign $s \leftarrow ([a - b])$ locally to see $[s < 0]$.
  2. Denote $k$ as the bit length of $s$. Take $r \leftarrow [s/2^{k-1}]$ which has output either $[0]$ or $[1]$ depending on the sign of $s$. Due to some technicalities of sign preserving, the output is in practice $[0]$ or $[-1]$.
  3. To normalize the result, output $0 - [r]$. This is done locally again.

The expensive part here is step $2$ since parties have to communicate to achieve the truncation.

If you want to check the details you can find the specific protocols ($3.2$, $3.3$) on page $7$ here.

$\endgroup$
  • $\begingroup$ I'd originally meant an equality comparison, but I realize that wasn't clear in the question. Since this is a good answer to the question of less-than comparison, I have rephrased my question to be about that and asked a new question about equality comparison here $\endgroup$ – danxinnoble Nov 15 '16 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.