ACM Symposium on Principles of Distributed Computing (PODC)

On the theoretical gap between synchronous and asynchronous MPC protocols

Zuzana Beerliová-Trubíniová, Martin Hirt, Jesper Buus Nielsen

Published Jul 25, 2010• 21 citations

Publisher

Abstract

Multiparty computation (MPC) protocols among n parties secure against t active faults are known to exist if and only if

DOI: 10.1145/1835698.1835746

Related papers

Perfectly-secure Network-agnostic MPC with Optimal Resiliency

Shravani Mahesh Patil, Arpita Patra

We study network-agnostic secure multiparty computation with perfect security. Traditionally MPC is studied assuming the underlying network is either synchronous or asynchronous. In a network-agnostic setting, the parties are unaware of whether the underlying network is synchronous or asynchronous.

ACM Symposium on Principles of Distributed Computing (PODC)Jun 13, 20254 citations

Unconditionally Secure Asynchronous Multiparty Computation with Linear Communication Complexity

Ashish Choudhury, Martin Hirt, Arpita Patra

Jan 17, 20132 citations

Is It Even Possible? On the Parallel Composition of Asynchronous MPC Protocols

Ran Cohen, Pouyan Forghani, Juan A. Garay +2 more

Lecture notes in computer scienceDec 1, 20250 citations

On Communication-Efficient Asynchronous MPC with Adaptive Security

Annick Chopard, Martin Hirt, Chen-Da Liu-Zhang

Lecture notes in computer scienceJan 1, 202122 citations

Network Agnostic Perfectly Secure Multiparty Computation Against General Adversaries

Ananya Appan, Anirudh Chandramouli, Ashish Choudhury

IEEE Transactions on Information TheorySep 30, 20241 citation

Secure multiparty computation

Yehuda Lindell

MPC has moved from theoretical study to real-world usage. How is it doing?

Communications of the ACMDec 17, 2020327 citations

ACM Symposium on Principles of Distributed Computing (PODC)

On the theoretical gap between synchronous and asynchronous MPC protocols

Zuzana Beerliová-Trubíniová, Martin Hirt, Jesper Buus Nielsen

Published Jul 25, 2010• 21 citations

Publisher

Abstract

Multiparty computation (MPC) protocols among n parties secure against t active faults are known to exist if and only if

DOI: 10.1145/1835698.1835746

Related papers

Perfectly-secure Network-agnostic MPC with Optimal Resiliency

Shravani Mahesh Patil, Arpita Patra

ACM Symposium on Principles of Distributed Computing (PODC)Jun 13, 20254 citations

Unconditionally Secure Asynchronous Multiparty Computation with Linear Communication Complexity

Ashish Choudhury, Martin Hirt, Arpita Patra

Unconditionally secure multiparty computation (MPC) allows a set of n mutually distrusting parties to securely compute an agreed function f over some finite field in the presence of a computationally unbounded adversary, who can actively corrupt any t out of the n parties. Designing an asynchronous MPC (AMPC) protocol with a communication complexity of O(n) field elements per multiplication gate is a long standing open problem. We solve the open problem by presenting two AMPC protocols with the corruption threshold t < n/4. Our first protocol is statistically secure (i.e. involves a negligible error in the protocol outcome) in a completely asynchronous setting and improves the communication complexity of the previous best AMPC protocol in the same setting by a factor of Θ(n). Our second protocol is perfectly secure (i.e. error free) in a hybrid setting, where one round of communication is assumed to be synchronous and improves the communication complexity of the previous best AMPC protocol in the hybrid setting by a factor of Θ(n 2). Starting with the seminal work of Beaver (CRYPTO 1991), it is by now a well-known technique to evaluate multiplication gates in an MPC protocol using shared random multiplication triples. The central contribution common to both the presented protocols is a new and simple framework for generating shared random multiplication triples. All the existing protocols approach the problem by first producing shared pairs of random values, followed by computingUnconditionally secure multiparty computation (MPC) allows a set of n mutually distrusting parties to securely compute an agreed function f over some finite field in the presence of a computationally unbounded adversary, who can actively corrupt any t out of the n parties. Designing an asynchronous MPC (AMPC) protocol with a communication complexity of O(n) field elements per multiplication gate is a long standing open problem. We solve the open problem by presenting two AMPC protocols with the corruption threshold t < n/4. Our first protocol is statistically secure (i.e. involves a negligible error in the protocol outcome) in a completely asynchronous setting and improves the communication complexity of the previous best AMPC protocol in the same setting by a factor of Θ(n). Our second protocol is perfectly secure (i.e. error free) in a hybrid setting, where one round of communication is assumed to be synchronous and improves the communication complexity of the previous best AMPC protocol in the hybrid setting by a factor of Θ(n 2). Starting with the seminal work of Beaver (CRYPTO 1991), it is by now a well-known technique to evaluate multiplication gates in an MPC protocol using shared random multiplication triples. The central contribution common to both the presented protocols is a new and simple framework for generating shared random multiplication triples. All the existing protocols approach the problem by first producing shared pairs of random values, followed by computing

