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 class field 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 Weberpolynomials.
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 ofWeberpolynomials for all values
of the discriminant.We present an extensive experimental
assessment of the computational efficiency of the
Hilbert and Weberpolynomials 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 class field 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 Weberpolynomials
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 Weberpolynomials 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 Weberpolynomials
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 Weberpolynomials have roots in F
p3 and present a
set of transformations for mapping roots of Weberpolynomials 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 Weberpolynomials.
Keywords: Elliptic Curve Cryptosystems,
Abstract: We consider a variant of the Complex Multiplication (CM)
method for constructing elliptic curves (ECs) of prime order with additional
security properties. Our variant uses Weberpolynomials whose
discriminant D is congruent to 3 (mod 8), and is based on a new transformation
for converting roots of Weberpolynomials to their Hilbert
counterparts. We also present a new theoretical estimate of the bit precision
required for the construction of the Weberpolynomials for these
values of D. We conduct a comparative experimental study investigating
the time and bit precision of using Weberpolynomials against the (typical)
use of Hilbert polynomials. We further investigate the time efficiency
of the new CM variant under four different implementations of a crucial
step of the variant and demonstrate the superiority of two of them.
Abstract: We present a variant of the complex multiplication method
that generates elliptic curves of cryptographically strong order. Our variant
is based on the computation ofWeberpolynomials that require significantly
less time and space resources than their Hilbert counterparts. We
investigate the time efficiency and precision requirements for generating
off-line Weberpolynomials and its comparison to another variant based
on the off-line generation of Hilbert polynomials. We also investigate the
efficiency of our variant when the computation of Weberpolynomials
should be made on-line due to limitations in resources (e.g., hardware
devices of limited space).We present trade-offs that could be useful to potential
implementors of elliptic curve cryptosystems on resource-limited
hardware devices.
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 class field 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 Weberpolynomials. In attempting to construct prime-order ECs using Weberpolynomials, 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 Weberpolynomials 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 Weberpolynomials 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 Weberpolynomials have roots in the extension field $\mathbb{F}_{p^{3}}$ and present a set of transformations for mapping roots of Weberpolynomials 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 Weberpolynomials. 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.
Abstract: In many cryptographic applications it is necessary to generate
elliptic curves (ECs) with certain security properties. These curves
are commonly constructed using the Complex Multiplication method
which typically uses the roots of Hilbert or Weberpolynomials. The former
generate the EC directly, but have high computational demands,
while the latter are faster to construct but they do not lead, directly, to
the desired EC. In this paper we present in a simple and unifying manner
a complete set of transformations of the roots of a Weber polynomial to
the roots of its corresponding Hilbert polynomial for all discriminant values
on which they are defined. Moreover, we prove a theoretical estimate
of the precision required for the computation of Weberpolynomials. Finally,
we experimentally assess the computational efficiency of theWeberpolynomials along with their precision requirements for various discriminant
values and compare the results with the theoretical estimates. Our
experimental results may be used as a guide for the selection of the most
efficient curves in applications residing in resource limited devices such as
smart cards that support secure and efficient Public Key Infrastructure
(PKI) services.
