An Efficient Quantum Algorithm for a Variant of the Closest Lattice-Vector Problem

The Systematic Normal Form (SysNF) is a canonical form of lattices introduced in [Eldar,Shor 16], in which the basis entries satisfy a certain co-primality condition. Using a smooth analysis of lattices by SysNF lattices we design a quantum algorithm that can efficiently solve the following variant of the bounded-distance-decoding problem: given a lattice L, a vector v, and numbers b = {lambda}_1(L)/n^{17}, a = {lambda}_1(L)/n^{13} decide if vs distance from L is in the range [a/2, a] or at most b, where {lambda}_1(L) is the length of Ls shortest non-zero vector. Improving these parameters to a = b = {lambda}_1(L)/sqrt{n} would invalidate one of the security assumptions of the Learning-with-Errors (LWE) cryptosystem against quantum attacks.