(57)【要約】【課題】Ｔａｔｅペアリングの計算を計算量が少なく高速に行うことが可能なアルゴリズムを提案する。【解決手段】楕円曲線Ｅｂ：ｘ３−ｘ＋ｂ，ｂ∈｛−１，１｝上の２点Ｐ，Ｑの座標データを入力し、標数３の体Ｆｑ（ここで、ｑ＝３ｎ）での四則演算により図１のアルゴリズムを用いてηＴペアリングηＴ（Ｐ，Ｑ）の３（ｎ＋１）／２乗を計算する。続いて、ηＴ（Ｐ，Ｑ）の３（ｎ＋１）／２乗からηＴ（Ｐ，Ｑ）を求める。図１のアルゴリズムでは、計算の時間コストの大きい３乗根の演算を必要としないため、従来のアルゴリズムより高速に計算を行うことができる。【選択図】図１
2008020653.tif 000002
【特許請求の範囲】
【請求項１】
楕円曲線Ｅｂ：ｙ２＝ｘ３−ｘ＋ｂ，ｂ∈｛−１，１｝上の２点Ｐ，Ｑの座標データを入力する入力手段と、
標数３の体Ｆｑ（ここで、ｑ＝３ｎ）での四則演算により前記２点Ｐ，Ｑの座標データからηＴペアリングηＴ（Ｐ，Ｑ）の３（ｎ＋１）／２乗を演算する第一の演算手段と、
前記第一の演算手段による計算結果に基づいてηＴ（Ｐ，Ｑ）を求める第二の演算手段と
を具備することを特徴とするペアリング計算装置。
【請求項２】
楕円曲線Ｅｂ：ｙ２＝ｘ３−ｘ＋ｂ，ｂ∈｛−１，１｝上の２点Ｐ，Ｑの座標データを入力する入力手段と、
標数３の体Ｆｑ（ここで、ｑ＝３ｎ）での四則演算により前記２点Ｐ，Ｑの座標データからηＴペアリングηＴ（Ｐ，Ｑ）の３ｎ乗を演算する第一の演算手段と、
前記第一の演算手段による計算結果に基づいてηＴ（Ｐ，Ｑ）を求める第二の演算手段と
を具備することを特徴とするペアリング計算装置。
【請求項３】
Ｔａｔｅペアリングｅ（Ｐ，Ｑ）をｅ（Ｐ，Ｑ）＝＜Ｐ，ψ（Ｑ）＞ＮＭ（ここで、Ｎ＝３３ｎ＋１、Ｍ＝（３６ｎ−１）／Ｎ）として、
楕円曲線Ｅｂ：ｙ２＝ｘ３−ｘ＋ｂ，ｂ∈｛−１，１｝上の４点Ｐ，Ｑ，Ｒ，Ｓの座標データを入力する入力手段と、
標数３の体Ｆｑ（ここで、ｑ＝３ｎ）での四則演算により前記４点Ｐ，Ｑ，Ｒ，Ｓの座標データからＲ０＝＜Ｐ，ψ（Ｑ）＞Ｎ・＜Ｒ，ψ（Ｓ）＞Ｎを演算する第一の演算手段と、
前記第一の演算手段で求めたＲ０がＦｑ（ここで、ｑ＝３３ｎ）の元である場合には検証成功と判定し、Ｒ０がＦｑ（ここで、ｑ＝３３ｎ）の元でない場合には検証失敗と判定する判定手段と
を具備することを特徴とするペアリング計算装置。
【請求項４】
楕円曲線Ｅｂ：ｙ２＝ｘ３−ｘ＋ｂ，ｂ∈｛−１，１｝上の４点Ｐ，Ｑ，Ｒ，Ｓの座標データを入力する入力手段と、
標数３の体Ｆｑ（ここで、ｑ＝３ｎ）での四則演算により前記４点Ｐ，Ｑ，Ｒ，Ｓの座標データからＲ０＝（ηＴ（Ｐ，Ｑ）・ηＴ（Ｒ，Ｓ））Ｎ（ここで、Ｎ＝３（ｎ＋１）／２）を演算する第一の演算手段と、
前記第一の演算手段で求めたＲ０からＲ０Ｍ（ここで、Ｍ＝（３６ｎ−１）／（３ｎ＋ｂ３（ｎ＋１）／２＋１））を演算する第二の演算手段と、
Ｒ０Ｍ＝１である場合には検証成功と判定し、Ｒ０Ｍ≠１である場合には検証失敗と判定する判定手段と
を具備することを特徴とするペアリング計算装置。
【請求項５】
コンピュータに、
楕円曲線Ｅｂ：ｙ２＝ｘ３−ｘ＋ｂ，ｂ∈｛−１，１｝上の２点Ｐ，Ｑの座標データを入力する入力手順と、
標数３の体Ｆｑ（ここで、ｑ＝３ｎ）での四則演算により前記２点Ｐ，Ｑの座標データからηＴペアリングηＴ（Ｐ，Ｑ）の３（ｎ＋１）／２乗を演算する第一の演算手段と、
前記第一の演算手順による計算結果に基づいてηＴ（Ｐ，Ｑ）を求める第二の演算手段と
を実行させるためのペアリング計算プログラム。
【請求項６】
コンピュータに、
楕円曲線Ｅｂ：ｙ２＝ｘ３−ｘ＋ｂ，ｂ∈｛−１，１｝上の２点Ｐ，Ｑの座標データを入力する入力手順と、
標数３の体Ｆｑ（ここで、ｑ＝３ｎ）での四則演算により前記２点Ｐ，Ｑの座標データからηＴペアリングηＴ（Ｐ，Ｑ）の３ｎ乗を演算する第一の演算手順と、
前記第一の演算手順による計算結果に基づいてηＴ（Ｐ，Ｑ）を求める第二の演算手順と
を実行させるためのペアリング計算プログラム。
【請求項７】
Ｔａｔｅペアリングｅ（Ｐ，Ｑ）をｅ（Ｐ，Ｑ）＝＜Ｐ，ψ（Ｑ）＞ＮＭ（ここで、Ｎ＝３３ｎ＋１、Ｍ＝（３６ｎ−１）／Ｎ）として、
コンピュータに、
楕円曲線Ｅｂ：ｙ２＝ｘ３−ｘ＋ｂ，ｂ∈｛−１，１｝上の４点Ｐ，Ｑ，Ｒ，Ｓの座標データを入力する入力手順と、
標数３の体Ｆｑ（ここで、ｑ＝３ｎ）での四則演算により前記４点Ｐ，Ｑ，Ｒ，Ｓの座標データからＲ０＝＜Ｐ，ψ（Ｑ）＞Ｎ・＜Ｒ，ψ（Ｓ）＞Ｎを演算する第一の演算手順と、
前記第一の演算手順で求めたＲ０がＦｑ（ここで、ｑ＝３３ｎ）の元である場合には検証成功と判定し、Ｒ０がＦｑ（ここで、ｑ＝３３ｎ）の元でない場合には検証失敗と判定する判定手順と
を実行させるためのペアリング計算プログラム。
【請求項８】
コンピュータに、
楕円曲線Ｅｂ：ｙ２＝ｘ３−ｘ＋ｂ，ｂ∈｛−１，１｝上の４点Ｐ，Ｑ，Ｒ，Ｓの座標データを入力する入力手順と、
標数３の体Ｆｑ（ここで、ｑ＝３ｎ）での四則演算により前記４点Ｐ，Ｑ，Ｒ，Ｓの座標データからＲ０＝（ηＴ（Ｐ，Ｑ）・ηＴ（Ｒ，Ｓ））Ｎ（ここで、Ｎ＝３（ｎ＋１）／２）を演算する第一の演算手順と、
前記第一の演算手順で求めたＲ０からＲ０Ｍ（ここで、Ｍ＝（３６ｎ−１）／（３ｎ＋ｂ３（ｎ＋１）／２＋１））を演算する第二の演算手順と、
Ｒ０Ｍ＝１である場合には検証成功と判定し、Ｒ０Ｍ≠１である場合には検証失敗と判定する判定手順と
を実行させるためのペアリング計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高速にＴａｔｅペアリングの計算が可能なペアリング計算装置及びペアリング計算プログラムに関する。
【背景技術】
【０００２】
情報通信技術に不可欠な技術の一つとして、暗号化のための鍵を公開する公開鍵暗号の技術が知られている。しかし、公開鍵暗号の技術は、鍵の管理が煩雑であることや特定のグループのみが解読可能となるブロードキャスト暗号が未整備であるといった問題がある。
【０００３】
近年、これらの問題を解決する手法としてＴａｔｅペアリングを用いる暗号技術が注目されている。Ｔａｔｅペアリングを用いる暗号系では、ＩＤを公開鍵とするＩＤベース暗号やブロードキャスト暗号を構築でき、さらに署名長が従来の半分であるshort signatureといった署名システムも構築できる。
【０００４】
Ｔａｔｅペアリングの計算は、公開鍵暗号技術において暗号化や署名生成において用いる場合と、署名検証等で用いる場合の二通りがある。暗号化や署名生成で用いる場合には、Ｔａｔｅペアリングｅの値をそのまま用いる。一方、署名検証等で用いる場合には、二つのＴａｔｅペアリングの値ｅとｅ´が等しいことをチェックする。
【０００５】
続いて、楕円曲線上のＴａｔｅペアリングについて説明する。
まず、（１）式で示される楕円曲線を考える。
【０００６】
【数１】
2008020653.tif 000003
（１）式の楕円曲線Ｅｂ上の２点Ｐ，Ｑの和（Ｐ＋Ｑ）を次のように定義する。２点P，Qを通る直線Ｌ（Ｐ＝Ｑの時は、直線ＬはＰを通る楕円曲線Ｅｂの接線とする。）と楕円曲線Eｂとの交点Ｍを求め、その交点ＭとX軸に関して対称な位置に存在する点Ｎを求める。この交点Ｎを２点Ｐ，Ｑの和（Ｐ＋Ｑ）と定義する。図９は、ｂ＝１の場合の楕円曲線を示す図である。
【０００７】
Ｔａｔｅペアリングは、（１）式の楕円曲線上の２点Ｐ，Ｑに関してある値を返す関数ｅ（Ｐ，Ｑ）として（２）式のように定義する。Ｔａｔｅペアリングは（３）式に示すように双線形を満たすという性質があり、この双線形が暗号技術に応用される。
【０００８】
【数２】
2008020653.tif 000004
【０００９】
【数３】
2008020653.tif 000005
（２）式に示すＴａｔｅペアリングを計算する際には、楕円曲線上の計算及び標数３の体での演算（標数３の体でのアルゴリズム）が必要となる。
【００１０】
従来、＜Ｐ、ψ（Ｑ）＞Ｎを計算するアルゴリズムとしては、図１０に示すアルゴリズム１（Modified Duursma-Leeアルゴリズム）が知られている。アルゴリズム１においては、ステップ１２〜１６までループ処理をｎ回繰り返す。なお、σはσ２＝１を満たし、ρはρ３＝ρ＋ｂを満たし、拡大体Ｆｑ（ｑ＝３６ｎ）は｛１，σ，ρ，σρ，ρ２，σρ２｝を基底とする体Ｆｑ（ｑ＝３ｎ）の６次のベクトル空間である。
【００１１】
図１１に示すアルゴリズム２は、このループ処理の回数を減らす目的で改良されたアルゴリズムであり、ηＴペアリングを求めるものである。アルゴリズム２においては、ステップ２２〜２６までのループ処理の回数が（ｎ＋１）／２回に減少しているが、処理に時間のかかる３乗根の計算が発生する。なお、ηＴペアリングとＴａｔｅペアリングは（４）式に示すような関係がある。
【００１２】
【数４】
2008020653.tif 000006
ここで、Ｔ、Ｚ、Ｗの定義は（５）式で表される。
【００１３】
【数５】
2008020653.tif 000007
よって、（６）式を用いることでηＴペアリングからＴａｔｅペアリングを求めることが出来る。なお、ηＴ（Ｐ，Ｑ）Ｗは双線形性を満たす。
【００１４】
【数６】
2008020653.tif 000008
図１２は、各手法における署名と署名検証にかかる時間（単位はｍｓ）を比較した表であり、非特許文献１に記載されたものである。図１２において、ＥＣ（Elliptic Curve）は楕円曲線であり、ＢＬＳはshort signature、すなわちＴａｔｅペアリングの計算を用いた暗号である。
【非特許文献１】P. S. L. Barreto, “Efficient Algorithms for Pairing-Based Cryptosystems,” Advances in Cryptology-CRYPTO 2002, LNCS3027, Springer-Verlag, pp.354-368, 2002.
【非特許文献２】P. S. L. M. Barreto, S. Galbraith, C.O. hEigeartaigh and M. Scott, "Efficient Pairing computation on supersingular Abelian Varieties,"Cryptology ePrint Archive, Report 2004/375, 2004. ［２００６年７月１１日検索］,インターネット＜ＵＲＬ：http://eprint.iacr.org/2004/375＞.
【発明の開示】
【発明が解決しようとする課題】
【００１５】
図１２から明らかなように、従来のアルゴリズムを用いた方法では、特に署名検証においてＴａｔｅペアリングの計算に時間がかかり、ＲＳＡ（Rivest Shamir Adleman）方式やＤＳＡ（Digital Signature Algorithm）方式、楕円曲線の特性を利用した暗号方式等と比較して処理が遅い。このため、Ｔａｔｅペアリングの計算の高速化が世界的に大きな研究テーマとなっている。
【００１６】
本発明は上記事情を考慮してなされたもので、その目的は、Ｔａｔｅペアリングの計算を計算量が少なく高速に行うことが可能なアルゴリズムを提案し、該アルゴリズムを用いて処理を行うペアリング計算装置を提供することにある。
【課題を解決するための手段】
【００１７】
本発明は上記の課題を解決するためになされたもので、請求項１に記載の発明は、楕円曲線Ｅｂ：ｙ２＝ｘ３−ｘ＋ｂ，ｂ∈｛−１，１｝上の２点Ｐ，Ｑの座標データを入力する入力手段と、標数３の体Ｆｑ（ここで、ｑ＝３ｎ）での四則演算により前記２点Ｐ，Ｑの座標データからηＴペアリングηＴ（Ｐ，Ｑ）の３（ｎ＋１）／２乗を演算する第一の演算手段と、前記第一の演算手段による計算結果に基づいてηＴ（Ｐ，Ｑ）を求める第二の演算手段とを具備することを特徴とするペアリング計算装置である。
【００１８】
また、請求項２に記載の発明は、楕円曲線Ｅｂ：ｙ２＝ｘ３−ｘ＋ｂ，ｂ∈｛−１，１｝上の２点Ｐ，Ｑの座標データを入力する入力手段と、標数３の体Ｆｑ（ここで、ｑ＝３ｎ）での四則演算により前記２点Ｐ，Ｑの座標データからηＴペアリングηＴ（Ｐ，Ｑ）の３ｎ乗を演算する第一の演算手段と、前記第一の演算手段による計算結果に基づいてηＴ（Ｐ，Ｑ）を求める第二の演算手段とを具備することを特徴とするペアリング計算装置である。
【００１９】
また、請求項３に記載の発明は、Ｔａｔｅペアリングｅ（Ｐ，Ｑ）をｅ（Ｐ，Ｑ）＝＜Ｐ，ψ（Ｑ）＞ＮＭ（ここで、Ｎ＝３３ｎ＋１、Ｍ＝（３６ｎ−１）／Ｎ）として、楕円曲線Ｅｂ：ｙ２＝ｘ３−ｘ＋ｂ，ｂ∈｛−１，１｝上の４点Ｐ，Ｑ，Ｒ，Ｓの座標データを入力する入力手段と、標数３の体Ｆｑ（ここで、ｑ＝３ｎ）での四則演算により前記４点Ｐ，Ｑ，Ｒ，Ｓの座標データからＲ０＝＜Ｐ，ψ（Ｑ）＞Ｎ・＜Ｒ，ψ（Ｓ）＞Ｎを演算する第一の演算手段と、前記第一の演算手段で求めたＲ０がＦｑ（ここで、ｑ＝３３ｎ）の元である場合には検証成功と判定し、Ｒ０がＦｑ（ここで、ｑ＝３３ｎ）の元でない場合には検証失敗と判定する判定手段とを具備することを特徴とするペアリング計算装置である。
【００２０】
また、請求項４に記載の発明は、楕円曲線Ｅｂ：ｙ２＝ｘ３−ｘ＋ｂ，ｂ∈｛−１，１｝上の４点Ｐ，Ｑ，Ｒ，Ｓの座標データを入力する入力手段と、標数３の体Ｆｑ（ここで、ｑ＝３ｎ）での四則演算により前記４点Ｐ，Ｑ，Ｒ，Ｓの座標データからＲ０＝（ηＴ（Ｐ，Ｑ）・ηＴ（Ｒ，Ｓ））Ｎ（ここで、Ｎ＝３（ｎ＋１）／２）を演算する第一の演算手段と、前記第一の演算手段で求めたＲ０からＲ０Ｍ（ここで、Ｍ＝（３６ｎ−１）／（３ｎ＋ｂ３（ｎ＋１）／２＋１））を演算する第二の演算手段と、Ｒ０Ｍ＝１である場合には検証成功と判定し、Ｒ０Ｍ≠１である場合には検証失敗と判定する判定手段とを具備することを特徴とするペアリング計算装置である。
【００２１】
上記構成において、第一の演算手段、第二の演算手段及び判定手段は、例えば実施の形態において有限体演算器３０１で行われる。
【００２２】
また、請求項５に記載の発明は、コンピュータに、楕円曲線Ｅｂ：ｙ２＝ｘ３−ｘ＋ｂ，ｂ∈｛−１，１｝上の２点Ｐ，Ｑの座標データを入力する入力手順と、標数３の体Ｆｑ（ここで、ｑ＝３ｎ）での四則演算により前記２点Ｐ，Ｑの座標データからηＴペアリングηＴ（Ｐ，Ｑ）の３（ｎ＋１）／２乗を演算する第一の演算手段と、前記第一の演算手順による計算結果に基づいてηＴ（Ｐ，Ｑ）を求める第二の演算手段とを実行させるためのペアリング計算プログラムである。
【００２３】
また、請求項６に記載の発明は、コンピュータに、楕円曲線Ｅｂ：ｙ２＝ｘ３−ｘ＋ｂ，ｂ∈｛−１，１｝上の２点Ｐ，Ｑの座標データを入力する入力手順と、標数３の体Ｆｑ（ここで、ｑ＝３ｎ）での四則演算により前記２点Ｐ，Ｑの座標データからηＴペアリングηＴ（Ｐ，Ｑ）の３ｎ乗を演算する第一の演算手順と、前記第一の演算手順による計算結果に基づいてηＴ（Ｐ，Ｑ）を求める第二の演算手順とを実行させるためのペアリング計算プログラムである。
【００２４】
また、請求項７に記載の発明は、Ｔａｔｅペアリングｅ（Ｐ，Ｑ）をｅ（Ｐ，Ｑ）＝＜Ｐ，ψ（Ｑ）＞ＮＭ（ここで、Ｎ＝３３ｎ＋１、Ｍ＝（３６ｎ−１）／Ｎ）として、コンピュータに、楕円曲線Ｅｂ：ｙ２＝ｘ３−ｘ＋ｂ，ｂ∈｛−１，１｝上の４点Ｐ，Ｑ，Ｒ，Ｓの座標データを入力する入力手順と、標数３の体Ｆｑ（ここで、ｑ＝３ｎ）での四則演算により前記４点Ｐ，Ｑ，Ｒ，Ｓの座標データからＲ０＝＜Ｐ，ψ（Ｑ）＞Ｎ・＜Ｒ，ψ（Ｓ）＞Ｎを演算する第一の演算手順と、前記第一の演算手順で求めたＲ０がＦｑ（ここで、ｑ＝３３ｎ）の元である場合には検証成功と判定し、Ｒ０がＦｑ（ここで、ｑ＝３３ｎ）の元でない場合には検証失敗と判定する判定手順とを実行させるためのペアリング計算プログラムである。
【００２５】
また、請求項８に記載の発明は、コンピュータに、楕円曲線Ｅｂ：ｙ２＝ｘ３−ｘ＋ｂ，ｂ∈｛−１，１｝上の４点Ｐ，Ｑ，Ｒ，Ｓの座標データを入力する入力手順と、標数３の体Ｆｑ（ここで、ｑ＝３ｎ）での四則演算により前記４点Ｐ，Ｑ，Ｒ，Ｓの座標データからＲ０＝（ηＴ（Ｐ，Ｑ）・ηＴ（Ｒ，Ｓ））Ｎ（ここで、Ｎ＝３（ｎ＋１）／２）を演算する第一の演算手順と、前記第一の演算手順で求めたＲ０からＲ０Ｍ（ここで、Ｍ＝（３６ｎ−１）／（３ｎ＋ｂ３（ｎ＋１）／２＋１））を演算する第二の演算手順と、Ｒ０Ｍ＝１である場合には検証成功と判定し、Ｒ０Ｍ≠１である場合には検証失敗と判定する判定手順とを実行させるためのペアリング計算プログラムである。
【発明の効果】
【００２６】
請求項１及び請求項２に記載の発明によれば、ηＴペアリングを求める従来のアルゴリズム（図１１のアルゴリズム２）で計算コストが大きくなる要因であった３乗根の計算を行う必要がなくなるため、高速にηＴペアリングの計算を行うことができる。ηＴペアリングが求まると、（６）式を用いることでＴａｔｅペアリングを求めることが可能であるため、Ｔａｔｅペアリングの計算も高速に行うことができる。
【００２７】
また、Ｔａｔｅペアリングのもう一つの使用方法である、ｅ（Ｐ，Ｑ）＝ｅ（Ｒ，Ｓ）であるかを判定するDiffie-Hellmanペア検証においても従来はModified Durrsma-Leeアルゴリズムでｅ（Ｐ，Ｑ）及びｅ（Ｒ，Ｓ）をそれぞれ計算して比較していたため、２回のＴａｔｅペアリングの計算が必要となり時間がかかっていたが、請求項３及び請求項４に記載の発明はｅ（Ｐ，Ｑ）＝ｅ（Ｒ，Ｓ）と同値であるｅ（Ｐ，Ｑ）・ｅ（−Ｒ，Ｓ）＝１を利用して計算を行うものであり、３乗根の計算は行わないため、Diffie-Hellmanペア検証を高速に行うことができる。さらに、請求項３に記載の発明はべき乗の計算も必要とせず、より高速にDiffie-Hellmanペア検証を行うことができる。
【発明を実施するための最良の形態】
【００２８】
以下、図面を参照して本発明の実施形態について説明する。
まず、図１１に示した従来のアルゴリズム２を高速化したアルゴリズムに関して図１を参照して説明する。
【００２９】
図１のアルゴリズム３は、ηＴ（Ｐ，Ｑ）の３（ｎ＋１）／２乗を求めるアルゴリズムであり、アルゴリズム２と異なり、ループの終端（ステップ３５−ｄ）でアルゴリズム１の各値（ｘｑ、ｙｑ、ｘｐ、ｙｐ）が３ｉ＋１乗になる。３ｉ＋１乗を求める目的で、ステップ３１−ｂ、ステップ３３、ステップ３５−ａ、ステップ３５−ｃにおいて基底の調整を行っている。
【００３０】
アルゴリズム３の処理に関して詳細に説明する。楕円曲線Ｅｂ上の２点Ｐ（ｘｐ，ｙｐ）及びＱ（ｘｑ，ｙｑ）を入力すると、ｂ＝１の場合には−ｙｐの値をｙｐに代入する（ステップ３１−ａ）。続いて、体Ｆｑ（ｑ＝３ｎ）上でｂの値をｄに代入する（ステップ３１−ｂ）。
【００３１】
続いて、拡大体Ｆｑ（ｑ＝３６ｎ）上でーｙｐ（ｘｐ＋ｘｑ＋ｂ）＋ｙｑσ＋ｙｐρの演算を行い、結果をＲ０に代入する（ステップ３１−ｃ）。この後、ステップ３２〜３６のループ演算を（ｎ＋１）／２回行う。ループ演算においては、まず体Ｆｑ（ｑ＝３ｎ）上でｘｐ＋ｘｑ＋ｄの演算を行い、結果をγ０に代入する（ステップ３３）。
【００３２】
続いて、拡大体Ｆｑ（ｑ＝３６ｎ）上で−γ０２＋ｙｐｙｑσ−γ０ρ―ρ２を演算し、Ｒ１に代入する（ステップ３４−ａ）。その後、拡大体Ｆｑ（ｑ＝３６ｎ）上でＲ０Ｒ１を演算し、結果をＲ０に代入する（ステップ３４−ｂ）。
【００３３】
続いて、拡大体Ｆｑ（ｑ＝３ｎ）上で−ｙｐの値をｙｐに代入する（ステップ３５−ａ）。その後、拡大体Ｆｑ（ｑ＝３ｎ）上でｘｑ９を演算し、その結果をｘｑに代入する。さらに、ｙｑ９を演算し、その結果をｙｑに代入する（ステップ３５−ｂ）。その後、（ｄ−ｂ）に対してｍｏｄ３を演算し、結果をｄに代入する（ステップ３５−ｃ）。その後、拡大体Ｆｑ（ｑ＝３６ｎ）上でＲ０３を演算し、結果をＲ０に代入する（ステップ３５−ｄ）。
【００３４】
ループ演算が終了すると、Ｒ０の値をηＴ（Ｐ，Ｑ）の３（ｎ＋１）／２乗として出力する。標数３の体Ｆｑ（ｑ＝３ｎ）における演算の時間的コストは、数学的性質のため、３乗算の時間的コストが乗算や３乗根の時間的コストより小さいという特徴がある。図２は乗算の時間コストを基準（Ｍ）として各演算の時間コストを示した図である。
【００３５】
図２に示した時間コストに基づいて、アルゴリズム３の計算量を見積もると、（１０．２５ｎ＋１１．２５）Ｍとなる。一方、従来のアルゴリズム２の計算量は、（１２．０５ｎ＋１３．０５）Ｍとなる。一般的にｎ＝９７が用いられることが多いが、ｎ＝９７ではアルゴリズム３はアルゴリズム２より約１５％軽量化される。
【００３６】
なお、アルゴリズム３の出力はηＴ（Ｐ，Ｑ）の３（ｎ＋１）／２乗であるため、Ｔａｔｅペアリングｅ（Ｐ，Ｑ）を求める演算が必要であるが、この演算は次の手順により容易に求められる。ηＴ（Ｐ，Ｑ）Ｗの双線形より、（７）式が成立する。
【００３７】
【数７】
2008020653.tif 000009
すなわち、楕円曲線上の演算において予め３（ｎ−１）／２Ｐを求めた上でアルゴリズム３を実行し、Ｗ乗の計算を行うことで（７）式の左辺が求められる。続いて３ｎ乗根（計算コストは小さい）を行うことでηＴ（Ｐ，Ｑ）Ｗが求まり、（６）式に代入することでＴａｔｅペアリングｅ（Ｐ，Ｑ）が求まる。
【００３８】
なお、前述の通りηＴ（Ｐ，Ｑ）Ｗも双線形性を満たすため、暗号技術に応用することが可能である。暗号技術にηＴ（Ｐ，Ｑ）Ｗを用いる場合には、（６）式の演算を行う必要はない。
【００３９】
続いて、アルゴリズム３の処理を行うペアリング計算装置について説明する。図３はペアリング計算装置の構成を示す構成図である。図３において、ペアリング計算装置３０の有限体演算器３０１は、アルゴリズム３で行う演算を実行するハードウェアであり、二値の論理で演算を行う汎用のＣＰＵ（Central Processing Unit）であってもよいし、標数３の体での演算処理に特化した専用のハードウェアであってもよい。
【００４０】
コンソールインタフェース３０２は、外部の装置（図示せず）からペアリング計算装置３０を制御する際に用いるインタフェースである。通信インタフェース３０３は、入力ポートからデータを入力し、出力ポートへ演算結果を出力するインタフェースである。
【００４１】
メモリ３０４は、データを記憶するメモリである。メモリ３０４には、アルゴリズム３を実行するプルグラムである演算器制御プログラム３０５が記憶されており、また、有限体３０１における演算結果を格納する領域である演算データ記憶部３０６が確保されている。
【００４２】
入力ポートからＰ，Ｑのデータが入力されると、通信インタフェース３０３は、Ｐ，Ｑのデータを有限体演算器３０１に出力する。有限体演算器３０１は、演算器制御プログラム３０６にしたがってアルゴリズム３の処理を実行し、その結果（ηＴ（Ｐ，Ｑ）の３（ｎ＋１）／２乗）を通信インタフェース３０３へ出力する。通信インタフェース３０３は、ηＴ（Ｐ，Ｑ）の３（ｎ＋１）／２乗の演算結果を出力ポートから出力する。
【００４３】
次に、図１１に示した従来のアルゴリズム２を高速化した別のアルゴリズムに関して図４を参照して説明する。
【００４４】
図４のアルゴリズム４は、ηＴ（Ｐ，Ｑ）の３ｎ乗を求めるアルゴリズムであり、アルゴリズム２と異なり、ループの終端（ステップ４５−ｄ）でアルゴリズム１の各値（ｘｑ、ｙｑ、ｘｐ、ｙｐ）が３２ｉ＋２乗になる。３２ｉ＋２乗を求める目的で、ステップ４１−ｂ、ステップ４３、ステップ４５−ｃにおいて基底の調整を行っている。
【００４５】
アルゴリズム４の処理に関して詳細に説明する。楕円曲線Ｅｂ上の２点Ｐ（ｘｐ，ｙｐ）及びＱ（ｘｑ，ｙｑ）を入力すると、ｂ＝１の場合には−ｙｐの値をｙｐに代入する（ステップ４１−ａ）。続いて、体Ｆｑ（ｑ＝３ｎ）上でｂの値をｄに代入する（ステップ４１−ｂ）。
【００４６】
続いて、拡大体Ｆｑ（ｑ＝３６ｎ）上でーｙｐ（ｘｐ＋ｘｑ＋ｂ）＋ｙｑσ＋ｙｐρの演算を行い、結果をＲ０に代入する（ステップ４１−ｃ）。この後、ステップ４２〜４６のループ演算を（ｎ＋１）／２回行う。ループ演算においては、まず体Ｆｑ（ｑ＝３ｎ）上でｘｐ＋ｘｑ＋ｄの演算を行い、結果をγ０に代入する（ステップ４３）。
【００４７】
続いて、拡大体Ｆｑ（ｑ＝３６ｎ）上で−γ０２＋ｙｐｙｑσ−γ０ρ―ρ２を演算し、Ｒ１に代入する（ステップ４４−ａ）。この後、拡大体Ｆｑ（ｑ＝３６ｎ）上でＲ０Ｒ１を演算し、結果をＲ０に代入する（ステップ４４−ｂ）。
【００４８】
続いて、拡大体Ｆｑ（ｑ＝３ｎ）上でｘｐ３の演算を行い、結果をｘｐに代入する。さらに、ｙｐ３の演算を行い、結果をｙｐに代入する（ステップ４５−ａ）。この後、拡大体Ｆｑ（ｑ＝３ｎ）上でｘｑ２７を演算し、その結果をｘｑに代入する。さらに、ｙｑ２７を演算し、その結果をｙｑに代入する（ステップ４５−ｂ）。この後、（ｄ＋ｂ）に対してｍｏｄ３を演算し、結果をｄに代入する（ステップ４５−ｃ）。
【００４９】
続いて、ｉ＜（ｎ−１）／２の場合は、拡大体Ｆｑ（ｑ＝３６ｎ）上でＲ０９を演算し、結果をＲ０に代入する。一方、ｉ＝（ｎ−１）／２の場合は、Ｒ０３を演算し、結果をＲ０に代入する（ステップ４５−ｄ）。ループ演算が終了すると、Ｒ０の値をηＴ（Ｐ，Ｑ）の３ｎ乗として出力する。
【００５０】
図２に示した時間コストに基づいて、アルゴリズム４の計算量を見積もると、（１０．５ｎ＋１１．２）Ｍとなる。一方、従来のアルゴリズム２の計算量は、（１２．０５ｎ＋１３．０５）Ｍである。一般的にｎ＝９７が用いられることが多いが、ｎ＝９７ではアルゴリズム４はアルゴリズム２より約１３％軽量化される。
【００５１】
なお、アルゴリズム３の出力はηＴ（Ｐ，Ｑ）の３ｎ乗であるため、Ｔａｔｅペアリングｅ（Ｐ，Ｑ）を求める演算が必要であるが、この演算は次の手順により容易に求められる。アルゴリズム３により求めたηＴ（Ｐ，Ｑ）の３ｎ乗に対して３ｎ乗根（計算コストは小さい）の演算を行い、さらにＷ乗の計算を行うことでηＴ（Ｐ，Ｑ）Ｗが求められる。これを（６）式に代入することでＴａｔｅペアリングｅ（Ｐ，Ｑ）が求まる。
【００５２】
なお、前述の通りηＴ（Ｐ，Ｑ）Ｗも双線形性を満たすため、暗号技術に応用することが可能である。暗号技術にηＴ（Ｐ，Ｑ）Ｗを用いる場合には、（６）式の演算を行う必要はない。アルゴリズム４の処理を行うペアリング計算装置は、図３に示したペアリング計算装置３０の演算器制御プログラム３０５を、アルゴリズム４を実行するプログラムとすることで実現できる。
【００５３】
次に、二つのＴａｔｅペアリングの値ｅ（Ｐ，Ｑ）とｅ（Ｒ，Ｓ）とが一致するかを検証するＤＨ（Diffie-Hellman）検証を高速化したアルゴリズムについて説明する。従来のＤＨ検証は、ｅ（Ｐ，Ｑ）とｅ（Ｒ，Ｓ）とをそれぞれ計算してから一致判定を行っていたため、図１２で前述したとおり時間がかかっていた。また、ｅ（Ｐ，Ｑ）及びｅ（Ｒ，Ｓ）を従来のアルゴリズム２で求まるηＴペアリングから求めることで高速化したとしても、アルゴリズム２には３乗根の計算が必要であるため、時間がかかる。
【００５４】
ＤＨ検証においては、ｅ（Ｐ，Ｑ）＝ｅ（Ｒ，Ｓ）を検証する必要があるが、Ｔａｔｅペアリングの双線形性よりｅ（Ｒ，Ｓ）＝ｅ（−Ｒ，Ｓ）−１であるため、（８）式が成立する。したがって、ＤＨ検証では、ｅ（Ｐ，Ｑ）・ｅ（−Ｒ，Ｓ）＝１であるか否かを検証すればよい。
【００５５】
【数８】
2008020653.tif 000010
ここで、Ｒの座標を（ｘ，ｙ）とおくと、−Ｒの座標は（ｘ，−ｙ）となり容易に求められる。
【００５６】
ｅ（Ｐ，Ｑ）・ｅ（−Ｒ，Ｓ）＝１であるか否かを検証するアルゴリズムを、図５を参照して説明する。図５は図１０のアルゴリズム１に基づくＤＨ検証のアルゴリズムである。
【００５７】
Ｒ０（０）をアルゴリズム１に（Ｐ０，Ｑ０）を入力した時のＲ０、Ｒ０（１）をアルゴリズム１に（Ｐ１，Ｑ１）を入力した時のＲ０、Ｒ１（０）をアルゴリズム１に（Ｐ０，Ｑ０）を入力した時のＲ１、Ｒ１（１）をアルゴリズム１に（Ｐ１，Ｑ１）を入力した時のＲ１とおくと、アルゴリズム５はＲ０（０）Ｒ０（１）を求めるアルゴリズムである。
【００５８】
アルゴリズム５の処理に関して詳細に説明する。楕円曲線Ｅｂ上の４点Ｐ０（ｘｐ０，ｙｐ０）、Ｑ０（ｘｑ０，ｙｑ０）、Ｐ１（ｘｐ１，ｙｐ１）及びＱ１（ｘｑ１，ｙｑ１）を入力すると、まず拡大体Ｆｑ（ｑ＝３６ｎ）上でＲ０に１を代入する（ステップ５１−ａ）。
【００５９】
続いて、体Ｆｑ（ｑ＝３ｎ）上でｘｑ０３を演算し、結果をｘｑｏに代入する。同様に、ｙｐｏ３の演算結果をｙｐ０に、ｘｑ１３の演算結果をｘｑ１に、ｙｑ１３の演算結果をｙｑ１にそれぞれ代入する（ステップ５１−ｂ）。さらに、ｂｎに対してｍｏｄ３を演算し、結果をｄに代入する（ステップ５１−ｃ）。
【００６０】
この後、ステップ５２〜５６のループ演算をｎ回行う。ループ演算においては、まず体Ｆｑ（ｑ＝３ｎ）上でｘｐ０９を演算し、結果をｘｐｏに代入する。同様に、ｙｐ０９の演算結果をｙｐ０に、ｘｐ１９の演算結果をｘｐ１に、ｙｐ１９の演算結果をｙｐ１にそれぞれ代入する（ステップ５３−ａ）。
【００６１】
続いて、Ｓ（ｘｐ０，ｙｐ０，ｘｑ０，ｙｑ０，ｘｐ１，ｙｐ１，ｘｑ１，ｙｑ１，ｄ
）を演算し、結果を（λ０，λ１，λ２，λ３，λ４，λ５）に代入する（ステップ５３−ｂ）。ここで、Ｓはサブアルゴリズムであり、その詳細な処理は後述する。（λ０，λ１，λ２，λ３，λ４，λ５）をＲ１に代入する（ステップ５３−ｃ）。ここで求められるＲ１は、上述したＲ１（０）Ｒ１（１）に相当する。
【００６２】
続いて、拡大体Ｆｑ（ｑ＝３６ｎ）上でＲ０３の演算を行い、結果をＲ０に代入する（ステップ５４−ａ）。さらに、Ｒ０Ｒ１の演算を行い、結果をＲ０に代入する（ステップ５４−ｂ）。この後、体Ｆｑ（ｑ＝３ｎ）上で−ｙｑ０をｙｑ０に、−ｙｑ１をｙｑ１にそれぞれ代入する（ステップ５５−ａ）。その後、（ｄ−ｂ）に対してｍｏｄ３を演算し、結果をｄに代入する（ステップ５５−ｂ）。
【００６３】
ループ演算が終了すると、Ｒ０の値を＜Ｐ０，ψ（Ｑ０）＞Ｎ・＜Ｐ１，ψ（Ｑ１）＞Ｎ（Ｎ＝３３ｎ＋１）として出力する。なお、アルゴリズム５においては、（２）式におけるＮは３３ｎ＋１であるが、このとき、（３６ｎ−１）／（３３ｎ＋１）＝３３ｎ−１であるため、（９）式が成立する。
【００６４】
【数９】
2008020653.tif 000011
ところが、数学的性質により、Ｆｑ（ｑ＝３６ｎ）の０でない元ｘに対して、ｘの３３ｎ−１乗が１であることとｘがＦｑ（ｑ＝３３ｎ）の元であることとは同値である。したがって、Ｐ，Ｑ，−Ｒ，Ｓをアルゴリズム５に代入し、その結果がＦｑ（ｑ＝３３ｎ）の元であるか否かを判定することでＤＨ判定を行うことが可能であり、べき乗の演算を行う必要はない。
【００６５】
続いて、ステップ５３−ｂで用いたサブアルゴリズムＳの処理について図６を参照して説明する。サブアルゴリズムでは、ｘｐ０，ｙｐ０，ｘｑ０，ｙｑ０，ｘｐ１，ｙｐ１，ｘｑ１，ｙｑ１，ｄを入力し、体Ｆｑ（ｑ＝３ｎ）上でｘｐ０＋ｘｑ０＋ｄを演算し、結果をγ０に代入する。同様に、ｘｐ１＋ｘｑ１＋ｄを演算し、結果をγ１に代入する（ステップS０１）。
【００６６】
続いて、ｙｐ０ｙｑ０の演算結果をγ２に、ｙｐ１ｙｑ１の演算結果をγ３にそれぞれ代入する（ステップＳ０２）。この後、γ０γ１を演算し、結果をγ４に代入する（ステップＳ０３）。この後、γ２γ３を演算し、結果をγ５に代入する（ステップＳ０４）。γ２＋γ０の演算結果をγ６に、γ３＋γ１の演算結果をγ７にそれぞれ代入する（ステップＳ０５）。この後、γ０＋γ１を演算し、結果をγ８に代入する（ステップＳ０６）。
【００６７】
続いて、体Ｆｑ（ｑ＝３ｎ）上でγ６γ７−γ４−γ５を演算し、結果をλ３に代入する（ステップＳ０７）。この後、γ２＋γ３を演算し、結果をλ５に代入する（ステップＳ０８）。この後、γ４２−γ５＋ｂγ８を演算し、λ０に代入するステップＳ０９）。さらに、γ８λ３−γ４λ５を演算し、結果をλ１に代入する（ステップＳ１０）。
【００６８】
続いて、体Ｆｑ（ｑ＝３ｎ）上で（γ４＋１）γ８＋ｂを演算し、結果をλ２に代入する（ステップＳ１１）。その後、γ８２−γ４＋１を演算し、結果をλ４に代入する（ステップＳ１２）。以上の処理が終了すると、（λ０，λ１，λ２，λ３，λ４，λ５）を出力する。
【００６９】
図２に示した時間コストに基づいて、アルゴリズム５の計算量を見積もると、（２８．３ｎ＋０．５）Ｍとなる。一方、ｅ（Ｐ，Ｑ）とｅ（Ｒ，Ｓ）のそれぞれに対して従来のアルゴリズム１を用いた後にべき乗計算を行い、ＤＨ検証を行う場合の時間コストは、（４１ｎ＋１８．１）Ｍ＋２Ｆである。
【００７０】
ここで、Ｆはべき乗の計算コストであり、１Ｍ〜１０００Ｍである。一般的にｎ＝９７が用いられることが多いが、ｎ＝９７ではアルゴリズム４はアルゴリズム１より約３０％軽量化される。
【００７１】
続いて、アルゴリズム５の処理を行うペアリング計算装置について説明する。図７はペアリング装置の構成を示す構成図である。図７において、図３と同様の構成に対しては同じ符号を付与し、詳細な説明は省略する。ペアリング計算装置３１の演算器制御プログラム７０５は、アルゴリズム５を実行するプログラムである。
【００７２】
入力ポートからＰ，Ｑ，Ｒ，Ｓのデータが入力されると、通信インタフェース３０３は、Ｐ，Ｑ，Ｒ，Ｓのデータを有限体演算器３０１に出力する。有限体演算器３０１は、Ｒを−Ｒに変換した上で演算器制御プログラム７０５にしたがってアルゴリズム５の処理を実行し、その結果（＜Ｐ０，ψ（Ｑ０）＞Ｎ・＜Ｐ１，ψ（Ｑ１）＞Ｎ（Ｎ＝３３ｎ＋１））がＦｑ（ｑ＝３３ｎ）の元であるか否かを判定する（判定手段）。
【００７３】
Ｆｑ（ｑ＝３３ｎ）の元である場合には、ＤＨ判定の結果は一致したと判定し「Ｙｅｓ」のデータを通信インタフェース３０３へ出力する。一方、Ｆｑ（ｑ＝３３ｎ）の元でない場合には、ＤＨ判定の結果は一致しないと判定し「Ｎｏ」のデータを通信インタフェース３０３へ出力する。通信インタフェース３０３は、「Ｙｅｓ」又は「Ｎｏ」のデータを出力ポートから出力する。
【００７４】
次に、二つのＴａｔｅペアリングの値ｅ（Ｐ，Ｑ）とｅ（Ｒ，Ｓ）とが一致するかを検証するＤＨ（Diffie-Hellman）検証を高速化した別のアルゴリズムについて説明する。図８はアルゴリズム３に基づくＤＨ検証のアルゴリズムであり、ηＴペアリングのＤＨ検証を行うものであるが、（８）式が成立することを利用したアルゴリズムである点はアルゴリズム５と同様である。
【００７５】
アルゴリズム６の処理に関して詳細に説明する。楕円曲線Ｅｂ上の４点Ｐ０（ｘｐ０，ｙｐ０）、Ｑ０（ｘｑ０，ｙｑ０）、Ｐ１（ｘｐ１，ｙｐ１）及びＱ１（ｘｑ１，ｙｑ１）を入力すると、まずｂ＝１の場合には−ｙｐ０の値をｙｐ０に、−ｙｐ１の値をｙｐ１にそれぞれ代入する（ステップ６１−ａ）。続いて、体Ｆｑ（ｑ＝３ｎ）上でｂの値をｄに代入する（ステップ６１−ｂ）。
【００７６】
続いて、体Ｆｑ（ｑ＝３６ｎ）上でｙｐ０（ｘｐ０＋ｘｑ０＋ｂ）＋ｙｑ０σ＋ｙｐ０ρを演算し、結果をＲ０に代入する。さらに、ｙｐ１（ｘｐ１＋ｘｑ１＋ｂ）＋ｙｑ１σ＋ｙｐ１ρを演算し、結果をＲ１に代入する（ステップ６１−ｃ）。その後、Ｒ０Ｒ１を演算し、結果をＲ０に代入する（ステップ６１−ｄ）。
【００７７】
この後、ステップ６２〜６６のループ演算を（ｎ＋１）／２回行う。ループ演算においては、まず、Ｓ（ｘｐ０，ｙｐ０，ｘｑ０，ｙｑ０，ｘｐ１，ｙｐ１，ｘｑ１，ｙｑ１，ｄ）を演算し、結果を（λ０，λ１，λ２，λ３，λ４，λ５）に代入する（ステップ６３−ａ）。その後、（λ０，λ１，λ２，−λ３，λ４，−λ５）の値をＲ１に代入する（ステップ６３−ｂ）。
【００７８】
続いて、拡大体Ｆｑ（ｑ＝３６ｎ）上でＲ０Ｒ１を演算し、結果をＲ０に代入する（ステップ６４）。その後、ｘｑ０９を演算し、結果をｘｑ０に代入する。同様に、ｙｑ０９の演算結果をｙｑ０に、ｘｑ１９の演算結果をｘｑ１に、ｙｑ１９の演算結果をｙｑ１にそれぞれ代入する（ステップ６５−ａ）。さらに、（ｄ−ｂ）に対してｍｏｄ３を演算し、結果をｄに代入する（ステップ６５−ｂ）。
【００７９】
続いて、体Ｆｑ（ｑ＝３６ｎ）上でＲ０３を演算し、結果をＲ０に代入する（ステップ６５−ｃ）。ループ演算が終了すると、Ｒ０の値を（ηＴ（Ｐ０，Ｑ０）・ηＴ（Ｐ１，Ｑ１））の３（ｎ＋１）／２乗として出力する。アルゴリズム６から出力されるＲ０に対して（１０）式のべき乗計算を行った後にＤＨ検証の判定を行う。
【００８０】
【数１０】
2008020653.tif 000012
アルゴリズム６の処理を行うペアリング計算装置は、図７に示したペアリング計算装置３１の演算器制御プログラム７０５を、アルゴリズム６を実行するプログラムとすることで実現できる。有限体演算器３０１は、（１０）式によるべき乗計算後のＲ０が１である場合にはＤＨ検証で一致したと判定し、出力ポートへの出力は「Ｙｅｓ」となる。一方、Ｒ０が１でない場合にはＤＨ検証で一致しないと判定し、出力ポートへの出力は「Ｎｏ」となる。
【００８１】
図２に示した時間コストに基づいて、アルゴリズム６の計算量を見積もると、（１４．７ｎ＋３４．２５）Ｍ＋Ｆとなる。一方、ηＴ（Ｐ，Ｑ）とηＴ（Ｒ，Ｓ）のそれぞれに対してアルゴリズム３を用いた後にべき乗計算を行い、ＤＨ検証を行う場合の時間コストは、（２４．１ｎ＋２６．１）Ｍ＋２Ｆである。一般的にｎ＝９７が用いられることが多いが、ｎ＝９７ではアルゴリズム６はアルゴリズム２より約４０％軽量化される。
【００８２】
本発明のアルゴリズム３及び４では、標数３の体における演算で時間コストの小さい３乗算の計算を増やす代わりに、３乗根の演算を行わないようにしたため、Ｔａｔｅペアリング（又はηＴペアリング）を高速に計算することが出来る。さらに、本発明のアルゴリズム５及び６では、３乗根の演算を行わないだけでなく、（８）式の性質を利用してＤＨ検証を行うことで計算量を削減し、高速にＤＨ検証を行うことができる。
【００８３】
以上、本発明の実施形態を詳述してきたが、具体的な構成は本実施形態に限られるものではなく、本発明の要旨を逸脱しない範囲の設計変更等も含まれる。
【産業上の利用可能性】
【００８４】
本発明は、ＩＤを公開鍵とするＩＤベース暗号やブロードキャスト暗号、さらに署名長が従来の半分であるshort signatureといった署名システムにおいて、署名や署名検証の段階でＴａｔｅペアリング又はηＴペアリングを計算する装置に用いて好適である。
【図面の簡単な説明】
【００８５】
【図１】ηＴ（Ｐ，Ｑ）の３（ｎ＋１）／２乗を求める本願の第一のアルゴリズムである。
【図２】乗算の時間コストを基準（Ｍ）として各演算の時間コストを示した図である。
【図３】図１のアルゴリズムを実行するペアリング計算装置の構成を示す構成図である。
【図４】ηＴ（Ｐ，Ｑ）の３ｎ乗を求める本願の第二のアルゴリズムである。
【図５】図１０のアルゴリズムに基づくＤＨ検証を行う、本願の第三のアルゴリズムである。
【図６】図５のサブアルゴリズムＳを示す図である。
【図７】図５のアルゴリズムを実行するペアリング計算装置の構成を示す構成図である。
【図８】ηＴペアリングに基づくＤＨ検証を行う、本願の第四のアルゴリズムである。
【図９】ｙ２＝ｘ３−ｘ＋１の楕円曲線を示す図である。
【図１０】従来のModified Duursma-Leeアルゴリズムを示す図である。
【図１１】図１０のアルゴリズムを改良し、ηＴペアリングを求めるようにしたアルゴリズムを示す図である。
【図１２】暗号化に用いる各手法における署名と署名検証にかかる時間（単位はｍｓ）を比較した表である。
【符号の説明】
【００８６】
３０…ペアリング計算装置、３０１…有限体演算器、３０２…コンソールＩ／Ｏ、３０３…通信インタフェース、３０４…メモリ、３０５…演算器制御プログラム、３０６…演算データ記憶部。
【図１】
2008020653.tif 000013
【図２】
2008020653.tif 000014
【図３】
2008020653.tif 000015
【図４】
2008020653.tif 000016
【図５】
2008020653.tif 000017
【図６】
2008020653.tif 000018
【図７】
2008020653.tif 000019
【図８】
2008020653.tif 000020
【図９】
2008020653.tif 000021
【図１０】
2008020653.tif 000022
【図１１】
2008020653.tif 000023
【図１２】
2008020653.tif 000024