Pairing computation device, pairing computation method and recording medium storing pairing computation program

1. 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 .

2. A pairing computation method, 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 non-degenerate bilinear map

e:G 1 ×G 2 →F* p k /( F* p k ) r ,

an electronic computer which includes a CPU 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),

the order r and a trace t of the Frobenius endomorphism φ p being specified preliminarily according to the embedding degree k using the integer variable χ,

the pairing computation method comprising:

a step of inputting the integer variable χ, the rational point S, and the rational point Q into respective predetermined registers by causing the CPU of the electronic computer to function as an input unit;

a step of computing F by causing the CPU of the electronic computer to function as a computation unit;

a step of computing a value of a straight line passing through given rational points at a rational point Q(x Q , y Q ) by causing the CPU of the electronic computer to function as a computation unit;

a step of computing f′ χ, S (Q) using said F and said value by causing the CPU of the electronic computer to function as a computation unit; and

a step of computing the pairing e(S,Q) using said f′ χ, S (Q) as

[F2]

e ( S,Q )= f′ χ, S ( Q ) (p k −1)/r

by causing the CPU of the electronic computer to function as a computation unit.

3. A non-transitory computer recording medium storing a pairing computation program, 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 non-degenerate bilinear map

e:G 1 ×G 2 →F* p k /( F* p k ) r ,

the pairing computation program causes an electronic computer which includes a CPU to compute 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),

the order r and a trace t of the Frobenius endomorphism φ p being specified preliminarily according to the embedding degree k using the integer variable χ,

the pairing computation program causing the CPU of the electronic computer to function as:

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

[F3]

e ( S,Q )= f′ χ, S ( Q ) (p k −1)/r .

4. A pairing computation device, wherein an elliptic curve is given as y 2 =x 3 +b, bεF p , letting an embedding degree be 12, E be an additive group constituted of rational points on the pairing enabled elliptic curve defined over an extension field F p 12 , 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 12 /( F* p 12 ) 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, Z S be a set of rational points S and pS, Z Q be a set of rational points pQ and Q, and F 2χ,ZS (Z Q ) 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 using the integer variable χ as,

r (χ)=36 χ 4 −36 χ 3 +18 χ 2 −6 χ +1,

t (χ)=6 χ 2 +1,

and a representation of the integer variable χ using p 10 with p as a characteristic is

p≡( 2 χ −1) p 10 +2χ(modr(χ)) 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 first computation unit which computes F 2χ,ZS (Z Q );

a second computation unit which computes given rational points using 2 χ S and 2 χ pS which are calculated when computing said F 2χ,ZS (Z Q );

a third computation unit which computes a value at a rational point Q(x Q , y Q ) of a straight line passing through the given rational points;

a fourth computation unit which computes f′ χ, S (Q) using said F 2χ,ZS (Z Q ) and said value; and

a fifth computation unit which computes the pairing e(S,Q) using said f′ χ, S (Q) as

[F4]

e ( S,Q )= f′ χ, S ( Q ) (p 12 −1)/r .

5. The pairing computation device according to claim 4 , wherein

the second computation unit computes respective rational points −S, (2 χ −1)S, p 10 ((2 χ −1)S), −pS, (2 χ −1)pS, p 10 ((2 χ −1)pS) in order using previously obtained results,

the third computation unit respectively computes a value l 1 at a rational point Q(x Q , y Q ) of a straight line passing through rational points ((2 χ −1)S, −S), a value l 2 at the rational point Q(x Q , y Q ) of a straight line passing through rational points ((2 χ −1)pS, −pS), a value l 3 at the rational point Q(x Q , y Q ) of a straight line passing through rational points (p 10 ((2 χ −1)S), 2 χ S), and a value l 4 at the rational point Q(x Q , y Q ) of a straight line passing through rational points (p 10 ((2 χ −1)pS), 2 χ pS), and

the fourth computation unit computes f′ χ, S (Q) as

[F5]

f′ χ, S ( Q )={ F 2 χ ,Z S ( Z Q )·{ l 1 p ·l 2 } −1 } p 10 ·F 2 χ ,Z S ( Z Q )· l 3 p ·l 4 .

6. A pairing computation method, wherein an elliptic curve is given as y 2 =x 3 +b, bεF p , letting an embedding degree be 12, E be an additive group constituted of rational points on the pairing enabled elliptic curve defined over an extension field F p 12 , 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 12 /( F* p 12 ) r ,

