SPDZ- How to do secure less-than comparison

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.

• 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. Nov 11 '16 at 8:06

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 $$ or $$ depending on the sign of $s$. Due to some technicalities of sign preserving, the output is in practice $$ 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.

• 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 Nov 15 '16 at 1:46