(57)【要約】【課題】楕円曲線のマルチペアリングの演算量を少なくし、マルチペアリング方法およびペアリング比較方法の高速化を図る。【解決手段】本発明は、複数の有限体ＧＦ（ｐｋ）上の元の積Πｅ（Ｐｉ，Ｑｉ）を出力するマルチペアリング演算方法に関する。（ｆｐ）＝ｍ（Ｐ）−ｍ（Ｏ）を満たす有理関数ｆｐに前記の入力の組（Ｐｉ，Ｑｉ）を代入した結果をＦｉとすると、本発明では、個別のＦｉを求めることなく、divisor有理式の評価を行う演算でΠＦｉを直接求める。    また、もう１つの発明は、ペアリングの結果ｅ（Ｐ１，Ｑ１）とｅ（Ｐ２，Ｑ２）とが等しいかを判定するペアリング比較方法では、（Ｐ１，Ｑ１）と（Ｐ２，−Ｑ２）を入力とし、積ｅ（Ｐ１，Ｑ１）・ｅ（Ｐ２，−Ｑ２）を出力するマルチペアリング演算を行う。このマルチペアリング演算の結果と１とを比較することで、ペアリング結果が等しいことを確認する。【選択図】図１２
2006301513.tif 000002
【特許請求の範囲】
【請求項１】
ｐは素数または素数のべき乗、ｋは偶数、Ｉは２以上の整数、ｉは１からＩの整数、Ｐｉは有限体ＧＦ（ｐ）上の楕円曲線上の点、Ｑｉは有限体ＧＦ（ｐｋ）上の楕円曲線上の点、ｅ（Ｐｉ，Ｑｉ）はＰｉとＱｉのペアリング結果の有限体ＧＦ（ｐｋ）上の元、Ｆｉは（ｆｐ）＝ｍ（Ｐ）−ｍ（Ｏ）を満たす有理関数ｆｐにＰｉとＱｉを代入した結果とするときに、
入力が複数の組（Ｐｉ，Ｑｉ）、出力がペアリング結果の積Πｅ（Ｐｉ，Ｑｉ）であるマルチペアリング演算装置において、
divisor有理式の評価を行う演算でΠＦｉを計算することを特徴とし、繰り返し計算によって最終的なΠＦｉを求める有理関数演算部
を備えるマルチペアリング演算装置。
【請求項２】
請求項１記載のマルチペアリング演算装置であって、
前記有理関数演算部からの出力に対して、べき乗有限体演算を行うべき乗演算部
を備えるマルチペアリング演算装置。
【請求項３】
請求項２記載のマルチペアリング演算装置であって、
Millerのアルゴリズムに従う処理を行うことを特徴とする前記有理関数演算部
を備えるマルチペアリング演算装置。
【請求項４】
請求項２記載のマルチペアリング演算装置であって、
修正Duursma-Leeのアルゴリズムに従う処理を行うことを特徴とする前記有理関数演算部
を備えるマルチペアリング演算装置。
【請求項５】
ｐは素数または素数のべき乗、ｋは偶数、ｉは１または２の整数、Ｐｉは有限体ＧＦ（ｐ）上の楕円曲線上の点、Ｑｉは有限体ＧＦ（ｐｋ）上の楕円曲線上の点、ｅ（Ｐｉ，Ｑｉ）はＰｉとＱｉのペアリング結果の有限体ＧＦ（ｐｋ）上の元、Ｆｉは（ｆｐ）＝ｍ（Ｐ）−ｍ（Ｏ）を満たす有理関数ｆｐにＰｉとＱｉを代入した結果とするときに、
（Ｐ1，Ｑ１）と（Ｐ２，Ｑ２）を入力とし、ペアリング結果のｅ（Ｐ１，Ｑ１）とｅ（Ｐ２，Ｑ２）とが等しいかの判定結果を出力とするペアリング比較装置において、
（Ｐ１，Ｑ１）と（Ｐ２，−Ｑ２）を入力とし、divisor有理式の評価を行う演算でＦ１・Ｆ２を計算し、繰り返し計算によって最終的なＦ１・Ｆ２を求める有理関数演算部を有し、積ｅ（Ｐ１，Ｑ１）・ｅ（Ｐ２，−Ｑ２）を出力するマルチペアリング演算部と、
前記マルチペアリング演算部の出力と１とを比較するＧＦ（ｐｋ）比較部と
を備えるペアリング比較装置。
【請求項６】
請求項５記載のペアリング比較装置であって、
前記有理関数演算部からの出力に対して、べき乗有限体演算を行うべき乗演算部を有することを特徴とする前記マルチペアリング演算部
を備えるペアリング比較装置。
【請求項７】
請求項６記載のペアリング比較装置であって、
Millerのアルゴリズムに従う処理を行う前記有理関数演算部を、有することを特徴とする前記マルチペアリング演算部
を備えるペアリング比較装置。
【請求項８】
請求項６記載のペアリング比較装置であって、
修正Duursma-Leeのアルゴリズムに従う処理を行う前記有理関数演算部を、有することを特徴とする前記マルチペアリング演算部
を備えるペアリング比較装置。
【請求項９】
ｐは素数または素数のべき乗、ｋは偶数、Ｉは２以上の整数、ｉは１からＩの整数、Ｐｉは有限体ＧＦ（ｐ）上の楕円曲線上の点、Ｑｉは有限体ＧＦ（ｐｋ）上の楕円曲線上の点、ｅ（Ｐｉ，Ｑｉ）はＰｉとＱｉのペアリング結果の有限体ＧＦ（ｐｋ）上の元、Ｆｉは（ｆｐ）＝ｍ（Ｐ）−ｍ（Ｏ）を満たす有理関数ｆｐにＰｉとＱｉを代入した結果とするときに、
複数の（Ｐｉ，Ｑｉ）の組を入力とし、ｅ（Ｐｉ，Ｑｉ）の積Πｅ（Ｐｉ，Ｑｉ）を出力するマルチペアリング演算方法において、
有理関数演算部で、divisor有理式の評価を行う演算でΠＦｉを計算し、繰り返し計算によって最終的なΠＦｉを求める有理関数演算過程
を含むことを特徴とするマルチペアリング演算方法。
【請求項１０】
請求項９記載のマルチペアリング演算方法であって、
前記有理関数演算過程からの出力に対して、べき乗演算部で、べき乗有限体演算を行うべき乗有限体演算過程
を含むことを特徴とするマルチペアリング演算方法。
【請求項１１】
請求項１０記載のマルチペアリング演算方法であって、
Millerのアルゴリズムに従う処理を行う前記有理関数演算過程
を含むことを特徴とするマルチペアリング演算方法。
【請求項１２】
請求項１０記載のマルチペアリング演算方法であって、
修正Duursma-Leeのアルゴリズムに従う処理を行う前記有理関数演算過程
を含むことを特徴とするマルチペアリング演算方法。
【請求項１３】
ｐは素数または素数のべき乗、ｋは偶数、ｉは１または２の整数、Ｐｉは有限体ＧＦ（ｐ）上の楕円曲線上の点、Ｑｉは有限体ＧＦ（ｐｋ）上の楕円曲線上の点、ｅ（Ｐｉ，Ｑｉ）はＰｉとＱｉのペアリング結果の有限体ＧＦ（ｐｋ）上の元、Ｆｉは（ｆｐ）＝ｍ（Ｐ）−ｍ（Ｏ）を満たす有理関数ｆｐにＰｉとＱｉを代入した結果とするときに、
（Ｐ1，Ｑ１）と（Ｐ２，Ｑ２）を入力とし、ペアリング結果のｅ（Ｐ１，Ｑ１）とｅ（Ｐ２，Ｑ２）とが等しいかを判定するペアリング比較方法において、
マルチペアリング演算部で、（Ｐ１，Ｑ１）と（Ｐ２，−Ｑ２）を入力とし、divisor有理式の評価を行う演算でＦ１・Ｆ２を計算し、繰り返し計算によって最終的なＦ１・Ｆ２を求め、積ｅ（Ｐ１，Ｑ１）・ｅ（Ｐ２，−Ｑ２）を出力するマルチペアリング演算過程と、
ＧＦ（ｐｋ）比較部で、前記マルチペアリング演算過程の出力と１とを比較するＧＦ（ｐｋ）比較過程と
を含むことを特徴とするペアリング比較方法。
【請求項１４】
請求項１３記載のペアリング比較方法であって、
前記有理関数演算過程からの出力に対して、べき乗演算部でべき乗有限体演算を行う前記マルチペアリング演算過程
を含むことを特徴とするペアリング比較方法。
【請求項１５】
請求項１から８のいずれかに記載の装置をコンピュータにより実現するペアリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、楕円曲線上の演算、特にセキュリティ技術を実現するための演算を利用した装置、方法、およびプログラムに関する。
【背景技術】
【０００２】
楕円曲線のペアリングを用いたID-base暗号や短署名長デジタル署名を実現する方法が提案されている。楕円曲線のペアリングには、TateペアリングとWeilペアリングなどがある。
有限体ＧＦ（ｐ）上で定義される楕円をＥ／ＧＦ（ｐ）とする。楕円Ｅ／ＧＦ（ｐ）上のＧＦ（ｐ）有理点をＰ（ｘＰ、ｙＰ）、楕円Ｅ／ＧＦ（ｐ）上のＧＦ（ｐｋ）有理点をＱ（ｘＱ、ｙＱ）とする。TateペアリングとWeilペアリングなどでは、（ｆｐ）＝ｍ（Ｐ）−ｍ（Ｏ）を満たす有理関数ｆｐに、（Ｐ，Ｑ）を代入した結果を求める有理関数演算が利用される。この有理関数演算をdivisor有理式の評価を行う演算という。また、ＧＦ（ｐｋ）の元のべき乗や乗算に、ほとんどの処理時間を費やしている。以下の説明では、高速演算が実現しやすいTateペアリングを中心に説明する。
Tateペアリングによる暗号や署名の概要を図１に示す。Tateペアリングでは、ＰとＱを入力とし、Millerのアルゴリズムや修正Duursma-Leeのアルゴリズムなどのdivisor有理式の評価を行う演算によって、有限体ＧＦ（ｐｋ）上の元ｆを出力し、さらにべき乗演算によってｆを（ｐｋ−１）／ｍ乗することで有限体ＧＦ（ｐｋ）上の元ｅへ写像し、出力する。ここで、ｐは素数または素数のべき乗、ｍは素数かつＰ、Ｑ、ｅの位数、ｋはｍ｜（ｐｋ−１）を満足する最小の整数、ｍは（ｐ−１）の約数ではない、かつｐとｍの最大公約数は１である。
【０００３】
図２はTateペアリングを用いたペアリング演算装置１０００の機能構成例を示している。図１に示した処理を行うため、Millerアルゴリズムや修正Duursma-Leeのアルゴリズムなどを用いて、入力ＰとＱを有限体ＧＦ（ｐｋ）上の元ｆに変換して出力する有理関数演算装置１０と、べき乗演算によって入力ｆを有限体ＧＦ（ｐｋ）上の元ｅに写像して出力するべき乗演算装置２０から構成されている。
Tateペアリングでの演算量のほとんどを占める有理関数演算装置１０の代表的な例として、Millerのアルゴリズムを用いたMiller演算装置３０の内部構成例を図３に示す。また、処理フロー例を図４に示す。Miller演算装置３０は、制御部１００、代入部２００、楕円上点生成部４００、楕円加算部５００、入出力部６００、ＧＦ（ｐｋ）乗算部７００、ＧＦ（ｐｋ）逆元部８５０、および記録部１９０から構成される。制御部１００は、以下に示す処理フローに沿った処理を実行するために他の構成部を制御する。また、記録部１９０はハードディスク等の不揮発性のメモリでもよいし、一連の計算を行う間だけ一時的に記録する揮発性のメモリでもよい。また、組み合わせてもよい。
【０００４】
入出力部６００にｍ、Ｐ、Ｑが入力されると、ｍ、Ｐ、Ｑを記録部１９０に記録する（Ｓ７００）。次に代入部２００で、ＴにＰを、Ｆに１を代入し、記録部１９０に記録する（Ｓ７１０）。楕円上点生成部４００で、Ｓ≠ＰかつＳ≠Ｑの条件を満足する有限体ＧＦ（ｐｋ）上で定義される楕円上の点Ｓ（∈Ｅ／ＧＦ（ｐｋ））を生成し、記録部１９０に記録する（Ｓ７２０）。Ｓは条件を満足する点であれば、あらかじめ定めてもいいし、ランダムに生成してもよい。楕円加算部５００で、記録部１９０からＱとＳを読み取り、Ｑ’（＝Ｑ＋Ｓ）を計算し、記録部１９０に記録する（Ｓ７３０）。代入部２００で、ｌｏｇ（ｍ）−１の小数点以下を切り上げた整数をｎに代入し、記録部１９０に記録する（Ｓ７４０）。制御部１００は、記録部１９０からｎを読み取り、ｎ＜０か否かを確認し、Ｙｅｓの場合にはステップＳ９１０に進み、Ｎｏの場合にはステップＳ７６０に進む（Ｓ７５０）。Ｙｅｓの場合、入出力部６００は、記録部１９０からＦを読み取り、出力し（Ｓ９１０）、Millerアルゴリズムによる演算が終了する。Ｎｏの場合、楕円加算部５００は、記録部１９０からＴを読み取り、２Ｔを計算し、記録部１９０に記録する（Ｓ７６０）。ＧＦ（ｐｋ）乗算部７００は、Ｑ’、Ｓ、Ｔ、２Ｔを記録部１９０から読み取り、ｌ１（ｘ，ｙ）＝０をＴと２Ｔとを結ぶ直線、ｌ２（ｘ，ｙ）＝０を２ＴとＯとを結ぶ直線として、ｌ１（Ｑ’）、ｌ２（Ｑ’）、ｌ１（Ｓ）、ｌ２（Ｓ）を計算し、記録部１９０に記録する（Ｓ７７０）。ただし、ｌ１（Ｑ’）とは、Ｑ’のｘ座標とｙ座標とを、ｌ１（ｘ，ｙ）に代入した値である。なお、Ｓを有限体ＧＦ（ｐ）の元から選定すると（この場合、残りのｋ−１個の有限体ＧＦ（ｐ）の元は０である。）、ｌ１（Ｓ）、ｌ２（Ｓ）の計算は省略でき、以降のステップでｌ１（Ｓ）、ｌ２（Ｓ）を省略できる。次に、代入部２００は、記録部１９０から２Ｔを読み取り、Ｔに２Ｔの値を代入し、Ｔを記録部１９０に記録する（Ｓ７８０）。ＧＦ（ｐｋ）逆元部８５０で、記録部１９０からｌ２（Ｑ’）、ｌ１（Ｓ）を読み取り、ｌ２（Ｑ’）−１、ｌ１（Ｓ）−１を計算し、記録部１９０に記録する（Ｓ７９０）。ＧＦ（ｐｋ）乗算部７００は、記録部１９０からＦ、ｌ１（Ｑ’）、ｌ２（Ｓ）、ｌ２（Ｑ’）−１、ｌ１（Ｓ）−１を読み取り、
【０００５】
【数１】
2006301513.tif 000003
を計算し、Ｆの値として記録部１９０に記録する（Ｓ８１０）。制御部１００は、記録部１９０からｍとｎを読み取り、ｍのｎ番目のビットが１かを確認し、Ｙｅｓの場合にはステップＳ８３０へ進み、Ｎｏの場合にはステップＳ９００へ進む（Ｓ８２０）。Ｙｅｓの場合、楕円加算部５００で、記録部１９０からＴ、Ｐを読み取り、Ｔ＋Ｐを計算し、記録部１９０に記録する（Ｓ８３０）。ＧＦ（ｐｋ）乗算部７００は、Ｑ’、Ｓ、Ｔ、Ｐ，Ｔ＋Ｐを記録部１９０から読み取り、ｌ１（ｘ，ｙ）＝０をＴとＰとを結ぶ直線、ｌ２（ｘ，ｙ）＝０をＴ＋ＰとＯとを結ぶ直線とし、ｌ１（Ｑ’）、ｌ２（Ｑ’）、ｌ１（Ｓ）、ｌ２（Ｓ）を計算して、記録部１９０に記録する（Ｓ８４０）。代入部２００は、記録部１９０からＴ＋Ｐを読み取り、ＴにＴ＋Ｐを代入し、Ｔを記録部１９０に記録する（Ｓ８５０）。ＧＦ（ｐｋ）逆元部８５０は、記録部１９０からｌ２（Ｑ’）、ｌ１（Ｓ）を読み取り、ｌ２（Ｑ’）−１、ｌ１（Ｓ）−１を計算し、記録部１９０に記録する（Ｓ８６０）。ＧＦ（ｐｋ）乗算部７００は、記録部１９０からＦ、ｌ１（Ｑ’）、ｌ２（Ｓ）、ｌ２（Ｑ’）−１、ｌ１（Ｓ）−１を読み取り、
【０００６】
【数２】
2006301513.tif 000004
を計算し、Ｆの値として記録部１９０に記録する（Ｓ８９０）。ステップＳ８２０でＮｏと判断した場合とステップＳ８９０が終了した場合、代入部２００は、記録部１９０からｎを読み取り、ｎ−１をｎに代入し、ｎを記録部１９０に記録する（Ｓ９００）。次にステップＳ７５０に戻り、ステップＳ７５０の判断がＹｅｓとなるまで処理が繰り返される。
【０００７】
なお、Millerのアルゴリズムでは、ステップS８１０とS８８０とが、演算量の多い処理である。以下では、ステップS８１０やS８８０のように、Ｆの値を用いて計算した結果をＦに代入するステップを、「Ｆの更新演算」という。
有理関数演算装置１０の代表的なもう１つの例として、修正Duursma-Leeのアルゴリズムを用いた修正Duursma-Lee演算装置４０の内部構成例を図５に示す。また、その処理フロー例を図６に示す。修正Duursma-Lee演算装置４０は、制御部１１０、代入部２１０、ＧＦ（ｐ）乗算部３１０、ＧＦ（ｐｋ）乗算部４１０、ＧＦ（ｐｋ）べき乗演算部５１０、入出力部６１０、および記録部７１０から構成される。制御部１１０は、以下に示す処理フローに沿った処理を実行するために、他の構成部を制御する。また、記録部７１０はハードディスク等の不揮発性のメモリでもよいし、一連の計算を行う間だけ一時的に記録する揮発性のメモリでもよい。また、組み合わせてもよい。
【０００８】
修正Duursma-Leeでは、ｚは６との最大公約数が１となる正の整数、ｐは３ｚ、楕円曲線Ｅを表す式をｙ２＝ｘ３＋ａＸ＋ｂ、ただしｂは±１とする。また、σは有限体ＧＦ（ｐ６）上の元であり、かつ有限体ＧＦ（ｐ）上の２次既約多項式ｆ（ｘ）の根である。ρは有限体ＧＦ（ｐ６）上の元であり、かつ有限体ＧＦ（ｐ）上の３次既約多項式ｇ（ｘ）の根である。σとρとは、前記の条件を満足する値であり、あらかじめ定めて記録部７１０に記録される。
入出力部６１０にｚ、Ｐ（ｘＰ，ｙＰ）、Ｑ（ｘＱ，ｙＱ）が入力されると、ｚ、Ｐ、Ｑを記録部７１０に記録する（Ｓ９２０）。次に代入部２１０で、ｎにｚ−１を、Ｆに１を、ｄにｚｂを代入し、記録部７１０に記録する。また、ＧＦ（ｐｋ）べき乗演算部５１０では、記録部７１０からｘＱとｙＱを読み出し、ｘＱ３とｙＱ３を計算し、代入部２１０でｘＱにｘＱ３を、ｙＱにｙＱ３を代入し、記録部７１０に記録する（Ｓ９３０）。ＧＦ（ｐ）乗算部３１０では、記録部７１０からｘＰとｙＰを読み出し、ｘP9とｙP9が計算され、代入部２１０でｘPにｘP９を、ｙPにｙP９を代入し、記録部７１０に記録する（Ｓ９４０）。次に制御部１１０では、記録部７１０からｘＰ，ｙＰ，ｘＱ，ｙＱ，ｄ，σを読み出し、μ＝ｘP＋ｘＱ＋ｄ、γ＝σｙPｙＱ−μ２を記録部７１０に記録する（Ｓ９５０）。ＧＦ（ｐｋ）乗算部４１０では、記録部７１０からＦ，γ，μ，ρを読み出し、Ｆ３（γ−μρ−ρ２）を計算し、代入部２１０でＦにＦ３（γ−μρ−ρ２）を代入し、記録部７１０に記録する（Ｓ９６０）。次に代入部２１０で、ｙＱに−ｙＱを、ｄにｄ−ｂを代入し、記録部７１０に記録する（Ｓ９７０）。さらに、代入部２１０でｎにｎ−１を代入し、記録部７１０に記録する（Ｓ９８０）。ｎ＞０ならばステップＳ９４０に戻り、違う場合はステップＳ１０００に進む（Ｓ９９０）。ステップＳ１０００では、記録部７１０に記録されているＦを出力する（Ｓ１０００）。
【０００９】
なお、修正Duursma-Leeのアルゴリズムでは、ステップS９６０が、Ｆの更新演算であり、演算量が多い。
Millerのアルゴリズムの高速化に関しては特許文献１、修正Duursma-Leeのアルゴリズムに関しては非特許文献１などの提案がある。しかし、これらの提案は、単一のペアリング演算を高速化することを目的としている。したがって、複数のペアリング演算結果を乗じたもの（「マルチペアリング」という。）を求める場合には、それぞれのペアリング演算を行った上で、各ペアリング演算の結果を乗じなければならない。したがって、従来の方法では、次のような構成と手順となる。図７に従来のマルチTateペアリング演算装置２０００の機能構成例を示す。また、処理フローを図８に示す。マルチTateペアリング演算装置２０００は、Millerのアルゴリズムや修正Duursma-Leeのアルゴリズムなどの演算を行う有理関数演算装置１０、べき乗演算装置２０、および乗算装置２５から構成される。マルチペアリングを行う対象である、複数の有限体ＧＦ（ｐ）上の楕円曲線上の点Ｐｉと有限体ＧＦ（ｐｋ）上の楕円曲線上の点Ｑｉとの組（Ｐｉ，Ｑｉ）が、マルチTateペアリング演算装置に入力される（Ｓ１０１０）。ただし、ｉ＝１，…，Ｉ（Ｉは２以上の整数）とする。まずｉに１を代入する（Ｓ１０２０）。有理関数演算装置１０では個別の入力の組（Ｐｉ，Ｑｉ）ごとに演算を行い（Ｓ１０３０）、演算結果をべき乗演算装置２０でべき乗演算し、個々のペアリングｅ（Ｐｉ，Ｑｉ）を得る（Ｓ１０４０）。この処理をＩ回行い（Ｓ１０５０、Ｓ１０６０）、乗算装置２５でΠｅ（Ｐｉ，Ｑｉ）を計算する（Ｓ１０７０）ことで、マルチペアリング結果が得られる。
【特許文献１】特開2004-177673号公報
【非特許文献１】P.Barreto, H.Kim, B.Lynn and M.Scott, “Efficient Algorithm for Pairing-Based Cryptosystems,” Advances in Cryptology - Crypto 2002, LNCS 2442, Springer-Verlag, pp.354-368 (2002).
【発明の開示】
【発明が解決しようとする課題】
【００１０】
楕円曲線のマルチペアリングの演算量を少なくし、マルチペアリング方法およびペアリング比較方法の高速化を図る。
【課題を解決するための手段】
【００１１】
本発明は、複数の有限体ＧＦ（ｐ）上の楕円曲線上の点Ｐｉと有限体ＧＦ（ｐｋ）上の楕円曲線上の点Ｑｉとの組（Ｐｉ，Ｑｉ）を入力とし、有限体ＧＦ（ｐｋ）上の元ｅ（Ｐｉ，Ｑｉ）の積Πｅ（Ｐｉ，Ｑｉ）を出力するマルチペアリング演算方法に関する。ここで、ｐは素数または素数のべき乗、ｋは偶数、Ｉは２以上の整数、ｉは１からＩの整数である。（ｆｐ）＝ｍ（Ｐ）−ｍ（Ｏ）を満たす有理関数ｆｐに前記の入力の組（Ｐｉ，Ｑｉ）を代入した結果をＦｉとすると、本発明では、個別のＦｉを求めるのではなく、divisor有理式の評価を行う演算で直接ΠＦｉを求める。この際に、ｉ＝１，…，Ｉで共通の演算を１回で行うことができる。また、マルチTateペアリングでは、前記のΠＦｉにべき乗演算を行い、マルチペアリングの結果を得る。
【００１２】
さらに、もう１つの発明は、ペアリングの結果である有限体ＧＦ（ｐｋ）上の２つの元ｅ（Ｐ１，Ｑ１）とｅ（Ｐ２，Ｑ２）とが等しいかを判定するペアリング比較方法に関する。この発明では、（Ｐ１，Ｑ１）と（Ｐ２，−Ｑ２）を入力とし、積ｅ（Ｐ１，Ｑ１）・ｅ（Ｐ２，−Ｑ２）を出力するマルチペアリング演算を行い、前記マルチペアリング演算の結果と１とを比較することで、ｅ（Ｐ１，Ｑ１）とｅ（Ｐ２，Ｑ２）とが等しいことを確認する。
【発明の効果】
【００１３】
本発明によれば、複数の楕円曲線上のペアリング演算結果を乗算する場合に、共通する演算であり、かつ演算量の多い演算を、まとめて行うことができる。また、マルチTateペアリングの場合には、個別にべき乗計算した後に乗算するのではなく、乗算した上でべき乗することができる。したがって、乗算に比べて演算量の多いべき乗計算の回数を少なくすることができ、演算量を大幅に削減することができる。
また、ペアリング結果を比較する場合には、前記のマルチペアリング演算方法を利用し、一方のペアリング結果の逆数とのマルチペアリング演算結果を１と比較することで、２つのペアリングが等しいことを確認できる。したがって、認証などで使用するペアリング結果の比較でも、演算量を大幅に削減することができる。
【発明を実施するための最良の形態】
【００１４】
以下に本発明の実施形態を説明する。なお、説明の重複を避けるため、同一の機能を有する構成部には同じ番号を付して重複説明を省略する。
［第１実施形態］
図９に本発明のマルチTateペアリング演算装置の機能構成例を示す。また、その処理フローを図１０に示す。マルチTateペアリング演算装置３０００は、有理演算装置５０とべき乗演算装置２０から構成される。有理演算装置５０は、Millerアルゴリズムや修正Duursma-Leeのアルゴリズムなどを用いて、複数の入力の組（Ｐｉ，Ｑｉ）をΠＦｉに変換する装置である。ただし、ｉ＝１，…，Ｉ（Ｉは２以上の整数）、Ｐｉは有限体ＧＦ（ｐ）上の楕円曲線上の点、Ｑｉは有限体ＧＦ（ｐｋ）上の楕円曲線上の点、ＦｉはMillerアルゴリズムや修正Duursma-Leeのアルゴリズムなどを用いてＰｉとＱｉとが変換される有限体ＧＦ（ｐｋ）上の元である。従来技術では、有理演算装置１０が個別のＦｉを出力し、べき乗演算装置２０がべき乗演算を行って個別のペアリング結果ｅ（Ｐｉ，Ｑｉ）を求め、その後で乗算装置２５で乗算を行ってマルチペアリングΠｅ（Ｐｉ，Ｑｉ）を求めた（図７，８参照）。一方、本発明では、Ｐｉ，Ｑｉが入力されると（Ｓ１０）、有理演算装置５０で個別のＦｉを求めることなく、ΠＦｉを出力し（Ｓ２０）、べき乗演算装置２０でΠＦｉを（（ｐｋ−１）／ｍ）乗して、マルチペアリングΠｅ（Ｐｉ，Ｑｉ）を求める。
【００１５】
本発明の第１の特徴は、後述するdivisor有理式の評価を行う演算を行う有理演算装置５０である。有理演算装置５０では、個別のＦｉを求めることなく、ΠＦｉを求めることで演算量を削減している。この方法は、Tateペアリングに限らず、Weilペアリングなどの他のアルゴリズムでマルチペアリングを行う場合にも用いることができる。第２の特徴はTateペアリング特有の特徴であって、個別にＦｉのべき乗演算するのではなく、ΠＦｉに対してべき乗計算することである。言い換えると、Millerのアルゴリズムの場合には、Ｆｉを（（ｐｋ−１）／ｍ）乗した後で乗算するのではなく、各Ｆｉを乗算した後で（（ｐｋ−１）／ｍ）乗している。また、修正Duursma-Leeのアルゴリズムの場合には、Ｆｉを（ｐ３−１）乗した後で乗算するのではなく、各Ｆｉを乗算した後で（ｐ３−１）乗している。このことによって、演算量の多いべき乗計算を、Ｉ回から１回に削減できる。
【００１６】
以下に第１の特徴である有理関数演算装置５０とステップＳ２０の詳細について説明する。
図１１に、有理関数演算装置５０のアルゴリズムとして、Millerのアルゴリズムを用いたMiller演算装置６０の機能構成例を示す。また、その処理フローを図１２に示す。Miller演算装置６０は、制御部１０１、代入部２００、楕円上点生成部４００、楕円加算部５００、入出力部６０１、ＧＦ（ｐｋ）乗算部７００、ＧＦ（ｐｋ）逆元部８５０、および記録部１９１から構成される。図３に示した従来のMiller演算装置３０とは、制御部、入出力部と記録部が異なる。これは、処理フロー、入力データ、記録するデータが異なるためである。
【００１７】
入出力部６０１にｍ、Ｐｉ、Ｑｉが入力されると、ｍ、Ｐｉ、Ｑｉを記録部１９１に記録する（Ｓ１００）。楕円上点生成部４００で、Ｓ≠ＰかつＳ≠Ｑの条件を満足する有限体ＧＦ（ｐｋ）上で定義される楕円上の点Ｓ（∈Ｅ／ＧＦ（ｐｋ））を生成し、記録部１９１に記録する（Ｓ１１０）。Ｓは条件を満足する点であれば、あらかじめ定めてもよいし、ランダムに生成してもよい。次に代入部２００で、ｉに１を、Ｆに１を代入し、記録部１９１に記録する（Ｓ１２０）。また、代入部２００で、ＴｉにＰｉを代入し、記録部１９１に記録する（Ｓ１３０）。楕円加算部５００では、記録部１９１からＱｉとＳを読み取り、Ｑｉ’（＝Ｑｉ＋Ｓ）を計算し、記録部１９１に記録する（Ｓ１４０）。ステップ１３０とステップ１４０の処理をｉ＝１，…，Ｉに対して繰り返し行う（Ｓ１５０、Ｓ１６０）。代入部２００で、ｌｏｇ（ｍ）−１の小数点以下を切り上げた整数をｎに代入し、記録部１９１に記録する（Ｓ１７０）。制御部１０１は、記録部１９１からｎを読み取り、ｎ＜０か否かを確認し、Ｙｅｓの場合にはステップＳ３７０に進み、Ｎｏの場合にはステップＳ１９０に進む（Ｓ１８０）。Ｙｅｓの場合、入出力部６０１は、記録部１９１からＦを読み取り、出力し（Ｓ３７０）、Millerアルゴリズムによる演算が終了する。Ｎｏの場合、代入部２００は、ｉに１を代入し、記録部１９１に記録する（Ｓ１９０）。楕円加算部５００は、記録部１９１からＴｉを読み取り、２Ｔｉを計算し、記録部１９１に記録する（Ｓ２００）。ＧＦ（ｐｋ）乗算部７００は、Ｑｉ’、Ｓ、Ｔｉ、２Ｔｉを記録部１９１から読み取り、ｌ１ｉ（ｘ，ｙ）＝０をＴｉと２Ｔｉとを結ぶ直線、ｌ２ｉ（ｘ，ｙ）＝０を２ＴｉとＯとを結ぶ直線として、ｌ１ｉ（Ｑｉ’）、ｌ２ｉ（Ｑｉ’）、ｌ１ｉ（Ｓ）、ｌ２ｉ（Ｓ）を計算し、記録部１９１に記録する（Ｓ２１０）。ただし、ｌ１ｉ（Ｑｉ’）とは、Ｑｉ’のｘ座標とｙ座標とを、ｌ１ｉ（ｘ，ｙ）に代入した値である。なお、Ｓを有限体ＧＦ（ｐ）の元から選定すると（この場合、残りのｋ−１個の有限体ＧＦ（ｐ）の元は０である。）、ｌ１ｉ（Ｓ）、ｌ２ｉ（Ｓ）の計算は省略でき、以降のステップでもｌ１ｉ（Ｓ）、ｌ２ｉ（Ｓ）を省略できる。次に、代入部２００は、記録部１９１から２Ｔｉを読み取り、Ｔｉに２Ｔｉの値を代入し、Ｔｉを記録部１９１に記録する（Ｓ２２０）。ＧＦ（ｐｋ）逆元部８５０で、記録部１９１からｌ２ｉ（Ｑｉ’）、ｌ１ｉ（Ｓ）を読み取り、ｌ２ｉ（Ｑｉ’）−１、ｌ１ｉ（Ｓ）−１を計算し、記録部１９１に記録する（Ｓ２３０）。ステップＳ２００からＳ２３０までの処理をｉ＝１，…，Ｉまで繰り返す（Ｓ２４０、Ｓ２５０）。なお、図１２の処理フローでは、各ｉの値に対して、ステップＳ２００からＳ２３０を行い、次のｉの処理を行っている。しかし、ステップＳ２００をＩ回繰り返した後、ステップＳ２１０をＩ回繰り返すように、各ステップをＩ回繰り返しながら処理を進めてもよい。ＧＦ（ｐｋ）乗算部７００は、記録部１９１からＦ、ｌ１ｉ（Ｑｉ’）、ｌ２ｉ（Ｓ）、ｌ２ｉ（Ｑｉ’）−１、ｌ１ｉ（Ｓ）−１を読み取り、
【００１８】
【数３】
2006301513.tif 000005
を計算し、Ｆの値として記録部１９１に記録する（Ｓ２６０）。なお、本ステップがＦの更新演算である。制御部１０１は、記録部１９１からｍとｎを読み取り、ｍのｎ番目のビットが１かを確認し、Ｙｅｓの場合にはステップＳ２８０へ進み、Ｎｏの場合にはステップＳ３６０へ進む（Ｓ２７０）。Ｙｅｓの場合、代入部２００は、ｉに１を代入し、記録部１９１に記録する（Ｓ２８０）。楕円加算部５００で、記録部１９１からＴｉ、Ｐｉを読み取り、Ｔｉ＋Ｐｉを計算し、記録部１９１に記録する（Ｓ２９０）。ＧＦ（ｐｋ）乗算部７００は、Ｑｉ’、Ｓ、Ｔｉ、Ｐｉ，Ｔｉ＋Ｐｉを記録部１９１から読み取り、ｌ１ｉ（ｘ，ｙ）＝０をＴｉとＰｉとを結ぶ直線、ｌ２ｉ（ｘ，ｙ）＝０をＴｉ＋ＰｉとＯとを結ぶ直線とし、ｌ１ｉ（Ｑｉ’）、ｌ２ｉ（Ｑｉ’）、ｌ１ｉ（Ｓ）、ｌ２ｉ（Ｓ）を計算して、記録部１９１に記録する（Ｓ３００）。代入部２００は、記録部１９１からＴｉ＋Ｐｉを読み取り、ＴｉにＴｉ＋Ｐｉを代入し、Ｔｉを記録部１９１に記録する（Ｓ３１０）。ＧＦ（ｐｋ）逆元部８５０は、記録部１９１からｌ２ｉ（Ｑｉ’）、ｌ１ｉ（Ｓ）を読み取り、ｌ２ｉ（Ｑｉ’）−１、ｌ１ｉ（Ｓ）−１を計算し、記録部１９１に記録する（Ｓ３２０）。ステップＳ２９０からＳ３２０までの処理をｉ＝１，…，Ｉまで繰り返す（Ｓ３３０、Ｓ３４０）。なお、図１２の処理フローでは、各ｉの値に対して、ステップＳ２９０からＳ３２０を行い、次のｉの処理を行っている。しかし、ステップＳ２９０をＩ回繰り返した後、ステップＳ３００をＩ回繰り返すように、各ステップをＩ回繰り返しながら処理を進めてもよい。ＧＦ（ｐｋ）乗算部７００は、記録部１９１からＦ、ｌ１ｉ（Ｑｉ’）、ｌ２ｉ（Ｓ）、ｌ２ｉ（Ｑｉ’）−１、ｌ１ｉ（Ｓ）−１を読み取り、
【００１９】
【数４】
2006301513.tif 000006
を計算し、Ｆの値として記録部１９１に記録する（Ｓ３５０）。なお、本ステップもＦの更新演算である。ステップＳ２７０でＮｏと判断した場合とステップＳ３５０が終了した場合、代入部２００は、記録部１９１からｎを読み取り、ｎ−１をｎに代入し、ｎを記録部１９１に記録する（Ｓ３６０）。次にステップＳ１８０に戻り、ステップＳ１８０の判断がＹｅｓとなるまで処理が繰り返される。なお、出力されたＦが、ΠＦｉの値となっている。このように、Ｆの更新演算（ステップＳ２６０、Ｓ３５０）で、おのおののＦｉを求めることなく、Ｆ（＝ΠＦｉ）を求めることが特徴である。
【００２０】
Ｉ個の入力の組み（Ｐｉ，Ｑｉ）を個別にMillerのアルゴリズムで演算した場合、図７、図８に示した従来の構成では、演算量の多いＦの更新演算（図４のステップＳ８１０、Ｓ８８０）をｎＩ回行うことになる。一方、本発明によれば、演算量の多いＦの更新演算（図１２のステップＳ２６０、Ｓ３５０）をｎ回行うだけでよい。したがって、演算量を大幅に削減することができる。
［変形例］
第１実施形態では、Millerのアルゴリズムを用いた場合を説明したが、変形例として、有理関数演算装置５０に修正Duursma-Leeのアルゴリズムを用いた場合を以下に説明する。
【００２１】
図９の有理関数演算装置５０の変わりに、図１３の修正Duursma-Lee演算装置７０を用いる。図１４に修正Duursma-Lee演算装置７０の処理フローを示す。修正Duursma-Lee演算装置７０は、制御部１１１、代入部２１０、ＧＦ（ｐ）乗算部３１０、ＧＦ（ｐｋ）乗算部４１０、ＧＦ（ｐｋ）べき乗演算部５１０、入出力部６１１、および記録部７１１から構成される。図５に示した修正Duursma-Lee演算装置４０との違いは、制御部、入出力部、記録部である。これは、処理手順、入力データ、記録データが異なるためである。
従来技術と同様に、ｚは６との最大公約数が１となる正の整数、ｐは３ｚ、楕円曲線Ｅを表す式をｙ２＝ｘ３＋ａＸ＋ｂ、ただしｂは±１である。また、σは有限体ＧＦ（ｐ６）上の元であり、かつ有限体ＧＦ（ｐ）上の２次既約多項式ｆ（ｘ）の根である。ρは有限体ＧＦ（ｐ６）上の元であり、かつ有限体ＧＦ（ｐ）上の３次既約多項式ｇ（ｘ）の根である。σとρとは、前記の条件を満足する値であり、あらかじめ定めて記録部７１１に記録される。
【００２２】
入出力部６１１にｚ、Ｐ（ｘＰｉ，ｙＰｉ）、Ｑ（ｘＱｉ，ｙＱｉ）が入力されると、ｚ、Ｐｉ、Ｑｉを記録部７１０に記録する（Ｓ４００）。ただし、ｉ＝１，…，Ｉ（Ｉは２以上の整数）である。代入部２１０で、ｎにｚ−１を、Ｆに１を、ｄにｚｂを代入し、記録部７１１に記録する（Ｓ４１０）。次に代入部２１０で、ｉに１を代入し、記録部７１１に記録する（Ｓ４２０）。ＧＦ（ｐｋ）べき乗演算部５１０では、記録部７１１からｘＱｉとｙＱｉを読み出し、ｘＱｉ３とｙＱｉ３を計算し、代入部２１０でｘＱｉにｘＱｉ３を、ｙＱｉにｙＱｉ３を代入し、記録部７１１に記録する（Ｓ４３０）。ステップＳ４３０は、ｉが１，…，Ｉまで繰り返す（Ｓ４４０、Ｓ４５０）。代入部２１０で、ｉに１を代入し、記録部７１１に記録する（Ｓ４６０）。ＧＦ（ｐ）乗算部３１０では、記録部７１０からｘＰｉとｙＰｉを読み出し、ｘPｉ9とｙPｉ9が計算され、代入部２１０でｘPｉにｘPｉ９を、ｙPｉにｙPｉ９を代入し、記録部７１１に記録する（Ｓ４７０）。次に制御部１１１では、記録部７１１からｘＰｉ，ｙＰｉ，ｘＱｉ，ｙＱｉ，ｄ，σを読み出し、μｉ＝ｘPｉ＋ｘＱｉ＋ｄ、γｉ＝σｙPｉｙＱｉ−μｉ２とて記録部７１１に記録する（S４８０）。ステップＳ４７０とＳ４８０とは、ｉ＝１，…，Ｉまで繰り返す（Ｓ４９０、Ｓ５００）。なお、図１４の処理フローでは、各ｉの値に対して、ステップＳ４７０とＳ４８０を行い、次のｉの処理を行っている。しかし、ステップＳ４７０をＩ回繰り返した後、ステップＳ４８０をＩ回繰り返してもよい。ＧＦ（ｐｋ）乗算部４１０では、記録部７１１からＦ，γｉ，μｉ，ρを読み出し、Ｆ３Π（γｉ−μｉρ−ρ２）を計算し、代入部２１０でＦにＦ３Π（γｉ−μｉρ−ρ２）を代入し、記録部７１１に記録する（Ｓ５１０）。なお、ステップＳ５１０が、Ｆの更新演算である。再度、代入部２１０で、ｉに１を代入し、記録部７１１に記録する（Ｓ５２０）。代入部２１０で、記録部７１１からｙＱｉを読み出し、ｙＱｉに−ｙＱｉを代入し、記録部７１１に記録する（Ｓ５３０）。ステップＳ５３０は、ｉ＝１，…，Ｉまで繰り返す（Ｓ５４０、Ｓ５５０）。さらに、代入部２１０で、記録部７１１からｄ，ｂ，ｎを読み出し、ｄにｄ−ｂを、ｎにｎ−１を代入し、記録部７１１に記録する（Ｓ５６０）。ｎ＞０ならばステップＳ４６０に戻り、違う場合はステップＳ５８０に進む（Ｓ５７０）。ステップＳ５７０では、入出力部６１１が、記録部７１１に記録されているＦを出力する（Ｓ５８０）。なお、出力されたＦが、ΠＦｉの値となっている。このように、Ｆの更新演算（ステップＳ５１０）で、おのおののＦｉを求めることなく、Ｆ（＝ΠＦｉ）を求めることが特徴である。
【００２３】
Ｉ個の入力の組み（Ｐｉ，Ｑｉ）を個別にMillerのアルゴリズムで演算した場合、図７、図８に示した従来の構成では、演算量の多いＦの更新演算（図６のステップＳ９６０）をｎＩ回行うことになる。一方、本発明によれば、演算量の多いＦの更新演算（図１４のステップＳ５１０）をｎ回行うだけでよい。したがって、演算量を大幅に削減することができる。
［第２実施形態］
第１実施形態では、マルチペアリング方法とその装置について説明したが、本実施形態では、第１実施形態で示したマルチペアリング装置を用いた応用例として、ペアリング比較装置を示す。図１５にペアリング比較装置の構成例を、図１６にその処理フローを示す。ペアリング比較装置４０００は、マルチTateペアリング演算装置３０００、入力生成装置３０１０、ＧＦ（ｐｋ）比較装置３０２０から構成される。マルチTateペアリング演算装置３０００は、図９に示したマルチTateペアリング演算装置３０００である。
【００２４】
２つのペアリング結果ｅ（Ｐ１，Ｑ１）とｅ（Ｐ２，Ｑ２）との比較を行う場合の処理フローを以下に示す。Ｐ１，Ｑ１，Ｐ２，Ｑ２をペアリング比較装置４０００が受け取ると（Ｓ６００）、入力生成装置３０１０が、−Ｑ２を求め、Ｐ１，Ｑ１，Ｐ２，−Ｑ２をマルチTateペアリング演算装置３０００に入力する（Ｓ６１０）。マルチTateペアリング演算装置３０００では、ｅ（Ｐ１，Ｑ１）・ｅ（Ｐ２，−Ｑ２）を計算し、出力する（Ｓ６２０）。ここで、ペアリングの特性から、ｅ（Ｐ２，−Ｑ２）は、ｅ（Ｐ２，Ｑ２）の逆数となっている。したがって、ｅ（Ｐ１，Ｑ１）・ｅ（Ｐ２，−Ｑ２）が１に等しければ、ｅ（Ｐ１，Ｑ１）とｅ（Ｐ２，Ｑ２）とは等しいことになる。そこで、ＧＦ（ｐｋ）比較装置３０２０では、マルチTateペアリング演算装置３０００が出力したｅ（Ｐ１，Ｑ１）ｅ（Ｐ２，−Ｑ２）と１とを比較する（Ｓ６３０）。ペアリング比較装置４０００は、ステップＳ６３０の結果が等しければ、ｅ（Ｐ１，Ｑ１）とｅ（Ｐ２，Ｑ２）とは等しいことを出力し、等しくなければ、等しくないことを出力する。
【００２５】
このように、２つのペアリング結果が等しいか否かの確認方法としても、本発明のマルチペアリング方法が使用できる。したがって、２つのペアリングを比較するような認証装置内部に、本実施形態のペアリング比較装置を組み込むことで、演算量を削減することができる。
なお、本実施形態ではマルチTateペアリング演算装置を用いたペアリング比較装置を説明したが、マルチペアリング演算装置であれば、Weilペアリングなどの他のアルゴリズムを用いてもよい。
【００２６】
また、第１実施形態および第２実施形態で示した各装置は、読み取り可能な記録媒体に記録したプログラムを、コンピュータで読み取り、実行してもよい。
【図面の簡単な説明】
【００２７】
【図１】Tateペアリングによる暗号や署名の概要を示す図。
【図２】Tateペアリングを用いたペアリング演算装置の機能構成例を示す図。
【図３】従来のMiller演算装置の内部構成例を示す図。
【図４】従来のMiller演算装置の処理フローを示す図。
【図５】従来の修正Duursma-Lee演算装置の内部構成例を示す図。
【図６】従来の修正Duursma-Lee演算装置の処理フローを示す図。
【図７】従来のマルチTateペアリング演算装置の機能構成例を示す図。
【図８】従来のマルチTateペアリング演算装置の処理フローを示す図。
【図９】本発明のマルチTateペアリング演算装置の機能構成例を示す図。
【図１０】本発明のマルチTateペアリング演算装置の処理フローを示す図。
【図１１】本発明のMiller演算装置の内部構成例を示す図。
【図１２】本発明のMiller演算装置の処理フローを示す図。
【図１３】本発明の修正Duursma-Lee演算装置の内部構成例を示す図。
【図１４】本発明の修正Duursma-Lee演算装置の処理フローを示す図。
【図１５】本発明のペアリング比較装置の構成例を示す図。
【図１６】本発明のペアリング比較装置の処理フローを示す図。
【図１】
2006301513.tif 000007
【図２】
2006301513.tif 000008
【図３】
2006301513.tif 000009
【図４】
2006301513.tif 000010
【図５】
2006301513.tif 000011
【図６】
2006301513.tif 000012
【図７】
2006301513.tif 000013
【図８】
2006301513.tif 000014
【図９】
2006301513.tif 000015
【図１０】
2006301513.tif 000016
【図１１】
2006301513.tif 000017
【図１２】
2006301513.tif 000018
【図１３】
2006301513.tif 000019
【図１４】
2006301513.tif 000020
【図１５】
2006301513.tif 000021
【図１６】
2006301513.tif 000022