Welcome to the resource topic for 2011/560
Title:
Randomized Secure Two-Party Computation for Modular Conversion, Zero Test, Comparison, MOD and Exponentiation
Authors: Ching-Hua Yu, 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.
ePrint: https://eprint.iacr.org/2011/560
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .