{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,26]],"date-time":"2026-01-26T23:13:49Z","timestamp":1769469229669,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662498958","type":"print"},{"value":"9783662498965","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49896-5_16","type":"book-chapter","created":{"date-parts":[[2016,4,27]],"date-time":"2016-04-27T04:45:32Z","timestamp":1461732332000},"page":"448-476","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":63,"title":["The Exact Round Complexity of Secure Computation"],"prefix":"10.1007","author":[{"given":"Sanjam","family":"Garg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pratyay","family":"Mukherjee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Omkant","family":"Pandey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antigoni","family":"Polychroniadou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,28]]},"reference":[{"key":"16_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/978-3-642-29011-4_29","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","author":"G Asharov","year":"2012","unstructured":"Asharov, G., Jain, A., L\u00f3pez-Alt, A., Tromer, E., Vaikuntanathan, V., Wichs, D.: Multiparty computation with low communication, computation and interaction via threshold FHE. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 483\u2013501. Springer, Heidelberg (2012)"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Barak, B.: How to go beyond the black-box simulation barrier. In: 42nd Annual Symposium on Foundations of Computer Science, pp. 106\u2013115. IEEE Computer Society Press, October 2001","DOI":"10.1109\/SFCS.2001.959885"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"Barak, B.: Constant-round coin-tossing with a man in the middle or realizing the shared random string model. In: 43rd Annual Symposium on Foundations of Computer Science, pp. 345\u2013355. IEEE Computer Society Press, November 2002","DOI":"10.1109\/SFCS.2002.1181957"},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"Barak, B., Lindell, Y.: Strict polynomial-time in simulation and extraction. In: 34th Annual ACM Symposium on Theory of Computing, pp. 484\u2013493. ACM Press, May 2002","DOI":"10.1145\/509907.509979"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: 22nd Annual ACM Symposium on Theory of Computing, pp. 503\u2013513. ACM Press, May 1990","DOI":"10.1145\/100216.100287"},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"Or Ben, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: 20th Annual ACM Symposium on Theory of Computing, pp. 1\u201310. ACM Press, May 1988","DOI":"10.1145\/62212.62213"},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: 34th Annual ACM Symposium on Theory of Computing, pp. 494\u2013503. ACM Press, May 2002","DOI":"10.1145\/509907.509980"},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"Chaum, D., Cr\u00e9peau, C., Damg\u00e5rd, I.: Multiparty unconditionally secure protocols (extended abstract). In: 20th Annual ACM Symposium on Theory of Computing, pp. 11\u201319. ACM Press, May 1988","DOI":"10.1145\/62212.62214"},{"key":"16_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/11535218_23","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"IB Damg\u00e5rd","year":"2005","unstructured":"Damg\u00e5rd, I.B., Ishai, Y.: Constant-round multiparty computation using a black-box pseudorandom generator. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 378\u2013394. Springer, Heidelberg (2005)"},{"key":"16_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/11818175_30","volume-title":"Advances in Cryptology - CRYPTO 2006","author":"IB Damg\u00e5rd","year":"2006","unstructured":"Damg\u00e5rd, I.B., Ishai, Y.: Scalable secure multiparty computation. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 501\u2013520. Springer, Heidelberg (2006)"},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"Damg\u00e5rd, I., Nielsen, J.B., Polychroniadou, A.: On the communication required for unconditionally secure multiplication (2015)","DOI":"10.1007\/978-3-662-53008-5_16"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"Dolev, D., Dwork, C., Naor, M.: Non-malleable cryptography (extended abstract). In: 23rd Annual ACM Symposium on Theory of Computing, pp. 542\u2013552. ACM Press, May 1991","DOI":"10.1145\/103418.103474"},{"key":"16_CR13","unstructured":"Feige, U.: Alternative models for zero knowledge interactive proofs. Ph.D thesis (1990)"},{"issue":"1","key":"16_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539792230010","volume":"29","author":"U Feige","year":"1999","unstructured":"Feige, U., Lapidot, D., Shamir, A.: Multiple noninteractive zero knowledge proofs under general assumptions. SIAM J. Comput. 29(1), 1\u201328 (1999)","journal-title":"SIAM J. Comput."},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"Feige, U., Shamir, A.: Witness indistinguishable and witness hiding protocols. In: 22nd Annual ACM Symposium on Theory of Computing, pp. 416\u2013426. ACM Press, May 1990","DOI":"10.1145\/100216.100272"},{"key":"16_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/978-3-642-54242-8_4","volume-title":"Theory of Cryptography","author":"S Garg","year":"2014","unstructured":"Garg, S., Gentry, C., Halevi, S., Raykova, M.: Two-round secure MPC from indistinguishability obfuscation. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 74\u201394. Springer, Heidelberg (2014)"},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: 54th Annual Symposium on Foundations of Computer Science, pp. 40\u201349. IEEE Computer Society Press, October 2013","DOI":"10.1109\/FOCS.2013.13"},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Draft of a chapter on cryptographic protocols. http:\/\/www.wisdom.weizmann.ac.il\/oded\/foc-vol2.html . Accessed June 2003","DOI":"10.1007\/s00446-002-0077-1"},{"key":"16_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721656","volume-title":"Foundations of Cryptography: Basic Applications","author":"O Goldreich","year":"2004","unstructured":"Goldreich, O.: Foundations of Cryptography: Basic Applications, vol. 2. Cambridge University Press, Cambridge (2004)"},{"key":"16_CR20","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: STOC, pp. 218\u2013229 (1987)","DOI":"10.1145\/28395.28420"},{"key":"16_CR21","doi-asserted-by":"crossref","unstructured":"Goyal, V.: Constant round non-malleable protocols using one way functions. In: Fortnow, L., Vadhan, S.P. (eds) 43rd Annual ACM Symposium on Theory of Computing, pp. 695\u2013704. ACM Press, June 2011","DOI":"10.1145\/1993636.1993729"},{"key":"16_CR22","doi-asserted-by":"crossref","unstructured":"Goyal, V., Lee, C.-K., Ostrovsky, R., Visconti, I.: Constructing non-malleable commitments: a black-box approach. In: 53rd Annual Symposium on Foundations of Computer Science, pp. 51\u201360. IEEE Computer Society Press, October 2012","DOI":"10.1109\/FOCS.2012.47"},{"key":"16_CR23","doi-asserted-by":"crossref","unstructured":"Goyal, V., Pandey, O., Richelson, S.: Textbook non-malleable commitments. Manuscript, November 2015","DOI":"10.1145\/2897518.2897657"},{"key":"16_CR24","doi-asserted-by":"crossref","unstructured":"Goyal, V., Richelson, S., Rosen, A., Vald, M.: An algebraic approach to non-malleability. In: 55th Annual Symposium on Foundations of Computer Science, pp. 41\u201350. IEEE Computer Society Press, October 2014","DOI":"10.1109\/FOCS.2014.13"},{"key":"16_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1007\/978-3-540-85174-5_32","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"Y Ishai","year":"2008","unstructured":"Ishai, Y., Prabhakaran, M., Sahai, A.: Founding cryptography on oblivious transfer \u2013 efficiently. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 572\u2013591. Springer, Heidelberg (2008)"},{"key":"16_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/978-3-540-28628-8_21","volume-title":"Advances in Cryptology \u2013 CRYPTO 2004","author":"J Katz","year":"2004","unstructured":"Katz, J., Ostrovsky, R.: Round-optimal secure two-party computation. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 335\u2013354. Springer, Heidelberg (2004)"},{"key":"16_CR27","first-page":"578","volume-title":"Lecture Notes in Computer Science","author":"Jonathan Katz","year":"2003","unstructured":"Katz, J., Ostrovsky, R., Smith, A.: Round efficiency of multi-party computation with a dishonest majority. In: Advances in Cryptology - EUROCRYPT, International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, Proceedings, pp. 578\u2013595, 4\u20138 May 2003"},{"key":"16_CR28","doi-asserted-by":"crossref","unstructured":"Lin, H., Pass, R.: Constant-round non-malleable commitments from any one-way function. In: Fortnow, L., Vadhan, S.P. (eds.) 43rd Annual ACM Symposium on Theory of Computing, pp. 705\u2013714. ACM Press, June 2011","DOI":"10.1145\/1993636.1993730"},{"key":"16_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/978-3-642-14623-7_23","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"H Lin","year":"2010","unstructured":"Lin, H., Pass, R., Tseng, W.-L.D., Venkitasubramaniam, M.: Concurrent non-malleable zero knowledge proofs. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 429\u2013446. Springer, Heidelberg (2010)"},{"key":"16_CR30","doi-asserted-by":"crossref","unstructured":"Lin, H., Pass, R., Venkitasubramaniam, M.: A. unified framework for concurrent security: universal composability from stand-alone non-malleability. In: Mitzenmacher, M. (ed.) 41st Annual ACM Symposium on Theory of Computing, pp. 179\u2013188. ACM Press, May\/June 2009","DOI":"10.1145\/1536414.1536441"},{"key":"16_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/3-540-44647-8_10","volume-title":"Advances in Cryptology - CRYPTO 2001","author":"Y Lindell","year":"2001","unstructured":"Lindell, Y.: Parallel coin-tossing and constant-round secure two-party computation. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 171\u2013189. Springer, Heidelberg (2001)"},{"issue":"2","key":"16_CR32","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s00145-008-9036-8","volume":"22","author":"Y Lindell","year":"2009","unstructured":"Lindell, Y., Pinkas, B.: A proof of security of Yao\u2019s protocol for two-party computation. J. Cryptol. 22(2), 161\u2013188 (2009)","journal-title":"J. Cryptol."},{"key":"16_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/978-3-642-19571-6_20","volume-title":"Theory of Cryptography","author":"Y Lindell","year":"2011","unstructured":"Lindell, Y., Pinkas, B.: Secure two-party computation via cut-and-choose oblivious transfer. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 329\u2013346. Springer, Heidelberg (2011)"},{"key":"16_CR34","unstructured":"Mukherjee, P., Wichs, D.: Two round MPC from LWE via multi-key FHE. IACR Cryptology ePrint Archive 2015:345 (2015)"},{"key":"16_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/978-3-662-48000-7_17","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"R Ostrovsky","year":"2015","unstructured":"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\u2013358. Springer, Heidelberg (2015)"},{"key":"16_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/978-3-540-85174-5_4","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"O Pandey","year":"2008","unstructured":"Pandey, O., Pass, R., Vaikuntanathan, V.: Adaptive one-way functions and applications. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 57\u201374. Springer, Heidelberg (2008)"},{"key":"16_CR37","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) 37th Annual ACM Symposium on Theory of Computing, pp. 84\u201393. ACM Press, May 2005","DOI":"10.1145\/1060590.1060603"},{"key":"16_CR38","doi-asserted-by":"crossref","unstructured":"Wee, H.: Black-box, round-efficient secure computation via non-malleability amplification. In: 51st Annual Symposium on Foundations of Computer Science, pp. 531\u2013540. IEEE Computer Society Press, October 2010","DOI":"10.1109\/FOCS.2010.87"},{"key":"16_CR39","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Protocols for secure computations (extended abstract). In: 23rd Annual Symposium on Foundations of Computer Science, pp. 160\u2013164. IEEE Computer Society Press, November 1982","DOI":"10.1109\/SFCS.1982.38"},{"key":"16_CR40","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: How to generate and exchange secrets (extended abstract). In: FOCS, pp. 162\u2013167 (1986)","DOI":"10.1109\/SFCS.1986.25"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2016"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49896-5_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T22:03:35Z","timestamp":1748901815000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49896-5_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662498958","9783662498965"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49896-5_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"28 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}