Is it safe to reveal an arbitrary EC point multiplied by a secret key?

We have a primary-order EC group. Need to perform a (sort-of) DH protocol, whereas the key is permanent, not a nonce (single-usage ephemeral key).

So we receive an arbitrary group element (EC point) from an untrusted party, and reveal it multiplied by the secret key.

Is it always safe to do that? I mean, can the attacker craft the EC point in some manner to extract some info about the key? We ensure that the EC point is indeed on the curve, and, as I mentioned, it's a primary-order group.

• I think you can deduce this from the fact that ephemeral-static DH would be extremely broken if this wasn't the case. If I remember correctly there is no other check on the ephemeral public key other than that it is on the curve. Sep 14 '21 at 9:59
• @MaartenBodewes: normally in DH the peer has no incentives to extract your nonce. Sep 14 '21 at 10:39
• @valdo: Your description lacks two important details: would adversaries be able to perform many (say $2^{24}$) queries? And would these be iterated queries, or not? That makes a difference, because $k$ iterated queries let one compute $(d^{k+1})\,G$ where $d$ is a private key and $d\,G$ is a known public key, whereas $k\ge1$ pre-established queries would allow to compute $(d^2)\,G$ but not $(d^j)\,G$ for $j\ge3$ regardless of $k$. Independently: if the result of DH (before key derivation function) became public, then adversaries in ephemeral DH would be about in the position you describe.
– fgrieu
Sep 14 '21 at 11:55
• @valdo: if $k$ divides $p-1$ and the adversary has $G, d\,G, (d^k)\,G$, then according to my reading of the summary of Jung Hee Cheon's Security Analysis of the Strong Diffie-Hellman Problem (in proceedings of Eurocrypt 2006), there's an attack $\sqrt k$ times faster than Baby Step/Giant Step to recover $d$. As in the summary the attack requires impractically much memory, but so does BSGS, yet collision search solves that, and allows distribution; so it could get practical. Note: I should not get the credit for coming with this idea for this question.
– fgrieu
Sep 14 '21 at 15:39
• @fgrieu: thanks a lot! This is an excellent point. Good to know. I believe in my particular case this is still fine. Practically the adversary can invoke this protocol several millions of times, perhaps even billions, but not trillions. We're talking about p order of 2^256. So the complexity of the attack is reduced by like 30/2 = 15 bits. from 128 bits to something like 113 bits. Still good enough for our particular case. Sep 14 '21 at 16:12

Assuming that by “primary order” you mean “prime order”, this is called the static Diffie-Hellman problem, and there are some known attacks against it. The main ones to consider off the top of my head would be:

• the Cheon DLP with auxiliary inputs attack: there are several variants, but for example if the prime order $$p$$ of your elliptic curves satisfies that $$d$$ is a divisor of $$p-1$$, then an attacker making many queries can solve the discrete log problem in time $$\widetilde{O}(\sqrt{p/d} + \sqrt{d})$$, which in the worst case $$d = \Theta(p^{1/2})$$ is $$\widetilde{O}(p^{1/4})$$. This could be pretty bad in principle, but there are various reasons why the attack is not extremely threatening in this setting. Firstly, due to the attack's memory requirements and the fact most values of $$p$$ would be fairly far from the worst case, it's likely to be hard to mount in practice in most scenarios. Secondly, if $$\alpha$$ is the secret key, the attacker needs to somehow obtain both $$\alpha G$$ and $$\alpha^d G$$ for $$G$$ the group generator, and the only way to do so seems to be $$d$$ sequential adaptive queries $$G \to \alpha G \to \alpha^2 G \to \cdots \to \alpha^d G$$. This is a lot to expect from the oracle, and since it takes time $$O(d)$$, this reduces the optimal $$d$$ to $$\Theta(p^{1/3})$$ and increases the resulting complexity to $$\widetilde{O}(p^{1/3})$$ (assuming again that $$p-1$$ has the required form). There aren't many settings in which the oracle would answer $$2^{85}$$ queries from the adversary. This is why the Cheon attack is usually more relevant in settings where group elements of the form $$\alpha^j G$$ are readily available as public key material, rather than obtained using sequential queries;

• the Granger extension field attack if you happen to be using curves over extension fields of degree $$\geq 3$$ (which is most likely not the case).

• I don't see why the Cheon attack that you mention would not work to a degree, when the question uses iterated queries, and $p-1$ has a moderate prime factor.