(57)【要約】  埋め込み次数１かつ合成数位数の楕円曲線上の有理点について、自己準同形写像により定まる部分群を用いることにより、スカラー倍算およびペアリング演算を効率的に行う。
2012015047.tif 000002
【特許請求の範囲】
【請求項１】
標数ｐの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をE(Fp)とし、合成数位数ｒを持つ有理点の集合すなわち前記加法群の部分群をG=E(Fp)[r]として、有理点P∈Gの整数0<s<rによるスカラー倍算[s]Pを演算するCPU及び記憶手段を備えたスカラー倍算装置において、
前記加法群E(Fp)は、埋め込み次数を１とし、
前記CPUは、
有理点P’∈E(Fp)[r]、前記整数s、をそれぞれ入力して前記記憶手段に記憶する入力手段と、
前記記憶手段から前記有理点P’を読み出し、自己準同型写像ψ(P)=λP（λは整数）を満足する前記有理点Pの集合である前記部分群Gを特定し、前記有理点Pを前記記憶手段に記憶する有理点部分群特定手段と、
前記記憶手段から前記有理点Pを読み出し、前記自己準同型写像ψ(P)を演算し、その結果の有理点を前記記憶手段に記憶する自己準同型写像演算手段と、
前記記憶手段から前記整数ｓを読み出し、次式に基づいてλ進展開し、
s=s0+s1λ
係数s０及びs１を求めその結果を前記記憶手段に記憶するλ進展開手段と、
スカラー倍算を、
[s]P＝［s0 +s1λ］P=［s0］P +［s1］ψ(P)
として演算し、その結果を前記記憶手段に記憶するマルチ・スカラー倍算演算手段と、を有することを特徴とするスカラー倍算装置。
【請求項２】
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 3|(p-1) であり、
前記合成数位数ｒは、 r|#E(Fp), 3|(r-1) を満たし、
前記整数λは、 λ2+λ +1≡0(mod r) を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,y), ε3=1,ε(≠1)∈Fp である請求項１に記載のスカラー倍算装置。
【請求項３】
前記楕円曲線は、 E:y2 = x3 +ax, a∈Fp, 4|(p-1) であり、
前記合成数位数ｒは、 r|#E(Fp), 4|(r-1) を満たし、
前記整数λは、 λ2+1≡0(mod r) を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (−x,ζy),ζ4=1,ζ(≠1)∈Fp である請求項１に記載のスカラー倍算装置。
【請求項４】
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 6|(p-1) であり、
前記合成数位数ｒは、 r|#E(Fp), 3|(r-1) を満たし、
前記整数λは、 λ2-λ +1≡0(mod r) を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,-y), ε3=1,ε(≠1)∈Fp である請求項１に記載のスカラー倍算装置。
【請求項５】
標数ｐの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をE(Fp)とし、合成数位数ｒを持つ有理点の集合すなわち前記加法群の部分群をG=E(Fp)[r]として、有理点P∈Gの整数0<s<rによるスカラー倍算[s]Pを、CPU及び記憶手段を備えた電子計算機で演算するスカラー倍算方法において、
前記加法群E(Fp)は、埋め込み次数を１とし、
前記電子計算機のCPUを入力手段として機能させて、有理点P’∈E(Fp)[r]、前記整数ｓ、をそれぞれ入力して前記記憶手段に記憶する入力ステップと、
前記電子計算機のCPUを有理点部分群特定手段として機能させて、前記記憶手段からP’を読み出し、自己準同型写像ψ(P)=λP（λは整数）を満足する前記有理点Pの集合である前記部分群Gを特定し、前記有理点Pを前記記憶手段に記憶する有理点部分群特定ステップと、
前記電子計算機のCPUを自己準同型写像演算手段として機能させて、前記記憶手段から前記有理点Pを読み出し、前記自己準同型写像ψ(P)を演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算ステップと、
前記電子計算機のCPUをλ進展開手段として機能させて、前記記憶手段から前記整数ｓを読み出し次式に基づいてλ進展開し、
s=s0+s1λ
係数s０及びs１を求めその結果を前記記憶手段に記憶するλ進展開ステップと、
前記電子計算機のCPUをマルチ・スカラー倍算演算手段として機能させて、スカラー倍算を、
[s]P＝[s0 +s1λ]P= [s0]P +[s1]ψ(P)
として演算しその結果を前記記憶手段に記憶するマルチ・スカラー倍算演算ステップと、を有することを特徴とするスカラー倍算方法。
【請求項６】
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 3|(p-1) であり、
前記合成数位数ｒは、 r|#E(Fp), 3|(r-1) を満たし、
前記整数λは、 λ2+λ +1≡0(mod r) を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,y), ε3=1,ε(≠1)∈Fp である請求項５に記載のスカラー倍算方法。
【請求項７】
前記楕円曲線は、 E:y2 = x3 +ax, a∈Fp, 4|(p-1) であり、
前記合成数位数ｒは、 r|#E(Fp), 4|(r-1) を満たし、
前記整数λは、 λ2+1≡0(mod r) を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (−x,ζy),ζ4=1,ζ(≠1)∈Fp である請求項５に記載のスカラー倍算方法。
【請求項８】
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 6|(p-1) であり、
前記合成数位数ｒは、 r|#E(Fp), 3|(r-1) を満たし、
前記整数λは、 λ2-λ +1≡0(mod r) を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,-y), ε3=1,ε(≠1)∈Fp である請求項５に記載のスカラー倍算方法。
【請求項９】
標数ｐの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をE(Fp)とし、合成数位数ｒを持つ有理点の集合すなわち前記加法群の部分群をG=E(Fp)[r]として、有理点P∈Gの整数0<s<rによるスカラー倍算[s]Pを、CPU及び記憶手段を備えた電子計算機に演算させるスカラー倍算プログラムにおいて、
前記加法群E(Fp)は、埋め込み次数を１とし、
前記電子計算機のCPUを、
有理点P’∈E(Fp)[r]、前記整数ｓをそれぞれ入力し、前記記憶手段に記憶する入力手段、
前記記憶手段からP’を読み出し自己準同型写像ψ(P)= λPを満足する前記有理点Pの集合である前記部分群Gを特定し、前記有理点Pを前記記憶手段に記憶する有理点部分群特定手段、前記記憶手段から前記有理点Pを読み出し、自己準同型写像ψ(P)を演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算手段、
前記記憶手段から前記整数ｓを読み出し、次式に基づいてλ進展開し、
s=s0+s1λ
係数s０及びs１を求めその結果を前記記憶手段に記憶するλ進展開手段、
スカラー倍算を、
[s]P＝[s0 +s1λ]P= [s0]P +[s1]ψ(P)
として演算し、その結果を前記記憶手段に記憶するマルチ・スカラー倍算演算手段、
として機能させることを特徴とするスカラー倍算プログラム。
【請求項１０】
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 3|(p-1) であり、
前記合成数位数ｒは、 r|#E(Fp), 3|(r-1) を満たし、
前記整数λは、 λ2+λ +1≡0(mod r) を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,y), ε3=1,ε(≠1)∈Fp である請求項９に記載のスカラー倍算プログラム。
【請求項１１】
前記楕円曲線は、 E:y2 = x3 +ax, a∈Fp, 4|(p-1) であり、
前記合成数位数ｒは、 r|#E(Fp), 4|(r-1) を満たし、
前記整数λは、 λ2+1≡0(mod r) を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (−x,ζy),ζ4=1,ζ(≠1)∈Fp である請求項９に記載のスカラー倍算プログラム。
【請求項１２】
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 6|(p-1) であり、
前記合成数位数ｒは、 r|#E(Fp), 3|(r-1) を満たし、
前記整数λは、 λ2-λ +1≡0(mod r) を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,-y), ε3=1,ε(≠1)∈Fp である請求項９に記載のスカラー倍算プログラム。
【請求項１３】
標数ｐの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をE(Fp)とし、合成数位数ｒを持つ有理点の集合すなわち前記加法群の部分群をG1=E(Fp)[r]、G2=E(Fp)[r]として、次式により、
e:G1×G2→F*p/( F*p)r
である非退化な双線形写像としてペアリングeを定義し、
有理点P(xP,yP)∈G1及びQ(xQ,yQ)∈G2、ミラーのアルゴリズムを用いて計算される有理関数をｆとして、ペアリングe(P,Q)を演算するCPU及び記憶手段を備えたペアリング演算装置において、
前記加法群E(Fp)は、埋め込み次数を１とし、
前記CPUは、
有理点P’を入力して前記記憶手段に記憶する入力手段と、
前記記憶手段から前記有理点P’を読み出し、自己準同型写像ψにより、
λ1P=ψ(P)、λ２Q=ψ(Q)  （λ1≠λ２は整数）を満足する前記有理点P及びQの集合である前記部分群G1及びG2を特定する有理点部分群特定手段と、
前記記憶手段から前記有理点PまたはQを読み出し、前記自己準同型写像ψ(P) またはψ(Q)を演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算手段と、
前記ｆを演算する第1演算手段と、
所定の有理点を通る直線及び垂線の前記有理点Qにおける値を演算する第2演算手段と、
前記ｆと前記値を用いてf’r,p(Q)を演算する第3演算手段と、
前記f’r,p(Q)を用いて前記ペアリングe(P,Q)を
【数１】
2012015047.tif 000022
として演算する第4演算手段と
を有するペアリング演算装置。
【請求項１４】
前記楕円曲線は、 E:y2 = x3 +ax, a∈Fp, 4|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 4|(r-1) を満たし、
前記整数λ1、λ2は、λ12+1≡0(mod r)、λ22+1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (-x,ζy),ζ4=1, ζ(≠1)∈Fp  であり、
前記f’r,p(Q)は、
【数２】
2012015047.tif 000023
である請求項１３に記載のペアリング演算装置。
【請求項１５】
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 3|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12+λ1+1≡0(mod r)、λ22+λ2 +1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,y), ε3=1, ε(≠1)∈Fp  であり、
前記f’r,p(Q)は、
【数３】
2012015047.tif 000024
である請求項１３に記載のペアリング演算装置。
【請求項１６】
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 6|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12-λ1+1≡0(mod r)、λ22-λ2 +1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,-y), ε3=1, ε(≠1)∈Fp  であり、
前記f’r,p(Q)は、
【数４】
2012015047.tif 000025
である請求項１３に記載のペアリング演算装置。
【請求項１７】
標数ｐの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をE(Fp)とし、合成数位数ｒを持つ有理点の集合すなわち前記加法群の部分群をG1=E(Fp)[r]、G2=E(Fp)[r]として、次式により、
e:G1×G2→F*p/( F*p)r
である非退化な双線形写像としてペアリングeを定義し、
有理点P(xP,yP)∈G1及びQ(xQ,yQ)∈G2、ミラーのアルゴリズムを用いて計算される有理関数をｆとして、CPU及び記憶手段を備えた電子計算機でペアリングe(P,Q)を演算するペアリング演算方法において、
前記加法群E(Fp)は、埋め込み次数を１とし、
前記電子計算機のCPUを入力手段として機能させて、有理点P’を入力して前記記憶手段に記憶する入力ステップと、
前記電子計算機のCPUを有理点部分群特定手段として機能させて、前記記憶手段から前記有理点P’を読み出し、自己準同型写像ψにより、
λ1P=ψ(P)、λ２Q=ψ(Q)  （λ1≠λ２は整数）を満足する前記有理点P及びQの集合である前記部分群G1及びG2を特定するステップと、
前記電子計算機のCPUを自己準同型写像演算手段として機能させて、前記記憶手段から前記有理点PまたはQを読み出し、前記自己準同型写像ψ(P) またはψ(Q)を演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算ステップと、
前記電子計算機のCPUを第1演算手段として機能させて、前記ｆを演算する第1演算ステップと、
前記電子計算機のCPUを第2演算手段として機能させて、所定の有理点を通る直線及び垂線の前記有理点Qにおける値を演算する第2演算ステップと、
前記電子計算機のCPUを第3演算手段として機能させて、前記ｆと前記値を用いてf’r,p(Q)を演算する第3演算ステップと、
前記電子計算機のCPUを第4演算手段として機能させて、前記f’r,p(Q)を用いて前記ペアリングe(P,Q)を
【数５】
2012015047.tif 000026
として演算する第4演算ステップと、
を有するペアリング演算方法。
【請求項１８】
前記楕円曲線は、 E:y2 = x3 +ax, a∈Fp, 4|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 4|(r-1) を満たし、
前記整数λ1、λ2は、λ12+1≡0(mod r)、λ22+1≡0(mod r) を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (-x,ζy),ζ4=1,ζ(≠1)∈Fp  であり、
前記f’r,p(Q)は、
【数６】
2012015047.tif 000027
である請求項１７に記載のペアリング演算方法。
【請求項１９】
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 3|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12+λ1+1≡0(mod r)、λ22+λ2 +1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,y),ε3=1,ε(≠1)∈Fp  であり、
前記f’r,p(Q)は、
【数７】
2012015047.tif 000028
である請求項１７に記載のペアリング演算方法。
【請求項２０】
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 6|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12-λ1+1≡0(mod r)、λ22-λ2 +1≡0(mod r) であり、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,-y),ε3=1,ε(≠1)∈Fp  であり、
前記f’r,p(Q)は、
【数８】
2012015047.tif 000029
である請求項１７に記載のペアリング演算方法。
【請求項２１】
標数ｐの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をE(Fp)とし、合成数位数ｒを持つ有理点の集合すなわち前記加法群の部分群をG1=E(Fp)[r]、G2=E(Fp)[r]として、次式により、
e:G1×G2→F*p/( F*p)r
である非退化な双線形写像としてペアリングeを定義し、
有理点P(xP,yP)∈G1及びQ(xQ,yQ)∈G2、ミラーのアルゴリズムを用いて計算される有理関数をｆとして、CPU及び記憶手段を備えた電子計算機にペアリングe(P,Q)を演算させるペアリング演算プログラムにおいて、
前記加法群E(Fp)は、埋め込み次数を１とし、
前記電子計算機のCPUを、有理点P’を入力して前記記憶手段に記憶する入力手段、
前記記憶手段から前記有理点P’を読み出し、自己準同型写像ψにより、
λ1P=ψ(P)、λ２Q=ψ(Q)  （λ1≠λ２は整数）を満足する前記有理点P及びQの集合である前記部分群G1及びG2を特定する有理点部分群特定手段、
前記記憶手段から前記有理点PまたはQを読み出し、前記自己準同型写像ψ(P) またはψ(Q)を演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算手段、
前記ｆを演算する第1演算手段、
所定の有理点を通る直線及び垂線の前記有理点Qにおける値を演算する第2演算手段、
前記ｆと前記値を用いてf’r,p(Q)を演算する第3演算手段、
前記f’r,p(Q)を用いて前記ペアリングe(P,Q)を
【数９】
2012015047.tif 000030
として演算する第4演算手段、
として機能させるペアリング演算プログラム。
【請求項２２】
前記楕円曲線は、 E:y2 = x3 +ax, a∈Fp, 4|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 4|(r-1) を満たし、
前記整数λ1、λ2は、λ12+1≡0(mod r)、λ22+1≡0(mod r) であり、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (-x,ζy),ζ4=1,ζ(≠1)∈Fp  であり、
前記f’r,p(Q)は、
【数１０】
2012015047.tif 000031
である請求項２１に記載のペアリング演算プログラム。
【請求項２３】
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 3|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12+λ1+1≡0(mod r)、λ22+λ2 +1≡0(mod r) であり、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,y),ε3=1,ε(≠1)∈Fp   であり、
前記f’r,p(Q)は、
【数１１】
2012015047.tif 000032
である請求項２１に記載のペアリング演算プログラム。
【請求項２４】
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 6|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12-λ1+1≡0(mod r)、λ22-λ2 +1≡0(mod r) であり、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,-y),ε3=1,ε(≠1)∈Fp  であり、
前記f’r,p(Q)は、
【数１２】
2012015047.tif 000033
である請求項２１に記載のペアリング演算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有理点Pのスカラー倍算[ｓ]Pを行うスカラー倍算装置、スカラー倍算方法、及びスカラー倍算プログラム、並びにペアリング演算を高速に実行可能としたペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラムに関する。特に、有理点群の埋め込み次数を１とした場合において、有理点Pのスカラー倍算[ｓ]Pを行うスカラー倍算装置、スカラー倍算方法、及びスカラー倍算プログラム、並びに有理点群の埋め込み次数を１とした場合において、ペアリング演算を高速に実行可能としたペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラムに関する。
【背景技術】
【０００２】
昨今、インターネットなどの電気通信回線を利用した情報ネットワーク技術が高度に発展し、インターネットによって様々な情報を取得するだけでなく、インターネットバンキングや行政機関への電子申請などのような各種のサービスが提供されてきている。【０００３】
このようなサービスを利用する場合には、サービスの利用者が成りすましや架空の人間などではなく、適正な利用者であることを確認するための認証処理が必要であり、信頼性の高い認証方法として、公開鍵と秘密鍵を用いる公開鍵暗号をベースとした電子認証技術がよく利用されている。【０００４】
しかしながら、公開鍵暗号方式の電子認証では、公開鍵あるいは秘密鍵が漏洩した場合には直ちに公開鍵と秘密鍵を変更する必要があり、公開鍵及び秘密鍵の管理を慎重に行わなければならないとともに、必要に応じて新たな公開鍵と秘密鍵の設定登録作業が生じるという煩雑さがあるため、最近では、利用者の氏名やメールアドレスのように利用者特有のIDを用いて電子認証を行うIDベース暗号が用いられることが多くなっている。【０００５】
また、電子認証を行う認証装置によって利用者の個人認証を行った場合には、認証装置に利用者ごとの履歴が蓄積されることとなり、この履歴情報自体が利用者の個人情報であって、最近では、この履歴情報が漏洩することによる個人情報の漏洩のおそれが指摘されている。【０００６】
そこで、認証装置では利用者の個人情報を利用して認証を行うのではなく、複数の利用者をひとまとまりのグループとして、このグループに所属していることを示すグループ署名を用いることにより、利用者を特定することなく認証を行うことによって、認証装置に個人情報が蓄積されることなく認証を可能としたグループ署名技術が提案されている。【０００７】
国家UNS戦略プログラムにおいても、プライバシを保護しつつユーザ認証を行うことのできる匿名認証技術の重要性、必要性が取り上げられている。
UNS:Universal Communications、New Generation Networks、Security and safety【０００８】
このようなIDベース暗号やグループ署名等を簡便に実現するための数学的な土台としてペアリング暗号がある。ペアリングとは、楕円曲線上で定義される２入力１出力の関数であり、入力は楕円曲線上の２つの有理点、出力は有限体の元が用いられている。このペアリングは２入力に対して双線形性を持つ。すなわち、例えば、Pを素体Fp上で定義される楕円曲線上の有理点、Qをk次拡大体Fpk上で定義される楕円曲線上の有理点として、PとQを入力して拡大体F*pkの元ｚが出力されるとき、a倍のPとｂ倍のQを入力するとｚのab乗が出力される。ペアリング暗号ではこの双線形性を利用して暗号システムを構築する。なお、ここで「ｋ」を埋め込み次数と呼び「F*pk」は、位数がpｋである有限体（拡大体）から単位元０を除いた乗法群を表わす。【０００９】
楕円曲線上の有理点とは、楕円曲線ｙ２＝ｘ３+ax＋ｂを満たす有限体Fqの元の座標（x,y）の組をいう。この集合に無限遠点Oを加えたものは加法群を成し、E(Fq)と表わす。すなわち、楕円曲線上の2つの有理点P、Qを通る直線が楕円曲線と交わる点のｘ軸を対称とした点をRとすれば、P+Q=Rが成立する。この演算を楕円加算と呼ぶ。PとQが同一点の場合はPを通る接線が楕円曲線と交わる点のｘ軸を対称とした点をRとすれば、P＋P=2P=Rが成立する。この演算を楕円２乗算と呼ぶ。ペアリング暗号及び楕円暗号の安全性の根拠は楕円曲線上の離散対数問題の求解困難性に基づいている。素因数分解の困難性を安全性の根拠とするRSA暗号等と比べ、はるかに短い鍵長で同等の暗号強度（安全性強度）を実現できる。【００１０】
このような楕円曲線上の有理点のペアリング演算は、ミラーのアルゴリズムを用いて演算するステップとその演算結果に対してべき乗算を行うステップで構成されている。【００１１】
デジタルグループ署名では、グループに所属する個人ユーザのアクセス権の認証処理を行う際に、アクセス権が失効している個人ユーザを除外するためのペアリング演算を行った後に所定の個人ユーザのペアリング演算を行って認証処理を行うことにより、個人ユーザごとのアクセス権の発行または失効の属性変更に柔軟に対応可能としている。【００１２】
したがって、例えば、10,000人の個人ユーザで構成されるグループのデジタルグループ署名の場合、アクセス権が失効している個人ユーザが100人いれば、100回のペアリング演算が必要となっており、現時点での一般的な電子計算機による1回のペアリング演算に約0.1秒を要していることから、100回のペアリング演算には約10秒を要することとなってしまうため、実用上、個人ユーザの数が制限されることとなって、広く利用されるものとはなっていなかった。【００１３】
そこで、ペアリング演算の演算速度を向上させることによりデジタルグループ署名の実用性を向上させるために、例えば、ペアリング演算として楕円曲線上で定義されるTateペアリング演算法を用い、演算負荷を低減させて高速化を図る技術が提案されている（例えば、特許文献１、非特許文献１参照。）。【００１４】
また、IDベース暗号における暗号化あるいは復号の処理や、グループ署名における認証処理では、できるだけ短時間に実行することが求められる。特にペアリングに基づく暗号方式などにおいてはスカラー倍算が数多く実行されているためスカラー倍算を高速に実行することも求められている。【００１５】
スカラー倍算の高速化手法として、バイナリー法やWindow法が知られている。
また、自己準同型写像を利用することにより、演算回数を削減して高速化を図る手法も提案されている（例えば、非特許文献２、特許文献２参照。）。【００１６】
このように、これまでペアリングを用いた暗号方式（IDベース暗号、グループ署名等）は数多く提案され、また、それを高速に実行するために大きな割合を占めるスカラー倍算の高速化手法も数多く提案されているが、その多くは、160ビット以上の素数位数を持つペアリング曲線（ペアリングに効率のよい楕円曲線）を用いるものである。本発明者らはこれまで、土台の数学的構造から、拡大体における計算、楕円曲線暗号の計算、ペアリング計算について出願を行なってきた。そのいずれもが、素数位数のペアリング暗号を効率化するものである。【００１７】
一方、近年、有理点群の埋め込み次数が１で2000ビットを超える合成数位数（r=22000）を持つペアリング曲線を用いるものが提案されており、また新たなアプリケーションも提案されている（例えば、非特許文献３参照。）。【００１８】
素数位数のペアリング暗号を効率化するこれまでの手法は、本発明がターゲットとする大きな合成数位数のペアリングに対して即座に適用できるものではない。言い換えれば、合成数位数のペアリング曲線は埋め込み次数が１となるなど特殊な状況におかれるため、これを考慮した新たな高速化手法を提案する必要性がでてきた。埋め込み次数を１とする理由は、ペアリング暗号の暗号強度を必要十分に確保するための強度と効率のバランスを図るのに最も適しているのが埋め込み次数１だからである。埋め込み次数を大きくした場合は暗号強度が十分すぎ、また実現する上での効率が悪くなる。【００１９】
しかしながら、有理点群の埋め込み次数を１とし合成数位数を用いるアプリケーションに用いるためのペアリング曲線の生成法や、ペアリング計算やスカラー倍算の効率化手法等は未だ十分ではない。
【先行技術文献】
【特許文献】
【００２０】
【特許文献１】特開２００５−３１６２６７号公報
【特許文献２】特開２００４−２７１７９２号公報
【非特許文献】
【００２１】
【非特許文献１】K.Takashima, “Scaling Security of Elliptic Curves with Fast Pairing Using Efficient Endomorphisms”,IEICE,vol.90-A,no.1,Jan 2007
【非特許文献２】R. Gallant, R. Lambert, and S. Vanstone, “Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms”
【非特許文献３】D. Boneh, K. Rubin and A. Silverberg, “Finding Composite OrderOrdinary Elliptic Curves Using the Cock-Pinch method”
【発明の開示】
【発明が解決しようとする課題】
【００２２】
従来、有理点群の埋め込み次数が1でない場合には、2つの有理点部分群G1,G2を簡便に識別できたため、それらを用いてGLV（Gallant-Lambert-Vanstone）法（スカラー倍算の高速化手法）やXateペアリング（ペアリングの高速化手法）を適用することができた。【００２３】
しかしながら、有理点群の埋め込み次数を１とした場合、従来のように効率的にスカラー倍算やペアリング計算を行うことができる有理点の部分群を特定する方法がこれまで知られていなかった。そこで、そのような特殊な条件、すなわち、素体上でスカラー倍算を効率的に行えるような有理点だけから成る部分群を識別、特定する必要があった。そして、現在提案されているスカラー倍算及びペアリング演算の高速化は未だに十分ではなく、さらなる高速化が求められている。【００２４】
本発明者らは、このような現状に鑑み、有理点群の埋め込み次数を１とし大きな合成数位数を持つペアリング曲線におけるスカラー倍算及びペアリング演算を高速化することにより実用性を向上させるべく研究開発を行って、本発明を成すに至ったものである。
【課題を解決するための手段】
【００２５】
本発明のスカラー倍算装置では、
標数ｐの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をE(Fp)とし、合成数位数ｒを持つ有理点の集合すなわち前記加法群の部分群をG=E(Fp)[r]として、有理点P∈Gの整数0<s<rによるスカラー倍算[s]Pを演算するCPU及び記憶手段を備えたスカラー倍算装置において、
前記加法群E(Fp)は、埋め込み次数を１とし、
前記CPUは、
有理点P’∈E(Fp)[r]、前記整数s、をそれぞれ入力して前記記憶手段に記憶する入力手段と、
前記記憶手段から前記有理点P’を読み出し、自己準同型写像ψ(P)=λP（λは整数）を満足する前記有理点Pの集合である前記部分群Gを特定し、前記有理点Pを前記記憶手段に記憶する有理点部分群特定手段と、
前記記憶手段から前記有理点Pを読み出し、前記自己準同型写像ψ(P)を演算し、その結果の有理点を前記記憶手段に記憶する自己準同型写像演算手段と、
前記記憶手段から前記整数ｓを読み出し、次式に基づいてλ進展開し、
s=s0+s1λ
係数s０及びs１を求めその結果を前記記憶手段に記憶するλ進展開手段と、
スカラー倍算を、
[s]P=[s0+s1λ]P=[s0]P+[s1]ψ(P)
として演算し、その結果を前記記憶手段に記憶するマルチ・スカラー倍算演算手段と、を有することとした。【００２６】
さらに、本発明のスカラー倍算装置では、
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 3|(p-1) であり、
前記合成数位数ｒは、 r|#E(Fp), 3|(r-1) を満たし、
前記整数λは、 λ2+λ +1≡0(mod r) を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,y), ε3=1, ε(≠1)∈Fp であることにも特徴を有するものである。【００２７】
さらに、本発明のスカラー倍算装置では、
前記楕円曲線は、 E:y2 = x3 +ax, a∈Fp, 4|(p-1) であり、
前記合成数位数ｒは、 r|#E(Fp), 4|(r-1) を満たし、
前記整数λは、 λ2+1≡0(mod r) を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (−x,ζy),ζ4=1, ζ,ζ2(≠1)∈Fpであることにも特徴を有するものである。【００２８】
さらに、本発明のスカラー倍算装置では、
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 6|(p-1) であり、
前記合成数位数ｒは、 r|#E(Fp), 3|(r-1) を満たし、
前記整数λは、 λ2-λ +1≡0(mod r) を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,-y), ε3=1,ε(≠1)∈Fp であることにも特徴を有するものである。【００２９】
本発明のスカラー倍算方法では、
標数ｐの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をE(Fp)とし、合成数位数ｒを持つ有理点の集合すなわち前記加法群の部分群をG=E(Fp)[r]として、有理点P∈Gの整数0<s<rによるスカラー倍算[s]Pを、CPU及び記憶手段を備えた電子計算機で演算するスカラー倍算方法において、
前記加法群E(Fp)は、埋め込み次数を１とし、
前記電子計算機のCPUを入力手段として機能させて、有理点P’∈E(Fp)[r]、前記整数ｓ、をそれぞれ入力して前記記憶手段に記憶する入力ステップと、
前記電子計算機のCPUを有理点部分群特定手段として機能させて、前記記憶手段からP’を読み出し、自己準同型写像ψ(P)=λP（λは整数）を満足する前記有理点Pの集合である前記部分群Gを特定し、前記有理点Pを前記記憶手段に記憶する有理点部分群特定ステップと、
前記電子計算機のCPUを自己準同型写像演算手段として機能させて、前記記憶手段から前記有理点Pを読み出し、前記自己準同型写像ψ(P)を演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算ステップと、
前記電子計算機のCPUをλ進展開手段として機能させて、前記記憶手段から前記整数ｓを読み出し次式に基づいてλ進展開し、
s=s0+s1λ
係数s０及びs１を求めその結果を前記記憶手段に記憶するλ進展開ステップと、
前記電子計算機のCPUをスカラー倍算演算手段として機能させて、スカラー倍算を、 
[s]P=[s0+s1λ]P=[s0]P+[s1]ψ(P)
として演算しその結果を前記記憶手段に記憶するマルチ・スカラー倍算演算ステップと、を有することとした。【００３０】
さらに、本発明のスカラー倍算方法では、
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 3|(p-1) であり、
前記合成数位数ｒは、 r|#E(Fp), 3|(r-1) を満たし、
前記整数λは、 λ2+λ +1≡0(mod r) を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、    
(x,y) → (εx,y), ε3=1,ε(≠1)∈Fp であることにも特徴を有するものである。【００３１】
さらに、本発明のスカラー倍算方法では、
前記楕円曲線は、 E:y2 = x3 +ax, a∈Fp, 4|(p-1) であり、
前記合成数位数ｒは、 r|#E(Fp), 4|(r-1) を満たし、
前記整数λは、 λ2+1≡0(mod r) を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、  
(x,y) → (−x,ζy),ζ4=1, ζ,ζ2(≠1)∈Fp であることにも特徴を有するものである。【００３２】
さらに、本発明のスカラー倍算方法では、
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 6|(p-1) であり、
前記合成数位数ｒは、 r|#E(Fp), 3|(r-1) を満たし、
前記整数λは、 λ2-λ +1≡0(mod r) を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、    
(x,y) → (εx,-y), ε3=1,ε(≠1)∈Fp であることにも特徴を有するものである。【００３３】
本発明のスカラー倍算プログラムでは、
標数ｐの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をE(Fp)とし、合成数位数ｒを持つ有理点の集合すなわち前記加法群の部分群をG=E(Fp)[r]として、有理点P∈Gの整数0<s<rによるスカラー倍算[s]Pを、CPU及び記憶手段を備えた電子計算機に演算させるスカラー倍算プログラムにおいて、
前記加法群E(Fp)は、埋め込み次数を１とし、
前記電子計算機のCPUを、
有理点P’∈E(Fp)[r]、前記整数ｓをそれぞれ入力し、前記記憶手段に記憶する入力手段、前記記憶手段からP’を読み出し自己準同型写像ψ(P)= λPを満足する前記有理点Pの集合である前記部分群Gを特定し、前記有理点Pを前記記憶手段に記憶する有理点部分群特定手段、
前記記憶手段から前記有理点Pを読み出し、自己準同型写像ψ(P)を演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算手段、
前記記憶手段から前記整数ｓを読み出し、次式に基づいてλ進展開し、
s=s0+s1λ
係数s０及びs１を求めその結果を前記記憶手段に記憶するλ進展開手段、
スカラー倍算を、
[s]P=[s0+s1λ]P=[s0]P+[s1]ψ(P)
として演算し、その結果を前記記憶手段に記憶するマルチ・スカラー倍算演算手段、
として機能させることとした。【００３４】
さらに、本発明のスカラー倍算プログラムでは、
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 3|(p-1) であり、
前記合成数位数ｒは、 r|#E(Fp), 3|(r-1) を満たし、
前記整数λは、 λ2+λ +1≡0(mod r) を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,y), ε3=1,ε(≠1)∈Fp であることにも特徴を有するものである。【００３５】
さらに、本発明のスカラー倍算プログラムでは、
前記楕円曲線は、 E:y2 = x3 +ax, a∈Fp, 4|(p-1) であり、
前記合成数位数ｒは、 r|#E(Fp), 4|(r-1) を満たし、
前記整数λは、 λ2+1≡0(mod r) を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、    
(x,y) → (−x,ζy),ζ4=1, ζ,ζ2(≠1)∈Fp であることにも特徴を有するものである。【００３６】
さらに、本発明のスカラー倍算プログラムでは、
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 6|(p-1) であり、
前記合成数位数ｒは、 r|#E(Fp), 3|(r-1) を満たし、
前記整数λは、 λ2-λ +1≡0(mod r) を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、    
(x,y) → (εx,-y), ε3=1,ε(≠1)∈Fp であることにも特徴を有するものである。【００３７】
本発明のペアリング演算装置では、
標数ｐの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をE(Fp)とし、合成数位数ｒを持つ有理点の集合すなわち前記加法群の部分群をG1=E(Fp)[r]、G2=E(Fp)[r]として、次式により、
e:G1×G2→F*p/( F*p)r
である非退化な双線形写像としてペアリングeを定義し、
有理点P(xP,yP)∈G1及びQ(xQ,yQ)∈G2、ミラーのアルゴリズムを用いて計算される有理関数をｆとして、ペアリングe(P,Q)を演算するCPU及び記憶手段を備えたペアリング演算装置において、
前記加法群E(Fp)は、埋め込み次数を１とし、
前記CPUは、
有理点P’を前記記憶手段に入力する入力手段と、
前記記憶手段から前記有理点P’を読み出し、自己準同型写像ψにより、
λ1P=ψ(P)、λ２Q=ψ(Q)  （λ1≠λ２は整数）を満足する前記有理点P及びQの集合である前記部分群G1及びG2を特定する有理点部分群特定手段と、
前記記憶手段から前記有理点PまたはQを読み出し、前記自己準同型写像ψ(P) またはψ(Q)を演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算手段と、
前記ｆを演算する第1演算手段と、
所定の有理点を通る直線及び垂線の前記有理点Qにおける値を演算する第2演算手段と、
前記ｆと前記値を用いてf’r,p(Q)を演算する第3演算手段と、
前記f’r,p(Q)を用いて前記ペアリングe(P,Q)を
【数１３】
2012015047.tif 000003
として演算する第4演算手段と
を有することとした。【００３８】
さらに、本発明のペアリング演算装置では、
前記楕円曲線は、 E:y2 = x3 +ax, a∈Fp, 4|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 4|(r-1) を満たし、
前記整数λ1、λ2は、λ12+1≡0(mod r)、λ22+1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (-x,ζy),ζ4=1, ζ,ζ2(≠1)∈Fp  であり、
前記f’r,p(Q)は、
【数１４】
2012015047.tif 000004
であることにも特徴を有するものである。【００３９】
さらに、本発明のペアリング演算装置では、
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 3|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12+λ1+1≡0(mod r)、λ22+λ2 +1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,y), ε3=1, ε(≠1)∈Fp  であり、
前記f’r,p(Q)は、
【数１５】
2012015047.tif 000005
であることにも特徴を有するものである。【００４０】
さらに、本発明のペアリング演算装置では、
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 6|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12-λ1+1≡0(mod r)、λ22-λ2 +1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,-y), ε3=1, ε(≠1)∈Fp  であり、
前記f’r,p(Q)は、
【数１６】
2012015047.tif 000006
であることにも特徴を有するものである。【００４１】
本発明のペアリング演算方法では、
標数ｐの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をE(Fp)とし、合成数位数ｒを持つ有理点の集合すなわち前記加法群の部分群をG1=E(Fp)[r]、G2=E(Fp)[r]として、次式により、
e:G1×G2→F*p/( F*p)r
である非退化な双線形写像としてペアリングeを定義し、
有理点P(xP,yP)∈G1及びQ(xQ,yQ)∈G2、ミラーのアルゴリズムを用いて計算される有理関数をｆとして、CPU及び記憶手段を備えた電子計算機でペアリングe(P,Q)を演算するペアリング演算方法において、
前記加法群E(Fp)は、埋め込み次数を１とし、
前記電子計算機のCPUを入力手段として機能させて、有理点P’を入力し記憶手段に記憶するステップと、
前記電子計算機のCPUを有理点部分群特定手段として機能させて、前記記憶手段から前記有理点P’を読み出し、自己準同型写像ψにより、
λ1P=ψ(P)、λ２Q=ψ(Q)  （λ1≠λ２は整数）を満足する前記有理点P及びQの集合である前記部分群G1及びG2を特定するステップと、
前記電子計算機のCPUを自己準同型写像演算手段として機能させて、前記記憶手段から前記有理点PまたはQを読み出し、前記自己準同型写像ψ(P) またはψ(Q)を演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算ステップと、
前記電子計算機のCPUを第1演算手段として機能させて、前記ｆを演算する第1演算ステップと、
前記電子計算機のCPUを第2演算手段として機能させて、所定の有理点を通る直線及び垂線の前記有理点Qにおける値を演算する第2演算ステップと、
前記電子計算機のCPUを第3演算手段として機能させて、前記ｆと前記値を用いてf’r,p(Q)を演算する第3演算ステップと、
前記電子計算機のCPUを第4演算手段として機能させて、前記f’r,p(Q)を用いて前記ペアリングe(P,Q)を
【数１７】
2012015047.tif 000007
として演算する第4演算ステップと、
を有することとした。【００４２】
さらに本発明のペアリング演算方法では、
前記楕円曲線は、 E:y2 = x3 +ax, a∈Fp, 4|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 4|(r-1) を満たし、
前記整数λ1、λ2は、λ12+1≡0(mod r)、λ22+1≡0(mod r) を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (-x,ζy),ζ4=1, ζ,ζ2(≠1)∈Fp  であり、
前記f’r,p(Q)は、
【数１８】
2012015047.tif 000008
であることにも特徴を有するものである。【００４３】
さらに本発明のペアリング演算方法では、
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 3|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12+λ1+1≡0(mod r)、λ22+λ2 +1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,y),ε3=1,ε(≠1)∈Fp  であり、
前記f’r,p(Q)は、
【数１９】
2012015047.tif 000009
であることにも特徴を有するものである。【００４４】
さらに本発明のペアリング演算方法では、
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 6|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12-λ1+1≡0(mod r)、λ22-λ2 +1≡0(mod r) であり、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,-y),ε3=1,ε(≠1)∈Fp  であり、
前記f’r,p(Q)は、
【数２０】
2012015047.tif 000010
であることにも特徴を有するものである。【００４５】
本発明のペアリング演算プログラムでは、
標数ｐの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をE(Fp)とし、合成数位数ｒを持つ有理点の集合すなわち前記加法群の部分群をG1=E(Fp)[r]、G2=E(Fp)[r]として、次式により、
e:G1×G2→F*p/( F*p)r
である非退化な双線形写像としてペアリングeを定義し、
有理点P(xP,yP)∈G1及びQ(xQ,yQ)∈G2、ミラーのアルゴリズムを用いて計算される有理関数をｆとして、CPU及び記憶手段を備えた電子計算機にペアリングe(P,Q)を演算させるペアリング演算プログラムにおいて、
前記加法群E(Fp)は、埋め込み次数を１とし、
前記電子計算機のCPUを、有理点P’を入力して記憶手段に記憶する入力手段、
前記記憶手段から前記有理点P’を読み出し、自己準同型写像ψにより、
λ1P=ψ(P)、λ２Q=ψ(Q)  （λ1≠λ２は整数）を満足する前記有理点P及びQの集合である前記部分群G1及びG2を特定する有理点部分群特定手段、
前記記憶手段から前記有理点PまたはQを読み出し、前記自己準同型写像ψ(P) またはψ(Q)を演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算手段、
前記ｆを演算する第1演算手段、
所定の有理点を通る直線及び垂線の前記有理点Qにおける値を演算する第2演算手段、
前記ｆと前記値を用いてf’r,p(Q)を演算する第3演算手段、
前記f’r,p(Q)を用いて前記ペアリングe(P,Q)を
【数２１】
2012015047.tif 000011
として演算する第4演算手段、
として機能させることとした。【００４６】
さらに本発明のペアリング演算プログラムでは、
前記楕円曲線は、 E:y2 = x3 +ax, a∈Fp, 4|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 4|(r-1) を満たし、
前記整数λ1、λ2は、λ12+1≡0(mod r)、λ22+1≡0(mod r) であり、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (-x,ζy),ζ4=1, ζ,ζ2(≠1)∈Fp  であり、
前記f’r,p(Q)は、
【数２２】
2012015047.tif 000012
であることにも特徴を有するものである。【００４７】
さらに本発明のペアリング演算プログラムでは、
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 3|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12+λ1+1≡0(mod r)、λ22+λ2 +1≡0(mod r) であり、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,y),ε3=1,ε(≠1)∈Fp   であり、
前記f’r,p(Q)は、
【数２３】
2012015047.tif 000013
であることにも特徴を有するものである。【００４８】
さらに本発明のペアリング演算プログラムでは、
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 6|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12-λ1+1≡0(mod r)、λ22-λ2 +1≡0(mod r) であり、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,-y),ε3=1,ε(≠1)∈Fp  であり、
前記f’r,p(Q)は、
【数２４】
2012015047.tif 000014
であることにも特徴を有するものである。
【発明の効果】
【００４９】
本発明のスカラー倍算によれば、有理点群の埋め込み次数が１の場合において、有理点Pのスカラーｓによるスカラー倍算[s]Pを演算するにあたり、
λP＝ψ(P)  （λは整数）
となる有理点の集合Gを特定して、ｓをλ進展開してs=s0 +s1λとし、
スカラー倍算[s]Pを、
[s]P＝(s0+s1λ)P= s0P +s1ψ(P)
として演算を行うことにより、バイナリー法に比べ、演算量をほぼ半減させることができ、スカラー倍算を高速化することができる。【００５０】
また、本発明のペアリング演算によれば、ペアリング演算において、ミラーのアルゴリズムを用いて計算される有理関数の計算を2回行うこととなるが、前半で求めた値を記憶手段に保持しておき、それらを後半の計算に効率よく用いることにより、Tateペアリングと比べ約30％の効率化を図ることができる。
【図面の簡単な説明】
【００５１】
【図１】本発明の実施形態にかかるスカラー倍算装置またはペアリング演算装置の概略構成を示す模式図である。
【図２】本発明の実施形態にかかるスカラー倍算装置またはペアリング演算装置の全体構成を例示したブロック図である。
【図３】本発明の実施形態にかかる有理点部分群特定部の機能構成を例示した図である。
【図４】本発明の実施形態にかかる有理点部分群特定プログラムのフローチャートである。
【図５】本発明の実施形態にかかるスカラー倍算演算部の機能構成を例示した図である。
【図６】本発明の実施形態にかかるスカラー倍算演算プログラムのフローチャートである。
【図７】本発明の実施形態にかかるペアリング演算部の機能構成を例示した図である。
【図８】本発明の実施形態にかかるペアリング演算プログラムのフローチャートである。
【図９】本発明の実施形態にかかるペアリング演算プログラムのフローチャートである。
【図１０】本発明の実施形態にかかるペアリング演算プログラムのフローチャートである。
【図１１】本発明の実施形態にかかるペアリング演算プログラム（メモリ節約型）のフローチャートである。
【発明を実施するための最良の形態】
【００５２】
本発明の成果を適用できるようなペアリング曲線は、以下のような条件を満たす必要がある。まず、標数ｐの有限体Fp上で定義される楕円曲線を、
E/Fp: y2 = x3 +ax +b, a∈Fp b∈Fpとし、
E(Fp):標数ｐの有限体Fp上で定義される楕円曲線の有理点が成す加法群、
ｒ：E(Fp)の位数#E(Fp)を割り切る合成数、
E[r]：位数が合成数ｒである有理点の集合、
ψ:有理点に対する自己準同型写像、
ｔ：フロベニウス写像のトレース、
[j]：有理点をｊ倍する写像、
G：G=E[r]∩Ker(ψ-λ)、（λは整数）を満たす有理点の集合、と定義する。
また、ｘ｜ｙは、ｘがｙを割り切ることを表わすものとする。【００５３】
楕円曲線の生成にはCM（Complex Multiplication）法が知られている。標数ｐ、フロベニウス写像のトレースｔ、判別式Dによる次式のようなCM方程式において、判別式D=1,3の場合を考える。
4p=t2-Ds2    (1)
この時、ペアリング曲線の式はそれぞれ以下のように与えられる。
Ea: y2 = x3 +ax, a∈Fp   (D=1)   (2a)
Eb: y2 = x3 +b, b∈Fp    (D=3)   (2b)
本発明者らは、大きな合成数位数に対してこのようなペアリング曲線を生成する簡便な生成法を提案済みである。上記のペアリング曲線上の有理点が簡単な自己準同型写像ψ（即ち有理点をP、整数をλとして、ψ(P)=λP）を持つためには、パラメータの条件がある。これには、以下に示すように、自己準同型写像の周期３，４，６に対応して3次、4次、6次の3つの場合がある。この自己準同型写像をスカラー倍算に用いるのがGLV法である。
また、この自己準同型写像をペアリング演算の高速化にも用いる。
以下に、パラメータの条件及びその写像を示す。【００５４】
＜3次の場合＞
楕円曲線のパラメータが、3|(p-1), E: y2 =x3 +b, b∈Fp, D=3の場合、
r|#E(Fp), 3|(r-1)  を満たす合成数ｒに対して、次式を満足するある整数λ3が存在する。
λ32+λ3 +1≡0(mod r)      (3)
また、以下に示す周期３の自己準同型写像ψ３が与えられる。
ψ3:E(Fp)[r] → E(Fp)[r],    (4a)
【数２５】
2012015047.tif 000015
このような合成数ｒを位数として持つ有理点をP∈E(Fp)[r]とすれば、3次の場合は、[λ3]P=ψ3(P)の関係を用いることでスカラー倍算の効率化を図っている。また、後述のペアリング演算の効率化も図っている。【００５５】
具体的には、スカラー倍算の場合、ｒに較べて極めて小さいλ3であれば、これは[λ3]Pというスカラー倍算が簡便な自己準同型写像ψ3(P)で求められる（すなわち、有理点Pのｘ座標値をε倍する演算だけでよい）ことから、スカラーｓをλ3進展開することなどによりこの自己準同型写像を効率よく用いてこれを計算する。【００５６】
しかしながら、有理点群の埋め込み次数が１の場合、一般の有理点P’∈E(Fp)[r]に対しては、[λ3]P’=ψ３(P’)は成り立たない。そのためGLV法は適用することができない。上述したように、これを満たすような有理点の割合は1／ｒ＝1／22000  であり、簡便にそのような有理点及び有理点部分群を準備できる必要がある。【００５７】
本発明では、本発明者らが発見した以下の性質を用いる。
まず、任意の有理点P’∈E(Fp)[r]は次式を満たす。
[(ψ３-λ3)( ψ３ +λ3  +1)]P’=O         (5)
ここで、O  は無限遠点を表わしている。
すなわち、ランダムに生成した有理点P’∈E(Fp)[r]を(ψ３ +λ3  +1)倍し、
P=[ψ３ +λ3  +1]P’                      (6)
とすることにより、その有理点Pは[λ3]P= ψ３(P)を満たすこととなる。そして、そのようなPが生成する有理点部分群をG1  とする。また逆に、
Q=[ψ３ -λ3]P’                   (7)
とすれば、[λ3  +1]Q= -ψ３(Q)を満たす有理点Qとなる。そして、そのようなQが生成する有理点部分群をG2  とする。これらG1、G2 を用いて後述のスカラー倍算及びペアリング演算の高速化を実現することができる。【００５８】
＜関係式の導出法の説明＞
3次の場合の式(5)の導出について以下に説明する。
まず、任意の有理点P’∈E(Fp)[r]は、E(Fp)のフロベニウス写像のトレースｔ及びフロベニウス写像φを用いて、次式を満たすことが知られている。
φ:(x,y)→(xp,yp)
(φ2 -tφ+[p])P’= O        (8)
同様に、P’をE(Fp)と同型な群を内包する拡大体上ツイスト曲線E’(Fp３)に写像した有理点P~を考えれば、E’(Fｐ)のフロベニウス写像のトレースをt’として次式を満たす。
(φ2 -t’φ+[p])P~= O       (9)
ここで、ツイスト曲線は、E’:y2 = x3 +bv-2,b∈Fｐで与えられ、ｖはFｐの３乗非剰余な元であり、P~は、P’=(x,y)として以下で与えられる。
P~ = (xv2/3,yv)           (10)
ここで、上式を写像ψ: P’∈E(Fp)→P~∈E’(Fp3)とすれば、式(9)は次式のように変形できる。
{（ψ-1φ2ψ）-t’(ψ-1φψ）+[p]}P’=O   (11)
そしてこの場合、ψ-1φψ=ψ3が成り立つので次式を得る。
(ψ32 -t’ψ3+[p])P’= O     (12)
上式に対して、有理点群の埋め込み次数が１であることからｐ≡1 (mod r)であり、加えてこれに用いる楕円曲線をt’≡-1(3次)、0(4次)、1(6次) (mod r) となるように生成していることから、P’∈E(Fp)[r] （位数ｒの有理点）とすれば、３次のときには次式を得る。
(ψ32 ＋ψ3+[1])P’= O       (13)
一方で3次の場合には、式(3)を満たすような整数λ3も存在し、すなわちψ32 ＋ψ3+1≡0
(mod r)を、ψ3を変数とするような方程式と考えれば、その解の１つがψ3となる。したがって、式(5)のような因数分解された関係式が得られる。【００５９】
＜4次の場合＞
同様に、楕円曲線のパラメータが、4|(p-1), E: y2=x3 +ax, a∈Fp, D=1の場合、
r|#E(Fp), 4|(r-1)  を満たす合成数ｒに対して、次式を満足するある整数λ4が存在する。        λ42+1≡0(mod r)           (14)
また、以下に示す周期４の自己準同型写像ψ4が与えられる。
ψ4:E(Fp)[r] → E(Fp)[r],    (15a)
【数２６】
2012015047.tif 000016
このような合成数ｒを位数として持つ有理点をP∈E(Fp)[r]とすれば、４次の場合は、[λ4]P=ψ4(P)の関係を用いることでスカラー倍算の効率化を図っている。また、後述のペアリング演算の効率化も図っている。【００６０】
本発明では、本発明者らが発見した以下の性質を用いる。
まず、任意の有理点P’∈E(Fp)[r]は次式を満たす。
[(ψ4-λ4)( ψ4 +λ4)]P’=O        (16)
すなわち、ランダムに生成した有理点P’∈E(Fp)[r]を(ψ4 +λ4  )倍し、
P=[ψ4 +λ4]P’             (17)
とすることにより、その有理点Pは[λ4]P= ψ4(P)を満たすこととなる。そして、そのようなPが生成する有理点部分群をG1  とする。また逆に、
Q=[ψ4 -λ4]P’             (18)
とすれば、[λ4]Q= -ψ4(Q)を満たす有理点Qとなる。そして、そのようなQが生成する有理点部分群をG2  とする。これらG1, G2 を用いて後述のスカラー倍算及びペアリング演算の高速化を実現することができる。【００６１】
4次の場合の式(16)の導出については、3次の場合と同様であるので説明は省略する。【００６２】
＜６次の場合＞
さらに同様に、楕円曲線のパラメータが、6|(p-1), E: y2 =x3 +b, b∈Fp, D=3の場合、
r|#E(Fp), 3|(r-1)  を満たす合成数ｒに対して、次式を満足するλ6が存在する。
λ62-λ6+1≡0(mod r).      (19)
また、以下に示す周期６の自己準同型写像ψ6が与えられる。
ψ6:E(Fp)[r] → E(Fp)[r],    (20a)
【数２７】
2012015047.tif 000017
このような位数ｒを持つ有理点をP∈E(Fp)[r]とし、6次の場合は、[λ6]P=ψ6(P)の関係を用いることでスカラー倍算の効率化を図っている。また、後述のペアリング演算の効率化も図っている。【００６３】
本発明では、本発明者らが発見した以下の性質を用いる。
まず、任意の有理点P’∈E(Fp)[r]は次式を満たす。
[(ψ6-λ6)( ψ6 +λ6-1)]P’=O    (22)
すなわち、ランダムに生成した有理点P’∈E(Fp)[r]を(ψ6 +λ6 -1)倍し、
P=[ψ6 +λ6 -1]P’          (23)
とすることにより、その有理点Pは[λ6]P= ψ6(P)を満たすこととなる。そして、そのようなPが生成する有理点部分群をG1  とする。また逆に、
Q=[ψ6 -λ6]P’             (24)
とすれば、[λ6 -1]Q= -ψ6(Q)を満たす有理点Qとなる。そして、そのようなQが生成する有理点部分群をG2  とする。これらG1、G2 を用いて後述のスカラー倍算及びペアリング演算の高速化を実現することができる。【００６４】
6次の場合の式(22)の導出についても、3次の場合と同様であるので説明は省略する。【００６５】
以下に、本発明のGLV法によるスカラー倍算について説明する。
有理点Pのスカラー0<ｓ<ｒによるスカラー倍算[s]Pは、ｓをλ進展開して、
s=s0+s1λ s0,s1＜λ          (25)
とすると、
[s]P=[ s0+s1λ]P= [s0]P +[s1λ]P=[s0]P +[s1]ψ(P)          (26)
となる。
s0、s1はλより小さく、λはｒに較べてはるかに小さい。またψ(P)は上述したように簡単な計算（有限体上の乗算1回）で求めることができる。従ってｓよりはるかに小さいスカラー値を用いてスカラー倍算を求めることができ、高速化を実現できる。式（26）は複数の有理点のスカラー倍算を求める場合の既存の高速化手法である後述のマルチ・スカラー倍算法（［表１]参照。）により求めることができる。λ２≒ｒであり、s0、s1は、２進数展開したときのビット数が約半分となるので、バイナリー法に比べおおよそ半分の計算時間で求まることとなる。【００６６】
以下において、本発明のスカラー倍算の実施形態について、図を用いて説明する。図１は、本発明の実施形態にかかるスカラー倍算装置の概略模式図である。図２は、本発明の実施形態にかかるスカラー倍算装置の全体構成を例示したブロック図である。まず、図1及び図2を用いてこの形態の全体について説明し、次にその詳細について説明する。なお、本実施形態では、所要の電子計算機で構成された認証サーバによってデジタルグループ署名の認証処理を行う際に、与えられたペアリング曲線から上述した有理点部分群を特定するプログラム、及び一般的にサブルーチン処理として実行されているスカラー倍算演算プログラム部分についてのみ説明する。なお、有理点部分群の特定及びスカラー倍算の演算は、認証サーバで実行される場合に限定されるものではなく、少なくともCPUなどの演算手段及び記憶手段を備えた装置であれば、どのような装置であってもよい。【００６７】
図１に示すように、認証サーバを構成する電子計算機10は、演算処理を実行するCPU 11と有理点部分群特定プログラム、スカラー倍算演算プログラム、ペアリング演算プログラムなどの各種プログラム、及びこれらのプログラムで使用するデータなどを記憶したハードディスクなどの記憶装置12と、これらのプログラムを展開して実行可能とするとともに、これらプログラムの実行にともなって生成されたデータを一時的に記憶するRAMなどで構成されたメモリ装置13を備えている。図１中、14はバスである。【００６８】
また、認証サーバを構成する電子計算機10は、インターネットなどの電気通信回線20に接続して、この電気通信回線20に接続されたクライアント装置30から送信されたデジタルグループ署名の署名データを受信可能としている（図２、認証データ入力部100）。図１中、15は電子計算機10の入出力部である。【００６９】
認証サーバを構成する電子計算機10では、クライアント装置30からデジタルグループ署名の署名データが送信されると、送信された署名データをメモリ装置13に一旦記憶し（認証データ入力部100）、有理点部分群特定プログラムを起動して効率的な自己準同型写像を可能とする有理点部分群を特定(図２、有理点部分群特定部200)した後、ペアリング演算プログラムを起動して、ペアリング演算を実行している(図２、ペアリング演算部300)。
そして、認証サーバを構成する電子計算機10では、ペアリング演算の実行に際して、所要のスカラー倍算の演算が必要となった場合に、スカラー倍算演算プログラムを起動して、スカラー倍算を実行している（図２、スカラー倍算演算部400）。
その後、認証結果を出力している（図２、認証結果出力部500）。【００７０】
次に、本実施形態の詳細について図を用いて説明する。
＜有理点部分群の特定＞【００７１】
図３は図１で示した装置で所定のプログラムを実行させることにより実現される有理点部分群特定部の機能構成を例示した図である。
図４は有理点部分群特定部の処理を行う有理点部分群特定プログラムのフローチャートである。
電子計算機10では、起動した有理点部分群特定プログラムによって、図４に示すフローチャートに基づいて効率的な自己準同型写像を可能とする有理点部分群を特定している。すなわち、入力された、有理点群が埋め込み次数１の一般の有理点を特定の有理点部分群内の有理点に変換している。この場合電子計算機10は有理点部分群特定手段として機能する。以下では、3次GLV法の場合について説明する。【００７２】
ステップ  T1（有理点入力部210）では、外部から与えられ入力手段により記憶手段に記憶された一般の有理点P’を読み出している。
ステップ  T2（定数演算部220）では、あらかじめレジスタに記憶された有限体の標数ｐ及び合成数位数ｒとを用いて、式（３）で示したλ2＋λ＋１≡０ (mod r)となるλ及び、式（４ｂ）で示したε3≡1 (mod p)となるε(≠1)を演算し設定している。
ステップ  T3（自己準同型写像演算部230）では、式（４ｂ）のψ(P’)：(x,y)→(εx,y)として、P’のｘ座標値ｘをε倍し、ψ(P’)を求めている。
ステップ  T4（有理点演算部240）では、式（６）のP=ψ(P’)+(λ+1)P’を計算している。なお、このψ(P’) +(λ+1)P’は2個の有理点スカラー倍算を同時に求める後述の[表１]に基づくアルゴリズムにより求めている。
ステップ  T5（判定部250）では、P=O  (無限遠点)  かどうかを判定している。
P=O  の場合は、2つの部分群を特定できないのでエラー・リターンしている。
ステップ  T6 (有理点演算部240)では、式（７）のQ=ψ(P’)+(-λ)P’を計算している。なお、このψ(P’)+(-λ)P’も2個の有理点のスカラー倍算を同時に求める後述の[表１]に基づくアルゴリズムにより求めている。
ステップ  T7(判定部250)では、Q=O  （無限遠点）かどうかを判定している。
Q=O  の場合は2つの部分群を特定できないのでエラー・リターンしている）。
ステップ T8では、P、Qを記憶手段に記憶している。Pの集合が有理点部分群G1となり、Qの集合が有理点部分群G2となる。【００７３】
本実施形態では、3次GLV法の場合について説明したが、4次GLV法,及び6次GLV法の場合も、λ、ψ(P’)、εまたはζ、P、Qがそれぞれ
4次GLV法では、式(14)：λ2+1≡0 (mod r)、 
式(15b)：ψ(P’):(x,y)→(-x,ζy), (ζ４=1, ζ,ζ2(≠1)∈Fp)、
式(17）：P=ψ(P’) +λP’、
式(18)：Q=ψ(P’) +(-λ)P’
となり、
6次GLV法では、式(19)：λ2-λ+1≡0 (mod r)、 
式(20b)：ψ(P’):(x,y)→(εx,-y), (ε3=1, ε(≠1)∈Fp)、
式(23)：P=ψ(P’) +(λ-1)P’、 
式(24)：Q=ψ(P’) +(-λ)P’
となるだけであり、同様に有理点部分群を特定することができる（説明は省略する。）。【００７４】
＜スカラー倍算演算プログラム＞
図５は図１で示した装置で所定のプログラムを実行させることにより実現されるスカラー倍算演算部の機能構成を例示した図である。図６はスカラー倍算演算部の処理を行うスカラー倍算演算プログラムのフローチャートである。
電子計算機10では、起動したスカラー倍算演算プログラムによって、図６に示すフローチャートに基づいてスカラー倍算の演算を行い、演算結果を記憶手段に記憶すると共に、メインルーチンのプログラムに返している。以下では、3次GLV法の場合について説明する。【００７５】
起動したスカラー倍算演算プログラムによって、電子計算機10では、ペアリング演算部300より、スカラーｓのデータ及び、有理点Pのデータ、を入力して、CPU11の内部に設けている所定のレジスタ490にそれぞれ入力している（パラメータ入力部410）（ステップ  S1）。【００７６】
次いで、電子計算機10では、スカラー倍算演算プログラムによってCPU11を定数演算手段として機能させて、あらかじめレジスタ490に格納されている合成数位数ｒ及び有限体の標数ｐを用いて、式(3)で示したλ2＋λ+1≡0 (mod r)  となるλ及び式(4b)で示したε3≡1 (mod p)  となるε(≠1)を演算しそれぞれ設定している(定数演算部420)（ステップS2）。【００７７】
次いで、電子計算機10では、スカラー倍算演算プログラムによってCPU11を自己準同型写像演算手段として機能させて、式(4b)で示したP(x,y)→ψ(P)(εx,y)を演算している。すなわち、Pのｘ座標値をε倍して新たな有理点を求めている（自己準同型写像演算部430）(ステップ S3)。【００７８】
次いで、電子計算機10では、スカラー倍算演算プログラムによってCPU11をλ進展開手段として機能させて、スカラーｓをλ進展開して、式(25)で示した
s=s0+s1λ (mod r)
となる係数s0、s1を演算している（λ進展開部440）（ステップ  S4）。
具体的には、s0=s%λ, s1=(s - s0)/λとしている。（％は、剰余演算子、／は除算演算子。）【００７９】
次いで、電子計算機10では、スカラー倍算演算プログラムによってCPU11をスカラー倍算演算手段として機能させて、式(26)で示した
[s]P=(s0+s1λ)P= s0P+s1λP=s0P+s1ψ(P)としてスカラー倍算[s]Pの演算を行っている（マルチ・スカラー倍算演算部450）（ステップ  S5）。
このs0P+s1ψ(P)の演算は、二つの有理点のスカラー倍算の演算を同時に求めるマルチ・スカラー倍算として以下の[表１]のアルゴリズムに基づいて行っている。【００８０】
[表１]マルチ・スカラー倍算アルゴリズム
Input: w, k=(kt-1,...,k1,k0)2, l=(lt-1,...,l1,l0)2  , P,Q.
Output: kP +lQ.
(1) Compute iP+jQ for all i,j∈[0,2w-1].
(2) Write k=(kd-1,...,k1,k0) and l=(ld-1,...,l1,l0) , d=[t/w].
(3) R←O.
(4) For i from d-1 down to 0 do
(4.1) R←2wR.
(4.2) R←R+(kiP +liQ).
(5) Return(R).  
この場合、このアルゴリズムにおける入力パラメータのｋはs0、lはs１、Pは入力した有理点P、Qは有理点ψ(P)となる。ｗはウインドー巾である。  kｊ、lｊ はｋ、ｌを2進展開した時の各係数、ki、li  はｋ、ｌを２ｗ進展開した時の各係数である。全体でｄ個となる。
ステップ１では、ウインドー巾までの有理点P,Qの全てのスカラー倍算の組合せについて、事前に計算しておきテーブル化して記憶手段に記憶している。
ステップ２では、各ki、liを求めている。
ステップ３では、求めるべき有理点の変数Rを初期化している。
ステップ４では、以下の４．１及び４．２のステップをiがｄ−１から０まで繰り返している。
ステップ４．１では、Rをウインドー巾倍すなわち楕円２乗算をｗ回行っている。
ステップ４．２では、ステップ１で作成したテーブルを参照してkiP+liQの値をRに楕円加算している。
ステップ５では、Rを戻り値としてリターンしている。【００８１】
このとき、スカラーｓが2000ビットであった場合にはs0及びs1は1000  ビットとなるため、バイナリー法に比べ、演算量を半減させることができ、スカラー倍算を高速化することができる。【００８２】
演算後、電子計算機10では、演算結果をメモリ装置13に記憶するとともにメインルーチンのプログラムに返している。【００８３】
本実施形態では、3次GLV法の場合について説明したが、4次GLV法,及び6次GLV法の場合も、λ及びψ(P)と、εまたはζがそれぞれ、
4次GLVでは、式(14)：λ2+1≡0 (mod r)、
式(15b)：ψ(P):(x,y)→(-x,ζy), (ζ４≡1 (mod p))
となり、
6次GLVでは、式（19）：λ2-λ+1≡0 (mod r)、
式(20b)：ψ(P):(x,y)→(εx,-y), (ε3≡1( mod p))
となるだけであり、同様に演算することができる(説明は省略する。)。【００８４】
以上説明したように、本実施形態の有理点部分群特定手段である有理点部分群特定部200では、有理点入力部210において、有理点群の埋め込み次数が１であるFp上の一般の有理点P’∈ Fp[r]を入力し、定数演算部220において、あらかじめレジスタ290に格納された合成数位数ｒ及び標数ｐを用いて、式(3)に示すλ2 +λ+1≡0 (mod r)  及び式(4b)に示すε3≡1 (mod p)を演算し、自己準同型写像演算部230において自己準同型写像ψ(P’)を演算し、有理点演算部240において有理点P及びQを演算して、有理点部分群を特定している。このようにすることにより、これら有理点部分群の1つを用いてスカラー倍算の演算を高速に行うことができる。【００８５】
また、本実施形態のスカラー倍算演算部400では、入力手段であるパラメータ入力部410において、スカラー値ｓ及び有理点Pを入力し、定数演算部420において、あらかじめレジスタ490に格納された合成数位数ｒ及び標数ｐを用いて、式(3)に示すλ2 +λ+1≡0 (mod r)  及び式(4b)に示すε3≡1 (mod p)を演算し、自己準同型写像演算手段である自己準同型演算部430において自己準同型写像ψ(P)を演算し、λ進展開手段であるλ進展開部440においてスカラーｓをλ進展開し、マルチ・スカラー倍算演算手段であるマルチ・スカラー倍算演算部450において、スカラー倍算[ｓ]Pを演算している。このようにすることにより有理点群が埋め込み次数１である有理点のスカラー倍算を高速に実行することができる。【００８６】
なお、本発明のスカラー倍算は、上述の実施形態に限定されるものではない。例えば、マルチ・スカラー倍算演算部では、既存の手法であるJSF(Joint  Sparse  Form)を用いて演算してもよい。【００８７】
また、有理点群特定プログラム及びスカラー倍算演算プログラムはコンピュータで読み取り可能な記録媒体に記録することができる。また、これらのプログラムをサーバのコンピュータの記憶装置に記憶しておき、ネットワークを介して電子計算機の記憶装置にダウンロードすることもできる。【００８８】
以下に本発明のペアリング演算について説明する。
本発明のペアリング演算では、ペアリング演算におけるミラーのアルゴリズムを用いて有理関数を演算する第1のステップと、その結果に対してべき乗算を行う第2のステップのうち、第1のステップにおいて、上記整数λ及び自己準同型写像ψ(P)を用いて有理関数を演算することにより、演算の高速化を図っているものである。【００８９】
すなわち、従来のペアリング演算では、曲線の式がy2=x3+ax+b,a∈Fp, b∈Fpで与えられ、Fp上の素数位数ｒを持つ有理点の集合をE[r]とし、埋め込み次数がｋでFpkを定義体とするペアリング可能な楕円曲線上の有理点の成す加法群をE(Fpk)、φｐをフロベニウス自己準同型写像として、
G1=E[r],
G2=E(Fpk)
により、
e:G1×G2→F*pk/( F*pk)r
である非退化な双線形写像としてペアリングeを定義し、有理点P(xP,yP)∈G1及びQ(xQ,yQ)∈G2、ミラーのアルゴリズムを用いて計算される有理関数fr,P(Q)を用いて、ペアリングe(P,Q)を、
【数２８】
2012015047.tif 000018
として演算していた。これらは、Tateペアリングとして知られているものである。【００９０】
これに対して、本発明者らは、有理点群の埋め込み次数が１の場合において、有理点部分群G1、G2を特定し、その特性により有理関数fr,P(Q)の計算を例えば、4次の場合、以下のように行うこととした。
【数２９】
2012015047.tif 000019
まず、fλ_4,P(Q)を計算する。この計算の過程で得られる途中のデータを記憶手段に記憶する。続いてfλ_4,ψ4(P)(Q)を計算する際に先の計算とψ4(P)のみが異なること、加えてそれが簡単な写像ψ4を仲介して与えられていることから、先に記憶しておいた計算結果を活用することができ、加えて、その計算の初期値としてfλ_4,P(Q)の計算結果を使うことにより、残りのλ4乗算（べき乗算）も併せて済ませることができる。これにより、おおよそ30％の効率化が図れる。【００９１】
3次の場合も同様に、 
【数３０】
2012015047.tif 000020
として計算する。【００９２】
さらに、6次の場合も同様に、
【数３１】
2012015047.tif 000021
として計算する。【００９３】
以下において、本発明のペアリング演算の実施形態について、図を用いて説明する。
図1は、本発明の実施形態にかかるペアリング演算装置の概略構成を示す模式図である。
図2は、本発明の実施形態にかかるペアリング演算装置の全体構成を例示したブロック図である。
図1及び図2については、スカラー倍算の場合と同様であるので説明は省略する。【００９４】
次に、本実施形態の詳細について図を用いて説明する。
＜有理点部分群の特定＞【００９５】
図３は図１で示した装置で所定のプログラムを実行させることにより実現される有理点部分群特定部の機能構成を例示した図である。
図４は有理点部分群特定部の処理を行う有理点部分群特定プログラムのフローチャートである。
図3及び図4についてもスカラー倍算の場合と同様であるので説明は省略する。
＜ペアリング演算プログラム＞【００９６】
図７は、図1で示した装置で所定のプログラムを実行させることにより実現されるペアリング演算部の機能構成を例示した図である。
図８は、ペアリング演算部の処理を行うペアリング演算プログラムのフローチャートである。以下では4次の場合について説明する。【００９７】
起動したペアリング演算プロラムによって、電子計算機10では、CPU  11を入力手段として機能させて、メモリ装置13にあらかじめ記憶されている整数λ1=λ４のデータと、有理点Pのデータ、及び署名データとしてメモリ装置13に一旦記憶された有理点QのデータをCPUの内部に設けている所定のレジスタにそれぞれ入力している（パラメータ入力部）（ステップS1）。【００９８】
次いで、有理関数fλ_4,P(Q)の変数f1,h1を初期化すなわちf1=１、h1=1としている。（ステップS2）【００９９】
次いで、電子計算機10では、ペアリング演算プログラムによってCPU  11を
第1演算手段として機能させて、ミラーのアルゴリズムによって有理関数
fλ_4,P(Q)を演算しその演算結果をメモリ装置13に記憶している。（ステップS3）。【０１００】
この有理関数fλ_4,P(Q)は、具体的には図９に示すように実行している。
特にステップS2では、有理関数fλ_4,P(Q)の演算とともにT1の中間結果を楕円２倍算、楕円加算に分けてメモリ装置13に記憶している。【０１０１】
まず、初期設定としてT1←Pとするとともに整数λを２進数表示とした場合のビット数をiとしている（ステップS31）。【０１０２】
次いで、ステップS32では、CPU  11を第２演算手段として機能させて直線及び垂線における値を求め、有理関数fλ_4,P(Q)の楕円２倍算に伴う所定の演算を行っている。ここで、有理関数を求めるにはf1/h1が必要であるが、都度の除算を避けてf1、h1のままとしている。【０１０３】
次いで、T1の中間結果を配列Cdbl[i]に記憶するとともに有理点変数T1の楕円２倍算を行いT1に代入している。（ステップS33）。【０１０４】
次いで、ステップS34では、整数λ4の低次から数えてi番目のビットの値λ4iが「１」かであるか「０」であるかを判定し、λ4i=1の場合には、ステップS35で、有理関数fλ_4,P(Q)の楕円加算に伴う所定の演算を行っている。ここでも都度の除算を避けてｆ1、ｈ1のままとしている。ステップS36で、T1の中間結果を配列Cadd[i]に記憶するとともに有理点変数T1の有理点Pとの楕円加算を行いT1に代入している。【０１０５】
次いで、λ4i≠1の場合、iのデクリメントを行って(ステップS38)、ステップS32に戻り、ステップS37でi=1になるまで繰り返すことにより、有理関数fλ_4,P(Q)を演算しその結果であるf1、h1をメモリ装置13にそれぞれ記憶している。【０１０６】
次いで、有理関数fλ_4,P(Q)の変数f1,h1をメモリ装置13から読み出し初期化している。すなわち、ステップS3での結果をステップS5の初期値としている。（ステップS4）。【０１０７】
次いで、電子計算機10では、ペアリング演算プログラムによってCPU  11を
第1演算手段として機能させて、ミラーのアルゴリズムによって有理関数
fλ_4,ψ4(P)(Q)を演算しその演算結果をメモリ装置13に記憶している。（ステップS5）。【０１０８】
この有理関数fλ_4,ψ4(P)(Q)は、具体的には図１０に示すように実行している。【０１０９】
まず、初期設定として、整数λ4を２進数表示とした場合のビット数をiとしている（ステップS51）【０１１０】
ステップS52では、配列Cdbl[i]を記憶装置13から読み出し、CPU  11を自己準同型写像手段として機能させて、ψ４（Cdbl[i]）を求め、その結果をT1に代入している。【０１１１】
次いで、ステップS53では、CPU  11を第２演算手段として機能させて直線及び垂線における値を求め、有理関数fλ_4,P(Q)の楕円２倍算に伴う所定の演算を行っている。ここで、有理関数を求めるにはf1/h1が必要であるが、都度の除算を避けてf1,h1のままとしている。【０１１２】
次いで、ステップS54では、整数λ4の低次から数えてi番目のビットの値λ4iが「１」かであるか「０」であるかを判定し、λ4i=1の場合には、ステップS55でメモリ装置13から配列Cadd[i]を読み出し、CPU  11を自己準同型写像手段として機能させて、ψ４（Cadd[i]）を求め、その結果をT1に代入している。ステップS56では、CPU  11を第２演算手段として機能させて直線及び垂線における値を求め、有理関数fλ_4,P(Q)の楕円加算に伴う所定の演算を行っている。ここでも都度の除算を避けてｆ1、ｈ1のままとしている。【０１１３】
次いで、λ4i≠1の場合、iのデクリメントを行って(ステップS58)、ステップS52に戻り、ステップS57でi=1になるまで繰り返すことにより、有理関数fλ_4,ψ4(P)(Q)を演算している。【０１１４】
次いで、ステップS59では、f1/h1を行いf1に代入している。ループの中で除算を実行することなく、1度の除算で済ませている。次いで、f1・(xQ- xP)を計算しf’r,P(Q)の値を求め、f1に代入し、その結果をメモリ装置13に記憶している。【０１１５】
具体的には、記号の意味を次の通りとして、
λ4i :λ4を2進表記した際の低次からi番目のビット
lT1,T1(Q):有理点T1での接線における有理点Qの値
（表示の制限上、下付き文字は正しくはT1であるがT1としている。以下も同じ。）
lT1,P(Q) :有理点T1と有理点Pを通る直線における有理点Qの値
v2T1(Q) :有理点２T1での垂線における有理点Qの値
vT1+P(Q) :有理点T1＋Pでの垂線における有理点Qの値
Cdbl[i] :繰り返し回数がi番目の２倍算２T1を格納するための配列(メモリ)
Cadd[i] :繰り返し回数がi番目の加算T1＋Pを格納するための配列(メモリ)
以下のアルゴリズムを実行している。
［表２］ミラーのアルゴリズム１(4次の場合：スピード重視型)
入力:λ4, P∈G1, Q∈G2
出力：f’r,P(Q)
1. f1←1, f2←1, h1←1, h2←1, T1←P
2. For i=[log2(λ4)] down to 1 do:
3. f1←f12・lT1,T1(Q).
4. h1←h12・v2T1(Q).
5. Cdbl[i] ←T1.
6. T1 ←2T1.
7. if λ4i=1, then:
8. f1←f1・lT1,P(Q).
9. h1←h1・vT1+P(Q).
10. Cadd[i] ←T1.
11. T1←T1+P.
12. T1←P.
13. f2←f1.
14. h2←h1.
15. For i=[log2(λ4)] down to 1 do:
16. T1←ψ4(Cdbl[i]).
17. f1←f12・lT1,T1(Q).
18. h1←h12・v2T1(Q).
19. if λ4i=1, then:
20. T1←ψ4(Cadd[i]).
21. f1←f1・f2・lT1,P(Q).
22. h1←h1・h2・vT1+P(Q).
23. f1←f1/h1.
24. f1←f1・(xQ-xP).
25. Return f1.
すなわち、CPU  11は、メモリ装置13を用いて上記手順の各演算を行いｆ‘r,P(Q)を得てその値をメモリ装置13に記憶している。具体的には、手順１では、有理関数変数f1,f2,h1,h2を１に、有理点変数T1を有理点Pに初期設定している。手順2では、変数iを整数λ４を2進数展開した時のビット数に初期設定し、手順３から手順11までを繰り返している。手順3及び4では有理関数の演算を直線及び垂線に分けて行っている。有理関数の値を求めるにはf1/h1が必要であるが除算の回数を減らすためループの中では除算を行わないようにしている。手順5では、中間結果のT1を配列Cdbl[i]に代入している。手順6では、有理点T1の楕円２倍算を行いT1に代入している。手順７では、整数λ4の低次からi番目のビットが「１」か「０」かを判定し「１」の場合に手順８から11を実行している。手順8及び9では有理関数の演算を直線及び垂線に分けて行っている。有理関数の値を求めるにはf1/h1が必要であるが除算の回数を減らすためループの中では除算を行わないようにしている。手順10では、有理点変数T1の中間結果を配列Cadd[i]に代入している。手順11では、有理点変数T1と有理点Pを楕円加算しその値をT1に代入している。
手順12では有理点変数T1を有理点Pに初期設定している。手順13,14では、前半の結果をf2,h2に代入している。手順15では、変数iを、整数λ４を2進数展開した時のビット数に初期設定し、手順16から手順22までを繰り返している。手順16では、配列Cdbl[i]をメモリ装置13から読み出し自己準同型写像を行い、その値を有理点変数T1に代入している。手順17,18では、有理関数の演算を直線及び垂線に分けて行っている。有理関数の値を求めるにはf1/h1が必要であるが除算の回数を減らすためループの中では除算を行わないようにしている。手順19では、整数λ4の低次からi番目のビットが「１」か「０」かを判定し「１」の場合に手順20から22を実行している。手順20では、配列Cadd[i]をメモリ装置13から読み出し自己準同型写像を行い、その値を有理点変数T1に代入している。手順21及び22では、有理関数の演算を直線及び垂線に分けて行うと共にそれぞれf2 、h2を賭け合わせることによりλ4乗を実現している。手順23,24では最終的な有理関数の値f’r,P(Q)を求めf1に代入している。【０１１６】
次いで、電子計算機10では、ペアリング演算プログラムによってCPU  11を第４演算手段として機能させて、ステップS５で得られたf’r,P(Q)の値をメモリ装置13から読み出し、ペアリングe(P,Q)における最終べきの、べき乗算を行いその結果をメモリ装置13に記憶している（ステップS6）。【０１１７】
具体的には、
［表３］最終べきのアルゴリズム
1. a←p-1
2. a←a・r-1
3. f’←f’a 
4. Return f’
として演算し、f’すなわちe(P,Q)の値をメモリ装置13に記憶している。【０１１８】
認証サーバを構成する電子計算機10では、上述したようにして得られたペアリングの演算結果を用いて認証処理を行っている。【０１１９】
以上、4次の場合のペアリング演算について、図８及び表２では、前半のミラー・アルゴリズムの計算の結果を求める際に得られた中間結果をメモリ装置13に記憶しておき後半のミラー・アルゴリズムの計算に活用することによりペアリング演算を高速に実行することとしているが、メモリ容量を節約して実行することもできる。図１１及び表４は、その場合のフローチャート及びアルゴリズムである。記号の意味は、表２の場合と同じなので説明は省略する。
［表４］ミラーのアルゴリズム２（4次：メモリ節約型）
入力:λ4, P∈G1, Q∈G2
出力：f’r,P(Q)
1. f1←1, f2←1, h1←1, h2←1, T1←P
2. For i=[log2(λ4)] down to 1 do:
3. f1←f12・lT1,T1(Q).
4. h1←h12・v2T1(Q).
5. T2←ψ4(T1).
6. f2←f22・lT2,T2(Q).
7. h2←h22・v2T2(Q).
8. T1←2T1.
9. If λ4i=1, then :
10. f1←f1・lT1,P(Q).
11. h1←h1・vT1+P(Q).
12. T2←ψ4(T1).
13. f2←f2・lT2,P(Q).
14. h2←h2・vT2+P(Q).
15. T1←T1+P.
16. f1←f1λ_4.
17. h1←h1λ_4. 
18. f1←(f1・f2)/(h1・h2).
19. f1←f1・(xQ-xP).
20. Return f1.
すなわち、手順１では、有理関数変数f1,f2,h1,h2を１に、有理点変数T1を有理点Pに初期設定している。手順2では、変数iを整数λ４を2進数展開した時のビット数に初期設定し、手順３から手順15までを繰り返している。手順3及び4では、第2演算手段を用いて、楕円２倍算にともなう有理関数の演算を直線及び垂線に分けて行っている。有理関数の値を求めるにはf1/h1が必要であるが除算の回数を減らすためループの中では除算を行わないようにしている。手順5では、自己準同型写像演算手段により、有理点T1を変換しT2に代入している。手順6及び7では、第2演算手段を用いて、楕円加算にともなう有理関数の演算を直線及び垂線に分けて行っている。有理関数の値を求めるにはf2/h2が必要であるが除算の回数を減らすためループの中では除算を行わないようにしている。手順8では、有理点T1の楕円２倍算を行いT1に代入している。手順９では、整数λ4の低次からi番目のビットが「１」か「０」かを判定し「１」の場合に手順10から15を実行している。手順10及び11では、T1について有理関数の演算を直線及び垂線に分けて行っている。有理関数の値を求めるにはf1/h1が必要であるが除算の回数を減らすためループの中では除算を行わないようにしている。手順12では、自己準同型写像演算手段により、有理点T1を変換しT2に代入している。手順13及び14では、第2演算手段を用いて、楕円加算にともなう有理関数の演算を直線及び垂線に分けて行っている。有理関数の値を求めるにはf2/h2が必要であるが除算の回数を減らすためループの中では除算を行わないようにしている。手順１5では、有理点変数T1と有理点Pを楕円加算しその値をT1に代入している。手順16及び17では、f1及びh1のλ4乗算を行っている。
手順18及び19では最終的な有理関数の値f’r,P(Q)を求めf1に代入している。除算は、手順18の1回だけで済ませている。【０１２０】
以上、本実施形態では、4次の場合について説明したが、3次及び6次の場合でも同様のアルゴリズムでペアリング演算を高速に演算できる。
以下に、3次の場合のアルゴリズムを示す。記号の意味は、表２の場合と同様なので説明は省略する。
［表５］ミラーのアルゴリズム３(３次の場合：スピード重視型)
入力:λ3, P∈G1, Q∈G2
出力：f’r,P(Q)
1. f1←1, f2←1, h1←1, h2←1, T1←P.
2. For i=[log2(λ3)] down to 1 do:
3. f1←f12・lT1,T1(Q).
4. h1←h12・v2T1(Q).
5. Cdbl[i] ←T1.
6. T1 ←2T1.
7. if λ3i=1, then:
8. f1←f1・lT1,P(Q).
9. h1←h1・vT1+P(Q).
10. Cadd[i] ←T1.
11. T1←T1+P.
12. T1←P.
13. f2←f1.
14. f3←f1 /h1.
15. h2←h1.
16. For i=[log2(λ3)] down to 1 do:
17. T1←ψ3(Cdbl[i]).
18. f1←f12・lT1,T1(Q).
19. h1←h12・v2T1(Q).
20. if λ3i=1, then:
21. T1←ψ3(Cadd[i]).
22. f1←f1・f2・lT1,P(Q).
23. h1←h1・h2・vT1+P(Q).
24. f1←f1・lT1,ψ3(P)(Q).
25. f1←f1 /h1.
26. f1←f1・f3.
27. Return f1.
3次の場合のアルゴリズムは、4次の場合と同様であるので、異なる部分のみ説明する。
手順14では、前半の結果をｆ３に代入し、手順26でλ３＋１乗を得ている。手順24では、補正項lT1,ψ3(P)(Q)を掛け合わせている。【０１２１】
以下に、６次の場合のアルゴリズムを示す。記号の意味は、表２の場合と同様なので説明は省略する。
［表６］ミラーのアルゴリズム４(６次の場合：スピード重視型)
入力:λ6, P∈G1, Q∈G2
出力：f’r,P(Q)
1. f1←1, f2←1, h1←1, h2←1, T1←P.
2. For i=[log2(λ6-1)] down to 1 do:
3. f1←f12・lT1,T1(Q).
4. h1←h12・v2T1(Q).
5. Cdbl[i] ←T1.
6. T1 ←2T1.
7. if λ6i=1, then:
8. f1←f1・lT1,P(Q).
9. h1←h1・vT1+P(Q).
10. Cadd[i] ←T1.
11. T1←T1+P.
12. T1←P.
13. f1←f1・lT1,P(Q).
14. h1←h1・vT1+P(Q).
15. f2←f1.
16. h2←h1.
17. For i=[log2(λ6-1)] down to 1 do:
18. T1←ψ6(Cdbl[i]).
19. f1←f12・lT1,T1(Q).
20. h1←h12・v2T1(Q).
21. if λ6i=1, then:
22. T1←ψ6(Cadd[i]).
23. f1←f1・f2・lT1,P(Q).
24. h1←h1・h2・vT1+P(Q).
25. f1←f1 /h1.
26. f1←f1・(xQ-xP).
27. Return f1.
6次の場合のアルゴリズムも4次の場合と同様であるので異なる部分のみ説明する。
手順２及び17の繰り返し回数はλ６−１回としている。手順13、14では補正項を掛け合わせている。【０１２２】
なお、上述においては、各演算結果を記憶する記憶手段としてメモリ装置13を用いることとしたがCPU  11の内部に設けているレジスタを上記記憶手段として用いるようにしてもよい。【０１２３】
また、有理点群特定プログラム及びペアリング演算プログラムはコンピュータで読み取り可能な記録媒体に記録することができる。また、これらのプログラムをサーバのコンピュータの記憶装置に記憶しておき、ネットワークを介して電子計算機の記憶装置にダウンロードすることもできる。
【符号の説明】
【０１２４】
10  電子計算機
11  CPU
12  記憶装置
13  メモリ装置
14  バス
15  入出力制御部
20  電気通信回線
30  クライアント装置
100  認証データ入力部
200  有理点部分群特定部
300  ペアリング演算部
400  スカラー倍算演算部
500  認証結果出力部
210  有理点入力部
220  定数演算部
230  自己準同型演算部
240  有理点演算部
250  判定部
290  レジスタ
310  パラメータ入力部
320  第3演算部
330  第1演算部
340  第2演算部
350  自己準同型写像演算部
360  第4演算部
380  記憶手段
390  レジスタ
410  パラメータ入力部
420  定数演算部
430  自己準同型写像演算部
440  マルチ・スカラー倍算演算部
490  レジスタ
【図１】
2012015047.tif 000034
【図２】
2012015047.tif 000035
【図３】
2012015047.tif 000036
【図４】
2012015047.tif 000037
【図５】
2012015047.tif 000038
【図６】
2012015047.tif 000039
【図７】
2012015047.tif 000040
【図８】
2012015047.tif 000041
【図９】
2012015047.tif 000042
【図１０】
2012015047.tif 000043
【図１１】
2012015047.tif 000044
【国際調査報告】
2012015047.tif 000045
2012015047.tif 000046
2012015047.tif 000047
2012015047.tif 000048