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

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

1 2 3 next

  1. Bai, Shi; Galbraith, Steven D.; Li, Liangze; Sheffield, Daniel: Improved combinatorial algorithms for the inhomogeneous short integer solution problem (2019)
  2. Hu, Yupu; Jia, Huiwen: A new Gaussian sampling for trapdoor lattices with arbitrary modulus (2019)
  3. Ben-Sasson, Eli; Chiesa, Alessandro; Tromer, Eran; Virza, Madars: Scalable zero knowledge via cycles of elliptic curves (2017)
  4. 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_\mathbbK|\left(\frac12\right)) and application to the cryptanalysis of a FHE scheme (2017)
  5. Cayrel, Pierre-Louis; Meziani, Mohammed; Ndiaye, Ousmane; Lindner, Richard; Silva, Rosemberg: A pseudorandom number generator based on worst-case lattice problems (2017)
  6. Cramer, Ronald; Damgård, Ivan; Xing, Chaoping; Yuan, Chen: Amortized complexity of zero-knowledge proofs revisited: achieving linear soundness slack (2017)
  7. Albrecht, Martin; Grassi, Lorenzo; Rechberger, Christian; Roy, Arnab; Tiessen, Tyge: MiMC: efficient encryption and cryptographic hashing with minimal multiplicative complexity (2016)
  8. Baum, Carsten; Damgård, Ivan; Larsen, Kasper Green; Nielsen, Michael: How to prove knowledge of small secrets (2016)
  9. Kalach, Kassem; Safavi-Naini, Reihaneh: An efficient post-quantum one-time signature scheme (2016)
  10. Albrecht, Martin R.; Cid, Carlos; Faugère, Jean-Charles; Fitzpatrick, Robert; Perret, Ludovic: On the complexity of the BKW algorithm on LWE (2015)
  11. Guritman, Sugi; Aliatiningtyas, Nur; Wulandari, Teduh; Ilyas, Muhammad: Construction of family of hash functions based on ideal lattice (2015)
  12. Jarvis, Katherine; Nevins, Monica: ETRU: NTRU over the Eisenstein integers (2015)
  13. Wang, Maoning; Liu, Mingjie: Improved information set decoding for code-based cryptosystems with constrained memory (2015)
  14. Bellare, Mihir; Ristov, Todor: A characterization of chameleon hash functions and new, efficient designs (2014)
  15. Ben-Sasson, Eli; Chiesa, Alessandro; Tromer, Eran; Virza, Madars: Scalable zero knowledge via cycles of elliptic curves (2014)
  16. Ducas, Léo; Micciancio, Daniele: Improved short lattice signatures in the standard model (2014)
  17. Estuningsih, Rachmawati Dwi; Guritman, Sugi; Silalahi, Bib P.: Algorithm construction of HLI hash function (2014)
  18. Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded: A toolkit for ring-LWE cryptography (2013)
  19. Bartkewitz, Timo; Güneysu, Tim: Full lattice basis reduction on graphics cards (2012)
  20. Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas: Practical lattice-based cryptography: a signature scheme for embedded systems (2012)

1 2 3 next