International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Multiparty Computation for Modulo Reduction without Bit-Decomposition and a Generalization to Bit-Decomposition

Authors:
Chao Ning
Qiuliang Xu
Download:
URL: http://eprint.iacr.org/2010/266
Search ePrint
Search Google
Abstract: 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.
BibTeX
@misc{eprint-2010-23167,
  title={Multiparty Computation for Modulo Reduction without Bit-Decomposition and a Generalization to Bit-Decomposition},
  booktitle={IACR Eprint archive},
  keywords={foundations / Multiparty Computation, Constant Rounds, Secret Sharing, Bitwise Sharing, Digit-wise Sharing, Modulo Reduction, Generalization to Bit-Decomposition.},
  url={http://eprint.iacr.org/2010/266},
  note={ ncnfl@mail.sdu.edu.cn 14744 received 8 May 2010, last revised 15 May 2010},
  author={Chao Ning and Qiuliang Xu},
  year=2010
}