{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:34Z","timestamp":1781077714106,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":49,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642420443","type":"print"},{"value":"9783642420450","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-42045-0_17","type":"book-chapter","created":{"date-parts":[[2013,11,23]],"date-time":"2013-11-23T08:53:33Z","timestamp":1385196813000},"page":"321-340","source":"Crossref","is-referenced-by-count":49,"title":["Non-uniform Cracks in the Concrete: The Power of Free Precomputation"],"prefix":"10.1007","author":[{"given":"Daniel J.","family":"Bernstein","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tanja","family":"Lange","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"Bellare, M.: New proofs for NMAC and HMAC: security without collision-resistance. In: Crypto 2006 [40], pp. 602\u2013619 (2006) Cited in \u00a71, \u00a71.1, \u00a71.3, \u00a72.6","DOI":"10.1007\/11818175_36"},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"Bellare, M., Kilian, J., Rogaway, P.: The security of cipher block chaining. In: Crypto 1994 [38], pp. 341\u2013358 (1994); see also newer version [12]. Cited in \u00a71.2","DOI":"10.1007\/3-540-48658-5_32"},{"key":"17_CR3","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1006\/jcss.1999.1694","volume":"61","author":"M. Bellare","year":"2000","unstructured":"Bellare, M., Kilian, J., Rogaway, P.: The security of the cipher block chaining message authentication code. Journal of Computer and System Sciences 61, 362\u2013399 (2000); see also older version [11]. Cited in \u00a71, \u00a71, \u00a71, \u00a71.2, \u00a71.2, \u00a71.2","journal-title":"Journal of Computer and System Sciences"},{"key":"17_CR4","doi-asserted-by":"crossref","unstructured":"Bellare, M., Rogaway, P.: Optimal asymmetric encryption|how to encrypt with RSA. In: Eurocrypt 1994 [37], pp. 92\u2013111 (1995) Cited in \u00a71","DOI":"10.1007\/BFb0053428"},{"key":"17_CR5","doi-asserted-by":"crossref","unstructured":"Bellare, M., Rogaway, P.: The exact security of digital signatures: how to sign with RSA and Rabin. In: Eurocrypt 1996 [64], pp. 399\u2013416 (1996) Cited in \u00a71, \u00a71.1","DOI":"10.1007\/3-540-68339-9_34"},{"key":"17_CR6","unstructured":"Bellare, M., Rogaway, P.: Introduction to modern cryptography (2005), http:\/\/cseweb.ucsd.edu\/~mihir\/cse207\/classnotes.html . Cited in \u00a71, \u00a71.1, \u00a72.6"},{"key":"17_CR7","unstructured":"Bernstein, D.J.: Circuits for integer factorization: a proposal (2001), http:\/\/cr.yp.to\/papers.html#nfscircuit . Cited in \u00a75.4"},{"key":"17_CR8","unstructured":"Bernstein, D.J.: How to find smooth parts of integers (2004), http:\/\/cr.yp.to\/papers.html#smoothparts . Cited in \u00a75.1"},{"key":"17_CR9","unstructured":"Bernstein, D.J.: Scaled remainder trees (2004), http:\/\/cr.yp.to\/papers.html#scaledmod . Cited in \u00a75.3"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"Bernstein, D.J., Lange, T.: Computing small discrete logarithms faster. In: Indocrypt 2012 [41], pp. 317\u2013338 (2012) Cited in \u00a73.2, \u00a73.4","DOI":"10.1007\/978-3-642-34931-7_19"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"Biham, E., Goren, Y.J., Ishai, Y.: Basing weak public-key cryptography on strong one-way functions. In: TCC 2008 [31], pp. 55\u201372 (2008) Cited in \u00a72.6","DOI":"10.1007\/978-3-540-78524-8_4"},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"Biryukov, A., Shamir, A.: Cryptanalytic time\/memory\/data tradeoffs for stream ciphers. In: Asiacrypt 2000 [70], pp. 1\u201313 (2000) Cited in \u00a72.6","DOI":"10.1007\/3-540-44448-3_1"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Khovratovich, D., Rechberger, C.: Biclique cryptanalysis of the full AES. In: Asiacrypt 2011 [60], pp. 344\u2013371 (2011) Cited in \u00a71","DOI":"10.1007\/978-3-642-25385-0_19"},{"key":"17_CR14","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1145\/322261.322269","volume":"28","author":"R.P. Brent","year":"1981","unstructured":"Brent, R.P., Kung, H.T.: The area-time complexity of binary multiplication. Journal of the ACM 28, 521\u2013534 (1981) Cited in \u00a71.2","journal-title":"Journal of the ACM"},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"Buhler, J.P., Lenstra Jr., H.W., Pomerance, C.: Factoring integers with the number field sieve. In: [63], pp. 50\u201394 (1993) Cited in \u00a75.1, \u00a75.1, \u00a75.1, \u00a75.4","DOI":"10.1007\/BFb0091539"},{"key":"17_CR16","unstructured":"Canetti, R. (ed.): TCC 2008. LNCS, vol. 4948. Springer (2008). See [23]"},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"Commeine, A., Semaev, I.: An algorithm to solve the discrete logarithm problem with the number field sieve. In: PKC 2006 [91], pp. 174\u2013190 (2006) Cited in \u00a74.2","DOI":"10.1007\/11745853_12"},{"key":"17_CR18","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF00198464","volume":"6","author":"D. Coppersmith","year":"1993","unstructured":"Coppersmith, D.: Modifications to the number field sieve. Journal of Cryptology 6, 169\u2013180 (1993) Cited in \u00a75.4, \u00a75.4","journal-title":"Journal of Cryptology"},{"key":"17_CR19","doi-asserted-by":"crossref","unstructured":"De, A., Trevisan, L., Tulsiani, M.: Non-uniform attacks against one-way functions and PRGs. Electronic Colloquium on Computational Complexity 113 (2009); see also newer version [36]","DOI":"10.1007\/978-3-642-14623-7_35"},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"De, A., Trevisan, L., Tulsiani, M.: Time space tradeoffs for attacks against oneway functions and PRGs. In: Crypto 2010 [75], pp. 649\u2013665 (2010); see also older version [35]. Cited in \u00a72.6, \u00a72.6","DOI":"10.1007\/978-3-642-14623-7_35"},{"key":"17_CR21","unstructured":"De Santis, A. (ed.): Eurocrypt 1994. LNCS, vol. 950. Springer (1995). See [14]"},{"key":"17_CR22","unstructured":"Desmedt, Y. (ed.): Crypto 1994. LNCS, vol. 839. Springer (1994). See [11]"},{"key":"17_CR23","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Steinberger, J.: Message authentication codes from unpredictable block ciphers. In: Crypto 2009 [44], pp. 267\u2013285 (2009) Cited in \u00a72.6","DOI":"10.1007\/978-3-642-03356-8_16"},{"key":"17_CR24","unstructured":"Dwork, C. (ed.): Crypto 2006. LNCS, vol. 4117. Springer (2006). See [7]"},{"key":"17_CR25","unstructured":"Galbraith, S., Nandi, M. (eds.): Indocrypt 2012. LNCS, vol. 7668. Springer (2012). See [22]"},{"key":"17_CR26","unstructured":"Halevi, S. (ed.): Crypto 2009. LNCS, vol. 5677. Springer (2009). See [39]"},{"key":"17_CR27","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1109\/TIT.1980.1056220","volume":"26","author":"M.E. Hellman","year":"1980","unstructured":"Hellman, M.E.: A cryptanalytic time-memory tradeoff. IEEE Transactions on Information Theory 26, 401\u2013406 (1980) Cited in \u00a72.6","journal-title":"IEEE Transactions on Information Theory"},{"key":"17_CR28","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1007\/s10207-004-0045-9","volume":"3","author":"Y. Hitchcock","year":"2004","unstructured":"Hitchcock, Y., Montague, P., Carter, G., Dawson, E.: The efficiency of solving multiple discrete logarithm problems and the implications for the security of fixed elliptic curves. International Journal of Information Security 3, 86\u201398 (2004) Cited in \u00a73.4","journal-title":"International Journal of Information Security"},{"key":"17_CR29","doi-asserted-by":"crossref","unstructured":"Hong, J., Sarkar, P.: New applications of time memory data tradeoffs. In: Asiacrypt 2005 [78], pp. 353\u2013372 (2005) Cited in \u00a72.6","DOI":"10.1007\/11593447_19"},{"key":"17_CR30","doi-asserted-by":"crossref","first-page":"953","DOI":"10.1090\/S0025-5718-02-01482-5","volume":"72","author":"A. Joux","year":"2003","unstructured":"Joux, A., Lercier, R.: Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the Gaussian integer method. Mathematics of Computation 72, 953\u2013967 (2003) Cited in \u00a74.2","journal-title":"Mathematics of Computation"},{"key":"17_CR31","doi-asserted-by":"crossref","unstructured":"Katz, J., Lindell, Y.: Introduction to modern cryptography: principles and protocols. Chapman & Hall\/CRC (2007) Cited in \u00a71","DOI":"10.1201\/9781420010756"},{"key":"17_CR32","unstructured":"Koblitz, N., Menezes, A.: Another look at HMAC (2012), http:\/\/eprint.iacr.org\/2012\/074 . Cited in \u00a71.2, \u00a71.3, \u00a71.3, \u00a71.3, \u00a72.6"},{"key":"17_CR33","unstructured":"Koblitz, N., Menezes, A.: Another look at non-uniformity (2012), http:\/\/eprint.iacr.org\/2012\/359 . Cited in \u00a71.2, \u00a71.3, \u00a71.3"},{"key":"17_CR34","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Struik, R.: Random walks revisited: extensions of Pollard\u2019s rho algorithm for computing multiple discrete logarithms. In: SAC 2001 [89], pp. 212\u2013229 (2001) Cited in \u00a73.4","DOI":"10.1007\/3-540-45537-X_17"},{"key":"17_CR35","unstructured":"Lee, D.H., Wang, X. (eds.): Asiacrypt 2011. LNCS, vol. 7073. Springer (2011). See [27]"},{"key":"17_CR36","unstructured":"Lee, H.T., Cheon, J.H., Hong, J.: Accelerating ID-based encryption based on trapdoor DL using pre-computation, 11 January 2012 (2012), http:\/\/eprint.iacr.org\/2011\/187 . Cited in \u00a73.4"},{"key":"17_CR37","doi-asserted-by":"crossref","unstructured":"Lenstra, A.K., Lenstra Jr., H.W. (eds.): The development of the number field sieve. LNM, vol. 1554. Springer (1993). See [30]","DOI":"10.1007\/BFb0091534"},{"key":"17_CR38","unstructured":"Maurer, U.M. (ed.): Eurocrypt 1996. LNCS, vol. 1070. Springer (1996). See [15]"},{"key":"17_CR39","unstructured":"NIST: Announcing request for candidate algorithm nominations for the Advanced Encryption Standard (AES) (1997), http:\/\/www.gpo.gov\/fdsys\/pkg\/FR-1997-09-12\/pdf\/97-24214.pdf . Cited in \u00a71"},{"key":"17_CR40","unstructured":"NIST: Digital signature standard, Federal Information Processing Standards Publication 186-2 (2000), http:\/\/csrc.nist.gov . Cited in \u00a73"},{"key":"17_CR41","unstructured":"Okamoto, T. (ed.): Asiacrypt 2000. LNCS, vol. 1976. Springer (2000). See [25]"},{"key":"17_CR42","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/PL00003816","volume":"12","author":"P.C. Oorschot","year":"1999","unstructured":"van Oorschot, P.C., Wiener, M.: Parallel collision search with cryptanalytic applications. Journal of Cryptology 12, 1\u201328 (1999) Cited in \u00a73.1","journal-title":"Journal of Cryptology"},{"key":"17_CR43","doi-asserted-by":"crossref","unstructured":"Pollard, J.M.: Monte Carlo methods for index computation mod p. Mathematics of Computation 32, 918\u2013924 (1978) Cited in \u00a73.1","DOI":"10.2307\/2006496"},{"key":"17_CR44","unstructured":"Rabin, T. (ed.): Crypto 2010. LNCS, vol. 6223. Springer (2010). See [36]"},{"key":"17_CR45","unstructured":"Roy, B. (ed.): Asiacrypt 2005. LNCS, vol. 3788. Springer (2005). See [49]"},{"key":"17_CR46","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1137\/0209036","volume":"9","author":"A. Sch\u00f6nhage","year":"1980","unstructured":"Sch\u00f6nhage, A.: Storage modification machines. SIAM Journal on Computing 9, 490\u2013508 (1980) Cited in \u00a75.3","journal-title":"SIAM Journal on Computing"},{"key":"17_CR47","doi-asserted-by":"crossref","first-page":"809","DOI":"10.1090\/S0025-5718-00-01213-8","volume":"70","author":"E. Teske","year":"2001","unstructured":"Teske, E.: On random walks for Pollard\u2019s rho method. Mathematics of Computation 70, 809\u2013825 (2001) Cited in \u00a73.1","journal-title":"Mathematics of Computation"},{"key":"17_CR48","unstructured":"Vaudenay, S., Youssef, A.M. (eds.): SAC 2001. LNCS, vol. 2259. Springer (2001). See [58]"},{"key":"17_CR49","unstructured":"Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.): PKC 2006. LNCS, vol. 3958. Springer (2006). See [32]"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology - ASIACRYPT 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-42045-0_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T22:54:46Z","timestamp":1746053686000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-42045-0_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642420443","9783642420450"],"references-count":49,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-42045-0_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}