You are looking at a specific version 20090715:093026 of this paper. See the latest version.

Paper 2008/493

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

Metadata
Available format(s)
PDF
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
2008-12-02: received
See all versions
Short URL
https://ia.cr/2008/493
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.