1
$\begingroup$

From wikipedia, the DDH assumption says，given a cyclic group $G$ of order $q$ with generator $g$, $(g^a, g^b, g^{ab})$ looks like $(g^a, g^b, g^c)$ where $a,b,c$ are randomly and independently chosen from $\mathbb{Z}_q$.

Then what I wonder is, whether $(a,(g^a)^b )$ looks like $(a, g^c)$, where $a,b,c$ are randomly and independently chosen from $\mathbb{Z}_q$? Further, in which kind of group does this `assumption' hold?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ They are even more than computationally indistinguishable: they are identically distributed. $\endgroup$
    – fkraiem
    Jun 2, 2015 at 3:34
  • 1
    $\begingroup$ (The above assumes $q$ is prime and $a\ne 0$, by the way...) $\endgroup$
    – fkraiem
    Jun 2, 2015 at 3:42
  • $\begingroup$ Then can we say $(a, g^{ba}, g^{bc})$ and $(a, g^d, g^e)$ are identically distributed? $\endgroup$
    – phan
    Jun 2, 2015 at 3:44
  • $\begingroup$ Under the same assumptions, yes. $\endgroup$
    – fkraiem
    Jun 2, 2015 at 3:46

1 Answer 1

Reset to default
3
$\begingroup$

Their statistical distance is less than $\: (q\hspace{-0.04 in}-$$\phi$$(q))\hspace{.02 in}/q\:$, $\:$ since

$\:$ if $a$ is relatively prime to $q$ then $(\hspace{.02 in}g^a)^b$ and $g^c$ are
$\:$ each uniformly distributed and independent of $a$
$\;\;\;\;$ and
$\:$ even if $a$ isn't relatively prime to $q$, $(\hspace{.02 in}g^a)^b$ and $g^c$ each
$\:$ have a positive probability of being the identity element

.


Therefore, if $q$ has no small factors then they are in fact statistically indistinguishable.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Correction: if q has no small factors, then they are statistically indistinguishable. For example, if $q = 2r$ for large prime $r$, it's not smooth; however is $a$ is even and $c$ is odd, $g^{ab}$ and $g^c$ can be distinguished. $\endgroup$
    – poncho
    Jun 2, 2015 at 19:47
  • $\begingroup$ Agh, very good point, I just made that change. $\;$ $\endgroup$
    – user991
    Jun 2, 2015 at 20:17
  • $\begingroup$ Thank you very much, @poncho and Ricky Demer. By the way, is there any real cryptographic protocols/schemes that uses this property? $\endgroup$
    – phan
    Jun 4, 2015 at 9:24

Your Answer

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

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