We show the first dimension-preserving search-to-decision reductions for approximate SVP and CVP. In particular, for any @math , we obtain an efficient dimension-preserving reduction from @math -SVP to @math -GapSVP and an efficient dimension-preserving reduction from @math -CVP to @math -GapCVP. These results generalize the known equivalences of the search and decision versions of these problems in the exact case when @math . For SVP, we actually obtain something slightly stronger than a search-to-decision reduction---we reduce @math -SVP to @math -unique SVP, a potentially easier problem than @math -GapSVP.
Some efficient dimension-preserving search-to-decision reductions were known for other lattice problems prior to this work. For example, Regev showed such a reduction for Learning with Errors, an important average-case lattice problem with widespread applications in cryptography @cite_44 . (Both the search and decision versions of LWE are average-case problems.) And, Liu, Lyubashevsky, and Micciancio implicitly use a search-to-decision reduction for Bounded Distance Decoding in their work @cite_42 . Finally, Aggarwal and Dubey showed how to use some of the ideas from @cite_37 to obtain a search-to-decision reduction for unique SVP @cite_17 . While all of these works are quite interesting, they are concerned with promise problems, and not the two most important and natural lattice problems, SVP and CVP.
@cite_44 @cite_37 @cite_42 @cite_17
2007466965 1490468194 2949988970
Our main result is a reduction from worst-case lattice problems such as GapSVP and SIVP to a certain learning problem. This learning problem is a natural extension of the “learning from parity with error” problem to higher moduli. It can also be viewed as the problem of decoding from a random linear code. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, is quantum. Hence, an efficient solution to the learning problem implies a quantum algorithm for GapSVP and SIVP. A main open question is whether this reduction can be made classical (i.e., nonquantum). We also present a (classical) public-key cryptosystem whose security is based on the hardness of the learning problem. By the main result, its security is also based on the worst-case quantum hardness of GapSVP and SIVP. The new cryptosystem is much more efficient than previous lattice-based cryptosystems: the public key is of size O(n2) and encrypting a message increases its size by a factor of O(n) (in previous cryptosystems these values are O(n4) and O(n2), respectively). In fact, under the assumption that all parties share a random bit string of length O(n2), the size of the public key can be reduced to O(n). We prove the equivalence, up to a small polynomial approximation factor @math , of the lattice problems uSVP (unique Shortest Vector Problem), BDD (Bounded Distance Decoding) and GapSVP (the decision version of the Shortest Vector Problem). This resolves a long-standing open problem about the relationship between uSVP and the more standard GapSVP, as well the BDD problem commonly used in coding theory. The main cryptographic application of our work is the proof that the Ajtai-Dwork ([2]) and the Regev ([33]) cryptosystems, which were previously only known to be based on the hardness of uSVP, can be equivalently based on the hardness of worst-case GapSVP @math and GapSVP @math , respectively. Also, in the case of uSVP and BDD, our connection is very tight, establishing the equivalence (within a small constant approximation factor) between the two most central problems used in lattice based public key cryptography and coding theory. We give several improvements on the known hardness of the unique shortest vector problem. - We give a deterministic reduction from the shortest vector problem to the unique shortest vector problem. As a byproduct, we get deterministic NP-hardness for unique shortest vector problem in the @math norm. - We give a randomized reduction from SAT to uSVP_ 1+1 poly(n) . This shows that uSVP_ 1+1 poly(n) is NP-hard under randomized reductions. - We show that if GapSVP_ coNP (or coAM) then uSVP_ coNP (coAM respectively). This simplifies previously known uSVP_ n^ 1 4 coAM proof by Cai Cai98 to uSVP_ (n n)^ 1 4 coAM, and additionally generalizes it to uSVP_ n^ 1 4 coNP. - We give a deterministic reduction from search-uSVP_ to the decision-uSVP_ 2 . We also show that the decision-uSVP is NP -hard for randomized reductions, which does not follow from Kumar-Sivakumar KS01 .