Deciding orthogonality in construction-A lattices

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 + qZⁿ, 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.