(57)【要約】【課題】Millerのアルゴリズムの演算速度を高速にする。具体的には、ｍを２進数で表現するときに、０のビットの数を多くする。【解決手段】ｍを表現するときに０と１だけでなく、−１も用いて、ｍを表現するビットに１が連続する場合には、−１を用いて０の数を増やす。また、（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）をあらかじめ計算しておく。そして、ｍのｎ番目のビットが−１の場合には、点Ｔと点−Ｐとを通る直線をｌ１（ｘ、ｙ）、Ｔ−Ｐを通るｙ軸に平行な直線をｌ２（ｘ、ｙ）、Ｐを通るｙ軸に平行な直線をｌ３（ｘ、ｙ）として、Ａ＝ｌ１（Ｑ’）／ｌ３（Ｑ’）を（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）−λを用いて表現できることを利用して個別に計算し、Ｆ・（Ａ・ｌ２（Ｓ）ｌ３（Ｓ））／（ｌ２（Ｑ’）ｌ１（Ｓ））を計算する。【選択図】図７
2006330497.tif 000002
【特許請求の範囲】
【請求項１】
有限体ＧＦ（ｐ）上の楕円曲線上の点Ｐと有限体ＧＦ（ｐｋ）上の楕円曲線上の点Ｑを入力とし、入力された点から有限体ＧＦ（ｐｋ）上の元ｆを求めるMiller演算部と、求めた有限体上の元を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）に写像し、出力するべき乗演算部とを備えるペアリング演算装置において、
ｐは素数または素数のべき乗、ｍは素数かつＰ、Ｑ、ｅの位数、ｋはｍ｜（ｐｋ−１）を満足する最小の偶数、ｍは（ｐ−１）の約数ではない、かつｐとｍの最大公約数は１、Ｔを有限体ＧＦ（ｐ）上の元、ＳとＦを有限体ＧＦ（ｐｋ）上の元、Ｑ’をＱ＋Ｓとして、
ｍを２進数で表した値を、０、１、および−１を用いて表現するｍ符号化手段を有し
ｍのｎ番目のビットが−１の場合には、
Ｔ−Ｐを計算して記録手段に記録し、
点Ｔと点−Ｐとを通る直線をｌ１、Ｔ−Ｐを通るｙ軸に平行な直線をｌ２、Ｐを通るｙ軸に平行な直線をｌ３として、Ｆ・（ｌ１（Ｑ’）ｌ２（Ｓ）ｌ３（Ｓ））／（ｌ２（Ｑ’）ｌ３（Ｑ’）ｌ１（Ｓ））をＦに代入する楕円減算を行うこと
を特徴とする前記Miller演算部
を備えるペアリング演算装置。
【請求項２】
請求項１記載のペアリング演算装置において、
Ｑ’とＰの座標をそれぞれ（ｘＱ’，ｙＱ’）（ｘＰ，ｙＰ）とするときに、あらかじめ（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）を計算して、記録手段に記録しておき、
前記楕円減算を行うときに、あらかじめ記録されている（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）を用いてＡ＝ｌ１（Ｑ’）／ｌ３（Ｑ’）を計算して記録部に記録し、
Ｆ・（ｌ１（Ｑ’）ｌ２（Ｓ）ｌ３（Ｓ））／（ｌ２（Ｑ’）ｌ３（Ｑ’）ｌ１（Ｓ））を計算するときには、記録部に記録した、Ａを読み出し、Ｆ・（Ａ・ｌ２（Ｓ）ｌ３（Ｓ））／（ｌ２（Ｑ’）ｌ１（Ｓ））を計算すること
を特徴とする前記Miller演算部
を備えるペアリング演算装置。
【請求項３】
有限体ＧＦ（ｐ）上の楕円曲線上の点Ｐと有限体ＧＦ（ｐｋ）上の楕円曲線上の点Ｑを入力とし、入力された点から有限体ＧＦ（ｐｋ）上の元ｆ’を求める擬似Miller演算部と、求めた有限体上の元を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）に写像し、出力するべき乗演算部とを備えるペアリング演算装置において、
ｐは素数または素数のべき乗、ｍは素数かつＰ、Ｑ、ｅの位数、ｋはｍ｜（ｐｋ−１）を満足する最小の偶数、ｍは（ｐ−１）の約数ではない、かつｐとｍの最大公約数は１、Ｔを有限体ＧＦ（ｐ）上の元、ＳとＦを有限体ＧＦ（ｐｋ）上の元、Ｑ’をＱ＋Ｓとして、
ｍを２進数で表した値を、０、１、および−１を用いて表現するｍ符号化手段を有し
ｍのｎ番目のビットが−１の場合には、
Ｔ−Ｐを計算して記録手段に記録し、
点Ｔと点−Ｐとを通る直線をｌ１、Ｔ−Ｐを通るｙ軸に平行な直線をｌ２、Ｐを通るｙ軸に平行な直線をｌ３、ｌ２（Ｑ’）の擬似の逆元をＬ２とする場合に、Ｆ・（ｌ１（Ｑ’）ｌ２（Ｓ）ｌ３（Ｓ））・Ｌ２／（ｌ３（Ｑ’）ｌ１（Ｓ））をＦに代入する楕円減算を行うこと
を特徴とする前記擬似Miller演算部と、
前記似Miller演算部で求めた元ｆ’を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）にべき乗演算により写像することを特徴とする前記べき乗演算部と、
を備えるペアリング演算装置。
【請求項４】
請求項３記載のペアリング演算装置において、
Ｑ’とＰの座標をそれぞれ（ｘＱ’，ｙＱ’）（ｘＰ，ｙＰ）とするときに、あらかじめ（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）を計算して、記録手段に記録しておき、
前記楕円減算を行うときに、あらかじめ記録されている（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）を用いてＡ＝ｌ１（Ｑ’）／ｌ３（Ｑ’）を計算して記録部に記録し、
Ｆ・（ｌ１（Ｑ’）ｌ２（Ｓ）ｌ３（Ｓ））・Ｌ２／（ｌ３（Ｑ’）ｌ１（Ｓ））を計算するときには、記録部に記録した、Ａを読み出し、Ｆ・（Ａ・ｌ２（Ｓ）ｌ３（Ｓ））・Ｌ２／ｌ１（Ｓ）を計算すること
を特徴とする前記擬似Miller演算部
を備えるペアリング演算装置。
【請求項５】
有限体ＧＦ（ｐ）上の楕円曲線上の点Ｐと有限体ＧＦ（ｐｋ）上の楕円曲線上の点Ｑを入力とし、入力された点から有限体ＧＦ（ｐｋ）上の元ｆを求めるMiller演算と、求めた有限体上の元を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）に写像し、出力するべき乗演算とを行うペアリング演算方法において、
ｐは素数または素数のべき乗、ｍは素数かつＰ、Ｑ、ｅの位数、ｋはｍ｜（ｐｋ−１）を満足する最小の偶数、ｍは（ｐ−１）の約数ではない、かつｐとｍの最大公約数は１、Ｔを有限体ＧＦ（ｐ）上の元、ＳとＦを有限体ＧＦ（ｐｋ）上の元、Ｑ’をＱ＋Ｓとして、
Miller演算部で、
ｍを２進数で表した値を、０、１、および−１を用いて表現し、
ｍのｎ番目のビットが−１の場合には、
Ｔ−Ｐを計算して記録手段に記録し、
点Ｔと点−Ｐとを通る直線をｌ１、Ｔ−Ｐを通るｙ軸に平行な直線をｌ２、Ｐを通るｙ軸に平行な直線をｌ３として、Ｆ・（ｌ１（Ｑ’）ｌ２（Ｓ）ｌ３（Ｓ））／（ｌ２（Ｑ’）ｌ３（Ｑ’）ｌ１（Ｓ））をＦに代入する楕円減算を行う
ことを特徴とするペアリング演算方法。
【請求項６】
請求項５記載のペアリング演算方法において、
前記Miller演算部で、
Ｑ’とＰの座標をそれぞれ（ｘＱ’，ｙＱ’）（ｘＰ，ｙＰ）とするときに、あらかじめ（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）を計算して、記録手段に記録しておき、
前記楕円減算を行うときに、あらかじめ記録されている（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）を用いてＡ＝ｌ１（Ｑ’）／ｌ３（Ｑ’）を計算して記録部に記録し、
Ｆ・（ｌ１（Ｑ’）ｌ２（Ｓ）ｌ３（Ｓ））／（ｌ２（Ｑ’）ｌ３（Ｑ’）ｌ１（Ｓ））を計算するときには、記録部に記録した、Ａを読み出し、Ｆ・（Ａ・ｌ２（Ｓ）ｌ３（Ｓ））／（ｌ２（Ｑ’）ｌ１（Ｓ））を計算すること
を特徴とするペアリング演算方法。
【請求項７】
有限体ＧＦ（ｐ）上の楕円曲線上の点Ｐと有限体ＧＦ（ｐｋ）上の楕円曲線上の点Ｑを入力とし、入力された点から有限体ＧＦ（ｐｋ）上の元ｆ’を求める擬似Miller演算と、求めた有限体上の元を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）に写像し、出力するべき乗演算とを行うペアリング演算方法において、
ｐは素数または素数のべき乗、ｍは素数かつＰ、Ｑ、ｅの位数、ｋはｍ｜（ｐｋ−１）を満足する最小の偶数、ｍは（ｐ−１）の約数ではない、かつｐとｍの最大公約数は１、Ｔを有限体ＧＦ（ｐ）上の元、ＳとＦを有限体ＧＦ（ｐｋ）上の元、Ｑ’をＱ＋Ｓとして、
擬似Miller演算部で、
ｍを２進数で表した値を、０、１、および−１を用いて表現し、
ｍのｎ番目のビットが−１の場合には、
Ｔ−Ｐを計算して記録手段に記録し、
点Ｔと点−Ｐとを通る直線をｌ１、Ｔ−Ｐを通るｙ軸に平行な直線をｌ２、Ｐを通るｙ軸に平行な直線をｌ３、ｌ２（Ｑ’）の擬似の逆元をＬ２とする場合に、Ｆ・（ｌ１（Ｑ’）ｌ２（Ｓ）ｌ３（Ｓ））・Ｌ２／（ｌ３（Ｑ’）ｌ１（Ｓ））をＦに代入する楕円減算を行い、
べき乗演算部で、
前記擬似Miller演算で求めた元ｆ’を有限体ＧＦ（ｐｋ）上の元ｅ（Ｐ，Ｑ）にべき乗演算により写像する
ことを特徴とするペアリング演算方法。
【請求項８】
請求項７記載のペアリング演算方法において、
前記擬似Miller演算部で、
Ｑ’とＰの座標をそれぞれ（ｘＱ’，ｙＱ’）（ｘＰ，ｙＰ）とするときに、あらかじめ（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）を計算して、記録手段に記録しておき、
前記楕円減算を行うときに、あらかじめ記録されている（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）を用いてＡ＝ｌ１（Ｑ’）／ｌ３（Ｑ’）を計算して記録部に記録し、
Ｆ・（ｌ１（Ｑ’）ｌ２（Ｓ）ｌ３（Ｓ））・Ｌ２／（ｌ３（Ｑ’）ｌ１（Ｓ））を計算するときには、記録部に記録した、Ａを読み出し、Ｆ・（Ａ・ｌ２（Ｓ）ｌ３（Ｓ））・Ｌ２／ｌ１（Ｓ）を計算すること
を特徴とするペアリング演算方法。
【請求項９】
請求項１から４のいずれかに記載の装置をコンピュータにより実現するペアリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、楕円曲線上の演算、特にセキュリティ技術を実現するための演算を利用した装置、方法、およびプログラムに関する。
【背景技術】
【０００２】
楕円曲線のペアリングを用いたＩＤ−ｂａｓｅ暗号や短署名長デジタル署名を実現する方法が提案されている（特許文献１）。
Tateペアリングによる暗号や署名の概要を図１に示す。有限体ＧＦ（ｐ）上で定義される楕円をＥ／ＧＦ（ｐ）とする。楕円Ｅ／ＧＦ（ｐ）上のＧＦ（ｐ）有理点をＰ（ｘＰ、ｙＰ）、楕円Ｅ／ＧＦ（ｐ）上のＧＦ（ｐｋ）有理点をＱ（ｘＱ、ｙＱ）とする。Tateペアリングでは、ＰとＱを入力とし、Millerアルゴリズムによって有限体ＧＦ（ｐｋ）上の元ｆを出力し、さらにべき乗演算によってｆを（ｐｋ−１）／ｍ乗することで有限体ＧＦ（ｐｋ）上の元ｅへ写像し、出力する。ここで、ｐは素数または素数のべき乗、ｍは素数かつＰ、Ｑ、ｅの位数、ｋはｍ｜（ｐｋ−１）を満足する最小の整数、ｍは（ｐ−１）の約数ではない、かつｐとｍの最大公約数は１である。
【０００３】
図２はTateペアリングを用いたペアリング演算装置１０００の機能構成例を示している。図１に示した処理を行うため、Millerアルゴリズムを用いて入力ＰとＱを有限体ＧＦ（ｐｋ）上の元ｆに変換して出力するMiller演算装置３０と、べき乗演算によって入力ｆを有限体ＧＦ（ｐｋ）上の元ｅに写像して出力するべき乗演算装置２０から構成されている。
Tateペアリングで９０％の計算量を占めるMiller演算装置３０の内部構成例を図３に、処理フロー例を図４に示す。Miller演算装置３０は、制御部１００、代入部２００、楕円上点生成部４００、楕円加算部５００、入出力部６００、ＧＦ（ｐｋ）乗算部７００、ＧＦ（ｐｋ）逆元部８５０、および記録部１９０から構成される。制御部１００は、以下に示す処理フローに沿った処理を実行するために他の構成部を制御する。また、記録部１９０はハードディスク等の不揮発性のメモリでもよいし、一連の計算を行う間だけ一時的に記録する揮発性のメモリでもよい。また、組み合わせてもよい。
【０００４】
入出力部６００にｍ、Ｐ、Ｑが入力されると、ｍ、Ｐ、Ｑを記録部１９０に記録する（Ｓ７００）。次に代入部２００で、ＴにＰを、Ｆに１を代入し、記録部１９０に記録する（Ｓ７１０）。楕円上点生成部４００で、Ｓ≠ＰかつＳ≠Ｑの条件を満足する有限体ＧＦ（ｐｋ）上で定義される楕円上の点Ｓ（∈Ｅ／ＧＦ（ｐｋ））を生成し、記録部１９０に記録する（Ｓ７２０）。Ｓは条件を満足する点であれば、あらかじめ定めてもいいし、ランダムに生成してもよい。楕円加算部５００で、記録部１９０からＱとＳを読み取り、Ｑ’（＝Ｑ＋Ｓ）を計算し、記録部１９０に記録する（Ｓ７３０）。代入部２００で、ｌｏｇ（ｍ）−１の小数点以下を切り上げた整数をｎに代入し、記録部１９０に記録する（Ｓ７４０）。制御部１００は、記録部１９０からｎを読み取り、ｎ＜０か否かを確認し、Ｙｅｓの場合にはステップＳ９１０に進み、Ｎｏの場合にはステップＳ７６０に進む（Ｓ７５０）。Ｙｅｓの場合、入出力部６００は、記録部１９０からＦを読み取り、出力し（Ｓ９１０）、Millerアルゴリズムによる演算が終了する。Ｎｏの場合、楕円加算部５００は、記録部１９０からＴを読み取り、２Ｔを計算し、記録部１９０に記録する（Ｓ７６０）。ＧＦ（ｐｋ）乗算部７００は、Ｑ’、Ｓ、Ｔ、２Ｔを記録部１９０から読み取り、ｌ１（ｘ，ｙ）＝０をＴと２Ｔとを結ぶ直線、ｌ２（ｘ，ｙ）＝０を２ＴとＯとを結ぶ直線として、ｌ１（Ｑ’）、ｌ２（Ｑ’）、ｌ１（Ｓ）、ｌ２（Ｓ）を計算し、記録部１９０に記録する（Ｓ７７０）。ただし、ｌ１（Ｑ’）とは、Ｑ’のｘ座標とｙ座標とを、ｌ１（ｘ，ｙ）に代入した値である。なお、Ｓを有限体ＧＦ（ｐ）の元から選定すると（この場合、残りのｋ−１個の有限体ＧＦ（ｐ）の元は０である。）、ｌ１（Ｓ）、ｌ２（Ｓ）の計算は省略でき、以降のステップでｌ１（Ｓ）、ｌ２（Ｓ）を省略できる。次に、代入部２００は、記録部１９０から２Ｔを読み取り、Ｔに２Ｔの値を代入し、Ｔを記録部１９０に記録する（Ｓ７８０）。ＧＦ（ｐｋ）逆元部８５０で、記録部１９０からｌ２（Ｑ’）、ｌ１（Ｓ）を読み取り、ｌ２（Ｑ’）−１、ｌ１（Ｓ）−１を計算し、記録部１９０に記録する（Ｓ７９０）。ＧＦ（ｐｋ）乗算部７００は、記録部１９０からＦ、ｌ１（Ｑ’）、ｌ２（Ｓ）、ｌ２（Ｑ’）−１、ｌ１（Ｓ）−１を読み取り、
【数１】
2006330497.tif 000003
を計算し、Ｆの値として記録部１９０に記録する（Ｓ８１０）。ここで、ステップＳ７６０からＳ８１０までの過程を、楕円２倍演算（ＴＤＢＬ、Ｓ８００）と呼ぶ。制御部１００は、記録部１９０からｍとｎを読み取り、ｍのｎ番目のビットが１かを確認し、Ｙｅｓの場合にはステップＳ８３０へ進み、Ｎｏの場合にはステップＳ９００へ進む（Ｓ８２０）。Ｙｅｓの場合、楕円加算部５００で、記録部１９０からＴ、Ｐを読み取り、Ｔ＋Ｐを計算し、記録部１９０に記録する（Ｓ８３０）。ＧＦ（ｐｋ）乗算部７００は、Ｑ’、Ｓ、Ｔ、Ｐ，Ｔ＋Ｐを記録部１９０から読み取り、ｌ１（ｘ，ｙ）＝０をＴとＰとを結ぶ直線、ｌ２（ｘ，ｙ）＝０をＴ＋ＰとＯとを結ぶ直線とし、ｌ１（Ｑ’）、ｌ２（Ｑ’）、ｌ１（Ｓ）、ｌ２（Ｓ）を計算して、記録部１９０に記録する（Ｓ８４０）。代入部２００は、記録部１９０からＴ＋Ｐを読み取り、ＴにＴ＋Ｐを代入し、Ｔを記録部１９０に記録する（Ｓ８５０）。ＧＦ（ｐｋ）逆元部８５０は、記録部１９０からｌ２（Ｑ’）、ｌ１（Ｓ）を読み取り、ｌ２（Ｑ’）−１、ｌ１（Ｓ）−１を計算し、記録部１９０に記録する（Ｓ８６０）。ＧＦ（ｐｋ）乗算部７００は、記録部１９０からＦ、ｌ１（Ｑ’）、ｌ２（Ｓ）、ｌ２（Ｑ’）−１、ｌ１（Ｓ）−１を読み取り、
【数２】
2006330497.tif 000004
を計算し、Ｆの値として記録部１９０に記録する（Ｓ８８０）。ここで、ステップＳ８３０からＳ８８０までを、楕円加算演算（ＴＡＤＤ、Ｓ９００）と呼ぶ。ステップＳ８２０でＮｏと判断した場合とステップＳ８８０が終了した場合、代入部２００は、記録部１９０からｎを読み取り、ｎ−１をｎに代入し、ｎを記録部１９０に記録する（Ｓ８９０）。次にステップＳ７５０に戻り、ステップＳ７５０の判断がＹｅｓとなるまで処理が繰り返される。
【特許文献１】特開2004-177673号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ペアリングの演算に必要な演算量は、通常の楕円演算にくらべると非常に大きいため、その演算速度が遅いことが問題となっている。Tateペアリングの場合、Millerのアルゴリズムというdevisor有理式の評価を行う演算に費やされる。本発明が解決しようとする課題は、Millerのアルゴリズムの演算速度の高速化である。
特に、図４に示した楕円加算演算Ｓ９００は、ｍを２進数で表現した場合の１の数だけ行われる。そこで、ｍを２進数で表現した場合に、０のビットの数を多くすることができれば、演算速度の高速化が図れる。本発明の解決しようとする課題は、ｍを２進数で表現するときに、０のビットの数を多くすることである。
【課題を解決するための手段】
【０００６】
本発明では、ｍを表現するときに０と１だけでなく、−１も用いて、ｍを表現するビットに１が連続する場合には、−１を用いて０の数を増やす。たとえば、図５に示したようにｍが１０１１１１と表現される場合には、１１０００（−１）と表現する。この表現は、１１００００−１を意味しており、１０１１１１と同じ値である。このように−１を用いた場合には、楕円減算演算が必要となる。そこで、ｍのｎ番目のビットが−１の場合には、点Ｔと点−Ｐとを通る直線をｌ１（ｘ、ｙ）、Ｔ−Ｐを通るｙ軸に平行な直線をｌ２（ｘ、ｙ）、Ｐを通るｙ軸に平行な直線をｌ３（ｘ、ｙ）として、Ｆ・（ｌ１（Ｑ’）ｌ２（Ｓ）ｌ３（Ｓ））／（ｌ２（Ｑ’）ｌ３（Ｑ’）ｌ１（Ｓ））をＦに代入する楕円減算を行う。
【０００７】
また、Ｑ’の座標を（ｘＱ’、ｙＱ’）とすると、ｌ１（ｘ、ｙ）は、点Ｔと点−Ｐとを通る直線だから、（ｙＱ’＋ｙＰ）−λ（ｘＱ’−ｘＰ）を用いて表現できる。また、ｌ３（ｘ、ｙ）は、Ｐを通るｙ軸に平行な直線だから、（ｘＱ’−ｘＰ）を用いて表現できる。したがって、ｌ１（ｘ、ｙ）／ｌ３（ｘ、ｙ）は、（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）−λを用いて表現できる。また、（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）は、Ｑ’とＰによって決まる値であるから、最初に計算しておけば、繰り返し利用することができる。そこで、（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）をあらかじめ計算しておき、Ａ＝ｌ１（Ｑ’）／ｌ３（Ｑ’）を（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）−λを用いて表現できることを利用して個別に計算し、Ｆ・（Ａ・ｌ２（Ｓ）ｌ３（Ｓ））／（ｌ２（Ｑ’）ｌ１（Ｓ））を計算する。
【発明の効果】
【０００８】
本発明によれば、ｍの表現で０のビットの数が増えるため、楕円加算演算を行う頻度が少なくなり、演算量を減少させることができる。また、ｌ１（ｘ、ｙ）もｌ３（ｘ、ｙ）もＰを通る直線であることから、（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）をあらかじめ計算しておき、ｌ１（ｘ、ｙ）／ｌ３（ｘ、ｙ）をまとめて計算することで、計算量を削減することができる。さらに、任意の標数の楕円曲線に適用することが可能であり、応用範囲が広い。
【発明を実施するための最良の形態】
【０００９】
以下では、説明の重複を避けるため同じ機能を有する構成部や同じ処理を行う処理ステップには同一の番号を付与し、説明を省略する。
［第１実施形態］
図６に本発明のMiller演算装置３０’を示す。図３との違いは、ｍ符号化部３００を有していることである。ｍ符号化部３００では、図５に示したｍの表現の変更を行う。図７に図６のMiller演算装置３０’の処理フローを示す。図４に示した従来の処理フローとの違いは、以下のとおりである。ステップＳ７４０の後にｍのビット列変換（Ｓ１１０）が追加されたこと、ステップＳ８２０がＮｏの場合にｍのｎ番目のビットが−１かを確認する過程（Ｓ１３０）が追加されたこと、ステップＳ１３０がＹｅｓの場合に楕円減算演算（ＴＳＵＢ、Ｓ１４０またはＳ１４０’）が追加されたことである。
【００１０】
図８にステップＳ１１０の詳細を、図９にステップＳ１４０の詳細を示す。ステップＳ１１０では、まずｉに０を代入し、記録部１９０に記録する（Ｓ１１１）。制御部１００が、ｍのｉ番目のビットが１かを確認する（Ｓ１１２）。ステップＳ１１２の確認がＮｏの場合には、ステップＳ１１５に進む。ステップＳ１１２の確認がＹｅｓの場合には、制御部１００が、ｍのｉ＋１晩目のビットが１かを確認する（Ｓ１１３）。ステップＳ１１３の確認がＮｏの場合には、ステップＳ１１５に進む。ステップＳ１１３の確認がＹｅｓの場合には、制御部１００が、ｍのｉ番目のビットを−１とし、ｉ＋１番目のビットを２とし、新しいｍを記録部１９０に記録する（Ｓ１１４）。次に、制御部１００が、ｍのｉ番目のビットが２かを確認する（Ｓ１１５）。ステップＳ１１５がＮｏのときはステップＳ１１７に進む。ステップＳ１１５がＹｅｓのときは、制御部１００が、ｍのｉ番目のビットを０にし、ｉ＋１番目のビットに１を加え、新しいｍを記録部１９０に記録する（Ｓ１１６）。次にｉ＝ｎかを確認し（Ｓ１１７）、Ｎｏの場合にはステップＳ１１８に進む。ステップＳ１１８では、代入部２００がｉ＋１をｉに代入する（Ｓ１１８）。Ｙｅｓの場合には、制御部１００が、ｍのｎ＋１番目のビットが１かを確認する（Ｓ１１９）。ステップＳ１１９がＮｏの場合にはステップＳ１１０を終了する。ステップＳ１１９がＹｅｓの場合には、代入部２００がｎにｎ＋１を代入して、記録部１９０に記録し（Ｓ１２０）、ステップＳ１１０を終了する。
【００１１】
図９に楕円減算演算（ＴＳＵＢ、Ｓ１４０）の詳細を示す。楕円加算部５００で、記録部１９０からＴ、Ｐを読み取り、Ｔ−Ｐを計算し、記録部１９０に記録する（Ｓ１４１）。ＧＦ（ｐｋ）乗算部７００は、Ｑ’、Ｓ、Ｔ、Ｐ，Ｔ−Ｐを記録部１９０から読み取り、ｌ１（ｘ，ｙ）＝０をＴと−Ｐとを結ぶ直線、ｌ２（ｘ，ｙ）＝０をＴ−Ｐを通るｙ軸と平行な直線、ｌ３（ｘ，ｙ）＝０をＰを通るｙ軸に平行な直線とし、ｌ１（Ｑ’）、ｌ２（Ｑ’）、ｌ３（Ｑ’）、ｌ１（Ｓ）、ｌ２（Ｓ）、ｌ３（Ｓ）を計算して、記録部１９０に記録する（Ｓ１４２）。代入部２００は、記録部１９０からＴ−Ｐを読み取り、ＴにＴ−Ｐを代入し、Ｔを記録部１９０に記録する（Ｓ１４３）。ＧＦ（ｐｋ）逆元部８５０は、記録部１９０からｌ２（Ｑ’）、ｌ３（Ｑ’）、ｌ１（Ｓ）を読み取り、ｌ２（Ｑ’）−１、ｌ３（Ｑ’）−１、ｌ１（Ｓ）−１を計算し、記録部１９０に記録する（Ｓ１４４）。ＧＦ（ｐｋ）乗算部７００は、記録部１９０からＦ、ｌ１（Ｑ’）、ｌ２（Ｓ）、ｌ３（Ｓ）、ｌ２（Ｑ’）−１、ｌ３（Ｑ’）−１、ｌ１（Ｓ）−１を読み取り、
【数３】
2006330497.tif 000005
を計算し、Ｆの値として記録部１９０に記録する（Ｓ１４５）。このような処理によって楕円減算演算（Ｓ１４０）は終了する。
上述のように処理することによって、ｍを表現するビット列の０を多くすることができ、演算量の削減が期待できる。
【００１２】
［変形例］
本変形例では、ｌ１（ｘ、ｙ）もｌ３（ｘ、ｙ）もＰを通る直線であることを利用して、演算量を削減する。具体的には、（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）をあらかじめ計算しておき、Ａ＝ｌ１（ｘ、ｙ）／ｌ３（ｘ、ｙ）を計算した上で、Ｆ・（Ａ・ｌ２（Ｓ）ｌ３（Ｓ））／（ｌ２（Ｑ’）ｌ１（Ｓ））を計算する。図１０と図１１に第１実施形態で示した処理フローとの変更点を示す。
図１０は、図７のステップＳ７３０の代わりとなるステップＳ７３０’である。ステップＳ７３０’では、Ｑ’の座標を計算しておくだけでなく、記録部からＰの座標も読み出し、（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）も計算して、記録部１９０に記録する。
【００１３】
図１１は、図９のステップＳ１４０の代わりとなるステップＳ１４０’である。ステップＳ１４０’とステップＳ１４０との違いは、ステップＳ１４２’、ステップＳ１４４’、およびステップＳ１４５’である。ステップＳ１４２’では、ＧＦ（ｐｋ）乗算部７００が、Ｑ’、Ｓ、Ｔ、Ｐ、Ｔ−Ｐ、（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）を記録部１９０から読み取り、ｌ１（ｘ，ｙ）＝０をＴと−Ｐとを結ぶ直線、ｌ２（ｘ，ｙ）＝０をＴ−Ｐを通るｙ軸と平行な直線、ｌ３（ｘ，ｙ）＝０をＰを通るｙ軸に平行な直線とし、λ、ｌ１（Ｑ’）／ｌ３（Ｑ’）、ｌ２（Ｑ’）、ｌ１（Ｓ）／ｌ３（Ｓ）、ｌ２（Ｓ）を計算して、記録部１９０に記録する。ステップＳ１４４’では、ＧＦ（ｐｋ）逆元部８５０が、記録部１９０からｌ２（Ｑ’）、ｌ１（Ｓ）／ｌ３（Ｓ）を読み取り、ｌ２（Ｑ’）−１、（ｌ１（Ｓ）／ｌ３（Ｑ’））−１を計算し、記録部１９０に記録する。ステップＳ１４５’では、ＧＦ（ｐｋ）乗算部７００が、記録部１９０からＦ、ｌ１（Ｑ’）／ｌ３（Ｑ’）、ｌ２（Ｓ）、ｌ２（Ｑ’）−１、（ｌ１（Ｓ）／ｌ３（Ｑ’））−１を読み取り、
【数４】
2006330497.tif 000006
を計算し、Ｆの値として記録部１９０に記録する。このような処理によって（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）をあらかじめ計算しておけるので、繰り返し処理での演算量を削減できる。
【００１４】
［第２実施形態］
本発明では、有限体の性質を用いてさらに高速化を行う。図１２に演算の高速化の原理を示す。Tateペアリングでは、有限体ＧＦ（ｐｋ）上の元ｆをべき乗演算により有限体ＧＦ（ｐｋ）上の元ｅに写像するが、次の条件を満足する有限体ＧＦ（ｐｋ）上の元ｆ’も、べき乗演算により有限体ＧＦ（ｐｋ）上の元ｅに写像する。
【００１５】
ｆ’＝ｒｆ  ただし、ｒは有限体ＧＦ（ｐｋ／２）上の元                （１）
そこで、本発明ではｋが偶数の場合に、この有限体の性質を利用し、Millerアルゴリズムよりも計算量が少ないアルゴリズム（以下、「擬似Millerアルゴリズム」という。）で、元ｆ’を求め、元ｆ’をべき乗演算することで元ｅを求める。
【００１６】
擬似Millerアルゴリズムでは、Millerアルゴリズムで逆元を求める処理を、少ない計算量で求められる逆元のｒ倍の元（以下、「擬似逆元」という。）を求める処理に置き換える。具体的には、ｋが偶数であり、Ｌが有限体ＧＦ（ｐｋ）上の元の場合、
【数５】
2006330497.tif 000007
を満足する有限体ＧＦ（ｐｋ／２）上の元ｎが存在する。したがって、
【数６】
2006330497.tif 000008
であり、式（１）の関係を満足する。そこで、
【数７】
2006330497.tif 000009
を擬似逆元として使用できる。
さらに、特に、ｌ２（Ｑ’）の逆元の場合には、以下のような擬似逆元を使うことができる。ｌ２（Ｑ’）は、
ｌ２（Ｑ’）＝ｇＸＱ’＋ｈ                                          （５）
と表すことができる。ここで、ｇ、ｈはＧＦ（ｐ）上の元である。さらに、フェルマーの小定理から、
【数８】
2006330497.tif 000010
と変形することができる。ここでＸ＾Ｑ’はＸＱ’の共役元、ｌ＾２（Ｑ’）はｌ２（Ｑ’）の共役元である。そこで、ｌ＾２（Ｑ’）をｌ２（Ｑ’）の擬似逆元として用いることができる。
【００１７】
図１３に本発明のペアリング演算装置の機能構成例を示す。図２との違いはMiller演算装置３０の代わりに、擬似Miller演算装置１０が備えられていることである。擬似Miller演算装置１０は、前記の擬似逆元を用いることで、擬似Millerアルゴリズムを実現する装置である。擬似Miller演算装置１０の内部構成例を図１４に示す。図１４と図３との違いは、図１４の記録部１５０に記録するデータの種類が、図３の記録部１９０に記録するデータの種類と異なるものがあること、擬似逆元を計算するために擬似ＧＦ（ｐｋ）逆元部８００が追加されたことである。図１５は、図９と差し替えられる楕円減算演算Ｓ１４０”の処理フローである。本処理フローの全般に共通することであるが、図４、図７〜１１の説明中での「記録部１９０への記録」または「記録部１９０からの読み取り」は、図１５では「記録部１５０への記録」または「記録部１５０からの読み取り」と読み替える。図１５の処理フローと図９の処理フローとの違いは、ステップＳ１４４がステップＳ１４６に、ステップＳ１４５がステップＳ１４７に置き換えられていることである。
【００１８】
ステップＳ１４６では、擬似ＧＦ（ｐｋ）逆元部８００が、記録部１５０からｌ２（Ｑ’）、ｌ３（Ｑ’）、ｌ１（Ｓ）を読み取り、ｌ２（Ｑ’）、ｌ３（Ｑ’）、ｌ１（Ｓ）の擬似逆元を計算し、記録部１５０に記録する。ステップＳ１４７では、ＧＦ（ｐｋ）乗算部７００が、記録部１５０からｌ２（Ｑ’）とｌ３（Ｑ’）とｌ１（Ｓ）の擬似逆元と、Ｆ、ｌ１（Ｑ’）、ｌ２（Ｓ）、ｌ３（Ｓ）を読み取り、
【数９】
2006330497.tif 000011
を計算し、Ｆの値として記録部１５０に記録する。
【００１９】
［変形例］
本変形例では、第１実施形態の変形例と同じように、ｌ１（ｘ、ｙ）もｌ３（ｘ、ｙ）もＰを通る直線であることを利用して、演算量を削減する。具体的には、（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）をあらかじめ計算しておき、Ａ＝ｌ１（ｘ、ｙ）／ｌ３（ｘ、ｙ）を計算した上で、擬似のＦ・（Ａ・ｌ２（Ｓ）ｌ３（Ｓ））／（ｌ２（Ｑ’）ｌ１（Ｓ））を計算する。図１０と図１６に第２実施形態で示した処理フローとの変更点を示す。
図１０は、図７のステップＳ７３０の代わりとなるステップＳ７３０’である。ステップＳ７３０’では、Ｑ’の座標を計算しておくだけでなく、記録部からＰの座標も読み出し、（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）も計算して、記録部１５０に記録する。
【００２０】
図１６は、図１５のステップＳ１４０”の代わりとなるステップＳ１４０’’’である。ステップＳ１４０’’’とステップＳ１４０”との違いは、ステップＳ１４２’、ステップＳ１４６’、およびステップＳ１４７’である。ステップＳ１４２’では、ＧＦ（ｐｋ）乗算部７００が、Ｑ’、Ｓ、Ｔ、Ｐ、Ｔ−Ｐ、（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）を記録部１５０から読み取り、ｌ１（ｘ，ｙ）＝０をＴと−Ｐとを結ぶ直線、ｌ２（ｘ，ｙ）＝０をＴ−Ｐを通るｙ軸と平行な直線、ｌ３（ｘ，ｙ）＝０をＰを通るｙ軸に平行な直線とし、λ、ｌ１（Ｑ’）／ｌ３（Ｑ’）、ｌ２（Ｑ’）、ｌ１（Ｓ）／ｌ３（Ｓ）、ｌ２（Ｓ）を計算して、記録部１５０に記録する。ステップＳ１４６’では、ＧＦ（ｐｋ）逆元部８００が、記録部１５０からｌ２（Ｑ’）、ｌ１（Ｓ）／ｌ３（Ｓ）を読み取り、ｌ２（Ｑ’）、（ｌ１（Ｓ）／ｌ３（Ｑ’））の擬似逆元を計算し、記録部１５０に記録する。ステップＳ１４７’では、ＧＦ（ｐｋ）乗算部７００が、記録部１９０からｌ２（Ｑ’）と（ｌ１（Ｓ）／ｌ３（Ｑ’））の擬似逆元、Ｆ、ｌ１（Ｑ’）／ｌ３（Ｑ’）、ｌ２（Ｓ）、を読み取り、
【数１０】
2006330497.tif 000012
を計算し、Ｆの値として記録部１５０に記録する。このような処理によって（ｙＱ’＋ｙＰ）／（ｘＱ’−ｘＰ）をあらかじめ計算しておけるので、繰り返し処理での演算量をさらに削減できる。
【００２１】
なお、本発明は、コンピュータ本体とコンピュータプログラムとして実行することが可能であるし、デジタルシグナルプロセッサや専用LSIに実装して実現することも可能である。
【図面の簡単な説明】
【００２２】
【図１】Tateペアリング演算の概要を示す図。
【図２】Tateペアリングを用いたペアリング演算装置の機能構成例を示す図。
【図３】Miller演算装置の内部構成例を示す図。
【図４】Millerアルゴリズムの処理フローを示す図。
【図５】ｍを（−１）を含むビット列で表現する方法の例を示す図。
【図６】本発明のMiller演算装置を示す図。
【図７】本発明のMiller演算装置の処理フローを示す図。
【図８】ｍのビット列変換の処理フローを示す図。
【図９】楕円減算演算の処理フローを示す図。
【図１０】ステップＳ７３０をステップＳ７３０’に変更することを示す図。
【図１１】楕円減算演算の処理フローの変形例を示す図。
【図１２】演算の高速化の原理を示す図。
【図１３】本発明のペアリング演算装置の機能構成例を示す図。
【図１４】擬似Miller演算装置の内部構成例を示す図。
【図１５】擬似逆元を用いた場合の楕円減算演算の処理フローを示す図。
【図１６】擬似逆元を用いた場合の楕円減算演算の処理フローの変形例を示す図。
【図１】
2006330497.tif 000013
【図２】
2006330497.tif 000014
【図３】
2006330497.tif 000015
【図４】
2006330497.tif 000016
【図５】
2006330497.tif 000017
【図６】
2006330497.tif 000018
【図７】
2006330497.tif 000019
【図８】
2006330497.tif 000020
【図９】
2006330497.tif 000021
【図１０】
2006330497.tif 000022
【図１１】
2006330497.tif 000023
【図１２】
2006330497.tif 000024
【図１３】
2006330497.tif 000025
【図１４】
2006330497.tif 000026
【図１５】
2006330497.tif 000027
【図１６】
2006330497.tif 000028