Abstract
This paper presents the first explicit formulas for counting the number of distinct isomorphism classes of elliptic curves within the Doche-Icart-Kohel (DIK) "tripling-oriented" and "doubling-oriented" families. By employing techniques from algebraic geometry to partition parameter spaces and linking these counts to the number of rational points on auxiliary curves, the authors provide a rigorous framework for assessing the variety of these cryptographically significant curves. The results demonstrate that DIK families offer a sufficiently large number of unique curves to remain viable for secure Elliptic Curve Cryptography (ECC) implementations.
Introduction
In the domain of Elliptic Curve Cryptography (ECC), the efficiency of scalar multiplication—specifically point doubling and tripling—is a primary driver for performance. To this end, specialized curve models like the Doche-Icart-Kohel (DIK) curves have been proposed to accelerate these fundamental operations. However, the cryptographic utility of any specialized family depends on its "richness": the number of distinct isomorphism classes it contains over a given finite field $\mathbb{F}_q$.
While previous research established counts for $j$-invariants over algebraic closures, such metrics do not account for isomorphism over the specific finite fields used in practice. This paper addresses this gap by providing exact counts for isomorphism classes over $\mathbb{F}_q$, taking into account the nuances of quadratic and cubic twists.
Methodology
The authors' approach centers on the analysis of the rational functions that define the $j$-invariant for each DIK family. The methodology follows a structured progression:
- Parameter Partitioning: The possible values for the curve parameters are divided into disjoint sets based on their algebraic properties, such as the discriminant and quadratic/cubic characters ($\chi_2, \chi_3$).
- Isomorphism Mapping: The authors determine the conditions under which two distinct parameters $u$ and $v$ result in curves that are isomorphic over the field $\mathbb{F}_q$. This is significantly more restrictive than isomorphism over an algebraic closure.
- Reduction to Point Counting: A key innovation of this work is the reduction of the counting problem to finding the number of $\mathbb{F}_q$-rational points on specific "auxiliary" curves. These include the Legendre curve and other higher-genus curves.
As shown in Table 1, the size of the partitioned sets ($\mathcal{A}_i, \mathcal{B}_i$) depends on the field characteristic and the value of $q \pmod{12}$ (represented by $r$). This granular breakdown is essential for deriving the final counting formulas.
Key Results
The paper provides explicit formulas for the number of isomorphism classes in both DIK families, revealing a dependency on the Hasse-Weil bound.
Tripling-Oriented DIK Curves
For the tripling-oriented family, the number of isomorphism classes $I_T(q)$ is approximately:
- $\frac{79}{96}q$ when $q \equiv 1 \pmod 3$
- $\frac{3}{4}q$ when $q \equiv 2 \pmod 3$
The exact formulas are functions of $N_1$ (the number of points on an auxiliary curve $\mathcal{C}$ related to cubic roots of unity) and $N_2$ (the number of points on a Legendre curve).
Doubling-Oriented DIK Curves
For the doubling-oriented family, the number of isomorphism classes $I_D(q)$ is approximately $\frac{19}{24}q$. The precise count depends on the number of points $N$ on the elliptic curve defined by $L: Y^2 = X(X+1)(X+3/4)$.
Discussion and Conclusion
The findings confirm that while DIK curves represent a restricted subset of all possible elliptic curves, they still provide a vast number of isomorphism classes. The dependency on auxiliary curve point counts means that the exact number of classes fluctuates, but it remains well-distributed within the bounds predicted by the Hasse-Weil theorem.
This work provides the necessary theoretical foundation for cryptographers to use DIK curves with confidence, knowing that the available parameter space is not overly constrained. Future work could apply these counting methodologies to other optimized models, such as Edwards or Montgomery curves, and further investigate the security properties of individual curves within these families.
Summary updated