Climbing and descending tall volcanos

Steven Galbraith

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: isogeny volcano elliptic 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: 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}
}