# Complexity of LSB and MSB of Diffie-Hellman

Given generator $$g$$ of multiplicative cyclic group modulo $$p$$ a prime and two elements $$h_1$$ and $$h_2$$ such that there are $$x_1$$ and $$x_2$$ respectively satisfying $$g^{x_i}=h_i\bmod p$$ at every $$i\in\{1,2\}$$, the Discrete Logarithm problem is to find $$x_1$$ and $$x_2$$ while the Diffie Hellman problem is to find $$g^{x_1x_2}\bmod p$$. Both these problems do not have polynomial in $$\log p$$ time algorithm.

What is the complexity of LSB and MSB of $$g^{x_1x_2}\bmod p$$? Is it related to or complete in any complexity class? I believe it should be in at most $$UP$$.

• This problem is at least as hard as the decisional version of DH which asks to distinguish $g^{x_1x_2}$ from $g^z$ for a random $z$. If you could compute the first bit of $g^{x_1x_2}$, you could distinguish both with probability $\frac 12$. Mar 22 at 19:58
• The problem appears related to the notion of hard-core predicate. A quick search reveals many papers that may contain answers. Mar 22 at 20:02
• @lamontap Is this true for LSB as well? Mar 22 at 20:44
• Yes, this should hold for any bit of $g^{x_1x_2}$. Although note that decisional DH is thought to be easier than computation/search DH in certain groups. For a reference, see Section 9.3.2 of this textbook. Mar 25 at 15:47