Thursday, November 26, 2015

Lattice meeting in Lyon

On November 25 and 26 I, together with some colleagues from the ENS lab, have taken part in a lattice meeting held at ENS Lyon and organized by Damien Stehlé.

We took a morning train from Paris to Lyon, where we arrived at about 11 am. We then had lunch in a Spanish restaurant, where we enjoyed some tapas, tortillas, serrano ham and other delicious things, before heading for ENS Lyon for the meeting.

The first talk, based on this article, was given by Nicolas Gama, from Inpher Switzerland and UVSQ France, and the title was "Solving shortest and closest vector problems: the decomposition approach". He began by giving some background notions on lattices (and also showed a very nice 3D animation of a lattice which was very appreciated by the audience) before moving on to the real topic of the talk. After introducing the Minkowski inequality he talked about the hardness of the SVP problem and showed us a graph which gives an idea of how the hardness changes when we choose a different approximation factor.
Then he talked about lattice basis reduction, starting from Lagrange's algorithm, which unfortunately works only for dimension 2: for higher dimensions we have LLL algorithm by Lenstra, Lenstra and Lovasz.
The central part of the talk was dedicated to sieving algorithms to solve SVP and CVP problems. Three kinds of approach were presented: based on geometric clustering, based on "representation and decomposition" and based on "towers of lattices", which means considering many lattices, each one included in the following one.

The second talk, based on this article, was given by Ilya Ozerov, who is about to complete his PhD in RUB, and the title was "On computing nearest neighbours with applications to decoding of binary linear codes". After a quick introduction to codes he presented a new algorithm which achieves the fastest decoding for random binary linear codes, with a complexity of $2^{0.097n}$, which is a nice improvement on Prange's $2^{0.121n}$ (1962) and subsequent results.

After two very interesting talks, we had a nice dinner in a bouchon Lyonnaise and... now we get ready for day two! In particular we will talk about algebraic algorithms for LWE and nearest neighbour searching with applications to lattice sieving.

Stay tuned for the second part!

Day 2

The second day started with a talk given by Ludovic Perret, from UPMC. The talk, based on this paper, was about "Algebraic algorithms for LWE". After a very quick introduction to the LWE problem and the worst-case/average-case connection with Gap-SVP problem, the speaker presented the Arora-Ge algorithm and introduced the BinaryError LWE problem, which features a binary error but provides the same security guarantee as the normal version of the problem. In this case we have to pay a particular attention to the number of samples that is given: if the error is binary then it must be limited, while in the general case there is no such constraint and we can have as many samples as we want. In the second part of the talk, a proof of the Arora-Ge algorithm was presented.

Léo Ducas from CWI gave the second talk of the day about "New directions in nearest neighbour searching with applications to lattice sieving". During this talk the technique of sieving and the Gap-NNS problem were presented.

Conclusions:
This was my first lattice meeting and I have to say it was a really nice experience, so I would like to thank the organizers and all the friends I spent time with. I think such meetings are a wonderful opportunity to learn new things, ask questions and discuss new ideas, but also to meet people from different institutions who work on various problems.
Should anyone be interested, the next lattice meeting will be on January 21 and 22 in Paris. It will be organized by ENS Paris, and we hope to welcome many researchers!