{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T22:08:28Z","timestamp":1757542108346,"version":"3.41.0"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319968773"},{"type":"electronic","value":"9783319968780"}],"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_23","type":"book-chapter","created":{"date-parts":[[2018,7,23]],"date-time":"2018-07-23T12:53:57Z","timestamp":1532350437000},"page":"674-697","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["From Laconic Zero-Knowledge to Public-Key Cryptography"],"prefix":"10.1007","author":[{"given":"Itay","family":"Berman","sequence":"first","affiliation":[]},{"given":"Akshay","family":"Degwekar","sequence":"additional","affiliation":[]},{"given":"Ron D.","family":"Rothblum","sequence":"additional","affiliation":[]},{"given":"Prashant Nalini","family":"Vasudevan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,7,24]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Barak, B., Wigderson, A.: Public-key cryptography from different assumptions. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5\u20138 June 2010, pp. 171\u2013180 (2010)","DOI":"10.1145\/1806689.1806715"},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M.: More on average case vs approximation complexity. In: Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), Cambridge, MA, USA, 11\u201314 October 2003, pp. 298\u2013307. IEEE Computer Society (2003)","DOI":"10.1109\/SFCS.2003.1238204"},{"key":"23_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/978-3-662-53015-3_16","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"B Applebaum","year":"2016","unstructured":"Applebaum, B., Raykov, P.: On the relationship between statistical zero-knowledge and statistical randomized encodings. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 449\u2013477. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53015-3_16"},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"Babai, L.: Graph isomorphism in quasipolynomial time [extended abstract]. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, 18\u201321 June 2016, pp. 684\u2013697 (2016)","DOI":"10.1145\/2897518.2897542"},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Degwekar, A., Vaikuntanathan, V.: Structure vs hardness through the obfuscation lens. IACR Cryptology ePrint Archive 2016:574 (2016)","DOI":"10.1007\/978-3-319-63688-7_23"},{"key":"23_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-01001-9_1","volume-title":"Advances in Cryptology - EUROCRYPT 2009","author":"M Bellare","year":"2009","unstructured":"Bellare, M., Hofheinz, D., Yilek, S.: Possibility and impossibility results for encryption and commitment secure under selective opening. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 1\u201335. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-01001-9_1"},{"key":"23_CR7","doi-asserted-by":"crossref","unstructured":"Bellare, M., Impagliazzo, R., Naor, M.: Does parallel repetition lower the error in computationally sound protocols? In: 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, Miami Beach, Florida, USA, 19\u201322 October 1997, pp. 374\u2013383 (1997)","DOI":"10.1109\/SFCS.1997.646126"},{"key":"23_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-642-40041-4_7","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"A Bogdanov","year":"2013","unstructured":"Bogdanov, A., Lee, C.H.: Limits of Provable Security for Homomorphic Encryption. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 111\u2013128. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40041-4_7"},{"key":"23_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/3-540-46035-7_4","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2002","author":"R Cramer","year":"2002","unstructured":"Cramer, R., Shoup, V.: Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 45\u201364. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-46035-7_4"},{"issue":"6","key":"23_CR10","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)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"4","key":"23_CR11","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/S0020-0190(98)00116-1","volume":"67","author":"O Goldreich","year":"1998","unstructured":"Goldreich, O., H\u00e5stad, J.: On the complexity of interactive proofs with bounded communication. Inf. Process. Lett. 67(4), 205\u2013214 (1998)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"23_CR12","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF02620137","volume":"6","author":"O Goldreich","year":"1993","unstructured":"Goldreich, O., Kushilevitz, E.: A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm. J. Cryptol. 6(2), 97\u2013116 (1993)","journal-title":"J. Cryptol."},{"key":"23_CR13","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: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, New York, New York, USA, pp. 218\u2013229 (1987)","DOI":"10.1145\/28395.28420"},{"key":"23_CR14","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Computational Complexity - A Conceptual Perspective. Cambridge University Press, Cambridge (2008)","DOI":"10.1017\/CBO9780511804106"},{"key":"23_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1007\/978-3-642-28914-9_28","volume-title":"Theory of Cryptography","author":"S Garg","year":"2012","unstructured":"Garg, S., Ostrovsky, R., Visconti, I., Wadia, A.: Resettable statistical zero knowledge. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 494\u2013511. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-28914-9_28"},{"key":"23_CR16","unstructured":"Goldreich, O., Vadhan, S.P.: Comparing entropies in statistical zero knowledge with applications to the structure of SZK. In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, 4\u20136 May 1999, p. 54 (1999)"},{"issue":"1\u20132","key":"23_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-002-0169-0","volume":"11","author":"O Goldreich","year":"2002","unstructured":"Goldreich, O., Vadhan, S., Wigderson, A.: On interactive proofs with a laconic prover. Comput. Complex. 11(1\u20132), 1\u201353 (2002)","journal-title":"Comput. Complex."},{"issue":"1","key":"23_CR18","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/130938438","volume":"44","author":"I Haitner","year":"2015","unstructured":"Haitner, I., Hoch, J.J., Reingold, O., Segev, G.: Finding collisions in interactive protocols\u2013tight lower bounds on the round and communication complexities of statistically hiding commitments. SIAM J. Comput. 44(1), 193\u2013242 (2015)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"23_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. 28(4), 1364\u20131396 (1999)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"23_CR20","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1007\/s00145-015-9200-x","volume":"29","author":"C Hazay","year":"2016","unstructured":"Hazay, C., L\u00f3pez-Alt, A., Wee, H., Wichs, D.: Leakage-resilient cryptography from minimal assumptions. J. Cryptol. 29(3), 514\u2013551 (2016)","journal-title":"J. Cryptol."},{"issue":"3","key":"23_CR21","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.H., Reingold, O., Vadhan, S.P.: Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function. SIAM J. Comput. 39(3), 1153\u20131218 (2009)","journal-title":"SIAM J. Comput."},{"key":"23_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1007\/11535218_29","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"T Holenstein","year":"2005","unstructured":"Holenstein, T., Renner, R.: One-way secret-key agreement and applications to circuit polarization and immunization of public-key encryption. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 478\u2013493. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11535218_29"},{"issue":"4","key":"23_CR23","doi-asserted-by":"publisher","first-page":"1865","DOI":"10.1109\/TIT.2011.2110230","volume":"57","author":"T Holenstein","year":"2011","unstructured":"Holenstein, T., Renner, R.: On the randomness of independent experiments. IEEE Trans. Inf. Theory 57(4), 1865\u20131871 (2011)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"23_CR24","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, pp. 44\u201361. ACM (1989)","DOI":"10.1145\/73007.73012"},{"key":"23_CR25","doi-asserted-by":"crossref","unstructured":"Kilian, J.: Founding crytpography on oblivious transfer. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 20\u201331. ACM (1988)","DOI":"10.1145\/62212.62215"},{"key":"23_CR26","doi-asserted-by":"crossref","unstructured":"Komargodski, I., Moran, T., Naor, M., Pass, R., Rosen, A., Yogev, E.: One-way functions and (im)perfect obfuscation. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, 18\u201321 October 2014, pp. 374\u2013383. IEEE Computer Society (2014)","DOI":"10.1109\/FOCS.2014.47"},{"key":"23_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1007\/978-3-662-49096-9_16","volume-title":"Theory of Cryptography","author":"T Liu","year":"2016","unstructured":"Liu, T., Vaikuntanathan, V.: On basing private information retrieval on NP-hardness. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016, Part I. LNCS, vol. 9562, pp. 372\u2013386. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49096-9_16"},{"key":"23_CR28","doi-asserted-by":"crossref","unstructured":"Nguyen, M.-H., Vadhan, S.P.: Zero knowledge with efficient provers. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, 21\u201323 May 2006, pp. 287\u2013295 (2006)","DOI":"10.1145\/1132516.1132559"},{"key":"23_CR29","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R.: One-way functions, hard on average problems, and statistical zero-knowledge proofs. In: Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, 30 June - 3 July 1991, pp. 133\u2013138 (1991)","DOI":"10.1109\/SCT.1991.160253"},{"key":"23_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1007\/978-3-540-78524-8_27","volume-title":"Theory of Cryptography","author":"SJ Ong","year":"2008","unstructured":"Ong, S.J., Vadhan, S.: An equivalence between zero knowledge and commitments. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 482\u2013500. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78524-8_27"},{"key":"23_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1007\/978-3-662-46497-7_25","volume-title":"Theory of Cryptography","author":"O Pandey","year":"2015","unstructured":"Pandey, O., Prabhakaran, M., Sahai, A.: Obfuscation-based non-black-box simulation and four message concurrent zero knowledge for NP. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 638\u2013667. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46497-7_25"},{"key":"23_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/978-3-540-85174-5_31","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"C Peikert","year":"2008","unstructured":"Peikert, C., Vaikuntanathan, V., Waters, B.: A framework for efficient and composable oblivious transfer. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 554\u2013571. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-85174-5_31"},{"key":"23_CR33","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, 22\u201324 May 2005, pp. 84\u201393. ACM (2005)","DOI":"10.1145\/1060590.1060603"},{"key":"23_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-3-642-19571-6_14","volume-title":"Theory of Cryptography","author":"R Rothblum","year":"2011","unstructured":"Rothblum, R.: Homomorphic encryption: from private-key to public-key. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 219\u2013234. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-19571-6_14"},{"issue":"2","key":"23_CR35","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"RL Rivest","year":"1978","unstructured":"Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120\u2013126 (1978)","journal-title":"Commun. ACM"},{"issue":"3","key":"23_CR36","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","volume":"27","author":"CE Shannon","year":"1948","unstructured":"Shannon, C.E.: A mathematical theory of communication. Bell Syst. Tech. J. 27(3), 379\u2013423 (1948)","journal-title":"Bell Syst. Tech. J."},{"issue":"2","key":"23_CR37","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1145\/636865.636868","volume":"50","author":"A Sahai","year":"2003","unstructured":"Sahai, A., Vadhan, S.: A complete problem for statistical zero knowledge. J. ACM (JACM) 50(2), 196\u2013249 (2003)","journal-title":"J. ACM (JACM)"},{"key":"23_CR38","doi-asserted-by":"crossref","unstructured":"Vadhan, S., Zheng, C.J.: Characterizing pseudoentropy and simplifying pseudorandom generator constructions. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, pp. 817\u2013836. ACM (2012)","DOI":"10.1145\/2213977.2214051"}],"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_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T23:35:01Z","timestamp":1751758501000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-96878-0_23"}},"subtitle":["Extended Abstract"],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319968773","9783319968780"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-96878-0_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"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"}]}}