(57)【要約】  K個の有限体GF(pm)の元R(i,k)∈GF(pm)に対する有限体上の演算をe(R(i,0),...,R(i,K-1))とした場合における演算Πi=0N-1e(R(i,0),...,R(i,K-1))を効率的に演算する。各iに対する演算e(R(i,0),...,R(i,K-1))を行う過程でそれぞれ得られる、有限体GF(pm)のd次拡大体を示す多項式poly(R(i,0),...,R(i,K-1))同士を乗算し、その乗算結果を累積乗算する。当該多項式poly(R(i,0),...,R(i,K-1))は、入力された有限体GF(pm)の元からの写像であり、少なくとも一部の項の係数が0となっている。同様な処理を異なるiの組み合わせについて実行し、その結果を用いて演算Πi=0N-1e(R(i,0),...,R(i,K-1))を行う。
2010123117.tif 000002
【特許請求の範囲】
【請求項１】
N・K個(N≧2,K≧1)の有限体GF(pm)の元R(i,k)∈GF(pm)〔i∈{0,...,N-1}，k∈{0,...,K-1}，pは素数，mは1以上の整数〕が入力される入力部と、
K個の前記有限体GF(pm)の元R(i,0),...,R(i,K-1)∈GF(pm)に対する有限体上の演算をe(R(i,0),...,R(i,K-1))とした場合における、演算Πi=0N-1e(R(i,0),...,R(i,K-1))を行う有限体演算部と、
前記有限体演算部での演算結果を出力する出力部と、を有し、
前記有限体上の演算e(R(i,0),...,R(i,K-1))は、それぞれ、有限体GF(pm)のd次拡大体GF(pd・m)(d≧2)上の拡大体演算を一部に含み、
前記拡大体演算は、入力された１以上の有限体GF(pm)の元R(i,k)∈{R(i,0),...,R(i,K-1)}に依存する有限体GF(pm)上の像及び／又は有限体GF(pm)の元R(i,k)∈{R(i,0),...,R(i,K-1)}を、d次拡大体GF(pd・m)の元を示す多項式poly(R(i,0),...,R(i,K-1))∈GF(pd・m)に写す演算であり、
前記多項式poly(R(i,0),...,R(i,K-1))∈GF(pd・m)は、項数dの多項式であり、そのうち一部の項h∈{0,...,d-1}の係数ahが前記１以上の有限体GF(pm)の元R(i,k)に依存する有限体GF(pm)上の像及び／又は有限体GF(pm)の元R(i,k)とされ、予め定められた一部の項r∈{0,...,d-1}(r≠h)の係数arが予め0∈GF(pm)とされた多項式であり、
前記有限体演算部は、
何れかのi1∈{0,...,N-1}について、１以上の有限体GF(pm)の元R(i1,k)に依存する有限体GF(pm)上の像及び／又は有限体GF(pm)の元R(i1,k)が入力され、これらに対する前記拡大体演算を行い、多項式poly(R(i1,0),...,R(i1,K-1))∈GF(pd・m)を得る第１演算部と、
何れかのi2∈{0,...,N-1}(i2≠i1)について、１以上の有限体GF(pm)の元R(i2,k)に依存する有限体GF(pm)上の像及び／又は有限体GF(pm)の元R(i2,k)が入力され、これらに対する前記拡大体演算を行い、多項式poly(R(i2,0),...,R(i2,K-1))∈GF(pd・m)を得る第２演算部と、
前記多項式poly(R(i1,0),...,R(i1,K-1))と前記多項式poly(R(i2,0),...,R(i2,K-1))とが入力され、それらの積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))∈GF(pd・m)を算出する第３演算部と、
集合{0,...,N-1}に含まれるL個〔Lは偶数〕の互いに異なる複数の元からなる部分集合の各元をそれぞれ１回ずつi1又はi2として選択し、選択したi1とi2との組のそれぞれに対して前記第１演算部と前記第２演算部と前記第３演算部とによる第１処理を１回ずつ実行させることで、L/2個の前記組のそれぞれに対応する前記第１処理を含むループ処理を実行させる制御部と、
それぞれの前記第１処理によって得られた前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))を用いてΠi=0N-1poly(R(i,0),...,R(i,K-1))∈GF(pd・m)を算出する第４演算部と、を含む、有限体演算装置。
【請求項２】
請求項１の有限体演算装置であって、
前記第３演算部は、前記多項式poly(R(i1,0),...,R(i1,K-1))の予め0∈GF(pm)とされた項、及び／又は、前記多項式poly(R(i2,0),...,R(i2,K-1))の予め0∈GF(pm)とされた項、を被演算子とした演算を行うことなく、前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))を求める、有限体演算装置。
【請求項３】
請求項１又は２の有限体演算装置であって、
Nは偶数であり、L=Nであり、前記部分集合は集合{0,...,N-1}である、有限体演算装置。
【請求項４】
請求項１又は２の有限体演算装置であって、
前記制御部は、前記第１処理をL/2回実行させるループ処理を、複数回実行させる、有限体演算装置。
【請求項５】
請求項３の有限体演算装置であって、
前記制御部は、前記第１処理をL/2回実行させるループ処理を、複数回実行させる、有限体演算装置。
【請求項６】
請求項１又は２の有限体演算装置であって、
N≧4であり、
前記第４演算部は、それぞれの前記第１処理によって得られた前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))の乗算値を用いてΠi=0N-1poly(R(i,0),...,R(i,K-1))∈GF(pd・m)を求める、有限体演算装置。
【請求項７】
請求項３の有限体演算装置であって、
N≧4であり、
前記第４演算部は、それぞれの前記第１処理によって得られた前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))の乗算値を用いてΠi=0N-1poly(R(i,0),...,R(i,K-1))∈GF(pd・m)を求める、有限体演算装置。
【請求項８】
請求項４の有限体演算装置であって、
N≧4であり、
前記第４演算部は、それぞれの前記第１処理によって得られた前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))の乗算値を用いてΠi=0N-1poly(R(i,0),...,R(i,K-1))∈GF(pd・m)を求める、有限体演算装置。
【請求項９】
請求項５の有限体演算装置であって、
N≧4であり、
前記第４演算部は、それぞれの前記第１処理によって得られた前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))の乗算値を用いてΠi=0N-1poly(R(i,0),...,R(i,K-1))∈GF(pd・m)を求める、有限体演算装置。
【請求項１０】
請求項６の有限体演算装置であって、
前記第４演算部は、前記第１処理が１回実行されるたびに、それまでに得られた前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))の乗算値を更新する、有限体演算装置。
【請求項１１】
請求項７の有限体演算装置であって、
前記第４演算部は、前記第１処理が１回実行されるたびに、それまでに得られた前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))の乗算値を更新する、有限体演算装置。
【請求項１２】
請求項８の有限体演算装置であって、
前記第４演算部は、前記第１処理が１回実行されるたびに、それまでに得られた前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))の乗算値を更新する、有限体演算装置。
【請求項１３】
請求項９の有限体演算装置であって、
前記第４演算部は、前記第１処理が１回実行されるたびに、それまでに得られた前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))の乗算値を更新する、有限体演算装置。
【請求項１４】
請求項１の有限体演算装置であって、
K=4であり、
前記有限体GF(pm)の元R(i,0),R(i,1),R(i,2),R(i,3)は、それぞれ、有限体GF(pm)上で定義された楕円曲線上の2つの点P(X1[i],Y1[i])及び点Q(X2[i],Y2[i])の各アフィン座標点X 1[i],Y 1[i],X 2[i],Y 2[i]∈GF(pm)であり、
前記演算e(R(i,0),...,R(i,K-1))は、ペアリング演算e(P(X1[i],Y1[i]),Q(X2[i],Y2[i]))であり、
前記演算Πi=0N-1e(R(i,0),...,R(i,K-1))は、マルチペアリング演算Πi=0N-1e(P(X1[i],Y1[i]),Q(X2[i],Y2[i]))である、有限体演算装置。
【請求項１５】
請求項１４の有限体演算装置であって、
p=3であり、d=6であり、
前記楕円曲線がY2=X3-X+bであり、b∈{-1,1}であり、
前記拡大体演算は、前記入力部に入力された各アフィン座標点X 1[i],Y 1[i],X 2[i],Y 2[i]又はその像をそれぞれx1[i],y1[i],x2[i],y2[i]とし、u[i]=x1[i]+x2[i]+c∈GF(3m)とし、有限体GF(3m)の元を係数とする既約多項式σ2+1=0の根を不定元σとし、既約多項式ρ3-ρ-b=0の根を不定元ρとした場合における、有限体GF(3m)の6次拡大体GF(36m)の元を示す多項式poly(x1[i],y1[i],x2[i],y2[i])=-{u[i]}2+y1[i]・y2[i]・σ-u[i]・ρ-ρ2∈GF(36m)を求める演算であり、
前記制御部は、cの初期値をbとし、前記第１処理をL/2回実行させるループ処理が１回実行されるたびに(c-b)mod 3を新たなcとし、
前記多項式poly(R(i1,0),...,R(i1,K-1))は、g[i1]=-{u[i1]}2+y1[i1]・y2[i1]・σ-u[i1]・ρ-ρ2∈GF(36m)であり、
前記多項式poly(R(i2,0),...,R(i2,K-1))は、g[i2]=-{u[i2]}2+y1[i2]・y2[i2]・σ-u[i2]・ρ-ρ2∈GF(36m)であり、
前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))は、g[i1]・g[i2]∈GF(36m)であり、
前記第４演算部は、それぞれの前記第１処理によって得られた前記積g[i1]・g[i2]を用いてg=Πi=0N-1poly(R(i,0),...,R(i,K-1))∈GF(3d・m)を算出する、有限体演算装置。
【請求項１６】
請求項１５の有限体演算装置であって、
前記第３演算部は、前記多項式poly(R(i1,0),...,R(i1,K-1))の予め0∈GF(pm)とされた項、及び／又は、前記多項式poly(R(i2,0),...,R(i2,K-1))の予め0∈GF(pm)とされた項、を被演算子とした演算を行うことなく、前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))を求める、有限体演算装置。
【請求項１７】
請求項１５の有限体演算装置であって、
前記制御部は、それぞれの前記第１処理のたびに、-y1[i1]を新たなy1[i1]とし、{x2[i1]}9を新たなx2[i1]とし、{y2[i1]}9を新たなy2[i1]とし、-y1[i2]を新たなy1[i2]とし、{x2[i2]}9を新たなx2[i2]とし、{y2[i2]}9を新たなy2[i2]とする更新処理を行い、
前記制御部は、前記第１処理をL/2回実行させるループ処理を、複数回実行させる、有限体演算装置。
【請求項１８】
請求項１５から１７の何れかの有限体演算装置であって、
前記有限体演算部は、
b=-1の場合には、x1[i]=X1[i], y1[i]=Y1[i], x2[i]=X2[i]，y2[i]=Y2[i]とし、b=1の場合には、x1[i]=X1[i], y1[i]=-Y1[i], x2[i]=X2[i]，y2[i]=Y2[i]とし、f=Πi=0N-1(-y1[i]・(x1[i]+x2[i]+b)+y2[i]・σ+y1[i]・ρ)∈GF(36m)の演算を行う第５演算部をさらに有し、
前記第５演算部の処理は、前記第１処理が最初に実行される前に実行される処理である、有限体演算装置。
【請求項１９】
請求項１８の有限体演算装置であって、
前記有限体演算部は、
前記第５演算部で得られたfと、前記第４演算部で得られたgとの積f・g∈GF(36m)を新たなfとする第１０演算部と、
前記第１０演算部で得られたfの３乗値f3∈GF(36m)を新たなfとする第１１演算部と、を含み、
前記第１０演算部と前記第１１演算部との処理は、前記ループ処理が１回実行されるたびに実行される、有限体演算装置。
【請求項２０】
請求項１８の有限体演算装置であって、
N≧4であり、
前記第５演算部は、
何れかのi3∈{0,...,N-1}について、f[i3]=-y1[i3]・(x1[i3]+x2[i3]+b)+y2[i3]・σ+y1[i3]・ρ∈GF(36m)の演算を行う第６演算部と、
何れかのi4∈{0,...,N-1}(i4≠i3)について、f[i4]=-y1[i4]・(x1[i4]+x2[i4]+b)+y2[i4]・σ+y1[i4]・ρ∈GF(36m)の演算を行う第７演算部と、
f[i3]とf[i4]とが入力され、それらの積f[i3]・f[i4]∈GF(3d・m)を算出する第８演算部と、
集合{0,...,N-1}のW個〔Wは正の偶数〕の互いに異なる複数の元からなる部分集合の各元をそれぞれ１回ずつi3又はi4として選択し、選択したi3とi4との組のそれぞれに対して前記第６演算部と前記第７演算部と前記第８演算部とによる第２処理をW/2回実行させる第２制御部と、
それぞれの前記第２処理によって得られた前記積f[i3]・f[i4]の乗算値を用いてf=Πi=0N-1(-y1[i]・(x1[i]+x2[i]+b)+y2[i]・σ+y1[i]・ρ)∈GF(36m)を算出する第９演算部と、を含む、有限体演算装置。
【請求項２１】
請求項２０の有限体演算装置であって、
前記有限体演算部は、
前記第５演算部で得られたfと、前記第４演算部で得られたgとの積f・g∈GF(36m)を新たなfとする第１０演算部と、
前記第１０演算部で得られたfの３乗値f3∈GF(36m)を新たなfとする第１１演算部と、を含み、
前記第１０演算部と前記第１１演算部との処理は、前記ループ処理が１回実行されるたびに実行される、有限体演算装置。
【請求項２２】
請求項１４の有限体演算装置であって、
p=3であり、d=6であり、
前記楕円曲線がY2=X3-X+bであり、b∈{-1,1}であり、
前記拡大体演算は、前記入力部に入力された各アフィン座標点X 1[i],Y 1[i],X 2[i],Y 2[i]又はその像をそれぞれx1[i],y1[i],x2[i],y2[i]とし、有限体GF(3m)の元を係数とする既約多項式σ2+1=0の根を不定元σとし、既約多項式ρ3-ρ-b=0の根を不定元ρとした場合における、有限体GF(3m)の6次拡大体GF(36m)の元を示す多項式poly(x1[i],y1[i],x2[i],y2[i])=-y1[i]・(x1[i]+x2[i]+b)+y2[i]・σ+y1[i]・ρ∈GF(36m)を求める演算である、有限体演算装置。
【請求項２３】
入力部と有限体演算部と出力部とを有する有限体演算装置の有限体演算方法であって、
(A) N・K個(N≧2,K≧1)の有限体GF(pm)の元R(i,k)∈GF(pm)〔i∈{0,...,N-1}，k∈{0,...,K-1}，pは素数，mは1以上の整数〕が前記入力部に入力されるステップと、
(B) 前記有限体演算部が、K個の前記有限体GF(pm)の元R(i,0),...,R(i,K-1)∈GF(pm)に対する有限体上の演算をe(R(i,0),...,R(i,K-1))とした場合における、演算Πi=0N-1e(R(i,0),...,R(i,K-1))を行うステップと、
(C) ステップ(B)での演算結果を前記出力部から出力するステップと、を有し、
前記有限体上の演算e(R(i,0),...,R(i,K-1))は、それぞれ、有限体GF(pm)のd次拡大体GF(pd・m)(d≧2)上の拡大体演算を一部に含み、
前記拡大体演算は、入力された１以上の有限体GF(pm)の元R(i,k)∈{R(i,0),...,R(i,K-1)}に依存する有限体GF(pm)上の像及び／又は有限体GF(pm)の元R(i,k)∈{R(i,0),...,R(i,K-1)}を、d次拡大体GF(pd・m)の元を示す多項式poly(R(i,0),...,R(i,K-1))∈GF(pd・m)に写す演算であり、
前記多項式poly(R(i,0),...,R(i,K-1))∈GF(pd・m)は、項数dの多項式であり、そのうち一部の項h∈{0,...,d-1}の係数ahが前記１以上の有限体GF(pm)の元R(i,k)に依存する有限体GF(pm)上の像及び／又は有限体GF(pm)の元R(i,k)とされ、予め定められた一部の項r∈{0,...,d-1}(r≠h)の係数arが予め0∈GF(pm)とされた多項式であり、
前記ステップ(B)は、
(B-1) 何れかのi1∈{0,...,N-1}について、１以上の有限体GF(pm)の元R(i1,k)に依存する有限体GF(pm)上の像及び／又は有限体GF(pm)の元R(i1,k)が前記有限体演算部の第１演算部に入力され、当該第１演算部がこれらに対する前記拡大体演算を行い、多項式poly(R(i1,0),...,R(i1,K-1))∈GF(pd・m)を得るステップと、
(B-2) 何れかのi2∈{0,...,N-1}(i2≠i1)について、１以上の有限体GF(pm)の元R(i2,k)に依存する有限体GF(pm)上の像及び／又は有限体GF(pm)の元R(i2,k)が前記有限体演算部の第２演算部に入力され、当該第２演算部がこれらに対する前記拡大体演算を行い、多項式poly(R(i2,0),...,R(i2,K-1))∈GF(pd・m)を得るステップと、
(B-3) 前記多項式poly(R(i1,0),...,R(i1,K-1))と前記多項式poly(R(i2,0),...,R(i2,K-1))とが前記有限体演算部の第３演算部に入力され、当該第３演算部がそれらの積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))∈GF(pd・m)を算出するステップと、を含み、
(B-4) 前記有限体演算部の第４演算部が、前記ステップ(B-1),(B-2),(B-3)を含む第１処理によって得られた前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))を用いてΠi=0N-1poly(R(i,0),...,R(i,K-1))∈GF(pd・m)を算出するステップと、を含み、
集合{0,...,N-1}に含まれるL個〔Lは偶数〕の互いに異なる複数の元からなる部分集合の各元がそれぞれ１回ずつi1又はi2として選択され、選択されたi1とi2との組のそれぞれに対して前記第１処理が１回ずつ実行されることで、L/2個の前記組のそれぞれに対応する前記第１処理を含むループ処理が実行され、
前記ステップ(B-4)は、L/2個の前記組のそれぞれに対応する前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))を用いてΠi=0N-1poly(R(i,0),...,R(i,K-1))∈GF(pd・m)を算出するステップを含む、有限体演算方法。
【請求項２４】
請求項２３の有限体演算方法であって、
前記ステップ(B-3)は、前記多項式poly(R(i1,0),...,R(i1,K-1))の予め0∈GF(pm)とされた項、及び／又は、前記多項式poly(R(i2,0),...,R(i2,K-1))の予め0∈GF(pm)とされた項、を被演算子とした演算を行うことなく、前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))を求めるステップを含む、有限体演算方法。
【請求項２５】
請求項２３又は２４の有限体演算方法であって、
Nは偶数であり、L=Nであり、前記部分集合は集合{0,...,N-1}である、有限体演算方法。
【請求項２６】
請求項２３又は２４の有限体演算方法であって、
前記第１処理をL/2回実行するループ処理を、複数回実行する、有限体演算方法。
【請求項２７】
請求項２５の有限体演算方法であって、
前記第１処理をL/2回実行するループ処理を、複数回実行する、有限体演算方法。
【請求項２８】
請求項２３又は２４の有限体演算方法であって、
N≧4であり、
前記ステップ(B-4)は、それぞれの前記第１処理によって得られた前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))の乗算値を用いてΠi=0N-1poly(R(i,0),...,R(i,K-1))∈GF(pd・m)を求めるステップを含む、有限体演算方法。
【請求項２９】
請求項２５の有限体演算方法であって、
N≧4であり、
前記ステップ(B-4)は、それぞれの前記第１処理によって得られた前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))の乗算値を用いてΠi=0N-1poly(R(i,0),...,R(i,K-1))∈GF(pd・m)を求めるステップを含む、有限体演算方法。
【請求項３０】
請求項２６の有限体演算方法であって、
N≧4であり、
前記ステップ(B-4)は、それぞれの前記第１処理によって得られた前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))の乗算値を用いてΠi=0N-1poly(R(i,0),...,R(i,K-1))∈GF(pd・m)を求めるステップを含む、有限体演算方法。
【請求項３１】
請求項２７の有限体演算方法であって、
N≧4であり、
前記ステップ(B-4)は、それぞれの前記第１処理によって得られた前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))の乗算値を用いてΠi=0N-1poly(R(i,0),...,R(i,K-1))∈GF(pd・m)を求めるステップを含む、有限体演算方法。
【請求項３２】
請求項２８の有限体演算方法であって、
前記ステップ(B-4)は、前記第１処理が１回実行されるたびに、それまでに得られた前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))の乗算値を更新するステップを含む、有限体演算方法。
【請求項３３】
請求項２９の有限体演算方法であって、
前記ステップ(B-4)は、前記第１処理が１回実行されるたびに、それまでに得られた前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))の乗算値を更新するステップを含む、有限体演算方法。
【請求項３４】
請求項３０の有限体演算方法であって、
前記ステップ(B-4)は、前記第１処理が１回実行されるたびに、それまでに得られた前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))の乗算値を更新するステップを含む、有限体演算方法。
【請求項３５】
請求項３１の有限体演算方法であって、
前記ステップ(B-4)は、前記第１処理が１回実行されるたびに、前記第１処理が１回実行されるたびに、それまでに得られた前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))の乗算値を更新するステップを含む、有限体演算方法。
【請求項３６】
請求項２３の有限体演算方法であって、
K=4であり、
前記有限体GF(pm)の元R(i,0),R(i,1),R(i,2),R(i,3)は、それぞれ、有限体GF(pm)上で定義された楕円曲線上の2つの点P(X1[i],Y1[i])及び点Q(X2[i],Y2[i])の各アフィン座標点X 1[i],Y 1[i],X 2[i],Y 2[i]∈GF(pm)であり、
前記演算e(R(i,0),...,R(i,K-1))は、ペアリング演算e(P(X1[i],Y1[i]),Q(X2[i],Y2[i]))であり、
前記演算Πi=0N-1e(R(i,0),...,R(i,K-1))は、マルチペアリング演算Πi=0N-1e(P(X1[i],Y1[i]),Q(X2[i],Y2[i]))である、有限体演算方法。
【請求項３７】
請求項３６の有限体演算方法であって、
p=3であり、d=6であり、
前記楕円曲線がY2=X3-X+bであり、b∈{-1,1}であり、
前記拡大体演算は、前記入力部に入力された各アフィン座標点X 1[i],Y 1[i],X 2[i],Y 2[i]又はその像をそれぞれx1[i],y1[i],x2[i],y2[i]とし、u[i]=x1[i]+x2[i]+c∈GF(3m)とし、有限体GF(3m)の元を係数とする既約多項式σ2+1=0の根を不定元σとし、既約多項式ρ3-ρ-b=0の根を不定元ρとした場合における、有限体GF(3m)の6次拡大体GF(36m)の元を示す多項式poly(x1[i],y1[i],x2[i],y2[i])=-{u[i]}2+y1[i]・y2[i]・σ-u[i]・ρ-ρ2∈GF(36m)を求める演算であり、
cの初期値がbとされ、前記第１処理をL/2回実行するループ処理が１回実行されるたびに(c-b)mod 3が新たなcとされ、
前記多項式poly(R(i1,0),...,R(i1,K-1))は、g[i1]=-{u[i1]}2+y1[i1]・y2[i1]・σ-u[i1]・ρ-ρ2∈GF(36m)であり、
前記多項式poly(R(i2,0),...,R(i2,K-1))は、g[i2]=-{u[i2]}2+y1[i2]・y2[i2]・σ-u[i2]・ρ-ρ2∈GF(36m)であり、
前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))は、g[i1]・g[i2]∈GF(36m)であり、
前記ステップ(B-4)は、それぞれの前記第１処理によって得られた前記積g[i1]・g[i2]を用いてg=Πi=0N-1poly(R(i,0),...,R(i,K-1))∈GF(3d・m)を算出するステップを含む、有限体演算方法。
【請求項３８】
請求項３７の有限体演算方法であって、
前記ステップ(B-3)は、前記多項式poly(R(i1,0),...,R(i1,K-1))の予め0∈GF(pm)とされた項、及び／又は、前記多項式poly(R(i2,0),...,R(i2,K-1))の予め0∈GF(pm)とされた項、を被演算子とした演算を行うことなく、前記積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))を求めるステップを含む、有限体演算方法。
【請求項３９】
請求項３７の有限体演算方法であって、
それぞれの前記第１処理のたびに、-y1[i1]を新たなy1[i1]とし、{x2[i1]}9を新たなx2[i1]とし、{y2[i1]}9を新たなy2[i1]とし、-y1[i2]を新たなy1[i2]とし、{x2[i2]}9を新たなx2[i2]とし、{y2[i2]}9を新たなy2[i2]とする更新処理が行われ、
前記第１処理をL/2回実行させるループ処理が、複数回実行される、有限体演算方法。
【請求項４０】
請求項３７から３９の何れかの有限体演算方法であって、
前記ステップ(B)は、
(B-5) b=-1の場合に、x1[i]=X1[i], y1[i]=Y1[i], x2[i]=X2[i]，y2[i]=Y2[i]とし、b=1の場合に、x1[i]=X1[i], y1[i]=-Y1[i], x2[i]=X2[i]，y2[i]=Y2[i]とし、前記有限体演算部の第５演算部が、f=Πi=0N-1(-y1[i]・(x1[i]+x2[i]+b)+y2[i]・σ+y1[i]・ρ)∈GF(36m)の演算を行うステップをさらに含み、
前記ステップ(B-5)は、前記第１処理が最初に実行される前に実行される、有限体演算方法。
【請求項４１】
請求項４０の有限体演算方法であって、
前記ステップ(B)は、
(B-10) 前記有限体演算部の第１０演算部が、前記ステップ(B-5)で得られたfと、前記ステップ(B-4)で得られたgとの積f・g∈GF(36m)を新たなfとするステップと、
(B-11) 前記有限体演算部の第１１演算部が、前記ステップ(B-6)で得られたfの３乗値f3∈GF(36m)を新たなfとするステップと、を含み、
前記ステップ(B-10)と前記ステップ(B-11)との処理は、前記ループ処理が１回実行されるたびに実行される、有限体演算方法。
【請求項４２】
請求項４０の有限体演算方法であって、
N≧4であり、
前記ステップ(B-5)は、
(B-6) 前記有限体演算部の第６演算部が、何れかのi3∈{0,...,N-1}について、f[i3]=-y1[i3]・(x1[i3]+x2[i3]+b)+y2[i3]・σ+y1[i3]・ρ∈GF(36m)の演算を行うステップと、
(B-7) 前記有限体演算部の第７演算部が、何れかのi4∈{0,...,N-1}(i4≠i3)について、f[i4]=-y1[i4]・(x1[i4]+x2[i4]+b)+y2[i4]・σ+y1[i4]・ρ∈GF(36m)の演算を行うステップと、
(B-8) 前記有限体演算部の第８演算部が、f[i3]とf[i4]とを入力とし、それらの積f[i3]・f[i4]∈GF(3d・m)を算出するステップと、
(B-9) 前記有限体演算部の第９演算部が、前記ステップ(B-6)と前記ステップ(B-7)と前記ステップ(B-8)とを含む第２処理によって得られた前記積f[i3]・f[i4]の乗算値を用いてf=Πi=0N-1(-y1[i]・(x1[i]+x2[i]+b)+y2[i]・σ+y1[i]・ρ)∈GF(36m)を算出するステップと、を含み、
集合{0,...,N-1}に含まれるW個〔Wは正の偶数〕の互いに異なる複数の元からなる部分集合の各元がそれぞれ１回ずつi3又はi4として選択され、選択されたi3とi4との組のそれぞれに対して前記第２処理が１回ずつ実行されることで、W/2個の上記組(i3, i4)のそれぞれに対応する第２処理が実行される、有限体演算方法。
【請求項４３】
請求項４２の有限体演算方法であって、
前記ステップ(B)は、
(B-10) 前記有限体演算部の第１０演算部が、前記ステップ(B-5)で得られたfと、前記ステップ(B-4)で得られたgとの積f・g∈GF(36m)を新たなfとするステップと、
(B-11) 前記有限体演算部の第１１演算部が、前記ステップ(B-6)で得られたfの３乗値f3∈GF(36m)を新たなfとするステップと、を含み、
前記ステップ(B-10)と前記ステップ(B-11)との処理は、前記ループ処理が１回実行されるたびに実行される、有限体演算方法。
【請求項４４】
請求項３６の有限体演算方法であって、
p=3であり、d=6であり、
前記楕円曲線がY2=X3-X+bであり、b∈{-1,1}であり、
前記拡大体演算は、前記入力部に入力された各アフィン座標点X 1[i],Y 1[i],X 2[i],Y 2[i]又はその像をそれぞれx1[i],y1[i],x2[i],y2[i]とし、有限体GF(3m)の元を係数とする既約多項式σ2+1=0の根を不定元σとし、既約多項式ρ3-ρ-b=0の根を不定元ρとした場合における、有限体GF(3m)の6次拡大体GF(36m)の元を示す多項式poly(x1[i],y1[i],x2[i],y2[i])=-y1[i]・(x1[i]+x2[i]+b)+y2[i]・σ+y1[i]・ρ∈GF(36m)を求める演算である、有限体演算方法。
【請求項４５】
請求項１の有限体演算装置としてコンピュータを機能させるためのプログラム。
【請求項４６】
請求項１の有限体演算装置としてコンピュータを機能させるためのプログラムを格納したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号技術に関し、特に有限体上の演算技術に関する。
【背景技術】
【０００２】
ペアリングを利用した暗号方式の実用化に伴い、近年、ペアリングを効率的に実装するための研究が盛んに行われている。ペアリングとは、２入力１出力の双線形性関数である。現在の暗号技術では、有限体GF(pm)(pは素数、mは1以上の整数)上で定義された楕円曲線上の2つの点P(x1,y1),Q(x2,y2)(x1,y1,x2,y2∈GF(pm))を入力とし、有限体GF(pm)の拡大体GF(pd・m)の１つの元ηT(P,Q)∈GF(3d・m)を出力するペアリング
e(P(x1,y1),Q(x2,y2))→ηT(P,Q)      …(1)
が用いられる。【０００３】
ペアリングを多項式時間で計算するためのアルゴリズムとして最初に提案されたのは、Tateペアリングを計算するためのMillerアルゴリズムである。その後、Millerアルゴリズムに比べて再帰回数を半減させたηＴペアリングアルゴリズムが提案され、さらに、ηＴペアリングアルゴリズムに含まれる３乗根演算を取り除き、さらなる高速化を実現した改良ηＴペアリングアルゴリズムが提案された（例えば、非特許文献１等参照）。以下に、改良ηＴペアリングアルゴリズムの概要を示す。【０００４】
＜改良ηＴペアリング演算アルゴリズム＞
[準備]
Eb： EbはY2=X3-X+b (b∈{-1,1})を表す。Ebは有限体GF(3m)上で定義された超特異楕円曲線である。
σ： σは有限体GF(3m)の元を係数とする既約多項式σ2+1=0の根となる不定元を表す。
ρ： ρは有限体GF(3m)の元を係数とするρ3-ρ-b=0の根となる不定元を表す。
[入力] P(x1,y1),Q(x2,y2)(x1,y1,x2,y2∈GF(3m))
[出力] ηT(P,Q)∈GF(36m)
[計算方法]
Step1: y1=-y1∈GF(3m)（b=1の場合のみ）
Step2: u=x1+x2+b∈GF(3m)
Step3: c=b
Step4: f=-y1・u+y2・σ+y1・ρ∈GF(36m)
Step5: j=0から(m-1)/2までjを1ずつ増加させながらStep5-1〜Step5-8を繰り返す。 【０００５】
Step5-1: u=x1+x2+c∈GF(3m)
Step5-2: g=-u2+y1・y2・σ-u・ρ-ρ2∈GF(36m)
Step5-3: f=f・g∈GF(36m)
Step5-4: f=f3∈GF(36m)
Step5-5: y1=-y1∈GF(3m)
Step5-6: x2=x29∈GF(3m)
Step5-7: y2=y29∈GF(3m)
Step5-8: c=(c-b)mod3∈GF(3)
Step6:ffinalpow∈GF(36m)〔finalpow=(33m-1)(3m+1)(3m-3(m+1)/2+1)〕出力。【０００６】
また、非特許文献２には、ループ変換の一種である「ループアンローリング（Loop Unrolling）」の技術をηＴペアリング演算に適用したアルゴリズムが開示されている。「ループアンローリング」とは、ループの繰り返しごとに発生するループ終了条件の判定処理を減少させることによって実行速度を向上させる技術である。非特許文献２の方法では、基本的なアルゴリズムでは２回のループで実行している処理を１回のループの中で実行し、ループの繰り返し回数を半減させることで、ループ終了条件の判定処理を半減させている。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Beuchat, J.-L.; Shirase, M.; Takagi, T.; Okamoto, "An Algorithm for the ηT Pairing Calculation in Characteristic Three and its Hardware Implementation", Proceedings of the 18th IEEE Symposium on Computer Arithmetic,Institute of Electrical and Electronics Engineers, 25-27 June 2007, pp. 97-104
【非特許文献２】Beuchat, J.-L.; Brisebarre, N.; Detrey, J.; Okamoto, E.; Shirase, M.; Takagi, T., "Algorithms and Arithmetic Operators for Computing the ηT Pairing in Characteristic Three", IEEE transactions on computers, Institute of Electrical and Electronics Engineers, Nov. 2008, Volume 57, Issue 11, pp.1454-1468
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上述の引用文献１，２に開示されているのは、１つのペアリングを効率的に計算するための方式のみであり、複数のペアリングの積を効率的に計算する方式については開示されていない。【０００９】
すなわち、有限体GF(pm)上で定義された楕円曲線上の2つの点P(X1[i],Y1[i]),Q(X2[i],Y2[i])(X 1[i],Y1[i],X 2[i],Y2[i]∈GF(pm))を入力とし、有限体GF(pm)の拡大体GF(pd・m)の１つの元ηT(P[i],Q[i])∈GF(3d・m)を出力するペアリングを
e(P(X1[i],Y1[i]),Q(X2[i],Y2[i]))→ηT(P[i],Q[i])      …(2)
とした場合に、N≧2に対する
Πi=0N-1e(P(X1[i],Y1[i]),Q(X2[i],Y2[i]))      …(3)
を効率的に計算する方式は開示されていない。【００１０】
そのため、引用文献１，２等の従来の方式を用いて式(3)の計算を行う場合には、各i=0,...,N-1についてそれぞれ独立に式(2)の計算を行い、それぞれの計算で得られた演算結果ηT(P[i],Q[i])を乗じることによって式(3)の演算結果を得ることになる。例えば、「ループアンローリング」の技術を用いる場合であっても、「ループアンローリング」の対象となるのは、各i∈{0,...,N-1}についてそれぞれ独立に実行される式(2)を計算するためのループ処理（再帰処理）のみであり、異なるiについてのペアリング演算を協働させながら実行する演算方式は開示されていない。【００１１】
このようなことはペアリングに限られたものではなく、N・K個(N≧2,K≧1)の有限体GF(pm)の元R(i,k)∈GF(pm)〔i∈{0,...,N-1}，k∈{0,...,K-1}，pは素数，mは1以上の整数〕が入力され、K個の有限体GF(pm)の元R(i,0),...,R(i,K-1)∈GF(pm)〔i∈{0,...,N-1}に対する有限体上の演算を
e(R(i,0),...,R(i,K-1))      …(4)
とした場合における、演算
Πi=0N-1e(R(i,0),...,R(i,K-1))       …(5)
を計算する場合でも同様である。【００１２】
図１は、式(5)を計算するための従来手法を説明するための概念図である。なお、図１は、N=6,i=0,...,5の場合の例である。【００１３】
図１に例示するように、従来手法で式(5)を計算する場合には、各iについてそれぞれ独立に有限体GF(pm)演算や拡大体GF(pm)演算からなる複数の演算（点線で囲まれた演算）を実行する。そして、それらの演算によって各iについてそれぞれ独立に得られた演算結果e(R(i,0),...,R(i,K-1))を拡大体GF(pm)上で乗じることで式(5)の演算結果を得ることになる。【００１４】
しかしながら、異なるiについての式(4)の演算の協働方法を工夫することで、式(5)の演算をより効率的に演算できる余地がある。【００１５】
本発明はこのような点に鑑みてなされたものであり、K個の有限体GF(pm)の元R(i,0),...,R(i,K-1)∈GF(pm)に対する有限体上の演算をe(R(i,0),...,R(i,K-1))とした場合における演算Πi=0N-1e(R(i,0),...,R(i,K-1))を効率的に演算する技術を提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明では、N・K個(N≧2,K≧1)の有限体GF(pm)の元R(i,k)∈GF(pm)〔i∈{0,...,N-1}，k∈{0,...,K-1}，pは素数，mは1以上の整数〕が入力され、有限体演算部が、K個の有限体GF(pm)の元R(i,0),...,R(i,K-1)∈GF(pm)に対する有限体上の演算をe(R(i,0),...,R(i,K-1))とした場合における、演算Πi=0N-1e(R(i,0),...,R(i,K-1))を行い、その演算結果を出力する。【００１７】
上記有限体上の演算e(R(i,0),...,R(i,K-1))は、それぞれ、有限体GF(pm)のd次拡大体GF(pd・m)(d≧2)上の拡大体演算を一部に含む。当該拡大体演算は、入力された１以上の有限体GF(pm)の元R(i,k)∈{R(i,0),...,R(i,K-1)}に依存する有限体GF(pm)上の像及び／又は有限体GF(pm)の元R(i,k)∈{R(i,0),...,R(i,K-1)}を、d次拡大体GF(pd・m)の元を示す多項式poly(R(i,0),...,R(i,K-1))∈GF(pd・m)に写す演算である。なお、多項式poly(R(i,0),...,R(i,K-1))∈GF(pd・m)は項数dの多項式であり、そのうち一部の項h∈{0,...,d-1}の係数ahが１以上の有限体GF(pm)の元R(i,k)に依存する有限体GF(pm)上の像及び／又は有限体GF(pm)の元R(i,k)とされ、予め定められた一部の項r∈{0,...,d-1}(r≠h)の係数arが予め0∈GF(pm)とされたものである。すなわち、当該多項式poly(R(i,0),...,R(i,K-1))∈GF(pd・m)の少なくとも一部の係数は必ず0となる。【００１８】
また、上記有限体演算部の第１演算部が、何れかのi1∈{0,...,N-1}について、１以上の有限体GF(pm)の元R(i1,k)に依存する有限体GF(pm)上の像及び／又は有限体GF(pm)の元R(i1,k)が入力され、これらに対する上記拡大体演算を行い、それによって得られる多項式poly(R(i1,0),...,R(i1,K-1))∈GF(pd・m)を出力する。また、上記有限体演算部の第２演算部が、何れかのi2∈{0,...,N-1}(i2≠i1)について、１以上の有限体GF(pm)の元R(i2,k)に依存する有限体GF(pm)上の像及び／又は有限体GF(pm)の元R(i2,k)が入力され、これらに対する上記拡大体演算を行い、それによって得られる多項式poly(R(i2,0),...,R(i2,K-1))∈GF(pd・m)を出力する。そして、上記有限体演算部の第３演算部が、多項式poly(R(i1,0),...,R(i1,K-1))と多項式poly(R(i2,0),...,R(i2,K-1))とが入力され、それらの積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))∈GF(pd・m)を求め、当該積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))を出力する。【００１９】
そして、集合{0,...,N-1}に含まれるL個〔Lは偶数〕の互いに異なる複数の元からなる部分集合の各元をそれぞれ１回ずつi1又はi2として選択し、選択したi1とi2との組のそれぞれに対して第１演算部と第２演算部と第３演算部とによる処理が１回ずつ実行されることで、L/2個の前記組のそれぞれに対応する上記処理を含むループ処理が実行され、それぞれの処理によって得られた積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))を用いてΠi=0N-1poly(R(i,0),...,R(i,K-1))∈GF(pd・m)を求める。【００２０】
上述のように、多項式poly(R(i1,0),...,R(i1,K-1))∈GF(pd・m)と、多項式poly(R(i2,0),...,R(i2,K-1))∈GF(pd・m) と、のそれぞれの少なくとも一部の係数は必ず0となる。このような多項式同士の積を先に計算することで、0となる係数についての演算を不要とし、積の演算量を削減する。
【発明の効果】
【００２１】
本発明では、K個の有限体GF(pm)の元R(i,0),...,R(i,K-1)∈GF(pm)に対する有限体上の演算をe(R(i,0),...,R(i,K-1))とした場合における演算Πi=0N-1e(R(i,0),...,R(i,K-1))を効率的に演算できる。
【図面の簡単な説明】
【００２２】
【図１】図１は、式(5)を計算するための従来手法を説明するための概念図である。
【図２】図２Ａは、本形態の有限体演算装置の基本構成を説明するためのブロック図である。図２Ｂは、有限体演算部が含む４つのGF(pd・m)演算部の構成を説明するためのブロック図である。
【図３】図３は、実施形態の有限体演算装置の処理の概要を説明するための図である。
【図４】図４は、演算部の演算の特徴を説明するための図である。
【図５】図５は、第１実施形態の有限体演算部の基本構成を説明するためのブロック図である。
【図６】図６は、第１実施形態の有限体演算部の基本構成を説明するためのブロック図である。
【図７】図７は、第１実施形態の処理を説明するための図である。
【図８】図８は、第１実施形態の処理を説明するための図である。
【図９】図９は、第１実施形態の処理を説明するための図である。
【図１０】図１０は、第１実施形態の処理を説明するための図である。
【図１１】図１１は、Nが5以上の奇数である場合の処理を例示するための図である。
【図１２】図１２は、第２実施形態の有限体演算部の基本構成を説明するためのブロック図である。
【図１３】図１３は、第２実施形態の有限体演算部の基本構成を説明するためのブロック図である。
【図１４】図１４は、第２実施形態の処理を説明するための図である。
【図１５】図１５は、第２実施形態の処理を説明するための図である。
【図１６】図１６は、Nが5以上の奇数である場合の処理を例示するための図である。
【図１７】図１７は、第３実施形態の有限体演算部の基本構成を説明するためのブロック図である。
【図１８】図１８は、第３実施形態の有限体演算部の基本構成を説明するためのブロック図である。
【図１９】図１９は、第３実施形態の処理を説明するための図である。
【図２０】図２０は、第３実施形態の処理を説明するための図である。
【発明を実施するための形態】
【００２３】
以下、図面を参照して本発明の実施形態を説明する。
【００２４】
〔定義〕
まず、本形態で使用する用語や記号を定義する。
p：pは正の素数を表す。pの具体例は2や3などである。
m：mは1以上の整数を表す。mの具体例は奇数や3以上の素数であり、暗号技術では、m=97,167,193,239,353,509などが用いられることが多い。
d：dは2以上の整数を表す。
L：Lは正の偶数を表す。
N：Nは2以上の整数を表す。
K：Kは1以上の整数を表す。
i：iは集合{0,...,N-1}の要素を表す。
k：kは集合{0,...,K-1}の要素を表す。
【００２５】
GF(p)：GF(p)は位数（要素数）pの有限体を表す。位数pが素数であるためGF(p)は素体である。有限体GF(p)は、例えば、pを法とした剰余
β mod p      …(6)
によって構成できる。また、有限体GF(p)上の演算は、例えば、pを法とした剰余演算によって容易に構成できる。例えば、有限体GF(p)上の積β・γ∈GF(p)は(β・γ)mod pによって実現でき、有限体GF(p)上の加算β+γ∈GF(p)は(β+γ)mod pによって実現できる。
【００２６】
GF(pm)：m≧2の場合には、GF(pm)は有限体GF(p)をm次拡大した位数pmの拡大体を表す。m=1の場合には、GF(pm)はGF(pm)=GF(p)となる素体を表す。
【００２７】
なお、有限体GF(p)をm次拡大した拡大体GF(pm)は、有限体GF(p)を係数とする既約多項式の根を不定元とし、有限体GF(p)の元を係数とした項数mの１変数又は他変数の多項式によって構成できる。例えば、１変数多項式によって拡大体GF(pm)を構成する場合、拡大体GF(pm)は、有限体GF(p)を係数とするm次の既約多項式ipoly(ω)=0の根をω∈GF(pm)とし、有限体GF(p)の元を係数κ0,...,κm-1∈GF(p)とした多項式
κ0+κ1・ω+...+κm-1・ωm-1∈GF(pm)       …(7)
となる。また、有限体GF(p)の元を拡大体GF(pm)の元へ写す具体的な写像の例は、distortion写像である。なお、「係数」は、定数項の係数をも含む概念である。
【００２８】
また、拡大体GF(pm)上の加算は、拡大体GF(pm)を示す多項式間の加算によって実現できる。ただし、当該多項式間の加算における係数間の加算は有限体GF(p)上の加算となる。例えば、κ0+κ1・ω+...+κm-1・ωm-1∈GF(pm)とν0+ν1・ω+...+νm-1・ωm-1∈GF(pm)(ν0,...,νm-1∈GF(p))との加算結果は、{(κ0+ν0)+(κ1+ν1)・ω+...+(κm-1+νm-1)・ωm-1}∈GF(pm)となる。ただし、(κ0+ν0)∈GF(p),(κ1+ν1)∈GF(p),...,(κm-1+νm-1)∈GF(p)である。
【００２９】
また、拡大体GF(pm)上の乗算は、拡大体GF(pm)を示す多項式間の乗算結果に対し、その多項式の不定元を根にもつ既約多項式を法とした剰余をとることで実現できる。例えば、κ0+κ1・ω+...+κm-1・ωm-1∈GF(pm)とν0+ν1・ω+...+νm-1・ωm-1∈GF(pm)との乗算は、(κ0+κ1・ω+...+κm-1・ωm-1)・(ν0+ν1・ω+...+νm-1・ωm-1)に対し、既約多項式ipoly(ω)を法とした剰余をとることで実現できる。具体的には、(κ0+κ1・ω+...+κm-1・ωm-1)・(ν0+ν1・ω+...+νm-1・ωm-1)にipoly(ω)=0を代入して得られたm次以下の多項式が拡大体GF(pm)上の積となる。
【００３０】
GF(pd・m)：GF(pd・m)は有限体GF(pm)をd次拡大したd次拡大体を表す。有限体GF(pm)のd次拡大体GF(pd・m)は、有限体GF(pm)を係数とする既約多項式の根を不定元とし、有限体GF(pm)の元を係数とした項数dの１変数又は他変数の多項式によって構成できる。上記では１変数多項式によって拡大体を構成する例を示したため、ここでは２変数多項式によって6次拡大体を構成する例を示す。
【００３１】
有限体GF(pm)を係数とする既約多項式ipoly1(σ)=0の根をσ∈GF(p6m)とし、有限体GF(pm)を係数とするipoly2(ρ)=0の根をρ∈GF(p6m)とすると、有限体GF(p6m)の元は、有限体GF(pm)の元を係数a5,...,a0∈GF(pm)とした多項式
a0+a1・ρ+a2・ρ2+a3・σ+a4・ρ・σ+a5・ρ2・σ∈GF(p6m)   …(8)
で表現できる。なお、p=3の場合のipoly1(σ)=0の具体例はσ2+1=0であり、ipoly2(σ)=0の具体例はρ3-ρ-b=0(b∈{-1,1})である。なお、有限体GF(pm)の元を拡大体GF(p6m)の元へ写す具体的な写像の例は、distortion写像である。
【００３２】
また、d次拡大体GF(pd・m)上の加算は、d次拡大体GF(pd・m)を示す多項式間の加算によって実現できる。ただし、当該多項式間の加算における係数間の加算は有限体GF(pm)上の加算となる。例えば、a0+a1・ρ+a2・ρ2+a3・σ+a4・ρ・σ+a5・ρ2・σ∈GF(p6m)とν0+a1・ρ+ν2・ρ2+ν3・σ+ν4・ρ・σ+ν5・ρ2・σ∈GF(p6m)(ν5,...,ν0∈GF(pm))との加算結果は、{(a0+ν0)+(a1+ν1)・ρ+(a2+ν2)・ρ2+(a3+ν3)・σ+(a4+ν4)・ρ・σ+(a5+ν5)・ρ2・σ}∈GF(p6m)。ただし、(a0+ν0)∈GF(pm),(a1+ν1)∈GF(pm),...,(a5+ν5)∈GF(pm)である。
【００３３】
また、d次拡大体GF(pd・m)上の乗算は、d次拡大体GF(pd・m)を示す多項式間の乗算結果に対し、その多項式の不定元を根にもつ既約多項式を法とした剰余をとることで実現できる。例えば、a0+a1・ρ+a2・ρ2+a3・σ+a4・ρ・σ+a5・ρ2・σ∈GF(p6m)とν0+a1・ρ+ν2・ρ2+ν3・σ+ν4・ρ・σ+ν5・ρ2・σ∈GF(p6m)との乗算は、(a0+a1・ρ+a2・ρ2+a3・σ+a4・ρ・σ+a5・ρ2・σ)・(ν0+a1・ρ+ν2・ρ2+ν3・σ+ν4・ρ・σ+ν5・ρ2・σ)に対し、既約多項式ipoly1(σ)やipoly2(ρ)を法とした剰余をとることで実現できる。具体的には、(a0+a1・ρ+a2・ρ2+a3・σ+a4・ρ・σ+a5・ρ2・σ)・(ν0+a1・ρ+ν2・ρ2+ν3・σ+ν4・ρ・σ+ν5・ρ2・σ)にipoly1(σ)=0やipoly2(ρ)=0を代入して得られた6次以下の多項式が拡大体GF(p6m)上の積となる。
【００３４】
なお、以下に説明する各処理における、多項式の入力や多項式の演算や多項式の出力は、不定元と係数とを含む多項式そのものの入力、演算、出力であってもよいし、多項式を特定する係数からなるベクトルの入力、演算、出力であってもよい。
【００３５】
R(i,k): R(i,k)は有限体GF(pm)の元を表す。
E：Eは有限体GF(pm)上で定義された楕円曲線を表す。アフィン（affine）座標版のWeierstrass方程式
Y2+A1・X・Y+A3・Y=X3+A2・X2+A4・X+A6          …(9)
（ただし、A1,A 2,A 3,A4,A 6∈GF(pm)）を満たすX,Y∈GF(pm)からなる点(X,Y)の集合に無限遠点と呼ばれる特別な点Ｏを付加したもので定義される。
【００３６】
Eb：Ebは有限体GF(3m)上で定義された超特異楕円曲線を表す。
Y2=X3-X+b (b∈{-1,1})          …(10)
e(R(i,0),...,R(i,K-1))：e(R(i,0),...,R(i,K-1))はK個の有限体GF(pm)の元R(i,0),...,R(i,K-1)∈GF(pm)に対する有限体上の演算を表す。K=4の場合のe(R(i,0),...,R(i,K-1))の具体例は、R(i,0),R(i,1),R(i,2),R(i,3)を、それぞれ、有限体GF(pm)上で定義された楕円曲線E上の2つの点P(X1[i],Y1[i])及び点Q(X2[i],Y2[i])の各アフィン座標点X 1[i],Y 1[i],X 2[i],Y 2[i]∈GF(pm)としたペアリング演算e(P(X1[i],Y1[i]),Q(X2[i],Y2[i]))である。また、ペアリング演算e(P(X1[i],Y1[i]),Q(X2[i],Y2[i]))の具体例は、TateペアリングやηTペアリングや改良ηＴペアリング演算などの標数３(p=3)のペアリング演算や、標数２(p=2)のペアリング演算である。
【００３７】
〔概要〕
次に、本形態の概要を説明する。
＜構成＞
図２Ａは、本形態の有限体演算装置１の基本構成を説明するためのブロック図である。また、図２Ｂは、有限体演算部２０が含む４つのGF(pd・m)演算部２２−１〜４の構成を説明するためのブロック図である。
【００３８】
図２Ａに例示するように、本形態の有限体演算装置１は、入力部１０と、有限体演算部２０と、出力部３０とを有する。有限体演算部２０は、有限体GF(pm)上の演算を行う１以上のGF(pm)演算部２１−１〜α1（α1≧1）と、有限体GF(pd・m)上の演算を行う４以上のGF(pd・m)演算部２２−１〜α2（α2≧４）と、制御部２３と、メモリ２４とを有する。なお、有限体演算装置１は、CPU(central processing unit)，RAM(random-access memory)，ROM(read-only memory)，入出力インタフェース等を備えた公知のコンピュータに所定のプログラムが読み込まれて構成される。すなわち、GF(pm)演算部２１−１〜α1、GF(pd・m)演算部２２−１〜α2及び制御部２３は、所定のプログラムがCPUに読み込まれて構築される機能部であり、メモリ２４は、RAM、キャッシュメモリ、レジスタ、ハードディスク等である。また、有限体演算部２０の少なくとも一部が集積回路によって構成されてもよい。
【００３９】
＜処理＞
次に、本形態の有限体演算装置１の処理の概要を説明する。
図３は、本形態の有限体演算装置１の処理の概要を説明するための図である。また、図４は、演算部２２−３の演算の特徴を説明するための図である。なお、図３はN=6の場合の一例を示し、図４はd=6の場合の一例を示すが、これらは本発明を限定しない。また、以下では、逐一説明しないが、有限体演算装置１で実行される各処理は制御部２３の制御のもと実行される。また、各演算部から出力されたデータは、逐一、メモリ２４に格納される。メモリ２４に格納されたデータは、必要に応じて演算部から読み出され、その演算部での演算に利用される。
【００４０】
有限体演算装置１での処理が開始されると、まず、その入力部１０にN・K個の有限体GF(pm)の元R(i,k)∈GF(pm)が入力され、これらの元R(i,k)∈GF(pm)は有限体演算部２０に送られる。有限体演算部２０は、K個の有限体GF(pm)の元R(i,0),...,R(i,K-1)∈GF(pm)に対する有限体上の演算をe(R(i,0),...,R(i,K-1))とした場合における、演算Πi=0N-1e(R(i,0),...,R(i,K-1))を行い、その演算結果を出力部３０に送る。出力部３０は送られた演算結果を出力する。
【００４１】
［演算e(R(i,0),...,R(i,K-1))が含む拡大体演算］
有限体上の演算e(R(i,0),...,R(i,K-1))は、それぞれ、有限体GF(pm)のd次拡大体GF(pd・m)(d≧2)上の拡大体演算を一部に含む。当該拡大体演算は、入力された１以上の有限体GF(pm)の元R(i,k)∈{R(i,0),...,R(i,K-1)}に依存する有限体GF(pm)上の像及び／又は有限体GF(pm)の元R(i,k)∈{R(i,0),...,R(i,K-1)} を、d次拡大体GF(pd・m)の元を示す多項式poly(R(i,0),...,R(i,K-1))∈GF(pd・m)に写す演算である。すなわち、当該拡大体演算は、有限体GF(pm)からd次拡大体GF(pd・m)への写像である。
【００４２】
また、当該拡大体演算によって得られる多項式poly(R(i,0),...,R(i,K-1))∈GF(pd・m)は、一部の項h∈{0,...,d-1}の係数ahが１以上の有限体GF(pm)の元R(i,k)に依存する有限体GF(pm)上の像及び／又は有限体GF(pm)の元R(i,k)とされ、予め定められた一部の項r∈{0,...,d-1}(r≠h)の係数arが予め0∈GF(pm)とされている。ここで、d次拡大体GF(pd・m)の元を示す多項式poly(R(i,0),...,R(i,K-1))∈GF(pd・m)の項数は２以上（d≧2）であるため、有限体GF(pm)の元を、一部の項の係数が予め0∈GF(pm)とされた多項式に写すことは可能である。
【００４３】
なお、このような拡大体演算の具体例は、前述の「改良ηＴペアリング演算アルゴリズム」の6次拡大体GF(36m)上の演算である。すなわち、以下の式(11)や式(12)の演算は、上述の拡大体演算の具体例である。
f=-y1・u+y2・σ+y1・ρ∈GF(36m)      …(11)
g=-u2+y1・y2・σ-u・ρ-ρ2∈GF(36m)       …(12)
【００４４】
なお、これらはp=3,d=6,K=4の場合の例であり、R(i,0),R(i,1),R(i,2),R(i,3)を、それぞれ、超特異楕円曲線Eb（式(10)）上の2つの点P(X1,Y1)及び点Q(X2,Y2)の各アフィン座標点X1,Y 1,X 2,Y 2∈GF(3m)とし、当該各アフィン座標点X1,Y1,X2,Y2又はその像をそれぞれx1,y1,x2,y2∈GF(3m)とし、u=x1+x2+c∈GF(3m)とし、既約多項式をσ2+1=0及びρ3-ρ-b=0としたものである。
【００４５】
前述のように、有限体GF(pm)の6次拡大体GF(p6m)の元を示す多項式の項数の最大値は6であるが、多項式「f=-y1・u+y2・σ+y1・ρ∈GF(36m)」は、不定元ρ2，ρ・σ，ρ2・σ∈GF(p6m)の項の係数が予め0とされており、多項式「g=-u2+y1・y2・σ-u・ρ-ρ2∈GF(36m)」は、不定元ρ・σ，ρ2・σ∈GF(p6m)の項の係数が予め0とされている（式(8)参照）。すなわち、式(11)(12)は以下の式(13)(14)のように表現できる。
f=-y1・u+y1・ρ+0・ρ2+y2・σ+0・ρ・σ+0・ρ2・σ∈GF(36m)  …(13)
g=-u2-u・ρ-ρ2+y1・y2・σ+0・ρ・σ+0・ρ2・σ∈GF(36m)  …(14)
【００４６】
その他、以下に示すdistortion写像も上述の特徴を持つ拡大体演算の一例である。
-ｘ2+ρ∈GF(36m)      …(15)
y2・σ∈GF(36m)       …(16)
【００４７】
式(15)(16)は以下の式(17)(18)のように表現できる。
-ｘ2+ρ+0・ρ2+0・σ+0・ρ・σ+0・ρ2・σ∈GF(p6m)  …(17)
0+0・ρ+0・ρ2+y2・σ+0・ρ・σ+0・ρ2・σ∈GF(p6m)   …(18)
同様な例は、位数pmの有限体GF(pm)の元を、それよりも位数が大きな位数pd・m(d≧2)のd次拡大体GF(3d・m)に写像する演算において数多く存在する。
【００４８】
［有限体演算部２０の演算］
上述の演算e(R(i,0),...,R(i,K-1))が含む拡大体演算は、有限体演算部２０が含む図２Ｂに示したGF(pd・m)演算部２２によって実行される。
【００４９】
まず、このGF(pd・m)演算部２２の演算部２２−１（第１演算部）に、１以上の有限体GF(pm)の元R(i1,k)(i1∈{0,...,N-1})に依存する有限体GF(pm)上の像及び／又は有限体GF(pm)の元R(i1,k)が入力される。なお、「１以上の有限体GF(pm)の元R(i1,k)に依存する有限体GF(pm)上の像」は、有限体演算部２０の何れかのGF(pm)演算部２1によって行われた演算結果である。その具体例は、前述の「改良ηＴペアリング演算アルゴリズム」の有限体GF(3m)上の演算結果である。すなわち、以下の演算結果が「１以上の有限体GF(pm)の元R(i1,k)に依存する有限体GF(pm)上の像」の具体例である。
y1=-y1∈GF(3m)       …(19)
u=x1+x2+b∈GF(3m)    …(20)
u=x1+x2+c∈GF(3m)    …(21)
y1=-y1∈GF(3m)       …(22)
x2=x29∈GF(3m)       …(23)
y2=y29∈GF(3m)       …(24)
【００５０】
なお、これらは、有限体GF(pm)の元R(i,0),R(i,1),R(i,2),R(i,3)を、それぞれ、超特異楕円曲線Eb（式(10)）上の2つの点P(X1,Y1)及び点Q(X2,Y2)の各アフィン座標点X1,Y 1,X 2,Y 2∈GF(3m)とし、当該各アフィン座標点X1,Y1,X2,Y2又はその像をそれぞれx1,y1,x2,y2∈GF(3m)とした場合の例である。同様な有限体GF(pm)上の演算は数多く存在する。
【００５１】
演算部２２−１は、１以上の有限体GF(pm)の元R(i1,k)に依存する有限体GF(pm)上の像及び／又は有限体GF(pm)の元R(i1,k)に対する上述の拡大体演算を行い、それによって得られる多項式
poly(R(i1,0),...,R(i1,K-1))∈GF(pd・m)       …(25)
を出力する。
【００５２】
次に、当該GF(pd・m)演算部２２の演算部２２−２（第２演算部）に、１以上の有限体GF(pm)の元R(i2,k)(i2∈{0,...,N-1}(i2≠i1))に依存する有限体GF(pm)上の像及び／又は有限体GF(pm)の元R(i2,k)が入力される。なお、「１以上の有限体GF(pm)の元R(i2,k)に依存する有限体GF(pm)上の像」は、有限体演算部２０の何れかのGF(pm)演算部２1によって行われた演算結果である。演算部２２−２は、これらに対する上述の拡大体演算を行い、それによって得られる多項式
poly(R(i2,0),...,R(i2,K-1))∈GF(pd・m)       …(26)
を出力する。
【００５３】
次に、当該GF(pd・m)演算部２２の演算部２２−３（第３演算部）に、上述の多項式poly(R(i1,0),...,R(i1,K-1))と多項式poly(R(i2,0),...,R(i2,K-1))とが入力される。演算部２２−３は、それらの積
poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))∈GF(pd・m)…(27)
を求め、当該積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))∈GF(pd・m)を出力する。
【００５４】
なお、本形態の演算部２２−３は、多項式poly(R(i1,0),...,R(i1,K-1))の予め0∈GF(pm)とされた項、及び／又は、多項式poly(R(i2,0),...,R(i2,K-1))の予め0∈GF(pm)とされた項、を被演算子とした演算を行うことなく、積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))を求める。図４の例では、演算部２２−１からpoly(R(i1,0),...,R(i1,K-1))=a0[i1]+a1[i1]・ρ+a2[i1]・ρ2+a3[i1]・σ+0・ρ・σ+0・ρ2・σが出力され、演算部２２−２からpoly(R(i2,0),...,R(i2,K-1))=a0[i2]+a1[i2]・ρ+a2[i2]・ρ2+a3 [i2]・σ+0・ρ・σ+0・ρ2・σが出力され、演算部２２−３がこれらの6次拡大体GF(p6m)上の積を求める。この例では、各多項式の不定元ρ・σ及びρ2・σの係数が予め0に定められており、不定元ρ・σ及びρ2・σの係数を被演算子とした演算は行われない。このように、本形態では、一部の項の係数が予め0に定められた多項式同士で乗算を行うことによって演算量を削減する。
【００５５】
制御部２３は、集合{0,...,N-1}のL個〔Lは偶数〕の異なる元からなる部分集合の各元をそれぞれ１回ずつi1又はi2とし、i1とi2とを変更しながら演算部２２−１〜２２−３による一連の処理をL/2回実行させるループ処理を実行させる（横のループ）。言い換えると、制御部２３は、集合{0,...,N-1}に含まれるL個〔Lは偶数〕の互いに異なる複数の元からなる部分集合の各元をそれぞれ１回ずつi1又はi2として選択し、選択したi1とi2との組のそれぞれに対して演算部２２−１〜２２−３による一連の処理を１回ずつ実行させ、L/2個の上記組(i1, i2)のそれぞれに対応する上記一連の処理を含むループ処理を実行させる。また、必要に応じ、制御部２３は、当該一連の処理をL/2回実行させるループ処理を、複数回実行させる（縦のループ）。なお、Nが偶数であり、L=Nであり、上述の部分集合が集合{0,...,N-1}である場合、本形態の効果が最も大きくなる。
【００５６】
図３の例では、i=0とi=1とに対応する当該一連の処理（ステップＳ１１−ｊ）と、i=2とi=3とに対応する当該一連の処理（ステップＳ１２−ｊ）と、i=4とi=5とに対応する当該一連の処理（ステップＳ１３−ｊ）とからなるループ処理（横のループ）が、複数回（j=1,2,...）実行される。
【００５７】
それぞれの上記一連の処理によって演算部２２−３から出力された積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))は、演算部２２−４（第４演算部）に入力される。演算部２２−４は、これらを用いて
Πi=0N-1poly(R(i,0),...,R(i,K-1))∈GF(pd・m)       …(28)
を求め、当該Πi=0N-1poly(R(i,0),...,R(i,K-1))を出力する。例えば、N≧4の場合、演算部２２−４は、それぞれの上記一連の処理によって演算部２２−３から出力された積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))の乗算値を用いてΠi=0N-1poly(R(i,0),...,R(i,K-1))∈GF(pd・m)を求める。
【００５８】
なお、演算部２２−４は、それぞれの上記一連の処理によって演算部２２−３から出力された積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))を逐一メモリ２４に格納し、すべての当該積の計算終了後にそれらの乗算値をまとめて計算してもよい。しかし、メモリ２４の容量節約の観点からは、演算部２２−４は、上記一連の処理が１回実行されるたびに、演算部２２−３から出力された積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))を直前の乗算値（初期値は乗法単位元１）に乗じていくことで乗算値を求めることが望ましい。言い換えると、上記一連の処理が１回実行されるたびに、それまでに得られた積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))の乗算値が更新されることが望ましい。
【００５９】
〔第１実施形態〕
次に、本発明の第１実施形態を説明する。
本形態は、本発明を改良ηＴペアリング演算アルゴリズムのgの演算部分に適用した例である。
【００６０】
すなわち、本形態では、K=4，p=3，d=6であり、mが1以上の奇数であり、Nが4以上の偶数であり、L=Nであり、有限体GF(pm)の元R(i,0),R(i,1),R(i,2),R(i,3)が、それぞれ、有限体GF(pm)上で定義された楕円曲線E上の2つの点P(X1[i],Y1[i])及び点Q(X2[i],Y2[i])の各アフィン座標点X 1[i],Y 1[i],X 2[i],Y 2[i]∈GF(pm)であり、演算e(R(i,0),...,R(i,K-1))が、ペアリング演算e(P(X1[i],Y1[i]),Q(X2[i],Y2[i]))であり、演算Πi=0N-1e(R(i,0),...,R(i,K-1))が、マルチペアリング演算Πi=0N-1e(P(X1[i],Y1[i]),Q(X2[i],Y2[i]))である。また、本形態では、楕円曲線として式(10)の超特異楕円曲線Ebを用いる（b=-1であってもよいし、b=1であってもよい）。また、本形態の拡大体演算は、入力部に入力された各アフィン座標点X 1[i],Y 1[i],X 2[i],Y 2[i]又はその像をそれぞれx1[i],y1[i],x2[i],y2[i]とし、u[i]=x1[i]+x2[i]+c∈GF(3m)とし、有限体GF(3m)の元を係数とする既約多項式σ2+1=0の根を不定元σとし、既約多項式ρ3-ρ-b=0の根を不定元ρとした場合における、有限体GF(3m)の6次拡大体GF(36m)の元を示す多項式
g[i]=-{u[i]}2+y1[i]・y2[i]・σ-u[i]・ρ-ρ2∈GF(36m)   …(29)
を求める演算である。
【００６１】
＜構成＞
図５及び図６は、第１実施形態の有限体演算部１２０の基本構成を説明するためのブロック図である。
【００６２】
第１実施形態の有限体演算装置は、図２Ａに例示した有限体演算部２０を図５及び図６の有限体演算部１２０に置換したものである。以下では、有限体演算部１２０の構成のみを説明する。
【００６３】
図５及び図６に例示するように、本形態の有限体演算部１２０は、有限体GF(3m)上の演算を行うGF(3m)演算部１２１−１〜４と、有限体GF(3m)の6次拡大体GF(36m)上の演算を行うGF(36m)演算部１２２−１〜９と、制御部１２３と、メモリ１２４と、有限体GF(3)上の演算を行うGF(3)演算部１２５とを有する。
【００６４】
なお、有限体演算部１２０は、CPU，RAM，ROM等を備えた公知又は専用のコンピュータと特別なプログラムとを有する特別な装置である。すなわち、GF(3m)演算部１２１−１〜４、GF(36m)演算部１２２−１〜９、GF(3)演算部１２５及び制御部１２３は、所定のプログラムがCPUに読み込まれて構築される機能部であり、メモリ１２４は、RAM、キャッシュメモリ、レジスタ、ハードディスク等である。また、有限体演算部１２０の少なくとも一部が集積回路によって構成されてもよい。
【００６５】
＜処理＞
図７から図１０は、第１実施形態の処理を説明するための図である。以下、これらの図を用いて本形態の処理を説明する。
【００６６】
まず、入力部１０（図２Ａ）に、マルチペアリング演算Πi=0N-1e(P(X1[i],Y1[i]),Q(X2[i],Y2[i]))を構成する各ペアリング演算e(P(X1[i],Y1[i]),Q(X2[i],Y2[i]))の入力値である、超特異楕円曲線Eb上の2つの点P(X1[i],Y1[i])及び点Q(X2[i],Y2[i])の各アフィン座標点X 1[i],Y 1[i],X 2[i],Y 2[i]∈GF(3m)（i∈{0,...,N-1}）が入力され、有限体演算部１２０（図５及び図６）のメモリ１２４に格納される。以下、メモリ１２４に格納されたX 1[i],Y 1[i],X 2[i],Y 2[i]∈GF(3m)をx 1[i],y 1[i],x2[i],y 2[i]∈GF(3m)と表記する（ステップＳ１０１）。
【００６７】
[b=1の場合の処理（Ｓ１０２〜Ｓ１０５）]
b=1の超特異楕円曲線Ebを用いる場合にはステップＳ１０２〜Ｓ１０５の処理が実行される。b=-1の超特異楕円曲線Ebを用いる場合にはステップＳ１０２〜Ｓ１０５の処理は実行しない。
【００６８】
まず、制御部１２３がi=0に設定し、その設定内容をメモリ１２４に格納する（ステップＳ１０２）。次に、GF(3m)演算部１２１−１が、メモリ１２４からy 1[i]を読み出し、有限体GF(3m)上の演算
y1[i]={-y1[i]}∈GF(3m)       …(30)
を行い、その演算結果を新たなy 1[i]としてメモリ１２４に格納する（ステップＳ１０３）。
【００６９】
次に、制御部１２３がi=N-1であるか否かを判定する（ステップＳ１０４）。ここで、i=N-1でなければ、制御部１２３はi+1を新たなiに設定し、その設定内容をメモリ１２４に格納して処理をステップＳ１０３に戻す（ステップＳ１０５）。一方、i=N-1であれば、b=1の場合の処理（Ｓ１０２〜Ｓ１０５）を終了する（[b=1の場合の処理（Ｓ１０２〜Ｓ１０５）]の説明終わり）。
【００７０】
次に、GF(36m)演算部１２２−７（第５演算部を構成）が、メモリ１２４からx 1[0],y 1[0],x 2[0],y 2[0]∈GF(3m)を読み込み、6次拡大体GF(36m)上の演算
f=-y1[0]・(x1[0]+x2[0]+b)+y2[0]・σ+y1[0]・ρ∈GF(36m)   …(31)
を行い、その演算結果f∈GF(36m)をメモリ１２４に格納する（ステップＳ１０６）。
【００７１】
次に、GF(36m)演算部１２２−７が、メモリ１２４からx 1[1],y1[1],x 2[1],y 2[1]∈GF(3m)を読み込み、6次拡大体GF(36m)上の演算
f'=-y1[1]・(x1[1]+x2[1]+b)+y2[1]・σ+y1[1]・ρ∈GF(36m)   …(32)
を行い、その演算結果f'∈GF(36m)をメモリ１２４に格納する。さらに、GF(36m)演算部１２２−８が、メモリ１２４から演算結果f及びf'を読み込み、6次拡大体GF(36m)上の演算
f=f・f'∈GF(36m)     …(33)
を行い、その演算結果を新たなf∈GF(36m)としてメモリ１２４に格納する（ステップＳ１０７）。
【００７２】
次に、制御部１２３がi=2に設定し、その設定内容をメモリ１２４に格納する（ステップＳ１０８）。
【００７３】
次に、GF(36m)演算部１２２−７が、メモリ１２４からx 1[i],y1[i],x 2[i],y 2[i]∈GF(3m)を読み込み、6次拡大体GF(36m)上の演算
f'=-y1[i]・(x1[i]+x2[i]+b)+y2[i]・σ+y1[i]・ρ∈GF(36m)   …(34)
を行い、その演算結果を新たなf'∈GF(36m)としてメモリ１２４に格納する（ステップＳ１０９）。
【００７４】
次に、GF(36m)演算部１２２−８（第５演算部を構成）が、メモリ１２４から演算結果f及びf'を読み込み、6次拡大体GF(36m)上の演算
f=f・f'∈GF(36m)     …(35)
を行い、その演算結果を新たなf∈GF(36m)としてメモリ１２４に格納する（ステップＳ１１０）。
【００７５】
次に、制御部１２３がi=N-1であるか否かを判定する（ステップＳ１１１）。ここで、i=N-1でなければ、制御部１２３はi+1を新たなiに設定し、その設定内容をメモリ１２４に格納して処理をステップＳ１０９に戻す（ステップＳ１１３）。一方、i=N-1であれば、制御部１２３がbをcの初期値として設定し（c=b）、その設定内容をメモリ１２４に格納する（ステップＳ１１２）。
【００７６】
なお、ステップ１１１でi=N-1と判定されるまでにステップＳ１０６〜Ｓ１１０で実行される処理が、b=-1の場合には、x1[i]=X1[i], y1[i]=Y1[i], x2[i]=X2[i]，y2[i]=Y2[i]とし、b=1の場合には、x1[i]=X1[i], y1[i]=-Y1[i], x2[i]=X2[i]，y2[i]=Y2[i]とし、f=Πi=0N-1(-y1[i]・(x1[i]+x2[i]+b)+y2[i]・σ+y1[i]・ρ)∈GF(36m)の演算を行い、当該fを出力する処理に相当する。
【００７７】
次に、制御部１２３がj=0に設定し、その設定内容をメモリ１２４に格納する（ステップＳ１１４）。さらに、制御部１２３がi=0に設定し、その設定内容をメモリ１２４に格納する（ステップＳ１１５）。
【００７８】
次に、GF(3m)演算部１２１−２が、メモリ１２４からx 1[i],x2[i],cを読み込み、有限体GF(3m)上で
u[i]=x1[i]+x2[i]+c∈GF(3m)     …(36)
の演算を行い、その演算結果u[i]をメモリ１２４に格納する（ステップＳ１１６）。
【００７９】
次に、制御部１２３がi=N-1であるか否かを判定する（ステップＳ１１７）。ここで、i=N-1でなければ、制御部１２３はi+1を新たなiに設定し、その設定内容をメモリ１２４に格納して処理をステップＳ１１６に戻す（ステップＳ１１８）。
【００８０】
一方、i=N-1であれば、GF(36m)演算部１２２−１（第１演算部）が、メモリ１２４からy1[0],y2[0],u[0]∈GF(3m)（i1=0）を読み込み、
g[0]=-{u[0]}2+y1[0]・y2[0]・σ-u[0]・ρ-ρ2∈GF(36m)     …(37)
の演算を行い、その演算結果g[0]∈GF(36m)をメモリ１２４に格納する（ステップＳ１１９）。
【００８１】
また、GF(36m)演算部１２２−２（第２演算部）が、メモリ１２４からy1[1],y2[1],u[1]∈GF(3m)（i2=1）を読み込み、
g[1]=-{u[1]}2+y1[1]・y2[1]・σ-u[1]・ρ-ρ2∈GF(36m)     …(38)
の演算を行い、その演算結果g[1]∈GF(36m)をメモリ１２４に格納する（ステップＳ１２０）。
【００８２】
次に、GF(36m)演算部１２２−３（第３演算部）が、メモリ１２４から演算結果g[0]及びg[1]∈GF(36m)を読み込み、
g=g[0]・g[1]∈GF(36m)     …(39)
の演算を行い、その演算結果g∈GF(36m)をメモリ１２４に格納する（ステップＳ１２１）。なお、GF(36m)演算部１２２−３は、g[0]の予め0∈GF(pm)とされた項、及び／又は、g[1]の予め0∈GF(pm)とされた項、を被演算子とした演算を行うことなく、積g[0]・g[1]∈GF(36m)を求める。
【００８３】
次に、GF(3m)演算部１２１−１が、メモリ１２４からy 1[0]を読み出し、有限体GF(3m)上の演算
y1[0]={-y1[0]}∈GF(3m)       …(40)
を行い、その演算結果を新たなy 1[0]としてメモリ１２４に格納する（ステップＳ１２２）。
【００８４】
次に、GF(3m)演算部１２１−３が、メモリ１２４からx2[0]を読み出し、有限体GF(3m)上の演算
x2[0]={x2[0]}9∈GF(3m)       …(41)
を行い、その演算結果を新たなx2[0]としてメモリ１２３に格納する（ステップＳ１２３）。なお、この演算は例えば、フロベニウス写像(Frobenius map)を用いて行われる（以下の3χ乗算（χは1以上の整数）についても同様）。
【００８５】
次に、GF(3m)演算部１２１−３が、メモリ１２４からy2[0]を読み出し、有限体GF(3m)上の演算
y2[0]={y2[0]}9∈GF(3m)       …(42)
を行い、その演算結果を新たなy2[0]としてメモリ１２３に格納する（ステップＳ１２４）。
【００８６】
次に、GF(3m)演算部１２１−１が、メモリ１２４からy1[1]を読み出し、有限体GF(3m)上の演算
y1[1]={-y1[1]}∈GF(3m)       …(43)
を行い、その演算結果を新たなy 1[1]としてメモリ１２４に格納する（ステップＳ１２５）。
【００８７】
次に、GF(3m)演算部１２１−３が、メモリ１２４からx2[1]を読み出し、有限体GF(3m)上の演算
x2[1]={x2[1]}9∈GF(3m)       …(44)
を行い、その演算結果を新たなx2[1]としてメモリ１２３に格納する（ステップＳ１２６）。
【００８８】
次に、GF(3m)演算部１２１−３が、メモリ１２４からy2[1]を読み出し、有限体GF(3m)上の演算
y2[1]={y2[1]}9∈GF(3m)       …(45)
を行い、その演算結果を新たなy2[1]としてメモリ１２３に格納する（ステップＳ１２７）。
【００８９】
次に、制御部１２３がi=2に設定し、その設定内容をメモリ１２４に格納する（ステップＳ１２８）。
【００９０】
次に、GF(36m)演算部１２２−１（第１演算部）が、メモリ１２４からy1[i],y2[i],u[i]∈GF(3m)（i1=i)を読み込み、
g[i]=-{u[i]}2+y1[i]・y2[i]・σ-u[i]・ρ-ρ2∈GF(36m)     …(46)
の演算を行い、その演算結果g[i]∈GF(36m)をメモリ１２４に格納する（ステップＳ１２９）。
【００９１】
また、GF(36m)演算部１２２−２（第２演算部）が、メモリ１２４からy1[i+1],y2[i+1],u[i+1]∈GF(3m)（i2=i+1)を読み込み、
g[i+1]=-{u[i+1]}2+y1[i+1]・y2[i+1]・σ-u[i+1]・ρ-ρ2∈GF(36m) …(47)
の演算を行い、その演算結果g[i+1]∈GF(36m)をメモリ１２４に格納する（ステップＳ１３０）。
【００９２】
次に、GF(36m)演算部１２２−３（第３演算部）が、メモリ１２４から演算結果g[i]及びg[i+1]∈GF(36m)を読み込み、
g[i]・g[i+1]∈GF(36m)     …(48)
の演算を行い、その演算結果g[i]・g[i+1]∈GF(36m)をメモリ１２４に格納する（ステップＳ１３１）。なお、GF(36m)演算部１２２−３は、g[i]の予め0∈GF(pm)とされた項、及び／又は、g[i+1]の予め0∈GF(pm)とされた項、を被演算子とした演算を行うことなく、積g[i]・g[i+1]∈GF(36m)を求める。
【００９３】
次に、GF(36m)演算部１２２−３（第４演算部）が、メモリ１２４からg,g[i]・g[i+1]∈GF(36m)を読み込み、
g=g・g[i]・g[i+1]∈GF(36m)     …(49)
の演算を行い、その演算結果を新たなg∈GF(36m)としてメモリ１２４に格納する（ステップＳ１３２）。
【００９４】
このように、本形態のGF(36m)演算部１２２−３（第４演算部）は、GF(36m)演算部１２２−１（第１演算部）と、GF(36m)演算部１２２−２（第２演算部）と、GF(36m)演算部１２２−３（第３演算部）とによる「一連の処理」が１回実行されるたびに、GF(36m)演算部１２２−３（第３演算部）から出力された積g[i]・g[i+1]の乗算値を求める。前述のように、これによってメモリ１２４の容量を節約できる。
【００９５】
次に、GF(3m)演算部１２１−１が、メモリ１２４からy1[i]を読み出し、有限体GF(3m)上の演算
y1[i]={-y1[i]}∈GF(3m)       …(50)
を行い、その演算結果を新たなy1[i]としてメモリ１２４に格納する（ステップＳ１３３）。
【００９６】
次に、GF(3m)演算部１２１−３が、メモリ１２４からx2[i]を読み出し、有限体GF(3m)上の演算
x2[i]={x2[i]}9∈GF(3m)       …(51)
を行い、その演算結果を新たなx2[i]としてメモリ１２３に格納する（ステップＳ１３４）。
【００９７】
次に、GF(3m)演算部１２１−３が、メモリ１２４からy2[i]を読み出し、有限体GF(3m)上の演算
y2[i]={y2[i]}9∈GF(3m)       …(52)
を行い、その演算結果を新たなy2[i]としてメモリ１２３に格納する（ステップＳ１３５）。
【００９８】
次に、GF(3m)演算部１２１−１が、メモリ１２４からy1[i+1]を読み出し、有限体GF(3m)上の演算
y1[i+1]={-y1[i+1]}∈GF(3m)       …(53)
を行い、その演算結果を新たなy1[i+1]としてメモリ１２４に格納する（ステップＳ１３６）。
【００９９】
次に、GF(3m)演算部１２１−３が、メモリ１２４からx2[i+1]を読み出し、有限体GF(3m)上の演算
x2[i+1]={x2[i+1]}9∈GF(3m)       …(54)
を行い、その演算結果を新たなx2[i+1]としてメモリ１２３に格納する（ステップＳ１３７）。
【０１００】
次に、GF(3m)演算部１２１−３が、メモリ１２４からy2[i+1]を読み出し、有限体GF(3m)上の演算
y2[i+1]={y2[i+1]}9∈GF(3m)       …(55)
を行い、その演算結果を新たなy2[i+1]としてメモリ１２３に格納する（ステップＳ１３８）。
【０１０１】
次に、制御部１２３がi=N-2であるか否かを判定する（ステップＳ１３９）。ここで、i=N-2でなければ、制御部１２３はi+2を新たなiに設定し、その設定内容をメモリ１２４に格納して処理をステップＳ１２９に戻す（ステップＳ１４０）。
【０１０２】
一方、i=N-2であれば、GF(3)演算部１２５がメモリ１２４からcを読み出し、
c=(c-b)mod 3       …(56)
の演算を行い、その演算結果を新たなcとしてメモリ１２４に格納する（ステップＳ１４１）。
【０１０３】
次に、GF(36m)演算部１２２−５（第１０演算部）が、メモリ１２４からf,gを読み込み、
f=f・g∈GF(36m)       …(57)
の演算を行い、その演算結果を新たなfとしてメモリ１２４に格納する（ステップＳ１４２）。
【０１０４】
次に、GF(36m)演算部１２２−５（第１１演算部）が、メモリ１２４からfを読み込み、
f=f3∈GF(36m)       …(58)
の演算を行い、その演算結果を新たなfとしてメモリ１２４に格納する（ステップＳ１４３）。
【０１０５】
なお、ステップＳ１４１〜Ｓ１４３の処理は、GF(36m)演算部１２２−１（第１演算部）とGF(36m)演算部１２２−２（第２演算部）とGF(36m)演算部１２２−３（第３演算部）とによる「一連の処理」がN/2回実行される「ループ処理（ステップＳ１１５〜Ｓ１４０）」が１回実行されるたびに実行される。
【０１０６】
次に、制御部１２３がj=(m-1)/2であるか否かを判定する（ステップＳ１４４）。ここで、j=(m-1)/2でなければ、制御部１２３はj+1を新たなjに設定し、その設定内容をメモリ１２４に格納して処理をステップＳ１１５に戻す（ステップＳ１４５）。一方、j=(m-1)/2であれば、「ループ処理（ステップＳ１１５〜Ｓ１４０）」が終了する。すなわち、m=1である場合には、上記「一連の処理」をN/2回実行させる「ループ処理（ステップＳ１１５〜Ｓ１４０）」が１回のみ実行され、m≧3である場合には、上記「一連の処理」をN/2回実行させる「ループ処理（ステップＳ１１５〜Ｓ１４０）」が複数回実行される。
【０１０７】
この「ループ処理」が終了すると、GF(36m)演算部１２２−９が、メモリ１２４からfを読み込み、
output=ffinalpow∈GF(36m)       …(59)
〔finalpow=(33m-1)(3m+1)(3m-3(m+1)/2+1)〕
の演算を行い（ステップＳ１４６）、その演算結果output∈GF(36m)を出力する（ステップＳ１４７）。当該演算結果output∈GF(36m)がマルチペアリング演算Πi=0N-1e(P(X1[i],Y1[i]),Q(X2[i],Y2[i]))の演算結果である。そして、当該演算結果output∈GF(36m)は出力部３０（図２Ａ）から出力される。
【０１０８】
＜第１実施形態の特徴＞
以上説明したように、本形態では、マルチペアリング演算Πi=0N-1e(P(X1[i],Y1[i]),Q(X2[i],Y2[i]))を構成する、各ペアリング演算e(P(X1[i],Y1[i]),Q(X2[i],Y2[i]))をそれぞれ計算するための多項式
g[i]=-{u[i]}2+y1[i]・y2[i]・σ-u[i]・ρ-ρ2∈GF(36m)   …(60)
g[i+1]=-{u[i+1]}2+y1[i+1]・y2[i+1]・σ-u[i+1]・ρ-ρ2∈GF(36m) …(61)
を求め、それらの積
g[i]・g[i+1]∈GF(36m)       …(62)
を求め、それらの積を用いて
g=Πi=0N-1g[i]∈GF(36m)       …(63)
を計算する（ステップＳ１１９〜Ｓ１２１，ステップＳ１２９〜Ｓ１３２）。
【０１０９】
ここで、6次拡大体GF(36m)を示す式(60)(61)の多項式は不定元ρ・σ，ρ2・σ∈GF(p6m)の項の係数が予め0とされているものである。このような多項式同士の積を先に計算することによって係数が予め0とされている項の演算が不要となり、乗算回数を削減することができる。
【０１１０】
[本形態のアルゴリズム(b=1の場合)の乗算数]
以下に、本形態のアルゴリズムと乗算数とを併記する。なお、《θM》はθ回の乗算を示し、《θC》はθ回の３乗算を示す。
INPUT: x 1[i],y1[i],x 2[i],y 2[i]∈GF(3m)
for i=0 to N-1
y1[i]={-y1[i]}
end for
f=-y1[0]・(x1[0]+x2[0]+b)+y2[0]・σ+y1[0]・ρ  《1M》
f'=-y1[1]・(x1[1]+x2[1]+b)+y2[1]・σ+y1[1]・ρ  《1M》
f=f・f'  《6M》
for i=2 to N-1
f'=-y1[i]・(x1[i]+x2[i]+b)+y2[i]・σ+y1[i]・ρ  《1M》
f=f・f'  《15M》
end for
c=b
for j=0 to (m-1)/2
for i=0 to N-1
u[i]=x1[i]+x2[i]+c
end for
g[0]=-{u[0]}2+y1[0]・y2[0]・σ-u[0]・ρ-ρ2  《2M》        …(64)
g[1]=-{u[1]}2+y1[1]・y2[1]・σ-u[1]・ρ-ρ2  《2M》        …(65)
g=g[0]・g[1]   《6M》                                     …(66)
y1[0]={-y1[0]} 
x2[0]={x2[0]}9  《2C》
y2[0]={y2[0]}9  《2C》
y1[1]={-y1[1]}
x2[1]={x2[1]}9  《2C》
y2[1]={y2[1]}9  《2C》
for i=2 to N-2 step 2
g[i]=-{u[i]}2+y1[i]・y2[i]・σ-u[i]・ρ-ρ2  《2M》    …(67)
g[i+1]=-{u[i+1]}2+y1[i+1]・y2[i+1]・σ-u[i+1]・ρ-ρ2  《2M》
…(68)
g[i]・g[i+1]   《6M》                                 …(69)
g=g・g[i]・g[i+1]   《15M》                           …(70)
y1[i]={-y1[i]}
x2[i]={x2[i]}9  《2C》
y2[i]={y2[i]}9  《2C》
y1[i+1]={-y1[i+1]}
x2[i+1]={x2[i+1]}9  《2C》
y2[i+1]={y2[i+1]}9  《2C》
end for
c=(c-b)mod 3
f=f・g  《15M》
f=f3  《6C》
end for
Return output=ffinalpow
【０１１１】
以上のように、本形態では、式(64)(65)でg[0]，g[1]を求めてから、式(66)でこれらの積を求め、式(67)(68)でg[i]，g[i+1]を求めてから、式(70)でこれらの積を求める。これにより、g[i]を求めるたびにその演算結果をg=g・g[i]と累積乗算していく場合よりも演算量を大幅に削減できる。すなわち、g[0]，g[1], g[i]，g[i+1]は、1部の項の係数が0の多項式であるため、それらの間での乗算数は6Mでよい。しかし、g[i]を求めるたびにその演算結果をg=g・g[i]と累積乗算する場合には、初回を除きgのすべての項の係数が0以外となりうるため累積乗算のための乗算数は15Mとなる。例えば、式(67)〜(70)の乗算回数だけを比較すると、本願の方法では、
2M+2M+6M+15M=25M
の演算が必要であるのに対し、g[i]を求めるたびにその演算結果をg=g・g[i]と累積乗算する場合には、
(2M+15M)×2=34M
の演算が必要となる。このように、本形態のような順序で演算を行うことにより、乗算回数を大幅に削減できる。
【０１１２】
[従来技術を拡張したアルゴリズム(b=1の場合)の乗算数]
前述のように、引用文献１，２には複数のペアリングの積を効率的に計算する方式については開示されていない。以下では、仮に、引用文献１の改良ηＴペアリング演算アルゴリズムを単純にマルチペアリングの計算に拡張したとしても、本形態よりも演算量が削減できないことを示す。
【０１１３】
以下に、引用文献１の改良ηＴペアリング演算アルゴリズムを単純にマルチペアリングの計算に拡張したアルゴリズムを示す。なお、以下は本形態の特徴を明確にするためのものであり、以下の比較用のアルゴリズムが、本願出願当初に容易に発明できたことを示すものではない。
INPUT: x 1[i],y1[i],x 2[i],y 2[i]∈GF(3m)
for i=0 to N-1
y1[i]={-y1[i]}
end for
f=-y1[0]・(x1[0]+x2[0]+b)+y2[0]・σ+y1[0]・ρ  《1M》
f'=-y1[1]・(x1[1]+x2[1]+b)+y2[1]・σ+y1[1]・ρ  《1M》
f=f・f'  《6M》
for i=2 to N-1
f'=-y1[i]・(x1[i]+x2[i]+b)+y2[i]・σ+y1[i]・ρ  《1M》
f=f・f'  《15M》
end for
c=b
for j=0 to (m-1)/2
for i=0 to N-1
u[i]=x1[i]+x2[i]+c
end for
g[0]=-{u[0]}2+y1[0]・y2[0]・σ-u[0]・ρ-ρ2  《2M》        …(71)
y1[0]={-y1[0]} 
x2[0]={x2[0]}9  《2C》
y2[0]={y2[0]}9  《2C》
g[1]=-{u[1]}2+y1[1]・y2[1]・σ-u[1]・ρ-ρ2  《2M》        …(72)
g=g[0]・g[1]   《6M》                                     …(73)
y1[1]={-y1[1]}
x2[1]={x2[1]}9  《2C》
y2[1]={y2[1]}9  《2C》
for i=2 to N-1
g=g・(-{u[i]}2+y1[i]・y2[i]・σ-u[i]・ρ-ρ2)  《14M》 …(74)
y1[i]={-y1[i]}
x2[i]={x2[i]}9  《2C》
y2[i]={y2[i]}9  《2C》
end for
c=(c-b)mod 3
f=f・g  《15M》
f=f3  《6C》
end for
Return output=ffinalpow
【０１１４】
以上のように、引用文献１の改良ηＴペアリング演算アルゴリズムを単純にマルチペアリングの計算に拡張した場合、式(74)で各iについて14Mの演算が必要となり、2つのiに対しては28Mの演算が必要となる。
【０１１５】
[ループアンローリングを用いたアルゴリズム(b=1の場合)の乗算数]
前述のように、引用文献２には複数のペアリングの積を効率的に計算する方式については開示されていない。しかし、引用文献２にはループアンローリングを用いたアルゴリズムが開示されている。以下では、仮に、引用文献２のループアンローリングを用いたアルゴリズムの考え方をマルチペアリングの計算に拡張したとしても、本形態よりも演算量が削減できないことを示す。
【０１１６】
前述の多項式-{u[i]}2+y1[i]・y2[i]・σ-u[i]・ρ-ρ2は、各iに対応する異なるペアリングについてそれぞれ算出する必要があるとともに、それぞれのペアリングの"j=0 to (m-1)/2 "のループにおいて{(m-1)/2}+1回計算する必要がある。本形態の方法は、各iに対応する異なるペアリングに対応する多項式-{u[i]}2+y1[i]・y2[i]・σ-u[i]・ρ-ρ2をそれぞれ求め、それらの積を求めるものであった。これに対し、引用文献２のループアンローリングの考え方は、１つのペアリングの"j=0 to (m-1)/2 "のループにおいて複数回算出される多項式-{u[i]}2+y1[i]・y2[i]・σ-u[i]・ρ-ρ2の積を求めるものである。
【０１１７】
以下に、引用文献２のループアンローリングの考え方をマルチペアリングの計算に拡張したアルゴリズムを示す（未公開）。なお、以下は本形態の特徴を明確にするためのものであり、以下の比較用のアルゴリズムが、本願の優先日や出願当初に容易に発明できたことを示すものではない。
INPUT: x 1[i],y1[i],x 2[i],y 2[i]∈GF(3m)
for i=0 to N-1
y1[i]={-y1[i]}
end for
f=-y1[0]・(x1[0]+x2[0]+b)+y2[0]・σ+y1[0]・ρ  《1M》
f'=-y1[1]・(x1[1]+x2[1]+b)+y2[1]・σ+y1[1]・ρ  《1M》
f=f・f'  《6M》
for i=2 to N-1
f'=-y1[i]・(x1[i]+x2[i]+b)+y2[i]・σ+y1[i]・ρ  《1M》
f=f・f'  《15M》
end for
c=b
for j=0 to (m-1)/4
for i=0 to N-1
u[i]=x1[i]+x2[i]+c
end for
g1[0]=-{u[0]}2+y1[0]・y2[0]・σ-u[0]・ρ-ρ2  《2M》        …(75)
g1[0]={g1[0]}3                                             …(76)
y1[0]={-y1[0]} 
x2[0]={x2[0]}9  《2C》
y2[0]={y2[0]}9  《2C》
g2[0]=-{u[0]}2+y1[0]・y2[0]・σ-u[0]・ρ-ρ2  《2M》        …(77)
g=g1[0]・g2[0]   《6M》                                    …(78)
y1[0]={-y1[0]}
x2[0]={x2[0]}9  《2C》
y2[0]={y2[0]}9  《2C》
for i=1 to N-1
g1[i]=-{u[i]}2+y1[i]・y2[i]・σ-u[i]・ρ-ρ2  《2M》    …(79)
g1[i]={g1[i]}3                                         …(80)
y1[i]={-y1[i]}
x2[i]={x2[i]}9  《2C》
y2[i]={y2[i]}9  《2C》
g2[i]=-{u[i]}2+y1[i]・y2[i]・σ-u[i]・ρ-ρ2  《2M》   …(81)
g2[i]・g2[i]   《6M》                                 …(82)
g=g・g2[i]・g2[i]   《15M》                           …(83)
y1[i+1]={-y1[i+1]}
x2[i+1]={x2[i+1]}9  《2C》
y2[i+1]={y2[i+1]}9  《2C》
end for
c=(c-b)mod 3
f=f・g  《15M》
f=f3  《6C》
end for
Return output=ffinalpow
【０１１８】
以上のように、このアルゴリズムでは、同一のi=0について式(75)(77)でg1[0]，g2[0]を求めてから、式(74)でこれらの積を求め、同一のi=1,...,N-1について式(75)(77)でg1[i]，g2[i]を求めてから、式(82)でこれらの積を求める。しかし、このアルゴリズムでは、式(76)(80)で3乗算が必要になる。これは、本来、"j=0 to (m-1)/2 "のループごとに1回のf=f3の演算が必要なところ、ループアンローリングを用いたアルゴリズムでは、jについての２つのループを１つのループで実現しており、1回分のf=f3に対応する式(76)(80)の3乗算をループ内でi=0,...,N-1のそれぞれについて実行しなければならないことに基づく。
【０１１９】
本形態のアルゴリズムでは、この3乗算がf=f3として"j=0 to (m-1)/2 "のループの外でまとめて実行されるため、ループアンローリングの考え方をマルチペアリングの計算に拡張したアルゴリズムよりも演算量を削減できる。
【０１２０】
〔第１実施形態の変形例〕
第１実施形態は、Nが4以上の偶数である場合の形態であった。第１実施形態の変形例では、Nが5以上の奇数である場合の処理を説明する。
【０１２１】
図１１は、Nが5以上の奇数である場合の処理を例示するための図である。この変形例ではL=N-1とする。以下では、第１実施形態との相違点のみを説明する。
【０１２２】
第１実施形態の変形例では、第１実施形態で説明したステップＳ１３８の処理の後、制御部１２３がi=(N-1)-2であるか否かを判定する（ステップＳ１５９）。ここで、i=(N-1)-2でなければ、制御部１２３はi+2を新たなiに設定し、その設定内容をメモリ１２４に格納して処理をステップＳ１２９に戻す（ステップＳ１４０）。
【０１２３】
一方、i=(N-1)-2であれば、まず、制御部１２３がi+2を新たなiに設定し、その設定内容をメモリ１２４に格納する（ステップ１６０）。
【０１２４】
次に、GF(36m)演算部１２２−１が、メモリ１２４からy1[i],y2[i],u[i]∈GF(3m)を読み込み、
g[i]=-{u[i]}2+y1[i]・y2[i]・σ-u[i]・ρ-ρ2∈GF(36m)     …(84)
の演算を行い、その演算結果g[i]∈GF(36m)をメモリ１２４に格納する（ステップＳ１６１）。
【０１２５】
次に、GF(36m)演算部１２２−３が、メモリ１２４からg,g[i]∈GF(36m)を読み込み、
g=g・g[i]∈GF(36m)     …(85)
の演算を行い、その演算結果を新たなg∈GF(36m)としてメモリ１２４に格納する（ステップＳ１６２）。その後、第１実施形態で説明したステップＳ１４１以降の処理が実行される。
【０１２６】
〔第２実施形態〕
次に、本発明の第２実施形態を説明する。
【０１２７】
第１実施形態は、本発明を改良ηＴペアリング演算アルゴリズムのgの演算部分に適用した例であった。第２実施形態では、本発明を改良ηＴペアリング演算アルゴリズムのf及びgの両方の演算部分に適用する。これにより、さらなる演算量の削減が可能となる。
【０１２８】
すなわち、本形態では、K=4，p=3，d=6であり、mが1以上の奇数であり、Nが4以上の偶数であり、W=Nであり、有限体GF(pm)の元R(i,0),R(i,1),R(i,2),R(i,3)が、それぞれ、有限体GF(pm)上で定義された楕円曲線E上の2つの点P(X1[i],Y1[i])及び点Q(X2[i],Y2[i])の各アフィン座標点X 1[i],Y 1[i],X 2[i],Y 2[i]∈GF(pm)であり、演算e(R(i,0),...,R(i,K-1))が、ペアリング演算e(P(X1[i],Y1[i]),Q(X2[i],Y2[i]))であり、演算Πi=0N-1e(R(i,0),...,R(i,K-1))が、マルチペアリング演算Πi=0N-1e(P(X1[i],Y1[i]),Q(X2[i],Y2[i]))である。また、本形態では、楕円曲線として式(10)の超特異楕円曲線Ebを用いる（b=-1であってもよいし、b=1であってもよい）。また、本形態の拡大体演算は、入力部に入力された各アフィン座標点X 1[i],Y 1[i],X 2[i],Y 2[i]又はその像をそれぞれx1[i],y1[i],x2[i],y2[i]とし、u[i]=x1[i]+x2[i]+c∈GF(3m)とし、有限体GF(3m)の元を係数とする既約多項式σ2+1=0の根を不定元σとし、既約多項式ρ3-ρ-b=0の根を不定元ρとした場合における、有限体GF(3m)の6次拡大体GF(36m)の元を示す多項式
f[i]=-y1[i]・(x1[i]+x2[i]+b)+y2[i]・σ+y1[i]・ρ∈GF(36m)   …(86)
g[i]=-{u[i]}2+y1[i]・y2[i]・σ-u[i]・ρ-ρ2∈GF(36m)       …(87)
を求める演算である。以下では、第１実施形態との相違点を中心に説明し、第１実施形態と共通する事項については説明を省略する。
【０１２９】
＜構成＞
図１２及び図１３は、第２実施形態の有限体演算部２２０の基本構成を説明するためのブロック図である。
【０１３０】
第２実施形態の有限体演算装置は、図２Ａに示した有限体演算部２０を図１２及び図１３の有限体演算部２２０に置換したものである。以下では、有限体演算部２２０の構成のみを説明する。
【０１３１】
図１２及び図１３に例示するように、本形態の有限体演算部２２０は、有限体GF(3m)上の演算を行うGF(3m)演算部１２１−１〜４と、有限体GF(3m)の6次拡大体GF(36m)上の演算を行うGF(36m)演算部１２２−１〜５，９と、GF(36m)演算部２２２−１〜５と、制御部１２３と、メモリ１２４と、有限体GF(3)上の演算を行うGF(3)演算部１２５とを有する。
【０１３２】
なお、有限体演算部２２０は、CPU，RAM，ROM等を備えた公知又は専用のコンピュータと特別なプログラムとを有する特別な装置である。例えば、GF(36m)演算部２２２−１〜５は、所定のプログラムがCPUに読み込まれて構築される機能部である。また、有限体演算部２２０の少なくとも一部が集積回路によって構成されてもよい。
【０１３３】
＜処理＞
図１４及び図１５は、第２実施形態の処理を説明するための図である。以下、これらの図を用いて本形態の処理を説明する。
【０１３４】
まず、第１実施形態で説明したステップＳ１０１〜Ｓ１０５の処理が実行される。ただし、第１実施形態と同様、b=-1の場合には、ステップＳ１０２〜Ｓ１０５の処理は不要である。
【０１３５】
次に、GF(36m)演算部２２２−１（第１演算部又は第６演算部）が、メモリ１２４からx 1[0],y 1[0],x 2[0],y 2[0]∈GF(3m)（i3=0）を読み込み、6次拡大体GF(36m)上の演算
f[0]=-y1[0]・(x1[0]+x2[0]+b)+y2[0]・σ+y1[0]・ρ∈GF(36m)   …(88)
を行い、その演算結果f[0]∈GF(36m)をメモリ１２４に格納する（ステップＳ２０６）。
【０１３６】
次に、GF(36m)演算部２２２−１（第２演算部又は第７演算部）が、メモリ１２４からx 1[1],y 1[1],x 2[1],y 2[1]∈GF(3m)（i4=1）を読み込み、6次拡大体GF(36m)上の演算
f[1]=-y1[1]・(x1[1]+x2[1]+b)+y2[1]・σ+y1[1]・ρ∈GF(36m)   …(89)
を行い、その演算結果f[1]∈GF(36m)をメモリ１２４に格納する（ステップＳ２０７）。
【０１３７】
次に、GF(36m)演算部２２２−３（第３演算部又は第８演算部）が、メモリ１２４から演算結果f[0]及びf[1]∈GF(36m)を読み込み、
f=f[0]・f[1]∈GF(36m)     …(90)
の演算を行い、その演算結果f∈GF(36m)をメモリ１２４に格納する（ステップＳ２０８）。なお、GF(36m)演算部２２２−３は、f[0]の予め0∈GF(pm)とされた項、及び／又は、f[1]の予め0∈GF(pm)とされた項、を被演算子とした演算を行うことなく、積f[0]・f[1]∈GF(36m)を求める。
【０１３８】
次に、制御部１２３がi=2に設定し、その設定内容をメモリ１２４に格納する（ステップＳ２０９）。
【０１３９】
次に、GF(36m)演算部２２２−１が、メモリ１２４からy1[i],y2[i],x2[i],y 2[i]∈GF(3m)（i3=i）を読み込み、
f[i]=-y1[i]・(x1[i]+x2[i]+b)+y2[i]・σ+y1[i]・ρ∈GF(36m)   …(91)
の演算を行い、その演算結果g[i]∈GF(36m)をメモリ１２４に格納する（ステップＳ２１０）。
【０１４０】
また、GF(36m)演算部２２２−２が、メモリ１２４からy1[i+1],y2[i+1],x2[i+1],y 2[i+1]∈GF(3m)（i4=i+1）を読み込み、
f[i+1]=-y1[i+1]・(x1[i+1]+x2[i+1]+b)
+y2[i+1]・σ+y1[i+1]・ρ∈GF(36m) …(92)
の演算を行い、その演算結果f[i+1]∈GF(36m)をメモリ１２４に格納する（ステップＳ２１１）。
【０１４１】
次に、GF(36m)演算部２２２−３が、メモリ１２４から演算結果f[i]及びf[i+1]∈GF(36m)を読み込み、
f[i]・f[i+1]∈GF(36m)     …(93)
の演算を行い、その演算結果f[i]・f[i+1]∈GF(36m)をメモリ１２４に格納する（ステップＳ２１２）。なお、GF(36m)演算部２２２−３は、f[i]の予め0∈GF(pm)とされた項、及び／又は、f[i+1]の予め0∈GF(pm)とされた項、を被演算子とした演算を行うことなく、積f[i]・f[i+1]∈GF(36m)を求める。
【０１４２】
次に、GF(36m)演算部２２２−４（第４演算部又は第９演算部）が、メモリ１２４からf,f[i]・f[i+1]∈GF(36m)を読み込み、
f=f・f[i]・f[i+1]∈GF(36m)     …(94)
の演算を行い、その演算結果を新たなｆ∈GF(36m)としてメモリ１２４に格納する（ステップＳ２１３）。
【０１４３】
次に、制御部１２３がi=N-2であるか否かを判定する（ステップＳ２１４）。ここで、i=N-2でなければ、制御部２１４はi+2を新たなiに設定し、その設定内容をメモリ１２４に格納して処理をステップＳ２１０に戻す（ステップＳ２１５）。
【０１４４】
一方、i=N-2であれば、第１実施形態のステップＳ１１２以降の処理を実行する。
【０１４５】
＜第２実施形態の特徴＞
以上説明したように、本形態では、第１実施形態で説明したg[i]とg[i+1]に関する演算の工夫に加え、
f[i]=-y1[i]・(x1[i]+x2[i]+b)+y2[i]・σ+y1[i]・ρ∈GF(36m)   …(95)
f[i+1]=-y1[i+1]・(x1[i+1]+x2[i+1]+b)
+y2[i+1]・σ+y1[i+1]・ρ∈GF(36m)     …(96)
を求め、それらの積
f[i]・f[i+1]∈GF(36m)       …(97)
を求め、それらの積を用いて
f=Πi=0N-1f[i]∈GF(36m)       …(98)
を計算する（ステップＳ２０６〜Ｓ２０８，ステップＳ２１０〜Ｓ２１３）。
【０１４６】
ここで、6次拡大体GF(36m)を示す式(95)(96)の多項式は不定元ρ2，ρ・σ，ρ2・σ∈GF(p6m)の項の係数が予め0とされているものである。このような多項式同士の積を先に計算することによって係数が予め0とされている項の演算が不要となり、乗算回数を削減することができる。
【０１４７】
〔第２実施形態の変形例〕
第２実施形態は、Nが4以上の偶数である場合の形態であった。第２実施形態の変形例では、Nが5以上の奇数である場合の処理を説明する。
【０１４８】
図１６は、Nが5以上の奇数である場合の処理を例示するための図である。この変形例ではL=N-1とする。以下では、第２実施形態との相違点のみを説明する。
【０１４９】
第２実施形態の変形例では、第２実施形態で説明したステップＳ２１３の処理の後、制御部１２３がi=(N-1)-2であるか否かを判定する（ステップＳ２５４）。ここで、i=(N-1)-2でなければ、制御部１２３はi+2を新たなiに設定し、その設定内容をメモリ１２４に格納して処理をステップＳ２１０に戻す（ステップＳ２１５）。
【０１５０】
一方、i=(N-1)-2であれば、まず、制御部１２３がi+2を新たなiに設定し、その設定内容をメモリ１２４に格納する（ステップ２５５）。
【０１５１】
次に、GF(36m)演算部２２２−１が、メモリ１２４からy1[i],y2[i],x2[i],y 2[i]∈GF(3m)（i3=i）を読み込み、
f[i]=-y1[i]・(x1[i]+x2[i]+b)+y2[i]・σ+y1[i]・ρ∈GF(36m)   …(99)
の演算を行い、その演算結果g[i]∈GF(36m)をメモリ１２４に格納する（ステップＳ２５６）。
【０１５２】
次に、GF(36m)演算部２２２−４が、メモリ１２４からf,f[i]∈GF(36m)を読み込み、
f=f・f[i]∈GF(36m)     …(100)
の演算を行い、その演算結果を新たなｆ∈GF(36m)としてメモリ１２４に格納する（ステップＳ２５７）。その後、第１実施形態で説明したステップＳ１１２以降の処理が実行される。
【０１５３】
〔第３実施形態〕
次に、本発明の第３実施形態を説明する。
【０１５４】
第１実施形態は、本発明を改良ηＴペアリング演算アルゴリズムのgの演算部分に適用した例であった。第２実施形態では、本発明を改良ηＴペアリング演算アルゴリズムのfの演算部分のみに適用する。
【０１５５】
すなわち、本形態では、K=4，p=3，d=6であり、mが1以上の奇数であり、Nが4以上の偶数であり、L=Nであり、有限体GF(pm)の元R(i,0),R(i,1),R(i,2),R(i,3)が、それぞれ、有限体GF(pm)上で定義された楕円曲線E上の2つの点P(X1[i],Y1[i])及び点Q(X2[i],Y2[i])の各アフィン座標点X 1[i],Y 1[i],X 2[i],Y 2[i]∈GF(pm)であり、演算e(R(i,0),...,R(i,K-1))が、ペアリング演算e(P(X1[i],Y1[i]),Q(X2[i],Y2[i]))であり、演算Πi=0N-1e(R(i,0),...,R(i,K-1))が、マルチペアリング演算Πi=0N-1e(P(X1[i],Y1[i]),Q(X2[i],Y2[i]))である。また、本形態では、楕円曲線として式(10)の超特異楕円曲線Ebを用いる（b=-1であってもよいし、b=1であってもよい）。また、本形態の拡大体演算は、入力部に入力された各アフィン座標点X 1[i],Y 1[i],X 2[i],Y 2[i]又はその像をそれぞれx1[i],y1[i],x2[i],y2[i]とし、u[i]=x1[i]+x2[i]+c∈GF(3m)とし、有限体GF(3m)の元を係数とする既約多項式σ2+1=0の根を不定元σとし、既約多項式ρ3-ρ-b=0の根を不定元ρとした場合における、有限体GF(3m)の6次拡大体GF(36m)の元を示す多項式
f[i]==-y1[i]・(x1[i]+x2[i]+b)+y2[i]・σ+y1[i]・ρ∈GF(36m) …(101)
を求める演算である。以下では、第１実施形態との相違点を中心に説明し、第１実施形態と共通する事項については説明を省略する。
【０１５６】
＜構成＞
図１７及び図１８は、第３実施形態の有限体演算部３２０の基本構成を説明するためのブロック図である。
第３実施形態の有限体演算装置は、図２Ａに示した有限体演算部２０を図１７及び図１８の有限体演算部３２０に置換したものである。以下では、有限体演算部３２０の構成のみを説明する。
【０１５７】
図１７及び図１８に例示するように、本形態の有限体演算部３２０は、有限体GF(3m)上の演算を行うGF(3m)演算部１２１−１〜４と、有限体GF(3m)の6次拡大体GF(36m)上の演算を行うGF(36m)演算部１２２−５，９と、GF(36m)演算部２２２−１〜５と、GF(36m)演算部３２２−１，２と、制御部１２３と、メモリ１２４と、有限体GF(3)上の演算を行うGF(3)演算部１２５とを有する。
【０１５８】
なお、有限体演算部３２０は、CPU，RAM，ROM等を備えた公知又は専用のコンピュータと特別なプログラムとを有する特別な装置である。例えば、GF(36m)演算部３２２−１，２は、所定のプログラムがCPUに読み込まれて構築される機能部である。また、有限体演算部３２０の少なくとも一部が集積回路によって構成されてもよい。
【０１５９】
＜処理＞
図１９及び図２０は、第３実施形態の処理を説明するための図である。以下、これらの図を用いて本形態の処理を説明する。
【０１６０】
まず、第２実施形態で説明したステップＳ１０１〜Ｓ１０５，Ｓ２０６〜２１５の処理（図１４及び図１５）と、第１実施形態で説明したステップＳ１１２〜Ｓ１１８の処理が実行される。ただし、第１実施形態と同様、b=-1の場合には、ステップＳ１０２〜Ｓ１０５の処理は不要である。ステップＳ１１７の判定でi=N-1と判定された場合、次に、GF(36m)演算部３２２−１が、メモリ１２４からy1[0],y2[0],u[0]∈GF(3m)（i1=0）を読み込み、
g=-{u[0]}2+y1[0]・y2[0]・σ-u[0]・ρ-ρ2∈GF(36m)     …(102)
の演算を行い、その演算結果g∈GF(36m)をメモリ１２４に格納する（ステップＳ３１９）。
【０１６１】
次に、GF(36m)演算部３２２−１が、メモリ１２４からy1[1],y2[1],u[1]∈GF(3m)（i1=1）を読み込み、
g'=-{u[1]}2+y1[1]・y2[1]・σ-u[1]・ρ-ρ2∈GF(36m)     …(103)
の演算を行い、その演算結果g'∈GF(36m)をメモリ１２４に格納する。さらに、GF(36m)演算部３２２−２が、メモリ１２４から演算結果g,g'∈GF(36m)を読み込み、
g=g・g'∈GF(36m)     …(104)
の演算を行い、その演算結果を新たなgとしてメモリ１２４に格納する（ステップＳ３２１）。
【０１６２】
次に、制御部１２３がi=2に設定し、その設定内容をメモリ１２４に格納する（ステップＳ１２８）。
【０１６３】
次に、GF(36m)演算部３２２−１が、メモリ１２４からy1[i],y2[i],u[i]∈GF(3m)（i1=i)を読み込み、
g'=-{u[i]}2+y1[i]・y2[i]・σ-u[i]・ρ-ρ2∈GF(36m)     …(105)
の演算を行い、その演算結果を新たなg'∈GF(36m)としてメモリ１２４に格納する（ステップＳ３２９）。
【０１６４】
次に、GF(36m)演算部３２２−２が、メモリ１２４から演算結果g,g'∈GF(36m)を読み込み、
g=g・g'∈GF(36m)     …(106)
の演算を行い、その演算結果を新たなgとしてメモリ１２４に格納する（ステップＳ３３０）。
その後、第１実施形態のステップＳ１３３以降の処理が実行される。
【０１６５】
〔その他の変形例〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上記の各実施形態では、i1=0,i2=1とし、i1=i,i2=i+1とし、i3=0,i4=1とし、i3=i,i4=i+1とする例を示した。しかし、i1とi2とが異なり、i3とi4とが異なるのであれば、その他のi1,i2,i3,i4∈{0,...,N-1}を用いてもよい。すなわち、集合{0,...,N-1}のL個〔Lは偶数〕の異なる元からなる部分集合の各元をそれぞれ１回ずつi1又はi2とし、i1とi2とを変更しながら第１演算部と第２演算部と第３演算部とによる一連の処理をL/2回実行させるループ処理が実行され、集合{0,...,N-1}のW個〔Wは正の偶数〕の異なる元からなる部分集合の各元をそれぞれ１回ずつi3又はi4とし、i3とi4とを変更しながら第６演算部と第７演算部と第８演算部とによる一連の処理をW/2回実行されればよい。言い換えると、集合{0,...,N-1}に含まれるL個〔Lは偶数〕の互いに異なる複数の元からなる部分集合の各元がそれぞれ１回ずつi1又はi2として選択され、選択されたi1とi2との組のそれぞれに対して第１演算部と第２演算部と第３演算部とによる第１処理が１回ずつ実行されることで、L/2個の上記組(i1, i2)のそれぞれに対応する第１処理が実行され、集合{0,...,N-1}に含まれるW個〔Wは正の偶数〕の互いに異なる複数の元からなる部分集合の各元がそれぞれ１回ずつi3又はi4として選択され、選択されたi3とi4との組のそれぞれに対して第６演算部と第７演算部と第８演算部とによる第２処理が１回ずつ実行されることで、W/2個の上記組(i3, i4)のそれぞれに対応する第２処理が実行されればよい。
【０１６６】
また、上記の各実施形態では、Nが4以上の偶数であってL=NやW=Nとする構成や、Nが5以上の奇数であってL=N-1やW=N-1とする構成を説明した。しかし、N未満のその他の正の偶数をLやWとしてもよい。この場合、本発明の手法を適用しないこととなるiについての処理は、図１１のステップＳ１６１，Ｓ１６２や、図１６のステップＳ２５６，Ｓ２５７に示したような累積乗算を繰り返すことで実行できる。また、L≠Wであってもよい。また、Nが2や3であってもよい。この場合には、図７のステップＳ１０８〜Ｓ１１１，Ｓ１１３、図９のステップＳ１２８〜Ｓ１４０、図１１のステップＳ１２８〜Ｓ１５９、図１５のステップＳ２０９〜Ｓ２１５、図１６のステップＳ２０９〜Ｓ２１５、Ｓ２５４の処理は不要となる。
【０１６７】
また、上記の各実施形態では、bなどのパラメータが予め設定されていることとしたが、これらのパラメータが装置に入力される構成であってもよい。
【０１６８】
また、上記の各実施形態では、多項式poly(R(i1,0),...,R(i1,K-1))の予め0∈GF(pm)とされた項、及び／又は、多項式poly(R(i2,0),...,R(i2,K-1))の予め0∈GF(pm)とされた項、を被演算子とした演算を行うことなく、積poly(R(i1,0),...,R(i1,K-1))・poly(R(i2,0),...,R(i2,K-1))を求めることとした。しかし、これらの予め0∈GF(pm)とされた項の一部を被演算子とした演算を行うことにしてもよい。
【０１６９】
また、上記の各実施形態では、本発明を標数3の改良ηＴペアリング演算アルゴリズムに適用することとしたが、その他の標数3のペアリング演算や、標数2のペアリング演算や、その他の標数のペアリング演算に本発明を適用してもよい。
【０１７０】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１７１】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１７２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１７３】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１７４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【産業上の利用可能性】
【０１７５】
本発明の産業上の利用分野としては、内積述語暗号などのマルチペアリング演算を用いる暗号技術分野を例示できる。
【符号の説明】
【０１７６】
１  有限体演算装置
１０  入力部
３０  出力部
２０，１２０，２２０，３２０  有限体演算部
【図１】
2010123117.tif 000003
【図２】
2010123117.tif 000004
【図３】
2010123117.tif 000005
【図４】
2010123117.tif 000006
【図５】
2010123117.tif 000007
【図６】
2010123117.tif 000008
【図７】
2010123117.tif 000009
【図８】
2010123117.tif 000010
【図９】
2010123117.tif 000011
【図１０】
2010123117.tif 000012
【図１１】
2010123117.tif 000013
【図１２】
2010123117.tif 000014
【図１３】
2010123117.tif 000015
【図１４】
2010123117.tif 000016
【図１５】
2010123117.tif 000017
【図１６】
2010123117.tif 000018
【図１７】
2010123117.tif 000019
【図１８】
2010123117.tif 000020
【図１９】
2010123117.tif 000021
【図２０】
2010123117.tif 000022
【国際調査報告】
2010123117.tif 000023
2010123117.tif 000024
2010123117.tif 000025