CCIS Seminar - Tuesday 6 March 2012 - salle A. Turing CE4
14:00:00 - Salle de salle A. Turing CE4

Charles Bouillaguet, ENS

Presumably hard problems in multivariate cryptography

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.

Home page CCIS Seminars
How to come to salle A. Turing CE4 -