We study differential additions formulas on Kummer lines that factorize through a degree 2 isogeny \(\varphi \) . We call the resulting formulas half differential additions: from the knowledge of \(\varphi (P), \varphi (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=\varphi _i(P_{i-1})\) , which only depends on the base point P and not the scalar n, for a pre-computation cost of \(2\textbf{S}+1\textbf{m}_0\) by bit. Then we use half doublings and half differential additions to compute any scalar multiplication \(n \cdot P\) , for a cost of \(4\textbf{M}+2\textbf{S}+1\textbf{m}_0\) by bit. The total cost is then \(4 \textbf{M}+ 4 \textbf{S}+ 2\textbf{m}_0\) , even when the base point P is not normalized. By contrast, the usual Montgomery ladder costs \(4\textbf{M}+ 4\textbf{S}+ 1\textbf{m}+ 1\textbf{m}_0\) by bit, for a normalized point. In the long version of the paper, we extend our approach to higher dimensional ladders in theta coordinates or twisted theta coordinates. In dimension 2, after a precomputation step which depends on the base point P, our half ladder only costs \(7\textbf{M}+ 4\textbf{S}+3\textbf{m}_0\) , compared to \(10\textbf{M}+9\textbf{S}+6\textbf{m}_0\) for the standard ladder.

Halving Differential Additions on Kummer Lines

会议论文
发表日期：

2025年

查看全文

Damien Robert,
Nicolas Sarkis

摘要

We study differential additions formulas on Kummer lines that factorize through a degree 2 isogeny \(\varphi \) . We call the resulting formulas half differential additions: from the knowledge of \(\varphi (P), \varphi (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=\varphi _i(P_{i-1})\) , which only depends on the base point P and not the scalar n, for a pre-computation cost of \(2\textbf{S}+1\textbf{m}_0\) by bit. Then we use half doublings and half differential additions to compute any scalar multiplication \(n \cdot P\) , for a cost of \(4\textbf{M}+2\textbf{S}+1\textbf{m}_0\) by bit. The total cost is then \(4 \textbf{M}+ 4 \textbf{S}+ 2\textbf{m}_0\) , even when the base point P is not normalized. By contrast, the usual Montgomery ladder costs \(4\textbf{M}+ 4\textbf{S}+ 1\textbf{m}+ 1\textbf{m}_0\) by bit, for a normalized point. In the long version of the paper, we extend our approach to higher dimensional ladders in theta coordinates or twisted theta coordinates. In dimension 2, after a precomputation step which depends on the base point P, our half ladder only costs \(7\textbf{M}+ 4\textbf{S}+3\textbf{m}_0\) , compared to \(10\textbf{M}+9\textbf{S}+6\textbf{m}_0\) for the standard ladder.