I'm new to DDH. Reading this survey, I noticed that DDH is (believed to be) hard in many groups, but most of them are prime-order groups (the only one that is not is the cyclic subgroup of order $(p-1)(q-1)$ of the group of integers modulo $N = pq$). My question is about the hardness of DDH in this specific composite-order group:

Let $q$ be a prime such that $p = 4q+1$ is a prime. Is DDH hard in the subgroup of order $2q$ of $\Bbb Z_{p}^\ast$?

Note about this group: My algebra background is fairly basic and I don't even know if this group is guaranteed to exist, and if so, if it guaranteed to be cyclic.

  • 1
    $\begingroup$ Such a group does exist! Here is the smallest example: $q = 3, p = 4q + 1 = 13$, and the subgroup of $(\mathbb Z/p\mathbb Z)^\times$ generated by $10$ has order $2q = 6$. If you're not sure whether it is cyclic, I recommend reviewing your group theory textbook! $\endgroup$ Jul 15, 2018 at 22:05
  • $\begingroup$ Nit: the group $\mathbb{Z}_n^*$ for $n = pq$ does have order $(p-1)(q-1)$, but if both $p, q$ are odd, it is not cyclic, as it will always have the noncyclic group $\mathbb{Z}/2 \times \mathbb{Z}/2$ as a subgroup $\endgroup$
    – poncho
    Jul 15, 2018 at 22:10
  • $\begingroup$ @SqueamishOssifrage Thanks for your example! Just a question: do you mean that this subgroup always exists, no matter the choice of $p$ and $q$ (as long as they are both primes)? Also, if that's the case, I don't see why the group must be cyclic, since it has a composite order. Maybe I'm missing something? $\endgroup$
    – Cristina
    Jul 16, 2018 at 6:15
  • $\begingroup$ @Cristina I was just giving an example of a group satisfying all your criteria (except for the DDH part, since obviously it's too small). Under what circumstances is $(\mathbb Z/n\mathbb Z)^\times$ cyclic, for any integer $n$? How is it related to $(\mathbb Z/p\mathbb Z)^\times$ for prime $p$ What does the Chinese remainder theorem tell you? $\endgroup$ Jul 16, 2018 at 14:55
  • $\begingroup$ @SqueamishOssifrage Yep! Thanks for the reminder :) I just checked my book and it makes more sense $\endgroup$
    – Cristina
    Jul 17, 2018 at 9:04

1 Answer 1


Is DDH hard in the subgroup of order $2q$ of $\mathbb{Z}_p^*$

No, it is not.

If you define the function $F(x) = x^{q} \bmod p$, then for any $x$ is\n the group of order $2q$, we have $F(x)= 1$ if $x$ is a member of the proper subgroup of order $q$, and $-1$ if it is not. And, exactly half of the elements will be in that subgroup.

You will always have an even number (either 0 or 2) of $F(g^a)$, $F(g^b)$, $F(g^{ab})$ be -1; if you find that an odd number of $F(g^a)$, $F(g^b)$, $F(g^c)$ be -1, then you have determined that is not a DH triple.

This logic applies to any group that has an order with a small factor.

  • $\begingroup$ That's a great explanation! Thanks a lot, it's much clearer now $\endgroup$
    – Cristina
    Jul 16, 2018 at 6:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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