Paper 2024/1985

Endomorphisms for Faster Cryptography on Elliptic Curves of Moderate CM Discriminants

Abstract

This article generalizes the widely-used GLV decomposition for (multi-)scalar multiplication to a much broader range of elliptic curves with moderate CM discriminant $D<0$. Previously, it was commonly believed that this technique can only be applied efficiently for small values of $D$ (e.g., up to $100$). In practice, curves with $j$-invariant $0$ are most frequently employed, as they have the smallest possible $D=-3$. However, $j=0$ curves are either too suspicious for conservative government regulators (e.g., for Russian ones, which prefer $D=-619$) or unavailable under imposed extra restrictions in a series of cryptographic settings. The article thus participates in the decade-long development of numerous curves with moderate $$ 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 $$.