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 42 articles , 1 standard article )

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

1 2 3 next

  1. Ben-Sasson, Eli; Chiesa, Alessandro; Tromer, Eran; Virza, Madars: Scalable zero knowledge via cycles of elliptic curves (2017)
  2. Biasse, Jean-François; Espitau, Thomas; Fouque, Pierre-Alain; Gélin, Alexandre; Kirchner, Paul: Computing generator in cyclotomic integer rings. A subfield algorithm for the principal ideal problem in $L_|\varDelta_\mathbb K|\left(\frac12\right)$ and application to the cryptanalysis of a FHE scheme (2017)
  3. Cayrel, Pierre-Louis; Meziani, Mohammed; Ndiaye, Ousmane; Lindner, Richard; Silva, Rosemberg: A pseudorandom number generator based on worst-case lattice problems (2017)
  4. Cramer, Ronald; Damgård, Ivan; Xing, Chaoping; Yuan, Chen: Amortized complexity of zero-knowledge proofs revisited: achieving linear soundness slack (2017)
  5. Albrecht, Martin; Grassi, Lorenzo; Rechberger, Christian; Roy, Arnab; Tiessen, Tyge: MiMC: efficient encryption and cryptographic hashing with minimal multiplicative complexity (2016)
  6. Baum, Carsten; Damgård, Ivan; Larsen, Kasper Green; Nielsen, Michael: How to prove knowledge of small secrets (2016)
  7. Kalach, Kassem; Safavi-Naini, Reihaneh: An efficient post-quantum one-time signature scheme (2016)
  8. Albrecht, Martin R.; Cid, Carlos; Faugère, Jean-Charles; Fitzpatrick, Robert; Perret, Ludovic: On the complexity of the BKW algorithm on LWE (2015)
  9. Guritman, Sugi; Aliatiningtyas, Nur; Wulandari, Teduh; Ilyas, Muhammad: Construction of family of hash functions based on ideal lattice (2015)
  10. Jarvis, Katherine; Nevins, Monica: ETRU: NTRU over the Eisenstein integers (2015)
  11. Wang, Maoning; Liu, Mingjie: Improved information set decoding for code-based cryptosystems with constrained memory (2015)
  12. Bellare, Mihir; Ristov, Todor: A characterization of chameleon hash functions and new, efficient designs (2014)
  13. Ben-Sasson, Eli; Chiesa, Alessandro; Tromer, Eran; Virza, Madars: Scalable zero knowledge via cycles of elliptic curves (2014)
  14. Ducas, Léo; Micciancio, Daniele: Improved short lattice signatures in the standard model (2014)
  15. Estuningsih, Rachmawati Dwi; Guritman, Sugi; Silalahi, Bib P.: Algorithm construction of HLI hash function (2014)
  16. Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded: A toolkit for ring-LWE cryptography (2013)
  17. Bartkewitz, Timo; Güneysu, Tim: Full lattice basis reduction on graphics cards (2012)
  18. Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas: Practical lattice-based cryptography: a signature scheme for embedded systems (2012)
  19. Micciancio, Daniele; Peikert, Chris: Trapdoors for lattices: simpler, tighter, faster, smaller (2012)
  20. Minder, Lorenz; Sinclair, Alistair: The extended $k$-tree algorithm (2012)

1 2 3 next