# About DDH over cyclic group Z*p^2

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!

• Am I correct in assuming that this is a homework assignment or something similar? If so, please provide an indication of what you are not understanding / need clarification on and your attempts at solving it, so we have a clear indication of where you are stuck. Questions just asking for a solution to a homework exercise are considered off-topic here. Thanks. – Ilmari Karonen Jun 2 '18 at 21:28
• This is not my homework assignment. It is an important problem in my research in Secure multiparty computation area. So please do not close this topic. I need to be supported by the experts! – HienVD Jun 3 '18 at 3:19
• That's very interesting. Could you describe your research in more detail? – Ilmari Karonen Jun 3 '18 at 12:03
• I'm trying to construct a SMC protocol to efficiently compute the secure sum of n-parties. If this protocol is successfully built, then numerous of application problems are solved (e.g. privacy-preserving linear and logistic regression). – HienVD Jun 3 '18 at 14:32

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}$.