**Can we Beat the Square Root Bound for ECDLP over $\mathbb{F}_{p^2}$ via Representations?**

*Claire Delaplace and 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.

**Category / Keywords: **ECDLP

**Original Publication**** (in the same form): **NuTMiC 2019

**Date: **received 10 Jul 2019

**Contact author: **claire delaplace at rub de

**Available format(s): **PDF | BibTeX Citation

**Version: **20190714:154856 (All versions of this report)

**Short URL: **ia.cr/2019/800

[ Cryptology ePrint archive ]