On the complexity of the discrete logarithm and Diffie-Hellman problems (Q1827563)

The discrete logarithm problem (DLP): given an element \(a\) in a cyclic group \(G=\langle g\rangle\) of order \(n\) find the unique integer \(x\),\,\, \(0\leq x \leq n-1\) such that \(a = g^x\), is widely believed to be a computationally hard problem. It was proposed as a one-way function for use in public-key cryptography in the foundational paper of \textit{W. Diffie} and \textit{M. E. Hellman} [IEEE Trans. Inf. Theory 22, 644--654 (1976; Zbl 0435.94018)]. In that paper Diffie and Hellman also give a key exchange method related to DLP: two users randomly choose integers \(a,b\in (1,n)\)\,\, and they exchange \(g^a,g^b\). Each of them is then able to compute the common value \(g^{ab}\). The computation of \(g^{ab}\)\, given only \(g^a,g^b\) is called the Diffie-Hellman problem (DHP). Of course if one can solve DLP one can also solve DHP. A connected problem is the decision DHP (DDHP): given \(g^a,g^b,g^c\)\, decide if \(ab\equiv c \bmod n\). In general, DDHP is no harder than DHP and this is no harder than DLP. The object of the present paper is the study of some aspects of these relationships. In Section 2 the authors give an overview of the state of the art of these three and other related problems. Section 3 deals with the computational complexity of these problems in generic cyclic groups. An algorithm is called generic if it works for arbitrary groups, in contrast to algorithms that make use of some particular presentation of the group elements, as is the case in the well-known index-calculus method, which provides an algorithm of subexponential complexity for the DLP in multiplicative groups of finite fields and in Jacobians of hyperelliptic curves of large genus. Section 5 is the core of the paper. The authors first remember a previous result of \textit{D. Boneh} and \textit{R. Venkatesan} [Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes, Proc. CRYPTO `96, Lect. Notes Comput. Sci. 1109, 129--142 (1996)] that shows that it is as hard to compute the \(O(\sqrt n)\) most significant bits of the DHP as it is to compute the whole function. They prove then that if the DDHP is supposed to be hard then computing the two most significant bits of the DHP is also hard. The last section of the paper discusses the open question as to whether there exists a deterministic reduction of DDHP to the problem of computing the two most significant bits of DHP. A large list of references is also provided at the end of the paper.