Why discrete logarithm modulo composite moduli not popular and not defined in standards?

Question

The classical discrete logarithm problem is to find $x$ such that $g^x\equiv h\bmod p$ where $p$ is a prime and $g$ is generator of multiplicative group modulo $p$.

The demerit of this approach seems to be knowledge of $\lambda(p)$ where $\lambda$ is Carmichael Lambda function.

Supposing instead if we had $g^x\equiv h\bmod q$ where $q$ is composite $\lambda(q)$ is hidden since factorization is difficult.

One can still perform Diffie-Hellman at both Alice's and Bob's side since $(g^x)^y\bmod q$ can be computed without knowledge of $\lambda(q)$ and thus without knowing factorization of $q$.

Such a scheme includes factorization as an additional barrier in case discrete logarithm modulo primes is broken and so why is this not popular and defined in standards?

Note if discrete logarithm modulo primes is broken there is no way to use $q$ to be same length as $p$. We will only get smaller security if we use same length. $q$ has to be larger in length but the point is it cannot be prime. Perhaps $q$ is product of $\log p$ primes each of length $\log p$ bits.

Another phrasing of the problem is "Assuming an oracle solving the DLP modulo a prime, can we solve the DLP modulo a composite that's too large to factor?" as stated in a comment with each factor also reasonably large.

Answer 1

Such a scheme includes factorization as an additional barrier in case discrete logarithm modulo primes is broken and so why is this not popular and defined in standards?

Actually, it would not be an "additional barrier", instead, it would be an additional avenue of attack. After all, the standard attacks against a discrete log problem still work in a composite modulii; in addition, the attacker has the possibility of factoring the modulii, and then solving the discrete log problem modulo each prime factor. The primes are considerably smaller than the full modulii, and hence those subproblems are comparatively easy to solve; the difficulty is dominated by the factorization effort.

You state in your rephrasing "what if we had an Oracle that solved the discrete log problem modulo a prime (but not a composite)", well, since we have no indication that such an Oracle exists, we don't worry too much about it. In any case, your construction to change that to "what if we had an Oracle that solved the factorization problem" (because once we've factored, solving the discrete log modulo the smaller prime factors is comparatively easy).

On the other hand, that really doesn't answer the question "why don't standards do that?" Well, I didn't write the standards, so I can't give an authoritative answer there; however I would note that it makes it considerably harder to come up with a Nothing-Up-My-Sleeve group; that is, a group that we are pretty sure is actually secure, and that no one has a backdoor to.

For prime modulii, it is fairly easy to design a deterministic process that, at the end, generates a "good" prime number; that is, one where we know the large prime subgroup, (and which is not vulnerable to the Special Number Field Sieve algorithm); with that, we are fairly confident that it was not designed with a special vulnerability in mind.

In contrast, we don't have such a good way to have a deterministic process that generates a composite number of unknown factorization (and which is known to be hard to factor), and also has a large rough [1] subgroup with a known generator. What we are likely to do is rely on some trusted authority to generate one for us.

Well, the "trusted" part is a deal-breaker for quite a few; there isn't anyone which everyone would agree should be trusted with coming up with our crypto parameters. And, yes, "trust" is the right word; there are a number of ways a dealer can generate a composite modulus for which they can solve the discrete log problem, but other people can't (essentially by using different prime factors for which they can solve the discrete log problem, and then multiplying them together to hide things).

[1]: By rough, I mean one with no small prime factors. This is not standard terminology (hence this footnote); this is the obvious antonym to "smooth" (consists only of small factors).