Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Round-Optimal Black-Box Secure Computation from Two-Round Malicious OT

  • 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

We give round-optimal black-box constructions of two-party and multiparty protocols in the common random/reference string (CRS) model, with security against malicious adversaries, based on any two-round oblivious transfer (OT) protocol in the same model. Specifically, we obtain two types of results.

  1. 1.

    Two-party protocol. We give a (two-round) two-sided NISC protocol that makes black-box use of two-round (malicious-secure) OT in the CRS model. In contrast to the standard setting of non-interactive secure computation (NISC), two-sided NISC allows communication from both parties in each round and delivers the output to both parties at the end of the protocol. Prior black-box constructions of two-sided NISC relied on idealized setup assumptions such as OT correlations, or were proven secure in the random oracle model.

  2. 2.

    Multiparty protocol. We give a three-round secure multiparty computation protocol for an arbitrary number of parties making black-box use of a two-round OT in the CRS model. The round optimality of this construction follows from a black-box impossibility proof of Applebaum et al. (ITCS 2020). Prior constructions either required the use of random oracles, or were based on two-round malicious-secure OT protocols that satisfied additional security properties.

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 149.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 199.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.

    A bit more precisely, we refer here to the usual notion of a fully black-box reduction [IR90, RTV04], where not only the construction makes a black-box use of OT but also the security reduction makes a black-box use of the adversary.

  2. 2.

    The same is true even for the plain-model variant of OT with unbounded receiver simulation [NP01, AIR01]. Here we only consider OT and MPC with efficient simulation in the CRS model.

  3. 3.

    Jumping ahead, both compilers use a virtual honest-majority MPC protocol in which the number of parties serves as a security parameter. The use of the Fiat-Shamir paradigm in [IKSS22] requires the use of a computational security parameter instead of a statistical one.

  4. 4.

    By an honest-majority client-server MPC, we mean a setting where a malicious adversary can corrupt any subset of the clients and a constant fraction of the servers.

  5. 5.

    We note that [GS18] gave a non-black-box construction.

