ペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラム
【課題】ペアリング演算を高速に実行可能としたペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラムを提供する。
【解決手段】Ａｔｅペアリングｅ(Ｑ,Ｐ)を
【数４９】
とし、ｋが偶数、３の倍数、４の倍数、６の倍数のいずれかである場合に、ミラー関数fs,Q(Ｐ)の導出に必要となる有理関数の演算を、このfs,Q(Ｐ)の（ｑk−１）／ｒ乗のべき乗算の演算によって１となる平方非剰余あるいは３乗非剰余なｖを用いたツイスト曲線により特定される真部分体上の演算として行う。
【解決手段】Ａｔｅペアリングｅ(Ｑ,Ｐ)を
【数４９】
とし、ｋが偶数、３の倍数、４の倍数、６の倍数のいずれかである場合に、ミラー関数fs,Q(Ｐ)の導出に必要となる有理関数の演算を、このfs,Q(Ｐ)の（ｑk−１）／ｒ乗のべき乗算の演算によって１となる平方非剰余あるいは３乗非剰余なｖを用いたツイスト曲線により特定される真部分体上の演算として行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ペアリング演算を高速に実行可能としたペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラムに関する。
【背景技術】
【０００２】
昨今、高速な電気通信回線が低価格で利用可能となったことにより、インターネットなどのネットワーク上において、音楽や映像の配信、インターネットバンキング、行政機関への電子申請などのような各種のサービスが提供可能となっている。
【０００３】
また、企業による業務形態も変化しており、ノートパソコンや携帯電話などのいわゆるモバイル端末装置を用いて外出先などから会社のサーバ装置にアクセスして、各種の情報の入力あるいは取得が可能となっている。
【０００４】
特に、日本では、携帯電話をネットワークへの接続装置として利用するサービスが充実しており、いかなる所からでも所要のネットワークにアクセスして各種の情報を入手したり、サービスを利用したりすることができるいわゆるユビキタス社会の到来がいよいよ現実味を帯びてきた。
【０００５】
このように各種の情報を取得したり、サービスを利用したりするためにネットワークにアクセスする際には、所要の認証手段を備えた認証サーバによって認証処理が行われ、ネットワークにアクセスした利用者が、あらかじめ登録されている特定の利用者であることが認証されて、情報の取得あるいはサービスの利用が可能となっている。
【０００６】
特に、最近では、ディジタル署名技術を用いることにより、取り扱っている情報が第三者によって改ざんされていないこと、あるいは第三者に漏洩していないことを保証可能として、秘匿性の高い情報もネットワーク上で安全に取り扱い可能となっていることにより、さらに積極的にネットワークが利用されることとなっている。
【０００７】
ただし、このディジタル署名では、利用者個人が特定されるため、認証サーバにおける認証処理に基づいて認証サーバに利用者の履歴が情報として蓄積されることとなっており、この履歴情報は一種の個人情報であって、個人情報保護の問題があった。
【０００８】
そこで、ディジタル署名を拡張したディジタルグループ署名を用いることが提案されている。ディジタルグループ署名を用いた場合には、利用者は、認証サーバに対して匿名でグループに属していることのみを証明する署名データを送信し、認証サーバでは、受信した署名データから利用者を特定することなく利用者が所定のグループに属していることを認証している。したがって、認証サーバに各利用者の使用の履歴情報が蓄積されることを防止できる一方で、グループに属さない利用者による不正利用を阻止可能としている。
【０００９】
ここで、ディジタルグループ署名における匿名認証には、ペアリング演算が用いられている。ペアリング演算では、２入力１出力の関数を用いた演算を行っており、たとえば、Ｐを素体Ｆq上の有理点、Ｑをｋ次拡大体Ｆqk上の有理点として、ペアリングでＰとＱとを入力して拡大体Ｆ*qkの元ｚが出力されるとき、ａ倍のＰと、ｂ倍のＱを入力するとｚのab乗が算出されることを利用しているものであり、このような性質のことを双線形性と呼ぶ。なお、ここで、「ｋ」を埋込み次数と呼び、「Ｆ*qk」は、正しくは、以下の表示であるが、表示の制限上、「Ｆ*qk」と表示している。
【数１３】
【００１０】
一般的に、有理点Ｐ，Ｑはそれぞれ楕円曲線上の点が用いられ、このような楕円曲線のペアリングの演算は、ミラーのアルゴリズムを用いて演算するステップと、最終べきのべき乗演算を行うステップとで構成されている。
【００１１】
たとえば、10,000人のメンバーで構成されるグループのディジタルグループ署名であって、各メンバーのアクセス権の発行と失効とを柔軟に対応可能とするために、ディジタルグループ署名の検証時に失効者分のペアリング演算を行う方式が知られている。この場合、失効者が100人であれば100回のペアリング演算が必要であり、現時点での一般的な電子計算機による１回のペアリングの演算に約0.1秒を要していることから、100回のペアリング演算には10秒を要することとなって、大規模なディジタルグループ署名での利用は実用的とは言えなかった。
【００１２】
そこで、ペアリングの演算速度を向上させるために様々な開発が行われており、たとえば有限体上の楕円曲線上で定義されるＴａｔｅペアリング演算における高速化の技術が提案されている（例えば、特許文献１参照。）。
【特許文献１】特開２００５−３１６２６７号公報
【発明の開示】
【発明が解決しようとする課題】
【００１３】
しかしながら、現在提案されているペアリング演算の高速化技術では、未だに大規模なディジタルグループ署名での利用に適う速度とはなっておらず、ディジタルグループ署名のメンバー数を制限しなければならないという問題があった。
【００１４】
本発明者らは、このような現状に鑑み、ペアリング演算を高速化すべく研究開発を行って、本発明を成すに至ったものである。
【課題を解決するための手段】
【００１５】
本発明のペアリング演算装置では、曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ，ａ∈Ｆq，ｂ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が２ｈ次(ｈ：自然数)で、Ｆq2hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q2h/(Ｆ*q2h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数１４】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算装置において、fs,Q(Ｐ)の導出に必要となる有理関数の演算を、このfs,Q(Ｐ)の(ｑ2h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-2ｘ＋ｂｖ-3による真部分体上で行うこととした。
【００１６】
特に、
・ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付ける入力手段、
・有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1、ｍ←ｙPｖ-3/2の代入演算を行うとともに、ｆ←１、Ｔ'←Ｑ'の代入演算を行う代入手段、
・有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行う第１演算手段、
・Ｔ'←２Ｔ'の代入演算を行う第２演算手段、
・ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行う第３演算手段、
・ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行う第４演算手段、
・(ｑ2h−１)/r乗のべき乗算を演算する第５演算手段
を備えたことにも特徴を有するものである。
【００１７】
また、本発明のペアリング演算装置では、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が３ｈ次(ｈ：自然数)で、Ｆq3hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q3h/(Ｆ*q3h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数１５】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算装置において、
fs,Q(Ｐ)の導出に必要となる有理関数の演算を、このfs,Q(Ｐ)の(ｑ3h−１)／ｒ乗のべき乗算の演算によって１となる平方剰余かつ３乗非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1による真部分体上で行うこととした。
【００１８】
特に、
・ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付ける入力手段、
・有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行うとともに、ｆ←１、Ｔ'←Ｑ'の代入演算を行う代入手段、
・有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行う第１演算手段、
・Ｔ'←２Ｔ'の代入演算を行う第２演算手段、
・ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行う第３演算手段、
・ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行う第４演算手段、
・(ｑ3h−１)/r乗のべき乗算を演算する第５演算手段
を備えたことにも特徴を有するものである。
【００１９】
また、本発明のペアリング演算装置では、曲線の式がｙ2＝ｘ3＋ａｘ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が４ｈ次(ｈ：自然数)で、４がｑh−１を割り切るものとし、Ｆq4hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q4h/(Ｆ*q4h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数１６】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算装置において、fs,Q(Ｐ)の導出に必要となる有理関数の演算を、このfs,Q(Ｐ)の(ｑ4h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1ｘによる真部分体上で行うこととした。
【００２０】
特に、
・ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付ける入力手段、
・有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1/2、ｍ←ｙPｖ-3/4の代入演算を行うとともに、ｆ←１、Ｔ'←Ｑ'の代入演算を行う代入手段、
・有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/4をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行う第１演算手段、
・Ｔ'←２Ｔ'の代入演算を行う第２演算手段、
・ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/4をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行う第３演算手段、
・ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行う第４演算手段、
・(ｑ4h−１)/r乗のべき乗算を演算する第５演算手段と
を備えたことにも特徴を有するものである。
【００２１】
また、本発明のペアリング演算装置では、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が６ｈ次(ｈ：自然数)で、Ｆq6hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q6h/(Ｆ*q6h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数１７】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算装置において、fs,Q(Ｐ)の導出に必要となる有理関数の演算を、このfs,Q(Ｐ)の(ｑ6h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余かつ３乗非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1による真部分体上で行うこととした。
【００２２】
特に、
・ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付ける入力手段、
・有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行うとともに、ｆ←１、Ｔ'←Ｑ'の代入演算を行う代入手段、
・有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行う第１演算手段、
・Ｔ'←２Ｔ'の代入演算を行う第２演算手段、
・ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行う第３演算手段、
・ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行う第４演算手段、
・(ｑ6h−１)/r乗のべき乗算を演算する第５演算手段と
を備えたことにも特徴を有するものである。
【００２３】
また、本発明のペアリング演算方法では、曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ，ａ∈Ｆq，ｂ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が２ｈ次(ｈ：自然数)で、Ｆq2hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q2h/(Ｆ*q2h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数１８】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算方法において、fs,Q(Ｐ)の(ｑ2h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-2ｘ＋ｂｖ-3を用い、
・入力手段によって、ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆp)であるＰ、Ｑ'∈Ｅ'(Ｆp2)であるＱ'の入力を受け付けるステップ、
・代入手段によって、有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1、ｍ←ｙPｖ-3/2の代入演算を行うステップ、
・代入手段によって、ｆ←１、Ｔ'←Ｑ'の代入演算を行うステップ、
・第１演算手段によって、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行うステップ、
・第２演算手段によって、Ｔ'←２Ｔ'の代入演算を行うステップ、
・第３演算手段によって、ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行うステップ、
・第４演算手段によって、ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行うステップ
・第５演算手段によって、(ｑ2h−１)/r乗のべき乗算の演算を行うステップと
を有することとした。
【００２４】
また、本発明のペアリング演算方法では、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が３ｈ次(ｈ：自然数)で、Ｆq3hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q3h/(Ｆ*q3h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数１９】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算方法において、fs,Q(Ｐ)の(ｑ3h−１)／ｒ乗のべき乗算の演算によって１となる平方剰余かつ３乗非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1を用い、
・入力手段によって、ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けるステップ、
・代入手段によって、有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行うステップ、
・代入手段によって、ｆ←１、Ｔ'←Ｑ'の代入演算を行うステップ、
・第１演算手段によって、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行うステップ、
・第２演算手段によって、Ｔ'←２Ｔ'の代入演算を行うステップ、
・第３演算手段によって、ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行うステップ、
・第４演算手段によって、ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行うステップ、
・第５演算手段によって、(ｑ3h−１)/r乗のべき乗算の演算を行うステップと
を有することとした。
【００２５】
また、本発明のペアリング演算方法では、曲線の式がｙ2＝ｘ3＋ａｘ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が４ｈ次(ｈ：自然数)で、４がｑh−１を割り切るものとし、Ｆq4hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q4h/(Ｆ*q4h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数２０】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算方法において、fs,Q(Ｐ)の(ｑ4h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1ｘを用い、
・入力手段によって、ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けるステップ、
・代入手段によって、有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1/2、ｍ←ｙPｖ-3/4の代入演算を行うステップ、
・代入手段によって、ｆ←１、Ｔ'←Ｑ'の代入演算を行うステップ、
・第１演算手段によって、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/4をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行うステップ、
・第２演算手段によって、Ｔ'←２Ｔ'の代入演算を行うステップ、
・第３演算手段によって、ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/4をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行うステップ、
・第４演算手段によって、ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行うステップ、
・第５演算手段によって、(ｑ4h−１)/r乗のべき乗算の演算を行うステップと
を有することとした。
【００２６】
また、本発明のペアリング演算方法では、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が６ｈ次(ｈ：自然数)で、Ｆq6hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q6h/(Ｆ*q6h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数２１】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算方法において、fs,Q(Ｐ)の(ｑ6h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余かつ３乗非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1を用い、
・入力手段によって、ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けるステップ、
・代入手段によって、有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行うステップ、
・代入手段によって、ｆ←１、Ｔ'←Ｑ'の代入演算を行うステップ、
・第１演算手段によって、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行うステップ、
・第２演算手段によって、Ｔ'←２Ｔ'の代入演算を行うステップ、
・第３演算手段によって、ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行うステップ、
・第４演算手段によって、ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行うステップ、
・第５演算手段によって、(ｑ6h−１)/r乗のべき乗算の演算を行うステップと
を有することとした。
【００２７】
また、本発明のペアリング演算プログラムでは、曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ，ａ∈Ｆq，ｂ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が２ｈ次(ｈ：自然数)で、Ｆq2hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q2h/(Ｆ*q2h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数２２】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を電子計算機に演算させるペアリング演算プログラムにおいて、fs,Q(Ｐ)の(ｑ2h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-2ｘ＋ｂｖ-3を用い、
・電子計算機を入力手段として機能させて、ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けさせるステップ、
・電子計算機を代入手段として機能させて、有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1、ｍ←ｙPｖ-3/2の代入演算を行わせるステップ、
・電子計算機を代入手段として機能させて、ｆ←１、Ｔ'←Ｑ'の代入演算を行わせるステップ、
・電子計算機を第１演算手段として機能させて、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行わせるステップ、
・電子計算機を第２演算手段として機能させて、Ｔ'←２Ｔ'の代入演算を行わせるステップ、
・電子計算機を第３演算手段として機能させて、ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行わせるステップ、
・電子計算機を第４演算手段として機能させて、ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行わせるステップ、
・電子計算機を第５演算手段として機能させて、(ｑ2h−１)/r乗のべき乗算の演算を行わせるステップと
を有することとした。
【００２８】
また、本発明のペアリング演算プログラムでは、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が３ｈ次(ｈ：自然数)で、Ｆq3hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q3h/(Ｆ*q3h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数２３】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を電子計算機に演算させるペアリング演算プログラムにおいて、fs,Q(Ｐ)の(ｑ3h−１)／ｒ乗のべき乗算の演算によって１となる平方剰余かつ３乗非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1を用い、
・電子計算機を入力手段として機能させて、ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けさせるステップ、
・電子計算機を代入手段として機能させて、有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行わせるステップ、
・電子計算機を代入手段として機能させて、ｆ←１、Ｔ'←Ｑ'の代入演算を行わせるステップ、
・電子計算機を第１演算手段として機能させて、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行わせるステップ、
・電子計算機を第２演算手段として機能させて、Ｔ'←２Ｔ'の代入演算を行わせるステップ、
・電子計算機を第３演算手段として機能させて、ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行わせるステップ、
・電子計算機を第４演算手段として機能させて、ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行わせるステップ、
・電子計算機を第５演算手段として機能させて、(ｑ3h−１)/r乗のべき乗算の演算を行わせるステップと
を有することとした。
【００２９】
また、本発明のペアリング演算プログラムでは、曲線の式がｙ2＝ｘ3＋ａｘ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が４ｈ次(ｈ：自然数)で、４がｑh−１を割り切るものとし、Ｆq4hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q4h/(Ｆ*q4h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数２４】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を電子計算機に演算させるペアリング演算プログラムにおいて、fs,Q(Ｐ)の(ｑ4h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1ｘを用い、
・電子計算機を入力手段として機能させて、ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けさせるステップ、
・電子計算機を代入手段として機能させて、有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1/2、ｍ←ｙPｖ-3/4の代入演算を行わせるステップ、
・電子計算機を代入手段として機能させて、ｆ←１、Ｔ'←Ｑ'の代入演算を行わせるステップ、
・電子計算機を第１演算手段として機能させて、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/4をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行わせるステップ、
・電子計算機を第２演算手段として機能させて、Ｔ'←２Ｔ'の代入演算を行わせるステップ、
・電子計算機を第３演算手段として機能させて、ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/4をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行わせるステップ、
・電子計算機を第４演算手段として機能させて、ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行わせるステップ、
・電子計算機を第５演算手段として機能させて、(ｑ4h−１)/r乗のべき乗算の演算を行わせるステップと
を有することとした。
【００３０】
また、本発明のペアリング演算プログラムでは、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が６ｈ次(ｈ：自然数)で、Ｆq6hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q6h/(Ｆ*q6h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数２５】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を電子計算機に演算させるペアリング演算プログラムにおいて、fs,Q(Ｐ)の(ｑ6h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余かつ３乗非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1を用い、
・電子計算機を入力手段として機能させて、ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けさせるステップ、
・電子計算機を代入手段として機能させて、有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行わせるステップ、
・電子計算機を代入手段として機能させて、ｆ←１、Ｔ'←Ｑ'の代入演算を行わせるステップ、
・電子計算機を第１演算手段として機能させて、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行わせるステップ、
・電子計算機を第２演算手段として機能させて、Ｔ'←２Ｔ'の代入演算を行わせるステップ、
・電子計算機を第３演算手段として機能させて、ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行わせるステップ、
・電子計算機を第４演算手段として機能させて、ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行わせるステップ、
・電子計算機を第５演算手段として機能させて、(ｑ6h−１)/r乗のべき乗算の演算を行わせるステップと
を有することとした。
【発明の効果】
【００３１】
本発明では、ペアリング演算に際して、fs,Q(Ｐ)の導出に必要となる有理関数の演算を、ツイスト曲線を用いて低次の真部分体上で行うことにより演算負荷を低減して、ペアリング演算の高速化を図ることができる。
【発明を実施するための最良の形態】
【００３２】
本発明のペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラムでは、ミラーのアルゴリズムを用いて演算するステップと、最終べきのべき乗演算を行うステップとで構成されるペアリング演算において、ミラーのアルゴリズムを用いた演算を高速化することにより、高速演算を可能としているものである。
【００３３】
ミラーのアルゴリズムは、図１に示すアルゴリズムとして知られているものである。曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ，ａ∈Ｆq，ｂ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が２ｈ次(ｈ：自然数)で、Ｆq2hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、ミラーのアルゴリズムでは、フロベニウス自己準同型写像φqのトレースｔを用いたｓ＝ｔ−１と、Ｐ∈Ｅ(Ｆq)であるＰと、Ｑ∈Ｅ(Ｆq2h)であるＱとが入力されることにより、fs,Q(Ｐ)を出力している。
【００３４】
なお、埋込み次数は偶数次に限定されるものではなく、埋込み次数を３の倍数次とする場合には、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が３ｈ次(ｈ：自然数)で、Ｆq3hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群を用いることが望ましい。
【００３５】
また、特に、埋込み次数が４の倍数次の場合には、曲線の式がｙ2＝ｘ3＋ａｘ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が４ｈ次(ｈ：自然数)で、４がｑh−１を割り切るものとし、Ｆq4hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群を用いることが望ましい。
【００３６】
さらに、特に、埋込み次数が６の倍数次の場合には、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が６ｈ次(ｈ：自然数)で、Ｆq6hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群を用いることが望ましい。
【００３７】
図１に示すミラーのアルゴリズムの第１ステップでは、ｆ←１、Ｔ←Ｑの代入演算を行い、第２ステップの繰り返し条件に基づいて以下の演算を繰り返し行っている。第２ステップでは、具体的には、２進数表示したｓによって得られるビット数をｉの初期値とし、演算の繰り返しのたびにｉを１ずつ減算しながら繰り返し回数を管理している。第５ステップのｓ[i]は、２進数表示したｓの最小ビットから数えてｉ番目のビットの値を示すものであって、ｓ[i]は「０」と「１」のいずれか一方である。
【００３８】
図１に示すミラーのアルゴリズムの第３ステップでは、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)の演算を行っており、第４ステップでは、Ｔ←２Ｔとして楕円二倍算を行っている。
【００３９】
図１に示すミラーのアルゴリズムの第５ステップでは、ｓを２進数表示とした場合の所定のビットの値ｓ[i]が１であるか否かを判定し、１である場合に、第６ステップで有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)の演算を行い、第７ステップで、Ｔ←Ｔ＋Ｑとして楕円加算を行っている。
【００４０】
そして、第２ステップの繰り返し条件に基づいて演算を繰り返し行って、図１に示すミラーのアルゴリズムの第１０ステップでは、演算結果を出力している。ペアリング演算では、最後に、ミラーのアルゴリズムによって演算されて出力された演算結果のfs,Q(Ｐ)に対して(ｑ2h−１)/r乗のべき乗算を行っている。
【００４１】
なお、埋込み次数が３の倍数次の場合には、最終べきのべき乗算は(ｑ3h−１)/r乗のべき乗算であり、埋込み次数が４の倍数次の場合には、最終べきのべき乗算は(ｑ4h−１)/r乗のべき乗算であり、埋込み次数が６の倍数次の場合には、最終べきのべき乗算は(ｑ6h−１)/r乗のべき乗算である。
【００４２】
以下において、第３ステップでのlT,T(ｘP，ｙP)の演算、及び第５ステップでのlT,Q(ｘP，ｙP)の演算方法を説明する。ここで、埋込み次数を偶数次、すなわち２ｈ(ｈ：自然数)次として、楕円曲線をｙ2＝ｘ3＋ａｘ＋ｂ，ａ∈Ｆq，ｂ∈Ｆq(ｑ：３より大きい素数のべき乗)とする。
【００４３】
Ｔ＝(ｘT，ｙT),Ｑ＝(ｘQ，ｙQ)とすると、lT,Q(ｘ，ｙ)の傾きλT,Qは次式で与えられる。
【数２６】
【数２７】
【００４４】
この傾きλT,Qを用いてlT,Q(ｘP，ｙP)の値を以下のように計算する。
【数２８】
【００４５】
通常では、この［数２６］及び［数２７］によってＥ(Ｆq2h)上で演算を行っているのであるが、埋込み次数を偶数次、すなわち２ｈ(ｈ：自然数)次として、楕円曲線をｙ2＝ｘ3＋ａｘ＋ｂ，ａ∈Ｆq，ｂ∈Ｆq(ｑ：３より大きい素数のべき乗)とした場合には、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-2ｘ＋ｂｖ-3，ｖ∈Ｆqhが存在して、Ｅ'(Ｆqh)からＥ(Ｆq2h)への準同型写像(ｘ，ｙ)→(ｘｖ、ｙｖ3/2)が存在する。ここで、新たなパラメータｖは、(ｑ2h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余な元である。
【００４６】
したがって、Ｅ(Ｆq2h)[r]上の楕円加算を１／２の拡大次数のＥ'(Ｆqh)[r]上の楕円加算に置き換えて演算することが可能であり、演算負荷を低減して高速な演算を可能とすることができる。
【００４７】
特に、有理点Ｔ、Ｑ∈Ｅ(Ｆq2h)に対して、Ｔ＝(ｘT，ｙT)＝(ｘT'ｖ、ｙT'ｖ3/2)、Ｑ＝(ｘQ，ｙQ)＝(ｘQ'ｖ、ｙQ'ｖ3/2)の関係が成り立つ有理点Ｔ'、Ｑ'がＥ'(Ｆqh)に存在するので、まず、lT,T(ｘ，ｙ)の傾きλT,T、及びlT,Q(ｘ，ｙ)の傾きλT,Qを以下のように変形する。
【数２９】
【数３０】
【００４８】
［数２９］と［数３０］から、Ｔ＝Ｑ、Ｔ≠Ｑにかかわらず傾きλT,Qは、以下のようになる。
【数３１】
【００４９】
したがって、［数３１］の式から、［数２８］の式は以下のようになる。
【数３２】
【００５０】
この［数３２］の式の最後のｖ3/2の部分は、ペアリング演算における(ｑ2h−１)/r乗の最終べきの演算によって１となるので、ミラーのアルゴリズムにおけるlT,Q(ｘP，ｙP)を演算する際には、lT,Q(ｘP，ｙP)の演算を行うのではなく、lT',Q'(ｘPｖ-1，ｙPｖ-3/2)を真部分体上において演算すればよく、演算負荷を大きく低減することができる。
【００５１】
すなわち、曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ，ａ∈Ｆq，ｂ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が２ｈ次(ｈ：自然数)で、Ｆq2hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q2h/(Ｆ*q2h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数３３】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算する場合に、fs,Q(Ｐ)の導出に必要となる有理関数lT,T(ｘP，ｙP)及びlT,Q(ｘP，ｙP)の演算を、このfs,Q(Ｐ)の(ｑ2h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-2ｘ＋ｂｖ-3による真部分体上でlT',T'(ｘPｖ-1，ｙPｖ-3/2)及びlT',Q'(ｘPｖ-1，ｙPｖ-3/2)の演算として行うことにより、演算負荷を低減して高速な演算を可能とすることができる。
【００５２】
埋込み次数を３の倍数次、すなわち３ｈ(ｈ：自然数)次として、曲線の式をｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)とした場合には、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1，ｖ∈Ｆqhが存在して、Ｅ'(Ｆqh)からＥ(Ｆq3h)への準同型写像(ｘ，ｙ)→(ｘｖ1/3、ｙｖ1/2)が存在する。ここで、新たなパラメータｖは、(ｑ3h−１)／ｒ乗のべき乗算の演算によって１となる平方剰余かつ３乗非剰余な元である。
【００５３】
したがって、Ｅ(Ｆq3h)[r]上の楕円加算を１／３の拡大次数のＥ'(Ｆqh)[r]上の楕円加算に置き換えて演算することが可能であり、演算負荷を低減して高速な演算を可能とすることができる。
【００５４】
特に、有理点Ｔ、Ｑ∈Ｅ(Ｆq3h)に対して、Ｔ＝(ｘT，ｙT)＝(ｘT'ｖ1/3、ｙT'ｖ1/2)、Ｑ＝(ｘQ，ｙQ)＝(ｘQ'ｖ1/3、ｙQ'ｖ1/2)の関係が成り立つ有理点Ｔ'、Ｑ'がＥ'(Ｆqh)に存在するので、まず、lT,T(ｘ，ｙ)の傾きλT,T、及びlT,Q(ｘ，ｙ)の傾きλT,Qを以下のように変形する。
【数３４】
【数３５】
【００５５】
［数３４］と［数３５］から、Ｔ＝Ｑ、Ｔ≠Ｑにかかわらず傾きλT,Qは、以下のようになる。
【数３６】
【００５６】
したがって、［数３６］の式から、［数２８］の式は以下のようになる。
【数３７】
この［数３７］の式の最後のｖ1/2の部分は、ペアリング演算における(ｑ3h−１)/r乗の最終べきの演算によって１となるので、ミラーのアルゴリズムにおけるlT,Q(ｘP，ｙP)を演算する際には、lT,Q(ｘP，ｙP)の演算を行うのではなく、lT',Q'(ｘPｖ-1/3，ｙPｖ-1/2)を真部分体上において演算すればよく、演算負荷を大きく低減することができる。
【００５７】
すなわち、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が３ｈ次(ｈ：自然数)で、Ｆq3hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q3h/(Ｆ*q3h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数３８】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算する場合に、fs,Q(Ｐ)の導出に必要となる有理関数lT,T(ｘP，ｙP)及びlT,Q(ｘP，ｙP)の演算を、このfs,Q(Ｐ)の(ｑ3h−１)／ｒ乗のべき乗算の演算によって１となる平方剰余かつ３乗非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1による真部分体上でlT',T'(ｘPｖ-1/3，ｙPｖ-1/2)及びlT',Q'(ｘPｖ-1/3，ｙPｖ-1/2)の演算として行うことによって、演算負荷を低減して高速な演算を可能とすることができる。
【００５８】
埋込み次数を４の倍数次、すなわち４ｈ(ｈ：自然数)次として、曲線の式をｙ2＝ｘ3＋ａｘ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で、４がｑh−１を割り切るとした場合には、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1ｘ，ｖ∈Ｆqhが存在して、Ｅ'(Ｆqh)からＥ(Ｆq4h)への準同型写像(ｘ，ｙ)→(ｘｖ1/2、ｙｖ3/4)が存在する。ここで、新たなパラメータｖは、(ｑ4h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余な元である。
【００５９】
したがって、Ｅ(Ｆq4h)[r]上の楕円加算を１／４の拡大次数のＥ'(Ｆqh)[r]上の楕円加算に置き換えて演算することが可能であり、演算負荷を低減して高速な演算を可能とすることができる。
【００６０】
特に、有理点Ｔ、Ｑ∈Ｅ(Ｆq4h)に対して、Ｔ＝(ｘT，ｙT)＝(ｘT'ｖ1/2、ｙT'ｖ3/4)、Ｑ＝(ｘQ，ｙQ)＝(ｘQ'ｖ1/2、ｙQ'ｖ3/4)の関係が成り立つ有理点Ｔ'、Ｑ'がＥ'(Ｆqh)に存在するので、まず、lT,T(ｘ，ｙ)の傾きλT,T、及びlT,Q(ｘ，ｙ)の傾きλT,Qを以下のように変形する。
【数３９】
【数４０】
【００６１】
［数３９］と［数４０］から、Ｔ＝Ｑ、Ｔ≠Ｑにかかわらず傾きλT,Qは、以下のようになる。
【数４１】
【００６２】
したがって、［数４１］の式から、［数２８］の式は以下のようになる。
【数４２】
【００６３】
この［数４２］の式の最後のｖ3/4の部分は、ペアリング演算における(ｑ4h−１)/r乗の最終べきの演算によって１となるので、ミラーのアルゴリズムにおけるlT,Q(ｘP，ｙP)を演算する際には、lT,Q(ｘP，ｙP)の演算を行うのではなく、lT',Q'(ｘPｖ-1/2，ｙPｖ-3/4)を真部分体上において演算すればよく、演算負荷を大きく低減することができる。
【００６４】
すなわち、曲線の式がｙ2＝ｘ3＋ａｘ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が４ｈ次(ｈ：自然数)で、４がｑh−１を割り切るものとし、Ｆq4hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q4h/(Ｆ*q4h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数４３】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算する場合に、fs,Q(Ｐ)の導出に必要となる有理関数lT,T(ｘP，ｙP)及びlT,Q(ｘP，ｙP)の演算を、このfs,Q(Ｐ)の(ｑ4h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1ｘによる真部分体上でlT',T'(ｘPｖ-1/2，ｙPｖ-3/4)及びlT',Q'(ｘPｖ-1/2，ｙPｖ-3/4)の演算として行うことによって、演算負荷を低減して高速な演算を可能とすることができる。
【００６５】
埋込み次数を６の倍数次、すなわち６ｈ(ｈ：自然数)次として、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)とした場合には、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1，ｖ∈Ｆqhが存在して、Ｅ'(Ｆqh)からＥ(Ｆq6h)への準同型写像(ｘ，ｙ)→(ｘｖ1/3、ｙｖ1/2)が存在する。ここで、新たなパラメータｖは、(ｑ6h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余かつ３乗非剰余な元である。
【００６６】
したがって、Ｅ(Ｆq6h)[r]上の楕円加算を１／６の拡大次数のＥ'(Ｆqh)[r]上の楕円加算に置き換えて演算することが可能であり、演算負荷を低減して高速な演算を可能とすることができる。
【００６７】
特に、有理点Ｔ、Ｑ∈Ｅ(Ｆq6h)に対して、Ｔ＝(ｘT，ｙT)＝(ｘT'ｖ1/3、ｙT'ｖ1/2)、Ｑ＝(ｘQ，ｙQ)＝(ｘQ'ｖ1/3、ｙQ'ｖ1/2)の関係が成り立つ有理点Ｔ'、Ｑ'がＥ'(Ｆph)に存在するので、まず、lT,T(ｘ，ｙ)の傾きλT,T、及びlT,Q(ｘ，ｙ)の傾きλT,Qを以下のように変形する。
【数４４】
【数４５】
【００６８】
［数４４］と［数４５］から、Ｔ＝Ｑ、Ｔ≠Ｑにかかわらず傾きλT,Qは、以下のようになる。
【数４６】
【００６９】
したがって、［数４６］の式から、［数２８］の式は以下のようになる。
【数４７】
【００７０】
この［数４７］の式の最後のｖ1/2の部分は、ペアリング演算における(ｑ6h−１)/r乗の最終べきの演算によって１となるので、ミラーのアルゴリズムにおけるlT,Q(ｘP，ｙP)を演算する際には、lT,Q(ｘP，ｙP)の演算を行うのではなく、lT',Q'(ｘPｖ-1/3，ｙPｖ-1/2)を真部分体上において演算すればよく、演算負荷を大きく低減することができる。
【００７１】
すなわち、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が６ｈ次(ｈ：自然数)で、Ｆq6hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q6h/(Ｆ*q6h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数４８】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算する場合に、fs,Q(Ｐ)の導出に必要となる有理関数lT,T(ｘP，ｙP)及びlT,Q(ｘP，ｙP)の演算を、このfs,Q(Ｐ)の(ｑ6h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余かつ３乗非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1による真部分体上でlT',T'(ｘPｖ-1/3，ｙPｖ-1/2)及びlT',Q'(ｘPｖ-1/3，ｙPｖ-1/2)の演算として行うことによって、演算負荷を低減して高速な演算を可能とすることができる。
【００７２】
以下において、埋込み次数が、偶数次、３の倍数次、４の倍数次、及び６の倍数次の最小公倍数である１２次の場合におけるペアリング演算のプログラムについて説明する。図２は、図１に対応させた埋込み次数が１２次の場合のミラーのアルゴリズムである。ここで、これまで３より大きい素数のべき乗としていたｑを、素数ｐとする。
【００７３】
認証サーバなどのように電子計算機で構成されるペアリング演算装置では、図３に示すフローチャートに基づくプログラムによりペアリング演算を行って、大規模なディジタルグループ署名を実現している。
【００７４】
ここで、ペアリング演算を行う電子計算機は、図２に示したミラーのアルゴリズムに基づくプログラムを内蔵したペアリング演算プログラムを実行可能とした電子計算機であって、図４に示すように、電子計算機10は、演算処理を実行するＣＰＵ11と、ペアリング演算プログラムなどの各種プログラム、及びペアリング演算プログラムで使用するデータなどを記憶したハードディスクなどの記憶装置12と、ペアリング演算プログラムを展開して実行可能とするとともに、ペアリング演算プログラムの実行にともなって生成されたデータを一時的に記憶するＲＡＭなどで構成されたメモリ装置13を備えている。図４中、14はバスである。
【００７５】
本発明のペアリング演算プログラムを利用するディジタルグループ署名技術においては、電子計算機10は、インターネットなどの電気通信回線20に接続して、この電気通信回線20に接続されたクライアント装置30から送信されたディジタルグループ署名の署名データを受信可能としている。図４中、15は電子計算機10の入出力制御部である。電子計算機10では、クライアント装置30から送信されたディジタルグループ署名の署名データはメモリ装置13に一次的に記憶している。
【００７６】
電子計算機10では、クライアント装置30からディジタルグループ署名の署名データが送信されると、送信された署名データをメモリ装置13に一旦記憶し、ペアリング演算プログラムを起動させる(ステップＳ１)。
【００７７】
起動したペアリング演算プログラムによって、電子計算機10は、入力手段として機能して、フロベニウス自己準同型写像φpのトレースｔに基づくｓ＝ｔ−１、Ｐ∈Ｅ(Ｆp)であるＰ、Ｑ'∈Ｅ'(Ｆp2)であるＱ'の入力を受け付ける(ステップＳ２)。メモリ装置13に一旦記憶した署名データはＰとＱ'のいずれか一方であり、一般的にはＰである。Ｑ’及びフロベニウス自己準同型写像φpのトレースｔまたはｓ＝ｔ−１は、記憶装置12またはメモリ装置13の所定アドレスに記憶しており、所定アドレスから読み出して入力している。
【００７８】
次いで、電子計算機10は、代入手段として機能して、有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行う(ステップＳ３)。ここで、ｖ-1/3の値、及びｖ-1/2の値は既知であって、記憶装置12またはメモリ装置13の所定アドレスに記憶しており、所定アドレスから読み出して入力してｘPｖ-1/3の演算、及びｙPｖ-1/2の演算を行っている。
【００７９】
なお、この代入演算は、埋込み次数が１２次で、６の倍数次となっているのでｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算であるが、埋込み次数が偶数次の場合にはｎ←ｘPｖ-1、ｍ←ｙPｖ-3/2の代入演算、埋込み次数が３の倍数次の場合にはｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算、埋込み次数が４の倍数次の場合にはｎ←ｘPｖ-1/2、ｍ←ｙPｖ-3/4の代入演算となる。
【００８０】
次いで、電子計算機10は、代入手段として機能して、ｆ←１、Ｔ'←Ｑ'の代入演算を行う(ステップＳ４)。これは、いわゆる初期値設定である。
【００８１】
次いで、電子計算機10は、２進数表示したｓのビット数をいの初期値として、以下の演算の繰り返しのたびにｉを１ずつ減算しながらｆの値を演算している(ステップＳ５)。ここで、上記したのと同様に、ｓ[i]は、２進数表示したｓの最小ビットから数えてｉ番目のビットの値を示すものとする。
【００８２】
ステップＳ５では、具体的には、電子計算機10は、第１演算手段として機能して、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行い、次いで、電子計算機10は、第２演算手段として機能して、Ｔ'←２Ｔ'の代入演算を行っている。
【００８３】
さらに、２進数表示したｓのｉ番目のビットの値ｓ[i]が１である場合には、電子計算機10は、第３演算手段として機能して、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行い、次いで、電子計算機10は、第４演算手段として機能して、Ｔ'←Ｔ'＋Ｑ'の代入演算を行っている。
【００８４】
ステップＳ５での演算後、電子計算機10は、演算結果のｆをメモリ装置13に一次的に記憶して、ミラー関数の演算を終了している(ステップＳ６)。
【００８５】
次いで、電子計算機10は、演算結果のｆの値を用いて(ｐ12−１)/r乗のべき乗算を行って、演算結果をペアリング演算の結果としてメモリ装置13に一次的に記憶している(ステップＳ７)。
【００８６】
電子計算機10では、上記のペアリング演算を失効者の数に応じた回数だけ繰り返し行って、ペアリング演算プログラムを終了している。
【００８７】
電子計算機10が認証サーバである場合には、その後、電子計算機10は、ペアリング演算の結果を用いて認証を行っている。
【００８８】
このように、ペアリング演算を行う電子計算機で構成されたペアリング演算装置では、埋込み次数が１２次の場合、Ｅ(Ｆp12)[r]上の楕円加算ではなく、Ｅ'(Ｆp2)[r]上の楕円加算として演算を行うことにより、ミラーのアルゴリズムに基づく演算に要する時間を３０％程度削減可能であり、より高速にペアリング演算を可能とすることができる。
【００８９】
したがって、より多くのメンバーを対象としたディジタルグループ署名に利用でき、ディジタルグループ署名をより広範囲で利用することができる。
【００９０】
本実施形態では、ディジタルグループ署名に用いるペアリング演算について説明したが、本発明に係るペアリング演算の装置、方法、プログラムは、ディジタルグループ署名に用いる場合に限定するものではなく、必要に応じて適宜のペアリング演算に適用することができる。
【図面の簡単な説明】
【００９１】
【図１】従来のミラーのアルゴリズムの説明図である。
【図２】本発明に係るミラーのアルゴリズムの説明図である。
【図３】本発明に係るペアリング演算プログラムのフローチャートである。
【図４】本発明の実施形態に係るペアリング演算装置の概略説明図である。
【符号の説明】
【００９２】
10 電子計算機
11 ＣＰＵ
12 記憶装置
13 メモリ装置
14 バス
15 入出力制御部
20 電気通信回線
30 クライアント装置
【技術分野】
【０００１】
本発明は、ペアリング演算を高速に実行可能としたペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラムに関する。
【背景技術】
【０００２】
昨今、高速な電気通信回線が低価格で利用可能となったことにより、インターネットなどのネットワーク上において、音楽や映像の配信、インターネットバンキング、行政機関への電子申請などのような各種のサービスが提供可能となっている。
【０００３】
また、企業による業務形態も変化しており、ノートパソコンや携帯電話などのいわゆるモバイル端末装置を用いて外出先などから会社のサーバ装置にアクセスして、各種の情報の入力あるいは取得が可能となっている。
【０００４】
特に、日本では、携帯電話をネットワークへの接続装置として利用するサービスが充実しており、いかなる所からでも所要のネットワークにアクセスして各種の情報を入手したり、サービスを利用したりすることができるいわゆるユビキタス社会の到来がいよいよ現実味を帯びてきた。
【０００５】
このように各種の情報を取得したり、サービスを利用したりするためにネットワークにアクセスする際には、所要の認証手段を備えた認証サーバによって認証処理が行われ、ネットワークにアクセスした利用者が、あらかじめ登録されている特定の利用者であることが認証されて、情報の取得あるいはサービスの利用が可能となっている。
【０００６】
特に、最近では、ディジタル署名技術を用いることにより、取り扱っている情報が第三者によって改ざんされていないこと、あるいは第三者に漏洩していないことを保証可能として、秘匿性の高い情報もネットワーク上で安全に取り扱い可能となっていることにより、さらに積極的にネットワークが利用されることとなっている。
【０００７】
ただし、このディジタル署名では、利用者個人が特定されるため、認証サーバにおける認証処理に基づいて認証サーバに利用者の履歴が情報として蓄積されることとなっており、この履歴情報は一種の個人情報であって、個人情報保護の問題があった。
【０００８】
そこで、ディジタル署名を拡張したディジタルグループ署名を用いることが提案されている。ディジタルグループ署名を用いた場合には、利用者は、認証サーバに対して匿名でグループに属していることのみを証明する署名データを送信し、認証サーバでは、受信した署名データから利用者を特定することなく利用者が所定のグループに属していることを認証している。したがって、認証サーバに各利用者の使用の履歴情報が蓄積されることを防止できる一方で、グループに属さない利用者による不正利用を阻止可能としている。
【０００９】
ここで、ディジタルグループ署名における匿名認証には、ペアリング演算が用いられている。ペアリング演算では、２入力１出力の関数を用いた演算を行っており、たとえば、Ｐを素体Ｆq上の有理点、Ｑをｋ次拡大体Ｆqk上の有理点として、ペアリングでＰとＱとを入力して拡大体Ｆ*qkの元ｚが出力されるとき、ａ倍のＰと、ｂ倍のＱを入力するとｚのab乗が算出されることを利用しているものであり、このような性質のことを双線形性と呼ぶ。なお、ここで、「ｋ」を埋込み次数と呼び、「Ｆ*qk」は、正しくは、以下の表示であるが、表示の制限上、「Ｆ*qk」と表示している。
【数１３】
【００１０】
一般的に、有理点Ｐ，Ｑはそれぞれ楕円曲線上の点が用いられ、このような楕円曲線のペアリングの演算は、ミラーのアルゴリズムを用いて演算するステップと、最終べきのべき乗演算を行うステップとで構成されている。
【００１１】
たとえば、10,000人のメンバーで構成されるグループのディジタルグループ署名であって、各メンバーのアクセス権の発行と失効とを柔軟に対応可能とするために、ディジタルグループ署名の検証時に失効者分のペアリング演算を行う方式が知られている。この場合、失効者が100人であれば100回のペアリング演算が必要であり、現時点での一般的な電子計算機による１回のペアリングの演算に約0.1秒を要していることから、100回のペアリング演算には10秒を要することとなって、大規模なディジタルグループ署名での利用は実用的とは言えなかった。
【００１２】
そこで、ペアリングの演算速度を向上させるために様々な開発が行われており、たとえば有限体上の楕円曲線上で定義されるＴａｔｅペアリング演算における高速化の技術が提案されている（例えば、特許文献１参照。）。
【特許文献１】特開２００５−３１６２６７号公報
【発明の開示】
【発明が解決しようとする課題】
【００１３】
しかしながら、現在提案されているペアリング演算の高速化技術では、未だに大規模なディジタルグループ署名での利用に適う速度とはなっておらず、ディジタルグループ署名のメンバー数を制限しなければならないという問題があった。
【００１４】
本発明者らは、このような現状に鑑み、ペアリング演算を高速化すべく研究開発を行って、本発明を成すに至ったものである。
【課題を解決するための手段】
【００１５】
本発明のペアリング演算装置では、曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ，ａ∈Ｆq，ｂ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が２ｈ次(ｈ：自然数)で、Ｆq2hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q2h/(Ｆ*q2h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数１４】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算装置において、fs,Q(Ｐ)の導出に必要となる有理関数の演算を、このfs,Q(Ｐ)の(ｑ2h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-2ｘ＋ｂｖ-3による真部分体上で行うこととした。
【００１６】
特に、
・ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付ける入力手段、
・有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1、ｍ←ｙPｖ-3/2の代入演算を行うとともに、ｆ←１、Ｔ'←Ｑ'の代入演算を行う代入手段、
・有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行う第１演算手段、
・Ｔ'←２Ｔ'の代入演算を行う第２演算手段、
・ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行う第３演算手段、
・ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行う第４演算手段、
・(ｑ2h−１)/r乗のべき乗算を演算する第５演算手段
を備えたことにも特徴を有するものである。
【００１７】
また、本発明のペアリング演算装置では、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が３ｈ次(ｈ：自然数)で、Ｆq3hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q3h/(Ｆ*q3h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数１５】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算装置において、
fs,Q(Ｐ)の導出に必要となる有理関数の演算を、このfs,Q(Ｐ)の(ｑ3h−１)／ｒ乗のべき乗算の演算によって１となる平方剰余かつ３乗非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1による真部分体上で行うこととした。
【００１８】
特に、
・ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付ける入力手段、
・有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行うとともに、ｆ←１、Ｔ'←Ｑ'の代入演算を行う代入手段、
・有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行う第１演算手段、
・Ｔ'←２Ｔ'の代入演算を行う第２演算手段、
・ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行う第３演算手段、
・ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行う第４演算手段、
・(ｑ3h−１)/r乗のべき乗算を演算する第５演算手段
を備えたことにも特徴を有するものである。
【００１９】
また、本発明のペアリング演算装置では、曲線の式がｙ2＝ｘ3＋ａｘ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が４ｈ次(ｈ：自然数)で、４がｑh−１を割り切るものとし、Ｆq4hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q4h/(Ｆ*q4h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数１６】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算装置において、fs,Q(Ｐ)の導出に必要となる有理関数の演算を、このfs,Q(Ｐ)の(ｑ4h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1ｘによる真部分体上で行うこととした。
【００２０】
特に、
・ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付ける入力手段、
・有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1/2、ｍ←ｙPｖ-3/4の代入演算を行うとともに、ｆ←１、Ｔ'←Ｑ'の代入演算を行う代入手段、
・有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/4をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行う第１演算手段、
・Ｔ'←２Ｔ'の代入演算を行う第２演算手段、
・ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/4をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行う第３演算手段、
・ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行う第４演算手段、
・(ｑ4h−１)/r乗のべき乗算を演算する第５演算手段と
を備えたことにも特徴を有するものである。
【００２１】
また、本発明のペアリング演算装置では、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が６ｈ次(ｈ：自然数)で、Ｆq6hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q6h/(Ｆ*q6h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数１７】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算装置において、fs,Q(Ｐ)の導出に必要となる有理関数の演算を、このfs,Q(Ｐ)の(ｑ6h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余かつ３乗非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1による真部分体上で行うこととした。
【００２２】
特に、
・ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付ける入力手段、
・有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行うとともに、ｆ←１、Ｔ'←Ｑ'の代入演算を行う代入手段、
・有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行う第１演算手段、
・Ｔ'←２Ｔ'の代入演算を行う第２演算手段、
・ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行う第３演算手段、
・ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行う第４演算手段、
・(ｑ6h−１)/r乗のべき乗算を演算する第５演算手段と
を備えたことにも特徴を有するものである。
【００２３】
また、本発明のペアリング演算方法では、曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ，ａ∈Ｆq，ｂ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が２ｈ次(ｈ：自然数)で、Ｆq2hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q2h/(Ｆ*q2h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数１８】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算方法において、fs,Q(Ｐ)の(ｑ2h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-2ｘ＋ｂｖ-3を用い、
・入力手段によって、ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆp)であるＰ、Ｑ'∈Ｅ'(Ｆp2)であるＱ'の入力を受け付けるステップ、
・代入手段によって、有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1、ｍ←ｙPｖ-3/2の代入演算を行うステップ、
・代入手段によって、ｆ←１、Ｔ'←Ｑ'の代入演算を行うステップ、
・第１演算手段によって、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行うステップ、
・第２演算手段によって、Ｔ'←２Ｔ'の代入演算を行うステップ、
・第３演算手段によって、ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行うステップ、
・第４演算手段によって、ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行うステップ
・第５演算手段によって、(ｑ2h−１)/r乗のべき乗算の演算を行うステップと
を有することとした。
【００２４】
また、本発明のペアリング演算方法では、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が３ｈ次(ｈ：自然数)で、Ｆq3hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q3h/(Ｆ*q3h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数１９】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算方法において、fs,Q(Ｐ)の(ｑ3h−１)／ｒ乗のべき乗算の演算によって１となる平方剰余かつ３乗非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1を用い、
・入力手段によって、ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けるステップ、
・代入手段によって、有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行うステップ、
・代入手段によって、ｆ←１、Ｔ'←Ｑ'の代入演算を行うステップ、
・第１演算手段によって、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行うステップ、
・第２演算手段によって、Ｔ'←２Ｔ'の代入演算を行うステップ、
・第３演算手段によって、ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行うステップ、
・第４演算手段によって、ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行うステップ、
・第５演算手段によって、(ｑ3h−１)/r乗のべき乗算の演算を行うステップと
を有することとした。
【００２５】
また、本発明のペアリング演算方法では、曲線の式がｙ2＝ｘ3＋ａｘ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が４ｈ次(ｈ：自然数)で、４がｑh−１を割り切るものとし、Ｆq4hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q4h/(Ｆ*q4h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数２０】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算方法において、fs,Q(Ｐ)の(ｑ4h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1ｘを用い、
・入力手段によって、ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けるステップ、
・代入手段によって、有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1/2、ｍ←ｙPｖ-3/4の代入演算を行うステップ、
・代入手段によって、ｆ←１、Ｔ'←Ｑ'の代入演算を行うステップ、
・第１演算手段によって、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/4をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行うステップ、
・第２演算手段によって、Ｔ'←２Ｔ'の代入演算を行うステップ、
・第３演算手段によって、ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/4をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行うステップ、
・第４演算手段によって、ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行うステップ、
・第５演算手段によって、(ｑ4h−１)/r乗のべき乗算の演算を行うステップと
を有することとした。
【００２６】
また、本発明のペアリング演算方法では、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が６ｈ次(ｈ：自然数)で、Ｆq6hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q6h/(Ｆ*q6h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数２１】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算方法において、fs,Q(Ｐ)の(ｑ6h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余かつ３乗非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1を用い、
・入力手段によって、ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けるステップ、
・代入手段によって、有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行うステップ、
・代入手段によって、ｆ←１、Ｔ'←Ｑ'の代入演算を行うステップ、
・第１演算手段によって、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行うステップ、
・第２演算手段によって、Ｔ'←２Ｔ'の代入演算を行うステップ、
・第３演算手段によって、ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行うステップ、
・第４演算手段によって、ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行うステップ、
・第５演算手段によって、(ｑ6h−１)/r乗のべき乗算の演算を行うステップと
を有することとした。
【００２７】
また、本発明のペアリング演算プログラムでは、曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ，ａ∈Ｆq，ｂ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が２ｈ次(ｈ：自然数)で、Ｆq2hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q2h/(Ｆ*q2h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数２２】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を電子計算機に演算させるペアリング演算プログラムにおいて、fs,Q(Ｐ)の(ｑ2h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-2ｘ＋ｂｖ-3を用い、
・電子計算機を入力手段として機能させて、ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けさせるステップ、
・電子計算機を代入手段として機能させて、有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1、ｍ←ｙPｖ-3/2の代入演算を行わせるステップ、
・電子計算機を代入手段として機能させて、ｆ←１、Ｔ'←Ｑ'の代入演算を行わせるステップ、
・電子計算機を第１演算手段として機能させて、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行わせるステップ、
・電子計算機を第２演算手段として機能させて、Ｔ'←２Ｔ'の代入演算を行わせるステップ、
・電子計算機を第３演算手段として機能させて、ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行わせるステップ、
・電子計算機を第４演算手段として機能させて、ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行わせるステップ、
・電子計算機を第５演算手段として機能させて、(ｑ2h−１)/r乗のべき乗算の演算を行わせるステップと
を有することとした。
【００２８】
また、本発明のペアリング演算プログラムでは、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が３ｈ次(ｈ：自然数)で、Ｆq3hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q3h/(Ｆ*q3h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数２３】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を電子計算機に演算させるペアリング演算プログラムにおいて、fs,Q(Ｐ)の(ｑ3h−１)／ｒ乗のべき乗算の演算によって１となる平方剰余かつ３乗非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1を用い、
・電子計算機を入力手段として機能させて、ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けさせるステップ、
・電子計算機を代入手段として機能させて、有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行わせるステップ、
・電子計算機を代入手段として機能させて、ｆ←１、Ｔ'←Ｑ'の代入演算を行わせるステップ、
・電子計算機を第１演算手段として機能させて、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行わせるステップ、
・電子計算機を第２演算手段として機能させて、Ｔ'←２Ｔ'の代入演算を行わせるステップ、
・電子計算機を第３演算手段として機能させて、ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行わせるステップ、
・電子計算機を第４演算手段として機能させて、ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行わせるステップ、
・電子計算機を第５演算手段として機能させて、(ｑ3h−１)/r乗のべき乗算の演算を行わせるステップと
を有することとした。
【００２９】
また、本発明のペアリング演算プログラムでは、曲線の式がｙ2＝ｘ3＋ａｘ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が４ｈ次(ｈ：自然数)で、４がｑh−１を割り切るものとし、Ｆq4hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q4h/(Ｆ*q4h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数２４】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を電子計算機に演算させるペアリング演算プログラムにおいて、fs,Q(Ｐ)の(ｑ4h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1ｘを用い、
・電子計算機を入力手段として機能させて、ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けさせるステップ、
・電子計算機を代入手段として機能させて、有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1/2、ｍ←ｙPｖ-3/4の代入演算を行わせるステップ、
・電子計算機を代入手段として機能させて、ｆ←１、Ｔ'←Ｑ'の代入演算を行わせるステップ、
・電子計算機を第１演算手段として機能させて、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/4をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行わせるステップ、
・電子計算機を第２演算手段として機能させて、Ｔ'←２Ｔ'の代入演算を行わせるステップ、
・電子計算機を第３演算手段として機能させて、ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/4をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行わせるステップ、
・電子計算機を第４演算手段として機能させて、ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行わせるステップ、
・電子計算機を第５演算手段として機能させて、(ｑ4h−１)/r乗のべき乗算の演算を行わせるステップと
を有することとした。
【００３０】
また、本発明のペアリング演算プログラムでは、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が６ｈ次(ｈ：自然数)で、Ｆq6hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q6h/(Ｆ*q6h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数２５】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を電子計算機に演算させるペアリング演算プログラムにおいて、fs,Q(Ｐ)の(ｑ6h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余かつ３乗非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1を用い、
・電子計算機を入力手段として機能させて、ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けさせるステップ、
・電子計算機を代入手段として機能させて、有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行わせるステップ、
・電子計算機を代入手段として機能させて、ｆ←１、Ｔ'←Ｑ'の代入演算を行わせるステップ、
・電子計算機を第１演算手段として機能させて、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行わせるステップ、
・電子計算機を第２演算手段として機能させて、Ｔ'←２Ｔ'の代入演算を行わせるステップ、
・電子計算機を第３演算手段として機能させて、ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行わせるステップ、
・電子計算機を第４演算手段として機能させて、ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行わせるステップ、
・電子計算機を第５演算手段として機能させて、(ｑ6h−１)/r乗のべき乗算の演算を行わせるステップと
を有することとした。
【発明の効果】
【００３１】
本発明では、ペアリング演算に際して、fs,Q(Ｐ)の導出に必要となる有理関数の演算を、ツイスト曲線を用いて低次の真部分体上で行うことにより演算負荷を低減して、ペアリング演算の高速化を図ることができる。
【発明を実施するための最良の形態】
【００３２】
本発明のペアリング演算装置、ペアリング演算方法、及びペアリング演算プログラムでは、ミラーのアルゴリズムを用いて演算するステップと、最終べきのべき乗演算を行うステップとで構成されるペアリング演算において、ミラーのアルゴリズムを用いた演算を高速化することにより、高速演算を可能としているものである。
【００３３】
ミラーのアルゴリズムは、図１に示すアルゴリズムとして知られているものである。曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ，ａ∈Ｆq，ｂ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が２ｈ次(ｈ：自然数)で、Ｆq2hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、ミラーのアルゴリズムでは、フロベニウス自己準同型写像φqのトレースｔを用いたｓ＝ｔ−１と、Ｐ∈Ｅ(Ｆq)であるＰと、Ｑ∈Ｅ(Ｆq2h)であるＱとが入力されることにより、fs,Q(Ｐ)を出力している。
【００３４】
なお、埋込み次数は偶数次に限定されるものではなく、埋込み次数を３の倍数次とする場合には、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が３ｈ次(ｈ：自然数)で、Ｆq3hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群を用いることが望ましい。
【００３５】
また、特に、埋込み次数が４の倍数次の場合には、曲線の式がｙ2＝ｘ3＋ａｘ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が４ｈ次(ｈ：自然数)で、４がｑh−１を割り切るものとし、Ｆq4hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群を用いることが望ましい。
【００３６】
さらに、特に、埋込み次数が６の倍数次の場合には、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が６ｈ次(ｈ：自然数)で、Ｆq6hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群を用いることが望ましい。
【００３７】
図１に示すミラーのアルゴリズムの第１ステップでは、ｆ←１、Ｔ←Ｑの代入演算を行い、第２ステップの繰り返し条件に基づいて以下の演算を繰り返し行っている。第２ステップでは、具体的には、２進数表示したｓによって得られるビット数をｉの初期値とし、演算の繰り返しのたびにｉを１ずつ減算しながら繰り返し回数を管理している。第５ステップのｓ[i]は、２進数表示したｓの最小ビットから数えてｉ番目のビットの値を示すものであって、ｓ[i]は「０」と「１」のいずれか一方である。
【００３８】
図１に示すミラーのアルゴリズムの第３ステップでは、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)の演算を行っており、第４ステップでは、Ｔ←２Ｔとして楕円二倍算を行っている。
【００３９】
図１に示すミラーのアルゴリズムの第５ステップでは、ｓを２進数表示とした場合の所定のビットの値ｓ[i]が１であるか否かを判定し、１である場合に、第６ステップで有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)の演算を行い、第７ステップで、Ｔ←Ｔ＋Ｑとして楕円加算を行っている。
【００４０】
そして、第２ステップの繰り返し条件に基づいて演算を繰り返し行って、図１に示すミラーのアルゴリズムの第１０ステップでは、演算結果を出力している。ペアリング演算では、最後に、ミラーのアルゴリズムによって演算されて出力された演算結果のfs,Q(Ｐ)に対して(ｑ2h−１)/r乗のべき乗算を行っている。
【００４１】
なお、埋込み次数が３の倍数次の場合には、最終べきのべき乗算は(ｑ3h−１)/r乗のべき乗算であり、埋込み次数が４の倍数次の場合には、最終べきのべき乗算は(ｑ4h−１)/r乗のべき乗算であり、埋込み次数が６の倍数次の場合には、最終べきのべき乗算は(ｑ6h−１)/r乗のべき乗算である。
【００４２】
以下において、第３ステップでのlT,T(ｘP，ｙP)の演算、及び第５ステップでのlT,Q(ｘP，ｙP)の演算方法を説明する。ここで、埋込み次数を偶数次、すなわち２ｈ(ｈ：自然数)次として、楕円曲線をｙ2＝ｘ3＋ａｘ＋ｂ，ａ∈Ｆq，ｂ∈Ｆq(ｑ：３より大きい素数のべき乗)とする。
【００４３】
Ｔ＝(ｘT，ｙT),Ｑ＝(ｘQ，ｙQ)とすると、lT,Q(ｘ，ｙ)の傾きλT,Qは次式で与えられる。
【数２６】
【数２７】
【００４４】
この傾きλT,Qを用いてlT,Q(ｘP，ｙP)の値を以下のように計算する。
【数２８】
【００４５】
通常では、この［数２６］及び［数２７］によってＥ(Ｆq2h)上で演算を行っているのであるが、埋込み次数を偶数次、すなわち２ｈ(ｈ：自然数)次として、楕円曲線をｙ2＝ｘ3＋ａｘ＋ｂ，ａ∈Ｆq，ｂ∈Ｆq(ｑ：３より大きい素数のべき乗)とした場合には、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-2ｘ＋ｂｖ-3，ｖ∈Ｆqhが存在して、Ｅ'(Ｆqh)からＥ(Ｆq2h)への準同型写像(ｘ，ｙ)→(ｘｖ、ｙｖ3/2)が存在する。ここで、新たなパラメータｖは、(ｑ2h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余な元である。
【００４６】
したがって、Ｅ(Ｆq2h)[r]上の楕円加算を１／２の拡大次数のＥ'(Ｆqh)[r]上の楕円加算に置き換えて演算することが可能であり、演算負荷を低減して高速な演算を可能とすることができる。
【００４７】
特に、有理点Ｔ、Ｑ∈Ｅ(Ｆq2h)に対して、Ｔ＝(ｘT，ｙT)＝(ｘT'ｖ、ｙT'ｖ3/2)、Ｑ＝(ｘQ，ｙQ)＝(ｘQ'ｖ、ｙQ'ｖ3/2)の関係が成り立つ有理点Ｔ'、Ｑ'がＥ'(Ｆqh)に存在するので、まず、lT,T(ｘ，ｙ)の傾きλT,T、及びlT,Q(ｘ，ｙ)の傾きλT,Qを以下のように変形する。
【数２９】
【数３０】
【００４８】
［数２９］と［数３０］から、Ｔ＝Ｑ、Ｔ≠Ｑにかかわらず傾きλT,Qは、以下のようになる。
【数３１】
【００４９】
したがって、［数３１］の式から、［数２８］の式は以下のようになる。
【数３２】
【００５０】
この［数３２］の式の最後のｖ3/2の部分は、ペアリング演算における(ｑ2h−１)/r乗の最終べきの演算によって１となるので、ミラーのアルゴリズムにおけるlT,Q(ｘP，ｙP)を演算する際には、lT,Q(ｘP，ｙP)の演算を行うのではなく、lT',Q'(ｘPｖ-1，ｙPｖ-3/2)を真部分体上において演算すればよく、演算負荷を大きく低減することができる。
【００５１】
すなわち、曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ，ａ∈Ｆq，ｂ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が２ｈ次(ｈ：自然数)で、Ｆq2hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q2h/(Ｆ*q2h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数３３】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算する場合に、fs,Q(Ｐ)の導出に必要となる有理関数lT,T(ｘP，ｙP)及びlT,Q(ｘP，ｙP)の演算を、このfs,Q(Ｐ)の(ｑ2h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-2ｘ＋ｂｖ-3による真部分体上でlT',T'(ｘPｖ-1，ｙPｖ-3/2)及びlT',Q'(ｘPｖ-1，ｙPｖ-3/2)の演算として行うことにより、演算負荷を低減して高速な演算を可能とすることができる。
【００５２】
埋込み次数を３の倍数次、すなわち３ｈ(ｈ：自然数)次として、曲線の式をｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)とした場合には、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1，ｖ∈Ｆqhが存在して、Ｅ'(Ｆqh)からＥ(Ｆq3h)への準同型写像(ｘ，ｙ)→(ｘｖ1/3、ｙｖ1/2)が存在する。ここで、新たなパラメータｖは、(ｑ3h−１)／ｒ乗のべき乗算の演算によって１となる平方剰余かつ３乗非剰余な元である。
【００５３】
したがって、Ｅ(Ｆq3h)[r]上の楕円加算を１／３の拡大次数のＥ'(Ｆqh)[r]上の楕円加算に置き換えて演算することが可能であり、演算負荷を低減して高速な演算を可能とすることができる。
【００５４】
特に、有理点Ｔ、Ｑ∈Ｅ(Ｆq3h)に対して、Ｔ＝(ｘT，ｙT)＝(ｘT'ｖ1/3、ｙT'ｖ1/2)、Ｑ＝(ｘQ，ｙQ)＝(ｘQ'ｖ1/3、ｙQ'ｖ1/2)の関係が成り立つ有理点Ｔ'、Ｑ'がＥ'(Ｆqh)に存在するので、まず、lT,T(ｘ，ｙ)の傾きλT,T、及びlT,Q(ｘ，ｙ)の傾きλT,Qを以下のように変形する。
【数３４】
【数３５】
【００５５】
［数３４］と［数３５］から、Ｔ＝Ｑ、Ｔ≠Ｑにかかわらず傾きλT,Qは、以下のようになる。
【数３６】
【００５６】
したがって、［数３６］の式から、［数２８］の式は以下のようになる。
【数３７】
この［数３７］の式の最後のｖ1/2の部分は、ペアリング演算における(ｑ3h−１)/r乗の最終べきの演算によって１となるので、ミラーのアルゴリズムにおけるlT,Q(ｘP，ｙP)を演算する際には、lT,Q(ｘP，ｙP)の演算を行うのではなく、lT',Q'(ｘPｖ-1/3，ｙPｖ-1/2)を真部分体上において演算すればよく、演算負荷を大きく低減することができる。
【００５７】
すなわち、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が３ｈ次(ｈ：自然数)で、Ｆq3hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q3h/(Ｆ*q3h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数３８】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算する場合に、fs,Q(Ｐ)の導出に必要となる有理関数lT,T(ｘP，ｙP)及びlT,Q(ｘP，ｙP)の演算を、このfs,Q(Ｐ)の(ｑ3h−１)／ｒ乗のべき乗算の演算によって１となる平方剰余かつ３乗非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1による真部分体上でlT',T'(ｘPｖ-1/3，ｙPｖ-1/2)及びlT',Q'(ｘPｖ-1/3，ｙPｖ-1/2)の演算として行うことによって、演算負荷を低減して高速な演算を可能とすることができる。
【００５８】
埋込み次数を４の倍数次、すなわち４ｈ(ｈ：自然数)次として、曲線の式をｙ2＝ｘ3＋ａｘ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で、４がｑh−１を割り切るとした場合には、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1ｘ，ｖ∈Ｆqhが存在して、Ｅ'(Ｆqh)からＥ(Ｆq4h)への準同型写像(ｘ，ｙ)→(ｘｖ1/2、ｙｖ3/4)が存在する。ここで、新たなパラメータｖは、(ｑ4h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余な元である。
【００５９】
したがって、Ｅ(Ｆq4h)[r]上の楕円加算を１／４の拡大次数のＥ'(Ｆqh)[r]上の楕円加算に置き換えて演算することが可能であり、演算負荷を低減して高速な演算を可能とすることができる。
【００６０】
特に、有理点Ｔ、Ｑ∈Ｅ(Ｆq4h)に対して、Ｔ＝(ｘT，ｙT)＝(ｘT'ｖ1/2、ｙT'ｖ3/4)、Ｑ＝(ｘQ，ｙQ)＝(ｘQ'ｖ1/2、ｙQ'ｖ3/4)の関係が成り立つ有理点Ｔ'、Ｑ'がＥ'(Ｆqh)に存在するので、まず、lT,T(ｘ，ｙ)の傾きλT,T、及びlT,Q(ｘ，ｙ)の傾きλT,Qを以下のように変形する。
【数３９】
【数４０】
【００６１】
［数３９］と［数４０］から、Ｔ＝Ｑ、Ｔ≠Ｑにかかわらず傾きλT,Qは、以下のようになる。
【数４１】
【００６２】
したがって、［数４１］の式から、［数２８］の式は以下のようになる。
【数４２】
【００６３】
この［数４２］の式の最後のｖ3/4の部分は、ペアリング演算における(ｑ4h−１)/r乗の最終べきの演算によって１となるので、ミラーのアルゴリズムにおけるlT,Q(ｘP，ｙP)を演算する際には、lT,Q(ｘP，ｙP)の演算を行うのではなく、lT',Q'(ｘPｖ-1/2，ｙPｖ-3/4)を真部分体上において演算すればよく、演算負荷を大きく低減することができる。
【００６４】
すなわち、曲線の式がｙ2＝ｘ3＋ａｘ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が４ｈ次(ｈ：自然数)で、４がｑh−１を割り切るものとし、Ｆq4hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q4h/(Ｆ*q4h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数４３】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算する場合に、fs,Q(Ｐ)の導出に必要となる有理関数lT,T(ｘP，ｙP)及びlT,Q(ｘP，ｙP)の演算を、このfs,Q(Ｐ)の(ｑ4h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1ｘによる真部分体上でlT',T'(ｘPｖ-1/2，ｙPｖ-3/4)及びlT',Q'(ｘPｖ-1/2，ｙPｖ-3/4)の演算として行うことによって、演算負荷を低減して高速な演算を可能とすることができる。
【００６５】
埋込み次数を６の倍数次、すなわち６ｈ(ｈ：自然数)次として、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)とした場合には、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1，ｖ∈Ｆqhが存在して、Ｅ'(Ｆqh)からＥ(Ｆq6h)への準同型写像(ｘ，ｙ)→(ｘｖ1/3、ｙｖ1/2)が存在する。ここで、新たなパラメータｖは、(ｑ6h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余かつ３乗非剰余な元である。
【００６６】
したがって、Ｅ(Ｆq6h)[r]上の楕円加算を１／６の拡大次数のＥ'(Ｆqh)[r]上の楕円加算に置き換えて演算することが可能であり、演算負荷を低減して高速な演算を可能とすることができる。
【００６７】
特に、有理点Ｔ、Ｑ∈Ｅ(Ｆq6h)に対して、Ｔ＝(ｘT，ｙT)＝(ｘT'ｖ1/3、ｙT'ｖ1/2)、Ｑ＝(ｘQ，ｙQ)＝(ｘQ'ｖ1/3、ｙQ'ｖ1/2)の関係が成り立つ有理点Ｔ'、Ｑ'がＥ'(Ｆph)に存在するので、まず、lT,T(ｘ，ｙ)の傾きλT,T、及びlT,Q(ｘ，ｙ)の傾きλT,Qを以下のように変形する。
【数４４】
【数４５】
【００６８】
［数４４］と［数４５］から、Ｔ＝Ｑ、Ｔ≠Ｑにかかわらず傾きλT,Qは、以下のようになる。
【数４６】
【００６９】
したがって、［数４６］の式から、［数２８］の式は以下のようになる。
【数４７】
【００７０】
この［数４７］の式の最後のｖ1/2の部分は、ペアリング演算における(ｑ6h−１)/r乗の最終べきの演算によって１となるので、ミラーのアルゴリズムにおけるlT,Q(ｘP，ｙP)を演算する際には、lT,Q(ｘP，ｙP)の演算を行うのではなく、lT',Q'(ｘPｖ-1/3，ｙPｖ-1/2)を真部分体上において演算すればよく、演算負荷を大きく低減することができる。
【００７１】
すなわち、曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq(ｑ：３より大きい素数のべき乗)で与えられ、埋込み次数が６ｈ次(ｈ：自然数)で、Ｆq6hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q6h/(Ｆ*q6h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数４８】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算する場合に、fs,Q(Ｐ)の導出に必要となる有理関数lT,T(ｘP，ｙP)及びlT,Q(ｘP，ｙP)の演算を、このfs,Q(Ｐ)の(ｑ6h−１)／ｒ乗のべき乗算の演算によって１となる平方非剰余かつ３乗非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1による真部分体上でlT',T'(ｘPｖ-1/3，ｙPｖ-1/2)及びlT',Q'(ｘPｖ-1/3，ｙPｖ-1/2)の演算として行うことによって、演算負荷を低減して高速な演算を可能とすることができる。
【００７２】
以下において、埋込み次数が、偶数次、３の倍数次、４の倍数次、及び６の倍数次の最小公倍数である１２次の場合におけるペアリング演算のプログラムについて説明する。図２は、図１に対応させた埋込み次数が１２次の場合のミラーのアルゴリズムである。ここで、これまで３より大きい素数のべき乗としていたｑを、素数ｐとする。
【００７３】
認証サーバなどのように電子計算機で構成されるペアリング演算装置では、図３に示すフローチャートに基づくプログラムによりペアリング演算を行って、大規模なディジタルグループ署名を実現している。
【００７４】
ここで、ペアリング演算を行う電子計算機は、図２に示したミラーのアルゴリズムに基づくプログラムを内蔵したペアリング演算プログラムを実行可能とした電子計算機であって、図４に示すように、電子計算機10は、演算処理を実行するＣＰＵ11と、ペアリング演算プログラムなどの各種プログラム、及びペアリング演算プログラムで使用するデータなどを記憶したハードディスクなどの記憶装置12と、ペアリング演算プログラムを展開して実行可能とするとともに、ペアリング演算プログラムの実行にともなって生成されたデータを一時的に記憶するＲＡＭなどで構成されたメモリ装置13を備えている。図４中、14はバスである。
【００７５】
本発明のペアリング演算プログラムを利用するディジタルグループ署名技術においては、電子計算機10は、インターネットなどの電気通信回線20に接続して、この電気通信回線20に接続されたクライアント装置30から送信されたディジタルグループ署名の署名データを受信可能としている。図４中、15は電子計算機10の入出力制御部である。電子計算機10では、クライアント装置30から送信されたディジタルグループ署名の署名データはメモリ装置13に一次的に記憶している。
【００７６】
電子計算機10では、クライアント装置30からディジタルグループ署名の署名データが送信されると、送信された署名データをメモリ装置13に一旦記憶し、ペアリング演算プログラムを起動させる(ステップＳ１)。
【００７７】
起動したペアリング演算プログラムによって、電子計算機10は、入力手段として機能して、フロベニウス自己準同型写像φpのトレースｔに基づくｓ＝ｔ−１、Ｐ∈Ｅ(Ｆp)であるＰ、Ｑ'∈Ｅ'(Ｆp2)であるＱ'の入力を受け付ける(ステップＳ２)。メモリ装置13に一旦記憶した署名データはＰとＱ'のいずれか一方であり、一般的にはＰである。Ｑ’及びフロベニウス自己準同型写像φpのトレースｔまたはｓ＝ｔ−１は、記憶装置12またはメモリ装置13の所定アドレスに記憶しており、所定アドレスから読み出して入力している。
【００７８】
次いで、電子計算機10は、代入手段として機能して、有理点Ｐの座標(ｘP，ｙP)に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行う(ステップＳ３)。ここで、ｖ-1/3の値、及びｖ-1/2の値は既知であって、記憶装置12またはメモリ装置13の所定アドレスに記憶しており、所定アドレスから読み出して入力してｘPｖ-1/3の演算、及びｙPｖ-1/2の演算を行っている。
【００７９】
なお、この代入演算は、埋込み次数が１２次で、６の倍数次となっているのでｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算であるが、埋込み次数が偶数次の場合にはｎ←ｘPｖ-1、ｍ←ｙPｖ-3/2の代入演算、埋込み次数が３の倍数次の場合にはｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算、埋込み次数が４の倍数次の場合にはｎ←ｘPｖ-1/2、ｍ←ｙPｖ-3/4の代入演算となる。
【００８０】
次いで、電子計算機10は、代入手段として機能して、ｆ←１、Ｔ'←Ｑ'の代入演算を行う(ステップＳ４)。これは、いわゆる初期値設定である。
【００８１】
次いで、電子計算機10は、２進数表示したｓのビット数をいの初期値として、以下の演算の繰り返しのたびにｉを１ずつ減算しながらｆの値を演算している(ステップＳ５)。ここで、上記したのと同様に、ｓ[i]は、２進数表示したｓの最小ビットから数えてｉ番目のビットの値を示すものとする。
【００８２】
ステップＳ５では、具体的には、電子計算機10は、第１演算手段として機能して、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行い、次いで、電子計算機10は、第２演算手段として機能して、Ｔ'←２Ｔ'の代入演算を行っている。
【００８３】
さらに、２進数表示したｓのｉ番目のビットの値ｓ[i]が１である場合には、電子計算機10は、第３演算手段として機能して、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP)を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行い、次いで、電子計算機10は、第４演算手段として機能して、Ｔ'←Ｔ'＋Ｑ'の代入演算を行っている。
【００８４】
ステップＳ５での演算後、電子計算機10は、演算結果のｆをメモリ装置13に一次的に記憶して、ミラー関数の演算を終了している(ステップＳ６)。
【００８５】
次いで、電子計算機10は、演算結果のｆの値を用いて(ｐ12−１)/r乗のべき乗算を行って、演算結果をペアリング演算の結果としてメモリ装置13に一次的に記憶している(ステップＳ７)。
【００８６】
電子計算機10では、上記のペアリング演算を失効者の数に応じた回数だけ繰り返し行って、ペアリング演算プログラムを終了している。
【００８７】
電子計算機10が認証サーバである場合には、その後、電子計算機10は、ペアリング演算の結果を用いて認証を行っている。
【００８８】
このように、ペアリング演算を行う電子計算機で構成されたペアリング演算装置では、埋込み次数が１２次の場合、Ｅ(Ｆp12)[r]上の楕円加算ではなく、Ｅ'(Ｆp2)[r]上の楕円加算として演算を行うことにより、ミラーのアルゴリズムに基づく演算に要する時間を３０％程度削減可能であり、より高速にペアリング演算を可能とすることができる。
【００８９】
したがって、より多くのメンバーを対象としたディジタルグループ署名に利用でき、ディジタルグループ署名をより広範囲で利用することができる。
【００９０】
本実施形態では、ディジタルグループ署名に用いるペアリング演算について説明したが、本発明に係るペアリング演算の装置、方法、プログラムは、ディジタルグループ署名に用いる場合に限定するものではなく、必要に応じて適宜のペアリング演算に適用することができる。
【図面の簡単な説明】
【００９１】
【図１】従来のミラーのアルゴリズムの説明図である。
【図２】本発明に係るミラーのアルゴリズムの説明図である。
【図３】本発明に係るペアリング演算プログラムのフローチャートである。
【図４】本発明の実施形態に係るペアリング演算装置の概略説明図である。
【符号の説明】
【００９２】
10 電子計算機
11 ＣＰＵ
12 記憶装置
13 メモリ装置
14 バス
15 入出力制御部
20 電気通信回線
30 クライアント装置
【特許請求の範囲】
【請求項１】
曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ，ａ∈Ｆq，ｂ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が２ｈ次（ｈ：自然数）で、Ｆq2hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q2h/(Ｆ*q2h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数１】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算装置において、
fs,Q(Ｐ)の導出に必要となる有理関数の演算を、このfs,Q(Ｐ)の（ｑ2h−１）／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-2ｘ＋ｂｖ-3による真部分体上で行うことを特徴とするペアリング演算装置。
【請求項２】
請求項１に記載のペアリング演算装置において、
前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付ける入力手段と、
有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1、ｍ←ｙPｖ-3/2の代入演算を行うとともに、ｆ←１、Ｔ'←Ｑ'の代入演算を行う代入手段と、
有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行う第１演算手段と、
Ｔ'←２Ｔ'の代入演算を行う第２演算手段と、
前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行う第３演算手段と、
前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行う第４演算手段と、
(ｑ2h−１)/r乗のべき乗算を演算する第５演算手段と
を備えたことを特徴とするペアリング演算装置。
【請求項３】
曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が３ｈ次（ｈ：自然数）で、Ｆq3hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q3h/(Ｆ*q3h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数２】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算装置において、
fs,Q(Ｐ)の導出に必要となる有理関数の演算を、このfs,Q(Ｐ)の（ｑ3h−１）／ｒ乗のべき乗算の演算によって１となる平方剰余かつ３乗非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1による真部分体上で行うことを特徴とするペアリング演算装置。
【請求項４】
請求項３に記載のペアリング演算装置において、
前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付ける入力手段と、
有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行うとともに、ｆ←１、Ｔ'←Ｑ'の代入演算を行う代入手段と、
有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行う第１演算手段と、
Ｔ'←２Ｔ'の代入演算を行う第２演算手段と、
前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行う第３演算手段と、
前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行う第４演算手段と、
(ｑ3h−１)/r乗のべき乗算を演算する第５演算手段と
を備えたことを特徴とするペアリング演算装置。
【請求項５】
曲線の式がｙ2＝ｘ3＋ａｘ，ａ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が４ｈ次（ｈ：自然数）で、４がｑh−１を割り切るものとし、Ｆq4hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q4h/(Ｆ*q4h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数３】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算装置において、
fs,Q(Ｐ)の導出に必要となる有理関数の演算を、このfs,Q(Ｐ)の（ｑ4h−１）／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1ｘによる真部分体上で行うことを特徴とするペアリング演算装置。
【請求項６】
請求項５に記載のペアリング演算装置において、
前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付ける入力手段と、
有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1/2、ｍ←ｙPｖ-3/4の代入演算を行うとともに、ｆ←１、Ｔ'←Ｑ'の代入演算を行う代入手段と、
有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/4をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行う第１演算手段と、
Ｔ'←２Ｔ'の代入演算を行う第２演算手段と、
前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/4をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行う第３演算手段と、
前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行う第４演算手段と、
(ｑ4h−１)/r乗のべき乗算を演算する第５演算手段と
を備えたことを特徴とするペアリング演算装置。
【請求項７】
曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が６ｈ次（ｈ：自然数）で、Ｆq6hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q6h/(Ｆ*q6h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数４】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算装置において、
fs,Q(Ｐ)の導出に必要となる有理関数の演算を、このfs,Q(Ｐ)の（ｑ6h−１）／ｒ乗のべき乗算の演算によって１となる平方非剰余かつ３乗非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1による真部分体上で行うことを特徴とするペアリング演算装置。
【請求項８】
請求項７に記載のペアリング演算装置において、
前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付ける入力手段と、
有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行うとともに、ｆ←１、Ｔ'←Ｑ'の代入演算を行う代入手段と、
有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行う第１演算手段と、
Ｔ'←２Ｔ'の代入演算を行う第２演算手段と、
前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行う第３演算手段と、
前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行う第４演算手段と、
(ｑ6h−１)/r乗のべき乗算を演算する第５演算手段と
を備えたことを特徴とするペアリング演算装置。
【請求項９】
曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ，ａ∈Ｆq，ｂ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が２ｈ次（ｈ：自然数）で、Ｆq2hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q2h/(Ｆ*q2h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数５】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算方法において、
fs,Q(Ｐ)の（ｑ2h−１）／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-2ｘ＋ｂｖ-3を用いて、
入力手段によって、前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けるステップと、
代入手段によって、有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1、ｍ←ｙPｖ-3/2の代入演算を行うステップと、
代入手段によって、ｆ←１、Ｔ'←Ｑ'の代入演算を行うステップと、
第１演算手段によって、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行うステップと、
第２演算手段によって、Ｔ'←２Ｔ'の代入演算を行うステップと、
第３演算手段によって、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行うステップと、
第４演算手段によって、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行うステップと、
第５演算手段によって、(ｑ2h−１)/r乗のべき乗算の演算を行うステップと
を有することを特徴とするペアリング演算方法。
【請求項１０】
曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が３ｈ次（ｈ：自然数）で、Ｆq3hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q3h/(Ｆ*q3h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数６】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算方法において、
fs,Q(Ｐ)の（ｑ3h−１）／ｒ乗のべき乗算の演算によって１となる平方剰余かつ３乗非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1を用いて、
入力手段によって、前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けるステップと、
代入手段によって、有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行うステップと、
代入手段によって、ｆ←１、Ｔ'←Ｑ'の代入演算を行うステップと、
第１演算手段によって、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行うステップと、
第２演算手段によって、Ｔ'←２Ｔ'の代入演算を行うステップと、
第３演算手段によって、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行うステップと、
第４演算手段によって、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行うステップと、
第５演算手段によって、(ｑ3h−１)/r乗のべき乗算の演算を行うステップと
を有することを特徴とするペアリング演算方法。
【請求項１１】
曲線の式がｙ2＝ｘ3＋ａｘ，ａ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が４ｈ次（ｈ：自然数）で、４がｑh−１を割り切るものとし、Ｆq4hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q4h/(Ｆ*q4h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数７】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算方法において、
fs,Q(Ｐ)の(ｑ4h−１）／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1ｘを用いて、
入力手段によって、前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けるステップと、
代入手段によって、有理点Ｐの座標(ｘP，ｙP）に対して、ｎ←ｘPｖ-1/2、ｍ←ｙPｖ-3/4の代入演算を行うステップと、
代入手段によって、ｆ←１、Ｔ'←Ｑ'の代入演算を行うステップと、
第１演算手段によって、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/4をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行うステップと、
第２演算手段によって、Ｔ'←２Ｔ'の代入演算を行うステップと、
第３演算手段によって、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/4をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行うステップと、
第４演算手段によって、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行うステップと、
第５演算手段によって、(ｑ4h−１)/r乗のべき乗算の演算を行うステップと
を有することを特徴とするペアリング演算方法。
【請求項１２】
曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が６ｈ次（ｈ：自然数）で、Ｆq6hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q6h/(Ｆ*q6h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数８】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算方法において、
fs,Q(Ｐ)の（ｑ6h−１）／ｒ乗のべき乗算の演算によって１となる平方非剰余かつ３乗非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1を用いて、
入力手段によって、前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けるステップと、
代入手段によって、有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行うステップと、
代入手段によって、ｆ←１、Ｔ'←Ｑ'の代入演算を行うステップと、
第１演算手段によって、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行うステップと、
第２演算手段によって、Ｔ'←２Ｔ'の代入演算を行うステップと、
第３演算手段によって、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行うステップと、
第４演算手段によって、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行うステップと、
第５演算手段によって、(ｑ6h−１)/r乗のべき乗算の演算を行うステップと
を有することを特徴とするペアリング演算方法。
【請求項１３】
曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ，ａ∈Ｆq，ｂ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が２ｈ次（ｈ：自然数）で、Ｆq2hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q2h/(Ｆ*q2h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数９】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を電子計算機に演算させるペアリング演算プログラムにおいて、
fs,Q(Ｐ)の（ｑ2h−１）／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-2ｘ＋ｂｖ-3を用いて、
前記電子計算機を入力手段として機能させて、前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けさせるステップと、
前記電子計算機を代入手段として機能させて、有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1、ｍ←ｙPｖ-3/2の代入演算を行わせるステップと、
前記電子計算機を代入手段として機能させて、ｆ←１、Ｔ'←Ｑ'の代入演算を行わせるステップと、
前記電子計算機を第１演算手段として機能させて、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行わせるステップと、
前記電子計算機を第２演算手段として機能させて、Ｔ'←２Ｔ'の代入演算を行わせるステップと、
前記電子計算機を第３演算手段として機能させて、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行わせるステップと、
前記電子計算機を第４演算手段として機能させて、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行わせるステップと、
前記電子計算機を第５演算手段として機能させて、(ｑ2h−１)/r乗のべき乗算の演算を行わせるステップと
を有することを特徴とするペアリング演算プログラム。
【請求項１４】
曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が３ｈ次（ｈ：自然数）で、Ｆq3hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q3h/(Ｆ*q3h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数１０】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を電子計算機に演算させるペアリング演算プログラムにおいて、
fs,Q(Ｐ)の（ｑ3h−１）／ｒ乗のべき乗算の演算によって１となる平方剰余かつ３乗非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1を用いて、
前記電子計算機を入力手段として機能させて、前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けさせるステップと、
前記電子計算機を代入手段として機能させて、有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行わせるステップと、
前記電子計算機を代入手段として機能させて、ｆ←１、Ｔ'←Ｑ'の代入演算を行わせるステップと、
前記電子計算機を第１演算手段として機能させて、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行わせるステップと、
前記電子計算機を第２演算手段として機能させて、Ｔ'←２Ｔ'の代入演算を行わせるステップと、
前記電子計算機を第３演算手段として機能させて、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行わせるステップと、
前記電子計算機を第４演算手段として機能させて、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行わせるステップと、
前記電子計算機を第５演算手段として機能させて、(ｑ3h−１)/r乗のべき乗算の演算を行わせるステップと
を有することを特徴とするペアリング演算プログラム。
【請求項１５】
曲線の式がｙ2＝ｘ3＋ａｘ，ａ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が４ｈ次（ｈ：自然数）で、４がｑh−１を割り切るものとし、Ｆq4hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q4h/(Ｆ*q4h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数１１】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を電子計算機に演算させるペアリング演算プログラムにおいて、
fs,Q(Ｐ)の（ｑ4h−１）／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1ｘを用いて、
前記電子計算機を入力手段として機能させて、前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けさせるステップと、
前記電子計算機を代入手段として機能させて、有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1/2、ｍ←ｙPｖ-3/4の代入演算を行わせるステップと、
前記電子計算機を代入手段として機能させて、ｆ←１、Ｔ'←Ｑ'の代入演算を行わせるステップと、
前記電子計算機を第１演算手段として機能させて、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/4をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行わせるステップと、
前記電子計算機を第２演算手段として機能させて、Ｔ'←２Ｔ'の代入演算を行わせるステップと、
前記電子計算機を第３演算手段として機能させて、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/4をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行わせるステップと、
前記電子計算機を第４演算手段として機能させて、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行わせるステップと、
前記電子計算機を第５演算手段として機能させて、(ｑ4h−１)/r乗のべき乗算の演算を行わせるステップと
を有することを特徴とするペアリング演算プログラム。
【請求項１６】
曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が６ｈ次（ｈ：自然数）で、Ｆq6hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q6h/(Ｆ*q6h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数１２】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を電子計算機に演算させるペアリング演算プログラムにおいて、
fs,Q(Ｐ)の（ｑ6h−１）／ｒ乗のべき乗算の演算によって１となる平方非剰余かつ３乗非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1を用いて、
前記電子計算機を入力手段として機能させて、前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けさせるステップと、
前記電子計算機を代入手段として機能させて、有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行わせるステップと、
前記電子計算機を代入手段として機能させて、ｆ←１、Ｔ'←Ｑ'の代入演算を行わせるステップと、
前記電子計算機を第１演算手段として機能させて、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行わせるステップと、
前記電子計算機を第２演算手段として機能させて、Ｔ'←２Ｔ'の代入演算を行わせるステップと、
前記電子計算機を第３演算手段として機能させて、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行わせるステップと、
前記電子計算機を第４演算手段として機能させて、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行わせるステップと、
前記電子計算機を第５演算手段として機能させて、(ｑ6h−１)/r乗のべき乗算の演算を行わせるステップと
を有することを特徴とするペアリング演算方法。
【請求項１】
曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ，ａ∈Ｆq，ｂ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が２ｈ次（ｈ：自然数）で、Ｆq2hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q2h/(Ｆ*q2h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数１】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算装置において、
fs,Q(Ｐ)の導出に必要となる有理関数の演算を、このfs,Q(Ｐ)の（ｑ2h−１）／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-2ｘ＋ｂｖ-3による真部分体上で行うことを特徴とするペアリング演算装置。
【請求項２】
請求項１に記載のペアリング演算装置において、
前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付ける入力手段と、
有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1、ｍ←ｙPｖ-3/2の代入演算を行うとともに、ｆ←１、Ｔ'←Ｑ'の代入演算を行う代入手段と、
有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行う第１演算手段と、
Ｔ'←２Ｔ'の代入演算を行う第２演算手段と、
前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行う第３演算手段と、
前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行う第４演算手段と、
(ｑ2h−１)/r乗のべき乗算を演算する第５演算手段と
を備えたことを特徴とするペアリング演算装置。
【請求項３】
曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が３ｈ次（ｈ：自然数）で、Ｆq3hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q3h/(Ｆ*q3h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数２】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算装置において、
fs,Q(Ｐ)の導出に必要となる有理関数の演算を、このfs,Q(Ｐ)の（ｑ3h−１）／ｒ乗のべき乗算の演算によって１となる平方剰余かつ３乗非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1による真部分体上で行うことを特徴とするペアリング演算装置。
【請求項４】
請求項３に記載のペアリング演算装置において、
前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付ける入力手段と、
有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行うとともに、ｆ←１、Ｔ'←Ｑ'の代入演算を行う代入手段と、
有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行う第１演算手段と、
Ｔ'←２Ｔ'の代入演算を行う第２演算手段と、
前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行う第３演算手段と、
前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行う第４演算手段と、
(ｑ3h−１)/r乗のべき乗算を演算する第５演算手段と
を備えたことを特徴とするペアリング演算装置。
【請求項５】
曲線の式がｙ2＝ｘ3＋ａｘ，ａ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が４ｈ次（ｈ：自然数）で、４がｑh−１を割り切るものとし、Ｆq4hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q4h/(Ｆ*q4h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数３】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算装置において、
fs,Q(Ｐ)の導出に必要となる有理関数の演算を、このfs,Q(Ｐ)の（ｑ4h−１）／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1ｘによる真部分体上で行うことを特徴とするペアリング演算装置。
【請求項６】
請求項５に記載のペアリング演算装置において、
前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付ける入力手段と、
有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1/2、ｍ←ｙPｖ-3/4の代入演算を行うとともに、ｆ←１、Ｔ'←Ｑ'の代入演算を行う代入手段と、
有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/4をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行う第１演算手段と、
Ｔ'←２Ｔ'の代入演算を行う第２演算手段と、
前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/4をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行う第３演算手段と、
前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行う第４演算手段と、
(ｑ4h−１)/r乗のべき乗算を演算する第５演算手段と
を備えたことを特徴とするペアリング演算装置。
【請求項７】
曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が６ｈ次（ｈ：自然数）で、Ｆq6hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q6h/(Ｆ*q6h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数４】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算装置において、
fs,Q(Ｐ)の導出に必要となる有理関数の演算を、このfs,Q(Ｐ)の（ｑ6h−１）／ｒ乗のべき乗算の演算によって１となる平方非剰余かつ３乗非剰余なｖ∈Ｆqhを用いて、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1による真部分体上で行うことを特徴とするペアリング演算装置。
【請求項８】
請求項７に記載のペアリング演算装置において、
前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付ける入力手段と、
有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行うとともに、ｆ←１、Ｔ'←Ｑ'の代入演算を行う代入手段と、
有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行う第１演算手段と、
Ｔ'←２Ｔ'の代入演算を行う第２演算手段と、
前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行う第３演算手段と、
前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行う第４演算手段と、
(ｑ6h−１)/r乗のべき乗算を演算する第５演算手段と
を備えたことを特徴とするペアリング演算装置。
【請求項９】
曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ，ａ∈Ｆq，ｂ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が２ｈ次（ｈ：自然数）で、Ｆq2hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q2h/(Ｆ*q2h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数５】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算方法において、
fs,Q(Ｐ)の（ｑ2h−１）／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-2ｘ＋ｂｖ-3を用いて、
入力手段によって、前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けるステップと、
代入手段によって、有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1、ｍ←ｙPｖ-3/2の代入演算を行うステップと、
代入手段によって、ｆ←１、Ｔ'←Ｑ'の代入演算を行うステップと、
第１演算手段によって、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行うステップと、
第２演算手段によって、Ｔ'←２Ｔ'の代入演算を行うステップと、
第３演算手段によって、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行うステップと、
第４演算手段によって、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行うステップと、
第５演算手段によって、(ｑ2h−１)/r乗のべき乗算の演算を行うステップと
を有することを特徴とするペアリング演算方法。
【請求項１０】
曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が３ｈ次（ｈ：自然数）で、Ｆq3hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q3h/(Ｆ*q3h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数６】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算方法において、
fs,Q(Ｐ)の（ｑ3h−１）／ｒ乗のべき乗算の演算によって１となる平方剰余かつ３乗非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1を用いて、
入力手段によって、前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けるステップと、
代入手段によって、有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行うステップと、
代入手段によって、ｆ←１、Ｔ'←Ｑ'の代入演算を行うステップと、
第１演算手段によって、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行うステップと、
第２演算手段によって、Ｔ'←２Ｔ'の代入演算を行うステップと、
第３演算手段によって、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行うステップと、
第４演算手段によって、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行うステップと、
第５演算手段によって、(ｑ3h−１)/r乗のべき乗算の演算を行うステップと
を有することを特徴とするペアリング演算方法。
【請求項１１】
曲線の式がｙ2＝ｘ3＋ａｘ，ａ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が４ｈ次（ｈ：自然数）で、４がｑh−１を割り切るものとし、Ｆq4hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q4h/(Ｆ*q4h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数７】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算方法において、
fs,Q(Ｐ)の(ｑ4h−１）／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1ｘを用いて、
入力手段によって、前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けるステップと、
代入手段によって、有理点Ｐの座標(ｘP，ｙP）に対して、ｎ←ｘPｖ-1/2、ｍ←ｙPｖ-3/4の代入演算を行うステップと、
代入手段によって、ｆ←１、Ｔ'←Ｑ'の代入演算を行うステップと、
第１演算手段によって、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標(ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/4をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行うステップと、
第２演算手段によって、Ｔ'←２Ｔ'の代入演算を行うステップと、
第３演算手段によって、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/4をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行うステップと、
第４演算手段によって、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行うステップと、
第５演算手段によって、(ｑ4h−１)/r乗のべき乗算の演算を行うステップと
を有することを特徴とするペアリング演算方法。
【請求項１２】
曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が６ｈ次（ｈ：自然数）で、Ｆq6hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q6h/(Ｆ*q6h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数８】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を演算するペアリング演算方法において、
fs,Q(Ｐ)の（ｑ6h−１）／ｒ乗のべき乗算の演算によって１となる平方非剰余かつ３乗非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1を用いて、
入力手段によって、前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けるステップと、
代入手段によって、有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行うステップと、
代入手段によって、ｆ←１、Ｔ'←Ｑ'の代入演算を行うステップと、
第１演算手段によって、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行うステップと、
第２演算手段によって、Ｔ'←２Ｔ'の代入演算を行うステップと、
第３演算手段によって、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行うステップと、
第４演算手段によって、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行うステップと、
第５演算手段によって、(ｑ6h−１)/r乗のべき乗算の演算を行うステップと
を有することを特徴とするペアリング演算方法。
【請求項１３】
曲線の式がｙ2＝ｘ3＋ａｘ＋ｂ，ａ∈Ｆq，ｂ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が２ｈ次（ｈ：自然数）で、Ｆq2hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q2h/(Ｆ*q2h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数９】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を電子計算機に演算させるペアリング演算プログラムにおいて、
fs,Q(Ｐ)の（ｑ2h−１）／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-2ｘ＋ｂｖ-3を用いて、
前記電子計算機を入力手段として機能させて、前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けさせるステップと、
前記電子計算機を代入手段として機能させて、有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1、ｍ←ｙPｖ-3/2の代入演算を行わせるステップと、
前記電子計算機を代入手段として機能させて、ｆ←１、Ｔ'←Ｑ'の代入演算を行わせるステップと、
前記電子計算機を第１演算手段として機能させて、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行わせるステップと、
前記電子計算機を第２演算手段として機能させて、Ｔ'←２Ｔ'の代入演算を行わせるステップと、
前記電子計算機を第３演算手段として機能させて、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行わせるステップと、
前記電子計算機を第４演算手段として機能させて、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行わせるステップと、
前記電子計算機を第５演算手段として機能させて、(ｑ2h−１)/r乗のべき乗算の演算を行わせるステップと
を有することを特徴とするペアリング演算プログラム。
【請求項１４】
曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が３ｈ次（ｈ：自然数）で、Ｆq3hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q3h/(Ｆ*q3h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数１０】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を電子計算機に演算させるペアリング演算プログラムにおいて、
fs,Q(Ｐ)の（ｑ3h−１）／ｒ乗のべき乗算の演算によって１となる平方剰余かつ３乗非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1を用いて、
前記電子計算機を入力手段として機能させて、前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けさせるステップと、
前記電子計算機を代入手段として機能させて、有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行わせるステップと、
前記電子計算機を代入手段として機能させて、ｆ←１、Ｔ'←Ｑ'の代入演算を行わせるステップと、
前記電子計算機を第１演算手段として機能させて、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行わせるステップと、
前記電子計算機を第２演算手段として機能させて、Ｔ'←２Ｔ'の代入演算を行わせるステップと、
前記電子計算機を第３演算手段として機能させて、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行わせるステップと、
前記電子計算機を第４演算手段として機能させて、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行わせるステップと、
前記電子計算機を第５演算手段として機能させて、(ｑ3h−１)/r乗のべき乗算の演算を行わせるステップと
を有することを特徴とするペアリング演算プログラム。
【請求項１５】
曲線の式がｙ2＝ｘ3＋ａｘ，ａ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が４ｈ次（ｈ：自然数）で、４がｑh−１を割り切るものとし、Ｆq4hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q4h/(Ｆ*q4h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数１１】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を電子計算機に演算させるペアリング演算プログラムにおいて、
fs,Q(Ｐ)の（ｑ4h−１）／ｒ乗のべき乗算の演算によって１となる平方非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1ｘを用いて、
前記電子計算機を入力手段として機能させて、前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けさせるステップと、
前記電子計算機を代入手段として機能させて、有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1/2、ｍ←ｙPｖ-3/4の代入演算を行わせるステップと、
前記電子計算機を代入手段として機能させて、ｆ←１、Ｔ'←Ｑ'の代入演算を行わせるステップと、
前記電子計算機を第１演算手段として機能させて、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-3/4をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行わせるステップと、
前記電子計算機を第２演算手段として機能させて、Ｔ'←２Ｔ'の代入演算を行わせるステップと、
前記電子計算機を第３演算手段として機能させて、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-3/4をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行わせるステップと、
前記電子計算機を第４演算手段として機能させて、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行わせるステップと、
前記電子計算機を第５演算手段として機能させて、(ｑ4h−１)/r乗のべき乗算の演算を行わせるステップと
を有することを特徴とするペアリング演算プログラム。
【請求項１６】
曲線の式がｙ2＝ｘ3＋ａ，ａ∈Ｆq（ｑ：３より大きい素数のべき乗）で与えられ、埋込み次数が６ｈ次（ｈ：自然数）で、Ｆq6hを定義体とするペアリング可能な楕円曲線上の有理点のなす加法群をＥ、素数位数ｒの有理点の集合をＥ[r]とし、φqをフロベニウス自己準同型写像として、
Ｇ1＝Ｅ[r]∩Ker(φq−[1])
Ｇ2＝Ｅ[r]∩Ker(φq−[ｑ])
により、
ｅ：Ｇ2×Ｇ1→Ｆ*q6h/(Ｆ*q6h)r
である非退化な双線形写像として定義されるＡｔｅペアリングｅによって、Ｐ∈Ｇ1、Ｑ∈Ｇ2とし、フロベニウス自己準同型写像φqのトレースｔを用いてｓ＝ｔ−１とし、ミラー関数fs,Q(・)を用いて、
【数１２】
としてＡｔｅペアリングｅ(Ｑ,Ｐ)を電子計算機に演算させるペアリング演算プログラムにおいて、
fs,Q(Ｐ)の（ｑ6h−１）／ｒ乗のべき乗算の演算によって１となる平方非剰余かつ３乗非剰余なｖ∈Ｆqh、Ｅ(Ｆqh)のツイスト曲線Ｅ'(Ｆqh)：ｙ2＝ｘ3＋aｖ-1を用いて、
前記電子計算機を入力手段として機能させて、前記ｓ＝ｔ−１、Ｐ∈Ｅ(Ｆq)であるＰ、Ｑ'∈Ｅ'(Ｆqh)であるＱ'の入力を受け付けさせるステップと、
前記電子計算機を代入手段として機能させて、有理点Ｐの座標（ｘP，ｙP）に対して、ｎ←ｘPｖ-1/3、ｍ←ｙPｖ-1/2の代入演算を行わせるステップと、
前記電子計算機を代入手段として機能させて、ｆ←１、Ｔ'←Ｑ'の代入演算を行わせるステップと、
前記電子計算機を第１演算手段として機能させて、有理点Ｔを通る接線lT,T(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,T(ｘP，ｙP)を演算する代わりに、lT,T(ｘP，ｙP)ｖ-1/2をlT',T'(ｎ，ｍ)で演算して、ｆ←f2・lT',T'(ｎ，ｍ)の代入演算を行わせるステップと、
前記電子計算機を第２演算手段として機能させて、Ｔ'←２Ｔ'の代入演算を行わせるステップと、
前記電子計算機を第３演算手段として機能させて、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、有理点ＴとＱを通る直線lT,Q(ｘ，ｙ)＝０の左辺に有理点Ｐの座標（ｘP，ｙP）を代入した値lT,Q(ｘP，ｙP)を演算する代わりに、lT,Q(ｘP，ｙP)ｖ-1/2をlT',Q'(ｎ，ｍ)で演算して、ｆ←f・lT',Q'(ｎ，ｍ)の代入演算を行わせるステップと、
前記電子計算機を第４演算手段として機能させて、前記ｓを２進数表示とした場合の所定のビットの値が１である場合に、Ｔ'←Ｔ'＋Ｑ'の代入演算を行わせるステップと、
前記電子計算機を第５演算手段として機能させて、(ｑ6h−１)/r乗のべき乗算の演算を行わせるステップと
を有することを特徴とするペアリング演算方法。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２００９−１０９７７２（Ｐ２００９−１０９７７２Ａ）
【公開日】平成２１年５月２１日（２００９．５．２１）
【国際特許分類】
【出願番号】特願２００７−２８２４８７（Ｐ２００７−２８２４８７）
【出願日】平成１９年１０月３０日（２００７．１０．３０）
【特許番号】特許第４１８９８２８号（Ｐ４１８９８２８）
【特許公報発行日】平成２０年１２月３日（２００８．１２．３）
【出願人】（５０４１４７２４３）国立大学法人 岡山大学 (444)
【復代理人】
【識別番号】１００１２５６１２
【弁理士】
【氏名又は名称】中嶋 裕昭
【Ｆターム（参考）】
【公開日】平成２１年５月２１日（２００９．５．２１）
【国際特許分類】
【出願日】平成１９年１０月３０日（２００７．１０．３０）
【特許番号】特許第４１８９８２８号（Ｐ４１８９８２８）
【特許公報発行日】平成２０年１２月３日（２００８．１２．３）
【出願人】（５０４１４７２４３）国立大学法人 岡山大学 (444)
【復代理人】
【識別番号】１００１２５６１２
【弁理士】
【氏名又は名称】中嶋 裕昭
【Ｆターム（参考）】
[ Back to top ]