Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

SWIFFT: A Modest Proposal for FFT Hashing

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNSC,volume 5086))

Included in the following conference series:

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 theFast 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 asymptoticsecurity 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 theworst case.

Mod·est, adj.: Marked by simplicity.

Similar content being viewed by others

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.

References

  1. Ajtai, M.: Generating hard instances of lattice problems. In: STOC, pp. 99–108 (1996)

    Google Scholar 

  2. 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)

    Chapter  Google Scholar 

  3. Bentahar, K., Page, D., Silverman, J., Saarinen, M., Smart, N.: Lash. Technical report, 2nd NIST Cryptographic Hash Function Workshop (2006)

    Google Scholar 

  4. 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)

    Google Scholar 

  5. 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)

    Article MathSciNet  Google Scholar 

  6. Cai, J., Nerurkar, A.: An improved worst-case to average-case connection for lattice problems. In: FOCS, pp. 468–477 (1997)

    Google Scholar 

  7. 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)

    Google Scholar 

  8. 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/

  9. 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)

    Google Scholar 

  10. Damgård, I.: A design principle for hash functions. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 416–427. Springer, Heidelberg (1990)

    Google Scholar 

  11. Goldreich, O., Goldwasser, S., Halevi, S.: Collision-free hashing from lattice problems. Technical Report TR-42, ECCC (1996)

    Google Scholar 

  12. Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM 33(4), 792–807 (1986)

    Article MathSciNet  Google Scholar 

  13. Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: A ring-based public key cryptosystem. In: ANTS, pp. 267–288 (1998)

    Google Scholar 

  14. 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)

    Chapter  Google Scholar 

  15. 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)

    Google Scholar 

  16. 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)

    Chapter  Google Scholar 

  17. 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)

    Article MATH MathSciNet  Google Scholar 

  18. 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

    Article MATH MathSciNet  Google Scholar 

  19. Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. SIAM J. on Computing 37(1), 267–302 (2007)

    Article MATH MathSciNet  Google Scholar 

  20. Nguyen, P., Stehlé, D.: LLL on the average. In: ANTS, pp. 238–256 (2006)

    Google Scholar 

  21. 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)

    Google Scholar 

  22. 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)

    Google Scholar 

  23. 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)

    Google Scholar 

  24. Schnorr, C.P.: FFT-hash, an efficient cryptographic hash function. In: Crypto Rump Session (1991)

    Google Scholar 

  25. 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)

    Chapter  Google Scholar 

  26. Schnorr, C.P.: Serge Vaudenay. Parallel FFT-hashing. In: Fast Software Encryption, pp. 149–156 (1993)

    Google Scholar 

  27. 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)

    Google Scholar 

  28. Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288–303. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  29. 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)

    Google Scholar 

  30. 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)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of California at San Diego,  

    Vadim Lyubashevsky & Daniele Micciancio

  2. SRI International,  

    Chris Peikert

  3. IDC Herzliya,  

    Alon Rosen

Authors
  1. Vadim Lyubashevsky
  2. Daniele Micciancio
  3. Chris Peikert
  4. Alon Rosen

Editor information

Kaisa Nyberg

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

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp