1
$\begingroup$

I want to give an introductory talk on the Diffie-Hellman key exchange. Along the way, I will mention that there exist groups, like $(\mathbb Z/p\mathbb Z)^\times$ for which it is believed that the discrete logarithm problem (DLP) is hard. Trying to anticipate a question from the audience, suppose someone asks:

Are there groups for which the DLP is surely known to be hard?

What is a good way to answer such a question, and in the case of no answer, how do I convince the audience that the Diffie-Hellman key exchange is still worth the hustle? I understand this is not good question to ask here, so I bring my honest apologies.

Improve this question
$\endgroup$
6
  • $\begingroup$ Define "surely". $\endgroup$
    – mikeazo
    Commented Dec 14, 2016 at 13:11
  • $\begingroup$ I am using the definition of hard DLP from Introduction to Modern Cryptography of Katz and Lindell, which uses a randomized experiment to describe an adversary trying to find the discrete logarithm, and hard DLP means the adversary is successful with a negligible probabilty. Now, throughout the rest of the book, the authors provide examples for which the DLP is believed to be hard, but that's just because so far no good enough algorithm has been found, not because it does not exist. $\endgroup$
    – user223794
    Commented Dec 14, 2016 at 13:21
  • $\begingroup$ I can answer (in part) the negation of your question. For instance you have to avoid finite fields of small characteristic, since there are improved Index calculus attacks in this case. See eprint.iacr.org/2014/924.pdf. $\endgroup$
    – 111
    Commented Dec 14, 2016 at 13:30
  • 2
    $\begingroup$ So it sounds like the answer is that there is no example of the DLP that has been proven to be hard. Just that a bunch of really smart people have tried and tried to break the instances that we believe are hard and have failed. I don't see how you can give an answer different from that. As far as how to convince them it is worth the hustle, what else do they propose using? You can't let perfect be the enemy of good, especially when perfect doesn't exist. $\endgroup$
    – mikeazo
    Commented Dec 14, 2016 at 13:30
  • 1
    $\begingroup$ The comment "there's no group for which the DLP is proven hard" is a bit misleading. Without exploiting the representation of the group (e.g. additive group modulo some integer, elliptic-curve group), the DLP is "hard" in every prime order group. Now in practice, in particular in cryptography, we will of course always have a (exploitable) representation. But that's not the same statement. $\endgroup$
    – CurveEnthusiast
    Commented Dec 14, 2016 at 17:03

1 Answer 1

Reset to default
2
$\begingroup$

I think this is a very good question, and an interesting one. Not sure if my answer will go in the direction you meant.

Generally when first discussing the DLP for groups, you'd want to find an attack which uses only the most basic properties of a group. That is, you think of having a black box into which you can feed any two group elements, and it will compute the group operation on them. You see the result, but have no idea how it was computed.

Now suppose we have such a black box group, and assume that it is cyclic of prime order $r$. Then this paper proves that you need on average at least $O(\sqrt{r})$ calls to the black box to solve the DLP. For those groups we are sure that the DLP is hard, for some definition of "sure" and "hard".

This may be somewhat counterintuitive. Note that for a prime $p$, $\mathbb{Z}/p\mathbb{Z}$ with addition is a prime order group for which the DLP is trivial. Also for every black box group $G$ such that $|G|=p$ there exist an isomorphism $\phi:G\cong \mathbb{Z}/p\mathbb{Z}$. The problem is that we cannot reduce the problem from the black box group $G$ to $\mathbb{Z}/p\mathbb{Z}$, since we cannot compute the isomorphism $\phi$ efficiently.

Improve this answer
$\endgroup$
6
  • 4
    $\begingroup$ This does not answer the question, because black box groups do not exist. $\endgroup$
    – fkraiem
    Commented Dec 15, 2016 at 2:54
  • 2
    $\begingroup$ @fkraiem Whether or not this answers the question is for the OP to decide. Frankly, I find your opinion completely irrelevant on this matter. If you believe you can do better, there is always the option to add an answer of your own. As for the second part: indeed, black box groups do not exist. I do not claim that they do. The question asks for groups for which we are sure the DLP is hard, and I give a result which states in which circumstances we can prove a lower bound. $\endgroup$
    – CurveEnthusiast
    Commented Dec 15, 2016 at 7:22
  • 4
    $\begingroup$ Oh yeah? Well, I find your answer completely irrelevant. Do groups with hard DLP exist, or do they not, or is the answer unknown? That was the question, and you don't answer it, plain and simple. $\endgroup$
    – fkraiem
    Commented Dec 15, 2016 at 7:48
  • 1
    $\begingroup$ That was not the question, the question was how to answer such a question. This is not a yes/no question. For any group we use in crypto, we cannot prove that the DLP is hard. However under some, arguably practically useless, conditions we can prove some things. I believe this is a worthwhile addition to the argument, you seem to think otherwise. You are free to downvote in that case, this is what the system is for. The clever one-liner I can do without. $\endgroup$
    – CurveEnthusiast
    Commented Dec 15, 2016 at 8:14
  • 2
    $\begingroup$ I don't know why this is becoming such a dispute over here, but yes, I do believe that CurveEnthusiast really saw through my question and provided IMO an answer which was a lot better than what I even expected. Thank you for the help. $\endgroup$
    – user223794
    Commented Dec 15, 2016 at 17:56

Your Answer

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

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