Can one generalize the Diffie-Hellman key exchange to three or more parties?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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:

And this is how man_in_the_middle attack will look like: