Paper 2014/430

Revisiting the Gentry-Szydlo Algorithm

H. W. Lenstra and A. Silverberg

Abstract

We put the Gentry-Szydlo algorithm into a mathematical framework, and show that it is part of a general theory of ``lattices with symmetry''. 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. This sheds new light on the Gentry-Szydlo algorithm, and the ideas should be applicable to a range of questions in cryptography.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in CRYPTO 2014
Keywords
latticesGentry-Szydlo algorithmideal latticeslattice-based cryptography
Contact author(s)
asilverb @ uci edu
History
2014-06-12: received
Short URL
https://ia.cr/2014/430
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/430,
      author = {H.  W.  Lenstra and A.  Silverberg},
      title = {Revisiting the Gentry-Szydlo Algorithm},
      howpublished = {Cryptology ePrint Archive, Paper 2014/430},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/430}},
      url = {https://eprint.iacr.org/2014/430}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.