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.
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.
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).
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.
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.
