SVP-solver for PEng SS2020

This project implements the technique of extreme pruning for enumeration [Gama10 to solve the shortest vector problem (SVP).

Compilation

Prerequisites

• gcc 8.1 or higher https://gcc.gnu.org/ (not tested with lower versions)
• MPFR 4.0.1 or higher https://www.mpfr.org
• GMP 6.1.2 or higher https://gmplib.org/
• Boost 1.68.0 or higher https://www.boost.org
• NTL 11.2.0 or higher https://www.shoup.net/ntl/
• fplll https://github.com/fplll/fplll

Installation

Linux

Run make in the svp-solver-seminar directory.

Other OS

This project has not been tested yet on other operating systems.

How to use

There is only one executable file svpsolvein svpsolve\solver

You can configure the application with:

Mandatory parameters

• --basisfile : The path to the basis to reduce. The format must be that of the Darmstadt SVP Challenge.
• --prunefile : The path to the pre-calculated pruning function.
• --delta : A floating value between 0.6 and 0.999 which sets the accuracy δ of the LLL reduction.
• --prebeta: An integer value which determines the block size of the BKZ 1.0 reduction. Must be at least 2.
• --beta: An integer value which determines the block size of the BKZ 2.0 reduction on the already BKZ 1.0-reduced basis. Pass -1 to skip this step.

Optional parameters

• --pruneparam : A floating value between 0.0 and 1.0 which determines the shift of the pruning function along the y-axis to increase workload and probability (default = 0.0)

Bibliography

[Gama10] N. Gama, P. Q. Nguyen and Oded Regev. Lattice Enumeration Using Extreme Pruning.