salle A. Turing CE4
6 March 2012 - 14h00
Presumably hard problems in multivariate cryptography
by Charles Bouillaguet from ENS
Résumé : Public-key cryptography relies on the existence of computationaly hard
problems. It is not widely accepted that a public-key scheme is
worthless without a security proof, i.e., a proof that if an
attacker breaks the scheme, then she solves in passing an instance of
an intractable computational problem. As long as the hard problem is
intractable, then the scheme is secure. The most well-known hardness
assumptions of this kind are probably the hardness of integer
factoring, or that of taking logarithms in certain groups.
In this talk we focus on multivariate cryptography, a label covering
all the (mostly public-key) schemes explicitly relying on the hardness
of solving systems of polynomial equations in several variables over a
finite field. The problem, even when restricted to quadratic
polynomials, is well-known to be NP-complete. In the quadratic case,
it is called MQ. Interestingly, most schemes in this area are not
provably secure, and a lot of them have been broken because they
relied on another, less well-known, computational assumption, the
hardness of Polynomial Linear Equivalence (PLE), which is a
higher-degree generalization the problem testing whether two matrices
are equivalent.
In this talk I will present the algorithms I designed to tackle these
two hard problems. I will show that 80 bits of security are not enough
for MQ to be practically intractable, and I will present
faster-than-before, sometimes practical algorithms for various flavors
of PLE.
Slides of the Presentation.
