A key distribution system is a system in which users securely generate a common key. One kind of identity-based key distribution system was proposed by E. Okamoto[1]. Its security depends on the difficulty of factoring a composite number of two large primes like RSA public-key cryptosystem. Another kind of identity-based key distribution system was proposed by K. Nyberg, R.A. Rueppel[7]. Its security depends on the difficulty of the discrete logarithm problem.
On the other hand, Koblitz and Miller described how a group of points on an elliptic curve over a finite field can be used to construct a public key cryptosystem.
In 1997, we proposed an ID-based key distribution system over an elliptic curve[14], as well as over a ring Z/nZ. Its security depends on the difficulty of factoring a composite number of two large primes. We showed that the system is more suitable for the implementation on an elliptic curve than on a ring Z/nZ[14].
In this paper, we apply the Nyberg-Rueppel ID-based key distribution system[7] to an elliptic curve. It provides relatively small block size and high security. This public key scheme can be efficiently implemented. However the scheme[7] requires relatively large data transmission. As a solution to this problem, we improve the scheme. The improved scheme is very efficient since the data transferred for generation of a common key is reduced to half of the previous one.