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 and be groups with prime order , and let and be generators for their respective groups. A pairing is a mapping such that the following two properties hold:
- (Bilinearity). For all , .
- (Non-degeneracy). , where denotes the identity element in .
While not strictly part of the definition, we often require that the pairing be efficiently computable. In the cases that we will consider, the pairing is symmetric, that is, . For notational simplicity, we will denote and with , and so the pairing is a mapping from . From algebraic geometry, the Weil and Tate pairings are concrete examples of pairings that satisfy the above properties. In both these cases, the group is an elliptic-curve group and 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 be a cyclic group of order , and let be a generator of . Then, sample uniformly at random from . Then, we say that the DDH assumption holds in if given the values of , it is difficult to distinguish the element from a random element in . More formally, we say that the distributions given by the tuples and where are randomly sampled from 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 of order with generator such that the DDH assumption holds in . Then, Alice and Bob each choose random values . Then, Alice sends to Bob and Bob replies with . Finally, Alice computes, using her secret value along with Bob’s message, the quantity . Similarly, observe that Bob can take his secret value along with Alice’s message and compute . 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 , the generator , and the value of and , and its objective is to construct the element . But this is impossible by the DDH assumption! The distribution is computationally indistinguishable from the distribution for a random , or in other words, the values of and leak no information about the value .
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 . 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 along with a generator . Let denote the order of . We will examine what the necessary security assumption is shortly. As before, Alice, Bob, and Carol each choose a random element , respectively, and compute , 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 and Carol’s value and computes, using her secret value , the quantity , 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 . 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 means that DDH cannot hold in . To see this, suppose there exists a pairing . In the DDH challenge, we are given the group with a generator and three additional elements, where either or is random in . The goal is to decide whether . To do so, we apply the bilinear map. First, we compute . Next, we compute . Now, observe what happens when . Then, by bilinearity, . Conversely, if was random, then will give us a random element in distinct from . 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 , it should be difficult to compute . More formally, given cyclic groups and of order , a generator , and a pairing , the following two distributions are computationally indistinguishable: and where are drawn uniformly at random from . 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.