ABSTRACT
The theme of this chapter concerns public-key cryptosystems based on the Discrete Logarithm problem. The first and best-known of these is the ElGamal Cryptosystem. The chapter gives treatments of some other ElGamal-type systems based on finite fields and elliptic curves. The ElGamal Cryptosystem can be implemented in any group where the Discrete Logarithm problem is infeasible. Elliptic curves are described by the set of solutions to certain equations in two variables. Generic algorithms apply to the elliptic curve Discrete Logarithm problem, but there is no known adaptation of the Index calculus algorithm to the setting of elliptic curves. Pairings on elliptic curves were first used in a cryptographic context by Menezes, Okamoto, and Vanstone to assist in solving the Discrete Logarithm problem on certain curves. The chapter introduces two variants of the so-called Diffie-Hellman problems, a computational version and a decision version.
