Abstracts

How ideal lattices unlocked fully homomorphic encryption
by Francisco Vial-Prado [slides] [video]

Ideal lattices played a fundamental role in the construction of the first Fully Homomorphic Encryption scheme. Indeed, these lattices were the mathematical object which validated the theoretical framework proposed by Gentry in his Ph.D. thesis. We will first give an overview of his construction, highlighting the importance of the ideal lattices involved. We then jump on time to describe fancy properties of recent FHE schemes : identity or attribute based FHE schemes, Multikey FHE schemes, Key-homomorphic FHE schemes, and discuss some open problems.

Ideal lattices in number theory and in cryptology
by Jean-François Biasse [slides] [video]

We introduce recent results on the computation of the ideal class group and the unit group of a number field and on the resolution of the so-called “principal ideal problem”.

We will introduce both classical and quantum algorithms for these tasks, and we will address the relevance of these results to lattice-based cryptography.

Fast Decoding of Hermitian Codes Using -Lattice Basis Reduction
by Johan S. R. Nielsen [slides] [video]

Joint work with Peter Beelen.

Hermitian codes are a sub-family of Algebraic Geometry codes - a huge family of evaluation codes defined using function fields over (usually) plane curves. Hermitian codes have very good minimum distance and can be significantly longer than Reed-Solomon codes over the same alphabet. Unfortunately, decoding becomes more complicated, and the best algorithms we know are still asymptotically slower than those we know for Reed-Solomon codes.

In this talk, I will present the first method which brings the complexity of decoding Hermitian codes down to , where n is the length of the code. We achieve this by embedding the core function field equation into multiple equations over , being the base field of the code. The resulting problem becomes a generalised Padé approximation over , which can be solved by finding a “short” vector in an explicitly given lattice. This in turn can be found using recent methods from computer algebra, though the notion of “short” involves some extra difficulties.

Our method applies to two approaches of decoding beyond half the minimum distance: Guruswami-Sudan and Power decoding. In this talk, however, we will focus on how we embed the function field problem into , and therefore we discuss only decoding up to half the minimum distance (minus half the genus).

Coppersmith's method and generalizations
by Luca De Feo [slides] [video]

In 1996 a famous series of papers by D. Coppersmith introduced a method for finding small integer roots of a polynomial modulo an integer of unknown factorization. To highlight the power of his method, Coppersmith presented polynomial-time attacks against a variety of naive realizations of RSA encryption.

Coppersmith’s method encodes the fact of having small roots into a lattice problem. All coefficients are lifted to , and a lattice is formed so that any root of the original polynomial will also be a root of any element of the lattice. After performing an LLL-reduction, the shortest vector in the reduced basis is such that any small integer root (in ) is also a root of the original polynomial modulo .

Coppersmith’s method has a number of generalization, and it has recently been remarked that its analogue on function fields is the famous Guruswami-Sudan algorithm for list decoding Reed-Solomon codes.

In this talk we will present the original method by Coppersmith, then we will skim through the generalizations and links with coding theory.

Crash course on Order Bases : Theory and Algorithms
by Romain Lebreton [slides] [video]

Contrary to the integer coefficient situation, lattice reduction with polynomial coefficients can be done in polynomial time. In this talk, we present the tools that provide the best current complexity for this problem. Order bases are the cornerstone of algorithms on matrices with polynomial coefficients. We will present the mathematical foundations of the notion of order basis. Then we will give a survey of modern order basis algorithms. Finally, we will sketch the path that goes from order bases to lattice reduction.