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?

  • 1
    $\begingroup$ They are even more than computationally indistinguishable: they are identically distributed. $\endgroup$ – fkraiem Jun 2 '15 at 3:34
  • 1
    $\begingroup$ (The above assumes $q$ is prime and $a\ne 0$, by the way...) $\endgroup$ – fkraiem Jun 2 '15 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 '15 at 3:44
  • $\begingroup$ Under the same assumptions, yes. $\endgroup$ – fkraiem Jun 2 '15 at 3:46

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.

  • 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 '15 at 19:47
  • $\begingroup$ Agh, very good point, I just made that change. $\;$ $\endgroup$ – user991 Jun 2 '15 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 '15 at 9: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.