crypt@b-it 2007
Gadiel Seroussi
Elliptic curve cryptography
Elliptic curve (EC) public key cryptosystems were proposed independently in 1985 by Victor Miller and Neal Koblitz, and are considered an efficient and attractive alternative to the more conventional public key cryptosystems (e.g., RSA) in some applications. The security of EC cryptosystems is based on the difficulty of computing discrete logarithms in a suitable chosen subgroup of the group of rational points of an elliptic curve over a finite field. The complexity of the best known algorithms for this problem is exponential in the size of the field elements, as opposed to the sub-exponential complexity of the problems underlying conventional public key cryptography. Due to this complexity gap, EC cryptosystems can use much shorter keys, which in turn translate, in practice, to savings in running time, power consumption, silicon area, etc. In this lecture series, we survey the mathematical and algorithmic issues one faces in the design and implementation of EC cryptosystems. We will also touch on more recent developments in cryptography, where a different application of elliptic curves has enabled a practical implementation of the "identity-based cryptosystems" anticipated by Shamir in the early 80's.