<p>Here, I cranked out the <a href="https://oeis.org/A186202" rel="nofollow">black box optimum</a> to detect any subgroup of $S_{n}$, still exponential but much faster than brute force over all $n!$ permutations.</p>

<p>Your problem is around $O(n  \log  rb)$ with repeated doubling if you have $g$ given to you as a permutation in $S_{n}$.</p>

CC BY-SA 3.0
2014-04-01T17:41:22.227Z
thanks a lot @Chad Brewbaker, this is great :) .. but I am actually looking for a proof of its hardness .. so what i need is something that at least says your algo is optimal.. do you think you might be able to come up with something on that?
Subhayan
CC BY-SA 3.0
2014-04-01T18:10:50.607Z
Here, http://en.wikipedia.org/wiki/Addition-chain_exponentiation . The OEIS sequence is https://oeis.org/A003313 with many references.
Chad Brewbaker
CC BY-SA 3.0
2014-04-01T16:11:01.763Z
2014-04-01T16:11:01.763Z
Chad Brewbaker
<p>The problem you listed in the first sentence of your question does not seem to be hard.  Given $g,g^a,g^{ab}$, I output $g^a,g^{ab}$.  That is of the form you desired (consider $r=a$), so I have shown that what you are trying to prove is not true.  If that's not a break of your hardness assumption, please edit your question to make the question a whole lot clearer.</p>

