International Association
for Cryptologic Research

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 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\cM + 4\cS+3\cm_0$, compared to $10\cM+9\cS+6\cm_0$ for the standard ladder.

<p> We use theta groups to study $2$-isogenies between Kummer lines, with a particular focus on the Montgomery model. This allows us to recover known formulas, along with more efficient forms for translated isogenies, which require only $2S+2m_0$ for evaluation. We leverage these translated isogenies to build a hybrid ladder for scalar multiplication on Montgomery curves with rational $2$-torsion, which cost $3M+6S+2m_0$ per bit, compared to $5M+4S+1m_0$ for the standard Montgomery ladder. </p>