Problem 1:

Input: p, g,h.

Output: x such that g^x=h mod p

Problem 2:

Input: h.

Output: x such that g^x=h mod p for some fixed cyclic group Zp with generator g.

I think NSA may have P/poly algorithm for Problem 2.

What does it mean to have a P/poly algorithm for Problem 1?

Which of Problem 1 and Problem 2 is correct discrete log problem and which one if has P/poly algorithm would make you consider Discrete log is in P/poly?

Is Problem 1 the discrete log problem and problem 2 the diffie hellman problem or vice versa?

]]>Discrete logarithm in Z/n^* is pretty much the same as factoring n plus discrete logarithm in the multiplicative groups of the prime power factors of n. Factoring is the reduction step and this doesn’t really relate discrete logarithm to anything other than discrete logarithm.

]]>[1] Eric Bach, “Discrete Logarithms and Factoring”, technical report (1984). [I’d give you direct links but your blog software hates me when I do that.]

]]>https://support.globalsign.com/customer/portal/articles/1995283-ecc-compatibility

]]>See: http://arxiv.org/abs/1003.5461

In particular, see remark 7: “A great algorithmic advantage of the approach of Schnorr over that of Adleman is that the choice of the basis can be essentially independent of the number N.”

]]>Good points all, especially regarding Pocklington.

I’m not sure the problem of p-1 needing to not have too many small factors is that serious though: just take p-1 and try to factor it using naive division for small primes. If nothing turns up other than the 2 factor out to a fairly large size then you are good to go, but I’m enough on the theoretical end that I’m probably missing something here.

I agree with you that in that context 4096 would probably be an overreaction, especially because actual bandwith starts mattering.

I do think there’s another issue that hasn’t been touched upon that is a cause for (slight) concern: if everyone is producing their own primes then people need more random bits. Also, as long as one is reusing the same prime even for a single server, it makes the pre-computation type attack still somewhat viable.

]]>