To construct a secure multiparty computation function, we need to use the cyclic group G = Z*p^2 with p is a large prime. However, we are uncertain that DDH holds over this group.
Can you show that DDH holds/doesn't hold over the cyclic group Z*p^2?
Note that: the order of G is q = p(p-1) and q is multiple of the large prime p.
Thank you very much!
I would say that DDH does not hold in $Z^*_{p^2}$.
Let's first consider DDH in $Z^*_{p}$. We know DDH is not hard because given a DDH tuple $(g^a,g^b,g^c)$, one can compute the Legendre symbols $(L(g^a),L(g^b),L(g^c))$, and know whether they are quadratic residues or not. If any of $(g^a,g^b)$ is a residue but $g^c$ is not, then we know $c\ne ab$.
It has also shown by Gauss that a number co-prime to an odd prime $p$ is a residue modulo any power of $p$ if and only if it is a residue modulo $p$. Thus the above can be extended to $Z^*_{p^2}$.
