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)


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.


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.