CryptoDB
Just how hard are rotations of Z^n? Algorithms and cryptography with the simplest lattice
| Authors: |
|
|---|---|
| Download: |
|
| Conference: | EUROCRYPT 2023 |
| Abstract: | 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$. |
BibTeX
@inproceedings{eurocrypt-2023-32901,
title={Just how hard are rotations of Z^n? Algorithms and cryptography with the simplest lattice},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-30589-4_9},
author={Huck Bennett and Atul Ganju and Pura Peetathawatchai and Noah Stephens-Davidowitz},
year=2023
}