Is the additive discrete Logarithm problem always easy in Fields?

Question

While thinking about additive DH key exchanges, I somehow had the idea that additive DH key exchange may always be easy to break, if we are in a field.

So here's (directly) the question:
In any finite field, is the additive discrete logarithm and / or the computational diffie-hellman problem always easy?

Here's some more info on the details:

• It can safely be assumed that doing addition and multiplication is fast
• The additive discrete logarithm problem in a field $(\mathbb F,+,\cdot)$ is to find the smallest $k\in\mathbb Z^+$ such that such that $Q=k\odot P$ holds for given $Q,P\in\mathbb F$, where $\odot$ denotes repeated addition of an element to itself k-times (as usual).
• If solving these problems isn't always easy, I'd also be interested whether there are certain properties of the field that would make it easy.

Answer 1

I will call the field elements "points" (as an analogy with elliptic curves). We can thus add points together and multiply points together. We can also multiply a point with an integer with a double-and-add algorithm (which will be reasonably efficient), and, similarly, raise a point to some integer power with a square-and-multiply algorithm.

Your additive Diffie-Hellman thus looks like this:

• There is a conventional base point $G$.
• The two parties select random integers $a$ and $b$ respectively, and compute $aG$ and $bG$ (point $G$ multiplied by an integer), that they send to each other.
• They then both compute the common secret $a(bG) = b(aG) = abG$.

The attacker's goal is to find that secret.

Now if the field's order is a known integer $q$ then the attacker has it easy:

$$ (aG)(bG)(G^{q-2}) = abG^q = abG $$

Note that while this breaks Diffie-Hellman in that specific context, this does not mean that the attacker can break Discrete Logarithm per se.

---

If the field order is not known, then things become more interesting. What the equation above basically says is that the attacker, by multiplying the observed points $aG$ and $bG$, gets $abG^2$, and he wants $abG$, so what he needs is to multiply that value by $1/G$. So the problem really is: if the field order is not known, then can the attacker compute the inverse of the base point?

If $\mathbb{F}$ is a field, then its order $q = p^f$ for a prime $p$ and an integer $f$; $p$ is the field characteristic. For any point $X$ in $\mathbb{F}$, we have $pX = 0$. Thus, the additive order of $G$ is necessarily $p$ (the integers $a$ and $b$ are really integers modulo $p$). For the DH problem to be interesting, we must thus assume that $p$ is relatively large (and therefore odd). Correspondingly, $f$ must be rather small, otherwise the field elements will be unwieldy (very large in RAM). For instance, if $p$ is at least 200 bits in length (for "100-bit security" in DH) and field elements fit in 10000 bits when encoded, then $f$ can be no more than 50.

Therefore, if the group additive order ($p$) is known, then the attacker can exhaustively try successive values of $f$ (starting from 1), each time assuming $q = p^f$ and then trying to compute the inverse of $G$ as $1/G = G^{q-2}$.

If $p$ is not known either, then we are in a mythical "generic field" which is like the "generic group" but with two operations, and then I think that DH in the additive group would be fairly safe. The only problem here is that there is no proof that a generic field can exist at all (just like the generic group, because it would imply all sorts of things such as $P \neq NP$), and I have no idea how to build a plausible candidate. For generic groups, elliptic curves are one of our best approximations, and yet we know more about them than just having an addition on them (indeed, we can compute curve orders with Schoof's algorithm).

Summary: to make the additive DH safe, you would need at least your finite field to be such that its order and its characteristic (which is the additive order of your DH group) are totally unknown, and that seems to be a lot to ask for.

Answer 2

Since you ask whether the DL is always easy in any finite field, here is a perhaps silly view.

Let $E$ be some elliptic curve of prime order $p$, chosen carefully such that the DLP is hard. Let $P\in E$ be an arbitrary point other than $\mathcal{O}$, necessarily of prime order. Now consider the following straightforward map $$E\rightarrow \mathbb{Z}_p$$ by $Q\mapsto n$, where $n$ is such that $Q=nP$. It should be easily checked that this is a group homomorphism, and in fact an isomorphism. Using this, we can define a multiplication on $E$. That is, for $Q_1,Q_2\in E$, such that $Q_1=n_1P$ and $Q_2=n_2P$, we define $Q_1\cdot Q_2 = n_1n_2P$. It should be easily checked that by this multiplication $E$ becomes a field (which additive group isomorphic to $\mathbb{Z}_p$, and multiplicative group isomorphic to $\mathbb{Z}_p^*$). In other words, $E$ can be thought of as isomorphic to the field $\mathbb{F}_p$.

Thus solving the additive DLP in $\mathbb{F}_p$, if represented this way, becomes hard, as it is reduced to solving the DLP on $E$.