On polynomial interpolations related to Verheul homomorphisms
Takakazu Satoh
Abstract: The Verheul homomorphism is a group homomorphism from a finite
subgroup of the multiplicative group of a field to an elliptic
curve. The hardness of computation of the Verheul homomorphism was
shown by Verheul to be closely related to the hardness of the
computational Diffie–Hellman problem. Let p ≥ 5
be a prime, and let N be a prime satisfying
√(12p) < N < 2p / √3, where N
≠ p. Let E be an ordinary elliptic curve over
Fp, and let C ⊂ E be a
cyclic subgroup of order N. Let H be the group of
all Nth roots of unity (contained in the algebraic closure
of Fp ), and let phi be the Verheul
isomorphism from H to C.
We consider a polynomial
P such that P(z) is the X-coordinate
of phi(z) for all z ∈ H – {1}. We
show that, for at least approximately 58% of pairs (E, C),
none of the coefficients of the non-constant terms of P
vanishes.
|
