  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 \emph{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+q\mathbb{Z}^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. 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. We believe that these results could provide a better understanding of
the complexity of the orthogonality decision problem for general lattices.
