**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 ($\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)$ $\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 $\ell$. Then, we show that when these non-arithmetic functions are based on secure modular conversions, they can be computed in constant rounds and $O(k)$ $\MULT$s, where $k$ is a parameter for an error rate of $2^{-\Omega(k)}$. To promote our protocols to be actively secure, we apply $O(k)$ basic zero-knowledge proofs, which cost at most $O(k)$ exponentiation computation, $O(1)$ rounds and $O(k(\ell+\kappa))$ communication bits, where $\kappa$ is the security parameter used in the commitment scheme.

**Category / Keywords: **applications / secure two-party computation, randomized algorithm, efficiency

**Date: **received 14 Oct 2011, last revised 15 Nov 2011

**Contact author: **chinghua yu at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20111115:214821 (All versions of this report)

**Short URL: **ia.cr/2011/560

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]