(57)【特許請求の範囲】
【請求項１】
ｍ個の群Ｇ１の元Ｐ０，…，Ｐｍ−１と群Ｇ２の元Ｑ０，…，Ｑｍ−１とのマルチペアリングｅ（Ｐ０，Ｑ０）×ｅ（Ｐ１，Ｑ１）×…×ｅ（Ｐｍ−１，Ｑｍ−１）を求めるマルチペアリング演算装置であって、
ｍを２以上の整数、ｊを０以上ｍ−１以下の整数、ｐを素数または素数のべき乗、ｋを正の整数、Ｆ（ｐ）とＦ（ｐｋ）を有限体、Ｐｊを有限体Ｆ（ｐ）上の楕円曲線の点、Ｑｊを有限体Ｆ（ｐｋ）上の楕円曲線の点、Ｔｊ１とＴｊ２をＱｊに対応する有限体Ｆ（ｐｋ）上の楕円曲線の点、ｅを点Ｐｊと点Ｑｊとを入力とし有限体Ｆ（ｐｋ）上の元を出力するペアリング演算を示す記号、ｆを有限体Ｆ（ｐｋ）上の元、Ｌｊを点Ｔｊ１と点Ｔｊ２を通る直線をＰｊで評価した式評価であって係数にゼロまたは小整数を含む有限体Ｆ（ｐｋ）上の元、ΔをＬ０×…×ＬΔ−１の計算過程のすべての乗算を係数にゼロまたは小整数を含む元同士の乗算にできる最大の正整数とし、
ｆ，Ｌ０，Ｌ１，…，Ｌｍ−１を入力とし、マルチペアリング演算の処理に含まれるｆ×Ｌ０×…×Ｌｍ−１の演算結果を出力とする式評価演算部を有し、
前記式評価演算部は、
あらかじめ２以上Δ以下の整数δを定めており、
選択されていない式評価Ｌ０，Ｌ１，…，Ｌｍ−１の中からδ個を選択し、ｈ０，ｈ１，…，ｈδ−１とする式評価選択部と、
Ｌ”←ｈ０×ｈ１×…×ｈδ−１  を計算する式評価乗算部と、
ｆ←ｆ×Ｌ”  を計算し、ｆを更新する元乗算部と、
Ｌ０，Ｌ１，…，Ｌｍ−１の中で、前記式評価選択部で選択されていない式評価の数がδより少なくなるまで、前記式評価選択部と前記式評価乗算部と前記元乗算部の処理を繰り返す演算制御部と、
Ｌ０，Ｌ１，…，Ｌｍ−１の中で、前記式評価選択部で選択されていない式評価がある場合は、選択されていない式評価のすべてをｆに乗算し、乗算結果にｆを更新する未選択乗算部と、
を備え、ｆを演算結果として出力する
ことを特徴とするマルチペアリング演算装置。
【請求項２】
請求項１記載のマルチペアリング演算装置であって、
前記式評価乗算部は、ｈ０，ｈ１，…，ｈδ−１の中の２つからなる組を複数組作るように分けて組ごとに乗算する処理を含む
ことを特徴とするマルチペアリング演算装置。
【請求項３】
請求項１記載のマルチペアリング演算装置であって、
δ＝４であって、
前記式評価乗算部は、
Ｌ０’←ｈ０×ｈ１，  Ｌ１’←ｈ２×ｈ３
を計算し、
Ｌ”←Ｌ０’×Ｌ１’
のようにＬ”を計算する
ことを特徴とするマルチペアリング演算装置。
【請求項４】
請求項１記載のマルチペアリング演算装置であって、
δ＝３であって、
前記式評価乗算部は、
Ｌ０’←ｈ０×ｈ１
を計算し、
Ｌ”←Ｌ０’×ｈ２
のようにＬ”を計算する
ことを特徴とするマルチペアリング演算装置。
【請求項５】
ｍ個の群Ｇ１の元Ｐ０，…，Ｐｍ−１と群Ｇ２の元Ｑ０，…，Ｑｍ−１とのマルチペアリングｅ（Ｐ０，Ｑ０）×ｅ（Ｐ１，Ｑ１）×…×ｅ（Ｐｍ−１，Ｑｍ−１）を求めるマルチペアリング演算方法であって、
ｍを２以上の整数、ｊを０以上ｍ−１以下の整数、ｐを素数または素数のべき乗、ｋを正の整数、Ｆ（ｐ）とＦ（ｐｋ）を有限体、Ｐｊを有限体Ｆ（ｐ）上の楕円曲線の点、Ｑｊを有限体Ｆ（ｐｋ）上の楕円曲線の点、Ｔｊ１とＴｊ２をＱｊに対応する有限体Ｆ（ｐｋ）上の楕円曲線の点、ｅを点Ｐｊと点Ｑｊとを入力とし有限体Ｆ（ｐｋ）上の元を出力するペアリング演算を示す記号、ｆを有限体Ｆ（ｐｋ）上の元、Ｌｊを点Ｔｊ１と点Ｔｊ２を通る直線をＰｊで評価した式評価であって係数にゼロまたは小整数を含む有限体Ｆ（ｐｋ）上の元、ΔをＬ０×…×ＬΔ−１の計算過程のすべての乗算を係数にゼロまたは小整数を含む元同士の乗算にできる最大の正整数とし、
ｆ，Ｌ０，Ｌ１，…，Ｌｍ−１を入力とし、マルチペアリング演算の処理に含まれるｆ×Ｌ０×…×Ｌｍ−１の演算結果を出力とする式評価演算過程を有し、
前記式評価演算過程は、
あらかじめ２以上Δ以下の整数δを定めており、
式評価選択部が、選択されていない式評価Ｌ０，Ｌ１，…，Ｌｍ−１の中からδ個を選択し、ｈ０，ｈ１，…，ｈδ−１とする式評価選択ステップと、
式評価乗算部が、Ｌ”←ｈ０×ｈ１×…×ｈδ−１  を計算する式評価乗算ステップと、
元乗算部が、ｆ←ｆ×Ｌ”  を計算し、ｆを更新する元乗算ステップと、
演算制御部が、Ｌ０，Ｌ１，…，Ｌｍ−１の中で、前記式評価選択ステップで選択されていない式評価の数がδより少なくなるまで、前記式評価選択ステップと前記式評価乗算ステップと前記元乗算ステップの処理を繰り返す繰り返しステップと、
未選択乗算部が、Ｌ０，Ｌ１，…，Ｌｍ−１の中で、前記式評価選択部で選択されていない式評価がある場合は、選択されていない式評価のすべてをｆに乗算し、乗算結果にｆを更新する未選択乗算ステップと、
を有し、ｆを演算結果として出力する
ことを特徴とするマルチペアリング演算方法。
【請求項６】
請求項５記載のマルチペアリング演算方法であって、
前記式評価乗算ステップは、ｈ０，ｈ１，…，ｈδ−１を２つずつに分けて乗算し、その乗算結果同士を乗算する処理を含む
ことを特徴とするマルチペアリング演算方法。
【請求項７】
請求項５記載のマルチペアリング演算方法であって、
δ＝４であって、
前記式評価乗算ステップは、
Ｌ０’←ｈ０×ｈ１，  Ｌ１’←ｈ２×ｈ３
を計算し、
Ｌ”←Ｌ０’×Ｌ１’
のようにＬ”を計算する
ことを特徴とするマルチペアリング演算方法。
【請求項８】
請求項５記載のマルチペアリング演算方法であって、
δ＝３であって、
前記式評価乗算ステップは、
Ｌ０’←ｈ０×ｈ１
を計算し、
Ｌ”←Ｌ０’×ｈ２
のようにＬ”を計算する
ことを特徴とするマルチペアリング演算方法。
【請求項９】
請求項１〜４のいずれかに記載されたマルチペアリング演算装置としてコンピュータを機能させるためのマルチペアリング演算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術のためのマルチペアリング演算装置、マルチペアリング演算方法、マルチペアリング演算プログラムに関する。
【背景技術】
【０００２】
複数のペアリング演算の積を効率的に計算するマルチペアリングの従来技術として、特許文献１と非特許文献１が知られている。また、ペアリング演算の効率的なアルゴリズムの例が、非特許文献２，３などに示されている。例えば、Optimal Ateペアリングにおけるマルチペアリングのアルゴリズムを図１に示す。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００６−３０１５１３号公報
【非特許文献】
【０００４】
【非特許文献１】R. Granger, and N.P. Smart, "On Computing Products of Pairings," Cryptology ePrint Archive, Report 2006/172, 2006.
【非特許文献２】F. Vercauteren, "Optimal Pairings," IEEE Transactions on Information Theory, vol.56, no.1, pp.455-461, 2010.
【非特許文献３】D.F. Aranha, P.S.L.M. Barreto, P. Longa, and J.E. Ricardini, "The Realm of the Pairings," Cryptology ePrint Archive, Report 2013/722, 2013.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ペアリング暗号では、鍵や暗号文に対して属性と条件式を含め、属性が条件式を満たすかどうかにより復号制御が可能な関数型暗号など、従来の暗号よりも高機能な暗号システムが構成可能である。これらのペアリング暗号システムの構成の際には、暗号化や復号が十分に高速であることが求められる。特に、関数型暗号などの高機能な暗号方式では、多数のペアリング演算が必要となる。特許文献１や非特許文献１に示されたマルチペアリングは、共通化が可能な計算を共通化することで高速化しているので、多数のペアリングを効率的に計算する際には有効である。しかしながら、暗号システムの高機能化が進んでいる状況から、さらなる高速化が求められている。
【０００６】
本発明は、楕円曲線上のマルチペアリングについて従来技術を改良し、さらに演算速度を高速化することを目的とする。
【課題を解決するための手段】
【０００７】
本発明のマルチペアリング演算装置は、ｍ個の群Ｇ１の元Ｐ０，…，Ｐｍ−１と群Ｇ２の元Ｑ０，…，Ｑｍ−１とのマルチペアリングｅ（Ｐ０，Ｑ０）×ｅ（Ｐ１，Ｑ１）×…×ｅ（Ｐｍ−１，Ｑｍ−１）を求める。ここで、ｍを２以上の整数、ｊを０以上ｍ−１以下の整数、ｐを素数または素数のべき乗、ｋを正の整数、Ｆ（ｐ）とＦ（ｐｋ）を有限体、Ｐｊを有限体Ｆ（ｐ）上の楕円曲線の点、Ｑｊを有限体Ｆ（ｐｋ）上の楕円曲線の点、Ｔｊ１とＴｊ２をＱｊに対応する有限体Ｆ（ｐｋ）上の楕円曲線の点、ｅを点Ｐｊと点Ｑｊとを入力とし有限体Ｆ（ｐｋ）上の元を出力するペアリング演算を示す記号、ｆを有限体Ｆ（ｐｋ）上の元、Ｌｊを点Ｔｊ１と点Ｔｊ２を通る直線をＰｊで評価した式評価であって係数にゼロまたは小整数を含む有限体Ｆ（ｐｋ）上の元、ΔをＬ０×…×ＬΔ−１の計算過程のすべての乗算を係数にゼロまたは小整数を含む元同士の乗算にできる最大の正整数とする。
【０００８】
本発明のマルチペアリング演算装置は、ｆ，Ｌ０，Ｌ１，…，Ｌｍ−１を入力とし、マルチペアリング演算の処理に含まれるｆ×Ｌ０×…×Ｌｍ−１の演算結果を出力とする式評価演算部を有する。式評価演算部は、あらかじめ２以上Δ以下の整数δを定めており、式評価選択部、式評価乗算部、元乗算部、演算制御部、未選択乗算部を備える。式評価選択部は、選択されていない式評価Ｌ０，Ｌ１，…，Ｌｍ−１の中からδ個を選択し、ｈ０，ｈ１，…，ｈδ−１とする。式評価乗算部は、Ｌ”←ｈ０×ｈ１×…×ｈδ−１  を計算する。元乗算部は、ｆ←ｆ×Ｌ”  を計算し、ｆを更新する。演算制御部は、Ｌ０，Ｌ１，…，Ｌｍ−１の中で、式評価選択部で選択されていない式評価の数がδより少なくなるまで、式評価選択部と式評価乗算部と元乗算部の処理を繰り返す。未選択乗算部は、Ｌ０，Ｌ１，…，Ｌｍ−１の中で、式評価選択部で選択されていない式評価がある場合は、選択されていない式評価のすべてをｆに乗算し、乗算結果にｆを更新する。式評価演算部は、Ｌ０，Ｌ１，…，Ｌｍ−１のすべてを乗算されたｆを演算結果として出力する。
【発明の効果】
【０００９】
本発明のマルチペアリング演算装置によれば、マルチペアリング演算の処理に含まれるｆ×Ｌ０×…×Ｌｍ−１の演算において、まずゼロまたは小整数の係数を含む式評価Ｌ０，Ｌ１，…，Ｌｍ−１の中からΔ個以下の式評価を選択して乗算する処理を繰り返すので、係数にゼロや小整数を持つ元同士の演算を増やせる。したがって、計算コストを削減でき、計算速度を高速化できる。
【図面の簡単な説明】
【００１０】
【図１】従来のOptimal Ateペアリングにおけるマルチペアリングのアルゴリズムを示す図。
【図２】本発明のマルチペアリング演算装置の構成例を示す図。
【図３】本発明のマルチペアリング演算装置の式評価演算の処理フローの例を示す図。
【図４】Optimal Ateペアリングにおけるマルチペアリングのアルゴリズムの例（Algorithm 2）を示す図。
【図５】図４のアルゴリズムのステップ６，９，１８，２０に適用する式評価演算部１００の処理のアルゴリズムの１つ目の例（Algorithm 3）を示す図。
【図６】図５のステップ３の計算の部分のアルゴリズムの具体例（Algorithm 4）を示す図。
【図７】図５，１３のステップ４の処理のアルゴリズムの具体例（Algorithm 5）を示す図。
【図８】図５のステップ９の処理のアルゴリズムの具体例（Algorithm 6）を示す図。
【図９】図４のアルゴリズムのステップ６，９，１８，２０に適用する式評価演算部１００の処理のアルゴリズムの２つ目の例（Algorithm 7）を示す図。
【図１０】図９，１３のステップ３の計算の部分のアルゴリズムの具体例（Algorithm 8）を示す図。
【図１１】図９のステップ４の処理のアルゴリズムの具体例（Algorithm 9）を示す図。
【図１２】図９，１３のステップ９の処理のアルゴリズムの具体例（Algorithm 10）を示す図。
【図１３】図４のアルゴリズムのステップ６，９，１８，２０に適用する式評価演算部１００の処理のアルゴリズムの３つ目の例（Algorithm 11）を示す図。
【発明を実施するための形態】
【００１１】
以下、本発明の実施の形態について、詳細に説明する。本発明のマルチペアリング演算装置は、ｍ個の群Ｇ１の元Ｐ０，…，Ｐｍ−１と群Ｇ２の元Ｑ０，…，Ｑｍ−１とのマルチペアリングｅ（Ｐ０，Ｑ０）×ｅ（Ｐ１，Ｑ１）×…×ｅ（Ｐｍ−１，Ｑｍ−１）を求める。ｍを２以上の整数、ｊを０以上ｍ−１以下の整数、ｐを素数または素数のべき乗、ｋを正の整数、Ｆ（ｐ）とＦ（ｐｋ）を有限体、Ｐｊを有限体Ｆ（ｐ）上の楕円曲線の点、Ｑｊを有限体Ｆ（ｐｋ）上の楕円曲線の点、Ｔｊ１とＴｊ２をＱｊに対応する有限体Ｆ（ｐｋ）上の楕円曲線の点、ｅを点Ｐｊと点Ｑｊとを入力とし有限体Ｆ（ｐｋ）上の元を出力するペアリング演算を示す記号、ｆを有限体Ｆ（ｐｋ）上の元、Ｌｊを点Ｔｊ１と点Ｔｊ２を通る直線をＰｊで評価した式評価であって係数にゼロまたは小整数を含む有限体Ｆ（ｐｋ）上の元、ΔをＬ０×…×ＬΔ−１の計算過程のすべての乗算を係数にゼロまたは小整数を含む元同士の乗算にできる最大の正整数とする。点Ｔｊ１と点Ｔｊ２とが同一の点の場合、「点Ｔｊ１と点Ｔｊ２を通る直線」は点Ｔｊ１での接線とする。「小整数」とは少なくとも１を含む値の小さい整数であり、例えば、任意の元ｆと小整数ｄとの乗算（ｄ×ｆ）を、任意の元ｆのｄ−１回の加算（ｆ＋ｆ＋…＋ｆ）で行った方が、計算量が少なくなるような整数である。また、後述の１を係数として含む元の乗算と同様に計算コストを少なくできる小さい整数も含む。演算装置、演算方法、プログラムによって具体的な小整数は異なるが、ある演算装置が、整数ｄと元ｆとの乗算（ｄ×ｆ）を加算（ｆ＋ｆ＋…＋ｆ）に置き換えて計算している場合、その演算装置においては、整数ｄは小整数である。
【００１２】
また、図１，４，５，９，１３に示すアルゴリズムでは、ＴｊがＴｊ１に相当し、Ｔｊ，Ｑｊ，Ｑｊ’，−Ｑｊ”がＴｊ２に相当し、ａｏｐｔがｅに相当し、
【数１】
0006023728.tif 000002
がＬｊに相当する。また、Ｆ（ｐｋ）は、
【数２】
0006023728.tif 000003
のように示されている。
【００１３】
＜分析＞
ペアリング演算には、点Ｔｊ１と点Ｔｊ２と点Ｐｊに対して、点加算／２倍算と式評価の計算が含まれる。次に、具体的な座標系の例を示しながら説明する。
【００１４】
次の具体例の説明では、Barreto-Naehrig楕円曲線（ＢＮ曲線，Ｅ：ｙ２＝ｘ３＋ｂ，ｂ≠０∈Ｆ（ｐ））を用いる。ＢＮ曲線では、整数ｚに対して素数ｐとＢＮ曲線上のＦ（ｐ）有理点群の位数ｒは、
ｐ＝３６ｚ４＋３６ｚ３＋２４ｚ２＋６ｚ＋１
ｒ＝３６ｚ４＋３６ｚ３＋１８ｚ２＋６ｚ＋１
である。ＢＮ曲線では、ｒで割り切れる（ｐｋ−１）となる最小のｋは１２である。
【００１５】
拡大体Ｆ（ｐｋ）を逐次拡大により
Ｆ（ｐ２）＝Ｆ（ｐ）［ｕ］／（ｕ２−β）
Ｆ（ｐ６）＝Ｆ（ｐ２）［ｖ］／（ｖ３−ξ）
Ｆ（ｐ１２）＝Ｆ（ｐ６）［ｗ］／（ｗ２−ｖ）
ただし、βは平方非剰余、ξは平方非剰余かつ立方非剰余
のように構成する。そして、Ｆ（ｐ１２）上の元Ａを
Ａ＝ａ０＋ａ１ｖ＋ａ２ｖ２＋ａ３ｗ＋ａ４ｖｗ＋ａ５ｖ２ｗ        （式１）
【００１６】
ただし、ａ０，ａ１，ａ２，ａ３，ａ４，ａ５  ∈Ｆ（ｐ２）
と表現する。なお、６次のツイスト曲線Ｅ’は、ｙ２＝ｘ３＋ｂ／ξ  である。このとき、点（ｘ，ｙ）に対してＥ’，Ｅの同型写像（ｘ，ｙ）→（ｘｗ２，ｙｗ３）となる
Φ：Ｅ’（Ｆ（ｐ２））→Ｅ（Ｆ（ｐ１２））
が存在する。
【００１７】
Affine座標系の例
Ｔｊ１＝（ｘ１，ｙ１）、Ｔｊ２＝（ｘ２，ｙ２）、Ｐｊ＝（ｘＰ，ｙＰ）とする。λ＝（ｙ２−ｙ１）／（ｘ２−ｘ１）に対して、点加算と式評価（点Ｔｊ１と点Ｔｊ２とが異なる場合）は、
ｘ３＝λ２−ｘ１−ｘ２
ｙ３＝λ（ｘ１−ｘ３）−ｙ１
Ｌｊ＝ｙＰ−λｘｐｗ＋（λｘ１−ｙ１）ｖｗ      （式２）
となる。また、点２倍算と式評価（点Ｔｊ１と点Ｔｊ２とが同じ場合）は、λ＝３ｘ１２／２ｙ１に対して
ｘ３＝λ２−２ｘ１
ｙ３＝λ（ｘ１−ｘ３）−ｙ１
Ｌｊ＝ｙＰ−λｘｐｗ＋（λｘ１−ｙ１）ｖｗ      （式３）
となる。ここで、式１に示したＦ（ｐ１２）上の元Ａはａ０，ａ１，ａ２，ａ３，ａ４，ａ５の６つの係数が存在するが、式２、式３に示した式評価ではその中の３つの係数がゼロであることが分かる。
【００１８】
Affine座標系の異なる形式の式評価の例
式２、式３を
ｙＰ’・Ｌｊ＝１−λｘｐ’ｗ＋ｙＰ’（λｘ１−ｙ１）ｖｗ      （式４）
ただし、ｘｐ’＝ｘｐ／ｙＰ，  ｙＰ’＝１／ｙＰ
のように変換して式評価としてもよい。このように変形しても、ｙＰ’の部分は最終べきの計算（図１のアルゴリズムのステップ２１）で除去されるため、ペアリング演算の結果には影響しない。式４のように変形すると、３つの係数がゼロであり１つの係数が小整数の「１」であることが分かる。
【００１９】
Homogeneous Projective座標系の例
この座標系での楕円曲線Ｅは、Ｙ２Ｚ＝Ｘ３＋ｂ’Ｚ３となる。点の表現をＴｊ１＝（Ｘ１，Ｙ１，Ｚ１）∈Ｇ２とし、（ｘ１，ｙ１）＝（Ｘ１／Ｚ１，Ｙ１／Ｚ１）、Ｔｊ２＝（ｘ２，ｙ２）、Ｐｊ＝（ｘＰ，ｙＰ）とする。また点加算／２倍算と式評価は、Homogeneous Projective座標系の点とAffine座標系の点の混合座標で計算する。ｔ０＝Ｙ１−ｙ２Ｚ１，ｔ１＝Ｘ１−ｘ２Ｚ１に対して、点加算と式評価は、
Ｘ３＝ｔ１（ｔ１３＋Ｚ１ｔ０２−２Ｘ１ｔ１２）
Ｙ３＝ｔ０（３Ｘ１ｔ１２−ｔ１３−Ｚ１ｔ０２）−Ｙ１ｔ１３
Ｚ３＝Ｚ１ｔ１３
Ｌｊ＝−ｔ１ｙＰ−ｔ０ｘｐｗ＋（ｔ０Ｘ２−ｔ１Ｙ２）ｖｗ      （式５）
となる。また、点２倍算と式評価は、
Ｘ３＝Ｘ１Ｙ１（Ｙ１２−９ｂ’Ｚ１２）／２
Ｙ３＝［（Ｙ１２＋９ｂ’Ｚ１２）／２］２−２７ｂ’２Ｚ１４
Ｚ３＝２Ｙ１３Ｚ１
Ｌｊ＝−２Ｙ１Ｚ１ｙＰ＋３Ｘ１２ｘｐｗ＋（３ｂ’Ｚ１２−Ｙ１２）ｖｗ      （式６）
となる。元は式１で表現されるので、式５、式６に示した式評価では３つの係数がゼロであることが分かる。
【００２０】
本発明は、式評価にゼロの係数があることを利用して計算コストを削減する。
【実施例１】
【００２１】
図２に本発明のマルチペアリング演算装置の構成例を、図３に本発明のマルチペアリング演算装置の式評価演算の処理フローの例を示す。マルチペアリング演算装置１０は、ｍ個の群Ｇ１の元Ｐ０，…，Ｐｍ−１と群Ｇ２の元Ｑ０，…，Ｑｍ−１とのマルチペアリングｅ（Ｐ０，Ｑ０）×ｅ（Ｐ１，Ｑ１）×…×ｅ（Ｐｍ−１，Ｑｍ−１）を求める。マルチペアリング演算装置１０は、式評価演算部１００を有することを特徴としており、点加算や点２倍算などのその他の処理を行う構成部も有するが、それらは従来技術と同じである。そのため、図２，３では省略している。
【００２２】
式評価演算部１００は、ｆ，Ｌ０，Ｌ１，…，Ｌｍ−１を入力とし、マルチペアリング演算の処理に含まれるｆ×Ｌ０×…×Ｌｍ−１の演算結果を出力する（Ｓ１００）。式評価演算部１００は、あらかじめ２以上Δ以下の整数δを定めており、式評価選択部１１０、式評価乗算部１２０、元乗算部１３０、演算制御部１４０、未選択乗算部１５０を備える。マルチペアリング演算装置１０は、整数δなどを記録する記録部９０も備える。式評価選択部１１０は、選択されていない式評価Ｌ０，Ｌ１，…，Ｌｍ−１の中からδ個を選択し、ｈ０，ｈ１，…，ｈδ−１とする（Ｓ１１０）。
【００２３】
式評価乗算部１２０は、
Ｌ”←ｈ０×ｈ１×…×ｈδ−１
を計算する（Ｓ１２０）。式評価乗算部１２０は、ｈ０，ｈ１，…，ｈδ−１をゼロまたは小整数の係数を含む元同士の演算がより多くなるように工夫して乗算すればよい。例えば、ｈ０，ｈ１，…，ｈδ−１の中の２つからなる組を複数組作るように分けて組ごとに乗算する処理を含むように構成する方法がある。このように計算すれば、ゼロまたは小整数の係数を含む元同士の演算がより多くなる。「ｈ０，ｈ１，…，ｈδ−１の中の２つからなる組を複数組作るように分けて組ごとに乗算する」具体例としては以下のような例がある。δ＝４のときには、
Ｌ０’←ｈ０×ｈ１，  Ｌ１’←ｈ２×ｈ３
Ｌ”←Ｌ０’×Ｌ１’
のようにＬ”を計算すればよい。このときは、（ｈ０，ｈ１）の組と（ｈ２，ｈ３）の組を作るように分けられ、まず組ごとに乗算している。δ＝６のときには、
Ｌ０’←ｈ０×ｈ１，  Ｌ１’←ｈ２×ｈ３，  Ｌ２’←ｈ５×ｈ６
Ｌ”←Ｌ０’×Ｌ１’×Ｌ２’
のようにＬ”を求めてもよい。このときは、（ｈ０，ｈ１）の組と（ｈ２，ｈ３）の組と（ｈ４，ｈ５）の組を作るように分けられ、まず組ごとに乗算している。また、このような求め方を、
Ｌ”←（（ｈ０×ｈ１）×（ｈ２×ｈ３）×（ｈ５×ｈ６））
と表現する。また、δ＝６のときに、
Ｌ０’←ｈ０×ｈ１，  Ｌ１’←ｈ３×ｈ４
Ｌ０’←Ｌ０’×ｈ２，  Ｌ１’←Ｌ１’×ｈ５
Ｌ”←Ｌ０’×Ｌ１’
のようにＬ”を求めてもよい。このときは、（ｈ０，ｈ１）の組と（ｈ３，ｈ４）の組を作るように分けられ、まず組ごとに乗算している。ｈ２とｈ５のように、組に含まれないものがあってもよい。このような求め方を、
Ｌ”←（（（ｈ０×ｈ１）×ｈ２）×（（ｈ３×ｈ５）×ｈ６））
と表現する。δ＝６の場合にどちらの計算手順を選ぶかは、式評価の特徴を考慮して決めればよい。特に、δ＝２ｔの場合であれば、
Ｌ”←（…（（ｈ０×ｈ１）×（ｈ２×ｈ３））×（（ｈ５×ｈ６）×（ｈ２×ｈ３））×…）
のように、２つずつに分けて乗算する処理を繰り返せばよい。上記のようにδが４以上の場合であれば、ｈ０，ｈ１，…，ｈδ−１の中の２つからなる組を複数組作るように分けて組ごとに乗算する処理を含むように構成できる。また、δ＝３のときには、
Ｌ０’←ｈ０×ｈ１
Ｌ”←Ｌ０’×ｈ２
のようにＬ”を計算すればよい。
【００２４】
なお、上述のAffine座標系とHomogeneous Projective座標系では、ｈ０×ｈ１の乗算は、係数にゼロを含む元同士の乗算であり、計算結果には値がゼロの係数が１つ存在する。（ｈ０×ｈ１）×ｈ２や（ｈ０×ｈ１）×（ｈ２×ｈ３）の乗算は係数にゼロを含む元同士の乗算であるが、計算結果には値がゼロまたは小整数の係数はなくなる。そして、ｈ０×ｈ１×ｈ２×ｈ３×ｈ４のようが５つの元の乗算では、（（ｈ０×ｈ１）×（ｈ２×ｈ３））×ｈ４、（（ｈ０×ｈ１）×ｈ２）×（ｈ３×ｈ４）などの計算手順が考えられるが、どのように計算しても、少なくとも最後の乗算の一方の元は、値がゼロまたは小整数の係数を含まない元になってしまう。したがって、計算過程のすべての乗算において、係数にゼロまたは小整数を含む元同士の乗算にできるのは４つの元の乗算までである。よって、Δ＝４である。そして、δ＝４に設定すれば、上記の手順で計算ができる。また、ステップＳ１１０が終了してからステップＳ１２０を開始するのではなく、ステップＳ１１０で２つの式評価を選択してステップＳ１２０の乗算を行う処理を繰り返してもよい。
【００２５】
元乗算部１３０は、
ｆ←ｆ×Ｌ”
を計算し、ｆを更新する（Ｓ１３０）。演算制御部１４０は、Ｌ０，Ｌ１，…，Ｌｍ−１の中で、式評価選択部１１０で選択されていない式評価の数がδより少なくなるまで、式評価選択部１１０と式評価乗算部１２０と元乗算部１３０の処理（Ｓ１１０，Ｓ１２０，Ｓ１３０）を繰り返す（Ｓ１４０）。未選択乗算部１５０は、Ｌ０，Ｌ１，…，Ｌｍ−１の中で、式評価選択部１１０で選択されていない式評価がある場合は、選択されていない式評価のすべてをｆに乗算し、乗算結果にｆを更新する（Ｓ１５０）。式評価演算部１００は、Ｌ０，Ｌ１，…，Ｌｍ−１のすべてを乗算されたｆを演算結果として出力する。
【００２６】
マルチペアリング演算装置１０によれば、マルチペアリング演算の処理に含まれるｆ×Ｌ０×…×Ｌｍ−１の演算において、まずゼロまたは小整数の係数を含む式評価Ｌ０，Ｌ１，…，Ｌｍ−１の中からΔ個以下の式評価を選択して乗算する処理を繰り返すので、係数にゼロや小整数を持つ元同士の演算を増やせる。したがって、計算コストを削減でき、計算速度を高速化できる。
【００２７】
＜アルゴリズムの具体例＞
図４に、Optimal Ateペアリングにおけるマルチペアリングのアルゴリズムの例（Algorithm 2）を示す。図４のアルゴリズムは、図１に示した従来のアルゴリズムを、本発明の式評価の乗算を適用できるように変更したものである。式評価演算部１００の処理は、図４のアルゴリズムのステップ６，９，１８，２０に適用される。以下では、これらのステップに適用するアルゴリズムの例を示す。
【００２８】
例１
図５は、図４のアルゴリズムのステップ６，９，１８，２０に適用する式評価演算部１００の処理のアルゴリズムの１つ目の例（Algorithm 3）である。このアルゴリズムは、式３，５で表現できる式評価（３つの係数がゼロの式評価）の乗算に適用できる。図５のステップ３では、ｈ０，ｈ１，ｈ２，ｈ３として
【数３】
0006023728.tif 000004
【００２９】
が選択され、
Ｌ０’←ｈ０×ｈ１，  Ｌ１’←ｈ２×ｈ３
の計算が行われる。そして、ステップ４で
Ｌ”←Ｌ０’×Ｌ１’
のようにＬ”が求められている。つまり、ステップ３の式評価の選択部分がＳ１１０に相当し、ステップ３のＬ０’とＬ１’の計算の部分と、ステップ４がＳ１２０に相当する。また、ステップ５がＳ１３０に相当し、ステップ１，２，６がＳ１４０に相当し、ステップ７〜１０がＳ１５０に相当する。
【００３０】
図６は、図５のステップ３のＬ０’とＬ１’の計算の部分のアルゴリズムの具体例（Algorithm 4）である。図６のステップ８に示された元の式から、値がゼロの係数が１つあることが分かる。図７は、図５のステップ４の処理のアルゴリズムの具体例（Algorithm 5）である。図８は、図５のステップ９の処理のアルゴリズムの具体例（Algorithm 6）である。
【００３１】
例２
図９は、図４のアルゴリズムのステップ６，９，１８，２０に適用する式評価演算部１００の処理のアルゴリズムの２つ目の例（Algorithm 7）である。このアルゴリズムは、式４で表現できる式評価（３つの係数がゼロ、１つの係数が「１」の式評価）の乗算に適用できる。図９のステップ３，４では、ｈ０，ｈ１，ｈ２として
【数４】
0006023728.tif 000005
が選択され、
Ｌ’←ｈ０×ｈ１，
Ｌ”←Ｌ’×ｈ２’
のようにＬ”が求められている。つまり、ステップ３，４の式評価の選択部分がＳ１１０に相当し、ステップ３，４のＬ’とＬ”の計算の部分がＳ１２０に相当する。また、ステップ５がＳ１３０に相当し、ステップ１，２，６がＳ１４０に相当し、ステップ７〜１０がＳ１５０に相当する。
【００３２】
図１０は、図９のステップ３のＬ’の計算の部分のアルゴリズムの具体例（Algorithm 8）である。図１１は、図９のステップ４の処理のアルゴリズムの具体例（Algorithm 9）である。図１２は、図９のステップ９の処理のアルゴリズムの具体例（Algorithm 10）である。
【００３３】
例３
図１３は、図４のアルゴリズムのステップ６，９，１８，２０に適用する式評価演算部１００の処理のアルゴリズムの３つ目の例（Algorithm 11）である。このアルゴリズムは、式４で表現できる式評価（３つの係数がゼロ、１つの係数が「１」の式評価）の乗算に適用できる。図１３のステップ３では、ｈ０，ｈ１，ｈ２，ｈ３として
【数５】
0006023728.tif 000006
【００３４】
が選択され、
Ｌ０’←ｈ０×ｈ１，  Ｌ１’←ｈ２×ｈ３
の計算が行われる。そして、ステップ４で
Ｌ”←Ｌ０’×Ｌ１’
のようにＬ”が求められている。つまり、ステップ３の式評価の選択部分がＳ１１０に相当し、ステップ３のＬ０’とＬ１’の計算の部分と、ステップ４がＳ１２０に相当する。また、ステップ５がＳ１３０に相当し、ステップ１，２，６がＳ１４０に相当し、ステップ７〜１０がＳ１５０に相当する。
【００３５】
ステップ３は図１０に示したアルゴリズム（Algorithm 8）を用い、ステップ４は図７に示したアルゴリズム（Algorithm 5）を用い、ステップ９は図１２に示したアルゴリズム（Algorithm 10）を用いればよい。
【００３６】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００３７】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００３８】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００３９】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００４０】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００４１】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００４２】
１０  マルチペアリング演算装置          ９０  記録部
１００  式評価演算部                    １１０  式評価選択部
１２０  式評価乗算部                    １３０  元乗算部
１４０  演算制御部                      １５０  未選択乗算部
【図１】
0006023728.tif 000007
【図２】
0006023728.tif 000008
【図３】
0006023728.tif 000009
【図４】
0006023728.tif 000010
【図５】
0006023728.tif 000011
【図６】
0006023728.tif 000012
【図７】
0006023728.tif 000013
【図８】
0006023728.tif 000014
【図９】
0006023728.tif 000015
【図１０】
0006023728.tif 000016
【図１１】
0006023728.tif 000017
【図１２】
0006023728.tif 000018
【図１３】
0006023728.tif 000019