Discrete Logarithm - Cryptography

Cryptography

There exist groups for which computing discrete logarithms is apparently difficult. In some cases (e.g. large prime order subgroups of groups (Z_p)×) there is not only no efficient algorithm known for the worst case, but the average-case complexity can be shown to be about as hard as the worst case using random self-reducibility.

At the same time, the inverse problem of discrete exponentiation is not difficult (it can be computed efficiently using exponentiation by squaring, for example). This asymmetry is analogous to the one between integer factorization and integer multiplication. Both asymmetries have been exploited in the construction of cryptographic systems.

Popular choices for the group G in discrete logarithm cryptography are the cyclic groups (Z_p)×; see ElGamal encryption, Diffie–Hellman key exchange, and the Digital Signature Algorithm.

Newer cryptography applications use discrete logarithms in cyclic subgroups of elliptic curves over finite fields; see elliptic curve cryptography.