<p>Let $g$ be a generator of a group of prime order $p$; $a,b ∈_R Z_p^+$</p>

<p>Consider an Algorithm $\mathcal{A}$ which on input $g,g^a,g^{ab}$ outputs $g^{br},r$, for some non zero $r ∈ Z_p$</p>

<p>And an algorithm $\mathcal{B}$ which on the same inputs, $g,g^a,g^{ab}$, outputs $a^{-1}$</p>

<p>Can I claim the algorithms $\mathcal{A} \equiv \mathcal{B}$?</p>

<p>While it's trivial to construct $\mathcal{A}$ using $\mathcal{B}$, can we also construct a $\mathcal{B}$ using $\mathcal{A}$?</p>

CC BY-SA 3.0
2014-04-23T06:50:57.933Z
@RickyDemer thanks, one of the best things I like about you is your love for mathematical rigor :)
Subhayan
CC BY-SA 3.0
2014-04-26T19:17:55.380Z
$g$ can't be a generator of order $p$ if $g \in (\mathbb{Z}/p\mathbb{Z})^*$.  Perhaps you mean $g$ is a generator of prime order $q$, and $r \in \mathbb{Z}/q\mathbb{Z}$?
D.W.
<reductions>
On Equivalence of "gen-CONF" problem and "DH-exp-inv" problem
Subhayan
# On Equivalence of "gen-CONF" problem and "DH-exp-inv" problem

(Asked by: username_0 on 2014-04-21)

Let $g$ be a generator of a group of prime order $p$; $a,b ∈\_R Z\_p^+$

Consider an Algorithm $\mathcal{A}$ which on input $g,g^a,g^{ab}$ outputs $g^{br},r$, for some non zero $r ∈ Z\_p$

And an algorithm $\mathcal{B}$ which on the same inputs, $g,g^a,g^{ab}$, outputs $a^{-1}$

Can I claim the algorithms $\mathcal{A} \equiv \mathcal{B}$?

While it's trivial to construct $\mathcal{A}$ using $\mathcal{B}$, can we also construct a $\mathcal{B}$ using $\mathcal{A}$?

**Tags:** reductions
> **Comments:**
> **username_0**: @RickyDemer thanks, one of the best things I like about you is your love for mathematical rigor :)  
> **username_1**: $g$ can't be a generator of order $p$ if $g \in (\mathbb{Z}/p\mathbb{Z})^*$.  Perhaps you mean $g$ is a generator of prime order $q$, and $r \in \mathbb{Z}/q\mathbb{Z}$?  

---

## 0 answers

