(57)【特許請求の範囲】
【請求項１】
Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を拡張した拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現したＴｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の素数位数の点である第１の点と、ａｆｆｉｎｅ座標を用いて表現した前記第１の点と同じ位数を持ち異なる前記Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の第２の点と、前記第１の点および前記第２の点と同じ位数を持ち、前記Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の群とは異なる群に属する第１の元を算出する楕円曲線ペアリング演算装置による楕円曲線ペアリング演算方法であって、
前記楕円曲線ペアリング演算装置は、基本演算部と、楕円曲線ペアリング演算部と、を有しており、
前記第１の点の座標を前記拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＰ＝（Ｘ１：Ｙ１：Ｔ１：Ｚ１）と表現したとき、Ｚ１の値が１である場合の処理として、
前記基本演算部が、
入出力部を介して、前記第１の点、前記第２の点、前記第１の点の位数であり、かつ前記第２の点の位数である素数を入力し、
前記入力した素数を２進数展開し、
前記第１の元の初期値を単位元とし、
前記第１の点と同じ群に含まれ、前記拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標で表される第３の点の初期値を前記第１の点とし、
前記楕円曲線ペアリング演算部が、
前記展開した２進数の係数ごとに、（ａ）および（ｂ）の処理を行うことで前記第１の元の値を更新し、前記（ａ）および（ｂ）の処理で更新された前記第１の元に対してべき乗計算を行った結果を前記第１の元と置き直すことで、前記第１の元を得ることを特徴とする楕円曲線ペアリング演算方法。
（ａ）前記楕円曲線ペアリング演算部が、前記第３の点を２倍した値で置換することによって、前記第３の点を更新し、
前記２倍算に付随して計算される多項式に対して前記第２の点を代入した値と、前記第１の元の２乗と、を乗算することで得られた値を前記第１の元とすることで前記第１の元を更新し、
（ｂ）前記楕円曲線ペアリング演算部が、前記第１の点と、前記第３の点の加算処理を行い、
前記加算処理で算出された値を前記第３の点とすることで前記第３の点を更新し、
前記加算に付随して計算される多項式に対して前記第２の点を代入した値と、前記第１の元とを乗算することで得られた値を前記第１の元とすることで前記第１の元を更新する。
【請求項２】
前記Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線におけるｘ２の項の係数が−１である
ことを特徴とする請求項１に記載の楕円曲線ペアリング演算方法。
【請求項３】
基本演算部と、楕円曲線２倍演算部と、楕円曲線加算演算部と、を有し、Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上のペアリング演算（ｆ＝ｅ（Ｐ，Ｑ））を行う楕円曲線ペアリング演算装置による楕円曲線ペアリング演算方法であって、
前記楕円曲線ペアリング演算装置が、
入力部を介して、
位数ｑの有限体Ｆｑ（ｑは２以外の素数のべきｑで、Ｅ（Ｆｑ）の位数である＃Ｅ（Ｆｑ）を割り切る位数であるとともに３以上の素数である値ｎがｑｋ−１を割り切る最小のｋが偶数となる数）を定義体として持ち、かつ前記値ｎの部分群を最大位数の部分群として持つ前記Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線Ｅ（Ｆｑ）：ａｘ２＋ｙ２＝１＋ｄｘ２ｙ２（ａｄ（ａ−ｄ）≠０かつＦｑ上で係数ａは２乗根を持ち係数ｄは持たない）の値ｎを位数とする部分群Ｇ１の情報、前記Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線Ｅ（Ｆｑ）上の点（ｘ１，ｙ１）において、ｘ１＝Ｚ１／Ｘ１、ｙ１＝Ｚ１／Ｙ１、ｘ１ｙ１＝Ｚ１／Ｔ１、Ｘ１Ｙ１Ｔ１Ｚ１≠０を満たすとともにＺ１＝１を満たすＸ１，Ｙ１，Ｔ１，Ｚ１∈Ｆｑで表現される拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現したＧ１の元Ｐ＝（Ｘ１：Ｙ１：Ｔ１：Ｚ１）の情報、前記値ｎがｑｋ−１を割り切る最小の偶数ｋを拡大次数として持ち、かつα２＝δ∈Ｆｑ２（ｑ２＝ｑｋ／２）を満たす基底｛１，α｝を用いてＦｑのｋ／２次拡大体Ｆｑ２（ｑ２＝ｑｋ／２）上の２次拡大体と見なすことのできるＦｑのｋ次拡大体Ｆｑ１（ｑ１＝ｑｋ）の値ｎを位数とする乗法に関する部分群Ｇ３の情報、Ｅ（Ｆｑ）をＦｑ１（ｑ１＝ｑｋ）上の楕円曲線と見なしたＥ（Ｆｑ１）（ｑ１＝ｑｋ）の値ｎを位数とする部分群Ｇ２の情報、およびＡｆｆｉｎｅ座標を用いてＱ＝（ｘ０α，ｙ０）（ｘ０，ｙ０∈Ｆｑ２）（ｑ２＝ｑｋ／２）と表現できるＧ２の元Ｑの情報を入力し、
前記基本演算部が、
（ａ１）前記値ｎを２進数展開して、ｎ＝ｎ０＋ｎ１×２＋・・・＋ｎｔ−１×２ｔ−１  （ｎｔ−１＝１）とし、
（ａ２）η←（１＋ｙ０）／（ｘ０δ）とおき、
（ａ３）ｆ←１、ｉ←ｔ−２、Ｒ←Ｐとおき、
前記楕円曲線２倍演算部が、
（ａ４）ｆ←ｆ２ｇＲ，Ｒ（Ｑ）、Ｒ←２Ｒを計算し、
前記基本演算部が、
（ａ５）ｎｉ＝１であるか否かを判定し、ｎｉ＝１であれば（ａ６）の処理に進み、ｎｉ＝１でなければ（ａ７）の処理に進み、
前記楕円曲線加算演算部が、
（ａ６）ｆ←ｆｇＲ，Ｐ（Ｑ）、Ｒ←Ｒ＋Ｐを計算し、
前記基本演算部が、
（ａ７）ｉ←ｉ−１を計算し、
（ａ８）ｉ≧０であるか否かを判定し、ｉ≧０であれば、前記（ａ４）の処理に戻り、ｉ≧０でなければ（ａ９）の処理に進み、
（ａ９）ｆ←ｆ（ｑ１−１）／ｎ（ｑ１＝ｑｋ）を計算し、当該ｆを演算結果とする
ことを特徴とする楕円曲線ペアリング演算方法。
【請求項４】
前記（ａ４）の処理において、入力時におけるＲの座標を前記拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて（Ｘ２：Ｙ２：Ｔ２：Ｚ２）とした場合、
前記楕円曲線２倍演算部が、
（ｂ１）Ａ←Ｘ２２、Ｂ←Ｙ２２、Ｃ←Ｔ２２、Ｄ←ａＢ、Ｅ←ａＹ２Ｚ２をＦｑ上でそれぞれ計算し、
（ｂ２）Ｆ←Ａ＋Ｄ、Ｇ←Ａ−Ｄ、Ｈ←（Ｘ２＋Ｙ２）２−Ａ−Ｂ、Ｉ←（Ｘ２＋Ｔ２）２−Ａ−Ｃ、Ｊ←（２Ｃ−Ｆ）をＦｑ上でそれぞれ計算し、
（ｂ３）ｃＺＺ←２Ｘ２（Ｙ２−Ｚ２）をＦｑ上で計算し、
（ｂ４）ｃＸＹ←２（Ｆ−Ｃ）−ＩをＦｑ上で計算し、
（ｂ５）ｃＸＺ←２（Ａ−Ｅ）をＦｑ上で計算し、
（ｂ６）ｇＲ，Ｒ（Ｑ）←ｃＺＺηα＋ｃＸＹｙ０＋ｃＸＺをＦｑのｋ／２次拡大体Ｆｑ２（ｑ２＝ｑｋ／２）上で計算し、
（ｂ７）ｆ←ｆ２ｇＲ，Ｒ（Ｑ）をＦｑのｋ次拡大体Ｆｑ１（ｑ１＝ｑｋ）上で計算し、
（ｂ８）Ｘ３←ＦＧをＦｑ上で計算し、
（ｂ９）Ｙ３←ＨＪをＦｑ上で計算し、
（ｂ１０）Ｔ３←ＦＨをＦｑ上で計算し、
（ｂ１１）Ｚ３←ＧＨをＦｑ上で計算し、
（ｂ１２）Ｒ←（Ｘ３：Ｙ３：Ｔ３：Ｚ３）とおき、ｆとともに、演算結果とする
ことを特徴とする請求項３に記載の楕円曲線ペアリング演算方法。
【請求項５】
前記Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線における係数ａの値が−１と異なる場合、かつ前記（ａ６）の処理において、入力時のＰの座標を（Ｘ１：Ｙ１：Ｔ１：Ｚ１＝１）、Ｒの座標を（Ｘ２：Ｙ２：Ｔ２：Ｚ２）であるとした場合の処理として、
前記楕円曲線加算演算部が、
（ｃ１）Ａ←Ｘ１Ｘ２、Ｂ←Ｙ１Ｙ２、Ｃ←Ｔ２Ｚ１、Ｄ←Ｔ１Ｚ２をＦｑ上でそれぞれ計算し、
（ｃ２）Ｅ←（Ｘ１＋Ｙ１）（Ｘ２−Ｙ２）＋Ｂ−Ａ、Ｆ←Ｃ＋Ｄ、Ｇ←Ｃ−Ｄ、Ｈ←Ａ＋ａＢ、Ｉ←Ｔ１Ｔ２をＦｑ上でそれぞれ計算し、
（ｃ３）ｃＺＺ←Ｙ２Ｚ１−Ｙ１Ｚ２をＦｑ上で計算し、
（ｃ４）ｃＸＹ←（Ｙ１−Ｔ１）（Ｙ２＋Ｔ２）−Ｂ＋Ｉ＋ＥをＦｑ上で計算し、
（ｃ５）ｃＸＺ←Ｄ−Ｃ＋（Ｘ１Ｚ２＋Ｘ２Ｚ１）をＦｑ上で計算し、
（ｃ６）ｇＲ，Ｐ（Ｑ）←ｃＺＺηα＋ｃＸＹｙ０＋ｃＸＺをＦｑのｋ／２次拡大体Ｆｑ２（ｑ２＝ｑｋ／２）上で計算し、
（ｃ７）ｆ←ｆｇＲ，Ｐ（Ｑ）をＦｑのｋ次拡大体Ｆｑ１（ｑ１＝ｑｋ）上で計算し、
（ｃ８）ｉ＝０であるか否かを判定し、ｉ＝０であれば（ｃ１４）の処理に進み、ｉ＝０でなければ（ｃ９）の処理に進み、
（ｃ９）Ｘ３←ＨＧをＦｑ上で計算し、
（ｃ１０）Ｙ３←ＥＦをＦｑ上で計算し、
（ｃ１１）Ｔ３←ＨＥをＦｑ上で計算し、
（ｃ１２）Ｚ３←ＦＧをＦｑ上で計算し、
（ｃ１３）演算結果をＱ←（Ｘ３：Ｙ３：Ｔ３：Ｚ３）およびｆとし、
（ｃ１４）演算結果をｆとする
ことを特徴とする請求項３に記載の楕円曲線ペアリング演算方法。
【請求項６】
前記Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線における係数ａの値が−１の場合、かつ前記（ａ６）の処理において、入力時のＰの座標を（Ｘ１：Ｙ１：Ｔ１：Ｚ１＝１）、Ｒの座標を（Ｘ２：Ｙ２：Ｔ２：Ｚ２）とした場合の処理として、
前記楕円曲線加算演算部が、
（ｄ１）Ａ←（Ｘ１−Ｙ１）（Ｘ２＋Ｙ２）、Ｂ←（Ｘ１＋Ｙ１）（Ｘ２−Ｙ２）、Ｃ←２Ｔ２Ｚ１、Ｄ←２Ｔ１Ｚ２をＦｑ上でそれぞれ計算し、
（ｄ２）Ｅ←Ａ＋Ｂ、Ｆ←Ｃ＋Ｄ，Ｇ←Ｃ−Ｄ，Ｈ←Ｂ−ＡをＦｑ上でそれぞれ計算し、
（ｄ３）ｃＺＺ←２（Ｙ２Ｚ１−Ｙ１Ｚ２）をＦｑ上で計算し、
（ｄ４）ｃＸＹ←２（Ｙ１Ｔ２−Ｙ２Ｔ１）＋ＨをＦｑ上で計算し、
（ｄ５）ｃＸＺ←Ｄ−Ｃ＋２（Ｘ１Ｚ２−Ｘ２Ｚ１）をＦｑ上で計算し、
（ｄ６）ｇＲ，Ｐ（Ｑ）←ｃＺＺηα＋ｃＸＹｙ０＋ｃＸＺをＦｑのｋ／２次拡大体Ｆｑ２（ｑ２＝ｑｋ／２）上で計算し、
（ｄ７）ｆ←ｆｇＲ，Ｐ（Ｑ）をＦｑのｋ次拡大体Ｆｑ１（ｑ１＝ｑｋ）上で計算し、
（ｄ８）ｉ＝０であるか否かを判定し、ｉ＝０であれば（ｄ１４）の処理に進み、ｉ＝０でなければ（ｄ９）の処理に進み、
（ｄ９）Ｘ３←ＥＧをＦｑ上で計算し、
（ｄ１０）Ｙ３←ＨＦをＦｑ上で計算し、
（ｄ１１）Ｔ３←ＥＨをＦｑ上で計算し、
（ｄ１２）Ｚ３←ＦＧをＦｑ上で計算し、
（ｄ１３）演算結果をＱ←（Ｘ３：Ｙ３：Ｔ３：Ｚ３）およびｆとし、
（ｄ１４）演算結果をｆとする
ことを特徴とする請求項３に記載の楕円曲線ペアリング演算方法。
【請求項７】
請求項１から請求項６のいずれか一項に記載の楕円曲線ペアリング演算方法をコンピュータに実行させるためのプログラム。
【請求項８】
ＩＤベース暗号を利用した暗号化を行う暗号化装置による暗号化方法であって、
前記暗号化装置が、
鍵発行装置から、公開パラメータおよび暗号化データの受信者の公開鍵を取得し、
外部装置から暗号化対象データを取得し、
前記公開パラメータと、前記公開鍵を基に、請求項１または請求項２に記載の楕円曲線ペアリング演算装置としての前記暗号化装置が、請求項１または請求項２に記載の楕円曲線ペアリング演算方法を用いることによって、前記暗号化対象データを暗号化する
ことを特徴とする暗号化方法。
【請求項９】
ＩＤベース暗号を利用した暗号化を行う暗号化装置による暗号化方法であって、
前記暗号化装置が、
鍵発行装置から、公開パラメータｐａｒａｍｓ、および暗号化データの受信者の公開鍵ＩＤを取得し、
外部装置から暗号化対象データＷを取得し、
前記公開パラメータｐａｒａｍｓは、すべてのバイナリ系列から部分群Ｇ２への写像であるハッシュ関数Ｈ１、Ｆｑ上で定義される楕円曲線Ｅ（Ｆｑ）の位数である＃Ｅ（Ｆｑ）を割り切る位数であるとともに３以上の素数である値ｎ、Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の任意の点Ｐ、前記Ｐをｓ（ｓは０＜ｓ＜ｎを満たすランダムな整数）倍した点Ｐｐｕｂ、ｅ：Ｇ１×Ｇ２→Ｇ３を満たすｅを含んでおり、
（ｆ１）ＱＩＤ←Ｈ１（ＩＤ）を計算し、
（ｆ２）０＜ｒ＜ｎを満たす整数ｒをランダムに生成し、
（ｆ３）Ｃ１←ｒＰを計算し、計算結果をＺ＝１の拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標（Ｘ：Ｙ：Ｔ：１）を用いて表現し、
（ｆ４）請求項３から請求項６のいずれか一項に記載の楕円曲線ペアリング演算装置としての前記暗号化装置が、請求項３から請求項６のいずれか一項に記載の楕円曲線ペアリング演算方法を行って、ｇ←ｅ（Ｐｐｕｂ，ＱＩＤ）を計算し、
（ｆ５）ｇｒ←ｇｒを計算し、
（ｆ６）ｈ←Ｈ２（ｇｒ）を計算し、
（ｆ７）Ｃ２←Ｗ  ＸＯＲ  ｈを計算し、
（ｆ８）Ｃ←（Ｃ１，Ｃ２）を暗号化データとする
ことを特徴とする暗号化方法。
ここで、Ｇ１は位数ｑの有限体Ｆｑ（ｑは２以外の素数のべきｑで、＃Ｅ（Ｆｑ）を割り切る位数であるとともに３以上の素数である値ｎがｑｋ−１を割り切る最小のｋが偶数となる数）を定義体として持ち、かつ前記値ｎを位数とする部分群を最大位数の部分群として持つ前記Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線Ｅ（Ｆｑ）：ａｘ２＋ｙ２＝１＋ｄｘ２ｙ２（ａｄ（ａ−ｄ）≠０かつＦｑ上で係数ａは２乗根を持ち係数ｄは持たない）の値ｎを位数とする部分群であり、Ｇ２はＥ（Ｆｑ）をＦｑ１（ｑ１＝ｑｋ）上の楕円曲線と見なしたＥ（Ｆｑ１）（ｑ１＝ｑｋ）の値ｎを位数とする部分群であり、Ｇ３はＦ＊ｑ１（ｑ１＝ｑｋ）の値ｎを位数とする乗法に関する部分群である。
【請求項１０】
請求項８または請求項９に記載の暗号化方法をコンピュータに実行させるためのプログラム。
【請求項１１】
請求項８に記載の暗号化方法によって生成された暗号化データを復号する復号化装置による復号化方法であって、
前記復号化装置が、
鍵発行装置から、公開パラメータおよび復号者の秘密鍵を取得し、
前記公開パラメータと、前記秘密鍵を基に、請求項１または請求項２に記載の楕円曲線ペアリング演算装置としての前記復号化装置が、請求項１または請求項２に記載の楕円曲線ペアリング演算方法を用いることによって、前記暗号化データを復号する
ことを特徴とする復号化方法。
【請求項１２】
請求項９に記載の暗号化方法によって生成された暗号化データを復号する復号化装置による復号化方法であって、
前記復号化装置が、
鍵発行装置から、公開パラメータｐａｒａｍｓ、復号者である利用者Ｂの秘密鍵ｄＩＤを取得し、
前記暗号化装置から暗号化データＣ＝（Ｃ１，Ｃ２）を取得し、
前記公開パラメータｐａｒａｍｓは、部分群Ｇ３からすべてのＮビットバイナリ系列への写像であるハッシュ関数Ｈ２、ｅ：Ｇ１×Ｇ２→Ｇ３を満たすｅを含んでおり、
前記楕円曲線ペアリング演算部は、
（ｇ１）請求項３から請求項６のいずれか一項に記載の楕円曲線ペアリング演算装置としての前記復号化装置が、請求項３から請求項６に記載の楕円曲線ペアリング演算方法を行って、ｇ←ｅ（Ｃ１，ｄＩＤ）を計算し、
ハッシュ関数演算部は、
（ｇ２）ｈ←Ｈ２（ｇ）を計算し、
前記楕円曲線ペアリング演算部は、
（ｇ３）Ｗ←Ｃ２  ＸＯＲ  ｈを計算し、Ｗを復号データとする
ことを特徴とする復号化方法。
ここで、Ｇ１は位数ｑの有限体Ｆｑ（ｑは２以外の素数のべきｑで、＃Ｅ（Ｆｑ）を割り切る位数であるとともに３以上の素数である値ｎがｑｋ−１を割り切る最小のｋが偶数となる数）を定義体として持ち、かつ前記値ｎを位数とする部分群を最大位数の部分群として持つＴｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線Ｅ（Ｆｑ）：ａｘ２＋ｙ２＝１＋ｄｘ２ｙ２（ａｄ（ａ−ｄ）≠０かつＦｑ上で係数ａは２乗根を持ち係数ｄは持たない）の値ｎを位数とする部分群であり、Ｇ２はＥ（Ｆｑ）をＦｑ１（ｑ１＝ｑｋ）上の楕円曲線と見なしたＥ（Ｆｑ１）（ｑ１＝ｑｋ）の値ｎの部分群であり、Ｇ３はＦ＊ｑ１（ｑ１＝ｑｋ）の値ｎを位数とする乗法に関する部分群である。
【請求項１３】
請求項１１または請求項１２に記載の復号化方法をコンピュータに実行させるためのプログラム。
【請求項１４】
Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を拡張した拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現したＴｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の素数位数の点である第１の点と、ａｆｆｉｎｅ座標を用いて表現した前記第１の点と同じ位数を持ち異なる前記Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の第２の点と、前記第１の点および前記第２の点と同じ位数を持ち、前記Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の群とは異なる群に属する第１の元を算出する楕円曲線ペアリング演算装置であって、
前記第１の点の座標を前記拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＰ＝（Ｘ１：Ｙ１：Ｔ１：Ｚ１）と表現したとき、Ｚ１の値が１である場合の処理として、
入出力部を介して、前記第１の点、前記第２の点、前記第１の点の位数であり、かつ前記第２の点の位数である素数を入力し、前記入力した素数を２進数展開し、前記第１の元の初期値を単位元とし、前記第１の点と同じ群に含まれ、前記拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標で表される第３の点の初期値を前記第１の点とする基本演算部と、
前記展開した２進数の係数ごとに、（ａ）および（ｂ）の処理を行うことで前記第１の元の値を更新し、前記（ａ）および（ｂ）の処理で更新された前記第１の元に対してべき乗計算を行った結果を前記第１の元と置き直すことで、前記第１の元を得る楕円曲線ペアリング演算部と、
を有することを特徴とする楕円曲線ペアリング演算装置。
（ａ）前記楕円曲線ペアリング部が、前記第３の点を２倍した値で置換することによって、前記第３の点を更新し、
前記２倍算に付随して計算される多項式に対して前記第２の点を代入した値と、前記第１の元の２乗と、を乗算することで得られた値を前記第１の元とすることで前記第１の元を更新し、
（ｂ）前記楕円曲線ペアリング部が、前記第１の点と、前記第３の点の加算処理を行い、
前記加算処理で算出された値を前記第３の点とすることで前記第３の点を更新し、
前記加算に付随して計算される多項式に対して前記第２の点を代入した値と、前記第１の元とを乗算することで得られた値を前記第１の元とすることで前記第１の元を更新する。
【請求項１５】
前記Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線におけるｘ２の項の係数が−１である
ことを特徴とする請求項１４に記載の楕円曲線ペアリング演算装置。
【請求項１６】
ＩＤベース暗号を利用した暗号化を行う暗号化装置であって、
鍵発行装置から、公開パラメータおよび暗号化データの受信者の公開鍵を取得し、外部装置から暗号化対象データを取得する入出力部と、
前記公開パラメータと、前記公開鍵を基に、請求項１または請求項２に記載の楕円曲線ペアリング演算装置としての前記復号化装置が、請求項１または請求項２に記載の楕円曲線ペアリング演算方法を用いることによって、前記暗号化対象データを暗号化する制御演算部と、
を有することを特徴とする暗号化装置。
【請求項１７】
請求項１６に記載の暗号化装置によって生成された暗号化データを復号する復号化装置であって、
鍵発行装置から、公開パラメータおよび復号者の秘密鍵を取得する入出力部と、
前記公開パラメータと、前記秘密鍵を基に、請求項１または請求項２に記載の楕円曲線ペアリング演算装置としての前記復号化装置が、請求項１または請求項２に記載の楕円曲線ペアリング演算方法を用いることによって、前記暗号化データを復号する制御演算部と、
を有することを特徴とする復号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、楕円曲線ペアリング演算方法、暗号化方法、復号化方法、プログラム、楕円曲線ペアリング演算装置、暗号化装置および復号化装置に関するものである。
【背景技術】
【０００２】
任意の文字列を公開鍵として用いることのできるＩＤ（Identification）ベース方式による暗号、デジタル署名がある。これらは、ペアリングと呼ばれる双線形写像の性質を応用して実現される。
【０００３】
ペアリングとは、位数がｎの３つの群をＧ１,Ｇ２,Ｇ３とした時、Ｇ１×Ｇ２からＧ３への写像ｅで以下の性質を満たすもののことである。ここで、「×」は直積を意味する。
１.任意のＰ∈Ｇ１および任意のＱ∈Ｇ２に対してｅはｅ（ａＰ，ｂＱ）=e（Ｐ,Ｑ）ａｂを満たす。
２.任意のＰ∈Ｇ１および任意のＱ∈Ｇ２に対してｅ（Ｐ，Ｑ）はＧ３の単位元と異なる。
【０００４】
具体的なペアリングとしてはＲｅｄｕｃｅｄ  Ｔａｔｅペアリングが知られている。
ｑを２で割ることのできない素数のべきとし、Ｅ（Ｆｑ）をＦｑ上で定義される楕円曲線とし、その単位元をＯとする。Ｅ（Ｆｑ）の位数を#Ｅ（Ｆｑ）、ｎを#Ｅ（Ｆｑ）を割り切る素数、Ｅ（Ｆｑ）［ｎ］をＥ（Ｆｑ）の位数ｎの部分群、ｋをｋ＞１を満たし、ｎがｑｋ−１を割り切る最小の整数とする。またｆｐをＰ∈Ｅ（Ｆｑ）［ｎ］に対して計算される多項式とする。
この時Ｒｅｄｕｃｅｄ  Ｔａｔｅペアリングは以下のように定義することができる。
【０００５】
【数１】
0005450240.tif 000002
【０００６】
ここで、ＦｑおよびＦｑ＊の定義は以下の通りである。
Ｆｑ：位数ｑの有限体
Ｆｑ＊：位数ｑの有限体Ｆｑから０を除いたもので乗法に関して群構造を持つもの。
【０００７】
次に、非特許文献４に基づき、Ｒｅｄｕｃｅｄ  Ｔａｔｅペアリングを計算するアルゴリズムを示す。以下、Ｒｅｄｕｃｅｄ  Ｔａｔｅペアリングをペアリングと呼ぶ。
【０００８】
入力：楕円曲線上の点Ｐ∈Ｅ（Ｆｑ）、Ｑ∈Ｅ（Ｆｑ１）／ｎＥ（Ｆｑ１）、点Ｐ、Ｑの位数である素数ｎ
出力：ｆ＝ｅ（Ｐ，Ｑ）∈Ｆ＊ｑ１／ｎＦ＊ｑ１
（ここで、ｑ１＝ｑｋ）
【０００９】
処理手順：
（１）計算機が、ｎを２進数展開して、ｎ＝ｎ０＋ｎ１×２＋・・・＋ｎｔ−１×２ｔ−１  （ｎｔ−１＝１）とする。
（２）計算機が、Ｒ←Ｐとおく。
（３）計算機が、ｆ←１とおく。
（４）計算機が、ｉ←ｔ−２とおく。
（５）ｉ≧０を満たす間、計算機は、以下の処理（５−１）〜（５−３）を繰り返す。
（５−１）計算機が、ｆ←ｆ２--ｇＲ，Ｒ（Ｑ），Ｒ←２Ｒを計算する（２倍算処理）。
（５−２）計算機が、ｎｉ＝１であればｆ←ｆｇＲ，Ｐ（Ｑ），Ｑ←Ｑ＋Ｐを計算する（加算処理）。
（５−３）計算機が、ｉ←ｉ−１を計算する。
【００１０】
（６）計算機が、ｆ←ｆ（ｑ１−１）／ｎ（ｑ１＝ｑｋ）を計算する。
【００１１】
（７）計算機が、計算結果としてｆを出力する
【００１２】
このようなペアリングの具体的な計算方法は、ペアリングが定義される楕円曲線に依存して決まる。また、上記アルゴリズムにおけるループ処理では楕円曲線上の加算および２倍算処理が行われる。
ここでは楕円曲線として加算・２倍算処理に適した楕円曲線として知られているＴｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線を用いる（例えば、非特許文献２参照）。
【００１３】
まず、非特許文献２に基づきＴｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線について説明する。
Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線とは標数が２以外の有限体をＦｑとした場合、ａｘ２＋ｙ２＝１＋ｄｘ２ｙ２  （ａ，ｄはＦｑ上の定数でａｄ（ａ−ｄ）≠０を満たす）で表される曲線であり、この曲線上の点は、曲線の方程式を満たすｘ，ｙ∈Ｆｑの組（ｘ，ｙ）で表すことができる。以下（ｘ、ｙ）の組で表される座標をＡｆｆｉｎｅ座標と呼ぶ。
【００１４】
Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の２点Ｐ，Ｑに対して加算Ｐ＋Ｑが、１点Ｐに対して２倍算２Ｐが定義でき具体的な計算方法が知られている。
Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の２点Ｐ＝（ｘ１，ｙ１）、Ｑ＝（ｘ２，ｙ２）に対して加算は以下の式（１）で計算することができる。
【００１５】
【数２】
0005450240.tif 000003
【００１６】
さらに、点Ｐ＝（ｘ１，ｙ１）に対して２倍算は上記加算式においてＰ＝Ｑとすることで計算できる。以下に示す式（２）は２倍算に特化した形で前記した加算式（式（１））を記載したものである。
【００１７】
【数３】
0005450240.tif 000004
【００１８】
また、点Ｐ＝（ｘ１，ｙ１）に対して−Ｐを（−ｘ１，ｙ１）で定義する。
Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の点全体からなる集合は、加算に対して（０，１）を単位元とする加法群の構造を持つ。またＴｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の点Ｐおよび、正整数Ｌに対してＰのＬ回加算ＬＰを求める演算をスカラ倍と呼ぶ。
また、Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の点Ｐに対してＰをｎ回加算するスカラ倍の演算結果ｎＰが単位元である（０，１）となる場合、正整数ｎを点Ｐの位数と呼ぶ。
【００１９】
非特許文献３において、Ｆｑ上で係数ａは２乗根を持ち係数ｄは持たない場合、係数ｄを用いない加算方法が開示されている。以下、非特許文献３に基づき上記加算方法を説明する。
【００２０】
楕円曲線上の２点をＰ＝（ｘ１，ｙ１）、Ｑ＝（ｘ２，ｙ２）、Ｐ≠Ｑ、ＰおよびＱは素数位数とした場合、加算Ｐ＋Ｑは以下の式（３）で計算することができる。
【００２１】
【数４】
0005450240.tif 000005
【００２２】
非特許文献２に開示されている加算および２倍算では有限体Ｆｑ上の乗算に比べて１０倍以上演算コストの大きい逆元計算が用いられる。この問題に対して逆元計算を用いないことでより高速な加算および２倍算の計算方法が非特許文献３に開示されている。
【００２３】
具体的には、点（ｘ，ｙ）をｘ＝Ｘ／Ｚ、ｙ＝Ｙ／Ｚ、ｘｙ＝Ｔ／Ｚ、Ｚ≠０を満たすＸ，Ｙ，Ｚ，Ｔ∈Ｆｑを用いて変換した拡張射影座標（Ｘ：Ｙ：Ｔ：Ｚ）を用いて逆元計算をより負荷の少ない数回の乗算に置き換えることにより高速化を行う。
なお、拡張射影座標（Ｘ：Ｙ：Ｔ：Ｚ）に含まれるＴ座標を省略した座標（Ｘ：Ｙ：Ｚ）を射影座標と呼ぶことにする。
【００２４】
次に、非特許文献３に基づき逆元計算の必要の無い加算アルゴリズムを示す。なお、以降のアルゴリズムの説明においてｍ，ｓ，Ｄは、それぞれ定義体Ｆｑ上の乗算、２乗算、定数倍算の演算コストを示す。
入力情報：（Ｘ１：Ｙ１：Ｔ１：Ｚ１），（Ｘ２：Ｙ２：Ｔ２：Ｚ２）
出力情報：（Ｘ３：Ｙ３：Ｔ３：Ｚ３）＝（Ｘ１：Ｙ１：Ｔ１：Ｚ１）＋（Ｘ２：Ｙ２：Ｔ２：Ｚ２）
処理手順：
（１）計算機が、Ａ←Ｘ１Ｘ２、Ｂ←Ｙ１Ｙ２、Ｃ←Ｚ１Ｔ２、Ｄ←Ｔ１Ｚ２、Ｅ←Ｄ＋ＣをＦｑ上でそれぞれ計算する（４ｍ）。
（２）計算機が、Ｆ←（Ｘ１−Ｙ１）（Ｘ２＋Ｙ２）＋Ｂ−Ａ、Ｇ←Ｂ＋ａＡ、Ｈ←Ｄ−ＣをＦｑ上でそれぞれ計算する（１ｍ，１Ｄ）。
（３）計算機が、Ｘ３←ＥＦをＦｑ上で計算する（１ｍ）。
（４）計算機が、Ｙ３←ＧＨをＦｑ上で計算する（１ｍ）。
（５）計算機が、Ｔ３←ＥＨをＦｑ上で計算する（１ｍ）。
（６）計算機が、Ｚ３←ＦＧをＦｑ上で計算する（１ｍ）。
（７）計算機が、（Ｘ３：Ｙ３：Ｔ３：Ｚ３）を演算結果として出力する。
この加算アルゴリズムの総演算コストは９ｍ＋１Ｄ、Ｚ１が１であれば１回の乗算を削減できるため総演算コストは８ｍ＋１Ｄとなる。
【００２５】
次に、非特許文献３に基づき逆元計算の必要の無い２倍算アルゴリズムを示す。
入力情報：（Ｘ１：Ｙ１：Ｔ１：Ｚ１）
出力情報：（Ｘ３：Ｙ３：Ｔ３：Ｚ３）＝２（Ｘ１：Ｙ１：Ｔ１：Ｚ１）
処理手順：
（１）計算機が、Ａ←Ｘ１２、Ｂ←Ｙ１２、Ｃ←２Ｚ１２、Ｄ←ａＡをＦｑ上でそれぞれ計算する（３ｓ，１Ｄ）。
（２）計算機が、Ｅ←（Ｘ１＋Ｙ１）２−Ａ−Ｂ、Ｇ←Ｄ＋Ｂ、Ｆ←Ｇ−Ｃ、Ｈ←Ｄ−ＢをＦｑ上でそれぞれ計算する（１ｓ）。
（３）計算機が、Ｘ３←ＥＦをＦｑ上で計算する（１ｍ）。
（４）計算機が、Ｙ３←ＧＨをＦｑ上で計算する（１ｍ）。
（５）計算機が、Ｔ３←ＥＨをＦｑ上で計算する（１ｍ）。
（６）計算機が、Ｚ３←ＦＧをＦｑ上で計算する（１ｍ）。
（７）計算機が、（Ｘ３：Ｙ３：Ｔ３：Ｚ３）を演算結果として出力する。
この２倍算アルゴリズムの総演算コストは４ｍ＋４ｓ＋１Ｄとなる。
【００２６】
また、点（ｘ，ｙ）をｘ＝Ｚ／Ｘ、ｙ＝Ｚ／Ｙ、ＸＹＺ≠０を満たすＸ，Ｙ，Ｚ∈Ｆｑを用いて変換したＩｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標（Ｘ：Ｙ：Ｚ）を用いて逆元計算をより負荷の少ない数回の乗算に置き換えることにより高速化を行う方法が非特許文献２に開示されている。
【００２７】
次に、非特許文献２に基づき逆元計算の必要の無い加算アルゴリズムを示す。
入力情報：（Ｘ１：Ｙ１：Ｚ１），（Ｘ２：Ｙ２：Ｚ２）
出力情報：（Ｘ３：Ｙ３：Ｚ３）＝（Ｘ１：Ｙ１：Ｚ１）＋（Ｘ２：Ｙ２：Ｚ２）
処理手順：
（１）計算機が、Ａ←Ｚ１Ｚ２、Ｂ←ｄＡ２、Ｃ←Ｘ１Ｘ２、Ｄ←Ｙ１Ｙ２、Ｅ←ＣＤをＦｑ上でそれぞれ計算する（４ｍ，１ｓ，１Ｄ）。
（２）計算機が、Ｈ←Ｃ−ａＤ、Ｉ←（Ｘ１＋Ｙ１）（Ｘ２＋Ｙ２）−Ｃ−ＤをＦｑ上でそれぞれ計算する（１ｍ，１Ｄ）。
（３）計算機が、Ｘ３←（Ｅ＋Ｂ）ＨをＦｑ上で計算する（１ｍ）。
（４）計算機が、Ｙ３←（Ｅ−Ｂ）ＩをＦｑ上で計算する（１ｍ）。
（５）計算機が、Ｚ３←ＡＨＩをＦｑ上で計算する（２ｍ）。
（６）計算機が、（Ｘ３：Ｙ３：Ｚ３）を演算結果として出力する。
この加算アルゴリズムの総演算コストは９ｍ＋１ｓ＋２Ｄ、Ｚ１が１であれば１回の乗算を削減できるため総演算コストは８ｍ＋１ｓ＋２Ｄとなる。
【００２８】
次に、非特許文献２に基づき逆元計算の必要の無い２倍算アルゴリズムを示す。
入力情報：（Ｘ１：Ｙ１：Ｚ１）
出力情報：（Ｘ３：Ｙ３：Ｚ３）＝２（Ｘ１：Ｙ１：Ｚ１）
処理手順：
（１）計算機が、Ａ←Ｘ１２、Ｂ←Ｙ１２、Ｕ←ａＢをＦｑ上でそれぞれ計算する（２ｓ，１Ｄ）。
（２）計算機が、Ｃ←Ａ＋Ｕ、Ｄ←Ａ−Ｕ、Ｅ←（Ｘ１＋Ｙ１）２−Ａ−ＢをＦｑ上でそれぞれ計算する（１ｓ）。
（３）計算機が、Ｘ３←ＣＤをＦｑ上で計算する（１ｍ）。
（４：計算機が、Ｙ３←Ｅ（Ｃ−２ｄＺ１２）をＦｑ上で計算する（１ｍ，１ｓ，１Ｄ）。
（５）計算機が、Ｚ３←ＤＥをＦｑ上で計算する（１ｍ）。
（６）計算機が、（Ｘ３：Ｙ３：Ｚ３）を演算結果として出力する。
この２倍算アルゴリズムの総演算コストは３ｍ＋４ｓ＋２Ｄとなる。
【００２９】
次に、非特許文献４に基づきＴｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線を用いた、ペアリングの計算方法を説明する。
【００３０】
２以外の素数のべきｑに対して、素数ｎがｑｋ−１を割り切り、かつ最小のｋが偶数であるとする。この時、楕円曲線の定義体をＦｑ、位数ｎの部分群を最大位数の部分群として持つＴｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線Ｅ（Ｆｑ）をａｘ２＋ｙ２＝１＋ｄｘ２ｙ２（ａｄ（ａ−ｄ）≠０かつＦｑ上で係数ａは２乗根を持ち係数ｄは持たない）、その位数ｎの部分群をＧ１とする。
【００３１】
Ｆｑのｋ次拡大体Ｆｑ１（ｑ１＝ｑｋ、ｋは偶数）はＦｑのｋ／２次拡大体Ｆｑ２（ｑ２＝ｑｋ／２）の２次拡大体と見なすことができ、α２＝δ∈Ｆｑ２（ｑ２＝ｑｋ／２）を満たす基底｛１，α｝を用いることで任意の元をｘ＋ｙα（ｘ，ｙ∈Ｆｑ２（ｑ２＝ｑｋ／２））で表現することができる。
さらに、Ｑを、Ｅ（Ｆｑ）をＦｑ１（ｑ１＝ｑｋ）上の楕円曲線と見なしたＥ（Ｆｑ１）（ｑ１＝ｑｋ）上の位数ｎの元で射影座標を用いてＱ＝（Ｘ０α：Ｙ０：Ｚ０）（Ｘ０，Ｙ０，Ｚ０∈Ｆｑ２：ｑ２＝ｑｋ／２）と表現できるものとする。この時、Ｑの属する位数ｎの部分群をＧ２とし、Ｆｑ１（ｑ１＝ｑｋ）の位数ｎの乗法に関する部分群をＧ３とする。
【００３２】
次に、ペアリングを計算するアルゴリズムを非特許文献４に基づき示す。
入力：点Ｐ＝（Ｘ１：Ｙ１：Ｔ１：Ｚ１）∈Ｇ１，Ｑ＝（Ｘ０α：Ｙ０：Ｚ０）∈Ｇ２（Ｘ０，Ｙ０，Ｚ０∈Ｆｑ２：ｑ２＝ｑｋ／２）
出力：ｆ＝ｅ（Ｐ，Ｑ）∈Ｇ３
【００３３】
処理手順：
（１）計算機が、点Ｐの位数である３以上の素数ｎを２進数展開して、ｎ＝ｎ０＋ｎ１×２＋・・・＋ｎｔ−１×２ｔ−１  （ｎｔ−１＝１）とする。
（２）計算機が、η←（Ｚ０＋Ｙ０）／（Ｘ０δ）とおく。
（３）計算機が、ｙ０←Ｙ０／Ｚ０とおく。
（４）計算機が、Ｒ←Ｐとおく。
（５）計算機が、ｆ←１とおく。
（６）計算機が、ｉ←ｔ−２とおく。
（７）ｉ≧０を満たす間、計算機は、以下の処理（７−１）〜（７−３）を繰返す。
（７−１）計算機が、ｆ←ｆ２ｇＲ，Ｒ（Ｑ），Ｒ←２Ｒを計算する（２倍算処理）。なお、（７−１）の計算方法は後記する。
（７−２）計算機が、ｎｉ＝１であればｆ←ｆｇＲ，Ｐ（Ｑ），Ｒ←Ｒ＋Ｐを計算する（加算処理）。なお、（７−２）の計算方法は後記する。
（７−３）計算機が、ｉ←ｉ−１を計算する。
（８）計算機が、ｆ←ｆ（ｑ１−１）／ｎ（ｑ１＝ｑｋ）を計算する。
（９）ｆを計算結果とする。
【００３４】
次に、（７−１）における２倍算処理について詳しく説明する。
入力情報：Ｒ＝（Ｘ１：Ｙ１：Ｔ１：Ｚ１）
出力情報：Ｒ＝（Ｘ３：Ｙ３：Ｔ３：Ｚ３）＝２（Ｘ１：Ｙ１：Ｔ１：Ｚ１）、ｆ
処理手順：（７−１）、（７−２）の処理における、ｍ，ｓ，Ｄは、それぞれ定義体Ｆｑ上の乗算、２乗算、定数倍算の演算コスト、Ｍ，Ｄは、それぞれＦｑのｋ次拡大体Ｆｑ１（ｑ１＝ｑｋ）上の乗算、２乗算の演算コストを示す。ただし、定義体Ｆｑ上の２倍算については、より演算コストの小さい加算もしくは１ビットシフトなどの演算を用いることでコストの大きい乗算を用いないで計算できるため定数倍としては扱わない。
（１）計算機が、Ａ←Ｘ１２、Ｂ←Ｙ１２、Ｃ←Ｚ１２、Ｄ←（Ｘ１＋Ｙ１）２、Ｅ←（Ｙ１＋Ｚ１）２をＦｑ上でそれぞれ計算する（５ｓ）。
（２）計算機が、Ｆ←Ｄ−（Ａ＋Ｂ）、Ｇ←Ｅ−（Ｂ＋Ｃ）、Ｈ←ａＡをＦｑ上でそれぞれ計算する（１Ｄ）。
（３）計算機が、Ｉ←Ｈ＋Ｂ、Ｊ←Ｃ−Ｉ、Ｋ←Ｊ＋ＣをＦｑ上でそれぞれ計算する。
（４）計算機が、ｃＺＺ←２Ｙ１（Ｔ１−Ｘ１）をＦｑ上で計算する（１ｍ）。
（５）計算機が、ｃＸＹ←２Ｊ＋ＧをＦｑ上で計算する。
（６）計算機が、ｃＸＺ←２（ａＸ１Ｔ１−Ｂ）をＦｑ上で計算する（１ｍ，１Ｄ）。
（７）計算機が、ｇＲ，Ｒ（Ｑ）←ｃＺＺηα＋ｃＸＹｙ０＋ｃＸＺをＦｑ２（ｑ２＝ｑｋ／２）上で計算する（ｋｍ）。
【００３５】
（８）計算機が、ｆ←ｆ２ｇＲ，Ｒ（Ｑ）を計算する（１Ｍ、１Ｓ）。
（９）計算機が、Ｘ３←ＦＫをＦｑ上で計算する（１ｍ）。
（１０）計算機が、Ｙ３←Ｉ（Ｂ−Ｈ）をＦｑ上で計算する（１ｍ）。
（１１）計算機が、Ｔ３←Ｆ（Ｂ−Ｈ）をＦｑ上で計算する（１ｍ）。
（１２）計算機が、Ｚ３←ＩＫをＦｑ上で計算する（１ｍ）。
（１３）計算機が、Ｒ＝（Ｘ３：Ｙ３：Ｔ３：Ｚ３）、ｆを演算結果とする。
この２倍算アルゴリズムの総演算コストは１Ｍ＋１Ｓ＋（ｋ＋６）ｍ＋５ｓ＋２Ｄとなる。
【００３６】
次に、（７−２）における加算ステップについて説明する。
入力情報：Ｒ＝（Ｘ１：Ｙ１：Ｔ１：Ｚ１），Ｐ＝（Ｘ２：Ｙ２：Ｔ２：Ｚ２）、ｆ
出力情報：Ｒ＝（Ｘ３：Ｙ３：Ｔ３：Ｚ３）＝（Ｘ１：Ｙ１：Ｔ１：Ｚ１）＋（Ｘ２：Ｙ２：Ｔ２：Ｚ２）、ｆ
【００３７】
処理手順：
（１）計算機が、Ａ←Ｘ１Ｘ２、Ｂ←Ｙ１Ｙ２、Ｃ←Ｚ１Ｔ２、Ｄ←Ｔ１Ｚ２、Ｅ←Ｄ＋ＣをＦｑ上でそれぞれ計算する（４ｍ）。
（２）計算機が、Ｆ←（Ｘ１−Ｙ１）（Ｘ２＋Ｙ２）＋Ｂ−Ａ、Ｇ←Ｂ＋ａＡ、Ｈ←Ｄ−Ｃ、Ｉ←Ｔ１Ｔ２をＦｑ上でそれぞれ計算する（２ｍ，１Ｄ）。
（３）計算機が、ｃＺＺ←（Ｔ１−Ｘ１）（Ｔ２＋Ｘ２）−Ｉ＋ＡをＦｑ上で計算する（１ｍ）。
（４）計算機が、ｃＸＹ←Ｘ１Ｚ２−Ｘ２Ｚ１＋ＦをＦｑ上で計算する（２ｍ）。
（５）計算機が、ｃＸＺ←（Ｙ１−Ｔ１）（Ｙ２＋Ｔ２）−Ｂ＋Ｉ−ＨをＦｑ上で計算する（１ｍ）。
【００３８】
（７）計算機が、ｇＲ，Ｐ（Ｑ）←ｃＺＺηα＋ｃＸＹｙ０＋ｃＸＺをＦｑ２（ｑ２＝ｑｋ／２）上で計算する（ｋｍ）。
【００３９】
（８）計算機が、ｆ←ｆｇＲ，Ｐ（Ｑ）を計算する（１Ｍ）。
（６）計算機が、Ｘ３←ＥＦをＦｑ上で計算する（１ｍ）。
（７）計算機が、Ｙ３←ＧＨをＦｑ上で計算する（１ｍ）。
（８）計算機が、Ｔ３←ＥＨをＦｑ上で計算する（１ｍ）。
（９）計算機が、Ｚ３←ＦＧをＦｑ上で計算する（１ｍ）。
（１０）計算機が、Ｒ←（Ｘ３：Ｙ３：Ｔ３：Ｚ３）、ｆを演算結果として出力する。
この加算アルゴリズムの総演算コストは１Ｍ＋（ｋ＋１４）ｍ＋１Ｄ、Ｚ１＝１の場合、乗算を２回削減できて１Ｍ＋（ｋ＋１２）ｍ＋１Ｄとなる。
【００４０】
次に、非特許文献１に開示されているＩＤベース公開鍵暗号方式について説明する。
ＩＤベース公開鍵暗号方式を実現するシステムは、公開鍵の認証を行う認証局の代わりに、鍵生成センタを備える。鍵生成センタは、システムで共通に用いる公開パラメータを定め、各利用者が公開鍵として選択する任意のＩＤ（例えば、電子メールアドレス）に対して、鍵生成センタが外部にもれないよう厳重に保管するマスタ鍵を用いて公開鍵毎に秘密鍵を生成し、利用者に配布する。そして、鍵生成センタは、利用者が選択するＩＤ（公開鍵）と生成した秘密鍵とを対応づけて管理する。公開鍵の選定方法については、システム内でルール化しておく。
【００４１】
ＩＤベース公開鍵暗号方式は以下の４種類の処理より構成される。（１）、（２）は鍵生成センタでの処理であり、（３）は送信側端末の処理、（４）は受信側端末の処理である。
（１）公開パラメータおよびマスタ鍵生成処理：鍵生成センタに設置されている鍵発行装置が、システムで共通に用いる群やペアリングを含む公開パラメータの生成およびマスタ鍵の生成を行う。公開パラメータは、鍵生成センタによって外部に公開される。なお、システム全体の安全を確保するため、マスタ鍵は、システムの利用者を含む外部に漏洩しないよう、鍵生成センタによって厳重に保管される。
（２）秘密鍵生成処理：鍵発行装置が、利用者のメールアドレスなど、利用者と対応付けることのできる文字列（ＩＤ：公開鍵）毎に、マスタ鍵を用いて秘密鍵を生成する。この文字列が公開鍵となる。
（３）暗号化：送信側端末が鍵発行装置から公開パラメータや、送付先の公開鍵を取得し、取得した公開パラメータおよび送付先の公開鍵を用いて暗号化対象データの暗号化を行い、暗号化されたデータ（暗号化データ）を受信側端末へ送信する。
（４）復号：受信側端末が、鍵発行装置から公開パラメータおよび受信者の秘密鍵を取得し、公開パラメータおよび受信者の秘密鍵を用いて、送信側端末から送信された暗号化データを復号する。
【００４２】
次に上記（１）から（４）の各処理における、入力、出力、および処理について説明する。
以下、｛０，１｝＊は全てのバイナリ系列を表し、｛０，１｝Ｎは全てのＮビットバイナリ系列を表し、ＸＯＲは排他的論理和を表す。
【００４３】
（１）公開パラメータおよびマスタ鍵生成処理
入力情報：セキュリティパラメータである正整数Ｌ
出力情報：公開パラメータｐａｒａｍｓ、マスタ鍵ｓ
処理手順：
（１−１）鍵発行装置が、Ｌビットの素数ｎを生成する。
（１−２）鍵発行装置が、位数ｎの群Ｇ１、Ｇ２、Ｇ３を選択する。
（１−３）鍵発行装置が、ペアリングｅ：Ｇ１×Ｇ２→Ｇ３を選択する。
（１−４）鍵発行装置が、Ｇ１の生成元Ｐを選択する。
（１−５）鍵発行装置が、０＜ｓ＜ｎを満たす整数ｓをランダムに選択しマスタ鍵とする。
（１−６）鍵発行装置が、楕円曲線スカラ倍演算を用いて、Ｐｐｕｂ←ｓＰを計算する。
（１−７）鍵発行装置が、ハッシュ関数Ｈ１：｛０，１｝＊→Ｇ２を選択する。
（１−８）鍵発行装置が、ある整数Ｎに対して、ハッシュ関数Ｈ２：Ｇ３→｛０，１｝Ｎを選択する。
（１−９）鍵発行装置が、公開パラメータをｐａｒａｍｓ＝＜ｎ，Ｇ１，Ｇ２，Ｇ３，ｅ，Ｎ，Ｐ，Ｐｐｕｂ，Ｈ１，Ｈ２＞とする。
【００４４】
（２）秘密鍵生成処理：
入力情報：公開パラメータｐａｒａｍｓ、マスタ鍵ｓ、公開鍵として用いる任意の文字列ＩＤ
出力情報：ＩＤに対応する秘密鍵ｄＩＤ
処理手順：
（２−１）鍵発行装置が、任意のバイナリ列からなる集合に含まれる、与えられたＩＤ（ＩＤ∈｛０，１｝＊）に対して、公開パラメータｐａｒａｍｓに含まれているハッシュ関数Ｈ１を用いて、ＱＩＤ←Ｈ１（ＩＤ）を計算する。
（２−２）鍵発行装置が、マスタ鍵ｓを用いてｄＩＤ←ｓＱＩＤを計算し、秘密鍵とする。
【００４５】
（３）暗号化：
入力：暗号化対象データＷ、公開パラメータｐａｒａｍｓ、公開鍵ＩＤ
出力：暗号化データＣ＝（Ｃ１，Ｃ２）
処理手順：
（３−１）送信側端末が、公開パラメータｐａｒａｍｓに含まれているハッシュ関数Ｈ１を用いて、ハッシュ値ＱＩＤ←Ｈ１（ＩＤ）を計算する。
（３−２）送信側端末が、０＜ｒ＜ｎを満たす整数ｒをランダムに選択する。
（３−３）送信側端末が、楕円曲線スカラ倍演算を用いて、Ｃ１←ｒＰを計算する。
（３−４）送信側端末が、公開パラメータｐａｒａｍｓに含まれているペアリングｅを用いて、ペアリング演算を行い、ｇ←ｅ（Ｐｐｕｂ，ＱＩＤ）を計算する。
（３−５）送信側端末が、公開パラメータｐａｒａｍｓに含まれているハッシュ関数Ｈ２を用いて、ハッシュ値ｈ←Ｈ２（ｇｒ）を計算する。
（３−６）送信側端末が、Ｃ２←Ｗ  ＸＯＲ  ｈを計算する。
（３−７）送信側端末が、Ｃ←（Ｃ１，Ｃ２）を暗号化データとする。
【００４６】
（４）復号：
入力情報：暗号化データＣ＝（Ｃ１，Ｃ２）、公開パラメータｐａｒａｍｓ、秘密鍵ｄＩＤ
出力情報：復号データＭ
処理手順：
（４−１）受信側端末が、公開パラメータｐａｒａｍｓに含まれているペアリングｅを用いて、ペアリング演算を行い、ｇ←ｅ（Ｃ１，ｄＩＤ）を計算する。
（４−２）受信側端末が、公開パラメータｐａｒａｍｓに含まれているハッシュ関数Ｈ２を用いて、ｈ←Ｈ２（ｇ）を計算する。
（４−３）受信側端末が、Ｗ←Ｃ２  ＸＯＲ  ｈを計算し復号データとする。
【先行技術文献】
【非特許文献】
【００４７】
【非特許文献１】D. Boneh and M. Franklin. Identity based encryption from the Weil pairing SIAM J. of Computing, Vol. 32, No. 3, pp. 586-615, 2003. Extended abstract in proc. of Crypto '2001, LNCS Vol. 2139, Springer-Verlag, pp. 213-229, 2001.
【非特許文献２】Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters,”Twisted Edwards curves.” In AFRICACRYPT 2008, volume 5023 of LNCS,p389-p405. Springer, 2008.
【非特許文献３】Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, Ed Dawson,”Twisted Edwards Curves Revisited.” In ASIACRYPT 2008, volume 5350 of LNCS, p326-p343 Springer, 2008.
【非特許文献４】Christophe Arene, Tanja Lange, Michael Naehrig and Christophe Ritzenthaler, “Faster Computation of the Tate Pairing” Cryptology ePrint Archive： Report 2009/155, http：//eprint.iacr.org/2009/155
【発明の概要】
【発明が解決しようとする課題】
【００４８】
前記したＩＤベース暗号では、楕円曲線上のペアリング演算処理が必須である。しかし、ペアリング演算は暗号化および復号化処理において負荷が重いため処理性能に大きな影響を及ぼす事が知られている。
具体的には、ペアリング演算の処理性能は楕円曲線の定義体上の乗算および、２乗算、定数倍算の回数に依存する事が知られている。
また、ペアリング演算の際、Ｉｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標の適用可能性および係数ａ＝−１に特化した計算方法については、非特許文献４において開示されていない。
【００４９】
このような背景に鑑みて本発明がなされたのであり、本発明は、効率的なペアリング演算を行うことを目的とする。
【課題を解決するための手段】
【００５０】
前記課題を解決するため、本発明は、Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を拡張した拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現したＴｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の素数位数の点である第１の点（Ｚ１＝１）と、ａｆｆｉｎｅ座標を用いて表現した第２の点とのペアリング演算を行うことを特徴とする。
その他の解決手段については、実施形態中で適宜説明する。
【発明の効果】
【００５１】
本発明によれば効率的な楕円曲線ペアリング演算を行うことができる。
【図面の簡単な説明】
【００５２】
【図１】本実施形態に係る楕円曲線ペアリング演算装置の構成例を示す図である。
【図２】本実施形態に係る楕円曲線ペアリング演算部の構成例を示す図である。
【図３】本実施形態にかかる楕円曲線ペアリング演算処理の全体処理を説明するためのフローチャートである。
【図４】ステップＳ１０４における２倍算処理の手順を示すフローチャートである。
【図５】ステップＳ１０６において係数ａが−１と異なる場合の加算処理の手順を示すフローチャートである。
【図６】ステップＳ１０６において係数ａが−１の場合の加算処理の手順を示すフローチャートである。
【図７】本実施形態に係るＩＤベース暗号システムの構成例を示す図である。
【図８】本実施形態に係る鍵発行装置の構成例を示す図である。
【図９】本実施形態に係る鍵生成処理の手順を示すフローチャートである。
【図１０】本実施形態に係る公開パラメータおよびマスタ鍵生成処理の手順を示すフローチャートである。
【図１１】本実施形態に係る秘密鍵生成処理の手順を示すフローチャートである。
【図１２】本実施形態に係る暗号化装置の構成例を示す図である。
【図１３】本実施形態に係る暗号化処理の手順を示すフローチャートである。
【図１４】本実施形態に係る復号化装置の構成例を示す図である。
【図１５】本実施形態に係る復号化処理の手順を示すフローチャートである。
【図１６】情報処理装置のハードウェア構成例を示す図である。
【発明を実施するための形態】
【００５３】
次に、本発明を実施するための形態（「実施形態」という）について、適宜図面を参照しながら詳細に説明する。なお、本実施形態では、拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いることで、楕円曲線スカラ倍演算における演算コストを低減することを目的とする。
【００５４】
《楕円曲線ペアリング演算》
［楕円曲線ペアリング演算装置］
図１は、本実施形態に係る楕円曲線ペアリング演算装置の構成例を示す図である。
楕円曲線ペアリング演算装置１は、制御演算部１１０と、記憶部１２０を有している。
制御演算部１１０は、入出力部１１１と、制御部１１２と、楕円曲線ペアリング演算部１１３とを有する。入出力部１１１は、入力情報としての演算対象データおよび出力情報としての演算結果の入出力を行う機能を有する。制御部１１２は、楕円曲線ペアリング演算装置１全体を制御する機能を有する。楕円曲線ペアリング演算部１１３は、実際に楕円曲線上のペアリング演算を計算する機能を有する。
【００５５】
記憶部１２０には、中間データ１２１、データ１２２などが格納されている。中間データ１２１は、必要に応じて処理中に生成されるデータである。データ１２２は、楕円曲線のパラメータなどのデータである。
【００５６】
図２は、本実施形態に係る楕円曲線ペアリング演算部の構成例を示す図である。
楕円曲線ペアリング演算部１１３は、入出力部１１４と、楕円曲線加算演算部１１５と、楕円曲線２倍算演算部１１６と、基本演算部１１７とを有する。
楕円曲線加算演算部１１５は、楕円曲線上の２点の加算演算などを行う機能を有する。楕円曲線２倍算演算部１１６は、楕円曲線上の点の２倍算演算などを行う機能を有する。基本演算部１１７は、楕円曲線加算演算部１１５および楕円曲線２倍算演算部１１６から必要に応じて呼び出され楕円曲線の定義体上の演算や剰余計算（ｍｏｄ）を用いた四則演算などを行う機能を有する。
【００５７】
なお、楕円曲線ペアリング演算装置１は、図１６に示すような、バス６７で接続されたＣＰＵ（Central Processing Unit）６１と、ＲＡＭ（Random Access Memory）などのメモリ６２と、ＨＤＤ（Hard Disk Drive）やその他の外部記憶装置６５と、キーボードなどの入力装置６３と、ディスプレイなどの出力装置６４と、外部記憶装置６５や、入力装置６３や、出力装置６４と、バス６７とを中継するインタフェース６６とを備えた、一般的な構成を有する情報処理装置６上に構築することができる。
楕円曲線ペアリング演算装置１の制御演算部１１０および各部１１１〜１１７は、ＣＰＵ６１が、メモリ６２にロードされたプログラム（コードモジュールともいう）を実行することで、情報処理装置６上に具現化される。また、メモリ６２や、外部記憶装置６５が図１の記憶部１２０として使用される。
【００５８】
また、前記したプログラムは、予め外部記憶装置６５に記憶され、必要に応じてメモリ６２上にロードされ、ＣＰＵ６１により実行される。なお、このプログラムは、可搬性の記憶媒体、例えばＣＤ−ＲＯＭ（Compact Disk-Read Only Memory）などに格納され、必要に応じて、これら可搬性の記憶媒体からメモリ６２にロードされてもよい。また、プログラムは、一旦、ＣＤ−ＲＯＭなどの可搬性の記憶媒体からＨＤＤなどの外部記憶装置６５にインストールされた後、必要に応じて、この外部記憶装置６５からメモリ６２にロードされてもよい。さらに、プログラムは、図示していないネットワーク接続装置を介して、ネットワーク上の情報処理装置６が伝送信号により、一旦、外部記憶装置６５にダウンロードされてからメモリ６２にロードされてもよいし、あるいは、直接、ネットワーク経由でメモリ６２にロードされてもよい。
【００５９】
［楕円曲線ペアリング演算処理］
次に、図２を参照しつつ、図３〜図６に沿って楕円曲線ペアリング演算処理の手順を説明する。
２以外の素数のべきｑに対して、素数ｎがｑｋ−１を割り切りかつ最小のｋが偶数であるとする。この時、楕円曲線の定義体をＦｑ、位数ｎの部分群を最大位数の部分群として持つＴｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線Ｅ（Ｆｑ）をａｘ２＋ｙ２＝１＋ｄｘ２ｙ２（ａｄ（ａ−ｄ）≠０かつＦｑ上で係数ａは２乗根を持ち係数ｄは持たない）、その位数（素数位数）ｎの部分群をＧ１とする。
【００６０】
Ｆｑのｋ次拡大体Ｆｑ１（ｑ１＝ｑｋ：ｋは偶数）はＦｑのｋ／２次拡大体Ｆｑ２（ｑ２＝ｑｋ／２）上の２次拡大体と見なすことができ、α２＝δ∈Ｆｑ２（ｑ２＝ｑｋ／２）を満たす基底｛１，α｝を用いることで、任意の元はｘ＋ｙα（ｘ，ｙ∈Ｆｑ２：ｑ２＝ｑｋ／２）で表現することができる。
次にＱを、（Ｆｑ）をＦｑ１（ｑ１＝ｑｋ）上の楕円曲線の点と見なし、Ｅ（Ｆｑ１）（ｑ１＝ｑｋ）上の位数ｎの元でＡｆｆｉｎｅ座標を用いてＱ＝（ｘ０α，ｙ０）（ｘ０、ｙ０∈Ｆｑ２：ｑ２＝ｑｋ／２）と表現できるものとする。この時、Ｑの属する位数ｎの部分群をＧ２とし、Ｆｑ１（ｑ１＝ｑｋ）の乗法に関する位数ｎの部分群をＧ３とする。
【００６１】
以上の前提で、本実施形態に係る楕円曲線ペアリング演算の全体概要を説明すると、入出力部１１１により入力を受け付けた３つの群Ｇ１、Ｇ２、Ｇ３、拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現したＧ１の点（第１の点）Ｐ＝（Ｘ１：Ｙ１：Ｔ１：Ｚ１）∈Ｇ３、Ａｆｆｉｎｅ座標を用いて表現したＧ２の点（第２の点）Ｑ＝（ｘ０α，ｙ０）（ｘ０，ｙ０∈Ｆｑ２：ｑ２＝ｑｋ／２）、点ＰおよびＱの位数ｎ（ｎ≧３）の各入力情報は、記憶部１２０に保持される。
【００６２】
ここで、拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標とは、楕円曲線上の点（ｘ，ｙ）をｘ＝Ｚ／Ｘ、ｙ＝Ｚ／Ｙ、ＸＹＺ≠０を満たすＸ，Ｙ，Ｚを用いて変換したＩｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標（Ｘ：Ｙ：Ｚ）に対して、ｘｙ＝Ｔ／Ｚを満たす座標Ｔを加えて（Ｘ：Ｙ：Ｔ：Ｚ）とした座標である。
そして、制御演算部１１０が、記憶部１２０で保持されている各入力情報を用いて、図３〜図６に示すペアリング演算処理を行い、演算結果（第１の元）ｆ＝ｅ（Ｐ，Ｑ）∈Ｇ３を求め、出力する。
【００６３】
（全体処理）
図３は、本実施形態に係る楕円曲線ペアリング演算処理の全体処理を説明するためのフローチャートである。
ステップＳ１０１において、基本演算部１１７が、Ｐの位数である素数ｎを２進数展開して、ｎ＝ｎ０＋ｎ１×２＋・・・＋ｎｔ−１×２ｔ−１  （ｎｔ−１＝１）とする。
ステップＳ１０２において、基本演算部１１７が、η←（１＋ｙ０）／（ｘ０δ）とおく。
ステップＳ１０３において、基本演算部１１７が、ｆ←１（単位元）、ｉ←ｔ−２、Ｒ（第３の点）←Ｐとおく。
ステップＳ１０４において、楕円曲線２倍算演算部１１６が、ｆ←ｆ２ｇＲ，Ｒ（Ｑ）、Ｒ←２Ｒを、を計算する（２倍算処理）。ステップＳ１０４の計算方法は図４を参照して後記する。ｇＲ，Ｒ（Ｑ）については、図４のステップＳ２０６において後記する。
【００６４】
ステップＳ１０５において、基本演算部１１７が、ｎｉ＝１であるか否かを判定し、ｎｉ＝１であれば（Ｓ１０５→Ｙｅｓ）、ステップＳ１０６の処理に進み、ｎｉ＝１でなければ（Ｓ１０５→Ｎｏ）、ステップＳ１０７の処理に進む。
ステップＳ１０６において、楕円曲線加算演算部１１５が、ｆ←ｆｇＲ，Ｐ（Ｑ）、Ｒ←Ｒ＋Ｐを計算する（加算処理）。ステップＳ１０６の計算方法は、係数ａが−１以外の場合は図５を参照して後記し、係数ａが−１の場合は図６を参照して後記する。ｇＲ，Ｐ（Ｑ）については、図５のステップＳ３０６、図６のステップＳ４０６で後記する。
ステップＳ１０７において、基本演算部１１７が、ｉ←ｉ−１を計算する。
ステップＳ１０８において、基本演算部１１７が、ｉ≧０であるか否かを判定し、ｉ≧０であれば（Ｓ１０８→Ｙｅｓ）、ステップＳ１０４の処理に戻り、ｉ≧０でなければ（Ｓ１０８→Ｎｏ）、ステップＳ１０９の処理に進む。
ステップＳ１０９において、基本演算部１１７が、ｆのべき乗ｆ←ｆ（ｑ１−１）／ｎ（ｑ１＝ｑｋ）を計算しｆを演算結果とする。
【００６５】
（２倍算処理）
次に、図２を参照しつつ、図４に沿って図３のステップＳ１０４における２倍算処理について説明する。なお、これ以降、各処理の最後に記述してあるｍ，ｓ，Ｄは、それぞれ定義体Ｆｑ上の乗算、２乗算、定数倍算の演算コスト、Ｍ，Ｓは、それぞれＦｑのｋ次拡大体Ｆｑ１（ｑ１＝ｑｋ）上の乗算、２乗算の演算コストを示す。ただし、定義体Ｆｑ上の２倍算については、より演算コストの小さい加算もしくは１ビットシフトなどの演算を用いることでコストの大きい乗算を用いないで計算できるため定数倍としては扱わない。
【００６６】
図４は、図３のステップＳ１０４における２倍算処理の手順を示すフローチャートである。
なお、図４において、入力時におけるＲの座標は（Ｘ２：Ｙ２：Ｔ２：Ｚ２）であるとする。
ステップＳ２０１において、楕円曲線２倍算演算部１１６が、Ａ←Ｘ２２、Ｂ←Ｙ２２、Ｃ←Ｔ２２、Ｄ←ａＢ、Ｅ←ａＹ２Ｚ２をＦｑ上でそれぞれ計算する（１ｍ，３ｓ，２Ｄ）。ここでａ＝−１である場合、Ｄ←ａＢおよびＥ←ａＹ２Ｚ２はＦｑ上でＢの符号を反転することにより定数倍算を用いないで計算できるため、演算コストを２Ｄ削減することができる。
【００６７】
ステップＳ２０２において、楕円曲線２倍算演算部１１６が、Ｆ←Ａ＋Ｄ、Ｇ←Ａ−Ｄ、Ｈ←（Ｘ２＋Ｙ２）２−Ａ−Ｂ、Ｉ←（Ｘ２＋Ｔ２）２−Ａ−Ｃ、Ｊ←（２Ｃ−Ｆ）をＦｑ上でそれぞれ計算する（２ｓ）。
ステップＳ２０３において、楕円曲線２倍算演算部１１６が、ｃＺＺ←２Ｘ２（Ｙ２−Ｚ２）をＦｑ上で計算する（１ｍ）。
ステップＳ２０４において、楕円曲線２倍算演算部１１６が、ｃＸＹ←２（Ｆ−Ｃ）−ＩをＦｑ上で計算する。
ステップＳ２０５において、楕円曲線２倍算演算部１１６が、ｃＸＺ←２（Ａ−Ｅ）をＦｑ上で計算する。
【００６８】
ステップＳ２０６において、楕円曲線２倍算演算部１１６が、ｇＲ，Ｒ（Ｑ）←ｃＺＺηα＋ｃＸＹｙ０＋ｃＸＺをＦｑのｋ／２次拡大体Ｆｑ２（ｑ２＝ｑｋ／２）上で計算する（ｋｍ）。
【００６９】
ステップＳ２０７において、楕円曲線２倍算演算部１１６が、ｆ←ｆ２ｇＲ，Ｒ（Ｑ）をＦｑのｋ次拡大体Ｆｑ１（ｑ１＝ｑｋ）上で計算する（１Ｍ，１Ｓ）。
ステップＳ２０８において、楕円曲線２倍算演算部１１６が、Ｘ３←ＦＧをＦｑ上で計算する（１ｍ）。
ステップＳ２０９において、楕円曲線２倍算演算部１１６が、Ｙ３←ＨＪをＦｑ上で計算する（１ｍ）。
ステップＳ２１０において、楕円曲線２倍算演算部１１６が、Ｔ３←ＦＪをＦｑ上で計算する（１ｍ）。
ステップＳ２１１において、楕円曲線２倍算演算部１１６が、Ｚ３←ＧＨをＦｑ上で計算する（１ｍ）。
ステップＳ２１２において、楕円曲線２倍算演算部１１６が、２倍算の演算結果を拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＲ←（Ｘ３：Ｙ３：Ｔ３：Ｚ３）とおき、ｆとともに、演算結果として出力する。
この２倍算の総演算コストは、１Ｍ＋１Ｓ＋（ｋ＋６）ｍ＋５ｓ＋２Ｄとなる。
またａ＝−１である場合、１Ｍ＋１Ｓ＋（ｋ＋６）ｍ＋５ｓとなる。
【００７０】
ここで、図４の処理について詳細に説明する。
まず、非特許文献２に基づくＩｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標（Ｘ：Ｙ：Ｚ）を用いた（Ｘ３：Ｙ３：Ｚ３）＝２（Ｘ２：Ｙ２：Ｚ２）を計算する２倍算は以下の式（４）〜（６）で計算できる。
【００７１】
Ｘ３＝（Ｘ２２＋ａＹ２２）（Ｘ２２−ａＹ２２）・・・（４）
Ｙ３＝２Ｘ２Ｙ２（Ｘ２２＋ａＹ２２−２ｄＺ２２）・・・（５）
Ｚ３＝２Ｘ２Ｙ２（Ｘ２２−ａＹ２２）・・・（６）
【００７２】
次に、この非特許文献２に記載の２倍算計算方法を本実施形態による、すなわち拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いるペアリング演算手段に適するよう変形する。
つまり、上記のＩｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標（Ｘ３：Ｙ３：Ｚ３）に加えて１／（ｘ３ｙ３）＝Ｚ３／Ｔ３を満たすＴ３座標を求める必要がある。
ここで、Ｔ３は以下の条件（式（７））を満たす。
【００７３】
【数５】
0005450240.tif 000006
【００７４】
さらに、変形して、式（８）を得る。
【００７５】
【数６】
0005450240.tif 000007
【００７６】
以上より、Ｔ３は、式（９）とおける。
【００７７】
Ｔ３＝（Ｘ２２＋ａＹ２２）（Ｘ２２＋ａＹ２２−２ｄＺ２２）・・・（９）
【００７８】
次に楕円曲線ａｘ２＋ｙ２＝１＋ｄｘ２ｙ２をｘ＝Ｚ２／Ｘ２、ｙ＝Ｚ２／Ｙ２を用いて変換すると、式（１０）を得る。
【００７９】
（Ｘ２２＋ａＹ２２）Ｚ２２＝Ｘ２２Ｙ２２＋ｄＺ２４・・・（１０）
【００８０】
Ｚ２２で両辺を割ることによって、式（１１）とおける。
【００８１】
【数７】
0005450240.tif 000008
【００８２】
Ｘ２２Ｙ２２＝Ｔ２２Ｚ２２を用いることで式（１２）を得る。
【００８３】
２ｄＺ２２＝２（Ｘ２２＋ａＹ２２−Ｔ２２）・・・（１２）
【００８４】
式（１２）を式（５）に代入することによりＹ３が求まる。
【００８５】
Ｙ３＝２Ｘ２Ｙ２（２Ｔ２２−Ｘ２２−ａＹ２２）・・・（１３）
【００８６】
式（１２）を式（９）に代入することによりＴ３が求まる。
【００８７】
Ｔ３＝（Ｘ２２＋ａＹ２２）（２Ｔ２２−Ｘ２２−ａＹ２２）・・・（１４）
【００８８】
次に非特許文献４に基づくと、ｇＲ，Ｒ（Ｑ）は式（１５）で表すことができる。
【００８９】
ｇＲ，Ｒ（Ｑ）＝ｃ０ＺＺηα＋ｃ０ＸＹｙ０＋ｃ０ＸＺ・・・（１５）
【００９０】
射影座標を用いてＲ＝（Ｘ３：Ｙ３：Ｚ３）とした場合、式（１５）の係数ｃ０ＺＺ、ｃ０ＸＹ、ｃ０ＸＺは以下の式（１６）〜（１８）で求められる。
【００９１】
ｃ０ＺＺ＝Ｘ３Ｚ３（Ｚ３−Ｙ３）・・・（１６）
ｃ０ＸＹ＝ｄＸ３２−Ｚ３３・・・（１７）
ｃ０ＸＺ＝Ｚ３（Ｚ３Ｙ３−ａＸ３２）・・・（１８）
【００９２】
Ｒの各座標はすべてＦｑの元であるため、Ｆｑの元をｇＲ，Ｒ（Ｑ）全体に乗算したとしても、あるいはＦｑの元でｇＲ，Ｒ（Ｑ）全体を割った結果を、新たにｇＲ，Ｒ（Ｑ）とおきなおして計算したとしても、乗算または除算に用いたＦｑの元は最後に行うｆのべき乗の過程で単位元となるためペアリングの演算結果には影響しない。また、Ｒの各座標は全てＦｑの元であるため、これらの座標でｇＲ，Ｐ（Ｑ）全体に乗算する、または座標ｇＲ，Ｒ（Ｑ）全体をすることで、ｇＲ，Ｒ（Ｑ）の係数を、拡張射影座標を用いる表現からＡｆｆｉｎｅ座標を用いる表現に変換し、その後Ａｆｆｉｎｅ座標を用いる表現から拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いる表現へと変換することでｇＲ，Ｒ（Ｑ）を得る。
【００９３】
ｇＲ，Ｒ（Ｑ）全体をＺ３３で割ることによって式（１６）より式（１９）を得る。
【００９４】
【数８】
0005450240.tif 000009
【００９５】
ｘ２＝Ｘ３／Ｚ３、ｙ２＝Ｙ３／Ｚ３を用いて射影座標をＡｆｆｉｎｅ座標（ｘ２，ｙ２）に変換することによって式（２０）を得る。
【００９６】
ｃＺＺ＝ｘ２（１−ｙ２）・・・（２０）
【００９７】
さらに、ｘ２＝Ｚ２／Ｘ２、ｙ２＝Ｚ２／Ｙ２、ｘ２ｙ２＝Ｚ２／Ｔ２を満たす拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標（Ｘ２：Ｙ２：Ｔ２：Ｚ２）を用いて変換することで式（２１）を得る。
【００９８】
【数９】
0005450240.tif 000010
【００９９】
式（１７）をＺ３３で割ることによって式（２２）を得る。
【０１００】
【数１０】
0005450240.tif 000011
【０１０１】
ｘ２＝Ｘ３／Ｚ３、ｙ２＝Ｙ３／Ｚ３を用いて射影座標をＡｆｆｉｎｅ座標（ｘ２，ｙ２）変換することによって式（２３）を得る。
【０１０２】
ｃＸＹ＝ｄｘ２２ｙ２−１・・・（２３）
【０１０３】
さらに、ｘ２＝Ｚ２／Ｘ２、ｙ２＝Ｚ２／Ｙ２、ｘ２ｙ２＝Ｚ２／Ｔ２を満たす拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標（Ｘ２：Ｙ２：Ｔ２：Ｚ２）を用いて変換することで式（２４）を得る。
【０１０４】
【数１１】
0005450240.tif 000012
【０１０５】
同様に式（１８）をＺ３３で割ることによって式（２５）を得る。
【０１０６】
【数１２】
0005450240.tif 000013
【０１０７】
ｘ２＝Ｘ２／Ｚ２、ｙ２＝Ｙ２／Ｚ２を用いて射影座標をＡｆｆｉｎｅ座標（ｘ２，ｙ２）変換することによって式（２６）を得る。
【０１０８】
ｃＸＹ＝ｙ２−ａｘ２２・・・（２６）
【０１０９】
さらに、ｘ２＝Ｚ２／Ｘ２、ｙ２＝Ｚ２／Ｙ２、ｘ２ｙ２＝Ｚ２／Ｔ２を満たす拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標（Ｘ２：Ｙ２：Ｔ２：Ｚ２）を用いて変換することで式（２７）を得る。
【０１１０】
【数１３】
0005450240.tif 000014
【０１１１】
ｇＲ，Ｒ（Ｑ）全体に２Ｘ２２Ｙ２を掛けることでｃＺＺ←２Ｘ２２Ｙ２ｃＺＺを計算し、式（２８）を得る。
【０１１２】
ｃＺＺ＝２Ｘ２Ｚ２（Ｙ２−Ｚ２）・・・（２８）
【０１１３】
ｇＲ，Ｒ（Ｑ）全体に２Ｘ２２Ｙ２を掛けることでｃＸＹ←２Ｘ２２Ｙ２ｃＸＹを計算し式（２９）を得る。
【０１１４】
ｃＸＹ＝２ｄＺ２３−２Ｘ２２Ｙ２・・・（２９）
【０１１５】
Ｘ２Ｙ２＝Ｔ２Ｚ２を用いて変形することで式（３０）を得る。
【０１１６】
ｃＸＹ＝２ｄＺ２３−２Ｘ２Ｔ２Ｚ２＝Ｚ２（２ｄＺ２２−２Ｘ２Ｔ２）・・・（３０）
【０１１７】
さらに、式（１２）を用いることで式（３１）を得る。
【０１１８】
ｃＸＹ＝Ｚ２（２（Ｘ２２＋ａＹ２２−Ｔ２２）２Ｘ２Ｔ２）・・・（３１）
【０１１９】
ｇＲ，Ｒ（Ｑ）全体に２Ｘ２２Ｙ２を掛けることでＣの係数ｃＸＺ←２Ｘ２２Ｙ２ｃＸＺを計算し式（３２）を得る。
【０１２０】
ｃＸＺ＝２Ｘ２２Ｚ２−２ａＹ２Ｚ２２・・・（３２）
【０１２１】
最後にｇＲ，Ｒ（Ｑ）全体をＺ２で割ることによって、Ｃの係数ｃＺＺ←ｃＺＺ／Ｚ２、ｃＸＹ←ｃＸＹ／Ｚ２、ｃＸＺ←ｃＸＺ／Ｚ２を計算することで式（３３）〜（３５）を得る。
【０１２２】
ｃＺＺ＝２Ｘ２（Ｙ２−Ｚ２）・・・（３３）
ｃＸＹ＝２（Ｘ２２＋ａＹ２２−Ｔ２２）−２Ｘ２Ｔ２・・・（３４）
ｃＸＺ＝２（Ｘ２２−ａＹ２Ｚ２）・・・（３５）
【０１２３】
以上をアルゴリズムの形でまとめると、図４で示す手順となる。
【０１２４】
（加算処理）
次に、図２を参照しつつ、図５および図６に沿って図３のステップＳ１０６における処理を説明する。
図５は、図３のステップＳ１０６において係数ａが−１以外の場合の加算処理の手順を示すフローチャートである。
なお、図５において、入力時のＰの座標は（Ｘ１：Ｙ１：Ｔ１：Ｚ１）、Ｒの座標は（Ｘ２：Ｙ２：Ｔ２：Ｚ２）であるとする。
ステップＳ３０１において、楕円曲線加算演算部１１５が、Ａ←Ｘ１Ｘ２、Ｂ←Ｙ１Ｙ２、Ｃ←Ｔ２Ｚ１、Ｄ←Ｔ１Ｚ２をＦｑ上でそれぞれ計算する（４ｍ）。
ここでＺ１＝１である場合、Ｃ←Ｔ２Ｚ１はＣ←Ｔ２となり、乗算の必要がなくなるため、演算コストを１ｍ削減することができる。
ステップＳ３０２において、楕円曲線加算演算部１１５が、Ｅ←（Ｘ１＋Ｙ１）（Ｘ２−Ｙ２）＋Ｂ−Ａ、Ｆ←Ｃ＋Ｄ、Ｇ←Ｃ−Ｄ、Ｈ←Ａ＋ａＢ、Ｉ←Ｔ１Ｔ２をＦｑ上でそれぞれ計算する（２ｍ，１Ｄ）。
ステップＳ３０３において、楕円曲線加算演算部１１５が、ｃＺＺ←Ｙ２Ｚ１−Ｙ１Ｚ２をＦｑ上で計算する（２ｍ）。
ここでＺ１＝１である場合、ｃＺＺ←Ｙ２−Ｙ１Ｚ２となり、１回分の乗算の必要がなくなるため、演算コストを１ｍ削減することができる。
【０１２５】
ステップＳ３０４において、楕円曲線加算演算部１１５が、ｃＸＹ←（Ｙ１−Ｔ１）（Ｙ２＋Ｔ２）−Ｂ＋Ｉ＋ＥをＦｑ上で計算する（１ｍ）。
ステップＳ３０５において、楕円曲線加算演算部１１５が、ｃＸＺ←Ｄ−Ｃ＋（Ｘ１Ｚ２＋Ｘ２Ｚ１）をＦｑ上で計算する（２ｍ）。
ここでＺ１＝１である場合、ｃＸＺ←Ｄ−Ｃ＋（Ｘ１Ｚ２＋Ｘ２）となり、１回分の乗算の必要がなくなるため、演算コストを１ｍ削減することができる。
【０１２６】
ステップＳ３０６において、ｇＲ，Ｐ（Ｑ）←ｃＺＺηα＋ｃＸＹｙ０＋ｃＸＺをＦｑのｋ／２次拡大体Ｆｑ２（ｑ２＝ｑｋ／２）上で計算する（ｋｍ）。
【０１２７】
ステップＳ３０７において、ｆ←ｆｇＲ，Ｐ（Ｑ）をＦｑのｋ次拡大体Ｆｑ１（ｑ１＝ｑｋ）上で計算する（１Ｍ）。
【０１２８】
ステップＳ３０８において、楕円曲線加算演算部１１５が、ｉ＝０であるか否かを判定し、ｉ＝０であれば（Ｓ３０８→Ｙｅｓ）、ステップＳ３１４の処理に進み、そうでなければ（Ｓ３０８→Ｎｏ）、ステップＳ３０９に進む。
ステップＳ３０９において、楕円曲線加算演算部１１５が、Ｘ３←ＨＧをＦｑ上で計算する（１ｍ）。
ステップＳ３１０において、楕円曲線加算演算部１１５が、Ｙ３←ＥＦをＦｑ上で計算する（１ｍ）。
ステップＳ３１１において、楕円曲線加算演算部１１５が、Ｔ３←ＨＥをＦｑ上で計算する（１ｍ）。
ステップＳ３１２において、楕円曲線加算演算部１１５が、Ｚ３←ＦＧをＦｑ上で計算する（１ｍ）
【０１２９】
ステップＳ３１３において、楕円曲線加算演算部１１５が、演算結果をＩｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＲ←（Ｘ３：Ｙ３：Ｔ３：Ｚ３）としｆとともに出力し、加算処理を終了する。
ステップＳ３１４では、楕円曲線加算演算部１１５が、演算結果をｆとして出力し、加算処理を終了する。
図５に示す加算アルゴリズムの総演算コストは１Ｍ＋（ｋ＋１５）ｍ＋１Ｄ、Ｚ１＝１の場合、１Ｍ＋（ｋ＋１２）ｍ＋１Ｄとなる。なお、通常はＺ１＝１が用いられる。
【０１３０】
ここで、図５の処理の詳細について説明する。
非特許文献３に基づく加算公式によるとＴｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の２点Ｐ＝（ｘ１，ｙ１）、Ｑ＝（ｘ２，ｙ２）に対して係数ｄを用いない加算Ｐ＋Ｑ＝（ｘ３，ｙ３）は以下の式（３６）で計算することができる。
【０１３１】
この式（３６）より、図５に示す加算アルゴリズムを導く。
【０１３２】
【数１４】
0005450240.tif 000015
【０１３３】
２点Ｐ＝（ｘ１，ｙ１）、Ｑ＝（ｘ２，ｙ２）と拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現したＰ＝（Ｘ１：Ｙ１：Ｔ１：Ｚ１）、Ｑ＝（Ｘ２：Ｙ２：Ｔ２：Ｚ２）は以下の関係を満たす。
【０１３４】
ｘ１＝  Ｚ１／Ｘ１、ｙ１＝Ｚ１／Ｙ１、ｘ１ｙ１＝  Ｚ１／Ｔ１、ｘ２＝  Ｚ２／Ｘ２、ｙ２＝Ｚ２／Ｙ２、ｘ２ｙ２＝  Ｚ２／Ｔ２  
【０１３５】
これらの関係式を、式（３６）に代入することによって、加算公式（式（３６））を変形し、式（３７）を得る。
【０１３６】
【数１５】
0005450240.tif 000016
【０１３７】
次に、以下の式（３８）より式（３９）が導かれる。
【０１３８】
【数１６】
0005450240.tif 000017
【０１３９】
Ｘ１Ｙ１Ｘ２Ｙ２＝Ｚ１Ｚ２Ｔ１Ｔ２・・・（３９）
【０１４０】
この式（３９）を式（３７）に代入して、変形すると、以下の式（４０）を得る。
【０１４１】
【数１７】
0005450240.tif 000018
【０１４２】
最終的にＰ＋Ｑは以下の式（４１）を計算することで求められる。
【０１４３】
【数１８】
0005450240.tif 000019
【０１４４】
式（３９）より、ｘ３＝Ｚ３／Ｘ３、ｙ３＝Ｚ３／Ｙ３、ｘ３ｙ３＝Ｚ３／Ｔ３  を満たすＸ３、Ｙ３、Ｔ３、Ｚ３をそれぞれ求めると、以下の式（４２）〜（４５）を得る。
【０１４５】
Ｘ３＝（Ｘ１Ｘ２＋ａＹ１Ｙ２）（Ｚ１Ｔ２−Ｔ１Ｚ２）・・・（４２）
Ｙ３＝（Ｙ１Ｘ２−Ｘ１Ｙ２）（Ｚ１Ｔ２＋Ｔ１Ｚ２）・・・（４３）
Ｔ３＝（Ｘ１Ｘ２＋ａＹ１Ｙ２）（Ｙ１Ｘ２−Ｘ１Ｙ２）・・・（４４）
Ｚ３＝（Ｚ１Ｔ２＋Ｔ１Ｚ２）（Ｚ１Ｔ２−Ｔ１Ｚ２）・・・（４５）
【０１４６】
式（４２）〜（４５）を用いることでＰ＋Ｒ＝（Ｘ１：Ｙ１：Ｔ１：Ｚ１）＋（Ｘ２：Ｙ２：Ｔ２：Ｚ２）＝（Ｘ３：Ｙ３：Ｔ３：Ｚ３）を計算することができる。
実際にｘ３＝Ｚ３／Ｘ３、ｙ３＝Ｚ３／Ｙ３、ｘ３ｙ３＝Ｚ３／Ｔ３を満たしていることは以下の式（４６）〜（４８）で確認できる。
【０１４７】
【数１９】
0005450240.tif 000020
【０１４８】
次に非特許文献４に基づくと、ｇＲ，Ｐ（Ｑ）は式（４９）で表すことができる。
【０１４９】
ｇＲ，Ｐ（Ｑ）＝ｃ０ＺＺηα＋ｃ０ＸＹｙ０＋ｃ０ＸＺ・・・（４９）
【０１５０】
拡張射影座標を用いてＰ＝（Ｘ３：Ｙ３：Ｔ３：Ｚ３）、Ｒ＝（Ｘ４：Ｙ４：Ｔ４：Ｚ４）とした場合、式（４７）の係数ｃ０ＺＺ、ｃ０ＸＹ、ｃ０ＸＺは以下の式（５０）〜（５２）で求められる。
【０１５１】
ｃ０ＺＺ＝Ｘ３Ｘ４（Ｙ３Ｚ４−Ｙ４Ｚ３）・・・（５０）
ｃ０ＸＹ＝Ｚ３Ｚ４（Ｘ３Ｚ４−Ｘ４Ｚ３＋Ｘ３Ｙ４−Ｘ４Ｙ３）・・・（５１）
ｃ０ＸＺ＝Ｘ４Ｙ４Ｚ３２−Ｘ３Ｙ３Ｚ４２＋Ｙ３Ｙ４（Ｘ４Ｚ３−Ｘ３Ｚ４）・・・（５２）
【０１５２】
ＰおよびＲの各座標は全てＦｑの元であるため、Ｆｑの元をｇＲ，Ｐ（Ｑ）全体に乗算したとしても、あるいはＦｑの元でｇＲ，Ｐ（Ｑ）全体を割った結果を、新たにｇＲ，Ｐ（Ｑ）とおきなおして計算したとしても、乗算または除算に用いたＦｑの元は最後に行うｆのべき乗の過程で単位元となるためペアリングの演算結果には影響しない。また、ＰおよびＲの各座標は全てＦｑの元であるため、これらの座標でｇＲ，Ｐ（Ｑ）全体に乗算する、または座標ｇＲ，Ｐ（Ｑ）全体をすることで、ｇＲ，Ｐ（Ｑ）の係数を、拡張射影座標を用いる表現からＡｆｆｉｎｅ座標を用いる表現に変換し、その後Ａｆｆｉｎｅ座標を用いる表現から拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いる表現へと変換することで図５に示すｇＲ，Ｐ（Ｑ）を得る。
【０１５３】
ｇＲ，Ｐ（Ｑ）全体をＺ３２Ｚ４２で割ることによって式（５０）より式（５３）を得る。
【０１５４】
【数２０】
0005450240.tif 000021
【０１５５】
ｘ３＝Ｘ３／Ｚ３、ｙ３＝Ｙ３／Ｚ３、ｘ４＝Ｘ４／Ｚ４、ｙ４＝Ｙ４／Ｚ４を用いて射影座標をＡｆｆｉｎｅ座標（ｘ３，ｙ３）および（ｘ４，ｙ４）に変換することによって式（５４）を得る。
【０１５６】
ｃＺＺ＝ｘ３ｘ４（ｙ３−ｙ４）・・・（５４）
【０１５７】
ｘ３＝Ｚ１／Ｘ１、ｙ３＝Ｚ１／Ｙ１、ｘ３ｙ３＝Ｚ１／Ｔ１、ｘ４＝Ｚ２／Ｘ２、ｙ４＝Ｚ２／Ｙ２、ｘ４ｙ４＝Ｚ２／Ｔ２を満たすＩｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標（Ｘ１：Ｙ１：Ｔ１：Ｚ１）および（Ｘ２：Ｙ２：Ｔ２：Ｚ２）を用いて変換することで式（５５）を得る。
【０１５８】
【数２１】
0005450240.tif 000022
【０１５９】
ｇＲ，Ｐ（Ｑ）全体をＺ３２Ｚ４２で割ることによって式（５１）より式（５６）を得る。
【０１６０】
【数２２】
0005450240.tif 000023
【０１６１】
ｘ３＝Ｘ３／Ｚ３、ｙ３＝Ｙ３／Ｚ３、ｘ４＝Ｘ４／Ｚ４、ｙ４＝Ｙ４／Ｚ４を用いて射影座標をＡｆｆｉｎｅ座標（ｘ３，ｙ３）および（ｘ４，ｙ４）に変換することで式（５７）を得る。
【０１６２】
ｃＸＹ＝ｘ３−ｘ４＋ｘ３ｙ４−ｘ４ｙ３・・・（５７）
【０１６３】
ｘ３＝Ｚ１／Ｘ１、ｙ３＝Ｚ１／Ｙ１、ｘ３ｙ３＝Ｚ１／Ｔ１、ｘ４＝Ｚ２／Ｘ２、ｙ４＝Ｚ２／Ｙ２、ｘ４ｙ４＝Ｚ２／Ｔ２を満たすＩｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標（Ｘ１：Ｙ１：Ｔ１：Ｚ１）および（Ｘ２：Ｙ２：Ｔ２：Ｚ２）を用いて変換することで式（５８）を得る。
【０１６４】
【数２３】
0005450240.tif 000024
【０１６５】
ｇＲ，Ｐ（Ｑ）全体をＺ３２Ｚ４２で割ることによって式（５２）より式（５９）を得る。
【０１６６】
【数２４】
0005450240.tif 000025
【０１６７】
ｘ３＝Ｘ３／Ｚ３、ｙ３＝Ｙ３／Ｚ３、ｘ４＝Ｘ４／Ｚ４、ｙ４＝Ｙ４／Ｚ４を用いて射影座標をＡｆｆｉｎｅ座標（ｘ３，ｙ３）および（ｘ４，ｙ４）に変換することで式（６０）を得る。
【０１６８】
ｃＸＺ＝ｘ４ｙ４−ｘ３ｙ３＋ｙ３ｙ４（ｘ４−ｘ３）・・・（６０）
【０１６９】
ｘ３＝Ｚ１／Ｘ１、ｙ３＝Ｚ１／Ｙ１、ｘ３ｙ３＝Ｚ１／Ｔ１、ｘ４＝Ｚ２／Ｘ２、ｙ４＝Ｚ２／Ｙ２、ｘ４ｙ４＝Ｚ２／Ｔ２を満たすＩｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標（Ｘ１：Ｙ１：Ｔ１：Ｚ１）および（Ｘ２：Ｙ２：Ｔ２：Ｚ２）を用いて変換することで式（６１）が得られる。
【０１７０】
【数２５】
0005450240.tif 000026
【０１７１】
ｇＲ，Ｐ（Ｑ）全体にＸ１Ｘ２Ｙ１Ｙ２を掛けることによって式（５５）より式（６２）を得る。
【０１７２】
ｃＺＺ←Ｘ１Ｘ２Ｙ１Ｙ２ｃＺＺ＝Ｚ１Ｚ２（Ｙ２Ｚ１−Ｙ１Ｚ２）・・・（６２）
【０１７３】
ｇＲ，Ｐ（Ｑ）全体にＸ１Ｘ２Ｙ１Ｙ２を掛けることによって式（５８）より式（６３）を得る。
【０１７４】
ｃＸＹ←Ｘ１Ｘ２Ｙ１Ｙ２ｃＸＹ＝Ｙ１Ｘ２Ｙ２Ｚ１−Ｘ１Ｙ１Ｙ２Ｚ２＋Ｚ１Ｚ２（Ｘ２Ｙ１−Ｘ１Ｙ２）・・・（６３）
【０１７５】
さらに、Ｘ１Ｙ１＝Ｔ１Ｚ１、Ｘ２Ｙ２＝Ｔ２Ｚ２を用いて変形することで式（６４）を得る。
【０１７６】
ｃＸＹ＝Ｚ１Ｚ２（Ｙ１Ｔ２−Ｙ２Ｔ１＋Ｘ２Ｙ１−Ｘ１Ｙ２）・・・（６４）
【０１７７】
ｇＲ，Ｐ（Ｑ）全体にＸ１Ｘ２Ｙ１Ｙ２を掛けることによって式（５９）より式（６５）を得る。
【０１７８】
ｃＸＺ←Ｘ１Ｘ２Ｙ１Ｙ２ｃＸＺ＝Ｘ１Ｙ１Ｚ２２−Ｘ２Ｙ２Ｚ１２＋Ｚ１Ｚ２（Ｘ１Ｚ２−Ｘ２Ｚ１）・・・（６５）
【０１７９】
さらに、Ｔ１＝Ｘ１Ｙ１Ｚ１、Ｔ２＝Ｘ２Ｙ２Ｚ２を用いて変形することで式（６６）を得る。
【０１８０】
ｃＸＺ＝Ｚ１Ｚ２（Ｔ１Ｚ２−Ｔ２Ｚ１＋Ｘ１Ｚ２−Ｘ２Ｚ１）・・・（６６）
【０１８１】
ｇＲ，Ｐ（Ｑ）全体をＺ１Ｚ２で割、ｃＺＺ←ｃＺＺ／（Ｚ１Ｚ２）、ｃＸＹ←ｃＸＹ／（Ｚ１Ｚ２）、ｃＸＺ←ｃＸＺ／（Ｚ１Ｚ２）を計算することにより式（６７）〜（６９）を得る。
【０１８２】
ｃＺＺ＝Ｙ２Ｚ１−Ｙ１Ｚ２・・・（６７）
ｃＸＹ＝Ｙ１Ｔ２−Ｙ２Ｔ１＋Ｘ２Ｙ１−Ｘ１Ｙ２・・・（６８）
ｃＸＺ＝Ｔ１Ｚ２−Ｔ２Ｚ１＋Ｘ１Ｚ２−Ｘ２Ｚ１・・・（６９）
【０１８３】
上記の内容をアルゴリズムの形でまとめると、図５に示す処理手順となる。
【０１８４】
図６は、図３のステップＳ１０６において係数ａが−１の場合の加算処理の手順を示すフローチャートである。
なお、図６において、入力時におけるＰの座標は（Ｘ１：Ｙ１：Ｔ１：Ｚ１）、Ｒの座標は（Ｘ２：Ｙ２：Ｔ２：Ｚ２）であるとする。
ステップＳ４０１において、楕円曲線加算演算部１１５が、Ａ←（Ｘ１−Ｙ１）（Ｘ２＋Ｙ２）、Ｂ←（Ｘ１＋Ｙ１）（Ｘ２−Ｙ２）、Ｃ←２Ｔ２Ｚ１、Ｄ←２Ｔ１Ｚ２をＦｑ上でそれぞれ計算する（４ｍ）。
ここでＺ１＝１である場合、Ｃ←２Ｔ２Ｚ１はＣ←２Ｔ２となり、乗算の必要がなくなるため、演算コストを１ｍ削減することができる。
ステップＳ４０２において、楕円曲線加算演算部１１５が、Ｅ←Ａ＋Ｂ、Ｆ←Ｃ＋Ｄ，Ｇ←Ｃ−Ｄ，Ｈ←Ｂ−ＡをＦｑ上でそれぞれ計算する。
ステップＳ４０３において、楕円曲線加算演算部１１５が、ｃＺＺ←２（Ｙ２Ｚ１−Ｙ１Ｚ２）をＦｑ上で計算する（２ｍ）。
ここでＺ１＝１である場合、ｃＺＺ←２（Ｙ２−Ｙ１Ｚ２）となり、１回分の乗算の必要がなくなるため、演算コストを１ｍ削減することができる。
【０１８５】
ステップＳ４０４において、楕円曲線加算演算部１１５が、ｃＸＹ←２（Ｙ１Ｔ２−Ｙ２Ｔ１）＋ＨをＦｑ上で計算する（２ｍ）。
ステップＳ４０５において、楕円曲線加算演算部１１５が、ｃＸＺ←Ｄ−Ｃ＋２（Ｘ１Ｚ２−Ｘ２Ｚ１）をＦｑ上で計算する（２ｍ）。
ここでＺ１＝１である場合、ｃＸＺ←Ｄ−Ｃ＋２（Ｘ１Ｚ２−Ｘ２）となり、１回分の乗算の必要がなくなるため、演算コストを１ｍ削減することができる。
ステップＳ４０６において、楕円曲線加算演算部１１５が、ｇＲ，Ｐ（Ｑ）←ｃＺＺηα＋ｃＸＹｙ０＋ｃＸＺをＦｑのｋ／２次拡大体Ｆｑ２（ｑ２＝ｑｋ／２）上で計算する（ｋｍ）。
ステップＳ４０７において、楕円曲線加算演算部１１５が、ｆ←ｆｇＲ，Ｐ（Ｑ）をＦｑのｋ次拡大体Ｆｑ１（ｑ１＝ｑｋ）上で計算する（１Ｍ）。
【０１８６】
ステップＳ４０８において、楕円曲線加算演算部１１５が、ｉ＝０であるか否かを判定し、ｉ＝０であれば（Ｓ４０８→Ｙｅｓ）、ステップＳ４１４の処理に進み、そうでなければ（Ｓ４０８→Ｎｏ）、ステップＳ４０９に進む。
ステップＳ４０９において、楕円曲線加算演算部１１５が、Ｘ３←ＥＧをＦｑ上で計算する（１ｍ）。
ステップＳ４１０において、楕円曲線加算演算部１１５が、Ｙ３←ＨＦをＦｑ上で計算する（１ｍ）。
ステップＳ４１１において、楕円曲線加算演算部１１５が、Ｔ３←ＥＨをＦｑ上で計算する（１ｍ）。
ステップＳ４１２において、楕円曲線加算演算部１１５が、Ｚ３←ＦＧをＦｑ上で計算する（１ｍ）。
ステップＳ４１３において、楕円曲線加算演算部１１５が、演算結果をＩｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いたＲ←（Ｘ３：Ｙ３：Ｔ３：Ｚ３）としてｆとともに出力し、加算処理を終了する。
ステップＳ４１４では、楕円曲線加算演算部１１５が、演算結果をｆとして出力し、加算処理を終了する。
図６に示す加算アルゴリズムの演算コストは１Ｍ＋（ｋ＋１４）ｍ（Ｚ１＝１以外）、１Ｍ＋（ｋ＋１１）ｍ（Ｚ１＝１）となる。この処理における演算コストは、非特許文献４において該当するコストより、１ｍ＋１Ｄ減っている。非特許文献４に記載の技術にａ＝−１を適用した場合と比べても１ｍ減っている。
【０１８７】
ここで、図６に示す処理について詳細に説明する。
ここでは、図５に示す加算方法を変形することにより、図６に示す加算アルゴリズムを導く。
図５における加算方法（式（４２）〜（４５））に対して、ａ＝−１を代入することにより以下の式（７０）〜（７３）が得られる。
【０１８８】
Ｘ３＝（Ｘ１Ｘ２＋ａＹ１Ｙ２）（Ｚ１Ｔ２−Ｔ１Ｚ２）・・・（４２）
Ｙ３＝（Ｙ１Ｘ２−Ｘ１Ｙ２）（Ｚ１Ｔ２＋Ｔ１Ｚ２）・・・（４３）
Ｔ３＝（Ｘ１Ｘ２＋ａＹ１Ｙ２）（Ｙ１Ｘ２−Ｘ１Ｙ２）・・・（４４）
Ｚ３＝（Ｚ１Ｔ２＋Ｔ１Ｚ２）（Ｚ１Ｔ２−Ｔ１Ｚ２）・・・（４５）
【０１８９】
Ｘ３＝（Ｘ１Ｘ２−Ｙ１Ｙ２）（Ｚ１Ｔ２−Ｔ１Ｚ２）・・・（７０）
Ｙ３＝（Ｙ１Ｘ２−Ｘ１Ｙ２）（Ｚ１Ｔ２＋Ｔ１Ｚ２）・・・（７１）
Ｔ３＝（Ｘ１Ｘ２−Ｙ１Ｙ２）（Ｙ１Ｘ２−Ｘ１Ｙ２）・・・（７２）
Ｚ３＝（Ｚ１Ｔ２＋Ｔ１Ｚ２）（Ｚ１Ｔ２−Ｔ１Ｚ２）・・・（７３）
【０１９０】
式（７０）〜（７３）を用いることによりＰ＋Ｒ＝（Ｘ１：Ｙ１：Ｔ１：Ｚ１）＋（Ｘ２：Ｙ２：Ｔ２：Ｚ２）＝（Ｘ３：Ｙ３：Ｔ３：Ｚ３）を計算することができ、（Ｘ３：Ｙ３：Ｔ３：Ｚ３）の代わりに（Ｘ４：Ｙ４：Ｔ４：Ｚ４）＝（４Ｘ３：４Ｙ３：４Ｔ３：４Ｚ３）を用いてもｘ３＝Ｚ４／Ｘ４、ｙ３＝Ｚ４／Ｙ４、ｘ３ｙ３＝Ｚ４／Ｔ４を満たすことから、以下の式（７４）〜（７７）を用いることによりＰ＋Ｑ＝（Ｘ１：Ｙ１：Ｔ１：Ｚ１）＋（Ｘ２：Ｙ２：Ｔ２：Ｚ２）＝（Ｘ３：Ｙ３：Ｔ３：Ｚ３）を計算できる。
【０１９１】
Ｘ３＝（２Ｘ１Ｘ２−２Ｙ１Ｙ２）（２Ｚ１Ｔ２−２Ｔ１Ｚ２）・・・（７４）
Ｙ３＝（２Ｙ１Ｘ２−２Ｘ１Ｙ２）（２Ｚ１Ｔ２＋２Ｔ１Ｚ２）・・・（７５）
Ｔ３＝（２Ｘ１Ｘ２−２Ｙ１Ｙ２）（２Ｙ１Ｘ２−２Ｘ１Ｙ２）・・・（７６）
Ｚ３＝（２Ｚ１Ｔ２＋２Ｔ１Ｚ２）（２Ｚ１Ｔ２−２Ｔ１Ｚ２）・・・（７７）
【０１９２】
ここで、Ｘ３、Ｙ３、Ｚ３座標を求める際に必要となる式は以下の条件（式（７８），（７９））を満たす。
【０１９３】
（２Ｘ１Ｘ２−２Ｙ１Ｙ２）＝（Ｘ１−Ｙ１）（Ｘ２＋Ｙ２）＋（Ｘ１＋Ｙ１）（Ｘ２−Ｙ２）・・・（７８）
（２Ｙ１Ｘ２−２Ｘ１Ｙ２）＝（Ｘ１＋Ｙ１）（Ｘ２−Ｙ２）−（Ｘ１−Ｙ１）（Ｘ２＋Ｙ２）・・・（７９）
【０１９４】
次にｇＲ，Ｐ（Ｑ）について説明する。
図５におけるｇＲ，Ｐ（Ｑ）の式（６７）から（６９）で表される係数を２倍し、ｃＺＺ←２ｃＺＺ、ｃＸＹ←２ｃＸＹ、ｃＸＺ←２ｃＸＺを計算することにより式（８０）〜（８２）を得る。
【０１９５】
ｃＺＺ＝Ｙ２Ｚ１−Ｙ１Ｚ２・・・（６７）
ｃＸＹ＝Ｙ１Ｔ２−Ｙ２Ｔ１＋Ｘ２Ｙ１−Ｘ１Ｙ２・・・（６８）
ｃＸＺ＝Ｔ１Ｚ２−Ｔ２Ｚ１＋Ｘ１Ｚ２−Ｘ２Ｚ１・・・（６９）
【０１９６】
ｃＺＺ＝２（Ｙ２Ｚ１−Ｙ１Ｚ２）・・・（８０）
ｃＸＹ＝２（Ｙ１Ｔ２−Ｙ２Ｔ１）＋２Ｘ２Ｙ１−２Ｘ１Ｙ２・・・（８１）
ｃＸＺ＝２Ｔ１Ｚ２−２Ｔ２Ｚ１＋２（Ｘ１Ｚ２−Ｘ２Ｚ１）・・・（８２）
【０１９７】
上記の内容をアルゴリズムの形でまとめると、図６に示す処理手順となる。
【０１９８】
ここで、ａ＝−１の場合の加算処理において、１ｍ分、乗算コストが削減できる理由を、削減に影響する箇所のみを取り出して説明する。
【０１９９】
ａが−１以外の場合、加算は以下の方法で求まる。まず、前記した式（４２）〜（４５）をみてみる。
【０２００】
Ｘ３＝（Ｘ１Ｘ２＋ａＹ１Ｙ２）（Ｚ１Ｔ２−Ｔ１Ｚ２）・・・（４２）
Ｙ３＝（Ｙ１Ｘ２−Ｘ１Ｙ２）（Ｚ１Ｔ２＋Ｔ１Ｚ２）・・・（４３）
Ｔ３＝（Ｘ１Ｘ２＋ａＹ１Ｙ２）（Ｙ１Ｘ２−Ｘ１Ｙ２）・・・（４４）
Ｚ３＝（Ｚ１Ｔ２＋Ｔ１Ｚ２）（Ｚ１Ｔ２−Ｔ１Ｚ２）・・・（４５）
【０２０１】
上記の式の内、乗算の削減に影響するのはＥ＝Ｙ１Ｘ２−Ｘ１Ｙ２、Ｈ＝Ｘ１Ｘ２＋ａＹ１Ｙ２であり、これら２つの式を求める部分で以下の方法が適用できる。
【０２０２】
Ａ←Ｘ１Ｘ２、Ｂ←Ｙ１Ｙ２、Ｅ←（Ｘ１＋Ｙ１）（Ｘ２−Ｙ２）＋Ｂ−Ａ、Ｈ←Ａ＋ａＢ
【０２０３】
この場合の計算コストは３ｍ＋１Ｄ、ａ＝−１であればＨ←Ａ−Ｂとなり１Ｄの削減が可能となり計算コストは３ｍとなる。
【０２０４】
次にａ＝−１の場合、ａが−１以外の場合の加算結果（Ｘ３：Ｙ３：Ｔ３：Ｚ３）を求める代わりに（４Ｘ３：４Ｙ３：４Ｔ３：４Ｚ３）を加算結果とするようにアルゴリズムを修正する。
具体的には（４２）〜（４３）式にａ＝−１を代入し全体を４倍した以下の式（７４）〜（７７）で求めることができる。
【０２０５】
Ｘ３＝（２Ｘ１Ｘ２−２Ｙ１Ｙ２）（２Ｚ１Ｔ２−２Ｔ１Ｚ２）・・・（７４）
Ｙ３＝（２Ｙ１Ｘ２−２Ｘ１Ｙ２）（２Ｚ１Ｔ２＋２Ｔ１Ｚ２）・・・（７５）
Ｔ３＝（２Ｘ１Ｘ２−２Ｙ１Ｙ２）（２Ｙ１Ｘ２−２Ｘ１Ｙ２）・・・（７６）
Ｚ３＝（２Ｚ１Ｔ２＋２Ｔ１Ｚ２）（２Ｚ１Ｔ２−２Ｔ１Ｚ２）・・・（７７）
【０２０６】
ａが−１以外の場合のＥに相当するＥ＝２Ｙ１Ｘ２−２Ｘ１Ｙ２、Ｈに相当するＨ＝２Ｘ１Ｘ２−Ｙ１Ｙ２は以下の方法で求めることができる。
【０２０７】
Ａ←（Ｘ１−Ｙ１）（Ｘ２＋Ｙ２）、Ｂ←（Ｘ１＋Ｙ１）（Ｘ２−Ｙ２）、Ｅ←Ａ＋Ｂ、Ｈ←Ｂ−Ａ
【０２０８】
この場合の計算コストは２ｍとなりａが−１以外の場合に比べて１ｍ＋１Ｄの計算コストを削減できる。
【０２０９】
ここで、本実施形態の効果について説明する。非特許文献４に開示されている拡張射影座標を用いて表現した点Ｐ＝（Ｘ：Ｙ：Ｔ：Ｚ）（Ｚ≠１）を用いてＲｅｄｕｃｅｄ  Ｔａｔｅペアリングを計算したときにおいて、ｍ，ｓ，Ｄを、それぞれ定義体Ｆｑ上の乗算、２乗算、定数倍算の演算コストとし、Ｍ，Ｓを、それぞれＦｑのｋ次拡大体Ｆｑ１（ｑ１＝ｑｋ）上の乗算、２乗算の演算コストとした場合、ループ処理で計算される加算処理の演算コストは１Ｍ＋（ｋ＋１４）ｍ＋１Ｄ、２倍算処理の演算コストは１Ｍ＋１Ｓ＋（ｋ＋６）ｍ＋５ｓ＋２Ｄとなる。
【０２１０】
本実施形態における拡張Ｉｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した点Ｐ＝（Ｘ：Ｙ：Ｔ：Ｚ）（Ｚ≠１）を用いてＲｅｄｕｃｅｄ  Ｔａｔｅペアリングを計算した場合、ループ処理で計算される加算処理の演算コストは１Ｍ＋（ｋ＋１５）ｍ＋１Ｄ、２倍算処理の演算コストは１Ｍ＋１Ｓ＋（ｋ＋６）ｍ＋５ｓ＋２Ｄとなる。
【０２１１】
非特許文献４に開示されている拡張射影座標を用いて表現した点Ｐ＝（Ｘ：Ｙ：Ｔ：Ｚ）（Ｚ＝１）を用いてＲｅｄｕｃｅｄ  Ｔａｔｅペアリングを計算した場合、ループ処理で計算される加算処理の演算コストは１Ｍ＋（ｋ＋１２）ｍ＋１Ｄ、２倍算処理の演算コストは１Ｍ＋１Ｓ＋（ｋ＋６）ｍ＋５ｓ＋２Ｄとなる。
本実施形態における拡張Ｉｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した点Ｐ＝（Ｘ：Ｙ：Ｔ：Ｚ）（Ｚ＝１）を用いてＲｅｄｕｃｅｄ  Ｔａｔｅペアリングを計算した場合、ループ処理で計算される加算処理の演算コストは１Ｍ＋（ｋ＋１２）ｍ＋１Ｄ、２倍算処理の演算コストは１Ｍ＋１Ｓ＋（ｋ＋６）ｍ＋５ｓ＋２Ｄとなり、非特許文献４に開示されている計算方法と同等の演算コストとなる。
加算ステップにおけるＰのＺ座標を１にすることは実用上問題が無いため、Ｚ＝１とすることにより非特許文献４に開示されている計算方法と同等の演算速度を実現できる。
【０２１２】
さらに、楕円曲線の係数ａを−１とすることにより本実施形態における加算ステップの演算コストは１Ｍ＋（ｋ＋１１）ｍ、２倍算処理の演算コストは１Ｍ＋１Ｓ＋（ｋ＋６）ｍ＋５ｓとなり、非特許文献４に開示されている計算方法に比べて、加算処理において１ｍ＋Ｄ、２倍算ステップにおいて２Ｄの演算コストを削減できる。
【０２１３】
すなわち、本実施形態によれば、非特許文献４に記載の技術に比べてペアリング演算時の演算コストを削減できるためスカラ倍演算コストをより高速化することができる。これにより高速なＩＤベース暗号など楕円曲線上で定義されるペアリングの性質を用い、任意の文字列を公開鍵として用いることのできる署名方式や公開鍵暗号の実現が可能となる。
【０２１４】
《ＩＤベース暗号システム》
次に、本実施形態に係る楕円曲線ペアリング演算方法を利用したＩＤベース暗号システムについて図７〜図１５を参照して説明する。
【０２１５】
図７は、本実施形態に係る楕円曲線ペアリング演算方法を利用したＩＤベース暗号システムの構成例を示す図である。
図７に示すように、本実施形態のＩＤベース暗号システム２は、鍵生成センタに設置されている鍵発行装置３と、暗号化装置４と、復号化装置５とを備える。鍵発行装置３、暗号化装置４および復号化装置５のそれぞれは、ネットワーク２０１により接続されている。以下、暗号化装置４の利用者を利用者Ａ、復号化装置５の利用者を利用者Ｂとする。両者を区別する必要がない場合は、利用者と呼ぶ。
【０２１６】
これらの各装置を用いた本実施形態での暗号化および復号化処理の概略について説明する。本実施形態では、公開鍵として、所定のルールによって定められた利用者と対応付けられるＩＤ、例えば電子メールアドレスなどを用いるものとする。
まず、鍵発行装置３において、ＩＤベース暗号システム２全体で用いる公開パラメータおよびマスタ鍵を生成し、生成した公開パラメータを公開する。
暗号化したメッセージを送信する場合、暗号化装置４において、鍵発行装置３から取得した送信相手の公開鍵（利用者ＢのＩＤ）および公開パラメータを用いて暗号化対象データを暗号化することによって暗号化データを生成し、生成した暗号化データを送出する。復号化装置５では、予め、鍵発行装置３に自身の公開鍵に対応する秘密鍵の発行を依頼し、その秘密鍵および公開パラメータを用いて、暗号化装置４から受け取った暗号化データを復号する。
【０２１７】
《鍵生成》
次に、本実施形態に係る楕円曲線スカラ倍演算方法を利用した鍵生成方法について図８から図１１を参照して説明する。
【０２１８】
［鍵発行装置］
図８は、本実施形態に係る鍵発行装置の構成例を示す図である。
鍵発行装置３は、制御演算部３１０および記憶部３２０を有している。
制御演算部３１０は、入出力部３１１、制御部３１２、群選択部３１３、乱数生成部３１４、楕円曲線スカラ倍演算部３１５、ハッシュ関数選択部３１６、ハッシュ関数演算部３１７を有している。入出力部３１１は、公開パラメータおよびマスタ鍵生成処理または秘密鍵生成処理のいずれの処理を実行するかの処理選択情報や、公開パラメータおよびマスタ鍵生成処理時のセキュリティパラメータや、秘密鍵生成処理時の利用者の公開鍵などを入力情報として受け付けるとともに、生成された公開パラメータまたは秘密鍵を出力情報として出力する機能を有している。制御部３１２は、鍵発行装置３を制御する機能を有している。群選択部３１３は、群を選択する機能を有する。乱数生成部３１４は、乱数を生成する機能を有する。楕円曲線スカラ倍演算部３１５は、楕円曲線上の点のスカラ倍、定義体上の演算、剰余演算（ｍｏｄ）、比較などを行う機能を有する。ハッシュ関数選択部３１６は、ハッシュ関数を選択する機能を有する。ハッシュ関数演算部３１７は、ハッシュ関数選択部３１６で選択されたハッシュ関数を用いてハッシュ値を生成する機能を有する。
【０２１９】
記憶部３２０には、中間データ３２１、セキュリティパラメータ３２２、公開パラメータ３２３、マスタ鍵３２４、公開鍵３２５、秘密鍵３２６などが格納されている。中間データ３２１は、制御演算部３１０における演算時の中間データである。セキュリティパラメータ３２２は、入出力部３１１により入力を受け付けたセキュリティパラメータのデータである。公開パラメータ３２３は、制御演算部３１０で生成された公開パラメータのデータである。マスタ鍵３２４は、制御演算部３１０で生成されたマスタ鍵のデータである。公開鍵３２５は、入出力部３１１により入力を受け付けた公開鍵のデータである。秘密鍵３２６は、制御演算部３１０で生成された秘密鍵のデータである。
【０２２０】
なお、鍵発行装置３は、図１６に示すような、バス６７で接続されたＣＰＵ６１と、ＲＡＭなどのメモリ６２と、ＨＤＤやその他の外部記憶装置６５と、キーボードなどの入力装置６３と、ディスプレイなどの出力装置６４と、外部記憶装置６５や、入力装置６３や、出力装置６４と、バス６７とを中継するインタフェース６６とを備えた、一般的な構成を有する情報処理装置６上に構築することができる。
鍵発行装置３の制御演算部３１０および各部３１１〜３２０は、ＣＰＵ６１が、メモリ６２にロードされたプログラム（コードモジュールともいう）を実行することで、情報処理装置６上に具現化されるプロセスとして実現される。また、メモリ６２や、外部記憶装置６５が図８の記憶部３２０として使用される。
【０２２１】
また、前記したプログラムは、予め外部記憶装置６５に記憶され、必要に応じてメモリ６２上にロードされ、ＣＰＵ６１により実行される。なお、このプログラムは、可搬性の記憶媒体、例えばＣＤ−ＲＯＭなどに格納され、必要に応じて、これら可搬性の記憶媒体からメモリ６２にロードされてもよい。また、プログラムは、一旦、ＣＤ−ＲＯＭなどの可搬性の記憶媒体からＨＤＤなどの外部記憶装置６５にインストールされた後、必要に応じて、この外部記憶装置６５からメモリ６２にロードされてもよい。さらに、プログラムは、図示していないネットワーク接続装置を介して、ネットワーク上の情報処理装置６が伝送信号により、一旦外部記憶装置６５にダウンロードされてからメモリ６２にロードされてもよいし、あるいは、直接、ネットワーク経由でメモリ６２にロードされてもよい。
【０２２２】
［鍵生成処理］
図９は、本実施形態に係る鍵生成処理の手順を示すフローチャートである。鍵の生成はＩＤベース暗号システム２全体で用いる公開パラメータおよびマスタ鍵を生成する公開パラメータおよびマスタ鍵生成処理と利用者の秘密鍵を生成する秘密鍵生成処理と、から構成される。
【０２２３】
図８を参照しつつ、鍵生成処理の概略を記述すると、入出力部３１１により、鍵発行装置３が、入力情報として、公開パラメータおよびマスタ鍵生成処理を行うか、または秘密鍵生成処理を行うかの処理選択情報と、公開パラメータおよびマスタ鍵生成処理であればセキュリティパラメータ３２２である正整数Ｌ、秘密鍵生成処理であれば、公開鍵である任意の文字列を入力情報として受け付けると、制御演算部３１０は受け付けた入力情報を記憶部３２０に格納する。
そして、制御演算部３１０が、記憶部３２０に保持されている入力情報を参照し、選択された処理が公開パラメータおよびマスタ鍵生成処理であれば図１０の処理に従って公開パラメータ３２３およびマスタ鍵３２４を生成する。そして、制御演算部３１０は公開パラメータ３２３およびマスタ鍵３２４を記憶部３２０に格納とするとともに公開パラメータのみ入出力部３１１より出力情報として出力し動作を終了する。制御演算部３１０は、秘密鍵生成処理であれば図１１の処理に従って秘密鍵３２６を生成し、制御演算部３１０は生成した秘密鍵３２６を記憶部３２０に格納とするとともに入出力部３１１より出力情報として出力し動作を終了する。
まず、図８を参照しつつ、図９に沿って、鍵発行装置３における全体処理を説明する。
【０２２４】
ステップＳ５０１において、制御演算部３１０による制御の元、入出力部３１１が処理の選択を受け付ける。公開パラメータおよびマスタ鍵生成処理が選択された場合、制御演算部３１０はセキュリティパラメータ３２２である正整数Ｌの入力を受け付けるとともにＬを必要に応じて記憶部３２０に格納後、ステップＳ５０２に進む。秘密鍵生成処理が選択された場合、制御演算部３１０は利用者の公開鍵である任意の文字列ＩＤの入力を受け付けるとともに、このＩＤを必要に応じて記憶部３２０に格納後、ステップＳ５０３に進む。
ステップＳ５０２において、制御演算部３１０は公開パラメータおよびマスタ鍵生成処理を行った後、処理を終了する。ステップＳ５０２の処理については、図１０を用いて後述する。
ステップＳ５０３において、制御演算部３１０は秘密鍵生成処理を行った後、処理を終了する。ステップＳ５０３の処理については、図１１を用いて後述する。
なお、以降の処理において、｛０，１｝＊はすべてのバイナリ系列を表し、｛０，１｝ＮはすべてのＮビットバイナリ系列を表し、ＸＯＲは排他的論理和を表す。
【０２２５】
以下、図８を参照しつつ、図１０に沿って、ステップＳ５０２における公開パラメータおよびマスタ鍵生成処理を説明する。
ステップＳ６０１において、群選択部３１３が、Ｌビットの素数ｎを選択し、ｎがｑｋ−１を割り切りかつ最小の整数ｋが偶数となる、偶数ｋおよび  ２以外の素数のべきｑを選択し、楕円曲線の定義体をＦｑ、位数ｎの部分群を最大位数の部分群として持つＴｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線Ｅ（Ｆｑ）：ａｘ２＋ｙ２＝１＋ｄｘ２ｙ２（ａｄ（ａ−ｄ）≠０かつＦｑ上で係数ａは２乗根を持ち係数ｄは持たない）を選択し、位数ｎの部分群をＧ１とすることによって群Ｇ１を選択する。
【０２２６】
ステップＳ６０２において、群選択部３１３が、位数のｎの群Ｇ２をＥ（Ｆｑ１）／ｎＥ（Ｆｑ１）（ｑ１＝ｑｋ）とすることによって群Ｇ２を選択する。
ステップＳ６０３において、群選択部３１３が、Ｇ３をＦ＊ｑ１（ｑ１＝ｑｋ）の位数ｎの乗法に関する部分群Ｇとし、ペアリングe：Ｇ１×Ｇ２→Ｇ３を選択する。
【０２２７】
ステップＳ６０４において、群選択部３１３が、Ｇ１の生成元Ｐを選択する。
ステップＳ６０５において、乱数生成部３１４が、０＜ｓ＜ｎを満たす整数ｓをランダムに生成し、マスタ鍵３２４とするとともに記憶部３２０に格納する。
ステップＳ６０６において、楕円曲線スカラ倍演算部３１５が、Ｐｐｕｂ←ｓＰを計算し、計算結果をＺ＝１の拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標（Ｘ：Ｙ：Ｔ：１）を用いて表現する。この処理は、特許文献１〜３に記載の技術や、特願２００９−１１９２５６に記載の技術などを用いて計算される。
【０２２８】
ステップＳ６０７において、ハッシュ関数選択部３１６が、ハッシュ関数Ｈ１：｛０，１｝＊→Ｇ２を選択する。なおＧ２の元は、（αｘ０，ｙ０）（ｘ０，ｙ０∈Ｆｑ２）（ｑ２＝ｑｋ／２）で表現されているものとする。
【０２２９】
ステップＳ６０８において、ハッシュ関数選択部３１６が、予め設定されている整数Ｎに対して、ハッシュ関数Ｈ２：Ｇ３→｛０，１｝Ｎを選択する。
ステップＳ６０９において、公開パラメータｐａｒａｍｓ＝＜ｎ，Ｇ１，Ｇ２，Ｇ３，ｅ，Ｎ，Ｐ，Ｐｐｕｂ，Ｈ１，Ｈ２＞を出力するとともに記憶部３２０に格納する。
【０２３０】
以下、図８を参照しつつ、図１１に沿って、ステップＳ５０３における秘密鍵生成処理を説明する。なお、この処理では公開パラメータおよびマスタ鍵生成処理Ｓ５０２において生成され、記憶部３２０に格納されている公開パラメータ３２３（ｐａｒａｍｓ）およびマスタ鍵３２４（ｓ）を用いるものとする。
【０２３１】
ステップＳ７０１において、ハッシュ関数演算部３１７が、公開パラメータ３２３（ｐａｒａｍｓ）に含まれているハッシュ関数Ｈ１を使用して、ハッシュ値ＱＩＤ←Ｈ１（ＩＤ）を計算する。
ステップＳ７０２において、楕円曲線スカラ倍演算部３１５が、マスタ鍵ｓを用いてｄＩＤ←ｓＱＩＤを計算し、計算結果である（αｘ０,ｙ０）を利用者の秘密鍵３２６とする。この処理は、特許文献１〜３に記載の技術や、特願２００９−１１９２５６に記載の技術などを用いて計算される。
【０２３２】
《暗号化》
次に、本実施形態に係る楕円曲線ペアリング演算方法を利用した暗号化処理について図１２および図１３を参照して説明する。
【０２３３】
［暗号化装置］
図１２は、本実施形態に係る暗号化装置の構成例を示す図である。
暗号化装置４は、制御演算部４１０および記憶部４２０を有している。
制御演算部４１０は、入出力部４１１、制御部４１２、乱数生成部４１３、楕円曲線ペアリング演算部４１４、ハッシュ関数演算部４１５を有している。入出力部４１１は、公開パラメータ４２２、利用者Ｂの公開鍵、暗号化対象データ４２４を入力情報として受け付けるとともに、生成した暗号化データ４２５を出力情報として出力する機能を有している。制御部４１２は、暗号化装置４を制御する機能を有している。乱数生成部４１３は、乱数を生成する機能を有する。楕円曲線ペアリング演算部４１４は、ペアリングを計算する機能に加えて楕円曲線上の点のスカラ倍、定義体上の演算、剰余演算（ｍｏｄ）、比較などを行う機能を有し、図１の楕円曲線ペアリング演算部１１３に相当するものである。ハッシュ関数演算部４１５は、ハッシュ関数を用いてハッシュ値を生成する機能を有する。
【０２３４】
記憶部４２０には、中間データ４２１、公開パラメータ４２２、利用者Ｂ公開鍵４２３、暗号化対象データ４２４、暗号化データ４２５などが格納されている。中間データ４２１は、制御演算部４１０における演算時の中間データである。公開パラメータ４２２は、鍵発行装置３で生成された公開パラメータのデータである。利用者Ｂ公開鍵４２３は、入出力部４１１により入力を受け付けた暗号化データ４２５の受信する利用者Ｂの公開鍵である。暗号化対象データ４２４は、入出力部４１１により入力を受け付けた暗号化の対象データである。暗号化データ４２５は、制御演算部４１０で暗号化対象データ４２４を暗号化することにより生成されるデータである。
【０２３５】
なお、暗号化装置４は、図１６に示すような、バス６７で接続されたＣＰＵ６１と、ＲＡＭなどのメモリ６２と、ＨＤＤやその他の外部記憶装置６５と、キーボードなどの入力装置６３と、ディスプレイなどの出力装置６４と、外部記憶装置６５や、入力装置６３や、出力装置６４と、バス６７を中継するインタフェース６６とを備えた、一般的な構成を有する情報処理装置６上に構築することができる。
暗号化装置４の制御演算部４１０および各部４１１〜４１５は、ＣＰＵ６１が、メモリ６２にロードされたプログラム（コードモジュールともいう）を実行することで、情報処理装置６上に具現化されるプロセスとして実現される。また、メモリ６２や、外部記憶装置６５が図１２の記憶部４２０として使用される。
【０２３６】
また、前記したプログラムは、予め外部記憶装置６５に記憶され、必要に応じてメモリ６２上にロードされ、ＣＰＵ６１により実行される。なお、このプログラムは、可搬性の記憶媒体、例えばＣＤ−ＲＯＭなどに格納され、必要に応じて、これら可搬性の記憶媒体からメモリ６２にロードされてもよい。また、プログラムは、一旦、ＣＤ−ＲＯＭなどの可搬性の記憶媒体からＨＤＤなどの外部記憶装置６５にインストールされた後、必要に応じて、この外部記憶装置６５からメモリ６２にロードされてもよい。さらに、プログラムは、図示していないネットワーク接続装置を介して、ネットワーク上の情報処理装置６が読み取り可能な媒体の一種である伝送信号により、一旦外部記憶装置６５にダウンロードされてからメモリ６２にロードされてもよいし、あるいは、直接、ネットワーク経由でメモリ６２にロードされてもよい。
【０２３７】
［暗号化処理］
図１３は、本実施形態に係る暗号化処理の手順を示すフローチャートである。
図１２を参照しつつ、暗号化処理の概略を記述すると、入出力部４１１により、暗号化装置４が、入力情報として、公開パラメータ４２２（ｐａｒａｍｓ）、暗号データの受信者である利用者Ｂの公開鍵４２３（ＩＤ）を鍵発行装置３から取得し、暗号化対象データ４２４を入力情報として受け付けると、制御演算部４１０は受け付けた各入力情報を記憶部４２０に格納する。
そして、制御演算部４１０が、記憶部４２０に保持されている入力情報を用いて、図１３の処理に従って暗号化処理を行う。
制御演算部４１０は、生成された暗号化データを、記憶部４２０に保持するとともに、入出力部４１１より出力情報として出力し、動作を終了する。
【０２３８】
以下、図１２を参照しつつ、図１３に沿って暗号化処理を説明する。
ステップＳ８０１において、ハッシュ関数演算部４１５が、公開パラメータ４２２に含まれているハッシュ関数Ｈ１を用いて、ハッシュ値ＱＩＤ←Ｈ１（ＩＤ）を計算する。
ステップＳ８０２において、乱数生成部４１３が、公開パラメータ４２２に含まれている値ｎを用いて、０＜ｒ＜ｎを満たす整数ｒをランダムに生成する。
ステップＳ８０３において、楕円曲線ペアリング演算部４１４が、公開パラメータ４２２に含まれているＰと、ステップＳ８０２で生成した整数ｒを用いて、Ｃ１←ｒＰを計算し、計算結果をＺ＝１の拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標（Ｘ：Ｙ：Ｔ：１）を用いて表現する。この処理は、スカラ倍演算処理であり、特許文献１〜３に記載の技術や、特願２００９−１１９２５６に記載の技術を用いて行われるものである。
ステップＳ８０４において、楕円曲線ペアリング演算部４１４が、公開パラメータ４２２に含まれているｅと、Ｐｐｕｂと、ステップＳ８０１で生成したＱＩＤを用いて、ｇ←ｅ（Ｐｐｕｂ，ＱＩＤ）を計算する。この処理は、図１〜図６を参照して説明した処理を用いる。
ステップＳ８０５において、楕円曲線ペアリング演算部４１４が、ｇｒ←ｇｒを計算する。
ステップＳ８０６において、ハッシュ関数演算部４１５が、公開パラメータ４２２に含まれているハッシュ関数Ｈ２を用いて、ハッシュ値ｈ←Ｈ２（ｇｒ）を計算する。
ステップＳ８０７において、楕円曲線ペアリング演算部４１４が、Ｃ２←Ｗ  ＸＯＲ  ｈを計算する。ここで、Ｗは暗号化対象データ４２４である。
ステップＳ８０８において、制御演算部４１０が、算出した（Ｃ１，Ｃ２）を暗号化データ４２５として出力するとともに、記憶部４２０に格納する。
【０２３９】
《復号化処理》
次に、本実施形態に係る楕円曲線ペアリング演算方法を利用した復号化処理について図１４および図１５を参照して説明する。
【０２４０】
［復号化装置］
図１４は、本実施形態に係る復号化装置の構成例を示す図である。
復号化装置５は、制御演算部５１０および記憶部５２０を有している。
制御演算部５１０は、入出力部５１１、制御部５１２、楕円曲線ペアリング演算部５１３、ハッシュ関数演算部５１４を有している。入出力部５１１は、公開パラメータ５２２、利用者Ｂの秘密鍵５２３、暗号化データ５２４を入力情報として受け付けるとともに、復号データ５２５を出力情報として出力する機能を有している。制御部５１２は、復号化装置５を制御する機能を有している。楕円曲線ペアリング演算部５１３は、ペアリングを計算する機能に加えて楕円曲線上の点のスカラ倍、定義体上の演算、剰余演算（ｍｏｄ）、比較などを行う機能を有し、図１の楕円曲線ペアリング演算部１１３に相当するものである。ハッシュ関数演算部５１４は、ハッシュ関数を用いてハッシュ値を生成する機能を有する。
【０２４１】
記憶部５２０には、中間データ５２１、公開パラメータ５２２、利用者Ｂ秘密鍵５２３、暗号化データ５２４、復号データ５２５などが格納されている。中間データ５２１は、制御演算部５１０における演算時の中間データである。公開パラメータ５２２は、鍵発行装置３で生成された公開パラメータのデータである。利用者Ｂ秘密鍵５２３は、鍵発行装置３から受け付けた暗号化データの復号者である利用者Ｂ秘密鍵のデータである。暗号化データ５２４は、暗号化装置４から送られた復号の対象データである。復号データ５２５は、制御演算部５１０で暗号化データ５２４を復号することにより生成されるデータである。
【０２４２】
なお、復号化装置５は、図１６に示すような、バス６７で接続されたＣＰＵ６１と、ＲＡＭなどのメモリ６２と、ＨＤＤやその他の外部記憶装置６５と、キーボードなどの入力装置６３と、ディスプレイなどの出力装置６４と、外部記憶装置６５や、入力装置６３や、出力装置６４と、バス６７を中継するインタフェース６６とを備えた、一般的な構成を有する情報処理装置６上に構築することができる。
復号化装置５の制御演算部５１０および各部５１１〜５１４は、ＣＰＵ６１が、メモリ６２にロードされたプログラム（コードモジュールともいう）を実行することで、情報処理装置６上に具現化される。また、メモリ６２や、外部記憶装置６５が図１４の記憶部５２０として使用される。
【０２４３】
また、前記したプログラムは、予め外部記憶装置６５に記憶され、必要に応じてメモリ６２上にロードされ、ＣＰＵ６１により実行される。なお、このプログラムは、可搬性の記憶媒体、例えばＣＤ−ＲＯＭなどに格納され、必要に応じて、これら可搬性の記憶媒体からメモリ６２にロードされてもよいし、一旦、ＣＤ−ＲＯＭなどの可搬性の記憶媒体からＨＤＤなどの外部記憶装置６５にインストールされた後、必要に応じて、この外部記憶装置６５からメモリ６２にロードされてもよいし、さらには、図示していないネットワーク接続装置を介して、ネットワーク上の情報処理装置６が伝送信号により、一旦外部記憶装置６５にダウンロードされてからメモリ６２にロードされてもよいし、あるいは、直接、ネットワーク経由でメモリ６２にロードされてもよい。
【０２４４】
［復号化処理］
図１５は、本実施形態に係る復号化処理の手順を示すフローチャートである。
図１４を参照しつつ、図１５に沿って復号化処理の概略を記述すると、入出力部５１１により、復号化装置５が、公開パラメータ５２２（ｐａｒａｍｓ）、復号者である利用者Ｂの秘密鍵５２３（ｄＩＤ）を鍵発行装置３から取得し、暗号化データ５２４（Ｃ＝（Ｃ１，Ｃ２））を暗号化装置４から受け付けると、制御演算部５１０は受け付けた各入力情報を記憶部５２０に格納する。
そして、制御演算部５１０が、記憶部５２０に保持されている各入力情報を用いて、図１５の処理に従って復号化処理を行う。
制御演算部５１０は、復号化処理によって生成した復号データ５２５を、記憶部５２０に保持するとともに、入出力部５１１より出力情報として出力し、動作を終了する。
【０２４５】
以下、図１４を参照しつつ、図１５に沿って、復号化処理を説明する。
ステップＳ９０１において、楕円曲線ペアリング演算部５１３が、公開パラメータ５２２に含まれるｅと、秘密鍵５２３（ｄＩＤ）と、暗号化データ５２４に含まれるｄＩＤを用いて、ｇ←ｅ（Ｃ１，ｄＩＤ）を計算する。この処理は、図１〜図６を参照して説明した処理を使用することによって行なわれる。
ステップＳ９０２において、ハッシュ関数演算部５１４が、公開パラメータ５２２に含まれるハッシュ関数Ｈ２を用いて、ハッシュ値ｈ←Ｈ２（ｇ）を計算する。
ステップＳ９０３において、楕円曲線ペアリング演算部５１３が、Ｗ←Ｃ２  ＸＯＲ  ｈを計算しＷを復号データ５２５とし、生成した復号データ５２５を出力するとともに、記憶部５２０に格納する。
【０２４６】
［ハードウェア構成］
図１６は、情報処理装置のハードウェア構成例を示す図である。
この情報処理装置６は、楕円曲線ペアリング演算装置１（図１）、鍵発行装置３（図８）、暗号化装置４（図１２）、復号化装置５（図１４）に相当する装置である。
情報処理装置６では、ＣＰＵ６１およびメモリ６２がバス６７を介して互いに接続されている。また、キーボードや、マウスに相当する入力装置６３、ディスプレイに相当する出力装置６４、ＨＤＤや、ＣＤ−ＲＯＭなどに相当し、プログラムや、データが格納されている外部記憶装置６５がインタフェース６６を介してバス６７に接続している。
【０２４７】
《まとめ》
本実施形態では、楕円曲線ａｘ２＋ｙ２＝１＋ｄｘ２ｙ２（ａｄ（ａ−ｄ）≠０，定義体上で係数ａは２乗根を持ち係数ｄは持たない）上の点（ｘ，ｙ）に対してｘ＝Ｚ／Ｘ、ｙ＝Ｚ／Ｙ、ＸＹＺ≠０を満たすＸ、Ｙ、Ｚ∈Ｆｑを用いて（Ｘ：Ｙ：Ｚ）と変換したＩｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標に加えて、ｘ＝Ｚ／Ｘ、ｙ＝Ｚ／Ｙ、ｘｙ＝Ｚ／Ｔ、ＸＹＴＺ≠０を満たすＸ、Ｙ、Ｔ、Ｚ∈Ｆｑを用いて（Ｘ：Ｙ：Ｔ：Ｚ）と変換した拡張Ｉｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を導入する。
つまり、拡張Ｉｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標をペアリング計算の際にループ処理で行われる２倍算処理における２倍算および２倍算に付随する多項式の計算、加算処理における加算および加算に付随する多項式計算に用いている。
このとき、加算においてａ＝−１の場合、a倍は符号の反転のみで行えるためａ＝−１の楕円曲線を採用するだけで２倍算ステップ１回あたり２回の定数倍算、加算処理１回あたり１回の定数倍算を削減できるが、加算処理においてそれに特化したアルゴリズムを用いることにより、さらに、加算処理１回あたり乗算を１回削減することができる。
【符号の説明】
【０２４８】
１      楕円曲線ペアリング演算装置
２      ＩＤベース暗号システム
３      鍵発行装置
４      暗号化装置
５      復号化装置
６      情報処理装置
１１０  制御演算部（楕円曲線ペアリング演算装置）
１１１  入出力部（楕円曲線ペアリング演算装置）
１１２  制御部（楕円曲線ペアリング演算装置）
１１３  楕円曲線ペアリング演算部（楕円曲線ペアリング演算装置）
１１４  入出力部
１１５  楕円曲線加算演算部
１１６  楕円曲線２倍算演算部
１１７  基本演算部
１２０  記憶部（楕円曲線ペアリング演算装置）
３１０  制御演算部（鍵発行装置）
３１１  入出力部（鍵発行装置）
３１２  制御部（鍵発行装置）
３１３  群選択部（鍵発行装置）
３１４  乱数生成部（鍵発行装置）
３１５  楕円曲線ペアリング演算部（鍵発行装置）
３１６  ハッシュ関数選択部（鍵発行装置）
３１７  ハッシュ関数演算部（鍵発行装置）
３２０  記憶部（鍵発行装置）
４１０  制御演算部（暗号化装置）
４１１  入出力部（暗号化装置）
４１２  制御部（暗号化装置）
４１３  乱数生成部（暗号化装置）
４１４  楕円曲線ペアリング演算部（暗号化装置）
４１５  ハッシュ関数演算部（暗号化装置）
４２０  記憶部（暗号化装置）
５１０  制御演算部（復号化装置）
５１１  入出力部（復号化装置）
５１２  制御部（復号化装置）
４１３  楕円曲線ペアリング演算部（復号化装置）
５１４  ハッシュ関数演算部（復号化装置）
５２０  記憶部（復号化装置）
【図１】
0005450240.tif 000027
【図２】
0005450240.tif 000028
【図３】
0005450240.tif 000029
【図４】
0005450240.tif 000030
【図５】
0005450240.tif 000031
【図６】
0005450240.tif 000032
【図７】
0005450240.tif 000033
【図８】
0005450240.tif 000034
【図９】
0005450240.tif 000035
【図１０】
0005450240.tif 000036
【図１１】
0005450240.tif 000037
【図１２】
0005450240.tif 000038
【図１３】
0005450240.tif 000039
【図１４】
0005450240.tif 000040
【図１５】
0005450240.tif 000041
【図１６】
0005450240.tif 000042