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$ – Squeamish Ossifrage Jul 15 '18 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 '18 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 '18 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$ – Squeamish Ossifrage Jul 16 '18 at 14:55
  • $\begingroup$ @SqueamishOssifrage Yep! Thanks for the reminder :) I just checked my book and it makes more sense $\endgroup$ – Cristina Jul 17 '18 at 9:04

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 '18 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.