fpylll

fpylll is a Python library for performing lattice reduction on lattices over the Integers. It is based on the fplll, a C++ library which describes itself as follows:

fplll contains several algorithms on lattices that rely on floating-point computations. This includes implementations of the floating-point LLL reduction algorithm, offering different speed/guarantees ratios. It contains a ‘wrapper’ choosing the estimated best sequence of variants in order to provide a guaranteed output as fast as possible. In the case of the wrapper, the succession of variants is oblivious to the user. It also includes a rigorous floating-point implementation of the Kannan-Fincke-Pohst algorithm that finds a shortest non-zero lattice vector, and the BKZ reduction algorithm.

fplll is distributed under the GNU Lesser General Public License (either version 2.1 of the License, or, at your option, any later version) as published by the Free Software Foundation.

In short, fplll is your best bet at a publicly available fast lattice-reduction library and fpylll provides a convenient interface for it — for experimentation, development and extension — from Python.

For the rest of this post, I’ll give you a tour of the features currently implemented in fpylll and point out some areas where we could do with some help.

An Interface to fplll

First of all, fpylll is a thin wrapper around fplll. In the example below, we first generate an NTRU-like matrix and consider the norm of the first row:

from fpylll import IntegerMatrix, LLL
q = 1073741789
A = IntegerMatrix.random(30, "ntrulike", bits=30, q=q)
A[0].norm()
3294809651.09

We then call LLL reduction, i.e. we perform integer-linear combinations of the rows to make shorter rows and observe the output:

LLL.reduction(A)
A[0].norm()
82117.5815888

If LLL reduction isn’t strong enough, we can call the BKZ algorithm for some block size k.

from fpylll import BKZ
BKZ.reduction(A, o=BKZ.Param(block_size=10))
A[0].norm()
71600.8858744

We may want to increase the block size k to find shorter vectors.

from fpylll import BKZ
BKZ.reduction(A, o=BKZ.Param(block_size=20))
A[0].norm()
68922.4558181

Or, we just go for the shortest vector. Solving the Shortest Vector Problem (SVP) is supposed to be hard problem, so we only attempt it for a small lattice.

from fpylll import SVP
q = 1073741789
B = IntegerMatrix.random(10, "ntrulike", bits=7, q=127)
SVP.shortest_vector(B)
(1, 2, -3, 5, -2, 4, 5, -1, 1, 1, 0, -1, 6, -3, 0, 2, 6, -8, 0, 1)

Of course, fpylll being a Python library means you can use your favourite Python libraries with it. For example, say, we want to LLL reduce many matrices in parallel, using all our cores, and to compute the norm of the shortest vector across all matrices after LLL reduction. We’ll make use of Python’s multiprocessing:

from multiprocessing import Pool

If we want to recover the reduced matrix, we have to return it. However, LLL.reduction returns nothing and its input A will live in its own process. So we add a small function which returns A.

def f(A):
    from fpylll import LLL
    LLL.reduction(A)
    return A

For this example, we want dimension 40, four worker processes and 32 matrices:

from fpylll import IntegerMatrix

d = 20
workers = 4
tasks = 32

A = [IntegerMatrix.random(d, "ntrulike", bits=30, q=1073741789) for _ in range(tasks)]

Let’s get to work: we create a pool of workers and kick off the computation:

pool = Pool(workers)
A = pool.map(f, A)

Finally, we output the minimal norm found:

min([A_[0].norm() for A_ in A])
7194.545155880252

A Python Library for Developing Lattice-Reduction Algorithms

The main objective of fpylll is to make developing and experimenting with the kind of algorithms implemented in fplll easier. For example, there are a few variants of the BKZ algorithm in the literature which essentially re-combine the same building blocks — LLL and an SVP oracle — in some way. These kind of algorithms should be easy to implement. The code below is an implementation of the plain BKZ algorithm in 70 lines of Python.

from fpylll import IntegerMatrix, GSO, LLL, BKZ
from fpylll import Enumeration as Enum
from fpylll import gso

class BKZReduction:
    def __init__(self, A):
        wrapper = LLL.Wrapper(A)
        wrapper()

        self.A = A
        self.M = GSO.Mat(A, flags=gso.GSO.ROW_EXPO)
        self.lll_obj = LLL.Reduction(self.M)

    def __call__(self, block_size):
        self.M.discover_all_rows()

        while True:
            clean = self.bkz_tour(block_size, 0, self.A.nrows)
            if clean:
                break

    def bkz_tour(self, block_size, min_row, max_row):
        clean = True
        for kappa in range(min_row, max_row-1):
            bs = min(block_size, max_row - kappa)
            clean &= self.svp_reduction(kappa, bs)
        return clean

    def svp_reduction(self, kappa, block_size):
        clean = True

        self.lll_obj(0, kappa, kappa + block_size)
        if self.lll_obj.nswaps > 0:
            clean = False

        max_dist, expo = self.M.get_r_exp(kappa, kappa)
        delta_max_dist = self.lll_obj.delta * max_dist

        solution, max_dist = Enum.enumerate(self.M, max_dist, expo, kappa, kappa + block_size, None)

        if max_dist >= delta_max_dist:
            return clean

        nonzero_vectors = len([x for x in solution if x])

        if nonzero_vectors == 1:
            first_nonzero_vector = None
            for i in range(block_size):
                if abs(solution[i]) == 1:
                    first_nonzero_vector = i
                    break

            self.M.move_row(kappa + first_nonzero_vector, kappa)
            self.lll_obj.size_reduction(kappa, kappa + 1)

        else:
            d = self.M.d
            self.M.create_row()

            with self.M.row_ops(d, d+1):
                for i in range(block_size):
                    self.M.row_addmul(d, kappa + i, solution[i])

            self.M.move_row(d, kappa)
            self.lll_obj(kappa, kappa, kappa + block_size + 1)
            self.M.move_row(kappa + block_size, d)

            self.M.remove_last_row()

        return False

