{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T04:26:52Z","timestamp":1778128012996,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642146220","type":"print"},{"value":"9783642146237","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14623-7_32","type":"book-chapter","created":{"date-parts":[[2010,8,10]],"date-time":"2010-08-10T08:15:26Z","timestamp":1281428126000},"page":"595-612","source":"Crossref","is-referenced-by-count":23,"title":["A Zero-One Law for Cryptographic Complexity with Respect to Computational UC Security"],"prefix":"10.1007","author":[{"given":"Hemanta K.","family":"Maji","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manoj","family":"Prabhakaran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mike","family":"Rosulek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"32_CR1","unstructured":"Proc. 30th FOCS. IEEE, Los Alamitos (1989)"},{"key":"32_CR2","first-page":"65","volume-title":"Proceedings of DIMACS Workshop on Distributed Computing and Cryptography","author":"D. Beaver","year":"1989","unstructured":"Beaver, D.: Perfect privacy for two-party protocols. In: Feigenbaum, J., Merritt, M. (eds.) Proceedings of DIMACS Workshop on Distributed Computing and Cryptography, vol.\u00a02, pp. 65\u201377. American Mathematical Society, Providence (1989)"},{"key":"32_CR3","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. (ed.) CRYPTO 1999. LNCS, vol.\u00a01666, pp. 80\u201397. Springer, Heidelberg (1999)"},{"key":"32_CR4","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\u201d availabe at the ECCC archive TR01-016. Extended abstract in FOCS (2001)"},{"key":"32_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/3-540-44647-8_2","volume-title":"Advances in Cryptology - CRYPTO 2001","author":"R. Canetti","year":"2001","unstructured":"Canetti, R., Fischlin, M.: Universally composable commitments. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol.\u00a02139, p. 19. Springer, Heidelberg (2001)"},{"key":"32_CR6","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)"},{"key":"32_CR7","first-page":"494","volume-title":"Proc. 34th STOC","author":"R. Canetti","year":"2002","unstructured":"Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable twoparty computation. In: Proc. 34th STOC, pp. 494\u2013503. ACM, New York (2002)"},{"key":"32_CR8","first-page":"62","volume-title":"STOC","author":"B. Chor","year":"1989","unstructured":"Chor, B., Kushilevitz, E.: A zero-one law for boolean privacy (extended abstract). In: STOC, pp. 62\u201372. ACM, New York (1989)"},{"key":"32_CR9","doi-asserted-by":"crossref","unstructured":"Damg\u00e5rd, I., Nielsen, J.B., Orlandi, C.: On the necessary and sufficient assumptions for UC computation. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol.\u00a05978, pp. 109\u2013127. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-11799-2_8"},{"key":"32_CR10","unstructured":"Goldreich, O.: Foundations of Cryptography: Basic Tools. Cambridge University Press, Cambridge (2001), Earlier version available on, http:\/\/www.wisdom.weizmann.ac.il\/~oded\/frag.html"},{"key":"32_CR11","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511721656","volume-title":"Foundations of Cryptography: Basic Applications","author":"O. Goldreich","year":"2004","unstructured":"Goldreich, O.: Foundations of Cryptography: Basic Applications. Cambridge University Press, Cambridge (2004)"},{"key":"32_CR12","doi-asserted-by":"crossref","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), See 11, Chap. 7 for more details","DOI":"10.1145\/28395.28420"},{"issue":"4","key":"32_CR13","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"},{"issue":"4","key":"32_CR14","doi-asserted-by":"crossref","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput.\u00a028(4), 1364\u20131396 (1999); Preliminary versions appeared in STOC 1989 and STOC 1990","journal-title":"SIAM J. Comput."},{"key":"32_CR15","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R.: A personal view of average-case complexity. In: Structure in Complexity Theory Conference, pp. 134\u2013147 (1995)","DOI":"10.1109\/SCT.1995.514853"},{"key":"32_CR16","unstructured":"Impagliazzo, R., Luby, M.: One-way functions are essential for complexity based cryptography (extended abstract). In: Proc. 30th FOCS [1], pp. 230\u2013235"},{"key":"32_CR17","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Prabhakaran, M., Sahai, A.: Founding cryptography on oblivious transfer - efficiently. In: Wagner (ed.) [32], pp. 572\u2013591","DOI":"10.1007\/978-3-540-85174-5_32"},{"key":"32_CR18","first-page":"20","volume-title":"STOC","author":"J. Kilian","year":"1988","unstructured":"Kilian, J.: Founding cryptography on oblivious transfer. In: STOC, pp. 20\u201331. ACM, New York (1988)"},{"key":"32_CR19","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":"32_CR20","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":"32_CR21","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":"32_CR22","unstructured":"Kraschewski, D., M\u00fcller-Quade, J.: Completeness theorems with constructive proofs for symmetric, asymmetric and general 2-party-functions, 2008 (2008) (Unpublished Manuscript), http:\/\/iks.ira.uka.de\/eiss\/completeness"},{"key":"32_CR23","doi-asserted-by":"crossref","unstructured":"K\u00fcnzler, R., M\u00fcller-Quade, J., Raub, D.: Secure computability of functions in the it setting with dishonest majority and applications to long-term security (2009)","DOI":"10.1007\/978-3-642-00457-5_15"},{"key":"32_CR24","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E.: Privacy and communication complexity. In: FOCS [1], pp. 416\u2013421","DOI":"10.1109\/SFCS.1989.63512"},{"key":"32_CR25","doi-asserted-by":"crossref","unstructured":"Maji, H.K., Prabhakaran, M., Rosulek, M.: Complexity of multi-party computation problems: The case of 2-party symmetric secure function evaluation. In: Reingold (ed.) [31], pp. 256\u2013273","DOI":"10.1007\/978-3-642-00457-5_16"},{"key":"32_CR26","first-page":"266","volume-title":"Innovations in Computer Science","author":"H.K. Maji","year":"2010","unstructured":"Maji, H.K., Prabhakaran, M., Rosulek, M.: Cryptographic complexity classes and computational intractability assumptions. In: Yao, A.C.-C. (ed.) Innovations in Computer Science, pp. 266\u2013289. Tsinghua University Press, Beijing (2010)"},{"key":"32_CR27","unstructured":"Naor, M.: Bit commitment using pseudorandomness 4(2), 151\u2013158 (1991), Brassard, G. (ed.) CRYPTO 1989. LNCS, vol.\u00a0435, pp. 128\u2013136. Springer, Heidelberg (1990)"},{"key":"32_CR28","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1145\/1132516.1132559","volume-title":"STOC","author":"M.-H. Nguyen","year":"2006","unstructured":"Nguyen, M.-H., Vadhan, S.P.: Zero knowledge with efficient provers. In: STOC, pp. 287\u2013295. ACM, New York (2006)"},{"key":"32_CR29","unstructured":"Prabhakaran, M.: New Notions of Security. PhD thesis, Department of Computer Science, Princeton University (2005)"},{"key":"32_CR30","doi-asserted-by":"crossref","unstructured":"Prabhakaran, M., Rosulek, M.: Cryptographic complexity of multi-party computation problems: Classifications and separations. In: Wagner (ed.) [32], pp. 262\u2013279","DOI":"10.1007\/978-3-540-85174-5_15"},{"key":"32_CR31","series-title":"Lecture Notes in Computer Science","volume-title":"Theory of Cryptography","year":"2009","unstructured":"Reingold, O. (ed.): TCC 2009. LNCS, vol.\u00a05444. Springer, Heidelberg (2009)"},{"key":"32_CR32","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","year":"2008","unstructured":"Wagner, D. (ed.): CRYPTO 2008. LNCS, vol.\u00a05157. Springer, Heidelberg (2008)"},{"key":"32_CR33","first-page":"162","volume-title":"Proc. 27th FOCS","author":"A.C. Yao","year":"1986","unstructured":"Yao, A.C.: How to generate and exchange secrets. In: Proc. 27th FOCS, pp. 162\u2013167. IEEE, Los Alamitos (1986)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14623-7_32.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T18:40:58Z","timestamp":1685731258000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14623-7_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642146220","9783642146237"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14623-7_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}