US 8,477,934 B2 · Pairing computation device, pairing computation method and recording medium storing pairing computation program

A pairing computation device, wherein an elliptic curve is given as y2=x3+ax+b, aεFp, bεFp, 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 Fpk, 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

G1=E[r]∩Ker(φp−[1]),
G2=E[r]∩Ker(φp−[p]),
as a non-degenerate bilinear map
e:G1×G2→F*pk/(F*pk)r,
the pairing computation device comprising a CPU which computes the pairing e(S,Q), by letting SεG1, QεG2, χ 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 (xQ, yQ);
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)(pk−1)/r.

12 more elements

A pairing computation device, wherein an elliptic curve is given as y2=x3+b, bεFp, 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 Fp12, 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

G1=E[r]∩Ker(φp−[1]),
G2=E[r]∩Ker(φp−[p]),
as a non-degenerate bilinear map
e:G1×G2→F*p12/(F*p12)r,
the pairing computation device comprising a CPU which computes the pairing e(S,Q), by letting SεG1, QεG2, χ be a given integer variable, ZS be a set of rational points S and pS, ZQ be a set of rational points pQ and Q, and F2χ,ZS(ZQ) 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 p10 with p as a characteristic is
p≡(2χ−1)p10+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 F2χ,ZS(ZQ);
a second computation unit which computes given rational points using 2χS and 2χpS which are calculated when computing said F2χ,ZS(ZQ);
a third computation unit which computes a value at a rational point Q(xQ, yQ) of a straight line passing through the given rational points;
a fourth computation unit which computes f′ χ,S(Q) using said F2χ,ZS(ZQ) 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)(p12−1)/r.

17 more elements

A pairing computation method, wherein an elliptic curve is given as y2=x3+b, bεFp, 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 Fp12, 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

G1=E[r]∩Ker(φp−[1]),
G2=E[r]∩Ker(φp−[p]),
as a non-degenerate bilinear map
e:G1×G2→F*p12/(F*p12)r,
an electronic computer which includes a CPU computes the pairing e(S,Q), by letting SεG1, QεG2, χ be a given integer variable, ZS be a set of rational points S and pS, ZQ be a set of rational points pQ and Q, and F2χ,ZS(ZQ) 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 p10 with p as a characteristic being
p≡(2χ−1)p10+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 F2χ,ZS(ZQ) 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 F2χ,ZS(ZQ) 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(xQ, yQ) 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 F2χ, ZS(ZQ) 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)(p12−1)/r,
by causing the CPU of the electronic computer to function as a fifth computation unit.

18 more elements

A non-transitory computer recording medium storing a pairing computation program, wherein an elliptic curve is given as y2=x3+b, bεFp, 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 Fp12, 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

G1=E[r]∩Ker(φp−[1]),
G2=E[r]∩Ker(φp−[p]),
as a non-degenerate bilinear map
e:G1×G2→F*p12/(F*p12)r,
the pairing computation program causes an electronic computer which includes a CPU to compute the pairing e(S,Q), by letting SεG1, QεG2, χ be a given integer variable, ZS be a set of rational points S and pS, ZQ be a set of rational points pQ and Q, and F2χ,ZS (ZQ) 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 p10 with p as a characteristic being
p≡(2χ−1)p10+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 F2χ,ZS(ZQ);
a second computation unit which computes given rational points using 2χS and 2χpS which are calculated when computing said F2χ,ZS(ZQ);
a third computation unit which computes a value at a rational point Q(xQ, yQ) of a straight line passing through the given rational points;
a fourth computation unit which computes f′χ,S(Q) using said F2χ,ZS(ZQ) 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)(p12−1)/r.

17 more elements

A pairing computation device, wherein

