Paper 2021/1548
Just how hard are rotations of $\mathbb{Z}^n$? Algorithms and cryptography with the simplest lattice
Abstract
We study the computational problem of finding a shortest nonzero vector in a rotation of $\mathbb{Z}^n$, which we call $\mathbb{Z}$SVP. It has been a longstanding open problem to determine if a polynomialtime algorithm for $\mathbb{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 $\mathbb{Z}$SVP is still simply the fastest known algorithm for solving SVP (i.e., the problem of finding shortest nonzero 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 $\mathbb{Z}$SVP and instead ask what else we can say about the problem. E.g., can we find *any* nontrivial speedup over the best known SVP algorithm? And, what consequences would follow if $\mathbb{Z}$SVP actually is hard? Our results are as follows. 1) We show that $\mathbb{Z}$SVP is in a certain sense strictly easier than SVP on arbitrary lattices. In particular, we show how to reduce $\mathbb{Z}$SVP to an approximate version of SVP in the same dimension (in fact, even to approximate 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 $\mathbb{Z}$SVP from SVP. As a consequence of this reduction, we obtain a $2^{n/2 + o(n)}$time algorithm for $\mathbb{Z}$SVP, i.e., the first nontrivial speedup over the best known algorithm for SVP on general lattices. (In fact, this reduction works for a more general class of latticessemistable lattices with nottoolarge $\lambda_1$.) 2) We show a simple publickey encryption scheme that is secure if (an appropriate variant of) $\mathbb{Z}$SVP is actually hard. Specifically, our scheme is secure if it is difficult to distinguish (in the worst case) a rotation of $\mathbb{Z}^n$ from either a lattice with all nonzero vectors longer than $\sqrt{n/\log n}$ or a lattice with smoothing parameter significantly smaller than the smoothing parameter of $\mathbb{Z}^n$. The latter result has an interesting qualitative connection with reverse Minkowski theorems, which in some sense say that ``$\mathbb{Z}^n$ has the largest smoothing parameter.'' 3) We show a distribution of bases $B$ for rotations of $\mathbb{Z}^n$ such that, if $\mathbb{Z}$SVP is hard for *any* input basis, then $\mathbb{Z}$SVP is hard on input $B$. This gives a satisfying theoretical resolution to the problem of sampling hard bases for $\mathbb{Z}^n$, which was studied by Blanks and Miller (PQCrypto, 2021). This worstcase to averagecase 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 (Eurocrypt, 2022), and they also used this to analyze the security of a publickey encryption scheme.) Along the way to this result, we show a new algorithm for converting a generating set to a basis, which might be of independent interest. 4) We perform experiments to determine how practical basis reduction performs on bases of $\mathbb{Z}^n$ that are generated in different ways and how heuristic sieving algorithms perform on $\mathbb{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. We also observe a threshold phenomenon in which ``basis reduction algorithms on $\mathbb{Z}^n$ nearly always find a shortest nonzero vector once they have found a vector with length less than $\sqrt{n}/2$,'' and we explore this further. Our sieving experiments confirm that heuristic sieving algorithms perform as expected on $\mathbb{Z}^n$.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 lattices integer lattice Z^n
 Contact author(s)

huck bennett @ oregonstate edu
ag2222 @ cornell edu
pura @ stanford edu
noahsd @ gmail com  History
 20221002: revised
 20211129: received
 See all versions
 Short URL
 https://ia.cr/2021/1548
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/1548, author = {Huck Bennett and Atul Ganju and Pura Peetathawatchai and Noah StephensDavidowitz}, title = {Just how hard are rotations of $\mathbb{Z}^n$? Algorithms and cryptography with the simplest lattice}, howpublished = {Cryptology ePrint Archive, Paper 2021/1548}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/1548}}, url = {https://eprint.iacr.org/2021/1548} }