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

IEEE Transactions on Information Theory

An Efficient Framework for Unconditionally Secure Multiparty Computation

Ashish Choudhury, Arpita Patra

Published Oct 4, 2016• 63 citations
Publisher

Abstract

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.

DOI
10.1109/tit.2016.2614685

Related papers

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

Round and Communication Efficient Unconditionally-secure MPC with t < n/3 in Partially Synchronous Network.

Ashish Choudhury, Arpita Patra, Divya Ravi

In this work, we study unconditionally-secure multi-party computation (MPC) tolerating \(t < n/3\) corruptions, where n is the total number of parties involved. In this setting, it is well known that if the underlying network is completely asynchronous, then one can achieve only statistical security; moreover it is impossible to ensure input provision and consider inputs of all the honest parties. The best known statistically-secure asynchronous MPC (AMPC) with \(t<n/3\) requires a communication of \(\varOmega (n^5)\) field elements per multiplication. We consider a partially synchronous setting, where the parties are assumed to be globally synchronized initially for few rounds and then the network becomes completely asynchronous. In such a setting, we present a MPC protocol, which requires \(\mathcal {O}(n^2)\) communication per multiplication while ensuring input provision. Our MPC protocol relies on a new four round, communication efficient statistical verifiable secret-sharing (VSS) protocol with broadcast communication complexity independent of the number of secret-shared values.

•Jan 1, 2017•0 citations

Unconditionally Secure MPC for Boolean Circuits With Constant Online Communication

Zhenkai Hu, Kang Yang, Yu Yu

