PAIRING COMPUTATION DEVICE, PAIRING COMPUTATION METHOD, AND RECORDING MEDIUM WHERE PAIRING COMPUTATION PROGRAM IS RECORDEDThere is provided a pairing computation device, a pairing computation method and a recording medium recording a pairing computation program all enabling a pairing computation at high speed. In the case where the Ate pairing e(Q,P) is defined as in equation (1) and k is any one of even, a multiple of 3, a multiple of 4, and a multiple of 6, arithmetic operations of a rational function which is required to derive the Miller function fs,Q(P) are performed on the proper subfield specified by a twist curve using a quadratic and cubic non-residue v which becomes 1 when an exponentiation of this fs,Q(P) to the power of (qk - 1)/r is performed.A pairing computation device, wherein an elliptic curve equation is given as y2=x3+ax+b, a∈Fq, b∈Fq (q: a power of a prime number greater than 3), letting an embedding degree be 2h-th degree (h:a natural number), E be an additive group constituted of rational points on a pairing-enabled elliptic curve defined over Fq2h, E[r] be a set of rational points of prime order r, and φq be the Frobenius endomorphism, the Ate pairing e is defined, using G1=Er∩Ker⁢φq-1 G2=Er∩Ker⁢φq-q, as a non-degenerate bilinear map e:G2×G1→F*q2⁢h/F*q2⁢hr, letting P∈G1, Q∈G2, and letting s=t-1 using a trace t of the Frobenius endomorphism φq, and using the Miller function fs,Q(·), the Ate pairing e(Q,P) is computed as eQP=fs,Q⁢Pq2⁢h-1/r, the pairing computation device characterized by comprising: in order to perform an arithmetic operation of a rational function which is required to derive fs,Q(P) on the proper subfield by a twist curve of E(Fqh), that is, E' (Fqh):y2 = x3 +av-2x +bv-3 using v∈Fqh which is a quadratic non-residue element and becomes 1 by an exponentiation of fs,Q(P) to the power of (q2h -1)/r, an input unit which is configured to receive inputs of said s=t-1, P which satisfies P∈E(Fq), and Q' which satisfies Q'∈E'(Fqh); a substitution unit which is configured to perform substitution operations n←xpv-1, m←ypv-3/2 with respect to coordinates of the rational point P (xp,yp) and to perform substitution operations f←1, T'←Q'; a first arithmetic operation unit which is configured to calculate lT,T(xp,yp)v-3/2 as lT',T'(n,m), instead of calculating lT,T(xp,yp) which is a value substituted by coordinates (xp,yp) of the rational point P in the left hand side of an equation lT,T(x,y)=0 of the tangent line passing through the rational point T, and to perform a substitution operation f←f2. lT',T'(n,m) 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 the predetermined bit of s in binary representation is 1, to calculate lT,Q(xp,yp)v-3/2 as lT',Q'(n,m), instead of calculating lT,Q(xp,yp) which is a value substituted by coordinates of the rational point P in the left hand side of an equation lT,Q(x,y) =0 of the straight line passing through the rational points T and Q, and to perform a substitution operation f←f·lT',Q'(n,m) ; 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'+O'; and a fifth arithmetic operation unit which is configured to perform an exponentiation operation to the power of (q2h -1) /r.
페어링 연산 장치, 페어링 연산 방법, 및 페어링 연산 프로그램을 기록한 기록 매체페어링 연산을 고속으로 실행 가능하게 한 페어링 연산 장치, 페어링 연산 방법, 및 페어링 연산 프로그램을 기록한 기록 매체를 제공한다. Ate 페어링 e(Q, P)를 수학식 1로 하고, k가 짝수, 3의 배수, 4의 배수, 6의 배수 중 어느 하나인 경우에, 밀러 함수 fs,Q(P)의 도출에 필요로 되는 유리 함수의 연산을, 이 fs,Q(P)의 (qk-1)/r승의 멱승산의 연산에 의해 1로 되는 평방 및 3승 비잉여의 v를 이용한 트위스트 곡선에 의해 특정되는 진부분체 상의 연산으로서 행한다.타원 곡선(elliptic curve)의 식이 y2=x3+ax+b, a∈Fq, b∈Fq(q:3보다 큰 소수의 멱승)로 주어지고, 매립 차수가 2h차(h:자연수)이고, Fq2h를 정의체로 하는 페어링 가능한 타원 곡선 상의 유리점(rational point)이 이루는 가법군(additive group)을 E, 소수 위수(prime order) r의 유리점의 집합을 E[r]로 하고, φq를 프로베니우스 자기 준동형 사상(Frobenius endomorphism)으로 하여,G1=E[r]∩Ker(φq-[1])G2=E[r]∩Ker(φq-[q])에 의해,e:G2×G1→F*q2h/(F*q2h)r인 비퇴화의 쌍선형 사상으로서 정의되는 Ate 페어링 e에 의해, P∈G1, Q∈G2로 하고, 프로베니우스 자기 준동형 사상 φq의 트레이스 t를 이용하여 s=t-1로 하고, 밀러 함수 fs,Q(ㆍ)을 이용하여, [수학식 1]로서 Ate 페어링 e(Q, P)를 연산하는 페어링 연산 장치로서,fs, Q(P)의 도출에 필요로 되는 유리 함수의 연산을, 이 fs,Q(P)의 (q2h-1)/r승의 멱승산의 연산에 의해 1로 되는 평방 비잉여(quadratic non-residue element)의 v∈Fqh를 이용하여, E(Fqh)의 트위스트 곡선 E'(Fqh):y2=x3+av-2x+bv-3에 의한 진부분체(proper subfield) 상에서 행하기 위해서,상기 s=t-1, P∈E(Fq)인 P, Q'∈E'(Fqh)인 Q'의 입력을 접수하는 입력 수단과,유리점 P의 좌표 (xP, yP)에 대하여, n←xPv-1, m←yPv-3/2의 대입 연산을 행함과 함께, f←1, T'←Q'의 대입 연산을 행하는 대입 수단과,유리점 T를 통과하는 접선 lT,T(x, y)=0의 좌변에 유리점 P의 좌표 (xP, yP)를 대입한 값 lT,T(xP, yP)를 연산하는 대신에, lT,T(xP, yP)v-3/2를 lT',T'(n, m)로 연산하여, f←f2ㆍlT',T'(n, m)의 대입 연산을 행하는 제1 연산 수단과,T'←2T'의 대입 연산을 행하는 제2 연산 수단과,상기 s를 2진수 표시로 한 경우의 소정의 비트의 값이 1인 경우에, 유리점 T와 Q를 통과하는 직선 lT,Q(x, y)=0의 좌변에 유리점 P의 좌표 (xP, yP)를 대입한 값 lT,Q(xP, yP)를 연산하는 대신에, lT,Q(xP, yP)v-3/2을 lT',Q'(n, m)로 연산하여, f←fㆍlT',Q'(n, m)의 대입 연산을 행하는 제3 연산 수단과,상기 s를 2진수 표시로 한 경우의 소정의 비트의 값이 1인 경우에, T'←T'+Q'의 대입 연산을 행하는 제4 연산 수단과,(q2h-1)/r승의 멱승산을 연산하는 제5 연산 수단을 구비한 것을 특징으로 하는 페어링 연산 장치.