Pairings and Three-Party Diffie-Hellman

In the last ten years, pairings have served as the basis for many cryptographic constructions and protocols for which there are no known alternative constructions or implementations that are efficient. Pairings were first used in the construction of Joux’s single-round three-party Diffie-Hellman protocol in 2000 as well as the Boneh-Franklin identity based encryption (IBE) scheme in 2001 . Since then, pairings, specifically in the form of bilinear maps, have been successfully applied to predicate encryption, attribute-based encryption, broadcast encryption, traitor tracing, group signatures, and many other schemes. In this post, I will describe pairings at a very high level and illustrate how they can be used for single-round tripartite Diffie-Hellman.

Definition. Let {\mathbb{G}_{1}} and {\mathbb{G}_{2}} be groups with prime order {p}, and let {g_{1}\in\mathbb{G}_{1}} and {g_{2}\in\mathbb{G}_{2}} be generators for their respective groups. A pairing is a mapping {e:\mathbb{G}_{1}\times\mathbb{G}_{2}\rightarrow\mathbb{G}_{T}} such that the following two properties hold:

  1. (Bilinearity). For all {a,b\in\mathbb{Z}_{p}^{*}}, {e(g_{1}^{a},g_{2}^{b})=e(g_{1},g_{2})^{ab}}.
  2. (Non-degeneracy). {e(g_{1},g_{2})\ne1_{T}}, where {1_{T}} denotes the identity element in {\mathbb{G}_{T}}.

While not strictly part of the definition, we often require that the pairing {e} be efficiently computable. In the cases that we will consider, the pairing is symmetric, that is, {\mathbb{G}_{1}=\mathbb{G}_{2}}. For notational simplicity, we will denote {\mathbb{G}_{1}} and {\mathbb{G}_{2}} with {\mathbb{G}}, and so the pairing {e} is a mapping from {\mathbb{G}\times\mathbb{G}\rightarrow\mathbb{G}_{T}}. From algebraic geometry, the Weil and Tate pairings are concrete examples of pairings that satisfy the above properties. In both these cases, the group {\mathbb{G}} is an elliptic-curve group and {\mathbb{G}_{T}} is a finite field. Thus, cryptographic schemes involving pairings can be instantiated using the Weil and Tate pairings, as appropriate.

Before we proceed to the construction of the single-round, three-party Diffie-Hellman protocol, we first review the standard two-party Diffie-Hellman protocol. First, let’s review the decisional Diffie-Hellman (DDH) assumption.

Definition (Decisional Diffie-Hellman Assumption). Let {\mathbb{G}} be a cyclic group of order {q}, and let {g\in\mathbb{G}} be a generator of {\mathbb{G}}. Then, sample {a,b} uniformly at random from {\mathbb{Z}_{q}}. Then, we say that the DDH assumption holds in {\mathbb{G}} if given the values of {g^{a},g^{b}}, it is difficult to distinguish the element {g^{ab}} from a random element in {\mathbb{G}}. More formally, we say that the distributions given by the tuples {(g^{a},g^{b},g^{ab})} and {(g^{a},g^{b},g^{r})} where {a,b,r} are randomly sampled from {\mathbb{Z}_{q}} are computationally indistinguishable.

With this in mind, we describe the standard two-party Diffie-Hellman protocol. We have two parties, say Alice and Bob, and their objective is to derive a shared key. To do so, Alice and Bob first agree on a cyclic group {\mathbb{G}} of order {q} with generator {g} such that the DDH assumption holds in {\mathbb{G}}. Then, Alice and Bob each choose random values {a,b\in\mathbb{Z}_{q}}. Then, Alice sends {g^{a}} to Bob and Bob replies with {g^{b}}. Finally, Alice computes, using her secret value {a} along with Bob’s message, the quantity {\left(g^{a}\right)^{b}=g^{ab}}. Similarly, observe that Bob can take his secret value {b} along with Alice’s message and compute {\left(g^{b}\right)^{a}=g^{ab}}. Thus, Alice and Bob have successfully agreed on a shared key. To argue that this is secure, consider an adversary that eavesdrops on Alice and Bob’s communication. From the messages that Alice and Bob exchange, the adversary learns the group {\mathbb{G}}, the generator {g}, and the value of {g^{a}} and {g^{b}}, and its objective is to construct the element {g^{ab}}. But this is impossible by the DDH assumption! The distribution {(g^{a},g^{b},g^{ab})} is computationally indistinguishable from the distribution {(g^{a},g^{b},g^{r})} for a random {r\in\mathbb{Z}_{q}}, or in other words, the values of {g^{a}} and {g^{b}} leak no information about the value {g^{ab}}.

