Patent Document ID: 8625777
Application ID: 13060520
Patent Flag: 1

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 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 the order r and the trace t of the Frobenius endomorphism φ p are used as functions of an integer variable χ: a computation processor coupled to a memory and configured to compute a rational function f χ,Q (S); compute a value of a rational point S(x s , y s ) on a line passing through a predetermined rational point; compute a rational function f′ χ,Q (S) using computation results of the rational function f χ,Q (S) and the value of the rational point S(x s , y s ); and perform pairing computation by using the rational function f′ χ,Q (S) as: 
 e ( Q,S )=ƒ′ χ,Q ( S ) (p k −1)/r , the pairing computation being used in authentication of a digital group signature.