Tightest Lower Bound for the Elliptic Curve Diffie-Hellman Problem and New Attacks on the Discrete Logarithm Problem

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.