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.