Paper 2025/1751

On the Existence and Construction of Very Strong Elliptic Curves

Abstract

This paper introduces new, stringent security notions for elliptic curves. We define two new classes of strong elliptic curves, which offer resilience against a broader range of known attacks, including those leveraging the twist. To construct curves satisfying these exceptional criteria, we developed a highly scalable, parallel framework based on the complex multiplication method. Our approach efficiently navigates the vast parameter space defined by safe primes and fundamental discriminants. The core of our method is the efficient scanning algorithm that postpones expensive curve construction until after orders are confirmed to meet our security definitions, enabling significant search efficiency. As a concrete demonstration of our definitions and techniques, we conducted a large-scale computational experiment. This resulted in the first known construction of $91$ very strong 256-bit curves with extreme twist orders (i.e., where the curve order is a safe prime and the twist order is prime) and cofactors $u=1$ along with $4$ such 512-bit curves meeting the extreme twist order criteria. Among these, one 512-bit curve has both its order (a safe prime) and its twist order being prime, while the other three have a small cofactor ($u=7$) but their twist orders are primes. All curves are defined over finite fields whose orders are safe primes. These results not only prove the existence of these cryptographically superior curves but also provide a viable path for their systematic generation, shifting the paradigm from constructing curves faster to constructing curves that are fundamentally stronger.