{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T14:03:44Z","timestamp":1760709824091},"reference-count":70,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,2,7]],"date-time":"2019-02-07T00:00:00Z","timestamp":1549497600000},"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":["J Cryptol"],"published-print":{"date-parts":[[2020,1]]},"DOI":"10.1007\/s00145-019-09314-2","type":"journal-article","created":{"date-parts":[[2019,2,7]],"date-time":"2019-02-07T18:42:23Z","timestamp":1549564943000},"page":"271-318","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the Power of Secure Two-Party Computation"],"prefix":"10.1007","volume":"33","author":[{"given":"Carmit","family":"Hazay","sequence":"first","affiliation":[]},{"given":"Muthuramakrishnan","family":"Venkitasubramaniam","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,2,7]]},"reference":[{"key":"9314_CR1","unstructured":"S. Ames, C. Hazay, Y. Ishai, M. Venkitasubramaniam, Ligero: lightweight sublinear arguments without a trusted setup, in CCS (2017), pp. 2087\u20132104"},{"key":"9314_CR2","unstructured":"B. Applebaum, Y. Ishai, E. Kushilevitz, Cryptography in \n$$NC^0$$\n\n\n\n\nN\n\nC\n0\n\n\n\n\n\n, in FOCS (2004), pp. 166\u2013175"},{"issue":"4","key":"9314_CR3","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1137\/S0097539705446950","volume":"36","author":"B Applebaum","year":"2006","unstructured":"B. Applebaum, Y. Ishai, E. Kushilevitz, Cryptography in nc\n$${}^{\\text{0 }}$$\n\n\n\n\n\n\n0\n\n\n\n\n\n\n. SIAM J. Comput. 36(4), 845\u2013888 (2006)","journal-title":"SIAM J. Comput."},{"key":"9314_CR4","unstructured":"B. Applebaum, Y. Ishai, E. Kushilevitz, From secrecy to soundness: efficient verification via secure computation, in ICALP (2010), pp. 152\u2013163"},{"key":"9314_CR5","unstructured":"S. Agrawal, Y. Ishai, D. Khurana, A. Paskin-Cherniavsky, Statistical randomized encodings: a complexity theoretic view, in ICALP (2015), pp. 1\u201313"},{"key":"9314_CR6","unstructured":"B. Applebaum, Y. Ishai, E. Kushilevitz, B. Waters, Encoding functions with constant online rate or how to compress garbled circuits keys, in CRYPTO (2013), pp. 166\u2013184"},{"issue":"3","key":"9314_CR7","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s00145-013-9149-6","volume":"27","author":"B Applebaum","year":"2014","unstructured":"B. Applebaum, Key-dependent message security: generic amplification and completeness. J. Cryptol. 27(3), 429\u2013451 (2014)","journal-title":"J. Cryptol."},{"issue":"2","key":"9314_CR8","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0022-0000(88)90005-0","volume":"37","author":"G Brassard","year":"1988","unstructured":"G. Brassard, D. Chaum, C. Cr\u00e9peau, Minimum disclosure proofs of knowledge. J. Comput. Syst. Sci. 37(2), 156\u2013189 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"9314_CR9","unstructured":"D. Beaver, Correlated pseudorandomness and the complexity of private computations, in STOC (1996), pp. 479\u2013488"},{"key":"9314_CR10","unstructured":"M. Ben-Or, S. Goldwasser, A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract), in STOC (1988), pp. 1\u201310"},{"key":"9314_CR11","unstructured":"B. Barak, I. Haitner, D. Hofheinz, Y. Ishai, Bounded key-dependent message security, in EUROCRYPT (2010), pp. 423\u2013444"},{"key":"9314_CR12","unstructured":"M. Bellare, V. T. Hoang, P. Rogaway, Foundations of garbled circuits, in CCS (2012), pp. 784\u2013796"},{"key":"9314_CR13","unstructured":"M. Bellare, S. Micali, R. Ostrovsky, Stoc., 482\u2013493 (1990)"},{"key":"9314_CR14","unstructured":"D. Beaver, S. Micali, P. Rogaway, The round complexity of secure protocols (extended abstract), in STOC (1990), pp. 503\u2013513"},{"issue":"1","key":"9314_CR15","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s001459910006","volume":"13","author":"R Canetti","year":"2000","unstructured":"R. Canetti, Security and composition of multiparty cryptographic protocols. J. Cryptol.13(1), 143\u2013202 (2000)","journal-title":"J. Cryptol."},{"key":"9314_CR16","unstructured":"D. Chaum, C. Cr\u00e9peau, I. Damg\u00e5rd, Multiparty unconditionally secure protocols (abstract), in CRYPTO (1987), p. 462"},{"issue":"3","key":"9314_CR17","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s00145-004-0135-x","volume":"17","author":"R Canetti","year":"2004","unstructured":"R. Canetti, I. Damg\u00e5rd, S. Dziembowski, Y. Ishai, T. Malkin, Adaptive versus non-adaptive security of multi-party protocols. J. Cryptol.17(3), 153\u2013207 (2004)","journal-title":"J. Cryptol."},{"key":"9314_CR18","unstructured":"I. Cascudo, I. Damg\u00e5rd, B. M. David, I. Giacomelli, J. B. Nielsen, R. Trifiletti, Additively homomorphic UC commitments with optimal amortized overhead, in PKC (2015), pp. 495\u2013515"},{"key":"9314_CR19","unstructured":"M. Chase, D. Derler, S. Goldfeder, C. Orlandi, S. Ramacher, C. Rechberger, D. Slamanig, G. Zaverucha, Post-quantum zero-knowledge and signatures from symmetric-key primitives, in CCS (2017), pp. 1825\u20131842"},{"key":"9314_CR20","unstructured":"R. Canetti, Y. Lindell, R. Ostrovsky, A. Sahai, Universally composable two-party and multi-party secure computation, in STOC (2002), pp. 494\u2013503"},{"key":"9314_CR21","unstructured":"M. Ciampi, G. Persiano, A. Scafuro, L. Siniscalchi, I. Visconti, Improved or-composition of sigma-protocols, in TCC (2016), pp. 112\u2013141"},{"key":"9314_CR22","unstructured":"M. Ciampi, G. Persiano, A. Scafuro, L. Siniscalchi, I. Visconti, Online\/offline OR composition of sigma protocols, in EUROCRYPT (2016), pp. 63\u201392"},{"key":"9314_CR23","unstructured":"R. Canetti, O. Poburinnaya, M. Venkitasubramaniam, Equivocating yao: constant-round adaptively secure multiparty computation in the plain model, in STOC (2017), pp. 497\u2013509"},{"key":"9314_CR24","unstructured":"C. Cr\u00e9peau, J. van de Graaf, A. Tapp, Committed oblivious transfer and private multi-party computation, in CRYPTO (1995), pp. 110\u2013123"},{"key":"9314_CR25","unstructured":"I. Damg\u00e5rd, On \n$$\\Sigma $$\n\n\n\n\u03a3\n\n\n\n-protocols. \nhttp:\/\/www.cs.au.dk\/~ivan\/Sigma.pdf\n\n (2010)"},{"key":"9314_CR26","unstructured":"I. Damg\u00e5rd, Y. Ishai, Scalable secure multiparty computation, in CRYPTO (2006), pp. 501\u2013520"},{"key":"9314_CR27","unstructured":"I. Damg\u00e5rd, J. B. Nielsen, Improved non-committing encryption schemes based on a general complexity assumption, in CRYPTO (2000), pp. 432\u2013450"},{"key":"9314_CR28","unstructured":"I. Damg\u00e5rd, T. P. Pedersen, B. Pfitzmann, On the existence of statistically hiding bit commitment schemes and fail-stop signatures, in CRYPTO (1993), pp. 250\u2013265"},{"key":"9314_CR29","unstructured":"U. Feige, J. Kilian, M. Naor, A minimal model for secure computation (extended abstract), in STOC (1994), pp. 554\u2013563"},{"issue":"1","key":"9314_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539792230010","volume":"29","author":"U Feige","year":"1999","unstructured":"U. Feige, D. Lapidot, A. Shamir, Multiple noninteractive zero knowledge proofs under general assumptions. SIAM J. Comput. 29(1), 1\u201328 (1999)","journal-title":"SIAM J. Comput."},{"key":"9314_CR31","unstructured":"U. Feige, A. Shamir, Zero knowledge proofs of knowledge in two rounds, in CRYPTO (1989), pp. 526\u2013544"},{"key":"9314_CR32","unstructured":"R. Gennaro, C. Gentry, B. Parno, Non-interactive verifiable computing: Outsourcing computation to untrusted workers, in CRYPTO (2010), pp. 465\u2013482"},{"key":"9314_CR33","unstructured":"V. Goyal, Y. Ishai, A. Sahai, R. Venkatesan, A. Wadia, Founding cryptography on tamper-proof hardware tokens, in TCC (2010), pp. 308\u2013326"},{"issue":"3","key":"9314_CR34","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s001459900010","volume":"9","author":"O Goldreich","year":"1996","unstructured":"O. Goldreich, A. Kahan, How to construct constant-round zero-knowledge proof systems for NP. J. Cryptol.9(3), 167\u2013190 (1996)","journal-title":"J. Cryptol."},{"key":"9314_CR35","unstructured":"C. Ganesh, Y. Kondi, A. Patra, P. Sarkar, Efficient adaptively secure zero-knowledge from garbled circuits, in PKC (2018), pp. 499\u2013529"},{"key":"9314_CR36","unstructured":"S. Goldwasser, Y. T. Kalai, G. N. Rothblum, One-time programs, in CRYPTO (2008), pp. 39\u201356"},{"key":"9314_CR37","unstructured":"V. Goyal, C.-K. Lee, R. Ostrovsky, I. Visconti, Constructing non-malleable commitments: a black-box approach, in FOCS (2012), pp. 51\u201360"},{"key":"9314_CR38","unstructured":"I. Giacomelli, J. Madsen, C. Orlandi, Zkboo: faster zero-knowledge for boolean circuits, in USENIX (2016), pp. 1069\u20131083"},{"issue":"1","key":"9314_CR39","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S Goldwasser","year":"1989","unstructured":"S. Goldwasser, S. Micali, C. Rackoff, The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186\u2013208 (1989)","journal-title":"SIAM J. Comput."},{"key":"9314_CR40","unstructured":"O. Goldreich, S. Micali, A. Wigderson, How to play any mental game or A completeness theorem for protocols with honest majority, in STOC (1987), pp. 218\u2013229"},{"key":"9314_CR41","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546891","volume-title":"Foundations of Cryptography: Basic Tools","author":"O Goldreich","year":"2001","unstructured":"O. Goldreich, Foundations of Cryptography: Basic Tools (Cambridge University Press, Cambridge, 2001)"},{"key":"9314_CR42","unstructured":"V. Goyal, R. Ostrovsky, A. Scafuro, I. Visconti, Black-box non-black-box zero knowledge, in STOC (2014), pp. 515\u2013524"},{"key":"9314_CR43","unstructured":"J. A. Garay, D. Wichs, H.-S. Zhou, Somewhat non-committing encryption and efficient adaptively secure oblivious transfer, in CRYPTO (2009), pp. 505\u2013523"},{"key":"9314_CR44","unstructured":"D. Harnik, Y. Ishai, E. Kushilevitz, J. B. Nielsen, Ot-combiners via secure computation, in TCC (2008), pp. 393\u2013411"},{"key":"9314_CR45","unstructured":"B. Hemenway, Z. Jafargholi, R. Ostrovsky, A. Scafuro, D. Wichs, Adaptively secure garbled circuits from one-way functions, in CRYPTO (2016), pp. 149\u2013178"},{"key":"9314_CR46","unstructured":"S. Halevi, S. Micali, Practical and provably-secure commitment schemes from collision-free hashing, in CRYPTO (1996), pp. 201\u2013215"},{"key":"9314_CR47","unstructured":"I. Haitner, O. Reingold, A new interactive hashing theorem, in CCC (2007), pp. 319\u2013332"},{"key":"9314_CR48","unstructured":"Y. Ishai, E. Kushilevitz, Randomizing polynomials: a new representation with applications to round-efficient secure computation, in FOCS (2000), pp. 294\u2013304"},{"key":"9314_CR49","unstructured":"Y. Ishai, E. Kushilevitz, Perfect constant-round secure computation via perfect randomizing polynomials, in ICALP (2002), pp. 244\u2013256"},{"key":"9314_CR50","unstructured":"Y. Ishai, E. Kushilevitz, R. Ostrovsky, A. Sahai, Zero-knowledge from secure multiparty computation, in STOC (2007), pp. 21\u201330"},{"issue":"3","key":"9314_CR51","doi-asserted-by":"publisher","first-page":"1121","DOI":"10.1137\/080725398","volume":"39","author":"Y Ishai","year":"2009","unstructured":"Y. Ishai, E. Kushilevitz, R. Ostrovsky, A. Sahai, Zero-knowledge proofs from secure multiparty computation. SIAM J. Comput. 39(3), 1121\u20131152 (2009)","journal-title":"SIAM J. Comput."},{"key":"9314_CR52","unstructured":"Y. Ishai, E. Kushilevitz, M. Prabhakaran, A. Sahai, C.-H. Yu, Secure protocol transformations, in CRYPTO (2016), pp. 430\u2013458"},{"issue":"1","key":"9314_CR53","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s001459900018","volume":"10","author":"T Itoh","year":"1997","unstructured":"T. Itoh, Y. Ohta, H. Shizuya, A language-dependent cryptographic primitive. J. Cryptol.10(1), 37\u201350 (1997)","journal-title":"J. Cryptol."},{"key":"9314_CR54","unstructured":"Y. Ishai, M. Prabhakaran, A. Sahai, Founding cryptography on oblivious transfer\u2014efficiently, in CRYPTO (2008), pp. 572\u2013591"},{"key":"9314_CR55","unstructured":"Y. Ishai, M. Prabhakaran, A. Sahai, Secure arithmetic computation with no honest majority, in TCC (2009), pp. 294\u2013314"},{"key":"9314_CR56","unstructured":"Y. Ishai, M. Weiss, Probabilistically checkable proofs of proximity with zero-knowledge, in TCC (2014), pp. 121\u2013145"},{"key":"9314_CR57","unstructured":"Z. Jafargholi, A. Scafuro, D. Wichs, Adaptively indistinguishable garbled circuits, in TCC (2017), pp. 40\u201371"},{"key":"9314_CR58","unstructured":"Z. Jafargholi, D. Wichs, Adaptive security of yao\u2019s garbled circuits, in TCC (2016), pp. 433\u2013458"},{"key":"9314_CR59","unstructured":"J. Kilian, Founding cryptography on oblivious transfer, in STOC (1988), pp. 20\u201331"},{"key":"9314_CR60","unstructured":"J. Katz, R. Ostrovsky, Round-optimal secure two-party computation, in CRYPTO (2004), pp. 335\u2013354"},{"issue":"2","key":"9314_CR61","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s00145-008-9036-8","volume":"22","author":"Y Lindell","year":"2009","unstructured":"Y. Lindell, B. Pinkas, A proof of security of Yao\u2019s protocol for two-party computation. J. Cryptol.22(2), 161\u2013188 (2009)","journal-title":"J. Cryptol."},{"key":"9314_CR62","unstructured":"D. Lapidot, A. Shamir, Publicly verifiable non-interactive zero-knowledge proofs, in CRYPTO (1990), pp. 353\u2013365"},{"issue":"4","key":"9314_CR63","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1007\/s00145-010-9072-z","volume":"24","author":"Y Lindell","year":"2011","unstructured":"Y. Lindell, H. Zarosim, Adaptive zero-knowledge proofs and adaptively secure oblivious transfer. J. Cryptol.24(4), 761\u2013799 (2011)","journal-title":"J. Cryptol."},{"issue":"2","key":"9314_CR64","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/BF00196774","volume":"4","author":"M Naor","year":"1991","unstructured":"M. Naor, Bit commitment using pseudorandomness. J. Cryptol.4(2), 151\u2013158 (1991)","journal-title":"J. Cryptol."},{"key":"9314_CR65","unstructured":"R. Ostrovsky, A. Scafuro, M. Venkitasubramaniam, Resettably sound zero-knowledge arguments from OWFs: the (semi) black-box way, in TCC (2015), pp. 345\u2013374"},{"key":"9314_CR66","unstructured":"S. J. Ong, S. P. Vadhan, An equivalence between zero knowledge and commitments, in TCC (2008), pp. 482\u2013500"},{"key":"9314_CR67","unstructured":"B. Pinkas, T. Schneider, N. P. Smart, S. C. Williams, Secure two-party computation is practical, in ASIACRYPT (2009), pp. 250\u2013267"},{"key":"9314_CR68","unstructured":"R. Pass, H. Wee, Black-box constructions of two-party protocols from one-way functions, in TCC (2009), pp. 403\u2013418"},{"key":"9314_CR69","unstructured":"A. C.-C. Yao, How to generate and exchange secrets (extended abstract), in FOCS (1986), pp. 162\u2013167"},{"key":"9314_CR70","unstructured":"Y. Lindell, H. Zarosim, Adaptive zero-knowledge proofs and adaptively secure oblivious transfer, in TCC (2009), pp. 183\u2013201"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-019-09314-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-019-09314-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-019-09314-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,2,7]],"date-time":"2020-02-07T00:16:32Z","timestamp":1581034592000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-019-09314-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,7]]},"references-count":70,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["9314"],"URL":"https:\/\/doi.org\/10.1007\/s00145-019-09314-2","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,7]]},"assertion":[{"value":"7 January 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 January 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}