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

  • 2
    $\begingroup$ 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 iacr.org/archive/crypto2004/31520273/bp.pdf $\endgroup$ – Daniel Apon Mar 31 '14 at 21:01
  • 2
    $\begingroup$ "such that $(g^a)^t,(g^{ab})^t$" are what? $\;$ $\endgroup$ – user6973 Apr 1 '14 at 1:31
  • $\begingroup$ thanks, I made a few changes, does it make more sense now? please let me know if some part is still unclear $\endgroup$ – Subhayan Apr 1 '14 at 8:41
  • 1
    $\begingroup$ The problem is still not hard. $\:$ Given $g,g^a,g^{ab}$, output $g^0,g^0$. $\:$ That is of the form specified in the problem (consider $r=0$). $\:$ If "no clue about the value of the exponent" matters, then why isn't $r$ part of the output? $\;\;\;\;$ $\endgroup$ – user6973 Apr 1 '14 at 15:18
  • $\begingroup$ @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? $\endgroup$ – Subhayan Apr 1 '14 at 15:54

Your problem is equivalent to the CONF problem.

$g^b \; = \; g^{\hspace{.02 in}b\cdot 1} \; = \; g^{\hspace{.02 in}b\cdot r\cdot \operatorname{modinv}(r\hspace{-0.02 in},\hspace{.02 in}p)} \; = \; \left(g^{\hspace{.02 in}b\cdot r}\hspace{-0.03 in}\right)^{\hspace{-0.02 in}\operatorname{modinv}(r\hspace{-0.02 in},\hspace{.02 in}p)} \; = \; \left(g^{br}\hspace{-0.03 in}\right)^{\hspace{-0.02 in}\operatorname{modinv}(r\hspace{-0.02 in},\hspace{.02 in}p)} \; = \; \left(g^{rb}\hspace{-0.03 in}\right)^{\hspace{-0.02 in}\operatorname{modinv}(r\hspace{-0.02 in},\hspace{.02 in}p)}$

One can find an suitable output for your problem by chossing $\: r=2 \:$ or $\: r=1$
according to whether $\: g^a = g \:$ or $\: g^a \neq g \:$, $\:$ and then outputting $\:r,g^r\hspace{-0.02 in},\left(g^b\right)^r\;$.

  • $\begingroup$ this is embarrassing.. I think i am missing something, but we don't know $g^b$, .. so i think what this proof implies is if we could solve the CONF we can solve this problem.. but shouldn't there be another proof to say the other way (then we can say surely our problem is hard) $\endgroup$ – Subhayan Apr 1 '14 at 17:35
  • $\begingroup$ $g^b \; = \; \left(g^{rb}\hspace{-0.03 in}\right)^{\hspace{-0.02 in}\operatorname{modinv}(r\hspace{-0.02 in},\hspace{.02 in}p)} \;\;$. $\;\;\;\;$ Therefore if we can solve this problem then $\hspace{1.72 in}$ we can solve the CONF problem. $\;\;\;\;\;\;\;\;$ $\endgroup$ – user6973 Apr 1 '14 at 17:45
  • $\begingroup$ hahahaha.... YES OF COURSE.. i must be some special kind of stupid.. i JUST figured it out myself too!! $\endgroup$ – Subhayan Apr 1 '14 at 17:59

Here, I cranked out the black box optimum 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}$.

  • $\begingroup$ 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? $\endgroup$ – Subhayan Apr 1 '14 at 17:41
  • $\begingroup$ Here, en.wikipedia.org/wiki/Addition-chain_exponentiation . The OEIS sequence is oeis.org/A003313 with many references. $\endgroup$ – Chad Brewbaker Apr 1 '14 at 18:10

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

  • $\begingroup$ sorry it was not clear from earlier that $r \neq a$, anyway i made some changes, please take a look at that. $\endgroup$ – Subhayan Apr 1 '14 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.