On the Lattice Distortion Problem

Authors Huck Bennett, Daniel Dadush, Noah Stephens-Davidowitz



PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.9.pdf
  • Filesize: 0.6 MB
  • 17 pages

Document Identifiers

Author Details

Huck Bennett
Daniel Dadush
Noah Stephens-Davidowitz

Cite AsGet BibTex

Huck Bennett, Daniel Dadush, and Noah Stephens-Davidowitz. On the Lattice Distortion Problem. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ESA.2016.9

Abstract

We introduce and study the Lattice Distortion Problem (LDP). LDP asks how "similar" two lattices are. I.e., what is the minimal distortion of a linear bijection between the two lattices? LDP generalizes the Lattice Isomorphism Problem (the lattice analogue of Graph Isomorphism), which simply asks whether the minimal distortion is one. As our first contribution, we show that the distortion between any two lattices is approximated up to a n^{O(log(n))} factor by a simple function of their successive minima. Our methods are constructive, allowing us to compute low-distortion mappings that are within a 2^{O(n*log(log(n))/log(n))} factor of optimal in polynomial time and within a n^{O(log(n))} factor of optimal in singly exponential time. Our algorithms rely on a notion of basis reduction introduced by Seysen (Combinatorica 1993), which we show is intimately related to lattice distortion. Lastly, we show that LDP is NP-hard to approximate to within any constant factor (under randomized reductions), by a reduction from the Shortest Vector Problem.
Keywords
  • lattices
  • lattice distortion
  • lattice isomoprhism
  • geometry of numbers
  • basis reduction

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Miklós Ajtai. Generating hard instances of lattice problems. In STOC, 1996. Google Scholar
  2. Miklós Ajtai. The Shortest Vector Problem in L2 is NP-hard for randomized reductions. In STOC, 1998. URL: http://dx.doi.org/10.1145/276698.276705.
  3. Miklós Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the Shortest Lattice Vector Problem. In STOC, pages 601-610, 2001. URL: http://dx.doi.org/10.1145/380752.380857.
  4. Sanjeev Arora, Alan Frieze, and Haim Kaplan. A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. Mathematical Programming, 2002. URL: http://dx.doi.org/10.1007/s101070100271.
  5. Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and Yadu Vasudev. Approximate Graph Isomorphism. In Mathematical Foundations of Computer Science, 2012. Google Scholar
  6. L. Babai. Graph Isomorphism in quasipolynomial time, 2016. URL: http://arxiv.org/abs/1512.03547.
  7. W. Banaszczyk. New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen, 296(1):625-635, 1993. URL: http://dx.doi.org/10.1007/BF01445125.
  8. Zvika Brakerski and Vinod Vaikuntanathan. Lattice-based FHE as secure as PKE. In ITCS, 2014. URL: http://dx.doi.org/10.1145/2554797.2554799.
  9. J. Conway and N.J.A. Sloane. Sphere Packings, Lattices and Groups. Springer New York, 1998. Google Scholar
  10. Nicolas Gama and Phong Q. Nguyen. Finding short lattice vectors within Mordell’s inequality. In STOC, 2008. URL: http://dx.doi.org/10.1145/1374376.1374408.
  11. Craig Gentry. Fully homomorphic encryption using ideal lattices. In STOC, 2009. Google Scholar
  12. Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In STOC, 2008. Google Scholar
  13. Oded Goldreich, Daniele Micciancio, Shmuel Safra, and Jean-Paul Seifert. Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. Information Processing Letters, 71(2):55-61, 1999. URL: http://dx.doi.org/10.1016/S0020-0190(99)00083-6.
  14. Ishay Haviv and Oded Regev. Tensor-based hardness of the Shortest Vector Problem to within almost polynomial factors. Theory of Computing, 8(23):513-531, 2012. Preliminary version in STOC'07. Google Scholar
  15. Ishay Haviv and Oded Regev. On the Lattice Isomorphism Problem. In SODA, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.29.
  16. Ravi Kannan. Minkowski’s convex body theorem and Integer Programming. Mathematics of Operations Research, 12(3):pp. 415-440, 1987. URL: http://www.jstor.org/stable/3689974.
  17. Subhash Khot. Hardness of approximating the Shortest Vector Problem in lattices. Journal of the ACM, 52(5):789-808, September 2005. Preliminary version in FOCS'04. Google Scholar
  18. A. Korkine and G. Zolotareff. Sur les formes quadratiques. Mathematische Annalen, 6(3):366-389, 1873. URL: http://dx.doi.org/10.1007/BF01442795.
  19. J. C. Lagarias, Hendrik W. Lenstra Jr., and Claus-Peter Schnorr. Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice. Combinatorica, 10(4):333-348, 1990. URL: http://dx.doi.org/10.1007/BF02128669.
  20. A.K. Lenstra, H.W. Lenstra Jr., and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515-534, 1982. URL: http://dx.doi.org/10.1007/BF01457454.
  21. Hendrik W. Lenstra Jr. and Alice Silverberg. Lattices with symmetry, 2014. URL: http://arxiv.org/abs/1501.00178.
  22. Daniele Micciancio. The Shortest Vector Problem is NP-hard to approximate to within some constant. SIAM Journal on Computing, 30(6):2008-2035, March 2001. Preliminary version in FOCS 1998. Google Scholar
  23. Daniele Micciancio and Oded Regev. Worst-case to average-case reductions based on Gaussian measures. SIAM Journal on Computing, 37(1):267-302, 2007. Google Scholar
  24. Daniele Micciancio and Panagiotis Voulgaris. A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. SIAM J. Comput., 42(3):1364-1391, 2013. URL: http://dx.doi.org/10.1137/100811970.
  25. H. Minkowski. Geometrie der Zahlen. Number v. 1 in Geometrie der Zahlen. B.G. Teubner, 1910. Google Scholar
  26. W. Plesken and B. Souvignier. Computing isometries of lattices. J. Symbolic Comput., 24(3-4):327-334, 1997. Computational algebra and number theory (London, 1993). Google Scholar
  27. Oded Regev. Lecture notes from course on "Lattices in Computer Science", 2009. URL: http://www.cims.nyu.edu/~regev/teaching/lattices_fall_2009/index.html.
  28. Oded Regev. On lattices, Learning with Errors, random linear codes, and cryptography. Journal of the ACM, 56(6):Art. 34, 40, 2009. URL: http://dx.doi.org/10.1145/1568318.1568324.
  29. C.P. Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science, 1987. URL: http://dx.doi.org/10.1016/0304-3975(87)90064-8.
  30. Martin Seysen. Simultaneous reduction of a lattice basis and its reciprocal basis. Combinatorica, 13(3):363-376, 1993. URL: http://dx.doi.org/10.1007/BF01202355.
  31. Carl Ludwig Siegel. A mean value theorem in geometry of numbers. Annals of Mathematics, 46(2):pp. 340-347, 1945. URL: http://www.jstor.org/stable/1969027.
  32. Mathieu Dutour Sikiric, Achill Schürmann, and Frank Vallentin. Complexity and algorithms for computing Voronoi cells of lattices. Math. Comput., 78(267):1713-1731, 2009. URL: http://dx.doi.org/10.1090/S0025-5718-09-02224-8.
  33. Lloyd N. Trefethen and David Bau III. Numerical Linear Algebra. SIAM: Society for Industrial and Applied Mathematics, 1997. ISBN 0898713617. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail