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