4
$\begingroup$

The complexity of solving the discrete logarithm problem depends on the choice of the group $G$. A popular choice is $Z_p^*$ where $p$ is a safe prime (${p=2p' +1}$ and $p'$ is also prime). In this case, $G$ is a group of prime order so every element in it is a generator. We can do then:

  1. Pick ${g}$ as a random element from $Z_p^*$
  2. Pick a random $x$
  3. Evaluate ${y = g^x \: mod \: p}$

Now we can assume solving $x = {log_g(y)}$ is hard if $p$ is large enough.

However, I often see the group $G$ is chosen as $Z_N^*$ where $N=pq$ and both $p$ and $q$ are safe primes. The algorithm is as follows:

  1. Pick $g$ as a random element from $Z_N^*$
  2. Pick $x$ as a random element from $(0, N')$ where ${N' = p' q'}$ where ${p=2p' + 1}$ and ${q=2q' + 1}$
  3. Evaluate ${y = g^x \: mod \: N}$

This construction is used in various publications from MacKenzie and Fujisaki&Okamoto.

What's that group? Does $Z_N^*$ guarantee computing discrete logarithm is hard? Since ${Z_N^*}$ is not a group of a prime order, is there any guarantee $g$ is a generator?

$\endgroup$
  • $\begingroup$ For $\mathbb{Z}_p$, the actual group is usually some prime order subgroup with order $q$. With a safe prime that's $q = p'$. The reason is that the entire $\mathbb{Z}_p^*$ is isomorphic to $\mathbb{Z}_{p'} \times \mathbb{Z}_2$, and the order $2$ subgroup part is easily solved - that's quadratic residues and non-residues. $\endgroup$ – tylo Aug 24 '18 at 16:03
5
$\begingroup$

What's that group?

Algebraically, it is isomorphic to the group $\mathbb{Z}_{p-1} \times \mathbb{Z}_{q-1} = \mathbb{Z}_{p'} \times \mathbb{Z}_{q'} \times \mathbb{Z}_2 \times \mathbb{Z}_2$.

Does $\mathbb{Z}_N^*$ guarantee computing discrete logarithm is hard?

It can be shown that it is at least as hard as factoring $N$ (as if you can compute discrete logs, you can factor).

Hence, if factoring $N$ is infeasible, so is computing discrete logs.

Since $\mathbb{Z}_N^*$ is not a group of a prime order, is there any guarantee $g$ is a generator.

Actually, there is a guarantee that $g$ is not a generator for the entire group; that's because $\mathbb{Z}_N^*$ is not a cyclic group, and hence does not have a generator.

In particular, the subgroup generated by a single value $g$ will never contain both elements $a$ and $b$ where:

  • $a \bmod p$ is a Quadratic Residue $\bmod p$, and $a \bmod q$ is a Quadratic Nonresidue $\bmod q$

  • $b \bmod p$ is a Quadratic Nonresidue $\bmod p$, and $b \bmod q$ is a Quadratic Residue $\bmod q$

(Such elements $a$ and $b$ will always exist in $\mathbb{Z}_N^*$)

$\endgroup$
  • $\begingroup$ In this case, since there is a guarantee $g$ is not a generator for the entire group is the choice of $g$ for the logarithm base safe (considering we want the discrete algorithm computation to be infeasible)? $\endgroup$ – omnomnom Aug 24 '18 at 14:53
  • $\begingroup$ @PiotrDe: see the "the discrete log problem is at least as hard as factoring" part of the answer. $\endgroup$ – poncho Aug 24 '18 at 14:57
  • $\begingroup$ @PiotrDe: in addition, as long as $g \not\equiv \pm 1 \bmod p, \bmod q$, then the size of the subgroup that $g$ generates will be at least $p' q'$, and so it should be adequately large $\endgroup$ – poncho Aug 24 '18 at 15:03
  • $\begingroup$ OK, so just to make sure because this is the part I am probably missing. Since $g$ generates a subgroup of at least $p'q'$, we are fine. So even though $g$ is not a generator for the entire group, we are safe. In other words: one of the reasons that make the discrete logarithm hard is the size of the group that $g$ generates and $g$ does not have to be a generator for the entire group. Is that correct? $\endgroup$ – omnomnom Aug 24 '18 at 15:09
  • 2
    $\begingroup$ @PiotrDe: actually, the 'discrete log problem is at least as hard as factoring' is a more cogent reason. The subgroup size isn't that important (as long as it's large enough); there are plenty of groups that have large subgroups where the discrete log problem is easy. $\endgroup$ – poncho Aug 24 '18 at 15:11

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.