Beyond fplll

In the meantime fpylll has gained a contrib module which implements additional algorithms. As of writing, it contains a simple demo implementation of BKZ (see above), a simple implementation of Dual BKZ and a slightly feature enhanced re-implementation of fplll’s BKZ: it collects additional statistics compared to fplll’s implementation of the same algorithm. Let’s run it to see what that means:

from copy import copy
from fpylll.contrib.bkz import BKZReduction
C = copy(A)
b = BKZReduction(C)
b(BKZ.Param(block_size=30, flags=BKZ.AUTO_ABORT|BKZ.VERBOSE))
stats = b.stats; stats
{"i":   5,  "total":      1.02,  "time":     0.16,  "preproc":     0.03,  "svp":     0.05,  "r_0": 4.7503e+09,  "slope": -0.0541,  "enum nodes": 19.29,  "max(kappa)":  10}

That output isn’t that different from fplll outputs. However, in contrast to fplll (because I didn’t bother to implement it over there, yet) we also get access to a stats object after the computation finished. Let’s use it to inquire how many nodes where visited during enumeration

stats.enum_nodes
4085856

and how much time we spent in enumeration:

stats.svp_time
0.32868

fpylll also offers a few additional utility functions which go beyond what fplll offers such as copying submatrices and modular reduction.

Integration with other Projects

fpylll integrates reasonably nicely with Sage (once #20291 is merged, that is): converting back and forth between data types is seamless. For example:

sage: A = random_matrix(ZZ, 10, 10)
sage: from fpylll import IntegerMatrix, LLL
sage: B = IntegerMatrix.from_matrix(A)
sage: LLL.reduction(B)
sage: B.to_matrix(A)
[ -1   1  -1   0   1   0  -1  -2   0  -3]
[  4   0   0   0  -1   0  -1  -1   0   1]
[ -1   1   0   2  -3  -1  -2   0   0   3]
[  0  -1  -3  -1  -1   0  -3   0   2   3]
[ -2   2   0   0  -1   2  -1   2  -5   0]
[ -1   0   3   0   4   2   1  -2   1   2]
[ -1   6  -4   1   2  -1  -2   4   2   0]
[ -1   1  -7  -3   2  -3   6  -2  -4   3]
[  0  -7  -2   8   7  -9  -4   1  -4  -1]
[ -1   5   6 -12   4 -14  -4  -1  -2   5]

In fact, when installed inside Sage, element access for IntegerMatrix accepts and returns sage.rings.integer.Integer directly, instead of Python integers.

sage: type(B[0,0])
<type 'sage.rings.integer.Integer'>

fpylll also integrates somewhat with NumPy. To see how, let’s create a small NTRU-like matrix again:

from fpylll import *
A = IntegerMatrix.random(4, "ntrulike", bits=7, q=127)

We’d like to do some analysis on its Gram-Schmidt matrix, so let’s compute it:

sage: M = GSO.Mat(A)
sage: M.update_gso()
True

Let’s dump it into a NumPy array and spot check that the result is reasonably close:

sage: import numpy
sage: from fpylll.numpy import dump_mu
sage: N = numpy.ndarray(dtype="double", shape=(8,8))
sage: dump_mu(N, M, 0, 8)
sage: N[1,0] - M.get_mu(1,0)
0.0

Finally, let’s do something more or less useful with our output:

sage: numpy.linalg.eigvals(N)
[ -2.14381988e-39 +0.00000000e+00j  -1.51590958e-39 +1.51590958e-39j
  -1.51590958e-39 -1.51590958e-39j   3.26265223e-55 +2.14381988e-39j
   3.26265223e-55 -2.14381988e-39j   2.14381988e-39 +0.00000000e+00j
   1.51590958e-39 +1.51590958e-39j   1.51590958e-39 -1.51590958e-39j]

Tests

fpylll runs tests on every check-in for Python 2 and 3. As an added benefit, this extends test coverage for fplll as well, which only has a few highlevel tests.

Lisp

“This is all nice and well”, I hear you say, “but I prefer to do my computations in Lisp, so thanks, but not thanks”.

lisp_cycles.png

No worries, Hy has you covered:

=> (import [fpylll [*]])
=> (setv q 1073741789)
=> (setv A (.random IntegerMatrix 30 "ntrulike" :bits 30 :q q))   
=> (car A)
row 0 of <IntegerMatrix(60, 60) at 0x7f1cbbfbf888>
=> (get A 1)
row 1 of <IntegerMatrix(60, 60) at 0x7f1cbbfbf888>
=> (-> (car A) (.norm))
4019682565.5285482

=> (.reduction LLL A)
=> (.norm (car A))
6937.9845776709535

Help Wanted

fpylll isn’t quite done yet. Besides testing and documentation, it would be nice if someone would attempt to re-implement fplll’s LLL wrapper in pure Python. This would serve as a test case to see if everything that’s needed really is exposed and as a starting point for others who like to tweak the strategy. Speaking of LLL, fpylll is currently somewhat biased towards playing with BKZ, i.e. it would be nice to see how useful it is for trying out tweaks to the LLL algorithm.

Advertisements

One thought on “fpylll”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s