# Complexity of solving the discrete logarithm problem for the group formed from product of 2 safe primes

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?

• 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. – tylo Aug 24 '18 at 16:03

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^*$)

• 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)? – omnomnom Aug 24 '18 at 14:53
• @PiotrDe: see the "the discrete log problem is at least as hard as factoring" part of the answer. – poncho Aug 24 '18 at 14:57
• @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 – poncho Aug 24 '18 at 15:03
• 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? – omnomnom Aug 24 '18 at 15:09
• @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. – poncho Aug 24 '18 at 15:11