References

  1. Applebaum, B., Brakerski, Z., Garg, S., Ishai, Y., Srinivasan, A.: Separating two-round secure computation from oblivious transfer. In: ITCS 2020, vol. 151 of LIPIcs, pp. 71:1–71:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

    Google Scholar 

  2. Agarwal, A., Bartusek, J., Goyal, V., Khurana, D., Malavolta, G.: Two-round maliciously secure computation with super-polynomial simulation. In: Nissim, K., Waters, B. (eds.) TCC 2021. LNCS, vol. 13042, pp. 654–685. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-90459-3_22

    Chapter  Google Scholar 

  3. Ananth, P., Choudhuri, A.R., Jain, A.: A new approach to round-optimal secure multiparty computation. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 468–499. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_16

    Chapter  Google Scholar 

  4. Aiello, B., Ishai, Y., Reingold, O.: Priced oblivious transfer: how to sell digital goods. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 119–135. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44987-6_8

    Chapter  Google Scholar 

  5. Abdolmaleki, B., Malavolta, G., Rahimi, A.: Two-round concurrently secure two-party computation. IACR Cryptol. ePrint Arch., pp. 1357 (2021)

    Google Scholar 

  6. Boyle, E., et al.: Efficient two-round OT extension and silent non-interactive secure computation. In: CCS 2019, pp. 291–308. ACM (2019)

    Google Scholar 

  7. Branco, P., Döttling, N., Mateus, P.: Two-round oblivious linear evaluation from learning with errors. In: Hanaoka, G., Shikata, J., Watanabe, Y. (eds.) PKC 2022. LNCS, vol. 13177, pp. 379–408. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-97121-2_14

    Chapter  Google Scholar 

  8. Beaver, D.: Precomputing oblivious transfer. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 97–109. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-44750-4_8

    Chapter  Google Scholar 

  9. Bitansky, N., Freizeit, S.: Statistically sender-private OT from LPN and derandomization. In: Crypto 2022 (2022)

    Google Scholar 

  10. Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications. In: STOC, vol. 1988, pp. 103–112 (1988)

    Google Scholar 

  11. Badrinarayanan, S., Garg, S., Ishai, Y., Sahai, A., Wadia, A.: Two-message witness indistinguishability and secure computation in the plain model from new assumptions. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10626, pp. 275–303. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70700-6_10

    Chapter  MATH  Google Scholar 

  12. Boyle, E., Gilboa, N., Ishai, Y., Lin, H., Tessaro, S.: Foundations of homomorphic secret sharing. In: ITCS 2018, pp. 21:1–21:21 (2018)

    Google Scholar 

  13. Badrinarayanan, S., Goyal, V., Jain, A., Khurana, D., Sahai, A.: Round optimal concurrent MPC via strong simulation. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10677, pp. 743–775. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_25

    Chapter  Google Scholar 

  14. Badrinarayanan, S., Goyal, V., Jain, A., Kalai, Y.T., Khurana, D., Sahai, A.: Promise zero knowledge and its applications to round optimal MPC. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10992, pp. 459–487. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_16

    Chapter  Google Scholar 

  15. Brakerski, Z., Halevi, S., Polychroniadou, A.: Four round secure computation without setup. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10677, pp. 645–677. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_22

    Chapter  Google Scholar 

  16. Fabrice Benhamouda and Huijia Lin. \(k\)-round MPC from \(k\)-round OT via garbled interactive circuits. EUROCRYPT, 2018

    Google Scholar 

  17. Barak, B., Lindell, Y., Vadhan, S.P.: Lower bounds for non-black-box zero knowledge. In: FOCS, vol. 2003, pp. 384–393 (2003)

    Google Scholar 

  18. Rai Choudhuri, A., Ciampi, M., Goyal, V., Jain, A., Ostrovsky, R.: Round optimal secure multiparty computation from minimal assumptions. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12551, pp. 291–319. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64378-2_11

    Chapter  Google Scholar 

  19. Chase, M., Dodis, Y., Ishai, Y., Kraschewski, D., Liu, T., Ostrovsky, R., Vaikuntanathan, V.: Reusable non-interactive secure computation. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11694, pp. 462–488. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_15

    Chapter  Google Scholar 

  20. Döttling, N., Garg, S., Hajiabadi, M., Masny, D., Wichs, D.: Two-round oblivious transfer from CDH or LPN. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12106, pp. 768–797. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_26

    Chapter  Google Scholar 

  21. Dittmer, S., Ishai, Y., Ostrovsky, R.: Line-point zero knowledge and its applications. In: ITC 2021, pp. 5:1–5:24 (2021)

    Google Scholar 

  22. Fernando, R., Jain, A., Komargodski, I.: Maliciously-secure mrnisc in the plain model. In: IACR Cryptol. ePrint Arch., pp. 1319 (2021)

    Google Scholar 

  23. Garg, S., Goyal, V., Jain, A., Sahai, A.: Concurrently secure computation in constant rounds. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 99–116. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_8

    Chapter  Google Scholar 

  24. Gennaro, R., Ishai, Y., Kushilevitz, E., Rabin, T.: On 2-round secure multiparty computation. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 178–193. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45708-9_12

    Chapter  Google Scholar 

  25. Garg, S., Ishai, Y., Srinivasan, A.: Two-round MPC: information-theoretic and black-box. In: Beimel, A., Dziembowski, S. (eds.) TCC 2018. LNCS, vol. 11239, pp. 123–151. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03807-6_5

    Chapter  Google Scholar 

  26. Garg, S., Kiyoshima, S., Pandey, O.: On the exact round complexity of self-composable two-party computation. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 194–224. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_7

    Chapter  Google Scholar 

  27. Garg, S., Mukherjee, P., Pandey, O., Polychroniadou, A.: The exact round complexity of secure computation. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 448–476. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_16

    Chapter  Google Scholar 

  28. Goyal, V.: Constant round non-malleable protocols using one way functions. In: Fortnow, L., Vadhan, S.P. (eds) 43rd ACM STOC, pp. 695–704, San Jose, CA, USA, 6–8 June 2011. ACM Press

    Google Scholar 

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

  30. Halevi, S., Hazay, C., Polychroniadou, A., Venkitasubramaniam, M.: Round-optimal secure multi-party computation. Journal of Cryptology 34(3), 1–63 (2021). https://doi.org/10.1007/s00145-021-09382-3

    Article  MathSciNet  MATH  Google Scholar 

  31. Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending oblivious transfers efficiently. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 145–161. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_9

    Chapter  Google Scholar 

  32. Ishai, Y., Kushilevitz, E., Ostrovsky, R., Prabhakaran, M., Sahai, A.: Efficient non-interactive secure computation. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 406–425. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_23

    Chapter  Google Scholar 

  33. Ishai, Y., Kushilevitz, E., Paskin, A.: Secure multiparty computation with minimal interaction. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 577–594. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_31

    Chapter  Google Scholar 

  34. Ishai, Y., Khurana, D., Sahai, A., Srinivasan, A.: On the round complexity of black-box secure MPC. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12826, pp. 214–243. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84245-1_8

    Chapter  Google Scholar 

  35. Ishai, Y., Khurana, D., Sahai, A., Srinivasan, A.: Round-optimal black-box protocol compilers. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022. LNCS, vol. 13275, pp. 210–240. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-06944-4_8

    Chapter  Google Scholar 

  36. Ishai, Y., Prabhakaran, M., Sahai, A.: Founding cryptography on oblivious transfer – efficiently. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 572–591. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_32

    Chapter  Google Scholar 

  37. Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 8–26. Springer, New York (1990). https://doi.org/10.1007/0-387-34799-2_2

    Chapter  Google Scholar 

  38. Kiyoshima, S., Manabe, Y., Okamoto, T.: Constant-round black-box construction of composable multi-party computation protocol. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 343–367. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54242-8_15

    Chapter  MATH  Google Scholar 

  39. Katz, J., Ostrovsky, R.: Round-optimal secure two-party computation. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 335–354. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28628-8_21

    Chapter  Google Scholar 

  40. Katz, J., Ostrovsky, R., Smith, A.: Round efficiency of multi-party computation with a dishonest majority. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 578–595. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_36

    Chapter  Google Scholar 

  41. Masny, D., Rindal, P.: Endemic oblivious transfer. In: CCS 2019, pp. 309–326. ACM (2019)

    Google Scholar 

  42. Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In Rao Kosaraju, S. (ed.), Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 7–9 January 2001, Washington, DC, USA., pp. 448–457. ACM/SIAM (2001)

    Google Scholar 

  43. Ostrovsky, R., Richelson, S., Scafuro, A.: Round-optimal black-box two-party computation. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 339–358. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_17

    Chapter  Google Scholar 

  44. Paskin-Cherniavsky, A.: Secure Computation with minimal interaction. Ph.D. thesis, Technion (2012). http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2012/PHD/PHD-2012-16.pdf

  45. Patra, A., Srinivasan, A.: Three-round secure multiparty computation from black-box two-round oblivious transfer. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12826, pp. 185–213. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84245-1_7

    Chapter  Google Scholar 

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

  47. Reingold, O., Trevisan, L., Vadhan, S.: Notions of reducibility between cryptographic primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 1–20. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24638-1_1

    Chapter  MATH  Google Scholar 

  48. Wee, H.: Black-box, round-efficient secure computation via non-malleability amplification. In: 51st FOCS, pp. 531–540, Las Vegas, NV, USA, 23–26 October 2010. IEEE Computer Society Press

    Google Scholar 

  49. Yao, A.C.C.: How to generate and exchange secrets. In: 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, October 27–29 1986, pp. 162–167. IEEE Computer Society (1986)

    Google Scholar 

Download references

Acknowledgments

Y. Ishai was supported in part by ERC Project NTSC (742754), BSF grant 2018393, and ISF grant 2774/20. D. Khurana was supported in part by DARPA SIEVE award, a gift from Visa Research, and a C3AI DTI award. A. Sahai was supported in part from a Simons Investigator Award, DARPA SIEVE award, NTT Research, NSF Frontier Award 1413955, BSF grant 2012378, a Xerox Faculty Research Award, a Google Faculty Research Award, and an Okawa Foundation Research Grant. This material is based upon work supported by the Defense Advanced Research Projects Agency through Award HR00112020024. A. Srinivasan was supported in part by a SERB startup grant.

Author information

Authors and Affiliations

  1. Technion, Haifa, Israel

    Yuval Ishai

  2. UIUC, Champaign, USA

    Dakshita Khurana

  3. UCLA, Los Angeles, USA

    Amit Sahai

  4. 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. Dakshita Khurana
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Amit Sahai
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Akshayaram Srinivasan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Akshayaram Srinivasan .

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., Khurana, D., Sahai, A., Srinivasan, A. (2022). Round-Optimal Black-Box Secure Computation from Two-Round Malicious OT. 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_16

Download citation

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

  • 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