an elliptic curve is given as y2=x3+ax, aεFp, 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 Fp8, 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
G1=E[r]∩Ker(φp−[1]),
G2=E[r]∩Ker(φp−[p]),
as a non-degenerate bilinear map
e:G1×G2→F*p8/(F*p8)r,
the pairing computation device comprising a CPU which computes the pairing e(S,Q), by letting SεG1, QεG2, χ be a given integer variable, ZS be a set of rational points S and p3S, ZQ be a set of rational points p3Q and Q, and F3χ,ZS(ZQ) 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 p2 and p3 with p as a characteristic is
p3≡p2+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 F3 χ,ZS(ZQ);
a second computation unit which computes respective rational points p2(S), p2(p3S), (3χ+1)S, (3χ+1)p3S in order using previously obtained results;
a third computation unit which respectively computes a value l5 at a rational point Q (xQ, yQ) of a straight line passing through rational points (3χS, S), a value l6 at the rational point Q (xQ, yQ) of a straight line passing through rational points (p2(S), (3χ+1)S), a value l7 at the rational point Q (xQ, yQ) of a straight line passing through rational points (3χp3S, p3S), and a value l8 at the rational point Q (xQ, yQ) of a straight line passing through rational points (p2(p3S), (3χ+1)p3S);
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)=F3χ,ZS(ZQ){l5·l6}p3·l7·l8;
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)(p3−1)/r.

21 more elements

A pairing computation method, wherein an elliptic curve is given as y2=x3+ax, aεFp, 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 Fp8, 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

G1=E[r]∩Ker(φp−[1]),
G2=E[r]∩Ker(φp−[p]),
as a non-degenerate bilinear map
e:G1×G2→F*p8/(F*p8)r,
an electronic computer which includes a CPU computes the pairing e(S,Q), by letting SεG1, QεG2, χ be a given integer variable, ZS be a set of rational points S and p3S, ZQ be a set of rational points p3Q and Q, and F3χ,ZS(ZQ) 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 p2 and p3 with p as a characteristic being
p3≡p2+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 F3χ,ZS(ZQ) by causing the CPU of the electronic computer to function as a first computation unit;
a second computation step which computes respective rational points p2(S), p2(p3S), (3χ+1)S, (3χ+1)p3S 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 l5 at a rational point Q(xQ, yQ) of a straight line passing through rational points (3χS, S), a value l6 at the rational point Q(xQ, yQ) of a straight line passing through rational points (p2(S), (3χ+1)S), a value l7 at the rational point Q(xQ, yQ) of a straight line passing through rational points (3χp3S, p3S), and a value l8 at the rational point Q(xQ, yQ) of a straight line passing through rational points (p2(p3S), (3χ+1)p3S) 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 F3χ,ZS(ZQ) and said values l5, l6, l7, l8 as
[F12]
f′χ,S(Q)=F3χ,ZS(ZQ){l5·l6}p3·l7·l8
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)(p3−1)/r
by causing the CPU of the electronic computer to function as a fifth computation unit.

22 more elements

A non-transitory computer recording medium storing a pairing compututation program, wherein an elliptic curve is given as y2=x2+ax, aεFp, 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 Fp8, 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

G1=E[r]∩Ker(φp−[1]),
G2=E[r]∩Ker(φp−[p]),
as a non-degenerate bilinear map
e:G1×G2→F*p8/(F*p8)r,
the pairing computation program causes an electronic computer which includes a CPU to compute the pairing e(S,Q), by letting SεG1, QεG2, χ be a given integer variable, ZS be a set of rational points S and p3S, ZQ be a set of rational points p3Q and Q, and F3χ,ZS(ZQ) 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 p2 and p3 with p as a characteristic being
p3≡p2+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 F3χ,ZS(ZQ);
a second computation unit which computes respective rational points p2(S), p2(p3S), (3χ+1)S, (3χ+1)p2S in order using previously obtained results;
a third computation unit which respectively computes a value l5 at a rational point Q(xQ, yQ) of a straight line passing through rational points (3χS, S), a value l6 at the rational point Q(xQ, yQ) of a straight line passing through rational points (p2(S), (3χ+1)S), a value l7 at the rational point Q(xQ, yQ) of a straight line passing through rational points (3χp3S, p3S), and a value l8 at the rational point Q(xQ, yQ) of a straight line passing through rational points (p2(p3S), (3χ+1)p3S);
and
a fourth computation unit which computes f′χ,S(Q) using said F3χ,ZS(ZQ) and said values l5, l6, l7, l8 as
[F14]
f′χ,S(Q)=F3χ,ZS(ZQ){l5·l6}p3·l7·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)(p3−1)/r.

