Revisiting the Efficiency of Asynchronous MPC with Optimal Resilience Against General Adversaries

In this paper, we design unconditionally secure multi-party computation (MPC) protocols in the asynchronous communication setting with optimal resilience. Our protocols are secure against a computationally unbounded malicious adversary characterized by an adversary structure \(\mathcal {Z}\), which enumerates all possible subsets of potentially corrupt parties. We present protocols with both perfect-security, as well as with statistical-security. While the protocols in the former class achieve all the security properties in an error-free fashion, the protocols belonging to the latter category achieve all the security properties except with a negligible error. Our perfectly secure protocol incurs an amortized communication of \(\mathcal {O}(|\mathcal {Z}|^2)\) bits per multiplication. This improves upon the protocol of Choudhury and Pappu (INDOCRYPT 2020) with the least known amortized communication complexity of \(\mathcal {O}(|\mathcal {Z}|^3)\) bits per multiplication. On the other hand, our statistically secure protocol incurs an amortized communication of \(\mathcal {O}(|\mathcal {Z}|)\) bits per multiplication. This is the first statistically secure asynchronous MPC protocol against general adversaries. Previously, perfectly secure and statistically secure MPC with an amortized communication cost of \(\mathcal {O}(|\mathcal {Z}|^2)\) and \(\mathcal {O}(|\mathcal {Z}|)\) bits, respectively, per multiplication was known only in the relatively simpler synchronous communication setting (Hirt and Tschudi in ASIACRYPT, Springer, 2013).

1. A secret-sharing scheme is called linear if the shares are computed as a linear function of the secret and the underlying randomness used in the scheme.

2. The complexity is derived by substituting the broadcasts done in their protocol through the reliable broadcast protocol of [18], as referred in [24].

3. We stress that even though we prove the security of our protocols in the model proposed in [14], the proofs can be easily reworked to fit in the actual UC model proposed in [15].

4. In [15], the order of activation is maintained and tracked in the protocols and proofs. However, doing so in the context of our protocols will make the proofs hard to read and understand and so we avoid doing that. However, we confirm that this will not violate the correctness of our UC claims and their proofs.

5. In [15], while describing their protocols, the authors have used this functionality to capture the point-to-point communication between the parties. However, this brings in a lot of additional technicalities and notations. In the context of our protocols, sending every message through the asynchronous message-transmission functionality will make the protocols harder to read and understand. Hence, as done in [14], we will avoid communicating the messages in the protocol through the ideal asynchronous message-transmission functionality. However, we confirm that this will not violate the overall UC-security of our protocols.

6. In the latter case, we cannot let the functionality pick random shares on behalf of \(P_\textsf{D}\)’s input. This is because in the real-world VSS protocol, a corrupt \(P_\textsf{D}\) may not select random shares for secret-sharing its input.

7. Recall that M is the number of multiplication gates in the circuit \(\textsf{ckt}\).

8. This provision is made because in our pre-processing phase protocol, the real-world adversary will have full control over the shares of the corrupt parties corresponding to the random multiplication-triples generated in the protocol.

9. Checking for the existence of such a \(\mathcal {C}\) can be always performed with \(\mathcal {O}(\text{ poly }(n, |\mathcal {Z}|))\) computational effort.

10. The reason for two different discarded sets is that the various instances of cheater-identification corresponding to the failed \(\Pi _\textsf{MultCI}\) instances are executed asynchronously thus resulting in a corrupt party to be identified by different honest parties during different iterations.

