特許
J-GLOBAL ID：200903054777280005
楕円曲線ペアリング演算装置
発明者：
出願人/特許権者：
代理人 (1件)：
特許業務法人湘洋内外特許事務所
公報種別：公開公報
出願番号（国際出願番号）：特願2004-135867
公開番号（公開出願番号）：特開2005-316267
出願日： 2004年04月30日
公開日（公表日）： 2005年11月10日
要約：
【課題】 楕円曲線上で定義される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
請求項（抜粋）：
有限体上の楕円曲線上で定義される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件)：
FI (1件)：
Fターム (5件)：
5J104AA25
, 5J104JA21
, 5J104JA25
, 5J104NA02
, 5J104NA16
