Three-party Diffie-Hellman in one shot

Elliptic curve Diffie-Hellman

Given a point P on an elliptic curve E, and a random number a, aP means to add P to itself a times, using the addition on E. The pointaP can be computed efficiently, even ifa is a very large number [1]. However, if E has a large number of points, and if a is chosen at random from a large range, then it is not practical to compute a given P and aP.

This is the elliptic curve version of the discrete logarithm problem, and its presumed difficulty is the basis of the security of Diffie-Hellman key exchange.

Two-party Diffie-Hellman

With two-party Diffie-Hellman key exchange, two parties, Alice and Bob, generate random private keys a and b respectively. They agree on a point P on an elliptic curve E. Alice computes aP and sends it to Bob. Simultaneously Bob computes bP and sends it to Alice. Then Alice can compute

a(bP) = (ab)P

and Bob can compute

b(aP) = (ba)P = (ab)P.

Then both Alice and Bob know a shared secret, the point (ab)P on E, but neither party has revealed a private key.

Three-party Diffie-Hellman

You could extend the approach above to three parties, say adding Carol, but this would require extra communication: Alice could send (ab)P to Carol, which she could multiply by her private key c to obtain abcP. Similarly, everyone else could arrive at abcP. Each person has to do a computation, send and receive a message, do another computation, and send an receive another message.

Joux [2] came up with a way to do Diffie-Hellman key exchange with three people and only one round of sending and receiving messages. The set up uses a pairing e( , ) of two elliptic curve subgroups, G₁ and G₂, as in the previous post. Fix generators P G₁ and Q G₂. Each party multipliesP andQ by their private key and sends the results to the other two parties.

Alice receivesbP from Bob andcQ from Carol. This is enough for her to compute

e(bP,cQ)^a = e(P, Q)^abc.

Similarly, Bob receivesaP from Alice andcQ from Carol, enabling him to compute

e(aP,cQ)^b = e(P, Q)^abc.

And finally, Carol receivesaP from Alice andbQ from Bob, enabling her to compute

e(aP,bQ)^c = e(P, Q)^abc.

So all three parties can compute the shared secret e(P, Q)^abc. but no party knows the other parties' private keys.

Footnotes

[1] If you want to multiply a point by 2¹⁰⁰, for example, you don't carry out 2¹⁰⁰ additions; you carry out 100 doublings. Of course not every positive integer is a power of 2, but every positive integer is the sum of powers of 2, i.e. it can be written in binary. So as you're doing your doublings, sum the terms that correspond to 1s in the binary representation of the number you're multiplying by.

[2] Antoine Joux. A One Round Protocol for Tripartite Diffie-Hellman. Journal of Cryptology (2004) 17: 263-276.

The post Three-party Diffie-Hellman in one shot first appeared on John D. Cook.