Cryptography Reference
In-Depth Information
6.5.8 Final Remarks on the Discrete Logarithm Problem
We have given an overview of the most important algorithms to solve the discrete
logarithmproblem. This problemappears to be difficult and hence is a good source for
building cryptographic algorithms. Some conclusions from the preceding discussion
can be summarized as follows:
1. There are two broad classes of algorithms for solving theDL problem: the generic
algorithms whichwork in any cyclic group and the algorithms for specific groups.
The former are exponential while the index calculus algorithms for the cyclic
(sub)groups of finite fields are subexponential.
2. The index calculus algorithms have running times similar to the subexponential
factoring algorithms and hence the cryptographic schemes based on the DL
problem over finite fields do not have any substantial advantage over schemes
based on the difficulty of the integer factorization problem. This fact led to the
search for other groups where only generic algorithms were applicable.
3. The elliptic curve groups that we study in Chap.
11
are the best example of groups
where only generic algorithms are known for the DL problem. There are specific
classes of elliptic curves where the index calculus method can be applied but
this is not the case in general and the greater difficulty of the DL problem in this
setting makes it possible to use smaller keys.
4. Similarly to the schemes based on the difficulty of factoring integers, all the
DL-based cryptographic schemes, including those that use elliptic curve groups,
will be broken if functional quantum computers are built, since they can solve
the DL problem in polynomial time. We refer to [22] for a detailed examination
of the impact of quantum computers in cryptography.
