Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / lattice techniques, NTRU

Date: received 4 Mar 2005

Contact author: cludwig at cdc informatik tu-darmstadt de

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20050308:103518 (All versions of this report)

Short URL: ia.cr/2005/072

Discussion forum: Show discussion | Start new discussion