Paper 2016/885

Short Stickelberger Class Relations and application to Ideal-SVP

Ronald Cramer, 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.

Note: Bugfix in Appendix A.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in EUROCRYPT 2017
Keywords
LatticesIdeal-SVPCryptanalysis
Contact author(s)
ducas @ cwi nl
History
2017-03-28: last of 3 revisions
2016-09-14: received
See all versions
Short URL
https://ia.cr/2016/885
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/885,
      author = {Ronald Cramer and Léo Ducas and Benjamin Wesolowski},
      title = {Short Stickelberger Class Relations and application to Ideal-{SVP}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/885},
      year = {2016},
      url = {https://eprint.iacr.org/2016/885}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.