With the continued proliferation of computer technology in all aspects of our society it is important to develop means to ensure the secrecy and integrity of information exchanged over computer networks. This task has taken on an added urgency with the on-going implementation of the information super-highway. Cryptography, and in particular public-key cryptography, is concerned with all aspects of preserving the integrity of information including confidentiality, authentication, digital signatures (non-repudiation) and identification.
In 1976, Whit Diffie and Martin Hellman invented the notion of public-key cryptography. Since then numerous public-key cryptosystems were proposed whose security depends on the difficulty of the discrete logarithm problem in a finite group. Among this family of discrete-log cryptosystems are the Diffie-Hellman key exchange, the ElGamal public-key encryption and digital signature schemes, and the Digital Signature Standard recently introduced by the National Institute for Science and Technology in the USA.
An efficient method for computing discrete logarithms would render all such schemes insecure. While the discrete logarithm problem is widely believed to be computationally intractable, a proof to this effect is neither known nor thought to be forthcoming. Before wide-scale usage, it is thus imperative that an intensive investigation of the true complexity of the problem be undertaken in order to obtain a high degree of confidence in the security of discrete-log cryptosystems. Such an investigation is in progress by various researchers around the world.
The subjects of group theory, finite field theory and algebraic number theory have been intensively studied for several centuries, and their study remains very active today. Originally pursued mainly for purely aesthetic reasons, they have recently proved useful in several important applications, among them public-key cryptography.
Briefly, if G is a finite group, the discrete logarithm problem in G
is the following computational problem: given elements 
and 
in G, determine an integer x such that 
, provided
that such an integer exists.
The groups usually considered for practical usage are the multiplicative group
of a finite field, and the group of rational points on an elliptic curve defined
over a finite field.
Up until the mid 1970's, the best algorithm known for the discrete logarithm problem was the giant-step baby-step method, which is exponential in both time and space. The first sub-exponential time algorithm for the discrete logarithm in finite fields was developed by Len Adleman in 1979. This algorithm has since been further studied and refined, using increasingly more sophisticated techniques from algorithmic number theory and algebraic number theory.
The discrete logarithm problem, apart from having applications to cryptography, is of fundamental significance in mathematics and algorithmic number theory. Research in the theory and implementation of algorithms for the problem can be expected to significantly advance the state of our knowledge on the structure and arithmetic of finite fields, computing in algebraic number fields, distributed computing, and parallel computing.
For an introduction to cryptography and an illustration of the role of the discrete logarithm problem, consult D.R. Stinson, Cryptography: Theory and Practice, CRC Press, 1995, and G. Simmons (editor), Contemporary Cryptology: The Science of Information Integrity, IEEE Press, 1991.
Thu Sep 28 16:04:38 CDT 1995