Abstract |
: |
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 Diem 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). |