New answers tagged


Your reasoning is correct. Finding a collision will solve the discrete-logarithm problem. This is actually what Pollard's Rho does. If you can find $g^{x_1}h^{x_2} = g^{y_1}h^{y_2}$ then you can compute the discrete logarithm of $h$ $g^{x_1}h^{x_2} = g^{x_1 + kx_2}$ $x_1 + kx_2 = y_1 + ky_2$ $x_1 - y_1 = k(y_2 - x_2)$ $(x_1 - y_1)(y_2 - x_2)^{-1} = k$ ...


Yes, this logic works. You have shown that given the discrete log $x$ lets you easily find collisions. Now you need to show that any collision lets you extract the discrete log $x$ and then you are done (then you have shown the equivalence).


I will assume for simplicity that you're talking about the full multiplicative group of $F_p$ instead of a proper subgroup, thus there are no problems with $g^a+1$ (except when $g^a=p-1$ which can be trivially ruled out by comparing to $p$). The quantity $\log_g(g^a+1)$ is sometimes referred to as the Zech logarithm (strictly speaking, it is defined for ...


There is 3 kind of discrete log problem as you explained : Diffie-Hellman problem (Dlog): Pick $a \in \{1,\ldots,q\}$. Compute $A = g^a (mod\ p)$ Given $(p,q,g,A)$ find $a$. Assumed hard. Computational Diffie-Hellman problem (CDH) : Pick $a,b \in \{1,\ldots,q\}$. Compute $A = g^a (mod\ p)$ and $B = g^b (mod\ p)$ Given $(p,q,g,A,B)$ find $g^{ab}$. Note ...

Top 50 recent answers are included