an electronic computer which includes a CPU computes the pairing e(S,Q), by letting SεG 1 , QεG 2 , χ be a given integer variable, Z S be a set of rational points S and pS, Z Q be a set of rational points pQ and Q, and F 2χ,ZS (Z Q ) be a rational function which is calculated using Miller's algorithm with respect to multi-pairing (MMA),

the order r and a trace t of the Frobenius endomorphism φ p being specified using the integer variable χ as,

r (χ)=36 χ 4 −36 χ 3 +18 χ 2 −6 χ +1

t (χ)=6 χ 2 +1,

and a representation of the integer variable χ using p 10 with p as a characteristic being

p≡( 2 χ −1) p 10 +2 χ (modr(χ)),

the pairing computation method comprising:

an input step which inputs the integer variable χ, the rational point S, and the rational point Q into respective predetermined registers by causing the CPU of the electronic computer to function as an input unit;

a first computation step which computes F 2χ,ZS (Z Q ) by causing the CPU of the electronic computer to function as a first computation unit;

a second computation step which computes given rational points using 2χS and 2χpS which are calculated when computing said F 2χ,ZS (Z Q ) by causing the CPU of the electronic computer to function as a second computation unit;

a third computation step which computes a value at a rational point Q(x Q , y Q ) of a straight line passing through the given rational points by causing the CPU of the electronic computer to function as a third computation unit;

a fourth computation step which computes f′ χ, S (Q) using said F 2χ, ZS (Z Q ) and said value by causing the CPU of the electronic computer to function as a fourth computation unit ; and

a fifth computation step which computes the pairing e(S,Q) using said f′ χ, S (Q) as

[F6]

e ( S,Q )= f′ χ, S ( Q ) (p 12 −1)/r ,

by causing the CPU of the electronic computer to function as a fifth computation unit.

7. The pairing computation method according to claim 6 , wherein

the second computation step computes respective rational points −S, (2 χ −1)S, p 10 ((2 χ −1)S), −pS, (2 χ −1)pS, p 10 ((2 χ −1)pS) in order using previously obtained results,

the third computation step respectively computes a value l 1 at a rational point Q (x Q , y Q ) of a straight line passing through rational points ((2 χ −1)S, −S), a value l 2 at the rational point Q (x Q , y Q ) of a straight line passing through rational points ((2 χ −1)pS, −pS), a value l 3 at the rational point Q (x Q , y Q ) of a straight line passing through rational points (p 10 ((2 χ −1) S), 2 χ S), and a value l 4 at the rational point Q (x Q , y Q ) of a straight line passing through rational points (p 10 ((2 χ −1)pS), 2 χ pS), and

the fourth computation step computes f′ χ, S (Q) as

[F7]

f′ χ, S ( Q )={ F 2 χ ,Z S ( Z Q )·{ l 1 p ·l 2 } −1 } p 10 ·F 2 χ ,Z S ( Z Q )· l 3 p ·l 4 .

8. A non-transitory computer recording medium storing a pairing computation program, wherein an elliptic curve is given as y 2 =x 3 +b, bεF p , letting an embedding degree be 12, E be an additive group constituted of rational points on the pairing enabled elliptic curve defined over an extension field F p 12 , 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 12 /( F* p 12 ) r ,

the pairing computation program causes an electronic computer which includes a CPU to compute the pairing e(S,Q), by letting SεG 1 , QεG 2 , χ be a given integer variable, Z S be a set of rational points S and pS, Z Q be a set of rational points pQ and Q, and F 2χ,ZS (Z Q ) be a rational function which is calculated using Miller's algorithm with respect to multi-pairing (MMA),

the order r and a trace t of the Frobenius endomorphism φ p being specified using the integer variable χ as,

r (χ)=36 χ 4 −36 χ 3 +18 χ 2 −6 χ +1,

t (χ)=6 χ 2 +1,

and a representation of the integer variable χ using p 10 with p as a characteristic being

p≡( 2 χ −1)p 10 +2 χ (modr(χ)),

the pairing computation program causing the CPU of the electronic computer to function as:

an input unit which inputs the integer variable χ, the rational point S, and the rational point Q into respective predetermined registers;

a first computation unit which computes F 2χ,ZS (Z Q );

a second computation unit which computes given rational points using 2 χ S and 2 χ pS which are calculated when computing said F 2χ,ZS (Z Q );

a third computation unit which computes a value at a rational point Q(x Q , y Q ) of a straight line passing through the given rational points;

a fourth computation unit which computes f′ χ, S (Q) using said F 2χ,ZS (Z Q ) and said value; and

a fifth computation unit which computes the pairing e(S,Q) using said f′ χ, S (Q) as

