Ring-BKW

Ring-BKW

This page has scripts to support my paper, Algebraic aspects of solving Ring-LWE, including ring-based improvements in the Blum-Kalai-Wasserman algorithm. These are for the computer algebra system Sage, based on Python.

You are welcome to download and use these scripts; they and the software to run them are free.  Please let me know if you encounter errors.

Notes on usage: To use a Sage notebook, open Sage and upload it to the notebook interface.

This work has been supported by the National Science Foundation NSF-CAREER CNS-1652238 and NSF EAGER DMS-1643552. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation of the USA.

    • Algebraic aspects of solving Ring-LWE, including ring-based improvements in the Blum-Kalai-Wasserman algorithm [ ePrint | arXiv:1902.07140 ] – This is the paper.
    • Slides from a recent 20-minute talk on the subject.
    • Ring-BKW Demo Notebook [ ipynb v1.3 |  sws v1.3 ] – This implements the algorithms in the paper. Its purpose is only to verify correctness, not to benchmark speed.
    • Advanced Keying Demo Notebook [ ipynb v1.0 ] — This is the code used for the experiments in the paper demonstrating the effectiveness of advanced keying.