Paper 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.

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

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Lattice reduction
Contact author(s)
nhowgravegraham @ ntru com
History
2007-08-27: last of 2 revisions
2007-03-23: received
See all versions
Short URL
https://ia.cr/2007/105
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/105,
      author = {Nicholas A.  Howgrave-Graham},
      title = {Isodual Reduction of Lattices},
      howpublished = {Cryptology {ePrint} Archive, Paper 2007/105},
      year = {2007},
      url = {https://eprint.iacr.org/2007/105}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.