Patent Document ID: 20110179471
Application ID: 13060520
Patent Flag: 0

Claim One:
1. A pairing computation device for defining pairing e by using: 
 G 1 =E[r]∩Ker (φ p −[1]), and 
 G 2 =E[r]∩Ker (φ p −[p ]), as a nondegenerate bilinear map: 
 e:G 2 ×G 1 →F* p k /(F* p k ) r , where: E is an additive group of rational points on a pairable elliptic curve defined over F p k with an embedding degree of k, and the curve equation is given by y 2 =x 3 +ax+b where a∈F p and b∈F p , E[r] is a set of rational points of a prime order r, and φ p is Frobenius endomorphism, computing pairing e(Q,S) where S∈G 1 and Q∈G 2 , and outputting a result of the computation, the pairing computation device comprising, where t is a trace of the Frobenius endomorphism φ p , instead of computing the pairing e(Q,S) by using a rational function f t−1,Q (S) calculated according to Miller's algorithm as: 
 e ( Q,S )=ƒ t−1,Q ( S ) (p k −1)/r , and   [Formula 2] the order r and the trace t of the Frobenius endomorphism φ p are used as functions of an integer variable χ: computation means for computing a rational function f χ,Q (S); computation means for computing a value of a rational point S(x s , y s ) on a line passing through a predetermined rational point; computation means for computing a rational function f′ χ,Q (S) using computation results of these computation means; and computation means for performing pairing computation by using the rational function f′ χ,Q (S) as: 
 e ( Q,S )=ƒ′ χ,Q ( S ) (p k −1)/r.   [Formula 3]