[F8]

e ( S,Q )= f′ χ, S ( Q ) (p 12 −1)/r .

9. The non-transitory computer recording medium storing a pairing computation program according to claim 8 , wherein the pairing computation program causes:

the CPU of the electronic computer which functions as the second computation unit to compute respective rational points −S, (2 χ −1)S, p 10 ((2 χ −1)S), −pS, (2 χ −1)pS, p 10 ((2 χ −1)pS) in order using previously obtained results;

the CPU of the electronic computer which functions as the third computation unit to compute respectively a value l 1 at a rational point Q(x Q , y Q ) of a straight line passing through rational points ((2 χ −1)S, −S), a value l 2 at the rational point Q(x Q , y Q ) of a straight line passing through rational points ((2 χ −1)pS, −pS), a value l 3 at the rational point Q (x Q , y Q ) of a straight line passing through rational points (p 10 ((2 χ −1)S), 2 χ S), and a value l 4 at the rational point Q (x Q , y Q ) of a straight line passing through rational points (p 10 ((2 χ −1)pS), 2 χ pS); and

the CPU of the electronic computer which functions as the fourth computation unit to compute f′ χ, S (Q) as

[F9]

f′ χ, S ( Q )={ F 2 χ, Z S ( Z Q )·{ l 1 p ·l 2 } −1 } p 10 ·F 2 χ, Z S ( Z Q )· l 3 p ·l 4 .

10. A pairing computation device, wherein

an elliptic curve is given as y 2 =x 3 +ax, aεF p , letting an embedding degree be 8, E be an additive group constituted of rational points on the pairing enabled elliptic curve defined over an extension field F p 8 , 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 8 /( F* p 8 ) 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, Z S be a set of rational points S and p 3 S, Z Q be a set of rational points p 3 Q and Q, and F 3χ,ZS (Z Q ) 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 using the integer variable χ as,

r (χ)=9 χ 4 +12 χ 3 +8 χ 2 +4 χ +1,

t (χ)=9 χ 3 −3 χ 2 −2 χ ,

and a representation of the integer variable χ using p 2 and p 3 with p as a characteristic is

p 3 ≡p 2 +3 χ +1(modr(χ)) 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 first computation unit which computes F 3 χ,ZS (Z Q );

a second computation unit which computes respective rational points p 2 (S), p 2 (p 3 S), (3 χ +1)S, (3 χ +1)p 3 S in order using previously obtained results;

a third computation unit which respectively computes a value l 5 at a rational point Q (x Q , y Q ) of a straight line passing through rational points (3 χ S, S), a value l 6 at the rational point Q (x Q , y Q ) of a straight line passing through rational points (p 2 (S), (3 χ +1)S), a value l 7 at the rational point Q (x Q , y Q ) of a straight line passing through rational points (3 χp 3 S, p 3 S), and a value l 8 at the rational point Q (x Q , y Q ) of a straight line passing through rational points (p 2 (p 3 S), (3 χ +1)p 3 S); and

the fourth computation unit which computes f′ χ, S (Q) using a computation result of the first computation unit and a computation result of the third computation unit as

[F10]

f′ χ, S ( Q )= F 3 χ, Z S ( Z Q ){ l 5 ·l 6 } p 3 ·l 7 ·l 8 ; and

a fifth computation unit which computes the pairing e(S,Q) using said f′ χ, S (Q) as

[F11]

e ( S,Q )= f′ χ, S ( Q ) (p 3 −1)/r .

11. A pairing computation method, wherein an elliptic curve is given as y 2 =x 3 +ax, aεF p , letting an embedding degree be 8, E be an additive group constituted of rational points on the pairing enabled elliptic curve defined over an extension field F p 8 , 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 8 /( F* p 8 ) r ,

an electronic computer which includes a CPU computes the pairing e(S,Q), by letting SεG 1 , QεG 2 , χ be a given integer variable, Z S be a set of rational points S and p 3 S, Z Q be a set of rational points p 3 Q and Q, and F 3χ,ZS (Z Q ) be a rational function which is calculated using Miller's algorithm with respect to multi-pairing (MMA),

the order r and a trace t of the Frobenius endomorphism φ p being specified using the integer variable χ as,

r (χ)=9 χ 4 +12 χ 3 +8 χ 2 +4 χ +1.

t (χ)=−9 χ 3 −3 χ 2 −2 χ ,

and a representation of the integer variable χ using p 2 and p 3 with p as a characteristic being

p 3 ≡p 2 +3 χ +1(modr(χ))

