Diffie-Hellman public key exchange complexity

A main premise of the Diffie_Hellman key exchange is that calculating a public key from a private key is less complex than calculating a private key from a public key. What are those computational complexitites?

Private variables:

• $Xi\$ is the private key of user $i$.
• $Xj\$ is the private key of user $j$.

Public variables:

• $q\$ is a prime number > $1$
• $g\$ is a whole number, $1 <= g <= q-1$
• $Yi = g^{Xi} mod\ q\$ is user $i$'s public key.
• $Yj = g^{Xj} mod\ q\$ is user $j$'s public key.

The paper claims that the calculation of Y from X, as seen above, requires at most $2 * log_2(q)$ multiplications. Is that correct? It seems to me that the complexity is $X$ multiplications + 1 division. Unless $q$ is a power of $g$ in which case we know right away that the remainder $Y$ is $0$. How do we quantify the complexity here?

An eavesdropper, knowing the values of the public variables, calculates a private key $Xi$ like so:

$g^{Xi} mod\ q = Yi$

$\frac{g^{Xi}}{q} = n + \frac{Yi}{q}$

$g^{Xi} = qn + Yi$

$Xi = log_g(qn + Yi)$

Having two unknown variables ($Xi$ and $n$) and one equation, this equation should have infinitely many solutions. How can we define a computational complexity for calculating $Xi$ (or similarly $Xj$)?

The paper claims that a private key X can be calculated by an eavesdropper like this:

$X = log_g(Y)\ mod\ q$

It also claims that the complexity should be $q^{1/2}$ operations for carefully selected values of $q$. How is that so?

• "square and multiply". Note that computing $a^b$ from $a^{\lfloor b/2\rfloor}$ can be done in at most two multiplications – Hagen von Eitzen Oct 14 '17 at 17:53
• Can you please elaborate on how these principles help to solve the problems? – Vanilla Godzilla Oct 14 '17 at 17:58