47
$\begingroup$

Does anyone know how to do a Diffie-Hellman or ECDH key exchange with more than two parties?

I know how to do a key exchange between 2 parties, but I need to be able to have a key agreement between 3 or more parties.

$\endgroup$

4 Answers 4

48
$\begingroup$

The standard Diffie-Hellman key exchange algorithm (or family of algorithms) works in an cyclic group with generator $g$, and relies on

$$ {y_A}^{x_B} = (g^{x_A})^{x_B} = (g^{x_B})^{x_A} = {y_B}^{x_A}, $$

where $y_A$ and $y_B$ are publicly transmitted, while $x_A$ and $x_B$ remain private.

With three parties, we still have

$$((g^{x_A})^{x_B})^{x_C} = ((g^{x_A})^{x_C})^{x_B} = ((g^{x_B})^{x_A})^{x_C} = ((g^{x_B})^{x_C})^{x_A} = ((g^{x_C})^{x_B})^{x_A} = ((g^{x_C})^{x_A})^{x_B}. $$

As each party wants to let its own key private, each exponentiation needs to be done at different locations, which means some parties have to send their second-step results to the other parties.

One possible protocol could be the following:

  1. A, B, C each generate their private keys $x_A$, $x_B$, $x_C$.
  2. A, B, C each calculate $y_A = g^{x_A}$, $y_B = g^{x_B}$, $y_C = g^{x_C}$.
  3. A sends $y_A$ to B, B sends $y_B$ to C, C sends $y_C$ to A.
  4. A calculates $z_{CA} = {y_C}^{x_A}$, B calculates $z_{AB} = {y_A}^{x_B}$, C calculates $z_{BC} = {y_B}^{x_C}$.
  5. A sends $z_{CA}$ to B, B sends $z_{AB}$ to C, C sends $z_{BC}$ to A.
  6. A calculates $k_{BCA} = {z_{BC}}^{x_A}$, B calculates $k_{CAB} = {z_{CA}}^{x_B}$, C calculates $k_{ABC} = {z_{AB}}^{x_C}$.

The above equality means that the three parties now know a common secret $k_{ABC} = k_{CAB} = k_{BCA}$.

This obviously generalizes to more than three parties, but it needs one additional group exponentiation per participant more for each additional participant (i.e. in total $n^2$ exponentiations).

All of this works in all groups, so also in the elliptic curve groups (where this is usually written as point multiplication instead of exponentiation).

In practice it might be easier to exchange secret keys with some "hub" node, which then creates a common secret and sends it to each participant, like Dennis proposed in his answer.

