Abstract
The intent of this paper is to provide a comprehensive overview of the discrete logarithm problem including its properties, its cryptographic significance, the known methods for solving it, and of utmost importance, its individual bit security. The main result of the paper is an elegant proof showing how a perfect oracle on almost any bit of the binary representation of the discrete logarithm can be combined with clever reduction techniques to determine the other bits. This proves that almost all individual bits of the discrete logarithm are hard.
Thesis