Theory Seminar

On the Quantitative Hardness of the Closest Vector Problem

Huck Bennett

Postdoctoral Researcher
Northwestern University
Friday, January 25, 2019
10:30am - 11:30am
BBB 3725

Add to Google Calendar

About the Event

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).

Additional Information

Sponsor(s): Theory Group

Faculty Sponsor: Chris Peikert

Open to: Public