Patent ID: 8238550
Filing Date: 2012-08-07
Classification: G06F,H04L

Abstract:
1. 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 as a non-degenerate bilinear map 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 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 a substitution unit which is configured to perform substitution operations n←x a first arithmetic operation unit which is configured to calculate l 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 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