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 or any other secret parameter of the map. Instead, it solves the Extraction -graded CDH (Ext-GCDH) problem directly.
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.
A while back I described my (then current) setup to develop C code with Emacs. The other programming language I tend to spend a lot of time with is Python, specifically Sage’s Python. Here’s my Emacs setup for writing Sage code. For starters, it makes sense to highlight indentation in Python.
(use-package highlight-indentation :ensure t)
- M-. Goto definition for thing at point.
- M-, Switch to buffer of most recent marker.
- M-? Show documentation for context at point.
- M-r Show usage for thing at point.
(use-package anaconda-mode :ensure t :diminish anaconda-mode :config (bind-key "M-," #'anaconda-nav-pop-marker anaconda-mode-map))
Together with Rachel Player and Sam Scott (both also from the Information Security Group at Royal Holloway, University of London) we finally managed to put our survey on solving the Learning with Errors problem out. Here’s the abstract:
The Learning with Errors (LWE) problem has become a central building block of modern cryptographic constructions. This work collects and presents hardness results for concrete instances of LWE. In particular, we discuss algorithms proposed in the literature and give the expected resources required to run them. We consider both generic instances of LWE as well as small secret variants. Since for several methods of solving LWE we require a lattice reduction step, we also review lattice reduction algorithms and use a refined model for estimating their running times. We also give concrete estimates for various families of LWE instances, provide a Sage module for computing these estimates and highlight gaps in the knowledge about algorithms for solving the Learning with Errors problem.
When a year ends people make lists. I can only guess that several people are currently busy with writing “The 5 most revised papers on eprint ” and “The 8 best IACR flagship conference rump session presentations of 2014”. Since all the good lists are taken, my list has to be a little bit more personal. Alas, here is my list of stuff that happened in open-source computational mathematics in 2014 around me. That is, below I list what developments happened in 2014 and try to provide an outlook for 2015 (so that I can come back in a year to notice that nothing played out as planned).
If you are interested in any of the projects below feel invited to get involved. Also, if you are student and you are interested in working on one of the (bigger) projects listed below over the summer, get in touch: we could try to turn it into a Google Summer of Code 2015 project.
Meataxe64 is a large software development project to produce programs for working at high performance with large matrices over finite fields.
At the lowest level, the aim is to work modulo primes (only), using grease (much like “four Russians”) to reduce the amount of work, to use vectorized code in x86 assembler (SSE/AVX) to do the basic operations and to have short rows and few columns so that matrices fit suitably into the various levels of cache. The objective is to run as fast as possible with as little use of real-memory bandwidth as possible.
At a middle level, the aim is to use linear functions to work with extension fields, and to chop the matrices up so that the lowest level can operate.
At a higher level, the aim is to make effective use of a multi-core environment, building on the advantage that the cache-friendly lower level provides to ensure that many cores can be used effectively. The thread-farm looks after the messy signals, locks and thread handling.
It is hoped soon that a layer will be added to take a matrix that fits on disk but not in memory to extend the possible scale of operations further.
Finally I dream that a fault-tolerant distributed system can be build on top of this to handle matrices of gargantuan proportions, but this lies some considerable way into the future.
Go read the development blog, I certainly learned a lot from Richard Parker whenever we talked.
The list of accepted projects of this year’s Google Summer of Code is out. For the list of accepted projects for Sage see here, for the LMonade project see below, for all other accepted projects see Google’s site. I am going to mentor William’s M1RI project together with Clément Pernet. It’s going to be a blast.
This year Sage and lmonade are mentoring organizations for the Google Summer of Code again. We have many exciting projects for students to work (from home) over the summer, get mentored by experts in the field and get paid by Google.
Note that projects are not limited to the ideas presented on these pages. That is, if you have a nice project you’d like to propose, by all means do so! The application deadline for students is March 21st. These days they should be talking to potential mentors and forming an applications. If you know any student who might be interested or have access to any forum such students might read, please forward this announcement.