# Does DDH hold in $Z_N^*$ where N is product of 2 large primes

I know that DDH does not hold in $$Z_p^*$$ because given $$g, g^a, g^b, x$$, we can compute legendre symbols of $$g^a, g^b$$ and compare it with legendre symbol of $$x$$. The same attack doesn't work when we consider the group $$Z_N^*$$ where N is product of 2 large primes. This is because computing jacobi symbol without knowing factors of N is hard by Quadratic Residuocity assumption. So, does DDH assumption hold in $$Z_N^*$$?

The same attack doesn't work when we consider the group $$Z_N^*$$ where N is product of 2 large primes. This is because computing jacobi symbol without knowing factors of N is hard by Quadratic Residuocity assumption.
This is incorrect: computing the Jacobi symbol can always be done in polynomial time, and does not require knowing the factorization. You're confusing it with the hardness of computing residuosity (i.e., checking whether an element of $$Z_N^*$$ is a square). DDH does not hold over $$Z_N^*$$. It is however conjectured to hold over $$J_N$$, the subgroup of elements with Jacobi symbol 1, see pages 23-24 of my paper.
EDIT: a screenshot of some old slides of mine: each element of $$Z_N^*$$ can have Jacobi symbol 1 or -1, and if it has Jacobi symbol 1, be square or non-square.
• @satya: an element $x \in \mathbb{Z}_n^*$ (where $n=pq$) will be a QR if $x$ is a QR mod $p$ AND $x$ is a QR mod $q$. $x$ will have Jacobi symbol 1 if $x$ is a QR mod $p$ XOR $x$ is a QR mod $q$ Dec 12, 2018 at 13:49
• If one of $\Big(\frac{x}{p}\Big)$ and $\Big(\frac{x}{q}\Big)$ is 1 and the other is -1, then $\Big(\frac{x}{pq}\Big)$ would be -1 right? Dec 12, 2018 at 14:05