Welcome to the resource topic for 2010/266
Title:
Multiparty Computation for Modulo Reduction without Bit-Decomposition and A Generalization to Bit-Decomposition
Authors: Chao Ning, Qiuliang Xu
Abstract:Bit-decomposition, which is proposed by Damgård \emph{et al.}, is a powerful tool for multi-party computation (MPC). Given a sharing of secret x, it allows the parties to compute the sharings of the bits of x in constant rounds. With the help of bit-decomposition, constant-rounds protocols for various MPC problems can be constructed. However, bit-decomposition is relatively expensive, so constructing protocols for MPC problems without relying on bit-decomposition is a meaningful work. In multi-party computation, it remains an open problem whether the \emph{modulo reduction problem} can be solved in constant rounds without bit-decomposition. In this paper, we propose a protocol for (public) modulo reduction without relying on bit-decomposition. This protocol achieves constant round complexity and linear communication complexity. Moreover, we show a generalized bit-decomposition protocol which can, in constant rounds, convert the sharing of secret x into the sharings of the digits of x, along with the sharings of the bits of every digit. The digits can be base-\emph{m} for any m\geq2. Obviously, when \emph{m} is a power of 2, this generalized protocol is just the original bit-decomposition protocol.
ePrint: https://eprint.iacr.org/2010/266
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 .