Perfectly Secure Fluid MPC with Abort and Linear Communication Complexity

Alexander Bienstock; Daniel Escudero; Antigoni Polychroniadou

doi:10.62056/aesg89n4e

Perfectly Secure Fluid MPC with Abort and Linear Communication Complexity

Authors

Alexander Bienstock, Daniel Escudero, Antigoni Polychroniadou

Alexander Bienstock

J.P. Morgan AI Research & J.P. Morgan AlgoCRYPT CoE, New York, USA
alex dot bienstock at jpmchase dot com

Daniel Escudero

J.P. Morgan AI Research & J.P. Morgan AlgoCRYPT CoE, New York, USA
daniel dot escudero at protonmail dot com

Antigoni Polychroniadou

J.P. Morgan AI Research & J.P. Morgan AlgoCRYPT CoE, New York, USA
antigonipoly at gmail dot com

Abstract

The Fluid multiparty computation (MPC) model, introduced in (Choudhuri et al. CRYPTO 2021), addresses dynamic scenarios where participants can join or leave computations between rounds. Communication complexity initially stood at $\Omega(n^2)$ elements per gate, where $n$ is the number of parties in a committee online at a time. This held for both statistical security (honest majority) and computational security (dishonest majority) in (Choudhuri et al. CRYPTO'21) and (Rachuri and Scholl, CRYPTO'22), respectively. The work of (Bienstock et al. CRYPTO'23) improved communication to $O(n)$ elements per gate. However, it's important to note that the perfectly secure setting with one-third corruptions per committee has only recently been addressed in the work of (David et al. CRYPTO'23). Notably, their contribution marked a significant advancement in the Fluid MPC literature by introducing guaranteed output delivery. However, this achievement comes at the cost of prohibitively expensive communication, which scales to $\Omega(n^9)$ elements per gate.

In this work, we study the realm of perfectly secure Fluid MPC under one-third active corruptions. Our primary focus lies in proposing efficient protocols that embrace the concept of security with abort. Towards this, we design a protocol for perfectly secure Fluid MPC that requires only linear communication of $O(n)$ elements per gate, matching the communication of the non-Fluid setting. Our results show that, as in the case of computational and statistical security, perfect security with abort for Fluid MPC comes “for free” (asymptotically linear in $n$) with respect to traditional non-Fluid MPC, marking a substantial leap forward in large scale dynamic computations, such as Fluid MPC.

References

[AAPP23]

Ittai Abraham, Gilad Asharov, Shravani Patil, and Arpita Patra. Detect, pack and batch: perfectly-secure mpc with linear communication and constant expected time. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 251–281. 2023. Springer. DOI: 10.1007/978-3-031-30617-4_9

Google Scholar ePrint

[AAY21]

Ittai Abraham, Gilad Asharov, and Avishay Yanai. Efficient perfectly secure computation with optimal resilience. In Theory of Cryptography: 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8–11, 2021, Proceedings, Part II 19, pages 66–96. 2021. Springer. DOI: 10.1007/978-3-030-90453-1_3

Google Scholar ePrint

[BBG⁺20]

James Henry Bell, Adrià Bonawitz Kallista A and Gascón, Tancrède Lepoint, and Mariana Raykova. Secure single-server aggregation with (poly) logarithmic overhead. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 1253–1269. 2020. DOI: 10.1145/3372297.3417885

Google Scholar ePrint

[Bea92]

Donald Beaver. Efficient Multiparty Protocols Using Circuit Randomization. In Joan Feigenbaum, editor, Advances in Cryptology – CRYPTO'91, volume 576 of Lecture Notes in Computer Science, pages 420–432, Santa Barbara, CA, USA. August 11–15, 1992. Springer, Berlin, Heidelberg, Germany. DOI: 10.1007/3-540-46766-1_34

Google Scholar ePrint

[BEP23]

Alexander Bienstock, Daniel Escudero, and Antigoni Polychroniadou. On Linear Communication Complexity for (Maximally) Fluid MPC. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology – CRYPTO 2023, pages 263–294, Cham. 2023. Springer Nature Switzerland. DOI: 10.1007/978-3-031-38557-5_9

Google Scholar ePrint

[BH08]

Zuzana Beerliová-Trubíniová and Martin Hirt. Perfectly-Secure MPC with Linear Communication Complexity. In Ran Canetti, editor, Theory of Cryptography, pages 213–230, Berlin, Heidelberg. 2008. Springer Berlin Heidelberg. DOI: 10.5555/1802614.1802632

Google Scholar ePrint

[BIK⁺17]

Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical Secure Aggregation for Privacy-Preserving Machine Learning. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30 - November 03, 2017, pages 1175–1191. 2017. ACM. DOI: 10.1145/3133956.3133982

Google Scholar ePrint

[BJMS20]

Saikrishna Badrinarayanan, Aayush Jain, Nathan Manohar, and Amit Sahai. Secure MPC: laziness leads to GOD. In International Conference on the Theory and Application of Cryptology and Information Security, pages 120–150. 2020. Springer. DOI: 10.1007/978-3-030-64840-4_5

Google Scholar ePrint

[Can01]

Ran Canetti. Universally Composable Security: A New Paradigm for Cryptographic Protocols. In FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 136–145. 2001. IEEE Computer Society. DOI: 10.1145/3402457

Google Scholar ePrint

[CGG⁺21]

Arka Rai Choudhuri, Aarushi Goel, Matthew Green, Abhishek Jain, and Gabriel Kaptchuk. Fluid MPC: secure multiparty computation with dynamic participants. In Annual International Cryptology Conference, pages 94–123. 2021. Springer. DOI: 10.1007/978-3-030-84245-1_4

Google Scholar ePrint

[DDG⁺23]

Bernardo David, Giovanni Deligios, Aarushi Goel, Yuval Ishai, Anders Konring, Eyal Kushilevitz, Chen-Da Liu-Zhang, and Varun Narayanan. Perfect mpc over layered graphs. In Annual International Cryptology Conference, pages 360–392. 2023. Springer. DOI: 10.1007/978-3-031-38557-5_12

Google Scholar ePrint

[DEP21]

Ivan Damgård, Daniel Escudero, and Antigoni Polychroniadou. Phoenix: Secure Computation in an Unstable Network with Dropouts and Comebacks. 2021.

Google Scholar ePrint

[DIK10]

Ivan Damgård, Yuval Ishai, and Mikkel Krøigaard. Perfectly Secure Multiparty Computation and the Computational Overhead of Cryptography. In Henri Gilbert, editor, Advances in Cryptology – EUROCRYPT 2010, pages 445–465, Berlin, Heidelberg. 2010. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-13190-5_23

Google Scholar ePrint

[DN07]

Ivan Damgård and Jesper Buus Nielsen. Scalable and unconditionally secure multiparty computation. In Annual International Cryptology Conference, pages 572–590. 2007. Springer. DOI: 10.5555/1777777.1777823

Google Scholar ePrint

[DPSZ12]

Ivan Damgård, Valerio Pastro, Nigel P. Smart, and Sarah Zakarias. Multiparty Computation from Somewhat Homomorphic Encryption. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings, volume 7417 of Lecture Notes in Computer Science, pages 643–662. 2012. Springer. DOI: 10.1007/978-3-642-32009-5_38

Google Scholar ePrint

[FHM98]

Matthias Fitzi, Martin Hirt, and Ueli Maurer. Trading correctness for privacy in unconditional multi-party computation. In Annual International Cryptology Conference, pages 121–136. 1998. Springer. DOI: 10.5555/646763.706313

Google Scholar ePrint

[FY92]

Matthew Franklin and Moti Yung. Communication complexity of secure computation (extended abstract). In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, pages 699–710. 1992. Association for Computing Machinery. DOI: 10.1145/129712.129780

Google Scholar ePrint

[GHK⁺21]

Craig Gentry, Shai Halevi, Hugo Krawczyk, Bernardo Magri, Jesper Buus Nielsen, Tal Rabin, and Sophia Yakoubov. YOSO: you only speak once. In Annual International Cryptology Conference, pages 64–93. 2021. Springer. DOI: 10.1007/978-3-030-84245-1_3

Google Scholar ePrint

[GLS19]

Vipul Goyal, Yanyi Liu, and Yifan Song. Communication-efficient unconditional MPC with guaranteed output delivery. In Annual International Cryptology Conference, pages 85–114. 2019. Springer. DOI: 10.1007/978-3-030-26951-7_4

Google Scholar ePrint

[GPS19]

Yue Guo, Rafael Pass, and Elaine Shi. Synchronous, with a Chance of Partition Tolerance. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part I, volume 11692 of Lecture Notes in Computer Science, pages 499–529. 2019. Springer. DOI: 10.1007/978-3-030-26948-7_18

Google Scholar ePrint

[GSZ20]

Vipul Goyal, Yifan Song, and Chenzhi Zhu. Guaranteed output delivery comes free in honest majority MPC. In Annual International Cryptology Conference, pages 618–646. 2020. Springer. DOI: 10.1007/978-3-030-56880-1_22

Google Scholar ePrint

[MWA⁺23]

Yiping Ma, Jess Woods, Sebastian Angel, Antigoni Polychroniadou, and Tal Rabin. Flamingo: Multi-Round Single-Server Secure Aggregation with Applications to Private Federated Learning. In 44th IEEE Symposium on Security and Privacy, SP 2023, San Francisco, CA, USA, May 21-25, 2023, pages 477–496. 2023. IEEE. DOI: 10.1109/SP46215.2023.10179434

Google Scholar ePrint

[RS22]

Rahul Rachuri and Peter Scholl. Le Mans: Dynamic and Fluid MPC for Dishonest Majority. In Annual International Cryptology Conference. 2022. DOI: 10.1007/978-3-031-15802-5_25

Google Scholar ePrint

[WOG88]

Avi Wigderson, MB Or, and S Goldwasser. Completeness theorems for noncryptographic fault-tolerant distributed computations. In Proceedings of the 20th Annual Symposium on the Theory of Computing (STOC’88), pages 1–10. 1988. DOI: 10.1145/62212.62213

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/aesg89n4e

History

Submitted: 2024-10-08
Accepted: 2024-12-03
Published: 2025-01-13

How to cite

Alexander Bienstock, Daniel Escudero, and Antigoni Polychroniadou, Perfectly Secure Fluid MPC with Abort and Linear Communication Complexity. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/aesg89n4e.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-4-28,
    author = "Bienstock, Alexander and Escudero, Daniel and Polychroniadou, Antigoni",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Perfectly Secure Fluid {MPC} with Abort and Linear Communication Complexity",
    volume = "1",
    number = "4",
    date = "2025-01-13",
    year = "2025",
    issn = "3006-5496",
    doi = "10.62056/aesg89n4e"
}

TY - JOUR
AU - Bienstock, Alexander
AU - Escudero, Daniel
AU - Polychroniadou, Antigoni
PY  - 2025
TI  - Perfectly Secure Fluid MPC with Abort and Linear Communication Complexity
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 4
DO  - 10.62056/aesg89n4e
UR  - https://doi.org/10.62056/aesg89n4e
AB  - <p>The Fluid multiparty computation (MPC) model, introduced in (Choudhuri et al. CRYPTO 2021), addresses dynamic scenarios where participants can join or leave computations between rounds. Communication complexity initially stood at $\Omega(n^2)$ elements per gate, where $n$ is the number of parties in a committee online at a time. This held for both statistical security (honest majority) and computational security (dishonest majority) in (Choudhuri et al. CRYPTO'21) and (Rachuri and Scholl, CRYPTO'22), respectively. The work of (Bienstock et al. CRYPTO'23) improved communication to $O(n)$ elements per gate. However, it's important to note that the perfectly secure setting with one-third corruptions per committee has only recently been addressed in the work of (David et al. CRYPTO'23). Notably, their contribution marked a significant advancement in the Fluid MPC literature by introducing guaranteed output delivery. However, this achievement comes at the cost of prohibitively expensive communication, which scales to $\Omega(n^9)$ elements per gate.</p><p>    In this work, we study the realm of perfectly secure Fluid MPC under one-third active corruptions. Our primary focus lies in proposing efficient protocols that embrace the concept of security with abort. Towards this, we design a protocol for perfectly secure Fluid MPC that requires only linear communication of $O(n)$ elements per gate, matching the communication of the non-Fluid setting. Our results show that, as in the case of computational and statistical security, perfect security with abort for Fluid MPC comes “for free” (asymptotically linear in $n$) with respect to traditional non-Fluid MPC, marking a substantial leap forward in large scale dynamic computations, such as Fluid MPC. </p>
ER  -

Alexander Bienstock, Daniel Escudero, and Antigoni Polychroniadou, Perfectly Secure Fluid MPC with Abort and Linear Communication Complexity. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/aesg89n4e.