Paper 2019/234
On the Shortness of Vectors to be found by the Ideal-SVP Quantum Algorithm
Léo Ducas, Maxime Plançon, and Benjamin Wesolowski
Abstract
The hardness of finding short vectors in ideals of cyclotomic number fields (hereafter, Ideal-SVP) can serve as a worst-case assumption for numerous efficient cryptosystems, via the average-case problems Ring-SIS and Ring-LWE. For a while, it could be assumed the Ideal-SVP problem was as hard as the analog problem for general lattices (SVP), even when considering quantum algorithms.
But in the last few years, a series of works has lead to a quantum algorithm for Ideal-SVP that outperforms what can be done for general SVP in certain regimes. More precisely, it was demonstrated (under certain hypotheses) that one can find in quantum polynomial time a vector longer by a factor at most
Note: *Erratum.*
A previous version (Feb. 2019) of this report included errors in Figure~
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Quantum CryptanalysisCyclotomic Ideal Lattices.
- Contact author(s)
- ducas @ cwi nl
- History
- 2021-08-23: last of 2 revisions
- 2019-02-28: received
- See all versions
- Short URL
- https://ia.cr/2019/234
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/234, author = {Léo Ducas and Maxime Plançon and Benjamin Wesolowski}, title = {On the Shortness of Vectors to be found by the Ideal-{SVP} Quantum Algorithm}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/234}, year = {2019}, url = {https://eprint.iacr.org/2019/234} }