Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers 3

up vote 12 down vote accepted

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.

share|improve this answer
    
@imichaelmiers: Actually, for this we work we only need an abelian group - we then obviously work in a cyclic subgroup (the one generated by $g$) of it. Still, as it was worded, arguably "cyclic" is better (since a noncyclic group has no generator). Thanks for the edit! –  Paŭlo Ebermann Oct 23 '11 at 23:14
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
    
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 –  minar Jul 19 '13 at 18:11
    
why "Groups adequate for Diffie-Hellman with a computable pairing are not legion" is not legion meaning. –  Aria Aug 23 '13 at 9:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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