International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Chao Ning

Affiliation: IIIS, Tsinghua University, Beijing, P.R. China

Publications

Year
Venue
Title
2011
ASIACRYPT
2010
EPRINT
Multiparty Computation for Modulo Reduction without Bit-Decomposition and a Generalization to Bit-Decomposition
Chao Ning Qiuliang Xu
Bit-decomposition, which is proposed by Damg{\aa}rd \emph{et al.}, is a powerful tool for multi-party computation (MPC). Given a sharing of secret \emph{a}, it allows the parties to compute the sharings of the bits of \emph{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 also propose a generalization to bit-decomposition which can, in constant rounds, convert the sharing of secret \emph{a} into the sharings of the "digits" of \emph{a}, 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.
2010
ASIACRYPT

Coauthors

Qiuliang Xu (3)