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

$\endgroup$
  • $\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 Oct 14 '18 at 12:53
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$
  • $\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 Oct 31 '18 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 Nov 1 '18 at 15:30

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.