Deciding orthogonality in construction-A lattices

Karthekeyan Chandrasekaran, Venkata Gandikota, Elena Grigorescu

Research output: Contribution to journalArticlepeer-review

Abstract

Lattices are discrete mathematical objects with widespread applications to integer programs as well as modern cryptography. An important class of lattices are those that possess an orthogonal basis, since if such an orthogonal basis is known, then many other fundamental problems on lattices can be solved easily (e.g., the Closest Vector Problem). However, intriguingly, deciding whether a lattice has an orthogonal basis 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. We use this characterization to give an efficient algorithm to solve the orthogonality decision problem. Our algorithm also finds an orthogonal basis if one exists for this family of lattices.

Original languageEnglish (US)
Pages (from-to)1244-1262
Number of pages19
JournalSIAM Journal on Discrete Mathematics
Volume31
Issue number2
DOIs
StatePublished - 2017
Externally publishedYes

Keywords

  • Construction-A lattices
  • Lattice isomorphism
  • Orthogonal lattices

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

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

Cite this