2
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

The claim is completely false.

The security of DDH over appropriate composite-order elliptic curves is not only believed to hold, the assumption that it holds has been widely used in cryptography. To give a single famous example, the BGN cryptosystem was initially defined over composite-order elliptic curves (with a pairing), before being generalized a few years later to prime order curves. More generally, relying on composite order elliptic curves is actually the standard approach in various subfields of pairing-based cryptography when a feasibility result must be established (see e.g. this IBE), since it is usually much simpler to get feasibility results there. The choice of prime-order elliptic curves is not motivated by security, but by efficiency, since a composite-order modulus must be huge in general.

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

$\endgroup$
2
  • 1
    $\begingroup$ If you refer to the last part, that would be $O(\log \lambda)$, where $\lambda$ is your security parameter $\endgroup$ Jun 13, 2021 at 7:19
  • $\begingroup$ My autocorrect completely butchered your name, so I removed the comment. For future reference, it was: "What does 'small' mean in this context?" $\endgroup$
    – Marcel
    Jun 14, 2021 at 8:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.