(57)【要約】【課題】楕円曲線上のペアリングについて従来技術を改良し、さらに計算速度を高速化する。【解決手段】本発明のペアリング演算装置は、記録部、入力変換部、式評価生成部、式評価演算部を備える。式評価Ｌ０が、Ｌ０＝α０ｙ０Ｐ＋β０ｘ０ｐｗ＋γ０ｖｗのときに、記録部は、Ａ０と所定の関係を持つ値であるａ０と、Ｂ０と所定の関係を持つ値であるｂ０を記録している。入力変換部は、ｘ０Ｐとｙ０Ｐから、ｘ０Ｐ’＝γ０／（Ｂ０・β０・ｘ０Ｐ）、ｙ０Ｐ’＝（α０・ｙ０Ｐ）／（Ａ０・β０・ｘ０Ｐ）が成り立つｘ０Ｐ’とｙ０Ｐ’を求める。式評価生成部は、記録部からａ０とｂ０を読み出し、ａ０とｂ０を用いて、Ｌ０’＝ｄ０ｖＮ（Ａ０ｙ０Ｐ’＋ｗ＋Ｂ０ｘ０Ｐ’ｖｗ）のように式評価Ｌ０’を生成する。式評価演算部は、ｆ，Ｌ０’を入力とし、ｆ×Ｌ０’の演算結果を出力する。【選択図】図５
2015135452.tif 000002
【特許請求の範囲】
【請求項１】
群Ｇ１の元Ｐ０と群Ｇ２の元Ｑ０とのペアリングｅ（Ｐ０，Ｑ０）を求めるペアリング演算装置であって、
ｐを素数または素数のべき乗、Ｎをあらかじめ定めた０，１，２のいずれかの整数、ｋを正の整数、Ｆ（ｐ）とＦ（ｐｋ）を有限体、Ｐ０を有限体Ｆ（ｐ）上の楕円曲線の点、Ｑ０を有限体Ｆ（ｐ１２）上の楕円曲線の点であって固定された点、Ｔ０１とＴ０２をＱ０に対応する有限体Ｆ（ｐ１２）上の楕円曲線の点、Ｔ０１＝（ｘ０１，ｙ０１）、Ｔ０２＝（ｘ０２，ｙ０２）、Ｐ０＝（ｘ０Ｐ，ｙ０Ｐ）、ｅを点Ｐ０と点Ｑ０を入力とし有限体Ｆ（ｐ１２）上の元を出力するペアリング演算を示す記号、ｆを有限体Ｆ（ｐ１２）上の元、Ｌ０を点Ｔ０１と点Ｔ０２を通る直線をＰ０で評価した式評価、α０，β０，γ０，Ａ０，Ｂ０をＦ（ｐ２）上の元、ｓ０Ａとｓ０Ｂをあらかじめ定めた定数、ｄ０を小整数とし、
Ｆ（ｐ１２）上の元を、ｃ０，ｃ１，ｃ２，ｃ３，ｃ４，ｃ５はＦ（ｐ２）上の元である係数、ｖ３＝ξ、ｗ２＝ｖ、ξは平方非剰余かつ立方非剰余として、
ｃ０＋ｃ１ｖ＋ｃ２ｖ２＋ｃ３ｗ＋ｃ４ｖｗ＋ｃ５ｖ２ｗ
のように表現することとし、
式評価Ｌ０が、
Ｌ０＝α０ｙ０Ｐ＋β０ｘ０ｐｗ＋γ０ｖｗ
のときに、
Ａ０＝ｓ０Ａ（α０／β０）、Ｂ０＝ｓ０Ｂ（γ０／β０）とし、
Ａ０と所定の関係を持つ値であるａ０と、Ｂ０と所定の関係を持つ値であるｂ０を記録した記録部と、
ｘ０Ｐ’＝１／（ｓ０Ｂ・ｘ０Ｐ）、ｙ０Ｐ’＝ｙ０Ｐ／（ｓ０Ａ・ｘ０Ｐ）を計算する入力変換部と、
前記記録部からａ０とｂ０を読み出し、ａ０とｂ０を用いて、
Ｌ０’＝ｄ０ｖＮ（Ａ０ｙ０Ｐ’＋ｗ＋Ｂ０ｘ０Ｐ’ｖｗ）
のように式評価Ｌ０’を生成する式評価生成部と、
ｆ，Ｌ０’を入力とし、ｆ×Ｌ０’の演算結果を出力する式評価演算部と、
を備えることを特徴とするペアリング演算装置。
【請求項２】
群Ｇ１の元Ｐ０と群Ｇ２の元Ｑ０とのペアリングｅ（Ｐ０，Ｑ０）を求めるペアリング演算装置であって、
ｐを素数または素数のべき乗、Ｎをあらかじめ定めた０，１，２のいずれかの整数、ｋを正の整数、Ｆ（ｐ）とＦ（ｐｋ）を有限体、Ｐ０を有限体Ｆ（ｐ）上の楕円曲線の点、Ｑ０を有限体Ｆ（ｐ１２）上の楕円曲線の点であって固定された点、Ｔ０１とＴ０２をＱ０に対応する有限体Ｆ（ｐ１２）上の楕円曲線の点、Ｔ０１＝（ｘ０１，ｙ０１）、Ｔ０２＝（ｘ０２，ｙ０２）、Ｐ０＝（ｘ０Ｐ，ｙ０Ｐ）、ｅを点Ｐ０と点Ｑ０を入力とし有限体Ｆ（ｐ１２）上の元を出力するペアリング演算を示す記号、ｆを有限体Ｆ（ｐ１２）上の元、点Ｔ０１と点Ｔ０２とが異なる場合はλ０＝（ｙ０２−ｙ０１）／（ｘ０２−ｘ０１）、点Ｔ０１と点Ｔ０２とが同じ場合はλ０＝３ｘ０１２／２ｙ０１、ｄ０を小整数とし、
Ｆ（ｐ１２）上の元を、ｃ０，ｃ１，ｃ２，ｃ３，ｃ４，ｃ５はＦ（ｐ２）上の元である係数、ｖ３＝ξ、ｗ２＝ｖ、ξは平方非剰余かつ立方非剰余として、
ｃ０＋ｃ１ｖ＋ｃ２ｖ２＋ｃ３ｗ＋ｃ４ｖｗ＋ｃ５ｖ２ｗ
のように表現することとし、
（−１／λ０）と所定の関係を持つ値であるａ０と、（−（λ０ｘ０１−ｙ０１）／λ０）と所定の関係を持つ値であるｂ０を記録した記録部と、
ｘ０Ｐ’＝１／ｘ０Ｐ、ｙ０Ｐ’＝ｙ０Ｐ／ｘ０Ｐを計算する入力変換部と、
前記記録部からａ０とｂ０を読み出し、ａ０とｂ０を用いて、
Ｌ０’＝ｄ０ｖＮ（（−１／λ０）ｙ０Ｐ’＋ｗ＋（−（λ０ｘ０１−ｙ０１）／λ０）ｘ０Ｐ’ｖｗ）
のように式評価Ｌ０’を生成する式評価生成部と、
ｆ，Ｌ０’を入力とし、ｆ×Ｌ０’の演算結果を出力する式評価演算部と、
を備えることを特徴とするペアリング演算装置。
【請求項３】
ｍ個の群Ｇ１の元Ｐ０，…，Ｐｍ−１と群Ｇ２の元Ｑ０，…，Ｑｍ−１とのマルチペアリングｅ（Ｐ０，Ｑ０）×ｅ（Ｐ１，Ｑ１）×…×ｅ（Ｐｍ−１，Ｑｍ−１）を求めるマルチペアリング演算装置であって、
ｍを２以上の整数、ｊを０以上ｍ−１以下の整数、ｐを素数または素数のべき乗、Ｎを０，１，２のいずれかの整数、ｋを正の整数、Ｆ（ｐ）とＦ（ｐｋ）を有限体、Ｐｊを有限体Ｆ（ｐ）上の楕円曲線の点、Ｑｊを有限体Ｆ（ｐ１２）上の楕円曲線の点であって固定された点、Ｔｊ１とＴｊ２をＱｊに対応する有限体Ｆ（ｐ１２）上の楕円曲線の点、Ｔｊ１＝（ｘｊ１，ｙｊ１）、Ｔｊ２＝（ｘｊ２，ｙｊ２）、Ｐｊ＝（ｘｊＰ，ｙｊＰ）、ｅを点Ｐｊと点Ｑｊを入力とし有限体Ｆ（ｐ１２）上の元を出力するペアリング演算を示す記号、ｆを有限体Ｆ（ｐ１２）上の元、Ｌｊを点Ｔｊ１と点Ｔｊ２を通る直線をＰｊで評価した式評価、αｊ，βｊ，γｊ，Ａｊ，ＢｊをＦ（ｐ２）上の元、ｓｊＡとｓｊＢをあらかじめ定めた定数、ｄｊを小整数とし、
Ｆ（ｐ１２）上の元を、ｃ０，ｃ１，ｃ２，ｃ３，ｃ４，ｃ５はＦ（ｐ２）上の元である係数、ｖ３＝ξ、ｗ２＝ｖ、ξは平方非剰余かつ立方非剰余として、
ｃ０＋ｃ１ｖ＋ｃ２ｖ２＋ｃ３ｗ＋ｃ４ｖｗ＋ｃ５ｖ２ｗ
のように表現することとし、
式評価Ｌｊが、
Ｌｊ＝αｊｙｊＰ＋βｊｘｊｐｗ＋γｊｖｗ
のときに、
ｊ＝０,…,ｍ−１について、Ａｊ＝ｓｊＡ（αｊ／βｊ）、Ｂｊ＝ｓｊＢ（γｊ／βｊ）とし、
ｊ＝０,…,ｍ−１について、Ａｊと所定の関係を持つ値であるａｊと、Ｂｊと所定の関係を持つ値であるｂｊを記録した記録部と、
ｊ＝０,…,ｍ−１について、ｘｊＰ’＝１／（ｓｊＢ・ｘｊＰ）、ｙｊＰ’＝ｙｊＰ／（ｓｊＡ・ｘｊＰ）を計算する入力変換部と、
ｊ＝０,…,ｍ−１のすべてについて、記録部からａｊとｂｊを読み出し、ａｊとｂｊを用いて、
Ｌｊ’＝ｄｊｖＮ（ＡｊｙｊＰ’＋ｗ＋ＢｊｘｊＰ’ｖｗ）
のように式評価Ｌｊ’を生成する式評価生成部と、
ｆ，Ｌ０’，Ｌ１’，…，Ｌｍ−１’を入力とし、ｆ×Ｌ０’×…×Ｌｍ−１’の演算結果を出力する式評価演算部と、
を備えることを特徴とするマルチペアリング演算装置。
【請求項４】
ｍ個の群Ｇ１の元Ｐ０，…，Ｐｍ−１と群Ｇ２の元Ｑ０，…，Ｑｍ−１とのマルチペアリングｅ（Ｐ０，Ｑ０）×ｅ（Ｐ１，Ｑ１）×…×ｅ（Ｐｍ−１，Ｑｍ−１）を求めるマルチペアリング演算装置であって、
ｍを２以上の整数、ｊを０以上ｍ−１以下の整数、ｐを素数または素数のべき乗、Ｎを０，１，２のいずれかの整数、ｋを正の整数、Ｆ（ｐ）とＦ（ｐｋ）を有限体、Ｐｊを有限体Ｆ（ｐ）上の楕円曲線の点、Ｑｊを有限体Ｆ（ｐ１２）上の楕円曲線の点であって固定された点、Ｔｊ１とＴｊ２をＱｊに対応する有限体Ｆ（ｐ１２）上の楕円曲線の点、Ｔｊ１＝（ｘｊ１，ｙｊ１）、Ｔｊ２＝（ｘｊ２，ｙｊ２）、Ｐｊ＝（ｘｊＰ，ｙｊＰ）、ｅを点Ｐｊと点Ｑｊを入力とし有限体Ｆ（ｐ１２）上の元を出力するペアリング演算を示す記号、ｆを有限体Ｆ（ｐ１２）上の元、点Ｔｊ１と点Ｔｊ２とが異なる場合はλｊ＝（ｙｊ２−ｙｊ１）／（ｘｊ２−ｘｊ１）、点Ｔｊ１と点Ｔｊ２とが同じ場合はλｊ＝３ｘｊ１２／２ｙｊ１、ｄｊを小整数とし、
Ｆ（ｐ１２）上の元を、ｃ０，ｃ１，ｃ２，ｃ３，ｃ４，ｃ５はＦ（ｐ２）上の元である係数、ｖ３＝ξ、ｗ２＝ｖ、ξは平方非剰余かつ立方非剰余として、
ｃ０＋ｃ１ｖ＋ｃ２ｖ２＋ｃ３ｗ＋ｃ４ｖｗ＋ｃ５ｖ２ｗ
のように表現することとし、
ｊ＝０,…,ｍ−１について、（−１／λｊ）と所定の関係を持つ値であるａｊと、（−（λｊｘｊ１−ｙｊ１）／λｊ）と所定の関係を持つ値であるｂｊを記録した記録部と、
ｊ＝０,…,ｍ−１について、ｘｊＰ’＝１／ｘｊＰ、ｙｊＰ’＝ｙｊＰ／ｘｊＰを計算する入力変換部と、
ｊ＝０,…,ｍ−１のすべてについて、記録部からａｊとｂｊを読み出し、ａｊとｂｊを用いて、
Ｌｊ’＝ｄｊｖＮ（（−１／λｊ）ｙｊＰ’＋ｗ＋（−（λｊｘｊ１−ｙｊ１）／λｊ）ｘｊＰ’ｖｗ）
のように式評価Ｌｊ’を生成する式評価生成部と、
ｆ，Ｌ０’，Ｌ１’，…，Ｌｍ−１’を入力とし、ｆ×Ｌ０’×…×Ｌｍ−１’の演算結果を出力する式評価演算部と、
を備えることを特徴とするマルチペアリング演算装置。
【請求項５】
請求項３または４記載のマルチペアリング演算装置であって、
前記式評価演算部は、
選択されていない式評価Ｌ０’，Ｌ１’，…，Ｌｍ−１’の中から４個を選択し、ｈ０，ｈ１，ｈ２，ｈ３とする式評価選択部と、
Ｌ”←ｈ０×ｈ１×ｈ２×ｈ３  を計算する式評価乗算部と、
ｆ←ｆ×Ｌ”  を計算し、ｆを更新する元乗算部と、
Ｌ０’，Ｌ１’，…，Ｌｍ−１’の中で、前記式評価選択部で選択されていない式評価の数が４より少なくなるまで、前記式評価選択部と前記式評価乗算部と前記元乗算部の処理を繰り返す演算制御部と、
Ｌ０’，Ｌ１’，…，Ｌｍ−１’の中で、前記式評価選択部で選択されていない式評価がある場合は、選択されていない式評価のすべてをｆに乗算し、乗算結果にｆを更新する未選択乗算部と、
を備え、ｆを演算結果として出力する
ことを特徴とするマルチペアリング演算装置。
【請求項６】
請求項５記載のマルチペアリング演算装置であって、
前記式評価乗算部は、
Ｌ０’←ｈ０×ｈ１，  Ｌ１’←ｈ２×ｈ３
を計算し、
Ｌ”←Ｌ０’×Ｌ１’
のようにＬ”を計算する
ことを特徴とするマルチペアリング演算装置。
【請求項７】
請求項１もしくは２記載のペアリング演算装置、請求項３〜６のいずれかに記載されたマルチペアリング演算装置のいずれかの演算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術のためのペアリング演算装置、マルチペアリング演算装置、プログラムに関する。
【背景技術】
【０００２】
図１は、Barreto-Naehrig楕円曲線（ＢＮ曲線，Ｅ：ｙ２＝ｘ３＋ｂ，ｂ≠０∈Ｆ（ｐ））上のOptimal Ateペアリングの従来のアルゴリズムを示す図である。そして、このようなペアリング演算の入力の一方の元が固定されている場合に、事前に計算可能な値を事前に計算して記録しておくことで、元が入力されたときの計算速度を高速化する技術として非特許文献１が知られている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】C. Costello, D. Stebila, "Fixed Argument Pairings," LATINCRYPT 2010, LNCS 6212, pp. 92-108, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ペアリング暗号では、ＩＤベース暗号や関数型暗号など利便性の高い暗号方式が構成できる。これらの暗号方式ではペアリング演算が必要となるため、実用的なシステムの構成のためには、ペアリング演算が高速に計算できることが求められる。ペアリング暗号システムでは、事前に秘密情報（例えば，秘密鍵）が配布されており、ペアリング演算の際に秘密情報を入力の片方として計算することがある。この場合、入力の一方が固定であることを利用して、オフライン事前計算によりペアリング演算の高速化が可能となる。また関数型暗号などの高機能な暗号方式では、複数のペアリング演算の積を計算するマルチペアリング演算で片方の入力が固定である場合もあり、この場合でも、オフライン事前計算によりマルチペアリング演算の高速化が可能となる。しかしながら、暗号システムの高機能化が進んでいる状況から、さらなる高速化が求められている。
【０００５】
本発明は、楕円曲線上のペアリングについて従来技術を改良し、さらに計算速度を高速化することを目的とする。
【課題を解決するための手段】
【０００６】
まず、ｍを２以上の整数、ｊを０以上ｍ−１以下の整数、ｐを素数または素数のべき乗、Ｎをあらかじめ定めた０，１，２のいずれかの整数、ｋを正の整数、Ｆ（ｐ）とＦ（ｐｋ）を有限体、Ｐｊを有限体Ｆ（ｐ）上の楕円曲線の点、Ｑｊを有限体Ｆ（ｐ１２）上の楕円曲線の点であって固定された点、Ｔｊ１とＴｊ２をＱｊに対応する有限体Ｆ（ｐ１２）上の楕円曲線の点、Ｔｊ１＝（ｘｊ１，ｙｊ１）、Ｔｊ２＝（ｘｊ２，ｙｊ２）、Ｐｊ＝（ｘｊＰ，ｙｊＰ）、ｅを点Ｐｊと点Ｑｊを入力とし有限体Ｆ（ｐ１２）上の元を出力するペアリング演算を示す記号、ｆを有限体Ｆ（ｐ１２）上の元、Ｌｊを点Ｔｊ１と点Ｔｊ２を通る直線をＰｊで評価した式評価、αｊ，βｊ，γｊ，Ａｊ，ＢｊをＦ（ｐ２）上の元、ｄｊを小整数とし、
Ｆ（ｐ１２）上の元を、ｃ０，ｃ１，ｃ２，ｃ３，ｃ４，ｃ５はＦ（ｐ２）上の元である係数、ｖ３＝ξ、ｗ２＝ｖ、ξは平方非剰余かつ立方非剰余として、
ｃ０＋ｃ１ｖ＋ｃ２ｖ２＋ｃ３ｗ＋ｃ４ｖｗ＋ｃ５ｖ２ｗ
のように表現することとする。また、式評価Ｌｊは、
Ｌｊ＝αｊｙｊＰ＋βｊｘｊｐｗ＋γｊｖｗ
である。
【０００７】
本発明のペアリング演算装置は、群Ｇ１の元Ｐ０と群Ｇ２の元Ｑ０とのペアリングｅ（Ｐ０，Ｑ０）を求める。本発明のペアリング演算装置は、記録部、入力変換部、式評価生成部、式評価演算部を備える。記録部は、Ａ０と所定の関係を持つ値であるａ０と、Ｂ０と所定の関係を持つ値であるｂ０を記録している。入力変換部は、ｘ０Ｐとｙ０Ｐから、ｘ０Ｐ’＝γ０／（Ｂ０・β０・ｘ０Ｐ）、ｙ０Ｐ’＝（α０・ｙ０Ｐ）／（Ａ０・β０・ｘ０Ｐ）が成り立つｘ０Ｐ’とｙ０Ｐ’を求める。式評価生成部は、記録部からａ０とｂ０を読み出し、ａ０とｂ０を用いて、
Ｌ０’＝ｄ０ｖＮ（Ａ０ｙ０Ｐ’＋ｗ＋Ｂ０ｘ０Ｐ’ｖｗ）
のように式評価Ｌ０’を生成する。式評価演算部は、ｆ，Ｌ０’を入力とし、ｆ×Ｌ０’の演算結果を出力する。
【０００８】
本発明のマルチペアリング演算装置は、ｍ個の群Ｇ１の元Ｐ０，…，Ｐｍ−１と群Ｇ２の元Ｑ０，…，Ｑｍ−１とのマルチペアリングｅ（Ｐ０，Ｑ０）×ｅ（Ｐ１，Ｑ１）×…×ｅ（Ｐｍ−１，Ｑｍ−１）を求める。本発明のマルチペアリング演算装置は、記録部、式評価生成部、式評価演算部を備える。記録部は、ｊ＝０,…,ｍ−１について、Ａｊと所定の関係を持つ値であるａｊと、Ｂｊと所定の関係を持つ値であるｂｊを記録している。入力変換部は、ｊ＝０,…,ｍ−１について、ｘｊＰとｙｊＰから、ｘｊＰ’＝γｊ／（Ｂｊ・βｊ・ｘｊＰ）、ｙｊＰ’＝（αｊ・ｙｊＰ）／（Ａｊ・βｊ・ｘｊＰ）が成り立つｘｊＰ’とｙｊＰ’を求める。式評価生成部は、ｊ＝０,…,ｍ−１のすべてについて、記録部からａｊとｂｊを読み出し、ａｊとｂｊを用いて、
Ｌｊ’＝ｄｊｖＮ（ＡｊｙｊＰ’＋ｗ＋ＢｊｘｊＰ’ｖｗ）
のように式評価Ｌｊ’を生成する。式評価演算部は、ｆ，Ｌ０’，Ｌ１’，…，Ｌｍ−１’を入力とし、ｆ×Ｌ０’×…×Ｌｍ−１’の演算結果を出力する。
【発明の効果】
【０００９】
本発明のペアリング演算装置とマルチペアリング装置によれば、点Ｑｊが固定されていることを利用してあらかじめＡｊと所定の関係を持つ値であるａｊと、Ｂｊと所定の関係を持つ値であるｂｊを記録しておく。そして、可変である点Ｐｊが入力されると、
Ｌｊ’＝ｄｊｖＮ（ＡｊｙｊＰ’＋ｗ＋ＢｊｘｊＰ’ｖｗ）
のように式評価Ｌｊ’を生成し、式評価の乗算を行う。このような形式の式評価Ｌｊ’であれば、有限体Ｆ（ｐ１２）上の任意の元との乗算において、Ｌｊよりも有限体Ｆ（ｐ２）上の乗算回数を少なくできる。つまり、式評価をＬｊからＬｊ’に変更したことで計算コストが増えてしまう計算は、点Ｑｊが固定されていることを利用して事前に計算しておき、点Ｐｊが入力された後の計算コストを削減している。したがって、点Ｐｊが入力されてからの計算速度を高速化できる。
【図面の簡単な説明】
【００１０】
【図１】Barreto-Naehrig楕円曲線上のOptimal Ateペアリングの従来のアルゴリズムを示す図。
【図２】式５を用いた場合のOptimal Ateペアリングのアルゴリズム（Algorithm 2）を示す図。
【図３】図２のステップ７，１２，２１，２４の乗算のアルゴリズムの具体例（Algorithm 3）を示す図。
【図４】Ｆ（ｐ１２）上の任意の元と式４の形式の元との乗算のアルゴリズム（Algorithm 3’）を示す図。
【図５】本発明のペアリング演算装置の機能構成例を示す図。
【図６】本発明のペアリング演算装置の入力変換と式評価演算の処理フロー例を示す図。
【図７】本発明のマルチペアリング演算装置の機能構成例を示す図。
【図８】本発明のマルチペアリング演算装置の入力変換と式評価演算の処理フローの例を示す図。
【図９】Optimal Ateペアリングにおけるマルチペアリングのアルゴリズムの例（Algorithm 4）を示す図。
【図１０】図９のステップ７，１２，２１，２４の乗算のアルゴリズムの例（Algorithm 5）を示す図。
【図１１】図１０のステップ３の計算のアルゴリズム（Algorithm 6）を示す図。
【図１２】図１０のステップ４の計算のアルゴリズム（Algorithm 7）を示す図。
【図１３】従来技術である式４の形式の式評価を用いた場合の乗算のアルゴリズムの例（Algorithm 6’）を示す図。
【図１４】図１３で求めた元同士の乗算のアルゴリズムの例（Algorithm 7’）を示す図。
【発明を実施するための形態】
【００１１】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。まず、ｍを２以上の整数、ｊを０以上ｍ−１以下の整数、ｐを素数または素数のべき乗、Ｎをあらかじめ定めた０，１，２のいずれかの整数、ｋを正の整数、Ｆ（ｐ）とＦ（ｐｋ）を有限体、Ｐｊを有限体Ｆ（ｐ）上の楕円曲線の点、Ｑｊを有限体Ｆ（ｐ１２）上の楕円曲線の点であって固定された点、Ｔｊ１とＴｊ２をＱｊに対応する有限体Ｆ（ｐ１２）上の楕円曲線の点、Ｔｊ１＝（ｘｊ１，ｙｊ１）、Ｔｊ２＝（ｘｊ２，ｙｊ２）、Ｐｊ＝（ｘｊＰ，ｙｊＰ）、ｅを点Ｐｊと点Ｑｊを入力とし有限体Ｆ（ｐ１２）上の元を出力するペアリング演算を示す記号、ｆを有限体Ｆ（ｐ１２）上の元、Ｌｊを点Ｔｊ１と点Ｔｊ２を通る直線をＰｊで評価した式評価、ｄｊを小整数とする。なお、点Ｔｊ１と点Ｔｊ２とが同一の点の場合、「点Ｔｊ１と点Ｔｊ２を通る直線」は点Ｔｊ１での接線である。また、「小整数」とは少なくとも１を含む値の小さい整数であり、例えば、任意の元ｆと小整数ｄｊとの乗算（ｄｊ×ｆ）を、任意の元ｆのｄｊ−１回の加算（ｆ＋ｆ＋…＋ｆ）で行った方が、計算コストが小さくなるような整数である。演算装置、演算方法、プログラムによって具体的な小整数は異なるが、ある演算装置が、整数ｄと元ｆとの乗算（ｄ×ｆ）を加算（ｆ＋ｆ＋…＋ｆ）に置き換えて計算している場合、その演算装置においては、整数ｄは小整数である。また、小整数ｄｊは負の整数でもよい。
【００１２】
Ｆ（ｐ１２）上の元を、ｃ０，ｃ１，ｃ２，ｃ３，ｃ４，ｃ５はＦ（ｐ２）上の元である係数、ｖ３＝ξ、ｗ２＝ｖ、ξは平方非剰余かつ立方非剰余として、
ｃ０＋ｃ１ｖ＋ｃ２ｖ２＋ｃ３ｗ＋ｃ４ｖｗ＋ｃ５ｖ２ｗ
のように表現することとする。
【００１３】
また、図１に示すアルゴリズムでは、ＴがＴ０１に相当し、Ｔ，Ｑ，Ｑ’，−Ｑ”がＴ０２に相当し、ａｏｐｔがｅに相当し、
【数１】
2015135452.tif 000003
がＬ０に相当する。また、アルゴリズムの具体例を示す図では、Ｆ（ｐｋ）は、
【数２】
2015135452.tif 000004
のように示されている。
【００１４】
＜従来技術の分析＞
ペアリング演算には、点Ｔｊ１と点Ｔｊ２と点Ｐｊに対して、点加算／２倍算と式評価の計算が含まれる。次に、具体的な座標系の例を示しながら説明する。
【００１５】
次の具体例の説明では、Barreto-Naehrig楕円曲線（ＢＮ曲線，Ｅ：ｙ２＝ｘ３＋ｂ，ｂ≠０∈Ｆ（ｐ））を用いる。ＢＮ曲線では、整数ｚに対して素数ｐとＢＮ曲線上のＦ（ｐ）有理点群の位数ｒは、
ｐ＝３６ｚ４＋３６ｚ３＋２４ｚ２＋６ｚ＋１
ｒ＝３６ｚ４＋３６ｚ３＋１８ｚ２＋６ｚ＋１
である。ＢＮ曲線では、ｒで割り切れる（ｐｋ−１）となる最小のｋは１２である。
【００１６】
拡大体Ｆ（ｐｋ）を逐次拡大により
Ｆ（ｐ２）＝Ｆ（ｐ）［ｕ］／（ｕ２−β）
Ｆ（ｐ６）＝Ｆ（ｐ２）［ｖ］／（ｖ３−ξ）
Ｆ（ｐ１２）＝Ｆ（ｐ６）［ｗ］／（ｗ２−ｖ）
ただし、ｖ３＝ξ、ｗ２＝ｖ、βは平方非剰余、ξは平方非剰余かつ立方非剰余
のように構成する。そして、Ｆ（ｐ１２）上の元Ｃを
Ｃ＝ｃ０＋ｃ１ｖ＋ｃ２ｖ２＋ｃ３ｗ＋ｃ４ｖｗ＋ｃ５ｖ２ｗ        （式１）
ただし、ｃ０，ｃ１，ｃ２，ｃ３，ｃ４，ｃ５  ∈Ｆ（ｐ２）
のように表現する。なお、６次のツイスト曲線Ｅ’は、ｙ２＝ｘ３＋ｂ／ξ  である。このとき、点（ｘ，ｙ）に対してＥ’，Ｅの同型写像（ｘ，ｙ）→（ｘｗ２，ｙｗ３）となる
Φ：Ｅ’（Ｆ（ｐ２））→Ｅ（Ｆ（ｐ１２））
が存在する。
【００１７】
Affine座標系の例
Ｔｊ１＝（ｘｊ１，ｙｊ１）、Ｔｊ２＝（ｘｊ２，ｙｊ２）、Ｐｊ＝（ｘｊＰ，ｙｊＰ）とする。λｊ＝（ｙｊ２−ｙｊ１）／（ｘｊ２−ｘｊ１）に対して、点加算と式評価（点Ｔｊ１と点Ｔｊ２とが異なる場合）は、
ｘｊ３＝λｊ２−ｘｊ１−ｘ２ｊ
ｙｊ３＝λｊ（ｘｊ１−ｘｊ３）−ｙ１ｊ
Ｌｊ＝ｙｊＰ−λｊｘｊｐｗ＋（λｊｘｊ１−ｙｊ１）ｖｗ      （式２）
となる。また、点２倍算と式評価（点Ｔｊ１と点Ｔｊ２とが同じ場合）は、λｊ＝３ｘｊ１２／２ｙｊ１に対して
ｘｊ３＝λｊ２−２ｘｊ１
ｙｊ３＝λｊ（ｘｊ１−ｘｊ３）−ｙｊ１
Ｌｊ＝ｙｊＰ−λｊｘｊｐｗ＋（λｊｘｊ１−ｙｊ１）ｖｗ      （式３）
となる。ここで、式１に示したＦ（ｐ１２）上の元Ｃはｃ０，ｃ１，ｃ２，ｃ３，ｃ４，ｃ５の６つの係数が存在するが、式２、式３に示した式評価ではその中の３つの係数がゼロであることが分かる。
【００１８】
Affine座標系の異なる形式の式評価の例
式２、式３を
ｙｊＰ’・Ｌｊ＝１−λｊｘｊｐ’ｗ＋ｙｊＰ’（λｊｘｊ１−ｙｊ１）ｖｗ      （式４）
ただし、ｘｊｐ’＝ｘｊｐ／ｙｊＰ，  ｙｊＰ’＝１／ｙｊＰ
のように変換して式評価としてもよい。このように変形しても、ｙｊＰ’の部分は最終べきの計算（図１のアルゴリズムのステップ１４）で除去されるため、ペアリング演算の結果には影響しない。式４のように変形すると、３つの係数がゼロであり１つの係数が小整数の「１」であることが分かる。
【００１９】
非特許文献１では、事前に計算可能な値を事前に計算して記録しておく考え方をこの形式に当てはめ、（−λｊ，λｊｘｊ１−ｙｊ１）を事前に計算して記録している。また、
ｘｊｐ’＝ｘｊｐ／ｙｊＰ，  ｙｊＰ’＝１／ｙｊＰ
の計算は、点Ｐｊの入力に対して１回行えばよいだけなので、点Ｐｊが入力された後の計算コストを削減できる。
【００２０】
＜本発明で利用する式評価＞
本発明では、式評価を式４とは異なる形式に変形することで、計算コストを削減する。まず、１つの式評価の具体例を示して説明する。その具体例は、
Ｌｊ’＝−１／（λｊ・ｘｊｐ）・Ｌｊ
＝（−１／λｊ）ｙｊＰ’＋ｗ＋（−（λｊｘｊ１−ｙｊ１）／λｊ）ｘｊＰ’ｖｗ  （式５）
ただし、ｘｊＰ’＝１／ｘｊＰ、  ｙｊＰ’＝ｙｊＰ／ｘｊＰ
である。この評価式の場合、（−１／λｊ，−（λｊｘｊ１−ｙｊ１）／λｊ）を事前に計算して記録しておけばよい。（−１／λｊ，−（λｊｘｊ１−ｙｊ１）／λｊ）の計算には逆元算が必要であり、乗算よりも低速な計算になるが、点Ｐｊが入力された後の計算コストには影響しない。また、点Ｐｊの入力に対して
ｘｊＰ’＝１／ｘｊＰ、  ｙｊＰ’＝ｙｊＰ／ｘｊＰ
の計算を１回行えばよい。なお、−１／（λｊ・ｘｊｐ）の部分は最終べきの計算で除去されるため、ペアリング演算の結果には影響しない。また、−１／λｊと−（λｊｘｊ１−ｙｊ１）／λｊを事前に計算して記録しておくのが最も効率的と考えられる。しかし、乗算や逆元算のような低速な計算を必要とせずに−１／λｊと−（λｊｘｊ１−ｙｊ１）／λｊを求められる別の値を記録しておいてもよい。
【００２１】
図２は、式５を用いた場合のOptimal Ateペアリングのアルゴリズム（Algorithm 2）である。また、図３は、図２のステップ７，１２，２１，２４の乗算のアルゴリズムの具体例（Algorithm 3）である。このようなアルゴリズムで、ペアリング演算ができる。図２のアルゴリズムでは、ステップ２５が最終べきの計算である。なお、図２では式評価を小文字のエルで示している。
【００２２】
次に、式４と式５の違いを説明する。図３に示したアルゴリズムは、
Ａ＝ａ０＋ａ１ｖ＋ａ２ｖ２＋ａ３ｗ＋ａ４ｖｗ＋ａ５ｖ２ｗ
のように表現できるＦ（ｐ１２）上の任意の元Ａと、
Ｂ＝ｂ０＋ｗ＋ｂ４ｖｗ
のように表現できる式５の形式の元Ｂとの乗算のアルゴリズムである。これと対比するために、図４にＦ（ｐ１２）上の任意の元と式４の形式の元との乗算のアルゴリズム（Algorithm 3’）を示す。図４では、式４の形式の元を
Ｂ＝１＋ｂ３ｗ＋ｂ４ｖｗ
と表現している。図３と図４に示したアルゴリズムでは、Ｆ（ｐ２）上の元である係数同士の乗算回数が計算コストを決める要素である。図３では、ステップ１，４，７に３回ずつ係数同士の乗算が存在するので、Ｆ（ｐ２）上の元同士の乗算は９回である。一方、図４では、ステップ１，６に４回ずつ、ステップ２，７に１回ずつ係数同士の乗算が存在するので、Ｆ（ｐ２）上の元同士の乗算は１０回である。したがって、式５の形式に変換した方が、計算コストが小さいことが分かる。
【００２３】
Ｆ（ｐ１２）上の任意の元同士の乗算の場合、単純に係数同士を組み合わせると３６個の組み合わせがあるので、３６回のＦ（ｐ２）上の元同士の乗算がある。そして、カラツバ法（Karatsuba法）を利用することで１８回の乗算で計算できることが知られている。図３や図４のアルゴリズムでは、値がゼロや小整数の係数が含まれているので、乗算回数がさらに少なくなっている。そして、式４と式５の形式は、どちらも値がゼロの係数が３つあり、１つの係数が「１」であることは同じである。したがって、乗算回数の差は、どの係数を「１」にしているかによって生じている。本発明は、どの係数を「１」にするかによって、計算コストを削減する効果を得ている。
【００２４】
同様の効果が得られる式評価
「小整数ｄｊ」は、任意の元ｆと小整数ｄｊとの乗算（ｄｊ×ｆ）を、任意の元ｆのｄｊ−１回の加算（ｆ＋ｆ＋…＋ｆ）で行った方が、計算コストが小さくなるような整数なので、「１」となっている係数の部分を他の小整数に変更しても、従来に比べれば計算コストを削減できる。したがって、
Ｌｊ’＝ｄｊ（（−１／λｊ）ｙｊＰ’＋ｗ＋（−（λｊｘｊ１−ｙｊ１）／λｊ）ｘｊＰ’ｖｗ），
で表現される式評価Ｌｊ’でも従来に比べれば計算コストを削減できる。
【００２５】
また、この式評価にｖを乗算した式評価、ｖ２を乗算した式評価でも、式５と同じようにＦ（ｐ２）上の元同士の乗算を９回にできる。つまり、
Ｌｊ’＝ｄｊ（（−１／λｊ）ｙｊＰ’ｖ＋ｖｗ＋（−（λｊｘｊ１−ｙｊ１）／λｊ）ｘｊＰ’ｖ２ｗ）
または
Ｌｊ’＝ｄｊ（（−１／λｊ）ｙｊＰ’ｖ２＋ｖ２ｗ＋（−（λｊｘｊ１−ｙｊ１）／λｊ）ｘｊＰ’ξｗ）
の場合も、従来に比べれば計算コストを削減できる。上記の内容をまとめると、
Ｌｊ’＝ｄｊｖＮ（（−１／λｊ）ｙｊＰ’＋ｗ＋（−（λｊｘｊ１−ｙｊ１）／λｊ）ｘｊＰ’ｖｗ）
のような式評価Ｌｊ’であれば同様の効果が得られる。なお、式評価Ｌｊを式評価Ｌｊ’に変換するために乗算する−ｄｊ／（λｊ・ｘｊｐ）ｖＮの部分はＦ（ｐ６）の元なので最終べきの計算で除去されるため、ペアリング演算の結果には影響しない。
【００２６】
さらに、式評価Ｌｊが式２，３以外の場合でも同様の効果が得られる場合がある。具体的には、式評価Ｌｊが
Ｌｊ＝αｊｙｊＰ＋βｊｘｊｐｗ＋γｊｖｗ      （式６）
ただし、αｊ，βｊ，γｊはＦ（ｐ２）上の元
の場合には、
Ｌｊ’＝１／（βｊ・ｘｊｐ）・Ｌｊ
＝（αｊ・ｙｊＰ）／（βｊ・ｘｊＰ））＋ｗ＋（γｊ／（βｊ・ｘｊＰ））ｖｗ  （式７）
のようにｗの係数が１になるように変形すれば、式５の場合と同じようにＦ（ｐ２）上の元同士の乗算を９回にできる。また、ｖまたはｖ２をさらに乗算しても同様である。つまり、ＡｊとＢｊをＦ（ｐ２）上の元とし、式評価を
Ｌｊ’＝ｄｊｖＮ（ＡｊｙｊＰ’＋ｗ＋ＢｊｘｊＰ’ｖｗ）
ただし、Ａｊ＝ｓｊＡ（αｊ／βｊ）、Ｂｊ＝ｓｊＢ（γｊ／βｊ）
ｘｊＰ’＝１／（ｓｊＢ・ｘｊＰ）、ｙｊＰ’＝ｙｊＰ／（ｓｊＡ・ｘｊＰ）
ｓｊＡとｓｊＢはあらかじめ定めた定数
のように変換できれば、同様の効果が得られる。ｓｊＡ＝１、ｓｊＢ＝１の場合が最も簡単な計算になると考えるが、ｘ０Ｐ’とｙ０Ｐ’の計算は図２のアルゴリズムのステップ２に示すように、ステップ３以下の繰り返し処理の前に１回行っているだけである。このように、点Ｐｊの入力に対して１回行うだけなので、ｓｊＡとｓｊＢの場合は小整数に限らなくても、点Ｐｊの入力後の計算コストは従来よりも小さくできる。なお、Ｆ（ｐ６）上の元を乗算することで式評価Ｌｊを式評価Ｌｊ’に変換すれば、乗算した元の部分は最終べきの計算で除去されるため、ペアリング演算の結果には影響しない。
【実施例１】
【００２７】
図５に本発明のペアリング演算装置の機能構成例を示す。また、図６に本発明のペアリング演算装置の入力変換と式評価演算の処理フロー例を示す。ペアリング演算装置１０は、群Ｇ１の元Ｐ０と群Ｇ２の元Ｑ０とのペアリングｅ（Ｐ０，Ｑ０）を求める。ペアリング演算装置１０は、記録部５０が事前計算の結果を記録していることと、入力変換部１５、式評価処理手段２０を有することを特徴としており、点加算や点２倍算などのその他の処理を行う構成部も有するが、それらは従来技術と同じである。図５，６では従来技術と同じ構成部は省略している。式評価処理手段２０は、式評価生成部３０と式評価演算部４０からなる。
【００２８】
記録部５０は、（−１／λ０）と所定の関係を持つ値であるａ０と、（−（λ０ｘ０１−ｙ０１）／λ０）と所定の関係を持つ値であるｂ０を記録している。上述のとおり、ａ０＝−１／λ０、ｂ０＝−（λ０ｘ０１−ｙ０１）／λ０とするのが最も効率的と考える。しかし、例えば、（−１／λ０）に定数を加算した値をａ０として記憶しておき、読み出した後にその定数を減算して（−１／λ０）を求めても、計算コストへの影響は小さい。よって、乗算や逆元算のような低速な計算を必要とせずに−１／λ０と−（λ０ｘ０１−ｙ０１）／λ０を求められる別の値をａ０とｂ０として記録しておいてもよい。ここでは、「所定の関係を持つ値」は、低速な計算を必要とせずに−１／λ０と−（λ０ｘ０１−ｙ０１）／λ０を求めることができる値の意味である。
【００２９】
入力変換部１５は、ｘ０Ｐ’＝１／ｘ０Ｐ、ｙ０Ｐ’＝ｙ０Ｐ／ｘ０Ｐを計算する（Ｓ１５）。式評価生成部３０は、記録部５０からａ０とｂ０を読み出し、ａ０とｂ０を用いて、
Ｌ０’＝ｄ０ｖＮ（（−１／λ０）ｙ０Ｐ’＋ｗ＋（−（λ０ｘ０１−ｙ０１）／λ０）ｘ０Ｐ’ｖｗ）
のように式評価Ｌ０’を生成する（Ｓ３０）。上述のとおり、ｄ０＝１，Ｎ＝０が最も効率的と考えるが、ｄ０ｖＮを乗算した式評価Ｌ０’を生成してもよい。式評価演算部４０は、ｆ，Ｌ０’を入力とし、ｆ×Ｌ０’の演算結果を出力する（Ｓ４０）。例えば、図３に示したアルゴリズムで計算すればよい。また、ステップＳ３０、Ｓ４０が式評価の処理（Ｓ２０）である。なお、図２では、ステップ２がＳ１５に、ステップ６，１１，２０，２３がＳ３０に、ステップ７，１２，２１，２４がＳ４０に相当する。
【００３０】
ペアリング演算装置１０によれば、式評価Ｌ０’を用いているので、有限体Ｆ（ｐ１２）上の任意の元とＬ０’との乗算において、有限体Ｆ（ｐ２）上の乗算回数を少なくできる。つまり、式評価を変更したことで計算コストが増えてしまう計算は、点Ｑ０が固定されていることを利用して事前に計算しておき、点Ｐ０が入力された後の計算コストを削減している。したがって、点Ｐ０が入力されてからの計算速度を高速化できる。
【００３１】
［変形例］
さらに、上述のとおり、式評価が式６のように、
Ｌｊ＝αｊｙｊＰ＋βｊｘｊｐｗ＋γｊｖｗ
の場合には、式評価を
Ｌｊ’＝ｄｊｖＮ（ＡｊｙｊＰ’＋ｗ＋ＢｊｘｊＰ’ｖｗ）
ただし、Ａｊ＝ｓｊＡ（αｊ／βｊ）、Ｂｊ＝ｓｊＢ（γｊ／βｊ）
ｘｊＰ’＝１／（ｓｊＢ・ｘｊＰ）、ｙｊＰ’＝ｙｊＰ／（ｓｊＡ・ｘｊＰ）
ｓｊＡとｓｊＢはあらかじめ定めた定数
のように変形すれば同様の効果が得られる。したがって、図５に示したペアリング演算装置と、図６に示したペアリング演算装置の入力変換と式評価演算の処理フローは、以下のとおりでもよい。ただし、Ａ０とＢ０をＦ（ｐ２）上の元とする。
【００３２】
ペアリング演算装置１０は、群Ｇ１の元Ｐ０と群Ｇ２の元Ｑ０とのペアリングｅ（Ｐ０，Ｑ０）を求める。ペアリング演算装置１０は、記録部５０が事前計算の結果を記録していることと、入力変換部１５、式評価処理手段２０を有することを特徴としている。式評価処理手段２０は、式評価生成部３０と式評価演算部４０からなる。
【００３３】
Ａ０＝ｓ０Ａ（α０／β０）、Ｂ０＝ｓ０Ｂ（γ０／β０）とする。そして、記録部５０は、Ａ０と所定の関係を持つ値であるａ０と、Ｂ０と所定の関係を持つ値であるｂ０を記録している。ａ０＝Ａ０、ｂ０＝Ｂ０とするのが最も効率的と考える。しかし、例えば、Ａ０に定数を加算した値をａ０として記憶しておき、読み出した後にその定数を減算してＡ０を求めても、計算コストへの影響は小さい。よって、乗算や逆元算のような低速な計算を必要とせずにＡ０とＢ０を求められる別の値をａ０とｂ０として記録しておいてもよい。ここでは、「所定の関係を持つ値」は、低速な計算を必要とせずにＡ０とＢ０を求めることができる値の意味である。
【００３４】
入力変換部１５は、ｘ０Ｐ’＝１／（ｓ０Ｂ・ｘ０Ｐ）、ｙ０Ｐ’＝ｙ０Ｐ／（ｓ０Ａ・ｘ０Ｐ）を計算する（Ｓ１５）。式評価生成部３０は、記録部５０からａ０とｂ０を読み出し、ａ０とｂ０を用いて、
Ｌ０’＝ｄ０ｖＮ（Ａ０ｙ０Ｐ’＋ｗ＋Ｂ０ｘ０Ｐ’ｖｗ）
のように式評価Ｌ０’を生成する（Ｓ３０）。ｄ０＝１，Ｎ＝０が最も効率的と考えるが、ｄ０ｖＮを乗算した式評価Ｌ０’を生成してもよい。式評価演算部４０は、ｆ，Ｌ０’を入力とし、ｆ×Ｌ０’の演算結果を出力する（Ｓ４０）。
【実施例２】
【００３５】
図７に本発明のマルチペアリング演算装置の機能構成例を、図８に本発明のマルチペアリング演算装置の入力変換と式評価演算の処理フローの例を示す。マルチペアリング演算装置６０は、ｍ個の群Ｇ１の元Ｐ０，…，Ｐｍ−１と群Ｇ２の元Ｑ０，…，Ｑｍ−１とのマルチペアリングｅ（Ｐ０，Ｑ０）×ｅ（Ｐ１，Ｑ１）×…×ｅ（Ｐｍ−１，Ｑｍ−１）を求める。マルチペアリング演算装置６０は、記録部９０が事前計算の結果を記録していることと、入力変換部６５、式評価処理手段７０を有することを特徴としており、点加算や点２倍算などのその他の処理を行う構成部も有するが、それらは従来技術と同じである。図７，８では従来技術と同じ構成部は省略している。式評価処理手段７０は、式評価生成部８０と式評価演算部１００からなる。
【００３６】
記録部９０は、ｊ＝０,…,ｍ−１について、（−１／λｊ）と所定の関係を持つ値であるａｊと、（−（λｊｘｊ１−ｙｊ１）／λｊ）と所定の関係を持つ値であるｂｊを記録している。上述のとおり、ａｊ＝−１／λｊ、ｂｊ＝−（λｊｘｊ１−ｙｊ１）／λｊとするのが最も効率的と考える。しかし、乗算や逆元算のような低速な計算を必要とせずに−１／λｊと−（λｊｘｊ１−ｙｊ１）／λｊを求められる別の値をａｊとｂｊとして記録しておいてもよい。ここでは、「所定の関係を持つ値」は、低速な計算を必要とせずに−１／λｊと−（λｊｘｊ１−ｙｊ１）／λｊを求めることができる値の意味である。
【００３７】
入力変換部６５は、ｊ＝０,…,ｍ−１について、ｘｊＰ’＝１／ｘｊＰ、ｙｊＰ’＝ｙｊＰ／ｘｊＰを計算する（Ｓ６５）。式評価生成部８０は、ｊ＝０,…,ｍ−１のすべてについて、記録部からａｊとｂｊを読み出し、ａｊとｂｊを用いて、
Ｌｊ’＝ｄｊｖＮ（（−１／λｊ）ｙｊＰ’＋ｗ＋（−（λｊｘｊ１−ｙｊ１）／λｊ）ｘｊＰ’ｖｗ）
のように式評価Ｌｊ’を生成する（Ｓ８０）。なお、Ｎはあらかじめ定めた０，１，２のいずれかの整数であり、ｊ＝０,…,ｍ−１のすべてについて同じ値である。上述のとおり、ｄ０,…,ｄｍ−１＝１，Ｎ＝０が最も効率的と考えるが、ｄ０ｖＮ,…,ｄｍ−１ｖＮを乗算した式評価Ｌ０’，Ｌ１’，…，Ｌｍ−１’を生成してもよい。
【００３８】
式評価演算部１００は、ｆ，Ｌ０’，Ｌ１’，…，Ｌｍ−１’を入力とし、ｆ×Ｌ０’×…×Ｌｍ−１’の演算結果を出力する（Ｓ１００）。ステップＳ８０、Ｓ１００が式評価の処理（Ｓ７０）である。ステップＳ１００では、
ｆ←ｆ×Ｌｊ’
の処理を、ｊ＝０，…，ｍ−１について繰り返せば、実施例１のペアリング演算装置１０と同様の効果が得られる。
【００３９】
また、式評価にゼロの係数があることを利用すれば、さらに計算コストを削減することができる。その場合は、式評価演算部１００は、式評価選択部１１０、式評価乗算部１２０、元乗算部１３０、演算制御部１４０、未選択乗算部１５０を備える。式評価選択部１１０は、選択されていない式評価Ｌ０’，Ｌ１’，…，Ｌｍ−１’の中から４個を選択し、ｈ０，ｈ１，ｈ２，ｈ３とする（Ｓ１１０）。
【００４０】
式評価乗算部１２０は、
Ｌ”←ｈ０×ｈ１×ｈ２×ｈ３
を計算する（Ｓ１２０）。式評価乗算部１２０は、ｈ０，ｈ１，ｈ２，ｈ３をゼロまたは小整数の係数を含む元同士の演算がより多くなるように工夫して乗算すればよい。例えば、
Ｈ０’←ｈ０×ｈ１，  Ｈ１’←ｈ２×ｈ３
Ｌ”←Ｈ０’×Ｈ１’
のようにＬ”を計算すればよい。
【００４１】
元乗算部１３０は、
ｆ←ｆ×Ｌ”
を計算し、ｆを更新する（Ｓ１３０）。演算制御部１４０は、Ｌ０’，Ｌ１’，…，Ｌｍ−１’の中で、式評価選択部１１０で選択されていない式評価の数が４より少なくなるまで、式評価選択部１１０と式評価乗算部１２０と元乗算部１３０の処理（Ｓ１１０，Ｓ１２０，Ｓ１３０）を繰り返す（Ｓ１４０）。未選択乗算部１５０は、Ｌ０’，Ｌ１’，…，Ｌｍ−１’の中で、式評価選択部で選択されていない式評価がある場合は、選択されていない式評価のすべてをｆに乗算し、乗算結果にｆを更新する（Ｓ１５０）。式評価演算部１００は、Ｌ０，Ｌ１，…，Ｌｍ−１のすべてを乗算されたｆを演算結果として出力する。
【００４２】
マルチペアリング演算装置６０によれば、マルチペアリング演算の処理に含まれるｆ×Ｌ０×…×Ｌｍ−１の演算において、まずゼロまたは小整数の係数を含む式評価Ｌ０，Ｌ１，…，Ｌｍ−１の中から４個の式評価を選択して乗算する処理を繰り返すので、係数にゼロや小整数を持つ元同士の演算を増やせる。したがって、計算コストを削減でき、計算速度を高速化できる。
【００４３】
＜アルゴリズムの具体例＞
図９に、Optimal Ateペアリングにおけるマルチペアリングのアルゴリズムの例（Algorithm 4）を示す。式評価処理手段７０の処理は、図９のアルゴリズムのステップ５〜１４，１９〜２４に適用される。図１０に図９のステップ７，１２，２１，２４の乗算のアルゴリズムの例（Algorithm 5）を示す。図１１は図１０のステップ３の計算のアルゴリズム（Algorithm 6）、図１２は図１０のステップ４の計算のアルゴリズム（Algorithm 7）である。なお、図１０のステップ９は、上述の図３に示したアルゴリズム（algorithm 3）を用いればよい。
【００４４】
図１０のステップ３では、ｈ０，ｈ１，ｈ２，ｈ３として
【数３】
2015135452.tif 000005
が選択され、
Ｈ０’←ｈ０×ｈ１，  Ｈ１’←ｈ２×ｈ３
の計算が行われる。そして、ステップ４で
Ｌ”←Ｈ０’×Ｈ１’
のようにＬ”が求められている。つまり、ステップ３の式評価の選択部分がＳ１１０に相当し、ステップ３のＨ０’とＨ１’の計算の部分と、ステップ４がＳ１２０に相当する。また、ステップ５がＳ１３０に相当し、ステップ１，２，６がＳ１４０に相当し、ステップ７〜１０がＳ１５０に相当する。
【００４５】
式４の形式の４つの式評価を、図４に示された従来の乗算方法でＦ（ｐ１２）上の任意の元ｆに乗算するときに、
ｆ←ｆ×Ｌｊ’
の処理を４回繰り返した場合、Ｆ（ｐ２）上の元同士の乗算は４０回（４×１０）である。一方、式５の形式の４つの式評価を、図３に示された従来の乗算方法でＦ（ｐ１２）上の任意の元ｆに乗算するときに、
ｆ←ｆ×Ｌｊ’
の処理を４回繰り返した場合、Ｆ（ｐ２）上の元同士の乗算は３６回（４×９）である。したがって、式評価演算部１００が式評価選択部１１０、式評価乗算部１２０、元乗算部１３０、演算制御部１４０、未選択乗算部１５０を備えなくても、従来に比べれば計算コスト削減の効果がある。
【００４６】
そして、式５の形式の４つの式評価を、図１０〜１２に示したアルゴリズムでＦ（ｐ１２）上の任意の元ｆに乗算するときには、次のようになる。図１１にはステップ１に３回の係数の乗算があるので、Ｆ（ｐ２）上の元同士の乗算は３回である。図１２にはステップ１，２に４回ずつ、ステップ３に１回の係数同士の乗算が存在するので、Ｆ（ｐ２）上の元同士の乗算は９回である。また、Ｆ（ｐ１２）上の任意の元同士の乗算の場合、Ｆ（ｐ２）上の元同士の乗算は１８回である（従来技術なので理由は省略する）。したがって、Ｆ（ｐ２）上の元同士の乗算は３３回（３×２＋９＋１８）である。このように、マルチペアリング演算の処理に含まれるｆ×Ｌ０’×…×Ｌｍ−１’の演算において、式評価Ｌ０’，Ｌ１’，…，Ｌｍ−１’の中からΔ個以下の式評価を選択して乗算する処理を繰り返すことで、係数にゼロや小整数を持つ元同士の演算を増やせる。したがって、式５の形式の式評価を用い、式評価演算部１００が式評価選択部１１０、式評価乗算部１２０、元乗算部１３０、演算制御部１４０、未選択乗算部１５０を備えることで、さらに計算コストを削減できる。
【００４７】
次に、式４の形式の式評価を用いて
Ｈ０’←ｈ０×ｈ１，  Ｈ１’←ｈ２×ｈ３
Ｌ”←Ｈ０’×Ｈ１’
ｆ←ｆ×Ｌ”
のようにｆを更新することを繰り返す方法と比較する。図１３に、従来技術である式４の形式の式評価を用いた場合の乗算のアルゴリズムの例（Algorithm 6’）を示す。図１４に、図１３で求めた元同士の乗算のアルゴリズムの例（Algorithm 7’）を示す。図１１のステップ６に示された元の式から、値がゼロの係数が１つと小整数「１」の係数が１つあることが分かる。図１３のステップ７に示された元の式から、従来技術である式４の形式の式評価を用いた場合には、式評価同士の乗算の結果には、値がゼロの係数が１つあり、小整数「１」の係数はないことが分かる。そして、式４の形式の式評価を用いたときにはＨ０’×Ｈ１’の計算は図１４に示されたアルゴリズムになる。図１３に示されたアルゴリズムでは、ステップ１に３回の係数同士の乗算が存在するので、Ｆ（ｐ２）上の元同士の乗算は３回である。そして、図１４に示されたアルゴリズムでは、ステップ１に５回、ステップ３，５，７，９に２回ずつ、ステップ１１，１３に１回ずつ係数同士の乗算が存在するので、Ｆ（ｐ２）上の元同士の乗算は１５回である。したがって、式４の形式の４つの式評価を、図１３，１４に示された乗算方法でＦ（ｐ１２）上の任意の元ｆに乗算するときには、Ｆ（ｐ２）上の元同士の乗算は３９回（３×２＋１５＋１８）である。したがって、式評価演算部１００が式評価選択部１１０、式評価乗算部１２０、元乗算部１３０、演算制御部１４０、未選択乗算部１５０を備えなくても、式４の形式の式評価で計算方法を工夫するよりも、式５の形式で式評価を表現する方が計算コスト削減の効果がある。
【００４８】
［変形例］
さらに、上述のとおり、式評価が式６のように、
Ｌｊ＝αｊｙｊＰ＋βｊｘｊｐｗ＋γｊｖｗ
の場合には、式評価を
Ｌｊ’＝ｄｊｖＮ（ＡｊｙｊＰ’＋ｗ＋ＢｊｘｊＰ’ｖｗ）
ただし、Ａｊ＝ｓｊＡ（αｊ／βｊ）、Ｂｊ＝ｓｊＢ（γｊ／βｊ）
ｘｊＰ’＝１／（ｓｊＢ・ｘｊＰ）、ｙｊＰ’＝ｙｊＰ／（ｓｊＡ・ｘｊＰ）
ｓｊＡとｓｊＢはあらかじめ定めた定数
のように変形すれば同様の効果が得られる。したがって、図７に示したマルチペアリング演算装置と、図８に示したマルチペアリング演算装置の入力変換と式評価演算の処理フローは、以下のとおりでもよい。ただし、ＡｊとＢｊをＦ（ｐ２）上の元とする。
【００４９】
マルチペアリング演算装置６０は、ｍ個の群Ｇ１の元Ｐ０，…，Ｐｍ−１と群Ｇ２の元Ｑ０，…，Ｑｍ−１とのマルチペアリングｅ（Ｐ０，Ｑ０）×ｅ（Ｐ１，Ｑ１）×…×ｅ（Ｐｍ−１，Ｑｍ−１）を求める。マルチペアリング演算装置６０は、記録部９０が事前計算の結果を記録していることと、入力変換部６５、式評価処理手段７０を有することを特徴としている。式評価処理手段７０は、式評価生成部８０と式評価演算部１００からなる。
【００５０】
ｊ＝０,…,ｍ−１について、Ａｊ＝ｓｊＡ（αｊ／βｊ）、Ｂｊ＝ｓｊＢ（γｊ／βｊ）とする。そして、記録部９０は、ｊ＝０,…,ｍ−１について、Ａｊと所定の関係を持つ値であるａｊと、Ｂｊと所定の関係を持つ値であるｂｊを記録している。ａｊ＝Ａｊ、ｂｊ＝Ｂｊとするのが最も効率的と考える。しかし、乗算や逆元算のような低速な計算を必要とせずにＡｊとＢｊを求められる別の値をａｊとｂｊとして記録しておいてもよい。ここでは、「所定の関係を持つ値」は、低速な計算を必要とせずにＡｊとＢｊを求めることができる値の意味である。
【００５１】
入力変換部６５は、ｊ＝０,…,ｍ−１について、ｘｊＰ’＝１／（ｓｊＢ・ｘｊＰ）、ｙｊＰ’＝ｙｊＰ／（ｓｊＡ・ｘｊＰ）を計算する（Ｓ６５）。式評価生成部８０は、ｊ＝０,…,ｍ−１のすべてについて、記録部９０からａｊとｂｊを読み出し、ａｊとｂｊを用いて、
Ｌｊ’＝ｄｊｖＮ（ＡｊｙｊＰ’＋ｗ＋ＢｊｘｊＰ’ｖｗ）
のように式評価Ｌｊ’を生成する（Ｓ８０）。ｄ０,…,ｄｍ−１＝１，Ｎ＝０が最も効率的と考えるが、ｄ０ｖＮ,…,ｄｍ−１ｖＮを乗算した式評価Ｌ０’，Ｌ１’，…，Ｌｍ−１’を生成してもよい。
【００５２】
式評価演算部１００は、ｆ，Ｌ０’，Ｌ１’，…，Ｌｍ−１’を入力とし、ｆ×Ｌ０’×…×Ｌｍ−１’の演算結果を出力する（Ｓ１００）。式評価演算部１００については、実施例２と同様に式評価演算部１００が、式評価選択部１１０、式評価乗算部１２０、元乗算部１３０、演算制御部１４０、未選択乗算部１５０を備え、式評価にゼロの係数があることを利用してもよい。このように構成すれば、実施例２と同様の効果が得られる。
【００５３】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００５４】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００５５】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００５６】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５８】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００５９】
１０  ペアリング演算装置                １５、６５  入力変換部
２０、７０  式評価処理手段              ３０、８０  式評価生成部
４０、１００  式評価演算部              ５０、９０  記録部
６０  マルチペアリング演算装置          １１０  式評価選択部
１２０  式評価乗算部                    １３０  元乗算部
１４０  演算制御部                      １５０  未選択乗算部
【図１】
2015135452.tif 000006
【図２】
2015135452.tif 000007
【図３】
2015135452.tif 000008
【図４】
2015135452.tif 000009
【図５】
2015135452.tif 000010
【図６】
2015135452.tif 000011
【図７】
2015135452.tif 000012
【図８】
2015135452.tif 000013
【図９】
2015135452.tif 000014
【図１０】
2015135452.tif 000015
【図１１】
2015135452.tif 000016
【図１２】
2015135452.tif 000017
【図１３】
2015135452.tif 000018
【図１４】
2015135452.tif 000019