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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2019/800}},
      url = {https://eprint.iacr.org/2019/800}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.