{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T16:47:37Z","timestamp":1738342057190,"version":"3.35.0"},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540851738"},{"type":"electronic","value":"9783540851745"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85174-5_15","type":"book-chapter","created":{"date-parts":[[2008,8,20]],"date-time":"2008-08-20T12:32:02Z","timestamp":1219235522000},"page":"262-279","source":"Crossref","is-referenced-by-count":23,"title":["Cryptographic Complexity of Multi-Party Computation Problems: Classifications and Separations"],"prefix":"10.1007","author":[{"given":"Manoj","family":"Prabhakaran","sequence":"first","affiliation":[]},{"given":"Mike","family":"Rosulek","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"15_CR1","unstructured":"Proc. 20th STOC. ACM (1988)"},{"key":"15_CR2","unstructured":"Proc. 21st STOC. ACM (1989)"},{"key":"15_CR3","first-page":"186","volume-title":"FOCS","author":"B. Barak","year":"2004","unstructured":"Barak, B., Canetti, R., Nielsen, J.B., Pass, R.: Universally composable protocols with relaxed set-up assumptions. In: FOCS, pp. 186\u2013195. IEEE, Los Alamitos (2004)"},{"key":"15_CR4","volume-title":"Proc. 47th FOCS","author":"B. Barak","year":"2006","unstructured":"Barak, B., Prabhakaran, M., Sahai, A.: Concurrent non-malleable zero knowledge. In: Proc. 47th FOCS. IEEE, Los Alamitos (2006)"},{"key":"15_CR5","volume-title":"Proc. 46th FOCS","author":"B. Barak","year":"2005","unstructured":"Barak, B., Sahai, A.: How to play almost any mental game over the net - concurrent composition using super-polynomial simulation. In: Proc. 46th FOCS. IEEE, Los Alamitos (2005)"},{"key":"15_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1007\/3-540-48405-1_6","volume-title":"Advances in Cryptology - CRYPTO \u201999","author":"A. Beimel","year":"1999","unstructured":"Beimel, A., Malkin, T., Micali, S.: The all-or-nothing nature of two-party secure computation. In: Wiener, M.J. (ed.) CRYPTO 1999. LNCS, vol.\u00a01666, pp. 80\u201397. Springer, Heidelberg (1999)"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proc. 20th STOC [1], pp. 1\u201310","DOI":"10.1145\/62212.62213"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. Cryptology ePrint Archive, Report 2000\/067. Revised version of [9]","DOI":"10.1109\/SFCS.2001.959888"},{"key":"15_CR9","unstructured":"Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. Electronic Colloquium on Computational Complexity (ECCC) TR01-016 (2001). Previous version A unified framework for analyzing security of protocols, availabe at the ECCC archive TR01-016. Extended abstract in FOCS 2001 (2001)"},{"key":"15_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70936-7_4","volume-title":"Theory of Cryptography","author":"R. Canetti","year":"2007","unstructured":"Canetti, R., Dodis, Y., Pass, R., Walfish, S.: Universally composable security with global setup. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol.\u00a04392. Springer, Heidelberg (2007)"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"Canetti, R., Fischlin, M.: Universally composable commitments. Report 2001\/055, Cryptology ePrint Archive, July 2001. Extended abstract appeared in CRYPTO 2001 (2001)","DOI":"10.1007\/3-540-44647-8_2"},{"key":"15_CR12","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology \u2013 EUROCRPYT 2003","author":"R. Canetti","year":"2003","unstructured":"Canetti, R., Kushilevitz, E., Lindell, Y.: On the limitations of universally composable two-party computation without set-up assumptions. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol.\u00a02656. Springer, Heidelberg (2003)"},{"issue":"2","key":"15_CR13","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/s00145-005-0419-9","volume":"19","author":"R. Canetti","year":"2006","unstructured":"Canetti, R., Kushilevitz, E., Lindell, Y.: On the limitations of universally composable two-party computation without set-up assumptions. J. Cryptology\u00a019(2), 135\u2013167 (2006)","journal-title":"J. Cryptology"},{"key":"15_CR14","first-page":"494","volume-title":"Proc. 34th STOC","author":"R. Canetti","year":"2002","unstructured":"Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party computation. In: Proc. 34th STOC, pp. 494\u2013503. ACM, New York (2002)"},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"Chaum, D., Cr\u00e9peau, C., Damg\u00e5rd, I.: Multiparty unconditionally secure protocols. In: Proc. 20th STOC [1], pp. 11\u201319","DOI":"10.1145\/62212.62214"},{"issue":"1","key":"15_CR16","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1006\/inco.2000.3013","volume":"167","author":"B. Chor","year":"2001","unstructured":"Chor, B., Ishai, Y.: On privacy and partition arguments. Information and Computation\u00a0167(1), 2\u20139 (2001)","journal-title":"Information and Computation"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"Chor, B., Kushilevitz, E.: A zero-one law for boolean privacy (extended abstract). In: STOC [2], pp. 62\u201372","DOI":"10.1145\/73007.73013"},{"issue":"1","key":"15_CR18","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1137\/0404004","volume":"4","author":"B. Chor","year":"1991","unstructured":"Chor, B., Kushilevitz, E.: A zero-one law for boolean privacy. SIAM J. Discrete Math.\u00a04(1), 36\u201347 (1991)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"15_CR19","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1145\/42282.42283","volume":"35","author":"C. Dwork","year":"1988","unstructured":"Dwork, C., Lynch, N.A., Stockmeyer, L.J.: Consensus in the presence of partial synchrony. J. ACM\u00a035(2), 288\u2013323 (1988)","journal-title":"J. ACM"},{"key":"15_CR20","first-page":"218","volume-title":"Proc. 19th STOC","author":"O. Goldreich","year":"1987","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: How to play ANY mental game. In: ACM (ed.) Proc. 19th STOC, pp. 218\u2013229. ACM, New York (1987)"},{"key":"15_CR21","doi-asserted-by":"crossref","unstructured":"Harnik, D., Ishai, Y., Kushilevitz, E., Nielsen, J.B.: Ot-combiners via secure computation. In: TCC 2008 (to appear, 2008)","DOI":"10.1007\/978-3-540-78524-8_22"},{"issue":"4","key":"15_CR22","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/s00145-006-0346-4","volume":"19","author":"D. Harnik","year":"2006","unstructured":"Harnik, D., Naor, M., Reingold, O., Rosen, A.: Completeness in two-party secure computation: A computational view. J. Cryptology\u00a019(4), 521\u2013552 (2006)","journal-title":"J. Cryptology"},{"key":"15_CR23","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1145\/1250790.1250794","volume-title":"STOC","author":"Y. Ishai","year":"2007","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: STOC, pp. 21\u201330. ACM, New York (2007)"},{"key":"15_CR24","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1145\/1060590.1060687","volume-title":"STOC","author":"Y.T. Kalai","year":"2005","unstructured":"Kalai, Y.T., Lindell, Y., Prabhakaran, M.: Concurrent general composition of secure protocols in the timing model. In: STOC, pp. 644\u2013653. ACM, New York (2005)"},{"key":"15_CR25","unstructured":"Kidron, D., Lindell, Y.: Impossibility results for universal composability in public-key models and with fixed inputs. Cryptology ePrint Archive, Report 2007\/478 (2007), http:\/\/eprint.iacr.org\/2007\/478"},{"key":"15_CR26","doi-asserted-by":"crossref","unstructured":"Kilian, J.: Founding cryptography on oblivious transfer. In: STOC, pp. 20\u201331 (1988)","DOI":"10.1145\/62212.62215"},{"key":"15_CR27","first-page":"553","volume-title":"STOC","author":"J. Kilian","year":"1991","unstructured":"Kilian, J.: A general completeness theorem for two-party games. In: STOC, pp. 553\u2013560. ACM, New York (1991)"},{"key":"15_CR28","first-page":"316","volume-title":"Proc. 32th STOC","author":"J. Kilian","year":"2000","unstructured":"Kilian, J.: More general completeness theorems for secure two-party computation. In: Proc. 32th STOC, pp. 316\u2013324. ACM, New York (2000)"},{"issue":"4","key":"15_CR29","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.1137\/S0097539797321742","volume":"29","author":"J. Kilian","year":"2000","unstructured":"Kilian, J., Kushilevitz, E., Micali, S., Ostrovsky, R.: Reducibility and completeness in private computations. SIAM J. Comput.\u00a029(4), 1189\u20131208 (2000)","journal-title":"SIAM J. Comput."},{"key":"15_CR30","first-page":"416","volume-title":"FOCS","author":"E. Kushilevitz","year":"1989","unstructured":"Kushilevitz, E.: Privacy and communication complexity. In: FOCS, pp. 416\u2013421. IEEE, Los Alamitos (1989)"},{"issue":"2","key":"15_CR31","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1137\/0405021","volume":"5","author":"E. Kushilevitz","year":"1992","unstructured":"Kushilevitz, E.: Privacy and communication complexity. SIAM J. Discrete Math.\u00a05(2), 273\u2013284 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"15_CR32","first-page":"478","volume-title":"FOCS","author":"E. Kushilevitz","year":"1994","unstructured":"Kushilevitz, E., Micali, S., Ostrovsky, R.: Reducibility and completeness in multi-party private computations. In: FOCS, pp. 478\u2013489. IEEE, Los Alamitos (1994)"},{"key":"15_CR33","volume-title":"Proc. 44th FOCS","author":"Y. Lindell","year":"2003","unstructured":"Lindell, Y.: General composition and universal composability in secure multi-party computation. In: Proc. 44th FOCS. IEEE, Los Alamitos (2003)"},{"key":"15_CR34","series-title":"Lecture Notes in Computer Science","volume-title":"Theory of Cryptography","author":"Y. Lindell","year":"2004","unstructured":"Lindell, Y.: Lower bounds for concurrent self composition. In: Naor, M. (ed.) TCC 2004. LNCS, vol.\u00a02951, Springer, Heidelberg (2004)"},{"key":"15_CR35","doi-asserted-by":"crossref","unstructured":"Pfitzmann, B., Waidner, M.: Composition and integrity preservation of secure reactive systems. In: ACM Conference on Computer and Communications Security, pp. 245\u2013254 (2000)","DOI":"10.1145\/352600.352639"},{"key":"15_CR36","unstructured":"Prabhakaran, M.: New Notions of Security. PhD thesis, Department of Computer Science, Princeton University (2005)"},{"key":"15_CR37","unstructured":"Prabhakaran, M., Rosulek, M.: Cryptographic complexity of multi-party computation problems: Classifications and separations. Electronic Colloquium on Computational Complexity (ECCC)\u00a015(50) (2008)"},{"key":"15_CR38","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1145\/1007352.1007394","volume-title":"STOC","author":"M. Prabhakaran","year":"2004","unstructured":"Prabhakaran, M., Sahai, A.: New notions of security: achieving universal composability without trusted setup. In: STOC, pp. 242\u2013251. ACM, New York (2004)"},{"key":"15_CR39","doi-asserted-by":"crossref","unstructured":"Rabin, T., Ben-Or, M.: Verifiable secret sharing and multiparty protocols with honest majority. In: Proc. 21st STOC [2], pp. 73\u201385","DOI":"10.1145\/73007.73014"},{"key":"15_CR40","first-page":"160","volume-title":"Proc. 23rd FOCS","author":"A.C. Yao","year":"1982","unstructured":"Yao, A.C.: Protocols for secure computation. In: Proc. 23rd FOCS, pp. 160\u2013164. IEEE, Los Alamitos (1982)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2008"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85174-5_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T15:58:04Z","timestamp":1738339084000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85174-5_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540851738","9783540851745"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85174-5_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}