chapter  10
22 Pages

Choosing Parameters Sylvain Duquesne, Nadia El Mrabet, Safia Haloui, Damien Robert, and Franck Rondepierre

In this section, we explain how to construct or choose the parameters necessary to implement a pairing. We recall that in order to define a pairing, we need

• a finite field Fp, where p is a prime number, • an elliptic curve E defined over Fp, • a prime number r dividing card(E(Fp)), • the embedding degree k, i.e., the smallest integer such that r divides (pk − 1), • the set of points of r-torsion E[r] = Z/rZ× Z/rZ subdivided as G1 and G2. For the

implementation of the Tate pairing, G1 and G2 are defined by G1 = E(Fp)[r] and G2 = E(Fpk)[r] \ rE(Fp). For the (optimal) Ate, (optimal) twisted Ate we have that G1 = E(Fp)[r] ∩ Ker(pip − [1]) and G2 = E(Fpk)[r] ∩ Ker(pip − [p]), where pip is the Frobenius endomorphism on E.