# 22.1 Bilinear Pairings

Although most of this chapter could be done in the context of cyclic groups of prime order, the primary examples of pairings in cryptography are based on elliptic curves or closely related situations. Therefore, for concreteness, we use only the following situation.

Let  be a prime of the form  where  is also prime. Let  be the elliptic curve  mod  We need the following facts about .

1. There are exactly  points on .

2. There is a point  such that . In fact, if we take a random point  then, with very high probability,  and  is a multiple of .

3. There is a function  that maps pairs of points  to th roots of unity for all integers . It satisfies the bilinearity property



for all . This implies that



for all points  that are multiples of . (See Exercise 2.)

4. If we are given two points  and  that are multiples of  then  can be computed quickly from the coordinates of  and .

5.  so it is a nontrivial th root of unity.

We also make the following assumption:

1. If we are given a random point  on  and a random th root of unity  it is computationally infeasible to find a point  on  with  and it is computationally infeasible to find  with .

# Remarks

Properties (1) and (2) are fairly easy to verify (see Exercises 4 and 5). The existence of  satisfying (3), (4), (5) is deep. In fact,  is a modification of what is known as the Weil pairing in the theory of elliptic curves. The usual Weil pairing  satisfies  but the present version is modified using special properties of  to obtain (5). It is generally assumed that (A) is true if the prime  is large enough, but this is not known. See Exercise 10.

The fact that  can be computed quickly needs some more explanation. The two points  satisfy  and  for some . However, to find  and  requires solving a discrete log problem, which could take a long time. Therefore, the obvious solution of choosing a random th root of unity for  and then using the bilinearity property to define  does not work, since it cannot be computed quickly. Instead,  is computed directly in terms of the coordinates of the points  .

Although we will not need to know this, the th roots of unity lie in the finite field with  elements (see Section 3.11).

For more about the definition of  see [Boneh-Franklin] or [Washington].

The curve  is an example of a supersingular elliptic curve, namely one where the number of points is congruent to 1 mod . (See Exercise 4.) For a while, these curves were regarded as desirable for cryptographic purposes because computations can be done quickly on them. But then it was shown that the discrete logarithm problem for them is only slightly more difficult than the classical discrete logarithm mod  (see Section 22.2), so they fell out of favor (after all, they are slower computationally than simple multiplication mod  and they provide no security advantage). Because of the existence of the pairing  they have become popular again.