标题：Constant-Rounds, Linear Multi-party Computation for Exponentiation and Modulo Reduction with Perfect Security
作者：Ning, Chao; Xu, Qiuliang
作者机构：[Ning, Chao; Xu, Qiuliang] Shandong Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China.
会议名称：17th Annual International conference on the Theory and Application of Cryptology and Information Security
会议日期：DEC 04-08, 2011
来源：ADVANCES IN CRYPTOLOGY - ASIACRYPT 2011
关键词：Multi-party Computation; Perfectly Secure; Constant-Rounds; Linear;; Exponentiation; Modulo Reduction; Bit-Decomposition
摘要：Bit-decomposition is an important primitive in multi-party computation (MPC). With the help of bit-decomposition, we will be able to construct constant-rounds protocols for various MPC problems, such as equality test, comparison, public modulo reduction and private exponentiation, which are four main applications of bit-decomposition. However, when considering perfect security, bit-decomposition does not have a linear communication complexity; thus any protocols involving bit-decomposition inherit this inefficiency. Constructing protocols for MPC problems without relying on bit-decomposition is a meaningful work because this may provide us with perfectly secure protocols with linear communication complexity. It is already proved that equality test, comparison and public modulo reduction can be solved without involving bit-decomposition and the communication complexity can be reduced to linear. However, it remains an open problem whether private exponentiation could be done without relying on bit-decomposition. In this paper, maybe somewhat surprisingly, we show that it can. That is to say, we construct a constant-rounds, linear, perfectly secure protocol for private exponentiation without relying on bit-decomposition though it seems essential to this problem.; In a recent work, Ning and Xu proposed a generalization of bit-decomposi-tion and, as a simplification of their generalization, they also proposed a linear protocol for public modulo reduction. In this paper, we show that their generalization can be further generalized; more importantly, as a simplification of our further generalization, we propose a public modulo reduction protocol which is more efficient than theirs.