{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "
Sage Notebook Demonstrating Ring-BKW
\n", "Version 1.3, May 10, 2019
\n", "Katherine E. Stange
\n", "This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
This notebook has been prepared as an accompaniment to the paper Algebraic aspects of solving Ring-LWE, including ring-based improvements in the Blum-Kalai-Wasserman algorithm. See the website http://math.colorado.edu/~kstange/ring-bkw.html. Usage is demonstrated below.
\n", "The purpose of this worksheet is only to demonstrate/verify mathematical correctness of the algorithms, not to determine runtimes or parameter boundaries.
Limitations: In this version, the code has the following limitations (compared to the generality of the paper):
\n", "1) the error width x means error coefficients are drawn uniformly from integers in the window [-x,x]
\n", "2) the prime must be 1 mod 4 (to avoid a \"not-implemented\" error in Sage v7.3 associated to a tower of polynomial extensions)
Evaluate the following cell to load all the code.