SWIFFT: A modest proposal for FFT hashing. 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.par 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.

References in zbMATH (referenced in 32 articles , 1 standard article )

Showing results 1 to 20 of 32.
Sorted by year (citations)

1 2 next

  1. Albrecht, Martin R.; Cid, Carlos; Faugère, Jean-Charles; Fitzpatrick, Robert; Perret, Ludovic: On the complexity of the BKW algorithm on LWE (2015)
  2. Guritman, Sugi; Aliatiningtyas, Nur; Wulandari, Teduh; Ilyas, Muhammad: Construction of family of hash functions based on ideal lattice (2015)
  3. Jarvis, Katherine; Nevins, Monica: ETRU: NTRU over the Eisenstein integers (2015)
  4. Wang, Maoning; Liu, Mingjie: Improved information set decoding for code-based cryptosystems with constrained memory (2015)
  5. Bellare, Mihir; Ristov, Todor: A characterization of chameleon hash functions and new, efficient designs (2014)
  6. Ben-Sasson, Eli; Chiesa, Alessandro; Tromer, Eran; Virza, Madars: Scalable zero knowledge via cycles of elliptic curves (2014)
  7. Ducas, Léo; Micciancio, Daniele: Improved short lattice signatures in the standard model (2014)
  8. Estuningsih, Rachmawati Dwi; Guritman, Sugi; Silalahi, Bib P.: Algorithm construction of HLI hash function (2014)
  9. Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded: A toolkit for ring-LWE cryptography (2013)
  10. Bartkewitz, Timo; Güneysu, Tim: Full lattice basis reduction on graphics cards (2012)
  11. Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas: Practical lattice-based cryptography: a signature scheme for embedded systems (2012)
  12. Micciancio, Daniele; Peikert, Chris: Trapdoors for lattices: simpler, tighter, faster, smaller (2012)
  13. Minder, Lorenz; Sinclair, Alistair: The extended $k$-tree algorithm (2012)
  14. Pietrzak, Krzysztof: Cryptography from learning parity with noise (2012)
  15. Pöppelmann, Thomas; Güneysu, Tim: Towards efficient arithmetic for lattice-based cryptography on reconfigurable hardware (2012)
  16. Zhang, Jiang; Zhang, Zhenfeng: A ciphertext policy attribute-based encryption scheme without pairings (2012)
  17. Brakerski, Zvika; Vaikuntanathan, Vinod: Fully homomorphic encryption from ring-LWE and security for key dependent messages (2011)
  18. Rose, Michael; Plantard, Thomas; Susilo, Willy: Improving BDD cryptosystems in general lattices (2011)
  19. Stehlé, Damien; Steinfeld, Ron: Making NTRU as secure as worst-case problems over ideal lattices (2011)
  20. Cayrel, Pierre-Louis; Lindner, Richard; Rückert, Markus; Silva, Rosemberg: A lattice-based threshold ring signature scheme (2010)

1 2 next