Abstract: In many cryptographic applications it is
necessary to generate elliptic curves (ECs) whose order
possesses certain properties. The method that is usually
employed for the generation of such ECs is the
so-called Complex Multiplication method. This method
requires the use of the roots of certain classfield polynomials
defined on a specific parameter called the discriminant.
The most commonly used polynomials are
the Hilbert and Weber ones. The former can be used
to generate directly the EC, but they are characterized
by high computational demands. The latter have usually
much lower computational requirements, but they
do not directly construct the desired EC. This can be
achieved if transformations of their roots to the roots of the corresponding (generated by the same discriminant)
Hilbert polynomials are provided. In this paper we present
a variant of the Complex Multiplicationmethod that
generates ECs of cryptographically strong order. Our
variant is based on the computation of Weber polynomials.
We present in a simple and unifying manner a
complete set of transformations of the roots of aWeber
polynomial to the roots of its corresponding Hilbert
polynomial for all values of the discriminant. In addition,
we prove a theoretical estimate of the precision required
for the computation ofWeber polynomials for all values
of the discriminant.We present an extensive experimental
assessment of the computational efficiency of the
Hilbert and Weber polynomials along with their precision
requirements for various discriminant values and
we compare them with the theoretical estimates.We further
investigate the time efficiency of the new Complex
Multiplication variant under different implementations
of a crucial step of the variant. Our results can serve as
useful guidelines to potential implementers of EC cryptosystems
involving generation of ECs of a desirable
order on resource limited hardware devices or in systems
operating under strict timing response constraints
Abstract: We consider the generation of prime order elliptic curves
(ECs) over a prime field Fp using the Complex Multiplication (CM)
method. A crucial step of this method is to compute the roots of a special
type of classfield polynomials with the most commonly used being the
Hilbert and Weber ones, uniquely determined by the CM discriminant
D. In attempting to construct prime order ECs using Weber polynomials
two difficulties arise (in addition to the necessary transformations of the
roots of such polynomials to those of their Hilbert counterparts). The
first one is that the requirement of prime order necessitates that D ≡ 3
(mod 8), which gives Weber polynomials with degree three times larger
than the degree of their corresponding Hilbert polynomials (a fact that
could affect efficiency). The second difficulty is that these Weber polynomials
do not have roots in Fp. In this paper we show how to overcome
the above difficulties and provide efficient methods for generating ECs of
prime order supported by a thorough experimental study. In particular,
we show that such Weber polynomials have roots in F
p3 and present a
set of transformations for mapping roots of Weber polynomials in F
p3
to roots of their corresponding Hilbert polynomials in Fp. We also show
how a new class of polynomials, with degree equal to their corresponding
Hilbert counterparts (and hence having roots in Fp), can be used
in the CM method to generate prime order ECs. Finally, we compare
experimentally the efficiency of using this new class against the use of
the aforementioned Weber polynomials.
Keywords: Elliptic Curve Cryptosystems,
Abstract: We consider the generation of prime-order elliptic curves (ECs) over a prime field $\mathbb{F}_{p}$ using the Complex Multiplication (CM) method. A crucial step of this method is to compute the roots of a special type of classfield polynomials with the most commonly used being the Hilbert and Weber ones. These polynomials are uniquely determined by the CM discriminant D. In this paper, we consider a variant of the CM method for constructing elliptic curves (ECs) of prime order using Weber polynomials. In attempting to construct prime-order ECs using Weber polynomials, two difficulties arise (in addition to the necessary transformations of the roots of such polynomials to those of their Hilbert counterparts). The first one is that the requirement of prime order necessitates that D≡3mod8), which gives Weber polynomials with degree three times larger than the degree of their corresponding Hilbert polynomials (a fact that could affect efficiency). The second difficulty is that these Weber polynomials do not have roots in $\mathbb{F}_{p}$ .
In this work, we show how to overcome the above difficulties and provide efficient methods for generating ECs of prime order focusing on their support by a thorough experimental study. In particular, we show that such Weber polynomials have roots in the extension field $\mathbb{F}_{p^{3}}$ and present a set of transformations for mapping roots of Weber polynomials in $\mathbb{F}_{p^{3}}$ to roots of their corresponding Hilbert polynomials in $\mathbb{F}_{p}$ . We also show how an alternative class of polynomials, with degree equal to their corresponding Hilbert counterparts (and hence having roots in $\mathbb{F}_{p}$ ), can be used in the CM method to generate prime-order ECs. We conduct an extensive experimental study comparing the efficiency of using this alternative class against the use of the aforementioned Weber polynomials. Finally, we investigate the time efficiency of the CM variant under four different implementations of a crucial step of the variant and demonstrate the superiority of two of them.
