BLASter

BLASter is a proof of concept of an LLL-like lattice reduction algorithm that uses:

• parallelization,
• segmentation,
• Seysen's reduction instead of size reduction, and
• a linear algebra library.

Disclaimer

The goal of this software is to showcase speed ups that are possible in lattice reduction software. This software is a proof of concept!

In particular, we do not:

• guarantee the algorithm terminates, nor claim its output is correct on all lattices,
• support lattices with large entries,
• consider issues / PRs that improve efficiency or robustness,
• actively maintain this software.

We do:

• happily answer any questions to explain design choices phrased as: "Why is X done in Y way?". The answer may, in many cases, be: "because it is faster in practice".
• encourage the cryptographic community to build a new robust lattice reduction library incorporating the ideas in this proof of concept.

Requirements

• python3 (3.10 or later)
• Cython version 3.0 or later (installed automatically)
• Python modules: cysignals numpy setuptools matplotlib (installed automatically)
• Eigen3 headers (downloaded automatically during installation)
• OpenMP library (for parallel processing)
  • Linux: Usually available by default with GCC
  • macOS: Install with brew install llvm libomp (recommended) or just brew install libomp for system clang
  • Windows: Included with MSVC

Optional:

• Python module: virtualenv (for creating a local virtual environment to install python3 modules)
• fplll (for generating q-ary lattices with the latticegen command)

Installation

Modern PEP 517 Installation (Recommended)

BLASter now supports modern Python packaging with automatic dependency management:

# Install from source (automatically downloads Eigen3)
pip install -e .

# Or build wheel for distribution
python -m build

macOS Setup (Optional)

For optimal performance on macOS, you can use Homebrew LLVM instead of system clang:

# Install Homebrew LLVM and OpenMP
brew install llvm libomp

# Set environment variables for compilation
export CC=$(brew --prefix llvm)/bin/clang
export CXX=$(brew --prefix llvm)/bin/clang++

# Then install BLASter
pip install -e .

Legacy Building

• Optional: Run make eigen3 to install libeigen3 library in a subdirectory.
• Optional: Run make venv to create a local virtual environment and install the required python3 modules.
• Run make to compile all the Cython files in core/.

Debugging

• Debug the C++/Cython code with the libasan and libubsan sanitizers by running make cython-gdb. These sanitizers check for memory leaks, out of bounds accesses, and undefined behaviour.
• When executing the src/app.py, preload libasan like this: LD_PRELOAD=$(gcc -print-file-name=libasan.so) src/app.py -pvi INPUTFILE
• If you want to run the program with the gdb debugger, read the Cython documentation, for more info.

Running

Note: you first need to build the software, see above.

Run the command by e.g. typing ./python3 src/app.py -pvi INPUTFILE. Add -h for seeing all available command line arguments.

Example

Command: time latticegen q 128 64 20 p | src/app.py -pq.

Expected output:

Profile: [9.38 9.39 9.30 9.28 9.18 ... 4.27 4.33 4.31 4.29 4.35]
Root Hermite factor: 1.020447, ∥b_1∥ = 11906.636

real	0m0,754s
user	0m2,271s
sys	0m0,105s

To run deep-LLL with depth 4, run src/app.py -pq -i {lattice} -d4.

To run progressive BKZ-60 (with 4-deep-LLL) with 1 tours and block size increments of 2, run src/app.py -pq -i {lattice} -b60 -t1 -P2.