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 maximumlikelihood 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 codifferent $\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 BellmanFord 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 gluingconstruction to solve CVP in subexponential time $O(n m^{n+1})$.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 Lattice based cryptographyCyclotomic latticesTensored root latticesClosest vector problemMaximum likelihood decoding.
 Contact author(s)
 ducas @ cwi nl
 History
 20160921: revised
 20160919: received
 See all versions
 Short URL
 https://ia.cr/2016/910
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/910, 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{https://eprint.iacr.org/2016/910}}, url = {https://eprint.iacr.org/2016/910} }