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 .
There are exactly points on .
There is a point such that . In fact, if we take a random point then, with very high probability, and is a multiple of .
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.)
If we are given two points and that are multiples of then can be computed quickly from the coordinates of and .
so it is a nontrivial th root of unity.
We also make the following assumption:
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 .
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.