Noah Stephens-Davidowitz

STOC Conference 2023 Conference Paper

Lattice Problems beyond Polynomial Time

• Divesh Aggarwal
• Huck Bennett
• Zvika Brakerski
• Alexander Golovnev
• Rajendra Kumar 0002
• Zeyong Li
• Spencer Peters
• Noah Stephens-Davidowitz

SODA Conference 2021 Conference Paper

Dimension-Preserving Reductions Between SVP and CVP in Different p -Norms

• Divesh Aggarwal
• Yanlin Chen
• Rajendra Kumar 0002
• Zeyong Li
• Noah Stephens-Davidowitz

We show a number of reductions between the Shortest Vector Problem and the Closest Vector Problem over lattices in different ℓ p norms (SVP p and CVP p respectively). Specifically, we present the following 2 ∊m -time reductions for 1 ≤ p ≤ q ≤ ∞, which all increase the rank n and dimension m of the input lattice by at most one: • a reduction from Õ (1/ ∊ 1 / p ) γ -approximate SVP q to γ -approximate SVP p; • a reduction from Õ (1/ ∊ 1/ p ) γ -approximate CVP p to γ -approximate CVP q; and • a reduction from Õ (1/ ∊ 1+1/ p )-CVP q to (1 + ∊ )-unique SVP p (which in turn trivially reduces to (1 + ∊ )-approximate SVP p ). The last reduction is interesting even in the case p = q. In particular, this special case subsumes much prior work adapting 2 O ( m ) -time SVP p algorithms to solve O (1)-approximate CVP p. In fact, we show a stronger result in the special case when 1 ≤ p = q ≤ 2 and the SVP p oracle is exact: a reduction from O (1/ ∊ 1 / p )-CVP p to (exact) SVP p in 2 ∊m time. For example, taking ∊ = log m/m and p = 2 gives a slight improvement over Kannan's celebrated polynomial-time reduction from to SVP 2. We also note that the last two reductions can be combined to give a reduction from approximate-CVP p to SVP q for any p and q, regardless of whether p ≤ q or p > q. Our techniques combine those from the recent breakthrough work of Eisenbrand and Venzin [21] (which showed how to adapt the current fastest known algorithm for these problems in the ℓ 2 norm to all ℓ p norms) together with sparsification-based techniques.

SODA Conference 2021 Conference Paper

Fine-grained hardness of CVP(P) - Everything that we can prove (and nothing else)

• Divesh Aggarwal
• Huck Bennett
• Alexander Golovnev
• Noah Stephens-Davidowitz

We show a number of fine-grained hardness results for the Closest Vector Problem in the ℓ p norm (CVP p ), and its approximate and non-uniform variants. First, we show that CVP p cannot be solved in 2 (1– ∊ ) n time for all p ∉ 2ℤ and ∊ > 0, assuming the Strong Exponential Time Hypothesis (SETH). Second, we extend this by showing that there is no 2 (1– ∊ ) n -time algorithm for approximating CVP p to within a constant factor γ for such p assuming a “gap” version of SETH, with an explicit relationship between γ, p, and the arity k = k ( ∊ ) of the underlying hard CSP. Third, we show the same hardness result for (exact) CVP p with preprocessing (assuming non-uniform SETH). For exact “plain” CVP p, the same hardness result was shown in [Bennett, Golovnev, and Stephens-Davidowitz FOCS 2017] for all but finitely many p ∉ 2ℤ, where the set of exceptions depended on ∊ and was not explicit. For the approximate and preprocessing problems, only very weak bounds were known prior to this work. We also show that the restriction to p ∉ 2ℤ is in some sense inherent. In particular, we show that no “natural” reduction can rule out even a 2 3 n/ 4 -time algorithm for CVP 2 under SETH. For this, we prove that the possible sets of closest lattice vectors to a target in the ℓ 2 norm have quite rigid structure, which essentially prevents them from being as expressive as 3-CNFs. We prove these results using techniques from many different fields, including complex analysis, functional analysis, additive combinatorics, and discrete Fourier analysis. E. g. , along the way, we give a new (and tighter) proof of Szemerédi's cube lemma for the boolean cube. Please see the full version of this paper for the proofs of these results [1].

FOCS Conference 2019 Conference Paper

SETH-Hardness of Coding Problems

• Noah Stephens-Davidowitz
• Vinod Vaikuntanathan

We show that assuming the strong exponential-time hypothesis (SETH), there are no non-trivial algorithms for the nearest codeword problem (NCP), the minimum distance problem (MDP), or the nearest codeword problem with preprocessing (NCPP) on linear codes over any finite field. More precisely, we show that there are no NCP, MDP, or NCPP algorithms running in time q (1-ε)n for any constant ε > 0 for codes with q n codewords. (In the case of NCPP, we assume non-uniform SETH.) We also show that there are no sub-exponential time algorithms for y-approximate versions of these problems for some constant -y > 1, under different versions of the exponential-time hypothesis.

