{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T10:48:07Z","timestamp":1778150887682,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662456071","type":"print"},{"value":"9783662456088","type":"electronic"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-45608-8_21","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T10:46:39Z","timestamp":1415961999000},"page":"386-405","source":"Crossref","is-referenced-by-count":4,"title":["Black-Box Separations for Differentially Private Protocols"],"prefix":"10.1007","author":[{"given":"Dakshita","family":"Khurana","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hemanta K.","family":"Maji","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amit","family":"Sahai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"Barak, B., Mahmoody, M.: Merkle puzzles are optimal - an O(n 2)-query attack on any key exchange from a random oracle. In: Halevi (ed.) [17], pp. 374\u2013390","DOI":"10.1007\/978-3-642-03356-8_22"},{"key":"21_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/978-3-540-85174-5_25","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"A. Beimel","year":"2008","unstructured":"Beimel, A., Nissim, K., Omri, E.: Distributed private data analysis: Simultaneously solving how and what. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol.\u00a05157, pp. 451\u2013468. Springer, Heidelberg (2008)"},{"key":"21_CR3","doi-asserted-by":"crossref","unstructured":"Chor, B., Kushilevitz, E.: A zero-one law for boolean privacy (extended abstract). In: Johnson (ed.) [24], pp. 62\u201372.","DOI":"10.1145\/73007.73013"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Coron, J.-S., Patarin, J., Seurin, Y.: The random oracle model and the ideal cipher model are equivalent. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol.\u00a05157, pp. 1\u201320. Springer, Heidelberg (2008)","DOI":"10.1007\/978-3-540-85174-5_1"},{"key":"21_CR5","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 the black-box complexity of optimally-fair coin tossing. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol.\u00a06597, pp. 450\u2013467. Springer, Heidelberg (2011)"},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"Dinur, I., Nissim, K.: Revealing information while preserving privacy. In: Neven, F., Beeri, C., Milo, T. (eds.) PODS, pp. 202\u2013210. ACM (2003)","DOI":"10.1145\/773153.773173"},{"key":"21_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11787006_1","volume-title":"Automata, Languages and Programming","author":"C. Dwork","year":"2006","unstructured":"Dwork, C.: Differential privacy. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04052, pp. 1\u201312. Springer, Heidelberg (2006)"},{"issue":"1","key":"21_CR8","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1145\/1866739.1866758","volume":"54","author":"C. Dwork","year":"2011","unstructured":"Dwork, C.: A firm foundation for private data analysis. Commun. ACM\u00a054(1), 86\u201395 (2011)","journal-title":"Commun. ACM"},{"key":"21_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1007\/11761679_29","volume-title":"Advances in Cryptology - EUROCRYPT 2006","author":"C. Dwork","year":"2006","unstructured":"Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., Naor, M.: Our data, ourselves: Privacy via distributed noise generation. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol.\u00a04004, pp. 486\u2013503. Springer, Heidelberg (2006)"},{"key":"21_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/11681878_14","volume-title":"Theory of Cryptography","author":"C. Dwork","year":"2006","unstructured":"Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol.\u00a03876, pp. 265\u2013284. Springer, Heidelberg (2006)"},{"key":"21_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1007\/978-3-540-28628-8_32","volume-title":"Advances in Cryptology \u2013 CRYPTO 2004","author":"C. Dwork","year":"2004","unstructured":"Dwork, C., Nissim, K.: Privacy-preserving datamining on vertically partitioned databases. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol.\u00a03152, pp. 528\u2013544. Springer, Heidelberg (2004)"},{"issue":"1","key":"21_CR12","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":"21_CR13","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":"21_CR14","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: Aho, A.V. (ed.) STOC, pp. 218\u2013229. ACM (1987)","DOI":"10.1145\/28395.28420"},{"key":"21_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/978-3-642-40041-4_17","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"V. Goyal","year":"2013","unstructured":"Goyal, V., Mironov, I., Pandey, O., Sahai, A.: Accuracy-privacy tradeoffs for two-party differentially private protocols. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol.\u00a08042, pp. 298\u2013315. Springer, Heidelberg (2013)"},{"key":"21_CR16","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":"21_CR17","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology - CRYPTO 2009","year":"2009","unstructured":"Halevi, S. (ed.): CRYPTO 2009. LNCS, vol.\u00a05677. Springer, Heidelberg (2009)"},{"key":"21_CR18","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Pseudo-random generators under uniform assumptions. In: Ortiz (ed.) [34], pp. 395\u2013404.","DOI":"10.1145\/100216.100270"},{"issue":"4","key":"21_CR19","doi-asserted-by":"publisher","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)","journal-title":"SIAM J. Comput."},{"key":"21_CR20","doi-asserted-by":"crossref","unstructured":"Holenstein, T., K\u00fcnzler, R., Tessaro, S.: Equivalence of the random oracle model and the ideal cipher model, revisited. In: STOC (2011)","DOI":"10.1145\/1993636.1993650"},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Levin, L.A., Luby, M.: Pseudo-random generation from one-way functions (extended abstracts). In: Johnson (ed.) [24], pp. 12\u201324","DOI":"10.1145\/73007.73009"},{"key":"21_CR22","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Luby, M.: One-way functions are essential for complexity based cryptography (extended abstract). In: FOCS, pp. 230\u2013235. IEEE (1989)","DOI":"10.1109\/SFCS.1989.63483"},{"key":"21_CR23","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Johnson (ed.) [24], pp. 44\u201361","DOI":"10.1145\/73007.73012"},{"key":"21_CR24","unstructured":"Johnson, D.S. (ed.): Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, Seattle, Washington, USA, May 15-17. ACM (1989)"},{"key":"21_CR25","doi-asserted-by":"crossref","unstructured":"Kahn, J., Saks, M.E., Smyth, C.D.: A dual version of Reimer\u2019s inequality and a proof of Rudich\u2019s conjecture. In: IEEE Conference on Computational Complexity, pp. 98\u2013103 (2000)","DOI":"10.1109\/CCC.2000.856739"},{"key":"21_CR26","unstructured":"Katz, J., Koo, C.-Y.: On constructing universal one-way hash functions from arbitrary one-way functions. IACR Cryptology ePrint Archive, 2005:328 (2005)"},{"key":"21_CR27","doi-asserted-by":"crossref","unstructured":"Mahmoody, M., Maji, H.K., Prabhakaran, M.: Limits of random oracles in secure computation. In: ITCS (2014)","DOI":"10.1145\/2554797.2554801"},{"key":"21_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/978-3-642-54242-8_11","volume-title":"Theory of Cryptography","author":"M. Mahmoody","year":"2014","unstructured":"Mahmoody, M., Maji, H.K., Prabhakaran, M.: On the power of public-key encryption in secure computation. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol.\u00a08349, pp. 240\u2013264. Springer, Heidelberg (2014)"},{"key":"21_CR29","doi-asserted-by":"crossref","unstructured":"Maurer, U.M., Renner, R., Holenstein, C.: Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In: Naor (ed.) [32], pp. 21\u201339","DOI":"10.1007\/978-3-540-24638-1_2"},{"key":"21_CR30","doi-asserted-by":"crossref","unstructured":"McGregor, A., Mironov, I., Pitassi, T., Reingold, O., Talwar, K., Vadhan, S.P.: The limits of two-party differential privacy. In: FOCS, pp. 81\u201390. IEEE Computer Society (2010)","DOI":"10.1109\/FOCS.2010.14"},{"key":"21_CR31","doi-asserted-by":"crossref","unstructured":"Mironov, I., Pandey, O., Reingold, O., Vadhan, S.P.: Computational differential privacy. In: Halevi (ed.) [17], pp. 126\u2013142","DOI":"10.1007\/978-3-642-03356-8_8"},{"key":"21_CR32","series-title":"Lecture Notes in Computer Science","volume-title":"Theory of Cryptography","year":"2004","unstructured":"Naor, M. (ed.): TCC 2004. LNCS, vol.\u00a02951. Springer, Heidelberg (2004)"},{"key":"21_CR33","doi-asserted-by":"crossref","unstructured":"Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: Johnson (ed.) [24], pp. 33\u201343","DOI":"10.1145\/73007.73011"},{"key":"21_CR34","unstructured":"Ortiz, H. (ed.): Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, Baltimore, Maryland, USA, May 13-17. ACM (1990)"},{"key":"21_CR35","doi-asserted-by":"crossref","unstructured":"Reingold, O., Trevisan, L., Vadhan, S.P.: Notions of reducibility between cryptographic primitives. In: Naor (ed.) [32], pp. 1\u201320","DOI":"10.1007\/978-3-540-24638-1_1"},{"key":"21_CR36","doi-asserted-by":"crossref","unstructured":"Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: Ortiz (ed.) [34], pp. 387\u2013394","DOI":"10.1145\/100216.100269"},{"key":"21_CR37","unstructured":"Rudich, S.: Limits on the Provable Consequences of One-way Functions. PhD thesis, University of California at Berkeley (1988)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 ASIACRYPT 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-45608-8_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T17:56:03Z","timestamp":1747158963000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-45608-8_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662456071","9783662456088"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-45608-8_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}