Lattices with Symmetry

H.  W.  Lenstra Jr.; A.  Silverberg

Paper 2014/1026 Original: eprint.iacr.org/2014/1026 ↗

Lattices with Symmetry

H. W. Lenstra Jr.

A. Silverberg

Abstract

For large ranks, there is no good algorithm that decides whether a given lattice has an orthonormal basis. But when the lattice is given with enough symmetry, we can construct a provably deterministic polynomial-time algorithm to accomplish this, based on the work of Gentry and Szydlo. The techniques involve algorithmic algebraic number theory, analytic number theory, commutative algebra, and lattice basis reduction.

Metadata

Available format(s): PDF
Publication info: Preprint.
History: 2016-10-04: last updated; 2015-01-02: published
Short URL: https://ia.cr/2014/1026
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2014/1026,
      author = {H.  W.  Lenstra Jr. and A.  Silverberg},
      title = {Lattices with Symmetry},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/1026},
      year = {2014},
      url = {https://eprint.iacr.org/2014/1026}
}