$\endgroup$
5
  • $\begingroup$ what if there are 4 parties? should it be like A sends yA to B, B sends yB to C, C sends yC to D, D sends yD to A, D sends yD to B, and C sends Yc to A? $\endgroup$ Apr 6, 2018 at 1:39
  • $\begingroup$ @circusonfireee That looks too complicated. Everyone just needs to send one number to his "right" neighbor in each "sending" step (steps 3 and 5 in my example, you would have one more calculation step and one more sending step for four parties). $\endgroup$ Apr 6, 2018 at 21:29
  • $\begingroup$ Are there some examples implementation with openssl libraries? wiki.openssl.org/index.php/Elliptic_Curve_Diffie_Hellman I understand that we can create a shared secret bytes from a private key and a public key thanks to Key agreement process. But with n parties, how do we "transform" this shared secret to a new public key in order to compute a new shared secret? Thanks $\endgroup$ Nov 14, 2019 at 9:23
  • $\begingroup$ I've just created one available here: github.com/pyca/cryptography/issues/5064 $\endgroup$ Nov 18, 2019 at 9:10
  • $\begingroup$ I know this is old but I've ended up here when I was searching for how to do it. I've implemented this logic in JavaScript, for anyone interested, you can find it here: gist.github.com/saltimbanc/1fe0714afe6a00516c1dfde5f1295cdc (disclaimer, I'm a novice, make sure this implementation is secure before using it in production). $\endgroup$
    – Titus
    Oct 23, 2023 at 11:03
36
$\begingroup$

The really great thing about Diffie-Hellman is how light it is, network-wise: both parties send each other a single message; neither has to wait for the message from the peer before beginning to computing his own message.

If you can tolerate something heavier, you can have a look at what @Paŭlo describes; with $n$ participants, it requires $n-1$ messaging rounds (in each round, participants broadcast messages that they compute using the messages received during the previous round). There is actually another method which is actually both more efficient in the general case (2 messaging rounds for any $n$) and also more generic (it can be extended to any key-exchange protocol, not just Diffie-Hellman):

  • One participant ($P_1$) does a key-exchange with all the other participants, resulting in keys $K_2$, $K_3$... $K_n$ shared between $P_1$ and $P_2$, $P_3$... $P_n$, respectively.
  • $P_1$ generates a random key $K$ and encrypts it symmetrically with $K_2$, $K_3$... $K_n$.
  • $P_1$ broadcasts those $n-1$ symmetrically encrypted versions of $K$. Each of $P_2$, $P_3$... $P_n$ decrypts its own and gets $K$.

It still requires two messaging rounds.


There exists a protocol for three-party Diffie-Hellman key exchange with one messaging round. It was first described by Joux in 2000. It uses a pairing. Suppose that you have two groups $G_1$ and $G_2$ of prime order $p$, such that computational Diffie-Hellman is a hard problem in both (i.e. you can do a Diffie-Hellman key exchange in either $G_1$ or $G_2$, and it is secure), and such that there exist a bilinear map: \begin{eqnarray*} e : G_1 \times G_1 &\longrightarrow& G_2 \cr (P, Q) &\longmapsto& e(P, Q) \end{eqnarray*} such that:

  • if $e(P, Q) = 1$ then either $P = 1$ or $Q = 1$ or both (pairing is not degenerate);
  • for all $P$ and $Q$ from $G_1$, and all integers $a$ and $b$, $e(P^a, Q^b) = e(P, Q)^{ab}$ (pairing is bilinear).

Note that these properties imply that the pairing is symmetric ($e(P, Q) = e(Q, P)$). We call $g$ a generator of $G_1$ (any non-neutral element of $G_1$ will do, since the order $G_1$ is a prime: $G_1$ is cyclic).

If you have such objects, then three-party Diffie-Hellman in one messaging round goes like this:

  • $A$ chooses a random $a$ modulo $p$, and broadcasts $g^a$. Similary, $B$ and $C$ select random $b$ and $c$ and broadcast $g^b$ and $g^c$, respectively.
  • The shared key is $K = e(g^b, g^c)^a$, which $A$ can compute. Thanks to the bilinearity of the pairing, this is also equal to $e(g^a, g^c)^b$, which $B$ can compute, and to $e(g^a, g^b)^c$, which $C$ can compute.

Groups adequate for Diffie-Hellman with a computable pairing are not legion; but one can use supersingular elliptic curves with low embedding degree, and Weil or Tate pairings along with a distortion map. A good introduction on pairings over elliptic curves is Ben Lynn's PhD thesis; in his terminology, "type A" and "type B" curves are appropriate for three-party DH as described above.

Pairing mathematics are a bit complex (one level above basic elliptic curve maths, which are already one level above modular arithmetics as used in the original Diffie-Hellman). They require computing with fields which are quite larger than what is usually done with elliptic curves (we need integers modulo a 512-bit prime instead of a 160-bit prime, and some computation use a degree-2 extension field, hence 1024-bit field elements). Also, the advantage of having a single messaging round disappears if you need key confirmation (this really depends on the overall protocol). So three-party DH with pairings is not often used in practice. Pairings are a great tool for some more advanced protocols which involve three kinds of agents, in particular identity-based encryption and some protocols for electronic voting or digital cash.

For $n$-party Diffie-Hellman ($n \geq 4$) in one messaging round, one would need an $(n-1)$-linear "pairing"; I am not aware of any known candidate which achieves enough security while still being readily computable.

$\endgroup$
3
  • 1
    $\begingroup$ Since you answered, there has been some progress on proposing candidates for the multilinears maps needed for your last paragraph. See eprint.iacr.org/2012/610 $\endgroup$
    – minar
    Jul 19, 2013 at 18:11
  • $\begingroup$ why "Groups adequate for Diffie-Hellman with a computable pairing are not legion" is not legion meaning. $\endgroup$
    – Aria
    Aug 23, 2013 at 9:28
  • 2
    $\begingroup$ @aria - by legion, he means "plentiful" $\endgroup$ Aug 27, 2018 at 14:46
10
$\begingroup$

The easiest way I can think of:

As soon as $A$ has exchanged keys with $B$ and $C$, $A$ can randomly generate a password and communicate it to both $B$ and $C$.

$\endgroup$
1
$\begingroup$

This answer compleat "Paŭlo Ebermann" answer with a grafical view.

Let's show it for 4 parties: The public values are: g: generator.

Let's make it a bit more hard and assume that each of them can talk only to the next one:

P_0 -> P_1 -> P_2 -> P_3 -> (cycle) P_0 -> ... 

Assuming no "man_in_the_middle" attack, you can do this:

  1. Each participant chooes a secret random key: P_0: p_0, P_1: p_1, P_2: p_2, P_3: p_3
  2. Then each one of them P_i sends it key performing almost full cycle, ending at P_(i-1) which allows all of them to share the same key: p_0*p_1*p_2*p_3

This way: enter image description here

And this is how man_in_the_middle attack will look like: enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.