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