Lattices with Symmetry
- Author(s): Lenstra, HW
- Silverberg, A
- et al.
Published Web Locationhttps://doi.org/10.1007/s00145-016-9235-7
© 2016, International Association for Cryptologic Research. 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.