the pairing computation method comprising:

an input step which inputs the integer variable χ, the rational point S, and the rational point Q into respective predetermined registers by causing the CPU of the electronic computer to function as an input unit;

a first computation step which computes F 3χ,ZS (Z Q ) by causing the CPU of the electronic computer to function as a first computation unit;

a second computation step which computes respective rational points p 2 (S), p 2 (p 3 S), (3 χ +1)S, (3 χ +1)p 3 S in order using previously obtained results by causing the CPU of the electronic computer to function as a second computation unit;

a third computation step which respectively computes a value l 5 at a rational point Q(x Q , y Q ) of a straight line passing through rational points (3 χ S, S), a value l 6 at the rational point Q(x Q , y Q ) of a straight line passing through rational points (p 2 (S), (3 χ +1)S), a value l 7 at the rational point Q(x Q , y Q ) of a straight line passing through rational points (3 χp 3 S, p 3 S), and a value l 8 at the rational point Q(x Q , y Q ) of a straight line passing through rational points (p 2 (p 3 S), (3 χ +1)p 3 S) by causing the CPU of the electronic computer to function as a third computation unit; and

a fourth computation step which computes f′ χ, S (Q) using said F 3χ,ZS (Z Q ) and said values l 5 , l 6 , l 7 , l 8 as

[F12]

f′ χ, S ( Q )= F 3 χ, Z S ( Z Q ){ l 5 ·l 6 } p 3 ·l 7 ·l 8

by causing the CPU of the electronic computer to function as a fourth computation unit; and

a fifth computation step which computes the pairing e(S,Q) using said f′ χ, S (Q) as

[F13]

e ( S,Q )= f′ χ, S ( Q ) (p 3 −1)/r

by causing the CPU of the electronic computer to function as a fifth computation unit.

12. A non-transitory computer recording medium storing a pairing compututation program, wherein an elliptic curve is given as y 2 =x 2 +ax, aεF p , letting an embedding degree be 8, E be an additive group constituted of rational points on the pairing enabled elliptic curve defined over an extension field F p 8 , 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 8 /( F* p 8 ) r ,

the pairing computation program causes an electronic computer which includes a CPU to compute the pairing e(S,Q), by letting SεG 1 , QεG 2 , χ be a given integer variable, Z S be a set of rational points S and p 3 S, Z Q be a set of rational points p 3 Q and Q, and F 3χ,ZS (Z Q ) be a rational function which is calculated using Miller's algorithm with respect to multi-pairing (MMA),

the order r and a trace t of the Frobenius endomorphism φ p being specified using the integer variable χ as,

r (χ)=9 χ 4 +12 χ 3 +8 χ 2 +4 χ +1,

t (χ)=−9 χ 3 −3 χ 2 −2 χ ,

and a representation of the integer variable χ using p 2 and p 3 with p as a characteristic being

p 3 ≡p 2 +3 χ+1 (modr(χ))

the pairing computation program causing the CPU of the electronic computer to function as:

an input unit which inputs the integer variable χ, the rational point S, and the rational point Q into respective predetermined registers;

a first computation unit which computes F 3χ,ZS (Z Q );

a second computation unit which computes respective rational points p 2 (S), p 2 (p 3 S), (3 χ +1)S, (3 χ +1)p 2 S in order using previously obtained results;

a third computation unit which respectively computes a value l 5 at a rational point Q(x Q , y Q ) of a straight line passing through rational points (3 χ S, S), a value l 6 at the rational point Q(x Q , y Q ) of a straight line passing through rational points (p 2 (S), (3χ+1)S), a value l 7 at the rational point Q(x Q , y Q ) of a straight line passing through rational points (3 χp 3 S, p 3 S), and a value l 8 at the rational point Q(x Q , y Q ) of a straight line passing through rational points (p 2 (p 3 S), (3 χ +1)p 3 S); and

a fourth computation unit which computes f′ χ, S (Q) using said F 3χ,ZS (Z Q ) and said values l 5 , l 6 , l 7 , l 8 as

[F14]

f′ χ, S ( Q )= F 3 χ, Z S ( Z Q ){ l 5 ·l 6 } p 3 ·l 7 · 8 ; and

a fifth computation unit which computes the pairing e(S,Q) using said f′ χ, S (Q) as

[F15]

e ( S,Q )= f′ χ, S ( Q ) (p 3 −1)/r .

13. 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, 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

[F16]

e ( S,Q )= f′ χ, S ( Q ) (p k −1)/r .

14. A pairing computation method, 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 non-degenerate bilinear map

