Welcome to the resource topic for 2016/910
Title:
The closest vector problem in tensored root lattices of type A and in their duals
Authors: Léo Ducas, 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}).
ePrint: https://eprint.iacr.org/2016/910
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .