Paper 2014/788

Tuning GaussSieve for Speed

Robert Fitzpatrick, Christian Bischof, Johannes Buchmann, Ozgur Dagdelen, Florian Gopfert, Artur Mariano, and Bo-Yin Yang

Abstract

The area of lattice-based cryptography is growing ever-more prominent as a paradigm for quantum-resistant cryptography. One of the most important hard problem underpinning the security of lattice- based cryptosystems is the shortest vector problem (SVP). At present, two approaches dominate methods for solving instances of this problem in practice: enumeration and sieving. In 2010, Micciancio and Voulgaris presented a heuristic member of the sieving family, known as GaussSieve, demonstrating it to be comparable to enumeration methods in practice. With contemporary lattice-based cryptographic proposals relying largely on the hardness of solving the shortest and closest vector problems in ideal lattices, examining possible improvements to sieving algorithms becomes highly pertinent since, at present, only sieving algorithms have been successfully adapted to solve such instances more efficiently than in the random lattice case. In this paper, we propose a number of heuristic improvements to GaussSieve, which can also be applied to other sieving algorithms for SVP.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Latincrypt 2014
Keywords
Lattice-Based CryptographySievingSVP
Contact author(s)
rob @ rfcrypto com
History
2014-10-07: received
Short URL
https://ia.cr/2014/788
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/788,
      author = {Robert Fitzpatrick and Christian Bischof and Johannes Buchmann and Ozgur Dagdelen and Florian Gopfert and Artur Mariano and Bo-Yin Yang},
      title = {Tuning GaussSieve for Speed},
      howpublished = {Cryptology ePrint Archive, Paper 2014/788},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/788}},
      url = {https://eprint.iacr.org/2014/788}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.