# prove PRG is secure assuming DDH holds

Let $\Bbb{G}$ be a cyclic group of prime order $q$ generated by $g \in G$.

Let $G$ be a PRG defined over $(\Bbb{Z}_q^2, \Bbb{G}^3)$ such that:

$G(a, b) = (g^{a}, g^{b}, g^{ab})$

How can I show that $G$ is a secure PRG assuming DDH (decisional Diffie-Hellman) holds in $G$?

After reading this, I'm confused to prove $G$ is secure:

Importantly, the DDH assumption does not hold in the multiplicative group $\mathbb{Z}^*_p$, where $p$ is prime. This is because given $g^a$ and $g^b$, one can efficiently compute the [Legendre symbol] of $g^{ab}$, giving a successful method to distinguish $g^{ab}$ from a random group element

• I guess this is a homework question (the reduction is straightforward from the definitions of PRG and DDH). To answer your last question, $\Bbb{Z}_p^*$ is not equal to a cyclic group of order p, because the former excludes the zero element 0 hence has size p-1. – Shan Chen Jun 24 '18 at 4:32

As Shan Chen said, the reduction is easy. Note if the DDH adversary gets $g^a,g^b,g^{ab}$ then it gets $g(a,b)$, and if it gets $g^a,g^b,g^{c}$, then he gets a uniformly random string.

Now for the second question. First for a prime number $p$, the order of $\mathbb{Z}^*_p$ is $p-1$. If $G$ is a (integer) cyclic group of prime order $q$, then you are not using $\mathbb{Z}^*_p$, but the order-$q$ subgroup of it ($q$ needs to be large which I assume here).

Why DDH is not hard in $\mathbb{Z}^*_p$? By Euler's criterion, in $\mathbb{Z}^*_p$ there are $\frac{(p - 1)}{2}$ quadratic residues and $\frac{(p − 1)}{2}$ non-residues. So in for a random $x \in \mathbb{Z}^*_p$, the probability of $x$ being a residue (non-residue) is exactly $\frac{1}{2}$. Legendre symbol for an element $x \in \mathbb{Z}^*_p$ can be calculated as:

$$\Big(\frac{x}{p}\Big)= x^{\frac{p-1}{2}} \bmod p$$

and the symbol tells whether $a$ is a residue or non-residue: \begin{equation*} \Big(\frac{x}{p}\Big) = \begin{cases} 1 &\text{if $x$ is a residue}\\ -1 &\text{if $x$ is a non-residue} \end{cases} \end{equation*}

Now given the DDH tuple $(g^a,g^b,g^c) \in (\mathbb{Z}_p^*)^3$, we can calculate the Legendre symbols of $g^a,g^b,g^{c}$. If either $\Big(\frac{g^a}{p}\Big)$ or $\Big(\frac{g^b}{p}\Big)$ is 1, then $Pr[\Big(\frac{g^{ab}}{p}\Big)=1] =1$.

The reason is that a residue $x$ is congruent to a perfect square. So that if $g^a$ is a residue, then it can be expressed as $g^a=h^2$. For $g^{ab}$, it can be rewritten as $(h^b)^2$, which is also a residue.

But for a random $c$ that $c\ne ab$, the probability of it being a residue is only $\frac{1}{2}$, which means we can distinguish $g^{ab}$ and $g^c$ easily.

If the DDH tuple $(g^a,g^b,g^c) \in G^3$, since $q$ divide $p-1$ and $p-1$ is even, $\frac{p-1}{2} = kq$ for some $k$, then $\Big(\frac{g^a}{p}\Big), \Big(\frac{g^b}{p}\Big),\Big(\frac{g^{ab}}{p}\Big), \Big(\frac{g^c}{p}\Big)$ are all 1 (because all elements in $G$ are of order $q$, thus the $q$-th power of all elements in $G$ congruent to 1).