Alice, Bob, and Carlos want to agree on a common key (for a symmetric cryptosystem). All communications among them are public. If there were only two people, Diffie-Hellman could be used. A slight extension of this procedure works for three people:

1. Alice, Bob, and Carlos agree on a large prime $p$ and a primitive root $\alpha$.

2. Alice chooses a secret integer $a\text{,}$ Bob chooses a secret integer $b\text{,}$ and Carlos chooses a secret integer $c$.

3. Alice computes $A\equiv {\alpha }^a(\text{mod}p)\text{,}$ Bob computes $B\equiv {\alpha }^b(\text{mod}p)\text{,}$ and Carlos computes $C\equiv {\alpha }^c(\text{mod}p)$.

4. Alice sends $A$ to Bob, Bob sends $B$ to Carlos, and Carlos sends $C$ to Alice.

5. Alice computes $A^{\prime }\equiv C^a\text{,}$ Bob computes $B^{\prime }\equiv A^b\text{,}$ and Carlos computes $C^{\prime }\equiv B^c\text{.}$

6. Alice sends $A^{\prime }$ to Bob, Bob sends $B^{\prime }$ to Carlos, and Carlos sends $C^{\prime }$ to Alice.

7. Alice computes $A^{\prime \prime }\equiv {C^{\prime }}^a\text{,}$ Bob computes $B^{\prime \prime }\equiv {A^{\prime }}^b\text{,}$ and Carlos computes $C^{\prime \prime }\equiv {B^{\prime }}^c\text{.}$ Note that $A^{\prime \prime }=B^{\prime \prime }=C^{\prime \prime }\equiv {\alpha }^{abc}(\text{mod}p)\text{.}$

8. Alice, Bob, and Carlos use some agreed-upon method to obtain keys from $A^{\prime \prime }\text{,}{B}^{\prime \prime }\text{,}{C}^{\prime \prime }\text{.}$ For example, they could use some standard hash function and apply it to ${\alpha }^{abc}(\text{mod}p)\text{.}$

This protocol could also be used with $p$ and $\alpha$ replaced by an elliptic curve $E$ and a point $P_0\text{,}$ so Alice computes $a{P}_0\text{,}$ etc., and the final result is $abc{P}_0\text{.}$

In 2000, Joux showed how to use pairings to obtain a more efficient protocol, one in which there is only one round instead of two:

1. Alice, Bob, and Carlos choose a supersingular elliptic curve $E$ and a point $P_0\text{,}$ as in Section 22.1.

2. Alice chooses a secret integer $a\text{,}$ Bob chooses a secret integer $b\text{,}$ and Carlos chooses a secret integer $c\text{.}$

3. Alice computes $A=a{P}_0\text{,}$ Bob computes $B=b{P}_0\text{,}$ and Carlos computes $C=c{P}_0\text{.}$

4. Alice makes $A$ public, Bob makes $B$ public, and Carlos makes $C$ public.

5. Alice computes $\tilde{e}(B\text{,}C{)}^a\text{,}$ Bob computes $\tilde{e}(A\text{,}C{)}^b\text{,}$ and Carlos computes $\tilde{e}(A\text{,}B{)}^c\text{.}$ Note that each person has computed $\tilde{e}(P_0\text{,}{P}_0{)}^{abc}\text{.}$

6. Alice, Bob, and Carlos use some agreed-upon method to obtain keys from $\tilde{e}(P_0\text{,}{P}_0{)}^{abc}\text{.}$ For example, they could apply some standard hash function to this number.

The eavesdropper Eve sees $E$ and the points $P_0\text{,}a{P}_0\text{,}b{P}_0\text{,}c{P}_0$ and needs to compute $\tilde{e}(P_0\text{,}{P}_0{)}^{abc}\text{.}$ This computation is called the Bilinear Diffie-Hellman Problem. It is not known how difficult it is. However, if Eve can solve the Computational Diffie-Hellman Problem (see Section 10.4), then she uses $E\text{,}{P}_0\text{,}a{P}_0\text{,}b{P}_0$ to obtain $ab{P}_0$ and computes $\tilde{e}(ab{P}_0\text{,}c{P}_0)=\tilde{e}(P_0\text{,}{P}_0{)}^{abc}\text{.}$ Therefore, the Bilinear Diffie-Hellman Problem is no harder than the Computational Diffie-Hellman Problem.

Joux’s result showed that pairings could be used in a constructive way in cryptography, rather than only in a destructive method such as the MOV attack, and this led to pairings being considered for applications such as those in the next few sections. It also meant that supersingular curves again became useful in cryptography, with the added requirement that when a curve mod $p$ is used, the prime $p$ must be chosen large enough that the classical discrete logarithm problem (solve ${\alpha }^x\equiv \beta (\text{mod}p)$ for $x$) is intractable.