<p>(I don't know what's going on in the last sentence of your question or what that is trying to say.  I'm ignoring that for now since it is not clear to me what it means.  If that is essential, please make a major edit to your question to make it much clearer what problem you are trying to solve.)</p>

CC BY-SA 3.0
2014-04-01T13:24:51.533Z
sorry it was not clear from earlier that $r \neq a$, anyway i made some changes, please take a look at that.
Subhayan
CC BY-SA 3.0
2014-04-01T02:19:06.693Z
2014-04-01T02:19:06.693Z
D.W.
<p>I am trying to prove the following</p>

<blockquote>
  <p>Given $g, g^a, g^{ab}$ it is hard to compute $r, g^r, g^{rb}$, for some arbitrarily chosen value of $r$ </p>
</blockquote>

<p>where $g ∈ \mathbb{G}, \mathbb{G}$ is a cyclic group of prime order $p$ and $r∈ \mathbb{Z}^*_p -\{0\} $ and $r \neq a$.</p>

<p>I don't have a clear (far from elegant) proof that, if there exists an algorithm $\mathcal{A}$ that can solve this, then we can solve *some*  hard problem..</p>

<p>The best sketch I can think of is reducing this to a the Okamato's Conference Key Sharing Scheme. However, again, I don't have a clear proof idea here...</p>

<p>Also, I argue, the adversary can submit the following,$(g^a)^t, (g^{ab})^t$,  $t∈_R Z$, however in that case, the adversary has no clue about the value of the exponent</p>

CC BY-SA 3.0
2014-03-31T21:01:34.373Z
This sounds a lot like a knowledge-of-exponent assumption. Try taking a look at KEA2 (which is false) and KEA3 (the conjectured fix) from https://www.iacr.org/archive/crypto2004/31520273/bp.pdf
Daniel Apon
CC BY-SA 3.0
2014-04-01T08:41:42.150Z
thanks, I made a few changes, does it make more sense now? please let me know if some part is still unclear
Subhayan
CC BY-SA 3.0
2014-04-01T15:54:43.400Z
@RickyDemer good point,thanks, i did not post the question very formally.. let's see if we can fix that now.. I made a small edit, so does this make more sense now?
Subhayan
CC BY-SA 3.0
2014-04-01T16:00:11.550Z
to think about it, we can have $a$ in the set as well.. not a problem, but then $a$ must be in the output, that's just the general CONF scheme, right?
Subhayan
CC BY-SA 3.0
2014-04-01T16:01:52.953Z
but i should update it as $\mathbb{Z}_p^*$ - {0} ... we could accept a negative value of $r$
Subhayan
CC BY-SA 3.0
2014-04-01T16:05:22.887Z
oh.. i'll just tell you.. the CONF problem says given $g, g^a, g^{ab}$ it is hard to compute $g^b$ (This was given by Okamato '88, also known as Okamato's CONFerence key sharing scheme)
Subhayan
CC BY-SA 3.0
2014-04-01T16:07:25.417Z
$p$ is the order of the group, of course it is known..
Subhayan
<cr.crypto-security><reductions><gr.group-theory>
On proving it is hard to compute $g^{rb}$ with knowledge of $r$, given $g, g^a, g^{ab}$
Subhayan
# On proving it is hard to compute $g^{rb}$ with knowledge of $r$, given $g, g^a, g^{ab}$

(Asked by: username_0 on 2014-03-31)

I am trying to prove the following

> Given $g, g^a, g^{ab}$ it is hard to compute $r, g^r, g^{rb}$, for some arbitrarily chosen value of $r$

where $g ∈ \mathbb{G}, \mathbb{G}$ is a cyclic group of prime order $p$ and $r∈ \mathbb{Z}^\*\_p -\{0\} $ and $r \neq a$.

I don't have a clear (far from elegant) proof that, if there exists an algorithm $\mathcal{A}$ that can solve this, then we can solve \*some\* hard problem..

The best sketch I can think of is reducing this to a the Okamato's Conference Key Sharing Scheme. However, again, I don't have a clear proof idea here...

Also, I argue, the adversary can submit the following,$(g^a)^t, (g^{ab})^t$, $t∈\_R Z$, however in that case, the adversary has no clue about the value of the exponent

**Tags:** cr.crypto-security, reductions, gr.group-theory
> **Comments:**
> **username_1**: This sounds a lot like a knowledge-of-exponent assumption. Try taking a look at KEA2 (which is false) and KEA3 (the conjectured fix) from https://www.iacr.org/archive/crypto2004/31520273/bp.pdf  
> **username_0**: thanks, I made a few changes, does it make more sense now? please let me know if some part is still unclear  
> **username_0**: @RickyDemer good point,thanks, i did not post the question very formally.. let's see if we can fix that now.. I made a small edit, so does this make more sense now?  
> **username_0**: to think about it, we can have $a$ in the set as well.. not a problem, but then $a$ must be in the output, that's just the general CONF scheme, right?  
> **username_0**: but i should update it as $\mathbb{Z}_p^*$ - {0} ... we could accept a negative value of $r$  
> **username_0**: oh.. i'll just tell you.. the CONF problem says given $g, g^a, g^{ab}$ it is hard to compute $g^b$ (This was given by Okamato '88, also known as Okamato's CONFerence key sharing scheme)  
> **username_0**: $p$ is the order of the group, of course it is known..  

---

## 2 answers

### Answer by username_2 on 2014-04-01. Score: 2

Here, I cranked out the [black box optimum](https://oeis.org/A186202) to detect any subgroup of $S\_{n}$, still exponential but much faster than brute force over all $n!$ permutations.

Your problem is around $O(n \log rb)$ with repeated doubling if you have $g$ given to you as a permutation in $S\_{n}$.

> **Comments:**
> **username_0**: thanks a lot @Chad Brewbaker, this is great :) .. but I am actually looking for a proof of its hardness .. so what i need is something that at least says your algo is optimal.. do you think you might be able to come up with something on that?  
> **username_2**: Here, http://en.wikipedia.org/wiki/Addition-chain_exponentiation . The OEIS sequence is https://oeis.org/A003313 with many references.  

---

### Answer by username_3 on 2014-04-01. Score: 1

The problem you listed in the first sentence of your question does not seem to be hard. Given $g,g^a,g^{ab}$, I output $g^a,g^{ab}$. That is of the form you desired (consider $r=a$), so I have shown that what you are trying to prove is not true. If that's not a break of your hardness assumption, please edit your question to make the question a whole lot clearer.

(I don't know what's going on in the last sentence of your question or what that is trying to say. I'm ignoring that for now since it is not clear to me what it means. If that is essential, please make a major edit to your question to make it much clearer what problem you are trying to solve.)

> **Comments:**
> **username_0**: sorry it was not clear from earlier that $r \neq a$, anyway i made some changes, please take a look at that.  

---