e:G 1 ×G 2 →F* p k /( F* p k ) r ,

an electronic computer which includes a CPU 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,

the order r and a trace t of the Frobenius endomorphism φ p being specified preliminarily according to the embedding degree k using the integer variable χ,

the pairing computation method comprising:

a step of inputting the integer variable χ, the rational point S, and the rational point Q into respective predetermined registers by causing the CPU of the electronic computer to function as an input unit;

a step of computing f by causing the CPU of the electronic computer to function as a computation unit;

a step of computing a value of a straight line passing through given rational points at a rational point Q(x Q , y Q ) by causing the CPU of the electronic computer to function as a computation unit;

a step of computing f′ χ, S (Q) using said f and said value by causing the CPU of the electronic computer to function as a computation unit; and

a step of computing the pairing e(S,Q) using said f′ χ, S (Q) as

[F17]

e ( S,Q )= f′ χ, S ( Q ) (p k −1)/r

by causing the CPU of the electronic computer to function as a computation unit.

15. A non-transitory computer recording medium storing a pairing computation program, 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 non-degenerate bilinear map

e:G 1 ×G 2 →F* p k /( F* p k ) r ,

the pairing computation program causes an electronic computer which includes a CPU to compute 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,

the order r and a trace t of the Frobenius endomorphism φ p being specified preliminarily according to the embedding degree k using the integer variable χ,

the pairing computation program causing the CPU of the electronic computer to function as:

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

[F18]

e ( S,Q )= f′ χ, S ( Q ) p k −1)/r .

16. A pairing computation device, wherein an elliptic curve is given as y 2 =x 3 +b, bεF p , letting an embedding degree be 12, E be an additive group constituted of rational points on the pairing enabled elliptic curve defined over an extension field F p 12 , 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 12 /( F* p 12 ) 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, f 2 χ, S (Q) be a rational function which is calculated using Miller's algorithm, wherein

the order r and a trace t of the Frobenius endomorphism φ p are specified using the integer variable χ as,

r (χ)=36 χ 4 −36 χ 3 +18 χ 2 −6 χ +1,

t (χ)=6 χ 2 +1,

and a representation of the integer variable χ using p 10 with p as a characteristic is

p≡( 2χ−1) p 10 +2χ(modr(χ)) 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 first computation unit which computes f 2χ,S (Q) and f 2χ,pS (Q);

a second computation unit which computes given rational points using 2 χ S and 2 χ pS which are calculated when computing said f 2χ,S (Q) and f 2χ,pS (Q);

a third computation unit which computes a value at a rational point Q (x Q , y Q ) of a straight line passing through the given rational points;

a fourth computation unit which computes f′ χ, S (Q) using said f 2χ,S (Q) and said value; and

a fifth computation unit which computes the pairing e(S,Q) using said f′ χ, S (Q) as

[F19]

e ( S,Q )= f′ χ, S ( Q ) (p 12 −1)/r .

17. The pairing computation device according to claim 16 , wherein

the second computation unit computes respective rational points −S, (2 χ −)S, p 10 ((2 χ −1)S), −pS, (2 χ −1)pS, p 10 ((2 χ −1)pS) in order using previously obtained results,

the third computation unit respectively computes a value l 1 at a rational point Q (x Q , y Q ) on a straight line passing through rational points ((2 χ −1)S, −S), a value l 2 at the rational point Q (x Q , y Q ) of a straight line passing through rational points (p 10 ((2 χ −1)S), 2 χ S), a value l 3 at the rational point Q (x Q , y Q ) of a straight line passing through rational points ((2 χ −1)pS, −pS), and a value l 4 at the rational point Q(x Q , y Q ) of a straight line passing through rational points (p 10 ((2 χ −1) pS), 2 χ pS), and

the fourth computation unit computes f′ χ, S (Q) using the values of the rational point Q (x Q , y Q ) l 1 , l 2 , l 3 , l 4 as

[F20]

f′ χ, S ( Q )=({ f 2χ ,S ( Q )· l 1 −1 } p 10 ·f 2χ ,S ( Q )· l 2 ) p ·{f 2χ,pS ( Q )· l 3 −1 } p 10 ·f 2χ,pS ( Q )· l 4 .

18. A pairing computation method, wherein an elliptic curve is given as y 2 =x 3 +b, bεF p , letting an embedding degree be 12, E be an additive group constituted of rational points on the pairing enabled elliptic curve defined over an extension field F p 12 , 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 12 /( F* p 12 ) r ,

