Paper 2019/791
Solving Ring-LWE over Algebraic Integer Rings
Hao Chen
Abstract
Many cryptographic schemes have been proposed from learning with errors problems over some rings (Ring-LWE). Polynomial time quantum reduction from the approximating Shortest Independent Vectors Problem ($\textrm{SIVP}_\gamma$) for fractional ideal lattices in any algebraic number field to the average-case decision Ring-LWE for any modu- lus over the integer ring in this number field was established in the Peikert-Regev-Stephens-Davidowitz STOC 2017 paper. However the hardness of approximating SIVPpoly(n) in quantum computing was only a folklore conjecture. In this paper we prove that decision Ring- LWE for arbitrary number fields can be solved within polynomial time for infinitely many modulus parameters under a suitable bound on widths (with respect to the canonical embedding). We construct some algebraic number fields such that the decision versions of Ring-LWE with parameters in the range of Peikert-Regev-Stephens-Davidowitz K - SIV P to Ring-LWE reduction result can be solved within poly- nomial time. Our results indicate that approximating SIV Ppoly(n) for fractional ideal lattices in these algebraic number fields can be solved by a polynomial time quantum algorithm.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- Ring-LWEAlgebraic Integer RingSIVP_poly(n) for ideal lattices.
- Contact author(s)
- haochen @ jnu edu cn,chenhao @ fudan edu cn
- History
- 2019-12-17: last of 9 revisions
- 2019-07-14: received
- See all versions
- Short URL
- https://ia.cr/2019/791
- License
-
CC BY