Can we beat the square root bound for ECDLP over \(\mathbb{F}_p^2\) via representation? (Q2023309)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Can we beat the square root bound for ECDLP over \(\mathbb{F}_p^2\) via representation? |
scientific article |
Statements
Can we beat the square root bound for ECDLP over \(\mathbb{F}_p^2\) via representation? (English)
0 references
3 May 2021
0 references
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.
0 references
representations
0 references
multivariate polynomial zero-testing
0 references
elliptic curve discrete logarithm (ECDLP)
0 references
0 references
0 references
0 references