Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Ring-LWE, Algebraic Integer Ring, SIVP_poly(n) for ideal lattices.

Date: received 7 Jul 2019

Contact author: haochen at jnu edu cn,chenhao@fudan edu cn

Available format(s): PDF | BibTeX Citation

Version: 20190714:153558 (All versions of this report)

Short URL: ia.cr/2019/791


[ Cryptology ePrint archive ]