Paper 2021/1548

Just how hard are rotations of $\mathbb{Z}^n$? Algorithms and cryptography with the simplest lattice

Huck Bennett, Oregon State University
Atul Ganju, Cornell University
Pura Peetathawatchai, Stanford University
Noah Stephens-Davidowitz, Cornell University
Abstract

We study the computational problem of finding a shortest non-zero vector in a rotation of $\mathbb{Z}^n$, which we call $\mathbb{Z}$SVP. It has been a long-standing open problem to determine if a polynomial-time 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 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 $\mathbb{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, 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 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) $\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 non-zero 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 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 (Eurocrypt, 2022), and they also used this to analyze the security of a public-key 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 non-zero 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)
PDF
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
2022-10-02: revised
2021-11-29: received
See all versions
Short URL
https://ia.cr/2021/1548
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1548,
      author = {Huck Bennett and Atul Ganju and Pura Peetathawatchai and Noah Stephens-Davidowitz},
      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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.