STOC Conference 2018 Conference Paper

(Gap/S)ETH hardness of SVP

• Divesh Aggarwal
• Noah Stephens-Davidowitz

STOC Conference 2017 Conference Paper

A reverse Minkowski theorem

• Oded Regev 0001
• Noah Stephens-Davidowitz

We prove a conjecture due to Dadush, showing that if ℒ⊂ ℝ n is a lattice such that det(ℒ′) 1 for all sublattices ℒ′ ⊆ ℒ, then $$\sum_{ y ∈ℒ}^e -t 2||y||2 ≤3/2,$$ where t := 10(logn + 2). From this we also derive bounds on the number of short lattice vectors and on the covering radius.

FOCS Conference 2017 Conference Paper

On the Quantitative Hardness of CVP

• Huck Bennett
• Alexander Golovnev
• Noah Stephens-Davidowitz

For odd integers p ≥ 1 (and p = ∞), we show that the Closest Vector Problem in the ℓ p norm (CVP p ) over rank n lattices cannot be solved in 2 (1-ε)n time for any constant ε > 0 unless the Strong Exponential Time Hypothesis (SETH) fails. We then extend this result to “almost all” values of p ≥ 1, not including the even integers. 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. In particular, our result applies for any p = p(n) ≠ 2 that approaches 2 as n → ∞. We also show a similar SETH-hardness result for SVP ∞; hardness of approximating CVP p to within some constant factor under the so-called Gap-ETH assumption; and other hardness results for CVP p and CVPP p for any 1 ≤ p <; ∞ under different assumptions.

STOC Conference 2017 Conference Paper

Pseudorandomness of ring-LWE for any ring and modulus

• Chris Peikert
• Oded Regev 0001
• Noah Stephens-Davidowitz

We give a polynomial-time quantum reduction from worst-case (ideal) lattice problems directly to decision (Ring-)LWE. This extends to decision all the worst-case hardness results that were previously known for the search version, for the same or even better parameters and with no algebraic restrictions on the modulus or number field. Indeed, our reduction is the first that works for decision Ring-LWE with any number field and any modulus.

SODA Conference 2016 Conference Paper

Discrete Gaussian Sampling Reduces to CVP and SVP

• Noah Stephens-Davidowitz

FOCS Conference 2015 Conference Paper

Solving the Closest Vector Problem in 2^n Time - The Discrete Gaussian Strikes Again!

• Divesh Aggarwal
• Daniel Dadush
• Noah Stephens-Davidowitz

We give a 2 n+o(n) -time and space randomized algorithm for solving the exact Closest Vector Problem (CVP) on n-dimensional Euclidean lattices. This improves on the previous fastest algorithm, the deterministic Õ(4 n )-time and Õ(2 n )-space algorithm of Micciancio and Voulgaris [1]. We achieve our main result in three steps. First, we show how to modify the sampling algorithm from [2] to solve the problem of discrete Gaussian sampling over lattice shifts, L - t, with very low parameters. While the actual algorithm is a natural generalization of [2], the analysis uses substantial new ideas. This yields a 2 n+o(n) -time algorithm for approximate CVP with the very good approximation factor γ = 1 + 2 -o(n/ log n). Second, we show that the approximate closest vectors to a target vector t can be grouped into “lower-dimensional clusters, ” and we use this to obtain a recursive reduction from exact CVP to a variant of approximate CVP that “behaves well with these clusters. ” Third, we show that our discrete Gaussian sampling algorithm can be used to solve this variant of approximate CVP. The analysis depends crucially on some new properties of the discrete Gaussian distribution and approximate closest vectors, which might be of independent interest.

STOC Conference 2015 Conference Paper

Solving the Shortest Vector Problem in 2 n Time Using Discrete Gaussian Sampling: Extended Abstract

• Divesh Aggarwal
• Daniel Dadush
• Oded Regev 0001
• Noah Stephens-Davidowitz

We give a randomized 2 n+o(n) -time and space algorithm for solving the Shortest Vector Problem (SVP) on n-dimensional Euclidean lattices. This improves on the previous fastest algorithm: the deterministic ~O(4 n )-time and ~O(2 n )-space algorithm of Micciancio and Voulgaris (STOC 2010, SIAM J. Comp. 2013). In fact, we give a conceptually simple algorithm that solves the (in our opinion, even more interesting) problem of discrete Gaussian sampling (DGS). More specifically, we show how to sample 2 n/2 vectors from the discrete Gaussian distribution at any parameter in 2 n+o(n) time and space. (Prior work only solved DGS for very large parameters.) Our SVP result then follows from a natural reduction from SVP to DGS. In addition, we give a more refined algorithm for DGS above the so-called smoothing parameter of the lattice, which can generate 2 n/2 discrete Gaussian samples in just 2 n/2+o(n) time and space. Among other things, this implies a 2 n/2+o(n) -time and space algorithm for 1.93-approximate decision SVP.