On compact representations of Voronoi cells of lattices
In a seminal work, Micciancio & Voulgaris (2010) described a deterministic single-exponential time algorithm for the Closest Vector Problem (CVP) on lattices. It is based on the computation of the Voronoi cell of the given lattice and thus may need exponential space as well. We address the major open question whether there exists such an algorithm that requires only polynomial space. To this end, we define a lattice basis to be c-compact if every facet normal of the Voronoi cell is a linear combination of the basis vectors using coefficients that are bounded by c in absolute value. Given such a basis, we get a polynomial space algorithm for CVP whose running time naturally depends on c. Thus, our main focus is the behavior of the smallest possible value of c, with the following results: There always exist c-compact bases, where c is bounded by n^2 for an n-dimension lattice; there are lattices not admitting a c-compact basis with c growing sublinearly with the dimension; and every lattice with a zonotopal Voronoi cell has a 1-compact basis.
WOS:000493314100020
1811.08532
2018-11-20
Cham
Lecture Notes in Computer Science; 11480
261
274
REVIEWED
Event name | Event place | Event date |
Ann Arbor, MI, USA | May 22-24, 2019 | |
Funder | Grant Number |
FNS | 163071 |