分野別セミナー

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. Based on joint work with Jean-Charles Faugère, Ludovic Perret, Jean-Jacques Quisquater and Guénaël Renault.