SWIFFT swMATH ID: 11588 Software Authors: Lyubashevsky, Vadim; Micciancio, Daniele; Peikert, Chris; Rosen, Alon Description: 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. Homepage: http://www.eecs.harvard.edu/~alon/PAPERS/lattices/swifft.pdf Source Code: https://github.com/micciancio/SWIFFT Related Software: NTRU; NTL; ring-LWE; SWIFFTX; GitHub; CUDA; BKZ; Pinocchio; McEliece; NTRUSign; fpLLL; mctoolbox; gmp; ETRU; SNARKs for C; Geppetto; zk-SNARK; Falcon; BLISS; FACCT Cited in: 53 Documents Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year SWIFFT: a modest proposal for FFT hashing. Zbl 1154.68403Lyubashevsky, Vadim; Micciancio, Daniele; Peikert, Chris; Rosen, Alon 2008 all top 5 Cited by 107 Authors 6 Lyubashevsky, Vadim 5 Lindner, Richard 5 Micciancio, Daniele 4 Rückert, Markus 3 Buchmann, Johannes A. 3 Cayrel, Pierre-Louis 3 Güneysu, Tim 3 Peikert, Chris 3 Silva, Rosemberg 2 Albrecht, Martin R. 2 Bellare, Mihir 2 Ben-Sasson, Eli 2 Chiesa, Alessandro 2 Damgård, Ivan Bjerre 2 Guritman, Sugi 2 Hu, Yupu 2 Pöppelmann, Thomas 2 Ristov, Todor 2 Rosen, Alon 2 Safavi-Naini, Reihaneh 2 Schneider, Michael 2 Stehlé, Damien 2 Tromer, Eran 2 Virza, Madars 1 Aliatiningtyas, Nur 1 Bai, Shi 1 Bartkewitz, Timo 1 Baum, Carsten 1 Bermudo Mera, Jose Maria 1 Biasse, Jean-François 1 Bogdanov, Andrej 1 Booth, Roland 1 Boschini, Cecilia 1 Brakerski, Zvika 1 Camenisch, Jan L. 1 Cenk, Murat 1 Chen, Long 1 Cid, Carlos Frederico 1 Cramer, Ronald John Fitzgerald 1 Ducas, Léo 1 Espitau, Thomas 1 Estuningsih, Rachmawati Dwi 1 Faugère, Jean-Charles 1 Fitzpatrick, Robert 1 Fouque, Pierre-Alain 1 Galbraith, Steven D. 1 Gélin, Alexandre 1 Grassi, Lorenzo 1 Hermans, Jens 1 Howgrave-Graham, Nick A. 1 Ilyas, Muhammad 1 Jarvis, Katherine 1 Jia, Huiwen 1 Joux, Antoine 1 Kalach, Kassem 1 Karati, Sabyasachi 1 Karmakar, Angshuman 1 Kawachi, Akinori 1 Kirchner, Paul 1 Larsen, Kasper Green 1 Lehmann, Anja 1 Lei, Hao 1 Li, Liangze 1 Li, Yanan 1 Liu, Mingjie 1 Liu, Zhen 1 Marc, Tilen 1 Meziani, Mohammed 1 Minder, Lorenz 1 Ndiaye, Ousmane 1 Nevins, Monica 1 Nguyen, Ngoc Khanh 1 Ovsiankin, Max 1 Pan, Yanbin 1 Perret, Ludovic 1 Pietrzak, Krzysztof 1 Plantard, Thomas 1 Preneel, Bart 1 Pujol, Xavier 1 Rechberger, Christian 1 Regev, Oded 1 Roy, Arnab 1 Šarinay, Juraj 1 Sheffield, Daniel 1 Silalahi, Bib Paruhum 1 Sinclair, Alistair 1 Soleimanian, Azam 1 Spooner, Nicholas 1 Steinfeld, Ron 1 Susilo, Willy 1 Tanaka, Keisuke 1 Tang, Qiang 1 Tessaro, Stefano 1 Tiessen, Tyge 1 Ulu, Metin Evrim 1 Vaikuntanathan, Vinod 1 Vercauteren, Frederik 1 Wang, Baocang 1 Wang, Maoning 1 Wulandari, Teduh ...and 7 more Authors all top 5 Cited in 8 Serials 3 Journal of Cryptology 3 Designs, Codes and Cryptography 1 Computing 1 Information Sciences 1 Algorithmica 1 Applicable Algebra in Engineering, Communication and Computing 1 Far East Journal of Mathematical Sciences 1 JP Journal of Algebra, Number Theory and Applications all top 5 Cited in 9 Fields 53 Information and communication theory, circuits (94-XX) 13 Computer science (68-XX) 4 Number theory (11-XX) 4 Quantum theory (81-XX) 1 Combinatorics (05-XX) 1 Order, lattices, ordered algebraic structures (06-XX) 1 Algebraic geometry (14-XX) 1 Probability theory and stochastic processes (60-XX) 1 Numerical analysis (65-XX) Citations by Year