A series of recent works has shown that Principal Ideal-SVP is not always as hard as finding short vectors in general lattices, and some schemes were broken using quantum algorithms --- the Soliloquy encryption scheme, Smart-Vercauteren fully homomorphic encryption scheme from PKC 2010, and Gentry-Garg-Halevi cryptographic multilinear-maps from Eurocrypt 2013.
Those broken schemes were using a special class of principal ideals, but these works also showed how to solve SVP for principal ideals in the worst-case in quantum polynomial time for an approximation factor of $\exp(\tilde O(\sqrt n))$. This exposed an unexpected hardness gap between general lattices and some structured ones, and called into question the hardness of various problems over structured lattices, such as Ideal-SVP and Ring-LWE.
In this work, we generalize the previous result to general ideals. Precisely, we show how to solve the close principal multiple problem (CPM) by exploiting the classical theorem that the class-group is annihilated by the (Galois-module action of) the so-called Stickelberger ideal. Under some plausible number-theoretical hypothesis, our approach provides a close principal multiple in quantum polynomial time. Combined with the previous results, this solves Ideal-SVP in the worst case in quantum polynomial time for an approximation factor of $\exp(\tilde O(\sqrt n))$.
Although it does not seem that the security of Ring-LWE based cryptosystems is directly affected, we contribute novel ideas to the cryptanalysis of schemes based on structured lattices. Moreover, our result shows a deepening of the gap between general lattices and structured ones.Category / Keywords: public-key cryptography / Lattices, Ideal-SVP, Cryptanalysis Original Publication (in the same form): IACR-EUROCRYPT-2017 Date: received 8 Sep 2016, last revised 28 Mar 2017 Contact author: ducas at cwi nl Available format(s): PDF | BibTeX Citation Note: Bugfix in Appendix A. Version: 20170328:092935 (All versions of this report) Short URL: ia.cr/2016/885 Discussion forum: Show discussion | Start new discussion