[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Secure Multiparty Computation with Free Branching

  • Conference paper
  • First Online:
Advances in Cryptology – EUROCRYPT 2022 (EUROCRYPT 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13275))

  • 2320 Accesses

Abstract

We study secure multi-party computation (MPC) protocols for branching circuits that contain multiple sub-circuits (i.e., branches) and the output of the circuit is that of single “active” branch. Crucially, the identity of the active branch must remain hidden from the protocol participants.

While such circuits can be securely computed by evaluating each branch and then multiplexing the output, such an approach incurs a communication cost linear in the size of the entire circuit. To alleviate this, a series of recent works have investigated the problem of reducing the communication cost of branching executions inside MPC (without relying on fully homomorphic encryption). Most notably, the stacked garbling paradigm [Heath and Kolesnikov, CRYPTO’20] yields garbled circuits for branching circuits whose size only depends on the size of the largest branch. Presently, however, it is not known how to obtain similar communication improvements for secure computation involving more than two parties.

In this work, we provide a generic framework for branching multi-party computation that supports any number of parties. The communication complexity of our scheme is proportional to the size of the largest branch and the computation is linear in the size of the entire circuit. We provide an implementation and benchmarks to demonstrate practicality of our approach.

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
$34.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
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 99.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 129.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping 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.

    We require the underlying MPC to be such that it evaluates the circuit in a gate-by-gate manner and maintains an invariant that for every intermediate wire in the circuit, the parties collectively hold a sharing of the value induced on that wire during evaluation.

  2. 2.

    Our compiler can work with circuits that have gates with arbitrary fan-out. In our construction, it suffices to view such gates as having a single outgoing wire that acts as the incoming wire for multiple gates. Hence, we only assign a single label to the outgoing wire of each gate.

  3. 3.

    Since the type of each gate in each branch is sampled uniformly at random.

  4. 4.

    It grows slightly, since the unary representation of the selection wire must be shared/computed. However the computation of the branch completely dominates the communication.

