Paper 2008/493

Secure Parameters for SWIFFT

Johannes Buchmann and Richard Lindner


The SWIFFT compression functions, proposed by Lyubashevsky et al. at FSE 2008, are very efficient instantiations of generalized compact knapsacks for a specific set of parameters. They have the property that, asymptotically, finding collisions for a randomly chosen compression function implies being able to solve computationally hard ideal lattice problems in the worst-case. We present three results. First, we present new average-case problems, which may be used for all lattice schemes whose security is proven with the worst-case to average-case reduction in either general or ideal lattices. The new average-case problems require less description bits, resulting in improved keysize and speed for these schemes. Second, we propose a parameter generation algorithm for SWIFFT where the main parameter n can be any integer in the image of Euler's totient function, and not necessarily a power of 2 as before. Third, we give experimental evidence that finding pseudo-collisions for SWIFFT is as hard as breaking a 68-bit symmetric cipher according to the well-known heuristic by Lenstra and Verheul. We also recommend conservative parameters corresponding to a 127-bit symmetric cipher.

Note: Added section on new average-case problems

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
post-quantum cryptographyhash functionslattices
Contact author(s)
rlindner @ cdc informatik tu-darmstadt de
2009-07-15: last of 3 revisions
2008-12-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Johannes Buchmann and Richard Lindner},
      title = {Secure Parameters for SWIFFT},
      howpublished = {Cryptology ePrint Archive, Paper 2008/493},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.