an electronic computer which includes a CPU computes the pairing e(S,Q), by letting SεG 1 , QεG 2 , χ be a given integer variable, and f 2χ ,S (Q) be a rational function which is calculated using Miller's algorithm,

the order r and a trace t of the Frobenius endomorphism φ p being specified using the integer variable χ as,

r (χ)=36 χ 4 −36 χ 3 +18 χ 2 −6 χ +1,

t (χ)=6 χ 2 +1,

and a representation of the integer variable χ using p 10 with p as a characteristic being

p≡( 2 χ −1) p 10 +2 χ (modr(χ)),

the pairing computation method comprising:

an input step which inputs the integer variable χ, the rational point S, and the rational point Q into respective predetermined registers by causing the CPU of the electronic computer to function as an input unit;

a first computation step which computes f 2χ, S (Q) and f 2χ,pS (Q) by causing the CPU of the electronic computer to function as a first computation unit;

a second computation step which computes given rational points using 2 χ S and 2 χ pS which are calculated when computing said f 2χ, S (Q) and f 2χ,pS (Q) by causing the CPU of the electronic computer to function as a second computation unit;

a third computation step which computes a value at a rational point Q(x Q , y Q ) of a straight line passing through the given rational points by causing the CPU of the electronic computer to function as a third computation unit;

a fourth computation step which computes f′ χ, S (Q) using said f 2χ, S (Q) and said value by causing the CPU of the electronic computer to function as a fourth computation unit; and

a fifth computation step which computes the pairing e(S,Q) using said f′ χ, S (Q) as

[F21]

e ( S,Q )= f′ χ, S ( Q ) (p 12 −1)/r .

by causing the CPU of the electronic computer to function as a fifth computation unit.

19. The pairing computation method according to claim 18 , wherein

the second computation step computes respective rational points −S, (2 χ −1)S, p 10 ((2 χ −1)S), −pS, (2 χ −1)pS, p 10 ((2 χ −1)pS) in order using previously obtained results,

the third computation step respectively computes a value l 1 at a rational point Q(x Q , y Q ) of a straight line passing through rational points ((2 χ −1)S, −S), a value l 2 at the rational point Q(x Q , y Q ) of a straight line passing through rational points (p 10 ((2 χ −1)S), 2 χ S), a value l 3 at the rational point Q(x Q , y Q ) of a straight line passing through rational points ((2 χ −1)pS, −pS), and a value l 4 at the rational point Q(x Q , y Q ) of a straight line passing through rational points (p 10 ((2 χ −1)pS), 2 χ pS), and

the fourth computation step computes f′ χ, S (Q) using the values of the rational point Q(x Q , y Q ) l 1 , l 2 , l 3 , l 4 as

[F22]

f′ χ, S ( Q )=({ f 2χ, S ( Q )· l 1 −1 } p 10 ·f 2χ, S ( Q )· l 2 ) p ·{f 2χ,pS ( Q )· l 3 −1 } p 10 ·f 2χ,pS ( Q )· l 4 .

20. A non-transitory computer recording medium storing a pairing computation program, wherein an elliptic curve is given as y 2 =x 3 +b, bεF p , letting an embedding degree be 12, E be an additive group constituted of rational points on the pairing enabled elliptic curve defined over an extension field F p 12 , 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 12 /( F* p 12 ) r ,

the pairing computation program causes an electronic computer which includes a CPU to compute the pairing e(S,Q), by letting SεG 1 , QεG 2 , χ be a given integer variable, and f 2χ, S (Q) and f 2χ,pS (Q) be a rational function which is calculated using Miller's algorithm,

the order r and a trace t of the Frobenius endomorphism φ p being specified using the integer variable χ as,

r (χ)=36 χ 4 −36 χ 3 +18 χ 2 −6 χ +1,

t (χ)=6 χ 2 +1,

and a representation of the integer variable χ using p 10 with p as a characteristic being

p≡( 2 χ−1 ) p 10 +2 χ (modr(χ)),

the pairing computation program causing the CPU of the electronic computer to function as:

an input unit which inputs the integer variable χ, the rational point S, and the rational point Q into respective predetermined registers;

a first computation unit which computes f 2χ, S (Q) and f 2χ,pS (Q);

a second computation unit which computes given rational points using 2 χ S and 2 χ pS which are calculated when computing said f 2χ, S (Q) and f 2χ,pS (Q);

a third computation unit which computes a value at a rational point Q(x Q , y Q ) of a straight line passing through the given rational points;

a fourth computation unit which computes f′ χ, S (Q) using said f 2χ, S (Q) and said value; and

