This is the source code of the optimizer used to produce the complexity estimates
of the paper "On the Provable Dual Attack for LWE by Modulus Switching" [1]. 

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

1) Option 1: Installing dependencies manually

The main script (estimator.py) is written in SageMath Python and requires both SageMath [3] and the lattice-estimator library [2].  It should be executable on any compatible system.

Please install SageMath [3] on your computer: this can either be done by download an archive
from the website or by using your system package manager. 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.py*:

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

2) Option 2: Using Docker

We provide a Dockerfile to build an image containing all required dependencies. Assuming Docker is installed on your system, use the following command to build the image:

    docker build -t lwe_estimator .

To run the built image, use the following command:

    sudo docker run -it lwe_estimator

This will launch Sage directly, allowing you to begin working with the commands described in the next section right away.

3) Running the code

After installing SageMath and cloning the lattice-estimator, launch SageMath in the directory containing estimator.py and execute the following commands:

    import sys
    sys.path.append('./lattice-estimator')
    attach("estimator.py")
    # run the optimize (takes about 50min)
    %time results = runall()

The optimization process may take approximately 50 minutes (on our test machine) and will output results progressively. To quickly reproduce the estimates from the paper without re-running the full optimization, please use:

    import sys
    sys.path.append('./lattice-estimator')
    attach("estimator.py")
    # run the cost function on the parameters of the paper (<2min)
    reproduce()

4) Processing the output

After executing the command %time results = runall() or reproduce(), multiple blocks of output will be generated. Each block follows a structure similar to the example below:

Kyber512 (with modulus switching):
        rop:    2^169.9
      delta:   0.000000
          N:    2^105.6
          s:      0.197
       beta:        500
    n_guess:         45
     n_dual:        467
          m:       1013

Here, Kyber512 denotes the Kyber-512 scheme being analyzed, and (with modulus switching) indicates the use of the modulus switching technique in the attack. The output parameters are defined as follows:
rop: The total number of operations required to perform the attack (runtime complexity).
delta: The upper bound of the score function error, as defined in the paper.
N: The number of dual lattice vectors required for the attack.
s: The width parameter used in discrete Gaussian sampling.
beta: The block size parameter used in the BKZ algorithm.
n_guess: The number of secret components that can be recovered by the attack.
n_dual: The number of secret components that remain to be recovered after the guessing step.
m: The number of LWE samples required to conduct the attack.

5) References

[1]: https://eprint.iacr.org/2025/859
[2]: https://github.com/malb/lattice-estimator
[3]: https://www.sagemath.org/