London-ish Lattice Coding & Crypto Meeting: 21 September 2016

The next London-ish Lattice Coding & Crypto Meeting is coming up on September 21.

Programme

  • 11:00–12:30 | Jean-Claude Belfiore: Ideal Lattices: Connections between number fields and coding constructions
  • 13:30–15:00 | Dan Shepherd: Rings and Modules for Identity-Based Post-Quantum Public-Key Cryptography
  • 15:30–16:30 | Antonio Campello: Sampling Algorithms for Lattice Gaussian Codes
  • 16:30–17:00 | Cong Ling: Lattice Gaussian Sampling with Markov Chain Monte Carlo (MCMC)
  • 17:00–18:30 | Daniel Dadush: Solving SVP and CVP in 2^n Time via Discrete Gaussian Sampling

Venue

Arts Building Ground Floor Room 24
Royal Holloway, University of London
Egham Hill
Egham
Surrey TW20 0EX

See meeting website for details.

fpylll

fpylll is a Python library for performing lattice reduction on lattices over the Integers. It is based on the fplll, a C++ library which describes itself as follows:

fplll contains several algorithms on lattices that rely on floating-point computations. This includes implementations of the floating-point LLL reduction algorithm, offering different speed/guarantees ratios. It contains a ‘wrapper’ choosing the estimated best sequence of variants in order to provide a guaranteed output as fast as possible. In the case of the wrapper, the succession of variants is oblivious to the user. It also includes a rigorous floating-point implementation of the Kannan-Fincke-Pohst algorithm that finds a shortest non-zero lattice vector, and the BKZ reduction algorithm.

fplll is distributed under the GNU Lesser General Public License (either version 2.1 of the License, or, at your option, any later version) as published by the Free Software Foundation.

In short, fplll is your best bet at a publicly available fast lattice-reduction library and fpylll provides a convenient interface for it — for experimentation, development and extension — from Python.

For the rest of this post, I’ll give you a tour of the features currently implemented in fpylll and point out some areas where we could do with some help.

Continue reading “fpylll”

London-ish Lattice Coding & Crypto Meetings

Cong Ling and myself are starting London-ish Lattice Coding & Crypto Meetings. Please help us spread the word.

Lattice-based approaches are emerging as a common theme in modern cryptography and coding theory. In communications, they are an indispensable mathematical tool to construct powerful error-correction codes achieving the capacity of wireless channels. In cryptography, they are used to building lattice-based schemes with provable security, better asymptotic efficiency, resilience against quantum attacks and new functionalities such as fully homomorphic encryption.

We are setting up meetings on lattices in cryptography and coding in the London area. 1 These meetings are inspired by similar meetings held in Lyon 2 and are aimed at connecting the two communities in the UK with a common interest in lattices, with a long-term goal of building a synergy of the two fields.

The meetings will consist of several talks on related topics, with a format that will hopefully encourage interaction (e.g. longer than usual time slots).

Tentative program

For details (as they become available) see website.

11:00 – 12:30: Achieving Channel Capacity with Lattice Codes Cong Ling

13:30 – 15:00: Post-Quantum Cryptography Nigel Smart

15:00 – 16:30: Lattice Coding with Applications to Compute-and-Forward Alister Burr

16:30 – 18:00: A Subfield Lattice Attack on Overstretched NTRU Assumptions Martin Albrecht

Venue

Room 611
(Dennis Gabor Seminar Room)
Department of Electrical and Electronic Engineering
Imperial College London
South Kensington London
SW7 2AZ

http://www.imperial.ac.uk/visit/campuses/south-kensington/

Registration

Everyone is welcome. Two caveats:

  1. Speakers are told the audience is somewhat familiar with lattices.
  2. Please send us an email at c.ling@imperial.ac.uk, so that the size of the room fits with the number of participants.

Footnotes:

1

Our definition of London includes Egham, where Royal Holloway’s main campus is located.

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”

Looking Back and Forward for Open-Source Mathematics Software (2014)

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.

Continue reading “Looking Back and Forward for Open-Source Mathematics Software (2014)”

Lattice Stuff

We — with Jean-Charles FaugèreRobert Fitzpatrick and Ludovic Perret – managed to finish our work on the cryptanalysis of all proposed parameters of the public-key encryption scheme proposed at PKC 2012 by Huang, Liu and Yang. The key observation is that the scheme can be viewed as an easy LWE instance:

In this paper, we investigate the security of a public-key encryption scheme introduced by Huang, Liu and Yang (HLY) at PKC’12. This new scheme can be provably reduced to the hardness of solving a set of quadratic equations whose coefficients of highest degree are chosen according to a discrete Gaussian distributions. The other terms being chosen uniformly at random. Such a problem is a variant of the classical problem of solving a system of non-linear equations (PoSSo), which is known to be hard for random systems. The main hypothesis of Huang, Liu and Yang is that their variant is not easier than solving PoSSo for random instances. In this paper, we disprove this hypothesis. To this end, we exploit the fact that the new problem proposed by Huang, Liu and Yang reduces to an easy instance of the Learning With Errors (LWE) problem. The main contribution of this paper is to show that security and efficiency are essentially incompatible for the HLY proposal. That is, one cannot find parameters which yield a secure and a practical scheme. For instance, we estimate that a public-key of at least 1.03 GB is required to achieve 80-bit security against known attacks. As a proof of concept, we present practical attacks against all the parameters proposed Huang, Liu and Yang. We have been able to recover the private-key in roughly one day for the first challenge proposed by HLY and in roughly three days for the second challenge.

Furthermore, I gave a talk yesterday on solving LWE with binary secret using a variant of the BKW algorithm at SIAM AG’13.