References

  1. Lattigo v2.2.0. Online: http://github.com/ldsec/lattigo, July 2021. EPFL-LDS

  2. Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: 22nd ACM STOC, pp. 503–513. ACM Press, May 1990

    Google Scholar 

  3. Beck, G., Goel, A., Jain, A., Kaptchuk, G.: Order-C secure multiparty computation for highly repetitive circuits. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12697, pp. 663–693. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77886-6_23

    Chapter  Google Scholar 

  4. Ben-Efraim, A., Lindell, Y., Omri, E.: Efficient scalable constant-round MPC via garbled circuits. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10625, pp. 471–498. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70697-9_17

    Chapter  Google Scholar 

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

    Google Scholar 

  6. Boneh, D., Lewi, K., Montgomery, H., Raghunathan, A.: Key homomorphic PRFs and their applications. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 410–428. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_23

    Chapter  Google Scholar 

  7. Boyle, E., Gilboa, N., Ishai, Y.: Breaking the circuit size barrier for secure computation under DDH. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 509–539. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_19

    Chapter  Google Scholar 

  8. Castagnos, G., Laguillaumie, F.: Linearly homomorphic encryption from \(\sf DDH\). In: Nyberg, K. (ed.) CT-RSA 2015. LNCS, vol. 9048, pp. 487–505. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-16715-2_26

    Chapter  Google Scholar 

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

    Chapter  Google Scholar 

  10. Chen, M., et al.: Diogenes: lightweight scalable RSA modulus generation with a dishonest majority. Cryptology ePrint Archive, Report 2020/374 (2020). https://eprint.iacr.org/2020/374

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

  12. Cramer, R., Damgård, I., Escudero, D., Scholl, P., Xing, C.: SPDZ2k: efficient MPC mod \(2^k\) for dishonest majority. Cryptology ePrint Archive, Report 2018/482 (2018). https://eprint.iacr.org/2018/482

  13. Cramer, R., Damgård, I., Nielsen, J.B.: Multiparty computation from threshold homomorphic encryption. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 280–300. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44987-6_18

    Chapter  Google Scholar 

  14. 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 

  15. Damgård, I., Jurik, M.: A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 119–136. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44586-2_9

    Chapter  MATH  Google Scholar 

  16. 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 

  17. Fan, J., Vercauteren, F.: Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, Report 2012/144 (2012). https://eprint.iacr.org/2012/144

  18. Frederiksen, T.K., Keller, M., Orsini, E., Scholl, P.: A unified approach to MPC with preprocessing using OT. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 711–735. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48797-6_29

    Chapter  Google Scholar 

  19. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) 41st ACM STOC, pp. 169–178. ACM Press, May/June 2009

    Google Scholar 

  20. 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, pp. 218–229. ACM Press, May 1987

    Google Scholar 

  21. Gordon, S.D., Starin, D., Yerukhimovich, A.: The more the merrier: reducing the cost of large scale MPC. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12697, pp. 694–723. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77886-6_24

    Chapter  Google Scholar 

  22. Goyal, V., Li, H., Ostrovsky, R., Polychroniadou, A., Song, Y.: ATLAS: efficient and scalable MPC in the honest majority setting. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12826, pp. 244–274. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84245-1_9

    Chapter  Google Scholar 

  23. Goyal, V., Polychroniadou, A., Song, Y.: Unconditional communication-efficient MPC via Hall’s marriage theorem. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12826, pp. 275–304. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84245-1_10

    Chapter  Google Scholar 

  24. Goyal, V., Song, Y.: Malicious security comes free in honest-majority MPC. Cryptology ePrint Archive, Report 2020/134 (2020). https://eprint.iacr.org/2020/134

  25. Hazay, C., Orsini, E., Scholl, P., Soria-Vazquez, E.: Concretely efficient large-scale MPC with active security (or, TinyKeys for TinyOT). In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11274, pp. 86–117. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03332-3_4

    Chapter  Google Scholar 

  26. Heath, D., Kolesnikov, V.: Stacked garbling - garbled circuit proportional to longest execution path. In: Micciancio, D., Ristenpart, T. (ed.) CRYPTO 2020, Part II, vol. 12171 of LNCS, pp. 763–792. Springer, Heidelberg, August 2020. https://doi.org/10.1007/978-3-030-56880-1_27

  27. Heath, D., Kolesnikov, V.: \(\sf LogStack\): stacked garbling with \(O(b \log b)\) computation. In: Canteaut, A., François-Xavier Standaert, editors, EUROCRYPT 2021, Part III, volume 12698 of LNCS, pages 3–32. Springer, Heidelberg, October 2021 . https://doi.org/10.1007/978-3-030-77883-5_1

  28. Heath, D., Kolesnikov, V., Peceny, S.: MOTIF: (almost) free branching in GMW - via vector-scalar multiplication. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. Part III, vol. 12493 of LNCS, pp. 3–30. Springer, Heidelberg (2020). https://doi.org/10.1007/978-3-030-64840-4_1

  29. Heath, D., Kolesnikov, V., Peceny, S.: Garbling, stacked and staggered - faster k-out-of-n garbled function evaluation. In: Tibouchi, M., Wang, H. (eds.) Advances in Cryptology - ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, 6–10 December 2021, Proceedings, Part II, vol. 13091 of Lecture Notes in Computer Science, pp. 245–274. Springer (2021). https://doi.org/10.1007/978-3-030-92075-3

  30. Heath, D., Kolesnikov, V., Peceny, S.: Masked triples- amortizing multiplication triples across conditionals. In: Garay, J.A. (ed.) PKC 2021. LNCS, vol. 12711, pp. 319–348. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-75248-4_12

    Chapter  Google Scholar 

  31. Katz, J., Malka, L.: Constant-round private function evaluation with linear complexity. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 556–571. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_30

    Chapter  Google Scholar 

  32. Keller, M.: MP-SPDZ: a versatile framework for multi-party computation. In: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security (2020)

    Google Scholar 

  33. Keller, M., Orsini, E., Scholl, P.: MASCOT: faster malicious arithmetic secure computation with oblivious transfer. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016, pp. 830–842. ACM Press, October 2016

    Google Scholar 

  34. Keller, M., Pastro, V., Rotaru, D.: Overdrive: making SPDZ great again. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10822, pp. 158–189. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_6

    Chapter  Google Scholar 

  35. Mohassel, P., Sadeghian, S.: How to hide circuits in MPC an efficient framework for private function evaluation. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 557–574. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_33

    Chapter  MATH  Google Scholar 

  36. Mohassel, P., Sadeghian, S., Smart, N.P.: Actively secure private function evaluation. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 486–505. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45608-8_26

    Chapter  Google Scholar 

  37. Naor, M., Pinkas, B., Reingold, O.: Distributed Pseudo-random functions and KDCs. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 327–346. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_23

    Chapter  Google Scholar 

  38. Peikert, C., Vaikuntanathan, V., Waters, B.: A framework for efficient and composable oblivious transfer. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 554–571. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_31

    Chapter  Google Scholar 

  39. 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.F., Katz, J. (eds.) ACM CCS 2019, pp. 615–632. ACM Press, November 2019

    Google Scholar 

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

    Google Scholar 

Download references

Acknowledgements

We thank the anonymous reviewers of EUROCRYPT 2022 for their helpful comments. The first, third and forth authors are supported in part by an NSF CNS grant 1814919, NSF CAREER award 1942789 and Johns Hopkins University Catalyst award. The second author is funded by Concordium Blockhain Research Center, Aarhus University, Denmark. The third author is additionally supported by NSF CNS-1653110, NSF CNS-1801479, a Google Security & Privacy Award and DARPA under Agreements No. HR00112020021 and Agreements No. HR001120C0084. 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

    Aarushi Goel, Aditya Hegde & Abhishek Jain

  2. Aarhus University, Aarhus, Denmark

    Mathias Hall-Andersen

Authors
  1. Aarushi Goel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mathias Hall-Andersen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Aditya Hegde
    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

Corresponding author

Correspondence to Abhishek Jain .

Editor information

Editors and Affiliations

  1. University of Haifa, Haifa, Haifa, Israel

    Orr Dunkelman

  2. University of Warsaw, Warsaw, Poland

    Stefan Dziembowski

Rights and permissions

Reprints and permissions

Copyright information

© 2022 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Goel, A., Hall-Andersen, M., Hegde, A., Jain, A. (2022). Secure Multiparty Computation with Free Branching. In: Dunkelman, O., Dziembowski, S. (eds) Advances in Cryptology – EUROCRYPT 2022. EUROCRYPT 2022. Lecture Notes in Computer Science, vol 13275. Springer, Cham. https://doi.org/10.1007/978-3-031-06944-4_14

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-06944-4_14

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-06943-7

  • Online ISBN: 978-3-031-06944-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships