{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T22:13:13Z","timestamp":1791324793509,"version":"4.3.1"},"publisher-location":"Berlin, Heidelberg","reference-count":49,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642289132","type":"print"},{"value":"9783642289149","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-28914-9_4","type":"book-chapter","created":{"date-parts":[[2012,3,5]],"date-time":"2012-03-05T16:12:39Z","timestamp":1330963959000},"page":"54-74","source":"Crossref","is-referenced-by-count":78,"title":["Secure Two-Party Computation with Low Communication"],"prefix":"10.1007","author":[{"given":"Ivan","family":"Damg\u00e5rd","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Faust","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carmit","family":"Hazay","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"4_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/3-540-45022-X_39","volume-title":"Automata, Languages and Programming","author":"W. Aiello","year":"2000","unstructured":"Aiello, W., Bhatt, S., Ostrovsky, R., Rajagopalan, S.R.: Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 463\u2013474. Springer, Heidelberg (2000)"},{"key":"4_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/978-3-642-14165-2_14","volume-title":"Automata, Languages and Programming","author":"B. Applebaum","year":"2010","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: From Secrecy to Soundness: Efficient Verification via Secure Computation. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010, Part I. LNCS, vol.\u00a06198, pp. 152\u2013163. Springer, Heidelberg (2010)"},{"issue":"1","key":"4_CR3","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: A new characterization of np. J. ACM\u00a045(1), 70\u2013122 (1998)","journal-title":"J. ACM"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Canetti, R., Chiesaz, A., Tromer, E.: From extractable collision resistance to succinct non- interactive arguments of knowledge, and back again. Cryptology ePrint Archive, Report 2011\/443 (2011)","DOI":"10.1145\/2090236.2090263"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: STOC, pp. 21\u201331 (1991)","DOI":"10.1145\/103418.103428"},{"key":"4_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/978-3-642-22792-9_7","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"S. Benabbas","year":"2011","unstructured":"Benabbas, S., Gennaro, R., Vahlis, Y.: Verifiable Delegation of Computation over Large Datasets. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol.\u00a06841, pp. 111\u2013131. Springer, Heidelberg (2011)"},{"key":"4_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/978-3-540-30539-2_4","volume-title":"Advances in Cryptology - ASIACRYPT 2004","author":"M. Bellare","year":"2004","unstructured":"Bellare, M., Palacio, A.: Towards Plaintext-Aware Public-Key Encryption Without Random Oracles. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol.\u00a03329, pp. 48\u201362. Springer, Heidelberg (2004)"},{"key":"4_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/11935230_20","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2006","author":"M. Bellare","year":"2006","unstructured":"Bellare, M., Ristenpart, T.: Multi-Property-Preserving Hash Domain Extension and the EMD Transform. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol.\u00a04284, pp. 299\u2013314. Springer, Heidelberg (2006)"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Sudan, M.: Simple pcps with poly-log rate and query complexity. In: STOC, pp. 266\u2013275 (2005)","DOI":"10.1145\/1060590.1060631"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) lwe. In: FOCS (2011)","DOI":"10.1109\/FOCS.2011.12"},{"key":"4_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/978-3-642-22792-9_29","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"Z. Brakerski","year":"2011","unstructured":"Brakerski, Z., Vaikuntanathan, V.: Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol.\u00a06841, pp. 505\u2013524. Springer, Heidelberg (2011)"},{"issue":"1","key":"4_CR12","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s001459910006","volume":"13","author":"R. Canetti","year":"2000","unstructured":"Canetti, R.: Security and composition of multiparty cryptographic protocols. J. Cryptology\u00a013(1), 143\u2013202 (2000)","journal-title":"J. Cryptology"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. In: FOCS, pp. 136\u2013145 (2001)","DOI":"10.1109\/SFCS.2001.959888"},{"key":"4_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1007\/978-3-642-14623-7_26","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"K.-M. Chung","year":"2010","unstructured":"Chung, K.-M., Kalai, Y., Vadhan, S.: Improved Delegation of Computation Using Fully Homomorphic Encryption. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.\u00a06223, pp. 483\u2013501. Springer, Heidelberg (2010)"},{"key":"4_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/978-3-540-69407-6_21","volume-title":"Logic and Theory of Algorithms","author":"G. Crescenzo Di","year":"2008","unstructured":"Di Crescenzo, G., Lipmaa, H.: Succinct NP Proofs from an Extractability Assumption. In: Beckmann, A., Dimitracopoulos, C., L\u00f6we, B. (eds.) CiE 2008. LNCS, vol.\u00a05028, pp. 175\u2013185. Springer, Heidelberg (2008)"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Cleve, R.: Limits on the security of coin flips when half the processors are faulty (extended abstract). In: STOC, pp. 364\u2013369 (1986)","DOI":"10.1145\/12130.12168"},{"key":"4_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1007\/3-540-46766-1_36","volume-title":"Advances in Cryptology - CRYPTO \u201991","author":"I. Damg\u00e5rd","year":"1992","unstructured":"Damg\u00e5rd, I.: Towards Practical Public Key Systems Secure against Chosen Ciphertext Attacks. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol.\u00a0576, pp. 445\u2013456. Springer, Heidelberg (1992)"},{"key":"4_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/11761679_18","volume-title":"Advances in Cryptology - EUROCRYPT 2006","author":"A.W. Dent","year":"2006","unstructured":"Dent, A.W.: The Cramer-Shoup Encryption Scheme Is Plaintext Aware in the Standard Model. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol.\u00a04004, pp. 289\u2013307. Springer, Heidelberg (2006)"},{"key":"4_CR19","unstructured":"Damg\u00e5rd, I., Faust, S., Hazay, C.: Secure two-party computation with low communication. Cryptology ePrint Archive, Report 2011\/508 (2011), http:\/\/eprint.iacr.org\/"},{"issue":"3","key":"4_CR20","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/1236457.1236459","volume":"54","author":"I. Dinur","year":"2007","unstructured":"Dinur, I.: The pcp theorem by gap amplification. J. ACM\u00a054(3), 12 (2007)","journal-title":"J. ACM"},{"key":"4_CR21","unstructured":"Dwork, C., Langberg, M., Naor, M., Nissim, K., Reingold, O.: Succinct np proofs and spooky interactions (2004), http:\/\/www.openu.ac.il\/home\/mikel\/papers\/spooky.ps"},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC, pp. 169\u2013178 (2009)","DOI":"10.1145\/1536414.1536440"},{"key":"4_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/978-3-642-14623-7_25","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"R. Gennaro","year":"2010","unstructured":"Gennaro, R., Gentry, C., Parno, B.: Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.\u00a06223, pp. 465\u2013482. Springer, Heidelberg (2010)"},{"key":"4_CR24","doi-asserted-by":"crossref","unstructured":"Gordon, D., Katz, J., Kolesnikov, V., Malkin, T., Raykov, M., Vahlis, Y.: Secure computation with sublinear amortized work. Cryptology ePrint Archive, Report 2011\/482 (2011)","DOI":"10.1145\/2382196.2382251"},{"key":"4_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/3-540-38424-3_6","volume-title":"Advances in Cryptology - CRYPTO \u201990","author":"S. Goldwasser","year":"1991","unstructured":"Goldwasser, S., Levin, L.A.: Fair Computation of General Functions in Presence of Immoral Majority. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol.\u00a0537, pp. 77\u201393. Springer, Heidelberg (1991)"},{"key":"4_CR26","unstructured":"Goldwasser, S., Lin, H., Rubinstein, A.: Delegation of computation without rejection problem from designated verifier cs-proofs. Cryptology ePrint Archive, Report 2011\/456 (2011)"},{"key":"4_CR27","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":"4_CR28","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Foundations of Cryptography: Basic Applications. Cambridge University Press (2004)","DOI":"10.1017\/CBO9780511721656"},{"key":"4_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/978-3-642-17373-8_19","volume-title":"Advances in Cryptology - ASIACRYPT 2010","author":"J. Groth","year":"2010","unstructured":"Groth, J.: Short Pairing-Based Non-interactive Zero-Knowledge Arguments. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol.\u00a06477, pp. 321\u2013340. Springer, Heidelberg (2010)"},{"key":"4_CR30","unstructured":"Groth, J.: Minimizing non-interactive zero-knowledge proofs using fully homomorphic encryption. Cryptology ePrint Archive, Report 2011\/012 (2011)"},{"key":"4_CR31","doi-asserted-by":"crossref","unstructured":"Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: STOC, pp. 99\u2013108 (2011)","DOI":"10.1145\/1993636.1993651"},{"key":"4_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"408","DOI":"10.1007\/BFb0055744","volume-title":"Advances in Cryptology - CRYPTO \u201998","author":"S. Hada","year":"1998","unstructured":"Hada, S., Tanaka, T.: On the Existence of 3-Round Zero-Knowledge Protocols. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol.\u00a01462, pp. 408\u2013423. Springer, Heidelberg (1998)"},{"key":"4_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1007\/978-3-642-20465-4_23","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2011","author":"Y. Ishai","year":"2011","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Prabhakaran, M., Sahai, A.: Efficient Non-interactive Secure Computation. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol.\u00a06632, pp. 406\u2013425. Springer, Heidelberg (2011)"},{"key":"4_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1007\/978-3-642-14623-7_31","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"Y. Ishai","year":"2010","unstructured":"Ishai, Y., Kushilevitz, E., Paskin, A.: Secure Multiparty Computation with Minimal Interaction. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.\u00a06223, pp. 577\u2013594. Springer, Heidelberg (2010)"},{"key":"4_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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.\u00a05157, pp. 572\u2013591. Springer, Heidelberg (2008)"},{"key":"4_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/978-3-642-00457-5_18","volume-title":"Theory of Cryptography","author":"Y. Ishai","year":"2009","unstructured":"Ishai, Y., Prabhakaran, M., Sahai, A.: Secure Arithmetic Computation with No Honest Majority. In: Reingold, O. (ed.) TCC 2009. LNCS, vol.\u00a05444, pp. 294\u2013314. Springer, Heidelberg (2009)"},{"key":"4_CR37","doi-asserted-by":"crossref","unstructured":"Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: STOC, pp. 723\u2013732 (1992)","DOI":"10.1145\/129712.129782"},{"key":"4_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/978-3-540-72540-4_18","volume-title":"Advances in Cryptology - EUROCRYPT 2007","author":"J. Katz","year":"2007","unstructured":"Katz, J., Koo, C.-Y.: Round-Efficient Secure Computation in Point-to-Point Networks. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol.\u00a04515, pp. 311\u2013328. Springer, Heidelberg (2007)"},{"key":"4_CR39","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Ostrovsky, R.: Replication is not needed: Single database, computationally-private information retrieval. In: FOCS, pp. 364\u2013373 (1997)","DOI":"10.1109\/SFCS.1997.646125"},{"key":"4_CR40","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.\u00a06597, pp. 329\u2013346. Springer, Heidelberg (2011)"},{"key":"4_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/3-540-48184-2_32","volume-title":"Advances in Cryptology - CRYPTO \u201987","author":"R.C. Merkle","year":"1988","unstructured":"Merkle, R.C.: A Digital Signature Based on a Conventional Encryption Function. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol.\u00a0293, pp. 369\u2013378. Springer, Heidelberg (1988)"},{"issue":"4","key":"4_CR42","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1137\/S0097539795284959","volume":"30","author":"S. Micali","year":"2000","unstructured":"Micali, S.: Computationally sound proofs. SIAM J. Comput.\u00a030(4), 1253\u20131298 (2000)","journal-title":"SIAM J. Comput."},{"key":"4_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/978-3-540-45146-4_6","volume-title":"Advances in Cryptology - CRYPTO 2003","author":"M. Naor","year":"2003","unstructured":"Naor, M.: On Cryptographic Assumptions and Challenges. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol.\u00a02729, pp. 96\u2013109. Springer, Heidelberg (2003)"},{"key":"4_CR44","doi-asserted-by":"crossref","unstructured":"Naor, M., Nissim, K.: Communication preserving protocols for secure function evaluation. In: STOC, pp. 590\u2013599 (2001)","DOI":"10.1145\/380752.380855"},{"key":"4_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/978-3-642-00457-5_22","volume-title":"Theory of Cryptography","author":"J.B. Nielsen","year":"2009","unstructured":"Nielsen, J.B., Orlandi, C.: LEGO for Two-Party Secure Computation. In: Reingold, O. (ed.) TCC 2009. LNCS, vol.\u00a05444, pp. 368\u2013386. Springer, Heidelberg (2009)"},{"key":"4_CR46","doi-asserted-by":"crossref","unstructured":"Polishchuk, A., Spielman, D.A.: Nearly-linear size holographic proofs. In: STOC, pp. 194\u2013203 (1994)","DOI":"10.1145\/195058.195132"},{"key":"4_CR47","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/978-3-642-10366-7_15","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2009","author":"B. Pinkas","year":"2009","unstructured":"Pinkas, B., Schneider, T., Smart, N.P., Williams, S.C.: Secure Two-Party Computation is Practical. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol.\u00a05912, pp. 250\u2013267. Springer, Heidelberg (2009)"},{"key":"4_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-642-13190-5_2","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"M. Dijk van","year":"2010","unstructured":"van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully Homomorphic Encryption over the Integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol.\u00a06110, pp. 24\u201343. Springer, Heidelberg (2010)"},{"key":"4_CR49","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","Theory of Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-28914-9_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T08:03:48Z","timestamp":1742630628000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-28914-9_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642289132","9783642289149"],"references-count":49,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-28914-9_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}