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


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 \otimes A^*_n$). 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^*$ 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 $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})$.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Lattice based cryptographyCyclotomic latticesTensored root latticesClosest vector problemMaximum likelihood decoding.
Contact author(s)
ducas @ cwi nl
2016-09-21: revised
2016-09-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Léo Ducas and Wessel P. J.  van Woerden},
      title = {The closest vector problem in tensored root lattices of type A and in their duals},
      howpublished = {Cryptology ePrint Archive, Paper 2016/910},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.