The elliptic curve discrete logarithm problem (ECDLP) is commonly believed to be much harder than its finite field counterpart, resulting in smaller cryptography key sizes. In this talk, we review recent results suggesting that ECDLP is not as hard as previously expected in the case of composite fields.
We first recall how Semaev's summation polynomials can be used to build index calculus algorithms for elliptic curves over composite fields. These ideas due to Pierrick Gaudry and Claus Diem reduce ECDLP over composite fields to the resolution of polynomial systems of equations over the base field.
We then argue that the particular structure of these systems makes them much easier to solve than generic systems of equations. In fact, the systems involved here can be seen as natural extensions of the well-known HFE systems, and many theoretical arguments and experimental results from HFE literature can be generalized to these systems as well.
Finally, we consider the application of this heuristic analysis to a particular ECDLP index calculus algorithm due to Claus Diem. As a main consequence, we provide evidence that ECDLP can be solved in heuristic subexponential time over composite fields. We conclude the talk with concrete complexity estimates for binary curves and perspectives for furture works.
The talk is based on joint works with Jean-Charles Faugère, Timothy Hodges, Yung-Ju Huang, Ludovic Perret, Jean-Jacques Quisquater, Guénaël Renault, Jacob Schlatter, Naoyuki Shinohara, Tsuyoshi Takagi