2
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Shan Chen
    Commented Jun 24, 2018 at 4:32

1 Answer 1

2
$\begingroup$

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

$\endgroup$

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.