Patent ID: 8238550

Claim:
A pairing computation device, wherein an elliptic curve equation is given as y 2 =x 3 +ax+b, aεF q , bεF q , q is a prime number greater than 3, letting an embedding degree be 2h-th degree, h is a natural number, E be an additive group constituted of rational points on a pairing-enabled elliptic curve defined over F q 2h , E[r] be a set of rational points of prime order r, and φ q be a Frobenius endomorphism, an Ate pairing e is defined, using G 1 =E[r ]∩Ker(φ q −[1]) G 2 =E[r ]∩Ker(φ q −[q ]), as a non-degenerate bilinear map e:G 2 ×G 1 →F* q 2h /( F* q 2h ) r , letting PεG 1 , QεG 2 , and letting s=t−1 using a trace t of the Frobenius endomorphism φ q , and using a Miller function f s,Q (•), the Ate pairing e(Q,P) is computed as e ⁡ ( Q , P ) = f s , Q ⁡ ( P ) q 2 ⁢ h - 1 r , [ E1 ] the pairing computation device characterized by comprising: in order to perform an arithmetic operation of a rational function which is required to derive f s,Q (P) on a proper subfield by a twist curve of E(F q h ), that is, E′(F q h ):y 2 =x 3 +av −2 x+bv −3 using vεF q h which is a quadratic non-residue element and becomes 1 by an exponentiation of f s,Q (P) to a power of (q 2h −1)/r, an input unit which is configured to receive inputs of said s=t−1, P which satisfies PεE(F q ), and Q′ which satisfies Q′εE′(F q h ); a substitution unit which is configured to perform substitution operations n←x p v −1 , m←y p v −3/2 with respect to coordinates of the rational point P (x p ,y p ) and to perform substitution operations f←1, T′←Q′; a first arithmetic operation unit which is configured to calculate l T,T (x p ,y p )v −3/2 as l T′,T′ (n,m), instead of calculating l T,T (x p ,y p ) which is a value substituted by coordinates (x p ,y p ) of the rational point P in the left hand side of an equation l T,T (x,y)=0 of a tangent line passing through the rational point T, and to perform a substitution operation f←f 2 ·l T′,T′ (n,m); a second arithmetic operation unit which is configured to perform a substitution operation T′←2T′; a third arithmetic operation unit which is configured, when a value of a predetermined bit of s in binary representation is 1, to calculate l T,Q (x p ,y p )v −3/2 as l T′,Q′ (n,m), instead of calculating l T,Q (x p ,y p ) which is a value substituted by coordinates of the rational point P in the left hand side of an equation l T,Q (x,y)=0 of a straight line passing through the rational points T and Q, and to perform a substitution operation f←f·l T′,Q′ (n,m); a fourth arithmetic operation unit which is configured, when a value of the predetermined bit of s in binary representation is 1, to perform a substitution operation T′←T′+Q′; and a fifth arithmetic operation unit which is configured to perform an exponentiation operation to the power of (q 2h −1)/r.