What is the Discrete Logarithm Problem in (Z/Zp) in the DSA?

Question

Literature on the DSA (e.g. Gupta 2014) agrees that the security in DSA relies on the difficulty to solve two distinct discrete logarithm problems (DLP):

One is the DLP in prime-order ($q$) subgroups of $\mathbb{Z}_p^*$ for which the most efficient algorithm is Pollard's rho method. I understand this is basically calculating the private key $x$ given the corresponding public key $y$ for $y=g^x$ mod $p$, and to avoid this we choose a large enough $q$ (e.g. 160-bit).

The other DLP is said to be in $\mathbb{Z}_p^*$ itself, to which the Number Field Sieve algorithm would apply; but I am uncertain what the meaning behind this second DLP is, i.e. what is the exact calculation that we try to do here, and how would it affect the security of digital signatures that are based on subgroups, not the overall $\mathbb{Z}_p^*$?

My initial idea was that it is because the domain parameters are in $\mathbb{Z}_p^*$, but I can't find online sources or literature that goes into more detail regarding this point.

What is the Discrete Logarithm Problem in (Z/Zp) in the DSA?

Answer 1

There is actually only one DLP in DSA. There are multiple approaches to solve it, that can be classified in two categories.

---

The security of DSA (as defined in FIPS 186-4 section 4) is no better (and equivalent under some models) to the difficulty of the Discrete Logarithm Problem in some Schnorr group. The problem is finding an integer $x$ solution of the equation $y=g^x\bmod p$ for given $p$ defining the group, $g$ in the group, and public key $y$ in the group.

More precisely, that group is a subgroup of $\mathbb Z_p^*$, or equivalently $(\mathbb Z/p\mathbb Z)^*$, for some prime $p$, under modular multiplication, with the subgroup generated by $g$, having as order some randomly seeded prime $q$, and as a consequence $q$ dividing $p-1$. When following FIPS 186-4, $p$ is of L bits and $q$ is of N bits, for one of of these parameters sets:

L = 1024, N = 160
L = 2048, N = 224
L = 2048, N = 256
L = 3072, N = 256

This DLP problem can be solved by two classes of algorithms:

• Generic algorithms applicable to the DLP in any group of prime order $q$; this includes Pollard's rho and baby-step/giant-step; the cost of the algorithms depends mostly on parameter N (exponentially so, but only polynomialy on L).
• Specialized algorithms for subgroups of $\mathbb Z_p^*$, including index calculus and the DLP variant of the General Number Field Sieve; the cost of the algorithms depends nearly only on parameter L (less than exponentially so, but more than polynomialy).

Answer 2

While I do not know which literature you're referring to, and do personally not agree with the fact that DSA relies on two distinct DLP, I can see one explanation to a possible distinction in some text:

Upon signature, for $H$ a hash function and $m$ the message, you will:

• Pick a random $k$ such that $1 < k < q$
• Compute $r=\left(g^{k}\bmod\,p\right)\bmod\,q$
• If $r=0$, start with another $k$
• Compute $s=k^{-1}\left(H\left(m\right)+xr\right)\bmod\,q$
• If $s=0$, start with another $k$
• Disclose the signature $\left(r,s\right)$

So, now the value $r$ is assumed to be publicly available, but the value $k$ must be kept secret, otherwise, one can compute $$x=(sk-H(m))r^{-1} \bmod\,q$$

And so, if one could also solve the DLP in $\mathbb{Z}^*_p$, one could attack the value $$r=\left(g^{k}\bmod\,p\right)\bmod\,q$$ in order to recover the secret value $k$ and find out the secret key $x$!