Paper 2016/910

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

Léo Ducas and Wessel P. J. van Woerden

Abstract

In this work we consider the closest vector problem (CVP) ---a problem also known as maximum-likelihood decoding--- in the tensor of two root lattices of type A ($A_m\otimes A_n$), as well as in their duals ($A_m^{\ast }\otimes A_n^{\ast }$). This problem is mainly motivated by {\em lattice based cryptography}, where the cyclotomic rings $\mathbb{Z}[{\zeta }_c]$ (resp. its co-different $\mathbb{Z}[{\zeta }_c{]}^{\vee }$) play a central role, and turn out to be isomorphic as lattices to tensors of $A^{\ast }$ lattices (resp. $A$ root lattices). In particular, our results lead to solving CVP in $\mathbb{Z}[{\zeta }_c]$ and in $\mathbb{Z}[{\zeta }_c{]}^{\vee }$ for conductors of the form $c=2^{\alpha }{p}^{\beta }{q}^{\gamma }$ for any two odd primes $p,q$. For the primal case $$, we provide a full characterization of the Voronoi region in terms of simple cycles in the complete directed bipartite graph $$. This leads ---relying on the Bellman-Ford algorithm for negative cycle detection--- to a CVP algorithm running in *polynomial time*. Precisely, our algorithm performs $$ operations on reals, where $$ 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 $$.