Welcome to the resource topic for 2024/1582
Title:
Halving differential additions on Kummer lines
Authors: Damien Robert, Nicolas Sarkis
Abstract:We study differential additions formulas on Kummer lines that factorize through a degree 2 isogeny \phi. We call the resulting formulas half differential additions: from the knowledge of \phi(P), \phi(Q) and P-Q, the half differential addition allows to recover P+Q. We explain how Mumford’s theta group theory allows, in any model of Kummer lines, to find a basis of the half differential relations. This involves studying the dimension 2 isogeny (P, Q) \mapsto (P+Q, P-Q).
We then use the half differential addition formulas to build a new type of Montgomery ladder, called the half-ladder, using a time-memory trade-off. On a Montgomery curve with full rational 2-torsion, our half ladder first build a succession of isogeny images P_i=\phi_i(P_{i-1}), which only depends on the base point P and not the scalar n, for a pre-computation cost of 2S+1m_0 by bit. Then we use half doublings and half differential additions
to compute any scalar multiplication n \cdot P, for a cost of 4M+2S+1m_0 by bit. The total cost is then 4M+4S+2m_0, even when the base point P is not normalized. By contrast, the usual Montgomery ladder costs 4M+4S+1m+1m_0 by bit, for a normalized point.
In the appendix, we extend our approach to higher dimensional ladders in theta coordinates.
ePrint: https://eprint.iacr.org/2024/1582
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .