{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T04:21:51Z","timestamp":1775794911896,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540710387","type":"print"},{"value":"9783540710394","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-71039-4_4","type":"book-chapter","created":{"date-parts":[[2008,7,18]],"date-time":"2008-07-18T14:09:52Z","timestamp":1216390192000},"page":"54-72","source":"Crossref","is-referenced-by-count":167,"title":["SWIFFT: A Modest Proposal for FFT Hashing"],"prefix":"10.1007","author":[{"given":"Vadim","family":"Lyubashevsky","sequence":"first","affiliation":[]},{"given":"Daniele","family":"Micciancio","sequence":"additional","affiliation":[]},{"given":"Chris","family":"Peikert","sequence":"additional","affiliation":[]},{"given":"Alon","family":"Rosen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Generating hard instances of lattice problems. In: STOC, pp. 99\u2013108 (1996)","DOI":"10.1145\/237814.237838"},{"key":"4_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/3-540-47555-9_3","volume-title":"Advances in Cryptology - EUROCRYPT \u201992","author":"T. Baritaud","year":"1993","unstructured":"Baritaud, T., Gilbert, H., Girault, M.: FFT hashing is not collision-free. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol.\u00a0658, pp. 35\u201344. Springer, Heidelberg (1993)"},{"key":"4_CR3","unstructured":"Bentahar, K., Page, D., Silverman, J., Saarinen, M., Smart, N.: Lash. Technical report, 2nd NIST Cryptographic Hash Function Workshop (2006)"},{"key":"4_CR4","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2005","author":"E. Biham","year":"2005","unstructured":"Biham, E., Chen, R., Joux, A., Carribault, P., Jalby, W., Lemuet, C.: Collisions of SHA-0 and reduced SHA-1. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol.\u00a03494. Springer, Heidelberg (2005)"},{"issue":"4","key":"4_CR5","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. Journal of the ACM\u00a050(4), 506\u2013519 (2003)","journal-title":"Journal of the ACM"},{"key":"4_CR6","unstructured":"Cai, J., Nerurkar, A.: An improved worst-case to average-case connection for lattice problems. In: FOCS, pp. 468\u2013477 (1997)"},{"key":"4_CR7","series-title":"Lecture Notes in Computer Science","first-page":"39","volume-title":"Advances in Cryptology - EUROCRYPT \u201989","author":"P. Camion","year":"1990","unstructured":"Camion, P., Patarin, J.: The knapsack hash function proposed at Crypto 1989 can be broken. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol.\u00a0434, pp. 39\u201353. Springer, Heidelberg (1990)"},{"key":"4_CR8","unstructured":"Contini, S., Matusiewicz, K., Pieprzyk, J., Steinfeld, R., Guo, J., Ling, S., Wang, H.: Cryptanalysis of LASH. Cryptology ePrint Archive, Report 2007\/430 (2007), http:\/\/eprint.iacr.org\/"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology - ASIACRYPT \u201991","author":"J. Daemen","year":"1993","unstructured":"Daemen, J., Bosselaers, A., Govaerts, R., Vandewalle, J.: Collisions for Schnorr\u2019s hash function FFT-hash presented at crypto 1991. In: Matsumoto, T., Imai, H., Rivest, R.L. (eds.) ASIACRYPT 1991. LNCS, vol.\u00a0739. Springer, Heidelberg (1993)"},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1007\/0-387-34805-0_39","volume-title":"Advances in Cryptology - CRYPTO \u201989","author":"I. Damg\u00e5rd","year":"1990","unstructured":"Damg\u00e5rd, I.: A design principle for hash functions. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol.\u00a0435, pp. 416\u2013427. Springer, Heidelberg (1990)"},{"key":"4_CR11","unstructured":"Goldreich, O., Goldwasser, S., Halevi, S.: Collision-free hashing from lattice problems. Technical Report TR-42, ECCC (1996)"},{"issue":"4","key":"4_CR12","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O. Goldreich","year":"1986","unstructured":"Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM\u00a033(4), 792\u2013807 (1986)","journal-title":"J. ACM"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: A ring-based public key cryptosystem. In: ANTS, pp. 267\u2013288 (1998)","DOI":"10.1007\/BFb0054868"},{"key":"4_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/BFb0053424","volume-title":"Advances in Cryptology - EUROCRYPT \u201994","author":"A. Joux","year":"1995","unstructured":"Joux, A., Granboulan, L.: A practical attack against knapsack based hash functions (extended abstract). In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol.\u00a0950, pp. 58\u201366. Springer, Heidelberg (1995)"},{"key":"4_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1007\/11538462_32","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"V. Lyubashevsky","year":"2005","unstructured":"Lyubashevsky, V.: The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 378\u2013389. Springer, Heidelberg (2005)"},{"key":"4_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/11787006_13","volume-title":"Automata, Languages and Programming","author":"V. Lyubashevsky","year":"2006","unstructured":"Lyubashevsky, V., Micciancio, D.: Generalized compact knapsacks are collision resistant. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04052, pp. 144\u2013155. Springer, Heidelberg (2006)"},{"issue":"1","key":"4_CR17","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1137\/S0097539703433511","volume":"34","author":"D. Micciancio","year":"2004","unstructured":"Micciancio, D.: Almost perfect lattices, the covering radius problem, and applications to Ajtai\u2019s connection factor. SIAM J. on Computing\u00a034(1), 118\u2013169 (2004)","journal-title":"SIAM J. on Computing"},{"key":"4_CR18","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s00037-007-0234-9","volume":"16","author":"D. Micciancio","year":"2007","unstructured":"Micciancio, D.: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions. Computational Complexity\u00a016, 365\u2013411 (2007); Preliminary version in FOCS 2002","journal-title":"Computational Complexity"},{"issue":"1","key":"4_CR19","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1137\/S0097539705447360","volume":"37","author":"D. Micciancio","year":"2007","unstructured":"Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. SIAM J. on Computing\u00a037(1), 267\u2013302 (2007)","journal-title":"SIAM J. on Computing"},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"Nguyen, P., Stehl\u00e9, D.: LLL on the average. In: ANTS, pp. 238\u2013256 (2006)","DOI":"10.1007\/11792086_18"},{"key":"4_CR21","series-title":"Lecture Notes in Computer Science","volume-title":"Theory of Cryptography","author":"C. Peikert","year":"2006","unstructured":"Peikert, C., Rosen, A.: Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol.\u00a03876. Springer, Heidelberg (2006)"},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"Peikert, C., Rosen, A.: Lattices that admit logarithmic worst-case to average-case connection factors. In: STOC, pp. 478\u2013487; Full version in ECCC Report TR06-147 (2007)","DOI":"10.1145\/1250790.1250860"},{"key":"4_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1007\/978-3-540-25937-4_24","volume-title":"Fast Software Encryption","author":"P. Rogaway","year":"2004","unstructured":"Rogaway, P., Shrimpton, T.: Cryptographic hash-function basics: Definitions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol.\u00a03017, pp. 371\u2013388. Springer, Heidelberg (2004)"},{"key":"4_CR24","unstructured":"Schnorr, C.P.: FFT-hash, an efficient cryptographic hash function. In: Crypto Rump Session (1991)"},{"key":"4_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/3-540-47555-9_4","volume-title":"Advances in Cryptology - EUROCRYPT \u201992","author":"C.P. Schnorr","year":"1993","unstructured":"Schnorr, C.P.: FFT\u2013Hash II, efficient cryptographic hashing. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol.\u00a0658, pp. 45\u201354. Springer, Heidelberg (1993)"},{"key":"4_CR26","doi-asserted-by":"crossref","unstructured":"Schnorr, C.P.: Serge Vaudenay. Parallel FFT-hashing. In: Fast Software Encryption, pp. 149\u2013156 (1993)","DOI":"10.1007\/3-540-58108-1_18"},{"key":"4_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1007\/3-540-48071-4_43","volume-title":"Advances in Cryptology - CRYPTO \u201992","author":"S. Vaudenay","year":"1993","unstructured":"Vaudenay, S.: FFT-Hash-II is not yet collision-free. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol.\u00a0740, pp. 587\u2013593. Springer, Heidelberg (1993)"},{"key":"4_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/3-540-45708-9_19","volume-title":"Advances in Cryptology - CRYPTO 2002","author":"D. Wagner","year":"2002","unstructured":"Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol.\u00a02442, pp. 288\u2013303. Springer, Heidelberg (2002)"},{"key":"4_CR29","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2005","author":"X. Wang","year":"2005","unstructured":"Wang, X., Lai, X., Feng, D., Chen, H., Yu, X.: Cryptanalysis for hash functions MD4 and RIPEMD. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol.\u00a03494. Springer, Heidelberg (2005)"},{"key":"4_CR30","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2005","author":"X. Wang","year":"2005","unstructured":"Wang, X., Yu, H.: How to break MD5 and other hash functions. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol.\u00a03494. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Fast Software Encryption"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-71039-4_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T04:35:26Z","timestamp":1620016526000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-71039-4_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540710387","9783540710394"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-71039-4_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}