(57)【要約】【課題】ペアリングの演算に必要な演算量は通常の楕円演算にくらべると非常に大きいため、その演算速度が遅い。【解決手段】本発明では、有限体の性質を用いて高速化を行う。ｒを有限体ＧＦ（ｐｋ／２）上の元、ｆをMillerのアルゴリズムで求められる有限体ＧＦ（ｐｋ）上の元とすると、ｆ’＝ｒｆを満足する有限体ＧＦ（ｐｋ）上の元ｆ’へ写像するMillerアルゴリズムよりも計算量が少ないアルゴリズム用いて計算する。逆元を求める代わりに、乗算する元のｐｋ乗を求める。また、積算では、積算する元のｋ個の有限体ＧＦ（ｐ）上の元の少なくとも１つの値が０となる元を乗算する。【選択図】図８
2006309068.tif 000002
【特許請求の範囲】
【請求項１】
ｐは素数または素数のべき乗、ｋは偶数であって、有限体ＧＦ（ｐ）上の楕円曲線上の点Ｐと有限体ＧＦ（ｐｋ）上の楕円曲線上の点Ｑを入力とし、入力された点から有限体ＧＦ（ｐｋ）上の元を求め、求めた有限体上の元を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）に写像し、出力するペアリング演算装置において、
ＰとＱから有限体上の元ｆを求めるMillerアルゴリズムを、Millerアルゴリズム内で用いる有限体ＧＦ（ｐｋ）上の元Ｌの逆元の代わりに
【数１】
2006309068.tif 000008
を用いるアルゴリズムに変更して、ＰとＱから有限体ＧＦ（ｐｋ）上の元ｆ’を求める擬似Miller演算部と、
前記擬似Miller演算部で求めた元ｆ’を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）にべき乗演算により写像するべき乗演算部と、
を備えるペアリング演算装置。
【請求項２】
ｐは素数または素数のべき乗、ｋは偶数であって、有限体ＧＦ（ｐ）上の楕円曲線上の点Ｐと有限体ＧＦ（ｐｋ）上の楕円曲線上の点Ｑを入力とし、入力された点から有限体ＧＦ（ｐｋ）上の元を求め、求めた有限体上の元を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）に写像し、出力するペアリング演算装置において、
ｒを有限体ＧＦ（ｐｋ／２）上の元とする場合に、
ＰとＱから有限体上の元ｆを求めるMillerアルゴリズムを、Millerアルゴリズム内で用いる有限体ＧＦ（ｐｋ）上の元Ｌを積算する代わりに、
有限体ＧＦ（ｐｋ）の元Ｌ’を、Ｌ’を表現するｋ個の有限体ＧＦ（ｐ）上の元の少なくとも１つの値が０  かつ  Ｌ’＝ｒＬ
を満足する元から選定し、Ｌ’を積算するアルゴリズムに変更して、ＰとＱから有限体ＧＦ（ｐｋ）上の元ｆ’を求める擬似Miller演算部と、
前記擬似Miller演算部で求めた元ｆ’を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）にべき乗演算により写像するべき乗演算部と、
を備えるペアリング演算装置。
【請求項３】
ｐは素数または素数のべき乗、ｋは偶数であって、有限体ＧＦ（ｐ）上の楕円曲線上の点Ｐと有限体ＧＦ（ｐｋ）上の楕円曲線上の点Ｑを入力とし、入力された点から有限体ＧＦ（ｐｋ）上の元を求め、求めた有限体上の元を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）に写像し、出力するペアリング演算装置において、
ｒを有限体ＧＦ（ｐｋ／２）上の元とする場合に、
ＰとＱから有限体ＧＦ（ｐｋ）上の元ｆを求めるMillerアルゴリズムを、Millerアルゴリズム内で用いる有限体ＧＦ（ｐｋ）上の元Ｌの逆元の代わりに
【数２】
2006309068.tif 000009
を用いること、
Millerアルゴリズム内で用いる有限体ＧＦ（ｐｋ）上の元Ｌを積算する代わりに、
有限体ＧＦ（ｐｋ）の元Ｌ’を、Ｌ’を表現するｋ個の有限体ＧＦ（ｐ）上の元の少なくとも１つの値が０  かつ  Ｌ’＝ｒＬ
を満足する元から選定し、Ｌ’を積算するアルゴリズムに変更して、有限体ＧＦ（ｐｋ）上の元ｆ’を求めることを特徴とする擬似Miller演算部と、
前記擬似Miller演算部で求めた元ｆ’を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）にべき乗演算により写像するべき乗演算部と、
を備えるペアリング演算装置。
【請求項４】
請求項２または３記載のペアリング演算装置において、
ａとｂが整数、有限体ＧＦ（ｐｋ）の元Ｘが有限体ＧＦ（ｐｋ/2）の２つの元Ｘ０とＸ１とを用いて表されており、有限体ＧＦ（ｐｋ）上の元ＬがＬ＝ａＸ＋ｂと表現できる場合に、
Ｌ’＝Ｘ１−１Ｌとする擬似Miller演算部
を備えるペアリング演算装置。
【請求項５】
請求項１、３または４のいずれかに記載のペアリング演算装置において、
有限体ＧＦ（ｐｋ）の元Ｓが正規基底を用いて有限体ＧＦ（ｐｋ/2）の２つの元Ｓ０とＳ１とで表される場合に、
Ｓ０とＳ１とを置き換えることで擬似逆元を求める擬似Miller演算部
を備えるペアリング演算装置。
【請求項６】
請求項１、３または４のいずれかに記載のペアリング演算装置において、
有限体ＧＦ（ｐｋ）の元Ｓが、多項式基底を用いて有限体ＧＦ（ｐｋ/2）の２つの元Ｓ０、Ｓ１、および最小多項式ｆ（ｘ）＝ｘ２＋ｕ１ｘ＋ｕ０で表される場合に、
Ｓ０−ｕ１Ｓ１と−Ｓ１とを合成することで擬似逆元を求める擬似Miller演算部
を備えるペアリング演算装置。
【請求項７】
ｐは素数または素数のべき乗、ｋは偶数であって、有限体ＧＦ（ｐ）上の楕円曲線上の点Ｐと有限体ＧＦ（ｐｋ）上の楕円曲線上の点Ｑを入力とし、入力された点から有限体ＧＦ（ｐｋ）上の元を求め、求めた有限体上の元を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）に写像し、出力するペアリング演算方法において、
擬似Miller演算部で、ＰとＱから有限体上の元ｆを求めるMillerアルゴリズムを、Millerアルゴリズム内で用いる有限体ＧＦ（ｐｋ）上の元Ｌの逆元の代わりに
【数３】
2006309068.tif 000010
を用いるアルゴリズムに変更して、ＰとＱから有限体ＧＦ（ｐｋ）上の元ｆ’を求め、
べき乗演算部で、前記擬似Miller演算部で求めた元ｆ’を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）にべき乗演算により写像する
ことを特徴とするペアリング演算方法。
【請求項８】
ｐは素数または素数のべき乗、ｋは偶数であって、有限体ＧＦ（ｐ）上の楕円曲線上の点Ｐと有限体ＧＦ（ｐｋ）上の楕円曲線上の点Ｑを入力とし、入力された点から有限体ＧＦ（ｐｋ）上の元を求め、求めた有限体上の元を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）に写像し、出力するペアリング演算方法において、
ｒを有限体ＧＦ（ｐｋ／２）上の元とする場合に、
擬似Miller演算部で、ＰとＱから有限体上の元ｆを求めるMillerアルゴリズムを、Millerアルゴリズム内で用いる有限体ＧＦ（ｐｋ）上の元Ｌを積算する代わりに、
有限体ＧＦ（ｐｋ）の元Ｌ’を、Ｌ’を表現するｋ個の有限体ＧＦ（ｐ）上の元の少なくとも１つの値が０  かつ  Ｌ’＝ｒＬ
を満足する元から選定し、Ｌ’を積算するアルゴリズムに変更して、ＰとＱから有限体ＧＦ（ｐｋ）上の元ｆ’を求め、
べき乗演算部で、前記擬似Miller演算部で求めた元ｆ’を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）にべき乗演算により写像する
ことを特徴とするペアリング演算方法。
【請求項９】
ｐは素数または素数のべき乗、ｋは偶数であって、有限体ＧＦ（ｐ）上の楕円曲線上の点Ｐと有限体ＧＦ（ｐｋ）上の楕円曲線上の点Ｑを入力とし、入力された点から有限体ＧＦ（ｐｋ）上の元を求め、求めた有限体上の元を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）に写像し、出力するペアリング演算方法において、
ｒを有限体ＧＦ（ｐｋ／２）上の元とする場合に、
擬似Miller演算部で、ＰとＱから有限体ＧＦ（ｐｋ）上の元ｆを求めるMillerアルゴリズムを、Millerアルゴリズム内で用いる有限体ＧＦ（ｐｋ）上の元Ｌの逆元の代わりに
【数４】
2006309068.tif 000011
を用いる過程と、
Millerアルゴリズム内で用いる有限体ＧＦ（ｐｋ）上の元Ｌを積算する代わりに、
有限体ＧＦ（ｐｋ）の元Ｌ’を、Ｌ’を表現するｋ個の有限体ＧＦ（ｐ）上の元の少なくとも１つの値が０  かつ  Ｌ’＝ｒＬ
を満足する元から選定し、Ｌ’を積算するアルゴリズムに変更して、有限体ＧＦ（ｐｋ）上の元ｆ’を求める過程と、
べき乗演算部で、前記擬似Miller演算部で求めた元ｆ’を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）にべき乗演算により写像する過程と
を有することを特徴とするペアリング演算方法。
【請求項１０】
請求項８または９記載のペアリング演算方法において、
ａとｂが整数、有限体ＧＦ（ｐｋ）の元Ｘを表現するｋ個の有限体ＧＦ（ｐ）上の元を２つに分割してできる有限体ＧＦ（ｐｋ/2）の２つの元をＸ０とＸ１とし、有限体ＧＦ（ｐｋ）上の元ＬがＬ＝ａＸ＋ｂと表現できる場合に、
擬似Miller演算部で、Ｌ’＝Ｘ１−１Ｌとする
ことを特徴とするペアリング演算方法。
【請求項１１】
請求項７、９または１０のいずれかに記載のペアリング演算方法において、
有限体ＧＦ（ｐｋ）の元Ｓを表現するｋ個の有限体ＧＦ（ｐ）上の元を２つに分割してできる有限体ＧＦ（ｐｋ/2）の２つの元をＳ０とＳ１とする場合に、
擬似Miller演算部で、Ｓ０とＳ１とを置き換えることで擬似逆元を求める
ことを特徴とするペアリング演算方法。
【請求項１２】
請求項７、９または１０のいずれかに記載のペアリング演算方法において、
有限体ＧＦ（ｐｋ）の元Ｓが多項式基底であり、ｋ個の有限体ＧＦ（ｐ）上の元を２つに分割してできる有限体ＧＦ（ｐｋ/2）の２つの元をＳ０とＳ１、多項式基底ごとに定まる有限体ＧＦ（ｐｋ／２）上の元をｕ１とする場合に、
擬似Miller演算部で、Ｓ０−ｕ１Ｓ１と−Ｓ１とを合成することで擬似逆元を求める
ことを特徴とするペアリング演算方法。
【請求項１３】
請求項１から６のいずれかに記載のペアリング演算装置をコンピュータにより実現するペアリング演算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、楕円曲線上の演算、特にセキュリティ技術を実現するための演算を利用した装置、方法、およびプログラムに関する。
【背景技術】
【０００２】
楕円曲線のペアリングを用いたＩＤ−ｂａｓｅ暗号や短署名長デジタル署名を実現する方法が提案されている（特許文献１）。
Tateペアリングによる暗号や署名の概要を図１に示す。有限体ＧＦ（ｐ）上で定義される楕円をＥ／ＧＦ（ｐ）とする。楕円Ｅ／ＧＦ（ｐ）上のＧＦ（ｐ）有理点をＰ（ｘ、ｙ）、楕円Ｅ／ＧＦ（ｐ）上のＧＦ（ｐｋ）有理点をＱ（ｘＱ、ｙＱ）とする。Tateペアリングでは、ＰとＱを入力とし、Millerアルゴリズムによって有限体ＧＦ（ｐｋ）上の元ｆを出力し、さらにべき乗演算によってｆを（ｐｋ−１）／ｍ乗することで有限体ＧＦ（ｐｋ）上の元ｅへ写像し、出力する。ここで、ｐは素数または素数のべき乗、ｍは素数かつＰ、Ｑ、ｅの位数、ｋはｍ｜（ｐｋ−１）を満足する最小の整数、ｍは（ｐ−１）の約数ではない、かつｐとｍの最大公約数は１である。
【０００３】
図２はTateペアリングを用いたペアリング演算装置１０００の機能構成例を示している。図１に示した処理を行うため、Millerアルゴリズムを用いて入力ＰとＱを有限体ＧＦ（ｐｋ）上の元ｆに変換して出力するMiller演算装置３０と、べき乗演算によって入力ｆを有限体ＧＦ（ｐｋ）上の元ｅに写像して出力するべき乗演算装置２０から構成されている。
Tateペアリングで９０％の計算量を占めるMiller演算装置３０の内部構成例を図３に、処理フロー例を図４に示す。Miller演算装置３０は、制御部１００、代入部２００、楕円上点生成部４００、楕円加算部５００、入出力部６００、ＧＦ（ｐｋ）乗算部７００、ＧＦ（ｐｋ）逆元部８５０、および記録部１９０から構成される。制御部１００は、以下に示す処理フローに沿った処理を実行するために他の構成部を制御する。また、記録部１９０はハードディスク等の不揮発性のメモリでもよいし、一連の計算を行う間だけ一時的に記録する揮発性のメモリでもよい。また、組み合わせてもよい。
【０００４】
入出力部６００にｍ、Ｐ、Ｑが入力されると、ｍ、Ｐ、Ｑを記録部１９０に記録する（Ｓ７００）。次に代入部２００で、ＴにＰを、Ｆに１を代入し、記録部１９０に記録する（Ｓ７１０）。楕円上点生成部４００で、Ｓ≠ＰかつＳ≠Ｑの条件を満足する有限体ＧＦ（ｐｋ）上で定義される楕円上の点Ｓ（∈Ｅ／ＧＦ（ｐｋ））を生成し、記録部１９０に記録する（Ｓ７２０）。Ｓは条件を満足する点であれば、あらかじめ定めてもいいし、ランダムに生成してもよい。楕円加算部５００で、記録部１９０からＱとＳを読み取り、Ｑ’（＝Ｑ＋Ｓ）を計算し、記録部１９０に記録する（Ｓ７３０）。代入部２００で、ｌｏｇ（ｍ）−１の小数点以下を切り上げた整数をｎに代入し、記録部１９０に記録する（Ｓ７４０）。制御部１００は、記録部１９０からｎを読み取り、ｎ＜０か否かを確認し、Ｙｅｓの場合にはステップＳ９１０に進み、Ｎｏの場合にはステップＳ７６０に進む（Ｓ７５０）。Ｙｅｓの場合、入出力部６００は、記録部１９０からＦを読み取り、出力し（Ｓ９１０）、Millerアルゴリズムによる演算が終了する。Ｎｏの場合、楕円加算部５００は、記録部１９０からＴを読み取り、２Ｔを計算し、記録部１９０に記録する（Ｓ７６０）。ＧＦ（ｐｋ）乗算部７００は、Ｑ’、Ｓ、Ｔ、２Ｔを記録部１９０から読み取り、ｌ１（ｘ，ｙ）＝０をＴと２Ｔとを結ぶ直線、ｌ２（ｘ，ｙ）＝０を２ＴとＯとを結ぶ直線として、ｌ１（Ｑ’）、ｌ２（Ｑ’）、ｌ１（Ｓ）、ｌ２（Ｓ）を計算し、記録部１９０に記録する（Ｓ７７０）。ただし、ｌ１（Ｑ’）とは、Ｑ’のｘ座標とｙ座標とを、ｌ１（ｘ，ｙ）に代入した値である。なお、Ｓを有限体ＧＦ（ｐ）の元から選定すると（この場合、残りのｋ−１個の有限体ＧＦ（ｐ）の元は０である。）、ｌ１（Ｓ）、ｌ２（Ｓ）の計算は省略でき、以降のステップでｌ１（Ｓ）、ｌ２（Ｓ）を省略できる。次に、代入部２００は、記録部１９０から２Ｔを読み取り、Ｔに２Ｔの値を代入し、Ｔを記録部１９０に記録する（Ｓ７８０）。ＧＦ（ｐｋ）逆元部８５０で、記録部１９０からｌ２（Ｑ’）、ｌ１（Ｓ）を読み取り、ｌ２（Ｑ’）−１、ｌ１（Ｓ）−１を計算し、記録部１９０に記録する（Ｓ７９０）。ＧＦ（ｐｋ）乗算部７００は、記録部１９０からＦ、ｌ１（Ｑ’）、ｌ２（Ｓ）、ｌ２（Ｑ’）−１、ｌ１（Ｓ）−１を読み取り、
【０００５】
【数５】
2006309068.tif 000003
を計算し、Ｆの値として記録部１９０に記録する（Ｓ８１０）。制御部１００は、記録部１９０からｍとｎを読み取り、ｍのｎ番目のビットが１かを確認し、Ｙｅｓの場合にはステップＳ８３０へ進み、Ｎｏの場合にはステップＳ９００へ進む（Ｓ８２０）。Ｙｅｓの場合、楕円加算部５００で、記録部１９０からＴ、Ｐを読み取り、Ｔ＋Ｐを計算し、記録部１９０に記録する（Ｓ８３０）。ＧＦ（ｐｋ）乗算部７００は、Ｑ’、Ｓ、Ｔ、Ｐ，Ｔ＋Ｐを記録部１９０から読み取り、ｌ１（ｘ，ｙ）＝０をＴとＰとを結ぶ直線、ｌ２（ｘ，ｙ）＝０をＴ＋ＰとＯとを結ぶ直線とし、ｌ１（Ｑ’）、ｌ２（Ｑ’）、ｌ１（Ｓ）、ｌ２（Ｓ）を計算して、記録部１９０に記録する（Ｓ８４０）。代入部２００は、記録部１９０からＴ＋Ｐを読み取り、ＴにＴ＋Ｐを代入し、Ｔを記録部１９０に記録する（Ｓ８５０）。ＧＦ（ｐｋ）逆元部８５０は、記録部１９０からｌ２（Ｑ’）、ｌ１（Ｓ）を読み取り、ｌ２（Ｑ’）−１、ｌ１（Ｓ）−１を計算し、記録部１９０に記録する（Ｓ８６０）。ＧＦ（ｐｋ）乗算部７００は、記録部１９０からＦ、ｌ１（Ｑ’）、ｌ２（Ｓ）、ｌ２（Ｑ’）−１、ｌ１（Ｓ）−１を読み取り、
【０００６】
【数６】
2006309068.tif 000004
を計算し、Ｆの値として記録部１９０に記録する（Ｓ８９０）。ステップＳ８２０でＮｏと判断した場合とステップＳ８９０が終了した場合、代入部２００は、記録部１９０からｎを読み取り、ｎ−１をｎに代入し、ｎを記録部１９０に記録する（Ｓ９００）。次にステップＳ７５０に戻り、ステップＳ７５０の判断がＹｅｓとなるまで処理が繰り返される。
【特許文献１】特開2004-177673号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ペアリングの演算に必要な演算量は通常の楕円演算にくらべると非常に大きいため、その演算速度が遅いことが問題になっている。Tateペアリングを実現する場合、その処理時間のほとんどは上記のようにMillerのアルゴリズムであり、特許文献１でもMillerのアルゴリズムの高速化の検討が行われている。これらの高速化の方法は、超特異曲線という特殊な曲線の場合の高速演算法など、楕円曲線の性質に着眼して高速化を行っているものが多かった。
本発明が解決しようとする課題も、ペアリングの演算速度の高速化である。
【課題を解決するための手段】
【０００８】
本発明では、有限体の性質を用いて高速化を行う。図５に本発明による演算の高速化の原理を示す。Tateペアリングでは、有限体ＧＦ（ｐｋ）上の元ｆをべき乗演算により有限体ＧＦ（ｐｋ）上の元ｅに写像するが、次の条件を満足する有限体ＧＦ（ｐｋ）上の元ｆ’も、べき乗演算により有限体ＧＦ（ｐｋ）上の元ｅに写像する。
ｆ’＝ｒｆ  ただし、ｒは有限体ＧＦ（ｐｋ／２）上の元                （１）
そこで、本発明ではｋが偶数の場合に、この有限体の性質を利用し、Millerアルゴリズムよりも計算量が少ないアルゴリズム（以下、「擬似Millerアルゴリズム」という。）で、元ｆ’を求め、元ｆ’をべき乗演算することで元ｅを求める。
【０００９】
擬似Millerアルゴリズムでは、Millerアルゴリズムで逆元を求める処理を、少ない計算量で求められる逆元のｒ倍の元（以下、「擬似逆元」という。）を求める処理に置き換える。具体的には、ｋが偶数であり、Ｌが有限体ＧＦ（ｐｋ）上の元の場合、
【００１０】
【数７】
2006309068.tif 000005
を擬似逆元として使用する。
ここで、正規基底表現の場合には、Ｌのｐｋ／２乗は、Ｌを２つの有限体ＧＦ（ｐｋ／２）上の元Ｌ０とＬ１に分割し、Ｌ０とＬ１とを入れ替えることで実現できる。また、多項式基底表現の場合には、Ｌ（∈ＧＦ（ｐｋ））のｐｋ／２乗は、Ｌを２つの有限体ＧＦ（ｐｋ／２）上の元Ｌ０とＬ１に分割し、Ｌ０−ｕ１Ｌ１と−Ｌ１とを合成することで実現できる。ここで、ｕ１（∈ＧＦ（ｐｋ／２））は最小多項式の係数として定まる定数であり、通常０や±１などの小さい数を用いることが多い。
【００１１】
ｌ２（ｘ，ｙ）（∈ＧＦ（ｐｋ））は、ｋ個の有限体ＧＦ（ｐ）上の元を並べて表現されるが、Millerアルゴリズムで、ｌ２（ｘ，ｙ）を乗算する代わりに、ｋ個の有限体ＧＦ（ｐ）上の元の中に０である元を含むｌ２（ｘ，ｙ）のｒ倍の有限体ＧＦ（ｐｋ）上の元を乗算すれば、値が０の有限体ＧＦ（ｐ）上の元の乗算は０であることは明確なため、省略できる。そこで図６に示す方法により、値が０である有限体ＧＦ（ｐ）上の元を含むｌ２（ｘ，ｙ）のｒ倍の元を求める。ｌ２（ｘ，ｙ）は、
Ｌ＝ａＸ＋ｂ                                                        （４）
と表現できる。たとえばＸを有限体ＧＦ（ｐ６）上の元として、元Ｘを図６のように２つの有限体ＧＦ（ｐ３）上の元Ｘ１とＸ０とに分割し、式（４）の両辺に、有限体ＧＦ（ｐ３）上の元ｃ（＝Ｘ１−１）を掛ける。Ｌ’＝ｃＬとすると、Ｌ’は図６に示すように値が０の有限体ＧＦ（ｐ）上の元を２つ含んだ元であり、かつ式（１）を満足する。したがって、ｌ２（ｘ，ｙ）を乗算する代わりに、ｃｌ２（ｘ，ｙ）を乗算すれば（以下、「擬似乗算」という。）、べき乗演算による写像は同じ点となるが、計算量を少なくできる。
【００１２】
次に、Ｌ’の擬似逆元を求める場合を示す。擬似逆元を求めるときは、上記のようにＬ’を２つの有限体ＧＦ（ｐｋ／２）上の元Ｌ０’とＬ１’に分割するが、正規基底の場合も多項式基底の場合も、Ｌ１’に値が０の有限体ＧＦ（ｐ）上の元が含まれていれば、Ｌ１’の擬似逆元にも値が０の有限体ＧＦ（ｐ）上の元がそのまま含まれることになる。したがって、Ｌの割り算を行う場合にも、Ｌ’を求め、Ｌ’の擬似逆元を求めた上で、乗算することで、計算量を削減できる。
【発明の効果】
【００１３】
本発明によれば、楕円曲線上のTateペアリング演算において、ｋが偶数である場合に、有限体の性質を用いて、Ｅ／ＧＦ（ｐｋ）からＧＦ（ｐｋ）への写像の高速化を行うことができる。また、本発明は、特殊な楕円曲線の性質を用いず高速化を行うことができる。さらに、任意の標数の楕円曲線に適用することが可能であり、応用範囲が広い。
【発明を実施するための最良の形態】
【００１４】
以下では、説明の重複を避けるため同じ機能を有する構成部や同じ処理を行う処理ステップには同一の番号を付与し、説明を省略する。
［第１実施形態］
図７に本発明のペアリング演算装置の機能構成例を示す。図２との違いはMiller演算装置３０の代わりに、擬似Miller演算装置１０が備えられていることである。擬似Miller演算装置１０は、上記の擬似逆元と擬似乗算を行うことで、擬似Millerアルゴリズムを実現する装置である。擬似Miller演算装置１０の内部構成例を図８に、擬似Miller演算装置１０の処理フローを図９に示す。図８と図３との違いは、図８の記録部１５０に記録するデータの種類が、図３の記録部１９０に記録するデータの種類と異なるものがあること、擬似逆元を計算するためにＧＦ（ｐｋ）逆元部８５０が擬似ＧＦ（ｐｋ）逆元部８００に置き換えられたこと、擬似乗算のためにｃ生成部３００と擬似ＧＦ（ｐｋ）乗算部９００が追加されたことである。まず、図４の説明中での「記録部１９０への記録」または「記録部１９０からの読み取り」は、図９では「記録部１５０への記録」または「記録部１５０からの読み取り」と読み替える。その他の図９の処理フローと図４の処理フローとの違いは、以下のとおりである。
【００１５】
ステップＳ７３０とステップＳ７４０との間に、ステップＳ１１０とＳ１２０とを追加している。ステップＳ１１０では、ｃ生成部３００が、Ｑ’のｘ座標であるＸＱ’（∈ＧＦ（ｐｋ））をＸ１とＸ０に２分割し、Ｘ１−１を計算し、ｃの値として記録部１５０に記録する。ステップＳ１２０では、Ｑ’の座標を（ＸＱ’，ＹＱ’）とすると、ＧＦ（ｐｋ）乗算部７００が、（ｃＸＱ’，ｃＹＱ’）を計算し、Ｑ”として記録部１５０に記録する。
ステップＳ７７０は、ステップＳ１３０に置き換えられる。ステップＳ１３０では、ＧＦ（ｐｋ）乗算部７００が、Ｑ”、Ｓ、Ｔ、２Ｔを記録部１５０から読み取り、ｌ１（ｘ，ｙ）＝０をＴと２Ｔとを結ぶ直線、ｌ２（ｘ，ｙ）＝０を２ＴとＯとを結ぶ直線として、ｌ１（Ｑ”）、ｌ２（Ｑ”）、ｌ１（Ｓ）、ｌ２（Ｓ）を計算し、記録部１５０に記録する。
【００１６】
ステップＳ７９０とステップＳ８１０は、ステップＳ１４０〜Ｓ１６０に置き換える。ステップＳ１４０では、擬似ＧＦ（ｐｋ）逆元部８００が、記録部１５０からｌ２（Ｑ”）、ｌ１（Ｓ）を読み取り、ｌ２（Ｑ”）の擬似逆元とｌ１（Ｓ）の擬似逆元を計算し、記録部１５０に記録する。ステップＳ１５０では、擬似ＧＦ（ｐｋ）乗算部９００が、記録部１５０からｌ１（Ｑ”）、ｌ２（Ｑ”）の擬似逆元を読み取り、
【００１７】
【数８】
2006309068.tif 000006
を計算し、Ｆの値として記録部１５０に記録する。
ステップＳ８４０は、ステップＳ１７０に置き換えられる。ステップＳ１７０では、
ＧＦ（ｐｋ）乗算部７００が、Ｑ”、Ｓ、Ｔ、Ｐ，Ｔ＋Ｐを記録部１５０から読み取り、ｌ１（ｘ，ｙ）＝０をＴとＰとを結ぶ直線、ｌ２（ｘ，ｙ）＝０をＴ＋ＰとＯとを結ぶ直線とし、ｌ１（Ｑ”）、ｌ２（Ｑ”）、ｌ１（Ｓ）、ｌ２（Ｓ）を計算して、記録部１５０に記録する。
【００１８】
ステップＳ８６０とステップＳ８８０は、ステップＳ１８０〜Ｓ２００に置き換える。ステップＳ１８０では、擬似ＧＦ（ｐｋ）逆元部８００が、記録部１５０からｌ２（Ｑ”）、ｌ１（Ｓ）を読み取り、ｌ２（Ｑ”）の擬似逆元とｌ１（Ｓ）の擬似逆元を計算し、記録部１５０に記録する。ステップＳ１９０では、擬似ＧＦ（ｐｋ）乗算部９００が、記録部１５０からｌ１（Ｑ”）、ｌ２（Ｑ”）の擬似逆元を読み取り、
【００１９】
【数９】
2006309068.tif 000007
を計算し、Ｆの値として記録部１５０に記録する。
なお、本発明でもＳを有限体ＧＦ（ｐ）の元から選定すると（この場合、残りのｋ−１個の有限体ＧＦ（ｐ）の元は０である。）、ｌ１（Ｓ）、ｌ２（Ｓ）の計算や演算を省略できる。
このように変更した処理フローによって、Millerアルゴリズムよりも計算量を少なくし、有限体ＧＦ（ｐｋ）上の元ｆ’を求めることができる。
［第２実施形態］
本実施形態では、第１実施形態の図８中に示した擬似ＧＦ（ｐｋ）逆元部８００の内部構成について示す。入力Ｓ（∈ＧＦ（ｐｋ））の擬似逆元の計算では、ｋを偶数としたことを利用して、逆元Ｓ−１を求めるのではなく、逆元Ｓ−１のｒ（∈ＧＦ（ｐｋ／２））倍であるＳのｐｋ／２乗を求めている。正規基底の場合には、入力Ｓのｐｋ／２乗は、Ｓを２つの有限体ＧＦ（ｐｋ／２）上の元Ｓ０とＳ１に分割し、Ｓ０とＳ１とを入れ替えることで実現できる。
【００２０】
図１０に正規基底の場合の擬似ＧＦ（ｐｋ）逆元部８００の機能構成例を、図１１に処理フローを示す。擬似ＧＦ（ｐｋ）逆元部８００は、分割部８１０と置換合成部８２０から構成されている。分割部８１０は、有限体ＧＦ（ｐｋ）上の元Ｓが入力されると、Ｓを２つの有限体ＧＦ（ｐｋ／２）の元Ｓ０とＳ１に分割する（Ｓ８１０）。置換合成部８２０では、分割された元Ｓ０とＳ１とを入れ替えて合成することでＳの擬似逆元を生成し（Ｓ８２０）、Ｓの擬似逆元を出力する（Ｓ８３０）。
このように元を入れ替えるだけで擬似逆元を求めることができるため、割り算と比較すると大幅な計算量の削減が期待できる。
［変形例］
第２実施形態では、正規基底の場合の擬似ＧＦ（ｐｋ）逆元部８００について示したが、本変形例では、多項式基底の場合を示す。多項式基底の場合には、入力Ｓ（∈ＧＦ（ｐｋ））のｐｋ／２乗は、Ｓを２つの有限体ＧＦ（ｐｋ／２）上の元Ｓ０とＳ１に分割し、Ｓ０−ｕ１Ｓ１と−Ｓ１とを合成することで実現できる。ここで、ｕ１（∈ＧＦ（ｐｋ／２））は多項式基底における最小多項式ｆ（ｘ）＝ｘ２＋ｕ１ｘ＋ｕ０の一次の係数であって、０や±１などの小さい値を用いることが多い。
【００２１】
多項式基底の場合の擬似ＧＦ（ｐｋ）逆元部８００’を図１２に、処理フローを図１３に示す。擬似ＧＦ（ｐｋ）逆元部８００’は、分割部８１０、記録部８６０、乗算部８７０、減算部８８０、合成部８９０から構成されている。記録部８６０にはあらかじめｕ１（∈ＧＦ（ｐｋ／２））を記録しておく。分割部８１０は、有限体ＧＦ（ｐｋ）上の元Ｓが入力されると、Ｓを２つの有限体ＧＦ（ｐｋ／２）の元Ｓ０とＳ１に分割する（Ｓ８１０）。乗算部８７０は、記録部８６０に記録されたｕ１と分割部８１０の出力であるＳ１とを掛けることで、ｕ１Ｓ１を得る（Ｓ８４０）。減算部８８０では、分割部８１０の出力であるＳ０から乗算部８７０の出力であるｕ１Ｓ１を引き、Ｓ０−ｕ１Ｓ１を得る（Ｓ８５０）。合成部８９０では、減算部８８０からの出力であるＳ０−ｕ１Ｓ１と分割部８１０の出力であるＳ１から、Ｓ０−ｕ１Ｓ１と−Ｓ１とを合成してＳの擬似逆元を求め（Ｓ８６０）、Ｓの擬似逆元を出力する（Ｓ８３０）。
【００２２】
このように元を分割と１回の乗算、減算、および合成で擬似逆元を求めることができるため、割り算と比較すると大幅な計算量の削減が期待できる。
［第３実施形態］
本実施形態では、第１実施形態の図８中に示した擬似ＧＦ（ｐｋ）乗算部９００の内部構成について示す。値が０の有限体ＧＦ（ｐ）上の元を含むようにステップＳ１１０とＳ１２０でＱ”を求めたので、ｌ２（Ｑ”）は値が０の有限体ＧＦ（ｐ）上の元を含んでおり、その数は、ｋ／２−１個である。そこで、ｌ２（Ｑ”）またはｌ２（Ｑ”）擬似逆元の乗算では、ｋ／２＋１個の有限体ＧＦ（ｐ）上の元の掛算を繰り返せばよい。
【００２３】
擬似ＧＦ（ｐｋ）乗算部９００の内部構成例を図１４に示す。乗算範囲を変更した乗算部９１０では、上記のようにｌ２（Ｑ”）またはｌ２（Ｑ”）の擬似逆元の計算範囲ｊ＝１〜ｋをｊ＝１〜１＋ｋ／２に変更し、乗算を行う。図１５に、処理フローを示す。ただし、処理フロー中に示しているαｉ＋ｊは、桁（乗算の結果を表現する複数の有限体ＧＦ（ｐ）上の元のどの元に加算するのかを示している。）
ｋ＝６での計算量の評価
有限体ＧＦ（ｐｋ）上の元の掛算の計算量をＭｋ、有限体ＧＦ（ｐ）上の元の掛算の計算量をＭとする。加算の計算量および定数倍は乗算の計算量にくらべ十分に小さいので、説明を簡単にするため、本評価では無視し、一般的に乗算の方法として知られている教科書法とKaratsuba法についてｋ＝６の場合の評価を行う。
【００２４】
一般的に教科書法では、Ｍ６＝４Ｍ３、Ｍ３＝９Ｍ、Ｍ６＝３６Ｍの関係であり、Karatsuba法では、Ｍ６＝３Ｍ３、Ｍ３＝６Ｍ、Ｍ６＝１８Ｍである。多項式基底の逐次拡大により、通常の有限体ＧＦ（ｐ６）上の元は６つの有限体ＧＦ（ｐ）上の元で表されるが、擬似乗算のｌ２（Ｑ”）は、６つの有限体ＧＦ（ｐ）上の元のうち２つが０となり、それを利用して通常の乗算よりも少ない計算量で乗算を行う。
ｌ２（Ｑ”）と有限体ＧＦ（ｐ６）上の元との擬似乗算での計算量Ｍ６’は、教科書法の場合、Ｍ６’＝２４Ｍとなる。次にKaratsuba法の場合を検討する。有限体ＧＦ（ｐ３）上の元は、有限体ＧＦ（ｐ）上の元３つで表現できるが、そのうち１つが３回の乗算で全て０となるため、それを利用して通常の乗算より少ない計算量で乗算できる。「２項多項式×３項多項式」の乗算は、教科書法では６回の単項乗算となるが、Toom-Cook法を用いると４回の単項乗算で可能である（M.Gonda, K.Matsuo, K.Aoki, J.Chao, and S.Tsujii, “Improvements of addition algorithm on genus 3 hyperelliptic curves and their implementations”, Vol.II, 3A3-1, pp.995-1000, January 2004.）。したがって、Karatsuba法とToom-Cook法とを組み合わせると、Ｍ６’＝３Ｍ３’、Ｍ３’＝４Ｍ、Ｍ６’＝１２Ｍとなる。上記のように、教科書法でもKaratsuba法でも擬似乗算を用いることで、計算量は通常の乗算の２／３となる。
【００２５】
なお、本発明のすべての実施形態は、上記の処理手順の全部または一部を、コンピュータと当該コンピュータを動作させるプログラムによっても実行することができる。また、当該プログラムはコンピュータ読み取り可能な記録媒体に記録しておき、必要に応じてコンピュータに読み取らせて実行することも可能である。
［計算量の評価］
机上評価
Millerのアルゴリズムでの楕円加算部分、楕円二倍部分の計算量をそれぞれＴＡＤＤ、ＴＤＢＬとすると、計算量は以下のようになる。Millerのアルゴリズム全体の計算量ＴＭｉｌｌｅｒは、ｎをｌｏｇ（ｍ）＋１の小数点以下を切り上げた整数として、
ＴＭｉｌｌｅｒ＝（ｎ／２）ＴＡＤＤ＋ｎＴＤＢＬ
となる。有限体ＧＦ（ｐｋ）上の元の掛算の計算量をＭｋ、自乗の計算量をＳｋ、有限体ＧＦ（ｐ）上の元の掛算の計算量をＭ、自乗の計算量をＳとすると、従来の方法（特許文献１）では、
ＴＡＤＤ＝２Ｍｋ＋（３ｋ＋１０）Ｍ＋３Ｓ
ＴＤＢＬ＝２Ｍｋ＋２Ｓｋ＋（３ｋ＋７）Ｍ＋６Ｓ
となる。ただし、有限体ＧＦ（ｐｋ）上の元ｆの分母と分子を別々に求めた場合である。
【００２６】
擬似逆元を使用した楕円加算部分ＴＡＤＤ’、楕円二倍部分の計算量ＴＤＢＬ’は、
ＴＡＤＤ’＝２Ｍｋ＋（３ｋ＋１０）Ｍ＋３Ｓ
ＴＤＢＬ’＝２Ｍｋ＋Ｓｋ＋（３ｋ＋７）Ｍ＋６Ｓ
となる。また、逆元の計算量がほぼ０となるため、有限体ＧＦ（ｐｋ）上の元ｆの分母と分子とを別々に求める必要がなくなる。これにより、余分な演算を削減できる。
擬似乗算を使用した楕円加算部分ＴＡＤＤ”、楕円二倍部分の計算量ＴＤＢＬ”は、Ｍｋの片方を擬似乗算の場合の計算量Ｍｋ’に置き換えることができるので、
ＴＡＤＤ”＝Ｍｋ＋Ｍｋ’＋（３ｋ＋１０）Ｍ＋３Ｓ
ＴＤＢＬ”＝Ｍｋ＋Ｍｋ’＋Ｓｋ＋（３ｋ＋７）Ｍ＋６Ｓ
となる。
【００２７】
したがって、計算量の削減が期待できることが分かる。
実験
本発明の効果を確認するため、コンピュータ上で本発明のプログラムと従来の方法でのプログラムとを動作させ、比較した。言語はgcc version3.3.3、ＯＳはFreeBSD 5.2.1、多倍長ライブラリはGNU MP ver.4.1.4、ＣＰＵはAMD Opteron(TM) Processor 248 (2.2Ghz)、パラメータはM.Scott and P.Barreto, “Generating more MNT elliptic curves”, Cryptology ePrint Archive 2004/058, available form http://eprint.iacr.org/2004/058に示されているものを使用した。ｐ＝625852803282871856053922297323874661378036491717（16ｂｉｔ）、ｋ＝６、ｍ＝208617601094290618684641029477488665211553761021、ａ＝−３、ｂ＝423976005090848776334332509669574781621802740510である。
【００２８】
その結果、従来のMillerのアルゴリズム１回の実行時間が11.22ｍｓに対して、本発明の擬似Millerのアルゴリズム１回の実行時間は9.03ｍｓであり、２４％高速化できた。
【図面の簡単な説明】
【００２９】
【図１】Tateペアリング演算の概要を示す図。
【図２】Tateペアリングを用いたペアリング演算装置の機能構成例を示す図。
【図３】Miller演算装置の内部構成例を示す図。
【図４】Millerアルゴリズムの処理フローを示す図。
【図５】擬似Millerのアルゴリズムを用いた演算の高速化の原理を示す図。
【図６】擬似乗算により乗算回数が少なくするための前処理の概要を示す図。
【図７】擬似Millerアルゴリズムを用いたペアリング演算装置の機能構成例を示す図。
【図８】擬似Miller演算装置の機能構成例を示す図。
【図９】擬似Millerアルゴリズムの処理フローを示す図。
【図１０】正規基底での擬似逆元演算部の機能構成例を示す図。
【図１１】正規基底での擬似逆元演算部の処理フローを示す図。
【図１２】多項式基底での擬似逆元演算部の機能構成例を示す図。
【図１３】多項式基底での擬似逆元演算部の処理フローを示す図。
【図１４】擬似乗算部の機能構成例を示す図。
【図１５】擬似乗算部の処理フローを示す図。
【図１】
2006309068.tif 000012
【図２】
2006309068.tif 000013
【図３】
2006309068.tif 000014
【図４】
2006309068.tif 000015
【図５】
2006309068.tif 000016
【図６】
2006309068.tif 000017
【図７】
2006309068.tif 000018
【図８】
2006309068.tif 000019
【図９】
2006309068.tif 000020
【図１０】
2006309068.tif 000021
【図１１】
2006309068.tif 000022
【図１２】
2006309068.tif 000023
【図１３】
2006309068.tif 000024
【図１４】
2006309068.tif 000025
【図１５】
2006309068.tif 000026