The closest vector problem in tensored root lattices of type A and in their duals (Q1692156)

The closest vector problem (also known as maximum likelihood decoding) is a fundamental question in lattice based cryptography. The authors study the closest vector problem in the tensor root lattices of Type A, \((A_m \otimes A_n)\), and in their duals \((A_m^* \otimes A_n^*).\) They solve the closest vector problem in \(Z[\zeta_c]\) and \(Z[\zeta_c]^\lor\) for conductors of the form \(c = 2^\alpha p ^\beta q^\gamma\) for any two odd primes \(p\) and \(q\). In the primal case \((A_m \otimes A_n)\), they give a full characterization of the Voronoi region in terms of simple cycles in the complete directed bipartite graph \(K_{m+1,n+1}.\) Using this, they obtain a closest vector problem algorithm running in polynomial time. The algorithm performs \(O(l m^2n^2 \min \{ m,n \})\) operations on reals, where \(l\) is the number of bits per coordinate of the input target. In the dual case a gluing construction is used to solve the closest vector problem in sub-exponential time \(O(nm^{n+1})\).