20 more elements

A pairing computation device, wherein an elliptic curve is given as y2=x3+b, bεFp, 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 Fp12, 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

G1=E[r]∩Ker(φp−[1]),
G2=E[r]∩Ker(φp−[p]),
as a non-degenerate bilinear map
e:G1×G2→F*p12/(F*p12)r,
the pairing computation device comprising a CPU which computes the pairing e(S,Q), by letting SεG1, QεG2, χ be a given integer variable, f2χ,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 p10 with p as a characteristic is
p≡(2χ−1)p10+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 f2χ,S(Q) and f2χ,pS(Q);
a second computation unit which computes given rational points using 2χS and 2χpS which are calculated when computing said f2χ,S(Q) and f2χ,pS(Q);
a third computation unit which computes a value at a rational point Q (xQ, yQ) of a straight line passing through the given rational points;
a fourth computation unit which computes f′χ,S(Q) using said f2χ,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)(p12−1)/r.

17 more elements

A pairing computation method, wherein an elliptic curve is given as y2=x3+b, bεFp, 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 Fp12, 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

G1=E[r]∩Ker(φp−[1]),
G2=E[r]∩Ker(φp−[p]),
as a non-degenerate bilinear map
e:G1×G2→F*p12/(F*p12)r,
an electronic computer which includes a CPU computes the pairing e(S,Q), by letting SεG1, QεG2, χ be a given integer variable, and f2χ,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 p10 with p as a characteristic being
p≡(2χ−1)p10+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 f2χ,S(Q) and f2χ,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 f2χ,S(Q) and f2χ,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(xQ, yQ) 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 f2χ,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)(p12−1)/r.
by causing the CPU of the electronic computer to function as a fifth computation unit.

18 more elements

A non-transitory computer recording medium storing a pairing computation program, wherein an elliptic curve is given as y2=x3+b, bεFp, 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 Fp12, 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

G1=E[r]∩Ker(φp−[1]),
G2=E[r]∩Ker(φp−[p]),
as a non-degenerate bilinear map
e:G1×G2→F*p12/(F*p12)r,
the pairing computation program causes an electronic computer which includes a CPU to compute the pairing e(S,Q), by letting SεG1, QεG2, χ be a given integer variable, and f2χ,S(Q) and f2χ,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 p10 with p as a characteristic being
p≡(2χ−1)p10+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 f2χ,S(Q) and f2χ,pS(Q);
a second computation unit which computes given rational points using 2χS and 2χpS which are calculated when computing said f2χ,S(Q) and f2χ,pS(Q);
a third computation unit which computes a value at a rational point Q(xQ, yQ) of a straight line passing through the given rational points;
a fourth computation unit which computes f′χ,S(Q) using said f2χ,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)(p12−1)/r.

17 more elements

A pairing computation device, wherein an elliptic curve is given as y2=x3+ax, aεFp, 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 Fp8, 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

