For the organizers, this year’s Eurocrypt must have been a huge challenge. Due to the France-Afrique summit, they had to relocate a large part of the conference from Nice to Monaco, with only a few months of delay. In any case, they did a great job and the conference is running very smoothly.

From a technical point of view, this Eurocrypt has also been very nice. One very active new trend concerns fully homomorphic schemes and the use of LWE (Learning with errors) and Lattices. In particular, Vinod Vaikuntanathan presented a new fully homorphic scheme based on learning with errors of the integers (from a paper with Marten van Dijk, Craig Gentry and Shai Halevi). I will not go into the details of their scheme, but I would like to present the underlying hard problem. In the simplest instantiation of their scheme, which was presented at the conference but slightly differ from the version described in the article, everything boils downs to the following problem:

Given an exact multiple of a prime p and many approximate multiples of p, recover the prime p.

Clearly, with two exact multiples, the problem is usually easy and it essentially suffices to compute a GCD to be done. With a single exact multiple, we have an approximate GCD problem (as introduced by Nick Howgrave-Graham at CaLC 2001). This problem can often be solved using lattice reduction. However, in the above homomorphic scheme, the parameters have been chosen to prevent this lattice reduction approach from working. More precisely, it would work without any trouble using a lattice reduction oracle but fails when LLL is used (due to the fact that LLL only finds an approximate shortest vector). More precisely, the chosen multiples (or approximate multiples) are huge compared to p.

In the proceedings, a more variant of the problem is used. In this variant, no exact multiple is available and only approximate multiples are given. In this case, no approach to solving the problem is currently known.

According to wikipedia, the first cryptographic scheme based on this approximate GCD problem was published by Levieil and Naccache at PKC 2008, in a paper entitled “Cryptographic Test Correction”.

On the cryptanalysis side of this lattice topic, Nicolas Gama presented his paper with Phong Nguyen and Oded Regev on a new analysis of pruned enumeration of short vectors in lattices. Remarkably, this allowed then to find the shortest non-zero vectors in lattices of dimension 110, a task which previously was completely out of practical range.

PS: For those who are interested, I attach my Eurocrypt 2010 slides of the knapsack algorithm developed with Nick Howgrave-Graham.