**Short Stickelberger Class Relations and application to Ideal-SVP**

*Ronald Cramer and Léo Ducas and Benjamin Wesolowski*

**Abstract: **The worst-case hardness of finding short vectors in ideals of cyclotomic number fields (Ideal-SVP) is a central matter in lattice based cryptography. Assuming the worst-case hardness of Ideal-SVP allows to prove the Ring-LWE and Ring-SIS assumptions, and therefore to prove the security of numerous cryptographic schemes and protocols --- including key-exchange, digital signatures, public-key encryption and fully-homomorphic encryption.

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

[ Cryptology ePrint archive ]