Paper 2011/560

Randomized Secure Two-Party Computation for Modular Conversion, Zero Test, Comparison, MOD and Exponentiation

Ching-Hua Yu and Bo-Yin Yang

Abstract

When secure arithmetic is required, computation based on secure multiplication ($\text{MULT}$) is much more efficient than computation based on secure boolean circuits. However, a typical application can also require other building blocks, such as comparison, exponentiation and the modulo (MOD) operation. Secure solutions for these functions proposed in the literature rely on bit-decomposition or other bit-oriented methods, which require $O(\ell )$ $\text{MULT}$s for $\ell$-bit inputs. In the absence of a known bit-length independent solution, the complexity of the whole computation is often dominated by these non-arithmetic functions. To resolve the above problem, we start with a general modular conversion, which converts secret shares over distinct moduli. For this, we proposed a probabilistically correct protocol for this with a complexity that is independent of $$. Then, we show that when these non-arithmetic functions are based on secure modular conversions, they can be computed in constant rounds and $$ $$s, where $$ is a parameter for an error rate of $$. To promote our protocols to be actively secure, we apply $$ basic zero-knowledge proofs, which cost at most $$ exponentiation computation, $$ rounds and $$ communication bits, where $$ is the security parameter used in the commitment scheme.