Welcome to the resource topic for 2019/800
Title:
Can we Beat the Square Root Bound for ECDLP over \mathbb{F}_{p^2} via Representations?
Authors: Claire Delaplace, Alexander May
Abstract:We give a 4-list algorithm for solving the Elliptic Curve Discrete Logarithm (ECDLP) over some quadratic field \mathbb{F}_{p^2}. 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 \mathcal{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^{\frac 3 4}, only their computation is yet too costly.
ePrint: https://eprint.iacr.org/2019/800
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .