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 \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})$.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Lattice based cryptographyCyclotomic latticesTensored root latticesClosest vector problemMaximum likelihood decoding.
Contact author(s)
ducas @ cwi nl
History
2016-09-21: revised
2016-09-19: received
See all versions
Short URL
https://ia.cr/2016/910
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.