11. Recall that we are assuming that no honest party is ever included in the set \(\mathcal{G}\mathcal{D}\) and all honest parties are eventually removed from the \( \mathcal {W}^{(i)}_{\textsf{iter}'}, \mathcal{L}\mathcal{D}^{(i)}_{\textsf{iter}'}\) sets of every honest \(P_i\) for every \(\textsf{iter}' < \textsf{iter}\).

12. If there are multiple parties \(P_j\) satisfying this condition, then we consider the \(P_j\) with the smallest index.

13. If there are multiple parties \(P_j\) satisfying this condition, then we consider the \(P_j\) with the smallest index.

14. If there are multiple conflicting-pairs, then we consider the one having parties with the smallest indices.

15. Recall that in the protocol, ACS is executed after every block of \(tn + 1\) failed iterations and \(\mathcal{G}\mathcal{D}\) gets updated through ACS. In the context of the given scenario, the parties would have run ACS after iteration numbers \(tn + 1, 2(tn + 1), \ldots , (k' - 1)(tn + 1)\) and \(k'(tn + 1)\) to update the set \(\mathcal{G}\mathcal{D}\). The set \(\mathcal{G}\mathcal{D}_{k'}\) denotes the updated \(\mathcal{G}\mathcal{D}\) set after the ACS instance number \(k'\).

16. This dummy point serves as an indicator for the receiver that \(P_i\) is in conflict with \(P_j\).

17. Recall that in the original \(\Pi _\textsf{SVSS}\) protocol, apart from checking the pairwise consistency of the signed \(s_{qj}\) and \(s_{qi}\), party does not check for anything additional, for broadcasting the \(\textsf{OK}_q(i, j)\) message. Specifically, if \(P_i, P_j \in S_q\), then while receiving the signatures \(\textsf{ICSig}(\textsf{sid}^{(P_\textsf{D},q)}_{j, i, \star }, P_j, P_i, \star , s_{qj})\) from \(P_j\), party \(P_i\) as an intermediary, does not care whether \(P_j\) as a signer has broadcasted \(\textsf{OK}\) or \(\textsf{NOK}\) during the underlying \(\Pi _\textsf{Auth}\) instances. But now in the modified protocol, along with \(S_q\), for every other subset \(S_{q'} \in \mathbb {S}\) where \(P_j, P_i \in S_{q'}\), in all the instances of \(\Pi _\textsf{Auth}\) involving \(P_j\) as the signer and \(P_i\) as the intermediary, \(P_i\) checks whether \(P_j\) has issued the required signatures to \(P_i\) and that too, by broadcasting \(\textsf{OK}\) messages in the underlying \(\Pi _\textsf{Auth}\) instances, while giving signatures to \(P_i\).

18. This is because there may not be any honest party in the set \((S_p \cap S_q) {\setminus } Z\), possessing the shares \([a]_p\) as well as \([b]_q\), who can secret-share the summand \([a]_p[b]_q\), since we are now working with the \(\mathbb {Q}^{(3)}(\mathcal {P}, \mathcal {Z})\) condition.

19. Recall that the ABA protocols of [12], as well as [11], are almost-surely terminating, where \(\mathcal {Z}\) satisfies the \(\mathbb {Q}^{(4)}(\mathcal {P}, \mathcal {Z})\) and \(\mathbb {Q}^{(3)}(\mathcal {P}, \mathcal {Z})\) condition, respectively. Communication-complexity-wise, the ABA protocol of [12] is more efficient, compared to [11].

We would like to sincerely thank the anonymous referees for their insightful remarks and feedback, which helped us to significantly improve the overall paper.

Authors and Affiliations

1. SAP Labs, Bangalore, India

   Ananya Appan

2. Department of Computer Science, Bar Ilan University, Ramat Gan, Israel

   Anirudh Chandramouli

3. International Institute of Information Technology, Bangalore, India

   Ashish Choudhury

Corresponding author

Correspondence to Ashish Choudhury.

Communicated by Paulo L. Barreto.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

A preliminary version of this article is published as an extended abstract at INDOCRYPT 2022; this is the full and elaborate version with full security proofs, along with the results for statistically secure MPC. Ananya Appan: The work was done as a student at the International Institute of Information Technology, Bangalore. Anirudh Chandramouli: The work was done as a student at the International Institute of Information Technology, Bangalore, Ashish Choudhury: This research is an outcome of the R &D work undertaken in the project under the Visvesvaraya PhD Scheme of Ministry of Electronics and Information Technology, Government of India, being implemented by Digital India Corporation (formerly Media Lab Asia). The author is also thankful to the Electronics, IT and BT Government of Karnataka for supporting this work under the CIET project.

This paper was reviewed by Carsten Baum and Marcos Antonio Simplicio Jr.

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions