For the primal case $A_m \otimes A_n$, we provide a full characterization of the Voronoi region in terms of simple cycles in the complete directed bipartite graph $K_{m+1,n+1}$. This leads ---relying on the Bellman-Ford algorithm for negative cycle detection--- to a CVP algorithm running in *polynomial time*. Precisely, our algorithm performs $O(l\ m^2 n^2 \min\{m,n\})$ operations on reals, where $l$ is the number of bits per coordinate of the input target. For the dual case, we use a gluing-construction to solve CVP in sub-exponential time $O(n m^{n+1})$.
Category / Keywords: public-key cryptography / Lattice based cryptography, Cyclotomic lattices, Tensored root lattices, Closest vector problem, Maximum likelihood decoding. Date: received 19 Sep 2016, last revised 21 Sep 2016 Contact author: ducas at cwi nl Available format(s): PDF | BibTeX Citation Version: 20160921:191802 (All versions of this report) Short URL: ia.cr/2016/910 Discussion forum: Show discussion | Start new discussion