SWIFFT: A Modest Proposal for FFT Hashing

By Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, Alon Rosen. Fast Software Encryption Workshop, 2008

311 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/70faa1d2f195ecda8de6a8d6f983f06ac388a819

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Scalable Zero Knowledge Via Cycles of Elliptic Curves (2014, background): “17 Recent works [1,26,70,72,86] use a small modulus and larger dimension, but our “native” modulus is already a large one.”
Lattice-Based Cryptography (2006, methodology): “Here we follow the approach used in the latter work, which also generalizes the construction of [52, 62] based on circulant matrices, to a wider range of structured matrices, some of which admit very efficient implementations [45].”
Speeding up the Number Theoretic Transform for Faster Ideal Lattice-Based Cryptography (2016, methodology): “In this setting, the NTT is usually computed with a special type of FFT algorithm that can be used eﬃciently when q is a prime that satisﬁes the congruence condition q ≡ 1 mod 2 n (cf. [19, § 2.1]), which in turn means that the underlying ﬁnite ﬁeld contains primitive 2 n -th roots of unity.”
A Toolkit for Ring-LWE Cryptography (2013, background): “, [25, 24, 21, 14, 15, 26, 33, 9, 8, 17, 18, 22, 5, 28, 20, 16]), often to the exclusion of all other rings.”
Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller (2012, methodology): “See the representative works [Mic02, PR06, LM06, LMPR08, LPR10] for more details on these functions and their security foundations.”
Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures (2009, methodology): “We hope that our work provides further motivation for studying latticereduction algorithms for lattices of the form Λ⊥p (A), which also happen to be central to the cryptanalysis of other lattice-based schemes such as [20,19,15].”
Pseudorandom Functions and Lattices (2012, methodology): “The ring product can also be computed with a constant depth, size-O(n(2)) circuit over Zq, or in O(log n) depth and only O(n log n) scalar operations using Fast Fourier Transform-like techniques [24, 25].”
Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages (2011, methodology): “Starting with the work of Micciancio [28], there has been an ongoing effort [31, 23, 32, 25, 24] to come up with very efficient constructions of various cryptographic primitives whose security can formally be reduced to the hardness of short-vector problems in ideal lattices.”
Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems (2012, background): “This has changed since the introduction of cyclic and ideal lattices [27] and related computationally hard problems like Ring-SIS [32, 23, 25] and Ring-LWE [26] which enabled the constructions of a great variety of theoretically elegant and efficient cryptographic primitives.”
On Ideal Lattices and Learning with Errors over Rings (2010, background): “a fast and practical implementation [22].”