9
$\begingroup$

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.
$\endgroup$
  • 2
    $\begingroup$ Note that adding $P$ to itself $k$ times isn't the same as using the field's multiplication operation. $\endgroup$ – CodesInChaos Nov 11 '16 at 19:39
  • $\begingroup$ @CodesInChaos OK, I see that my notation may be unclear / confusing here, lemme try and fix that. $\endgroup$ – SEJPM Nov 11 '16 at 19:45
  • $\begingroup$ @CodesInChaos Yes it is, because $k\cdot x = (k\cdot 1) \times x$, and it is natural to identify $k$ with $k\cdot 1$. $\endgroup$ – fkraiem Nov 12 '16 at 0:06
  • 1
    $\begingroup$ @CodesInChaos In a binary field, $2 = 0$. $\endgroup$ – fkraiem Nov 12 '16 at 11:43
  • 1
    $\begingroup$ @CodesInChaos I have no idea what you are saying, but the fact that the only way to meaningfully define 2 in a field of characteristic 2 is by 2 = 0. $\endgroup$ – fkraiem Nov 12 '16 at 12:06
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In the first part, do you mean that the multiplicative order (instead of additive order) is a divisor of $q-1$? $\endgroup$ – CurveEnthusiast Nov 11 '16 at 21:51
  • $\begingroup$ @CurveEnthusiast Mmh yes, that part was faulty (and confusing), I removed it. $\endgroup$ – Thomas Pornin Nov 11 '16 at 22:27
  • $\begingroup$ can I say that DH with an additive group is broken in a field, even though I can use the additive notation with a multiplicative group in a field? My intuition is yes I can, but these terms are confusing. $\endgroup$ – David 天宇 Wong May 28 at 1:34
4
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ The question assumes that the field operations are easy to compute, however. $\endgroup$ – fkraiem Nov 12 '16 at 0:23
  • $\begingroup$ True, that assumption does definitely not hold. On the other hand, scalar multiplication is efficient, which is essentially what we want for DH. So this would be a finite field in which additive DH can be efficiently computed, and the additive DLP is hard. Indeed not exactly what was asked for, but hopefully still interesting! $\endgroup$ – CurveEnthusiast Nov 12 '16 at 7:54
  • $\begingroup$ @fkraiem The question states "It can safely be assumed that doing addition and multiplication is fast" $\endgroup$ – CodesInChaos Nov 12 '16 at 11:35

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.