fplll 5.0 in sage

153 views
Skip to first unread message

Martin R. Albrecht

unread,
Aug 5, 2016, 7:32:58 AM8/5/16
to sage-...@googlegroups.com, fplll-devel
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.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
~/test_lattice.txt

-> killed after 80 minutes without finishing the first tour.

--

_pgp: https://keybase.io/martinralbrecht
_www: https://martinralbrecht.wordpress.com
_jab: martinr...@jabber.ccc.de
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF

Dima Pasechnik

unread,
Aug 5, 2016, 8:10:48 AM8/5/16
to sage-devel


On Friday, August 5, 2016 at 12:32:58 PM UTC+1, Martin Albrecht 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.

[X ] Yes

Thierry

unread,
Aug 5, 2016, 8:44:42 AM8/5/16
to 'Martin R. Albrecht' via sage-devel, fplll-devel
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
> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

Johan S. H. Rosenkilde

unread,
Aug 5, 2016, 10:15:07 AM8/5/16
to sage-...@googlegroups.com
Sounds pretty great!

> [X] Yes
> [ ] No
> [ ] Maybe

Best,
Johan

Jean-Pierre Flori

unread,
Aug 9, 2016, 5:46:59 AM8/9/16
to sage-devel
Yes!

Did you open a ticket for this?

Martin R. Albrecht

unread,
Aug 11, 2016, 7:06:30 AM8/11/16
to sage-...@googlegroups.com
This is now

https://trac.sagemath.org/ticket/21221

Cheers,
Martin

Jean-Pierre Flori writes:
> Yes!
>
> Did you open a ticket for this?


Reply all
Reply to author
Forward
0 new messages