Welcome to the resource topic for 2025/1751
Title:
On the Existence and Construction of Very Strong Elliptic Curves
Authors: Andrey S. Shchebetov
Abstract:This paper introduces and formalizes new, stringent security notions for elliptic curves, establishing a higher benchmark for cryptographic strength. We define two new classes of secure elliptic curves, which offer resilience against a broader range of known attacks, including those leveraging the curve’s endomorphism ring or the twist’s group structure. To construct curves satisfying these exceptional criteria, we develop 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 an 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 order (i.e., curve order is a safe prime and twist order is prime) and cofactor 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.
ePrint: https://eprint.iacr.org/2025/1751
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .