Communication Complexity of Equality comparison (Catrina and de Hoogh)

Question

I was reading secure MPC protocol for finding a secret representation of whether a secret value equals zero, from Catrina and de Hoogh (summarized here).

In the paper, the communication complexity costs are measured in terms of "invocations of a primitive in which every party sends a share ... to the others" (page 3). The paper shows a way to do equality-to-zero testing in a constant number of rounds. This seems to require the following costs:

1. Generating a secret random number r, as well as secret representations of its lower $k$ bits by calling PRandM (Protocol 3.7, step 1). This requires $k$ invocations (see Table 1).

2. Making a secret value public. (Protocol 3.7, step 2). This requires $1$ invocation.

3. Generate a public product of two secret numbers by calling MulPub. This is done $2k$ times. (Protocol 4.2, steps 4 and 9) This requires $2k$ invocations.

4. Generate a secret product of two secret numbers. This is done $k-1$ times. (Protocol 4.2, step 5) and requires $k-1$ invocations.

(I am assuming Protocol 4.2 is how KOr from Protocol 3.7 is implemented.)

What does an invocation mean? Does it mean $O(n^2)$ data complexity? Does this mean the total communication complexity is something like $O(kn^2)$?

The SPDZ protocol, shows that the multiplication of secret values to generate a secret value (Cost #4) can be moved to a pre-processing phase by generating Mulitplicative Triples. Can Costs #1 and #3 also be moved to a pre-processing phase?

I was pointed to Catrina and de Hoogh here as an implementation of secure equality-to-zero test that can be used in a SPDZ-like environment. By SPDZ-like environment I mean each secret number $a$ is represented by each party having a 'share' of that number $a_i$, such that $\sum a_i = a (\mod p)$ for some large prime (or exponent of a prime) $p$. Is Catrina and de Hoogh the most computationally efficient constant-round protocol currently out there that does a secure equals-zero test of a secret value to generate a secret result?

Answer 1

What does an invocation mean?

The communication cost of opening 1 secret-shared field element.

Since the protocols of Catrina and de Hoogh are mostly independent of the underlying MPC protocol, this cost can vary. In SPDZ, for example, the trivial opening algorithm requires $O(n^2)$ field elements to be sent across the network in all, but it can also be done in $O(n)$ (see p25).

Can Costs #1 and #3 also be moved to a pre-processing phase?

Step 1 just generates random bits, so can be done as preprocessing. Step 3 consists of two parts: the first (line 4 of Protocol 4.2 in the paper) can be preprocessed, while the second (line 9) depends on the inputs, $[a_i]$, so must be done online.

Is Catrina and de Hoogh the most computationally efficient constant-round protocol currently out there that does a secure equals-zero test of a secret value to generate a secret result?

There's a paper by Lipmaa and Toft with a constant-round equality test with less communication than Catrina and de Hoogh's. However, it has higher local computation costs. I don't know of a computationally more efficient protocol.