<p>Given generator <span class="math-container">$g$</span> of multiplicative cyclic group modulo <span class="math-container">$p$</span> a prime and two elements <span class="math-container">$h_1$</span> and <span class="math-container">$h_2$</span> such that there are <span class="math-container">$x_1$</span> and <span class="math-container">$x_2$</span> respectively satisfying <span class="math-container">$g^{x_i}=h_i\bmod p$</span> at every <span class="math-container">$i\in\{1,2\}$</span>, the Discrete Logarithm problem is to find <span class="math-container">$x_1$</span> and <span class="math-container">$x_2$</span> while the Diffie Hellman problem is to find <span class="math-container">$g^{x_1x_2}\bmod p$</span>. Both these problems do not have polynomial in <span class="math-container">$\log p$</span> time algorithm.</p>
<p>What is the complexity of LSB and MSB of <span class="math-container">$g^{x_1x_2}\bmod p$</span>? Is it related to or complete in any complexity class? I believe it should be in at most <span class="math-container">$UP$</span>.</p>

CC BY-SA 4.0
2024-03-22T19:58:44.830Z
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$.
lamontap
CC BY-SA 4.0
2024-03-22T20:02:45.867Z
The problem appears related to the notion of hard-core predicate. A quick [search](https://scholar.google.com/scholar?q=Hard%2Dcore%20predicate%20for%20diffie%20hellman&btnG=Search&as_sdt=800000000001&as_sdtp=on) reveals many papers that may contain answers.
lamontap
CC BY-SA 4.0
2024-03-22T20:44:45.353Z
@lamontap Is this true for LSB as well?
Turbo
CC BY-SA 4.0
2024-03-25T15:47:57.273Z
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](https://www.cs.umd.edu/~jkatz/imc.html).
lamontap
<cc.complexity-theory>
Complexity of LSB and MSB of Diffie-Hellman
Turbo
# Complexity of LSB and MSB of Diffie-Hellman

(Asked by: username_0 on 2024-03-22)

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

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: 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$.  
> **username_1**: The problem appears related to the notion of hard-core predicate. A quick [search](https://scholar.google.com/scholar?q=Hard%2Dcore%20predicate%20for%20diffie%20hellman&btnG=Search&as_sdt=800000000001&as_sdtp=on) reveals many papers that may contain answers.  
> **username_0**: @lamontap Is this true for LSB as well?  
> **username_1**: 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](https://www.cs.umd.edu/~jkatz/imc.html).  

---

## 0 answers

