Welcome to the resource topic for 2021/1548
Title:
Just how hard are rotations of \mathbb{Z}^n? Algorithms and cryptography with the simplest lattice
Authors: Huck Bennett, Atul Ganju, Pura Peetathawatchai, Noah Stephens-Davidowitz
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 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^{0.802n}-time algorithm for $\mathbb{Z}SVP, i.e., a non-trivial speedup over the best known algorithm for SVP on general lattices. 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 (ia.cr/2021/1332), and they also used this to analyze the security of a public-key encryption scheme.) 4) We perform experiments to determine how practical basis reduction performs on different bases of $\mathbb{Z}^n$. These experiments complement and add to those performed by Blanks and Miller, as we work with a larger class of reduction 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.
ePrint: https://eprint.iacr.org/2021/1548
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .