标题：Multiparty Computation for Modulo Reduction without Bit-Decomposition and a Generalization to Bit-Decomposition
作者：Qiu, Chao Ning; Xu, Qiuliang
作者机构：[Qiu, Chao Ning; Xu, Qiuliang] Shandong Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China.
会议名称：16th International Conference on the Theory and Application of Cryptology and Information Security
会议日期：DEC 05-09, 2010
来源：ADVANCES IN CRYPTOLOGY - ASIACRYPT 2010
关键词：Multiparty Computation; Constant-Rounds; Modulo Reduction;; Generalization to Bit-Decomposition
摘要：Bit-decomposition, which is proposed by Damgard et al., is a powerful tool for multi-party computation (MPC). Given a sharing of secret a, it allows the parties to compute the sharings of the bits of a 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 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 a into the sharings of the digits of a, along with the sharings of the bits of every digit. The digits can be base-m for any m >= 2.