Practical Lattice Basis Sampling Reduction

Johannes Buchmann; Christoph Ludwig

Paper 2005/072 Original: eprint.iacr.org/2005/072 ↗

Practical Lattice Basis Sampling Reduction

Johannes Buchmann

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
Category: Public-key cryptography
Publication info: Preprint.
History: 2005-03-08: last updated; 2005-03-08: published
Short URL: https://ia.cr/2005/072
License: https://creativecommons.org/licenses/by/4.0/

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},
      url = {https://eprint.iacr.org/2005/072}
}