(57)【特許請求の範囲】
【請求項１】
標数２及び拡大次数ｍの第１有限体Ｆ2m上で定義される楕円曲線上のペアリング対象データから点データｆを計算した後、前記点データｆの(２2m−１)(２m−２(m+1)/2＋１)乗を計算する最終べき処理を実行し、この最終べき処理の計算結果を出力するペアリング計算装置であって、
前記第１有限体Ｆ2m上の四則演算、二乗算及びべき乗演算を実行するための第１有限体Ｆ2m演算手段と、
標数２、拡大次数ｍ及び埋め込み次数４の第２有限体Ｆ24m上の四則演算及び二乗算を実行するための第２有限体Ｆ24m演算手段と、
前記第１有限体Ｆ2mの元a0,a1,a2,a3及び前記第２有限体Ｆ24mの各基底s,t,stに基づいて、前記第２有限体Ｆ24mの任意元Ａの２m乗Ａ^(2m)をＡ^(2m)＝a0＋a1s^(2m)＋a2t^(2m)＋a3(st)^(2m)と計算可能な場合（但し、^は べき乗を表す符号）、予め前記拡大次数ｍと、前記各基底の２m乗s^(2m),t^(2m),(st)^(2m)とを互いに関連付けて記憶した基底べき乗記憶手段と、
前記点データｆを前記任意元Ａとした場合の当該任意元Ａの２2m乗を計算するように、前記基底べき乗記憶手段、前記第１有限体Ｆ2m演算手段及び前記第２有限体Ｆ24m演算手段を制御する第１計算制御手段と、
前記点データｆを前記任意元Ａとした場合の当該任意元Ａの逆元Ａ-1を計算するように、前記基底べき乗記憶手段、前記第１有限体Ｆ2m演算手段及び前記第２有限体Ｆ24m演算手段を制御する第２計算制御手段と、
前記第１計算制御手段により得られた計算結果Ａ^(22m)及び前記第２計算制御手段により得られた逆元Ａ-1に基づいて、途中結果Ｂ＝Ａ^(22m)・Ａ-1＝Ａ^(22m-1)を計算するように、前記第１有限体Ｆ2m演算手段及び前記第２有限体Ｆ24m演算手段を制御する第３計算制御手段と、
前記途中結果Ｂの逆元Ｂ-1をＢ-1＝Ｂ^(22m)の関係式に基づいて計算するように、前記第１有限体Ｆ2m演算手段及び前記第２有限体Ｆ24m演算手段を制御する第４計算制御手段と、
前記第４計算制御手段により得られた逆元Ｂ-1に基づいて、前記途中結果Ｂの−２(m+1)/2乗を計算するように、前記第１有限体Ｆ2m演算手段及び前記第２有限体Ｆ24m演算手段を制御する第５計算制御手段と、
前記途中結果Ｂの２m乗を計算するように、前記第２有限体Ｆ24m演算手段を制御する第６計算制御手段と、
前記第６計算制御手段により得られた計算結果Ｂ^(2m)、前記第５計算制御手段により得られた計算結果Ｂ^(-2(m+1)/2)、及び前記途中結果Ｂに基づいて、前記途中結果Ｂの(2m-2(m+1)/2+1)乗を計算するように、前記第１有限体Ｆ2m演算手段及び前記第２有限体Ｆ24m演算手段を制御する第７計算制御手段と、
前記第７計算制御手段により得られた計算結果Ｂ^(2m-2(m+1)/2+1)を前記最終べき処理の計算結果ｆ^{(22m-1)(2m-2(m+1)/2+1)}として出力する手段と、
を備えたことを特徴とするペアリング計算装置。
【請求項２】
標数ｐ及び拡大次数ｍの第１有限体Ｆq（但し、ｑ＝ｐm）上で定義される楕円曲線をＥ(Ｆq)とし、前記楕円曲線の位数を＃Ｅ(Ｆq)とし、当該楕円曲線Ｅ(Ｆq)上のペアリング写像の集合を第２有限体Ｆqkとしたとき、前記楕円曲線Ｅ(Ｆq)上のペアリング対象データから点データｆを計算した後、前記点データｆの(ｑk−１)／＃Ｅ(Ｆq)乗を計算する最終べき処理を実行し、この最終べき処理の計算結果を出力するペアリング計算装置であって、
前記第１有限体Ｆq上の四則演算、二乗算及びべき乗演算を実行するための第１有限体Ｆq演算手段と、
前記第２有限体Ｆqk上の四則演算及び二乗算を実行するための第２有限体Ｆqk演算手段と、
前記第２有限体Ｆqkの部分体Ｆqk/i上の四則演算及び二乗算を実行するための部分体Ｆqk/i演算手段（但し、ｉはｋの因数）と、
前記第１有限体Ｆqの元a0,a1,a2,a3及び前記第２有限体Ｆqkの各基底s,t,stに基づいて、前記第２有限体Ｆqkの任意元Ａのｑ乗ＡqをＡq＝a0＋a1sq＋a2tq＋a3(st)qと計算可能な場合、予め前記拡大次数ｍと、前記各基底のｑ乗sq,tq,(st)qとを互いに関連付けて記憶した基底べき乗記憶手段と、
前記楕円曲線の位数＃Ｅ(Ｆq)、前記第１有限体Ｆqの位数ｑ、前記第２有限体Ｆqkの拡大次数ｋに基づいて、第１の関係＃Ｅ(Ｆq)｜（ｑk/2＋１）、又は第２の関係＃Ｅ(Ｆq)｜（ｑk/2−１）が成り立つか否かを判定する判定手段（但し、｜は、左辺が右辺を割り切ることを表す符号）と、
前記第１の関係＃Ｅ(Ｆq)｜（ｑk/2＋１）が成り立つ場合、前記点データｆを前記任意元Ａとした場合の当該任意元Ａのｑk/2乗を計算するように、前記基底べき乗記憶手段、前記第１有限体Ｆq演算手段及び前記第２有限体Ｆqk演算手段を制御する第１計算制御手段と、
前記点データｆを前記任意元Ａとした場合の当該任意元Ａの逆元Ａ-1を計算するように、前記基底べき乗記憶手段、前記第１有限体Ｆq演算手段及び前記第２有限体Ｆqk演算手段を制御する第２計算制御手段と、
前記第１計算制御手段により得られた計算結果Ａ^(ｑk/2)及び前記第２計算制御手段により得られた逆元Ａ-1に基づいて、途中結果Ｂ＝Ａ^(qk/2)・Ａ-1＝Ａ^(qk/2-1)を計算するように、前記第１有限体Ｆq演算手段及び前記第２有限体Ｆqk演算手段を制御する第３計算制御手段（但し、＾は、べき乗を表す符号）と、
前記途中結果Ｂの逆元Ｂ-1をＢ-1＝Ｂ^(qk/2)の関係式に基づいて計算するように、前記第１有限体Ｆq演算手段及び前記第２有限体Ｆqk演算手段を制御する第４計算制御手段と、
前記逆元Ｂ-1及び前記途中結果Ｂに基づいて、前記任意元Ａの（ｑk−１）乗Ａ^(qk-1)を計算するように、前記第１有限体Ｆq演算手段及び前記第２有限体Ｆqk演算手段を制御する第５計算制御手段と、
前記第５計算制御手段により得られた計算結果Ａ^(qk-1)及び前記位数＃Ｅ（Ｆq）に基づいて、Ａ^｛{(qk-1)/#E(Fq)}を計算するように、前記第１有限体Ｆq演算手段及び前記第２有限体Ｆqk演算手段を制御する第６計算制御手段と、
前記第２の関係＃Ｅ(Ｆq)｜（ｑk/2−１）が成り立つ場合、前記＃Ｅ(Ｆq)｜（ｑk/2−１）の因数に含まれる（ｑ(i-1)k/i＋ｑ(i-2)k/i＋…＋ｑk/i＋１）に基づき、前記任意元Ａの（ｑ(i-1)k/i＋ｑ(i-2)k/i＋…＋ｑk/i＋１）乗を計算するように、前記第１有限体Ｆq演算手段及び前記第２有限体Ｆqk演算手段を制御する第７計算制御手段と、
前記第７計算制御手段により得られた計算結果Ａ^(q(i-1)k/i+q(i-2)k/i+…+qk/i+1)に基づき、Ａ^｛{(qk-1)/#E(Fq)}を計算するように、前記第１有限体Ｆq演算手段及び前記部分体Ｆqk/i演算手段を制御する第８計算制御手段と、
前記第６又は第８計算制御手段により得られた計算結果Ａ^{(qk-1)/#E(Fq)}を前記最終べき処理の計算結果ｆ^{(qk-1)/#E(Fq)}として出力する手段と、
を備えたことを特徴とするペアリング計算装置。
【請求項３】
標数２及び拡大次数ｍの第１有限体Ｆ2m上で定義される楕円曲線上のペアリング対象データから点データｆを計算した後、前記点データｆの(２2m−１)(２m−２(m+1)/2＋１)乗を計算する最終べき処理を実行し、この最終べき処理の計算結果を出力するペアリング計算装置のプログラムであって、
前記ペアリング計算装置を、
前記第１有限体Ｆ2m上の四則演算、二乗算及びべき乗演算を実行するための第１有限体Ｆ2m演算手段、
標数２、拡大次数ｍ及び埋め込み次数４の第２有限体Ｆ24m上の四則演算及び二乗算を実行するための第２有限体Ｆ24m演算手段、
前記第１有限体Ｆ2mの元a0,a1,a2,a3及び前記第２有限体Ｆ24mの各基底s,t,stに基づいて、前記第２有限体Ｆ24mの任意元Ａの２m乗Ａ^(2m)をＡ^(2m)＝a0＋a1s^(2m)＋a2t^(2m)＋a3(st)^(2m)と計算可能な場合（但し、^は べき乗を表す符号）、予め前記拡大次数ｍと、前記各基底の２m乗s^(2m),t^(2m),(st)^(2m)とを互いに関連付けて前記ペアリング計算装置の基底べき乗記憶手段に書き込む手段、
前記点データｆを前記任意元Ａとした場合の当該任意元Ａの２2m乗を計算するように、前記基底べき乗記憶手段、前記第１有限体Ｆ2m演算手段及び前記第２有限体Ｆ24m演算手段を制御する第１計算制御手段、
前記点データｆを前記任意元Ａとした場合の当該任意元Ａの逆元Ａ-1を計算するように、前記基底べき乗記憶手段、前記第１有限体Ｆ2m演算手段及び前記第２有限体Ｆ24m演算手段を制御する第２計算制御手段、
前記第１計算制御手段により得られた計算結果Ａ^(22m)及び前記第２計算制御手段により得られた逆元Ａ-1に基づいて、途中結果Ｂ＝Ａ^(22m)・Ａ-1＝Ａ^(22m-1)を計算するように、前記第１有限体Ｆ2m演算手段及び前記第２有限体Ｆ24m演算手段を制御する第３計算制御手段、
前記途中結果Ｂの逆元Ｂ-1をＢ-1＝Ｂ^(22m)の関係式に基づいて計算するように、前記第１有限体Ｆ2m演算手段及び前記第２有限体Ｆ24m演算手段を制御する第４計算制御手段、
前記第４計算制御手段により得られた逆元Ｂ-1に基づいて、前記途中結果Ｂの−２(m+1)/2乗を計算するように、前記第１有限体Ｆ2m演算手段及び前記第２有限体Ｆ24m演算手段を制御する第５計算制御手段、
前記途中結果Ｂの２m乗を計算するように、前記第２有限体Ｆ24m演算手段を制御する第６計算制御手段、
前記第６計算制御手段により得られた計算結果Ｂ^(2m)、前記第５計算制御手段により得られた計算結果Ｂ^(-2(m+1)/2)、及び前記途中結果Ｂに基づいて、前記途中結果Ｂの(2m-2(m+1)/2+1)乗を計算するように、前記第１有限体Ｆ2m演算手段及び前記第２有限体Ｆ24m演算手段を制御する第７計算制御手段、
前記第７計算制御手段により得られた計算結果Ｂ^(2m-2(m+1)/2+1)を前記最終べき処理の計算結果ｆ^{(22m-1)(2m-2(m+1)/2+1)}として出力する手段、
として機能させるためのプログラム。
【請求項４】
標数ｐ及び拡大次数ｍの第１有限体Ｆq（但し、ｑ＝ｐm）上で定義される楕円曲線をＥ(Ｆq)とし、前記楕円曲線の位数を＃Ｅ(Ｆq)とし、当該楕円曲線Ｅ(Ｆq)上のペアリング写像の集合を第２有限体Ｆqkとしたとき、前記楕円曲線Ｅ(Ｆq)上のペアリング対象データから点データｆを計算した後、前記点データｆの(ｑk−１)／＃Ｅ(Ｆq)乗を計算する最終べき処理を実行し、この最終べき処理の計算結果を出力するペアリング計算装置のプログラムであって、
前記ペアリング計算装置を、
前記第１有限体Ｆq上の四則演算、二乗算及びべき乗演算を実行するための第１有限体Ｆq演算手段、
前記第２有限体Ｆqk上の四則演算及び二乗算を実行するための第２有限体Ｆqk演算手段、
前記第２有限体Ｆqkの部分体Ｆqk/i上の四則演算及び二乗算を実行するための部分体Ｆqk/i演算手段（但し、ｉはｋの因数）、
前記第１有限体Ｆqの元a0,a1,a2,a3及び前記第２有限体Ｆqkの各基底s,t,stに基づいて、前記第２有限体Ｆqkの任意元Ａのｑ乗ＡqをＡq＝a0＋a1sq＋a2tq＋a3(st)qと計算可能な場合、予め前記拡大次数ｍと、前記各基底のｑ乗sq,tq,(st)qとを互いに関連付けて前記ペアリング計算装置の基底べき乗記憶手段に書き込む手段、
前記楕円曲線の位数＃Ｅ(Ｆq)、前記第１有限体Ｆqの位数ｑ、前記第２有限体Ｆqkの拡大次数ｋに基づいて、第１の関係＃Ｅ(Ｆq)｜（ｑk/2＋１）、又は第２の関係＃Ｅ(Ｆq)｜（ｑk/2−１）が成り立つか否かを判定する判定手段（但し、｜は、左辺が右辺を割り切ることを表す符号）、
前記第１の関係＃Ｅ(Ｆq)｜（ｑk/2＋１）が成り立つ場合、前記点データｆを前記任意元Ａとした場合の当該任意元Ａのｑk/2乗を計算するように、前記基底べき乗記憶手段、前記第１有限体Ｆq演算手段及び前記第２有限体Ｆqk演算手段を制御する第１計算制御手段、
前記点データｆを前記任意元Ａとした場合の当該任意元Ａの逆元Ａ-1を計算するように、前記基底べき乗記憶手段、前記第１有限体Ｆq演算手段及び前記第２有限体Ｆqk演算手段を制御する第２計算制御手段、
前記第１計算制御手段により得られた計算結果Ａ^(ｑk/2)及び前記第２計算制御手段により得られた逆元Ａ-1に基づいて、途中結果Ｂ＝Ａ^(qk/2)・Ａ-1＝Ａ^(qk/2-1)を計算するように、前記第１有限体Ｆq演算手段及び前記第２有限体Ｆqk演算手段を制御する第３計算制御手段（但し、＾は、べき乗を表す符号）、
前記途中結果Ｂの逆元Ｂ-1をＢ-1＝Ｂ^(qk/2)の関係式に基づいて計算するように、前記第１有限体Ｆq演算手段及び前記第２有限体Ｆqk演算手段を制御する第４計算制御手段、
前記逆元Ｂ-1及び前記途中結果Ｂに基づいて、前記任意元Ａの（ｑk−１）乗Ａ^(qk-1)を計算するように、前記第１有限体Ｆq演算手段及び前記第２有限体Ｆqk演算手段を制御する第５計算制御手段、
前記第５計算制御手段により得られた計算結果Ａ^(qk-1)及び前記位数＃Ｅ（Ｆq）に基づいて、Ａ^｛{(qk-1)/#E(Fq)}を計算するように、前記第１有限体Ｆq演算手段及び前記第２有限体Ｆqk演算手段を制御する第６計算制御手段、
前記第２の関係＃Ｅ(Ｆq)｜（ｑk/2−１）が成り立つ場合、前記＃Ｅ(Ｆq)｜（ｑk/2−１）の因数に含まれる（ｑ(i-1)k/i＋ｑ(i-2)k/i＋…＋ｑk/i＋１）に基づき、前記任意元Ａの（ｑ(i-1)k/i＋ｑ(i-2)k/i＋…＋ｑk/i＋１）乗を計算するように、前記第１有限体Ｆq演算手段及び前記第２有限体Ｆqk演算手段を制御する第７計算制御手段、
前記第７計算制御手段により得られた計算結果Ａ^(q(i-1)k/i+q(i-2)k/i+…+qk/i+1)に基づき、Ａ^｛{(qk-1)/#E(Fq)}を計算するように、前記第１有限体Ｆq演算手段及び前記部分体Ｆqk/i演算手段を制御する第８計算制御手段、
前記第６又は第８計算制御手段により得られた計算結果Ａ^{(qk-1)/#E(Fq)}を前記最終べき処理の計算結果ｆ^{(qk-1)/#E(Fq)}として出力する手段、
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ペアリング計算の過程で行う有限体の乗法群におけるべき乗演算を高速に実行し得るペアリング計算装置及びプログラムに関する。
【背景技術】
【０００２】
楕円曲線のペアリングを用いたＩＤベース(ID-Based)暗号や署名長の短いデジタル署名を実現する方法が提案されている（例えば、非特許文献１，２参照。）。
【０００３】
ペアリングとは、ＤＨ(Diffie-Hellman)問題が困難な巡回群Ｇ1，Ｇ2上の非退化な双線型写像のことを意味する。
【０００４】
ｆ：Ｇ1×Ｇ1→Ｇ2 
詳しくは有限体Ｆq上で定義される楕円曲線をＥ(Ｆq)とする。この楕円曲線Ｅ(Ｆq)の有理点のなす群に含まれる元Ｐ＝(xP,yP)及び元Ｑ＝(xQ,yQ)とすると、ペアリングではこのＰとＱを入力として、乗法群Ｆqiへの元を導出する。
【０００５】
ここでペアリングは以下の性質を持つ。
【０００６】
（１）非退化性
任意のＱに対して、ｅ（Ｐ，Ｑ）＝１が成立するとき、Ｐ＝Ｏである。ここでＯは無限遠点を意味する。
【０００７】
（２）反対称性
任意のＰ，Ｑに対して、ｅ（Ｐ，Ｑ）＝ｅ（Ｑ，Ｐ）-1 が成立する。
【０００８】
（３）双線形性
任意のＰ，Ｑ，Ｒに対して、
ｅ（Ｐ＋Ｑ，Ｒ）＝ｅ（Ｐ，Ｒ）ｅ（Ｑ，Ｒ）
ｅ（Ｐ，Ｑ＋Ｒ）＝ｅ（Ｐ，Ｑ）ｅ（Ｐ，Ｒ）
が成立する。
【０００９】
また、ペアリングは双線形性を満たすことから、任意の整数mに対して以下の性質を持つことが知られている。
【００１０】
ｅ（ｍＰ＋Ｑ）＝ｅ（Ｐ，ｍＱ）＝ｅ（Ｐ，Ｑ）m 
ＩＤベース(ID-Based)暗号や署名長の短いデジタル署名はこの双線型を満たすペアリングを用いることで実現した方式である。
【００１１】
このペアリング写像を実現するアルゴリズムとして、テイト(Tate)ペアリング、エイト(Ate)ペアリング、イータ(eta)ペアリングなどが知られている（例えば、非特許文献３，４参照。）。これらペアリング内の処理に注目すると、それぞれ各ペアリングにおける処理は大きく以下の２つに分けて考えることができる。
【００１２】
（１）各アルゴリズムの計算
（２）最終べき(final exponentiation)の計算
このとき(1)の各アルゴリズムの計算処理は、前述したようにテイトペアリング、エイトペアリング、イータペアリングのようなアルゴリズムに依存して異なる処理となっている。これに対し、(2)の最終べきの計算処理は各アルゴリズムにはあまり依存せずに同様の処理となっている。
【００１３】
ここで、(1)と(2)の各処理の計算量について検討する。イータペアリングでは(1)の処理の計算量の半分が(2)の処理に必要となる場合が存在する。従って、各ペアリングにおいては、(1)の各アルゴリズムの計算処理を高速化することと同様に、(2)のべき乗演算の処理を高速化することも重要である。
【００１４】
これらの各処理のうち、(2)最終べきの計算処理については、トーラスと呼ばれる手法により高速化を実現している。但し、トーラスを用いた高速化手法としては、標数３の有限体上で定義される楕円曲線上の有理点を用いたペアリングに適用した手法のみが示されている。また、トーラスによる高速化の効果は、最新の研究でも１５％程度といわれている。
【非特許文献１】D.Boneh, B.Lynn, H.Shacham, ”Short signature from the Weil pairing”, Asiacrypt 2001, LNCS 2248, pp.514-532, 2001
【非特許文献２】D.Boneh, M.Franklin, ”Identity-based encryption from the weil pairing”, CRYPTO 2001, LNCS 2139, pp.213-229, 2001
【非特許文献３】Paulo S.L.M.Barreto, Steven Galbraith, Colm O hEigeartaigh, Michael Scott, ”Efficient Pairing Computation on Supersingular Abelian Varieties”, ePrint Archive, Report 2004/375, 2004. http://eprint.iacr.org/2004/375
【非特許文献４】Masaaki Shirase, Tsuyoshi Takagi, Eiji Okamoto, ”Some Efficient Algorithms for the Final Exponentiation of ηT Pairing”, Cryptology ePrint Archive: Report 2006/431，2006, http://eprint.iacr.org/2006/431
【発明の開示】
【発明が解決しようとする課題】
【００１５】
しかしながら、(2)最終べきの計算処理に関してトーラスを用いた高速化手法においては、より一般的な標数の有限体上で定義されたペアリングに適用した手法が示されていない。
【００１６】
また、標数３の有限体上で定義される楕円曲線上の演算は、標数２の有限体上で定義される楕円曲線上の演算と比較して、３倍点などの演算が容易なことが知られている。
【００１７】
しかしながら、本発明者の検討によれば、ハードウェア構成の規模に着目すると、標数３よりも標数２の回路のほうが小規模のハードウェア構成となり、少ない構成要素で実現できると考えられる。すなわち、従来の高速化手法よりも小規模のハードウェア構成となる標数２の回路において、(2)最終べきの計算処理の高速化を実現することが望ましいと考えられる。
【００１８】
本発明は上記実情を考慮してなされたもので、一般的な標数の有限体上で定義される楕円曲線の有理点を用いたペアリング計算のうち、最終べき計算の高速化を実現し得るペアリング計算装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１９】
第１の発明は、標数２及び拡大次数ｍの第１有限体Ｆ2m上で定義される楕円曲線上のペアリング対象データから点データｆを計算した後、前記点データｆの(２2m−１)(２m−２(m+1)/2＋１)乗を計算する最終べき処理を実行し、この最終べき処理の計算結果を出力するペアリング計算装置であって、前記第１有限体Ｆ2m上の四則演算、二乗算及びべき乗演算を実行するための第１有限体Ｆ2m演算手段と、標数２、拡大次数ｍ及び埋め込み次数４の第２有限体Ｆ24m上の四則演算及び二乗算を実行するための第２有限体Ｆ24m演算手段と、前記第１有限体Ｆ2mの元a0,a1,a2,a3及び前記第２有限体Ｆ24mの各基底s,t,stに基づいて、前記第２有限体Ｆ24mの任意元Ａの２m乗Ａ^(2m)をＡ^(2m)＝a0＋a1s^(2m)＋a2t^(2m)＋a3(st)^(2m)と計算可能な場合（但し、^は べき乗を表す符号）、予め前記拡大次数ｍと、前記各基底の２m乗s^(2m),t^(2m),(st)^(2m)とを互いに関連付けて記憶した基底べき乗記憶手段と、前記点データｆを前記任意元Ａとした場合の当該任意元Ａの２2m乗を計算するように、前記基底べき乗記憶手段、前記第１有限体Ｆ2m演算手段及び前記第２有限体Ｆ24m演算手段を制御する第１計算制御手段と、前記点データｆを前記任意元Ａとした場合の当該任意元Ａの逆元Ａ-1を計算するように、前記基底べき乗記憶手段、前記第１有限体Ｆ2m演算手段及び前記第２有限体Ｆ24m演算手段を制御する第２計算制御手段と、前記第１計算制御手段により得られた計算結果Ａ^(22m)及び前記第２計算制御手段により得られた逆元Ａ-1に基づいて、途中結果Ｂ＝Ａ^(22m)・Ａ-1＝Ａ^(22m-1)を計算するように、前記第１有限体Ｆ2m演算手段及び前記第２有限体Ｆ24m演算手段を制御する第３計算制御手段と、前記途中結果Ｂの逆元Ｂ-1をＢ-1＝Ｂ^(22m)の関係式に基づいて計算するように、前記第１有限体Ｆ2m演算手段及び前記第２有限体Ｆ24m演算手段を制御する第４計算制御手段と、前記第４計算制御手段により得られた逆元Ｂ-1に基づいて、前記途中結果Ｂの−２(m+1)/2乗を計算するように、前記第１有限体Ｆ2m演算手段及び前記第２有限体Ｆ24m演算手段を制御する第５計算制御手段と、前記途中結果Ｂの２m乗を計算するように、前記第２有限体Ｆ24m演算手段を制御する第６計算制御手段と、前記第６計算制御手段により得られた計算結果Ｂ^(2m)、前記第５計算制御手段により得られた計算結果Ｂ^(-2(m+1)/2)、及び前記途中結果Ｂに基づいて、前記途中結果Ｂの(2m-2(m+1)/2+1)乗を計算するように、前記第１有限体Ｆ2m演算手段及び前記第２有限体Ｆ24m演算手段を制御する第７計算制御手段と、前記第７計算制御手段により得られた計算結果Ｂ^(2m-2(m+1)/2+1)を前記最終べき処理の計算結果ｆ^{(22m-1)(2m-2(m+1)/2+1)}として出力する手段と、を備えたペアリング計算装置である。
【００２０】
第２の発明は、標数ｐ及び拡大次数ｍの第１有限体Ｆq（但し、ｑ＝ｐm）上で定義される楕円曲線をＥ(Ｆq)とし、前記楕円曲線の位数を＃Ｅ(Ｆq)とし、当該楕円曲線Ｅ(Ｆq)上のペアリング写像の集合を第２有限体Ｆqkとしたとき、前記楕円曲線Ｅ(Ｆq)上のペアリング対象データから点データｆを計算した後、前記点データｆの(ｑk−１)／＃Ｅ(Ｆq)乗を計算する最終べき処理を実行し、この最終べき処理の計算結果を出力するペアリング計算装置であって、前記第１有限体Ｆq上の四則演算、二乗算及びべき乗演算を実行するための第１有限体Ｆq演算手段と、前記第２有限体Ｆqk上の四則演算及び二乗算を実行するための第２有限体Ｆqk演算手段と、前記第２有限体Ｆqkの部分体Ｆqk/i上の四則演算及び二乗算を実行するための部分体Ｆqk/i演算手段（但し、ｉはｋの因数）と、前記第１有限体Ｆqの元a0,a1,a2,a3及び前記第２有限体Ｆqkの各基底s,t,stに基づいて、前記第２有限体Ｆqkの任意元Ａのｑ乗ＡqをＡq＝a0＋a1sq＋a2tq＋a3(st)qと計算可能な場合、予め前記拡大次数ｍと、前記各基底のｑ乗sq,tq,(st)qとを互いに関連付けて記憶した基底べき乗記憶手段と、前記楕円曲線の位数＃Ｅ(Ｆq)、前記第１有限体Ｆqの位数ｑ、前記第２有限体Ｆqkの拡大次数ｋに基づいて、第１の関係＃Ｅ(Ｆq)｜（ｑk/2＋１）、又は第２の関係＃Ｅ(Ｆq)｜（ｑk/2−１）が成り立つか否かを判定する判定手段（但し、｜は、左辺が右辺を割り切ることを表す符号）と、前記第１の関係＃Ｅ(Ｆq)｜（ｑk/2＋１）が成り立つ場合、前記点データｆを前記任意元Ａとした場合の当該任意元Ａのｑk/2乗を計算するように、前記基底べき乗記憶手段、前記第１有限体Ｆq演算手段及び前記第２有限体Ｆqk演算手段を制御する第１計算制御手段と、前記点データｆを前記任意元Ａとした場合の当該任意元Ａの逆元Ａ-1を計算するように、前記基底べき乗記憶手段、前記第１有限体Ｆq演算手段及び前記第２有限体Ｆqk演算手段を制御する第２計算制御手段と、前記第１計算制御手段により得られた計算結果Ａ^(ｑk/2)及び前記第２計算制御手段により得られた逆元Ａ-1に基づいて、途中結果Ｂ＝Ａ^(qk/2)・Ａ-1＝Ａ^(qk/2-1)を計算するように、前記第１有限体Ｆq演
算手段及び前記第２有限体Ｆqk演算手段を制御する第３計算制御手段（但し、＾は、べき乗を表す符号）と、前記途中結果Ｂの逆元Ｂ-1をＢ-1＝Ｂ^(qk/2)の関係式に基づいて計算するように、前記第１有限体Ｆq演算手段及び前記第２有限体Ｆqk演算手段を制御する第４計算制御手段と、前記逆元Ｂ-1及び前記途中結果Ｂに基づいて、前記任意元Ａの（ｑk−１）乗Ａ^(qk-1)を計算するように、前記第１有限体Ｆq演算手段及び前記第２有限体Ｆqk演算手段を制御する第５計算制御手段と、前記第５計算制御手段により得られた計算結果Ａ^(qk-1)及び前記位数＃Ｅ（Ｆq）に基づいて、Ａ^｛{(qk-1)/#E(Fq)}を計算するように、前記第１有限体Ｆq演算手段及び前記第２有限体Ｆqk演算手段を制御する第６計算制御手段と、前記第２の関係＃Ｅ(Ｆq)｜（ｑk/2−１）が成り立つ場合、前記＃Ｅ(Ｆq)｜（ｑk/2−１）の因数に含まれる（ｑ(i-1)k/i＋ｑ(i-2)k/i＋…＋ｑk/i＋１）に基づき、前記任意元Ａの（ｑ(i-1)k/i＋ｑ(i-2)k/i＋…＋ｑk/i＋１）乗を計算するように、前記第１有限体Ｆq演算手段及び前記第２有限体Ｆqk演算手段を制御する第７計算制御手段と、前記第７計算制御手段により得られた計算結果Ａ^(q(i-1)k/i+q(i-2)k/i+…+qk/i+1)に基づき、Ａ^｛{(qk-1)/#E(Fq)}を計算するように、前記第１有限体Ｆq演算手段及び前記部分体Ｆqk/i演算手段を制御する第８計算制御手段と、前記第６又は第８計算制御手段により得られた計算結果Ａ^{(qk-1)/#E(Fq)}を前記最終べき処理の計算結果ｆ^{(qk-1)/#E(Fq)}として出力する手段と、を備えたペアリング計算装置である。
【００２１】
なお、各発明は「装置」として表現したが、これに限らず、「方法」、「プログラム」又は「コンピュータ読み取り可能な記憶媒体」等として表現してもよい。
【００２２】
（作用）
第１の発明においては、最終べきの計算処理のうち、逆元をＢ-1＝Ｂ^(22m)の関係式に基づいて計算する構成により、従来の逆元導出アルゴリズムに比べ、逆元を高速に計算できるので、一般的な標数２の有限体上で定義される楕円曲線の有理点を用いたペアリング計算のうち、最終べき計算の高速化を実現することができる。
【００２３】
第２の発明においては、最終べきに関し、第１の関係＃Ｅ(Ｆq)｜(ｑk/2＋１)が成り立つ場合には、第１の発明と同様に最終べきを計算し、第２の関係＃Ｅ(Ｆq)｜(ｑk/2−１)が成り立つ場合には、第２有限体Ｆqkの任意元Ａを部分体Ｆqk/iの元に落として（ペアリングの写像先の集合をＦqkより小さいＦqk/iに変えて）最終べきを計算する構成により、一般的な標数ｑの有限体上で定義される楕円曲線の有理点を用いたペアリング計算のうち、最終べき計算の高速化を実現することができる。
【発明の効果】
【００２４】
以上説明したように本発明によれば、一般的な標数の有限体上で定義される楕円曲線の有理点を用いたペアリング計算のうち、最終べき計算の高速化を実現できる。
【発明を実施するための最良の形態】
【００２５】
以下、本発明の各実施形態について図面を用いて説明するが、その前に各実施形態の概要を述べる。
【００２６】
（第１の実施形態の概要）
各実施形態では、最終べきの計算についてトーラスを用いることなく、楕円曲線を定義する有限体の性質を用いて高速化を実現する。また、第１の実施形態では埋め込み次数ｋ＝４の場合の例を示す。また各実施形態におけるmは楕円曲線を定義する有限体の拡大次数とする。例えばｍ＝１６３、ｋ＝４の場合、各演算を行う集合は図９に示すような関係となる。なお、同図中、ＧＦ(２)は｛０，１｝の集合であり、有限体Ｆ2と呼んでもよい。ＧＦ(２m=163)は楕円曲線の定義体であり、ｆ(x)＝ｘ163＋ｘ7＋ｘ6＋ｘ3＋１で構成している。ＧＦ(２m=163)は、楕円曲線Ｅ（Ｆ2m）と呼んでもよい。＃Ｅ（ＧＦ(２m=163)）は楕円曲線上で定義される集合であり、ｙ2＋ｙ＝ｘ3＋ｘ＋１で構成している。＃Ｅ（ＧＦ(２m=163)）は、楕円曲線の位数＃Ｅ（Ｆ2m）と呼んでもよい。ＧＦ(２km=652)は、ペアリングの写像先の集合であり、有限体Ｆ2kmと呼んでもよい。
【００２７】
＜全体の処理シーケンス＞
例えば、非特許文献３においてイータ(eta)ペアリングにおける任意の元Ａは次のように表現される。
【００２８】
Ａ＝ａ0＋ａ1ｓ＋ａ2ｔ＋ａ3ｓｔ 
ここで、Ａ∈Ｆ24m ，
ａi∈Ｆ2m ，
ｓ：ｆ(s)＝ｓ2＋ｓ＋１＝０を満たす元
ｔ：ｆ(t)＝ｔ2＋ｔ＋ｓ＝０を満たす元
非特許文献３におけるペアリング計算全体の処理フローは以下のようになる。
【００２９】
（１）ペアリング対象データＰ，Ｑはペアリング計算装置に入力される。
【００３０】
（２）入力されたペアリング対象データＰ，Ｑは、ペアリングアルゴリズム処理部に送られる。
【００３１】
（３）送られたペアリング対象データＰ，Ｑは、ペアリングアルゴリズム処理部により、点データｆに変換される。
【００３２】
（４）点データｆは、最終べき処理部に送られる。
【００３３】
（５）送られた点データｆは、最終べき処理部により、最終べき結果が求められる。
【００３４】
（６）点データｆの最終べき結果はペアリング計算装置から出力される。
【００３５】
ここで、上記（５）の最終べきの処理以外は従来と同様のため、説明を省略する。
【００３６】
＜上記（５）の最終べきの処理シーケンス＞
非特許文献３における最終べきの処理は、
【数１】
0004970291.tif 000002
【００３７】
本実施形態では、上記処理（５−４−１）及び（５−４−２）により、最終べき計算を行う。
【数２】
0004970291.tif 000003
【００３８】
つまり、Ｂ-1はＢ^(22m)により求めることができる。従ってＢ-1は通常の逆元導出処理を行うことなく、べき乗演算のみで導出することができる。
【００３９】
＜２mべき乗処理について＞
ここで例として任意元Ａ∈Ｆ24mについて、その２m乗の計算コストについて考える。
【００４０】
任意元Ａは前述したように次のように表される。
【００４１】
Ａ＝ａ0＋ａ1ｓ＋ａ2ｔ＋ａ3ｓｔ 
ここでまず標数２の拡大体であることに注意すると、２i乗は次式により算出できる。
【数３】
0004970291.tif 000004
【００４２】
理由は係数に２の倍数がある場合、標数２の集合では０と等しい（２で余りをとる集合）ためである。なお、べき乗のコンビネーションの項は、必ず２の倍数の係数となることは周知である。
【００４３】
従って、Ａ∈Ｆ24m，ａ0,ａ1,ａ2,ａ3∈Ｆ2mであることに注意すると、２m 乗は次のように考えることができる。
【数４】
0004970291.tif 000005
【００４４】
ここでａ0,ａ1,ａ2,ａ3はＦ2mの元なので２m 乗すると元に戻る性質を持っているため、上記式変形を行うことができる。
【００４５】
また、各基底のべき乗は、法多項式の関係式ｓ2＋ｓ＋１＝０，ｔ2＋ｔ＋ｓ＝０を用いて次のように予め求めることができる。
【数５】
0004970291.tif 000006
【００４６】
すなわち、２m 乗の計算は加算のみで実行できる。また、標数２の拡大体における加算はＸＯＲ演算で実現可能である。このため、任意元の２m 乗の計算は非常に高速に実現できる。
【００４７】
例えば、第１の実施形態においてｍ=１６３の場合、任意元Ａの２m 乗は次式のように計算できる。
【数６】
0004970291.tif 000007
【００４８】
また、第１の実施形態における計算コストについて考察する。
【００４９】
４ｍ次拡大体上の逆元導出、乗算、二乗算のコストをＩＮＶ、ＭＵＬ、ＳＱＲとし、それぞれをＩＮＶ＝１０ＭＵＬ、ＭＵＬ＝１０ＳＱＵ、を一例として見積もったとする。なお、次数ｍ＝１６３の場合で評価する。
【００５０】
従来の計算量：２ＩＮＶ＋３ＭＵＬ＋（１６３＋１）／２ＳＱＲ＝３１２ＳＱＲ
本実施形態の計算量：ＩＮＶ＋３ＭＵＬ＋（１６３＋１）／２ＳＱＲ＝２１２ＳＱＲ
すなわち、前記計算量を前提としたとき、本実施形態を用いた最終べき(final exponentiation)の計算は、従来に比べ、３割程度の計算量を削減できる。
【００５１】
このように、逆元を本実施形態により求めることで、『（１）各アルゴリズムの計算』と『（２）最終べき(final exponentiation)の計算』の計算量の比が２対１であるとすると、ペアリング計算全体では１０数％程度の計算量削減を実現できる。
【００５２】
（第２の実施形態の概要）
第１の実施形態では、ｋ＝４となるようなパラメータを選択した場合の標数２上における計算について説明した。第２の実施形態では、より一般的な計算について述べる。
【００５３】
＜最終べきの処理について＞
任意の有限体Ｆq、（ここでｑ＝ｐmとする）有限体Ｆq上で定義される楕円曲線をＥ(Ｆq)とし、その楕円曲線の位数を＃Ｅ(Ｆq)とする。
【００５４】
また、その楕円曲線上の点を用いたペアリングの写像先の集合を乗法群Ｆqkとする。
【００５５】
このときペアリング計算における最終べきは次式を用いる。
【００５６】
最終べき：(qk−１)／＃Ｅ(Ｆq)
このとき、＃Ｅ(Ｆq)は一般的に次式で表すことができる。
【数７】
0004970291.tif 000008
【００５７】
この最終べきについて以下の［１］〜［３］の場合に分けて考えることができる。
【００５８】
［１］＃Ｅ(Ｆq)｜(ｑk/2＋１)の場合
このとき最終べきは
(qk−１)／＃Ｅ(Ｆq)＝(ｑk/2−１)(…)
と変形できるので、上式(…)内における逆元導出を高速化することができる。
【００５９】
詳しくは、第１の実施形態と同様に任意の元ＡはＦqkの乗法群の元であることから、次のような性質を持つ。
【数８】
0004970291.tif 000009
【００６０】
本実施形態においても、Ｆqkの元はＦqの元を用いて表されるため、ｑのべき乗も第１の実施形態と同様に加算のみで行えることから、逆元導出のコストは大幅に削減することが可能になる。
【００６１】
一例として、本実施形態に適用できる２つのパラメータ例を以下にしめす。
【００６２】
（第１のパラメータ例）
非特許文献３において、標数２、拡大次数ｍ、楕円曲線上の位数＃Ｅ(Ｆ2m)、
Ｆ2m上の楕円曲線ｙ2＋ｙ＝ｘ3＋ｘ＋ｂについて、
【数９】
0004970291.tif 000010
【００６３】
となり、本実施形態を適用することができる。
【００６４】
（第２のパラメータ例）
本実施形態は、標数３の拡大体でも同様に逆元を関係式により高速演算する装置が実現可能となっている。
【００６５】
例えば非特許文献３，４においては、標数３の拡大体についても検討している。
【００６６】
ここでも同様に楕円曲線の位数は
【数１０】
0004970291.tif 000011
【００６７】
と変形でき、同様に逆元導出の演算を行うことなく逆元を求めることが可能になる。
【００６８】
［２］最終べきが＃Ｅ(Ｆq)｜(ｑk/2−１)の場合
この場合、最終べきは次式のように変形できる。
【００６９】
(qk−１)／＃Ｅ(Ｆq)＝(ｑk/2＋１)(…)
このとき、任意元Ａに関し、Ａ^(qk/2＋１)はＦqk/2の元となることが知られている。従って、残り（…）乗の計算はＦqkの部分体Ｆqk/2で実行できる。
【００７０】
このように、部分体で計算できるので、通常に最終べきを求めるよりも計算コストの削減が可能になる。
【００７１】
さらに（…）内の項に注目し、(ｑk/4＋１)｜(…)となる場合はさらに部分体Ｆqk/4に落とすことができ、逐次的に部分体に落とすことが可能である。
【００７２】
また上記のような場合だけではなく、最終べきの項に
【数１１】
0004970291.tif 000012
【００７３】
のような項が含まれている場合にはＦqkの部分体Ｆqk/iに落とすことができるため、残りの計算をその部分体で実行することが可能になる。
【００７４】
なお、ここで、部分体に落とすことができることについて補足的に説明する。
【００７５】
有限体Ｆqkの任意元Ａは次の性質を持つ。
【数１２】
0004970291.tif 000013
【００７６】
となる。
【数１３】
0004970291.tif 000014
【００７７】
このとき、最終べきの計算は、前述した方法を用いて高速化を行うことはできず、逆元も通常通り導出して最終べきを求めることとなる。これは従来法でも高速化できない場合である。
【００７８】
以上が各実施形態の概要である。次に、本発明の各実施形態を具体的に説明する。
【００７９】
（第１の実施形態の具体的な構成）
図１は本発明の第１の実施形態に係るペアリング計算装置の構成を示す模式図である。このペアリング計算装置１００は、入出力部１０、ペアリング計算制御部２０、メモリ３０、ペアリングアルゴリズム処理部４０及び最終べき処理部５０を備えている。
【００８０】
ここで、入出力部１０は、標数２及び拡大次数ｍの第１有限体Ｆ2m上で定義される楕円曲線上のペアリング対象データが入力されると、このペアリング対象データをペアリング計算制御部２０に送出する機能と、ペアリング計算制御部２０から受けた最終べき計算結果を出力する機能とをもっている。
【００８１】
ペアリング計算制御部２０は、入出力部１０から入力されたペアリング対象データをメモリ３０に書き込む機能と、メモリ３０内のペアリング対象データをペアリングアルゴリズム処理部４０に送出する機能と、ペアリングアルゴリズム処理部４０から受けた点データｆをメモリ３０に書き込む機能と、メモリ３０内の点データｆを最終べき処理部５０に送出する機能と、最終べき処理部５０から受けた最終べきの計算結果を入出力部１０に送出する機能とをもっている。
【００８２】
メモリ３０は、各部２０，３０，５０から読出／書込可能な記憶装置である。
【００８３】
ペアリングアルゴリズム処理部４０は、ペアリングアルゴリズム計算制御部４１及びペアリングアルゴリズム計算実行部４２を備えている。
【００８４】
ペアリングアルゴリズム計算制御部４１は、ペアリング計算制御部２０から受けたペアリング対象データに基づいて、ペアリングアルゴリズム計算を実行するようにペアリングアルゴリズム計算実行部４２を制御する機能と、ペアリングアルゴリズム計算実行部４２により計算された点データｆをペアリング計算制御部２０に送出する機能とをもっている。ここで、ペアリングアルゴリズム計算は、前述した（１）各アルゴリズムの計算に相当するものであり、テイトペアリング、エイトペアリング又はイータペアリングといった任意のペアリングアルゴリズムの計算が適用可能となっている。
【００８５】
ペアリングアルゴリズム計算実行部４２は、ペアリングアルゴリズム計算制御部４１に制御され、ペアリングアルゴリズム計算制御部４１から受けたペアリング対象データに基づいて、適宜メモリ３０を用いつつ、ペアリングアルゴリズム計算を実行する機能と、ペアリングアルゴリズム計算の実行により得られた点データｆをペアリングアルゴリズム計算制御部４１に送出する機能とをもっている。
【００８６】
最終べき処理部５０は、ペアリング最終べき計算制御部５１、Ｆ2km計算部６０及びＦ2m計算部７０を備えている。なお、本実施形態では埋め込み次数ｋを４としているので、Ｆ2kmをＦ24mと読んでもよい。
【００８７】
ペアリング最終べき計算制御部５１は、ペアリング計算制御部２０から受けた点データｆに基づいて、点データｆの(２2m−１)(２m−２(m+1)/2＋１)乗を計算する最終べき処理を実行するように、Ｆ2km計算部６０及びＦ2m計算部７０を制御する機能と、この最終べき処理の計算結果をペアリング計算制御部２０に出力する機能とをもっている。
【００８８】
具体的にはペアリング最終べき計算制御部５１は、以下の各機能(f51-1)〜(f51-7)をもっている。  
(f51-1)  点データｆを任意元Ａとした場合の当該任意元Ａの２2m乗を計算するように、基底べき乗記憶部６１、２m乗演算実行部６４及びＦ2m演算実行部７１を制御する第１計算制御機能。
【００８９】
(f51-2)  点データｆを任意元Ａとした場合の当該任意元Ａの逆元Ａ-1を計算するように、基底べき乗記憶部６１、Ｆ2km基本演算実行部６２及びＦ2m演算実行部７１を制御する第２計算制御機能。
【００９０】
(f51-3)  第１計算制御機能により得られた計算結果Ａ^(22m)及び第２計算制御機能により得られた逆元Ａ-1に基づいて、途中結果Ｂ＝Ａ^(22m)・Ａ-1＝Ａ^(22m-1)を計算するように、Ｆ2km基本演算実行部６２及びＦ2m演算実行部７１を制御する第３計算制御機能。
【００９１】
(f51-4)  途中結果Ｂの逆元Ｂ-1をＢ-1＝Ｂ^(22m)の関係式に基づいて計算するように、２m乗演算実行部６４及びＦ2m演算実行部７１を制御する第４計算制御機能。
【００９２】
(f51-5)  第４計算制御機能により得られた逆元Ｂ-1に基づいて、途中結果Ｂの−２(m+1)/2乗を計算するように、２-(m+1)/2乗演算実行部６３及びＦ2m演算実行部７１を制御する第５計算制御機能。
【００９３】
(f51-6)  途中結果Ｂの２m乗を計算するように、２m乗演算実行部６４及びＦ2m演算実行部７１を制御する第６計算制御機能。
【００９４】
(f51-7)  第６計算制御機能により得られた計算結果Ｂ^(2m)、第５計算制御機能により得られた計算結果Ｂ^(-2(m+1)/2)、及び途中結果Ｂに基づいて、途中結果Ｂの(2m-2(m+1)/2+1)乗を計算するように、Ｆ2km基本演算実行部６２及びＦ2m演算実行部７１を制御する第７計算制御機能。
【００９５】
(f51-8)  第７計算制御機能により得られた計算結果Ｂ^(2m-2(m+1)/2+1)を最終べき処理の計算結果ｆ^{(22m-1)(2m-2(m+1)/2+1)}としてペアリング計算制御部２０に出力する機能。
【００９６】
Ｆ2km計算部６０は、基底べき乗記憶部６１、Ｆ2km基本演算実行部６２、２-(m+1)/2乗演算実行部６３及び２m乗演算実行部６４を備えている。
【００９７】
基底べき乗記憶部６１は、各部６２〜６４から読出／書込可能な記憶装置であり、有限体Ｆ2mの元を用いたｋ次拡大体上における各基底の２m乗の対応結果を記憶している。基底べき乗記憶部６１は、具体的には、有限体Ｆ2mの元a0,a1,a2,a3及び有限体Ｆ24mの各基底s,t,stに基づいて、有限体Ｆ24mの任意元Ａの２m乗Ａ^(2m)をＡ^(2m)＝a0＋a1s^(2m)＋a2t^(2m)＋a3(st)^(2m)と計算可能な場合（但し、^は べき乗を表す符号）、図２に示すように、予め拡大次数ｍと、各基底の２m乗s^(2m),t^(2m),(st)^(2m)とを互いに関連付けて記憶したものである。
【００９８】
Ｆ2km基本演算実行部６２は、標数２、拡大次数ｍ及び埋め込み次数４の有限体Ｆ24m上の四則演算及び二乗算を実行する機能をもっている。
【００９９】
２-(m+1)/2乗演算実行部６３は、メモリ３０を適宜用いつつ、有限体Ｆ24m上の−２(m+1)/2乗の演算を実行する機能をもっている。
【０１００】
２m乗演算実行部６４は、有限体Ｆ24m上の２m乗の演算を実行する機能をもっている。
【０１０１】
Ｆ2m計算部７０は、Ｆ2m演算実行部７１を備えている。
【０１０２】
Ｆ2m演算実行部７１は、有限体Ｆ2m上の四則演算、二乗算及びべき乗演算を実行する機能をもっている。このＦ2m演算実行部７１は、Ｆ2km計算部６０の実行中、常に用いられる。
【０１０３】
なお、以上のようなペアリング計算装置１００は、ハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又は記憶媒体から対応する装置のコンピュータにインストールされ、対応する装置の機能を実現させるためのプログラムが用いられる。このようにペアリング計算装置１００がハードウェア構成又はプログラムを用いた構成で実施可能なことは、以下の各実施形態でも同様である。
【０１０４】
次に、以上のように構成されたペアリング計算装置の動作について図３乃至図５のフローチャートを用いて説明する。
【０１０５】
（ＳＴ１）  ペアリング計算装置１００においては、入出力部１０により、ペアリング対象データＰ，Ｑがペアリング計算制御部２０に入力される。
【０１０６】
（ＳＴ２）  ペアリング計算制御部２０は、このペアリング対象データＰ，Ｑをペアリングアルゴリズム処理部４０に送出する。
【０１０７】
（ＳＴ３）  ペアリングアルゴリズム処理部４０においては、ペアリングアルゴリズム計算実行部４２により、ペアリング対象データＰ，Ｑから点データｆを計算し、この点データｆをペアリング計算制御部２０に送出する。
【０１０８】
（ＳＴ４）  ペアリング計算制御部２０は、この点データｆを最終べき処理部５０に送出する。
【０１０９】
（ＳＴ５）  最終べき処理部５０においては、ペアリング最終べき計算制御部５１が、この点データｆに基づいて、点データｆの(２2m−１)(２m−２(m+1)/2＋１)乗を計算する最終べき処理を実行するように、Ｆ2km計算部６０及びＦ2m計算部７０を制御する。
【０１１０】
（ＳＴ５−１）  具体的には、ペアリング最終べき計算制御部５１は、点データｆを任意元Ａとした場合の当該任意元Ａの２2m乗を計算するように、基底べき乗記憶部６１、２m乗演算実行部６４及びＦ2m演算実行部７１を制御する。これにより、点データｆを任意元Ａとした場合の当該任意元Ａの２2m乗を求める。
【０１１１】
（ＳＴ５−２）  ペアリング最終べき計算制御部５１は、点データｆを任意元Ａとした場合の当該任意元Ａの逆元Ａ-1を計算するように、基底べき乗記憶部６１、Ｆ2km基本演算実行部６２及びＦ2m演算実行部７１を制御する。これにより、点データｆを任意元Ａとした場合の当該任意元Ａの逆元Ａ-1を求める。
【０１１２】
（ＳＴ５−３）  ペアリング最終べき計算制御部５１は、ステップＳＴ５−１により得られた計算結果Ａ^(22m)及びステップＳＴ５−２により得られた逆元Ａ-1に基づいて途中結果Ｂ＝Ａ^(22m)・Ａ-1＝Ａ^(22m-1)を計算するように、Ｆ2km基本演算実行部６２及びＦ2m演算実行部７１を制御する。これにより、途中結果Ｂ＝Ａ^(22m)・Ａ-1＝Ａ^(22m-1)を求める。
【０１１３】
（ＳＴ５−４）
（ＳＴ５−４−１）  ペアリング最終べき計算制御部５１は、途中結果Ｂの逆元Ｂ-1をＢ-1＝Ｂ^(22m)の関係式に基づいて計算するように、２m乗演算実行部６４及びＦ2m演算実行部７１を制御する。これにより、途中結果Ｂの逆元Ｂ-1がＢ-1＝Ｂ^(22m)の関係式により求める。
【０１１４】
（ＳＴ５−４−２）  ペアリング最終べき計算制御部５１は、ステップＳＴ５−４−１により得られた逆元Ｂ-1に基づいて、途中結果Ｂの−２(m+1)/2乗を計算するように、２-(m+1)/2乗演算実行部６３及びＦ2m演算実行部７１を制御する。これにより、逆元Ｂ-1に基づいて、途中結果Ｂの−２(m+1)/2乗を求める。
【０１１５】
（ＳＴ５−５）  ペアリング最終べき計算制御部５１は、途中結果Ｂの２m乗を計算するように、２m乗演算実行部６４及びＦ2m演算実行部７１を制御する。これにより、途中結果Ｂの２m乗を求める。
【０１１６】
（ＳＴ５−６）  ペアリング最終べき計算制御部５１は、ステップＳＴ５−５により得られた計算結果Ｂ^(2m)、ステップＳＴ５−４−２により得られた計算結果Ｂ^(-2(m+1)/2)、及び途中結果Ｂに基づいて、途中結果Ｂの(2m-2(m+1)/2+1)乗を計算するように、Ｆ2km基本演算実行部６２及びＦ2m演算実行部７１を制御する。これにより、途中結果Ｂの(2m-2(m+1)/2+1)乗を求める。
【０１１７】
しかる後、ペアリング最終べき計算制御部５１は、得られた計算結果Ｂ^(2m-2(m+1)/2+1)を最終べき処理の計算結果ｆ^{(22m-1)(2m-2(m+1)/2+1)}としてペアリング計算制御部２０に出力する。
【０１１８】
（ＳＴ６）  ペアリング計算制御部２０は、点データｆの最終べき処理の計算結果を、入出力部１０を介してペアリング計算装置１００から出力する。
【０１１９】
上述したように本実施形態によれば、最終べきの計算処理のうち、逆元をＢ-1＝Ｂ^(22m)の関係式に基づいて計算する構成により、従来の逆元導出アルゴリズムに比べ、逆元を高速に計算できるので、一般的な標数２の有限体上で定義される楕円曲線の有理点を用いたペアリング計算のうち、最終べき計算の高速化を実現することができる。
【０１２０】
補足すると、本実施形態によれば、２2m乗演算を高速に行うことができ、またこの２2m乗演算装置を用いることで任意元の逆元を逆元導出アルゴリズムを用いることなく、標数２の拡大体上の加算のみで実現することが可能になる。
【０１２１】
また、標数２の拡大体において高速化が可能となり、従来法と同等の効果が得られる。
【０１２２】
また、標数２の拡大体で高速化を実現することにより、ハードウェア構成が従来法の標数３におけるハードウェア構成よりもコンパクトに構成可能となる。
【０１２３】
さらに、従来法においては、有限体の演算に加えてトーラスの演算を実現する各種演算を別途定義してライブラリを準備する必要があったが、提案手法においては、有限体の演算のみで高速化が実現できるため、ライブラリを準備する必要がなく、リソースが削減できている。
【０１２４】
（第２の実施形態の具体的な構成）
図６は本発明の第２の実施形態に係るペアリング計算装置の構成を示す模式図であり、図１と同一機能部については同一符号を付してその詳しい説明を省略し、ここでは異なる部分について主に述べる。
【０１２５】
すなわち、第２の実施形態は、第１の実施形態における標数２及び拡大次数ｍの有限体Ｆ2mを、標数ｐ及び拡大次数ｍの任意の有限体Ｆq（＝Ｆpm）に一般化したものであり、概略的には、標数ｐ及び拡大次数ｍの有限体Ｆq（但し、ｑ＝ｐm）上で定義される楕円曲線をＥ(Ｆq)とし、楕円曲線の位数を＃Ｅ(Ｆq)とし、当該楕円曲線Ｅ(Ｆq)上のペアリング写像の集合を有限体Ｆqkとしたとき、楕円曲線Ｅ(Ｆq)上のペアリング対象データから点データｆを計算した後、点データｆの(ｑk−１)／＃Ｅ(Ｆq)乗を計算する最終べき処理を実行し、この最終べき処理の計算結果を出力するペアリング計算装置となっている。
【０１２６】
具体的には主に、最終べき計算判定部５２及びＦqk/i計算部８０を付加し、２-(m+1)/2乗演算実行部６３に代えて逆元導出実行部６５を備えた構成となっている。また、各機能部の名称もＦ2m又はＦ2kmに代えて、Ｆq又はＦqkを用いた名称となっている。またこれらの変更に伴い、ペアリング最終べき計算制御部５１の機能を一般化したペアリング最終べき計算制御部５１’と、基底べき乗記憶部６１の記憶内容を一般化した基底べき乗記憶部６１’とを有している。
【０１２７】
ここで、最終べき計算判定部５２は、ペアリング最終べき計算制御部５１’から入力された点データｆに関する楕円曲線の位数＃Ｅ(Ｆq)、有限体Ｆqの位数ｑ、有限体Ｆqkの拡大次数ｋに基づいて、第１の関係＃Ｅ(Ｆq)｜（ｑk/2＋１）、又は第２の関係＃Ｅ(Ｆq)｜（ｑk/2−１）が成り立つか否かを判定する判定機能（但し、｜は、左辺が右辺を割り切ることを表す符号）と、判定結果をペアリング最終べき計算制御部５１’に送出する機能とをもっている。
【０１２８】
逆元導出実行部６５は、有限体Ｆqk上の逆元をＢ-1＝Ｂ^(qk/2)の関係式に基づいて計算する機能をもっている。
【０１２９】
Ｆqk/i計算部８０は、Ｆqk/i演算実行部８１を備えている。
【０１３０】
Ｆqk/i演算実行部８１は、ペアリング最終べき計算制御部５１’に制御され、有限体Ｆqkの部分体Ｆqk/i上の四則演算及び二乗算を実行する機能をもっている（但し、ｉはｋの因数）。
【０１３１】
ペアリング最終べき計算制御部５１’は、以下の各機能(f51’-1)〜(f51’-10)をもっている。
【０１３２】
(f51’-1)  最終べき計算判定部５２による判定の結果、第１の関係＃Ｅ(Ｆq)｜（ｑk/2＋１）が成り立つ場合、点データｆを任意元Ａとした場合の当該任意元Ａのｑk/2乗を計算するように、基底べき乗記憶部６１’、ｑ乗演算実行部６４’及びＦq演算実行部７１’を制御する第１計算制御機能。
【０１３３】
(f51’-2)  点データｆを任意元Ａとした場合の当該任意元Ａの逆元Ａ-1を計算するように、基底べき乗記憶部６１’、Ｆqk基本演算実行部６２’及びＦq演算実行部７１’を制御する第２計算制御機能。
【０１３４】
(f51’-3)  第１計算制御機能により得られた計算結果Ａ^(ｑk/2)及び第２計算制御機能により得られた逆元Ａ-1に基づいて、途中結果Ｂ＝Ａ^(qk/2)・Ａ-1＝Ａ^(qk/2-1)を計算するように、Ｆqk基本演算実行部６２’及びＦq演算実行部７１’を制御する第３計算制御機能。
【０１３５】
(f51’-4)  途中結果Ｂの逆元Ｂ-1をＢ-1＝Ｂ^(qk/2)の関係式に基づいて計算するように、逆元導出実行部６５及びＦq演算実行部７１’を制御する第４計算制御機能。
【０１３６】
(f51’-5)  逆元Ｂ-1及び途中結果Ｂに基づいて、任意元Ａの（ｑk−１）乗Ａ^(qk-1)を計算するように、Ｆqk基本演算実行部６２’及びＦq演算実行部７１’を制御する第５計算制御機能。
【０１３７】
(f51’-6)  第５計算制御機能により得られた計算結果Ａ^(qk-1)及び位数＃Ｅ（Ｆq）に基づいて、Ａ^｛{(qk-1)/#E(Fq)}を計算するように、Ｆqk基本演算実行部６２’及びＦq演算実行部７１’を制御する第６計算制御機能。
【０１３８】
(f51’-7)  最終べき計算判定部５２による判定の結果、第２の関係＃Ｅ(Ｆq)｜（ｑk/2−１）が成り立つ場合、＃Ｅ(Ｆq)｜（ｑk/2−１）の因数に含まれる（ｑ(i-1)k/i＋ｑ(i-2)k/i＋…＋ｑk/i＋１）に基づき、任意元Ａの（ｑ(i-1)k/i＋ｑ(i-2)k/i＋…＋ｑk/i＋１）乗を計算するように、Ｆqk基本演算実行部６２’及びＦq演算実行部７１’を制御する第７計算制御機能。
【０１３９】
(f51’-8)  第７計算制御機能により得られた計算結果Ａ^(q(i-1)k/i+q(i-2)k/i+…+qk/i+1)に基づき、Ａ^｛{(qk-1)/#E(Fq)}を計算するように、Ｆqk/i演算実行部８１及びＦq演算実行部７１’を制御する第８計算制御機能。
【０１４０】
(f51’-9)  最終べき計算判定部５２による判定の結果、第１の関係＃Ｅ(Ｆq)｜（ｑk/2＋１）及び第２の関係＃Ｅ(Ｆq)｜（ｑk/2−１）がいずれも成り立たない場合で且つ第３の関係＃Ｅ(Ｆq)｜（ｑk＋１）が成り立つ場合、通常通りに、点データｆの(ｑk−１)／＃Ｅ(Ｆq)乗を計算するように、Ｆqk基本演算実行部６２’及びＦq演算実行部７１’を制御する第９計算制御機能。
【０１４１】
ここで、「通常通りに…計算する」とは、「逆元Ｂ-1をＢ-1＝Ｂ^(qk/2)の関係式に基づいて計算する高速化手法や、有限体Ｆqk任意元Ａを部分体Ｆqk/iの元に落とす高速化手法を用いずに…計算する」ということを意味している。
【０１４２】
(f51’-10)  第６計算制御機能、第８計算制御機能又は第９計算制御機能により得られた計算結果Ａ^{(qk-1)/#E(Fq)}を最終べき処理の計算結果ｆ^{(qk-1)/#E(Fq)}としてペアリング計算制御部２０に出力する機能。
【０１４３】
基底べき乗記憶部６１’は、各部６２’，６４’，６５から読出／書込可能な記憶装置であり、有限体Ｆqの元a0,a1,a2,a3及び有限体Ｆqkの各基底s,t,stに基づいて、有限体Ｆqkの任意元Ａのｑ乗ＡqをＡq＝a0＋a1sq＋a2tq＋a3(st)qと計算可能な場合、図７に示すように、予め拡大次数ｍと、各基底のｑ乗sq,tq,(st)qとを互いに関連付けて記憶している。
【０１４４】
次に、以上のように構成されたペアリング計算装置の動作を図８のフローチャートを用いて説明する。なお、本実施形態は、前述したステップＳＴ１〜ＳＴ６のうち、ＳＴ５の変形例のため、前述したステップＳＴ５に代えて、ステップＳＴ５０〜ＳＴ５９を用いて述べる。すなわち、前述したステップＳＴ１〜ＳＴ４と、前述したＳＴ６との間に、以下のステップＳＴ５０〜ＳＴ５９が実行される。
【０１４５】
（ＳＴ５０）  ペアリング最終べき計算制御部５１’は、ペアリング計算制御部２０から入力された点データｆに関する楕円曲線の位数＃Ｅ(Ｆq)、有限体Ｆqの位数ｑ、有限体Ｆqkの拡大次数ｋを最終べき計算判定部５２に送出する。
【０１４６】
最終べき計算判定部５２は、楕円曲線の位数＃Ｅ(Ｆq)、有限体Ｆqの位数ｑ、有限体Ｆqkの拡大次数ｋに基づいて、第１の関係＃Ｅ(Ｆq)｜（ｑk/2＋１）、又は第２の関係＃Ｅ(Ｆq)｜（ｑk/2−１）が成り立つか否かを判定し、判定結果をペアリング最終べき計算制御部５１’に送出する。
【０１４７】
（ＳＴ５１）  ペアリング最終べき計算制御部５１’は、第１の関係＃Ｅ(Ｆq)｜（ｑk/2＋１）が成り立つ場合、点データｆを任意元Ａとした場合の当該任意元Ａのｑk/2乗を計算するように、基底べき乗記憶部６１’、ｑ乗演算実行部６４’及びＦq演算実行部７１’を制御する。これにより、点データｆを任意元Ａとした場合の当該任意元Ａのｑk/2乗を求める。
【０１４８】
（ＳＴ５２）  ペアリング最終べき計算制御部５１’は、点データｆを任意元Ａとした場合の当該任意元Ａの逆元Ａ-1を計算するように、基底べき乗記憶部６１’、Ｆqk基本演算実行部６２’及びＦq演算実行部７１’を制御する。これにより、点データｆを任意元Ａとした場合の当該任意元Ａの逆元Ａ-1を求める。
【０１４９】
（ＳＴ５３）  ペアリング最終べき計算制御部５１’は、ステップＳＴ５１により得られた計算結果Ａ^(ｑk/2)及びステップＳＴ５３により得られた逆元Ａ-1に基づいて、途中結果Ｂ＝Ａ^(qk/2)・Ａ-1＝Ａ^(qk/2-1)を計算するように、Ｆqk基本演算実行部６２’及びＦq演算実行部７１’を制御する。これにより、途中結果Ｂ＝Ａ^(qk/2)・Ａ-1＝Ａ^(qk/2-1)を求める。
【０１５０】
（ＳＴ５４）  ペアリング最終べき計算制御部５１’は、途中結果Ｂの逆元Ｂ-1をＢ-1＝Ｂ^(qk/2)の関係式に基づいて計算するように、逆元導出実行部６５及びＦq演算実行部７１’を制御する。これにより、途中結果Ｂの逆元Ｂ-1をＢ-1＝Ｂ^(qk/2)の関係式により求める。
【０１５１】
（ＳＴ５５）  ペアリング最終べき計算制御部５１’は、逆元Ｂ-1及び途中結果Ｂに基づいて、任意元Ａの（ｑk−１）乗Ａ^(qk-1)を計算するように、Ｆqk基本演算実行部６２’及びＦq演算実行部７１’を制御する。これにより、任意元Ａの（ｑk−１）乗Ａ^(qk-1)を求める。
【０１５２】
続いて、ペアリング最終べき計算制御部５１’は、得られた計算結果Ａ^(qk-1)及び位数＃Ｅ（Ｆq）に基づいて、Ａ^｛{(qk-1)/#E(Fq)}を計算するように、Ｆqk基本演算実行部６２’及びＦq演算実行部７１’を制御する。これにより、Ａ^｛{(qk-1)/#E(Fq)}を求める。
【０１５３】
（ＳＴ５６）  一方、最終べき計算判定部５２による判定の結果、第２の関係＃Ｅ(Ｆq)｜（ｑk/2−１）が成り立つ場合には以下のステップＳＴ５７〜ＳＴ５８を実行する。
【０１５４】
（ＳＴ５７）  ペアリング最終べき計算制御部５１’は、＃Ｅ(Ｆq)｜（ｑk/2−１）の因数に含まれる（ｑ(i-1)k/i＋ｑ(i-2)k/i＋…＋ｑk/i＋１）に基づき、任意元Ａの（ｑ(i-1)k/i＋ｑ(i-2)k/i＋…＋ｑk/i＋１）乗を計算するように、Ｆqk基本演算実行部６２’及びＦq演算実行部７１’を制御する。これにより、任意元Ａの（ｑ(i-1)k/i＋ｑ(i-2)k/i＋…＋ｑk/i＋１）乗を求める。
【０１５５】
（ＳＴ５８）  ペアリング最終べき計算制御部５１’は、ステップＳＴ５７により得られた計算結果Ａ^(q(i-1)k/i+q(i-2)k/i+…+qk/i+1)に基づき、Ａ^｛{(qk-1)/#E(Fq)}を計算するように、Ｆqk/i演算実行部８１及びＦq演算実行部７１’を制御する。これにより、Ａ^｛{(qk-1)/#E(Fq)}を求める。
【０１５６】
（ＳＴ５９）  また一方、最終べき計算判定部５２による判定の結果、第１の関係＃Ｅ(Ｆq)｜（ｑk/2＋１）及び第２の関係＃Ｅ(Ｆq)｜（ｑk/2−１）がいずれも成り立たない場合で且つ第３の関係＃Ｅ(Ｆq)｜（ｑk＋１）が成り立つ場合、ペアリング最終べき計算制御部５１’は、通常通りに、点データｆの(ｑk−１)／＃Ｅ(Ｆq)乗を計算するように、Ｆqk基本演算実行部６２’及びＦq演算実行部７１’を制御する。これにより、点データｆの(ｑk−１)／＃Ｅ(Ｆq)乗を求める。
【０１５７】
しかる後、ペアリング最終べき計算制御部５１’は、ステップＳＴ５６、ステップ５８又はステップＳＴ５９により得られた計算結果Ａ^{(qk-1)/#E(Fq)}を最終べき処理の計算結果ｆ^{(qk-1)/#E(Fq)}としてペアリング計算制御部２０に出力する。
【０１５８】
上述したように本実施形態によれば、最終べきに関し、第１の関係＃Ｅ(Ｆq)｜(ｑk/2＋１)が成り立つ場合には、第１の実施形態と同様に最終べきを計算し、第２の関係＃Ｅ(Ｆq)｜(ｑk/2−１)が成り立つ場合には、第２有限体Ｆqkの任意元Ａを部分体Ｆqk/iの元に落として（ペアリングの写像先の集合をＦqkより小さいＦqk/iに変えて）最終べきを計算する構成により、一般的な標数ｑの有限体上で定義される楕円曲線の有理点を用いたペアリング計算のうち、最終べき計算の高速化を実現することができる。
【０１５９】
補足すると、第２の実施形態によれば、標数に依存しない一般的な楕円曲線上におけるペアリングの計算処理において、最終べきの計算を高速化することができる。
【０１６０】
効果として、＃Ｅ(Ｆq)｜(ｑk/2＋１)の場合はトーラスを用いた場合と同等の効果が得られ、＃Ｅ(Ｆq)｜(ｑk/2−１)の場合は、効果を比較することは難しいが部分体に落として最終べきを計算することができるので、従来法よりも高速となる。
【０１６１】
ただし、セキュリティ的にペアリングの写像先がＦqkではなくＦqk/iとなるので、通常はそのような楕円曲線は推奨されず、セキュリティを保持するためには一般的に大きな埋め込み次数の場合、もしくはセキュリティを考慮しないような場合にしか適用することができない。
【０１６２】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１６３】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１６４】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０１６５】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１６６】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１６７】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１６８】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１６９】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０１７０】
【図１】本発明の第１の実施形態に係るペアリング計算装置の構成を示す模式図である。
【図２】同実施形態における基底べき乗記憶部の構成を示す模式図である。
【図３】同実施形態におけるペアリング計算処理の動作を説明するためのフローチャートである。
【図４】同実施形態における最終べき計算処理の動作を説明するためのフローチャートである。
【図５】同実施形態における最終べき計算処理の動作の一部を説明するためのフローチャートである。
【図６】本発明の第２の実施形態に係るペアリング計算装置の構成を示す模式図である。
【図７】同実施形態における基底べき乗記憶部の構成を示す模式図である。
【図８】同実施形態における最終べき計算処理の動作を説明するためのフローチャートである。
【図９】第１の実施形態における各演算を行う集合の一例を示す模式図である。
【符号の説明】
【０１７１】
１００…ペアリング計算装置、１０…入出力部、２０…ペアリング計算制御部、３０…メモリ、４０…ペアリングアルゴリズム処理部、４１…ペアリングアルゴリズム計算制御部、４２…ペアリングアルゴリズム計算実行部、５０…最終べき処理部、５１，５１’…ペアリング最終べき計算制御部、５２…最終べき計算判定部、６０…Ｆ2km計算部、６０’…Ｆqk計算部、６１，６１’…基底べき乗記憶部、６２…Ｆ2km基本演算実行部、６２’…Ｆqk基本演算実行部、６３…２-(m+1)/2乗演算実行部、６４…２m乗演算実行部、６４’…ｑ乗演算実行部、６５…逆元導出実行部、７０…Ｆ2m計算部、７０’…Ｆq計算部、７１…Ｆ2m演算実行部、７１’…Ｆq演算実行部、８０…Ｆqk/i計算部、８１…Ｆqk/i演算実行部。
【図１】
0004970291.tif 000015
【図２】
0004970291.tif 000016
【図３】
0004970291.tif 000017
【図４】
0004970291.tif 000018
【図５】
0004970291.tif 000019
【図６】
0004970291.tif 000020
【図７】
0004970291.tif 000021
【図８】
0004970291.tif 000022
【図９】
0004970291.tif 000023