Can we beat the square root bound for ECDLP over \(\mathbb{F}_p^2\) via representation? (Q2023309)

Let \(E\) be an elliptic curve, defined over a finite field \(\mathbb{F}_q\). Given two points \(P\) and \(Q\) on \(E\) such that \(Q = kP\), where \(k\) is an integer, the elliptic curve discrete logarithm problem (ECDLP) consists in recovering \(k\). In this paper, a 4-list algorithm using the representation technique for solving ECDLP over \(\mathbb{F}_{p^2}\) is presented. The authors introduce a problem, called Zero-Join (ZJ-Problem), which given two lists \(A\) and \(B\) of elements of \(\mathbb{F}_{p^2}\), and a polynomial \(f \in \mathbb{F}_p[X_1, X_2, X_3, X_4]\) consists in returning all \(((x_1, y_1), (x_2, y_2))\in A \times B \) with \(f(x_1, y_1, x_2, y_2) = 0\). It is shown that \(|A|\cdot |B| = p^{3/2}\), and that any algorithm which solves the ZJ-Problem in time \(T\) and in memory \(M\) also solves ECDLP over \(\mathbb{F}_{p^2}\) in time \(T\) and memory \(M\). If \(|A| = |B| = p^{3/4}\), and the ZJ-Problem could be solved in time linear in \(|A|\) and \(|B|\), then ECDLP could be solved in time \(O(p^{3/4})\). A trivial solution to the ZJ-Problem can be achieved in quadratic time which results in a \(p^{3/2}\)-algorithm. Furthermore, it is proved that the ZJ-Problem admits sub-quadratic solutions. Moreover, using multi-evaluation techniques for bivariate polynomials, a \(p^{1.314}\)-algorithm is obtained.