Paper 2019/800

Can we Beat the Square Root Bound for ECDLP over Fp2 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 Fp2. 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 p1.314-algorithm for ECDLP. While this is inferior to Pollard's Rho algorithm with square root (in the field size) complexity 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 p34, 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},
      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.