Searching for differential addition chains

Daniel J. Bernstein; Jolijn Cottaar; Tanja Lange

Paper 2024/1044

Searching for differential addition chains

Daniel J. Bernstein

Jolijn Cottaar

Tanja Lange

Abstract

The literature sometimes uses slow algorithms to find minimum-length continued-fraction differential addition chains to speed up subsequent computations of multiples of points on elliptic curves. This paper introduces two faster algorithms to find these chains. The first algorithm prunes more effectively than previous algorithms. The second algorithm uses a meet-in-the-middle approach and appears to have a limiting cost exponent below 1.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. ANTS XVI
Contact author(s): authorcontact-dacmitm-djb @ box cr yp to
jolijncottaar @ gmail com
tanja @ hyperelliptic org
History: 2024-06-28: approved; 2024-06-27: received; See all versions
Short URL: https://ia.cr/2024/1044
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1044,
      author = {Daniel J. Bernstein and Jolijn Cottaar and Tanja Lange},
      title = {Searching for differential addition chains},
      howpublished = {Cryptology ePrint Archive, Paper 2024/1044},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/1044}},
      url = {https://eprint.iacr.org/2024/1044}
}