Paper 2005/072

Practical Lattice Basis Sampling Reduction

Johannes Buchmann and Christoph Ludwig

Abstract

We propose a practical sampling reduction algorithm for lattice bases based on work by Schnorr as well as two even more effective generalizations. We report the empirical behaviour of these algorithms. We describe how Sampling Reduction allows to stage lattice attacks against the NTRU cryptosystem with smaller BKZ parameters than before and conclude that therefore the recommeded NTRU security parameters offer $\leq 74$ Bit security.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
lattice techniquesNTRU
Contact author(s)
cludwig @ cdc informatik tu-darmstadt de
History
2005-03-08: received
Short URL
https://ia.cr/2005/072
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/072,
      author = {Johannes Buchmann and Christoph Ludwig},
      title = {Practical Lattice Basis Sampling Reduction},
      howpublished = {Cryptology ePrint Archive, Paper 2005/072},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/072}},
      url = {https://eprint.iacr.org/2005/072}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.