What Is Joux's Weil Pairing Key Exchange? Bilinear Forms, Distortion Maps, and the Decisional Diffie-Hellman Problem

Why three-party key exchange is hard

Standard Diffie-Hellman is a two-party protocol. Given a public elliptic-curve generator point P, Alice and Bob exchange aP and bP, and each computes a(bP) = b(aP) = abP to arrive at the shared secret abP. Naively extending this to three parties (Alice, Bob, and Carol) usually requires multiple rounds of communication -- for instance, having two parties first establish a shared key and then using it to exchange a key with the third.

In 2000, Antoine Joux showed in "A One Round Protocol for Tripartite Diffie–Hellman" that a bilinear map on elliptic curves called the Weil pairing makes it possible to perform three-party key exchange in exactly one round -- each party sends exactly one public value, just as in ordinary Diffie-Hellman. We cover the mathematical foundations of elliptic curve cryptography in more depth in a separate article.

The Weil pairing as a bilinear form

The Weil pairing takes two elements of the n-torsion subgroup E[n] of an elliptic curve E and returns an element of μ_n, the group of n-th roots of unity: it's a map e: E[n] × E[n] → μ_n. Three properties matter here:

Bilinearity: e(aP, bQ) = e(P, Q)^(ab). It behaves linearly in each argument.
Alternating: e(P, P) = 1. Pairing a point with itself is always trivial.
Non-degeneracy: if P is nonzero, there always exists some Q with e(P, Q) ≠ 1.

That bilinearity is the heart of Joux's protocol. It lets you perform something like multiplication on group elements (where discrete logarithms are hard to compute), while the exponents themselves get multiplied together in the process.

Why distortion maps are needed

There's a catch. Because of the alternating property (e(P,P)=1), if everyone only ever exchanges multiples of the same generator point P (i.e. aP, bP, cP), all of these lie in the same cyclic subgroup generated by P -- and some combinations of the pairing collapse to a trivial value, effectively wasting the non-degeneracy property. The tool used to get around this is the distortion map.

A distortion map φ efficiently sends a point P on E to a different point φ(P) that is linearly independent from P (i.e., not expressible as an integer multiple of P). Eric Verheul showed that such distortion maps can be explicitly constructed on supersingular elliptic curves, which lets a protocol use only multiples of a single generator P as its public values while still obtaining a non-trivial pairing e(P, φ(P)) ≠ 1.

How the key exchange is computed

Joux's protocol proceeds as follows. The elliptic curve E, generator point P, and distortion map φ are all assumed to be public.

Alice, Bob, and Carol each choose a secret integer: a, b, and c.
Each computes aP, bP, and cP, and publishes it (in one round) to the others.
Alice computes e(bP, φ(cP))^a.
Bob computes e(aP, φ(cP))^b.
Carol computes e(aP, φ(bP))^c.

By bilinearity, all three of these computations yield the identical value e(P, φ(P))^(abc). All three parties arrive at the shared secret e(P, φ(P))^(abc) using just one round of communication. The originality of this construction lies in achieving three-party key exchange -- something ordinary Diffie-Hellman-style protocols need multiple rounds for -- with the same communication cost as the two-party case.

A supplementary note: pairings solve the elliptic-curve DDH problem

Pairings come with an important side effect alongside enabling this key exchange: their relationship with the Decisional Diffie-Hellman problem (DDH).

Ordinary Diffie-Hellman's security rests on the Computational Diffie-Hellman problem (CDH) -- given P, aP, and bP, computing abP is assumed to be hard. The DDH problem is weaker: given P, aP, bP, and cP, just decide whether c ≡ ab (mod n).

On elliptic curves where a pairing is available, this DDH problem becomes efficiently solvable. Just compute and compare e(aP, bP) and e(cP, P). By bilinearity, e(aP, bP) = e(P, P)^(ab) and e(cP, P) = e(P, P)^c, and these are equal exactly when ab ≡ c (mod n). In other words, a pairing lets you solve DDH in polynomial time even while CDH remains hard.

Gap Diffie-Hellman groups: Groups with this property -- DDH is easy, but CDH remains hard -- are called Gap-DH groups in cryptography, and many pairing-friendly elliptic curves have exactly this property. Much of pairing-based cryptography (BLS signatures and others) actively exploits the fact that DDH is solvable, while basing its security instead on a stronger assumption: the Bilinear Diffie-Hellman Problem (BDHP) -- given P, aP, bP, and cP, computing e(P,P)^(abc) is assumed to be hard. Joux's key exchange protocol's security also rests on this bilinear variant of the assumption, not on ordinary CDH.

Summary

Joux's protocol (2000) uses the bilinearity of the Weil pairing to achieve three-party key exchange in the same one round Diffie-Hellman needs for two parties
The Weil pairing is a map e: E[n]×E[n]→μ_n satisfying bilinearity, the alternating property, and non-degeneracy
Because multiples of a single generator point alone don't yield a non-trivial pairing, a distortion map constructed on a supersingular elliptic curve is used to obtain a linearly independent point
Each participant combines the other two parties' public values with the distortion map to compute a pairing, and bilinearity guarantees everyone lands on the same shared key e(P,φ(P))^(abc)
Because pairings solve the elliptic-curve DDH problem in polynomial time, pairing-based cryptography grounds its security in the stronger Bilinear Diffie-Hellman Problem (BDHP) rather than ordinary CDH