TY - JOUR
T1 - Deciding orthogonality in construction-A lattices
AU - Chandrasekaran, Karthekeyan
AU - Gandikota, Venkata
AU - Grigorescu, Elena
N1 - The research of the second and third authors was supported in part by NSF CCF-1649515.
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
KW - Construction-A lattices
KW - Lattice isomorphism
KW - Orthogonal lattices
UR - http://www.scopus.com/inward/record.url?scp=85022095804&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85022095804&partnerID=8YFLogxK
U2 - 10.1137/15M1054766
DO - 10.1137/15M1054766
M3 - Article
AN - SCOPUS:85022095804
SN - 0895-4801
VL - 31
SP - 1244
EP - 1262
JO - SIAM Journal on Discrete Mathematics
JF - SIAM Journal on Discrete Mathematics
IS - 2
ER -