Paper 2019/800
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.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. NuTMiC 2019
- Keywords
- ECDLP
- Contact author(s)
- claire delaplace @ rub de
- History
- 2019-07-14: received
- Short URL
- https://ia.cr/2019/800
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/800,
author = {Claire Delaplace and Alexander May},
title = {Can we Beat the Square Root Bound for {ECDLP} over $\mathbb{F}_{p^2}$ via Representations?},
howpublished = {Cryptology {ePrint} Archive, Paper 2019/800},
year = {2019},
url = {https://eprint.iacr.org/2019/800}
}
