meataxe64

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.

PyME 0.9.0

PyMe is a Python interface to GPGME library using SWIG. Being based on SWIG, which does most of the heavy lifiting, it should be fairly complete in terms of coverage of what GPGME has to offer. Here is the history of PyMe as far as I understand it.

  1. PyMe up to v0.5.1 was written and maintained by John Goerzen in 2002.
  2. From 2004-2008 Igor Belyi maintained PyMe and produced up to v0.8.1.
  3. In 2014 I took over maintaining PyMe because there was no one who would accept by tiny bugfix.

Alas, here is PyME 0.9.0.

Changelog

  • python setup.py calls make swig, so
  • pip install git+https://bitbucket.org/malb/pyme should work
  • op_export_keys() works now
  • revision constrol was switched from SVN on Sourceforge to Git on Bitbucket.

Mailing List

If you have bug reports, suggestions etc. please send them to pyme-help@lists.sourceforge.net which is still the official PyME support mailing list. Speaking of which:

Bugs

Support for Windows is currently untested, so it is probably broken. It would be much appreciated if those who use PyME on Windows could step up and offer their help in maintaining that part.

IACR Statement

The IACR membership meeting at Eurocrypt produced a statement on mass surveillance:

Statement of Principle from the IACR Membership on Mass Surveillance and the Subversion of Cryptography

The membership of the IACR repudiates mass surveillance and the undermining of cryptographic solutions and standards. Population-wide surveillance threatens democracy and human dignity. We call for expediting research and deployment of effective techniques to protect personal privacy against governmental and corporate overreach.

I could think of stronger words, but then, I’m not trying to speak for all cryptographers.

LMonade GSoC 2014 Accepted Projects

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.

Continue reading

Sage & LMonade GSOC 2014

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.

Cryptanalysis of the FHE based on GACD?

Jintai Ding and Chengdong Tao published a new preprint on the IACR’s ePrint titled A New Algorithm for Solving the Approximate Common Divisor Problem and Cryptanalysis of the FHE based on GACD.

Abstract. In this paper, we propose a new algorithm for solving the approximate common divisors problems, which is based on LLL reduction algorithm of certain special lattice and linear equation solving algorithm over integers. Through both theoretical argument and experimental data, we show that our new algorithm is a polynomial time algorithm under reasonable assumptions on the parameters. We use our algorithm to solve concrete problems that no other algorithm could solve before. Further more, we show that our algorithm can break the fully homomorphic encryption schemes, which are based on the approximate common divisors problem, in polynomial time in terms of the system parameter λ.

It is worth emphasising that the Approximate GCD problem not only underpins one of the few fully homomorphic encryption schemes we have but it is also somewhat related to one of two candidates for multilinear maps. So if it could be shown to be easy then this would be somewhat sad as the choice of problems for building fancy crypto schemes would have gotten a lot smaller. So what is the Approxmiate GCD problem? Continue reading