# Three-way key exchange with elliptic curves without pairing

Assume that there are three users, each with their own secret key $d_i$ and the corresponding public key $Q_i = d_i \cdot P$, such that $Q_i$ is a point on an elliptic curve and $P$ is a base point on this elliptic curve.

Is $d_1 \cdot Q_2 \cdot Q_3$ equal to $d_2 \cdot Q_1 \cdot Q_3$ or $d_3 \cdot Q_1 \cdot Q_2$?

How can three users compute a shared key without knowing $d_1 \cdot Q_2$, $d_2 \cdot Q_1$, $d_3 \cdot Q_1$, $d_3 \cdot Q_2$, $d_2 \cdot Q_3$ and $d_1 \cdot Q_3$? The only things that each user knows are his own secret key $d_i$ and other users' public key $Q_1, Q_2, Q_3$. Can this be done without pairing?

• What do you mean by $Q_1\cdot Q_2$ ? There is no standard operation to multiply points of an elliptic curve. – minar Aug 23 '13 at 11:12
• Q1 = d1.P and Q2 = d2.P and Q3 = d3.P – star Aug 23 '13 at 11:23
• I got this. But what is $Q_1\cdot Q_2$ ? – minar Aug 23 '13 at 11:26
• If a (symmetric) pairing is available then $e(Q_1,Q_2)^{d_3}$ is a common key. – minar Aug 23 '13 at 11:55
• Then, there is no single-round protocol known. Use Burmester-Desmedt. – minar Aug 23 '13 at 12:00

This being said, would it be possible to find a protocol along the line you are suggesting? The key problem would be to define the product of two points $Q_1Q_2$ on an elliptic curve. Moreover, for your idea to produce a common key $d_1\cdot Q_2Q_3=d_2\cdot Q_1Q_3=d_3\cdot Q_1Q_2$, you would like this definition of the product to be both bilinear and non-degenerate. Thus, your definition of the product of two points would be some (possibly new) kind of pairing.
Moreover, if the product of two points $Q_1$ and $Q_2$ is again a point on the elliptic curve, you would have an (efficient) algorithm for the computational Diffie-Hellman in this group. From a security point of view, this is bad, because there are reductions that use such an algorithm to solve the discrete logarithm problem once the computational Diffie-Hellman becomes easy (For example see http://www.stanford.edu/class/cs259c/finalpapers/dlp-cdh.pdf).