(57)【特許請求の範囲】
【請求項１】
ｑを素数のべき乗、Ｆqを要素数ｑの有限体、Ｆq^5を有限体Ｆqの5次拡大体、Ｆq^10を有限体Ｆqの10次拡大体として、入力値Ｘ（該入力値Ｘは、Ｆq^10の要素であり且つトーラスＴ2(Fq^5)の要素である。）を（ｑ＋１）乗した値Ｙを計算する、べき乗計算装置であって、
前記入力値Ｘを、5個のＦqの要素からなり且つＦq^5の要素である第１の部分Ｘ０と、5個のＦqの要素からなり且つＦq^5の要素である第２の部分Ｘ１との二つに分割する分割部と、
前記第１の部分Ｘ０に含まれる前記5個のＦqの要素をもとに、基礎体上の乗算を実行して、複数の乗算値からなる第１の乗算結果を求めるとともに、前記第２の部分Ｘ１に含まれる前記5個のＦqの要素をもとに、基礎体上の乗算を実行して、複数の乗算値からなる第２の乗算結果を求める第１の計算部と、
前記入力値を（ｑ＋１）乗した値Ｙを、5個のＦqの要素からなり且つＦq^5の要素である第３の部分Ｙ０と、5個のＦqの要素からなり且つＦq^5の要素である第４の部分Ｙ１との二つに分割した場合における、該第３の部分Ｙ０を、前記第１の乗算結果に含まれる前記複数の乗算値及び前記第２の乗算結果に含まれる前記複数の乗算値に基づく線形加算を実行することによって算出する第２の計算部と、
前記第４の部分Ｙ１を、前記第１の部分及び前記第２の部分に基づくＦq^5の要素同士の乗算により算出する第３の計算部と、
前記入力値を（ｑ＋１）乗した値Ｙを得るために、前記第３の部分Ｙ０と前記第４の部分Ｙ１とを結合する結合部とを備え、
前記第１の計算部が実行する前記基礎体上の乗算は、前記第３の部分Ｙ０の算出に必要になる複数の基礎体上の乗算から、前記入力値ＸがトーラスＴ2（Ｆq^5）の要素であることから成立する数式Ｘ^（q^5＋１）＝１に基づき他の乗算で置き換え可能になる乗算を省いたものであり、
前記第１の計算部が実行する前記基礎体上の乗算は、前記数式Ｘ^（q^５＋１）＝１に基づき前記入力値Ｘに含まれる１０個の値の組（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）の間に成立する５個の関係式から導き出される、ｘ１２＋ｘ６２が他の乗算で置き換え可能になることを示す関係式、ｘ３２＋ｘ８２が他の乗算で置き換え可能になることを示す関係式及びｘ５２＋ｘ１０２が他の乗算で置き換え可能になることを示す関係式に基づいて、前記第３の部分Ｙ０の算出に必要になる複数の基礎体上の乗算から、ｘ１２、ｘ６２、ｘ３２、ｘ８２、ｘ５２及びｘ１０２の乗算を省いたものであることを特徴とするべき乗計算装置。
【請求項２】
ｑを素数のべき乗、Ｆqを要素数ｑの有限体、Ｆq^5を有限体Ｆqの5次拡大体、Ｆq^10を有限体Ｆqの10次拡大体として、入力値Ｘ（該入力値Ｘは、Ｆq^10の要素であり且つトーラスＴ2(Fq^5)の要素である。）を（ｑ＋１）乗した値Ｙを計算する、べき乗計算装置であって、
前記入力値Ｘを、5個のＦqの要素からなり且つＦq^5の要素である第１の部分Ｘ０と、5個のＦqの要素からなり且つＦq^5の要素である第２の部分Ｘ１との二つに分割する分割部と、
前記第１の部分Ｘ０に含まれる前記5個のＦqの要素をもとに、基礎体上の乗算を実行して、複数の乗算値からなる第１の乗算結果を求めるとともに、前記第２の部分Ｘ１に含まれる前記5個のＦqの要素をもとに、基礎体上の乗算を実行して、複数の乗算値からなる第２の乗算結果を求める第１の計算部と、
前記入力値を（ｑ＋１）乗した値Ｙを、5個のＦqの要素からなり且つＦq^5の要素である第３の部分Ｙ０と、5個のＦqの要素からなり且つＦq^5の要素である第４の部分Ｙ１との二つに分割した場合における、該第３の部分Ｙ０を、前記第１の乗算結果に含まれる前記複数の乗算値及び前記第２の乗算結果に含まれる前記複数の乗算値に基づく線形加算を実行することによって算出する第２の計算部と、
前記第４の部分Ｙ１を、前記第１の部分及び前記第２の部分に基づくＦq^5の要素同士の乗算により算出する第３の計算部と、
前記入力値を（ｑ＋１）乗した値Ｙを得るために、前記第３の部分Ｙ０と前記第４の部分Ｙ１とを結合する結合部とを備え、
前記第１の計算部が実行する前記基礎体上の乗算は、前記第３の部分Ｙ０の算出に必要になる複数の基礎体上の乗算から、前記入力値ＸがトーラスＴ2（Ｆq^5）の要素であることから成立する数式Ｘ^（q^5＋１）＝１に基づき他の乗算で置き換え可能になる乗算を省いたものであり、
前記第１の計算部が実行する前記基礎体上の乗算は、前記数式Ｘ^（q^５＋１）＝１に基づき前記入力値Ｘに含まれる１０個の値の組（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）の間に成立する５個の関係式から導き出される、ｘ１２＋ｘ６２が他の乗算で置き換え可能になることを示す関係式に基づいて、ｘ１２及びｘ６２の乗算を他の乗算で置き換えることによって省く第１の置き換えと、該５個の関係式から導き出される、ｘ３２＋ｘ８２が他の乗算で置き換え可能になることを示す関係式に基づいて、ｘ３２及びｘ８２の乗算を他の乗算で置き換えることによって省く第２の置き換えと、該５個の関係式から導き出される、ｘ５２＋ｘ１０２が他の乗算で置き換え可能になることを示す関係式に基づいて、ｘ５２及びｘ１０２の乗算を他の乗算で置き換えることによって省く第３の置き換えとのうちの少なくとも一つの置き換えがなされたものであることを特徴とするべき乗計算装置。
【請求項３】
ζを１の原始１１乗根、σを−１の平方根として、１０次拡大体Ｆq^10の法多項式が、σ２＝−１，ζ１０＋ζ９＋ζ８＋ζ７＋ζ６＋ζ５＋ζ４＋ζ３＋ζ２＋ζ＋１＝０と設定され、１０次拡大体Ｆq^10の基底が、｛（ζ＋ζ１０），（ζ２＋ζ９），（ζ３＋ζ８），（ζ４＋ζ７），（ζ５＋ζ６），（ζ＋ζ１０）σ，（ζ２＋ζ９）σ，（ζ３＋ζ８）σ，（ζ４＋ζ７）σ，（ζ５＋ζ６）σ｝と設定されたことを特徴とする請求項１または２に記載のべき乗計算装置。
【請求項４】
前記法多項式及び基底は、Ｆq^5の要素をｑ乗した値が、５次拡大体Ｆq^5の要素の入れ替えにより求められるようにするものであり、
前記第３の部分Ｙ０は、Ｆq^5の要素である前記第１の部分Ｘ０とＦq^5の要素である前記第２の部分Ｘ１とを用いて、Ｙ０＝Ｘ０ｑ・Ｘ０＋Ｘ１ｑ・Ｘ１により求められるものであり、
前記第２の計算部は、Ｘ０をｑ乗する代わりにＸ０の要素を入れ替えることによってＸ０ｑを求めるとともに、Ｘ１をｑ乗する代わりにＸ１の要素を入れ替えることによってＸ１ｑを求めるものであることを特徴とする請求項３に記載のべき乗計算装置。
【請求項５】
前記入力値Ｘに含まれる１０個の値の組を（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）として、前記分割部は、該入力値Ｘを、第１の部分Ｘ０＝（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５）と第２の部分Ｘ１＝（ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）に分割し、
前記第１の計算部は、前記第１の部分Ｘ０＝（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５）について、ｘ１ｘ２、ｘ１ｘ３、ｘ１ｘ４、ｘ１ｘ５、ｘ２ｘ２、ｘ２ｘ３、ｘ２ｘ４、ｘ２ｘ５、ｘ３ｘ４、ｘ３ｘ５、ｘ４ｘ４、ｘ４ｘ５を計算し、前記第２の部分Ｘ１＝（ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）について、ｘ６ｘ７、ｘ６ｘ８、ｘ６ｘ９、ｘ６ｘ１０、ｘ７ｘ７、ｘ７ｘ８、ｘ７ｘ９、ｘ７ｘ１０、ｘ８ｘ９、ｘ８ｘ１０、ｘ９ｘ９、ｘ９ｘ１０を計算することを特徴とする請求項３または４に記載のべき乗計算装置。
【請求項６】
前記法多項式及び前記基底を記憶する記憶手段を更に備えたことを特徴とする請求項３ないし５のいずれか１項に記載のべき乗計算装置。
【請求項７】
前記第３の計算部は、
前記第４の部分Ｙ１を算出するもととなる値を得るために、前記第１の部分Ｘ０に含まれる前記5個のＦqの要素及び前記第２の部分Ｘ１に含まれる前記5個のＦqの要素に基づく乗算を実行して、複数の乗算結果を得る第４の計算部と、
前記複数の乗算結果をもとにして、前記第４の部分Ｙ１を算出する第５の計算部とを含むことを特徴とする請求項１ないし６のいずれか1項に記載のべき乗計算装置。
【請求項８】
ｑを素数のべき乗、Ｆqを要素数ｑの有限体、Ｆq^5を有限体Ｆqの5次拡大体、Ｆq^10を有限体Ｆqの１０次拡大体として、入力値Ｘ（該入力値Ｘは、Ｆq^10の要素であり且つトーラスＴ2(Fq^5)の要素である。）を（ｑ＋１）乗した値Ｙを計算する、べき乗計算装置のべき乗計算方法であって、
前記べき乗計算装置の備える分割部が、前記入力値Ｘを、5個のＦqの要素からなり且つＦq^5の要素である第１の部分Ｘ０と、5個のＦqの要素からなり且つＦq^5の要素である第２の部分Ｘ１との二つに分割するステップと、
前記べき乗計算装置の備える第１の計算部が、前記第１の部分Ｘ０に含まれる前記5個のＦqの要素をもとに、基礎体上の乗算を実行して、複数の乗算値からなる第１の乗算結果を求めるとともに、前記第２の部分Ｘ１に含まれる前記5個のＦqの要素をもとに、基礎体上の乗算を実行して、複数の乗算値からなる第２の乗算結果を求めるステップと、
前記べき乗計算装置の備える第２の計算部が、前記入力値を（ｑ＋１）乗した値Ｙを、5個のＦqの要素からなり且つＦq^5の要素である第３の部分Ｙ０と、5個のＦqの要素からなり且つＦq^5の要素である第４の部分Ｙ１との二つに分割した場合における、該第３の部分Ｙ０を、前記第１の乗算結果に含まれる前記複数の乗算値及び前記第２の乗算結果に含まれる前記複数の乗算値に基づく線形加算を実行することによって算出するステップと、
前記べき乗計算装置の備える第３の計算部が、前記第４の部分Ｙ１を、前記第１の部分及び前記第２の部分に基づくＦq^5の要素同士の乗算により算出するステップと、
前記べき乗計算装置の備える結合部が、前記入力値を（ｑ＋１）乗した値Ｙを得るために、前記第３の部分Ｙ０と前記第４の部分Ｙ１とを結合するステップとを有し、
前記第１の計算部が実行する前記基礎体上の乗算は、前記第３の部分Ｙ０の算出に必要になる複数の基礎体上の乗算から、前記入力値ＸがトーラスＴ2（Ｆq^5）の要素であることから成立する数式Ｘ^（q^5＋１）＝１に基づき他の乗算で置き換え可能になる乗算を省いたものであり、
前記第１の計算部が実行する前記基礎体上の乗算は、前記数式Ｘ^（q^５＋１）＝１に基づき前記入力値Ｘに含まれる１０個の値の組（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）の間に成立する５個の関係式から導き出される、ｘ１２＋ｘ６２が他の乗算で置き換え可能になることを示す関係式、ｘ３２＋ｘ８２が他の乗算で置き換え可能になることを示す関係式及びｘ５２＋ｘ１０２が他の乗算で置き換え可能になることを示す関係式に基づいて、前記第３の部分Ｙ０の算出に必要になる複数の基礎体上の乗算から、ｘ１２、ｘ６２、ｘ３２、ｘ８２、ｘ５２及びｘ１０２の乗算を省いたものであることを特徴とするべき乗計算方法。
【請求項９】
ｑを素数のべき乗、Ｆqを要素数ｑの有限体、Ｆq^5を有限体Ｆqの5次拡大体、Ｆq^10を有限体Ｆqの１０次拡大体として、入力値Ｘ（該入力値Ｘは、Ｆq^10の要素であり且つトーラスＴ2(Fq^5)の要素である。）を（ｑ＋１）乗した値Ｙを計算する、べき乗計算装置のべき乗計算方法であって、
前記べき乗計算装置の備える分割部が、前記入力値Ｘを、5個のＦqの要素からなり且つＦq^5の要素である第１の部分Ｘ０と、5個のＦqの要素からなり且つＦq^5の要素である第２の部分Ｘ１との二つに分割するステップと、
前記べき乗計算装置の備える第１の計算部が、前記第１の部分Ｘ０に含まれる前記5個のＦqの要素をもとに、基礎体上の乗算を実行して、複数の乗算値からなる第１の乗算結果を求めるとともに、前記第２の部分Ｘ１に含まれる前記5個のＦqの要素をもとに、基礎体上の乗算を実行して、複数の乗算値からなる第２の乗算結果を求めるステップと、
前記べき乗計算装置の備える第２の計算部が、前記入力値を（ｑ＋１）乗した値Ｙを、5個のＦqの要素からなり且つＦq^5の要素である第３の部分Ｙ０と、5個のＦqの要素からなり且つＦq^5の要素である第４の部分Ｙ１との二つに分割した場合における、該第３の部分Ｙ０を、前記第１の乗算結果に含まれる前記複数の乗算値及び前記第２の乗算結果に含まれる前記複数の乗算値に基づく線形加算を実行することによって算出するステップと、
前記べき乗計算装置の備える第３の計算部が、前記第４の部分Ｙ１を、前記第１の部分及び前記第２の部分に基づくＦq^5の要素同士の乗算により算出するステップと、
前記べき乗計算装置の備える結合部が、前記入力値を（ｑ＋１）乗した値Ｙを得るために、前記第３の部分Ｙ０と前記第４の部分Ｙ１とを結合するステップとを有し、
前記第１の計算部が実行する前記基礎体上の乗算は、前記第３の部分Ｙ０の算出に必要になる複数の基礎体上の乗算から、前記入力値ＸがトーラスＴ2（Ｆq^5）の要素であることから成立する数式Ｘ^（q^5＋１）＝１に基づき他の乗算で置き換え可能になる乗算を省いたものであり、
前記第１の計算部が実行する前記基礎体上の乗算は、前記数式Ｘ^（q^５＋１）＝１に基づき前記入力値Ｘに含まれる１０個の値の組（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）の間に成立する５個の関係式から導き出される、ｘ１２＋ｘ６２が他の乗算で置き換え可能になることを示す関係式に基づいて、ｘ１２及びｘ６２の乗算を他の乗算で置き換えることによって省く第１の置き換えと、該５個の関係式から導き出される、ｘ３２＋ｘ８２が他の乗算で置き換え可能になることを示す関係式に基づいて、ｘ３２及びｘ８２の乗算を他の乗算で置き換えることによって省く第２の置き換えと、該５個の関係式から導き出される、ｘ５２＋ｘ１０２が他の乗算で置き換え可能になることを示す関係式に基づいて、ｘ５２及びｘ１０２の乗算を他の乗算で置き換えることによって省く第３の置き換えとのうちの少なくとも一つの置き換えがなされたものであることを特徴とするべき乗計算方法。
【請求項１０】
ｑを素数のべき乗、Ｆqを要素数ｑの有限体、Ｆq^5を有限体Ｆqの5次拡大体、Ｆq^10を有限体Ｆqの１０次拡大体として、入力値Ｘ（該入力値Ｘは、Ｆq^10の要素であり且つトーラスＴ2(Fq^5)の要素である。）を（ｑ＋１）乗した値Ｙを計算する、べき乗計算装置としてコンピュータを機能させるためのプログラムであって、
前記入力値Ｘを、5個のＦqの要素からなり且つＦq^5の要素である第１の部分Ｘ０と、5個のＦqの要素からなり且つＦq^5の要素である第２の部分Ｘ１との二つに分割する分割部と、
前記第１の部分Ｘ０に含まれる前記5個のＦqの要素をもとに、基礎体上の乗算を実行して、複数の乗算値からなる第１の乗算結果を求めるとともに、前記第２の部分Ｘ１に含まれる前記5個のＦqの要素をもとに、基礎体上の乗算を実行して、複数の乗算値からなる第２の乗算結果を求める第１の計算部と、
前記入力値を（ｑ＋１）乗した値Ｙを、5個のＦqの要素からなり且つＦq^5の要素である第３の部分Ｙ０と、5個のＦqの要素からなり且つＦq^5の要素である第４の部分Ｙ１との二つに分割した場合における、該第３の部分Ｙ０を、前記第１の乗算結果に含まれる前記複数の乗算値及び前記第２の乗算結果に含まれる前記複数の乗算値に基づく線形加算を実行することによって算出する第２の計算部と、
前記第４の部分Ｙ１を、前記第１の部分及び前記第２の部分に基づくＦq^5の要素同士の乗算により算出する第３の計算部と、
前記入力値を（ｑ＋１）乗した値Ｙを得るために、前記第３の部分Ｙ０と前記第４の部分Ｙ１とを結合する結合部とをコンピュータに機能させるためのものであるとともに、
前記第１の計算部が実行する前記基礎体上の乗算は、前記第３の部分Ｙ０の算出に必要になる複数の基礎体上の乗算から、前記入力値ＸがトーラスＴ2（Ｆq^5）の要素であることから成立する数式Ｘ^（q^5＋１）＝１に基づき他の乗算で置き換え可能になる乗算を省いたものであり、
前記第１の計算部が実行する前記基礎体上の乗算は、前記数式Ｘ^（q^５＋１）＝１に基づき前記入力値Ｘに含まれる１０個の値の組（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）の間に成立する５個の関係式から導き出される、ｘ１２＋ｘ６２が他の乗算で置き換え可能になることを示す関係式、ｘ３２＋ｘ８２が他の乗算で置き換え可能になることを示す関係式及びｘ５２＋ｘ１０２が他の乗算で置き換え可能になることを示す関係式に基づいて、前記第３の部分Ｙ０の算出に必要になる複数の基礎体上の乗算から、ｘ１２、ｘ６２、ｘ３２、ｘ８２、ｘ５２及びｘ１０２の乗算を省いたものであることを特徴とするプログラム。
【請求項１１】
ｑを素数のべき乗、Ｆqを要素数ｑの有限体、Ｆq^5を有限体Ｆqの5次拡大体、Ｆq^10を有限体Ｆqの１０次拡大体として、入力値Ｘ（該入力値Ｘは、Ｆq^10の要素であり且つトーラスＴ2(Fq^5)の要素である。）を（ｑ＋１）乗した値Ｙを計算する、べき乗計算装置としてコンピュータを機能させるためのプログラムであって、
前記入力値Ｘを、5個のＦqの要素からなり且つＦq^5の要素である第１の部分Ｘ０と、5個のＦqの要素からなり且つＦq^5の要素である第２の部分Ｘ１との二つに分割する分割部と、
前記第１の部分Ｘ０に含まれる前記5個のＦqの要素をもとに、基礎体上の乗算を実行して、複数の乗算値からなる第１の乗算結果を求めるとともに、前記第２の部分Ｘ１に含まれる前記5個のＦqの要素をもとに、基礎体上の乗算を実行して、複数の乗算値からなる第２の乗算結果を求める第１の計算部と、
前記入力値を（ｑ＋１）乗した値Ｙを、5個のＦqの要素からなり且つＦq^5の要素である第３の部分Ｙ０と、5個のＦqの要素からなり且つＦq^5の要素である第４の部分Ｙ１との二つに分割した場合における、該第３の部分Ｙ０を、前記第１の乗算結果に含まれる前記複数の乗算値及び前記第２の乗算結果に含まれる前記複数の乗算値に基づく線形加算を実行することによって算出する第２の計算部と、
前記第４の部分Ｙ１を、前記第１の部分及び前記第２の部分に基づくＦq^5の要素同士の乗算により算出する第３の計算部と、
前記入力値を（ｑ＋１）乗した値Ｙを得るために、前記第３の部分Ｙ０と前記第４の部分Ｙ１とを結合する結合部とをコンピュータに機能させるためのものであるとともに、
前記第１の計算部が実行する前記基礎体上の乗算は、前記第３の部分Ｙ０の算出に必要になる複数の基礎体上の乗算から、前記入力値ＸがトーラスＴ2（Ｆq^5）の要素であることから成立する数式Ｘ^（q^5＋１）＝１に基づき他の乗算で置き換え可能になる乗算を省いたものであり、
前記第１の計算部が実行する前記基礎体上の乗算は、前記数式Ｘ^（q^５＋１）＝１に基づき前記入力値Ｘに含まれる１０個の値の組（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）の間に成立する５個の関係式から導き出される、ｘ１２＋ｘ６２が他の乗算で置き換え可能になることを示す関係式に基づいて、ｘ１２及びｘ６２の乗算を他の乗算で置き換えることによって省く第１の置き換えと、該５個の関係式から導き出される、ｘ３２＋ｘ８２が他の乗算で置き換え可能になることを示す関係式に基づいて、ｘ３２及びｘ８２の乗算を他の乗算で置き換えることによって省く第２の置き換えと、該５個の関係式から導き出される、ｘ５２＋ｘ１０２が他の乗算で置き換え可能になることを示す関係式に基づいて、ｘ５２及びｘ１０２の乗算を他の乗算で置き換えることによって省く第３の置き換えとのうちの少なくとも一つの置き換えがなされたものであることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、べき乗計算装置、べき乗計算方法及びプログラムに関する。
【背景技術】
【０００２】
昨今、ペアリングの有用性を利用した暗号プロトコル（例えば、ＩＤベース暗号、ショート署名など）が提案されている。大きな埋め込み次数ｋの楕円曲線を用いたペアリングは、安全性の観点において有効であり、例えば、ｋ＝２×ｒ（ｒは奇素数）なる楕円曲線の構成法が、提案されている（非特許文献１参照）。
【０００３】
ペアリングには幾つかのアルゴリズムが知られているが、例えば、有限体上のＴａｔｅペアリングは、数式（１）のような写像である。  
＜P，Q＞ｍ：Ｅ（Ｆq）[m]×Ｅ（Ｆq^k）/mＥ（Ｆq^k）→Ｆ＊q^k／（Ｆ＊q^k）ｍ 
…（１）  
qは、素数ｐのべき乗、Ｆqは、元がq個の有限体、Ｅ（Ｆq）は、有限体Ｆq上で定義される楕円曲線、mは、qと互いに素で且つm｜＃Ｅ（Ｆq）を満たす正整数、ｋは、埋め込み次数と呼ばれ、m｜（q^k−１）を満たす最小の正整数である。＃Ｅは、楕円曲線Ｅの点の個数（曲線の位数）を示す。ａ｜ｂは、ａがｂの約数であることを示す。
【０００４】
有限体上のＴａｔｅペアリングは、楕円曲線Ｅ（Ｆq）上のＦq有理点Pと、楕円曲線Ｅ（Ｆq^k）上のＦq^k有理点Ｑを入力し、Ｆq^k上の要素を出力する写像である。
【０００５】
一般に、ペアリング計算の手順は、  
［第１段階］曖昧さを含んだペアリングの計算（Millerアルゴリズム等）、  
［第２段階］曖昧さの除去  
の２ステップからなる。  
上記第１段階で得られる値は、有限体Ｆq^kの要素であるが、曖昧さを含んだ表現であるため、暗号プロトコルでの使用には適さない。そこで、第２段階において、上記第１段階で得られる値から、曖昧さを除去する。
【０００６】
以下、第１段階の計算を、「ペアリング中間値計算」と呼び、ペアリング中間値計算により得られる値を、「ペアリング中間値」と呼ぶものとする。また、第２段階の計算は、「最終べき」と呼ばれる。最終べきにより得られる値が、求めるべき「ペアリング値」である。
【０００７】
ペアリング計算を高速化するためには、ペアリング中間値計算と最終べきの両方を高速化する必要がある。ペアリング中間値計算については、これまでに大幅に高速化されてきた。最終べきの高速化については、例えば、ｒ＝３（ｋ＝６）としたときの最終べきに対する高速化手法が、提案されている（非特許文献２参照）。しかし、最終べきについては、それほど、高速化の手法が知られていない。
【０００８】
ここで、最終べきとは、有限体Ｆq^kの要素で表現されたペアリング中間値が、位数ｍの巡回群の要素として一意となるように、該ペアリング中間値を（q^k−１）／ｍ乗する操作である。
【０００９】
例えば、非特許文献２においては、ｒ＝３の場合、位数ｍの巡回群は、トーラスＴ6（Ｆq）の部分群となっているので、トーラスＴ6（Ｆq）の要素として一意となるように、ペアリング値を（q^3−１）（ｑ＋１）乗した後に、さらに、この結果を（q^2−q+1）／ｍ乗する手順が記載されている。
【００１０】
上記手順において、（q^3−１）乗した段階で、計算結果は、トーラスＴ2（Ｆq^3）の一意な表現となるので、トーラスＴ2（Ｆq^3）の要素である性質を用いて、残りの（ｑ＋１）乗を計算することによって、高速化が図られる。具体的には、入力される６個の数の組の間に在る３個の関係式を用いて、計算中の或る乗算を、他の乗算で置き換えることにより、（ｑ＋１）乗算中の乗算の回数を減らしている。
【００１１】
同文献において、乗算の回数の減らし方の戦略は不明であるが、同文献によれば、１８回から９回に減らすことにより２倍の高速化となっている。
【非特許文献１】D. Freeman, M. Scott, E. Teske, “A taxonomy of pairing-friendly elliptic curves”, IACR ePrint Archive 2006/372
【非特許文献２】白勢、高木、岡本「ηＴペアリングの最終べきについて」情報通信学会研究報告ＩＳＥＣ２００６−９８
【発明の開示】
【発明が解決しようとする課題】
【００１２】
従来、ペアリング計算における最終べきを高速化する手法は、ｒ＝３（ｋ＝６）とした場合の手法しか知られていなかった。
【００１３】
本発明は、上記事情を考慮してなされたもので、埋め込み次数ｋ＝２×ｒ（ｒは奇素数）におけるｒが５以上の場合にも、ペアリング計算における最終べきを高速化することができる、べき乗計算装置、べき乗計算方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明は、ｑを素数のべき乗、Ｆqを要素数ｑの有限体、Ｆq^5を有限体Ｆqの5次拡大体、Ｆq^10を有限体Ｆqの10次拡大体として、入力値Ｘ（該入力値Ｘは、Ｆq^10の要素であり且つトーラスＴ2(Fq^5)の要素である。）を（ｑ＋１）乗した値Ｙを計算する、べき乗計算装置であって、前記入力値Ｘを、5個のＦqの要素からなり且つＦq^5の要素である第１の部分Ｘ０と、5個のＦqの要素からなり且つＦq^5の要素である第２の部分Ｘ１との二つに分割する分割部と、前記第１の部分Ｘ０に含まれる前記5個のＦqの要素をもとに、基礎体上の乗算を実行して、複数の乗算値からなる第１の乗算結果を求めるとともに、前記第２の部分Ｘ１に含まれる前記5個のＦqの要素をもとに、基礎体上の乗算を実行して、複数の乗算値からなる第２の乗算結果を求める第１の計算部と、前記入力値を（ｑ＋１）乗した値Ｙを、5個のＦqの要素からなり且つＦq^5の要素である第３の部分Ｙ０と、5個のＦqの要素からなり且つＦq^5の要素である第４の部分Ｙ１との二つに分割した場合における、該第３の部分Ｙ０を、前記第１の乗算結果に含まれる前記複数の乗算値及び前記第２の乗算結果に含まれる前記複数の乗算値に基づく線形加算を実行することによって算出する第２の計算部と、前記第４の部分Ｙ１を、前記第１の部分及び前記第２の部分に基づくＦq^5の要素同士の乗算により算出する第３の計算部と、前記入力値を（ｑ＋１）乗した値Ｙを得るために、前記第３の部分Ｙ０と前記第４の部分Ｙ１とを結合する結合部とを備え、前記第１の計算部が実行する前記基礎体上の乗算は、前記第３の部分Ｙ０の算出に必要になる複数の基礎体上の乗算から、前記入力値ＸがトーラスＴ2（Ｆq^5）の要素であることから成立する数式Ｘ^（q^5＋１）＝１に基づき他の乗算で置き換え可能になる乗算を省いたものであり、前記第１の計算部が実行する前記基礎体上の乗算は、前記数式Ｘ^（q^５＋１）＝１に基づき前記入力値Ｘに含まれる１０個の値の組（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）の間に成立する５個の関係式から導き出される、ｘ１２＋ｘ６２が他の乗算で置き換え可能になることを示す関係式、ｘ３２＋ｘ８２が他の乗算で置き換え可能になることを示す関係式及びｘ５２＋ｘ１０２が他の乗算で置き換え可能になることを示
す関係式に基づいて、前記第３の部分Ｙ０の算出に必要になる複数の基礎体上の乗算から、ｘ１２、ｘ６２、ｘ３２、ｘ８２、ｘ５２及びｘ１０２の乗算を省いたものであることを特徴とする。  
また、本発明は、ｑを素数のべき乗、Ｆqを要素数ｑの有限体、Ｆq^5を有限体Ｆqの5次拡大体、Ｆq^10を有限体Ｆqの10次拡大体として、入力値Ｘ（該入力値Ｘは、Ｆq^10の要素であり且つトーラスＴ2(Fq^5)の要素である。）を（ｑ＋１）乗した値Ｙを計算する、べき乗計算装置であって、前記入力値Ｘを、5個のＦqの要素からなり且つＦq^5の要素である第１の部分Ｘ０と、5個のＦqの要素からなり且つＦq^5の要素である第２の部分Ｘ１との二つに分割する分割部と、前記第１の部分Ｘ０に含まれる前記5個のＦqの要素をもとに、基礎体上の乗算を実行して、複数の乗算値からなる第１の乗算結果を求めるとともに、前記第２の部分Ｘ１に含まれる前記5個のＦqの要素をもとに、基礎体上の乗算を実行して、複数の乗算値からなる第２の乗算結果を求める第１の計算部と、前記入力値を（ｑ＋１）乗した値Ｙを、5個のＦqの要素からなり且つＦq^5の要素である第３の部分Ｙ０と、5個のＦqの要素からなり且つＦq^5の要素である第４の部分Ｙ１との二つに分割した場合における、該第３の部分Ｙ０を、前記第１の乗算結果に含まれる前記複数の乗算値及び前記第２の乗算結果に含まれる前記複数の乗算値に基づく線形加算を実行することによって算出する第２の計算部と、前記第４の部分Ｙ１を、前記第１の部分及び前記第２の部分に基づくＦq^5の要素同士の乗算により算出する第３の計算部と、前記入力値を（ｑ＋１）乗した値Ｙを得るために、前記第３の部分Ｙ０と前記第４の部分Ｙ１とを結合する結合部とを備え、前記第１の計算部が実行する前記基礎体上の乗算は、前記第３の部分Ｙ０の算出に必要になる複数の基礎体上の乗算から、前記入力値ＸがトーラスＴ2（Ｆq^5）の要素であることから成立する数式Ｘ^（q^5＋１）＝１に基づき他の乗算で置き換え可能になる乗算を省いたものであり、前記第１の計算部が実行する前記基礎体上の乗算は、前記数式Ｘ^（q^５＋１）＝１に基づき前記入力値Ｘに含まれる１０個の値の組（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）の間に成立する５個の関係式から導き出される、ｘ１２＋ｘ６２が他の乗算で置き換え可能になることを示す関係式に基づいて、ｘ１２及びｘ６２の乗算を他の乗算で置き換えることによって省く第１の置き換えと、該５個の関係式から導き出される、ｘ３２＋ｘ８２が他の乗算で置き換え可能になることを示す関係式に基づいて、ｘ３２及びｘ８２の乗算を他の乗算で置き換えることによって省く第２の置き換えと、該５個の関係式から導き出される、ｘ５２＋ｘ１０２が他の乗算で置き換え可能になることを示す関係式に基づいて、ｘ５２及びｘ１０２の乗算を他の乗算で置き換えることによって省く第３の置き換えとのうちの少なくとも一つの置き換えがなされたものであることを特徴とする。
【発明の効果】
【００１５】
本発明によれば、埋め込み次数ｋ＝２×ｒ（ｒは奇素数）におけるｒが５以上の場合にも、ペアリング計算における最終べきを高速化することが可能になる。
【発明を実施するための最良の形態】
【００１６】
以下、図面を参照しながら本発明の実施形態について説明する。
【００１７】
（第1の実施形態）
本発明の第１の実施形態に係るペアリング計算装置について説明する。
【００１８】
本実施形態は、ペアリング計算の第２段階にあたる「最終べき」のうちの、（ｑ＋１）乗を高速化するものである。
【００１９】
なお、以下では、具体例としては、埋め込み次数ｋ＝２×ｒ（ｒは奇素数）におけるｒを５とする場合（すなわち、ｋ＝１０とする場合）を例にとって説明する。
【００２０】
図１に、本発明の第１の実施形態に係るペアリング計算装置の機能ブロックの構成例を示す。図１に示されるように、ペアリング計算装置１は、ペアリング中間値計算部１００、最終べき計算部２００を備える。
【００２１】
なお、ペアリング計算に必要なパラメータは、適宜の方法で設定されるものとして構わない。
【００２２】
図２に、図１の最終べき計算部２００の機能ブロックの構成例を示す。図２に示されるように、最終べき計算部２００は、（q^r−１）乗計算部２０１、（ｑ＋１）乗計算部２０２、Φ2r（ｑ）／ｍ乗計算部２０３を含む。ここで、Φｎ（ｑ）は、ｎ次の円分多項式である。
【００２３】
なお、ペアリング計算装置１の内部構成は、最終べき計算部２００内にある（ｑ＋１）乗計算部２０２（特に、後述するＹ０事前計算及びＹ０計算）に係る部分を除いて、基本的には、従来の構成と同様で構わない。
【００２４】
図３に、ペアリング計算装置の処理手順の一例を示す。
【００２５】
ペアリング中間値計算部１００は、２入力（Ｐ，Ｑ）に対して、１つのペアリング中間値ｅ（Ｐ，Ｑ）を計算して出力する（ステップＳ１）。ペアリング中間値の計算には、既存のアルゴリズム（例えば、Millerアルゴリズム等）を用いて構わない。ペアリング中間値計算部１００の入力は、有限体Ｆq上で定義される楕円曲線Ｅ（Ｆq）上のＦq有理点Pと、楕円曲線Ｅ（Ｆq^2r）上のＦq^2r有理点Ｑであり、出力ｅ（Ｐ，Ｑ）は、２ｒ次拡大体（Ｆq^2r）の要素である。例えば、ｒ＝５とする場合、ペアリング中間値計算部１００の出力は、１０次拡大体（Ｆq^10）の要素である。
【００２６】
最終べき計算部２００は、ペアリング中間値計算部１００で算出されたペアリング中間値を入力し、該ペアリング中間値に対して、最終べきを実行する。最終べき計算部２００は、最終べきの計算結果を、ペアリング値として出力する。
【００２７】
最終べき計算部２００の（q^r−１）乗計算部２０１は、入力される２ｒ次拡大体の要素（図２の構成例では、ペアリング中間値計算部１００が算出したペアリング中間値）を、（q^r−１）乗する（ステップＳ２）。（q^r−１）乗の計算結果も、２ｒ次拡大体の要素である。
【００２８】
（ｑ＋１）乗計算部２０２は、入力される２ｒ次拡大体の要素（図２の構成例では、(q^r−１)乗計算部２０１の計算結果）を、（ｑ＋１）乗する（ステップＳ３）。（ｑ＋１）乗の計算結果も、２ｒ次拡大体の要素である。
【００２９】
Φ2r（ｑ）／ｍ乗計算部２０３は、入力される２ｒ次拡大体の要素（図２の構成例では、（ｑ＋１）乗計算部２０２の計算結果）を、Φ2r（ｑ）／ｍ乗する（ステップＳ４）。Φ2r（ｑ）／ｍ乗の計算結果も、２ｒ次拡大体の要素である。
【００３０】
前述したように、ペアリング中間値の計算結果は、ペアリングとしての性質は満たすが、曖昧さを含んだ表現であるため、暗号プロトコルでの使用には適さない。
【００３１】
最終べきは、有限体Ｆq^2rの要素で表現されたペアリング中間値が、位数ｍの巡回群の要素として一意となるように、該ペアリング中間値を（q^k−１）／ｍ乗する操作である。これによって、ペアリング中間値から曖昧さが除去され、暗号プロトコルでの使用が可能になる。
【００３２】
本実施形態では、図２及び図３に示すように、最終べきとして、（q^r−１）乗と（ｑ＋１）乗とΦ2r（ｑ）／ｍ乗の計算が行われる。
【００３３】
有限体Ｆq^2rの要素であるペアリング中間値に対して、（q^r−１）乗を施すことによって、その計算結果は、トーラスＴ2(Fq^r)の一意な表現となる。更に、その計算結果に対して、（ｑ＋１）乗を施すことによって、計算結果は、トーラスＴ２ｒ（Ｆq）の一意な表現となる。
【００３４】
例えば、ｒ＝５の場合には、１０次拡大体（Ｆq^10）の要素であるペアリング中間値を、（q^5−１）乗することによって、その計算結果は、トーラスＴ2（Ｆq^5）の一意な表現となり、更に、その計算結果を（ｑ＋１）乗することによって、計算結果は、トーラスＴ10（Ｆq）の一意な表現となる。
【００３５】
本実施形態の最終べきでは、（q^r−１）乗を（ｑ＋１）乗よりも先にし、（q^r−１）乗の計算結果が、トーラスＴ2(Fq^r)の一意な表現となる性質を利用して、（ｑ＋１）乗の計算を高速化する。
【００３６】
なお、上記のように、（ｑ＋１）乗の前に（q^r−１）乗を実行する必要があるが、Φ2r（ｑ）／ｍ乗の実行の順番は任意である。よって、  
図２及び図３の例のように、（q^r−１）乗、（ｑ＋１）乗、Φ2r（ｑ）／ｍ乗の順で実行する代わりに、  
（q^r−１）乗、Φ2r（ｑ）／ｍ乗、（ｑ＋１）乗の順で実行してもよいし、
Φ2r（ｑ）／ｍ乗、（ｑ^r−１）乗、（ｑ＋１）乗の順で実行してもよい。
【００３７】
これに応じて、図２の構成例を変形することが可能である。すなわち、Φ2r（ｑ）／ｍ乗計算部２０３は、（ｑ＋１）乗計算部２０２の直前に置かれてもよいし、（q^r−１）乗計算部２０１の直前に置かれてもよい。
【００３８】
また、図２の構成例では、（q^r−１）乗計算部２０１とΦ2r（ｑ）／ｍ乗計算部２０３とを独立して設けたが、（q^r−１）乗計算部２０１とΦ2r（ｑ）／ｍ乗計算部２０３とを合体させた一つの乗計算部（（q^r−１）Φ2r（ｑ）／ｍ乗計算部）として設けてもよい。
【００３９】
さて、以下では、本実施形態の（ｑ＋１）乗計算部についてより詳しく説明する。
【００４０】
図４に、図２の（ｑ＋１）乗計算部２０２の機能ブロックの構成例を示す。図４に示されるように、（ｑ＋１）乗計算部２０２は、分割部２２１、Ｙ０事前計算部２２２、Ｙ１事前計算部２２３、Ｙ０計算部２２４、Ｙ１計算部２２５、結合部２２６を含む。
【００４１】
また、図５に、（ｑ＋１）乗計算部２０２の処理手順の一例を示す。
【００４２】
ここで、ｒ＝５とすると、（ｑ＋１）乗計算部２０２への入出力は、１０（＝２×ｒ）次拡大体の要素である。
【００４３】
ｒ＝５とした場合に（ｑ＋１）乗計算部２０２へ入力される１０（＝２×ｒ）個の数の組Ｘを、  
Ｘ＝（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）  
で表し、（ｑ＋１）乗計算部２０２から出力される１０（＝２×ｒ）個の数の組Ｙを、  
Ｙ＝（ｙ１，ｙ２，ｙ３，ｙ４，ｙ５，ｙ６，ｙ７，ｙ８，ｙ９，ｙ１０）  
で表すものとする。  
また、Ｘ０＝（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５）、Ｘ１＝（ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）、Ｙ０＝（ｙ１，ｙ２，ｙ３，ｙ４，ｙ５）、Ｙ１＝（ｙ６，ｙ７，ｙ８，ｙ９，ｙ１０）で表すものとする。これらは、５次拡大体の要素である。
【００４４】
分割部２２１は、２ｒ次拡大体の要素Ｘが入力されると、これを、ｒ次拡大体の要素Ｘ０とｒ次拡大体の要素Ｘ１の二つに分割する（ステップＳ１１）。
【００４５】
例えば、ｒ＝５の場合、分割部２２１は、１０次拡大体の要素Ｘ＝（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）が入力されると、これを、５次拡大体の二つの要素Ｘ０＝（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５），Ｘ１＝（ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）に分割する。
【００４６】
Ｙ０事前計算部２２２は、（ｑ＋１）乗計算の出力となる２ｒ次拡大体の要素Ｙを、ｒ次拡大体の要素Ｙ０とｒ次拡大体の要素Ｙ１との二つに分割したとして、前者のＹ０を算出するもととなる値を得るために、Ｙ０に関する事前計算を行う（ステップＳ１２）。
【００４７】
この事前計算では、Ｔ2(Fq^r)の要素がＦq^2rの表現で表される冗長性を用いて、２ｒ次拡大体上の乗算に必要な事前計算のうち、基礎体上の乗算を他の乗算で置き換える。これによって、乗算回数を削減する。具体的には、例えば、Ｘ０に含まれるｒ個の値のうち、一部の値の二乗及び一部の値同士の乗算と、Ｘ１に含まれるｒ個の値のうち、一部の値の二乗及び一部の値同士の乗算とを実行する。
【００４８】
Ｙ０計算部２２４は、Ｙ０事前計算部２２２により得られた複数の演算値の線形加算によって、Ｙ０を算出する（ステップＳ１３）。
【００４９】
Ｙ１事前計算部２２３は、（ｑ＋１）乗計算の出力となる２ｒ次拡大体の要素Ｙを、ｒ次拡大体の要素Ｙ０とｒ次拡大体の要素Ｙ１の二つに分割したとして、後者のＹ１を算出するもととなる値を得るために、Ｙ１に関する事前計算を行う（ステップＳ１４）。この事前計算では、例えば、Ｘ０に含まれるｒ個の値と、Ｘ１に含まれるｒ個の値とをもとにした、複数の乗算を実行する。
【００５０】
Ｙ１計算部２２５は、Ｙ１事前計算部２２３により得られた複数の演算値の線形加算によって、Ｙ１を算出する（ステップＳ１５）。
【００５１】
結合部２２６は、Ｙ０計算部２２４が算出したｒ次拡大体の要素Ｙ０と、Ｙ１計算部２２５が算出したｒ次拡大体の要素Ｙ１とを結合して、２ｒ次拡大体の要素Ｙにして、これを出力する（ステップＳ１６）。例えば、ｒ＝５の場合、５次拡大体の要素Ｙ０＝（ｙ１，ｙ２，ｙ３，ｙ４，ｙ５）と、５次拡大体の要素Ｙ１＝（ｙ６，ｙ７，ｙ８，ｙ９，ｙ１０）とを結合して、１０次拡大体の要素Ｙ＝（ｙ１，ｙ２，ｙ３，ｙ４，ｙ５，ｙ６，ｙ７，ｙ８，ｙ９，ｙ１０）にして、これを出力する。
【００５２】
なお、ステップＳ１１が最初に実行され、ステップＳ１２がステップＳ１３の前に実行され、ステップＳ１４がステップＳ１５の前に実行され、ステップＳ１６が最後に実行されれば、図５とは異なる実行順でも良いし、複数のステップが同時に実行されてもよい。
【００５３】
このように、本実施形態の最終べきでは、（ｑ＋１）乗より先に（q^r−１）乗が行われるが、これによって、（q^r−１）乗が行われた段階で、その計算結果は、トーラスＴ2(Fq^r)の一意な表現となる。（q^r−１）乗の計算結果が、トーラスＴ2(Fq^r)の要素である性質を利用して、Ｙ０事前計算における幾つかの数の二乗を、他の乗算に置き換えることによって、計算量を減らす。
【００５４】
以下、ｒ＝５の場合を例にとって、（ｑ＋１）乗計算部２０２の構成・動作について詳しく説明する。
【００５５】
まず、２ｒ次拡大体の法多項式及び基底を、ｒ次拡大体のフロベニウス（Frobenius）写像（ｑ乗）が、要素同士の乗算よりも計算量の少ない演算（例えば、要素の入れ替え、及び又は、要素の重み付け加減算など）表現できるように、決定する。
【００５６】
ｒ＝５の場合、例えば、５次拡大体の２次拡大体の法多項式を、数式（２）のように設定する。  
σ２＝−１，  
ζ１０＋ζ９＋ζ８＋ζ７＋ζ６＋ζ５＋ζ４＋ζ３＋ζ２＋ζ＋１＝０        …（２）
また、数式（３）のように、１の原始１１乗根ζと、−１の平方根σとを用いて、基底を設定する。  
｛（ζ＋ζ１０），（ζ２＋ζ９），（ζ３＋ζ８），（ζ４＋ζ７），（ζ５＋ζ６），（ζ＋ζ１０）σ，（ζ２＋ζ９）σ，（ζ３＋ζ８）σ，（ζ４＋ζ７）σ，（ζ５＋ζ６）σ｝      …（３）
このとき、入力Ｘ＝（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）として、Ｘ０＝（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５）とＸ１＝（ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）は、５次拡大体の要素である。
【００５７】
ここで、ｘ１〜ｘ１０は、要素数ｑの有限体の要素である。簡単な例としては、ｑが素数のときｘ１〜ｘ１０を、それぞれ、０からｑ−１までの整数であるとすればよい。
【００５８】
Ｘ０のフロベニウス写像（Ｘ０のｑ乗）は、ｑ≡2 mod 11のとき、Ｘ０ｑ＝（ｘ５，ｘ１，ｘ４，ｘ２，ｘ３）となり、Ｘ０＝（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５）の要素の入れ替えとなっている。また、Ｘ１のフロベニウス写像（Ｘ１のｑ乗）は、ｑ≡2 mod 11のとき、Ｘ１ｑ＝（ｘ１０，ｘ６，ｘ９，ｘ７，ｘ８）となり、Ｘ１＝（ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）の要素の入れ替えとなっている。
【００５９】
ここで、入力Ｘは、既に（q^r−１）乗計算部２０１で（q^r−１）＝（q^5−１）乗されているので、トーラスＴ2(Fq^r)＝Ｔ2（Ｆq^5）の要素である。
【００６０】
ここで、ｒ＝５の場合、トーラスＴ2（Ｆq^5）の要素Ｘについて、これを（q^5＋１）乗すると１になる、という性質がある。ｒが５以外の奇素数である場合も同様で、トーラスＴ2（Ｆq^r）の要素Ｘについて、これを（q^r＋１）乗すると１になる、という性質がある。
【００６１】
これを、数式（２）の法多項式と、数式（３）の基底を用いて、具体的に表すと、数式（４）のようになる。ここで、Ｘ＝Ｘ０＋Ｘ１×σと置いた。  
Ｘ０２＋Ｘ１２＝１      …（４）
Ｘ０＝（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５）とＸ１＝（ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）とを数式（４）に代入すると、以下に示す数式（５）のような５個の関係が得られる。  
１−２x4２−２x9２−２x1２−２x6２−２x2２−２x7２−２x3２−２x8２−x5２−x10２＋２x1x2＋２x4x3＋２x6x7＋２x9x8＋２x3x2＋２x8x7＋２x5x4＋２x10x9＝０，  
１−２x4２−２x9２−x1２−x6２−２x2２−２x7２−２x3２−２x8２−２x5２−２x10２＋２x2x4＋２x3x5＋２x7x9＋２x8x10＋２x3x1＋２x8x6＋２x5x4＋２x10x9＝０，  
１−x4２−x9２−２x1２−２x6２−２x2２−２x7２−２x3２−２x8２−２x5２−２x10２＋２x1x2＋２x3x5＋２x6x7＋２x8x10＋２x5x2＋２x10x7＋２x4x1＋２x6x9＝０，  
１−２x4２−２x9２−２x1２−２x6２−x2２−x7２−２x3２−２x8２−２x5２−２x10２＋２x5x1＋２x4x3＋２x10x6＋２x9x8＋２x3x1＋２x8x6＋２x5x2＋２x10x7＝０，  
１−２x4２−２x9２−２x1２−２x6２−２x2２−２x7２−x3２−x8２−２x5２−２x10２＋２x5x1＋２x2x4＋２x10x6＋２x7x9＋２x3x2＋２x8x7＋２x4x1＋２x6x9＝０，  
…（５）
数式（５）について、第１の式から第３の式を減じた式、第２の式から第３の式を減じた式、第４の式から第５の式を減じた式を、それぞれ計算すると、次に示す数式（６）のような３個の関係式が得られる。  
−x4２−x9２＋x5２＋x10２＋２x4x3−２x3x5＋２x9x8−２x8x10＋２x3x2＋２x8x7−２x5x2−２x10x7＋２x5x4−２x4x1＋２x10x9−２x6x9＝０，  
−x4２−x9２＋x1２＋x6２−２x1x2＋２x2x4−２x6x7＋２x7x9＋２x3x1＋２x8x6−２x5x2−２x10x7＋２x5x4−２x4x1＋２x10x9−２x6x9＝０，  
x2２＋x７２−x3２−x8２＋２x4x3−２x2x4＋２x9x8−２x7x9＋２x3x1＋２x8x6−２x3x2−２x8x7＋２x5x2＋２x10x7−２x4x1−２x6x9＝０，  
…（６）
そして、数式（６）を用いて、ｘ5^2＋ｘ10^2，ｘ1^2＋ｘ6^2，ｘ3^2＋ｘ8^2を、他の乗算で置き換えることができる。
【００６２】
なお、数式（６）の代わりに、数式（５）について、第１の式から第４の式を減じた式、第２の式から第４の式を減じた式、第３の式から第５の式を減じた式の３個の関係式でも、ｘ5^2＋ｘ10^2，ｘ1^2＋ｘ6^2，ｘ3^2＋ｘ8^2を、他の乗算で置き換えることができる。
【００６３】
ここで、入力Ｘの（ｑ＋１）乗を、５次拡大体の要素を用いて表すと、例えば、次に示す数式（７）のようになる。  
Ｘｑ＋１＝（Ｘ０ｑ＋１＋Ｘ１ｑ＋１）＋（Ｘ０ｑ・Ｘ１−Ｘ０・Ｘ１ｑ）σ  
＝（Ｘ０ｑ・Ｘ０＋Ｘ１ｑ・Ｘ１）＋（Ｘ０ｑ・Ｘ１−Ｘ０・Ｘ１ｑ）σ      …（７）
ここで、数式（７）の右辺の第１項をＹ０、第２項をＹ１と置く。
【００６４】
まず、Ｙ０の計算について説明する。
【００６５】
Ｙ０については、Ｘ０ｑ＝（ｘ５，ｘ１，ｘ４，ｘ２，ｘ３）とＸ０＝（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５）の乗算と、Ｘ１ｑ＝（ｘ１０，ｘ６，ｘ９，ｘ７，ｘ８）とＸ１＝（ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）の乗算を、それぞれ、Karatsuba法を用いて計算すると、事前計算では、いずれも、Ｆq上乗算を１５回（すなわち、合計で３０回）行うことになる。ここで、数式（６）を用いて、ｘ5^2＋ｘ10^2，ｘ1^2＋ｘ6^2，ｘ3^2＋ｘ8^2を、他の乗算で置き換えると、事前計算のＦq上乗算は、合計で２４回となる。
【００６６】
Ｙ０＝（ｙ１，ｙ２，ｙ３，ｙ４，ｙ５）は、以下に示す数式（８）により求まる。  
ｙ１＝２x4２＋２x9２−２x5x1−x4x3−３x2x4−x3x5−２x10x6−x9x8−３x7x9−x8x10−x3x1−x8x6＋x3x2＋x8x7＋４x5x2＋４x7x10−２x5x4＋２x4x1−２x10x9＋２x6x9，  
ｙ２＝２x2２＋２x7２−x5x1−２x1x2＋x4x3−４x2x4−x3x5−x10x6−２x6x7＋x9x8−４x7x9−x8x10＋２x3x1＋２x8x6−２x3x2−２x8x7＋３x5x2＋３x7x10＋x5x4＋x10x9，  
ｙ３＝x4２＋x9２＋x2２＋x7２−x5x1＋x1x2−５x2x4−２x3x5−x10x6＋x6x7−５x7x9−２x8x10−x3x2−x8x7＋５x5x2＋５x10x7，  
ｙ４＝２x4２＋２x9２−x5x1−x1x2−４x4x3−２x2x4＋x3x5−x10x6−x6x7−４x9x8−２x7x9＋x8x10＋x3x1＋x8x6＋２x5x2＋２x10x7−２x5x4＋３x4x1−２x10x9＋３x6x9，  
ｙ５＝x4２＋x9２＋x2２＋x7２−２x5x1−３x4x3−x2x4−２x10x6−x6x7−３x9x8−x7x9＋２x3x1＋２x8x6−２x3x2−２x8x7＋２x5x2＋２x10x7−x5x4−３x4x1−x10x9＋３x6x9，  
…（８）
Ｙ０の事前計算としては、例えば、以下に示す数式（９）で表される計算を行う。  
ｚ１＝ｘ１ｘ２，  
ｚ２＝ｘ１ｘ３，  
ｚ３＝ｘ１ｘ４，  
ｚ４＝ｘ１ｘ５，  
ｚ５＝ｘ２ｘ２，  
ｚ６＝ｘ２ｘ３，  
ｚ７＝ｘ２ｘ４，  
ｚ８＝ｘ２ｘ５，  
ｚ９＝ｘ３ｘ４，  
ｚ１０＝ｘ３ｘ５，  
ｚ１１＝ｘ４ｘ４，  
ｚ１２＝ｘ４ｘ５，  
ｚ１３＝ｘ６ｘ７，  
ｚ１４＝ｘ６ｘ８，  
ｚ１５＝ｘ６ｘ９，  
ｚ１６＝ｘ６ｘ１０，  
ｚ１８＝ｘ７ｘ７，  
ｚ１９＝ｘ７ｘ８，  
ｚ２０＝ｘ７ｘ９，  
ｚ２１＝ｘ７ｘ１０，  
ｚ２１＝ｘ８ｘ９，  
ｚ２２＝ｘ８ｘ１０，  
ｚ２３＝ｘ９ｘ９，  
ｚ２４＝ｘ９ｘ１０  
…（９）
数式（９）の事前計算の結果を用いると、Ｙ０＝（ｙ１，ｙ２，ｙ３，ｙ４，ｙ５）は、以下に示す数式（１０）により得られる。  
ｙ１＝２z11＋２z23−２z4−z9−３z7−z10−２z16−z21−３z19−z22−z2−z14＋z6＋z18＋４z8＋４z20−２z12＋２z3−２z24＋２z15，  
ｙ２＝２z5＋２z17−z4−２z1＋z9−４z7−z10−z16−２z12＋z21−４z19−z22＋２z2＋２z14−２z6−２z18＋３z8＋３z20＋z12＋z24，  
ｙ３＝z11＋z23＋z5＋z17−z4＋z1−５z7−２z10−z16＋z13−５z19−２z22−z6−z18＋５z8＋５z24，  
ｙ４＝２z11＋２z23−z4−４z9−２z7＋z10−z16−z13−４z21−２z19＋z22＋z2＋z14＋２z8＋２z20−２z12＋３z3−２z24＋３z15，  
ｙ５＝z11＋z23＋z17−２z4−z1−３z9−z7−２z16−z13−３z21−z19＋２z2＋２z14−z6−２z18＋２z8＋２z20−z12＋３z3−z24＋３z15，  
…（１０）
次に、Ｙ１の計算について説明する。
【００６７】
Ｙ１については、Ｆq^5乗算器を用いて計算すればよい。Ｙ１計算部２２５は、Ｙ０計算部２２４の結果を用いないために、Ｙ０計算部２２４とＹ１計算部２２５とは、並列に処理することが出来る。
【００６８】
Ｙ１は、以下に示す数式（１１）により求まる。  
ｙ６＝−２x5x6＋２x10x1−２x1x7＋２x6x2−３x4x8＋３x9x3−３x2x9＋３x7x4−x3x10＋x8x5−x3x6＋x1x8−x3x7＋x2x8，  
ｙ７＝−x5x6＋x10x1−２x1x7＋２x6x2−３x4x8＋３x9x3−２x2x9＋２x7x4−３x3x10＋３x8x5−x5x7＋x10x2−x5x9＋x10x4，  
ｙ８＝−２x5x6＋３x10x1−３x1x7＋３x6x2−２x4x8＋２x9x3−x2x9＋x7x4−２x3x10＋２x8x5＋x3x7−x2x8＋x5x7−x10x2，  
ｙ９＝−３x5x6＋３x10x1−x1x7＋x6x2−２x4x8＋２x9x3−２x2x9＋２x7x4−３x3x10＋３x8x5＋x3x6−x1x8−x1x9＋x6x4，  
ｙ１０＝−２x5x6＋２x10x1−３x1x7＋３x6x2−x4x8＋x9x3−３x2x9＋３x7x4−２x3x10＋２x8x5＋x5x9＋x1x9−x10x4−x6x4，  
…（１１）
Ｙ１の事前計算としては、例えば、以下に示す数式（１２）で表される計算を行う。  
ｗ１＝ｘ１ｘ６，  
ｗ２＝ｘ２ｘ７，  
ｗ３＝ｘ３ｘ８，  
ｗ４＝ｘ４ｘ９，  
ｗ５＝ｘ５ｘ１０，  
ｗ６＝（ｘ１＋ｘ２）（ｘ６−ｘ７），  
ｗ７＝（ｘ１＋ｘ３）（ｘ６−ｘ８），  
ｗ８＝（ｘ１＋ｘ４）（ｘ６−ｘ９），  
ｗ９＝（ｘ１＋ｘ５）（ｘ６−ｘ１０），  
ｗ１０＝（ｘ２＋ｘ３）（ｘ７−ｘ８），  
ｗ１１＝（ｘ２＋ｗ４）（ｘ７−ｘ９），  
ｗ１２＝（ｘ２＋ｘ５）（ｘ７−ｘ１０），  
ｗ１３＝（ｘ３＋ｘ４）（ｘ８−ｘ９），  
ｗ１４＝（ｘ３＋ｘ５）（ｘ８−ｘ１０），  
ｗ１５＝（ｘ４＋ｘ５）（ｘ９−ｘ１０）  
…（１２）
数式（１２）の事前計算の結果を用いると、Ｙ１＝（ｙ６，ｙ７，ｙ８，ｙ９，ｙ１０）は、以下に示す数式（１３）により得られる。  
ｙ６＝−２w9＋２w6−３w13＋３w11＋w14−w7−w10＋w1−w5，  
ｙ７＝−３w9＋２w6−３w13＋２w11＋３w14−w12−w15−w1＋w2−２w5，  
ｙ８＝−３w9＋３w6−２w13＋w11＋２w14＋w10＋w12＋w3−w4−w5，  
ｙ９＝−３w9＋w6−２w13＋２w11＋３w14＋w7＋w8−w2＋w4，  
ｙ１０＝−２w9＋３w6−w13＋３w11＋２w14＋w15−w8−w3＋w5  
…（１３）
ここで、（ｑ＋１）乗における乗算の削減の効果について説明する。
【００６９】
本実施形態では、例えば、ｒ＝５の場合に、（q^5−１）乗の計算結果が、トーラスＴ2（Ｆq^5）の一意な表現となる性質を利用し、（ｑ＋１）乗の入力Ｘ＝（ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０）の間にある５個の関係式により、ｘ１２，ｘ３２，ｘ５２，ｘ６２，ｘ８２，ｘ１０２を他の乗算で置き換えることによって、計算量を削減することができる。具体的には、従来のKaratsuba法による事前計算を用いた場合に、Ｙ０計算のための乗算が３０回、Ｙ１計算のための乗算が１５回で、合計４５回となる。これに対して、本実施形態によれば、Ｙ０計算のための乗算が２４回、Ｙ１計算のための乗算が１５回で、合計３９回となる。
【００７０】
ところで、本実施形態の（ｑ＋１）乗計算部２０２は、トーラスＴ2(Fq^r)の要素の（ｑ＋１）乗を高速に計算する装置であるので、ペアリングの最終べき以外でも、利用することが可能である。例えば、Ｆq^2rの要素が与えられたとき、（q^r−１）乗する代わりに、トーラスＴ2(Fq^r)の要素であるかの判定を行えば、一般に用いることができる。
【００７１】
（第２の実施形態）
２入力１出力関数であるペアリングｅは、次のように、各入力に対して線形性が成り立つという性質（双線形性）を持つ。  
ｅ（Ｐ１＋Ｐ２，Ｑ）＝ｅ（Ｐ１，Ｑ）ｅ（Ｐ２，Ｑ）  
ｅ（Ｐ，Ｑ１＋Ｑ２）＝ｅ（Ｐ，Ｑ１）ｅ（Ｐ，Ｑ２）
この性質により、  
ｅ（ａＰ，ｂＱ）＝ｅ（ｂＰ，ａＱ）＝ｅ（Ｐ，Ｑ）ａｂ 
という関係が成立する。暗号プロトコルにとって、この関係が非常に有用となる。
【００７２】
以下では、第１の実施形態のペアリング計算装置１を署名サービスに適用する一例について説明する。
【００７３】
なお、ペアリングを用いた署名方式については、例えば“D. Boneh, B. Lynn and H. Shacham. Short signatures from the Weil pairing. Asiacrypt 2001, LNCS 2248, 514-532, 2001”や“D. Boneh, B. Lynn and H. Shacham. Short signatures from the Weil pairing. J. of Cryptology, Vol. 17, No. 4, 297-319, 2004”などに詳しく開示されている。
【００７４】
図６に、本実施形態に係る署名サービスシステムの機能ブロックの構成例を示す。
【００７５】
図６に示されるように、署名サービスシステムには、サービス提供者システム５０と、署名者システム４０と、検証者システム１０とが存在する。この署名サービスシステムでは、ペアリング計算は、検証者システム１０の署名の検証において実施される。
【００７６】
図６では、署名者システム４０は、１台のみ示したが、複数台存在して構わない。また、図６では、検証者システム１０は、１台のみ示したが、複数台存在して構わない。
【００７７】
サービス提供者システム５０と署名者システム４０と、サービス提供者システム５０と検証者システム１０、署名者システム４０と検証者システム１０とは、いずれも、ネットワークを介して通信可能である。ネットワークは、例えば、インターネットであってもよい。
【００７８】
サービス提供者システム５０と署名者システム４０と検証者システム１０とは、いずれも、コンピュータを用いて構成することができる。
【００７９】
なお、１台の端末が、署名者システム４０の機能と検証者システム１０の機能とを兼ね備えてもよい。
【００８０】
なお、図６の署名サービスシステムは、ペアリング計算装置１の（ｑ＋１）乗計算部２０２に係る部分を除いて、基本的には、従来の構成と同様で構わない。
【００８１】
図６に示されるように、署名者システム４０は、鍵ペア生成部４１、署名生成部４２を含む。
【００８２】
検証者システム１０は、入力処理部１１、第１の実施形態のペアリング計算装置１、判定部１２を含む。
【００８３】
サービス提供者システム５０は、署名者システム４０と検証者システム１０に、必要なシステム・パラメータ情報（例えば、署名サービスに必要なシステム・パラメータ（例えば、ペアリング、楕円曲線、有限体、楕円曲線の有理点からなる群の生成元、ハッシュ関数等の全部又は一部）を提供する。
【００８４】
署名者システム４０の鍵ペア生成部４１は、秘密鍵と公開鍵を生成する。例えば、秘密鍵ｘを選択し、生成元ｇと秘密鍵ｘから、公開鍵ｖ＝ｇ^xを生成する。
【００８５】
署名者システム４０の署名生成部４２は、署名対象のメッセージに対する署名を生成する。例えば、署名対象となるメッセージＭのハッシュ値h(M)を求め、h(M)^xを署名とする。
【００８６】
署名者システム４０は、公開鍵と、メッセージと、署名を、検証者システム１０に与える。例えば、公開鍵ｖと、メッセージＭと、署名h(M)^xを与える。
【００８７】
検証者システム１０は、署名者システム４０から、公開鍵と、メッセージと、署名を、取得する。例えば、公開鍵ｖ＝ｇ^xと、メッセージＭと、署名h(M)^xを、取得する。
【００８８】
検証者システム１０の入力処理部１１は、まず、第１の入力（Ｐ１，Ｑ１）をペアリング計算装置１に入力する。例えば、（生成元ｇ，署名h(M)^x）を入力する。これに対するペアリング値Ｙａは、判定部１２へ入力される。
【００８９】
入力処理部１１は、次に、第２の入力（Ｐ２，Ｑ２）をペアリング計算装置１に入力する。例えば、取得したメッセージＭから、そのハッシュ値h(M)を求め、（公開鍵ｇ^x，メッセージのハッシュ値h(M)）を入力する。これに対するペアリング値Ｙｂは、判定部１２へ入力される。
【００９０】
判定部１２は、二つのペアリング値Ｙａ，Ｙｂを比較し、Ｙａ＝Ｙｂならば署名が正当である判定し、Ｙａ≠Ｙｂならば署名が正当でない判定する。
【００９１】
ここで、上記の例において、署名が正しければ、  
Ｙａ＝ｅ（ｇ，h(M)^x）＝ｅ（ｇ，h(M)）^x＝ｅ（ｇ^x，h(M)）＝Ｙｂ  
となる。
【００９２】
なお、本実施形態では、ペアリング計算装置を署名サービスに適用する一例について説明したが、もちろん、このペアリング計算装置は、他の署名サービスや、署名サービス以外の種々の暗号プロトコルに適用可能である。
【００９３】
（第３の実施形態）
本実施形態では、第２の実施形態において、サービス提供者システム５０が、ペアリング計算装置１のパラメータを設定可能とする例について説明する。
【００９４】
なお、本実施形態では、第１及び第２の実施形態と相違する点を中心に説明する。
【００９５】
図７に、本実施形態に係る署名サービスシステムの機能ブロックの構成例を示す。また、図８に、図７のペアリング計算装置１の機能ブロックの構成例を示す。
【００９６】
図７に示されるように、サービス提供者システム５０は、図７の構成に加えて、システム・パラメータ設定部５１を含む。また、システム・パラメータ設定部５１は、有限体設定部５２を含む。
【００９７】
システム・パラメータ設定部５１は、署名サービスに必要なシステム・パラメータ（例えば、ペアリング、楕円曲線、有限体、楕円曲線の有理点からなる群の生成元、ハッシュ関数等の全部又は一部）を設定し、公開する。
【００９８】
有限体設定部５２は、楕円曲線が定義される有限体のパラメータを設定する。ｒ（ｒは奇素数）は、例えば、セキュリティの要件より決定すればよい。２ｒ次拡大体の法多項式及び基底は、ｒ次拡大体のフロベニウス（Frobenius）写像（ｑ乗）が、要素同士の乗算よりも計算量の少ない演算（例えば、要素の入れ替え、及び又は、要素の重み付け加減算など）で表現できるように、決定する。例えば、ｒ＝５の場合、法多項式と基底を数式（２）と数式（３）のように設定する。
【００９９】
なお、システム・パラメータ設定部５１の操作は、必ずしも、署名生成や検証時に毎回行う必要はない。
【０１００】
署名者システム４０は、図６の構成に加えて、パラメータ記憶部４３を含む。パラメータ記憶部４３は、サービス提供者システム５０のシステム・パラメータ設定部５１により公開される、署名サービスに必要なシステム・パラメータのうち、当該署名者システム４０自身が必要とするものを記憶する。
【０１０１】
また、署名者システム４０の鍵ペア生成部４１と署名生成部４２は、パラメータ記憶部４３に記憶されているパラメータに基づいて、処理を行う。
【０１０２】
検証者システム１０は、図６の構成に加えて、パラメータ記憶部１３を含む。パラメータ記憶部１３は、サービス提供者システム５０のシステム・パラメータ設定部５１により公開される、署名サービスに必要なシステム・パラメータのうち、当該署名者システム４０自身が必要とするものを記憶する。
【０１０３】
また、検証者システム１０の入力処理部１１と、ペアリング計算装置１（のペアリング中間値計算部１００及び最終べき計算部２００）とは、パラメータ記憶部１３に記憶されているパラメータに基づいて、処理を行う。
【０１０４】
図９に、ペアリング計算装置１の最終べき計算部２００の機能ブロックの構成例を示す。最終べき計算部２００は、図６の構成に加えて、有限体上演算規則記憶部２０４を含む。有限体上演算規則記憶部２０４には、法多項式と基底とから決まる２次拡大体とｒ次拡大体の演算規則が記憶されている。
【０１０５】
図１０に、図９の（ｑ＋１）乗計算部２０２の機能ブロックの構成例を示す。（ｑ＋１）乗計算部２０２は、図６の構成に加えて、パラメータ記憶部２２７を含む。パラメータ記憶部２２７には、２ｒ次拡大体の法多項式と基底が記憶されている。基底は、ｒ次拡大体のフロベニウス写像（ｑ乗）が、要素同士の乗算よりも計算量の少ない演算（例えば、要素の入れ替え、及び又は、要素の重み付け加減算など）で表現できるように、決定されている。例えば、ｒ＝５の場合、法多項式と基底を数式（２）と数式（３）のように決定されている。
【０１０６】
本実施形態の署名者システム４０の動作と、署名者システム４０の動作は、基本的には、第２の実施形態と同様である。
【０１０７】
なお、本実施形態では、ペアリング計算装置を署名サービスに適用する一例について説明したが、もちろん、このペアリング計算装置は、他の署名サービスや、署名サービス以外の種々の暗号プロトコルに適用可能である。
【０１０８】
なお、以上の各機能は、ソフトウェアとして記述し適当な機構をもったコンピュータに処理させても実現可能である。  
また、本実施形態は、コンピュータに所定の手順を実行させるための、あるいはコンピュータを所定の手段として機能させるための、あるいはコンピュータに所定の機能を実現させるためのプログラムとして実施することもできる。加えて該プログラムを記録したコンピュータ読取り可能な記録媒体として実施することもできる。
【０１０９】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０１１０】
【図１】本発明の第１の実施形態に係るペアリング計算装置の機能ブロックの構成例を示す図
【図２】同実施形態に係るペアリング計算装置の最終べき計算部の機能ブロックの構成例を示す図
【図３】同実施形態に係るペアリング計算装置の処理手順の一例を示すフローチャート
【図４】同実施形態に係る最終べき計算部の（ｑ＋１）乗計算部の機能ブロックの構成例を示す図
【図５】同実施形態に係る（ｑ＋１）乗計算の処理手順の一例を示すフローチャート
【図６】本発明の第２の実施形態に係る署名サービスシステムの機能ブロックの構成例を示す図
【図７】本発明の第３の実施形態に係る署名サービスシステムの機能ブロックの構成例を示す図
【図８】同実施形態に係るペアリング計算装置の機能ブロックの構成例を示す図
【図９】同実施形態に係るペアリング計算装置の最終べき計算部の機能ブロックの構成例を示す図
【図１０】同実施形態に係る最終べき計算部の（ｑ＋１）乗計算部の機能ブロックの構成例を示す図
【符号の説明】
【０１１１】
１…ペアリング計算装置、１００…ペアリング中間値計算部、２００…最終べき計算部、２０１…（q^r−１）乗計算部、２０２…（ｑ＋１）乗計算部、２０３…Φ2r（ｑ）／ｍ乗計算部、２０４…有限体上演算規則記憶部、２２１…分割部、２２２…Ｙ０事前計算部、２２３…Ｙ１事前計算部、２２４…Ｙ０計算部、２２５…Ｙ１計算部、２２６…結合部、２２７…パラメータ記憶部、１０…検証者システム、１１…入力処理部、１２…判定部、１３…パラメータ記憶部、４０…署名者システム、４１…鍵ペア生成部、４２…署名生成部、４３…パラメータ記憶部、５０…サービス提供者システム、５１…システム・パラメータ設定部、５２…有限体設定部
【図１】
0004649456.tif 000002
【図２】
0004649456.tif 000003
【図３】
0004649456.tif 000004
【図４】
0004649456.tif 000005
【図５】
0004649456.tif 000006
【図６】
0004649456.tif 000007
【図７】
0004649456.tif 000008
【図８】
0004649456.tif 000009
【図９】
0004649456.tif 000010
【図１０】
0004649456.tif 000011