Deciding orthogonality in construction - A lattices

Karthekeyan Chandrasekaran, Venkata Gandikota, Elena Grigorescu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 + qZn, 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.

Original languageEnglish (US)
Title of host publication35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2015
EditorsPrahladh Harsha, G. Ramalingam
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages151-162
Number of pages12
ISBN (Electronic)9783939897972
DOIs
StatePublished - Dec 1 2015
Externally publishedYes
Event35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2015 - Bangalore, India
Duration: Dec 16 2015Dec 18 2015

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume45
ISSN (Print)1868-8969

Conference

Conference35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2015
Country/TerritoryIndia
CityBangalore
Period12/16/1512/18/15

Keywords

  • Construction-a
  • Lattice isomorphism
  • Orthogonal decomposition
  • Orthogonal lattices

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Deciding orthogonality in construction - A lattices'. Together they form a unique fingerprint.

Cite this