Hazay, Carmit
; Stam, Martijn
(Ed.)
We study the computational problem of finding a shortest non-zero vector in a rotation of β€π
, which we call β€
SVP. It has been a long-standing open problem to determine if a polynomial-time algorithm for β€
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 β€
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π+π(π)
time.
We therefore set aside the (perhaps impossible) goal of finding an efficient algorithm for β€
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 β€
SVP actually is hard, then what consequences would follow? Our results are as follows.
We show that β€
SVP is in a certain sense strictly easier than SVP on arbitrary lattices. In particular, we show how to reduce β€
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 β€
SVP from SVP. As a consequence of this reduction, we obtain a 2π/2+π(π)
-time algorithm for β€
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 π1
.)
We show a simple public-key encryption scheme that is secure if (an appropriate variant of) β€
SVP is actually hard. Specifically, our scheme is secure if it is difficult to distinguish (in the worst case) a rotation of β€π
from either a lattice with all non-zero vectors longer than π/logπβΎβΎβΎβΎβΎβΎβΎβ
or a lattice with smoothing parameter significantly smaller than the smoothing parameter of β€π
. The latter result has an interesting qualitative connection with reverse Minkowski theorems, which in some sense say that ββ€π
has the largest smoothing parameter.β
We show a distribution of bases π
for rotations of β€π
such that, if β€
SVP is hard for any input basis, then β€
SVP is hard on input π
. This gives a satisfying theoretical resolution to the problem of sampling hard bases for β€π
, which was studied by Blanks and Miller [9]. 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 [15], and they also used this to analyze the security of a public-key encryption scheme. Similar ideas also appeared in [5, 11, 20] in different contexts.)
We perform experiments to determine how practical basis reduction performs on bases of β€π
that are generated in different ways and how heuristic sieving algorithms perform on β€π
. 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 β€π
.
more »
« less