Deciding Orthogonality in Construction-A Lattices

Authors Karthekeyan Chandrasekaran, Venkata Gandikota, Elena Grigorescu



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2015.151.pdf
  • Filesize: 447 kB
  • 12 pages

Document Identifiers

Author Details

Karthekeyan Chandrasekaran
Venkata Gandikota
Elena Grigorescu

Cite AsGet BibTex

Karthekeyan Chandrasekaran, Venkata Gandikota, and Elena Grigorescu. Deciding Orthogonality in Construction-A Lattices. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 151-162, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.FSTTCS.2015.151

Abstract

Lattices are discrete mathematical objects with widespread applications to integer programs as well as modern cryptography. A fundamental problem in both domains is the Closest Vector Problem (popularly known as CVP). It is well-known that CVP can be easily solved in lattices that have an orthogonal basis if the orthogonal basis is specified. This motivates the orthogonality decision problem: verify whether a given lattice has an orthogonal basis. Surprisingly, the orthogonality decision problem is not known to be either NP-complete or in P. In this paper, we focus on the orthogonality decision problem for a well-known family of lattices, namely Construction-A lattices. These are lattices of the form C + qZ^n, where C is an error-correcting q-ary code, and are studied in communication settings. We provide a complete characterization of lattices obtained from binary and ternary codes using Construction- A that have an orthogonal basis. This characterization leads to an efficient algorithm solving the orthogonality decision problem, which also finds an orthogonal basis if one exists for this family of lattices. We believe that these results could provide a better understanding of the complexity of the orthogonality decision problem in general.
Keywords
  • Orthogonal Lattices
  • Construction-A
  • Orthogonal Decomposition
  • Lattice isomorphism

Metrics

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

References

  1. Miklós Ajtai. Generating hard instances of lattice problems (extended abstract). In STOC, pages 99-108, 1996. Google Scholar
  2. Laszlo Babai. Automorphism groups, isomorphism, reconstruction. In Handbook of Combinatorics, volume chapter 27, pages 1447-1540. North-Holland, 1996. Google Scholar
  3. H.C. Chan, C.A. Rodger, and J. Seberry. On inequivalent weighing matrices. Ars Combinatoria, 21(A):229-333, 1986. Google Scholar
  4. Karthekeyan Chandrasekaran, Venkata Gandikota, and Elena Grigorescu. Deciding Orthogonality in Construction-A Lattices. Under Preparation, 2015. Google Scholar
  5. John H. Conway and Neil J. A. Sloane. Sphere Packings, Lattices and Groups. Springer-Verlag, New York, 1998. Google Scholar
  6. Ishay Haviv and Oded Regev. On the lattice isomorphism problem. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 391-404, 2014. Google Scholar
  7. Ravi Kannan. Improved algorithms for integer programming and related lattice problems. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 193-206, 1983. Google Scholar
  8. Arjen K. Lenstra, Hendrik W. Lenstra, and Lászlo Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261:515-534, 1982. Google Scholar
  9. Hendrik W. Lenstra and Alice Silverberg. Lattices with symmetries. Manuscript, 2014. Google Scholar
  10. Hendrik W. Lenstra and Alice Silverberg. Revisiting the gentry-szydlo algorithm. In Advances in Cryptology - CRYPTO 2014, volume 8616 of Lecture Notes in Computer Science, pages 280-296. Springer Berlin Heidelberg, 2014. Google Scholar
  11. Daniele Micciancio. Lecture notes on lattice algorithms and applications, Winter 2010. Lecture 2. Google Scholar
  12. Daniele Micciancio and Oded Regev. Lattice-based cryptography. In Post-Quantum Cryptography, pages 147-191. Springer Berlin Heidelberg, 2009. Google Scholar
  13. Wilhelm Plesken and Bernd Souvignier. Computing isometries of lattices. J. Symb. Comput., 24(3/4):327-334, 1997. Google Scholar
  14. Claus-Peter Schnorr. Factoring integers by CVP algorithms. In Number Theory and Cryptography - Papers in Honor of Johannes Buchmann on the Occasion of His 60th Birthday, pages 73-93, 2013. Google Scholar
  15. 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. 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