Jan 17, 20132 citations

Is It Even Possible? On the Parallel Composition of Asynchronous MPC Protocols

Ran Cohen, Pouyan Forghani, Juan A. Garay +2 more

Lecture notes in computer scienceDec 1, 20250 citations

On Communication-Efficient Asynchronous MPC with Adaptive Security

Annick Chopard, Martin Hirt, Chen-Da Liu-Zhang

Lecture notes in computer scienceJan 1, 202122 citations

Network Agnostic Perfectly Secure Multiparty Computation Against General Adversaries

Ananya Appan, Anirudh Chandramouli, Ashish Choudhury

In this work, we initiate the study of network-agnostic perfectly-secure multi-party computation (MPC) against general (non-threshold) adversaries, where the corruption capacity of the adversary is specified through an adversary structure, which is a set of potentially corrupt subsets of parties. Known MPC protocols are designed either assuming a synchronous network where every sent message is guaranteed to be delivered within some known time or assuming an asynchronous network where no timing assumptions are made and every sent message is eventually delivered. Perfectly-secure MPC protocols in the synchronous network can be designed as long as the underlying adversary structure satisfies the$ {{\mathcal {Q}}}^{(3)} $condition, meaning that the union of no three subsets from the adversary structure covers the entire set of parties. On the other hand, perfectly-secure MPC protocols in the asynchronous network can be designed only against$ {{\mathcal {Q}}}^{(4)} $adversary structures, meaning that the union of no four subsets from the adversary structure covers the entire set of parties. A natural question is whether a single MPC protocol exists, which remains secure even if the parties are unaware of the network conditions at execution time. That is, if the synchrony is satisfied throughout the protocol execution then the protocol should be secure against any$ {{\mathcal {Q}}}^{(3)} $adversary structure. However, even if any synchrony assumption is violated during the execution, the protocol should still be secure against any$ {{\mathcal {Q}}}^{(4)} $adversary structure. We answer the above question affirmatively. Fix any adversary structure$ {\mathcal {Z}}_{s} $and$ {\mathcal {Z}}_{a} $satisfying$ {{\mathcal {Q}}}^{(3)} $and$ {{\mathcal {Q}}}^{(4)} $conditions respectively, such that$ {\mathcal {Z}}_{a} \subset {\mathcal {Z}} _{s} $. We show the existence of a network-agnostic perfectly-secure MPC protocol tolerating$ {\mathcal {Z}}_{s} $and$ {\mathcal {Z}}_{a} $in synchronous and asynchronous networks respectively as long as the$ {{\mathcal {Q}}}^{(3, 1)} $condition is satisfied, meaning that the union of no three subsets from$ {\mathcal {Z}}_{s} $and one subset from$ {\mathcal {Z}}_{a}$covers the entire set of parties. Our result generalizes the result of Appan, Chandramouli and Choudhury (IEEE Transactions on IT, 2023), which presents the only known perfectly-secure network-agnostic MPC protocol against threshold adversaries.In this work, we initiate the study of network-agnostic perfectly-secure multi-party computation (MPC) against general (non-threshold) adversaries, where the corruption capacity of the adversary is specified through an adversary structure, which is a set of potentially corrupt subsets of parties. Known MPC protocols are designed either assuming a synchronous network where every sent message is guaranteed to be delivered within some known time or assuming an asynchronous network where no timing assumptions are made and every sent message is eventually delivered. Perfectly-secure MPC protocols in the synchronous network can be designed as long as the underlying adversary structure satisfies the$ {{\mathcal {Q}}}^{(3)}$condition, meaning that the union of no three subsets from the adversary structure covers the entire set of parties. On the other hand, perfectly-secure MPC protocols in the asynchronous network can be designed only against$ {{\mathcal {Q}}}^{(4)}$adversary structures, meaning that the union of no four subsets from the adversary structure covers the entire set of parties. A natural question is whether a single MPC protocol exists, which remains secure even if the parties are unaware of the network conditions at execution time. That is, if the synchrony is satisfied throughout the protocol execution then the protocol should be secure against any$ {{\mathcal {Q}}}^{(3)}$adversary structure. However, even if any synchrony assumption is violated during the execution, the protocol should still be secure against any$ {{\mathcal {Q}}}^{(4)}$adversary structure. We answer the above question affirmatively. Fix any adversary structure${\mathcal {Z}}_{s}$and${\mathcal {Z}}_{a}$satisfying$ {{\mathcal {Q}}}^{(3)}$and$ {{\mathcal {Q}}}^{(4)}$conditions respectively, such that${\mathcal {Z}}_{a} \subset {\mathcal {Z}} _{s}$. We show the existence of a network-agnostic perfectly-secure MPC protocol tolerating${\mathcal {Z}}_{s}$and${\mathcal {Z}}_{a}$in synchronous and asynchronous networks respectively as long as the$ {{\mathcal {Q}}}^{(3, 1)}$condition is satisfied, meaning that the union of no three subsets from${\mathcal {Z}}_{s}$and one subset from${\mathcal {Z}}_{a}$covers the entire set of parties. Our result generalizes the result of Appan, Chandramouli and Choudhury (IEEE Transactions on IT, 2023), which presents the only known perfectly-secure network-agnostic MPC protocol against threshold adversaries.

IEEE Transactions on Information TheorySep 30, 20241 citation

Secure multiparty computation

Yehuda Lindell

MPC has moved from theoretical study to real-world usage. How is it doing?

Communications of the ACMDec 17, 2020327 citations

condition, meaning that the union of no three subsets from the adversary structure covers the entire set of parties. On the other hand, perfectly-secure MPC protocols in the asynchronous network can be designed only against

{{\mathcal {Q}}}^{(4)}

adversary structures, meaning that the union of no four subsets from the adversary structure covers the entire set of parties. A natural question is whether a single MPC protocol exists, which remains secure even if the parties are unaware of the network conditions at execution time. That is, if the synchrony is satisfied throughout the protocol execution then the protocol should be secure against any

{{\mathcal {Q}}}^{(3)}

adversary structure. However, even if any synchrony assumption is violated during the execution, the protocol should still be secure against any

{{\mathcal {Q}}}^{(4)}

adversary structure. We answer the above question affirmatively. Fix any adversary structure

{\mathcal {Z}}_{s}

and

{\mathcal {Z}}_{a}

satisfying

{{\mathcal {Q}}}^{(3)}

and

{{\mathcal {Q}}}^{(4)}

conditions respectively, such that

{\mathcal {Z}}_{a} \subset {\mathcal {Z}} _{s}

. We show the existence of a network-agnostic perfectly-secure MPC protocol tolerating

{\mathcal {Z}}_{s}

and

{\mathcal {Z}}_{a}

in synchronous and asynchronous networks respectively as long as the

{{\mathcal {Q}}}^{(3, 1)}

condition is satisfied, meaning that the union of no three subsets from

{\mathcal {Z}}_{s}

and one subset from

{\mathcal {Z}}_{a}$covers the entire set of parties. Our result generalizes the result of Appan, Chandramouli and Choudhury (IEEE Transactions on IT, 2023), which presents the only known perfectly-secure network-agnostic MPC protocol against threshold adversaries.