Can we Beat the Square Root Bound for ECDLP over Fp^2 via Representations?

Abstract

We give a 4-list algorithm for solving the Elliptic Curve Discrete Logarithm (ECDLP) over some quadratic field Fp2 . Using the representation technique, we reduce ECDLP to a multivariate polynomial zero testing problem. Our solution of this problem using bivariate polynomial multi-evaluation yields a p 1.314-algorithm for ECDLP. While this is inferior to Pollard’s Rho algorithm with square root (in the field size) complexity O (p), it still has the potential to open a path to an o(p)- algorithm for ECDLP, since all involved lists are of size as small as p 3 4 , only their computation is yet too costly.