Now, consider the scenario where we have three parties, Alice, Bob, and Carol, who all want to agree on a shared key. Is it possible to generalize the above construction? Turns out, the answer is yes, but we will need to rely on pairings. Observe that a pairing takes two arguments (say, messages) and outputs a new element in {\mathbb{G}_{T}}. Thus, we can naturally generalize the two-party Diffie-Hellman protocol from above. In the first round of the protocol, the three parties agree on a pairing {e:\mathbb{G}\times\mathbb{G}\rightarrow\mathbb{G}_{T}} along with a generator {g\in\mathbb{G}}. Let {q} denote the order of {\mathbb{G}}. We will examine what the necessary security assumption is shortly. As before, Alice, Bob, and Carol each choose a random element {a,b,c\in\mathbb{Z}_{q}}, respectively, and compute {g^{a},g^{b},g^{c}}, respectively. Each party broadcasts its value to the other two parties. To complete the protocol and derive a shared key, Alice takes Bob’s value {g^{b}} and Carol’s value {g^{c}} and computes, using her secret value {a}, the quantity {e(g^{b},g^{c})^{a}=e(g,g)^{abc}}, where we have exploited the bilinearity property of the pairing. Similarly, Bob and Carol takes their incoming messages, apply the pairing and raises the result to their secret value to obtain the shared key {e(g,g)^{abc}}. Thus, once again, we see that the three parties have succeeded in deriving a shared key.

The natural question now is what security assumption is needed to ensure that an eavesdropper cannot also learn the shared key. First, does the DDH assumption suffice in this case? It turns out that the answer is no. In fact, it is easy to see that the existence of a bilinear map on {\mathbb{G}} means that DDH cannot hold in {\mathbb{G}}. To see this, suppose there exists a pairing {e:\mathbb{G}\times\mathbb{G}\rightarrow\mathbb{G}_{T}}. In the DDH challenge, we are given the group {\mathbb{G}} with a generator {g} and three additional elements, {g^{a},g^{b},T\in\mathbb{G}} where either {T=g^{ab}} or {T} is random in {\mathbb{G}}. The goal is to decide whether {T=g^{ab}}. To do so, we apply the bilinear map. First, we compute {e(g^{a},g^{b})=e(g,g)^{ab}}. Next, we compute {e(g,T)}. Now, observe what happens when {T=g^{ab}}. Then, by bilinearity, {e(g,T)=e(g,g^{ab})=e(g,g)^{ab}=e(g^{a},g^{b})}. Conversely, if {T} was random, then {e(g,T)} will give us a random element in {\mathbb{G}_{T}} distinct from {e(g,g)^{ab}}. Thus, using the pairing, we can easily win the DDH challenge, and so, the standard two-party DDH assumption is not a valid security assumption when dealing with groups that admit bilinear maps.

Instead, we require a slight generalization of the DDH assumption in our setting. In particular, we would like to assume that given {g,g^{a},g^{b},g^{c}}, it should be difficult to compute {e(g,g)^{abc}}. More formally, given cyclic groups {\mathbb{G}} and {\mathbb{G}_{T}} of order {q}, a generator {g\in\mathbb{G}}, and a pairing {e:\mathbb{G}\times\mathbb{G}\rightarrow\mathbb{G}_{T}}, the following two distributions are computationally indistinguishable: {(g^{a},g^{b},g^{c},e(g,g)^{abc})} and {(g^{a},g^{b},g^{c},e(g,g)^{r})} where {a,b,c,r} are drawn uniformly at random from {\mathbb{Z}_{q}}. We call this the Bilinear Diffie-Hellman (BDH) assumption. Observe that if BDH holds, then the three-party Diffie-Hellman protocol described above is secure in the sense that a passive eavesdropper cannot derive the shared key.