Pat

J-GLOBAL ID：200903054777280005

楕円曲線ペアリング演算装置

Inventor： 高橋 昌史
Applicant, Patent owner： 株式会社日立製作所
Agent (1)： 特許業務法人湘洋内外特許事務所
Gazette classification：公開公報
Application number (International application number)：2004135867
Publication number (International publication number)：2005316267
Application date： Apr. 30, 2004
Publication date： Nov. 10, 2005
Summary：

【課題】 楕円曲線上で定義されるTateペアリングの計算を行う際の演算負荷を軽減する。【解決手段】 (1)f=f2gV,V(Q)/g2V(Q)の計算の代わりに、lg2V(Q)がペアリング演算の最後に行う(q-1)/m乗の過程で1となるlを用いてf=f2gVV(Q)lを計算する。これにより逆元計算を削減することができる。(2)f=fgV,P(Q)/gV+P(Q)の計算の代わりに、lgV+P(Q)がペアリング演算の最後に行う(q-1)/m乗の過程で1となるlを用いてf=fgV,P(Q)lを計算する。これにより逆元計算を削減することができる。(3)lの選択方法として、dをd|kかつd<kを満たす最大の整数、gV+P(Q)またはg2V(Q)=d1xQ+d0とした場合、 【数1】とする。【選択図】 図1

Claim (excerpt)：

有限体上の楕円曲線上で定義されるTateペアリング演算装置であって、 楕円曲線パラメータおよび定義体情報として、 定義体Fp、Fpのk次拡大体Fq(dをd|kかつd<kを満たす最大の整数としたときFpのk次拡大体Fqは、Fpのk/d次拡大体としての構造を持つ)、 楕円曲線E:y2=x3+ax+b、 以下の条件を満たすm「mはE(Fp)の位数#E(Fp)を割り切る。mはq-1を割り切る。3.mはα=1,2,...,k-1に対してpα-1を割り切らない」、 演算対象データとして、 mねじれ群E(Fp)[m]の点P、 E(Fq)/mE(Fq)の点Q の入力を受け付ける入力データ受付手段と、 Tateペアリング演算e(P,Q)を行うペアリング演算手段と、 ペアリング演算結果を出力する出力手段とを備え、 前記ペアリング演算手段は、以下の処理を行なうことを特徴とするペアリング演算装置: <S1:mの2進展開> mの2進展開を行い、 m=m0+m12+...+mr2r、mj∈{0,1}(0≦j≦r-1)、 mr≠0とおく。 <S2:中間データfおよびVの初期化> f=1、V=Qとおく。 <S3:iの初期化> i=r-1とおく。 <S4:入力データQのx座標に応じて最適な計算アルゴリズを選択> Q=(xQ,yQ)のx座標xQがFqの部分群であるFPのd次拡大体の元かどうかを判定し、d次拡大体の元であればS5に進み、そうでなければS2に進む。 <S5:接線の方程式の計算、および、gV,V(Q)の計算> VでE(Fp)と接する直線gV,V=c0+c1x+c2yを求め、 gV,V(Q)=c0+c1xQ+c2yQを計算する。 <S6:中間データfの更新> f=f2gV,V(Q)を計算し、fの値を更新する。 <S7:miの値による分岐> V=2Vとおき、mi=1であればS8に進み、mi=0であればS11に進む。 <S8:2点を通る直線の計算、および、gV,P(Q)の計算> VとPとを通る直線gV,P=c0+c1x+c2yを求め、 gV,P(Q)=c0+c1xQ+c2yQを計算する。 <S9:中間データfの更新> f=fgV,P(Q)を計算し、fの値を更新する。 <S10:Vの更新> V=V+Pとおく。 <S11:iの値による分岐> i=i-1とおき、i=-1であればS22に進み、異なればS6に進む。 <S12:従来例におけるdに対してdh(z,w)がべき乗の過程で1となるh(z,w)を求める際に用いる方程式h(z,w)を求める> z、wを変数とする多項式

IPC (1)：

G09C1/00

FI (1)：

G09C1/00 650A

F-Term (5)：

5J104AA25 ,  5J104JA21 ,  5J104JA25 ,  5J104NA02 ,  5J104NA16