SWIFFT
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.
Keywords for this software
References in zbMATH (referenced in 39 articles , 1 standard article )
Showing results 1 to 20 of 39.
Sorted by year (- 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)
- Cayrel, Pierre-Louis; Meziani, Mohammed; Ndiaye, Ousmane; Lindner, Richard; Silva, Rosemberg: A pseudorandom number generator based on worst-case lattice problems (2017)
- Cramer, Ronald; Damgård, Ivan; Xing, Chaoping; Yuan, Chen: Amortized complexity of zero-knowledge proofs revisited: achieving linear soundness slack (2017)
- Albrecht, Martin; Grassi, Lorenzo; Rechberger, Christian; Roy, Arnab; Tiessen, Tyge: MiMC: efficient encryption and cryptographic hashing with minimal multiplicative complexity (2016)
- Baum, Carsten; Damgård, Ivan; Larsen, Kasper Green; Nielsen, Michael: How to prove knowledge of small secrets (2016)
- Kalach, Kassem; Safavi-Naini, Reihaneh: An efficient post-quantum one-time signature scheme (2016)
- Albrecht, Martin R.; Cid, Carlos; Faugère, Jean-Charles; Fitzpatrick, Robert; Perret, Ludovic: On the complexity of the BKW algorithm on LWE (2015)
- Guritman, Sugi; Aliatiningtyas, Nur; Wulandari, Teduh; Ilyas, Muhammad: Construction of family of hash functions based on ideal lattice (2015)
- Jarvis, Katherine; Nevins, Monica: ETRU: NTRU over the Eisenstein integers (2015)
- Wang, Maoning; Liu, Mingjie: Improved information set decoding for code-based cryptosystems with constrained memory (2015)
- Bellare, Mihir; Ristov, Todor: A characterization of chameleon hash functions and new, efficient designs (2014)
- Ben-Sasson, Eli; Chiesa, Alessandro; Tromer, Eran; Virza, Madars: Scalable zero knowledge via cycles of elliptic curves (2014)
- Ducas, Léo; Micciancio, Daniele: Improved short lattice signatures in the standard model (2014)
- Estuningsih, Rachmawati Dwi; Guritman, Sugi; Silalahi, Bib P.: Algorithm construction of HLI hash function (2014)
- Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded: A toolkit for ring-LWE cryptography (2013)
- Bartkewitz, Timo; Güneysu, Tim: Full lattice basis reduction on graphics cards (2012)
- Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas: Practical lattice-based cryptography: a signature scheme for embedded systems (2012)
- Micciancio, Daniele; Peikert, Chris: Trapdoors for lattices: simpler, tighter, faster, smaller (2012)
- Minder, Lorenz; Sinclair, Alistair: The extended $k$-tree algorithm (2012)
- Pietrzak, Krzysztof: Cryptography from learning parity with noise (2012)