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 − ) and G2 = E(Fpk)[r] ∩ Ker(pip − [p]), where pip is the Frobenius endomorphism on E.