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:
Alice, Bob, and Carlos agree on a large prime and a primitive root .
Alice chooses a secret integer Bob chooses a secret integer and Carlos chooses a secret integer .
Alice computes Bob computes and Carlos computes .
Alice sends to Bob, Bob sends to Carlos, and Carlos sends to Alice.
Alice computes Bob computes and Carlos computes
Alice sends to Bob, Bob sends to Carlos, and Carlos sends to Alice.
Alice computes Bob computes and Carlos computes Note that
Alice, Bob, and Carlos use some agreed-upon method to obtain keys from For example, they could use some standard hash function and apply it to
This protocol could also be used with and replaced by an elliptic curve and a point so Alice computes etc., and the final result is
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:
Alice, Bob, and Carlos choose a supersingular elliptic curve and a point as in Section 22.1.
Alice chooses a secret integer Bob chooses a secret integer and Carlos chooses a secret integer
Alice computes Bob computes and Carlos computes
Alice makes public, Bob makes public, and Carlos makes public.
Alice computes Bob computes and Carlos computes Note that each person has computed
Alice, Bob, and Carlos use some agreed-upon method to obtain keys from For example, they could apply some standard hash function to this number.
The eavesdropper Eve sees and the points and needs to compute 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 to obtain and computes 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 is used, the prime must be chosen large enough that the classical discrete logarithm problem (solve for ) is intractable.