A note on \((2, 2)\)-isogenies via theta coordinates (Q6615553)

Isogeny-based cryptography is a promising candidate for post-quantum cryptography. The computation of chains of \((2,2)\)-isogenies between products of elliptic curves forms the core of many isogeny-based protocols.\N\NThis paper presents several techniques to optimize \((2,2)\)-isogeny computation. Specifically, the algorithm proposed by \textit{P. Dartois} et al. [``An algorithmic approach to \((2, 2)\)-isogenies in the theta model and applications to isogeny-based cryptography'', Cryptology ePrint Archive, Paper 2023/1747 (2023)], which computes chains of \((2,2)\)-isogenies between products of elliptic curves using theta coordinates, is revisited and enhanced. By employing projective coordinates, the proposed method eliminates all inversions, resulting in more efficient algorithms for \((2,2)\)-isogeny computations, including gluing and generic isogenies, compared to previous approaches.\N\NFor each fundamental block of the algorithm, an explicit inversion-free version is provided. The \(x\)-only ladder technique is applied to accelerate the computation of gluing isogenies. Additionally, a mixed optimal strategy is introduced, combining inversion-elimination techniques with the original methods to execute chains of \((2,2)\)-isogenies efficiently.\N\NFor the point doublings, in the gluing isogeny step, the \(x\)-only Montgomery ladder algorithm is used to compute the \(x\)-coordinates of target points, while the corresponding \(y\)-coordinates are recovered using the Okeya-Skurai formula. A detailed cost analysis and a concrete comparison with previously known inversion-elimination methods are also provided.