Abstract:
The elliptic curve discrete logarithm problem(ECDLP) is one of the most
widely used primitives in various public key cryptosystems. Hardness of
ECDLP is an absolute security necessity, but not sufficient, for these cryptosystems
and the actual security depends on the elliptic curve Diffie-Hellman
problem(ECDHP). Hence, it is imperative to study hardness of ECDLP as
well as of ECDHP on the elliptic curve parameters recommended for practical
implementations. Our work contributes in both the directions. We have
given the tightest lower bound for ECDHP on the elliptic curve parameters
most widely used in practical applications. These lower bounds ensure the
security of all those protocols which rely on ECDHP for their security. We
also present a novel generic algorithm which uses the multiplicative group
of a finite field as auxiliary group probably for the first time. Our algorithm
also indicates some security issues in NIST curves which are used for USA
federal government for extremely secure communications.
