# (How) Is DDH generally broken in groups of composite order?

In a somewhat recent lecture a claim was made that I couldn't back up myself but it got me curious whether it actually holds:

If the order of the group is not prime, then the DDH assumption does not hold.

So my question would simply be:
How does one break DDH in general assuming only that the group order is composite? Or is there a group with composite order where DDH is conjectured to hold?

My research only lead to the special case of $$\mathbb Z^*_p$$ which has composite order as $$p-1$$ is even which leads to exploitable attacks on ElGamal thanks to the Legendre Symbol containing useful information which breaks DDH because ElGamal is proven CPA-secure iff DDH holds.

Even outside of elliptic curves, DDH can be fine over a composite order group - for example, one of my paper proves, in the appendix, that DDH holds over the subgroup of $$\mathbb{Z}^*_n$$ of elements whose Jacobi symbol is one, which is a composite order group, assuming that DDH holds over the subgroups of squares of both $$\mathbb{Z}^*_p$$ and $$\mathbb{Z}^*_q$$ ($$q$$ and $$p$$ are the prime factors of $$n$$) together with the quadratic residuosity assumption. This is one of many examples, it is in fact very easy to build many composite order groups in which DDH holds, assuming DDH in prime-order subgroups of this group.
I have no idea why this claim was made in your lecture; the only things that comes to mind is that if the modulus contains small factors, then there is a straightforward CRT attack where you project onto the small groups. For example, DDH does not hold over $$\mathbb{Z}^*_p$$ itself, since it's a group of even order, so you can project a DDH instance to a subgroup isomorphic to $$\{-1,+1\}$$ (this is equivalent to distinguishing by computing the Legendre symbol, as you correctly observe).
• If you refer to the last part, that would be $O(\log \lambda)$, where $\lambda$ is your security parameter Jun 13, 2021 at 7:19