(57)【要約】  高速なペアリング演算を可能としたペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラムを提供する。  曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ,ａ∈Ｆp,ｂ∈Ｆpで与えられ、埋込み次数がｋで、Ｆpkを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、位数ｒと、フロベニウス自己準同型写像φpのトレースｔを整数変数χの関数とし、有理関数ｆχ,Q(Ｓ)を演算する演算手段と、所定の有理点を通る直線の有理点Ｓ(ｘs,ｙs)における値を演算する演算手段と、これらの演算手段の演算結果を用いて有理関数f'χ,Q(Ｓ)を演算する演算手段と、有理関数f'χ,Q(Ｓ)を用いて【数３】2010024401.tif 000059としてペアリング演算を行う演算手段と有するものとする。
2010024401.tif 000002
【特許請求の範囲】
【請求項１】
曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ,ａ∈Ｆp,ｂ∈Ｆpで与えられ、埋込み次数がｋで、Ｆpkを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φp−[１]),
Ｇ2＝Ｅ[r]∩Ker(φp−[ｐ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*pk/(Ｆ*pk)r
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ1、Ｑ∈Ｇ2としてペアリングｅ(Ｑ,Ｓ)を演算して演算結果を出力するペアリング演算装置であって、
フロベニウス自己準同型写像φpのトレースをｔとして、ペアリングｅ(Ｑ,Ｓ)をミラーのアルゴリズムを用いて計算される有理関数ｆt-1,Q(Ｓ)を用いて
【数２】
2010024401.tif 000049
として演算する代わりに、
位数ｒと、フロベニウス自己準同型写像φpのトレースｔを整数変数χの関数として、
有理関数ｆχ,Q(Ｓ)を演算する演算手段と、
所定の有理点を通る直線の有理点Ｓ(ｘs,ｙs)における値を演算する演算手段と、
これらの演算手段の演算結果を用いて有理関数f'χ,Q(Ｓ)を演算する演算手段と、
前記有理関数f'χ,Q(Ｓ)を用いて
【数３】
2010024401.tif 000050
としてペアリング演算を行う演算手段と
によりペアリング演算を行うペアリング演算装置。
【請求項２】
前記有理関数ｆχ,Q(Ｓ)を演算する演算手段では、χＱを演算して演算結果を所定のレジスタに記憶し、
前記χＱの演算結果を用いて前記所定の有理点を演算する演算手段を有する請求項１に記載のペアリング演算装置。
【請求項３】
前記埋込み次数ｋ＝12の場合に、
位数ｒと、フロベニウス自己準同型写像φpのトレースｔを、前記整数変数χを用いて
ｒ(χ)＝３６χ4−３６χ3＋１８χ2−６χ＋１,
ｔ(χ)＝６χ2＋１
とし、χＱ＝Ｒとして、このＲのフロベニウス自己準同型写像φpがφp(Ｒ)＝ｐＲである関係を用いて、有理点ｐ10χＱ、χＱ＋ｐ10χＱ、ｐχＱ＋ｐ3χＱをそれぞれ演算し、
有理点(χＱ,ｐ10χＱ)を通る直線における前記有理点Ｓ(ｘs,ｙs)の値l1と、有理点(χＱ＋ｐ10χＱ,ｐχＱ＋ｐ3χＱ)を通る直線における前記有理点Ｓ(ｘs,ｙs)の値l2をそれぞれ演算し、
有理点(ｐχＱ,ｐ3χＱ)を通る直線における前記有理点Ｓ(ｘs,ｙs)の値l3を用いて
【数４】
2010024401.tif 000051
として前記有理関数f'χ,Q(Ｓ)を演算する請求項２に記載のペアリング演算装置。
【請求項４】
前記有理関数fχ,Q(Ｓ)のフロベニウス自己準同型写像φpがφp(fχ,Q(Ｓ))＝fχ,Q(Ｓ)pであることを用いて
【数５】
2010024401.tif 000052
を演算するとともに、
Ｑ1,Ｑ2∈Ｇ2である有理点(Ｑ1,Ｑ2)を通る直線における前記有理点Ｓ(ｘs,ｙs)の値lのフロベニウス自己準同型写像φpが有理点(pＱ1,pＱ2)を通る直線における前記有理点Ｓ(ｘs,ｙs)の値であることを用いて
【数６】
2010024401.tif 000053
となる
【数７】
2010024401.tif 000054
を演算して前記有理関数f'χ,Q(Ｓ)を演算する請求項３に記載のペアリング演算装置。
【請求項５】
曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ,ａ∈Ｆp,ｂ∈Ｆpで与えられ、埋込み次数がｋで、Ｆpkを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φp−[１]),
Ｇ2＝Ｅ[r]∩Ker(φp−[ｐ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*pk/(Ｆ*pk)r
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ1、Ｑ∈Ｇ2としてＣＰＵを備えた電子計算機でペアリングｅ(Ｑ,Ｓ)を演算するペアリング演算方法であって、
フロベニウス自己準同型写像φpのトレースをｔとして、ペアリングｅ(Ｑ,Ｓ)をミラーのアルゴリズムを用いて計算される有理関数ｆt-1,Q(Ｓ)を用いて
【数２】
2010024401.tif 000055
として演算する代わりに、
位数ｒと、フロベニウス自己準同型写像φpのトレースｔを整数変数χの関数として、
前記電子計算機のＣＰＵを演算手段として機能させて、有理関数ｆχ,Q(Ｓ)を演算するステップと、
前記電子計算機のＣＰＵを演算手段として機能させて、所定の有理点を通る直線の有理点Ｓ(ｘs,ｙs)における値を演算するステップと、
前記電子計算機のＣＰＵを演算手段として機能させて、前記の演算結果を用いて有理関数f'χ,Q(Ｓ)を演算するステップと、
前記電子計算機のＣＰＵを演算手段として機能させて、前記有理関数f'χ,Q(Ｓ)を用いて
【数３】
2010024401.tif 000056
として演算するステップと
を有するペアリング演算方法。
【請求項６】
前記有理関数ｆχ,Q(Ｓ)を演算するステップの後、
前記電子計算機のＣＰＵを演算手段として機能させて、χＱを演算し、このχＱの演算結果を用いて前記所定の有理点を演算するステップを有する請求項５に記載のペアリング演算方法。
【請求項７】
曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ,ａ∈Ｆp,ｂ∈Ｆpで与えられ、埋込み次数がｋで、Ｆpkを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φp−[１]),
Ｇ2＝Ｅ[r]∩Ker(φp−[ｐ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*pk/(Ｆ*pk)r
である非退化な双線形写像としてペアリングｅを定義し、
Ｓ∈Ｇ1、Ｑ∈Ｇ2としてＣＰＵを備えた電子計算機にペアリングｅ(Ｑ,Ｓ)を演算させるペアリング演算プログラムであって、
フロベニウス自己準同型写像φpのトレースをｔとして、ペアリングｅ(Ｑ,Ｓ)をミラーのアルゴリズムを用いて計算される有理関数ｆt-1,Q(Ｓ)を用いて
【数２】
2010024401.tif 000057
として演算させる代わりに、
位数ｒと、フロベニウス自己準同型写像φpのトレースｔを整数変数χの関数として、
前記電子計算機を、
有理関数ｆχ,Q(Ｓ)を演算する演算手段と、
所定の有理点を通る直線の有理点Ｓ(ｘs,ｙs)における値を演算する演算手段と、
前記の演算結果を用いて有理関数f'χ,Q(Ｓ)を演算する演算手段と、
前記有理関数f'χ,Q(Ｓ)を用いて
【数３】
2010024401.tif 000058
として演算する演算手段
として機能させるペアリング演算プログラム。
【請求項８】
前記電子計算機を、
χＱを演算する演算手段と、
このχＱの演算結果を用いて前記所定の有理点を演算する演算手段
として機能させる請求項７に記載のペアリング演算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ペアリング演算を高速に実行可能としたペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラムに関する。
【背景技術】
【０００２】
従来、個人ユーザがインターネットなどのネットワーク上において提供されている各種のサービスを利用する場合に、その個人ユーザが正規のユーザであることを確認する認証処理が行われていることがある。このような認証処理では、一般的に、個人ユーザごとにあらかじめ設定されたＩＤ及びパスワード等を用いて認証している。そのために、ネットワークには、認証処理を実行するための認証サーバが設けられている。【０００３】
最近では、ディジタル署名技術を用いることにより、個々のデータ自体に個人ユーザに固有のディジタル署名データを付加している。このディジタル署名データによって、個人ユーザが利用するデータが第三者によって改ざんされていないこと、あるいは第三者に漏洩していないことを保証可能として、秘匿性の高い情報もネットワーク上で安全に取り扱い可能となってきている。【０００４】
一方、ディジタル署名では、認証サーバでの認証処理にともなって個人ユーザが特定されるため、認証処理のたびに認証サーバに個々の個人ユーザの履歴が情報として逐次蓄積されることとなっている。したがって、認証サーバには、個人ユーザが、どのようなサイトにアクセスしたかとか、どのようなサービスを利用したかなどの個人情報が蓄積されることとなるので、個人情報保護の点からこれらの情報の漏洩が生じないように、十分な注意が払われている。【０００５】
このようなディジタル署名を用いることによって生じる個人ユーザの履歴情報の蓄積を解消するために、ディジタル署名を拡張したディジタルグループ署名を用いることが提案されている。【０００６】
ディジタルグループ署名を用いた場合には、個人ユーザは、認証サーバに対して匿名で所定のグループに属していることのみを証明する署名データを送信し、認証サーバでは、受信した署名データから個人ユーザを特定することなく個人ユーザが所定のグループに属していることを認証している。したがって、認証サーバでは、グループに属さない個人ユーザによる不正利用を阻止する一方で、個人ユーザごとの履歴情報を蓄積することなく個人ユーザを認証している。【０００７】
このようなディジタルグループ署名における匿名認証には、ペアリング演算が用いられている。【０００８】
ペアリング演算は、２入力１出力の関数を用いた演算であって、たとえば、Ｓを素体Ｆp上の有理点、Ｑをｋ次拡大体Ｆpk上の有理点として、２つの有理点ＳとＱを入力することにより拡大体Ｆ*pkの元ｚが出力されるものである。しかも、ペアリング演算は、有理点Ｓのａ倍と、有理点Ｑのｂ倍を入力した場合に、ｚのab乗が算出されるという双線形性を有している。この双線形性を利用して認証を行っている。ここで、「ｋ」は埋込み次数であり、「Ｆ*pk」は、数学における表記上、正しくは、
【数１】
2010024401.tif 000003
であるが、表示の制限上、「Ｆ*pk」と表示している。【０００９】
一般的に、有理点Ｓ，Ｑにはそれぞれ楕円曲線上の点が用いられている。このような楕円曲線上の有理点のペアリング演算は、ミラーのアルゴリズムを用いて演算するステップと、その演算結果に対してべき乗算を行うステップとで構成されている。【００１０】
ディジタルグループ署名では、グループに所属する個人ユーザのアクセス権の認証処理を行う際に、まず、アクセス権が失効している個人ユーザを除外するためのペアリング演算を行っている。次いで、ディジタルグループ署名では、所定の個人ユーザのペアリング演算を行って認証処理を行うことにより、個人ユーザごとのアクセス権の発行または失効の属性変更に柔軟に対応可能としている。【００１１】
したがって、たとえば、10,000人の個人ユーザで構成されるグループのディジタルグループ署名の場合に、アクセス権が失効している個人ユーザが100人いれば、100回のペアリング演算が必要となっている。現時点での一般的な電子計算機による１回のペアリング演算には約0.1秒を要していることから、100回のペアリング演算には約10秒を要することとなっている。したがって、現状では、ディジタルグループ署名は実用的な技術とは考えられておらず、広く利用されるものとはなっていなかった。【００１２】
現状では、ディジタルグループ署名を実用化するために、ペアリング演算の演算速度を向上させる研究が行われている。たとえば、ペアリング演算の高速化の技術として、楕円曲線上で定義されるＴａｔｅペアリング演算を用い、演算負荷を低減させて高速化を図る技術が提案されている（例えば、特許文献１参照。）。
【特許文献１】特開２００５−３１６２６７号公報
【発明の開示】
【発明が解決しようとする課題】
【００１３】
しかしながら、現在提案されているペアリング演算の高速化の技術では未だに十分ではなく、さらなる高速化が求められていた。【００１４】
本発明者らは、このような現状に鑑み、ペアリング演算を高速化すべく研究開発を行って、本発明を成すに至ったものである。
【課題を解決するための手段】
【００１５】
本発明のペアリング演算装置では、曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ,ａ∈Ｆp,ｂ∈Ｆpで与えられ、埋込み次数がｋで、Ｆpkを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φp−[１]),
Ｇ2＝Ｅ[r]∩Ker(φp−[ｐ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*pk/(Ｆ*pk)r
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ1、Ｑ∈Ｇ2としてペアリングｅ(Ｑ,Ｓ)を演算して演算結果を出力するペアリング演算装置であって、フロベニウス自己準同型写像φpのトレースをｔとして、ペアリングｅ(Ｑ,Ｓ)をミラーのアルゴリズムを用いて計算される有理関数ｆt-1,Q(Ｓ)を用いて
【数２】
2010024401.tif 000004
として演算する代わりに、位数ｒと、フロベニウス自己準同型写像φpのトレースｔを整数変数χの関数として、有理関数ｆχ,Q(Ｓ)を演算する演算手段と、所定の有理点を通る直線の有理点Ｓ(ｘs,ｙs)における値を演算する演算手段と、これらの演算手段の演算結果を用いて有理関数f'χ,Q(Ｓ)を演算する演算手段と、有理関数f'χ,Q(Ｓ)を用いて
【数３】
2010024401.tif 000005
としてペアリング演算を行う演算手段とによりペアリング演算を行うこととした。【００１６】
さらに、本発明のペアリング演算装置では、有理関数ｆχ,Q(Ｓ)を演算する演算手段では、χＱを演算して演算結果を所定のレジスタに記憶し、χＱの演算結果を用いて所定の有理点を演算する演算手段を有することにも特徴を有する。【００１７】
しかも、本発明のペアリング演算装置では、埋込み次数ｋ＝12の場合に、位数ｒと、フロベニウス自己準同型写像φpのトレースｔを、整数変数χを用いて
ｒ(χ)＝３６χ4−３６χ3＋１８χ2−６χ＋１,
ｔ(χ)＝６χ2＋１
とし、χＱ＝Ｒとして、このＲのフロベニウス自己準同型写像φpがφp(Ｒ)＝ｐＲである関係を用いて、有理点ｐ10χＱ、χＱ＋ｐ10χＱ、ｐχＱ＋ｐ3χＱをそれぞれ演算し、有理点(χＱ,ｐ10χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l1と、有理点(χＱ＋ｐ10χＱ,ｐχＱ＋ｐ3χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l2をそれぞれ演算し、有理点(ｐχＱ,ｐ3χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l3を用いて
【数４】
2010024401.tif 000006
として有理関数f'χ,Q(Ｓ)を演算することにも特徴を有する。【００１８】
そのうえ、本発明のペアリング演算装置では、有理関数fχ,Q(Ｓ)のフロベニウス自己準同型写像φpがφp(fχ,Q(Ｓ))＝fχ,Q(Ｓ)pであることを用いて
【数５】
2010024401.tif 000007
を演算するとともに、Ｑ1,Ｑ2∈Ｇ2である有理点(Ｑ1,Ｑ2)を通る直線における有理点Ｓ(ｘs,ｙs)の値lのフロベニウス自己準同型写像φpが有理点(pＱ1,pＱ2)を通る直線における有理点Ｓ(ｘs,ｙs)の値であることを用いて
【数６】
2010024401.tif 000008
となる
【数７】
2010024401.tif 000009
を演算して有理関数f'χ,Q(Ｓ)を演算することにも特徴を有する。【００１９】
また、本発明のペアリング演算方法では、曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ,ａ∈Ｆp,ｂ∈Ｆpで与えられ、埋込み次数がｋで、Ｆpkを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φp−[１]),
Ｇ2＝Ｅ[r]∩Ker(φp−[ｐ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*pk/(Ｆ*pk)r
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ1、Ｑ∈Ｇ2としてＣＰＵを備えた電子計算機でペアリングｅ(Ｑ,Ｓ)を演算するペアリング演算方法であって、フロベニウス自己準同型写像φpのトレースをｔとして、ペアリングｅ(Ｑ,Ｓ)をミラーのアルゴリズムを用いて計算される有理関数ｆt-1,Q(Ｓ)を用いて
【数２】
2010024401.tif 000010
として演算する代わりに、位数ｒと、フロベニウス自己準同型写像φpのトレースｔを整数変数χの関数として、電子計算機のＣＰＵを演算手段として機能させて、有理関数ｆχ,Q(Ｓ)を演算するステップと、電子計算機のＣＰＵを演算手段として機能させて、所定の有理点を通る直線の有理点Ｓ(ｘs,ｙs)における値を演算するステップと、電子計算機のＣＰＵを演算手段として機能させて、前記の演算結果を用いて有理関数f'χ,Q(Ｓ)を演算するステップと、電子計算機のＣＰＵを演算手段として機能させて、有理関数f'χ,Q(Ｓ)を用いて
【数３】
2010024401.tif 000011
として演算するステップとを有するものである。【００２０】
さらに、本発明のペアリング演算方法では、有理関数ｆχ,Q(Ｓ)を演算するステップの後、電子計算機のＣＰＵを演算手段として機能させて、χＱを演算し、このχＱの演算結果を用いて所定の有理点を演算するステップを有することにも特徴を有する。【００２１】
また、本発明のペアリング演算プログラムでは、曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ,ａ∈Ｆp,ｂ∈Ｆpで与えられ、埋込み次数がｋで、Ｆpkを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φp−[１]),
Ｇ2＝Ｅ[r]∩Ker(φp−[ｐ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*pk/(Ｆ*pk)r
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ1、Ｑ∈Ｇ2としてＣＰＵを備えた電子計算機にペアリングｅ(Ｑ,Ｓ)を演算させるペアリング演算プログラムであって、フロベニウス自己準同型写像φpのトレースをｔとして、ペアリングｅ(Ｑ,Ｓ)をミラーのアルゴリズムを用いて計算される有理関数ｆt-1,Q(Ｓ)を用いて
【数２】
2010024401.tif 000012
として演算させる代わりに、位数ｒと、フロベニウス自己準同型写像φpのトレースｔを整数変数χの関数として、電子計算機を、有理関数ｆχ,Q(Ｓ)を演算する演算手段と、所定の有理点を通る直線の有理点Ｓ(ｘs,ｙs)における値を演算する演算手段と、これらの演算手段の演算結果を用いて有理関数f'χ,Q(Ｓ)を演算する演算手段と、この有理関数f'χ,Q(Ｓ)を用いて
【数３】
2010024401.tif 000013
として演算する演算手段として機能させることとした。【００２２】
さらに、本発明のペアリング演算プログラムでは、電子計算機を、χＱを演算する演算手段と、このχＱの演算結果を用いて所定の有理点を演算する演算手段として機能させることにも特徴を有する。
【発明の効果】
【００２３】
本発明によれば、ペアリング演算の際にミラーのアルゴリズムを用いて計算される有理関数を、整数変数χの関数とすることにより、有理関数の計算を高速に行うことができ、ペアリング演算を高速化することができる。したがって、実用性のあるディジタルグループ署名のサービスを提供できる。
【図面の簡単な説明】
【００２４】
【図１】図１は、本発明の実施形態にかかるペアリング演算装置の概略模式図である。
【図２】図２は、本発明の実施形態にかかるペアリング演算プログラムのフローチャートである。
【図３】図３は、有理関数fχ,Q(Ｓ)を演算するためのフローチャートである。
【図４】図４は、本発明の他の実施形態にかかるペアリング演算プログラムのフローチャートである。
【符号の説明】
【００２５】
10  電子計算機
11  ＣＰＵ
12  記憶装置
13  メモリ装置
14  バス
15  入出力制御部
20  電気通信回線
30  クライアント装置
【発明を実施するための最良の形態】
【００２６】
本発明のペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラムでは、ペアリング演算におけるミラーのアルゴリズムを用いて有理関数を演算する第１のステップと、その演算結果に対してべき乗算を行う第２のステップのうち、第１のステップにおいて整数変数χを用いて有理関数を演算することにより、演算を高速化している。【００２７】
すなわち、従来のペアリング演算では、曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ,ａ∈Ｆp,ｂ∈Ｆpで与えられ、埋込み次数がｋで、Ｆpkを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φp−[１]),
Ｇ2＝Ｅ[r]∩Ker(φp−[ｐ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*pk/(Ｆ*pk)r
である非退化な双線形写像としてペアリングｅを定義し、Ｓ∈Ｇ1、Ｑ∈Ｇ2、フロベニウス自己準同型写像φpのトレースをｔとして、ミラーのアルゴリズムで計算される有理関数ft-1,Q(Ｓ)を用いて、ペアリングｅ(Ｑ,Ｓ)を、Ａｔｅペアリングとして知られている次式により演算していた。
【数２】
2010024401.tif 000014
【００２８】
これに対して、本発明者らは、楕円曲線の整数変数χを用いることにより、より高速に演算が可能なペアリングを見い出した。このペアリングを、「Ｘａｔｅペアリング」と呼ぶこととする。【００２９】
すなわち、本発明のペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラムでは、ＡｔｅペアリングではなくＸａｔｅペアリングを用いることにより、高速な演算を可能としているものである。【００３０】
特に、ペアリング演算に用いられる楕円曲線は、組み込み次数に応じてそれぞれペアリングフレンドリ曲線として知られており、例えば組み込み次数ｋ＝12の場合には、位数ｒと、フロベニウス自己準同型写像φpのトレースｔが、整数変数χを用いて次のように表せることが知られている。
ｒ(χ)＝３６χ4−３６χ3＋１８χ2−６χ＋１,
ｔ(χ)＝６χ2＋１.【００３１】
また、組み込み次数ｋ＝10の場合には、次のように表せることが知られている。
ｒ(χ)＝２５χ4＋２５χ3＋１５χ2＋５χ＋１,
ｔ(χ)＝１０χ2＋５χ＋３.
あるいは、次のようにも表せることが知られている。
ｒ(χ)＝χ8−１,
ｔ(χ)＝−χ6＋χ4−χ2＋２.【００３２】
また、組み込み次数ｋ＝８の場合には、次のように表せることが知られている。
ｒ(χ)＝９χ4＋１２χ3＋８χ2＋４χ＋１,
ｔ(χ)＝−９χ3−３χ2−２χ.
あるいは、次のようにも表せることが知られている。
ｒ(χ)＝χ4−８χ2＋２５,
ｔ(χ)＝(２χ3−１１χ＋１５)／１５.
あるいは、次のようにも表せることが知られている。
ｒ(χ)＝χ8−χ4＋１,
ｔ(χ)＝χ5−χ＋１.【００３３】
また、組み込み次数ｋ＝18の場合には、次のように表せることが知られている。
ｒ(χ)＝(χ6＋３７χ3＋３４３)／３４３,
ｔ(χ)＝(χ4＋１６χ＋７)／７.【００３４】
以下において、組み込み次数ｋ＝12の場合を一例としてＸａｔｅペアリングを説明する。【００３５】
なお、組み込み次数ｋ＝12の場合には、曲線の式がｙ2＝ｘ3＋ｂ,ｂ∈Ｆpで与えられ、Ｆp12を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φp−[１]),
Ｇ2＝Ｅ[r]∩Ker(φp−[ｐ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*p12/(Ｆ*p12)r
である非退化な双線形写像としてペアリングｅを定義している。【００３６】
この場合、位数ｒと、フロベニウス自己準同型写像φpのトレースｔは、上述したように整数変数χを用いて次のように表せる。
ｒ(χ)＝３６χ4−３６χ3＋１８χ2−６χ＋１  ・・・（式１）
ｔ(χ)＝６χ2＋１  ・・・（式２）【００３７】
（式２）は次のように式変形できる。なお、特に必要でない場合には、便宜上、（χ）の表記を省略する。
６χ2≡ｔ−１≡ｐ  （mod r）  ・・・（式３）
ここで、標数ｐには次の関係式があることを用いている。
ｐ＝ｒ＋ｔ−１  ・・・（式４）【００３８】
したがって、標数ｐは整数変数χを用いて次のように表せる。
ｐ(χ)＝３６χ4−３６χ3＋２４χ2−６χ＋１・・・（式５）【００３９】
（式３）を用いて、（式５）は次のように式変形できる。
ｐ≡ｐ2−６χ（ｐ＋１）＋４ｐ＋１  （mod r）  ・・・（式６）【００４０】
この（式６）は、次のように式変形できる。
６χ(１＋ｐ)≡ｐ2＋３ｐ＋１  （mod r）  ・・・（式７）【００４１】
ここで、既に知られているｐ4−ｐ2＋１≡０（mod r）の関係式から、次の式が得られる。
ｐ2(１−ｐ)(１＋ｐ)≡１  （mod r）  ・・・（式８）【００４２】
この（式８）は、次のように式変形できる。
(１＋ｐ)-1≡ｐ2(１−ｐ)  （mod r）  ・・・（式９）【００４３】
（式９）を用いるとともに、ｐ6≡−１（mod r）の関係式から、（式７）は次のように式変形できる。
６χ≡(１＋ｐ)-1{(１＋ｐ)2＋ｐ}
≡１＋ｐ＋ｐ3＋ｐ10  （mod r）  ・・・（式１０）【００４４】
次に、Ａｔｅペアリングの有理関数ft-1,Q(・)について考える。特に、（式３）によって有理関数ft-1,Q(・)は次のように表すことができる。ここで、ｔ−１＝Ｔとしている。
【数８】
2010024401.tif 000015
【００４５】
ここで、Ｑ∈Ｇ2であり、∀Ｓ∈Ｇ1に対して、以下の式とする。
【数９】
2010024401.tif 000016
【００４６】
（式１０）を用いることにより次の式が得られる。
【数１０】
2010024401.tif 000017
【００４７】
ここで、有理関数は、次の関係式を満たすこととなっている。
【数１１】
2010024401.tif 000018
【数１２】
2010024401.tif 000019
【数１３】
2010024401.tif 000020
【００４８】
したがって、（式１３）は次のように式変形できる。
【数１４】
2010024401.tif 000021
【００４９】
なお、gaQ,bQ＝laQ,bQ／vaQ+bQであって、laQ,bQは２つの有理点ａＱとｂＱを通る直線の値、vaQ+bQは有理点ａＱ＋ｂＱの鉛直線の値である。組み込み次数が偶数の場合には、vaQ+bQの計算は省略できる。【００５０】
また、（式１７）中の
【数１５】
2010024401.tif 000022
は、双線形性を有していることから、次のように式変形できる。
【数１６】
2010024401.tif 000023
【００５１】
したがって、（式３）と（式１３）と（式１９）を用いて（式１７）を式変形することにより、次のようになる。
【数１７】
2010024401.tif 000024
【００５２】
ここで、本発明者らは、（式２０）の左辺が双線形性を有していることから、（式２０）の右辺も双線形性を有していることに思い至り、この（式２０）の右辺を新たな有理関数をf'χ,Q(・)とすることとした。【００５３】
すなわち、次の式によりペアリングｅ(Ｑ,Ｓ)の演算を行うこととするものである。
【数１８】
2010024401.tif 000025
本発明者らは、このペアリングｅ(Ｑ,Ｓ)をＸａｔｅペアリングと呼んでいる。【００５４】
さらに、（式２０）の右辺は、次のように式変形できる。
【数１９】
2010024401.tif 000026
【００５５】
すなわち、組み込み次数ｋ＝12の場合には、有理点(χＱ,ｐ10χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l1と、有理点(χＱ＋ｐ10χＱ,ｐχＱ＋ｐ3χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l2と、有理点(ｐχＱ,ｐ3χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l3をそれぞれ演算して特定しておくことにより、次の式に基づいてミラーのアルゴリズムを用いた演算を高速化できる。
【数４】
2010024401.tif 000027
【００５６】
しかも、（式２０）の右辺は、次のように式変形できるので、f'χ,Q(Ｓ)の演算をより高速化できる。
【数２０】
2010024401.tif 000028
【００５７】
以上のように、Ｘａｔｅペアリングを用いることによって、ペアリング演算を行う場合には、有理関数fχ,Q(Ｓ)と、所定の有理点を通る直線の値を用いて得られた新たな有理関数f'χ,Q(Ｓ)を用いて演算でき、特に、特に有理関数f'χ,Q(Ｓ)が、ｔ−１よりもサイズの小さいχを用いて演算できることによって、ペアリング演算を高速化できる。【００５８】
ここまでは、組み込み次数ｋ＝12の場合について説明してきたが、組み込み次数ｋ＝8,10,18の場合にも基本的に同様であるので詳細な説明は省略する。【００５９】
以下において、組み込み次数ｋ＝12の場合の実施形態について詳説する。なお、本実施形態では、ディジタルグループ署名を想定しており、所要の電子計算機で構成された認証サーバをペアリング演算装置としている。ただし、ペアリング演算装置は、認証サーバで構成する場合に限定されるものではなく、少なくともＣＰＵなどの演算手段を備えてペアリング演算が実行可能となった装置であれば、どのような装置であってもよい。【００６０】
図１に示すように、認証サーバを構成する電子計算機10は、演算処理を実行するＣＰＵ11と、ペアリング演算プログラムなどの各種プログラム、及びペアリング演算プログラムで使用するデータなどを記憶したハードディスクなどの記憶装置12と、ペアリング演算プログラムを展開して実行可能とするとともに、ペアリング演算プログラムの実行にともなって生成されたデータを一時的に記憶するＲＡＭなどで構成されたメモリ装置13を備えている。図４中、14はバスである。【００６１】
また、電子計算機10は、インターネットなどの電気通信回線20に接続して、この電気通信回線20に接続されたクライアント装置30から送信されたディジタルグループ署名の署名データを受信可能としている。図１中、15は電子計算機10の入出力制御部である。【００６２】
電子計算機10では、クライアント装置30からディジタルグループ署名の署名データが送信されると、送信された署名データをメモリ装置13に一旦記憶する。次いで、電子計算機10では、ペアリング演算プログラムを実行するすることによりペアリング演算を行っている。【００６３】
すなわち、電子計算機10では、ペアリング演算プログラムの実行にともなって、図２に示すフローチャートに基づいてペアリング演算を行い、ディジタルグループ署名を実現している。なお、ディジタルグループ署名における認証処理については詳説せず、認証処理におけるサブルーチン処理としてのペアリング演算についてのみ詳説する。【００６４】
ペアリング演算プログラムによって、電子計算機10では、図２に示すようにステップＳ１として、ＣＰＵ11を入力手段として機能させて、必要なデータの入力を行っている。すなわち、電子計算機10では、メモリ装置13にあらかじめ記憶している整数変数χのデータと有理点ＱのデータをＣＰＵ11の内部に設けている所定のレジスタに入力し、さらに、署名データとしてメモリ装置13に一旦記憶された有理点ＳのデータをＣＰＵ11の内部に設けている所定のレジスタに入力している。【００６５】
次いで、ペアリング演算プログラムによって、電子計算機10では、ステップＳ２として、ＣＰＵ11を第１演算手段として機能させて、ミラーのアルゴリズムによる有理関数fχ,Q(Ｓ)の演算を行っている。【００６６】
この有理関数fχ,Q(Ｓ)の演算は、具体的には図３のフローチャートに示すように実行している。特に、ステップＳ２では、有理関数fχ,Q(Ｓ)の演算とともにχＱの演算を行い、χＱの演算結果をＣＰＵ11の内部に設けている所定のレジスタの記憶している。【００６７】
すなわち、図３のフローチャートに基づいて、電子計算機10は、ステップＳ２１として、初期設定を行っている。すなわち、電子計算機10では、ｆ←１、Ｔ←Ｑとする処理を行い、さらにｉ←［log2(χ)］として、整数変数χを２進数表示とした場合のビット数をｉとしている【００６８】
次いで、図３のフローチャートに基づいて、電子計算機10は、ステップＳ２２として、有理関数fχ,Q(Ｓ)部分の所定の演算を行っている。【００６９】
次いで、図３のフローチャートに基づいて、電子計算機10は、ステップＳ２３として、χＱ部分の所定の演算を行っている。【００７０】
次いで、図３のフローチャートに基づいて、電子計算機10は、ステップＳ２４として、整数変数χのｉ番目のビットの値ｕiが「１」であるか「０」であるかを判定している。【００７１】
ｕi＝１の場合には、図３のフローチャートに基づいて、電子計算機10は、ステップＳ２５として、有理関数fχ,Q(Ｓ)部分の所定の演算を行い、さらに、ステップＳ２６として、χＱ部分の所定の演算を行っている。【００７２】
次いで、図３のフローチャートに基づいて、電子計算機10は、ステップＳ２７として、終了判定を行っている。【００７３】
ステップＳ２７においてｉ≠１の場合には、図３のフローチャートに基づいて、電子計算機10は、ステップＳ２８として、ｉのデクリメントを行ってステップＳ２２に戻り、ステップＳ２７においてｉ＝１となるまで有理関数fχ,Q(Ｓ)及びχＱの演算を繰り返し行っている。【００７４】
ステップＳ２７においてｉ＝１の場合には、電子計算機10は、有理関数fχ,Q(Ｓ)の演算結果、及びχＱの演算結果をそれぞれ所定のレジスタに記憶して、図３のフローチャートに基づくサブルーチンを終了している。【００７５】
次いで、ペアリング演算プログラムによって、電子計算機10では、ステップＳ３として、ＣＰＵ11を第２演算手段として機能させて、有理点ｐ10χＱ、χＱ＋ｐ10χＱ、ｐχＱ＋ｐ3χＱをそれぞれ演算している。【００７６】
特に、第２演算手段では、ステップＳ２において所定のレジスタに記憶されたχＱ＝Ｒとし、このＲのフロベニウス自己準同型写像φpがφp(Ｒ)＝ｐＲである関係を用いて、各有理点ｐ10χＱ＝ｐ10Ｒ、χＱ＋ｐ10χＱ＝Ｒ＋ｐ10Ｒ、ｐχＱ＋ｐ3χＱ＝ｐＲ＋ｐ3Ｒとして演算を行っている。【００７７】
具体的には、Ｔ＝χＱ＝Ｒであって、Ｘ＝ｐ10Ｒ、Ｙ＝Ｒ＋ｐ10Ｒ、Ｚ＝ｐＲ＋ｐ3Ｒとし、電子計算機10では、次のように演算している。
Ｘ←φp10(Ｔ),
Ｙ←Ｔ＋Ｘ,
Ｚ←φp3(Ｙ).【００７８】
したがって、ステップＳ３において、電子計算機10は、乗算処理をすることなく演算を実行できるので、演算を高速化することができる。【００７９】
次いで、ペアリング演算プログラムによって、電子計算機10では、ステップＳ４として、ＣＰＵ11を第３演算手段として機能させて、有理点(χＱ,ｐ10χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l1と、有理点(χＱ＋ｐ10χＱ,ｐχＱ＋ｐ3χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l2をそれぞれ演算している。【００８０】
具体的には、電子計算機10では、l1＝lT,X(Ｓ)を次のように演算している。
λT,X←(ｙX−ｙT)/(ｘX−ｘT),
lT,X(Ｓ)←(ｘS−ｘX)λT,X−(ｙS−ｙX).【００８１】
また、電子計算機10では、l2＝lY,Z(Ｓ)を次のように演算している。
λY,Z←(ｙZ−ｙY)/(ｘZ−ｘY),
lY,Z(Ｓ)←(ｘS−ｘZ)λY,Z−(ｙS−ｙZ).【００８２】
次いで、ペアリング演算プログラムによって、電子計算機10では、ステップＳ５として、ＣＰＵ11を第４演算手段として機能させて、第１演算手段での演算結果と、第３演算手段での演算結果と、有理点(ｐχＱ,ｐ3χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l3を用いて、次のように有理関数f'χ,Q(Ｓ)を演算している。
【数４】
2010024401.tif 000029
【００８３】
特に、この場合に、電子計算機10では、有理関数fχ,Q(Ｓ)のフロベニウス自己準同型写像φpが、φp(fχ,Q(Ｓ))＝fχ,Q(Ｓ)pであって、φp10(fχ,Q(Ｓ))＝fχ,Q(Ｓ)p⌒10（ここで、p⌒10はｐ10であることを表している）を用いて
【数５】
2010024401.tif 000030
を演算している。【００８４】
さらに、電子計算機10では、Ｑ1,Ｑ2∈Ｇ2である有理点(Ｑ1,Ｑ2)を通る直線における有理点Ｓ(ｘs,ｙs)の値lのフロベニウス自己準同型写像φpが、有理点(pＱ1,pＱ2)を通る直線における有理点Ｓ(ｘs,ｙs)の値であることを用いて
【数６】
2010024401.tif 000031
となる
【数７】
2010024401.tif 000032
を演算して有理関数f'χ,Q(Ｓ)を演算している。【００８５】
具体的には、電子計算機10は、次のように演算を行っている。ここで、p⌒3はｐ3であることを表している。
1.  Ｃ←ｆp⌒10
2.  Ｃ←Ｃ・ｆ
3.  Ａ←Ｃ・lT,X(Ｓ)
4.  Ｂ←Ａp⌒3
5.  returnＡ,Ｂ【００８６】
したがって、
【数４】
2010024401.tif 000033
は、
f'←Ａ・Ｂ・lY,Z(Ｓ)
として演算できる。【００８７】
このように、Ｘａｔｅペアリングを用いることによって演算量を大きく削減することができ、ペアリング演算を高速化できる。【００８８】
次いで、ペアリング演算プログラムによって、電子計算機10では、ステップＳ６として、ＣＰＵ11を第５演算手段として機能させて、ペアリングｅ(Ｑ,Ｓ)における最終べきのべき乗算を行っている。【００８９】
具体的には、電子計算機10は、次のように演算を行っている。
1.  f'←f'p⌒6・f'-1
2.  f'←f'p⌒2・f'
3.  ａ←(f'6)χ・(f'5)p⌒6
4.  ｂ←ａp
5.  ｂ←ａ・ｂ
6.  compute f'p,f'p⌒2,andf'p⌒3
7.  ｃ←ｂ・(f'p)2・f'p⌒2
8.  f'←f'p⌒3・(ｃ6)χ⌒2・ｃ・ｂ・(f'p・f')9・ａ・f'4
9.  Return f'【００９０】
認証サーバを構成する電子計算機10では、上述したようにして得られたペアリングの演算結果を用いて認証処理を行っている。【００９１】
本実施形態では、組み込み次数ｋ＝12の場合について説明したが、例えば組み込み次数ｋ＝10の場合でも、同様に演算できる。【００９２】
なお、組み込み次数ｋ＝10の場合には、曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ,ａ∈Ｆp,ｂ∈Ｆpで与えられ、埋込み次数が10で、Ｆp10を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φp−[１]),
Ｇ2＝Ｅ[r]∩Ker(φp−[ｐ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*p10/(Ｆ*p10)r
である非退化な双線形写像としてペアリングｅを定義している。【００９３】
この場合、位数ｒと、フロベニウス自己準同型写像φpのトレースｔは、整数変数χを用いて次のように表せる。
ｒ(χ)＝２５χ4＋２５χ3＋１５χ2＋５χ＋１,
ｔ(χ)＝１０χ2＋５χ＋３.【００９４】
また、整数変数χの標数ｐによるｐ進数展開は次のように表される。
５χ＝ｐ4＋ｐ5＋ｐ7＋ｐ8＝ｐ4(１＋ｐ＋ｐ3＋ｐ4)  （mod ｒ(χ)）.【００９５】
そして、有理点(χＱ,ｐχＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l4と、有理点(χＱ＋ｐχＱ,ｐ3χＱ＋ｐ4χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l5をそれぞれ演算し、さらに、有理点(ｐ3χＱ,ｐ4χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l6を用いることにより、有理関数f'χ,Q(Ｓ)を次の式により演算している。
【数２１】
2010024401.tif 000034
【００９６】
埋め込み次数ｋ＝12の場合と同様に、埋め込み次数ｋ＝10の場合でも、認証サーバでは、ペアリング演算プログラムを実行することにより、図４に示すフローチャートに基づいてペアリング演算を行っている。【００９７】
ペアリング演算プログラムによって、電子計算機10では、図４に示すようにステップＴ１として、ＣＰＵ11を入力手段として機能させて、必要なデータの入力を行っている。すなわち、電子計算機10では、メモリ装置13にあらかじめ記憶している整数変数χのデータと有理点ＱのデータをＣＰＵ11の内部に設けている所定のレジスタに入力し、さらに、署名データとしてメモリ装置13に一旦記憶された有理点ＳのデータをＣＰＵ11の内部に設けている所定のレジスタに入力している。【００９８】
次いで、ペアリング演算プログラムによって、電子計算機10では、ステップＴ２として、ＣＰＵ11を第１演算手段として機能させて、ミラーのアルゴリズムによる有理関数fχ,Q(Ｓ)の演算を行っている。【００９９】
なお、このステップＴ２では、図３に示したフローチャートのステップＳ２２における１番目の式を、次のようにしている。
1.  λT,T←(３ｘT2＋ａ）／（２ｙT）【０１００】
ここで、「ａ」は、ｙ2＝ｘ3＋ａｘ＋ｂ,ａ∈Ｆp,ｂ∈Ｆpで与えられた楕円曲線における１次の係数であり、この１番目の式以外は、図３に示したフローチャートと同様に有理関数fχ,Q(Ｓ)の演算を行っている。【０１０１】
また、電子計算機10は、ステップＴ２でも、有理関数fχ,Q(Ｓ)とともにχＱを演算して、演算結果を所定のレジスタに記憶している。【０１０２】
次いで、ペアリング演算プログラムによって、電子計算機10では、ステップＴ３として、ＣＰＵ11を第２演算手段として機能させて、有理点ｐχＱ、χＱ＋ｐχＱ、ｐ3χＱ＋ｐ4χＱをそれぞれ演算している。【０１０３】
特に、第２演算手段では、ステップＴ２において所定のレジスタに記憶されたχＱ＝Ｒとし、このＲのフロベニウス自己準同型写像φpがφp(Ｒ)＝ｐＲである関係を用いて、各有理点ｐχＱ＝ｐＲ、χＱ＋ｐχＱ＝Ｒ＋ｐＲ、ｐ3χＱ＋ｐ4χＱ＝ｐ3Ｒ＋ｐ4Ｒとして演算を行っている。【０１０４】
具体的には、Ｔ＝χＱ＝Ｒであって、Ｘ＝ｐＲ、Ｙ＝Ｒ＋ｐＲ、Ｚ＝ｐ3Ｒ＋ｐ4Ｒとし、電子計算機10では、次のように演算している。
Ｘ←φp(Ｔ),
Ｙ←Ｔ＋Ｘ,
Ｚ←φp3(Ｙ).【０１０５】
次いで、ペアリング演算プログラムによって、電子計算機10では、ステップＴ４として、ＣＰＵ11を第３演算手段として機能させて、有理点(χＱ,ｐχＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l4と、有理点(χＱ＋ｐχＱ,ｐ3χＱ＋ｐ4χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l5をそれぞれ演算している。【０１０６】
具体的には、電子計算機10では、l4＝lT,X(Ｓ)を次のように演算している。
λT,X←(ｙX−ｙT)/(ｘX−ｘT),
lT,X(Ｓ)←(ｘS−ｘX)λT,X−(ｙS−ｙX).【０１０７】
また、電子計算機10では、l5＝lY,Z(Ｓ)を次のように演算している。
λY,Z←(ｙZ−ｙY)/(ｘZ−ｘY),
lY,Z(Ｓ)←(ｘS−ｘZ)λY,Z−(ｙS−ｙZ).【０１０８】
次いで、ペアリング演算プログラムによって、電子計算機10では、ステップＴ５として、ＣＰＵ11を第４演算手段として機能させて、第１演算手段での演算結果と、第３演算手段での演算結果と、有理点(ｐ3χＱ,ｐ4χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l6を用いて、次のように有理関数f'χ,Q(Ｓ)を演算している。
【数２１】
2010024401.tif 000035
【０１０９】
特に、この場合に、電子計算機10では、有理関数fχ,Q(Ｓ)のフロベニウス自己準同型写像φpが、φp(fχ,Q(Ｓ))＝fχ,Q(Ｓ)pであることを用いて
【数２２】
2010024401.tif 000036
を演算している。【０１１０】
さらに、電子計算機10では、Ｑ1,Ｑ2∈Ｇ2である有理点(Ｑ1,Ｑ2)を通る直線における有理点Ｓ(ｘs,ｙs)の値lのフロベニウス自己準同型写像φpが、有理点(pＱ1,pＱ2)を通る直線における有理点Ｓ(ｘs,ｙs)の値であることを用いて
【数２３】
2010024401.tif 000037
となる
【数２４】
2010024401.tif 000038
を演算して有理関数f'χ,Q(Ｓ)を演算している。【０１１１】
具体的には、電子計算機10は、次のように演算を行っている。ここで、p⌒3はｐ3であることを表している。
1.  Ｃ←ｆp
2.  Ｃ←Ｃ・ｆ
3.  Ａ←Ｃ・lT,X(Ｓ)
4.  Ｂ←Ａp⌒3
5.  returnＡ,Ｂ【０１１２】
さらに、電子計算機10は、
1.  f'←Ａ・Ｂ・lY,Z(Ｓ)
2.  f'←f'p⌒4
として演算することにより、
【数２１】
2010024401.tif 000039
を演算している。【０１１３】
次いで、ペアリング演算プログラムによって、電子計算機10では、ステップＴ６として、ＣＰＵ11を第５演算手段として機能させて、ペアリングｅ(Ｑ,Ｓ)における最終べきのべき乗算を行っている。【０１１４】
認証サーバを構成する電子計算機10では、上述したようにして得られたペアリングの演算結果を用いて認証処理を行っている。【０１１５】
また、組み込み次数ｋ＝10の場合には、ミラーのアルゴリズムを用いて計算される有理関数をfχ⌒2,Q(Ｓ)（χ⌒2はχ2であることを示す）としてペアリングｅ(Ｑ,Ｓ)を演算することもできる。【０１１６】
この場合、位数ｒと、フロベニウス自己準同型写像φpのトレースｔは、整数変数χを用いて次のように表せる。
ｒ(χ)＝χ8−１,
ｔ(χ)＝−χ6＋χ4−χ2＋２.【０１１７】
また、整数変数χの標数ｐによるｐ進数展開は次のように表される。
ｐχ2＝−ｐ  （mod ｒ(χ)）.【０１１８】
そして、電子計算機10では、有理関数f'χ,Q(Ｓ)を次の式により演算している。
【数２５】
2010024401.tif 000040
【０１１９】
したがって、ペアリング演算プログラムによって、電子計算機10では、ペアリングｅ(Ｑ,Ｓ)を
【数２６】
2010024401.tif 000041
として演算することができる。【０１２０】
また、組み込み次数ｋ＝8の場合には、曲線の式がｙ2＝ｘ3＋ａｘ,ａ∈Ｆpで与えられ、Ｆp8を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φp−[１]),
Ｇ2＝Ｅ[r]∩Ker(φp−[ｐ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*p8/(Ｆ*p8)r
である非退化な双線形写像としてペアリングｅを定義している。【０１２１】
この場合、位数ｒと、フロベニウス自己準同型写像φpのトレースｔは、整数変数χを用いて次のように表せる。
ｒ(χ)＝９χ4＋１２χ3＋８χ2＋４χ＋１,
ｔ(χ)＝−９χ3−３χ2−２χ.【０１２２】
また、整数変数χの標数ｐによるｐ進数展開は次のように表される。
３χ＝−１−ｐ2＋ｐ3  （mod ｒ(χ)）.【０１２３】
そして、有理点(χＱ,χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l7と、有理点(２χＱ,χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l8と、有理点(ｐ2Ｑ,(３χ＋１)Ｑ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l9と、有理点(３χＱ,Ｑ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l10を用いることにより、電子計算機10では、有理関数f'χ,Q(Ｓ)を次の式により演算している。
【数２７】
2010024401.tif 000042
【０１２４】
すなわち、ペアリング演算プログラムによって、電子計算機10では、上述したようにミラーのアルゴリズムによる有理関数fχ,Q(Ｓ)の演算を行い、有理関数fχ,Q(Ｓ)とともにχＱを演算して、演算結果を所定のレジスタに記憶している。【０１２５】
次いで、電子計算機10では、所定のレジスタに記憶されたχＱ＝Ｒとし、このＲのフロベニウス自己準同型写像φpがφp(Ｒ)＝ｐＲである関係を用いて、各有理点２χＱ、ｐ2χ、３χＱ、(３χ＋１)Ｑを演算して、この演算結果を用いて各値l7,l8,l9,l10を演算し、有理関数f'χ,Q(Ｓ)を演算している。【０１２６】
そして、電子計算機10では、ペアリングｅ(Ｑ,Ｓ)を
【数２８】
2010024401.tif 000043
として演算することができる。【０１２７】
なお、組み込み次数ｋ＝8の場合には、位数ｒと、フロベニウス自己準同型写像φpのトレースｔを、整数変数χを用いて次のように表すこともできる。
ｒ(χ)＝χ4−８χ2＋２５,
ｔ(χ)＝(２χ3−１１χ＋１５)／１５.【０１２８】
この場合、整数変数χの標数ｐによるｐ進数展開は次のように表される。
χ＝−ｐ＋２ｐ3  （mod ｒ(χ)）.【０１２９】
この場合には、有理点(ｐＱ,χＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l11を用いて有理関数f'χ,Q(Ｓ)を次の式により演算することもできる。
【数２９】
2010024401.tif 000044
【０１３０】
あるいは、組み込み次数ｋ＝8の場合において、ミラーのアルゴリズムを用いて計算される有理関数をfχ⌒2,Q(Ｓ)（χ⌒2はχ2であることを示す）及びfχ,Q(Ｓ)としてペアリングｅ(Ｑ,Ｓ)を演算することもできる。【０１３１】
このとき、位数ｒと、フロベニウス自己準同型写像φpのトレースｔは、整数変数χを用いて次のように表すことができる。
ｒ(χ)＝χ8−χ4＋１,
ｔ(χ)＝χ5−χ＋１.【０１３２】
この場合、整数変数χの標数ｐによるｐ進数展開は次のように表される。
ｐχ＋χ2＝−ｐ2  （mod ｒ(χ)）【０１３３】
この場合には、有理点(χ2Ｑ,ｐχＱ)を通る直線における有理点Ｓ(ｘs,ｙs)の値l12を用いて有理関数f'χ,Q(Ｓ)を次の式により演算することができる。
【数３０】
2010024401.tif 000045
【０１３４】
ここで、電子計算機10では、上述したようにミラーのアルゴリズムによる有理関数fχ⌒2,Q(Ｓ)及び有理関数fχ,Q(Ｓ)の演算を行うとともにχＱを演算して、演算結果を所定のレジスタに記憶している。【０１３５】
そして、電子計算機10では、所定のレジスタに記憶されたχＱ＝Ｒとし、このＲのフロベニウス自己準同型写像φpがφp(Ｒ)＝ｐＲである関係を用いて、有理点ｐχＱを演算して、この演算結果を用いて前記の値l12を演算し、有理関数f'χ,Q(Ｓ)を演算し、ペアリングｅ(Ｑ,Ｓ)を
【数２８】
2010024401.tif 000046
として演算することができる。【０１３６】
また、組み込み次数ｋ＝18の場合には、曲線の式がｙ2＝ｘ3＋ｂ,ｂ∈Ｆpで与えられ、Ｆp18を定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φpをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φp−[１]),
Ｇ2＝Ｅ[r]∩Ker(φp−[ｐ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*p18/(Ｆ*p18)r
である非退化な双線形写像としてペアリングｅを定義している。【０１３７】
この場合、位数ｒと、フロベニウス自己準同型写像φpのトレースｔは、整数変数χを用いて次のように表せる。
ｒ(χ)＝(χ6＋３７χ3＋３４３)／３４３,
ｔ(χ)＝(χ4＋１６χ＋７)／７.【０１３８】
この場合、整数変数χの標数ｐによるｐ進数展開は次のように表される。
χ＝−３ｐ＋ｐ4  （mod ｒ(χ)）.【０１３９】
そして、有理点(３ｐＱ,χＱ)を通る直線の有理点Ｓ(ｘs,ｙs)の値l13、電子計算機10では、有理関数f'χ,Q(Ｓ)を次の式により演算している。
【数３１】
2010024401.tif 000047
【０１４０】
すなわち、ペアリング演算プログラムによって、電子計算機10では、上述したようにミラーのアルゴリズムによる有理関数fχ,Q(Ｓ)の演算を行い、有理関数fχ,Q(Ｓ)とともにχＱを演算して、演算結果を所定のレジスタに記憶している。【０１４１】
次いで、電子計算機10では、有理関数fχ,Q(Ｓ)とχＱの演算結果を用いて前記の値l13を演算し、有理関数f'χ,Q(Ｓ)を演算して、ペアリングｅ(Ｑ,Ｓ)を
【数３２】
2010024401.tif 000048
として演算することができる。【０１４２】
以上のように、Ｘａｔｅペアリングによってペアリング演算を行うことにより、ペアリング演算を高速化でき、ペアリング演算を用いたグループ署名を実用化させることができる。
【産業上の利用可能性】
【０１４３】
本発明によれば、高速なペアリング演算装置を提供でき、実用性のあるディジタルグループ署名のサービスを提供できる。
【図１】
2010024401.tif 000060
【図２】
2010024401.tif 000061
【図３】
2010024401.tif 000062
【図４】
2010024401.tif 000063
【国際調査報告】
2010024401.tif 000064
2010024401.tif 000065
2010024401.tif 000066