1
$\begingroup$

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?

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

Without pairings, there is no known single round tripartite key-exchange algorithm. However, it is possible to do it in two-rounds. For example, refer to the Burmester-Desmedt conference key protocol (http://www.cs.fsu.edu/~burmeste/eurocrypt_plus_proof.pdf) which in fact works for an arbitrary number of users.

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

As a consequence, the most likely answer to your question is: no, it can't be done without pairings.

Improve this answer
$\endgroup$

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.