Paper 2010/266

Multiparty Computation for Modulo Reduction without Bit-Decomposition and A Generalization to Bit-Decomposition

Chao Ning and Qiuliang Xu

Abstract

Bit-decomposition, which is proposed by Damgård \emph{et al.}, is a powerful tool for multi-party computation (MPC). Given a sharing of secret $x$, it allows the parties to compute the sharings of the bits of $x$ 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 \emph{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 $x$ into the sharings of the digits of $x$, 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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. AsiaCrypt 2010. LNCS, vol 6477, pp. 483-500. Springer, Heidelberg (2010)
Keywords
Secure ComputationMultiparty ComputationConstant-RoundsModulo ReductionGeneralization to Bit-Decomposition.
Contact author(s)
ncnfl @ 163 com
History
2015-09-23: last of 8 revisions
2010-05-11: received
See all versions
Short URL
https://ia.cr/2010/266
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/266,
      author = {Chao Ning and Qiuliang Xu},
      title = {Multiparty Computation for Modulo Reduction without Bit-Decomposition and A Generalization to Bit-Decomposition},
      howpublished = {Cryptology ePrint Archive, Paper 2010/266},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/266}},
      url = {https://eprint.iacr.org/2010/266}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.