SpringerLink
Log in

Fluid MPC: Secure Multiparty Computation with Dynamic Participants

  • Conference paper
  • First Online:
Advances in Cryptology – CRYPTO 2021 (CRYPTO 2021)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 12826))

Included in the following conference series:

Abstract

Existing approaches to secure multiparty computation (MPC) require all participants to commit to the entire duration of the protocol. As interest in MPC continues to grow, it is inevitable that there will be a desire to use it to evaluate increasingly complex functionalities, resulting in computations spanning several hours or days.

Such scenarios call for a dynamic participation model for MPC where participants have the flexibility to go offline as needed and (re)join when they have available computational resources. Such a model would also democratize access to privacy-preserving computation by facilitating an “MPC-as-a-service” paradigm—the deployment of MPC in volunteer-operated networks (such as blockchains, where dynamism is inherent) that perform computation on behalf of clients.

In this work, we initiate the study of fluid MPC, where parties can dynamically join and leave the computation. The minimum commitment required from each participant is referred to as fluidity, measured in the number of rounds of communication that it must stay online. Our contributions are threefold:

  • We provide a formal treatment of fluid MPC, exploring various possible modeling choices.

  • We construct information-theoretic fluid MPC protocols in the honest-majority setting. Our protocols achieve maximal fluidity, meaning that a party can exit the computation after receiving and sending messages in one round.

  • We implement our protocol and test it in multiple network settings.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (France)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 96.29
Price includes VAT (France)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 126.59
Price includes VAT (France)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    It was observed in [26] that almost all known secret sharing based semi-honest protocols in the static model naturally satisfy this weak privacy property. We observe that the fluid version of BGW continues to satisfy this property. Further, we conjecture that most secret-sharing based approaches in the fluid MPC setting would also yield semi-honest protocols that achieve this property.

  2. 2.

    In the static setting, this technique allows for batched randomness generation, by generating O(n) sharings with \(O(n^2)\) messages. In the fluid MPC setting, however, the number of servers cannot be known in advance and may not correspond to the width of the circuit. Therefore, such amortization techniques are not applicable.

  3. 3.

    We would like to point out that if one were to implement point-to-point channels via a PKI, this equivalence may not hold.

