International Association for Cryptologic Research

International Association
for Cryptologic Research


Noah Stephens-Davidowitz


Just how hard are rotations of Z^n? Algorithms and cryptography with the simplest lattice
Huck Bennett Atul Ganju Pura Peetathawatchai Noah Stephens-Davidowitz
We study the computational problem of finding a shortest non-zero vector in a rotation of $\Z^n$, which we call $\Z$SVP. It has been a long-standing open problem to determine if a polynomial-time algorithm for $\Z$SVP exists, and there is by now a beautiful line of work showing how to solve it efficiently in certain very special cases. However, despite all of this work, the fastest known algorithm that is proven to solve $\Z$SVP is still simply the fastest known algorithm for solving SVP (i.e., the problem of finding shortest non-zero vectors in arbitrary lattices), which runs in $2^{n + o(n)}$ time. We therefore set aside the (perhaps impossible) goal of finding an efficient algorithm for $\Z$SVP and instead ask what else we can say about the problem. E.g., can we find any non-trivial speedup over the best known SVP algorithm? And, if $\Z$SVP actually is hard, then what consequences would follow? Our results are as follows. 1. We show that $\Z$SVP is in a certain sense strictly easier than SVP on arbitrary lattices. In particular, we show how to reduce $\Z$SVP to an \emph{approximate} version of SVP in the same dimension (in fact, even to approximate \emph{unique} SVP, for any constant approximation factor). Such a reduction seems very unlikely to work for SVP itself, so we view this as a qualitative separation of $\Z$SVP from SVP. As a consequence of this reduction, we obtain a $2^{n/2 + o(n)}$-time algorithm for $\Z$SVP, i.e., the first non-trivial speedup over the best known algorithm for SVP on general lattices. (In fact, this reduction works for a more general class of lattices---semi-stable lattices with not-too-large $\lambda_1$.) 2. We show a simple public-key encryption scheme that is secure if (an appropriate variant of) $\Z$SVP is actually hard. Specifically, our scheme is secure if it is difficult to distinguish (in the worst case) a rotation of $\Z^n$ from \emph{either} a lattice with all non-zero vectors longer than $\sqrt{n/\log n}$ \emph{or} a lattice with smoothing parameter significantly smaller than the smoothing parameter of $\Z^n$. The latter result has an interesting qualitative connection with reverse Minkowski theorems, which in some sense say that ``$\Z^n$ has the largest smoothing parameter.'' 3. We show a distribution of bases $\basis$ for rotations of $\Z^n$ such that, if $\Z$SVP is hard for \emph{any} input basis, then $\Z$SVP is hard on input $\basis$. This gives a satisfying theoretical resolution to the problem of sampling hard bases for $\Z^n$, which was studied by Blanks and Miller. This worst-case to average-case reduction is also crucially used in the analysis of our encryption scheme. (In recent independent work that appeared as a preprint before this work, Ducas and van Woerden showed essentially the same thing for general lattices, and they also used this to analyze the security of a public-key encryption scheme. Similar ideas also appeared in prior work in different contexts.) 4. We perform experiments to determine how practical basis reduction performs on bases of $\Z^n$ that are generated in different ways and how heuristic sieving algorithms perform on $\Z^n$. Our basis reduction experiments complement and add to those performed by Blanks and Miller, as we work with a larger class of algorithms (i.e., larger block sizes) and study the ``provably hard'' distribution of bases described above. Our sieving experiments confirm that heuristic sieving algorithms perform as expected on $\Z^n$.
Revisiting Time-Space Tradeoffs for Function Inversion
Alexander Golovnev Siyao Guo Spencer Peters Noah Stephens-Davidowitz
We study the black-box function inversion problem, which is the problem of finding x \in [N] such that f(x) = y, given as input some challenge point y in the image of a function f : [N] \to [N], using T oracle queries to f \emph{and} preprocessed advice \sigma \in \{0,1\}^S depending on f. We prove a number of new results about this problem, as follows. 1. We show an algorithm that works for any T and S satisfying T S^2 \cdot \max\{S,T\} = \widetilde{\Theta}(N^3) In the important setting when S < T, this improves on the celebrated algorithm of Fiat and Naor [STOC, 1991], which requires T S^3 \gtrsim N^3. E.g., Fiat and Naor's algorithm is only non-trivial for S \gg N^{2/3}, while our algorithm gives a non-trivial tradeoff for any S \gg N^{1/2}. (Our algorithm and analysis are quite simple. As a consequence of this, we also give a self-contained and simple proof of Fiat and Naor's original result, with certain optimizations left out for simplicity.) 2. We observe that there is a very simple \emph{non-adaptive} algorithm (i.e., an algorithm whose i-th query x_i is chosen based entirely on \sigma and y, and not on the f(x_1),\ldots, f(x_{i-1})) that improves slightly on the trivial algorithm. It works for any T and S satisfying S = \Theta(N \log(N/T)), for example, T = N /\polylog(N), S = \Theta(N/\log \log N). This answers a question due to Corrigan-Gibbs and Kogan [TCC, 2019], who asked whether non-trivial non-adaptive algorithms exist; namely, algorithms that work with parameters T and S satisfying T + S/\log N < o(N). We also observe that our non-adaptive algorithm is what we call a \emph{guess-and-check} algorithm, that is, it is non-adaptive \emph{and} its final output is always one of the oracle queries x_1,\ldots, x_T. For guess-and-check algorithms, we prove a matching lower bound, therefore completely characterizing the achievable parameters (S,T) for this natural class of algorithms. (Corrigan-Gibbs and Kogan showed that any such lower bound for \emph{arbitrary} non-adaptive algorithms would imply new circuit lower bounds.) 3. We show equivalence between function inversion and a natural decision version of the problem in both the worst case and the average case, and similarly for functions f : [N] \to [M] with different ranges. Some of these equivalence results are deferred to the full version [ECCC, 2022]. All of the above results are most naturally described in a model with \emph{shared randomness} (i.e., random coins shared between the preprocessing algorithm and the online algorithm). However, as an additional contribution, we show (using a technique from communication complexity due to Newman [IPL, 1991]) how to generically convert any algorithm that uses shared randomness into one that does not.
A 2^{n/2}-Time Algorithm for \sqrt{n}-SVP and \sqrt{n}-Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP 📺
Divesh Aggarwal Zeyong Li Noah Stephens-Davidowitz
We show a 2^{n/2+o(n)}-time algorithm that, given as input a basis of a lattice $\lat \subset \R^n$, finds a (non-zero) vector in whose length is at most $\widetilde{O}(\sqrt{n})\cdot \min\{\lambda_1(\lat), \det(\lat)^{1/n}\}$, where $\lambda_1(\lat)$ is the length of a shortest non-zero lattice vector and $\det(\lat)$ is the lattice determinant. Minkowski showed that $\lambda_1(\lat) \leq \sqrt{n} \det(\lat)^{1/n}$ and that there exist lattices with $\lambda_1(\lat) \geq \Omega(\sqrt{n}) \cdot \det(\lat)^{1/n}$, so that our algorithm finds vectors that are as short as possible relative to the determinant (up to a polylogarithmic factor). The main technical contribution behind this result is new analysis of (a simpler variant of) a 2^{n/2 + o(n)}-time algorithm from [ADRS15], which was only previously known to solve less useful problems. To achieve this, we rely crucially on the ``reverse Minkowski theorem'' (conjectured by Dadush [DR16] and proven by [RS17]), which can be thought of as a partial converse to the fact that $\lambda_1(\lat) \leq \sqrt{n} \det(\lat)^{1/n}$. Previously, the fastest known algorithm for finding such a vector was the 2^{0.802n + o(n)}-time algorithm due to [LWXZ11], which actually found a non-zero lattice vector with length $O(1) \cdot \lambda_1(\lat)$. Though we do not show how to find lattice vectors with this length in time $2^{n/2+o(n)}$, we do show that our algorithm suffices for the most important application of such algorithms: basis reduction. In particular, we show a modified version of Gama and Nguyen's slide-reduction algorithm [GN08], which can be combined with the algorithm above to improve the time-length tradeoff for shortest-vector algorithms in nearly all regimes---including the regimes relevant to cryptography.
No Time to Hash:On Super-Efficient Entropy Accumulation 📺
Yevgeniy Dodis Siyao Guo Noah Stephens-Davidowitz Zhiye Xie
Real-world random number generators (RNGs) cannot afford to use (slow) cryptographic hashing every time they refresh their state R with a new entropic input X. Instead, they use ``super-efficient'' simple entropy-accumulation procedures, such as R <- rot_{alpha, n}(R) XOR X where rot_{alpha,n} rotates an n-bit state R by some fixed number alpha. For example, Microsoft's RNG uses alpha=5 for n=32 and alpha=19 for n=64. Where do these numbers come from? Are they good choices? Should rotation be replaced by a better permutation pi of the input bits? In this work we initiate a rigorous study of these pragmatic questions, by modeling the sequence of successive entropic inputs X_1,X_2, ... as independent (but otherwise adversarial) samples from some natural distribution family D. We show a simple but surprisingly powerful connection between entropy accumulation and understanding the Fourier spectrum of distributions in D. Our contribution is as follows. - We define 2-monotone distributions as a rich family D that includes relevant real-world distributions (Gaussian, exponential, etc.), but avoids trivial impossibility results. - For any alpha with gcd(alpha,n)=1, we show that rotation accumulates Omega(n) bits of entropy from n independent samples X_1,...,X_n from any (unknown) 2-monotone distribution with entropy k > 1. - However, we also show some choices of alpha perform much better than others for a given n. E.g., we show alpha=19 is one of the best choices for n=64; in contrast, alpha=5 is good, but generally worse than alpha=7, for n=32. - More generally, given a permutation pi and k > 1, we define a simple parameter, the covering number C_{pi,k}, and show that it characterizes the number of steps before the rule (R_1,...,R_n) <- (R_{pi(1)},..., R_{pi(n)}) XOR X accumulates nearly n bits of entropy from independent, 2-monotone samples of min-entropy k each. - We build a simple permutation pi^*, which achieves nearly optimal C_{pi^*,k} \approx n/k for all values of k simultaneously, and experimentally validate that it compares favorably with all rotations rot_{alpha,n}.
Slide Reduction, Revisited—Filling the Gaps in SVP Approximation 📺
Divesh Aggarwal Jianwei Li Phong Nguyen Noah Stephens-Davidowitz
We show how to generalize Gama and Nguyen's slide reduction algorithm [STOC '08] for solving the approximate Shortest Vector Problem over lattices (SVP) to allow for arbitrary block sizes, rather than just block sizes that divide the rank n of the lattice. This leads to significantly better running times for most approximation factors. We accomplish this by combining slide reduction with the DBKZ algorithm of Micciancio and Walter [Eurocrypt '16]. We also show a different algorithm that works when the block size is quite large---at least half the total rank. This yields the first non-trivial algorithm for sublinear approximation factors. Together with some additional optimizations, these results yield significantly faster provably correct algorithms for \delta-approximate SVP for all approximation factors n^{1/2+\eps} \leq \delta \leq n^{O(1)}, which is the regime most relevant for cryptography. For the specific values of \delta = n^{1-\eps} and \delta = n^{2-\eps}, we improve the exponent in the running time by a factor of 2 and a factor of 1.5 respectively.
Lattice Reduction for Modules, or How to Reduce ModuleSVP to ModuleSVP 📺
Tamalika Mukherjee Noah Stephens-Davidowitz
We show how to generalize lattice reduction algorithms to module lattices. Specifically, we reduce $\gamma$-approximate ModuleSVP over module lattices with rank $k \geq2$ to $\gamma'$-approximate ModuleSVP over module lattices with rank $2 \leq \beta \leq k$. To do so, we modify the celebrated slide-reduction algorithm of Gama and Nguyen to work with module filtrations, a high-dimensional generalization of the ($\Z$-)basis of a lattice. The particular value of $\gamma$ that we achieve depends on the underlying number field $K$, the order $R \subseteq \mathcal{O}_K$, and the embedding (as well as, of course, $k$ and $\beta$). However, for reasonable choices of these parameters, the approximation factor that we achieve is surprisingly close to the one achieved by ``plain'' lattice reduction algorithms, which require an arbitrary SVP oracle in the same dimension. In other words, we show that ModuleSVP oracles are nearly as useful as SVP oracles for solving approximate ModuleSVP in higher dimensions. Our result generalizes the recent independent result of Lee, Pellet-Mary, Stehl\'e, and Wallet, which works in the important special case when $\beta = 2$ and $R = \mathcal{O}_K$ is the ring of integers of $K$ under the canonical embedding. Indeed, at a high level our reduction can be thought of as a generalization of theirs in roughly the same way that block reduction generalizes LLL reduction.
New (and Old) Proof Systems for Lattice Problems
Navid Alamati Chris Peikert Noah Stephens-Davidowitz
We continue the study of statistical zero-knowledge (SZK) proofs, both interactive and noninteractive, for computational problems on point lattices. We are particularly interested in the problem $$\textsf {GapSPP}$$GapSPP of approximating the $$\varepsilon $$ε-smoothing parameter (for some $$\varepsilon < 1/2$$ε<1/2) of an n-dimensional lattice. The smoothing parameter is a key quantity in the study of lattices, and $$\textsf {GapSPP}$$GapSPP has been emerging as a core problem in lattice-based cryptography, e.g., in worst-case to average-case reductions. We show that $$\textsf {GapSPP}$$GapSPP admits SZK proofs for remarkably low approximation factors, improving on prior work by up to roughly $$\sqrt{n}$$n. Specifically:There is a noninteractive SZK proof for $$O(\log (n) \sqrt{\log (1/\varepsilon )})$$O(log(n)log(1/ε))-approximate $$\textsf {GapSPP}$$GapSPP. Moreover, for any negligible $$\varepsilon $$ε and a larger approximation factor $$\widetilde{O}(\sqrt{n \log (1/\varepsilon )})$$O~(nlog(1/ε)), there is such a proof with an efficient prover.There is an (interactive) SZK proof with an efficient prover for $$O(\log n + \sqrt{\log (1/\varepsilon )/\log n})$$O(logn+log(1/ε)/logn)-approximate coGapSPP. We show this by proving that $$O(\log n)$$O(logn)-approximate $$\textsf {GapSPP}$$GapSPP is in $$\mathsf {coNP} $$coNP. In addition, we give an (interactive) SZK proof with an efficient prover for approximating the lattice covering radius to within an $$O(\sqrt{n})$$O(n) factor, improving upon the prior best factor of $$\omega (\sqrt{n \log n})$$ω(nlogn).

Program Committees

Crypto 2022
TCC 2022
TCC 2019
Crypto 2018