We call an elliptic curve E(Fp) pairing-friendly if there is a prime factor of the groups order such that the Weil pairing is efficiently computable with respect to that prime factor. In real-world applications of pairing-friendly elliptic curves, the embedding degree is usually a small number like 2, 4, 6 or 12, and the number r is the largest prime factor of the curves order. Example 97. Consider curve E1,1(F5) from example 70. Since the only prime factor of the groups order is 3, we cannot compute the Weil pairing on this group using our definition of Millers algorithm. In fact, since G1 is of order 3, executing the algorithm will lead to a division by zero. Example 98. Consider the Tiny-jubjub curve TJJ_13(F13) from example 71 and its associated pairing groups from example 95: G1 = {O, (7, 2), (8, 8), (8, 5), (7, 11)} G2 = {O, (9t2 + 7,t3 + 11t), (9t2 + 7, 12t3 + 2t), (4t2 + 7, 5t3 + 10t), (4t2 + 7, 8t33 + 3t)}

Since we know from example 87 that the embedding degree of 5 id 4, we can instantiate the general definition of the Weil pairing for this example as follows: e(, ) : G1 G2 F 134 The first if-statement in Millers algorithm, implies that e(O, Q) = 1 as well as e(P, O) = 1 for all arguments P G1 and Q G2. In order to compute a non-trivial Weil pairing, we choose the argument P = (7, 2) G1 and Q = (9t2 + 7, 12t3 + 2t) G2. Invoking sage we get the following computation of the Weil pairing: sage: F13 = GF(13) sage: F13t.<t> = F13[] sage: P_MOD_4 = F13t(t^4+2) sage: F13_4.<t> = GF(13^4, name=t, modulus=P_MOD_4) sage: TJJF13_4 = EllipticCurve(F13_4,[8,8]) sage: P=TJJF13_4([7,2]) sage: Q=TJJF13_4([9*t^2+7,12*t^3+2*t]) sage: P.weil_pairing(Q,5) 7*t^3 + 7*t^2 + 6*t + 3

Example 99. Consider Bitcoins curve secp256k1 again. As we have seen in example 96, it is infeasible to compute elements from the pairing group G2 and as we know from example 93 it is moreover infeasible to do calculations in the extension field F pk. It follows that the Weil pairing is not efficiently computable and that secp256k1 is not pairing friendly. Exercise 84. Consider the curve alt_bn128 from example 73 and the generators g1 and g2 of G1[p] and G2[p] from exercise 83. Write a Sage program that computes the Weil pairing e(g1, g2). 5.5 Hashing to Curves Elliptic curve cryptography frequently requires the ability to hash data onto elliptic curves. If the order of the curve is not a prime number, hashing to prime order subgroups is of importance, 108 475 476 477 478 479 480 481 482 483 CHAPTER 5. ELLIPTIC CURVES

5.5. HASHING TO CURVES too and in the context of pairing-friendly curves, it is sometimes necessary to hash specifically onto the pairing group G1 or G2 as introduced in 5.4.3. As we have seen in section 4.1.7, some general methods are known for hashing into finite cyclic groups and since elliptic curves over finite fields are finite and cyclic groups, those methods can be utilized in this case, too. However, in what follows we want to describe some methods specific to elliptic curves that are frequently used in real-world applications.