Derive one public key from ECDH when the other and and the shared secret is known

Question

Suppose we have an elliptic curve Diffie-Hellman key exchange protocol, where Bob and Alice have public keys $pk_{Alice}= [sk_{Alice}]G$ and $pk_{Bob}= [sk_{Bob}]G$ ($[.]$ elliptic curve "exponentiation"). As usual, they computed the shared secret $s$ as the x-coordinate of $(x,y)= [sk_{Alice} sk_{Bob}]G$

Now Carol has access to $s$ as well as $pk_{Alice}$ and moreover knows a set of public keys $S_{pks}$, such that Bobs public key is in that set, i.e. $pk_{Bob}\in S_{pks}$.

Is it possible for Carol to find Bobs key in $S_{pks}$ (Assuming $S_{pks}$ contains more then just a single element of course)

Answer 1

Is it possible for Carol to find Bobs key in $S_{pks}$

This is a decisional Diffie-Hellman problem.

We can summary this problem as: "we're given the values $G, aG, abG$, and a series of values $c_1G, c_2G, ... c_nG$, can we recognize $c_iG = bG$"

We can reword the problem as "assuming $H = aG$, we're given the values $H, (a^{-1})H, bH$, can we recognize $c'_iH = (a^{-1}b)H$"; with this rewording, this is obviously a DDH problem.

Hence, this problem is possible if the DDH problem is tractable; that is, if we're in a pairing-friendly curve, or if the group order has small factors, or the group order is small enough (or you have a large quantum computer handy). If none of these are true, then it's believed hard.