1
$\begingroup$

The discrete logarithm problem is to find $z$ when the inputs are $g,h,p$ where $g^z\bmod p$.

Supposing if you fix $p$ then does the problem become any easier to attacks and is there a $(\log p)^c$ complexity algorithm?

$\endgroup$
  • $\begingroup$ Do you mean that if one has already spend time to solve a given discrete logarithm, say finding $z_1$ from $h_1 = g^{z_1} \bmod p$, is it easier to solve an other discrete logarithm, say finding $z_2$ from $h_2 = g^{z_2} \bmod p$. For example, by re-using some precomputations made in the resolution of the first discrete logarithm? $\endgroup$ – user94293 May 13 '16 at 0:01
  • 1
    $\begingroup$ Once you fix $p$, there is a constant-time algorithm: Simply try all possibilities. Asymptotics do not make sense when the instance size is bounded; you need a different notion of complexity in that case. $\endgroup$ – yyyyyyy May 13 '16 at 0:12
  • 1
    $\begingroup$ I'll write a more complete answer later, but in short: yes, there as algorithms which, given p, can precompute the discrete logarithm so that any discrete log is easy to compute next (but the setting you describe is not formal, in particular talking about asymptotic complexity is not relevant here). You can have for example a few weeks of precomputation, and then each discrete log will be computed in a few minutes. $\endgroup$ – Geoffroy Couteau May 13 '16 at 17:17
  • $\begingroup$ @GeoffroyCouteau Please do write an answer if you have time. If a question deserves an answer it probably also deserves an upvote. $\endgroup$ – Maarten Bodewes May 14 '16 at 10:22
  • $\begingroup$ @GeoffroyCouteau this is great what is the reference? what should i search in literature for this? $\endgroup$ – T.... May 14 '16 at 11:44
1
$\begingroup$

The best algorithm for computing discrete logarithms are based on families and variations of methods known as "number field sieve" and "function field sieve". They all share a common structure. In particular, they are divided in several phases, only the last of which depends on the value whose discrete logarithm must be computed: all the previous steps require only the order of the field.

I did some research. I do not know about the computational complexity of each step, this would involve some more research but can probably be found in some of the articles and surveys of Antoine Joux. However, I'll focus on the case which seems to be your target: discrete logarithm in prime order field. For that case, the actual record is a discrete log in a field of order $p$, with $bitsize(p) = 530$. You'll find Here the report on this record. The computation is divided in five phases: polynomial selection, sieving, filtering, linear algebra, and actual computation of the discrete logarithm. Among them, the sieving is by far the dominant cost: the report indicates it took approximately 50 core-years on a 2-GHz Intel E5-2650. This phase depends only on the order $p$ of the field. The report mention that once the four first phases have been performed, "Computing one individual logarithm required a few hours". Therefore, Compared to the overall time, computing discrete logarithms is extremely fast once the precomputation has been made (with the order of the field only).

Although I do not know the theoretical complexity of this last step, I'm pretty sure that this is still not polynomial time (id est, $O(\log^c p)$ for some $c$), even if it is only a negligible cost in the total computation.

$\endgroup$
  • $\begingroup$ Thank you. You said you can avoid the guess of $O(log^cp)$ but what is your best guess? $\endgroup$ – T.... May 16 '16 at 19:46
  • $\begingroup$ Sadly, I do not have much intuition regarding this topic - I'm by no mean a specialist, I just happened to hear about those running times during some talk, and did some research (mostly via Wikipedia) to find articles with concrete benchmarks. I've tried to look at some more articles but they do not seem to precisely provide a complexity for each step - it could however probably be determined with a more in-depth reading, but I'd rather hope for someone more knowledgeable to answer :) But if I absolutely had to give a guess, I might bet on L(1/3) for this step, as for the other steps. $\endgroup$ – Geoffroy Couteau May 17 '16 at 2:23
  • $\begingroup$ @Turbo: I just found this very interesting post on Aaronson's blog. It does target the Diffie-Hellman key exchange protocol but current known attacks on the latter involve computing a discrete logarithm anyway. It gives some interesting estimations on the time it takes to precompute discrete log over finite fields, and then to perform individual discrete logs. You should look at it! $\endgroup$ – Geoffroy Couteau May 18 '16 at 2:09
  • $\begingroup$ I have looked at it and it does not explicitly state $(\log ^cp)$ estimates post pre-computation steps. $\endgroup$ – T.... May 18 '16 at 4:07
  • $\begingroup$ Sure, and I'm now pretty convince that this step is not $O(\log^c p)$, but $L(1/3)$ as the others. The point of those articles is just that for practical parameters corresponding to everyday crypto, this last step can nevertheless be executed within a very small amount of time. $\endgroup$ – Geoffroy Couteau May 18 '16 at 7:49
1
$\begingroup$

No, it will not get easier and this is easy to see. Since p is public, everybody can make arbitrary many instances of a DL system with that p. You cannot diminish complexity by that means. If you could, such a scheme would bem consideed as broken or at least assigned a lower complexity in the first place.

$\endgroup$
  • $\begingroup$ Hardcoding the modulus $p$ in the definition of the protocol, hence constantly reusing the same $p$ throughout many instances of the protocol, is already considered "broken" in the theory community - or at least "a very bad habit". We have algorithms which are extremely fast at computing individual discrete logs given lot of precomputation time with $p$. $\endgroup$ – Geoffroy Couteau Jun 16 '16 at 14:58
  • $\begingroup$ Its neither broken nor bad habit. For instance, Nist Fips 186-4 explicitly allows sharing the donain parameters. $\endgroup$ – user27950 Jun 16 '16 at 17:13
  • $\begingroup$ That's why I said "in the theory community" $\endgroup$ – Geoffroy Couteau Jun 16 '16 at 17:17
  • $\begingroup$ could you please provide some precise argument or a papers from the 'theory community"? $\endgroup$ – user27950 Jun 17 '16 at 3:52
  • $\begingroup$ I gave a link to a post by d $\endgroup$ – Geoffroy Couteau Jun 17 '16 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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