Patent ID: 8477934

Claim:
A pairing computation device, wherein an elliptic curve is given as y 2 =x 3 +ax+b, aεF p , bεF p , letting k be an embedding degree, E be an additive group constituted of rational points on the pairing enabled elliptic curve defined over an extension field F p k , E[r] be a set of rational points having a prime order r, and φ p be a Frobenius endomorphism, a pairing e is defined using G 1 =E[r ]∩Ker(φ p −[1]), G 2 =E[r ]∩Ker(φ p −[p]), as a non-degenerate bilinear map e:G 1 ×G 2 →F* p k /( F* p k ) r , the pairing computation device comprising a CPU which computes the pairing e(S,Q), by letting SεG 1 , QεG 2 , χ be a given integer variable, and F be a rational function which is calculated using Miller's algorithm with respect to multi-pairing (MMA), wherein the order r and a trace t of the Frobenius endomorphism φ p are specified preliminarily according to the embedding degree k using the integer variable χ, and the CPU includes: an input unit which inputs the integer variable χ, the rational point S, and the rational point Q into respective predetermined registers; a computation unit which computes F; a computation unit which computes a value of a straight line passing through given rational points at a rational point Q (x Q , y Q ); a computation unit which computes f′ χ, S (Q) using said F and said value ; and a computation unit which computes the pairing e(S,Q) using said f′ χ, S (Q) as [F1] e ( S,Q )= f′ χ, S ( Q ) (p k −1)/r .