Paper 2024/924

Climbing and descending tall volcanos

Steven Galbraith, University of Auckland
Abstract

We revisit the question of relating the elliptic curve discrete logarithm problem (ECDLP) between ordinary elliptic curves over finite fields with the same number of points. This problem was considered in 1999 by Galbraith and in 2005 by Jao, Miller, and Venkatesan. We apply recent results from isogeny cryptography and cryptanalysis, especially the Kani construction, to this problem. We improve the worst case bound in Galbraith's 1999 paper from $\tilde{O}( q^{1.5} )$ to (heuristically) $\tilde{O}( q^{0.4} )$ operations. The two cases of main interest for discrete logarithm cryptography are random curves (flat volcanoes) and pairing-based crypto (tall volcanoes with crater of constant or polynomial size). In both cases we show a rigorous $\tilde{O}( q^{1/4})$ algorithm to compute an isogeny between any two curves in the isogeny class. We stress that this paper is motivated by pre-quantum elliptic curve cryptography using ordinary elliptic curves, which is not yet obsolete.

Note: The July 2nd version fixes a few mistakes

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision. To appear at Algorithmic Number Theory ANTS XVI
Keywords
isogenyvolcanoelliptic curve cryptography
Contact author(s)
s galbraith @ auckland ac nz
History
2024-07-02: revised
2024-06-10: received
See all versions
Short URL
https://ia.cr/2024/924
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

@misc{cryptoeprint:2024/924,
      author = {Steven Galbraith},
      title = {Climbing and descending tall volcanos},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/924},
      year = {2024},
      url = {https://eprint.iacr.org/2024/924}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.