(57)【特許請求の範囲】
【請求項１】
ペアリングを演算するペアリング演算装置において、
ある有限体を基礎体とする拡大体の元であり多項式で表現される第一の数を、その有限体の元を係数とする項数Ｗｓ（Ｗｓは所定の自然数）の複数の多項式とそれぞれ乗算する事前演算手段と、
上記項数Ｗｓの多項式の各組と、上記演算結果とを対応付けたものを、上記第一の数についての事前演算テーブルとして記憶する事前演算テーブル記憶手段と、
上記拡大体の元であり多項式で表現される第二の数を、項数ｗ以下の多項式に分割する分割手段と、
上記事前演算テーブル記憶部から読み込んだ事前演算テーブルを参照して、上記第一の数と上記分割された各多項式との積を求める参照手段と、
上記参照手段により求まった積を加算することにより、上記第一の数と上記第二の数との積を求める加算手段と、
を備え、
ペアリング演算中に、上記第一の数を、上記拡大体の元であり多項式で表現される複数の被乗数とそれぞれ乗算する場合には、各被乗数を第二の数として、上記分割手段、上記参照手段、上記加算手段による処理を行うことにより、上記事前演算テーブル記憶手段から読み込んだ既に生成された同じ事前演算テーブルを参照して、上記第一の数と上記被乗数との積をそれぞれ求め、
上記加算手段が求めた積をリダクションする第一のリダクション手段をさらに備え、
上記事前演算手段が演算した積をリダクションする第二のリダクション手段をさらに備え、
上記事前演算テーブルは、上記項数Ｗｓの多項式の各組と、上記第二のリダクション手段によってリダクションされた上記演算結果とを対応付けたものを、上記第一の数についての事前演算テーブルとして記憶する手段であり、
上記第一の数についての事前演算テーブルが上記事前演算テーブル記憶手段に記憶されているかどうかを判定して、上記事前演算テーブル記憶手段に上記第一の数についての事前演算テーブルが記憶されていないと判定された場合には、上記事前演算手段に上記第一の数についての事前演算テーブルを生成させる第一の制御手段、
をさらに備えることを特徴とするペアリング演算装置。
【請求項２】
ペアリングを演算するペアリング演算装置において、
ある有限体を基礎体とする拡大体の元であり多項式で表現される第一の数を、その有限体の元を係数とする項数Ｗｓ（Ｗｓは所定の自然数）の複数の多項式とそれぞれ乗算する事前演算手段と、
上記項数Ｗｓの多項式の各組と、上記演算結果とを対応付けたものを、上記第一の数についての事前演算テーブルとして記憶する事前演算テーブル記憶手段と、
上記拡大体の元であり多項式で表現される第二の数を、項数ｗ以下の多項式に分割する分割手段と、
上記事前演算テーブル記憶部から読み込んだ事前演算テーブルを参照して、上記第一の数と上記分割された各多項式との積を求める参照手段と、
上記参照手段により求まった積を加算することにより、上記第一の数と上記第二の数との積を求める加算手段と、
を備え、
ペアリング演算中に、上記第一の数を、上記拡大体の元であり多項式で表現される複数の被乗数とそれぞれ乗算する場合には、各被乗数を第二の数として、上記分割手段、上記参照手段、上記加算手段による処理を行うことにより、上記事前演算テーブル記憶手段から読み込んだ既に生成された同じ事前演算テーブルを参照して、上記第一の数と上記被乗数との積をそれぞれ求め、
上記加算手段が求めた積をリダクションする第一のリダクション手段をさらに備え、
上記事前演算手段が演算した積をリダクションする第二のリダクション手段をさらに備え、
上記事前演算テーブルは、上記項数Ｗｓの多項式の各組と、上記第二のリダクション手段によってリダクションされた上記演算結果とを対応付けたものを、上記第一の数についての事前演算テーブルとして記憶する手段であり、
上記のペアリング演算において、上記第一の数を乗数とする乗算が再び行われるかどうかを判定して、上記第一の数を乗数とする乗算が再び行われると判定された場合には、上記事前演算テーブル記憶手段に上記第一の数についての事前演算テーブルを記憶させるとともに、上記第一の数を乗数とする乗算が再び行われないと判定された場合には、上記事前演算テーブル記憶手段に上記第一の数についての事前演算テーブルを記憶させないように制御する第二の制御手段、
をさらに備えることを特徴とするペアリング演算装置。
【請求項３】
請求項１又は２に記載のペアリング演算装置において、
複数のＷｓに基づいて所定のペアリング演算をそれぞれ行った場合に、そのペアリング演算をするのにかかった時間を複数のＷｓごとに計測する第一計測手段と、
上記計測されたペアリング演算をするのにかかった時間を最小にするＷｓを選択して、その最小にするＷｓに基づいて上記事前演算手段に上記乗算をさせるウィンドウサイズ決定手段と、
を備えることを特徴とするペアリング演算装置。
【請求項４】
請求項１又は２に記載のペアリング演算装置において、
複数のペアリング演算アルゴリズムを記憶するアルゴリズム記憶手段と、
上記アルゴリズム記憶手段から読み込んだ複数のペアリング演算アルゴリズムに基づいてペアリング演算をそれぞれ行った場合に、そのペアリング演算をするのにかかった時間を複数のペアリング演算アルゴリズムごとに計測する第二計測手段と、
上記計測されたペアリング演算をするのにかかった時間を最小にするペアリング演算アルゴリズムを選択して、その最小にするペアリング演算アルゴリズムに基づいて、上記ペアリング演算装置にペアリング演算をさせるアルゴリズム決定手段と、
を備えることを特徴とするペアリング演算装置。
【請求項５】
請求項１から請求項４の何れかに記載のペアリング演算装置の各手段としてコンピュータを機能させるためのペアリング演算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報セキュリティ技術に関するものであり、特に、ペアリング演算を実現するためのペアリング演算装置、プログラム等に関する。
【背景技術】
【０００２】
ペアリングを多項式時間で計算するアルゴリズムは、Ｍｉｌｌｅｒによって提案され、２０００年頃までは主に楕円曲線暗号の攻撃に用いられた。２０００年頃にペアリングが暗号プロトコルに用いられるようになるとペアリングの高速化への関心が高まり、Ｄｕｕｒｓｍａ等による改良を経て、Ｂａｒｒｅｔｏ等によって以下のηＴペアリングアルゴリズムが与えられた。
【０００３】
なお、ペアリングとは、２入力１出力関数であって、各入力に対して線形性が成り立つ、いわゆる双線形関数である。また、ペアリングを計算、演算するとは、所定の値をペアリング関数に入力した場合の出力を求めることをいう。
【０００４】
［ηＴペアリング演算アルゴリズム］
〔準備〕Ｅ（Ｆ３＾ｍ）：有限体Ｆ３＾ｍ上定義された楕円曲線
ｇ１（ρ）＝ρ３−ρ−１
ｇ２（σ）＝σ２＋１
Ｆ３＾（６ｍ）の元は、Ｆ３＾ｍ［ρ，σ］／（ｇ１（ρ），ｇ２（σ））の元として表現する。
〔入力〕Ｐ＝（ｘｐ，ｙｐ），Ｑ＝（ｘｑ，ｙｑ）∈Ｅ（Ｆ３＾ｍ）
〔出力〕ηＴ（Ｐ，Ｑ）∈Ｆ＊３＾（６ｍ）
〔計算方法〕
Ｓｔｅｐ１：ｙｐ←−ｙｐ（∈Ｆ３＾ｍ）
Ｓｔｅｐ２：ｆ←−ｙｐ（ｘｐ＋ｘｑ＋１）＋ｙｑσ＋ｙｐρ（∈Ｆ３＾（６ｍ））
Ｓｔｅｐ３：ｉ＝０から（ｍ−１）／２までＳｔｅｐ３−１〜Ｓｔｅｐ３−５を繰り返す。
【０００５】
Ｓｔｅｐ３−１：ｕ←ｘｐ＋ｘｑ＋１（∈Ｆ３＾ｍ）
Ｓｔｅｐ３−２：ｇ←−ｕ２＋ｙｐｙｑσ−ｕρ−ρ２（∈Ｆ３＾（６ｍ））
Ｓｔｅｐ３−３：ｆ←ｆｇ（∈Ｆ３＾（６ｍ））
Ｓｔｅｐ３−４：ｘｐ←ｘｐ（１／３），ｙｐ←ｙｐ（１／３）
Ｓｔｅｐ３−５：ｘｑ←ｘｑ３，ｙｑ←ｙｑ３
Ｓｔｅｐ４：ｆ（（３＾３ｍ）−１）（（３＾ｍ）＋１）（（３＾ｍ）−（３＾（（ｍ＋１）／２））＋１）を出力する。
【０００６】
上記のηＴペアリング演算アルゴリズムにおいて計算する必要がある有限体Ｆ３＾ｍの乗算をコンピュータ上に実装するための方法が非特許文献１に開示されている。ここで、有限体Ｆ３＾ｍの乗算とは、有限体Ｆ３＾ｍに属する２つの元の積を求めることをいう。例えば、上記Ｓｔｅｐ２におけるｙｐ（ｘｐ＋ｘｑ＋１）、Ｓｔｅｐ３−２におけるｕ２、ｙｐｙｑが有限体Ｆ３＾ｍの乗算である。
【０００７】
非特許文献１に記載された技術においては、有限体Ｆ３＾ｍの乗算をする度ごとに事前演算テーブルを生成して、その事前演算テーブルを用いて有限体Ｆ３＾ｍの乗算を行っている（例えば、非特許文献１参照。）。
【０００８】
ここで、上記ηＴペアリング演算アルゴリズムにおいては、後述するように、Ｓｔｅｐ３−２、Ｓｔｅｐ３−３において１８回の有限体Ｆ３＾ｍ乗算をする必要がある。このため、非特許文献１に記載された発明を上記ηＴペアリング演算アルゴリズムに適用した場合には、Ｓｔｅｐ３−２、Ｓｔｅｐ３−３において１８回事前演算テーブルを生成することになる。
【非特許文献１】川原祐人、外３名、「ηＴペアリングの高速ソフトウェア実装」、ＳＣＩＳ２００７、２Ｅ３−２、２００７年、
【発明の開示】
【発明が解決しようとする課題】
【０００９】
非特許文献１に記載された技術においては、有限体の乗算をする度ごとに事前演算テーブルを生成しており、ペアリングの演算を十分に高速化できていないという問題があった。
本発明は、ペアリングの演算を高速化するための技術を提供することを目的とする。
【課題を解決するための手段】
【００１０】
ペアリングを演算するペアリング演算装置において、事前演算手段が、ある有限体を基礎体とする拡大体の元であり多項式で表現される第一の数を、その有限体の元を係数とする項数Ｗｓ（Ｗｓは所定の自然数）の複数の多項式とそれぞれ乗算する。事前演算テーブル記憶手段が、項数Ｗｓの多項式の各組と、演算結果とを対応付けたものを、第一の数についての事前演算テーブルとして記憶する。分割手段が、拡大体の元であり多項式で表現される第二の数を、項数ｗの多項式に分割する。参照手段が、事前演算テーブル記憶部から読み込んだ事前演算テーブルを参照して、第一の数と分割された各多項式との積を求める。加算手段が、参照手段により求まった積を加算することにより、第一の数と第二の数との積を求める。また、ペアリング演算中に、第一の数を、拡大体の元であり多項式で表現される複数の被乗数とそれぞれ乗算する場合には、各被乗数を第二の数として、分割手段、参照手段、加算手段による処理を行うことにより、事前演算テーブル記憶手段から読み込んだ既に生成された同じ事前演算テーブルを参照して、第一の数と被乗数との積をそれぞれ求める。
加算手段が求めた積をリダクションする第一のリダクション手段をさらに備え、事前演算手段が演算した積をリダクションする第二のリダクション手段をさらに備え、事前演算テーブルは、項数Ｗｓの多項式の各組と、第二のリダクション手段によってリダクションされた演算結果とを対応付けたものを、第一の数についての事前演算テーブルとして記憶する手段であり、第一の数についての事前演算テーブルが事前演算テーブル記憶手段に記憶されているかどうかを判定して、事前演算テーブル記憶手段に第一の数についての事前演算テーブルが記憶されていないと判定された場合には、事前演算手段に第一の数についての事前演算テーブルを生成させる第一の制御手段、をさらに備えていてもよい。
または、加算手段が求めた積をリダクションする第一のリダクション手段をさらに備え、事前演算手段が演算した積をリダクションする第二のリダクション手段をさらに備え、事前演算テーブルは、項数Ｗｓの多項式の各組と、第二のリダクション手段によってリダクションされた演算結果とを対応付けたものを、第一の数についての事前演算テーブルとして記憶する手段であり、のペアリング演算において、第一の数を乗数とする乗算が再び行われるかどうかを判定して、第一の数を乗数とする乗算が再び行われると判定された場合には、事前演算テーブル記憶手段に第一の数についての事前演算テーブルを記憶させるとともに、第一の数を乗数とする乗算が再び行われないと判定された場合には、事前演算テーブル記憶手段に第一の数についての事前演算テーブルを記憶させないように制御する第二の制御手段、をさらに備えていてもよい。
【発明の効果】
【００１１】
ペアリング演算において、ある乗数についての有限体の乗算を行うときに、その乗数についての事前演算テーブルが既に生成されている場合には、その既に生成された事前演算テーブルを用いて多項式乗算を行う。これにより、有限体の乗算をする度ごとに事前演算テーブルを生成する必要はなくなり、ペアリング演算を高速に行うことができる。
【発明を実施するための最良の形態】
【００１２】
［理論］
上記したηＴペアリング演算アルゴリズムにおけるｆは、ρとσの多項式として一般に、
f=(c0+c1ρ+c2ρ2)+(c3+c4ρ+c5ρ2)σ
と書くことができる。ここで、ｃ０，ｃ１，ｃ２，ｃ３，ｃ４，ｃ５∈F３＾ｍである。また、ｄ＝ｙｐｙｑとすると、上記したηＴペアリング演算アルゴリズムにおけるｇは、ρとσの多項式として、
g=-(u2+uρ+ρ2)+dσ
と書くことができる。そうすると、Ｓｔｅｐ３−３におけるｆｇの演算は、
fg={(c0+c1ρ+c2ρ2)+(c3+c4ρ+c5ρ2)σ}×{-(u2+uρ+ρ2)+dσ}
となり、分配の法則により、このｆｇの演算は次の４つの部分に分けて考えることができる。
【００１３】
(c0+c1ρ+c2ρ2)×ｄ            （１）
(c3+c4ρ+c5ρ2)×ｄ            （２）
(c0+c1ρ+c2ρ2)×(u2+uρ+ρ2)  （３）
(c3+c4ρ+c5ρ2)×(u2+uρ+ρ2)  （４）
上記（１）式、（２）式においては、ｄを乗数とする、ｃ０ｄ，ｃ１ｄ，ｃ２ｄ，ｃ３ｄ，ｃ４ｄ，ｃ５ｄという６回のＦ３＾ｍの乗算が行われる。ここで、本発明における事前演算テーブルは所定の乗数について作成されるものである（事前演算テーブルの詳細については後述する。）。したがって、上記（１）式、（２）式の演算においては、ｄを乗数とする事前演算テーブルを一回作成すれば、その事前演算テーブルを他のｄを乗数とするＦ３＾ｍの乗算にも使用することができる。具体的には、ｃ０ｄを演算する際に、ｄを乗数とする事前演算テーブルを作成すれば、その事前演算テーブルをｃ１ｄ，ｃ２ｄ，ｃ３ｄ，ｃ４ｄ，ｃ５ｄの演算にも使用することができる。
【００１４】
また、上記（３）式、（４）式においては、例えば、ｕを乗数とするｃ２ｕ，（ｃ２ｕ＋ｃ１）ｕ，ｃ０ｕ，（ｃ０ｕ）ｕ，ｃ５ｕ，（ｃ５ｕ＋ｃ４）ｕ，ｃ３ｕ，（ｃ３ｕ）ｕ，という８回のＦ３＾ｍの乗算が行われ、ｕ２を乗数とするｃ１ｕ２，ｃ４ｕ２という２回のＦ３＾ｍの乗算が行われると考えることができる。ここで、上記（３）式、（４）式の演算が行われるＳｔｅｐ３−３よりも前のＳｔｅｐ３−２においてｕ２を計算しており、このｕ２の計算において、ｕを乗数とする事前演算テーブルは既に作成されている。したがって、この既に作成されたｕを乗数とする事前演算テーブルを、上記したｕを乗数とする８回のＦ３＾ｍの乗算に用いることができる。したがって、この場合、ｕ２を乗数とする事前演算テーブルを一回作成すれば、上記（３）式、（４）式の演算を行うことができる。
【００１５】
このように、Ｓｔｅｐ３−２においてｕ２、ｙｐｙｑの２回の乗算と、Ｓｔｅｐ３−３において１６回（＝上記（１）、（２）式の６回＋上記（３）、（４）式の１０回）の乗算とを合わせた合計１８回のＦ３＾ｍの乗算の必要がある。しかし、上記のように考えると、Ｓｔｅｐ３−２、Ｓｔｅｐ３−３において、事前演算として、ｕ、ｙｐとｙｑの何れか一方、ｄ、ｕ２をそれぞれ乗数とする計４つの事前演算テーブルを作成すれば足りることがわかる。
【００１６】
また、上記（３）式、（４）式において、ｕ２を乗数とする演算は行われず、ｕを乗数とする、ｃ２ｕ，（ｃ２ｕ）ｕ，ｃ１ｕ，（ｃ１ｕ）ｕ，ｃ０ｕ，（ｃ０ｕ）ｕ，ｃ５ｕ，（ｃ５ｕ）ｕ，ｃ４ｕ，（ｃ４ｕ）ｕ，ｃ３ｕ，（ｃ３ｕ）ｕ，という１２回の演算が行われると考えることができる。この場合、ｕ２を乗数とする事前演算テーブルを作成する必要はない。したがって、この場合には、Ｓｔｅｐ３−２、Ｓｔｅｐ３−３において、事前演算として、ｕ、ｙｐとｙｑの何れか一方、ｄをそれぞれ乗数とする計３つの事前演算テーブルを作成すればよい。つまり、作成する必要がある事前演算テーブルをさらに少なくすることができることがわかる。
【００１７】
このように、ある乗数についての事前演算テーブルを、その乗数についての有限体の他の演算に使いまわすことにより、ペアリングの演算を高速に行うことができる。また、事前演算テーブルを作成する部分にコストをかけて、多項式乗算部分を高速化することによりさらにペアリング演算の高速化が可能である。
【００１８】
［事前演算テーブル］
事前演算テーブルと、その事前演算テーブルを用いた多項式乗算について説明をする。説明の便宜のため、標数３の基礎体Ｆ３＝｛０，１，２｝のｍ次拡大体である有限体Ｆ３＾ｍについての多項式乗算
Ｃ（ｘ）＝Ａ（ｘ）・Ｂ（ｘ）
を例に挙げる。他の標数の基礎体のｍ次拡大体である有限体についても、同様にして事前演算テーブルを構成して、多項式乗算をすることができる。多項式乗算とは、入力Ａ（ｘ），Ｂ（ｘ）∈Ｆ３＾ｍから、出力Ｃ（ｘ）∈Ｆ３＾ｍを求めることをいう。ここで、Ａ（ｘ），Ｂ（ｘ），Ｃ（ｘ）は次のように表記される。
【００１９】
Ａ（ｘ）＝ａ０＋ａ１ｘ＋ａ２ｘ２＋…＋ａｍ−１ｘｍ−１
Ｂ（ｘ）＝ｂ０＋ｂ１ｘ＋ｂ２ｘ２＋…＋ｂｍ−１ｘｍ−１
Ｃ（ｘ）＝ｃ０＋ｂ１ｘ＋ｂ２ｘ２＋…＋ｂ２ｍ−２ｘ２ｍ−２
この多項式乗算は、いわゆるＷｉｎｄｏｗｓ法によって高速処理が可能となる。Ｗｉｎｄｏｗｓ法は、Ａ（ｘ）に対して事前計算を行い、Ｂ（ｘ）の走査時に複数の係数ｂｉを同時に確認して加算を行うアルゴリズムのことである。ここで、１度に確認する係数の個数（ｂｉ＋ｗ−１，ｂｉ＋ｗ−２，…，ｂｉ）をウィンドウサイズＷｓとする。事前演算テーブルとは、このＡ（ｘ）に対する事前計算の結果のことである。
【００２０】
具体的には、Ａ（ｘ）に対する事前計算とは、項数ＷｓのＷｓ−１次多項式
Ｗ（ｘ）＝ｗ０＋ｗ１ｘ＋ｗ２ｘ２＋…＋ｗＷｓ−１ｘＷｓ−１（ｗｉ∈｛０，１，２｝）
のすべての組合せに対して、Ａ（ｘ）×Ｗ（ｘ）の結果を求めることをいう。言い換えると、有限体Ｆ３を基礎体とするｍ次拡大体Ｆ３＾ｍの元であり多項式で表現されるＡ（ｘ）を、その有限体Ｆ３の元を係数とする項数Ｗｓの各多項式Ｗ（ｘ）とそれぞれ演算することである。ある係数ｗｉ∈｛０，１，２｝の組｛ｗ０，ｗ１，ｗ２，…，ｗＷｓ−１｝についてのＡ（ｘ）×Ｗ（ｘ）の演算結果をＡ’［ｗ０，ｗ１，ｗ２，…，ｗＷｓ−１］∈Ｆ３＾ｍとすると、この演算により、例えば、図３に例示するような事前演算テーブルを得ることができる。このように事前演算テーブルとは、Ｗｓ個の係数の各組と、その演算結果とを対応づけたものである。換言すると、事前演算テーブルとは、項数Ｗｓの各多項式と、その演算結果を対応づけたものである。
【００２１】
次に、事前演算テーブルを用いた多項式乗算について説明をする。ｍ次多項式であるＢ（ｘ）は、項数Ｗｓの多項式に分割される。より詳細には、項数Ｗｓの多項式に分割された後に、項数Ｗｓの分割された各多項式は共通するｘの累乗で括られる。
【００２２】
B(x)= (b0+b1x+b2x2+…+bWs-1xWs-1)
+(bWs+b+Ws+1x+bWs+2x2+…+b2Ws-1xWs-1)xWs
…
+(bm-Ws+bm-Ws+1x+bm-Ws+2x2+…+bm-1xm-1)xm-Ws
この場合、Ａ（ｘ）・Ｂ（ｘ）を以下のように書くことができる。
【００２３】
A(x)・B(x)= A(x)・(b0+b1x+b2x2+…+bWs-1xWs-1)
+A(x)・(bWs+b+Ws+1x+bWs+2x2+…+b2Ws-1xWs-1)xWs
…
+A(x)・(bm-Ws+bm-Ws+1x+bm-Ws+2x2+…+bm-1xWs-1)xm-Ws
事前演算テーブルにおいて、Ａ（ｘ）と項数Ｗｓの任意の多項式Ｗ（ｘ）との積は計算してあるので、事前演算テーブルを参照することにより、Ａ（ｘ）と分割された項数Ｗｓの各多項式との積は容易に求めることができる。すなわち、分割された項数Ｗｓの多項式のＷｓ個の係数の組に対応する演算結果を参照する。そして、その分割された項数Ｗｓの多項式が、ｘの累乗で括ったものであれば、その演算結果にそのｘの累乗をかけることにより、Ａ（ｘ）と分割された項数Ｗｓの各多項式との積を求めることができる。
【００２４】
A(x)・B(x)= A[b0,b1,b2,…,bWs-1]
+A[bWs,bWs+1,bWs+2,…,b2Ws-1]xWs
…
+A[bm-Ws,bm-Ws+1,bm-Ws+2,…,bm-1]xm-Ws
このようにして求まったＡ（ｘ）と分割された項数Ｗｓの各多項式との積を加算することにより、Ｃ（ｘ）＝Ａ（ｘ）・Ｂ（ｘ）が計算される。
【００２５】
［装置構成］
図１に例示したペアリング演算部３は、所定の入力Ｐ，ＱについてのペアリングηＴ（Ｐ，Ｑ）を計算する。ペアリングの演算中に、有限体の乗算を行う必要がある場合には、ペアリング演算部３の乗算演算部１がその演算を行うように、ペアリング演算部３の制御部２が制御する。
【００２６】
以下、ある有限体を基礎体とする拡大体の元であり多項式で表現される乗数Ａと、同じ拡大体の元であり多項式で表現される被乗数Ｂとが乗算される場合を例に挙げて説明をする。乗数Ａは、上記［事前テーブル］の項目で説明をしたＡ（ｘ）に対応しており、被乗数ＢはＢ（ｘ）に対応するものである。
【００２７】
図２に、乗算演算部１の機能構成を示す。有限体を基礎体とする拡大体の元であり多項式で表現される乗数Ａが入力されると、乗算演算部１の事前演算部１０は、メモリ１５からウィンドウサイズＷｓを読み出して、その乗数Ａについての事前演算テーブルｔＡを生成する。具体的には、上記したように、ある有限体を基礎体とする拡大体の元であり多項式で表現される乗数Ａを、その有限体の元を係数とする項数Ｗｓ（Ｗｓは所定の自然数）の複数の多項式とそれぞれ乗算することにより事前演算テーブルｔＡを生成する。
【００２８】
生成された事前演算テーブルｔＡは、事前演算テーブル記憶部１１に記憶される。この例では、事前演算テーブル記憶部１１には、事前演算テーブルｔＡのみが記憶されているが、他の事前演算テーブルを記憶していてもよい。
【００２９】
積演算部１２に被乗数Ｂが入力されると、積演算部１２の分割部１２１は、メモリ１５からウィンドウサイズＷｓを読み込んで、被乗数Ｂを項数Ｗｓの多項式に分割する。分割された項数Ｗｓの多項式は、参照部１２２に送られる。被乗数Ｂの項数が、ウィンドウサイズＷｓの倍数でないときには、被乗数Ｂは、項数Ｗｓの多項式と、Ｗｓより下の項数の多項式に分割される。すなわち、一般に、被乗数Ｂは、項数Ｗｓ以下の多項式に分割される。
【００３０】
参照部１２２は、事前演算テーブル記憶部１１の事前演算テーブルｔＡを参照して、乗数Ａと、分割された項数Ｗｓの各多項式との積をそれぞれ求める。各多項式ごとに求まった積は、加算部１２３に送られる。被乗数Ｂの項数が、ウィンドウサイズＷｓの倍数でないときに生じるＷｓより下の項数の多項式については、対応する係数が０であるとして事前演算テーブルを参照すればよい。
【００３１】
加算部１２３は、参照部１２２が求めた積を加算することにより、乗数Ａと被乗数Ｂとの積、換言すると、事前演算テーブルｔＡに関する乗数Ａと被乗数Ｂの積Ｍ（ｔＡ，Ｂ）を計算して出力する。
【００３２】
ペアリング演算部３は、上記出力結果を用いてペアリングの演算を継続する。
【００３３】
再度、Ａを乗数とする乗算をする必要があるときには、既に生成されおり、事前演算テーブル記憶部１１に記憶されている事前演算テーブルｔＡを用いて、上記と同様に、乗数Ａと被乗数との積が計算される。
【００３４】
Ａ以外の数Ｄを乗数とする乗算をする必要があるときには、上記と同様にして、事前演算部１０が乗数Ｄについての事前演算テーブルｔＤを生成して、事前演算テーブル記憶部１１に格納し、積演算部１２がその事前演算テーブルｔＤを参照して、有限体の乗算を行う。
【００３５】
この処理を自動的に行うために、ある乗数についての事前演算テーブルが事前演算テーブル記憶部１１に記憶されているかどうかを判定して、事前演算テーブル記憶部１１にその乗数についての事前演算テーブルが記憶されていないと判定された場合には、事前演算部１０にその乗数についての事前演算テーブルを生成させる第一制御部１３を設けてもよい。
【００３６】
また、ある乗数についての乗算が再び行われるかどうかを判定して、その乗数についての乗算が再び行われると判定された場合には、事前演算テーブル記憶部１１にその乗数についての事前演算テーブルを記憶させるとともに、その乗数についての乗算が再び行われないと判定された場合には、事前演算テーブル記憶部１１にその乗数についての事前演算テーブルを記憶させないように制御する第二制御部１４を設けてもよい。
【００３７】
［第一のηＴペアリング演算アルゴリズム］
以下に、本発明をηＴペアリングに適用した場合の第一のηＴペアリング演算アルゴリズムを示す。この第一のηＴペアリング演算アルゴリズムは、上記（３）式、（４）式において、ｕを乗数とするｃ２ｕ，（ｃ２ｕ＋ｃ１）ｕ，ｃ０ｕ，（ｃ０ｕ）ｕ，ｃ５ｕ，（ｃ５ｕ＋ｃ４）ｕ，ｃ３ｕ，（ｃ３ｕ）ｕ，という８回のＦ３＾ｍの乗算を行い、ｕ２を乗数とするｃ１ｕ２，ｃ４ｕ２という２回のＦ３＾ｍの乗算を行う場合のアルゴリズムである。すなわち、Ｓｔｅｐ３において、事前演算として、ｕ、ｙｐとｙｑの何れか一方、ｄ、ｕ２をそれぞれ乗数とする計４つの事前演算テーブルを作成して、そのうちｕ、ｄ、ｕ２を乗数とする事前演算テーブルについては使いまわす場合のアルゴリズムである。
【００３８】
下記のアルゴリズムにおいて、Ｔ（Ａ）は乗数Ａ∈Ｆ３＾ｍに関する事前演算テーブルｔＡを出力する関数である。また、Ｍ（ｔ，Ｂ）は、事前演算テーブルｔに関する乗数とＢの積を出力する関数である。例えば、Ｍ（Ｔ（Ａ），Ｂ）＝Ａ・Ｂである。関数Ｔ（Ａ）と関数Ｍ（ｔ，Ｂ）についての演算は、乗算演算部１において行われる。具体的には、関数Ｔ（Ａ）についての演算は事前演算部１０において行われ、関数Ｍ（ｔ，Ｂ）についての演算は積演算部１２において行われる。他の処理は、ペアリング演算部３が行う。これは、後述する第二のηＴペアリング演算アルゴリズムにおいても同様である。
【００３９】
なお、下記Ｓｔｅｐ３−３−４は上記式（３）の演算に対応したステップであり、下記Ｓｔｅｐ３−３−５は上記式（４）の演算に対応したステップであり、下記Ｓｔｅｐ３−３−６はリダクションをしているステップである。
【００４０】
〔準備〕Ｅ（Ｆ３＾ｍ）：有限体Ｆ３＾ｍ上定義された楕円曲線
ｇ１（ρ）＝ρ３−ρ−１
ｇ２（σ）＝σ２＋１
Ｆ３＾（６ｍ）の元は、Ｆ３＾（ｍ）［ρ，σ］／（ｇ１（ρ），ｇ２（σ））の元として表現する。
〔入力〕Ｐ＝（ｘｐ，ｙｐ），Ｑ＝（ｘｑ，ｙｑ）∈Ｅ（Ｆ３＾ｍ）
〔出力〕ηＴ（Ｐ，Ｑ）∈Ｆ＊３＾（６ｍ）
〔計算方法〕
Ｓｔｅｐ１：ｙｐ←−ｙｐ（∈Ｆ３＾ｍ）
Ｓｔｅｐ２：ｆ←−ｙｐ（ｘｐ＋ｘｑ＋１）＋ｙｑσ＋ｙｐρ（∈Ｆ３＾（６ｍ））
Ｓｔｅｐ３：ｉ＝０から（ｍ−１）／２までＳｔｅｐ３−１〜Ｓｔｅｐ３−５を繰り返す。
【００４１】
Ｓｔｅｐ３−１：ｕ←ｘｐ＋ｘｑ＋１（∈Ｆ３＾ｍ）
Ｓｔｅｐ３−２：
Ｓｔｅｐ３−２−１：ｔｕ←Ｔ（ｕ）
Ｓｔｅｐ３−２−２：ｕ２←Ｍ（ｔｕ，ｕ）
Ｓｔｅｐ３−２−３：ｄ←ｙｐｙｑ
Ｓｔｅｐ３−３：ｆ＝（ｃ０＋ｃ１ρ＋ｃ２ρ２）＋（ｃ３＋ｃ４ρ＋ｃ５ρ２）σとする。
【００４２】
Ｓｔｅｐ３−３−１：ｔｄ←Ｔ（ｄ）
Ｓｔｅｐ３−３−２：
ｄ０  ←  Ｍ（ｔｄ，ｃ０）
ｄ１  ←  Ｍ（ｔｄ，ｃ１）
ｄ２  ←  Ｍ（ｔｄ，ｃ２）
ｄ３  ←  Ｍ（ｔｄ，ｃ３）
ｄ４  ←  Ｍ（ｔｄ，ｃ４）
ｄ５  ←  Ｍ（ｔｄ，ｃ５）
Ｓｔｅｐ３−３−３：ｔｕ＾２←Ｔ（ｕ２）
Ｓｔｅｐ３−３−４：
ｅ１  ←  Ｍ（ｔｕ，ｃ０）
ｅ０  ←  Ｍ（ｔｕ，ｅ１）
ｅ１  ←  Ｍ（ｔｕ＾２，ｃ１）＋ｅ１
ｅ３  ←  Ｍ（ｔｕ，ｃ２）＋ｃ１
ｅ２  ←  Ｍ（ｔｕ，ｅ３）＋ｃ０
ｅ４  ←  ｃ２
ｅ０  ←  ｅ０＋ｅ３
ｅ１  ←  ｅ１＋ｅ３＋ｅ４
ｅ２  ←  ｅ２＋ｅ４
Ｓｔｅｐ３−３−５：
ｆ１  ←  Ｍ（ｔｕ，ｃ３）
ｆ０  ←  Ｍ（ｔｕ，ｆ１）
ｆ１  ←  Ｍ（ｔｕ＾２，ｃ４）＋ｆ１
ｆ３  ←  Ｍ（ｔｕ，ｃ５）＋ｃ４
ｆ２  ←  Ｍ（ｔｕ，ｆ３）＋ｃ３
ｆ４  ←  ｃ５
ｆ０  ←  ｆ０＋ｆ３
ｆ１  ←  ｆ１＋ｆ３＋ｆ４
ｆ２  ←  ｆ２＋ｆ４
Ｓｔｅｐ３−３−６：
ｃ０  ←  −ｄ０−ｅ０
ｃ１  ←  −ｄ１−ｅ１
ｃ２  ←  −ｄ２−ｅ２
ｃ３  ←  ｄ３−ｆ０
ｃ４  ←  ｄ４−ｆ１
ｃ５  ←  ｄ５−ｆ２
Ｓｔｅｐ３−３−７：ｆ←（ｃ０＋ｃ１ρ＋ｃ２ρ２）＋（ｃ３＋ｃ４ρ＋ｃ５ρ２）σ
Ｓｔｅｐ３−４：ｘｐ←ｘｐ（１／３），ｙｐ←ｙｐ（１／３）
Ｓｔｅｐ３−５：ｘｑ←ｘｑ３，ｙｑ←ｙｑ３
Ｓｔｅｐ４：ｆ（（３＾３ｍ）−１）（（３＾ｍ）＋１）（（３＾ｍ）−（３＾（（ｍ＋１）／２））＋１）を出力する。
【００４３】
［第二のηＴペアリング演算アルゴリズム］
以下に、本発明をηＴペアリングに適用した場合の第二のηＴペアリング演算アルゴリズムを示す。この第二のηＴペアリング演算アルゴリズムは、上記（３）式、（４）式において、ｕ２を乗数とする演算は行わず、ｕを乗数とする、ｃ２ｕ，（ｃ２ｕ）ｕ，ｃ１ｕ，（ｃ１ｕ）ｕ，ｃ０ｕ，（ｃ０ｕ）ｕ，ｃ５ｕ，（ｃ５ｕ）ｕ，ｃ４ｕ，（ｃ４ｕ）ｕ，ｃ３ｕ，（ｃ３ｕ）ｕ，という１２回の演算が行う場合のアルゴリズムである。すなわち、Ｓｔｅｐ３−２、Ｓｔｅｐ３−３において、事前演算として、ｕ、ｙｐとｙｑの何れか一方、ｄをそれぞれ乗数とする計３つの事前演算テーブルを作成して、そのうちｕ、ｄを乗数とする事前演算テーブルについては使いまわす場合のアルゴリズムである。
【００４４】
なお、下記Ｓｔｅｐ３−３−３は上記式（３）の演算に対応したステップであり、下記Ｓｔｅｐ３−３−４は上記式（４）の演算に対応したステップであり、下記Ｓｔｅｐ３−３−５はリダクションをしているステップである。
【００４５】
〔準備〕Ｅ（Ｆ３＾ｍ）：有限体Ｆ３＾ｍ上定義された楕円曲線
ｇ１（ρ）＝ρ３−ρ−１
ｇ２（σ）＝σ２＋１
Ｆ３＾（６ｍ）の元は、Ｆ３＾（ｍ）［ρ，σ］／（ｇ１（ρ），ｇ２（σ））の元として表現する。
〔入力〕Ｐ＝（ｘｐ，ｙｐ），Ｑ＝（ｘｑ，ｙｑ）∈Ｅ（Ｆ３＾ｍ）
〔出力〕ηＴ（Ｐ，Ｑ）∈Ｆ＊３＾（６ｍ）
〔計算方法〕
Ｓｔｅｐ１：ｙｐ←−ｙｐ（∈Ｆ３＾ｍ）
Ｓｔｅｐ２：ｆ←−ｙｐ（ｘｐ＋ｘｑ＋１）＋ｙｑσ＋ｙｐρ（∈Ｆ３＾（６ｍ））
Ｓｔｅｐ３：ｉ＝０から（ｍ−１）／２までＳｔｅｐ３−１〜Ｓｔｅｐ３−５を繰り返す。
【００４６】
Ｓｔｅｐ３−１：ｕ←ｘｐ＋ｘｑ＋１（∈Ｆ３＾ｍ）
Ｓｔｅｐ３−２：
Ｓｔｅｐ３−２−１：ｔｕ←Ｔ（ｕ）
Ｓｔｅｐ３−２−２：ｄ←ｙｐｙｑ
Ｓｔｅｐ３−３：ｆ＝（ｃ０＋ｃ１ρ＋ｃ２ρ２）＋（ｃ３＋ｃ４ρ＋ｃ５ρ２）σとする。
【００４７】
Ｓｔｅｐ３−３−１：ｔｄ←Ｔ（ｄ）
Ｓｔｅｐ３−３−２：
ｄ０  ←  Ｍ（ｔｄ，ｃ０）
ｄ１  ←  Ｍ（ｔｄ，ｃ１）
ｄ２  ←  Ｍ（ｔｄ，ｃ２）
ｄ３  ←  Ｍ（ｔｄ，ｃ３）
ｄ４  ←  Ｍ（ｔｄ，ｃ４）
ｄ５  ←  Ｍ（ｔｄ，ｃ５）
Ｓｔｅｐ３−３−３：
ｅ４  ←  ｃ２
ｅ３  ←  Ｍ（ｔｕ，ｅ４）
ｅ２  ←  Ｍ（ｔｕ，ｅ３）
ｅ３  ←  ｅ３＋ｃ１
ｅ１  ←  Ｍ（ｔｕ，ｃ１）
ｅ２  ←  ｅ２＋ｅ１
ｅ１  ←  Ｍ（ｔｕ，ｅ１）
ｅ２  ←  ｅ２＋ｃ０
ｅ０  ←  Ｍ（ｔｕ，ｃ０）
ｅ１  ←  ｅ１＋ｅ０
ｅ０  ←  Ｍ（ｔｕ，ｅ０）
ｅ０  ←  ｅ０＋ｅ３
ｅ１  ←  ｅ１＋ｅ３＋ｅ４
ｅ２  ←  ｅ２＋ｅ４
Ｓｔｅｐ３−３−４：
ｆ４  ←  ｃ５
ｆ３  ←  Ｍ（ｔｕ，ｆ４）
ｆ２  ←  Ｍ（ｔｕ，ｆ３）
ｆ３  ←  ｆ３＋ｃ４
ｆ１  ←  Ｍ（ｔｕ，ｃ４）
ｆ２  ←  ｆ２＋ｆ１
ｆ１  ←  Ｍ（ｔｕ，ｆ１）
ｆ２  ←  ｆ２＋ｃ３
ｆ０  ←  Ｍ（ｔｕ，ｃ３）
ｆ１  ←  ｆ１＋ｆ０
ｆ０  ←  Ｍ（ｔｕ，ｆ０）
ｆ０  ←  ｆ０＋ｆ３
ｆ１  ←  ｆ１＋ｆ３＋ｆ４
ｆ２  ←  ｆ２＋ｆ４
Ｓｔｅｐ３−３−５：
ｃ０  ←  −ｄ０−ｅ０
ｃ１  ←  −ｄ１−ｅ１
ｃ２  ←  −ｄ２−ｅ２
ｃ３  ←  ｄ３−ｆ０
ｃ４  ←  ｄ４−ｆ１
ｃ５  ←  ｄ５−ｆ２
Ｓｔｅｐ３−３−６：ｆ←（ｃ０＋ｃ１ρ＋ｃ２ρ２）＋（ｃ３＋ｃ４ρ＋ｃ５ρ２）σ
Ｓｔｅｐ３−４：ｘｐ←ｘｐ（１／３），ｙｐ←ｙｐ（１／３）
Ｓｔｅｐ３−５：ｘｑ←ｘｑ３，ｙｑ←ｙｑ３
Ｓｔｅｐ４：ｆ（（３＾３ｍ）−１）（（３＾ｍ）＋１）（（３＾ｍ）−（３＾（（ｍ＋１）／２））＋１）を出力する。
【００４８】
［変形例等］
ηＴペアリングを例に説明をしたが、本発明は、ηＴペアリング以外のペアリング演算にも適用することが可能である。
【００４９】
事前演算部１０にリダクション部１０１を設けて、事前演算部１０が演算した演算結果を所定の既約多項式によりリダクションしてもよい。これにより、項数Ｗｓの多項式の各組と、リダクション部１０１によってリダクションされた各演算結果とが対応付けられた事前演算テーブルが、事前演算テーブル記憶部１１に記憶されることになる。リダクションにより、事前演算テーブルのデータ量を少なくすることができる。
【００５０】
また、加算部１２３にリダクション部１２３１を設けて、加算部１２３が加算した加算結果を所定の既約多項式によりリダクションしてもよい。
【００５１】
また、適切なウィンドウサイズＷｓを定めるために、第一計測部１７と、ウィンドウサイズ決定部１６を設けてもよい。第一計測部１７は、複数のＷｓに基づいて所定のペアリング演算をそれぞれ行った場合に、そのペアリング演算をするのにかかった時間を複数のＷｓごとに計測する。ウィンドウサイズＷｓごとに計測された、ペアリング演算をするのにかかった時間は、ウィンドウサイズ決定部１６に送られる。ウィンドウサイズ決定部１６は、上記計測されたペアリング演算をするのにかかった時間を最小にするＷｓを選択する。そして、その最小にするＷｓをメモリ１５に設定する。これにより、ペアリング演算をするのにかかった時間を最小にするＷｓに基づいて上記事前演算手段に上記乗算をさせることが可能となる。
【００５２】
なお、例えば上記した第一のηＴペアリング演算アルゴリズム、第二のηＴペアリング演算アルゴリズムのように、同じペアリングの演算をするための方法は一般に複数ある。適切なペアリング演算アルゴリズムを決定するために、図１に例示するように、アルゴリズム記憶部４、第二計測部５、アルゴリズム決定部６を設けてもよい。アルゴリズム記憶部４には、同じペアリングを演算するための複数のペアリング演算アルゴリズムが格納されている。第二計測部５は、ペアリング演算部３が、上記アルゴリズム記憶部４から読み込んだ複数のペアリング演算アルゴリズムに基づいてペアリング演算をそれぞれ行った場合の、そのペアリング演算をするのにかかった時間を複数のペアリング演算アルゴリズムごとに計測する。ペアリング演算アルゴリズムごとに計測された時間は、アルゴリズム決定部６に送られる。アルゴリズム決定部６は、計測されたペアリング演算をするのにかかった時間を最小にするペアリング演算アルゴリズムを選択する。そして、その最小にするペアリング演算アルゴリズムに基づいて、ペアリング演算部３にペアリング演算をさせるように制御する。これにより、ペアリング演算をするのにかかる時間を最小にすることができ、さらにペアリング演算を高速に行うことができる。
【００５３】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００５４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００５５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５６】
また、上述した実施形態とは別の実行形態として、コンピュータが可搬型記録媒体から直接このプログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５７】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００５８】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【図面の簡単な説明】
【００５９】
【図１】ペアリング演算部３の機能構成を例示する図。
【図２】乗算演算部１の機能構成を例示する図。
【図３】事前演算テーブルを例示する図。
【符号の説明】
【００６０】
１     乗算演算部
２     制御部
３     ペアリング演算部
４     アルゴリズム記憶部
５     第二計測部
６     アルゴリズム決定部
１０   事前演算部
１１   事前演算テーブル記憶部
１２   積演算部
１３   第一制御部
１４   第二制御部
１５   メモリ
１６   ウィンドウサイズ決定部
１７   第一計測部
１０１ リダクション部
１２１ 分割部
１２２ 参照部
１２３ 加算部
１２３１      リダクション部
【図１】
0004856599.tif 000002
【図２】
0004856599.tif 000003
【図３】
0004856599.tif 000004