{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T21:10:18Z","timestamp":1769721018961,"version":"3.49.0"},"publisher-location":"Cham","reference-count":79,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319783802","type":"print"},{"value":"9783319783819","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.springernature.com\/gp\/researchers\/text-and-data-mining"},{"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.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-78381-9_4","type":"book-chapter","created":{"date-parts":[[2018,3,30]],"date-time":"2018-03-30T05:53:14Z","timestamp":1522389194000},"page":"91-122","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":81,"title":["Fiat-Shamir and Correlation Intractability from Strong KDM-Secure Encryption"],"prefix":"10.1007","author":[{"given":"Ran","family":"Canetti","sequence":"first","affiliation":[]},{"given":"Yilei","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Leonid","family":"Reyzin","sequence":"additional","affiliation":[]},{"given":"Ron D.","family":"Rothblum","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,31]]},"reference":[{"key":"4_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1007\/3-540-46035-7_28","volume-title":"Advances in Cryptology \u2014 EUROCRYPT 2002","author":"M Abdalla","year":"2002","unstructured":"Abdalla, M., An, J.H., Bellare, M., Namprempre, C.: From identification to signatures via the Fiat-Shamir transform: minimizing assumptions for security and forward-security. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 418\u2013433. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-46035-7_28"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Adleman, L.: A subexponential algorithm for the discrete logarithm problem with applications to cryptography. In: 1979 20th Annual Symposiumon Foundations of Computer Science, pp. 55\u201360. IEEE (1979)","DOI":"10.1109\/SFCS.1979.2"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: STOC, pp. 99\u2013108 (1996)","DOI":"10.1145\/237814.237838"},{"issue":"3","key":"4_CR4","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1515\/jmc-2015-0016","volume":"9","author":"MR Albrecht","year":"2015","unstructured":"Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. 9(3), 169\u2013203 (2015)","journal-title":"J. Math. Cryptol."},{"issue":"3","key":"4_CR5","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s00145-013-9149-6","volume":"27","author":"B Applebaum","year":"2014","unstructured":"Applebaum, B.: Key-dependent message security: generic amplification and completeness. J. Cryptol. 27(3), 429\u2013451 (2014)","journal-title":"J. Cryptol."},{"key":"4_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/978-3-642-03356-8_35","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"B Applebaum","year":"2009","unstructured":"Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 595\u2013618. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03356-8_35"},{"key":"4_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/978-3-642-22006-7_34","volume-title":"Automata, Languages and Programming","author":"S Arora","year":"2011","unstructured":"Arora, S., Ge, R.: New algorithms for learning in presence of errors. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6755, pp. 403\u2013415. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22006-7_34"},{"issue":"1","key":"4_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579403","volume":"6","author":"L Babai","year":"1986","unstructured":"Babai, L.: On Lov\u00e1sz\u2019 lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1\u201313 (1986)","journal-title":"Combinatorica"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/978-3-642-13190-5_22","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"B Barak","year":"2010","unstructured":"Barak, B., Haitner, I., Hofheinz, D., Ishai, Y.: Bounded key-dependent message security. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 423\u2013444. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13190-5_22"},{"issue":"2","key":"4_CR10","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/j.jcss.2005.06.010","volume":"72","author":"B Barak","year":"2006","unstructured":"Barak, B., Lindell, Y., Vadhan, S.P.: Lower bounds for non-black-box zero knowledge. J. Comput. Syst. Sci. 72(2), 321\u2013391 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1007\/978-3-642-40084-1_23","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"M Bellare","year":"2013","unstructured":"Bellare, M., Hoang, V.T., Keelveedhi, S.: Instantiating random oracles via UCEs. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 398\u2013415. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40084-1_23"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: ACM Conference on Computer and Communications Security, pp. 62\u201373 (1993)","DOI":"10.1145\/168588.168596"},{"key":"4_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-662-53644-5_2","volume-title":"Theory of Cryptography","author":"E Ben-Sasson","year":"2016","unstructured":"Ben-Sasson, E., Chiesa, A., Spooner, N.: Interactive oracle proofs. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9986, pp. 31\u201360. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53644-5_2"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Dachman-Soled, D., Garg, S., Jain, A., TaumanKalai, Y., L\u00f3pez-Alt, A., Wichs, D.: Why \u201cfiat-shamir for proofs\u201d lacks a proof. In: TCC, pp. 182\u2013201 (2013)","DOI":"10.1007\/978-3-642-36594-2_11"},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"Black, J., Rogaway, P., Shrimpton. T.: Encryption-scheme security in the presence of key-dependent messages. In: Selected Areas in Cryptography, pp. 62\u201375 (2002)","DOI":"10.1007\/3-540-36492-7_6"},{"issue":"4","key":"4_CR16","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1145\/792538.792543","volume":"50","author":"A Blum","year":"2003","unstructured":"Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM (JACM) 50(4), 506\u2013519 (2003)","journal-title":"J. ACM (JACM)"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications (extended abstract). In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 2\u20134 May 1988, Chicago, Illinois, USA, pp. 103\u2013112 (1988)","DOI":"10.1145\/62212.62222"},{"key":"4_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1007\/978-3-642-10366-7_31","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2009","author":"A Boldyreva","year":"2009","unstructured":"Boldyreva, A., Cash, D., Fischlin, M., Warinschi, B.: Foundations of non-malleable hash and one-way functions. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 524\u2013541. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-10366-7_31"},{"key":"4_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-540-85174-5_7","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"D Boneh","year":"2008","unstructured":"Boneh, D., Halevi, S., Hamburg, M., Ostrovsky, R.: Circular-secure encryption from decision Diffie-Hellman. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 108\u2013125. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-85174-5_7"},{"key":"4_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-14623-7_1","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"Z Brakerski","year":"2010","unstructured":"Brakerski, Z., Goldwasser, S.: Circular and leakage resilient public-key encryption under subgroup indistinguishability. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 1\u201320. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14623-7_1"},{"key":"4_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/978-3-642-19571-6_13","volume-title":"Theory of Cryptography","author":"Z Brakerski","year":"2011","unstructured":"Brakerski, Z., Goldwasser, S., Kalai, Y.T.: Black-Box circular-secure encryption beyond affine functions. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 201\u2013218. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-19571-6_13"},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"Camenisch, J., Lysyanskaya, A.: An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In: EUROCRYPT: Advances in Cryptology: Proceedings of EUROCRYPT (2001)","DOI":"10.1007\/3-540-44987-6_7"},{"key":"4_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/BFb0052255","volume-title":"Advances in Cryptology \u2014 CRYPTO \u201997","author":"R Canetti","year":"1997","unstructured":"Canetti, R.: Towards realizing random oracles: hash functions that hide all partial information. In: Kaliski, B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 455\u2013469. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/BFb0052255"},{"key":"4_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/978-3-662-49096-9_17","volume-title":"Theory of Cryptography","author":"R Canetti","year":"2016","unstructured":"Canetti, R., Chen, Y., Reyzin, L.: On the correlation intractability of obfuscated pseudorandom functions. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9562, pp. 389\u2013415. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49096-9_17"},{"key":"4_CR25","doi-asserted-by":"crossref","unstructured":"Canetti, R., Chen, Y., Reyzin, L., Rothblum, R.D.: Fiat-Shamir and correlation intractability from strong KDM-secure encryption. Cryptology ePrint Archive, Report 2018\/131 (2018)","DOI":"10.1007\/978-3-319-78381-9_4"},{"key":"4_CR26","doi-asserted-by":"crossref","unstructured":"Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited (preliminary version). In: [78], pp. 209\u2013218. ACM (1998)","DOI":"10.1145\/276698.276741"},{"issue":"4","key":"4_CR27","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1145\/1008731.1008734","volume":"51","author":"R Canetti","year":"2004","unstructured":"Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. J. ACM 51(4), 557\u2013594 (2004)","journal-title":"J. ACM"},{"key":"4_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/978-3-642-11799-2_4","volume-title":"Theory of Cryptography","author":"R Canetti","year":"2010","unstructured":"Canetti, R., Tauman Kalai, Y., Varia, M., Wichs, D.: On symmetric encryption and point obfuscation. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 52\u201371. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-11799-2_4"},{"key":"4_CR29","doi-asserted-by":"crossref","unstructured":"Canetti, R., Micciancio, D., Reingold, O.: Perfectly one-way probabilistic hash functions (preliminary version). In: [78], pp. 131\u2013140. ACM (1998)","DOI":"10.1145\/276698.276721"},{"issue":"1","key":"4_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01840433","volume":"1","author":"D Coppersmith","year":"1986","unstructured":"Coppersmith, D., Odlyzko, A.M., Schroeppel, R.: Discrete logarithms in GF(p). Algorithmica 1(1), 1\u201315 (1986)","journal-title":"Algorithmica"},{"issue":"1","key":"4_CR31","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1112\/S0010437X10005075","volume":"147","author":"C Diem","year":"2011","unstructured":"Diem, C.: On the discrete logarithm problem in elliptic curves. Compositio Mathematica 147(1), 75\u2013104 (2011)","journal-title":"Compositio Mathematica"},{"key":"4_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/11535218_27","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"Y Dodis","year":"2005","unstructured":"Dodis, Y., Oliveira, R., Pietrzak, K.: On the generic insecurity of the full domain hash. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 449\u2013466. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11535218_27"},{"key":"4_CR33","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Ristenpart, T., Vadhan, S.P.: Randomness condensers for efficiently samplable, seed-dependent sources. In: TCC, pp. 618\u2013635 (2012)","DOI":"10.1007\/978-3-642-28914-9_35"},{"key":"4_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/978-3-642-38348-9_2","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2013","author":"N D\u00f6ttling","year":"2013","unstructured":"D\u00f6ttling, N., M\u00fcller-Quade, J.: Lossy codes and a new variant of the learning-with-errors problem. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 18\u201334. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38348-9_2"},{"key":"4_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/3-540-48071-4_10","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 92","author":"C Dwork","year":"1993","unstructured":"Dwork, C., Naor, M.: Pricing via processing or combatting junk mail. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 139\u2013147. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/3-540-48071-4_10"},{"issue":"6","key":"4_CR36","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1145\/950620.950623","volume":"50","author":"C Dwork","year":"2003","unstructured":"Dwork, C., Naor, M., Reingold, O., Stockmeyer, L.J.: Magic functions. J. ACM 50(6), 852\u2013921 (2003)","journal-title":"J. ACM"},{"issue":"4","key":"4_CR37","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","volume":"31","author":"T ElGamal","year":"1985","unstructured":"ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theor. 31(4), 469\u2013472 (1985)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"4_CR38","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\u201328 (1999)","journal-title":"SIAM J. Comput."},{"key":"4_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/3-540-47721-7_12","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 86","author":"A Fiat","year":"1987","unstructured":"Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186\u2013194. Springer, Heidelberg (1987). https:\/\/doi.org\/10.1007\/3-540-47721-7_12"},{"issue":"1","key":"4_CR40","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s10623-015-0146-7","volume":"78","author":"SD Galbraith","year":"2016","unstructured":"Galbraith, S.D., Gaudry, P.: Recent progress on the elliptic curve discrete logarithm problem. Des. Codes Crypt. 78(1), 51\u201372 (2016)","journal-title":"Des. Codes Crypt."},{"issue":"12","key":"4_CR41","doi-asserted-by":"publisher","first-page":"1690","DOI":"10.1016\/j.jsc.2008.08.005","volume":"44","author":"P Gaudry","year":"2009","unstructured":"Gaudry, P.: Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem. J. Symb. Comput. 44(12), 1690\u20131702 (2009)","journal-title":"J. Symb. Comput."},{"issue":"1","key":"4_CR42","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s00145-001-0011-x","volume":"15","author":"P Gaudry","year":"2002","unstructured":"Gaudry, P., Hess, F., Smart, N.P.: Constructive and destructive facets of weil descent on elliptic curves. J. Cryptology 15(1), 19\u201346 (2002)","journal-title":"J. Cryptology"},{"key":"4_CR43","doi-asserted-by":"crossref","unstructured":"Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) STOC, pp. 169\u2013178. ACM (2009)","DOI":"10.1145\/1536414.1536440"},{"key":"4_CR44","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Kalai, Y.T.: On the (in)security of the Fiat-Shamir paradigm. In: FOCS, pp. 102\u2013113 (2003)","DOI":"10.1109\/SFCS.2003.1238185"},{"issue":"2","key":"4_CR45","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"S Goldwasser","year":"1984","unstructured":"Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270\u2013299 (1984)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR46","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems (extended abstract). In: STOC, pp. 291\u2013304 (1985)","DOI":"10.1145\/22145.22178"},{"key":"4_CR47","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-642-19571-6_12","volume-title":"Theory of Cryptography","author":"V Goyal","year":"2011","unstructured":"Goyal, V., O\u2019Neill, A., Rao, V.: Correlated-input secure hash functions. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 182\u2013200. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-19571-6_12"},{"key":"4_CR48","doi-asserted-by":"crossref","unstructured":"Granville, A.: Smooth numbers: computational number theory and beyond, pp. 267\u2013323 (2008)","DOI":"10.1017\/9781139049801.010"},{"key":"4_CR49","doi-asserted-by":"publisher","first-page":"2894","DOI":"10.1093\/ietfec\/e89-a.10.2894","volume":"89\u2013A(10)","author":"S Hada","year":"2006","unstructured":"Hada, S., Tanaka, T.: Zero-knowledge and correlation intractability. IEICE Trans. 89\u2013A(10), 2894\u20132905 (2006)","journal-title":"IEICE Trans."},{"key":"4_CR50","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/978-3-642-00457-5_13","volume-title":"Theory of Cryptography","author":"I Haitner","year":"2009","unstructured":"Haitner, I., Holenstein, T.: On the (im)possibility of key dependent encryption. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 202\u2013219. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-00457-5_13"},{"key":"4_CR51","doi-asserted-by":"crossref","unstructured":"Halevi, S., Krawczyk, H.: Security under key-dependent inputs. In: Ning, P., De\u00a0Capitani di\u00a0Vimercati, S., Syverson, P.F. (eds.) Proceedings of the 2007 ACM Conference on Computer and Communications Security, CCS 2007, Alexandria, Virginia, USA, 28\u201331, October 2007, pp. 466\u2013475. ACM (2007)","DOI":"10.1145\/1315245.1315303"},{"key":"4_CR52","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/978-3-540-78524-8_2","volume-title":"Theory of Cryptography","author":"S Halevi","year":"2008","unstructured":"Halevi, S., Myers, S., Rackoff, C.: On seed-incompressible functions. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 19\u201336. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78524-8_2"},{"key":"4_CR53","unstructured":"Hanke, T.: Asicboost - a speedup for bitcoin mining. CoRR abs\/1604.00575 (2016)"},{"issue":"4","key":"4_CR54","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."},{"key":"4_CR55","unstructured":"Herold, G., Kirshanova, E., May, A.: On the asymptotic complexity of solving lWE. Des. Codes Crypt., 1\u201329 (2015)"},{"key":"4_CR56","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-540-78967-3_7","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2008","author":"D Hofheinz","year":"2008","unstructured":"Hofheinz, D., Unruh, D.: Towards key-dependent message security in the standard model. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 108\u2013126. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78967-3_7"},{"key":"4_CR57","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/978-3-540-45146-4_9","volume-title":"Advances in Cryptology - CRYPTO 2003","author":"Y Ishai","year":"2003","unstructured":"Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending oblivious transfers efficiently. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 145\u2013161. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-45146-4_9"},{"key":"4_CR58","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/978-3-642-03356-8_9","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"YT Kalai","year":"2009","unstructured":"Kalai, Y.T., Raz, R.: Probabilistically checkable arguments. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 143\u2013159. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03356-8_9"},{"key":"4_CR59","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/978-3-319-63715-0_8","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"YT Kalai","year":"2017","unstructured":"Kalai, Y.T., Rothblum, G.N., Rothblum, R.D.: From obfuscation to the security of Fiat-Shamir for proofs. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10402, pp. 224\u2013251. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63715-0_8"},{"key":"4_CR60","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/978-3-662-47989-6_3","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"P Kirchner","year":"2015","unstructured":"Kirchner, P., Fouque, P.-A.: An improved BKW algorithm for LWE with applications to cryptography and lattices. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 43\u201362. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47989-6_3"},{"issue":"4","key":"4_CR61","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra, H.W., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515\u2013534 (1982)","journal-title":"Math. Ann."},{"key":"4_CR62","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-642-19074-2_21","volume-title":"Topics in Cryptology \u2013 CT-RSA 2011","author":"R Lindner","year":"2011","unstructured":"Lindner, R., Peikert, C.: Better key sizes (and attacks) for LWE-based encryption. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 319\u2013339. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-19074-2_21"},{"issue":"5","key":"4_CR63","doi-asserted-by":"publisher","first-page":"1639","DOI":"10.1109\/18.259647","volume":"39","author":"A Menezes","year":"1993","unstructured":"Menezes, A., Okamoto, T., Vanstone, S.A.: Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Trans. Inf. Theor. 39(5), 1639\u20131646 (1993)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"4_CR64","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-642-40041-4_2","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"D Micciancio","year":"2013","unstructured":"Micciancio, D., Peikert, C.: Hardness of SIS and LWE with small parameters. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 21\u201339. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40041-4_2"},{"key":"4_CR65","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-540-88702-7_5","volume-title":"Post-Quantum Cryptography","author":"D Micciancio","year":"2009","unstructured":"Micciancio, D., Regev, O.: Lattice-based cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.) Post-Quantum Cryptography, pp. 147\u2013191. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-540-88702-7_5"},{"key":"4_CR66","unstructured":"Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2008). Accessed 28 Jan 2018"},{"key":"4_CR67","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/11792086_18","volume-title":"Algorithmic Number Theory","author":"PQ Nguyen","year":"2006","unstructured":"Nguyen, P.Q., Stehl\u00e9, D.: LLL on the average. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 238\u2013256. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11792086_18"},{"key":"4_CR68","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/3-540-45708-9_8","volume-title":"Advances in Cryptology \u2014 CRYPTO 2002","author":"JB Nielsen","year":"2002","unstructured":"Nielsen, J.B.: Separating random oracle proofs from complexity theoretic proofs: the non-committing encryption case. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 111\u2013126. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45708-9_8"},{"key":"4_CR69","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-662-49387-8_1","volume-title":"Public-Key Cryptography \u2013 PKC 2016","author":"C Petit","year":"2016","unstructured":"Petit, C., Kosters, M., Messeng, A.: Algebraic approaches for the elliptic curve discrete logarithm problem over prime fields. In: Cheng, C.-M., Chung, K.-M., Persiano, G., Yang, B.-Y. (eds.) PKC 2016. LNCS, vol. 9615, pp. 3\u201318. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49387-8_1"},{"issue":"3","key":"4_CR70","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/BF01933667","volume":"15","author":"JM Pollard","year":"1975","unstructured":"Pollard, J.M.: A Monte Carlo method for factorization. BIT Numer. Math. 15(3), 331\u2013334 (1975)","journal-title":"BIT Numer. Math."},{"issue":"4","key":"4_CR71","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1112\/jlms\/s1-13.4.242","volume":"1","author":"RA Rankin","year":"1938","unstructured":"Rankin, R.A.: The difference between consecutive prime numbers. J. London Math. Soc. 1(4), 242\u2013247 (1938)","journal-title":"J. London Math. Soc."},{"key":"4_CR72","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"},{"issue":"6","key":"4_CR73","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1145\/1568318.1568324","volume":"56","author":"O Regev","year":"2009","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 84\u201393 (2009)","journal-title":"J. ACM"},{"key":"4_CR74","doi-asserted-by":"crossref","unstructured":"Reingold, O., Rothblum, G.N.., Rothblum, R.D.: Constant-round interactive proofs for delegating computation. In: STOC, pp. 49\u201362. ACM (2016)","DOI":"10.1145\/2897518.2897652"},{"key":"4_CR75","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0304-3975(87)90064-8","volume":"53","author":"C-P Schnorr","year":"1987","unstructured":"Schnorr, C.-P.: A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci. 53, 201\u2013224 (1987)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR76","unstructured":"Semaev, I.A.: Summation polynomials and the discrete logarithm problem on elliptic curves (2004)"},{"key":"4_CR77","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/3-540-69053-0_18","volume-title":"Advances in Cryptology \u2014 EUROCRYPT \u201997","author":"V Shoup","year":"1997","unstructured":"Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 256\u2013266. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/3-540-69053-0_18"},{"key":"4_CR78","unstructured":"Vitter, J.S. (eds.): Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, 23\u201326 May 1998. ACM (1998)"},{"key":"4_CR79","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/978-3-662-53018-4_18","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"M Zhandry","year":"2016","unstructured":"Zhandry, M.: The magic of ELFs. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 479\u2013508. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53018-4_18"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2018"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-78381-9_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T03:52:03Z","timestamp":1751514723000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-78381-9_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319783802","9783319783819"],"references-count":79,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-78381-9_4","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":"31 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"EUROCRYPT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Tel Aviv","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Israel","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":"29 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 May 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"37","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"eurocrypt2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/eurocrypt.iacr.org\/2018\/index.html","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"}]}}