{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,27]],"date-time":"2025-04-27T14:46:24Z","timestamp":1745765184242,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662536407"},{"type":"electronic","value":"9783662536414"}],"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_25","type":"book-chapter","created":{"date-parts":[[2016,10,21]],"date-time":"2016-10-21T15:48:14Z","timestamp":1477064894000},"page":"659-689","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Strong Hardness of Privacy from Weak Traitor Tracing"],"prefix":"10.1007","author":[{"given":"Lucas","family":"Kowalczyk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tal","family":"Malkin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan","family":"Ullman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Zhandry","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,10,22]]},"reference":[{"key":"25_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"764","DOI":"10.1007\/978-3-662-49896-5_27","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"S Badrinarayanan","year":"2016","unstructured":"Badrinarayanan, S., Miles, E., Sahai, A., Zhandry, M.: Post-zeroizing obfuscation: new mathematical tools, and the case of evasive circuits. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 764\u2013791. Springer, Heidelberg (2016). doi:\n                      10.1007\/978-3-662-49896-5_27"},{"key":"25_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/978-3-642-40328-6_26","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A Beimel","year":"2013","unstructured":"Beimel, A., Nissim, K., Stemmer, U.: Private learning and sanitization: pure vs. approximate differential privacy. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) APPROX\/RANDOM -2013. LNCS, vol. 8096, pp. 363\u2013378. Springer, Heidelberg (2013). doi:\n                      10.1007\/978-3-642-40328-6_26"},{"key":"25_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1007\/978-3-662-49099-0_20","volume-title":"Theory of Cryptography","author":"M Bellare","year":"2016","unstructured":"Bellare, M., Stepanovs, I., Tessaro, S.: Contention in cryptoland: obfuscation, leakage and UCE. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 542\u2013564. Springer, Heidelberg (2016). doi:\n                      10.1007\/978-3-662-49099-0_20"},{"key":"25_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1007\/978-3-662-49096-9_20","volume-title":"Theory of Cryptography","author":"N Bitansky","year":"2016","unstructured":"Bitansky, N., Paneth, O., Wichs, D.: Perfect structure on the edge of chaos. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9562, pp. 474\u2013502. Springer, Heidelberg (2016). doi:\n                      10.1007\/978-3-662-49096-9_20"},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"Blum, A., Dwork, C., McSherry, F., Nissim, K.: Practical privacy: the SuLQ framework. In: PODS (2005)","DOI":"10.1145\/1065167.1065184"},{"issue":"2","key":"25_CR6","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/2450142.2450148","volume":"60","author":"A Blum","year":"2013","unstructured":"Blum, A., Ligett, K., Roth, A.: A learning theory approach to noninteractive database privacy. J. ACM 60(2), 12 (2013)","journal-title":"J. ACM"},{"key":"25_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/11761679_34","volume-title":"Advances in Cryptology - EUROCRYPT 2006","author":"D Boneh","year":"2006","unstructured":"Boneh, D., Sahai, A., Waters, B.: Fully collusion resistant traitor tracing with short ciphertexts and private keys. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 573\u2013592. Springer, Heidelberg (2006). doi:\n                      10.1007\/11761679_34"},{"key":"25_CR8","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. LNCS, vol. 8616, pp. 480\u2013499. Springer, Heidelberg (2014). doi:\n                      10.1007\/978-3-662-44371-2_27"},{"key":"25_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/978-3-662-44371-2_11","volume-title":"Advances in Cryptology \u2013 CRYPTO 2014","author":"C Brzuska","year":"2014","unstructured":"Brzuska, C., Farshim, P., Mittelbach, A.: Indistinguishability obfuscation and UCEs: the case of computationally unpredictable sources. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 188\u2013205. Springer, Heidelberg (2014). doi:\n                      10.1007\/978-3-662-44371-2_11"},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"Bun, M., Ullman, J., Vadhan, S.P.: Fingerprinting codes and the price of approximate differential privacy. In: STOC (2014)","DOI":"10.1145\/2591796.2591877"},{"key":"25_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/3-540-48658-5_25","volume-title":"Advances in Cryptology \u2014 CRYPTO 94","author":"B Chor","year":"1994","unstructured":"Chor, B., Fiat, A., Naor, M.: Tracing traitors. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 257\u2013270. Springer, Heidelberg (1994). doi:\n                      10.1007\/3-540-48658-5_25"},{"key":"25_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-662-47989-6_12","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"J-S Coron","year":"2015","unstructured":"Coron, J.-S., Gentry, C., Halevi, S., Lepoint, T., Maji, H.K., Miles, E., Raykova, M., Sahai, A., Tibouchi, M.: Zeroizing without low-level zeroes: new MMAP attacks and their limitations. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 247\u2013266. Springer, Heidelberg (2015). doi:\n                      10.1007\/978-3-662-47989-6_12"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"Dinur, I., Nissim, K.: Revealing information while preserving privacy. In: PODS (2003)","DOI":"10.1145\/773153.773173"},{"key":"25_CR14","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:\n                      10.1007\/11681878_14"},{"key":"25_CR15","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 (2009)","DOI":"10.1145\/1536414.1536467"},{"key":"25_CR16","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. 3152, pp. 528\u2013544. Springer, Heidelberg (2004). doi:\n                      10.1007\/978-3-540-28628-8_32"},{"key":"25_CR17","doi-asserted-by":"crossref","unstructured":"Dwork, C., Rothblum, G.N., Vadhan, S.P.: Boosting and differential privacy. In: FOCS. IEEE (2010)","DOI":"10.1109\/FOCS.2010.12"},{"key":"25_CR18","doi-asserted-by":"crossref","unstructured":"Dwork, C., Smith, A.D., Steinke, T., Ullman, J., Vadhan, S.P.: Robust traceability from trace amounts. In: FOCS (2015)","DOI":"10.1109\/FOCS.2015.46"},{"key":"25_CR19","doi-asserted-by":"crossref","unstructured":"Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: FOCS, pp. 40\u201349 (2013)","DOI":"10.1109\/FOCS.2013.13"},{"key":"25_CR20","unstructured":"Garg, S., Mukherjee, P., Srinivasan, A.: Obfuscation without the vulnerabilities of multilinear maps. Cryptology ePrint Archive, Report 2016\/390 (2016). \n                      http:\/\/eprint.iacr.org\/"},{"key":"25_CR21","doi-asserted-by":"crossref","unstructured":"Gentry, C., Lewko, A.B., Sahai, A., Waters, B.: Indistinguishability obfuscation from the multilinear subgroup elimination assumption. In: FOCS (2015)","DOI":"10.1109\/FOCS.2015.19"},{"key":"25_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/978-3-642-28914-9_19","volume-title":"Theory of Cryptography","author":"A Gupta","year":"2012","unstructured":"Gupta, A., Roth, A., Ullman, J.: Iterative constructions and private data release. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 339\u2013356. Springer, Heidelberg (2012). doi:\n                      10.1007\/978-3-642-28914-9_19"},{"key":"25_CR23","doi-asserted-by":"crossref","unstructured":"Hardt, M., Rothblum, G.N.: A multiplicative weights mechanism for privacy-preserving data analysis. In: FOCS (2010)","DOI":"10.1109\/FOCS.2010.85"},{"key":"25_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/978-3-642-55220-5_12","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2014","author":"S Hohenberger","year":"2014","unstructured":"Hohenberger, S., Sahai, A., Waters, B.: Replacing a random oracle: full domain hash from indistinguishability obfuscation. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 201\u2013220. Springer, Heidelberg (2014). doi:\n                      10.1007\/978-3-642-55220-5_12"},{"issue":"6","key":"25_CR25","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1145\/293347.293351","volume":"45","author":"MJ Kearns","year":"1998","unstructured":"Kearns, M.J.: Efficient noise-tolerant learning from statistical queries. J. ACM 45(6), 983\u20131006 (1998)","journal-title":"J. ACM"},{"key":"25_CR26","doi-asserted-by":"crossref","unstructured":"Kowalczyk, L., Malkin, T., Ullman, J., Zhandry, M.: Strong hardness of privacy from weak traitor tracing. IACR Cryptology ePrint Archive 2016\/721 (2016)","DOI":"10.1007\/978-3-662-53641-4_25"},{"key":"25_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1007\/978-3-662-53008-5_22","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"E Miles","year":"2016","unstructured":"Miles, E., Sahai, A., Zhandry, M.: Annihilation attacks for multilinear maps: cryptanalysis of indistinguishability obfuscation over GGH13. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 629\u2013658. Springer, Heidelberg (2016). doi:\n                      10.1007\/978-3-662-53008-5_22"},{"key":"25_CR28","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":"Ilya Mironov","year":"2009","unstructured":"Mironov, Ilya, Pandey, Omkant, Reingold, Omer, Vadhan, Salil: Computational Differential Privacy. In: Halevi, Shai (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 126\u2013142. Springer, Heidelberg (2009). doi:\n                      10.1007\/978-3-642-03356-8_8"},{"key":"25_CR29","doi-asserted-by":"crossref","unstructured":"Nikolov, A., Talwar, K., Zhang, L.: The geometry of differential privacy: the sparse and approximate cases. In: STOC (2013)","DOI":"10.1145\/2488608.2488652"},{"key":"25_CR30","doi-asserted-by":"crossref","unstructured":"Roth, A., Roughgarden, T.: Interactive privacy via the median mechanism. In: STOC, pp. 765\u2013774. ACM, 5\u20138 June 2010","DOI":"10.1145\/1806689.1806794"},{"key":"25_CR31","doi-asserted-by":"crossref","unstructured":"Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: STOC (2014)","DOI":"10.1145\/2591796.2591825"},{"key":"25_CR32","unstructured":"Steinke, T., Ullman, J.: Between pure and approximate differential privacy. CoRR abs\/1501.06095 (2015). \n                      http:\/\/arxiv.org\/abs\/org\/abs\/1501.06095"},{"key":"25_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"810","DOI":"10.1007\/978-3-642-31594-7_68","volume-title":"Automata, Languages, and Programming","author":"J Thaler","year":"2012","unstructured":"Thaler, J., Ullman, J., Vadhan, S.: Faster algorithms for privately releasing marginals. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012. LNCS, vol. 7391, pp. 810\u2013821. Springer, Heidelberg (2012). doi:\n                      10.1007\/978-3-642-31594-7_68"},{"key":"25_CR34","doi-asserted-by":"crossref","unstructured":"Ullman, J.: Answering $$n^{2+o(1)}$$ counting queries with differential privacy is hard. In: STOC (2013)","DOI":"10.1145\/2488608.2488653"},{"key":"25_CR35","doi-asserted-by":"crossref","unstructured":"Ullman, J.: Private multiplicative weights beyond linear queries. In: PODS (2015)","DOI":"10.1145\/2745754.2745755"},{"key":"25_CR36","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:\n                      10.1007\/978-3-642-19571-6_24"}],"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_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,23]],"date-time":"2020-10-23T00:08:32Z","timestamp":1603411712000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53641-4_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662536407","9783662536414"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53641-4_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"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"}]}}