Bilinear Pairings and Three-Party Key Exchange

By Nicholas O’Brien

 

Diffie-Hellman Key Exchange is one of the most used algorithms in cryptography today. Much of its popularity can be attributed to its ease of implementation, efficiency, and helping symmetric encryption to be used across an insecure channel i.e. the internet. However, many people do not realize that Diffie-Hellman Key Exchange (DHKE) has a three-party equivalent (3DHKE). In fact, the idea of DHKE can be expanded for N-Party Key Exchange. The problem is that the run time of the algorithm grows with N at a superlinear rate. Typically, this is not an issue as very few people need to do a 3DHKE let alone a 15DHKE. Nonetheless we should at least try to find a better method to agree on a shared key between three parties. In comes Bilinear Pairings! A Bilinear Pairing is a mapping that takes elements from two Elliptic Curve Group sand maps them to a singular multiplicative group. Further the mapping must have the following properties:

 

  1. (bilinearity) e(R+S, T) = e(R,T)e(S,T) and e(R,S+T) = e(R,S)e(R,T)
  2. (non-degenerate) e(P, P) != 1
  3. (feasibility) e must be able to be computed efficiently

 

The first property is our prime interest. It states that operations we do in the elliptic curve groups will have natural consequences when we map to the multiplicative group. The second property is simply telling us we do not want trivial maps. Clearly, if we create a map that sends all pairs to 1 then bilinearity would hold, but that’s not useful for us so we want maps besides that one. Lastly, we want the mapping to be efficient. If it takes 2 minutes to compute a single mapping, then what use would the mapping serve in real life applications?

 

One of the most popular Bilinear Pairings is the Reduced Tate Pairing. To understand how this Pairing works we must first begin with topic of Divisors. And no, I am not referencing those integer divisors ;). So, a divisor is a multiset of points on an elliptic curve denote like so

1

Where all but finitely many nP are 0. Remember! It is a multiset and not a summation. A cool note about divisors is that for all divisors on an elliptic curve they form a group. Unsurprisingly, we call this group the Divisor Group. Next, we define the Degree of a Divisor (Deg(D)) to be the sum of all the nP. Additionally, the support of a divisor (Supp(D)) is defined as the set of points where nP is not 0. Some examples are shown below.

2

Moving onto an advanced topic, there are also Divisors of functions. These are defined as

3

Where ordp(f) is the multiplicity of the function at the point on the elliptic curve. The Divisors of all functions will always be degree 0 as the multiplicity at O being always equal to the sum of multiplicities of all other points. All divisors of functions as also called principal divisors. Principal divisors have another cool property to them. If instead of a multiset you treat the divisor as an equation in the elliptic curve group and the result is O then the divisor is principal. The last definition we need is the equivalence relation of divisors. We say that two Divisors are equivalent (D1 ~ D2) if there exists a function f if

D1 = D2 + (f)

The next question you may have is how do you find such an f? Fortunately, we do not need to! Simply bring D2 over to the other side and get

D1 – D2 = (f).

So, all we have to do is prove D1 – D2 is principal! Easy. Now we can define the Reduced Tate Pairing 😀 Let q be a prime, k be an integer, E be an Elliptic Curve, Fq^k be a finite field, P ∈ E(Fq^k)[r], f be a function whose divisor (f) = r(P) – r(O), Q ∈ E(Fq^k) be any representative in any equivalence class in E(Fq^k)/rE(Fq^k), and DQ be a degree zero divisor defined over Fq^k that is equivalent to (Q)−(O) and Supp(DQ) is disjoint from Supp((f)). Then we define the Reduced Tate Pairing to be

4

Although the proof is rather dense, it can be shown that Tr does meet all the qualifications of a Bilinear Pairing.

 

Now, let us return to the classical DHKE. We know in the regular DHKE there are public parameters p and g. The prime p is the modulus and g is a generator of . The key exchange takes place as follows:

Screen Shot 2018-05-10 at 3.05.29 PM

Then Alice and Bob use some type of Key Derivation Function (KDF) with  as the input to get the shared key. This process is as secure as the discrete logarithm problem. Now when we extend this to 3DHKE it follows naturally as

Screen Shot 2018-05-10 at 3.05.36 PM

Then as  our three heroes can use a KDF to generate a shared secret key. Now we need to discuss the Bilinear Pairing Three Party Key Exchange (BPKE). In this system, the public parameters are P, Q, e, E1, and E2. Here E1 and E2 are Elliptic Curve Groups that P and Q are points in respectively, and e is our map. The main property we are going to use is bilinearity. Observe the flow below

Screen Shot 2018-05-10 at 3.05.53 PM

The astute reader will see that there is more than one “Step 2” for each person. This is because these operations can be done in parallel! Also take note that we can do “Step 3” from the bilinearity property! The only question that remains is which Three Party Key Exchange (3PKE) is faster. Fortunately, there are libraries that help us to test this. Even using our amazing Reduced Tate Pairing 😉

15

The Golang script I have a supplied will run both 3PKEs and find their average run time (from a single user perspective with no network lag) over the course of 200 tests. Running this on my 2015 Macbook gives an output of

16

Overall it appears that there is a slight advantage with the Pairing Key Exchange.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s