Skip to main content
Springer Nature Link
Log in

Fully-Secure MPC with Minimal Trust

  • Conference paper
  • First Online:
Theory of Cryptography (TCC 2022)

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

Included in the following conference series:

Abstract

The task of achieving full security (with guaranteed output delivery) in secure multiparty computation (MPC) is a long-studied problem. Known impossibility results (Cleve, STOC 86) rule out general solutions in the dishonest majority setting. In this work, we consider solutions that use an external trusted party (TP) to bypass the impossibility results, and study the minimal requirements needed from this trusted party. In particular, we restrict ourselves to the extreme setting where the size of the TP is independent of the size of the functionality to be computed (called “small" TP) and this TP is invoked only once during the protocol execution. We present several positive and negative results for fully-secure MPC in this setting.

  • For a natural class of protocols, specifically, those with a universal output decoder, we show that the size of the TP must necessarily be exponential in the number of parties. This result holds irrespective of the computational assumptions used in the protocol. The class of protocols to which our lower bound applies is broad enough to capture prior results in the area, implying that the prior techniques necessitate the use of an exponential-sized TP. We additionally rule out the possibility of achieving information-theoretic full security (without the restriction of using a universal output decoder) using a “small" TP in the plain model (i.e., without any setup).

  • In order to get around the above negative result, we consider protocols without a universal output decoder. The main positive result in our work is a construction of such a fully-secure MPC protocol assuming the existence of a succinct Functional Encryption scheme. We also give evidence that such an assumption is likely to be necessary for fully-secure MPC in certain restricted settings.

  • Finally, we explore the possibility of achieving full-security with a semi-honest TP that could collude with other malicious parties (which form a dishonest majority). In this setting, we show that even fairness is impossible to achieve regardless of the “small TP” requirement.

S. Patranabis—Most of the work was done while the author was affiliated with ETH Zürich, Switzerland and Visa Research USA.

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)
eBook
USD 149.00
Price excludes VAT (USA)
Softcover Book
USD 199.99
Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    This notion differs from the line of work on token-based cryptography initiated by Katz [Kat07], where the tamper-proof tokens are generated locally, and the main challenge is to guarantee security even when tokens can be maliciously generated.

  2. 2.

    The notion of fail-stop corruption lies between semi-honest and malicious corruption, where eavesdropping like semi-honest corruption is allowed and the only possible malicious corruption is stopping the execution of the protocol.

  3. 3.

    Some of the protocols in the literature realizing this functionality for general functions are [GS18].

  4. 4.

    We believe that a non-interactive post-TP computation phase is essentially without loss of generality. In other words, any fully secure MPC protocol (having access to one TP call) with interaction amongst the parties can be transformed to one where the parties do not communicate at all amongst themselves after receiving TP’s response. We give a proof in the full version of our paper.

