Cryptology ePrint Archive: Report 2007/105

Isodual Reduction of Lattices

Nicholas A. Howgrave-Graham

Abstract: We define a new notion of a reduced lattice, based on a quantity introduced in the LLL paper. We show that lattices reduced in this sense are simultaneously reduced in both their primal and dual. We show that the definition applies naturally to blocks, and therefore gives a new hierarchy of polynomial time algorithms for lattice reduction with fixed blocksize. We compare this hierarchy of algorithms to previous ones. We then explore algorithms to provably minimize the associated measure, and also some more efficient heuristics. Finally we comment on the initial investigations of applying our technique to the NTRU family of lattices.

Category / Keywords: foundations / Lattice reduction

Date: received 22 Mar 2007, last revised 26 Aug 2007

Contact author: nhowgravegraham at ntru com

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

Note: Revised to include an algorithmic description of a practical and useful isodual reduction technique.

Version: 20070827:032125 (All versions of this report)

Short URL: ia.cr/2007/105

Discussion forum: Show discussion | Start new discussion