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:
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).
Making a secret value public. (Protocol 3.7, step 2). This requires $1$ invocation.
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.
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?