{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T22:24:50Z","timestamp":1748384690230,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642542411"},{"type":"electronic","value":"9783642542428"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-642-54242-8_11","type":"book-chapter","created":{"date-parts":[[2014,2,3]],"date-time":"2014-02-03T02:42:54Z","timestamp":1391395374000},"page":"240-264","source":"Crossref","is-referenced-by-count":7,"title":["On the Power of Public-Key Encryption in Secure Computation"],"prefix":"10.1007","author":[{"given":"Mohammad","family":"Mahmoody","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hemanta K.","family":"Maji","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manoj","family":"Prabhakaran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Johnson, D.S. (ed.) STOC, pp. 44\u201361. ACM (1989)","DOI":"10.1145\/73007.73012"},{"key":"11_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/978-3-642-03356-8_22","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"B. Barak","year":"2009","unstructured":"Barak, B., Mahmoody-Ghidary, M.: Merkle puzzles are optimal - an O(n 2)-query attack on any key exchange from a random oracle. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol.\u00a05677, pp. 374\u2013390. Springer, Heidelberg (2009)"},{"key":"11_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/978-3-642-36594-2_25","volume-title":"Theory of Cryptography","author":"I. Haitner","year":"2013","unstructured":"Haitner, I., Omri, E., Zarosim, H.: Limits on the usefulness of random oracles. In: Sahai, A. (ed.) TCC 2013. LNCS, vol.\u00a07785, pp. 437\u2013456. Springer, Heidelberg (2013)"},{"key":"11_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1007\/978-3-642-19571-6_27","volume-title":"Theory of Cryptography","author":"D. Dachman-Soled","year":"2011","unstructured":"Dachman-Soled, D., Lindell, Y., Mahmoody, M., Malkin, T.: On black-box complexity of optimally-fair coin-tossing. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol.\u00a06597, pp. 450\u2013467. Springer, Heidelberg (2011)"},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"Mahmoody, M., Maji, H.K., Prabhakaran, M.: Limits of random oracles in secure computation. CoRR abs\/1205.3554 (2012); To appear in ITCS 2014","DOI":"10.1145\/2554797.2554801"},{"key":"11_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-24638-1_1","volume-title":"Theory of Cryptography","author":"O. Reingold","year":"2004","unstructured":"Reingold, O., Trevisan, L., Vadhan, S.: Notions of reducibility between cryptographic primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol.\u00a02951, pp. 1\u201320. Springer, Heidelberg (2004)"},{"key":"11_CR7","unstructured":"Maji, H.K., Prabhakaran, M., Rosulek, M.: Cryptographic complexity classes and computational intractability assumptions. In: Yao, A.C.C. (ed.) ICS, pp. 266\u2013289. Tsinghua University Press (2010)"},{"key":"11_CR8","unstructured":"Kushilevitz, E.: Privacy and communication complexity. In: [33], pp. 416\u2013421."},{"key":"11_CR9","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 (1989)"},{"key":"11_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/978-3-642-00457-5_16","volume-title":"Theory of Cryptography","author":"H.K. Maji","year":"2009","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, O. (ed.) TCC 2009. LNCS, vol.\u00a05444, pp. 256\u2013273. Springer, Heidelberg (2009)"},{"key":"11_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-642-34931-7_4","volume-title":"Progress in Cryptology - INDOCRYPT 2012","author":"H.K. Maji","year":"2012","unstructured":"Maji, H.K., Prabhakaran, M., Rosulek, M.: A unified characterization of completeness and triviality for secure function evaluation. In: Galbraith, S., Nandi, M. (eds.) INDOCRYPT 2012. LNCS, vol.\u00a07668, pp. 40\u201359. Springer, Heidelberg (2012)"},{"key":"11_CR12","first-page":"129","volume":"19","author":"I. Haitner","year":"2012","unstructured":"Haitner, I., Omri, E., Zarosim, H.: On the power of random oracles. Electronic Colloquium on Computational Complexity (ECCC)\u00a019, 129 (2012)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"11_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/BFb0054137","volume-title":"Advances in Cryptology - EUROCRYPT \u201998","author":"D.R. Simon","year":"1998","unstructured":"Simon, D.R.: Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol.\u00a01403, pp. 334\u2013345. Springer, Heidelberg (1998)"},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"Gertner, Y., Malkin, T., Reingold, O.: On the impossibility of basing trapdoor functions on trapdoor predicates. In: FOCS, pp. 126\u2013135 (2001)","DOI":"10.1109\/SFCS.2001.959887"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Boneh, D., Papakonstantinou, P.A., Rackoff, C., Vahlis, Y., Waters, B.: On the impossibility of basing identity based encryption on trapdoor permutations. In: FOCS, pp. 283\u2013292. IEEE Computer Society (2008)","DOI":"10.1109\/FOCS.2008.67"},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"Katz, J., Schr\u00f6der, D., Yerukhimovich, A.: Impossibility of blind signatures from one-way permutations. In: [34], pp. 615\u2013629","DOI":"10.1007\/978-3-642-19571-6_37"},{"key":"11_CR17","doi-asserted-by":"crossref","unstructured":"Matsuda, T., Matsuura, K.: On black-box separations among injective one-way functions. In: [34], pp. 597\u2013614","DOI":"10.1007\/978-3-642-19571-6_36"},{"key":"11_CR18","doi-asserted-by":"crossref","unstructured":"Gertner, Y., Kannan, S., Malkin, T., Reingold, O., Viswanathan, M.: The relationship between public key encryption and oblivious transfer. In: FOCS, pp. 325\u2013335. IEEE Computer Society (2000)","DOI":"10.1109\/SFCS.2000.892121"},{"key":"11_CR19","unstructured":"Kim, J.H., Simon, D.R., Tetali, P.: Limits on the efficiency of one-way permutation-based hash functions. In: FOCS, pp. 535\u2013542 (1999)"},{"issue":"1","key":"11_CR20","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1137\/S0097539704443276","volume":"35","author":"R. Gennaro","year":"2005","unstructured":"Gennaro, R., Gertner, Y., Katz, J., Trevisan, L.: Bounds on the efficiency of generic cryptographic constructions. SIAM J. Comput.\u00a035(1), 217\u2013246 (2005)","journal-title":"SIAM J. Comput."},{"key":"11_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/978-3-540-30576-7_3","volume-title":"Theory of Cryptography","author":"H. Lin","year":"2005","unstructured":"Lin, H., Trevisan, L., Wee, H.: On hardness amplification of one-way functions. In: Kilian, J. (ed.) TCC 2005. LNCS, vol.\u00a03378, pp. 34\u201349. Springer, Heidelberg (2005)"},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Haitner, I., Hoch, J.J., Reingold, O., Segev, G.: Finding collisions in interactive protocols - a tight lower bound on the round complexity of statistically-hiding commitments. In: FOCS, pp. 669\u2013679. IEEE Computer Society (2007)","DOI":"10.1109\/FOCS.2007.7"},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"Barak, B., Mahmoody, M.: Lower bounds on signatures from symmetric primitives. In: FOCS: IEEE Symposium on Foundations of Computer Science, FOCS (2007)","DOI":"10.1109\/FOCS.2007.4389536"},{"key":"11_CR24","unstructured":"Impagliazzo, R., Luby, M.: One-way functions are essential for complexity based cryptography (extended abstract). In: [34], pp. 230\u2013235"},{"key":"11_CR25","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R.: One-way functions, hard on average problems, and statistical zero-knowledge proofs. In: Structure in Complexity Theory Conference, pp. 133\u2013138 (1991)","DOI":"10.1109\/SCT.1991.160253"},{"key":"11_CR26","unstructured":"Ostrovsky, R., Wigderson, A.: One-way functions are essential for non-trivial zero-knowledge. Technical Report TR-93-073, International Computer Science Institute, Preliminary version in Proc. 2nd Israeli Symp. on Theory of Computing and Systems, 1993, pp. 3\u201317, Berkeley, CA (November 1993)"},{"key":"11_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/978-3-540-78524-8_23","volume-title":"Theory of Cryptography","author":"I. Haitner","year":"2008","unstructured":"Haitner, I.: Semi-honest to malicious oblivious transfer - the black-box way. In: Canetti, R. (ed.) TCC 2008. LNCS, vol.\u00a04948, pp. 412\u2013426. Springer, Heidelberg (2008)"},{"issue":"3","key":"11_CR28","doi-asserted-by":"publisher","first-page":"1153","DOI":"10.1137\/080725404","volume":"39","author":"I. Haitner","year":"2009","unstructured":"Haitner, I., Nguyen, M.H., Ong, S.J., Reingold, O., Vadhan, S.P.: Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function. SIAM J. Comput.\u00a039(3), 1153\u20131218 (2009)","journal-title":"SIAM J. Comput."},{"key":"11_CR29","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":"11_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/978-3-642-34961-4_9","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2012","author":"Y. Lindell","year":"2012","unstructured":"Lindell, Y., Omri, E., Zarosim, H.: Completeness for symmetric two-party functionalities - revisited. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol.\u00a07658, pp. 116\u2013133. Springer, Heidelberg (2012)"},{"key":"11_CR31","unstructured":"Haitner, I.: Personal communication (January 21, 2013)"},{"key":"11_CR32","first-page":"137","volume":"20","author":"M. Mahmoody","year":"2013","unstructured":"Mahmoody, M., Maji, H.K., Prabhakaran, M.: On the power of public-key encryption in secure computation. Electronic Colloquium on Computational Complexity (ECCC)\u00a020, 137 (2013)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"11_CR33","unstructured":"30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October-1 November (1989); In: FOCS. IEEE (1989)"},{"key":"11_CR34","series-title":"Lecture Notes in Computer Science","volume-title":"Theory of Cryptography","year":"2011","unstructured":"Ishai, Y. (ed.): TCC 2011. LNCS, vol.\u00a06597. Springer, Heidelberg (2011)"}],"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-54242-8_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T19:09:06Z","timestamp":1746126546000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-54242-8_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783642542411","9783642542428"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-54242-8_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}