On the Quantitative Hardness of the Closest Vector Problem

Computational problems on lattices have a wealth of applications in
computer science, and, in recent years, lattice-based cryptography has
emerged as the leading candidate for post-quantum cryptography. In
order to ensure the security of such cryptosystems, it is crucial to
understand the precise, quantitative computational complexity of
lattice problems.

In this talk, I will discuss work that initiates the study of the
quantitative hardness of lattice problems. As our main result, we
prove that for almost every p \geq 1 and every constant eps > 0 there
is no 2^{(1-\eps)n}-time algorithm for the Closest Vector Problem with
respect to the \ell_p norm (CVP_p) assuming the Strong Exponential
Time Hypothesis (SETH). This comes tantalizingly close to settling the
quantitative time complexity of the important special case of CVP_2
(i.e., CVP in the Euclidean norm) for which a 2^{n + o(n)}-time
algorithm is known, and is necessary (but not sufficient) for ensuring
the security of about-to-be-deployed lattice-based cryptosystems. If,
for example, there existed a 2^{n/20}-time algorithm for CVP then
these schemes would be insecure in practice.

Based on joint work with Alexander Golovnev and Noah
Stephens-Davidowitz (https://arxiv.org/abs/1704.03928).