1
$\begingroup$

Computational Diffie Hellman problem wants to know $g^{ab}$ given $g^a$, $g^b$ and $g$ while the discrete logarithm problem wants to know $x$ from $g^x$ and $g$.

The latter resolvable in polynomial-time implies the former as well but a converse result is not known.

What are the consequences to cryptography if Diffie-Hellman is breakable but an algorithm for discrete logarithm is unclear?

$\endgroup$
5
  • $\begingroup$ What consequences do those have? Like signatures, authentication etc. What will not breaking discrete logarithm leave? $\endgroup$
    – Turbo
    Oct 10, 2020 at 19:11
  • $\begingroup$ @kelalaka So you really do not need DL to not be in P for any application? $\endgroup$
    – Turbo
    Oct 10, 2020 at 23:45
  • $\begingroup$ Yeah..... I thought there may be some applications where even if CDH turns to be easy will still be difficult as with the knowledge now. $\endgroup$
    – Turbo
    Oct 10, 2020 at 23:52
  • $\begingroup$ Sorry that provides some algorithms for DL. $\endgroup$
    – Turbo
    Oct 10, 2020 at 23:55
  • $\begingroup$ Sorry I dont understand what you are getting to. $\endgroup$
    – Turbo
    Oct 11, 2020 at 0:01

2 Answers 2

1
$\begingroup$

There is a big question (that Meir Maor hints at) underlying your problem, namely:

Must the algorithm work for a fixed group, or any group?

Note that there exist groups for which DLOG (and things that reduce to DLOG) are easy, the most basic example is the group $(\mathbb{Z}/n\mathbb{Z}, +)$. Even among groups that have been used within cryptography, there are groups for which DLOG (and things that reduce to DLOG) are now much easier than we used to think they were --- specifically the group $(\mathbb{F}_{p^n}^\times, \times)$ for $p = O(1)$ admits quasi-polynomial time DLOG algorithms --- this paper shows expected time $(pn)^{2\log_2(n) + O(1)}$. This weakness isn't just theoretical, by far the largest DLOG computed was in $\mathbb{F}_{2^{30750}}^\times$.

Of course, this is all about the discrete logarithm problem. There are (in my eyes) two other natural questions:

  1. What if over arbitrary groups CDH is in $P$, but DLOG is not in $P$?
  2. What if for specific groups of cryptographic interest CDH is in $P$, but DLOG is not in $P$?

For the first problem, this is unlikely to happen. This is because in the Algebraic group model the problems are equivalent. This model restricts computations somewhat (the DLOG algorithm for $\mathbb{F}_{2^{30750}}^\times$ is not expressible within it), but the restriction is somewhat natural --- computations are seen as a (linear) sequence of steps, and any group elements used in step $i$ must be explicitly computed from group elements used in prior steps. There are some nuances here I am not entirely familiar with [1], but the point of the model is to capture algorithms that only use the "public API" of the group, instead of specific details about the structure of the group.

This means that if DLOG and CDH are not equivalent for general groups, the model is quite flawed in capturing the "public API" part of group-theoretic computations, which is perhaps not obvious (to me at least) from examining the model.

For the second problem, this is also not likely to happen (but for other reasons). Specifically, the two problems are known to be non-uniformly equivalent to eachother over arbitrary cyclic groups. See my prior answer for details.

Neither of these two points absolutely rules out a separation between CDH and DLOG, but both provide some formal evidence that such a separation is unlikely to happen.

[1] Specifically, what group elements do you start with? The group identity seems natural, but discussion at the bottom of page 7 sounds like you get random oracle queries too. Is there anything else?

$\endgroup$
0
$\begingroup$

There are very few consequences. In fact it is fairly likely Discrete logarithm is in P, or at least it is not likely to be NP hard. Discrete logarithm is random self reducible which is one of the reasons we like it. A random instance is as hard as the worst case.

Sadly the existence of an NP-Hard random self reducible problem implies the collapse of the polynomial heirarchy and this is believed not to be the case.

So despite having convincing arguments that Diffi Helman is not "Hard" we still use it. Since we know of no efficient algorithm to break it and we have been looking hard for a while, that's really as good as you get in cryptography.

Note we can rank possible events:

  1. Proof DH is in P
  2. Demonstrate a Polynomial time algorithm for DH
  3. An efficient algorithm capeable of breaking common schemes.

The first will make a stir in academic community but won't actually surprise anyone. The second may cause frantic replacement of DH based algorithms which are everywhere. The third will break the internet.

Also impact will be different for a general solution over any Field/Ring or e.g only for Zp.

$\endgroup$
1
  • $\begingroup$ "it is fairly likely Discrete logarithm is in P"; the only reasoning given is that it's not likely to be NP-hard (which I would agree with); however it is known (assuming P$\ne$NP) that there are NP problems that are neither P nor NP-complete. Given that in the generic group model, discrete log probably takes exponential time; however for DLog to be in P, that implies that all groups must have a weakness that allows for a polynomial attack - while not impossible, that would certainly surprise me... $\endgroup$
    – poncho
    Jun 30, 2021 at 21:32

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.