Paper 2014/1026
Lattices with Symmetry
H. W. Lenstra Jr. and 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.
Note: Published in Journal of Cryptology. Minor typos corrected.
Metadata
- Available format(s)
-
PDF
- Publication info
- A minor revision of an IACR publication in JOC 2016
- Keywords
- latticesGentry-Szydlo algorithmideal latticeslattice-based cryptography
- Contact author(s)
- asilverb @ math uci edu
- History
- 2016-10-04: last of 2 revisions
- 2015-01-02: received
- See all versions
- Short URL
- https://ia.cr/2014/1026
- License
-
CC BY
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}
}