a fifth computation unit which computes the pairing e(S,Q) using said f′ χ, S (Q) as

[F23]

e ( S,Q )= f′ χ, S ( Q ) (p 12 −1)/r .

21. The non-transitory computer recording medium storing a pairing computation program according to claim 20 , wherein The pairing computation program causes:

the CPU of the electronic computer which functions as the second computation unit to compute respective rational points −S, (2 χ− 1)S, p 10 ((2 χ −1)S), −pS, (2 χ −1)pS, p 10 ((2 χ −1)pS) in order using previously obtained results;

the CPU of the electronic computer which functions as the third computation unit to respectively compute a value l 1 at a rational point Q(x Q , y Q ) of a straight line passing through rational points ((2 χ −1)S, −S), a value l 2 at the rational point Q(x Q , y Q ) of a straight line passing through rational points (p 10 ((2 χ −1)S), 2 χ S), a value l 3 at the rational point Q(x Q , y Q ) of a straight line passing through rational points ((2 χ −1)pS, −pS), and a value l 4 at the rational point Q(x Q , y Q ) of a straight line passing through rational points (p 10 ((2 χ −1)pS), 2 χ pS); and

the CPU of the electronic computer which functions as the fourth computation unit to compute f′ χ, S (Q) using the values of the rational point Q (x Q , y Q ) l 1 , l 2 , l 3 , l 4 as

[F24]

f′ χ, S ( Q )=({ f 2χ, S ( Q )· l 1 −1 } p 10 ·f 2χ, S ( Q )· l 2 ) p ·{f 2χ,pS ( Q )· l 3 −1 } p 10 ·f 2χ,pS ( Q ) ·l 4 .

22. A pairing computation device, wherein an elliptic curve is given as y 2 =x 3 +ax, aεF p , letting an embedding degree be 8, E be an additive group constituted of rational points on the pairing enabled elliptic curve defined over an extension field F p 8 , 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 8 /( F* p 8 ) 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 3χ, S (Q) be a rational function which is calculated using Miller's algorithm, wherein

the order r and a trace t of the Frobenius endomorphism φ p are specified using the integer variable χ as,

r (χ)=9 χ 4 +12 χ 3 +8 χ 2 +4 χ +1,

t (χ)=−9 χ 3 −3 χ 2 −2 χ ,

and a representation of the integer variable χ using p 2 and p 3 with p as a characteristic is

p 3 ≡p 2 +3 χ +1(modr(χ)) 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 first computation unit which computes f 3χ, S (Q) and f 3χ,p^3S (Q);

a second computation unit which computes respective rational points p 2 (S), (3 χ +1)S, p 2 (p 3 S), (3 χ +1)p 3 S in order using previously obtained results;

a third computation unit respectively computes a value l 5 at a rational point Q(x Q , y Q ) of a straight line passing through rational points (3 χ S, S), a value l 6 at the rational point Q(x Q , y Q ) of a straight line passing through rational points (p 2 (S), (3 χ +1)S), a value l 7 at the rational point Q(x Q , y Q ) of a straight line passing through rational points (3 χ p 3 S, p 3 S), and a value l 8 at the rational point Q(x Q , y Q ) of a straight line passing through rational points (p 2 (p 3 S), (3 χ +1)p 3 S); and

the fourth computation unit which computes f′ χ, S (Q) using the computation result of the first computation unit and the computation result of the third computation unit as

[F25]

f′ χ, S ( Q )=( f 3χ, S ( Q )· l 5 ·l 6 ) p 3 f 3χ,p 3 S ( Q )· l 7 ·l 8 ; and

a fifth computation unit which computes the pairing e(S,Q) using said f′ χ, S (Q) as

[F26]

e ( S,Q )= f′ χ, S ( Q ) (p 3 −1)/r .

23. A pairing computation method, wherein an elliptic curve is given as y 2 =x 3 +ax, aεF p , letting an embedding degree be 8, E be an additive group constituted of rational points on the pairing enabled elliptic curve defined over an extension field F p 8 , 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 8 /( F* p 8 ) r ,

an electronic computer which includes a CPU computes the pairing e(S,Q), by letting SεG 1 , QεG 2 , χ be a given integer variable, and f 3χ, S (Q) be a rational function which is calculated using Miller's algorithm,

the order r and a trace t of the Frobenius endomorphism φ p being specified using the integer variable χ as,

r (χ)=9 χ 4 +12 χ 3 +8 χ 2 +4 χ+1,

t (χ)=−9 χ 3 −3 χ 2 −2 χ ,

