22.1 Bilinear Pairings – Introduction to Cryptography with Coding Theory, 3rd Edition

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 p be a prime of the form 6q1,  where q is also prime. Let E be the elliptic curve y2x3+1 mod p. We need the following facts about E.

  1. There are exactly p+1=6q points on E.

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

  3. There is a function e˜ that maps pairs of points (aP0, bP0) to qth roots of unity for all integers a, b. It satisfies the bilinearity property

    e˜(aP0, bP0)=e˜(P0, P0)ab

    for all a, b. This implies that

    e˜(aP, bQ)=e˜(P, Q)ab

    for all points P, Q that are multiples of P0. (See Exercise 2.)

  4. If we are given two points P and Q that are multiples of P0,  then e˜(P, Q) can be computed quickly from the coordinates of P and Q.

  5. e˜(P0, P0)1,  so it is a nontrivial qth root of unity.

We also make the following assumption:

  1. If we are given a random point P on E and a random qth root of unity ω1,  it is computationally infeasible to find a point Q on E with e˜(Q, P)=ω and it is computationally infeasible to find Q with e˜(P, Q)=ω.

Remarks

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

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

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

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

The curve E is an example of a supersingular elliptic curve, namely one where the number of points is congruent to 1 mod p. (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 p (see Section 22.2), so they fell out of favor (after all, they are slower computationally than simple multiplication mod p,  and they provide no security advantage). Because of the existence of the pairing e˜,  they have become popular again.