This is the source code of the optimizer used to produce the complexity estimates of the paper "Provable Dual Attacks on Learning with Errors" 1. This optimizer essentially brute forces all values of "m", "n_guess" and "beta" and keeps the best complexity. We have architectured the code in such a way that the cost function "compute_cost" is easily reusable so that it should be trivial to just plug any values of the parameter and immediately verify the complexity estimates of the paper. On the other hand, the function "opt_cost" runs the optimizer for a specific scheme so it should be easy to call it on other schemes of interest (see Examples below).

We provide two ways to run the code: manually install the dependencies and run it on your OS, or use docker.

1. Option1: Installing dependencies manually

The main file (estimator_eurocrypt.py) is written in sage python and therefore depends on sage 3. It also depends on the lattice-estimator 2. It should run on any machine but the code was tested on Linux using sage 9.5 and lattice-estimator git revision 564470e07d816f788d9c85acf72a1789c7787574.

Please install sage 3 on your computer: this can either be done by download an archive from the website or by using your system package manager. On MacOS, homebrew 4 provides a sage package. Assuming this is done, you will also need to download a copy of lattice-estimator 2. The easiest way to do so is to use git and to run the following command in the same directory as estimator_eurocrypt.py:

git clone https://github.com/malb/lattice-estimator.git

2. Option 2: using Docker

If you prefer using docker, we provide a Dockerfile to build a docker image that contains everything you need. This is not a docker tutorial but assuming you have docker installed on your machine, you can run the following command to build the docker image:

docker build -t eurocrypt_332 .

Note that on Linux machines, running docker might require some privileges, please refer to your distribution's documentation. Once the image is built, it can be run using:

docker sudo docker run -it eurocrypt_332

This will immmediately run sage and so you can start typing the sage commands of the next section.

3. Running the code

Assuming you have installed sage and downloaded lattice-estimator (either manually or using the docker image), run sage in the directory that contains estimator_eurocrypt.py and type the following commands in the sage prompt:

import sys
sys.path.append('./lattice-estimator')
attach("estimator_eurocrypt.py")
# run the optimize (takes about 10min)
%time results = runall()
# optional: produce the latex table of the article
print(results_table_latex(results))

Running the estimator takes a bit of time (around 10 minutes on our machine) and it will print the results as they are computed. Alternatively, if one does not want to run the optimizer and just reproduce the complexity estimates from the parameters of the paper, run in sage:

import sys
sys.path.append('./lattice-estimator')
attach("estimator_eurocrypt.py")
# run the cost function on the parameters of the paper (<1s)
reproduce_eurocrypt()

4. Extra features

The code contains more features than are used in the paper: one can change the cost estimate of the sampler to use GPV or MCMC with a higher value of s (the sampler runs in polynomial time but this makes the attack worse). It is also possible to use different cost models for the BKZ step, the lattice-estimator library provides many more.

5. References