and a representation of the integer variable χ using p 2 and p 3 with p as a characteristic being

p 3 ≡p 2 +3 χ +1(modr(χ))

the pairing computation method comprising:

an input step which inputs the integer variable χ, the rational point S, and the rational point Q into respective predetermined registers by causing the CPU of the electronic computer to function as an input unit;

a first computation step which computes f 3χ, S (Q) and f 3χ,p^3S (Q) by causing the CPU of the electronic computer to function as a first computation unit;

a second computation step which computes respective rational points p 2 (S), (3 χ +1)S, p 2 (p 3 S), (3 χ +1) p 3 S in order using previously obtained results by causing the CPU of the electronic computer to function as a second computation unit;

a third computation step which respectively computes a value l 5 at a rational point Q(x Q , y Q ) of a straight line passing through rational points (3 χ S, S), a value l 6 at the rational point Q(x Q , y Q ) of a straight line passing through rational points (p 2 (S), (3 χ +1)S), a value l 7 at the rational point Q(x Q , y Q ) of a straight line passing through rational points (3 χ p 3 S, p 3 S), and a value l 8 at the rational point Q(x Q , y Q ) of a straight line passing through rational points (p 2 (p 3 S), (3 χ +1)p 3 S) by causing the CPU of the electronic computer to function as a third computation unit; and

a fourth computation step which computes f′ χ, S (Q) using said f 3χ, S (Q) and said f 3χ,p^3S (Q) and said values l 5 , l 6 , l 7 , l 8 as

[F27]

f′ χ, S ( Q )=( f 3χ, S ( Q )· l 5 ·l 6 ) p 3 f 3χ,p 3 S ( Q )· l 7 ·l 8 ;

by causing the CPU of the electronic computer to function as a fourth computation unit; and

a fifth computation step which computes the pairing e(S,Q) using said f′ χ, S (Q) as

[F28]

e ( S,Q )= f′ χ, S ( Q ) (p 3 −1)/r

by causing the CPU of the electronic computer to function as a fifth computation unit.

24. A non-transitory computer recording medium storing a pairing computation program, wherein an elliptic curve is given as y 2 =x 3 +ax, aεF p , letting an embedding degree be 8, E be an additive group constituted of rational points on the pairing enabled elliptic curve defined over an extension field F p 8 , 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 8 /( F* p 8 ) r ,

the pairing computation program causes an electronic computer which includes a CPU to compute the pairing e(S,Q), by letting SεG 1 , QεG 2 , χ be a given integer variable, and f 3χ,S (Q) be a rational function which is calculated using Miller's algorithm,

the order r and a trace t of the Frobenius endomorphism φ p being specified using the integer variable χ as,

r (χ)=9 χ 4 +12 χ 3 +8 χ 2 +4 χ +1,

t (χ)=−9 χ 3 −3 χ 2 −2 χ ,

and a representation of the integer variable χ using p 2 and p 3 with p as a characteristic being

p 3 ≡p 2 +3 χ +1(modr(χ))

the pairing computation program causing the CPU of the electronic computer to function as:

an input unit which inputs the integer variable χ, the rational point S, and the rational point Q into respective predetermined registers;

a first computation unit which computes f 3χ, S (Q) and f 3χ,p^3S (Q);

a second computation unit which computes respective rational points p 2 (S), (3 χ +1)S, p 2 (p 3 S), (3 χ +1)p 3 S in order using previously obtained results;

a third computation unit which respectively computes a value l 5 at a rational point Q (x Q , y Q ) of a straight line passing through rational points (3 χ S, S), a value l 6 at the rational point Q (x Q , y Q ) of a straight line passing through rational points (p 2 (S), (3 χ +1)S), a value l 7 at the rational point Q (x Q , y Q ) of a straight line passing through rational points (3 χp 3 S, p 3 S), and a value l 8 at the rational point Q (x Q , y Q ) of a straight line passing through rational points (p 2 (p 2 S), (3 χ +1)p 3 S); and

a fourth computation unit which computes f′ χ, S (Q) using said f 3χ, S (Q) and said f 3χp^3S (Q) and said values l 5 , l 6 , l 7 , l 8 as

[F29]

f′ χ, S ( Q )=( f 3χ, S ( Q )· l 5 ·l 6 ) p 3 f 3χ,p 3 S ( Q )· l 7 ·l 8 ; and

a fifth computation unit which computes the pairing e(S,Q) using said f′ χ, S (Q) as

[F30]

e ( S,Q )= f′ χ, S ( Q ) (p 3 −1)/r .