Sieving For Codes

In this project, we provide an asymptotic analysis of the sieving-style algorithm for solving decoding problems and experimental validation of the heuristics required for instantiating the sieving algorithm as a sub-routine of an ISD algorithm. The code for the first is given in SievingISD_asymptotic_optimization.ipynb Python notebook, while the code for the experimental validation is given in the Heuristic_validation directory. The numerical results accompany the theoretical results presented in the corresponding paper.

Project's dependencies

Both the asymptotic analysis and the heuristic validation experiments require Python 3. In addition to that, the heuristics validation experiments require a CPU that supports Advanced Vector Extensions (AVX).

The asymptotic optimization requires the python packages progressbar, numpy and scipy you can install those using the terminal command

pip3 install -r requirements.txt

or just run the first cell of the jupyter notebook.

Asymptotic plots

All asymptotic plots can be reproduced by running SievingISD_asymptotic_optimization.ipynb jupyter notebook. To open this
file you require the web application jupyter, which you can install via

pip3 install jupyterlab

To then start jupyter just execute

jupyter lab

This opens the jupyter web application in your standard browser. Now you can navigate to the corresponding directory and
open the file SievingISD_asymptotic_optimization.ipynb. Then simply press the two right-oriented arrows at the top
which will execute all cells of the notebook.

(The data for the paper was generated by executing the notebook using a python 3.11.4 jupyter kernel)

Build the sieveisd library (for Linux distributions)

To build the sieveisd library for n

make sieveisdlib LENGTH=$n

where n is the code length. If no parameters are provided, n = 256.

Run the experiments

To obtain the results and visualization of the comparison between the theoretical prediction and the experimental data, run

python comparison.py $n $w $k $i

where n is the code length, w is the weight of the error, and k is the code dimension. If no parameters are provided, n = 256, w = 6, and k = 0.

Results of the experiments

The results of the experiments and the comparison are recorded in the ./Data/n$n directory.

Authors

Léo Ducas, Centrum Wiskunde & Informatica, Leiden University

Andre Esser, Technology Innovation Institute

Simona Etinski, Centrum Wiskunde & Informatica

Elena Kirshanova, Technology Innovation Institute, Immanuel Kant Baltic Federal University