blaster-python 0.1.1
BLASter: A proof of concept of an LLL-like lattice reduction algorithm with parallelization and segmentation
Requires Python: >=3.11

# 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:

```bash
# 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:

```bash
# 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](https://cython.readthedocs.io/en/stable/src/userguide/debugging.html#running-the-debugger), 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`.