3
$\begingroup$

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

This method requires to working on a field with modulus $p>2^{k+s}$, where $s$ is a is a statistical security parameter.

Does another method exist that perform this comparison but eliminate the need for security bits (performance is not my #1 concern)?

Thanks.

[1]-https://www1.cs.fau.de/filepool/publications/octavian_securescm/smcint-scn10.pdf

Improve this question
$\endgroup$
1
  • $\begingroup$ If you want to see whether [x] is zero you can retrieve a random [r] and then Open([x] * [r]). Checking whether [x] > 0 or [x] < 0 it's more complicated and I am not aware of any method computing this without some special preprocessed random bits [b] (using SPDZ). $\endgroup$
    – Dragos
    Commented Oct 14, 2018 at 12:53

1 Answer 1

Reset to default
3
$\begingroup$

Secure zero-testing without working in a large field can be done with a protocol by Lipmaa and Toft, and with similar efficiency to the Catrina and de Hoogh protocols.

The basic idea is to open $m = x+r \bmod p$, where $r$ is a uniformly random field element and the parties have shares of the bits of $r$.

The parties will test whether $m$ equals $r$ by computing shares of the Hamming distance $[H] = \sum_i (m_i + [r_i] - 2m_i[r_i])$ (which is $\sum m_i \oplus r_i$). Note that $x=0$ iff $H=0$.

They test whether $H = 0$ with a polynomial interpolation trick - this can be done with around $\log p$ multiplications since $H \le \log p$, and most of these can be preprocessed in advance (see Section 3.1 of the paper for the details).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Didn't know about this method. It seems to me that in order to generate the bit decomposition of [r] in $F_p$ one still needs room for $s$ bits though (as BitDec instruction is implemented now in SPDZ). Am I missing something? $\endgroup$
    – Dragos
    Commented Oct 31, 2018 at 17:44
  • 1
    $\begingroup$ You just need to do it in reverse - start with $\log p$ random bits, then add them up to get $[r]$. If $p$ is large and close to a power of 2 then $r$ is statistically close to uniform (and if not, just use $s$ extra random bits). $\endgroup$
    – pscholl
    Commented Nov 1, 2018 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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