Polynomial systems of equations appearing in cryptography tend to have special structures that simplify their resolution. In this talk, we discuss a class of polynomial systems arising after deploying a multivariate polynomial equation over an extension field into a system of polynomial equations over the ground prime field (a technique commonly called Weil descent).

We provide theoretical and experimental evidence that the degrees of regularity of these systems are very low, in fact only slightly larger than the maximal degrees of the equations.

We then discuss cryptographic applications of (particular instances of) these systems to the hidden field equation (HFE) cryptosystem, to the factorization problem in SL(2,2^n) and to the elliptic curve discrete logarithm over binary fields. In particular, we show (under a classical heuristic assumption in algebraic cryptanalysis) that an elliptic curve index calculus algorithm due to Claus  iem has subexponential time complexity O(2^{c\,n^{2/3}\log n})\) over the binary field GF(2^n), where c is a constant smaller than 2.

This talk is based on our Eurocrypt'12 paper (with Jean-Charles Faugère, Ludovic Perret and Guénaël Renault) and Asiacrypt'12 paper (with Jean-Jacques Quisquater).

 

Christophe Petit is a Post-doc at UCL Crypto Group, Louvain-la-Neuve. After a PhD thesis completed under supervision of Jean-Jacques Quisquater, he was a visiting scholar at UCSD, Paris VI and Ecole Polytechnique. His research interests go from the mathematical aspects of Cryptography to the modeling and analysis of side-channel and fault attacks. He is particularly interested in developing new algorithms for number theoretic assumptions used in cryptography.