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 \( 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 \).