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

Katherine E.  Stange

Paper 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. We also present a method to exploit symmetry to reduce table sizes, samples needed, and runtime during the reduction phase. The results apply to two-power cyclotomic Ring-LWE with parameters proposed for practical use (including all splitting types).

Note: Minor revisions, plus section on advanced keying extended in this version.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: ring learning with errors learning with errors Ring-LWE BKW Blum-Kalai-Wasserman cyclotomic
Contact author(s): kstange @ math colorado edu
History: 2020-07-10: last of 2 revisions; 2019-02-26: received; See all versions
Short URL: https://ia.cr/2019/183
License: CC BY

BibTeX

@misc{cryptoeprint:2019/183,
      author = {Katherine E.  Stange},
      title = {Algebraic aspects of solving Ring-LWE, including ring-based improvements in the Blum-Kalai-Wasserman algorithm},
      howpublished = {Cryptology ePrint Archive, Paper 2019/183},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/183}},
      url = {https://eprint.iacr.org/2019/183}
}