# Is $(a,g^{ab})$ computationally indistinguishable from $(a, g^c)$?

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?

• They are even more than computationally indistinguishable: they are identically distributed. – fkraiem Jun 2 '15 at 3:34
• (The above assumes $q$ is prime and $a\ne 0$, by the way...) – fkraiem Jun 2 '15 at 3:42
• Then can we say $(a, g^{ba}, g^{bc})$ and $(a, g^d, g^e)$ are identically distributed? – phan Jun 2 '15 at 3:44
• Under the same assumptions, yes. – 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.

• 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. – poncho Jun 2 '15 at 19:47
• Agh, very good point, I just made that change. $\;$ – user991 Jun 2 '15 at 20:17
• Thank you very much, @poncho and Ricky Demer. By the way, is there any real cryptographic protocols/schemes that uses this property? – phan Jun 4 '15 at 9:24