Hi,
giving interfaces initially developped for Sage to upstream is the way to go.
The benefits of free-software ecosystem should be two-ways, otherwise Sage is
only predating other softwares.
Moreover with such an approach, upstream will make it cover all features when
they appear so that they are automatically exposed to Sage users, and they can
ship Python bindings independently of Sage (which many mathematician consider
as too big for their specific needs). In the concrete case of fpLLL, we already
had the case where some developper reimplemented a feature of fpLLL just
because it was not exposed by our partial (not up-to-date) interface, see
https://trac.sagemath.org/ticket/15758
A common Python bindings is probably a better place to cut (for modularity)
than between upstream binary and Sage Cython bindings (though i admint that in
some specific cases, it may add a slowing Python layer).
+1 for using fpylll and make it standard.
Ciao,
Thierry
On Fri, Aug 05, 2016 at 12:32:53PM +0100, 'Martin R. Albrecht' via sage-devel
wrote:
> 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
>
> https://github.com/fplll/fplll
>
> 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
>
> https://github.com/fplll/fpylll
>
> 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?
>
> Cheers,
> Martin
>
> PS: Here is some random benchmark:
>
> $ ./latticegen q 100 50 30 b > ~/test_lattice.txt
>
> new fplll
>
> $ time ./fplll -a bkz -s ../strategies/default.json -bkzautoabort -v -b 60
> ~/test_lattice.txt > /dev/null
> Entering BKZ:
> block size: 60, flags: 0x0021, max_loops: 0, max_time: 0.0, autoAbort:
> (1., 5),
>
> End of BKZ loop0, time =12.832s, r_0 = 1.80e10, slope = -0.056809,
> log2(nodes) = 28.142067
> End of BKZ loop1, time =25.072s, r_0 = 1.07e10, slope = -0.050003,
> log2(nodes) = 29.120454
> End of BKZ loop2, time =36.836s, r_0 = 1.00e10, slope = -0.048468,
> log2(nodes) = 29.623702
> End of BKZ loop3, time =48.944s, r_0 = 9.42e9, slope = -0.048443,
> log2(nodes) = 29.991966
> End of BKZ loop4, time =58.176s, r_0 = 9.42e9, slope = -0.048230,
> log2(nodes) = 30.207781
> End of BKZ loop5, time =67.904s, r_0 = 9.42e9, slope = -0.048134,
> log2(nodes) = 30.414377
> End of BKZ loop6, time =78.040s, r_0 = 9.42e9, slope = -0.048500,
> log2(nodes) = 30.611421
> End of BKZ loop7, time =87.780s, r_0 = 9.42e9, slope = -0.048197,
> log2(nodes) = 30.784449
> End of BKZ loop8, time =96.468s, r_0 = 9.42e9, slope = -0.047948,
> log2(nodes) = 30.910345
> End of BKZ loop
