Welcome to the resource topic for 2019/183
Title:
Algebraic aspects of solving Ring-LWE, including ring-based improvements in the Blum-Kalai-Wasserman algorithm
Authors: 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).
ePrint: https://eprint.iacr.org/2019/183
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .