Abstract
We propose SWIFFT, a collection of compression functions that are highly parallelizable and admit very efficient implementations on modern microprocessors. The main technique underlying our functions is a novel use of the Fast Fourier Transform (FFT) to achieve “diffusion,” together with a linear combination to achieve compression and “confusion.” We provide a detailed security analysis of concrete instantiations, and give a high-performance software implementation that exploits the inherent parallelism of the FFT algorithm. The throughput of our implementation is competitive with that of SHA-256, with additional parallelism yet to be exploited.
Our functions are set apart from prior proposals (having comparable efficiency) by a supporting asymptotic security proof: it can be formally proved that finding a collision in a randomly-chosen function from the family (with noticeable probability) is at least as hard as finding short vectors in cyclic/ideal lattices in the worst case.
Mod·est, adj.: Marked by simplicity.
Chapter PDF
Similar content being viewed by others
References
Ajtai, M.: Generating hard instances of lattice problems. In: STOC, pp. 99–108 (1996)
Baritaud, T., Gilbert, H., Girault, M.: FFT hashing is not collision-free. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 35–44. Springer, Heidelberg (1993)
Bentahar, K., Page, D., Silverman, J., Saarinen, M., Smart, N.: Lash. Technical report, 2nd NIST Cryptographic Hash Function Workshop (2006)
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. 3494. Springer, Heidelberg (2005)
Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM 50(4), 506–519 (2003)
Cai, J., Nerurkar, A.: An improved worst-case to average-case connection for lattice problems. In: FOCS, pp. 468–477 (1997)
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. 434, pp. 39–53. Springer, Heidelberg (1990)
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/
Daemen, J., Bosselaers, A., Govaerts, R., Vandewalle, J.: Collisions for Schnorr’s hash function FFT-hash presented at crypto 1991. In: Matsumoto, T., Imai, H., Rivest, R.L. (eds.) ASIACRYPT 1991. LNCS, vol. 739. Springer, Heidelberg (1993)
Damgård, I.: A design principle for hash functions. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 416–427. Springer, Heidelberg (1990)
Goldreich, O., Goldwasser, S., Halevi, S.: Collision-free hashing from lattice problems. Technical Report TR-42, ECCC (1996)
Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM 33(4), 792–807 (1986)
Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: A ring-based public key cryptosystem. In: ANTS, pp. 267–288 (1998)
Joux, A., Granboulan, L.: A practical attack against knapsack based hash functions (extended abstract). In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 58–66. Springer, Heidelberg (1995)
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. 3624, pp. 378–389. Springer, Heidelberg (2005)
Lyubashevsky, V., Micciancio, D.: Generalized compact knapsacks are collision resistant. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 144–155. Springer, Heidelberg (2006)
Micciancio, D.: Almost perfect lattices, the covering radius problem, and applications to Ajtai’s connection factor. SIAM J. on Computing 34(1), 118–169 (2004)
Micciancio, D.: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions. Computational Complexity 16, 365–411 (2007); Preliminary version in FOCS 2002
Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. SIAM J. on Computing 37(1), 267–302 (2007)
Nguyen, P., Stehlé, D.: LLL on the average. In: ANTS, pp. 238–256 (2006)
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. 3876. Springer, Heidelberg (2006)
Peikert, C., Rosen, A.: Lattices that admit logarithmic worst-case to average-case connection factors. In: STOC, pp. 478–487; Full version in ECCC Report TR06-147 (2007)
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. 3017, pp. 371–388. Springer, Heidelberg (2004)
Schnorr, C.P.: FFT-hash, an efficient cryptographic hash function. In: Crypto Rump Session (1991)
Schnorr, C.P.: FFT–Hash II, efficient cryptographic hashing. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 45–54. Springer, Heidelberg (1993)
Schnorr, C.P.: Serge Vaudenay. Parallel FFT-hashing. In: Fast Software Encryption, pp. 149–156 (1993)
Vaudenay, S.: FFT-Hash-II is not yet collision-free. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 587–593. Springer, Heidelberg (1993)
Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288–303. Springer, Heidelberg (2002)
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. 3494. Springer, Heidelberg (2005)
Wang, X., Yu, H.: How to break MD5 and other hash functions. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A. (2008). SWIFFT: A Modest Proposal for FFT Hashing. In: Nyberg, K. (eds) Fast Software Encryption. FSE 2008. Lecture Notes in Computer Science, vol 5086. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-71039-4_4
Download citation
DOI: https://doi.org/10.1007/978-3-540-71039-4_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-71038-7
Online ISBN: 978-3-540-71039-4
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.