Paper 2024/1985

Endomorphisms for Faster Cryptography on Elliptic Curves of Moderate CM Discriminants

Abstract

This article generalizes the widely-used GLV decomposition for scalar multiplication to a broader range of elliptic curves with moderate CM discriminant \( D < 0 \) (up to a few thousand in absolute value). Previously, it was commonly believed that this technique could only be applied efficiently for small \( D \) values (e.g., up to \( 100 \)). In practice, curves with \( j \)-invariant \( 0 \) are most frequently employed, as they have the smallest possible \( D = -3 \). This article participates in the decade-long development of numerous real-world curves with moderate \( D \) in the context of ZK-SNARKs. Such curves are typically derived from others, which limits the ability to generate them while controlling the magnitude of \( D \). The most notable example is so-called "lollipop" curves demanded, among others, in the Mina protocol. Additionally, the new results are relevant to one of the "classical" curves (with \( D = -619 \)) from the Russian ECC standard. This curve was likely found using the CM method (with overwhelming probability), though this is not explicitly stated in the standard. Its developers seemingly sought to avoid curves with small \( D \) values, aiming to mitigate potential DLP attacks on such curves, and hoped these attacks would not extend effectively to \( D = -619 \). One goal of the present article is to address the perceived disparity between the \( D = -3 \) curves and the Russian curve. Specifically, the Russian curve should either be excluded from the standard for potential security reasons or local software should begin leveraging the advantages of the GLV decomposition.