Cryptology ePrint Archive: Report 2019/183

Algebraic aspects of solving Ring-LWE, including ring-based improvements in the Blum-Kalai-Wasserman algorithm

Katherine E. Stange

Abstract: We provide a reduction of the Ring-LWE problem to Ring-LWE problems in subrings, in the presence of samples of a restricted form (i.e. (a,b) such that a is restricted to a multiplicative coset of the subring). To create and exploit such restricted samples, we propose Ring-BKW, a version of the Blum-Kalai-Wasserman algorithm which respects the ring structure. Off-the-shelf BKW dimension reduction (including coded-BKW and sieving) can be used for the reduction phase. Its primary advantage is that there is no need for back-substitution, and the solving/hypothesis-testing phase can be parallelized. There is also the opportunity to exploit symmetry to reduce table sizes. The results apply to two-power cyclotomic Ring-LWE with parameters proposed for practical use (including all splitting types).

Category / Keywords: public-key cryptography / ring learning with errors, learning with errors, Ring-LWE, BKW, Blum-Kalai-Wasserman, cyclotomic

Date: received 19 Feb 2019, last revised 13 May 2019

Contact author: kstange at math colorado edu

Available format(s): PDF | BibTeX Citation

Note: Completely rewritten for simplicity and correctness.

Version: 20190513:204421 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]