CryptoDB
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
}