References

  1. Araki, T., et al.: Optimized honest-majority MPC for malicious adversaries - breaking the 1 billion-gate per second barrier. In: 2017 IEEE Symposium on Security and Privacy, San Jose, CA, USA, 22–26 May 2017, pp. 843–862. IEEE Computer Society Press (2017)

    Google Scholar 

  2. Araki, T., Furukawa, J., Lindell, Y., Nof, A., Ohara, K.: High-throughput semi-honest secure three-party computation with an honest majority. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016, Vienna, Austria, 24–28 October 2016, pp. 805–817. ACM Press (2016)

    Google Scholar 

  3. Barak, A., Hirt, M., Koskas, L., Lindell, Y.: An end-to-end system for large scale P2P MPC-as-a-service and low-bandwidth MPC for weak participants. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, pp. 695–712. ACM, New York (2018). http://doi.acm.org/10.1145/3243734.3243801

  4. Baron, J., El Defrawy, K., Lampkins, J., Ostrovsky, R.: How to withstand mobile virus attacks, revisited. In: Halldórsson, M.M., Dolev, S. (eds.) 33rd ACM PODC, Paris, France, 15–18 July 2014, pp. 293–302. ACM (2014)

    Google Scholar 

  5. Beerliová-Trubíniová, Z., Hirt, M.: Efficient multi-party computation with dispute control. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 305–328. Springer, Heidelberg (2006). https://doi.org/10.1007/11681878_16

    Chapter  Google Scholar 

  6. Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: 20th ACM STOC, Chicago, IL, USA, 2–4 May 1988, pp. 1–10. ACM Press (1988)

    Google Scholar 

  7. Benhamouda, F., et al.: Can a blockchain keep a secret? Cryptology ePrint Archive, Report 2020/464 (2020). https://eprint.iacr.org/2020/464

  8. Bogdanov, D., Kamm, L., Kubo, B., Rebane, R., Sokk, V., Talviste, R.: Students and taxes: a privacy-preserving study using secure computation. Proc. Priv. Enhancing Technol. 2016(3), 117–135 (2016)

    Article  Google Scholar 

  9. Buterin, V., et al.: A next-generation smart contract and decentralized application platform. White Paper 3(37) (2014)

    Google Scholar 

  10. Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols (abstract). In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 462–462. Springer, Heidelberg (1988). https://doi.org/10.1007/3-540-48184-2_43

    Chapter  Google Scholar 

  11. Chen, J., Micali, S.: Algorand: a secure and efficient distributed ledger. Theor. Comput. Sci. 777, 155–183 (2019)

    Article  MathSciNet  Google Scholar 

  12. Chida, K., et al.: Fast large-scale honest-majority MPC for malicious adversaries. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part III. LNCS, vol. 10993, pp. 34–64. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_2

    Chapter  Google Scholar 

  13. Choudhuri, A.R., Goel, A., Green, M., Jain, A., Kaptchuk, G.: Fluid MPC: secure multiparty computation with dynamic participants. Cryptology ePrint Archive, Report 2020/754 (2020). https://eprint.iacr.org/2020/754

  14. Clark, M.R., Hopkinson, K.M.: Transferable multiparty computation with applications to the smart grid. IEEE Trans. Inf. Forensics Secur. 9(9), 1356–1366 (2014)

    Article  Google Scholar 

  15. Cramer, R., Damgård, I., Ishai, Y.: Share conversion, pseudorandom secret-sharing and applications to secure computation. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 342–362. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30576-7_19

    Chapter  Google Scholar 

  16. Cryptobiu: cryptobiu/libscapi, May 2019. https://github.com/cryptobiu/libscapi

  17. Damgård, I., Ishai, Y.: Constant-round multiparty computation using a black-box pseudorandom generator. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 378–394. Springer, Heidelberg (2005). https://doi.org/10.1007/11535218_23

    Chapter  Google Scholar 

  18. Damgård, I., Ishai, Y.: Scalable secure multiparty computation. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 501–520. Springer, Heidelberg (2006). https://doi.org/10.1007/11818175_30

    Chapter  Google Scholar 

  19. Damgård, I., Nielsen, J.B.: Scalable and unconditionally secure multiparty computation. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 572–590. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74143-5_32

    Chapter  Google Scholar 

  20. Damgård, I., Pastro, V., Smart, N., Zakarias, S.: Multiparty computation from somewhat homomorphic encryption. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 643–662. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_38

    Chapter  Google Scholar 

  21. Dingledine, R., Mathewson, N., Syverson, P.: Tor: the second-generation onion router. In: Proceedings of the 13th Conference on USENIX Security Symposium, SSYM 2004, vol. 13, pp. 21–21. USENIX Association, Berkeley (2004). http://dl.acm.org/citation.cfm?id=1251375.1251396

  22. Eldefrawy, K., Ostrovsky, R., Park, S., Yung, M.: Proactive secure multiparty computation with a dishonest majority. In: Catalano, D., De Prisco, R. (eds.) SCN 2018. LNCS, vol. 11035, pp. 200–215. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98113-0_11

    Chapter  Google Scholar 

  23. Furukawa, J., Lindell, Y.: Two-thirds honest-majority MPC for malicious adversaries at almost the cost of semi-honest. In: Cavallaro, L., Kinder, J., Wang, X., Katz, J. (eds.) ACM CCS 2019, 11–15 November 2019, pp. 1557–1571. ACM Press (2019)

    Google Scholar 

  24. Garay, J., Kiayias, A., Leonardos, N.: The bitcoin backbone protocol: analysis and applications. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part II. LNCS, vol. 9057, pp. 281–310. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_10

    Chapter  Google Scholar 

  25. Genkin, D., Ishai, Y., Polychroniadou, A.: Efficient multi-party computation: from passive to active security via secure SIMD circuits. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015, Part II. LNCS, vol. 9216, pp. 721–741. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_35

    Chapter  Google Scholar 

  26. Genkin, D., Ishai, Y., Prabhakaran, M., Sahai, A., Tromer, E.: Circuits resilient to additive attacks with applications to secure computation. In: Shmoys, D.B. (ed.) 46th ACM STOC, New York, NY, USA, 31 May–3 June 2014, pp. 495–504. ACM Press (2014)

    Google Scholar 

  27. Genkin, D., Ishai, Y., Weiss, M.: Binary AMD circuits from secure multiparty computation. In: Hirt, M., Smith, A. (eds.) TCC 2016, Part I. LNCS, vol. 9985, pp. 336–366. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53641-4_14

    Chapter  Google Scholar 

  28. Gennaro, R., Rabin, M.O., Rabin, T.: Simplified VSS and fast-track multiparty computations with applications to threshold cryptography. In: Coan, B.A., Afek, Y. (eds.) 17th ACM PODC, Puerto Vallarta, Mexico, 28 June–2 July 1998, pp. 101–111. ACM (1998)

    Google Scholar 

  29. Gentry, C., Halevi, S., Magri, B., Nielsen, J.B., Yakoubov, S.: Random-index PIR and applications. Cryptology ePrint Archive, Report 2020/1248 (2020). https://eprint.iacr.org/2020/1248

  30. Gilad, Y., Hemo, R., Micali, S., Vlachos, G., Zeldovich, N.: Algorand: scaling byzantine agreements for cryptocurrencies. In: Proceedings of the 26th Symposium on Operating Systems Principles, Shanghai, China, 28–31 October 2017, pp. 51–68 (2017)

    Google Scholar 

  31. Gilad, Y., Hemo, R., Micali, S., Vlachos, G., Zeldovich, N.: Algorand: scaling byzantine agreements for cryptocurrencies. Cryptology ePrint Archive, Report 2017/454 (2017). http://eprint.iacr.org/2017/454

  32. Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: Aho, A. (ed.) 19th ACM STOC, New York City, NY, USA, 25–27 May 1987, pp. 218–229. ACM Press (1987)

    Google Scholar 

  33. Goyal, V., Kothapalli, A., Masserova, E., Parno, B., Song, Y.: Storing and retrieving secrets on a blockchain. Cryptology ePrint Archive, Report 2020/504 (2020). https://eprint.iacr.org/2020/504

  34. Goyal, V., Song, Y., Zhu, C.: Guaranteed output delivery comes free in honest majority MPC. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020, Part II. LNCS, vol. 12171, pp. 618–646. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_22

    Chapter  Google Scholar 

  35. Herzberg, A., Jarecki, S., Krawczyk, H., Yung, M.: Proactive secret sharing or: how to cope with perpetual leakage. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 339–352. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-44750-4_27

    Chapter  Google Scholar 

  36. Ikarashi, D., Kikuchi, R., Hamada, K., Chida, K.: Actively private and correct MPC scheme in \(t < n/2\) from passively secure schemes with small overhead. Cryptology ePrint Archive, Report 2014/304 (2014). http://eprint.iacr.org/2014/304

  37. Lapets, A., Volgushev, N., Bestavros, A., Jansen, F., Varia, M.: Secure MPC for analytics as a web application. In: 2016 IEEE Cybersecurity Development (SecDev), pp. 73–74. IEEE (2016)

    Google Scholar 

  38. Lindell, Y., Nof, A.: A framework for constructing fast MPC over arithmetic circuits with malicious adversaries and an honest-majority. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017, Dallas, TX, USA, 31 October–2 November 2017, pp. 259–276. ACM Press (2017)

    Google Scholar 

  39. Maram, S.K.D., et al.: CHURP: dynamic-committee proactive secret sharing. In: ACM Conference on Computer and Communications Security, pp. 2369–2386. ACM (2019)

    Google Scholar 

  40. Micali, S.: Very simple and efficient byzantine agreement. In: Papadimitriou, C.H. (ed.) ITCS 2017, Berkeley, CA, USA, 9–11 January 2017, vol. 4266, pp. 6:1–6:1. LIPIcs (2017)

    Google Scholar 

  41. Mohassel, P., Rosulek, M., Zhang, Y.: Fast and secure three-party computation: the garbled circuit approach. In: Ray, I., Li, N., Kruegel, C. (eds.) ACM CCS 2015, Denver, CO, USA, 12–16 October 2015, pp. 591–602. ACM Press (2015)

    Google Scholar 

  42. Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system, 2008 (2008). http://www.bitcoin.org/bitcoin.pdf

  43. Nordholt, P.S., Veeningen, M.: Minimising communication in honest-majority MPC by batchwise multiplication verification. In: Preneel, B., Vercauteren, F. (eds.) ACNS 2018. LNCS, vol. 10892, pp. 321–339. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93387-0_17

    Chapter  Google Scholar 

  44. Ostrovsky, R., Yung, M.: How to withstand mobile virus attacks (extended abstract). In: Logrippo, L. (ed.) 10th ACM PODC, Montreal, QC, Canada, 19–21 August 1991, pp. 51–59. ACM (1991)

    Google Scholar 

  45. Pass, R., Seeman, L., Shelat, A.: Analysis of the blockchain protocol in asynchronous networks. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part II. LNCS, vol. 10211, pp. 643–673. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_22

    Chapter  MATH  Google Scholar 

  46. Pass, R., Shi, E.: FruitChains: a fair blockchain. In: Schiller, E.M., Schwarzmann, A.A. (eds.) 36th ACM PODC, Washington, DC, USA, 25–27 July 2017, pp. 315–324. ACM (2017)

    Google Scholar 

  47. Wails, R., Johnson, A., Starin, D., Yerukhimovich, A., Gordon, S.D.: Stormy: statistics in tor by measuring securely. In: Cavallaro, L., Kinder, J., Wang, X., Katz, J. (eds.) ACM CCS 2019, 11–15 November 2019, pp. 615–632. ACM Press (2019)

    Google Scholar 

  48. Yao, A.C.C.: How to generate and exchange secrets (extended abstract). In: 27th FOCS, Toronto, Ontario, Canada, 27–29 October 1986, pp. 162–167. IEEE Computer Society Press (1986)

    Google Scholar 