Through tremendous efforts, the communication cost of secure multi-party computation (MPC) in the honest-majority setting has been significantly improved. In particular, the state-of-the-art honest-majority MPC protocol by Escudero et al. (CCS'22) takes 12 field elements in total per multiplication gate for arithmetic circuits in the online phase. However, it still requires$12 log (5n/4$) bits of online communication per AND gate for Boolean circuits. That is, for Boolean circuits, no MPC protocol with constant online communication is known. In this paper, we present an unconditionally secure MPC protocol for Boolean circuits in the honest-majority setting, which has constant online communication complexity and the offline communication complexity linear to the number$n$of parties. We first describe the semi-honest MPC protocol and then show how to extend it to achieve malicious security, where the maliciously secure protocol has the same communication cost as the semi-honest protocol. In particular, our protocol achieves the amortized communication cost 36 bits per AND gate in the online phase and 30n + 24 bits per AND gate in the offline phase.

IEEE Computer Security Foundations Workshop (CSFW)•Jul 8, 2024•1 citation

Round efficient computationally secure multi-party computation revisited

Laasya Bangalore, Ashish Choudhury, Gayathri Garimella

In this work, we consider the problem of secure multi-party computation (MPC) with n parties where at most t are under the control of a computationally bounded adversary given the constraint t < n/2. We aim to design a round efficient protocol by minimizing the number of rounds in which the broadcast primitive is involved. In this setting, the previous best protocol can be attributed to Katz-Koo (EUROCRYPT 2007) which is set in the offline-online paradigm (where the parties generate preprocessing data during the offline phase to lighten the computation in the online phase). Their online phase is a constant round protocol with no invocations of broadcast, while the offline phase protocol needs total 29 rounds with a broadcast invocation in one round. Our work improves the round complexity of their offline phase protocol, by running in 4 rounds, with only a single broadcast round. Additionally, we also improve the communication complexity of the offline phase protocol by a factor of Ω(n3). As a technical contribution, we present the first two round computationally-secure verifiable secret-sharing (VSS) scheme that invokes broadcast in only one round.

International Conference on Distributed Computing and Networking (ICDCN)•Jan 4, 2019•3 citations

Brief Announcement: Optimally-Resilient Unconditionally-Secure Asynchronous Multi-Party Computation Revisited

Ashish Choudhury

In this paper, we present an optimally-resilient, unconditionally-secure asynchronous multi-party computation (AMPC) protocol for n parties, tolerating a computationally unbounded adversary, capable of corrupting up to t < n/3 parties. Our protocol needs a communication of 𝒪(n⁴) field elements per multiplication gate. This is to be compared with previous best AMPC protocol (Patra et al, ICITS 2009) in the same setting, which needs a communication of 𝒪(n⁵) field elements per multiplication gate. To design our protocol, we present a simple and highly efficient asynchronous verifiable secret-sharing (AVSS) protocol, which is of independent interest.

Leibniz international proceedings in informatics•Jan 1, 2020•0 citations

Two-Thirds Honest-Majority MPC for Malicious Adversaries at Almost the Cost of Semi-Honest

Jun Furukawa, Yehuda Lindell

Secure multiparty computation (MPC) enables a set of parties to securely carry out a joint computation of their private inputs without revealing anything but the output. Protocols for semi-honest adversaries guarantee security as long as the corrupted parties run the specified protocol and ensure that nothing is leaked in the transcript. In contrast, protocols for malicious adversaries guarantee security in the presence of arbitrary adversaries who can run any attack strategy. Security for malicious adversaries is typically what is needed in practice (and is always preferred), but comes at a significant cost. In this paper, we present the first protocol for a two-thirds honest majority that achieves security in the presence of malicious adversariesat essentially the exact same cost as the best known protocols for semi-honest adversaries. Our construction is not a general transformation and thus it is possible that better semi-honest protocols will be constructed which do not support our transformation. Nevertheless, for the current state-of-the-art for many parties (based on Shamir sharing), our protocol invokes the best semi-honest multiplication protocol exactly once per multiplication gate (plus some additional local computation that is negligible to the overall cost). Concretely, the best version of our protocol requires each party to send on average of just 2 2/3 elements per multiplication gate (when the number of multiplication gates is at least the number of parties). This is four times faster than the previous-best protocol of Barak et al. (ACM CCS 2018) for small fields, and twice as fast as the previous-best protocol of Chida et al. (CRYPTO 2018) for large fields.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 6, 2019•34 citations
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.
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.
In this work, we study unconditionally-secure multi-party computation (MPC) tolerating t<n/3t < n/3t<n/3 corruptions, where n is the total number of parties involved. In this setting, it is well known that if the underlying network is completely asynchronous, then one can achieve only statistical security; moreover it is impossible to ensure input provision and consider inputs of all the honest parties. The best known statistically-secure asynchronous MPC (AMPC) with t<n/3t<n/3t<n/3 requires a communication of Ω(n5)\varOmega (n^5)Ω(n5) field elements per multiplication. We consider a partially synchronous setting, where the parties are assumed to be globally synchronized initially for few rounds and then the network becomes completely asynchronous. In such a setting, we present a MPC protocol, which requires O(n2)\mathcal {O}(n^2)O(n2) communication per multiplication while ensuring input provision. Our MPC protocol relies on a new four round, communication efficient statistical verifiable secret-sharing (VSS) protocol with broadcast communication complexity independent of the number of secret-shared values.
Through tremendous efforts, the communication cost of secure multi-party computation (MPC) in the honest-majority setting has been significantly improved. In particular, the state-of-the-art honest-majority MPC protocol by Escudero et al. (CCS'22) takes 12 field elements in total per multiplication gate for arithmetic circuits in the online phase. However, it still requires12log(5n/412 log (5n/412log(5n/4) bits of online communication per AND gate for Boolean circuits. That is, for Boolean circuits, no MPC protocol with constant online communication is known. In this paper, we present an unconditionally secure MPC protocol for Boolean circuits in the honest-majority setting, which has constant online communication complexity and the offline communication complexity linear to the numbernnnof parties. We first describe the semi-honest MPC protocol and then show how to extend it to achieve malicious security, where the maliciously secure protocol has the same communication cost as the semi-honest protocol. In particular, our protocol achieves the amortized communication cost 36 bits per AND gate in the online phase and 30n + 24 bits per AND gate in the offline phase.
In this work, we consider the problem of secure multi-party computation (MPC) with n parties where at most t are under the control of a computationally bounded adversary given the constraint t < n/2. We aim to design a round efficient protocol by minimizing the number of rounds in which the broadcast primitive is involved. In this setting, the previous best protocol can be attributed to Katz-Koo (EUROCRYPT 2007) which is set in the offline-online paradigm (where the parties generate preprocessing data during the offline phase to lighten the computation in the online phase). Their online phase is a constant round protocol with no invocations of broadcast, while the offline phase protocol needs total 29 rounds with a broadcast invocation in one round. Our work improves the round complexity of their offline phase protocol, by running in 4 rounds, with only a single broadcast round. Additionally, we also improve the communication complexity of the offline phase protocol by a factor of Ω(n3). As a technical contribution, we present the first two round computationally-secure verifiable secret-sharing (VSS) scheme that invokes broadcast in only one round.
In this paper, we present an optimally-resilient, unconditionally-secure asynchronous multi-party computation (AMPC) protocol for n parties, tolerating a computationally unbounded adversary, capable of corrupting up to t < n/3 parties. Our protocol needs a communication of 𝒪(n⁴) field elements per multiplication gate. This is to be compared with previous best AMPC protocol (Patra et al, ICITS 2009) in the same setting, which needs a communication of 𝒪(n⁵) field elements per multiplication gate. To design our protocol, we present a simple and highly efficient asynchronous verifiable secret-sharing (AVSS) protocol, which is of independent interest.
Secure multiparty computation (MPC) enables a set of parties to securely carry out a joint computation of their private inputs without revealing anything but the output. Protocols for semi-honest adversaries guarantee security as long as the corrupted parties run the specified protocol and ensure that nothing is leaked in the transcript. In contrast, protocols for malicious adversaries guarantee security in the presence of arbitrary adversaries who can run any attack strategy. Security for malicious adversaries is typically what is needed in practice (and is always preferred), but comes at a significant cost. In this paper, we present the first protocol for a two-thirds honest majority that achieves security in the presence of malicious adversariesat essentially the exact same cost as the best known protocols for semi-honest adversaries. Our construction is not a general transformation and thus it is possible that better semi-honest protocols will be constructed which do not support our transformation. Nevertheless, for the current state-of-the-art for many parties (based on Shamir sharing), our protocol invokes the best semi-honest multiplication protocol exactly once per multiplication gate (plus some additional local computation that is negligible to the overall cost). Concretely, the best version of our protocol requires each party to send on average of just 2 2/3 elements per multiplication gate (when the number of multiplication gates is at least the number of parties). This is four times faster than the previous-best protocol of Barak et al. (ACM CCS 2018) for small fields, and twice as fast as the previous-best protocol of Chida et al. (CRYPTO 2018) for large fields.