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$.

  • 1
    $\begingroup$ 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$. $\endgroup$
    – lamontap
    Mar 22 at 19:58
  • $\begingroup$ The problem appears related to the notion of hard-core predicate. A quick search reveals many papers that may contain answers. $\endgroup$
    – lamontap
    Mar 22 at 20:02
  • $\begingroup$ @lamontap Is this true for LSB as well? $\endgroup$
    – Turbo
    Mar 22 at 20:44
  • 1
    $\begingroup$ 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. $\endgroup$
    – lamontap
    Mar 25 at 15:47


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.