# Testing whether a secret value is zero without security bits (in SPDZ)

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.

• 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). – Dragos Oct 14 '18 at 12:53

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).
• 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? – Dragos Oct 31 '18 at 17:44
• 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). – pscholl Nov 1 '18 at 15:30