Hi Sage developers,
*tl;dr* Fplll 5.0 is about to hit the streets. It’s a major improvement
over Fplll 4.* which we currently ship with Sage. To update we need to
change the user interface of the function `IntegerMatrix.BKZ`. I
suggest to drop Sage’s own interface to Fplll in favour of the official
Fpylll interface, which I propose to make a standard package.
[ ] Yes
[ ] No
[ ] Maybe
# Details #
We are getting ready to release Fplll 5.0.0. Here are some highlights
from the changelog https://raw.githubusercontent.com/fplll/fplll/master/NEWS
- fplll switched to more open development model on GitHub
with a bigger development community
- public implementation of all techniques collectively known as BKZ 2.0.
BKZ in block size 80 is a reasonably easy computation now.
- build system overhaul, automated tests, test coverage increase
- Self-Dual BKZ and Slide reduction
- faster, recursive enumeration implementation
- Gaussian lattice sieving
- optional support for doubledouble and quaddouble
If you care only about LLL then this release won’t change much for you,
because Sage doesn’t ship libqd. But if you care about stronger lattice
reduction this release makes a huge difference.
# Sage Interface #
(a) Sage’s public interface is through the functions `IntegerMatrix.LLL` and
`IntegerMatrix.BKZ` and a few functions on the integer lattice class.
(b) These call some in `libs.fplll`
The the interface for calling BKZ has changed and does not match Sage’s
interface (a). We could write a translation layer, but I’d prefer to
simply change it. Users will want to use the new interface.
I also suggest to replace (b) completely with
It’s a Cython interface to fplll + additional Python code which started
as a fork of Sage’s Cython interface. It’s much more flexible and
powerful than what Sage has to offer. For example, it (easily) allows to
implement BKZ and LLL variants in pure Python. Strong lattice reduction
is a major area of research for cryptographers at the moment and this
library aims to make experimentation for this easy.
It is mainly written and maintained by me. Lattice-based cryptography
will be research area for the foreseeable future and this code is a key
component of this research for me, so I plan to maintain and improve it
over the next few years. I do commit to maintaining it in Sage, too.
The code has tests which are run on every check in.
Yes, No, Maybe?
PS: Here is some random benchmark:
$ ./latticegen q 100 50 30 b > ~/test_lattice.txt
$ time ./fplll -a bkz -s ../strategies/default.json -bkzautoabort -v -b 60 ~/test_lattice.txt > /dev/null
block size: 60, flags: 0x0021, max_loops: 0, max_time: 0.0, autoAbort: (1.0000, 5),
End of BKZ loop 0, time = 12.832s, r_0 = 1.80e10, slope = -0.056809, log2(nodes) = 28.142067
End of BKZ loop 1, time = 25.072s, r_0 = 1.07e10, slope = -0.050003, log2(nodes) = 29.120454
End of BKZ loop 2, time = 36.836s, r_0 = 1.00e10, slope = -0.048468, log2(nodes) = 29.623702
End of BKZ loop 3, time = 48.944s, r_0 = 9.42e9, slope = -0.048443, log2(nodes) = 29.991966
End of BKZ loop 4, time = 58.176s, r_0 = 9.42e9, slope = -0.048230, log2(nodes) = 30.207781
End of BKZ loop 5, time = 67.904s, r_0 = 9.42e9, slope = -0.048134, log2(nodes) = 30.414377
End of BKZ loop 6, time = 78.040s, r_0 = 9.42e9, slope = -0.048500, log2(nodes) = 30.611421
End of BKZ loop 7, time = 87.780s, r_0 = 9.42e9, slope = -0.048197, log2(nodes) = 30.784449
End of BKZ loop 8, time = 96.468s, r_0 = 9.42e9, slope = -0.047948, log2(nodes) = 30.910345
End of BKZ loop 9, time = 117.404s, r_0 = 9.42e9, slope = -0.048360, log2(nodes) = 31.053923
End of BKZ loop 10, time = 143.812s, r_0 = 9.42e9, slope = -0.048163, log2(nodes) = 31.180644
End of BKZ loop 11, time = 164.652s, r_0 = 9.42e9, slope = -0.047898, log2(nodes) = 31.286769
End of BKZ loop 12, time = 203.492s, r_0 = 9.20e9, slope = -0.048275, log2(nodes) = 31.392854
End of BKZ loop 13, time = 236.376s, r_0 = 9.20e9, slope = -0.047879, log2(nodes) = 31.501613
End of BKZ loop 14, time = 284.636s, r_0 = 9.20e9, slope = -0.048120, log2(nodes) = 31.608491
End of BKZ loop 15, time = 310.472s, r_0 = 9.20e9, slope = -0.047999, log2(nodes) = 31.696863
End of BKZ loop 16, time = 328.624s, r_0 = 9.20e9, slope = -0.048367, log2(nodes) = 31.795334
End of BKZ loop 17, time = 340.940s, r_0 = 9.20e9, slope = -0.048103, log2(nodes) = 31.876720
End of BKZ loop 18, time = 350.668s, r_0 = 9.20e9, slope = -0.048362, log2(nodes) = 31.940467
End of BKZ: success
fplll 4.* in Sage:
$ time fplll -a bkz -bkzautoabort -v -b 60 -bkzmaxloops 1
-> killed after 80 minutes without finishing the first tour.
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF