Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

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

Chao Ning, Qiuliang Xu

Published Jan 1, 2010• 25 citations
Publisher
DOI
10.1007/978-3-642-17373-8_28

Related papers

Multiparty Computation for Interval, Equality, and Comparison Without Bit-Decomposition Protocol

Takashi Nishide, Kazuo Ohta

Springer eBooks•Jun 20, 2007•230 citations

Constant-Rounds, Linear Multi-party Computation for Exponentiation and Modulo Reduction with Perfect Security.

Chao Ning, Qiuliang Xu

Bit-decomposition is an important primitive in 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, 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, i.e. the communication complexity is non-linear. Constructing protocols for MPC problems without relying on bit-decomposition is a meaningful work because this may provide us with perfect 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

•Jan 1, 2011•1 citation

Semi-homomorphic Encryption and Multiparty Computation

Rikke Bendlin, Ivan Damgård, Claudio Orlandi +1 more

Lecture notes in computer science•Jan 1, 2011•367 citations

Multiparty Computation from Threshold Homomorphic Encryption

Ronald Cramer, Ivan Damgård, Jesper Buus Nielsen

Lecture notes in computer science•Jan 1, 2001•598 citations

Bit Decomposition Protocols in Secure Multiparty Computation

Peeter Laud, Alisa Pankova

We present improved protocols for the conversion of secret-shared bit-vectors into secret-shared integers and vice versa, for the use as subroutines in secure multiparty computation (SMC) protocols and for protocols verifying the adherence of parties to prescribed SMC protocols. The protocols are primarily designed for three-party computation with honest majority. We evaluate our protocols as part of the Sharemind three-party protocol set and see a general reduction of verification overheads, thereby increasing the practicality of covertly or actively secure Sharemind protocols.

•Jan 1, 2018•1 citation

Hybrid Quantum Protocols for Secure Multiparty Summation and Multiplication

Kartick Sutradhar, Hari Om

The summation and multiplication are two basic operations for secure multiparty quantum computation. The existing secure multiparty quantum summation and multiplication protocols have (n, n) threshold approach and their computation type is bit-by-bit, where n is total number of players. In this paper, we propose two hybrid (t, n) threshold quantum protocols for secure multiparty summation and multiplication based on the Shamir's secret sharing, SUM gate, quantum fourier transform, and generalized Pauli operator, where t is a threshold number of players that can perform the summation and multiplication. Their computation type is secret-by-secret with modulo d, where d, n ≤ d ≤ 2n, is a prime. The proposed protocols can resist the intercept-resend, entangle-measure, collusion, collective, and coherent quantum attacks. They have better computation as well as communication costs and no player can get other player's private input.

Scientific Reports•Jun 4, 2020•58 citations
Bit-decomposition is an important primitive in 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, 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, i.e. the communication complexity is non-linear. Constructing protocols for MPC problems without relying on bit-decomposition is a meaningful work because this may provide us with perfect 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
We present improved protocols for the conversion of secret-shared bit-vectors into secret-shared integers and vice versa, for the use as subroutines in secure multiparty computation (SMC) protocols and for protocols verifying the adherence of parties to prescribed SMC protocols. The protocols are primarily designed for three-party computation with honest majority. We evaluate our protocols as part of the Sharemind three-party protocol set and see a general reduction of verification overheads, thereby increasing the practicality of covertly or actively secure Sharemind protocols.
The summation and multiplication are two basic operations for secure multiparty quantum computation. The existing secure multiparty quantum summation and multiplication protocols have (n, n) threshold approach and their computation type is bit-by-bit, where n is total number of players. In this paper, we propose two hybrid (t, n) threshold quantum protocols for secure multiparty summation and multiplication based on the Shamir's secret sharing, SUM gate, quantum fourier transform, and generalized Pauli operator, where t is a threshold number of players that can perform the summation and multiplication. Their computation type is secret-by-secret with modulo d, where d, n ≤ d ≤ 2n, is a prime. The proposed protocols can resist the intercept-resend, entangle-measure, collusion, collective, and coherent quantum attacks. They have better computation as well as communication costs and no player can get other player's private input.