(57)【特許請求の範囲】
【請求項１】
楕円曲線ｙ２＝ｘ３−ｘ＋ｂ上の２点に対するペアリング値を算出するペアリング算出装置であって、
データを記憶する記憶部と、
２つの数値データの入力を受付けて、該数値データの積を出力する乗算部と、
２つの数値データの入力を受付けて、該数値データの和を出力する加算部と、
制御部とを備え、
前記制御部は、楕円曲線上の任意の点（ｘｐ、ｙｐ）に対し、前記乗算部にｙｐとｙｐとを入力してｙｐ２を算出し、該算出したｙｐ２を中間データ格納テーブルに格納し、前記中間データ格納テーブルに格納したｙｐ２と前記記憶部に格納したｘｐと−ｂとを順不同で前記加算部に入力してｘｐ３を算出し、前記中間データ格納テーブルに格納したｙｐ２と前記記憶部に格納したｙｐを前記乗算部に入力してｙｐ３を算出し、該算出したｘｐ３及びｙｐ３に基づきペアリング値を算出する
ことを特徴とするペアリング算出装置。
【請求項２】
前記ペアリング値はηＴペアリング値であり、
前記記憶部に、楕円曲線上の点（ｘｑ、ｙｑ）に対するｘｑ３と、所定の制御変数の値に基づくＡおよびＢと、所定の値であるＣ１とＣ２の値を記憶させておき、
前記制御部は、前記乗算部に該算出したｙｐ３とｙｐ３とを入力してｙｐ６を算出させて該記憶部に格納し、前記記憶部に格納したｘｑ３と前記算出したｘｐ３と前記記憶部に格納した所定の制御変数の値に基づくＡとを順不同で前記加算部に入力してＵ１を算出し、Ｕ１とＵ１を該乗算部に入力してＵ２を算出し、算出したＵ２を該記憶部に格納し、前記記憶部に格納した所定の制御変数の値に基づくＢと前記中間データ格納テーブルに格納したｙｐ２を該乗算部に入力してＵ３を算出し、算出したＵ３を該記憶部に格納し、前記記憶部に格納したＣ１とＵ１を該乗算部に入力してＵ４を算出し、算出したＵ４を該記憶部に格納し、前記記憶部に格納したＵ３と−Ｕ２と−Ｕ４と前記記憶部に格納した−Ｃ２とを順不同で該加算部に入力してＧを算出し、該算出したＧに基づきηＴペアリング値を算出する
ことを特徴とする請求項１に記載のペアリング算出装置。
【請求項３】
前記ペアリング値はテートペアリング値であり、
前記制御部は、前記記憶部に前記算出したｙｐ３を格納し、前記乗算部に該算出したｙｐ３とｙｐ３とを入力してｙｐ６を算出させて該記憶部に格納し、該記憶部に格納したｙｐ６と前記算出したｘｐ３と−ｂとを順不同で前記加算部に入力してｘｐ９を算出し、算出したｘｐ９を該記憶部に格納し、該記憶部に格納したｙｐ６とｙｐ６とｙｐ６とを順不同で該乗算部に入力してｙｐ１８を算出し、算出したｙｐ１８を該記憶部に格納し、該記憶部に格納したｙｐ１８とｘｐ９と−ｂを順不同で該加算部に入力してｘｑ２７を算出し、該記憶部に格納したｙｐ１８とｙｐ６とｙｐ３とを順不同で該乗算部に入力してｙｐ２７を算出し、該算出したｘｑ２７及びｙｐ２７に基づきテートペアリング値を算出する
ことを特徴とする請求項１に記載のペアリング算出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ペアリング算出装置に関する。
【背景技術】
【０００２】
楕円曲線上に定義されたペアリングとよばれる関数を利用して、公開鍵暗号方式による情報の暗号化および復号化を実現する技術が知られている。以下の説明においてペアリングを用いた暗号をペアリング暗号と表記する。ペアリング暗号は、ＩＤ（Identification）を公開鍵とするＩＤベース暗号やaggregate署名などを構築できる。
【０００３】
ここで、要素数３ｍの有限体ＧＦ（３ｍ）上の楕円曲線を例にして説明する。楕円曲線の方程式は、
Ｅ：ｙ２＝ｘ３＋ａｘ＋ｂ
によって表される。有限体ＧＦ（３ｍ）上の楕円曲線Ｅは、Ｅの方程式を満たす点（ｘ，ｙ）の集合に、無限遠点と呼ばれる点∞を加えた集合である。無限遠点を０と表すこともある。Ｅの方程式に含まれるａ、ｂは定数であり、ｘ、ｙは変数である。定数ａ，ｂ、変数ｘ、ｙは、有限体ＧＦ（３ｍ）の要素である。
【０００４】
楕円曲線上の点は（ｘ、ｙ）のようなアファイン座標で表現できるが、無限遠点はアファイン座標で表現できない。したがって、アファイン座標では無限遠点を除く点を、有限体ＧＦ（３ｍ）の２つの要素の組として表す。楕円曲線Ｅ上の点の間には点の加算と呼ばれる演算が可能である。この点の加算は、有限体ＧＦ（３ｍ）における加減乗除の組合せによって計算される。
【０００５】
続いて、ペアリングについて説明する。ペアリングは２入力１出力関数で、３つの群Ｇ１、Ｇ２、Ｇ３に対して、写像ｅ：Ｇ×Ｇ→Ｇで定義される。また、ペアリングの写像ｅは、下記に示す性質１および性質２を満たす。
ｅ（ａｕ＋ｂｖ，ｘ）＝ａ・ｅ（ｕ，ｘ）＋ｂ・ｅ（ｖ，ｘ）・・・性質１
ｅ（ｕ，ｃｘ＋ｄｚ）＝ｃ・ｅ（ｕ，ｘ）＋ｄ・ｅ（ｖ，ｘ）・・・性質２
【０００６】
様々なペアリングが知られているが、暗号の分野ではテートペアリングと呼ばれるペアリングが利用されることがある。以下において、テートペアリングについて説明する。ｑ＝３ｍとし、有限体ＧＦ（ｑ）上の楕円曲線Ｅを固定する。整数ｒを楕円曲線Ｅの点の個数の約数とする。楕円曲線Ｅの点の個数を位数といい、＃Ｅと書く。ｒがｑｋ−１の約数となるような最小の自然数をｋとして選択する。ｋを埋め込み次数という。このときテートペアリングｅＴは、楕円曲線Ｅの有限体ＧＦ（ｑ）上の点Ｐと有限体ＧＦ（ｑｋ）上の点Ｑに対して、１のｒ乗根の集合の要素であるｅＴ（Ｐ，Ｑ）を出力する写像である。
【０００７】
なお、標数３の有限体では、係数３を有する演算を０とみなすことができる。例えば、
（ａ＋ｂ）３＝ａ３＋ｂ３
の関係が成り立ち、３ａｂ２、３ａｂ２を０とみなすことができる。したがって、３乗計算は２乗計算よりも高速に計算が可能となる。このため、従来のテートペアリングでは、３乗計算を多用することで計算時間を短縮している。
【０００８】
以下に、テートペアリングの計算方法の一例を示す。標数３の有限体ＧＦ（ｑ）上の楕円曲線をＥ：ｙ２＝ｘ３−ｘ＋ｂとし、写像φを（ｘ，ｙ）＝（ρ−ｘ，σｙ）とする。ただし、ｍと６とは互いに素な正整数、ｑ＝３ｍ、ｂ＝±１であるとする。また、σ、ρはσ２＋１＝０、ρ３−ρ−ｂ＝０を満たす有限体ＧＦ（ｑ６）の元とする。
【０００９】
以上の前提で、テートペアリングの計算手順を説明する。図１０は、テートペアリングの計算手順を示すフローチャートである。図１０に示すように、計算装置は、楕円曲線上の２点Ｐ＝（α，β）、Ｑ＝（ｘ，ｙ）を取得し（ステップＳ１０）、ｆに１を代入する（ステップＳ１１）。
【００１０】
計算装置は、ｘ３を算出し、算出結果をｘに代入する（ステップＳ１２）。計算装置は、ｙ３を算出し、算出結果をｙに代入する（ステップＳ１３）。計算装置は、ｄ＝（ｍ−１）・ｂを算出し、算出結果をｄに代入する（ステップＳ１４）。計算装置は、ｘ３を算出し、算出結果をｘ’に代入する（ステップＳ１５）。計算装置は、ｙ３を算出し、算出結果をｙ’に代入する（ステップＳ１６）。
【００１１】
計算装置は、ｉに１を代入し（ステップＳ１７）、「ｉ＞（ｍ−１）／２」となるか否かを判定する（ステップＳ１８）。「ｉ＞（ｍ−１）／２」となる場合には（ステップＳ１８，Ｙｅｓ）、計算装置は、α３を算出し、算出結果をαに代入する（ステップＳ１９）。
【００１２】
計算装置は、β３を算出し算出結果をβに代入する（ステップＳ２０）。計算装置は、α＋ｘ’＋ｂを算出し、算出結果をμに代入する（ステップＳ２１）。計算装置は、σ・β・ｙ−μ２を算出し、算出結果をλに代入する（ステップＳ２２）。計算装置は、λ−μρ−ρ２を算出し、算出結果をｇに代入する（ステップＳ２３）。
【００１３】
計算装置は、ｆ３・ｇを算出し、算出結果をｆに代入する（ステップＳ２４）。計算装置は、ｑ３の値をｑ’に代入する（ステップＳ２５）。計算装置は、ｆｑ’−１を算出し、算出結果をｅＴ（Ｐ，φ（Ｑ））に代入する（ステップＳ２６）。そして、計算装置は、ｅＴ（Ｐ，φ（Ｑ））を出力する（ステップＳ２７）。
【００１４】
一方、「ｉ≦（ｍ−１）／２」となる場合には（ステップＳ１８，Ｎｏ）、計算装置は、α２７を算出し、算出結果をαに代入する（ステップＳ２８）。計算装置は、β２７を算出し、算出結果をβに代入する（ステップＳ２９）。計算装置は、α＋ｘ’＋ｄを算出し、算出結果をμに代入する（ステップＳ３０）。
【００１５】
計算装置は、−αβｙ’−μ２を算出し、算出結果をλに代入する（ステップＳ３１）。計算装置は、λ−μρ−ρ２を算出し、算出結果をｇ１に代入する（ステップＳ３２）。計算装置は、α３を算出し、算出結果をαに代入する（ステップＳ３３）。計算装置は、β３を算出し、算出結果をβに代入する（ステップＳ３４）。
【００１６】
計算装置は、α＋ｘ＋ｄを算出し、算出結果をμに代入する（ステップＳ３５）。計算装置は、−αβｙ−μ２を算出し、算出結果をλに代入する（ステップＳ３６）。計算装置は、λ−μρ−ρ２を算出し、算出結果をｇ２に代入する（ステップＳ３７）。計算装置は、ｇ１・ｇ２を算出し、算出結果をｇに代入する（ステップＳ３８）。
【００１７】
計算装置は、ｆ９・ｇを算出し、算出結果をｆに代入する（ステップＳ３９）。計算装置は、ｄ−２ｂを算出し、算出結果をｄに代入する（ステップＳ４０）。計算装置は、ｉ＋１を算出し、算出結果をｉに代入し（ステップＳ４１）、ステップＳ１８に移行する。
【００１８】
図１０に示した計算手順で計算装置が計算を行うことにより、楕円曲線の２点Ｐ＝（α，β）、Ｑ＝（ｘ，ｙ）から、テートペアリングの計算結果ｅＴ（Ｐ，φ（Ｑ））が得られる。
【００１９】
暗号の分野では、標数３の有限体上の楕円曲線におけるηＴペアリングというペアリングが使用されることがある。非特許文献１に示されているηＴペアリングの具体的な計算手順を以下に説明する。図１１は、ηＴペアリングの計算手順を示すフローチャートである。図１１に示すように、計算装置は、楕円曲線上の２点Ｐ＝（ｘｐ，ｙｐ）、Ｑ＝（ｘｑ，ｙｑ）を取得し（ステップＳ５０）、ｂの値が１であるか否かを判定する（ステップＳ５１）。
【００２０】
計算装置は、ｂの値が１以外の場合には（ステップＳ５１，Ｎｏ）、ステップＳ５３に移行する。計算装置は、ｂの値が１の場合には（ステップＳ５１，Ｙｅｓ）、−ｙｐの値をｙｐに代入する（ステップＳ５２）。計算装置は、ｘｐ＋ｘｑ＋ｄを算出し、算出結果をｕに代入する（ステップＳ５３）。計算装置は、ｂの値をｄに代入する（ステップＳ５４）。
【００２１】
計算装置は、σｙｑ−ｕｙｐ＋ρｙｐを算出し、算出結果をｆに代入する（ステップＳ５５）。計算装置は、ｊに０を代入し（ステップＳ５６）、「ｊ＞（ｍ−１）／２」となるか否かを判定する（ステップＳ５７）。計算装置は、「ｊ＞（ｍ−１）／２」となる場合には（ステップＳ５７，Ｙｅｓ）、ｆ２／３（ｍ＋１）を算出し、算出結果をｆに代入する（ステップＳ５８）。計算装置は、ｆを出力する（ステップＳ５９）。ステップＳ５９で計算装置が出力するｆは、ηＴ（Ｐ，Ｑ）に対応する。
【００２２】
一方、「ｊ≦（ｍ−１）／２」となる場合には（ステップＳ５７，Ｎｏ）、ｘｐ＋ｘｑ＋ｄを算出し、算出結果をｕに代入する（ステップＳ６０）。計算装置は、σｙｐｙｑ−ｕ２−ρｕ−ρ２を算出し、算出結果をｇに代入する（ステップＳ６１）。計算装置は、（ｆｇ）３を算出し、算出結果をｆに代入する（ステップＳ６２）。
【００２３】
計算装置は、−ｙｐの値をｙｐに代入する（ステップＳ６３）。計算装置は、ｘｑ９を算出し、算出結果をｘｑに代入する（ステップＳ６４）。計算装置は、ｙｑ９を算出し、算出結果をｙｑに代入する（ステップＳ６５）。計算装置は、ｄ−ｂを３で割った余りをｄに代入し（ステップＳ６６）、ステップＳ５７に移行する。
【００２４】
図１１に示した計算手順で計算装置が計算を行うことにより、楕円曲線の２点Ｐ＝（ｘｐ，ｙｐ）、Ｑ＝（ｘｑ，ｙｑ）から、ηＴペアリングの計算結果ηＴ（Ｐ，Ｑ）が得られる。
【先行技術文献】
【特許文献】
【００２５】
【特許文献１】特開２００６−１７８１２５号公報
【非特許文献】
【００２６】
【非特許文献１】岡本栄司、岡本健、金山直樹、「ペアリングに関する最近の研究動向」
【発明の概要】
【発明が解決しようとする課題】
【００２７】
ペアリング暗号が現代社会において広く用いられるためには、様々な処理プラットフォームにおいて、処理時間の低減および実装上必要となる回路規模の低減が求められる。
【００２８】
従来のペアリングは、標数３の有限体の特性から、３乗計算を多用することで処理の高速化を図っている。しかし、ＦＰＧＡ（Field  Programmable  Gate  Array）等の回路に３乗計算を利用するペアリングを実装する場合、乗算回路の他に３乗算回路が必要となり、回路規模が大きくなってしまうという問題があった。
【００２９】
開示の技術は、上記に鑑みてなされたものであって、３乗算回路を用いずに、標数３の有限体上の楕円曲線におけるペアリングを高速に計算することを目的とする。すなわち、処理性能を確保しつつ、回路規模を低減させることができるペアリング算出装置を提供することを目的とする。
【課題を解決するための手段】
【００３０】
本願の開示するペアリング算出装置は、一つの態様において、楕円曲線ｙ２＝ｘ３−ｘ＋ｂ上の２点に対するペアリング値を算出するペアリング算出装置である。本願の開示するペアリング算出装置は、データを記憶する記憶部と、２つの数値データの入力を受付けて、該数値データの積を出力する乗算部と、２つの数値データの入力を受付けて、該数値データの和を出力する加算部と、制御部とを備える。制御部は、楕円曲線上の任意の点（ｘｐ、ｙｐ）に対し、乗算部にｙｐとｙｐとを入力してｙｐ２を算出させて記憶部に格納し、記憶部に格納したｙｐ２とｘｐと−ｂとを順不同で加算部に入力した後に加算部から得られる出力をｘｐ３とする。また、記憶部に格納したｙｐ２とｙｐを乗算部に入力した後に乗算部から得られる出力をｙｐ３とし、算出したｘｐ３及びｙｐ３に基づきペアリング値を算出することを要件とする。
【発明の効果】
【００３１】
本願の開示するペアリング算出装置の一つの態様によれば、３乗算回路を用いずに、標数３の有限体上の楕円曲線におけるペアリングを高速に計算できる。すなわち、処理性能を確保しつつ、回路規模を低減することができるという効果を奏する。
【図面の簡単な説明】
【００３２】
【図１】図１は、本実施例１にかかるペアリング算出装置の構成を示す図である。
【図２】図２は、本実施例２にかかるペアリング算出装置の構成を示す図である。
【図３】図３は、事前計算テーブルが記憶する各パラメータの値を説明する図である。
【図４】図４は、本実施例２にかかる制御部の処理手順を示すフローチャートである。
【図５】図５は、従来例の計算量と実施例２の計算量とを示す図である。
【図６】図６は、本実施例３にかかるペアリング算出装置の構成を示す図である。
【図７】図７は、本実施例３にかかる制御部の処理手順を示すフローチャート（１）である。
【図８】図８は、本実施例３にかかる制御部の処理手順を示すフローチャート（２）である。
【図９】図９は、従来例の計算量と実施例３の計算量とを示す図である。
【図１０】図１０は、テートペアリングの計算手順を示すフローチャートである。
【図１１】図１１は、ηＴペアリングの計算手順を示すフローチャートである。
【発明を実施するための形態】
【００３３】
以下に、本願の開示するペアリング算出装置の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例１】
【００３４】
本実施例１にかかるペアリング算出装置について説明する。図１は、本実施例１にかかるペアリング算出装置の構成を示す図である。ペアリング算出装置１００は、楕円曲線ｙ２＝ｘ３＋ｘ＋ｂ上の２点に対するペアリング値を算出する装置である。図１に示すように、ペアリング装置１００は、記憶部１１０、加算部１２０、乗算部１３０、制御部１４０を有する。
【００３５】
記憶部１１０は、データを記憶する装置である。加算部１２０は、２つの数値データの入力を受付けて、数値データの和を出力する装置である。乗算部１３０は、２つの数値データの入力を受付けて、数値データの積を出力する装置である。
【００３６】
制御部１４０は、記憶部１１０、加算部１２０、乗算部１３０を用いてペアリング値を算出する装置である。具体的に、制御部１４０は、楕円曲線上の任意の点（ｘｐ、ｙｐ）に対し、乗算部１３０にｙｐとｙｐとを入力してｙｐ２を算出させて記憶部１１０に格納する。制御部１４０は、加算部１２０に記憶部１１０に格納したｙｐ２とｘｐと−ｂとを順不同で入力した出力をｘｐ３とする。制御部１４０は、乗算部１３０に記憶部１１０に格納したｙｐ２とｙｐを入力した出力をｙｐ３とし、算出したｘｐ３及びｙｐ３に基づきペアリング値を算出する。
【００３７】
本実施例１にかかるペアリング算出装置１００は、３乗計算を実施する３乗算回路の代わりに、楕円曲線上の点の特性を利用して、加算部１２０および乗算部１３０を用いてペアリング値を算出するので、回路規模の増大を防止することができる。具体的には、楕円曲線上の点はｙ２＝ｘ３−ｘ＋ｂが成り立つ。このため、ペアリング算出装置１００は、ｙ２＋ｘ−ｂをｘ３として取り扱うことで、３乗算回路を用いることなく、ペアリング値の算出を可能にする。
【実施例２】
【００３８】
次に、本実施例２にかかるペアリング演算装置について説明する。本実施例２では、ηＴペアリング値を算出する場合について説明する。図２は、本実施例２にかかるペアリング算出装置の構成を示す図である。図２に示すように、このペアリング算出装置２００は、入力部２１０、出力部２２０、事前計算テーブル２３０、中間データ格納テーブル２４０、加算部２５０、乗算部２６０を有する。
【００３９】
入力部２１０は、外部の入力装置を介して、楕円曲線のパラメータと演算対象となるデータとを取得し、取得した楕円曲線のパラメータと演算対象となるデータを制御部２７０に入力する処理部である。
【００４０】
楕円曲線のパラメータは、ｑ、ｂ、σ、ρを含む。ｑは３ｍに対応する（ｑ＝３ｍ）。ｑを特定するｍは、６と互いに素な正整数である。ｂは１または−１の値である（ｂ＝±１）。σは、σ２＋１＝０を満たす有限体ＧＦ（ｑ６）の元とする。ρは、ρ３−ρ−ｂ＝０を満たす有限体ＧＦ（ｑ６）の元とする。
【００４１】
演算対象となるデータは、楕円曲線上の２点を示すＰ，Ｑである。実施例２では一例として、Ｐ＝（ｘｐ、ｙｐ）とし、Ｑ＝（ｘｑ、ｙｑ）とする。
【００４２】
出力部２２０は、ペアリングの算出結果となるηＴペアリング値ηＴ（Ｐ，Ｑ）を、制御部２７０から取得し、取得したηＴペアリング値を外部の装置等に出力する処理部である。
【００４３】
事前計算テーブル２３０は、ηＴペアリング値の計算に利用するパラメータを記憶する記憶部である。事前計算テーブル２３０が記憶するパラメータは、Ａ０、Ａ１、Ａ２、Ｂ０、Ｂ１、Ｂ２、Ｃ１、Ｃ２、Ｒ１、Ｒ２を含む。各パラメータに対応する値の説明は後述する。
【００４４】
中間データ格納テーブル２４０は、ηＴペアリング計算における中間の計算結果を必要に応じて記憶する記憶部である。加算部２５０は、２つの数値データを制御部２７０から受付けて、数値データの和を制御部２７０に出力する回路である。乗算部２６０は、２つの数値データを制御部２７０から受付けて、数値データの積を制御部２７０に出力する回路である。
【００４５】
制御部２７０は、事前計算テーブル２３０、中間データ格納テーブル２４０、加算部２５０、乗算部２６０を用いてηＴペアリング値を算出する処理部である。制御部２７０がηＴペアリング値を算出する場合には、標数３の有限体上の楕円曲線を利用する。標数３の有限体（ｑ）上の楕円曲線をＥ：ｙ２＝ｘ３−ｘ＋ｂ、写像φ：（ｘ、ｙ）＝（ρ−ｘ、σｙ）とする。
【００４６】
なお、制御部２７０は、３乗演算を実行する３乗回路を用いることがない。楕円曲線上の任意の点（ｘｐ、ｙｐ）に対しｘｐ３＝ｙｐ２＋ｘｐ−ｂの関係が成り立つため、制御部２７０は、ｙｐ２、ｘｐ、ｂの値をもとめることで、３乗回路を用いなくてもｘｐ３の値をもとめることができる。具体的に、制御部２７０は、ｙｐとｙｐとを乗算部２６０に入力してｙｐ２を算出させ、中間データ格納テーブル２４０にｙｐ２を格納しておく。そして、制御部２７０は、ｘｐと−ｂと中間データ格納テーブル２４０に格納されたｙｐ２を順不同で加算部２５０に入力することで、ｘｐ３を算出する。
【００４７】
ηＴペアリング値を算出するために必要となるその他の値は、制御部２７０が、事前計算テーブル２３０、中間データ格納テーブル２４０、加算部２５０、乗算部２６０を組合せて利用することで算出する。例えば、制御部２７０が、ｙｐ３を算出する場合には、ｙｐと中間データ格納テーブル２４０に格納されたｙｐ２を乗算部２６０に入力することで、ｙｐ３を算出する。
【００４８】
次に、事前計算テーブル２３０が記憶する各パラメータの値について説明する。図３は、事前計算テーブル２３０が記憶する各パラメータの値を説明する図である。図３に示すように、Ａ０はｂの値を格納し、Ａ１は０を格納し、Ａ２は−ｂの値を格納する。
【００４９】
Ｂ０は（σｙｑ）３の値を格納し、Ｂ１は−Ｂ０の値を格納する。ここで、制御部２７０が（σｙｑ）３を算出する処理の一例を説明する。制御部２７０は、σとｙｑとを乗算部２６０に入力してσｙｑを算出させ、中間データ格納テーブル２４０にσｙｑを格納する。制御部２７０は、中間データ格納テーブル２４０に格納されたσｙｑを乗算部２６０に２つ入力して（σｙｑ）２を算出させ、中間データ格納テーブル２４０に（σｙｑ）２を格納する。そして、制御部２７０は、中間データ格納テーブル２４０に格納された（σｙｑ）２とσｙｑとを乗算部２６０に入力して（σｙｑ）３を算出する。
【００５０】
Ｃ１はρ３の値を格納し、Ｃ２はρ６の値を格納する。まず、制御部２７０が、ρ３を算出する処理の一例を説明する。制御部２７０は、乗算部２６０にρを２つ入力してρ２を算出させ、中間データ格納テーブル２４０にρ２を格納する。そして、制御部２７０は、ρと中間データ格納テーブル２４０に格納されたρ２を乗算部２６０に入力してρ３を算出する。
【００５１】
続いて、制御部２７０が、ρ６を算出する処理の一例を説明する。ただし、制御部２７０はρ３を算出済みとする。制御部２７０は、事前計算テーブル２３０に格納されたρ３を乗算部２６０に２つ入力してρ６を算出する。
【００５２】
Ｒ１はｘｑ３の値を格納し、Ｒ２はｘｑ６の値を格納する。まず、制御部２７０がｘｑ３を算出する処理の一例を説明する。制御部２７０は、乗算部２６０にｘｑを２つ入力してｘｑ２を算出させ、中間データ格納テーブル２４０にｘｑ２を格納する。そして、制御部２７０は、ｘｑと中間データ格納テーブル２４０に格納されたｘｑ２を乗算部２６０に入力してｘｑ３を算出する。なお、制御部２７０は、楕円曲線の関係を利用して、ｘｑ３を算出してもよい。
【００５３】
続いて、制御部２７０が、ｘｑ６を算出する処理の一例を説明する。ただし、制御部２７０はｘｑ３を算出済みとする。制御部２７０は、事前計算テーブル２３０に格納されたｘｑ３を乗算部２６０に２つ入力してｘｑ６を算出する。
【００５４】
次に、ηＴペアリング値を算出する場合の制御部２７０の処理手順について説明する。図４は、制御部２７０の処理手順を示すフローチャートである。図４に示すように、制御部２７０は、楕円曲線のパラメータと楕円曲線上の２点Ｐ＝（ｘｐ、ｙｐ）、Ｑ＝（ｘｑ、ｙｑ）とを取得し（ステップＳ１０１）、ｂの値が１であるか否かを判定する（ステップＳ１０２）。制御部２７０は、ｂの値が１以外の場合には（ステップＳ１０２，Ｎｏ）、ステップＳ１０４に移行する。
【００５５】
一方、制御部２７０は、ｂの値が１の場合には（ステップＳ１０２，Ｙｅｓ）、−ｙｐの値をｙｐに代入する（ステップＳ１０３）。制御部２７０は、ｘｐ＋ｘｑ＋ｂを算出し、算出結果をｕに代入する（ステップＳ１０４）。
【００５６】
ステップＳ１０４において、制御部２７０は、ｘｐ、ｘｑ、ｂを順不同で加算部２５０に入力することで、ｘｐ＋ｘｑ＋ｂを算出する。制御部２７０は、算出結果をｕに格納し、ｕを中間データ格納テーブル２４０に格納する。
【００５７】
制御部２７０は、ｂの値をｄに代入する（ステップＳ１０５）。ステップＳ１０５において、制御部２７０は、ｂの値をｄに代入し、ｄを中間データ格納テーブル２４０に格納する。
【００５８】
制御部２７０は、σｙｑ−ｕｙｐ＋ρｙｐを算出し、算出結果をｆに代入する（ステップＳ１０６）。ステップＳ１０６において、制御部２７０は、σとｙｑとを乗算部２６０に入力することで、σｙｑを算出し、算出結果を中間データ格納テーブル２４０に格納する。制御部２７０は、ｕとｙｐとを乗算部２６０に入力することで、ｕｙｐを算出し、算出結果を中間データ格納テーブル２４０に格納する。制御部２７０は、ρとｙｐとを乗算部２６０に入力することで、ρｙｐを算出し、算出結果を中間データ格納テーブル２４０に格納する。そして、制御部２７０は、中間データ格納テーブル２４０に格納されたσｙｑ、ｕｙｐ、ρｙｐを順不同で加算部２５０に入力することで、σｙｑ＋ｕｙｐ＋ρｙｐを算出する。制御部２７０は、σｙｑ＋ｕｙｐ＋ρｙｐの算出結果をｆに代入し、ｆを中間データ格納テーブル２４０に格納する。
【００５９】
制御部２７０は、Ａ０、Ａ１、Ａ２、Ｂ０、Ｂ１、Ｃ１、Ｃ２、Ｒ１、Ｒ２を算出し、算出結果を事前計算テーブル２３０に格納する（ステップＳ１０７）。ステップＳ１０７における制御部２７０の具体的な処理は、図３において説明した処理と同様である。
【００６０】
制御部２７０は、ｊに０を代入し（ステップＳ１０８）、「ｊ＞（ｍ−１）／２」となるか否かを判定する（ステップＳ１０９）。「ｊ＞（ｍ−１）／２」となる場合には（ステップＳ１０９，Ｙｅｓ）、制御部２７０は、ｆを出力する（ステップＳ１１０）。ステップＳ１１０で出力されるｆが、ηＴペアリング値に対応する。
【００６１】
一方、「ｊ≦（ｍ−１）／２」となる場合には（ステップＳ１０９，Ｎｏ）、制御部２７０は、ｙｑ２の値を算出し、算出結果をＹ１に代入する（ステップＳ１１１）。ステップＳ１１１において、制御部２７０は、ｙｑを２つ乗算部２６０に入力することで、ｙｑ２を算出し、算出したｙｑ２の値をＹ１に代入する。制御部２７０は、Ｙ１を中間データ格納テーブル２４０に格納する。
【００６２】
制御部２７０は、Ｙ１＋ｘｐ−ｂを算出し、算出結果をＸ１に代入する（ステップＳ１１２）。ステップＳ１１２において、制御部２７０は、Ｙ１、ｘｐ、−ｂを順不同で加算部２５０に入力することで、Ｙ１＋ｘｐ−ｂを算出し、算出結果をＸ１に代入する。制御部２７０は、Ｘ１を中間データ格納テーブル２４０に格納する。
【００６３】
制御部２７０は、Ｙ１・ｙｐを算出し、算出結果をＹ１に代入する（ステップＳ１１３）。ステップＳ１１３において、制御部２７０は、Ｙ１とｙｐとを乗算部２６０に入力することで、Ｙ１・ｙｐを算出し、算出結果をＹ１に代入する。制御部２７０は、新たに算出したＹ１にて中間データ格納テーブル２４０に格納されたＹ１を更新する。
【００６４】
制御部２７０は、ｊを３で割った余りをｓに代入し（ステップＳ１１４）、Ｙ１２を算出し、算出結果をＹ２に代入する（ステップＳ１１５）。ステップＳ１１５において、制御部２７０は、Ｙ１を２つ乗算部２６０に入力することで、Ｙ１２を算出し、算出したＹ１２を中間データ格納テーブル２４０に格納する。制御部２７０は、ｓとＹ１２とを乗算部２６０に入力することで、Ｙ１２・ｓを算出し、算出結果をＹ２に代入する。制御部２７０は、Ｙ２を中間データ格納テーブル２４０に格納する。
【００６５】
制御部２７０は、Ａｓの値をＤに代入し（ステップＳ１１６）、ｊを２で割ったときの余りをｔに代入し（ステップＳ１１７）、Ｂｔの値をＺに代入する（ステップＳ１１８）。制御部２７０は、ステップＳ１１６、Ｓ１１８において、ＤおよびＺを中間データ格納テーブル２４０に格納する。
【００６６】
制御部２７０は、Ｒ１＋Ｘ１＋Ｄを算出し、算出結果をＵ１に代入する（ステップＳ１１９）。ステップＳ１１９において、制御部２７０は、中間データ格納テーブル２４０に格納されたＲ１、Ｘ１、Ｄを順不同で加算部２５０に入力することで、Ｒ１＋Ｘ１＋Ｄを算出し、算出結果をＵ１に代入する。制御部２７０は、Ｕ１を中間データ格納テーブル２４０に格納する。
【００６７】
制御部２７０は、Ｕ１２を算出し、算出結果をＵ２に代入する（ステップＳ１２０）。ステップＳ１２０において、制御部２７０は、中間データ格納テーブル２４０に格納されたＵ１を２つ乗算部２６０に入力することで、Ｕ１２を算出し、算出結果をＵ２に代入する。制御部２７０は、Ｕ２を中間データ格納テーブル２４０に格納する。
【００６８】
制御部２７０は、Ｚ・Ｙ１を算出し、算出結果をＵ３に代入する（ステップＳ１２１）。ステップＳ１２１において、制御部２７０は、中間データ格納テーブル２４０に格納されたＺとＹ１とを乗算部２６０に入力することで、Ｚ・Ｙ１を算出し、算出結果をＵ３に代入する。制御部２７０は、Ｕ３を中間データ格納テーブル２４０に格納する。
【００６９】
制御部２７０は、Ｃ１・Ｕ１を算出し、算出結果をＵ４に代入する（ステップＳ１２２）。ステップＳ１２２において、制御部２７０は、事前計算テーブル２３０のＣ１と中間データ格納テーブル２４０のＵ１とを乗算部２６０に入力することで、Ｃ１・Ｕ１を算出し、算出結果をＵ４に代入する。制御部２７０は、Ｕ４を中間データ格納テーブル２４０に格納する。
【００７０】
制御部２７０は、Ｕ３−Ｕ２−Ｕ４−Ｃ２を算出し、算出結果をＧに代入する（ステップＳ１２３）。ステップＳ１２３において、制御部２７０は、Ｕ３、−Ｕ２、−Ｕ４、事前計算テーブル２３０に格納された−Ｃ２を順不同で加算部２５０に入力することで、Ｕ３−Ｕ２−Ｕ４−Ｃ２を算出し、算出結果をＧに代入する。制御部２７０は、Ｇを中間データ格納テーブル２４０に格納する。
【００７１】
制御部２７０は、ｆ・ｆ２・Ｇを算出し、算出結果をｆに代入する（ステップＳ１２４）。ステップＳ１２４において、制御部２７０は、ｆを２つ乗算部２６０に入力することで、ｆ２を算出する。制御部２７０は、ｆ、ｆ２、Ｇを順不同で乗算部２６０に入力することで、ｆ・ｆ２・Ｇを算出し、算出結果をｆに代入する。制御部２７０は、新たに算出したｆにて、中間データ格納テーブル２４０に格納されたｆを更新する。
【００７２】
制御部２７０は、Ｙ２＋Ｘ１−ｂを算出し、算出結果をｘｐに代入する（ステップＳ１２５）。ステップＳ１２５において、制御部２７０は、中間データ格納テーブル２４０に格納されたＹ２、Ｘ１、−ｂを順不同で加算部２５０に入力することで、Ｙ２＋Ｘ１−ｂを算出し、算出結果をｘｐに代入する。制御部２７０は、ｘｐを中間データ格納テーブル２４０に格納する。
【００７３】
制御部２７０は、Ｙ１・Ｙ２を算出し、算出結果をｙｐに代入する（ステップＳ１２６）。ステップＳ１２６において、制御部２７０は、中間データ格納テーブル２４０のＹ１とＹ２とを乗算部２６０に入力することで、Ｙ１・Ｙ２を算出し、算出結果をｙｐに代入する。制御部２７０は、ｙｐを中間データ格納テーブル２４０に格納する。
【００７４】
制御部２７０は、ｊ＋１を算出し、算出結果をｊに代入し（ステップＳ１２７）、ステップＳ１０９に移行する。
【００７５】
ここで、図４に示したステップＳ１１１〜Ｓ１２７により計算される値と、図１１に示したＳ６０〜Ｓ６６により計算される値は同じである。実施例２では、事前計算テーブル２３０を利用すること、計算途中の中間値を再利用すること、計算途中の中間値が楕円曲線上の点であることを利用して、ηＴペアリングの計算式を変換している。
【００７６】
事前計算テーブル２３０を利用することを工夫１とし、計算途中の中間値を再利用することを工夫２とする。また、計算途中の中間値が楕円曲線上の点であることを利用することを工夫３とする。
【００７７】
図１１のステップＳ６０〜Ｓ６６を、図４のステップＳ１１１〜Ｓ１２７に変化させるに至った過程１〜４について説明する。まず、過程１を説明する。過程１では、図１１のステップＳ６４，Ｓ６５に工夫２，３を適用する。例えば、ｙｑ９を計算する過程（ｙｑ→ｙｑ２→ｙｑ３→ｙｑ６→ｙｑ９）で利用する中間値ｙｑ２、ｙｑ６を再利用し、更に、ｙｑ２、ｙｑ６が楕円曲線上にあることを利用して、ｘｑ３、ｘｑ９を計算する。
【００７８】
過程２を説明する。過程２では、図１１のステップＳ６１，Ｓ６４，Ｓ６５に着目する。具体的に、標数３の有限体では、ｇ＝σｙｐｙｑ−ｕ２−ρｕ−ρ２に対して、ｇ３＝（σｙｐ）３ｙｑ３−ｕ６−ρ３ｕ３−ρ６が成り立つことに着目する。また、ｕ＝ｘｐ＋ｘｑ＋ｄに対して、ｕ３＝ｘｐ３＋ｘｑ３＋ｄ３が成り立つことにも着目する。また、（ｕ３）２＝ｕ６にも着目する。
【００７９】
過程３を説明する。過程３では、過程２で着目した式に工夫１を適用する。具体的には、（σｙｐ）３、ρ３、ρ６、ｘｑ３、ｘｑ６等を事前計算テーブル２３０に保持することで、過程２で着目した式を高速に計算する。
【００８０】
過程４を説明する。過程４では、過程１〜３をふまえて、各処理を効率的に行う。まず、事前にステップＳ１１１〜Ｓ１１６で、ｙｑ２、ｙｑ３などを計算しておくことで、ステップＳ１１９のＵ１＝ｕ３、ステップＳ１２０のＵ２＝ｕ６を計算する。そして、ステップＳ１２３で、Ｕ１、Ｕ２、Ｚ、Ｙ１、Ｃ１、Ｃ２を利用して、ｇ３を計算する。ｇ３はＧに対応する。
【００８１】
また、ステップＳ１２４で、ｆ３・ｇ３を計算し、計算結果をｆに代入する。そして、点（Ｘ１、Ｙ１）＝（ｘｐ３、ｙｐ３）が楕円曲線上の点であることを利用して、ｘｐ９を計算する。具体的には、ｘｐ＝Ｙ２＋Ｘ１−ｂ＝Ｙ１２＋Ｘ１−ｂ＝ｘｐ９を計算する。また、ｙｐ９は、Ｙ１×Ｙ２を計算することでも求められる。
【００８２】
上述したように、過程１〜４の工程を経ることで、図１１に示したステップＳ６０〜Ｓ６６の計算式は、図４に示したステップＳ１１１〜Ｓ１２７の計算式に変換される。
【００８３】
次に、図１１に示した従来のηＴペアリングの計算量と、図４に示した実施例２のηＴペアリングの計算量とを比較する。ただし、図１１のステップＳ５０〜Ｓ５９の計算量と、図４のステップＳ１０１〜Ｓ１０６、Ｓ１０８〜Ｓ１１０の計算量は同じである。従ってここでは、図１１のステップＳ６０〜Ｓ６６の計算量と、図４のステップＳ１０７、ステップＳ１１１〜１２７の計算量とを比較する。
【００８４】
計算量を比較するために、乗算の計算量を「Ｍ」、２乗算の計算量を「Ｓ」とする。例えば、ｘ２とｙ２とを計算した場合には、２乗算が２回計算されたことになるので、計算量は「２Ｓ」となる。ｘ・ｙとｘ・ｘとを計算した場合には、乗算が２回計算されたことになるので、計算量は「２Ｍ」となる。また、３乗算の計算量を算出する場合には、乗算の計算量と２乗算の計算量とを加算する。
【００８５】
まず、従来のηＴペアリングのステップＳ６０〜６６における計算量を順に求める。ステップＳ６０は、乗算、２乗算が行われていないので、計算量は「０」となる。ステップＳ６１では、乗算が３回計算され、２乗算が２回計算されるので、計算量は「３Ｍ＋２Ｓ」となる。
【００８６】
ステップＳ６２では、乗算が２回計算され、２乗算が１回計算されるので、計算量は「２Ｍ＋Ｓ」となる。ステップＳ６３では、乗算、２乗算が行われていないので、計算量は「０」となる。ステップＳ６４では、乗算が１回計算され、２乗算が３回計算されるので、計算量は「１Ｍ＋３Ｓ」となる。なお、９乗算を計算する場合には、ｘの２乗算を計算して、ｘ２を算出し、ｘ２の２乗算を計算して、ｘ４を算出し、ｘ４の２乗算を計算してｘ８を算出し、ｘ８とｘとの乗算を計算することになる。
【００８７】
ステップＳ６５では、乗算が１回計算され、２乗算が３回計算されるので、計算量は「１Ｍ＋３Ｓ」となる。ステップＳ６６では、乗算、２乗算が行われていないので、計算量は「０」となる。従って、ステップＳ６０〜ステップＳ６６の計算量を合計すると、合計で「６Ｍ＋８Ｓ」となる。
【００８８】
続いて、実施例２のηＴペアリングのステップＳ１１１〜１２７の計算量を順に求める。ステップ１０７では、（σｙｐ）３、ρ３、ρ６、ｘｑ３、ｘｑ６の計算が行われる。ここでは、３乗算の計算量を「Ｍ＋Ｓ」とする。全体として、乗算が１回「σｙｐ」行われ、３乗算が３回「（σｙｐ）３、ρ３、ｘｑ３」行われ、２乗算が２回「ρ６（ρ６＝ρ３・２）、ｘｑ６（ｘｑ６＝ｘｑ３・２）」行われる。従って、ステップＳ１０７の計算量は「４Ｍ＋５Ｓ」となる。
【００８９】
ステップＳ１１１では、２乗算が１回行われるので、計算量は「Ｓ」となる。ステップＳ１１２では、乗算、２乗算が行われていないので、計算量は「０」となる。ステップＳ１１３では、乗算が１回行われるので、計算量は、「Ｍ」となる。ステップＳ１１４では、乗算、２乗算が行われていないので、計算量は「０」となる。
【００９０】
ステップＳ１１５では、２乗算が１回計算されるので、計算量は「Ｓ」となる。ステップＳ１１６では、乗算、２乗算が行われていないので、計算量は「０」となる。ステップＳ１１７では、乗算、２乗算が行われていないので、計算量は「０」となる。
【００９１】
ステップＳ１１８では、乗算、２乗算が行われていないので、計算量は「０」となる。ステップＳ１１９では、乗算、２乗算が行われていないので、計算量は「０」となる。ステップＳ１２０では、２乗算が１回計算されるので、計算量は「Ｓ」となる。
【００９２】
ステップＳ１２１では、乗算が１回計算されるので、計算量は「Ｍ」となる。ステップＳ１２２では、乗算が１回計算されるので、計算量は「Ｍ」となる。ステップＳ１２３では、乗算、２乗算が行われていないので、計算量は「０」となる。
【００９３】
ステップＳ１２４では、乗算が２回計算され、２乗算が１回計算されるので、計算量は「２Ｍ＋Ｓ」となる。ステップＳ１２５では、乗算、２乗算が行われていないので、計算量は「０」となる。ステップＳ１２６では、乗算が１回計算されるので、計算量は「Ｍ」となる。ステップＳ１２７では、乗算、２乗算が行われていないので、計算量は「０」となる。従って、ステップＳ１０７、Ｓ１１１〜１２７の計算量を合計すると、計算量は「１０Ｍ＋９Ｓ」となる。
【００９４】
ただし、図４においてステップＳ１０７の処理が行われる回数は１回である。ｍの値が十分大きく、ステップＳ１１１〜１２７のループ回数が大きければ、ステップＳ１０７の計算量を無視することができる。したがって、ステップＳ１０７の計算量「４Ｍ＋５Ｓ」を全体の計算量「１０Ｍ＋９Ｓ」から除いた残りの計算量「６Ｍ＋４Ｓ」を、ステップＳ１０７、Ｓ１１１〜１２７の計算量とみなすことができる。
【００９５】
したがって、実施例２の事前計算コストを無視した場合、Ｓ１１１〜１２７の計算量は「６Ｍ＋４Ｓ」となり、従来のステップＳ６０〜６６の計算量は「６Ｍ＋８Ｓ」となる。ゆえに、本実施例２の方が、従来例と比べると４回も２乗算を少なくすることができる。
【００９６】
ここで、図１１および図４のｍの値を「９７」、「１６７」、「１９３」に変化させた場合の従来例の計算量と本実施例２の計算量とを説明する。図５は、従来例の計算量と実施例２の計算量とを示す図である。なお、図５における「Ｍａｉｎ  Ｌｏｏｐ」は、図４のステップＳ１１１〜Ｓ１２７に対応する。
【００９７】
図５に示すように、ｍの値が「９７」の場合には、従来例の計算量は「２８８Ｍ＋３８４Ｓ」となり、実施例２の計算量は合計で「２９２Ｍ＋１９７Ｓ」となる。ここで、ＭとＳの計算量が等しいとすると、従来例の計算量は「６７２」となり、実施例２の計算量は合計で「４８９」となる。従って、従来例よりも実施例２のほうが、ηＴペアリング値を算出する場合に、２７．２％の高速化を図ることができる。
【００９８】
図５に示すように、ｍの値が「１６７」の場合には、従来例の計算量は「５０４Ｍ＋６７２Ｓ」となり、実施例２の計算量は合計で「５０８Ｍ＋３４１Ｓ」となる。ここで、ＭとＳの計算量が等しいとすると、従来例の計算量は「１１７６」となり、実施例２の計算量は合計で「８４９」となる。従って、従来例よりも実施例２のほうが、ηＴペアリング値を算出する場合に、２７．８％の高速化を図ることができる。
【００９９】
図５に示すように、ｍの値が「１９３」の場合には、従来例の計算量は「５８２Ｍ＋７７６Ｓ」となり、実施例２の計算量は合計で「５８６Ｍ＋３９３Ｓ」となる。ここで、ＭとＳの計算量が等しいとすると、従来例の計算量は「１３５８」となり、実施例２の計算量は合計で「９７９」となる。従って、従来例よりも実施例２のほうが、ηＴペアリング値を算出する場合に、２８．０％の高速化を図ることができる。
【０１００】
上述してきたように、本実施例２にかかるペアリング算出装置２００は、３乗算回路の代わりに、事前計算テーブル２３０、中間データ格納テーブル２４０、加算部２５０、乗算部２６０を用いてηＴペアリング値を算出するので、回路規模を低減することができる。具体的には、楕円曲線上の点はｙ２＝ｘ３−ｘ＋ｂが成り立つ。このため、ペアリング算出装置２００は、ｙ２＋ｘ−ｂをｘ３として取り扱うことで、３乗算回路を用いることなく、ペアリング値の算出を可能にする。
【０１０１】
また、本実施例２にかかるペアリング算出装置２００は、事前計算テーブル２３０を利用すること、計算途中の中間値を再利用すること、計算途中の中間値が楕円曲線上の点であることを利用してηＴペアリング値を算出する式を変形・効率化している。したがって、従来例と比較して、本実施例２にかかるペアリング算出装置２００は、計算量を削減し、処理を高速化することができる。
【実施例３】
【０１０２】
次に、本実施例３にかかるペアリング算出装置について説明する。本実施例３では、テートペアリング値を算出する場合について説明する。図６は、本実施例３にかかるペアリング算出装置の構成を示す図である。図６に示すように、このペアリング算出装置３００は、入力部３１０、出力部３２０、事前計算テーブル３３０、中間データ格納テーブル３４０、加算部３５０、乗算部３６０を有する。
【０１０３】
入力部３１０は、外部の入力装置を介して、楕円曲線のパラメータと演算対象となるデータとを取得し、取得した楕円曲線のパラメータと演算対象となるデータを制御部３７０に入力する処理部である。楕円曲線のパラメータは、実施例２の楕円曲線のパラメータと同様である。
【０１０４】
演算対象となるデータは、楕円曲線上の２点を示すＰ、Ｑである。実施例３では一例として、Ｐ＝（α、β）とし、Ｑ＝（ｘ、ｙ）とする。
【０１０５】
出力部３２０は、ペアリングの算出結果となるテートペアリング値ｅＴ（Ｐ，φ（Ｑ））を、制御部３７０から取得し、取得したテートペアリング値を外部の装置等に出力する処理部である。
【０１０６】
事前計算テーブル３３０は、ηＴペアリング値の計算に利用するパラメータを記憶する記憶部である。事前計算テーブル３３０が記憶するパラメータはＡを含む。パラメータＡは、ρ２の値を格納する。
【０１０７】
中間データ格納テーブル３４０は、テートペアリング計算における中間の計算結果を必要に応じて記憶する記憶部である。加算部３５０は、２つの数値データを制御部３７０から受付けて、数値データの和を制御部３７０に出力する回路である。乗算部３６０は、２つの数値データを制御部３７０から受付けて、数値データの積を制御部３７０に出力する回路である。
【０１０８】
制御部３７０は、事前計算テーブル３３０、中間データ格納テーブル３４０、加算部３５０、乗算部３６０を用いてテートペアリング値を算出する処理部である。制御部３７０は、テートペアリング値を算出する場合には、標数３の有限体上の楕円曲線を利用する。
【０１０９】
なお、制御部３７０は、３乗演算を実行する３乗回路を用いることがない。楕円曲線上の任意の点（α、β）に対しα３＝β２＋α−ｂの関係が成り立つため、制御部３７０は、β２、α、ｂの値をもとめることで、３乗回路を用いなくてもα３の値をもとめることができる。具体的に、制御部３７０は、βとβとを乗算部３６０に入力してβ２を算出させ、中間データ格納テーブル３４０にβ２を格納しておく。そして、制御部３７０は、αと−ｂと中間データ格納テーブル３４０に格納されたβ２を順不同で加算部３５０に入力することで、α３を算出する。
【０１１０】
テートペアリング値を算出するために必要となるその他の値は、制御部３７０が、事前計算テーブル３３０、中間データ格納テーブル３４０、加算部３５０、乗算部３６０を組合せて利用することで算出する。
【０１１１】
次に、テートペアリング値を算出する場合の制御部３７０の処理手順について説明する。図７および図８は、本実施例３にかかる制御部３７０の処理手順を示すフローチャートである。図７に示すように、制御部３７０は、楕円曲線のパラメータと楕円曲線上の２点Ｐ＝（α、β）、Ｑ＝（ｘ、ｙ）を取得し（ステップＳ２０１）、ｆに１を代入する（ステップＳ２０２）。
【０１１２】
制御部３７０は、ｘ３を算出し、算出結果をｘに代入する（ステップＳ２０３）。ステップＳ２０３において、制御部３７０は、ｘとｘとを乗算部３６０に入力することで、ｘ２を算出し、算出結果を中間データ格納テーブル３４０に格納する。制御部３７０は、ｘと中間データ格納テーブル３４０のｘ２とを乗算部３６０に入力することで、ｘ３を算出し、算出結果をｘに代入する。制御部３７０は、ｘを中間データ格納テーブル３４０に格納する。
【０１１３】
制御部３７０は、ｙ３を算出し、算出結果をｙに代入する（ステップＳ２０４）。ステップＳ２０４において、制御部３７０は、ｙとｙとを乗算部３６０に入力することで、ｙ２を算出し、算出結果を中間データ格納テーブル３４０に格納する。制御部３７０は、ｙと中間データ格納テーブル３４０のｙ２とを乗算部３６０に入力することで、ｙ３を算出し、算出結果をｙに代入する。制御部３７０は、ｙを中間データ格納テーブル３４０に格納する。
【０１１４】
制御部３７０は、（ｍ−１）・ｂを算出し、算出結果をｄに代入する（ステップＳ２０５）。ステップＳ２０５において、制御部３７０は、ｍと−１とを加算部３５０に入力することで、ｍ−１を算出し、算出結果を中間データ格納テーブル３４０に格納する。制御部３７０は、（ｍ−１）とｂとを乗算部３６０に入力することで、（ｍ−１）・ｂを算出し、算出結果をｄに代入する。制御部３７０は、ｄを中間データ格納テーブル３４０に格納する。
【０１１５】
制御部３７０は、ｘ３を算出し、算出結果をｘ’に代入する（ステップＳ２０６）。ステップＳ２０６は、中間データ格納テーブル３４０に格納されたｘを２つ乗算部３６０に入力することでｘ２を算出し、ｘ２とｘとを乗算部３６０に入力することでｘ３を算出する。制御部３７０は、ｘ３をｘ’に代入し、ｘ’を中間データ格納テーブル３４０に格納する。
【０１１６】
制御部３７０は、ｙ３を算出し、算出結果をｙ’に代入する（ステップＳ２０７）。ステップＳ２０７は、中間データ格納テーブル３４０に格納されたｙを２つ乗算部３６０に入力することでｙ２を算出し、ｙ２とｙとを乗算部３６０に入力することでｙ３を算出する。制御部３７０は、ｙ３をｙ’に代入し、ｙ’を中間データ格納テーブル３４０に格納する。
【０１１７】
制御部３７０は、Ａを算出し、算出結果を事前計算テーブル３３０に格納し（ステップＳ２０８）、ｉに１を代入する（ステップＳ２０９）。制御部３７０は、「ｉ＞（ｍ−１）／２」となるか否かを判定する（ステップＳ２１０）。制御部３７０は、「ｉ≦（ｍ−１）／２」となる場合には（ステップＳ２１０，Ｎｏ）、図８のステップＳ２２０に移行する。
【０１１８】
一方、「ｉ＞（ｍ−１）／２」となる場合には（ステップＳ２１０，Ｙｅｓ）、制御部３７０は、α３を算出し、算出結果をαに代入する（ステップＳ２１１）。制御部３７０は、αと中間データ格納テーブル３４０のα２とを乗算部３６０に入力することで、α３を算出し、算出結果をαに代入する。制御部３７０は、αを中間データ格納テーブル３４０に格納する。
【０１１９】
制御部３７０は、β３を算出し、算出結果をβに代入する（ステップＳ２１２）。ステップＳ２１２において、制御部３７０は、βとβとを乗算部３６０に入力することで、β２を算出し、算出結果を中間データ格納テーブル３４０に格納する。制御部３７０は、βと中間データ格納テーブル３４０のβ２とを乗算部３６０に入力することで、β３を算出し、算出結果をβに代入する。制御部３７０は、βを中間データ格納テーブル３４０に格納する。
【０１２０】
制御部３７０は、α＋ｘ＋ｂを算出し、算出結果をμに代入する（ステップＳ２１３）。ステップＳ２１３において、制御部３７０は、α、β、ｂを順不同で加算部３５０に入力することで、α＋ｘ＋ｂを算出し、算出結果をμに代入する。制御部３７０は、μを中間データ格納テーブル３４０に格納する。
【０１２１】
制御部３７０は、σ・β・ｙ−μ２を算出し、算出結果をλに代入する（ステップＳ２１４）。ステップ２１４において、制御部３７０は、σとβとを乗算部３６０に入力して、σ・βを算出し、算出したσ・βとｙとを乗算部３６０に入力することでσ・β・ｙを算出する。制御部３７０は、μを２つ乗算部３６０に入力することで、μ２を算出する。そして、制御部３７０は、σ・β・ｙとμ２とを加算部３５０に入力することで、σ・β・ｙ−μ２を算出し、算出結果をλに代入する。制御部３７０は、λを中間データ格納テーブル３４０に格納する。
【０１２２】
制御部３７０は、λ−μρ−ρ２を算出し、算出結果をｇに代入する（ステップＳ２１５）。ステップＳ２１５において、制御部３７０は、μとρとを乗算部３６０に入力して、μρを算出し、λ、−μρ、−ρ２を順不同で加算部３５０に入力することで、λ−μρ−ρ２を算出し、算出結果をｇに代入する。制御部３７０は、ｇを中間データ格納テーブル３４０に格納する。
【０１２３】
制御部３７０は、ｆ３・ｇを算出し、算出結果をｆに代入する（ステップＳ２１６）。ステップＳ２１６において、制御部３７０は、ｆを２つ乗算部３６０に入力して、ｆ２を算出し、ｆ２とｆとを乗算部３６０に入力して、ｆ３を算出する。そして、制御部３７０は、ｆ３とｇとを乗算部３６０に入力して、ｆ３・ｇを算出し、算出結果をｆに代入する。制御部３７０は、ｆを中間データ格納テーブル３４０に格納する。
【０１２４】
制御部３７０は、ｑ３を算出し、算出結果をｑ’に代入する（ステップＳ２１７）。ステップＳ２１７において、制御部３７０は、ｑとｑとを乗算部３６０に入力して、ｑ２を算出し、ｑ２とｑとを乗算部３６０に入力して、ｑ３を算出し、算出結果をｑ’に代入する。制御部３７０は、ｑ’を中間データ格納テーブル３４０に格納する。
【０１２５】
制御部３７０は、ｆｑ’−１を算出し、算出結果をｅＴ（Ｐ，φ（Ｑ））に代入する（ステップＳ２１８）。そして、制御部３７０は、ｅＴ（Ｐ，φ（Ｑ））を出力する（ステップＳ２１９）。ステップＳ２１９で出力されるｅＴ（Ｐ，φ（Ｑ））がテートペアリング値に対応する。
【０１２６】
次に、図８の説明に移行する。制御部３７０は、β２を算出し、算出結果をＹ１に代入する（ステップＳ２２０）。ステップＳ２２０において、制御部３７０は、βを２つ乗算部３６０に入力することで、β２を算出し、算出結果をＹ１に代入する。制御部３７０は、Ｙ１を中間データ格納テーブル３４０に格納する。
【０１２７】
制御部３７０は、−α＋Ｙ１＋ｂを算出し、算出結果をＸ１に代入する（ステップＳ２２１）。ステップＳ２２１において、制御部３７０は、−α、Ｙ１、ｂを順不同で加算部３５０に入力することで、−α＋Ｙ１＋ｂを算出し、算出結果をＸ１に代入する。制御部３７０は、Ｘ１を中間データ格納テーブル３４０に格納する。
【０１２８】
制御部３７０は、Ｙ１・βを算出し、算出結果をｔｍｐに代入する（ステップＳ２２２）。ステップＳ２２２において、制御部３７０は、Ｙ１とβとを乗算部３６０に入力することで、Ｙ１・βを算出し、算出結果をｔｍｐに代入する。制御部３７０は、ｔｍｐを中間データ格納テーブル３４０に格納する。
【０１２９】
制御部３７０は、ｔｍｐ２を算出し、算出結果をＹ２に代入する（ステップＳ２２３）。ステップＳ２２３において、制御部３７０は、ｔｍｐを２つ乗算部３６０に入力することでｔｍｐ２を算出し、算出結果をＹ２に代入する。制御部３７０は、Ｙ２を中間データ格納テーブル３４０に格納する。
【０１３０】
制御部３７０は、−Ｘ１＋Ｙ２＋ｂを算出し、算出結果をＸ２に代入する（ステップＳ２２４）。ステップＳ２２４において、制御部３７０は、−Ｘ１、Ｙ２、ｂを順不同で加算部３５０に入力することで、−Ｘ１＋Ｙ２＋ｂを算出し、算出結果をＸ２に代入する。制御部３７０は、Ｘ２を中間データ格納テーブル３４０に格納する。
【０１３１】
制御部３７０は、Ｙ２２・Ｙ２を算出し、算出結果をＹ３に代入する（ステップＳ２２５）。ステップＳ２２５において、制御部３７０は、Ｙ２を２つ乗算部３６０に入力することでＹ２２を算出し、Ｙ２２とＹ２とを乗算部３６０に入力することで、Ｙ２２・Ｙ２を算出する。制御部３７０は、Ｙ２２・Ｙ２の算出結果をＹ３に代入する。制御部３７０は、Ｙ３を中間データ格納テーブル３４０に格納する。
【０１３２】
制御部３７０は、ｔｍｐ・Ｙ２・Ｙ３を算出し、算出結果をβに代入する（ステップＳ２２６）。ステップＳ２２６において、制御部３７０は、ｔｍｐとＹ２とを乗算部３６０に入力することで、ｔｍｐ・Ｙ２を算出し、ｔｍｐ・Ｙ２とＹ３とを乗算部３６０に入力することで、ｔｍｐ・Ｙ２・Ｙ３を算出する。制御部３６０は、ｔｍｐ・Ｙ２・Ｙ３をβに代入する。制御部３７０は、βを中間データ格納テーブル３４０に格納する。
【０１３３】
制御部３７０は、−Ｘ２＋Ｙ３＋ｂを算出し、算出結果をαに代入する（ステップＳ２２７）。ステップＳ２２７において、制御部３７０は、−Ｘ２、Ｙ３、ｂを順不同で加算部３５０に入力することで、−Ｘ２＋Ｙ３＋ｂを算出し、算出結果をαに代入する。制御部３７０は、αを中間データ格納テーブル３４０に格納する。
【０１３４】
制御部３７０は、α＋ｘ’＋ｄを算出し、算出結果をμに代入する（ステップＳ２２８）。ステップＳ２２８において、制御部３７０は、α、ｘ’、ｄを順不同で加算部３５０に入力することで、α＋ｘ’＋ｄを算出し、算出結果をμに代入する。制御部３７０は、μを中間データ格納テーブル３４０に格納する。
【０１３５】
制御部３７０は、−α・β・ｙ’−μ２を算出し、算出結果をλに代入する（ステップＳ２２９）。ステップＳ２２９において、制御部３７０は、−αとβとを乗算部３６０に入力して−α・βを算出し、−α・βとｙ’とを乗算部３６０に入力して−α・β・ｙ’を算出する。制御部３７０は、μを２つ乗算部３６０に入力してμ２を算出する。そして、制御部３７０は、−α・β・ｙ’と−μ２とを加算部３５０に入力して、−α・β・ｙ’−μ２を算出し、算出結果をλに代入する。制御部３７０は、λを中間データ格納テーブル３４０に格納する。
【０１３６】
制御部３７０は、λ−μ・ρ−Ａを算出し、算出結果をｇ１に代入する（ステップＳ２３０）。ステップＳ２３０において、制御部３７０は、μとρとを乗算部３６０に入力することでμ・ρを算出し、λ、−μ・ρ、−Ａを順不同で加算部３５０に入力することで、λ−μ・ρ−Ａを算出する。制御部３７０は、λ−μ・ρ−Ａの算出結果をｇ１に代入する。制御部３７０は、ｇ１を中間データ格納テーブル３４０に格納する。
【０１３７】
制御部３７０は、β２を算出し、算出結果をｔｍｐに代入する（ステップＳ２３１）。ステップＳ２３１において、制御部３７０は、βを２つ乗算部３６０に入力することでβ２を算出し、算出結果をｔｍｐに代入する。制御部３７０は、ｔｍｐを中間データ格納テーブル３４０に格納する。
【０１３８】
制御部３７０は、ｔｍｐ＋α−ｂを算出し、算出結果をαに代入する（ステップＳ２３２）。ステップＳ２３２において、制御部３７０は、ｔｍｐ、α、−ｂを順不同で加算部３５０に入力することで、ｔｍｐ＋α−ｂを算出し、算出結果をαに代入する。制御部３７０は、αを中間データ格納テーブル３４０に格納する。
【０１３９】
制御部３７０は、ｔｍｐ・βを算出し、算出結果をβに代入する（ステップＳ２３３）。ステップＳ２３３において、制御部３７０は、ｔｍｐとβとを乗算部３６０に入力することで、ｔｍｐ・βを算出し、算出結果をβに代入する。制御部３７０は、βを中間データ格納テーブル３４０に格納する。
【０１４０】
制御部３７０は、α＋ｘ＋ｄを算出し、算出結果をμに代入する（ステップＳ２３４）。ステップＳ２３４において、制御部３７０は、α、ｘ、ｄを順不同で加算部３５０に入力することで、α＋ｘ＋ｄを算出し、算出結果をμに代入する。制御部３７０は、μを中間データ格納テーブル３４０に格納する。
【０１４１】
制御部３７０は、−α・β・ｙ−μ２を算出し、算出結果をλに入力する（ステップＳ２３５）。ステップＳ２３５において、制御部３７０は、αとβとを乗算部３６０に入力することで、α・βを算出し、α・βとｙとを乗算部３６０に入力することでα・β・ｙを算出する。制御部３７０は、−α・β・ｙと−μ２とを加算部３５０に入力することで、−α・β・ｙ−μ２を算出し、算出結果をλに入力する。制御部３７０は、λを中間データ格納テーブル３４０に格納する。
【０１４２】
制御部３７０は、λ−μ・ρ−Ａを算出し、算出結果をｇ２に代入する（ステップＳ２３６）。ステップＳ２３６において、制御部３７０は、μとρとを乗算部３６０に入力することでμ・ρを算出し、λ、−μ・ρ、−Ａを順不同で加算部３５０に入力することで、λ−μ・ρ−Ａを算出する。制御部３７０は、λ−μ・ρ−Ａの算出結果をｇ２に代入する。制御部３７０は、ｇ２を中間データ格納テーブル３４０に格納する。
【０１４３】
制御部３７０は、ｇ１・ｇ２を算出し、算出結果をｇに代入する（ステップＳ２３７）。ステップＳ２３７において、制御部３７０は、ｇ１とｇ２とを乗算部３６０に入力することで、ｇ１・ｇ２を算出し、算出結果をｇに代入する。制御部３７０は、ｇを中間データ格納テーブル３４０に格納する。
【０１４４】
制御部３７０は、ｆ９・ｇを算出し、算出結果をｆに代入する（ステップＳ２３８）。ステップＳ２３８において、制御部３７０は、ｆを２つ乗算部３６０に入力することでｆ２を算出し、ｆ２を２つ乗算部３６０に入力することでｆ４を算出し、ｆ４を２つ乗算部３６０に入力することでｆ８を算出する。制御部３７０は、ｆ８とｆとを乗算部３６０に入力することでｆ９を算出し、ｆ９とｇとを乗算部３６０に入力することで、ｆ９・ｇを算出し、算出結果をｆに代入する。制御部３７０は、ｆを中間データ格納テーブル３４０に格納する。
【０１４５】
制御部３７０は、ｄ−２ｂを算出し、算出結果をｄに代入する（ステップＳ２３９）。ステップＳ２３９において、制御部３７０は、ｄと−２ｂとを加算部３５０に入力することで、ｄ−２ｂを算出し、算出結果をｄに代入する。制御部３７０は、ｄを中間データ格納テーブル３４０に格納する。
【０１４６】
制御部３７０は、ｉ＋１を算出し、算出結果をｉに代入する（ステップＳ２４０）。ステップＳ２４０において、制御部３７０は、ｉと１とを加算部３５０に入力することでｉ＋１を算出し、算出結果をｉに代入する。制御部３７０は、ｉを中間データ格納テーブル３４０に格納する。ステップＳ２４０の後、制御部３７０は、図７のステップＳ２１０に移行する。
【０１４７】
ここで、図８に示したステップＳ２２０〜２４０により計算される値と、図１０に示したステップＳ２８〜Ｓ４１により計算される値は同じである。実施例３では、事前計算テーブル３３０を利用すること、計算途中の中間値を再利用すること、計算途中の中間値が楕円曲線上の点であることを利用して、ηＴペアリングの計算式を変換している。
【０１４８】
事前計算テーブル３３０を利用することを工夫１とし、計算途中の中間値を再利用することを工夫２とする。また、計算途中の中間値が楕円曲線上の点であることを利用することを工夫３とする。
【０１４９】
図１０のステップＳ２８〜Ｓ４１を、図８のステップＳ２２０〜２４０に変化させるに至った過程１、２について説明する。まず、過程１を説明する。過程１では、図１０のステップＳ２８，Ｓ２９、Ｓ３３、Ｓ３４に工夫２，３を適用する。例えば、β２７を計算する過程（β→β２→β３→β６→・・・）で利用する中間値を再利用し、更に、各中間値が楕円曲線上にあることを利用して、α３，α６，・・・を計算する。
【０１５０】
過程２を説明する。過程２では、図１０のステップＳ３２、Ｓ３７に工夫１を適用する。具体的には、ステップＳ３２，Ｓ３７で利用するρ２の値を事前計算テーブル３３０に保存する。そして、過程１と過程２とを組み合わせることで、図１０に示したステップＳ２８〜Ｓ４１の計算式は、図８に示したステップＳ２２０〜２４０の計算式に変換される。
【０１５１】
次に、図１０に示した従来のテートペアリングの計算量と、図７、８に示した実施例３のテートペアリングの計算量とを比較する。ただし、図１０のステップＳ１０〜Ｓ２７の計算量と、図７のステップＳ２０１〜Ｓ２０７、Ｓ２０９〜２１９の計算量とは同じである。したがってここでは、図１０のステップＳ２８〜Ｓ４１の計算量と、図７のステップＳ２０８および図８のステップＳ２２０〜Ｓ２４０の計算量とを比較する。計算量を比較するために、乗算の計算量を「Ｍ」、２乗算の計算量を「Ｓ」とする。
【０１５２】
まず、従来のテートペアリングのステップＳ２８〜Ｓ４１における計算量を順に求める。ただし、計算量を適切に比較するため、実施例３に合わせて、従来でもρ２は計算されているものとする。
【０１５３】
ステップＳ２８では、乗算が３回計算され、２乗算が４回計算されるので、計算量は「３Ｍ＋４Ｓ」となる。ステップＳ２９では、乗算が３回計算され、２乗算が４回計算されるので、計算量は「３Ｍ＋４Ｓ」となる。
【０１５４】
ステップＳ３０では、乗算、２乗算が行われていないので、計算量は「０」となる。ステップＳ３１では、乗算が２回計算され、２乗算が１回計算されるので、計算量は「２Ｍ＋Ｓ」となる。ステップＳ３２では、乗算が１回計算されるので、計算量は「Ｍ」となる。
【０１５５】
ステップＳ３３では、乗算が１回計算され、２乗算が１回計算されるので、計算量は「Ｍ＋Ｓ」となる。ステップＳ３４では、乗算が１回計算され、２乗算が１回計算されるので、計算量は「Ｍ＋Ｓ」となる。ステップＳ３５では、乗算、２乗算が行われていないので、計算量は「０」となる。ステップＳ３６では、乗算が２回計算され、２乗算が１回計算されるので、計算量は「２Ｍ＋Ｓ」となる。ステップＳ３７では、乗算が１回計算されるので、計算量は「Ｍ」となる。
【０１５６】
ステップＳ３８では、乗算が１回計算されるので、計算量は「Ｍ」となる。ステップＳ３９では、乗算が２回計算され、２乗算が３回計算されるので、計算量は「２Ｍ＋３Ｓ」となる。ステップＳ４０，４１は、乗算、２乗算が行われていないので、計算量は「０」となる。従って、ステップＳ２８〜ステップＳ４１の計算量を合計すると、合計で「１７Ｍ＋１３Ｓ」となる。
【０１５７】
続いて、実施例３のテートペアリングのステップＳ２２０〜Ｓ２４０の計算量を順に求める。ステップＳ２２０では、２乗算が１回計算されるので、計算量は「Ｓ」となる。ステップＳ２２１では、乗算、２乗算が行われていないので、計算量は「０」となる。ステップＳ２２２では、乗算が１回計算されるので、計算量は「Ｍ」となる。
【０１５８】
ステップＳ２２３では、２乗算が１回計算されるので、計算量は「Ｓ」となる。ステップＳ２２４では、乗算、２乗算が行われていないので、計算量は「０」となる。ステップＳ２２５では、乗算が１回計算され、２乗算が１回計算されるので、計算量は「Ｍ＋Ｓ」となる。
【０１５９】
ステップＳ２２６では、乗算が２回計算されるので、計算量は「２Ｓ」となる。ステップＳ２２７では、乗算、２乗算が行われていないので、計算量は「０」となる。ステップＳ２２８では、乗算、２乗算が行われていないので、計算量は「０」となる。ステップＳ２２９では、乗算が２回計算され、２乗算が１回計算されるので、計算量は「２Ｍ＋Ｓ」となる。
【０１６０】
ステップＳ２３０では、乗算が１回計算されるので、計算量は「Ｍ」となる。ステップＳ２３１では、２乗算が１回計算されるので、計算量は「Ｓ」となる。ステップＳ２３２では、乗算、２乗算が行われていないので、計算量は「０」となる。ステップＳ２３３では、乗算が１回計算されるので、計算量は「Ｍ」となる。
【０１６１】
ステップＳ２３４では、乗算、２乗算が行われていないので、計算量は「０」となる。ステップＳ２３５では、乗算が２回計算され、２乗算が１回計算されるので、計算量は「２Ｍ＋Ｓ」となる。ステップＳ２３６では、乗算が１回計算されるので、計算量は「Ｍ」となる。
【０１６２】
ステップＳ２３７では、乗算が１回計算されるので、計算量は「Ｍ」となる。ステップＳ２３８では、乗算が２回計算され、２乗算が３回計算されるので、計算量は「２Ｍ＋３Ｓ」となる。ステップＳ２３９、Ｓ２４０では、乗算、２乗算が行われていないので、計算量は「０」となる。したがって、ステップＳ２２０〜２４０の計算量を合計すると、計算量は「１４Ｍ＋９Ｓ」となる。
【０１６３】
したがって、実施例３の事前計算コストを無視しても、Ｓ２２０〜２４０の計算量は「１４Ｍ＋９Ｓ」となり、従来のステップＳ２８〜４１の計算量は「１７Ｍ＋１３Ｓ」となる。ゆえに、本実施例３の方が、従来例と比べると３回も２乗算を少なくすることができる。また、本実施例３の方が、従来例と比べると４回も乗算を少なくすることができる。
【０１６４】
ここで、図１０および図７，８のｍの値を「９７」、「１６７」、「１９３」に変化させた場合の従来例の計算量と本実施例３の計算量と説明する。図９は、従来例の計算量と実施例３の計算量とを示す図である。なお、図９における「Ｍａｉｎ  Ｌｏｏｐ」は、図８のステップＳ２２０〜Ｓ２４０に対応する。
【０１６５】
図９に示すように、ｍの値が「９７」の場合には、従来例の計算量は「８１６Ｍ＋６２４Ｓ」となり、実施例３の計算量は合計で「６７２Ｍ＋４３３Ｓ」となる。ここで、ＭとＳの計算量が等しいとすると、従来例の計算量は「１４４０」となり、実施例３の計算量は合計で「１１０５」となる。従って、従来例よりも実施例３のほうが、テートペアリング値を算出する場合に、２３．３％の高速化を図ることができる。
【０１６６】
図９に示すように、ｍの値が「１６７」の場合には、従来例の計算量は「１４１１Ｍ＋１０７９Ｓ」となり、実施例３の計算量は合計で「１１６２Ｍ＋７４８Ｓ」となる。ここで、ＭとＳの計算量が等しいとすると、従来例の計算量は「２４９０」となり、実施例３の計算量は合計で「１９１０」となる。従って、従来例よりも実施例３のほうが、テートペアリング値を算出する場合に、２３．３％の高速化を図ることができる。
【０１６７】
図９に示すように、ｍの値が「１９３」の場合には、従来例の計算量は「１６３２Ｍ＋１２４８Ｓ」となり、実施例３の計算量は合計で「１３４４Ｍ＋８６５Ｓ」となる。ここで、ＭとＳの計算量が等しいとすると、従来例の計算量は「２８８０」となり、実施例３の計算量は合計で「２２０９」となる。従って、従来例よりも実施例３のほうが、テートペアリング値を算出する場合に、２３．３％の高速化を図ることができる。
【０１６８】
上述してきたように、本実施例３にかかるペアリング算出装置３００は、３乗算回路の代わりに、事前計算テーブル３３０、中間データ格納テーブル３４０、加算部３５０、乗算部３６０を用いてテートペアリング値を算出するので、回路規模を低減することができる。具体的には、楕円曲線上の点はｙ２＝ｘ３−ｘ＋ｂが成り立つ。このため、ペアリング算出装置３００は、ｙ２＋ｘ−ｂをｘ３として取り扱うことで、３乗算回路を用いることなく、ペアリング値の算出を可能にする。
【０１６９】
また、本実施例３にかかるペアリング算出装置３００は、事前計算テーブル３３０を利用すること、計算途中の中間値を再利用すること、計算途中の中間値が楕円曲線上の点であることを利用してテートペアリング値を算出する式を変形・効率化している。したがって、従来例と比較して、本実施例３にかかるペアリング算出装置３００は、計算量を削減し、処理を高速化することができる。
【０１７０】
ところで、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。例えば、図１等に示した制御部１４０は、外部の回路に搭載された記憶部１１０、加算部１２０、乗算部１３０を利用してペアリング値を算出してもよい。
【０１７１】
本実施例１〜３に示したペアリング算出装置は、例えば、拡張カードなどに搭載され、公開鍵暗号方式による暗号化や復号化を実行するコンピュータに接続される。かかるコンピュータが、楕円曲線のパラメータと演算対象となるデータを拡張カード上のペアリング算出装置に入力することで、ペアリング値を算出させる。なお、コンピュータのマザーボード上に、ペアリング算出装置を直接搭載してもよい。
【符号の説明】
【０１７２】
１００    ペアリング算出装置
１１０    記憶部
１２０    加算部
１３０    乗算部
１４０    制御部
【図１】
0005471253.tif 000002
【図２】
0005471253.tif 000003
【図３】
0005471253.tif 000004
【図４】
0005471253.tif 000005
【図５】
0005471253.tif 000006
【図６】
0005471253.tif 000007
【図７】
0005471253.tif 000008
【図８】
0005471253.tif 000009
【図９】
0005471253.tif 000010
【図１０】
0005471253.tif 000011
【図１１】
0005471253.tif 000012