Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Revisiting the Gentry-Szydlo Algorithm

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNSC,volume 8616))

Included in the following conference series:

  • 4488Accesses

  • 13Citations

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.

Similar content being viewed by others

Keywords

References

  1. Atiyah, M.F., Macdonald, I.G.: Introduction to commutative algebra. Addison-Wesley Publishing Co., Reading (1969)

    Google Scholar 

  2. Garg, S., Gentry, C., Halevi, S.: Candidate Multilinear Maps from Ideal Lattices. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 1–17. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  3. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) Proceedings of the 41st ACM Symposium on Theory of Computing—STOC 2009, pp. 169–178. ACM, New York (2009)

    Google Scholar 

  4. Gentry, C.: A fully homomorphic encryption scheme, Stanford University PhD thesis (2009),http://crypto.stanford.edu/craig/craig-thesis.pdf

  5. Gentry, C.: email (May 9, 2012)

    Google Scholar 

  6. Gentry, C., Szydlo, M.: Cryptanalysis of the Revised NTRU Signature Scheme. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 299–320. Springer, Heidelberg (2002), Full version athttp://www.szydlo.com/ntru-revised-full02.pdf

    Chapter  Google Scholar 

  7. Heath-Brown, D.R.: Zero-free regions for DirichletL-functions, and the least prime in an arithmetic progression. Proc. London Math. Soc. 64(3), 265–338 (1992)

    Article MathSciNet MATH  Google Scholar 

  8. Lang, S.: Algebra, Graduate Texts in Mathematics, 3rd edn., vol. 211. Springer-Verlag, New York (2002)

    Google Scholar 

  9. Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515–534 (1982)

    Article MathSciNet MATH  Google Scholar 

  10. Lenstra Jr., H.W.: Lattices, in Algorithmic number theory: lattices, number fields, curves and cryptography. In: Buhler, J.P., Stevenhagen, P. (eds.) Math. Sci. Res. Inst. Publ., vol. 44, pp. 127–181. Cambridge University Press, Cambridge (2008)

    Google Scholar 

  11. Smart, N.: personal communication

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Mathematisch Instituut, Universiteit Leiden, The Netherlands

    H. W. Lenstra

  2. Department of Mathematics, University of California, Irvine, Irvine, CA, USA

    A. Silverberg

Authors
  1. H. W. Lenstra
  2. A. Silverberg

Editor information

Editors and Affiliations

  1. Yahoo Labs, 701 Firstz Avenue, 94089, Sunnyvale, CA, USA

    Juan A. Garay

  2. The City College of New York, 160 Convent Avenue, 10031, New York, NY, USA

    Rosario Gennaro

Rights and permissions

Copyright information

© 2014 International Association for Cryptologic Research

About this paper

Cite this paper

Lenstra, H.W., Silverberg, A. (2014). Revisiting the Gentry-Szydlo Algorithm. In: Garay, J.A., Gennaro, R. (eds) Advances in Cryptology – CRYPTO 2014. CRYPTO 2014. Lecture Notes in Computer Science, vol 8616. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44371-2_16

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp