What is the difference of the CDH problem in different groups? In particular, given a group $\mathbb{G}_1$ of order $q$ that is a subgroup of $\mathbb{Z}_q^*$, $q$ prime, and another group $\mathbb{G}_2$ of order $p$ that is a subgroup of $\mathbb{Z}_p^*$, $p = 2^n$, is solving the discrete log problem easier or harder in one or the other?
4
$\begingroup$
$\endgroup$
-
2$\begingroup$ The group $\mathbb{Z}_q^{*}$ has $\phi(q) = q-1$ elements. It can not have a subgroup with $q$ elements. If you meant two different large prime numbers, you should point that out. $\endgroup$ – tylo Jul 25 '13 at 10:43
2
$\begingroup$
$\endgroup$
If a prime $q$ is large enough discrete logs and CDH in $\mathbb{Z}_q$ are traditional hard problems in cryptography.
Your other example $\mathbb{Z}_{2^n}$ is typically easy to solve because it can be solved progressively modulo increasing powers of $2$.
May be you intended to consider the finite field with $2^n$ elements $\mathbb{F}_{2^n}$ and not numbers modulo $2^n$. If so, you might be interested be this related question: How robust is discrete logarithm in $GF(2^n)$?
-
$\begingroup$ Yes, sorry, this is what I meant. Thank you for the reference. $\endgroup$ – caw Jul 26 '13 at 17:09
