1
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ Pohlig-Hellman requires factorization of $q$ which is hard. $\endgroup$
    – Turbo
    Jul 2, 2020 at 22:43
  • 2
    $\begingroup$ crypto.stackexchange.com/q/30328/18298 $\endgroup$
    – kelalaka
    Jul 2, 2020 at 22:49
  • $\begingroup$ @Kelalaka Why did you delete the older comment? Your older comment was "Pohlig-Hellman and $q$ is public". I have already addressed that to use Pohlig-Hellman you need to factor $q$ which is hard which is the premise of the problem. You are reiterating the same. How is knowledge of $q$ going to help if factorization is hard and $\lambda(q)$ is unknown even if discrete logarithm modulo primes is broken? $\endgroup$
    – Turbo
    Jul 2, 2020 at 22:58
  • 1
    $\begingroup$ crypto.stackexchange.com/q/32415/18298 $\endgroup$
    – kelalaka
    Jul 2, 2020 at 23:01
  • 1
    $\begingroup$ Welcome to crypto.SE! Mod note: The question would be a better fit for the site as: Assuming an oracle solving the DLP modulo a prime, can we solve the DLP modulo a composite that's too large to factor?. This would be focusing on the mathematical problem, rather then "popularity" and inclusion "in standards", which does not follow a well-defined logic (things with no technical merit are used and/or standardized; in particular things often are standardized because they are used). The current "why is this not popular and defined in standards?" could remain as a secondary question, though. $\endgroup$
    – fgrieu
    Jul 3, 2020 at 4:46

1 Answer 1

5
$\begingroup$

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).

$\endgroup$
4
  • $\begingroup$ @Ruggero To form the private key Alice and Bob have to know not only $q$ but also its factors. It is unclear if this can be done without Eve knowing it. I think that answers that if DLP mod prime is broken then there is no cryptographic scheme based on Diffie-Hellman even if factoring is difficult. $\endgroup$
    – Turbo
    Jul 4, 2020 at 2:17
  • $\begingroup$ @T....: actually, if DLP mod prime is broken, there still is DH in an elliptic curve group, or a finite field extension (the latter is currently believed weaker than a prime field for a given size; however a break specific to prime fields would certainly change that) $\endgroup$
    – poncho
    Jul 4, 2020 at 3:00
  • $\begingroup$ Let me put it this way. What if knowing $\lambda(q)$ breaks DLP over $\bmod q$. If you read initial sentences in my post that was the intention. I was wondering what if knowledge of $\lambda(q)$ suffices to break DLP over $q$? Then would DH over elliptic curve group be broken as well (in other words over elliptic curve group do we have an analog of $\bmod\lambda(q)$ that we operate the exponents?)? $\endgroup$
    – Turbo
    Jul 4, 2020 at 6:24
  • $\begingroup$ @T....: there is a proof that if all you can do is perform generic actions on a group (the group operation, compute inverses, check for equality), then the known square-root algorithms are essentially optimal (hence, to do better, you need to make more assumptions on the group); knowing the order of the group doesn't change this. Hence, an attacker that would apply to both elliptic curve groups and finite field groups would need to rely on some property (beyond knowing the group order) that is true to both. $\endgroup$
    – poncho
    Jul 4, 2020 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.