{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T17:06:38Z","timestamp":1767978398802,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662536407","type":"print"},{"value":"9783662536414","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53641-4_23","type":"book-chapter","created":{"date-parts":[[2016,10,21]],"date-time":"2016-10-21T15:48:14Z","timestamp":1477064894000},"page":"607-634","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Separating Computational and Statistical Differential Privacy in the Client-Server Model"],"prefix":"10.1007","author":[{"given":"Mark","family":"Bun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi-Hsiu","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Salil","family":"Vadhan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,10,22]]},"reference":[{"key":"23_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/3-540-46035-7_6","volume-title":"Advances in Cryptology - EUROCRYPT 2002","author":"JH An","year":"2002","unstructured":"An, J.H., Dodis, Y., Rabin, T.: On the security of joint signature and encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 83\u2013107. Springer, Heidelberg (2002). doi: 10.1007\/3-540-46035-7_6"},{"key":"23_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. 5157, pp. 451\u2013468. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-85174-5_25"},{"key":"23_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/978-3-662-46497-7_16","volume-title":"Theory of Cryptography","author":"N Bitansky","year":"2015","unstructured":"Bitansky, N., Paneth, O.: ZAPs and non-interactive witness indistinguishability from indistinguishability obfuscation. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 401\u2013427. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-46497-7_16"},{"key":"23_CR4","unstructured":"Balcer, V., Vadhan, S.: Efficient algorithms for differentially private histograms with worst-case accuracy over large domains (2016). Manuscript"},{"key":"23_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1007\/978-3-662-44371-2_27","volume-title":"Advances in Cryptology \u2013 CRYPTO 2014","author":"D Boneh","year":"2014","unstructured":"Boneh, D., Zhandry, M.: Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 480\u2013499. Springer, Heidelberg (2014). doi: 10.1007\/978-3-662-44371-2_27"},{"key":"23_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-662-49096-9_8","volume-title":"Theory of Cryptography","author":"M Bun","year":"2016","unstructured":"Bun, M., Zhandry, M.: Order-revealing encryption and the hardness of private learning. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016-A. LNCS, vol. 9562, pp. 176\u2013206. Springer, Heidelberg (2016). doi: 10.1007\/978-3-662-49096-9_8"},{"key":"23_CR7","doi-asserted-by":"crossref","unstructured":"Canetti, R., Goldreich, O., Goldwasser, S., Micali, S.: Resettable zero-knowledge. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 235\u2013244. ACM (2000)","DOI":"10.1145\/335305.335334"},{"key":"23_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/978-3-642-32946-3_15","volume-title":"Financial Cryptography and Data Security","author":"T-HH Chan","year":"2012","unstructured":"Chan, T.-H.H., Shi, E., Song, D.: Privacy-preserving stream aggregation with fault tolerance. In: Keromytis, A.D. (ed.) FC 2012. LNCS, vol. 7397, pp. 200\u2013214. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-32946-3_15"},{"key":"23_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/3-540-45022-X_38","volume-title":"Automata, Languages and Programming","author":"A Santis","year":"2000","unstructured":"Santis, A., Crescenzo, G., Persiano, G.: Necessary and sufficient assumptions for non-interactive zero-knowledge proofs of knowledge for all NP relations. In: Montanari, U., Rolim, J.D.P., Welzl, E. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 451\u2013462. Springer, Heidelberg (2000). doi: 10.1007\/3-540-45022-X_38"},{"key":"23_CR10","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. 4004, pp. 486\u2013503. Springer, Heidelberg (2006). doi: 10.1007\/11761679_29"},{"key":"23_CR11","doi-asserted-by":"crossref","unstructured":"Dwork, C., Lei, J.: Differential privacy and robust statistics. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, 31 May\u20132 June 2009, pp. 371\u2013380 (2009)","DOI":"10.1145\/1536414.1536466"},{"key":"23_CR12","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. 3876, pp. 265\u2013284. Springer, Heidelberg (2006). doi: 10.1007\/11681878_14"},{"issue":"6","key":"23_CR13","doi-asserted-by":"publisher","first-page":"1513","DOI":"10.1137\/S0097539703426817","volume":"36","author":"C Dwork","year":"2007","unstructured":"Dwork, C., Naor, M.: Zaps, their applications. SIAM J. Comput. 36(6), 1513\u20131543 (2007). Preliminary version in FOCS 2000","journal-title":"SIAM J. Comput."},{"key":"23_CR14","doi-asserted-by":"crossref","unstructured":"Dwork, C., Naor, M., Reingold, O., Rothblum, G.N., Vadhan, S.P.: On the complexity of differentially private data release: efficient algorithms and hardness results. In: STOC, pp. 381\u2013390 (2009)","DOI":"10.1145\/1536414.1536467"},{"key":"23_CR15","doi-asserted-by":"crossref","unstructured":"De Santis, A., Persiano, G.: Zero-knowledge proofs of knowledge without interaction (extended abstract). In: 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, 24\u201327 October 1992, pp. 427\u2013436 (1992)","DOI":"10.1109\/SFCS.1992.267809"},{"issue":"3\u20134","key":"23_CR16","first-page":"211","volume":"9","author":"C Dwork","year":"2014","unstructured":"Dwork, C., Roth, A.: The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci. 9(3\u20134), 211\u2013407 (2014)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"1","key":"23_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539792230010","volume":"29","author":"U Feige","year":"1999","unstructured":"Feige, U., Lapidot, D., Shamir, A.: Multiple noninteractive zero knowledge proofs under general assumptions. SIAM J. Comput. 29(1), 1\u201328 (1999)","journal-title":"SIAM J. Comput."},{"key":"23_CR18","doi-asserted-by":"crossref","unstructured":"Feige, U., Shamir, A.: Witness indistinguishable and witness hiding protocols. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, STOC 1990, pp. 416\u2013426. ACM, New York (1990)","DOI":"10.1145\/100216.100272"},{"key":"23_CR19","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: Proceedings of 44th Symposium on Foundations of Computer Science (FOCS 2003), 11\u201314 October 2003, Cambridge, pp. 534\u2013543 (2003)","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"23_CR20","unstructured":"Goyal, V., Khurana, D., Mironov, I., Pandey, O., Sahai, A.: Do distributed differentially-private protocols require oblivious transfer? In: 43rd International Colloquium Automata, Languages, and Programming, ICALp 2016, Rome, 12\u201315 July 2016, Proceedings, Part I (2016, to appear)"},{"key":"23_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/978-3-642-19571-6_25","volume-title":"Theory of Cryptography","author":"A Groce","year":"2011","unstructured":"Groce, A., Katz, J., Yerukhimovich, A.: Limits of computational differential privacy in the client\/server setting. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 417\u2013431. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-19571-6_25"},{"key":"23_CR22","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. 8042, pp. 298\u2013315. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-40041-4_17"},{"key":"23_CR23","doi-asserted-by":"publisher","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)"},{"issue":"3","key":"23_CR24","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/2220357.2220358","volume":"59","author":"J Groth","year":"2012","unstructured":"Groth, J., Ostrovsky, R., Sahai, A.: New techniques for noninteractive zero-knowledge. J. ACM (JACM) 59(3), 11 (2012)","journal-title":"J. ACM (JACM)"},{"key":"23_CR25","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. 7785, pp. 437\u2013456. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-36594-2_25"},{"key":"23_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)"},{"issue":"3","key":"23_CR27","doi-asserted-by":"publisher","first-page":"793","DOI":"10.1137\/090756090","volume":"40","author":"SP Kasiviswanathan","year":"2011","unstructured":"Kasiviswanathan, S.P., Lee, H.K., Nissim, K., Raskhodnikova, S., Smith, A.D.: What can we learn privately? SIAM J. Comput. 40(3), 793\u2013826 (2011)","journal-title":"SIAM J. Comput."},{"key":"23_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1007\/978-3-662-45608-8_21","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2014","author":"D Khurana","year":"2014","unstructured":"Khurana, D., Maji, H.K., Sahai, A.: Black-box separations for differentially private protocols. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 386\u2013405. Springer, Heidelberg (2014). doi: 10.1007\/978-3-662-45608-8_21"},{"key":"23_CR29","doi-asserted-by":"crossref","unstructured":"McGregor, A., Mironov, I., Pitassi, T., Reingold, O., Talwar, K., Vadhan, S.: The limits of two-party differential privacy. In: 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 81\u201390. IEEE (2010)","DOI":"10.1109\/FOCS.2010.14"},{"key":"23_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/978-3-642-03356-8_8","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"I Mironov","year":"2009","unstructured":"Mironov, I., Pandey, O., Reingold, O., Vadhan, S.: Computational differential privacy. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 126\u2013142. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-03356-8_8"},{"key":"23_CR31","doi-asserted-by":"crossref","unstructured":"Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, STOC 1989, pp. 33\u201343. ACM, New York (1989)","DOI":"10.1145\/73007.73011"},{"key":"23_CR32","doi-asserted-by":"crossref","unstructured":"Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, STOC 1990, pp. 387\u2013394. ACM, New York (1990)","DOI":"10.1145\/100216.100269"},{"key":"23_CR33","unstructured":"Thakurta, A., Smith, A.D.: Differentially private feature selection via stability arguments, and the robustness of the Lasso. In: The 26th Annual Conference on Learning Theory. COLT 2013, 12\u201314 June 2013, Princeton University, pp. 819\u2013850 (2013)"},{"key":"23_CR34","doi-asserted-by":"crossref","unstructured":"Ullman, J.: Answering $$n^{2+ o (1)}$$ counting queries with differential privacy is hard. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 361\u2013370. ACM (2013)","DOI":"10.1145\/2488608.2488653"},{"key":"23_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1007\/978-3-642-19571-6_24","volume-title":"Theory of Cryptography","author":"J Ullman","year":"2011","unstructured":"Ullman, J., Vadhan, S.: PCPs and the hardness of generating private synthetic data. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 400\u2013416. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-19571-6_24"},{"key":"23_CR36","unstructured":"Vadhan, S.: The complexity of differential privacy (2016). http:\/\/privacytools.seas.harvard.edu\/publications\/complexity-differential-privacy"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53641-4_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T19:17:22Z","timestamp":1749669442000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53641-4_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662536407","9783662536414"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53641-4_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 October 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TCC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Theory of Cryptography Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Beijing","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 November 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 November 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}