Download references

Acknowledgements

The fourth author would like to thank Amit Sahai and Sunoo Park for insightful discussions on dynamism in MPC. The fifth author would like to thank Shaanan Cohney for early discussions around blockchains and MPC.

Arka Rai Choudhuri, Aarushi Goel and Abhishek Jain were supported in part by DARPA/ARL Safeware Grant W911NF-15-C-0213, NSF CNS-1814919, NSF CAREER 1942789, Samsung Global Research Outreach award and Johns Hopkins University Catalyst award. Arka Rai Choudhuri is also supported by NSF Grants CNS-1908181 and Office of Naval Research Grant N00014-19-1-2294. Matthew Green is supported by NSF under awards CNS-1653110 and CNS-1801479, the Office of Naval Research under contract N00014-19-1-2292, DARPA under Contract No. HR001120C0084, and a Security and Privacy research award from Google. Abhishek Jain was additionally supported in part by an Office of Naval Research grant N00014-19-1-2294. Gabriel Kaptchuk is supported by the National Science Foundation under Grant #2030859 to the Computing Research Association for the CIFellows Project. Significant portions of this work were done while Gabriel Kaptchuk was at Johns Hopkins University and supported by NSF CNS-1329737. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government or DARPA.

Author information

Authors and Affiliations

  1. Johns Hopkins University, Baltimore, USA

    Arka Rai Choudhuri, Aarushi Goel, Matthew Green & Abhishek Jain

  2. Boston University, Boston, USA

    Gabriel Kaptchuk

Authors
  1. Arka Rai Choudhuri
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Aarushi Goel
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Matthew Green
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Abhishek Jain
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Gabriel Kaptchuk
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Arka Rai Choudhuri .

Editor information

Editors and Affiliations

  1. Columbia University, New York City, NY, USA

    Tal Malkin

  2. University of Michigan, Ann Arbor, MI, USA

    Chris Peikert

Rights and permissions

Reprints and permissions

Copyright information

© 2021 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Choudhuri, A.R., Goel, A., Green, M., Jain, A., Kaptchuk, G. (2021). Fluid MPC: Secure Multiparty Computation with Dynamic Participants. In: Malkin, T., Peikert, C. (eds) Advances in Cryptology – CRYPTO 2021. CRYPTO 2021. Lecture Notes in Computer Science(), vol 12826. Springer, Cham. https://doi.org/10.1007/978-3-030-84245-1_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-84245-1_4

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-84244-4

  • Online ISBN: 978-3-030-84245-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation