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

Journal of Information Processing

Client-aided Robust Bit-composition Protocol with Deterministic Cheater Identification in Standard Model

Hikaru Tsuchida, Takashi Nishide

Published Jan 1, 2021• 0 citations
Publisher

Abstract

Secure multiparty computation (MPC) enables parties to compute an arbitrary function without revealing each party's inputs. A typical MPC is secret-sharing based MPC (SS-MPC). In the SS-MPC, each party distributes its inputs, and the computation proceeds with secret shares that look exactly like random numbers distributed among the parties. In the SS-MPC protocol, the parties can compute any function represented as a circuit by using shares locally and communicating among the parties. In particular, when the parties compute a complex function composed of binary and arithmetic circuits, an efficient share conversion protocol facilitates the computation of it. An important conversion protocol is a bit-composition protocol that converts a k-dimensional vector with shares on ℤ2 (i.e., shares of binary sequence) to shares on ℤ2k (i.e., shares of decimal value). Previous studies proposed a maliciously secure bit-composition protocol with robustness, which is a security notion that all parties learn the correct output regardless of the attacker's behaviour. However, its security is dependent on a statistical parameter or proved in the random oracle model. In this paper, we propose a novel bit-composition protocol with robustness independent of a statistical parameter by introducing additional clients generating the pair of shares of random values only in the offline phase (which can be performed without the parties' inputs). Our protocol is based on a maliciously secure four-party protocol with one corruption using replicated secret sharing. The security of our protocol is proved in the standard model (which is a weaker assumption than the random oracle model). Our protocol achieves efficiency and the strongest security simultaneously. We also propose a protocol for the Hamming distance with robustness by modifying our bit-composition protocol. It can achieve a secure iris recognition service via MPC with robustness. Furthermore, we extend our protocol with a constant number of parties and clients to one with an arbitrary number of parties and clients.

DOI
10.2197/ipsjjip.29.515

Related papers

Client-Aided Bit-Composition Protocol with Guaranteed Output Delivery

Hikaru Tsuchida, Takashi Nishide

Secure multiparty computation (MPC) enables par-ties to compute an arbitrary function without revealing each party’s inputs. A typical MPC is the secret sharing based MPC (SS-MPC). In the SS-MPC, each party distributes its inputs, and the computation proceeds with secret shares that just look like random numbers distributed among the parties. In the SS-MPC protocol, the parties can compute any function represented as a circuit by using shares locally and communicating among the parties. In particular, when the parties compute a complex function composed of binary and arithmetic circuits, an efficient share conversion protocol facilitates the computation of it. An important conversion protocol is the bit-composition protocol that converts a k-dimensional vector with the shares on Z 2 (i.e., shares of binary sequence) to the shares on Z 2 k (i.e., shares of decimal value). The previous work proposed a maliciously secure bit-composition protocol with guaranteed output delivery (GOD), which is the security notion that all the parties learn the correct output regardless of the attacker’s behaviour. However, its security is proved in the random oracle model.In this paper, we propose a new bit-composition protocol with GOD by introducing additional clients just helping the parties during computation. Our protocol is based on a maliciously secure four-party protocol with one corruption using replicated secret sharing. The security of our protocol is proved in the standard model (which is weaker than the random oracle model). Our protocol achieves the efficiency and strongest security simultaneously. We also propose a protocol for the Hamming distance with GOD by modifying our bit-composition protocol. It achieves a secure iris recognition service via MPC with GOD.

International Symposium on Information Theory and its Applications•Oct 24, 2020•0 citations

An Efficient Framework for Unconditionally Secure Multiparty Computation

Ashish Choudhury, Arpita Patra

parties to securely compute an agreed function f over some finite field in the presence of a computationally unbounded adversary, who can maliciously corrupt any t out of the n parties. Most of the known efficient MPC protocols are designed in the offline- online framework introduced in a seminal work by Beaver in CRYPTO 1991. In this framework, the parties generate shared random and private multiplication-triples during the offline phase, which are used later in the online phase for securely evaluating the multiplication gates in the circuit representing f . The efficiency of the MPC protocols in this framework then relies on efficient ways of implementing the offline phase. In this paper, we propose a new and simple framework for generating shared and private random multiplication triples with unconditional security. The existing protocols approach this problem by first producing shared pairs of private and random values, followed by securely computing the shared product of each pair of values. The latter task involves a multiplication protocol for shared values that are typically communication intensive. Our framework takes a completely different approach and shuns the use of multiplication protocol. Namely, we ask the parties to verifiably share random multiplication triples and then securely extract shared random multiplication triples unknown to the adversary, from the shared triples. Realizing our framework in the asynchronous and hybrid network setting,1 we present the first ever MPC protocols with a linear (in the number of parties) communication overhead per multiplication gate in the circuit representing f . These are significant improvements over the best known existing MPC protocols in the asynchronous and hybrid network setting with communication complexity O(n2) and O(n3), respectively. Our framework when applied to the synchronous setting results in round-efficient MPC protocols.

IEEE Transactions on Information Theory•Oct 4, 2016•63 citations

Committed MPC: Maliciously Secure Multiparty Computation from Homomorphic Commitments

Tore Kasper Frederiksen, Benny Pinkas B, Avishay Yanai

We present a new multiparty computation protocol secure against a static and malicious dishonest majority. Unlike most previous protocols that were based on working on MAC-ed secret shares, our approach is based on computations on homomorphic commitments to secret shares. Specifically we show how to realize MPC using any additively-homomorphic commitment scheme, even if such a scheme is an interactive two-party protocol. Our new approach enables us to do arithmetic computation over arbitrary finite fields. In addition, since our protocol computes over committed values, it can be readily composed within larger protocols, and can also be used for efficiently implementing committing OT or committed OT. This is done in two steps, each of independent interest: Black-box extension of any (possibly interactive) two-party additively homomorphic commitment scheme to an additively homomorphic multiparty commitment scheme, only using coin-tossing and a “weak” equality evaluation functionality. Realizing multiplication of multiparty commitments based on a lightweight preprocessing approach. Finally we show how to use the fully homomorphic commitments to compute any functionality securely in the presence of a malicious adversary corrupting any number of parties.

Lecture notes in computer science•Jan 1, 2018•20 citations

Enhancement of security in cloud computing with secure multi-party computation

Abhijeet Kumar, N J.V.Vineetha, P Sai Chakradar +1 more

The N sets of parties which are allowed by unconditionally the secure multiparty computation (MPC) for computing securely with a registered function f with the help of unbounded adversary computational at some specified field. Here one can corrupt t among n parties maliciously corrupt. The Protocols of MPC which are known and efficient are developed for online or offline framework. Coming to the offline process, the private & random multiplication-triples which is sharable can be generated by the parties in this framework. Later on, these are useful for online to evaluate the multiplication of gates securely in a circuit which describes as f. In this, Protocols of the MPC efficiency depends on the how the offline implementation efficiently. Here, we proposed a simple method, for shared & private multiplication-triples which are random in nature generation without any conditions securely & safely. The typical protocols face this issue, when the random values of shared pairs produced initially. And also, in computing the product values which is shared for every pair. After that, protocols of multiplication and values which are considered as communication intensive. In proposed scheme, the multiplication protocols are completely used in different manner. Later on, we observe that the share multiplication-triples verification by parties or they are extracted securely or not. With the use of setting of the hybrid network and asynchronous, linear communication MPC protocols used which are multiplication gate overhead & indicates as f. The above are the improvements on the typical MPC protocols with the help of hybrid networking setting, asynchronous and complexity of the communication, if we give to result of synchronous setting in our system. It results efficient MPC protocols which are rounded.

International Journal of Engineering & Technology•Dec 21, 2017•1 citation

Multiparty computation secure against continual memory leakage

Elette Boyle, Shafi Goldwasser, Abhishek Jain +1 more

We construct a multiparty computation (MPC) protocol that is secure even if a malicious adversary, in addition to corrupting 1-ε fraction of all parties for an arbitrarily small constant ε >0, can leak information about the secret state of each honest party. This leakage can be continuous for an unbounded number of executions of the MPC protocol, computing different functions on the same or different set of inputs. We assume a (necessary) "leak-free" preprocessing stage. We emphasize that we achieve leakage resilience without weakening the security guarantee of classical MPC. Namely, an adversary who is given leakage on honest parties' states, is guaranteed to learn nothing beyond the input and output values of corrupted parties. This is in contrast with previous works on leakage in the multi-party protocol setting, which weaken the security notion, and only guarantee that a protocol which leaks l bits about the parties' secret states, yields at most l bits of leakage on the parties' private inputs. For some functions, such as voting, such leakage can be detrimental.

ACM Symposium on Theory of Computing (STOC)•May 19, 2012•55 citations

Scalable Mixed-Mode MPC

Radhika Garg, Kang Yang, Jonathan Katz +1 more

Protocols for secure multi-party computation (MPC) supporting mixed-mode computation have found a lot of applications in recent years due to their flexibility in representing the function to be evaluated. However, existing mixed-mode MPC protocols are only practical for a small number of parties: they are either tailored to the case of two/three parties, or scale poorly for a large number of parties.In this paper, we design and implement a new system for highly efficient and scalable mixed-mode MPC tolerating an arbitrary number of semi-honest corruptions. Our protocols allow secret data to be represented in Encrypted, Boolean, Arithmetic, or Yao form, and support efficient conversions between these representations.1)We design a multi-party table-lookup protocol, where both the index and the table can be kept private. The protocol is scalable even with hundreds of parties.2)Using the above protocol, we design efficient conversions between additive arithmetic secret sharings and Boolean secret sharings for a large number of parties. For 32 parties, our conversion protocols require 1184× to 8141× less communication compared to the state-of-the-art protocols MOTION and MP-SPDZ; this leads to up to 1275× improvement in running time under 1 Gbps network. The improvements are even larger with more parties.3)We also use new protocols to design an efficient multi-party distributed garbling protocol. The protocol could achieve asymptotically constant communication per party.Our implementation will be made public.

IEEE Symposium on Security and Privacy (S&P)•May 19, 2024•15 citations
Secure multiparty computation (MPC) enables parties to compute an arbitrary function without revealing each party's inputs. A typical MPC is secret-sharing based MPC (SS-MPC). In the SS-MPC, each party distributes its inputs, and the computation proceeds with secret shares that look exactly like random numbers distributed among the parties. In the SS-MPC protocol, the parties can compute any function represented as a circuit by using shares locally and communicating among the parties. In particular, when the parties compute a complex function composed of binary and arithmetic circuits, an efficient share conversion protocol facilitates the computation of it. An important conversion protocol is a bit-composition protocol that converts a k-dimensional vector with shares on ℤ2 (i.e., shares of binary sequence) to shares on ℤ2k (i.e., shares of decimal value). Previous studies proposed a maliciously secure bit-composition protocol with robustness, which is a security notion that all parties learn the correct output regardless of the attacker's behaviour. However, its security is dependent on a statistical parameter or proved in the random oracle model. In this paper, we propose a novel bit-composition protocol with robustness independent of a statistical parameter by introducing additional clients generating the pair of shares of random values only in the offline phase (which can be performed without the parties' inputs). Our protocol is based on a maliciously secure four-party protocol with one corruption using replicated secret sharing. The security of our protocol is proved in the standard model (which is a weaker assumption than the random oracle model). Our protocol achieves efficiency and the strongest security simultaneously. We also propose a protocol for the Hamming distance with robustness by modifying our bit-composition protocol. It can achieve a secure iris recognition service via MPC with robustness. Furthermore, we extend our protocol with a constant number of parties and clients to one with an arbitrary number of parties and clients.
Secure multiparty computation (MPC) enables par-ties to compute an arbitrary function without revealing each party’s inputs. A typical MPC is the secret sharing based MPC (SS-MPC). In the SS-MPC, each party distributes its inputs, and the computation proceeds with secret shares that just look like random numbers distributed among the parties. In the SS-MPC protocol, the parties can compute any function represented as a circuit by using shares locally and communicating among the parties. In particular, when the parties compute a complex function composed of binary and arithmetic circuits, an efficient share conversion protocol facilitates the computation of it. An important conversion protocol is the bit-composition protocol that converts a k-dimensional vector with the shares on Z 2 (i.e., shares of binary sequence) to the shares on Z 2 k (i.e., shares of decimal value). The previous work proposed a maliciously secure bit-composition protocol with guaranteed output delivery (GOD), which is the security notion that all the parties learn the correct output regardless of the attacker’s behaviour. However, its security is proved in the random oracle model.In this paper, we propose a new bit-composition protocol with GOD by introducing additional clients just helping the parties during computation. Our protocol is based on a maliciously secure four-party protocol with one corruption using replicated secret sharing. The security of our protocol is proved in the standard model (which is weaker than the random oracle model). Our protocol achieves the efficiency and strongest security simultaneously. We also propose a protocol for the Hamming distance with GOD by modifying our bit-composition protocol. It achieves a secure iris recognition service via MPC with GOD.
parties to securely compute an agreed function f over some finite field in the presence of a computationally unbounded adversary, who can maliciously corrupt any t out of the n parties. Most of the known efficient MPC protocols are designed in the offline- online framework introduced in a seminal work by Beaver in CRYPTO 1991. In this framework, the parties generate shared random and private multiplication-triples during the offline phase, which are used later in the online phase for securely evaluating the multiplication gates in the circuit representing f . The efficiency of the MPC protocols in this framework then relies on efficient ways of implementing the offline phase. In this paper, we propose a new and simple framework for generating shared and private random multiplication triples with unconditional security. The existing protocols approach this problem by first producing shared pairs of private and random values, followed by securely computing the shared product of each pair of values. The latter task involves a multiplication protocol for shared values that are typically communication intensive. Our framework takes a completely different approach and shuns the use of multiplication protocol. Namely, we ask the parties to verifiably share random multiplication triples and then securely extract shared random multiplication triples unknown to the adversary, from the shared triples. Realizing our framework in the asynchronous and hybrid network setting,1 we present the first ever MPC protocols with a linear (in the number of parties) communication overhead per multiplication gate in the circuit representing f . These are significant improvements over the best known existing MPC protocols in the asynchronous and hybrid network setting with communication complexity O(n2) and O(n3), respectively. Our framework when applied to the synchronous setting results in round-efficient MPC protocols.
We present a new multiparty computation protocol secure against a static and malicious dishonest majority. Unlike most previous protocols that were based on working on MAC-ed secret shares, our approach is based on computations on homomorphic commitments to secret shares. Specifically we show how to realize MPC using any additively-homomorphic commitment scheme, even if such a scheme is an interactive two-party protocol. Our new approach enables us to do arithmetic computation over arbitrary finite fields. In addition, since our protocol computes over committed values, it can be readily composed within larger protocols, and can also be used for efficiently implementing committing OT or committed OT. This is done in two steps, each of independent interest: Black-box extension of any (possibly interactive) two-party additively homomorphic commitment scheme to an additively homomorphic multiparty commitment scheme, only using coin-tossing and a “weak” equality evaluation functionality. Realizing multiplication of multiparty commitments based on a lightweight preprocessing approach. Finally we show how to use the fully homomorphic commitments to compute any functionality securely in the presence of a malicious adversary corrupting any number of parties.
The N sets of parties which are allowed by unconditionally the secure multiparty computation (MPC) for computing securely with a registered function f with the help of unbounded adversary computational at some specified field. Here one can corrupt t among n parties maliciously corrupt. The Protocols of MPC which are known and efficient are developed for online or offline framework. Coming to the offline process, the private & random multiplication-triples which is sharable can be generated by the parties in this framework. Later on, these are useful for online to evaluate the multiplication of gates securely in a circuit which describes as f. In this, Protocols of the MPC efficiency depends on the how the offline implementation efficiently. Here, we proposed a simple method, for shared & private multiplication-triples which are random in nature generation without any conditions securely & safely. The typical protocols face this issue, when the random values of shared pairs produced initially. And also, in computing the product values which is shared for every pair. After that, protocols of multiplication and values which are considered as communication intensive. In proposed scheme, the multiplication protocols are completely used in different manner. Later on, we observe that the share multiplication-triples verification by parties or they are extracted securely or not. With the use of setting of the hybrid network and asynchronous, linear communication MPC protocols used which are multiplication gate overhead & indicates as f. The above are the improvements on the typical MPC protocols with the help of hybrid networking setting, asynchronous and complexity of the communication, if we give to result of synchronous setting in our system. It results efficient MPC protocols which are rounded.
We construct a multiparty computation (MPC) protocol that is secure even if a malicious adversary, in addition to corrupting 1-ε fraction of all parties for an arbitrarily small constant ε >0, can leak information about the secret state of each honest party. This leakage can be continuous for an unbounded number of executions of the MPC protocol, computing different functions on the same or different set of inputs. We assume a (necessary) "leak-free" preprocessing stage. We emphasize that we achieve leakage resilience without weakening the security guarantee of classical MPC. Namely, an adversary who is given leakage on honest parties' states, is guaranteed to learn nothing beyond the input and output values of corrupted parties. This is in contrast with previous works on leakage in the multi-party protocol setting, which weaken the security notion, and only guarantee that a protocol which leaks l bits about the parties' secret states, yields at most l bits of leakage on the parties' private inputs. For some functions, such as voting, such leakage can be detrimental.
Protocols for secure multi-party computation (MPC) supporting mixed-mode computation have found a lot of applications in recent years due to their flexibility in representing the function to be evaluated. However, existing mixed-mode MPC protocols are only practical for a small number of parties: they are either tailored to the case of two/three parties, or scale poorly for a large number of parties.In this paper, we design and implement a new system for highly efficient and scalable mixed-mode MPC tolerating an arbitrary number of semi-honest corruptions. Our protocols allow secret data to be represented in Encrypted, Boolean, Arithmetic, or Yao form, and support efficient conversions between these representations.1)We design a multi-party table-lookup protocol, where both the index and the table can be kept private. The protocol is scalable even with hundreds of parties.2)Using the above protocol, we design efficient conversions between additive arithmetic secret sharings and Boolean secret sharings for a large number of parties. For 32 parties, our conversion protocols require 1184× to 8141× less communication compared to the state-of-the-art protocols MOTION and MP-SPDZ; this leads to up to 1275× improvement in running time under 1 Gbps network. The improvements are even larger with more parties.3)We also use new protocols to design an efficient multi-party distributed garbling protocol. The protocol could achieve asymptotically constant communication per party.Our implementation will be made public.