PolyBoRi is dead, it needs your help

On the Sage development list a discussion is going on what to do about PolyBoRi. For those who do not know PolyBoRi, for computing Gröbner bases for Boolean polynomials it is pretty much the only (open-source) game in town (as far as I know):

The core of PolyBoRi is a C++ library, which provides high-level data types for Boolean polynomials and monomials, exponent vectors, as well as for the underlying polynomial rings and subsets of the powerset of the Boolean variables. As a unique approach, binary decision diagrams are used as internal storage type for polynomial structures.

On top of this C++-library we provide a Python interface. This allows parsing of complex polynomial systems, as well as sophisticated and extendable strategies for Gröbner base computation. PolyBoRi features a powerful reference implementation for Gröbner basis computation.

Boolean polynomials show up a lot in cryptography and other areas of computer science.

The trouble with PolyBoRi is that both authors of PolyBoRi – Alexander Dreyer and Michael Brickenstein – left academia and have jobs now which have nothing to do with PolyBoRi. Hence, PolyBoRi is currently not maintained. This is a big problem. In particular, there are some issues with PolyBoRi which cannot be ignored forever:

  • PolyBoRi uses Python (yay) but only Python 2. At some point the world – i.e. Sage – will switch to Python 3 and PolyBoRi is the only obstacle to that switch except for the Sage Python library itself.
  • PolyBoRi uses Scons as a build system. Everybody would be a lot happier if it was switched to using autotools (which are a lot more awesome than many people realise).

In the long-term the Singular team might get involved and keep PolyBoRi alive, but this is not certain. Also, there is a push for a decision about what to do with PolyBoRi in Sage now.

The current proposal on the table is to drop PolyBoRi from the default Sage installation, i.e. to demote it to an optional package. In my mind, this would be very bad as Sage and PolyBoRi benefit from the tight integration that currently exists. Also, in my experience, optional packages tend to simply not work that well as they are not tested in each release.

Hence, if you care about PolyBoRi you should consider to

  1. let us know in the relevant thread on the mailing list if you use PolyBoRi in Sage.
  2. volunteer to help to autotool-ify PolyBoRi if you speak autotools. (If you don’t speak autotools, you should learn, they are awesome.)
  3. volunteer to help to port PolyBoRi from Python 2 to Python 3.

I’m up for getting involved, but I don’t want to take on the responsibility alone.

Update (2015-06-13): A fair share of work has already been done by Andrew. Still, anyone up for helping out?

15th IMA International Conference on Cryptography and Coding

IMA-CCC (Facebook) is a crypto and coding conference biennially held in the UK. It was previously held in Cirencester. So you might have heard of it as the “Cirncester” conference. However, it has been moved to Oxford, so calling it Cirencester now is a bit confusing. Anyway, it is happening again this year. IMA is a small but fine conference with the added perk of being right before Christmas. This is great because around that time of the year Oxford is a fairly Christmas-y place to be.

Continue reading “15th IMA International Conference on Cryptography and Coding”

Sage Code for GGH Cryptanalysis by Hu and Jia

Recently, Yupu Hu and Huiwen Jia put a paper on the Cryptology ePrint Archive which describes a successful attack of the GGH (and GGHLite) candidate multilinear map. The attack does not try to recover the secret g or any other secret parameter of the map. Instead, it solves the Extraction \kappa-graded CDH (Ext-GCDH) problem directly.

Continue reading “Sage Code for GGH Cryptanalysis by Hu and Jia”

Google Summer of Code 2015

Both Sage and the Lmonade project were selected for Google’s Summer of Code 2015. If you are an eligible student, you should consider applying. If you need ideas what to work on, there are many fine projects/project ideas on either the Lmonade or the Sage GSoC pages. In particular, here are the fplll project ideas, for which I could be one of the two mentors.

Continue reading “Google Summer of Code 2015″