{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T11:45:33Z","timestamp":1777376733043,"version":"3.51.4"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319968773","type":"print"},{"value":"9783319968780","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-96878-0_12","type":"book-chapter","created":{"date-parts":[[2018,7,23]],"date-time":"2018-07-23T12:53:57Z","timestamp":1532350437000},"page":"335-364","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Limits on the Power of Garbling Techniques for Public-Key Encryption"],"prefix":"10.1007","author":[{"given":"Sanjam","family":"Garg","sequence":"first","affiliation":[]},{"given":"Mohammad","family":"Hajiabadi","sequence":"additional","affiliation":[]},{"given":"Mohammad","family":"Mahmoody","sequence":"additional","affiliation":[]},{"given":"Ameer","family":"Mohammed","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,7,24]]},"reference":[{"key":"12_CR1","series-title":"Information Security and Cryptography","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-319-57048-8_1","volume-title":"Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich","author":"B Applebaum","year":"2017","unstructured":"Applebaum, B.: Garbled circuits as randomized encodings of functions: a primer. In: Lindell, Y. (ed.) Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich. ISC, pp. 1\u201344. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-57048-8_1. 336"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Asharov, G., Segev, G.: Limits on the power of indistinguishability obfuscation and functional encryption. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 191\u2013209. IEEE (2015). 337, 339, 343","DOI":"10.1109\/FOCS.2015.21"},{"key":"12_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1007\/978-3-662-49099-0_19","volume-title":"Theory of Cryptography","author":"G Asharov","year":"2016","unstructured":"Asharov, G., Segev, G.: On constructing one-way permutations from indistinguishability obfuscation. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016, Part II. LNCS, vol. 9563, pp. 512\u2013541. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49099-0_19. 337"},{"key":"12_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1007\/978-3-642-42033-7_16","volume-title":"Advances in Cryptology - ASIACRYPT 2013","author":"P Baecher","year":"2013","unstructured":"Baecher, P., Brzuska, C., Fischlin, M.: Notions of black-box reductions, revisited. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013. LNCS, vol. 8269, pp. 296\u2013315. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-42033-7_16. 336, 346"},{"key":"12_CR5","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/978-3-319-57048-8_2","volume-title":"Tutorials on the Foundations of Cryptography","author":"B Barak","year":"2017","unstructured":"Barak, B.: The complexity of public-key cryptography. In: Lindell, Y. (ed.) Tutorials on the Foundations of Cryptography, pp. 45\u201377. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-57048-8_2. 336"},{"key":"12_CR6","unstructured":"Barak, B., Mahmoody-Ghidary, M.: Lower bounds on signatures from symmetric primitives. In: 48th Annual Symposium on Foundations of Computer Science, Providence, RI, USA, 20\u201323 October 2007, pp. 680\u2013688. IEEE Computer Society Press (2007). 361"},{"key":"12_CR7","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\u2014an O(n2)-query attack on any key exchange from a random oracle. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 374\u2013390. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03356-8_22. 350"},{"key":"12_CR8","unstructured":"Beaver, D.: Correlated pseudorandomness and the complexity of private computations. In: 28th Annual ACM Symposium on Theory of Computing, pp. 479\u2013488, Philadelphia, PA, USA, 22\u201324 May 1996. ACM Press (1996). 337"},{"key":"12_CR9","unstructured":"Bellare, M., Hoang, V.T., Rogaway, P.: Foundations of garbled circuits. In: Yu, T., Danezis, G., Gligor, V.D. (eds.) ACM CCS 12: 19th Conference on Computer and Communications Security, Raleigh, NC, USA, 16\u201318 October 2012, pp. 784\u2013796. ACM Press (2012). 336, 337, 338"},{"key":"12_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1007\/978-3-319-63688-7_23","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"N Bitansky","year":"2017","unstructured":"Bitansky, N., Degwekar, A., Vaikuntanathan, V.: Structure vs. hardness through the obfuscation lens. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 696\u2013723. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63688-7_23. 337"},{"key":"12_CR11","unstructured":"Boneh, D., Papakonstantinou, P.A., Rackoff, C., Vahlis, Y., Waters, B.: On the impossibility of basing identity based encryption on trapdoor permutations. In: 49th Annual Symposium on Foundations of Computer Science, Philadelphia, PA, USA, 25\u201328 October 2008, pp. 283\u2013292. IEEE Computer Society Press (2008). 336"},{"key":"12_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1007\/978-3-642-19571-6_34","volume-title":"Theory of Cryptography","author":"Z Brakerski","year":"2011","unstructured":"Brakerski, Z., Katz, J., Segev, G., Yerukhimovich, A.: Limits on the power of zero-knowledge proofs in cryptographic constructions. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 559\u2013578. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-19571-6_34. 337, 338, 339"},{"key":"12_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1007\/978-3-662-46497-7_18","volume-title":"Theory of Cryptography","author":"R Canetti","year":"2015","unstructured":"Canetti, R., Kalai, Y.T., Paneth, O.: On obfuscation with random oracles. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 456\u2013467. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46497-7_18. 340"},{"key":"12_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/978-3-662-53644-5_7","volume-title":"Theory of Cryptography","author":"D Dachman-Soled","year":"2016","unstructured":"Dachman-Soled, D.: Towards non-black-box separations of public key encryption and one way function. In: Hirt, M., Smith, A. (eds.) TCC 2016, Part II. LNCS, vol. 9986, pp. 169\u2013191. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53644-5_7. 339"},{"issue":"6","key":"12_CR15","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","volume":"22","author":"W Diffie","year":"1976","unstructured":"Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. Inf. Theory 22(6), 644\u2013654 (1976). 335","journal-title":"IEEE Trans. Inf. Theory"},{"key":"12_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/978-3-319-63688-7_18","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"N D\u00f6ttling","year":"2017","unstructured":"D\u00f6ttling, N., Garg, S.: Identity-based encryption from the Diffie-Hellman assumption. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part I. LNCS, vol. 10401, pp. 537\u2013569. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63688-7_18. 336, 338"},{"key":"12_CR17","unstructured":"Garg, S., Lu, S., Ostrovsky, R., Scafuro, A.: Garbled RAM from one-way functions. In: Servedio, R.A., Rubinfeld, R. (eds.) 47th Annual ACM Symposium on Theory of Computing, Portland, OR, USA, 14\u201317 June 2015, pp. 449\u2013458. ACM Press (2015). 337"},{"key":"12_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/978-3-319-63688-7_22","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"S Garg","year":"2017","unstructured":"Garg, S., Mahmoody, M., Mohammed, A.: Lower bounds on obfuscation from\u00a0all-or-nothing encryption primitives. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part I. LNCS, vol. 10401, pp. 661\u2013695. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63688-7_22. 339, 340"},{"key":"12_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/978-3-319-70500-2_4","volume-title":"Theory of Cryptography","author":"S Garg","year":"2017","unstructured":"Garg, S., Mahmoody, M., Mohammed, A.: When does functional encryption imply obfuscation? In: Kalai, Y., Reyzin, L. (eds.) TCC 2017, Part I. LNCS, vol. 10677, pp. 82\u2013115. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70500-2_4. 339"},{"key":"12_CR20","unstructured":"Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Fortnow, L., Vadhan, S.P. (eds.) 43rd Annual ACM Symposium on Theory of Computing, San Jose, CA, USA, 6\u20138 June 2011, pp. 99\u2013108. ACM Press (2011). 339"},{"key":"12_CR21","unstructured":"Gertner, Y., Malkin, T., Reingold, O.: On the impossibility of basing trapdoor functions on trapdoor predicates. In: 42nd Annual Symposium on Foundations of Computer Science, Las Vegas, NV, USA, 14\u201317 October 2001, pp. 126\u2013135. IEEE Computer Society Press (2001). 341"},{"key":"12_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/978-3-540-28628-8_6","volume-title":"Advances in Cryptology \u2013 CRYPTO 2004","author":"C-Y Hsiao","year":"2004","unstructured":"Hsiao, C.-Y., Reyzin, L.: Finding collisions on a public road, or do secure hash functions need secret coins? In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 92\u2013105. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-28628-8_6. 341"},{"key":"12_CR23","unstructured":"Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: 21st Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, 15\u201317 May 1989, pp. 44\u201361. ACM Press (1989). 336, 339, 340, 341, 342, 344, 346, 349, 350"},{"key":"12_CR24","unstructured":"Ishai, Y., Kushilevitz, E.: Randomizing polynomials: a new representation with applications to round-efficient secure computation. In: 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, USA, 12\u201314 November 2000, pp. 294\u2013304. IEEE Computer Society Press (2000). 336"},{"issue":"2","key":"12_CR25","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s00145-008-9036-8","volume":"22","author":"Y Lindell","year":"2009","unstructured":"Lindell, Y., Pinkas, B.: A proof of security of Yao\u2019s protocol for two-party computation. J. Cryptol. 22(2), 161\u2013188 (2009). 336","journal-title":"J. Cryptol."},{"key":"12_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1007\/978-3-642-38348-9_42","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2013","author":"S Lu","year":"2013","unstructured":"Lu, S., Ostrovsky, R.: How to garble RAM programs? In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 719\u2013734. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38348-9_42. 337"},{"key":"12_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/978-3-662-49096-9_2","volume-title":"Theory of Cryptography","author":"M Mahmoody","year":"2016","unstructured":"Mahmoody, M., Mohammed, A., Nematihaji, S.: On the impossibility of virtual black-box obfuscation in idealized models. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016, Part I. LNCS, vol. 9562, pp. 18\u201348. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49096-9_2. 340"},{"key":"12_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/978-3-662-49096-9_3","volume-title":"Theory of Cryptography","author":"M Mahmoody","year":"2016","unstructured":"Mahmoody, M., Mohammed, A., Nematihaji, S., Pass, R., Shelat, A.: Lower bounds on assumptions behind indistinguishability obfuscation. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016, Part I. LNCS, vol. 9562, pp. 49\u201366. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49096-9_3. 340"},{"key":"12_CR29","unstructured":"Papakonstantinou, P.A., Rackoff, C.W., Vahlis, Y.: How powerful are the DDH hard groups? Cryptology ePrint Archive, Report 2012\/653 (2012). http:\/\/eprint.iacr.org\/2012\/653. 336, 338"},{"key":"12_CR30","doi-asserted-by":"crossref","unstructured":"Pass, R.: Limits of provable security from standard assumptions. In: Fortnow, L., Vadhan, S.P. (eds.) 43rd Annual ACM Symposium on Theory of Computing, San Jose, CA, USA, 6\u20138 June 2011, pp. 109\u2013118. ACM Press (2011), 339","DOI":"10.1145\/1993636.1993652"},{"key":"12_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1007\/978-3-642-19571-6_35","volume-title":"Theory of Cryptography","author":"R Pass","year":"2011","unstructured":"Pass, R., Tseng, W.-L.D., Venkitasubramaniam, M.: Towards non-black-box lower bounds in cryptography. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 579\u2013596. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-19571-6_35. 339"},{"key":"12_CR32","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. 2951, pp. 1\u201320. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24638-1_1. 336, 337, 346"},{"issue":"2","key":"12_CR33","first-page":"120","volume":"21","author":"RL Rivest","year":"1978","unstructured":"Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signature and public-key cryptosystems. Commun. Assoc. Comput. Mach. 21(2), 120\u2013126 (1978). 335","journal-title":"Commun. Assoc. Comput. Mach."},{"key":"12_CR34","unstructured":"Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: Shmoys, D.B. (ed.) 46th Annual ACM Symposium on Theory of Computing, New York, NY, USA, 31 May\u20133 June 2014, pp. 475\u2013484. ACM Press (2014). 341"},{"key":"12_CR35","unstructured":"Yao, A.C.-C.: How to generate and exchange secrets (extended abstract). In: 27th Annual Symposium on Foundations of Computer Science, Toronto, Ontario, Canada, 27\u201329 October 1986, pp. 162\u2013167. IEEE Computer Society Press (1986). 336"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2018"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-96878-0_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,28]],"date-time":"2022-08-28T02:06:35Z","timestamp":1661652395000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-96878-0_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319968773","9783319968780"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-96878-0_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"24 July 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Santa Barbara, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 August 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 August 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"38","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}