References

  1. Asharov, G., Beimel, A., Makriyannis, N., Omri, E.: Complete characterization of fairness in secure two-party computation of boolean functions. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9014, pp. 199–228. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46494-6_10

    Chapter  MATH  Google Scholar 

  2. Andrychowicz, M., Dziembowski, S., Malinowski, D., Mazurek, L.: Secure multiparty computations on bitcoin. In: IEEE SP 2014, pp. 443–458. IEEE Computer Society (2014)

    Google Scholar 

  3. Beaver, D.: Correlated pseudorandomness and the complexity of private computations. In: ACM STOC 1996, pp. 479–488. ACM (1996)

    Google Scholar 

  4. Beerliová-Trubíniová, Z., Fitzi, M., Hirt, M., Maurer, U., Zikas, V.: MPC vs. SFE: perfect security in a unified corruption model. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 231–250. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78524-8_14

    Chapter  Google Scholar 

  5. Brzuska, C., Fischlin, M., Schröder, H., Katzenbeisser, S.: Physically uncloneable functions in the universal composition framework. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 51–70. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_4

    Chapter  MATH  Google Scholar 

  6. Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., Yang, K.: On the (Im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1–18. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_1

    Chapter  Google Scholar 

  7. Badrinarayanan, S., Jain, A., Ostrovsky, R., Visconti, I.: Non-interactive secure computation from one-way functions. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11274, pp. 118–138. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03332-3_5

    Chapter  Google Scholar 

  8. Bentov, I., Kumaresan, R.: How to use bitcoin to design fair protocols. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 421–439. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44381-1_24

    Chapter  Google Scholar 

  9. Badrinarayanan, S., Khurana, D., Ostrovsky, R., Visconti, I.: Unconditional UC-secure computation with (stronger-malicious) PUFs. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10210, pp. 382–411. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56620-7_14

    Chapter  Google Scholar 

  10. Beimel, A., Lindell, Y., Omri, E., Orlov, I.: 1/p-secure multiparty computation without an honest majority and the best of both worlds. J. Cryptol. 33(4), 1659–1731 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  11. Beimel, A., Omri, E., Orlov, I.: Protocols for multiparty coin toss with a dishonest majority. J. Cryptol. 28(3), 551–600 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  12. Boneh, D., Sahai, A., Waters, B.: Functional encryption: definitions and challenges. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 253–273. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19571-6_16

    Chapter  Google Scholar 

  13. Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: FOCS (2001)

    Google Scholar 

  14. Chandran, N., Chongchitmate, W., Ostrovsky, R., Visconti, I.: Universally composable secure computation with corrupted tokens. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11694, pp. 432–461. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_14

    Chapter  Google Scholar 

  15. Canetti, R., Fischlin, M.: Universally composable commitments. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 19–40. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_2

    Chapter  Google Scholar 

  16. Choudhuri, A.R., Green, M., Jain, A., Kaptchuk, G., Miers, I.: Fairness in an unfair world: fair multiparty computation from public bulletin boards. In: ACM CCS 2017, pp. 719–728. ACM (2017)

    Google Scholar 

  17. Chandran, N., Goyal, V., Sahai, A.: New constructions for UC secure computation using tamper-proof hardware. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 545–562. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_31

    Chapter  Google Scholar 

  18. Choi, S.G., Katz, J., Schröder, D., Yerukhimovich, A., Zhou, H.-S.: (Efficient) universally composable oblivious transfer using a minimal number of stateless tokens. In: TCC 2014, pp. 638–662 (2014)

    Google Scholar 

  19. Cleve, R.: Limits on the security of coin flips when half the processors are faulty (extended abstract). In: ACM STOC (1986)

    Google Scholar 

  20. Dachman-Soled, D., Malkin, T., Raykova, M., Venkitasubramaniam, M.: Adaptive and concurrent secure computation from new adaptive, non-malleable commitments. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013. LNCS, vol. 8269, pp. 316–336. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-42033-7_17

    Chapter  Google Scholar 

  21. De, A., Trevisan, L., Tulsiani, M.: Time space tradeoffs for attacks against one-way functions and PRGs. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 649–665. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_35

    Chapter  Google Scholar 

  22. Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. Commun. ACM 28(6), 637–647 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  23. Fitzi, M., Garay, J.A., Maurer, U., Ostrovsky, R.: Minimal complete primitives for secure multi-party computation. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 80–100. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_5

    Chapter  Google Scholar 

  24. Fitzi, M., Hirt, M., Maurer, U.: General Adversaries in Unconditional Multi-party Computation. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 1999. LNCS, vol. 1716, pp. 232–246. Springer, Heidelberg (1999). https://doi.org/10.1007/978-3-540-48000-6_19

    Chapter  MATH  Google Scholar 

  25. Feige, U., Kilian, J., Naor, M.: A minimal model for secure computation (extended abstract). In: ACM STOC 1994, pp. 554–563 (1994)

    Google Scholar 

  26. Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: IEEE FOCS 2013, pp. 40–49. IEEE Computer Society (2013)

    Google Scholar 

  27. Garg, S., Gentry, C., Sahai, A., Waters, B.: Witness encryption and its applications. In: ACM STOC 2013, pp. 467–476. ACM (2013)

    Google Scholar 

  28. Dov Gordon, S., Hazay, C., Katz, J., Lindell, Y.: Complete fairness in secure two-party computation. J. ACM 58(6), 24:1–24:37 (2011)

    Google Scholar 

  29. Dov Gordon, S., Ishai, Y., Moran, T., Ostrovsky, R., Sahai, A.: On complete primitives for fairness. In: TCC 2010, pp. 91–108 (2010)

    Google Scholar 

  30. Gordon, S.D., Katz, J.: Complete fairness in multi-party computation without an honest majority. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 19–35. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00457-5_2

    Chapter  Google Scholar 

  31. Dov Gordon, S., Katz, J.: Partial fairness in secure two-party computation. J. Cryptol. 25(1), 14–40 (2012)

    Google Scholar 

  32. Goldwasser, S., Kalai, Y.T., Popa, R.A., Vaikuntanathan, V., Zeldovich, N.: Reusable garbled circuits and succinct functional encryption. In: STOC 2013, pp. 555–564 (2013)

    Google Scholar 

  33. Garay, J.A., MacKenzie, P.D., Prabhakaran, M., Yang, K.: Resource fairness and composability of cryptographic protocols. J. Cryptol. 24(4), 615–658 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  34. Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or A completeness theorem for protocols with honest majority. In: ACM STOC (1987)

    Google Scholar 

  35. Garg, S., Srinivasan, A.: Two-round multiparty secure computation from minimal assumptions. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 468–499. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_16

    Chapter  Google Scholar 

  36. Hirt, M., Maurer, U., Zikas, V.: MPC vs. SFE: unconditional and computational security. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 1–18. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-89255-7_1

    Chapter  Google Scholar 

  37. Hazay, C., Polychroniadou, A., Venkitasubramaniam, M.: Composable security in the tamper-proof hardware model under minimal complexity. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9985, pp. 367–399. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53641-4_15

    Chapter  Google Scholar 

  38. Ishai, Y., Ostrovsky, R., Seyalioglu, H.: Identifying cheaters without an honest majority. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 21–38. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28914-9_2

    Chapter  Google Scholar 

  39. Jain, A., Lin, H., Sahai, A.: Indistinguishability obfuscation from well-founded assumptions. In: STOC 2021, pp. 60–73 (2021)

    Google Scholar 

  40. Katz, J.: Universally composable multi-party computation using tamper-proof hardware. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 115–128. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-72540-4_7

    Chapter  Google Scholar 

  41. Kumaresan, R., Bentov, I.: How to use bitcoin to incentivize correct computations. In: Ahn, G.-J., Yung, M., Li, N. (eds.) ACM CCS 2014, pp. 30–41. ACM (2014)

    Google Scholar 

  42. O’Neill, A.: Definitional issues in functional encryption. IACR Cryptol. ePrint Arch., p. 556 (2010)

    Google Scholar 

  43. Ostrovsky, R., Scafuro, A., Visconti, I., Wadia, A.: Universally composable secure computation with (malicious) physically uncloneable functions. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 702–718. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_41

    Chapter  Google Scholar 

  44. Pass, R., Shi, E., Tramèr, F.: Formal abstractions for attested execution secure processors. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10210, pp. 260–289. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56620-7_10

    Chapter  Google Scholar 

  45. Quach, W., Wee, H., Wichs, D.: Laconic function evaluation and applications. In: Thorup, M. (ed.) IEEE FOCS 2018, pp. 859–870. IEEE Computer Society (2018)

    Google Scholar 

  46. Sahai, A., Waters, B.: Fuzzy identity-based encryption. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 457–473. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_27

    Chapter  Google Scholar 

  47. Waters, B.: A punctured programming approach to adaptively secure functional encryption. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 678–697. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_33

    Chapter  Google Scholar 

Download references

Acknowledgments

We thank the anonymous reviewers of TCC 2022 for their helpful comments and suggestions. Y. Ishai was supported in part by ERC Project NTSC (742754), BSF grant 2018393, and ISF grant 2774/20. A. Patra would like to acknowledge financial support from DST National Mission on Interdisciplinary Cyber-Physical Systems (NM-ICPS) 2020–2025. D. Ravi was funded by the European Research Council (ERC) under the European Unions’s Horizon 2020 research and innovation programme under grant agreement No 803096 (SPEC). A. Srinivasan was supported in part by a SERB startup grant.

Author information

Authors and Affiliations

  1. Technion, Haifa, Israel

    Yuval Ishai

  2. Indian Institute of Science, Bangalore, India

    Arpita Patra

  3. IBM Research India, Bangalore, India

    Sikhar Patranabis

  4. Aarhus University, Aarhus, Denmark

    Divya Ravi

  5. Tata Institute of Fundamental Research, Mumbai, India

    Akshayaram Srinivasan

Authors
  1. Yuval Ishai
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Arpita Patra
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sikhar Patranabis
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Divya Ravi
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Akshayaram Srinivasan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Divya Ravi .

Editor information

Editors and Affiliations

  1. Ruhr University Bochum, Bochum, Germany

    Eike Kiltz

  2. Massachusetts Institute of Technology, Cambridge, MA, USA

    Vinod Vaikuntanathan

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Ishai, Y., Patra, A., Patranabis, S., Ravi, D., Srinivasan, A. (2022). Fully-Secure MPC with Minimal Trust. In: Kiltz, E., Vaikuntanathan, V. (eds) Theory of Cryptography. TCC 2022. Lecture Notes in Computer Science, vol 13748. Springer, Cham. https://doi.org/10.1007/978-3-031-22365-5_17

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-22365-5_17

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-22364-8

  • Online ISBN: 978-3-031-22365-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation