### Secure Parameters for SWIFFT

Johannes Buchmann and Richard Lindner

##### Abstract

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
Keywords
post-quantum cryptographyhash functionslattices
Contact author(s)
rlindner @ cdc informatik tu-darmstadt de
History
2009-07-15: last of 3 revisions
See all versions
Short URL
https://ia.cr/2008/493

CC BY

BibTeX

@misc{cryptoeprint:2008/493,
author = {Johannes Buchmann and Richard Lindner},
title = {Secure Parameters for SWIFFT},
howpublished = {Cryptology ePrint Archive, Paper 2008/493},
year = {2008},
note = {\url{https://eprint.iacr.org/2008/493}},
url = {https://eprint.iacr.org/2008/493}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.