G1=E[r]χKer(φp−[1]),
G2=E[r]χKer(φp−[p]),
as a non-degenerate bilinear map
e:G1×G2→F*p8/(F*p8)r,
the pairing computation device comprising a CPU which computes the pairing e(S,Q), by letting SεG1, QεG2, χ be a given integer variable, and f3χ,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 p2 and p3 with p as a characteristic is
p3≡p2+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 f3χ,S(Q) and f3χ,p^3S(Q);
a second computation unit which computes respective rational points p2(S), (3χ+1)S, p2(p3S), (3χ+1)p3S in order using previously obtained results;
a third computation unit respectively computes a value l5 at a rational point Q(xQ, yQ) of a straight line passing through rational points (3χS, S), a value l6 at the rational point Q(xQ, yQ) of a straight line passing through rational points (p2(S), (3χ+1)S), a value l7 at the rational point Q(xQ, yQ) of a straight line passing through rational points (3χp3S, p3S), and a value l8 at the rational point Q(xQ, yQ) of a straight line passing through rational points (p2(p3S), (3χ+1)p3S);
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)=(f3χ,S(Q)·l5·l6)p3f3χ,p3S(Q)·l7·l8;
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)(p3−1)/r.

20 more elements

A pairing computation method, wherein an elliptic curve is given as y2=x3+ax, aεFp, 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 Fp8, 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

G1=E[r]∩Ker(φp−[1]),
G2=E[r]∩Ker(φp−[p]),
as a non-degenerate bilinear map
e:G1×G2→F*p8/(F*p8)r,
an electronic computer which includes a CPU computes the pairing e(S,Q), by letting SεG1, QεG2, χ be a given integer variable, and f3χ,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 p2 and p3 with p as a characteristic being
p3≡p2+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 f3χ,S(Q) and f3χ,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 p2(S), (3χ+1)S, p2(p3S), (3χ+1) p3S 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 l5 at a rational point Q(xQ, yQ) of a straight line passing through rational points (3χS, S), a value l6 at the rational point Q(xQ, yQ) of a straight line passing through rational points (p2(S), (3χ+1)S), a value l7 at the rational point Q(xQ, yQ) of a straight line passing through rational points (3χp3S, p3S), and a value l8 at the rational point Q(xQ, yQ) of a straight line passing through rational points (p2(p3S), (3χ+1)p3S) 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 f3χ,S(Q) and said f3χ,p^3S(Q) and said values l5, l6, l7, l8 as
[F27]
f′χ,S(Q)=(f3χ,S(Q)·l5·l6)p3f3χ,p3S(Q)·l7·l8;
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)(p3−1)/r
by causing the CPU of the electronic computer to function as a fifth computation unit.

22 more elements

A non-transitory computer recording medium storing a pairing computation program, wherein an elliptic curve is given as y2=x3+ax, aεFp, 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 Fp8, 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

G1=E[r]∩Ker(φp−[1]),
G2=E[r]∩Ker(φp−[p]),
as a non-degenerate bilinear map
e:G1×G2→F*p8/(F*p8)r,
the pairing computation program causes an electronic computer which includes a CPU to compute the pairing e(S,Q), by letting SεG1, QεG2, χ be a given integer variable, and f3χ,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 p2 and p3 with p as a characteristic being
p3≡p2+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 f3χ,S(Q) and f3χ,p^3S(Q);
a second computation unit which computes respective rational points p2(S), (3χ+1)S, p2(p3S), (3χ+1)p3S in order using previously obtained results;
a third computation unit which respectively computes a value l5 at a rational point Q (xQ, yQ) of a straight line passing through rational points (3χS, S), a value l6 at the rational point Q (xQ, yQ) of a straight line passing through rational points (p2(S), (3χ+1)S), a value l7 at the rational point Q (xQ, yQ) of a straight line passing through rational points (3χp3S, p3S), and a value l8 at the rational point Q (xQ, yQ) of a straight line passing through rational points (p2(p2S), (3χ+1)p3S);
and
a fourth computation unit which computes f′χ,S(Q) using said f3χ,S(Q) and said f3χp^3S(Q) and said values l5, l6, l7, l8 as
[F29]
f′χ,S(Q)=(f3χ,S(Q)·l5·l6)p3f3χ,p3S(Q)·l7·l8;
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)(p3−1)/r.

20 more elements

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

Life of this patent

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

Life of this patent

Abstract

Claims24