カースルズ−テイトペアリングに基づくデータの暗号処理
【課題】カースルズ−テイトペアリングの関数としてデータを暗号処理するシステムおよび方法を提供する。
【解決手段】一態様では、シャファレヴィッチ−テイト群は、コホモロジ群から生成される。カースルズ−テイトペアリングは、シャファレヴィッチ−テイト群の要素の関数として決定される。次に、データを、カースルズ−テイトペアリングの関数として暗号処理する。
【解決手段】一態様では、シャファレヴィッチ−テイト群は、コホモロジ群から生成される。カースルズ−テイトペアリングは、シャファレヴィッチ−テイト群の要素の関数として決定される。次に、データを、カースルズ−テイトペアリングの関数として暗号処理する。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書のシステムおよび方法は、一般に、暗号処理に関し、より詳細には、カースルズ−テイトペアリングに基づくデータの暗号処理に関する。
【背景技術】
【０００２】
既存のペアリング（pairing）ベースの暗号システムは、楕円曲線またはアーベル多様体上の点で評価される、ベイユペアリングまたはテイトペアリングを使用する。固定された自然数ｍについて、ベイユペアリングｅｍは、楕円曲線上の２つのｍ−トーションポイント（m-torsion point）を入力として取り、ｍ番目の原始根を出力する双一次写像である。
【０００３】
【非特許文献１】C. Beaver, "5-torsion in the Shafarevich-Tate group of a family of elliptic curves", J. Number Theory, 82(1):25-46, 2000
【非特許文献２】William G. McCallum, "On the Shafarevich-Tate group of the Jacobian of a quotient of the Fermat curve", Invent. Math., 93(3):637-666, 1988 (I, Proposition 6.9)
【非特許文献３】Bjorn Poonen and Micheal Stoll, "The Cassels-Tate pairing on polarized abelian varieties", Ann. of Math. (2), 150(3): 1109-1149, 1999
【非特許文献４】McCallum (McC88 p.640)
【非特許文献５】Serre, Local Fields, Chapter XIV
【発明の開示】
【発明が解決しようとする課題】
【０００４】
カースルズ−テイトペアリングに基づいてデータを暗号処理するシステムおよび方法を提供する。
【課題を解決するための手段】
【０００５】
一態様では、シャファレヴィッチ−テイト群は、コホモロジ群から生成される。カースルズ−テイトペアリングは、シャファレヴィッチ−テイト群の要素の関数として決定される。次に、データは、カースルズ−テイトペアリングの関数として暗号処理される。
【０００６】
図面では、構成要素の符号の左端の桁が、その構成要素が初めて現れる特定の図面を識別する。
【発明を実施するための最良の形態】
【０００７】
（概要）
シャファレヴィッチ−テイト群におけるカースルズ−テイトペアリングに基づく、データの暗号処理のシステムおよび方法は、楕円曲線またはアーベル多様体において評価される、ベイユペアリングまたはテイトペアリングを使用するすべてのペアリングベースシステムに対する代替案を提供する。さらに、このシステムおよび方法は、シャファレヴィッチ−テイト群におけるすべてのペアリング応用（applications）において、応用分野（applications）を有する。
【０００８】
必須ではないが、カースルズ−テイトペアリングに基づくデータの暗号処理のシステムおよび方法を、パーソナルコンピュータなどのコンピューティングデバイスによって実行されるコンピュータ実行可能命令（プログラムモジュール）の一般的な文脈で説明する。プログラムモジュールは、一般に、特定のタスクを実行するか、または特定の抽象データ型を実施するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。本システムおよび方法を、前述の文脈で説明するが、以下に記載の行為および動作は、ハードウェアでも実施することができる。カースルズ−テイトペアリングに基づくデータの暗号処理のシステムおよび方法の上記および他の態様を、以下に詳細に説明する。
【０００９】
（例示的システム）
図１に、カースルズ−テイトペアリングに基づいてデータを暗号処理する例示的システム１００を示す。システム１００は、楕円曲線またはアーベル多様体において評価される、ベイユペアリングまたはテイトペアリングに基づくペアリングベースシステムに対する代替案を提供する。システム１００は、楕円曲線またはアーベル多様体のシャファレヴィッチ−テイト群上の点の群を、この群に対するカースルズ−テイトペアリングと組み合わせて使用する。システム１００は、多数の既知のペアリングベースの暗号プロトコルのいずれかを使用して、暗号システムでカースルズ−テイトペアリングの動作を実施することができる。たとえば、一実施形態で、システム１００は、署名（プレイン、ブラインド、プロキシ、リング、否定不能など）、暗号化、認証付き暗号化、ブロードキャスト暗号化、キーワード検索を用いる暗号化、バッチ署名、キーアグリーメント（プレイン、認証付き、グループなど）、トラストオーソリティおよび公開鍵認証、階層暗号システム、閾値暗号および署名、カメレオンハッシュおよび署名、認証、アプリケーションおよびシステム、または同種のものを対象とするものなどの、アイデンティティベースの暗号アルゴリズムに基づくプロトコルを実施する。
【００１０】
他の実施形態では、カースルズ−テイトペアリングに基づく暗号処理のシステム１００は、アクセス制御、キーアグリーメント、非対話型鍵配布、信任証（匿名、隠し、セルフ−ブラインダブル）、シークレットハンドシェイク、立証可能なセキュア署名、ショートシグネチャー、アグリゲート暗号化署名、リング暗号化署名、検証可能な暗号化署名、ブラインド署名、部分的なブラインド署名、プロキシ署名、否認不可署名、サインクリプション（signcryption）、多重署名、閾値署名、リミテッド−ベリファイア（limited-verifier）署名、デジグネイティッド−ベリファイア（designated-verifier）署名、閾値暗号システム、階層暗号システム、ロール−ベースの（role-based）暗号システム、カメレオンハッシュ、カメレオン署名、証明可能な確立関数、強力なインスレイティッド暗号化（strongly insulated encryption）、侵入攻撃に強い暗号化（intrusion-resilient encryption）、証明書なし公開鍵暗号方式（certificate-less PKC）、エーエル(al)、トレイタトレーシング（traitor tracing）、または同種のものに基づくプロトコルを実装する。
【００１１】
システム１００は、ネットワークを介して、ネットワーク化されたコンピューティングデバイス１０４に結合された、コンピューティングデバイス１０２を含む。コンピューティングデバイス１０２は、プログラムモジュール１０６およびプログラムデータ１０８を含む。プログラムモジュール１０６は、たとえば、（ａ）楕円曲線またはアーベル多様体のシャファレヴィッチ−テイト群１１４における点の群、および（ｂ）関連するカースルズ−テイトペアリング１１６を使用して、オリジナルデータ（「その他のデータ」１３２のそれぞれの部分）を暗号化するか、またはこれに署名する、署名／暗号化モジュール１１０を含む。例示のために、署名／暗号化モジュール１１０によってそれぞれ署名されたか、または暗号化されたオリジナルデータを、暗号化または署名されたデータ１１８としてコンピューティングデバイス１０２のプログラムデータ部分に示す。図１のネットワーク化されたコンピューティングデバイス１０４も、プログラムモジュールおよびプログラムデータを含む。たとえば、ネットワーク化されたコンピューティングデバイス１０４は、シャファレヴィッチ−テイト群１１４の要素の関数として、検証／暗号化解除モジュール１２０によって生成された、カースルズ−テイトペアリング１２２の関数として、暗号化または署名されたデータ１１８を暗号化解除または検証する、検証／暗号化解除モジュール１２０を含む。システム１００の上記および他の態様を、以下に詳細に説明する。
【００１２】
（シャファレヴィッチ−テイト群）
シャファレヴィッチ−テイト群１１４は、コホモロジ群１２４の部分群における要素などの、オブジェクトの集合である。シャファレヴィッチ−テイト群１１４は、シャファレヴィッチ−テイト群１１４における離散対数の困難さの関数として、システム１００にセキュリティを提供する。シャファレヴィッチ−テイト群１１４は、次のように定義される。Ｋが数体１２４である場合に、ＭＫによって、Ｋの同値でない付値（nonequivalent valuations）の集合を表す。Ｋｖによって、素数ｖによって導入される距離（metric）に関するＫの完備を表し、ｋｖによって、剰余体を表す。一般に、ｆ：Ｇ→Ｇ’が、群の射である場合に、その核（kernel）をＧｆによって表す。φ：Ａ→Ｂが、アーベル多様体の同種写像（isogeny）である場合に、Ａφによってφの核を表し、
【００１３】
【数１】
【００１４】
によって、双対写像（dual isogeny）
【００１５】
【数２】
【００１６】
を表す。体Ｋおよび滑らかな可換のＫ群スキームＧについて、群コホモロジＨｉ（Ｇａｌ（Ｋｓ／Ｋ），Ｇ（Ｋｓ））を表すのにＨｉ（Ｋ，Ｇ）と書き、Ｋｓは、Ｋの固定された離閉包である。
【００１７】
上記に鑑みて、アーベル多様体のシャファレヴィッチ−テイト群１１４を定義する。Ａが、数体Ｋ上のアーベル多様体であるものとする。以下で定義されるＡのシャファレヴィッチ−テイト群１１４は、あるtorsorについての局所−大域原理（local-to-global principle）の失敗を測定する。Ｋ上のＡのシャファレヴィッチ−テイト群１１４は、
【００１８】
【数３】
【００１９】
である。
【００２０】
（カースルズ−テイトペアリング）
Ａが、数体Ｋ上で定義されたアーベル多様体であるものとする。カースルズ−テイト（「ＣＴ」）ペアリング（たとえば、１１６または１２２）、ＣＴ（＊，＊）は、III（Ａ／Ｋ）の双一次非対称非退化ペアリング（割り切れる部分群を法とする（modulo））であり、
【００２１】
【数４】
【００２２】
はＱ／Ｚ内の値をとる。このＣＴペアリングは、ローカルペアリング（たとえば、ローカルペアリング１２６）の合計として書かれる。各ローカルペアリングは、ｍに関するテイトペアリング、ベイユペアリング、およびヒルベルト記号の評価の組合せによって評価される。Ａにおけるペアリングの特殊な事例、楕円曲線は、非特許文献１に記載のものなどの技法を使用して、より単純に評価することができる。
【００２３】
具体的に言うと、Ａが、デュアル（dual）
【００２４】
【数５】
【００２５】
を有する数体Ｋ上のアーベル多様体であるものとする。カースルズ−テイトペアリングＣＴ（＊，＊）は、
【００２６】
【数６】
【００２７】
であるペアリングであり、これは、割り切れる群を法とする非退化である。特殊な事例での定義を続ける（一般的な定義については、非特許文献２を参照されたい。他の同等の定義については、非特許文献３を参照されたい）。φ、ψが、Ｋ上のＡの同種写像であるものとする。カースルズ−テイトペアリングの制限は、φの核および
【００２８】
【数７】
【００２９】
に制限される。
【００３０】
正確なシーケンス
【００３１】
【数８】
【００３２】
および
【００３３】
【数９】
【００３４】
がある。＊が、グローバルコホモロジクラス、双対輪体、または双対体である場合に、対応するローカルオブジェクトについて＊ｖと書く。ａ∈III（Ａ／Ｋ）φであり、
【００３５】
【数１０】
【００３６】
であるものとする。ＣＴ（ａ，ａ’）を定義する。ａおよびａ’に写像されるＨ１（Ｋ，Ａφ）および
【００３７】
【数１１】
【００３８】
の要素ｂおよびｂ’を選択する。各ｖについて、ａは、Ｈ１（Ｋｖ，Ａ）で０に写像され、したがって、ｂｖを、Ａ（Ｋｖ）の像内の要素ｂｖ，１∈Ｈ１（Ｋｖ，Ａφψ）にリフトすることができる。ａが、Ｈ１（Ｋ，Ａ）に含まれるψによって割り切れ、たとえばａ＝ψａ１であると仮定し、ａ１に写像される要素ｂ１∈Ｈ１（Ｋ，Ａφψ）を選択する。すると、ｂｖ，１−ｂ１，ｖが、Ｈ１（Ｋｖ，Ａφψ）→Ｈ１（Ｋｖ，Ａφ）の下で０に写像され、したがって、これはＨ１（Ｋｖ，Ａψ）での要素ｃｖの像である。ＣＴ（ａ，ａ’）を、
【００３９】
【数１２】
【００４０】
になるように定義する。ここで、カップ積は、ベイユペアリング
【００４１】
【数１３】
【００４２】
によって誘導される。
【００４３】
ベイユペアリングによって誘導されるカップ積は、ベイユペアリングによって誘導されるコホモロジ上での写像との通常のカップ積の合成
【００４４】
【数１４】
【００４５】
を意味する。写像ｉｎｖｖは、正準写像Ｈ２（Ｋｖ，Ｇｍ）→Ｑ／Ｚである（ｉｎｖｖの像はｍ−１Ｚ／Ｚ内にある）。
【００４６】
カースルズ−テイトペアリング１２２は、ローカルペアリングの合計として記述される。具体的に言うと、ガロア加群（Galois modules）の写像
【００４７】
【数１５】
【００４８】
が、ガロア不変セクション（Galois invariant section）
【００４９】
【数１６】
【００５０】
を有すると仮定する。すると、ａ１＝ｓ＊ａとすることができる。次に、カースルズ−テイトペアリング１２２を、ローカルペアリングの合計として表す。III：＝III（Ａ／Ｋ）であり、
【００５１】
【数１７】
【００５２】
であるものとする。Ｓφが、セルマー群であるものとするが、これは、正確なシーケンス
０→Ａ（Ｋ）／φＡ（Ｋ）→Ｓφ→IIIφ→０
によって定義されるＨ１（Ｋ，Ａφ）の部分集合である。また、
【００５３】
【数１８】
【００５４】
が、
【００５５】
【数１９】
【００５６】
−セルマー群であるものとするが、これは、
【００５７】
【数２０】
【００５８】
の対応する正確なシーケンスによって定義される。ここで、カースルズ−テイトペアリングを
【００５９】
【数２１】
【００６０】
にリフトすることができる。次に、セルマー群でのペアリングを、ローカルペアリングの合計として記述する。この動機は、次の通りである。φ＝ψについてこれを適用する。IIIφを直接に計算する小さい可能性があるが、セルマー群Ｓφを計算できる。カースルズ−テイトペアリングのセルマー群
【００６１】
【数２２】
【００６２】
へのリフトは、Ａ（Ｋ）／φＡ（Ｋ）から来る要素について自明である。したがって、
【００６３】
【数２３】
【００６４】
におけるカースルズ−テイトペアリングが自明でない場合に、IIIにおける自明でないφ−トーションを有さなければならない。
【００６５】
IIIの定義により、
【００６６】
【数２４】
【００６７】
における第３垂直写像は、０である。したがって、写像ｌｖ，φ：Ｓφ→Ａ（Ｋｖ）／φＡ（Ｋｖ）が得られる。ｌｖ，φを使用して、セルマー群をローカル群Ａ（Ｋｖ）／φＡ（Ｋｖ）に写像する。ここで、ローカルペアリング
【００６８】
【数２５】
【００６９】
を定義することができ、ｂ∈Ｓφおよび
【００７０】
【数２６】
【００７１】
について、
【００７２】
【数２７】
【００７３】
が得られる。
【００７４】
（ローカルペアリングの定義）
ローカルペアリング（たとえば、ローカルペアリング１２６）
【００７５】
【数２８】
【００７６】
を定義するために、次の図式
【００７７】
【数２９】
【００７８】
を検討する。ｘ∈Ａ（Ｋｖ）／φＡ（Ｋｖ）であり、
【００７９】
【数３０】
【００８０】
であるものとする。ｘ１が、ｘのＡ（Ｋｖ）／φψＡ（Ｋｖ）へのリフトであるものとする。すると、ｉφψ（ｘ１）およびｓ＊ｉφ（ｘ）の両方が、Ｈ１（Ｋｖ，Ａφ）において同一の像を有する。したがって、（ｉφψ（ｘ１）−ｓ＊ｉφ（ｘ））は、要素ｃｖ∈Ｈ１（Ｋｖ，Ａψ）の像である。
【００８１】
【数３１】
【００８２】
を定義する。
【００８３】
ローカルペアリング
【００８４】
【数３２】
【００８５】
は、アーベル群の双一次ペアリングである。
【００８６】
【数３３】
【００８７】
上述のカースルズ−テイトペアリング１２２は、非特許文献４に記載されているように、ローカルペアリングの合計として表すことができ
【００８８】
【数３４】
【００８９】
であり、次の補助定理は、上記の合計を有限の合計に減らす（reduce）。ｖが複素アルキメデス的付値であるか、ｖがアルキメデス的でない場合に、Ａは、ｖの極大イデアルを法とする良還元（good reduction）を有し、ｖ（ｄｅｇ（φ）ｄｅｇ（ψ））＝０であり、したがって
【００９０】
【数３５】
【００９１】
は自明である。
【００９２】
ここで、図２に関して、次いで、図３に関して、カースルズ−テイトペアリングを選択データの暗号処理にどのように使用するかを説明する。
【００９３】
（データを暗号処理する例示的プロシージャ）
図２に、カースルズ−テイトペアリングを使用してデータを暗号処理する例示的プロシージャ２００を示す。プロシージャの動作を、図１のコンポーネントに関して説明する。コンポーネントの符号の左端の桁は、そのコンポーネントが初めて現れる特定の図面を識別する。
【００９４】
ブロック２０２で、署名／暗号化モジュール１１０が、コホモロジ群１２４および数体Ｋ上のアーベル多様体Ａからシャファレヴィッチ−テイト群１１４（図１）を生成する。ブロック２０４で、署名／暗号化モジュール１１０が、シャファレヴィッチ−テイト群１１４および秘密ｒに基づいてカースルズ−テイトペアリング（「その他のデータ」１３２を参照されたい）を判定する。この秘密ｒは、シャファレヴィッチ−テイト群１１４の要素ｘが、公開鍵ｒ＊ｘを得るためにそれ自体と合成された回数である。ブロック２０６で、選択された情報（たとえば、オリジナルデータ）を、判定されたカースルズ−テイトペアリングの関数として暗号処理する。たとえば、署名／暗号化モジュール１１０は、判定されたカースルズ−テイトペアリングの関数として、データを暗号化するか、またはデータに署名する。同様に、検証／暗号化解除モジュール１２０は、それぞれ、生成されたカースルズ−テイトペアリングの関数として、データを暗号化解除するか、または検証する。カースルズ−テイトペアリングを使用することによるデータへの署名および署名されたデータの検証の例示的プロシージャを、図３に関して以下で説明する。
【００９５】
データの処理（たとえば、署名または暗号化、同様に、検証または暗号化解除）のためにブロック２０６で選択される、特定のペアリングベースの暗号アルゴリズムは、任意であり、実装のために選択される特定のアルゴリズムの関数である。たとえば、一実施形態では、ブロック２０６の動作が、図４に関して以下で説明するアイデンティティベースの暗号化アルゴリズムを使用して、あるいはその代わりに、鍵発行に基づくアルゴリズム、署名（プレイン、ブラインド、プロキシ、リング、否定不能など）、暗号化、認証付き暗号化、またはブロードキャスト暗号化などを使用して、データを暗号処理する。もう１つの実施形態では、ブロック２０６で、キーアグリーメント、鍵配布、署名（たとえば、ショートシグネチャー、グループシグネチャーなど）などを使用して、データを暗号処理する。ほかの異なる実施形態では、ブロック２０６で、異なるペアリングベースの暗号アルゴリズムを使用して、データを暗号処理する。
【００９６】
（カースルズ−テイトペアリングを使用してデータに署名する例示的プロシージャ）
図３に、カースルズ−テイトペアリングを使用してデータに暗号署名する例示的プロシージャ３００を示す。データに署名するために選択される特定のペアリングベースの暗号アルゴリズムは、任意であり、実装のために選択される特定の暗号アーキテクチャの関数である。プロシージャ３００の動作を、図１のコンポーネントに関して説明する。コンポーネントの符号の左端の桁は、そのコンポーネントが初めて現れる特定の図面を識別する。
【００９７】
この例示的実施形態では、この実施形態では署名するモジュールであり、そう呼ばれる署名／暗号化モジュール１１０が、署名スキームを実施する。ブロック３０２で、署名モジュール１１０が、コホモロジ群１２４および数体Ｋ上のアーベル多様体Ａから、シャファレヴィッチ−テイト群１１４を生成する。ブロック３０４で、署名モジュール１１０が、Ａのシャファレヴィッチ−テイト群１１４内のIII（Ａ／Ｋ）内の要素ｘを選択し、公開する。ブロック３０６で、署名モジュール１１０が、（たとえば、整数乗算を介して）ＡからＡへの、ｍ次の、２つの同種写像φおよびψを生成する。同種写像の生成に使用できる複数の既知の技法がある。ブロック３０８で、署名モジュール１１０が、Ａψおよび
【００９８】
【数３６】
【００９９】
の核の生成作用素（generator）である、２つのランダムな点（random points）ＰおよびＰ’を入手する。ここで、
【０１００】
【数３７】
【０１０１】
は、双対写像（dual isogeny）
【０１０２】
【数３８】
【０１０３】
である。
【０１０４】
オリジナルデータの暗号化または署名、および／または関連する暗号化または署名されたデータ１１８の暗号化解除または検証、および／または共通の秘密の確立を望む、２人の当事者（たとえば、ＡｌｉｃｅおよびＢｏｂ）が、それぞれの公開鍵１２８を生成する。ブロック３１０で、それぞれの公開鍵１２８を生成することを望む当事者が、それぞれの秘密の乱数ｒを生成し、ｘを、シャファレヴィッチ−テイト群１１４内でｒ回それ自体と合成して、新しい要素（ｘのｒ番目の倍数、ｒ＊ｘ）を生成する。数ｒは、ユーザ（たとえば当事者Ａまたは当事者Ｂ）の秘密１３０である。秘密１３０は共有されない。ブロック３１２で、署名／暗号化モジュール１１０が、この新しい要素を公開鍵１２８として公開する。
【０１０５】
ブロック３１４で、署名モジュール１１０が、シャファレヴィッチ−テイト群１１４を使用してオリジナルデータに署名して、署名されたデータ１１８を生成する。たとえば、一実施形態では、署名モジュールが署名スキームを実施する場合に、署名モジュール１１０は、データ空間｛０，１｝ｎから
【０１０６】
【数３９】
【０１０７】
へのハッシュ関数ｈを使用して、オリジナルデータＭ（たとえば、平文メッセージ）に署名する。データ空間｛０，１｝ｎは、ある長さｎのビット列の集合である。同様に、データ空間｛０，１｝＊は、ある長さ＊のビット列の集合である。これは、Ｍのハッシュｈ（Ｍ）を、
【０１０８】
【数４０】
【０１０９】
の要素として計算し、次に、ｒ番目の乗算ｒ＊ｈ（Ｍ）をとって署名σ＝ｒ＊ｈ（Ｍ）を得ることによって達成される。例示のために、Ｍ’と表されるＭのハッシュ、カースルズ−テイトペアリング、および関連する署名σを、「その他のデータ」１３２のそれぞれの部分として図示した。
【０１１０】
ブロック３１６で、署名モジュール１１０は、ネットワーク化されたコンピューティングデバイス１０４上で実行されているアプリケーションなどの、ターゲットエンティティに、Ｍを署名σと共に送信する。このアプリケーションは、検証／暗号化解除モジュール１２０によって実装されるロジックを実施し、あるいは、そうでなければ、そのロジックにアクセスする。ブロック３１８で、Ｍおよび署名σの受信に応答して、この実施形態では検証モジュールである検証／暗号化解除モジュール１２０がＭをハッシュ化し、カースルズ−テイトペアリング１２２、ＣＴ（ｒ＊ｘ，ｈ（Ｍ））を計算し、これをＣＴ（ｘ，σ）と比較することによって、Ｍの署名の妥当性検査または検証を行う。これらが同一である場合には、メッセージ上の署名が有効とみなされる。
【０１１１】
（カースルズ−テイトペアリングの評価）
このセクションでは、ある事例において、ブロック３１８での検証／暗号化解除モジュール１２０の動作は、どのように、カースルズ−テイトペアリング１２２を明示的に計算することができるかを示す。この実施形態では、注意を、ペアリング１２２について明示的な式が提供される、特別な事例に集中する。例示的表記も提供する。
【０１１２】
１．アーベル多様体Ａが、数体Ｋで定義される楕円曲線Ｅであると仮定する。すると、Ｅは、そのデュアル
【０１１３】
【数４１】
【０１１４】
と同形（canonically isomorphic）である。
【０１１５】
２．Ｋ上で定義されたｐ次のＥの同種写像φが存在すると仮定する。ψが、双対写像（dual isogeny）
【０１１６】
【数４２】
【０１１７】
であるものとする。すると、
【０１１８】
【数４３】
【０１１９】
および
【０１２０】
【数４４】
【０１２１】
である。
【０１２２】
３．Ｅの全p−トーションがＫ上で定義されると仮定する。Ｐ∈Ｅ（Ｋ）が、ψの核についての生成作用素であるものとし、Ｐ’∈Ｅ（Ｋ）が、
【０１２３】
【数４５】
【０１２４】
の核の生成作用素であるものとする。
【０１２５】
４．写像ψ：Ｅｐ→Ｅφが、ガロア不変セクションｓ：Ｅφ→Ｅｐを有すると仮定する。
【０１２６】
５．ｓ’がデュアルセクションであるものとする。Ｑ：＝ｓ’Ｐ’であるものとする。
【０１２７】
固定されたφおよびψがあるので、これから、ローカルペアリングを単に＜，＞ｖと書く。
【０１２８】
（ヒルベルトノルム剰余記号に関する例示的なローカルペアリング）
φが、ｐ次のＥの同種写像であるものとする。上記のように、Ｐ∈Ｅ（Ｋ）が、
【０１２９】
【数４６】
【０１３０】
の核の生成作用素であるものとする。Ｄｐが、Ｐを表す、Ｋ上のＥの除数であるものとし、ｆＰ∈Ｋ（Ｅ）が、
（ｆＰ）＝ｐＤＰ
を満足する関数であるものとする。次の補助定理が得られる。
【０１３１】
補助定理３：Ｒ∈Ｅ（Ｋ）であるものとし、ＤＲが、（Ｒ）−（Ｏ）と同等で、ＤＰの支持集合を満足しない除数であるものとする。
【０１３２】
１．ｆＰ（φＤＲ）∈（Ｋ＊）ｐが得られる。
【０１３３】
２．ｇは、その除数ｄｉｖ ｇがＤＰからの互いに素な支持集合を有する関数であるものとする。ｆＰ（ｄｉｖ ｇ）∈（Ｋ＊）ｐが得られる。
【０１３４】
３．Ｄ’ＰがＫで定義され、ＤＰと線形に同等（linearly equivalent）であり、ｆ’Ｐ∈Ｅ（Ｋ）が、（ｆ’Ｐ）＝ｍＤ’Ｐになるものである場合に、あるｇ∈Ｋ（Ｅ）について、ｆＰ≡ｆ’Ｐｇｐ ｍｏｄ Ｋ＊である。
【０１３５】
証明．直前のステートメント２は、ベイユ相互作用（Weil reciprocity）からの当然の結果である。補助定理３から、写像ｆＰは、明確に定義された写像
ｌＰ：Ｅ（Ｋ）／φＥ（Ｋ）→Ｋ＊／（Ｋ＊）ｐ
を与える。これは、まさにテイトペアリングである。（３）から、この写像が、それを表すために選択された除数ではなく、Ｐだけに依存することがわかる。その一方で、ＰはＫ上の有理数なので、ガロア写像
Ｅφ→μｐ ａａ ｅφ（ａ，Ｐ）
が得られ、これから、写像
ｊＰ：Ｈ１（Ｋ，Ｅφ）→Ｈ１（Ｋ，μｐ）＝Ｋ＊／（Ｋ＊）ｐ
が誘導される。この等式は、クンマー理論から来る写像である。
【０１３６】
補助定理４：ｊＰｏｉφ＝ｉＰが得られる。ここで、ｉφは、コホモロジの短い正確なシーケンスからの写像ｉφ：Ｅ（Ｋ）／φＥ（Ｋ）→Ｈ１（Ｋ，Ｅφ）である。記号「ｏ」は、写像の合成を表す。Ｐ、Ｐ’、およびＱが上記と同一である、すなわち、Ｐがψの核の生成作用素であり、Ｐ’が
【０１３７】
【数４７】
【０１３８】
の核の生成作用素であり、Ｑ：＝ｓ’Ｐ’であり、ｓ’がデュアルセクションであるものとする。先に進む前に、次の２つの定義を検討されたい。
【０１３９】
・定義５．ヒルベルトノルム剰余記号（，）ｐは、写像
【０１４０】
【数４８】
【０１４１】
である。これは、
【０１４２】
【数４９】
【０１４３】
によって定義される。ここで、
【０１４４】
【数５０】
【０１４５】
は、ｙに写像されるＫ＊のすべての要素であり、
【０１４６】
【数５１】
【０１４７】
は、アルチン記号を表す。
【０１４８】
・定義６．ζ、ζ’∈μｐであるものとする。Ｉｎｄζ（ζ’）が、ζμｕ＝ζ’である一意の要素
【０１４９】
【数５２】
【０１５０】
であるものとする。次の命題を証明することができる。
【０１５１】
命題７：識別
【０１５２】
【数５３】
【０１５３】
および
【０１５４】
【数５４】
【０１５５】
の下で、ヒルベルトノルム剰余記号（，）ｐを、カップ積ペアリング
【０１５６】
【数５５】
【０１５７】
を用いて識別することができる。
【０１５８】
証明．これは、非特許文献５からの当然の結果である。次に、ローカルペアリングをヒルベルト記号に関係付ける、次の定理を証明することができる。
【０１５９】
定理８：ｘ，ｙ∈Ｅ（Ｋｖ）／φＥ（Ｋｖ）であるものとする。ｘ１がＥ（Ｋｖ）／ｐＥ（Ｋｖ）へのｘのリフトである場合に、
【０１６０】
【数５６】
【０１６１】
（１）である。証明．マッカラムの定理２．６を参照されたい。
【０１６２】
セルマー群Ｓφにおける要素の表現を、次に説明する。ｖが、ローカルペアリングが自明でない、上記のように区別された座であるものとする。各要素ζ∈Ｓφに、Ｔ：＝ｌｖ，φ（ζ）とすることによって、点Ｔ∈Ｅ（Ｋｖ）／φＥ（Ｋｖ）を関連付ける。ここで、ｌｖ，φは、ローカルペアリングとしてのカースルズ−テイトペアリングに関して説明したものと同様である。この要素Ｔ∈Ｅ（Ｑｐ）は、要素ζ∈Ｓφ（Ｅ／Ｋ）を一意に表す。
【０１６３】
Ｓ，Ｔ∈Ｋｖ＝Ｑｐのローカルペアリング＜Ｓ，Ｔ＞ｖの評価を、次に説明する。定理８によって、ローカルペアリング１２６を、２つのテイトペアリング１２２および１つのヒルベルト記号（「その他のデータ」１３２参照）の適用（application）として評価することができる。一実施形態では、除算を避けるために射影座標を使用し、デノミネータキャンセレーション（denominator cancellation）技法を使用して、テイトペアリングを評価する。
【０１６４】
（例示的なアイデンティティベースの暗号化）
図４に、アーベル多様体のシャファレヴィッチ−テイト群でのカースルズ−テイトペアリングを使用する、アイデンティティベースの暗号化システム１００の例示的プロシージャ４００を示す。プロシージャ４００の動作を、図１のコンポーネントに関して説明する。コンポーネントの符号の左端の桁は、そのコンポーネントが初めて現れる特定の図面を識別する。プロシージャ４００の動作は、次に基づく：ｘが、アーベル多様体のデュアルのシャファレヴィッチ−テイト群１１４の要素、おそらくは生成作用素であるものとし、ｒが、シャファレヴィッチ−テイト群の群位数より小さいランダムな整数であるものとする。
【０１６５】
ブロック４０２で、プログラムモジュール１０６、たとえば署名／暗号化モジュール１１０が、公開鍵にｒ＊ｘをセットする。例示的プロシージャ４００の実施形態では、モジュール１１０は、暗号化モジュールであり、このプロシージャに関してはそのように呼ばれる。整数ｒは、マスタ鍵である。ブロック４０４で、プログラムモジュール１０６が、データ空間｛０，１｝＊からシャファレヴィッチ−テイト群の非０要素への暗号ハッシュ関数ｈ１を選択する。ブロック４０６で、プログラムモジュール１０６が、カースルズ−テイトペアリング１１６のターゲット空間からデータ空間｛０，１｝＊への暗号ハッシュ関数ｈ２を選択する。
【０１６６】
ブロック４０８で、プログラムモジュール１０６が、データ空間｛０，１｝＊の２つのコピーからシャファレヴィッチ−テイト群１１４の群位数を法とする非０整数への第３の暗号ハッシュ関数ｈ３を選択する。ブロック４１０で、プログラムモジュール１０６が、データ空間｛０，１｝＊のコピーからそれ自体への第４の暗号ハッシュ関数ｈ４を選択する。ブロック４１２で、｛０，１｝＊内の所与のアイデンティティ文字列ＩＤに関して、システム１００のオーソリティ（たとえば、暗号化モジュール１１０などのプログラムモジュール１０６）が、アイデンティティ文字列をシャファレヴィッチ−テイト群１１４の要素にハッシュ化しｈ１（ＩＤ）、次に秘密鍵にｒ＊ｈ１（ＩＤ）をセットすることによって、対応する秘密鍵を生成する。例示のために、そのようなアイデンティティ文字列および秘密鍵を、「その他のデータ」１３２のそれぞれの部分に示す。
【０１６７】
ブロック４１４で、公開鍵ＩＤを使用してデータ空間｛０，１｝＊内のメッセージＭを暗号化するために、プログラムモジュール１０６が、シャファレヴィッチ−テイト群へのＩＤのハッシュｈ１（ＩＤ）を計算する。メッセージＭは、「その他のデータ」１３２のそれぞれの部分である。ブロック４１６で、プログラムモジュール１０６が、データ空間｛０，１｝＊内でランダム文字列ｓを選択する。ブロック４１８で、ａ＝ｈ３（ｓ，Ｍ）であるものとする。プログラムモジュール１０６が、Ｅ＝（ａ＊ｘ，ｓ＋ｈ２（ｃＩＤａ），Ｍ＋ｈ４（ｓ））に従うものとしてメッセージ１１８を暗号化する。ただし、ｃＩＤは、ｈ１（ＩＤ）とｒ＊ｘのカースルズ−テイトペアリング１１６であり、＋記号は、ビット列のＸＯＲ演算を表す。
【０１６８】
メッセージの暗号化解除は、次のように達成することができる。デクリプタ（decryptor）１２０は、アイデンティティ列ＩＤに関連する秘密鍵Ｄ＝ｒ＊ｈ１（ＩＤ）を所有する。デクリプタは、暗号文Ｅ＝（Ｆ，Ｇ，Ｈ）を受信する。デクリプタは、ｓ＝Ｇ＋ｈ２（ＣＴ（Ｄ，Ｆ））をセットする。次に、デクリプタは、メッセージＭにＭ＝Ｈ＋ｈ４（ｓ）をセットする。次に、デクリプタは、ａ＝ｈ３（ｓ，Ｍ）をセットし、受信した値Ｆがａ＊ｘと等しいかどうかをテストする。そうでない場合に、デクリプタは、メッセージを拒絶する。
【０１６９】
（例示的オペレーティング環境）
図５に、カースルズ−テイトペアリングに基づくデータの暗号処理を完全にまたは部分的に実施できる適切なコンピューティング環境の例を示す。例示的コンピューティング環境５００は、図１の例示的システムおよび図２〜４の例示的動作に適切なコンピューティング環境の一例にすぎず、本明細書に記載のシステムおよび方法の使用または機能性の範囲に関する制限を示唆することを意図したものではない。コンピューティング環境５００を、コンピューティング環境５００に示されたコンポーネントのいずれかまたはその組合せに関する依存性または要件を有するものと解釈してもならない。
【０１７０】
本明細書に記載の方法およびシステムは、多数の他の汎用または特殊目的のコンピューティングシステム、コンピューティング環境、またはコンピューティング構成と共に動作する。使用に適する可能性がある周知のコンピューティングシステム、コンピューティング環境、および／またはコンピューティング構成の例に、パーソナルコンピュータ、サーバコンピュータ、マルチプロセッサシステム、マイクロプロセッサベースのシステム、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記のシステムまたはデバイスのいずれかを含む分散コンピューティング環境などが含まれるが、これらに制限はされない。このフレームワークのコンパクト版またはサブセット版を、ハンドヘルドコンピュータまたは他のコンピューティングデバイスなどの限られたリソースのクライアントで実施することもできる。本発明は、通信ネットワークを介してリンクされたリモート処理デバイスによってタスクが実行される、分散コンピューティング環境で実践される。分散コンピューティング環境では、プログラムモジュールを、リモートメモリストレージデバイスとローカルメモリストレージデバイスの両方に置くことができる。
【０１７１】
図５を参照すると、カースルズ−テイトペアリングに基づいてデータを暗号処理する例示的システムは、たとえば図１のシステム１００を実施する、コンピュータ５１０の形の汎用コンピューティングデバイスを含む。コンピュータ５１０の次に説明される態様は、図１のコンピューティングデバイス１０２および／または１０４の例示的実施形態である。コンピュータ５１０のコンポーネントは、処理装置５２０、システムメモリ５３０、およびシステムメモリを含むさまざまなシステムコンポーネントを処理装置５２０に結合するシステムバス５２１を含むことができるが、これらには制限されない。システムバス５２１は、メモリバスまたはメモリコントローラ、周辺バス、およびさまざまなバスアーキテクチャのいずれかを使用するローカルバスを含む、複数のタイプのバス構造のいずれかとすることができる。限定ではなく例として、そのようなアーキテクチャには、ＩＳＡ（Industry Standard Architecture）バス、マイクロチャネルアーキテクチャ（ＭＣＡ）バス、ＥＩＳＡ（Enhanced ISA）バス、ＶＥＳＡ（Video Electronics Standards Association）ローカルバス、およびメザニンバスとも呼ばれるＰＣＩ（Peripheral Component Interconnect）バスを含めることができる。
【０１７２】
コンピュータ５１０は、通常、様々なコンピュータ読み取り可能記憶媒体を含む。コンピュータ読み取り可能記憶媒体は、コンピュータ５１０によってアクセスできるすべての使用可能な媒体とすることができ、揮発性および不揮発性の媒体、取り外し可能および取り外し不可能な媒体の両方が含まれる。限定ではなく例として、コンピュータ読み取り可能記憶媒体は、コンピュータ記憶媒体と通信媒体を含むことができる。コンピュータ記憶媒体は、コンピュータ読み取り可能命令、データ構造、プログラムモジュール、または他のデータなどの、情報の記憶に関する任意の方法または技術で実装される、揮発性および不揮発性、取り外し可能および取り外し不可能な媒体を含む。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、または他のメモリテクノロジ、ＣＤ−ＲＯＭ、ディジタル多用途ディスク（ＤＶＤ）、または他の光学ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージ、または他の磁気記憶装置、あるいは、所望の情報を格納するのに使用でき、コンピュータ５１０によってアクセスできる他のすべての媒体を含むが、これらに制限はされない。
【０１７３】
通信媒体は、通常は、搬送波または他のトランスポート機構などの被変調データ信号内で、コンピュータ読み取り可能命令、データ構造、プログラムモジュール、または他のデータを実施し、任意の情報配布媒体を含む。用語「被変調データ信号」は、信号内で情報を符号化する形でその特性の１つまたは複数を設定または変更された信号を意味する。限定ではなく例として、通信媒体は、有線ネットワークまたは直接配線接続などの有線媒体、音響、無線周波数（ＲＦ）、赤外線、および他の無線媒体などの無線媒体を含む。上記のいずれかの組み合わせも、コンピュータ読み取り可能記憶媒体の範囲に含まれるべきである。
【０１７４】
システムメモリ５３０は、読取専用メモリ（ＲＯＭ）５３１およびランダムアクセスメモリ（ＲＡＭ）５３２などの揮発性メモリおよび／または不揮発性メモリの形のコンピュータ記憶媒体を含む。起動中などにコンピュータ５１０内の要素間での情報の転送を助ける基本ルーチンを含む基本入出力システム５３３（ＢＩＯＳ）は、通常はＲＯＭ５３１に格納される。ＲＡＭ５３２は、通常は、処理装置５２０から即座にアクセス可能な、および／または処理装置５２０によって現在操作中のデータおよび／またはプログラムモジュールを含む。限定ではなく例として、図５に、オペレーティングシステム５３４、アプリケーションプログラム５３５、その他のプログラムモジュール５３６、およびプログラムデータ５３７を示す。
【０１７５】
コンピュータ５１０は、他の取り外し可能／取り外し不可能、揮発性／不揮発性のコンピュータ記憶媒体を含むことができる。ほんの一例として、図５に、取り外し不可能な不揮発性磁気媒体から読み取るか、またはこれに書き込むハードディスクドライブ５４１、取り外し可能な不揮発性磁気ディスク５５２から読み取るか、これに書き込む磁気ディスクドライブ５５１、ＣＤ−ＲＯＭまたは他の光媒体などの取り外し可能な不揮発性光ディスク５５６から読み取るか、これに書き込む光ディスクドライブ５５５を示す。例示的なオペレーティング環境で使用できる他の取り外し可能／取り外し不可能、揮発性／不揮発性のコンピュータ記憶媒体は、磁気テープカセット、フラッシュメモリカード、ディジタル多用途ディスク、ディジタルビデオテープ、ソリッドステートＲＡＭ、ソリッドステートＲＯＭなどを含むが、これに限定はされない。ハードディスクドライブ５４１は、通常は、インターフェース５４０などの取り外し不可能なメモリインターフェースを介してシステムバス５２１に接続され、磁気ディスクドライブ５５１および光ディスクドライブ５５５は、通常、インターフェース５５０などの取り外し可能なメモリインターフェースによってシステムバス５２１に接続される。
【０１７６】
上述し、図５に示したドライブおよびそれに関連するコンピュータ記憶媒体は、コンピュータ５１０のコンピュータ読み取り可能命令、データ構造、プログラムモジュール、および他のデータの記憶領域を提供する。図５では、たとえば、ハードドライブ５４１が、オペレーティングシステム５４４、アプリケーションプログラム５４５、その他のプログラムモジュール５４６、およびプログラムデータ５４７を格納するものとして図示されている。これらのコンポーネントを、オペレーティングシステム５３４、アプリケーションプログラム５３５、その他のプログラムモジュール５３６、およびプログラムデータ５３７と同一のまたは異なるもののいずれかとすることができることに留意されたい。アプリケーションプログラム５３５は、たとえば、図１のコンピューティングデバイス１０２または１０４のプログラムモジュールを含む。プログラムデータ５３７は、たとえば、図１のコンピューティングデバイス１０２または１０４のプログラムデータを含む。オペレーティングシステム５４４、アプリケーションプログラム５４５、その他のプログラムモジュール５４６、およびプログラムデータ５４７は、少なくとも異なるコピーであることを示すために、異なる符号を与えられている。
【０１７７】
ユーザは、キーボード５６２および、一般にマウス、トラックボール、またはタッチパッドと呼ばれるポインティングデバイス５６１などの入力デバイスを介して、コンピュータ５１０にコマンドおよび情報を入力することができる。他の入力デバイス（図示せず）には、マイクロホン、ジョイスティック、ゲームパッド、衛星パラボラアンテナ、スキャナなどを含むことができる。上記および他の入力デバイスは、しばしば、システムバス５２１に結合されたユーザ入力インターフェース５６０を介して処理装置５２０に接続されるが、パラレルポート、ゲームポート、またはＵＳＢ（universal serial bus）などの他のインターフェースおよびバス構造によって接続することができる。
【０１７８】
モニタ５９１または他のタイプのディスプレイデバイスも、ビデオインターフェース５９０などのインターフェースを介してシステムバス５２１に接続される。モニタのほかに、コンピュータは、プリンタ５９６およびオーディオデバイス５９７など、出力周辺インターフェース５９５を介して接続できる他の周辺出力デバイスも含むことができる。
【０１７９】
コンピュータ５１０は、リモートコンピュータ５８０などの１つまたは複数のリモートコンピュータへの論理接続を使用して、ネットワーク化された環境で動作する。一実施形態では、リモートコンピュータ５８０は、図１のコンピューティングデバイス１０２またはネットワーク化されたコンピュータ１０４を表す。リモートコンピュータ５８０は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、または他の一般的なネットワークノードとすることができ、その特定の実施形態の機能として、コンピュータ５１０に関して上述した要素の多くまたはすべてを含むことができるが、図５には、メモリストレージデバイス５８１だけを示した。図５に示された論理接続は、ローカルエリアネットワーク（ＬＡＮ）５７１および広域ネットワーク（ＷＡＮ）５７３を含むが、他のネットワークも含むことができる。そのようなネットワーキング環境は、オフィス、企業規模のコンピュータネットワーク、イントラネット、およびインターネットでは一般的なものである。
【０１８０】
ＬＡＮネットワーキング環境で使用される場合に、コンピュータ５１０は、ネットワークインターフェースまたはネットワークアダプタ５７０を介してＬＡＮ５７１に接続される。ＷＡＮネットワーキング環境で使用される場合に、コンピュータ５１０は、通常、インターネットなどのＷＡＮ５７３を介して通信を確立する、モデム５７２または他の手段を含む。モデム５７２は、内蔵または外付けとすることができるが、ユーザ入力インターフェース５６０または他の適当な手段を介して、システムバス５２１に接続することができる。ネットワーク化された環境では、コンピュータ５１０に関して図示されたプログラムモジュールまたはその一部を、リモートメモリストレージデバイスに格納することができる。限定ではなく例として、図５に、メモリデバイス５８１に常駐するものとしてリモートアプリケーションプログラム５８５を示す。図示のネットワーク接続は例示的であり、コンピュータ間の通信リンクを確立する他の手段を使用することができる。
【０１８１】
（結論）
暗号化におけるカースルズ−テイトペアリングのシステムおよび方法を、構造的特徴および／または方法論的動作もしくは行為に固有の言葉で説明したが、請求項で定義される実施形態は、必ずしも説明した特定の特徴または動作に限定されないことを理解されたい。たとえば、署名／暗号化モジュール１１０（図１）および検証／暗号化解除モジュール１２０（図１）は、異なるそれぞれのコンピューティングデバイス（すなわち、デバイス１０２および１０４）上に図示されているが、別の実施形態では、これらのプログラムモジュールに関するロジックを、単一のコンピューティングデバイス１０２で実施することができる。カースルズ−テイトペアリングのシステムおよび方法を、例示的な署名およびアイデンティティベースの実施形態で説明したが、ほかの例では、このシステムおよび方法を、上の段落番号０００９および００１０で示したものなどのシャファレヴィッチ−テイト群におけるペアリングベースのすべてのアプリケーションにも適用可能である。
【０１８２】
さらに別の代替実施形態では、公開要素ｘを、Ａのデュアルのシャファレヴィッチ−テイト群から選択することができ、メッセージＭを、Ａのシャファレヴィッチ−テイト群にハッシュ化することができる。同様に、アイデンティティベースの暗号化および他の応用例について、Ａの役割とＡのデュアルの役割を入れ替えることができる。
【０１８３】
したがって、システム１００の特定の特徴および動作は、請求される対象を実施する例示的な形として開示されたものである。
【図面の簡単な説明】
【０１８４】
【図１】カースルズ−テイトペアリングに基づいてデータを暗号処理する例示的システムを示す図である。
【図２】カースルズ−テイトペアリングに基づいてデータを暗号処理する例示的プロシージャを示す図である。
【図３】カースルズ−テイトペアリングを使用してデータにディジタル署名する例示的プロシージャを示す図である。
【図４】カースルズ−テイトペアリングを使用するアイデンティティベースの暗号化の例示的プロシージャを示す図である。
【図５】カースルズ−テイトペアリングに基づくデータの暗号処理を完全にまたは部分的に実施できる適切なコンピューティング環境の例を示す図である。
【技術分野】
【０００１】
本明細書のシステムおよび方法は、一般に、暗号処理に関し、より詳細には、カースルズ−テイトペアリングに基づくデータの暗号処理に関する。
【背景技術】
【０００２】
既存のペアリング（pairing）ベースの暗号システムは、楕円曲線またはアーベル多様体上の点で評価される、ベイユペアリングまたはテイトペアリングを使用する。固定された自然数ｍについて、ベイユペアリングｅｍは、楕円曲線上の２つのｍ−トーションポイント（m-torsion point）を入力として取り、ｍ番目の原始根を出力する双一次写像である。
【０００３】
【非特許文献１】C. Beaver, "5-torsion in the Shafarevich-Tate group of a family of elliptic curves", J. Number Theory, 82(1):25-46, 2000
【非特許文献２】William G. McCallum, "On the Shafarevich-Tate group of the Jacobian of a quotient of the Fermat curve", Invent. Math., 93(3):637-666, 1988 (I, Proposition 6.9)
【非特許文献３】Bjorn Poonen and Micheal Stoll, "The Cassels-Tate pairing on polarized abelian varieties", Ann. of Math. (2), 150(3): 1109-1149, 1999
【非特許文献４】McCallum (McC88 p.640)
【非特許文献５】Serre, Local Fields, Chapter XIV
【発明の開示】
【発明が解決しようとする課題】
【０００４】
カースルズ−テイトペアリングに基づいてデータを暗号処理するシステムおよび方法を提供する。
【課題を解決するための手段】
【０００５】
一態様では、シャファレヴィッチ−テイト群は、コホモロジ群から生成される。カースルズ−テイトペアリングは、シャファレヴィッチ−テイト群の要素の関数として決定される。次に、データは、カースルズ−テイトペアリングの関数として暗号処理される。
【０００６】
図面では、構成要素の符号の左端の桁が、その構成要素が初めて現れる特定の図面を識別する。
【発明を実施するための最良の形態】
【０００７】
（概要）
シャファレヴィッチ−テイト群におけるカースルズ−テイトペアリングに基づく、データの暗号処理のシステムおよび方法は、楕円曲線またはアーベル多様体において評価される、ベイユペアリングまたはテイトペアリングを使用するすべてのペアリングベースシステムに対する代替案を提供する。さらに、このシステムおよび方法は、シャファレヴィッチ−テイト群におけるすべてのペアリング応用（applications）において、応用分野（applications）を有する。
【０００８】
必須ではないが、カースルズ−テイトペアリングに基づくデータの暗号処理のシステムおよび方法を、パーソナルコンピュータなどのコンピューティングデバイスによって実行されるコンピュータ実行可能命令（プログラムモジュール）の一般的な文脈で説明する。プログラムモジュールは、一般に、特定のタスクを実行するか、または特定の抽象データ型を実施するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。本システムおよび方法を、前述の文脈で説明するが、以下に記載の行為および動作は、ハードウェアでも実施することができる。カースルズ−テイトペアリングに基づくデータの暗号処理のシステムおよび方法の上記および他の態様を、以下に詳細に説明する。
【０００９】
（例示的システム）
図１に、カースルズ−テイトペアリングに基づいてデータを暗号処理する例示的システム１００を示す。システム１００は、楕円曲線またはアーベル多様体において評価される、ベイユペアリングまたはテイトペアリングに基づくペアリングベースシステムに対する代替案を提供する。システム１００は、楕円曲線またはアーベル多様体のシャファレヴィッチ−テイト群上の点の群を、この群に対するカースルズ−テイトペアリングと組み合わせて使用する。システム１００は、多数の既知のペアリングベースの暗号プロトコルのいずれかを使用して、暗号システムでカースルズ−テイトペアリングの動作を実施することができる。たとえば、一実施形態で、システム１００は、署名（プレイン、ブラインド、プロキシ、リング、否定不能など）、暗号化、認証付き暗号化、ブロードキャスト暗号化、キーワード検索を用いる暗号化、バッチ署名、キーアグリーメント（プレイン、認証付き、グループなど）、トラストオーソリティおよび公開鍵認証、階層暗号システム、閾値暗号および署名、カメレオンハッシュおよび署名、認証、アプリケーションおよびシステム、または同種のものを対象とするものなどの、アイデンティティベースの暗号アルゴリズムに基づくプロトコルを実施する。
【００１０】
他の実施形態では、カースルズ−テイトペアリングに基づく暗号処理のシステム１００は、アクセス制御、キーアグリーメント、非対話型鍵配布、信任証（匿名、隠し、セルフ−ブラインダブル）、シークレットハンドシェイク、立証可能なセキュア署名、ショートシグネチャー、アグリゲート暗号化署名、リング暗号化署名、検証可能な暗号化署名、ブラインド署名、部分的なブラインド署名、プロキシ署名、否認不可署名、サインクリプション（signcryption）、多重署名、閾値署名、リミテッド−ベリファイア（limited-verifier）署名、デジグネイティッド−ベリファイア（designated-verifier）署名、閾値暗号システム、階層暗号システム、ロール−ベースの（role-based）暗号システム、カメレオンハッシュ、カメレオン署名、証明可能な確立関数、強力なインスレイティッド暗号化（strongly insulated encryption）、侵入攻撃に強い暗号化（intrusion-resilient encryption）、証明書なし公開鍵暗号方式（certificate-less PKC）、エーエル(al)、トレイタトレーシング（traitor tracing）、または同種のものに基づくプロトコルを実装する。
【００１１】
システム１００は、ネットワークを介して、ネットワーク化されたコンピューティングデバイス１０４に結合された、コンピューティングデバイス１０２を含む。コンピューティングデバイス１０２は、プログラムモジュール１０６およびプログラムデータ１０８を含む。プログラムモジュール１０６は、たとえば、（ａ）楕円曲線またはアーベル多様体のシャファレヴィッチ−テイト群１１４における点の群、および（ｂ）関連するカースルズ−テイトペアリング１１６を使用して、オリジナルデータ（「その他のデータ」１３２のそれぞれの部分）を暗号化するか、またはこれに署名する、署名／暗号化モジュール１１０を含む。例示のために、署名／暗号化モジュール１１０によってそれぞれ署名されたか、または暗号化されたオリジナルデータを、暗号化または署名されたデータ１１８としてコンピューティングデバイス１０２のプログラムデータ部分に示す。図１のネットワーク化されたコンピューティングデバイス１０４も、プログラムモジュールおよびプログラムデータを含む。たとえば、ネットワーク化されたコンピューティングデバイス１０４は、シャファレヴィッチ−テイト群１１４の要素の関数として、検証／暗号化解除モジュール１２０によって生成された、カースルズ−テイトペアリング１２２の関数として、暗号化または署名されたデータ１１８を暗号化解除または検証する、検証／暗号化解除モジュール１２０を含む。システム１００の上記および他の態様を、以下に詳細に説明する。
【００１２】
（シャファレヴィッチ−テイト群）
シャファレヴィッチ−テイト群１１４は、コホモロジ群１２４の部分群における要素などの、オブジェクトの集合である。シャファレヴィッチ−テイト群１１４は、シャファレヴィッチ−テイト群１１４における離散対数の困難さの関数として、システム１００にセキュリティを提供する。シャファレヴィッチ−テイト群１１４は、次のように定義される。Ｋが数体１２４である場合に、ＭＫによって、Ｋの同値でない付値（nonequivalent valuations）の集合を表す。Ｋｖによって、素数ｖによって導入される距離（metric）に関するＫの完備を表し、ｋｖによって、剰余体を表す。一般に、ｆ：Ｇ→Ｇ’が、群の射である場合に、その核（kernel）をＧｆによって表す。φ：Ａ→Ｂが、アーベル多様体の同種写像（isogeny）である場合に、Ａφによってφの核を表し、
【００１３】
【数１】
【００１４】
によって、双対写像（dual isogeny）
【００１５】
【数２】
【００１６】
を表す。体Ｋおよび滑らかな可換のＫ群スキームＧについて、群コホモロジＨｉ（Ｇａｌ（Ｋｓ／Ｋ），Ｇ（Ｋｓ））を表すのにＨｉ（Ｋ，Ｇ）と書き、Ｋｓは、Ｋの固定された離閉包である。
【００１７】
上記に鑑みて、アーベル多様体のシャファレヴィッチ−テイト群１１４を定義する。Ａが、数体Ｋ上のアーベル多様体であるものとする。以下で定義されるＡのシャファレヴィッチ−テイト群１１４は、あるtorsorについての局所−大域原理（local-to-global principle）の失敗を測定する。Ｋ上のＡのシャファレヴィッチ−テイト群１１４は、
【００１８】
【数３】
【００１９】
である。
【００２０】
（カースルズ−テイトペアリング）
Ａが、数体Ｋ上で定義されたアーベル多様体であるものとする。カースルズ−テイト（「ＣＴ」）ペアリング（たとえば、１１６または１２２）、ＣＴ（＊，＊）は、III（Ａ／Ｋ）の双一次非対称非退化ペアリング（割り切れる部分群を法とする（modulo））であり、
【００２１】
【数４】
【００２２】
はＱ／Ｚ内の値をとる。このＣＴペアリングは、ローカルペアリング（たとえば、ローカルペアリング１２６）の合計として書かれる。各ローカルペアリングは、ｍに関するテイトペアリング、ベイユペアリング、およびヒルベルト記号の評価の組合せによって評価される。Ａにおけるペアリングの特殊な事例、楕円曲線は、非特許文献１に記載のものなどの技法を使用して、より単純に評価することができる。
【００２３】
具体的に言うと、Ａが、デュアル（dual）
【００２４】
【数５】
【００２５】
を有する数体Ｋ上のアーベル多様体であるものとする。カースルズ−テイトペアリングＣＴ（＊，＊）は、
【００２６】
【数６】
【００２７】
であるペアリングであり、これは、割り切れる群を法とする非退化である。特殊な事例での定義を続ける（一般的な定義については、非特許文献２を参照されたい。他の同等の定義については、非特許文献３を参照されたい）。φ、ψが、Ｋ上のＡの同種写像であるものとする。カースルズ−テイトペアリングの制限は、φの核および
【００２８】
【数７】
【００２９】
に制限される。
【００３０】
正確なシーケンス
【００３１】
【数８】
【００３２】
および
【００３３】
【数９】
【００３４】
がある。＊が、グローバルコホモロジクラス、双対輪体、または双対体である場合に、対応するローカルオブジェクトについて＊ｖと書く。ａ∈III（Ａ／Ｋ）φであり、
【００３５】
【数１０】
【００３６】
であるものとする。ＣＴ（ａ，ａ’）を定義する。ａおよびａ’に写像されるＨ１（Ｋ，Ａφ）および
【００３７】
【数１１】
【００３８】
の要素ｂおよびｂ’を選択する。各ｖについて、ａは、Ｈ１（Ｋｖ，Ａ）で０に写像され、したがって、ｂｖを、Ａ（Ｋｖ）の像内の要素ｂｖ，１∈Ｈ１（Ｋｖ，Ａφψ）にリフトすることができる。ａが、Ｈ１（Ｋ，Ａ）に含まれるψによって割り切れ、たとえばａ＝ψａ１であると仮定し、ａ１に写像される要素ｂ１∈Ｈ１（Ｋ，Ａφψ）を選択する。すると、ｂｖ，１−ｂ１，ｖが、Ｈ１（Ｋｖ，Ａφψ）→Ｈ１（Ｋｖ，Ａφ）の下で０に写像され、したがって、これはＨ１（Ｋｖ，Ａψ）での要素ｃｖの像である。ＣＴ（ａ，ａ’）を、
【００３９】
【数１２】
【００４０】
になるように定義する。ここで、カップ積は、ベイユペアリング
【００４１】
【数１３】
【００４２】
によって誘導される。
【００４３】
ベイユペアリングによって誘導されるカップ積は、ベイユペアリングによって誘導されるコホモロジ上での写像との通常のカップ積の合成
【００４４】
【数１４】
【００４５】
を意味する。写像ｉｎｖｖは、正準写像Ｈ２（Ｋｖ，Ｇｍ）→Ｑ／Ｚである（ｉｎｖｖの像はｍ−１Ｚ／Ｚ内にある）。
【００４６】
カースルズ−テイトペアリング１２２は、ローカルペアリングの合計として記述される。具体的に言うと、ガロア加群（Galois modules）の写像
【００４７】
【数１５】
【００４８】
が、ガロア不変セクション（Galois invariant section）
【００４９】
【数１６】
【００５０】
を有すると仮定する。すると、ａ１＝ｓ＊ａとすることができる。次に、カースルズ−テイトペアリング１２２を、ローカルペアリングの合計として表す。III：＝III（Ａ／Ｋ）であり、
【００５１】
【数１７】
【００５２】
であるものとする。Ｓφが、セルマー群であるものとするが、これは、正確なシーケンス
０→Ａ（Ｋ）／φＡ（Ｋ）→Ｓφ→IIIφ→０
によって定義されるＨ１（Ｋ，Ａφ）の部分集合である。また、
【００５３】
【数１８】
【００５４】
が、
【００５５】
【数１９】
【００５６】
−セルマー群であるものとするが、これは、
【００５７】
【数２０】
【００５８】
の対応する正確なシーケンスによって定義される。ここで、カースルズ−テイトペアリングを
【００５９】
【数２１】
【００６０】
にリフトすることができる。次に、セルマー群でのペアリングを、ローカルペアリングの合計として記述する。この動機は、次の通りである。φ＝ψについてこれを適用する。IIIφを直接に計算する小さい可能性があるが、セルマー群Ｓφを計算できる。カースルズ−テイトペアリングのセルマー群
【００６１】
【数２２】
【００６２】
へのリフトは、Ａ（Ｋ）／φＡ（Ｋ）から来る要素について自明である。したがって、
【００６３】
【数２３】
【００６４】
におけるカースルズ−テイトペアリングが自明でない場合に、IIIにおける自明でないφ−トーションを有さなければならない。
【００６５】
IIIの定義により、
【００６６】
【数２４】
【００６７】
における第３垂直写像は、０である。したがって、写像ｌｖ，φ：Ｓφ→Ａ（Ｋｖ）／φＡ（Ｋｖ）が得られる。ｌｖ，φを使用して、セルマー群をローカル群Ａ（Ｋｖ）／φＡ（Ｋｖ）に写像する。ここで、ローカルペアリング
【００６８】
【数２５】
【００６９】
を定義することができ、ｂ∈Ｓφおよび
【００７０】
【数２６】
【００７１】
について、
【００７２】
【数２７】
【００７３】
が得られる。
【００７４】
（ローカルペアリングの定義）
ローカルペアリング（たとえば、ローカルペアリング１２６）
【００７５】
【数２８】
【００７６】
を定義するために、次の図式
【００７７】
【数２９】
【００７８】
を検討する。ｘ∈Ａ（Ｋｖ）／φＡ（Ｋｖ）であり、
【００７９】
【数３０】
【００８０】
であるものとする。ｘ１が、ｘのＡ（Ｋｖ）／φψＡ（Ｋｖ）へのリフトであるものとする。すると、ｉφψ（ｘ１）およびｓ＊ｉφ（ｘ）の両方が、Ｈ１（Ｋｖ，Ａφ）において同一の像を有する。したがって、（ｉφψ（ｘ１）−ｓ＊ｉφ（ｘ））は、要素ｃｖ∈Ｈ１（Ｋｖ，Ａψ）の像である。
【００８１】
【数３１】
【００８２】
を定義する。
【００８３】
ローカルペアリング
【００８４】
【数３２】
【００８５】
は、アーベル群の双一次ペアリングである。
【００８６】
【数３３】
【００８７】
上述のカースルズ−テイトペアリング１２２は、非特許文献４に記載されているように、ローカルペアリングの合計として表すことができ
【００８８】
【数３４】
【００８９】
であり、次の補助定理は、上記の合計を有限の合計に減らす（reduce）。ｖが複素アルキメデス的付値であるか、ｖがアルキメデス的でない場合に、Ａは、ｖの極大イデアルを法とする良還元（good reduction）を有し、ｖ（ｄｅｇ（φ）ｄｅｇ（ψ））＝０であり、したがって
【００９０】
【数３５】
【００９１】
は自明である。
【００９２】
ここで、図２に関して、次いで、図３に関して、カースルズ−テイトペアリングを選択データの暗号処理にどのように使用するかを説明する。
【００９３】
（データを暗号処理する例示的プロシージャ）
図２に、カースルズ−テイトペアリングを使用してデータを暗号処理する例示的プロシージャ２００を示す。プロシージャの動作を、図１のコンポーネントに関して説明する。コンポーネントの符号の左端の桁は、そのコンポーネントが初めて現れる特定の図面を識別する。
【００９４】
ブロック２０２で、署名／暗号化モジュール１１０が、コホモロジ群１２４および数体Ｋ上のアーベル多様体Ａからシャファレヴィッチ−テイト群１１４（図１）を生成する。ブロック２０４で、署名／暗号化モジュール１１０が、シャファレヴィッチ−テイト群１１４および秘密ｒに基づいてカースルズ−テイトペアリング（「その他のデータ」１３２を参照されたい）を判定する。この秘密ｒは、シャファレヴィッチ−テイト群１１４の要素ｘが、公開鍵ｒ＊ｘを得るためにそれ自体と合成された回数である。ブロック２０６で、選択された情報（たとえば、オリジナルデータ）を、判定されたカースルズ−テイトペアリングの関数として暗号処理する。たとえば、署名／暗号化モジュール１１０は、判定されたカースルズ−テイトペアリングの関数として、データを暗号化するか、またはデータに署名する。同様に、検証／暗号化解除モジュール１２０は、それぞれ、生成されたカースルズ−テイトペアリングの関数として、データを暗号化解除するか、または検証する。カースルズ−テイトペアリングを使用することによるデータへの署名および署名されたデータの検証の例示的プロシージャを、図３に関して以下で説明する。
【００９５】
データの処理（たとえば、署名または暗号化、同様に、検証または暗号化解除）のためにブロック２０６で選択される、特定のペアリングベースの暗号アルゴリズムは、任意であり、実装のために選択される特定のアルゴリズムの関数である。たとえば、一実施形態では、ブロック２０６の動作が、図４に関して以下で説明するアイデンティティベースの暗号化アルゴリズムを使用して、あるいはその代わりに、鍵発行に基づくアルゴリズム、署名（プレイン、ブラインド、プロキシ、リング、否定不能など）、暗号化、認証付き暗号化、またはブロードキャスト暗号化などを使用して、データを暗号処理する。もう１つの実施形態では、ブロック２０６で、キーアグリーメント、鍵配布、署名（たとえば、ショートシグネチャー、グループシグネチャーなど）などを使用して、データを暗号処理する。ほかの異なる実施形態では、ブロック２０６で、異なるペアリングベースの暗号アルゴリズムを使用して、データを暗号処理する。
【００９６】
（カースルズ−テイトペアリングを使用してデータに署名する例示的プロシージャ）
図３に、カースルズ−テイトペアリングを使用してデータに暗号署名する例示的プロシージャ３００を示す。データに署名するために選択される特定のペアリングベースの暗号アルゴリズムは、任意であり、実装のために選択される特定の暗号アーキテクチャの関数である。プロシージャ３００の動作を、図１のコンポーネントに関して説明する。コンポーネントの符号の左端の桁は、そのコンポーネントが初めて現れる特定の図面を識別する。
【００９７】
この例示的実施形態では、この実施形態では署名するモジュールであり、そう呼ばれる署名／暗号化モジュール１１０が、署名スキームを実施する。ブロック３０２で、署名モジュール１１０が、コホモロジ群１２４および数体Ｋ上のアーベル多様体Ａから、シャファレヴィッチ−テイト群１１４を生成する。ブロック３０４で、署名モジュール１１０が、Ａのシャファレヴィッチ−テイト群１１４内のIII（Ａ／Ｋ）内の要素ｘを選択し、公開する。ブロック３０６で、署名モジュール１１０が、（たとえば、整数乗算を介して）ＡからＡへの、ｍ次の、２つの同種写像φおよびψを生成する。同種写像の生成に使用できる複数の既知の技法がある。ブロック３０８で、署名モジュール１１０が、Ａψおよび
【００９８】
【数３６】
【００９９】
の核の生成作用素（generator）である、２つのランダムな点（random points）ＰおよびＰ’を入手する。ここで、
【０１００】
【数３７】
【０１０１】
は、双対写像（dual isogeny）
【０１０２】
【数３８】
【０１０３】
である。
【０１０４】
オリジナルデータの暗号化または署名、および／または関連する暗号化または署名されたデータ１１８の暗号化解除または検証、および／または共通の秘密の確立を望む、２人の当事者（たとえば、ＡｌｉｃｅおよびＢｏｂ）が、それぞれの公開鍵１２８を生成する。ブロック３１０で、それぞれの公開鍵１２８を生成することを望む当事者が、それぞれの秘密の乱数ｒを生成し、ｘを、シャファレヴィッチ−テイト群１１４内でｒ回それ自体と合成して、新しい要素（ｘのｒ番目の倍数、ｒ＊ｘ）を生成する。数ｒは、ユーザ（たとえば当事者Ａまたは当事者Ｂ）の秘密１３０である。秘密１３０は共有されない。ブロック３１２で、署名／暗号化モジュール１１０が、この新しい要素を公開鍵１２８として公開する。
【０１０５】
ブロック３１４で、署名モジュール１１０が、シャファレヴィッチ−テイト群１１４を使用してオリジナルデータに署名して、署名されたデータ１１８を生成する。たとえば、一実施形態では、署名モジュールが署名スキームを実施する場合に、署名モジュール１１０は、データ空間｛０，１｝ｎから
【０１０６】
【数３９】
【０１０７】
へのハッシュ関数ｈを使用して、オリジナルデータＭ（たとえば、平文メッセージ）に署名する。データ空間｛０，１｝ｎは、ある長さｎのビット列の集合である。同様に、データ空間｛０，１｝＊は、ある長さ＊のビット列の集合である。これは、Ｍのハッシュｈ（Ｍ）を、
【０１０８】
【数４０】
【０１０９】
の要素として計算し、次に、ｒ番目の乗算ｒ＊ｈ（Ｍ）をとって署名σ＝ｒ＊ｈ（Ｍ）を得ることによって達成される。例示のために、Ｍ’と表されるＭのハッシュ、カースルズ−テイトペアリング、および関連する署名σを、「その他のデータ」１３２のそれぞれの部分として図示した。
【０１１０】
ブロック３１６で、署名モジュール１１０は、ネットワーク化されたコンピューティングデバイス１０４上で実行されているアプリケーションなどの、ターゲットエンティティに、Ｍを署名σと共に送信する。このアプリケーションは、検証／暗号化解除モジュール１２０によって実装されるロジックを実施し、あるいは、そうでなければ、そのロジックにアクセスする。ブロック３１８で、Ｍおよび署名σの受信に応答して、この実施形態では検証モジュールである検証／暗号化解除モジュール１２０がＭをハッシュ化し、カースルズ−テイトペアリング１２２、ＣＴ（ｒ＊ｘ，ｈ（Ｍ））を計算し、これをＣＴ（ｘ，σ）と比較することによって、Ｍの署名の妥当性検査または検証を行う。これらが同一である場合には、メッセージ上の署名が有効とみなされる。
【０１１１】
（カースルズ−テイトペアリングの評価）
このセクションでは、ある事例において、ブロック３１８での検証／暗号化解除モジュール１２０の動作は、どのように、カースルズ−テイトペアリング１２２を明示的に計算することができるかを示す。この実施形態では、注意を、ペアリング１２２について明示的な式が提供される、特別な事例に集中する。例示的表記も提供する。
【０１１２】
１．アーベル多様体Ａが、数体Ｋで定義される楕円曲線Ｅであると仮定する。すると、Ｅは、そのデュアル
【０１１３】
【数４１】
【０１１４】
と同形（canonically isomorphic）である。
【０１１５】
２．Ｋ上で定義されたｐ次のＥの同種写像φが存在すると仮定する。ψが、双対写像（dual isogeny）
【０１１６】
【数４２】
【０１１７】
であるものとする。すると、
【０１１８】
【数４３】
【０１１９】
および
【０１２０】
【数４４】
【０１２１】
である。
【０１２２】
３．Ｅの全p−トーションがＫ上で定義されると仮定する。Ｐ∈Ｅ（Ｋ）が、ψの核についての生成作用素であるものとし、Ｐ’∈Ｅ（Ｋ）が、
【０１２３】
【数４５】
【０１２４】
の核の生成作用素であるものとする。
【０１２５】
４．写像ψ：Ｅｐ→Ｅφが、ガロア不変セクションｓ：Ｅφ→Ｅｐを有すると仮定する。
【０１２６】
５．ｓ’がデュアルセクションであるものとする。Ｑ：＝ｓ’Ｐ’であるものとする。
【０１２７】
固定されたφおよびψがあるので、これから、ローカルペアリングを単に＜，＞ｖと書く。
【０１２８】
（ヒルベルトノルム剰余記号に関する例示的なローカルペアリング）
φが、ｐ次のＥの同種写像であるものとする。上記のように、Ｐ∈Ｅ（Ｋ）が、
【０１２９】
【数４６】
【０１３０】
の核の生成作用素であるものとする。Ｄｐが、Ｐを表す、Ｋ上のＥの除数であるものとし、ｆＰ∈Ｋ（Ｅ）が、
（ｆＰ）＝ｐＤＰ
を満足する関数であるものとする。次の補助定理が得られる。
【０１３１】
補助定理３：Ｒ∈Ｅ（Ｋ）であるものとし、ＤＲが、（Ｒ）−（Ｏ）と同等で、ＤＰの支持集合を満足しない除数であるものとする。
【０１３２】
１．ｆＰ（φＤＲ）∈（Ｋ＊）ｐが得られる。
【０１３３】
２．ｇは、その除数ｄｉｖ ｇがＤＰからの互いに素な支持集合を有する関数であるものとする。ｆＰ（ｄｉｖ ｇ）∈（Ｋ＊）ｐが得られる。
【０１３４】
３．Ｄ’ＰがＫで定義され、ＤＰと線形に同等（linearly equivalent）であり、ｆ’Ｐ∈Ｅ（Ｋ）が、（ｆ’Ｐ）＝ｍＤ’Ｐになるものである場合に、あるｇ∈Ｋ（Ｅ）について、ｆＰ≡ｆ’Ｐｇｐ ｍｏｄ Ｋ＊である。
【０１３５】
証明．直前のステートメント２は、ベイユ相互作用（Weil reciprocity）からの当然の結果である。補助定理３から、写像ｆＰは、明確に定義された写像
ｌＰ：Ｅ（Ｋ）／φＥ（Ｋ）→Ｋ＊／（Ｋ＊）ｐ
を与える。これは、まさにテイトペアリングである。（３）から、この写像が、それを表すために選択された除数ではなく、Ｐだけに依存することがわかる。その一方で、ＰはＫ上の有理数なので、ガロア写像
Ｅφ→μｐ ａａ ｅφ（ａ，Ｐ）
が得られ、これから、写像
ｊＰ：Ｈ１（Ｋ，Ｅφ）→Ｈ１（Ｋ，μｐ）＝Ｋ＊／（Ｋ＊）ｐ
が誘導される。この等式は、クンマー理論から来る写像である。
【０１３６】
補助定理４：ｊＰｏｉφ＝ｉＰが得られる。ここで、ｉφは、コホモロジの短い正確なシーケンスからの写像ｉφ：Ｅ（Ｋ）／φＥ（Ｋ）→Ｈ１（Ｋ，Ｅφ）である。記号「ｏ」は、写像の合成を表す。Ｐ、Ｐ’、およびＱが上記と同一である、すなわち、Ｐがψの核の生成作用素であり、Ｐ’が
【０１３７】
【数４７】
【０１３８】
の核の生成作用素であり、Ｑ：＝ｓ’Ｐ’であり、ｓ’がデュアルセクションであるものとする。先に進む前に、次の２つの定義を検討されたい。
【０１３９】
・定義５．ヒルベルトノルム剰余記号（，）ｐは、写像
【０１４０】
【数４８】
【０１４１】
である。これは、
【０１４２】
【数４９】
【０１４３】
によって定義される。ここで、
【０１４４】
【数５０】
【０１４５】
は、ｙに写像されるＫ＊のすべての要素であり、
【０１４６】
【数５１】
【０１４７】
は、アルチン記号を表す。
【０１４８】
・定義６．ζ、ζ’∈μｐであるものとする。Ｉｎｄζ（ζ’）が、ζμｕ＝ζ’である一意の要素
【０１４９】
【数５２】
【０１５０】
であるものとする。次の命題を証明することができる。
【０１５１】
命題７：識別
【０１５２】
【数５３】
【０１５３】
および
【０１５４】
【数５４】
【０１５５】
の下で、ヒルベルトノルム剰余記号（，）ｐを、カップ積ペアリング
【０１５６】
【数５５】
【０１５７】
を用いて識別することができる。
【０１５８】
証明．これは、非特許文献５からの当然の結果である。次に、ローカルペアリングをヒルベルト記号に関係付ける、次の定理を証明することができる。
【０１５９】
定理８：ｘ，ｙ∈Ｅ（Ｋｖ）／φＥ（Ｋｖ）であるものとする。ｘ１がＥ（Ｋｖ）／ｐＥ（Ｋｖ）へのｘのリフトである場合に、
【０１６０】
【数５６】
【０１６１】
（１）である。証明．マッカラムの定理２．６を参照されたい。
【０１６２】
セルマー群Ｓφにおける要素の表現を、次に説明する。ｖが、ローカルペアリングが自明でない、上記のように区別された座であるものとする。各要素ζ∈Ｓφに、Ｔ：＝ｌｖ，φ（ζ）とすることによって、点Ｔ∈Ｅ（Ｋｖ）／φＥ（Ｋｖ）を関連付ける。ここで、ｌｖ，φは、ローカルペアリングとしてのカースルズ−テイトペアリングに関して説明したものと同様である。この要素Ｔ∈Ｅ（Ｑｐ）は、要素ζ∈Ｓφ（Ｅ／Ｋ）を一意に表す。
【０１６３】
Ｓ，Ｔ∈Ｋｖ＝Ｑｐのローカルペアリング＜Ｓ，Ｔ＞ｖの評価を、次に説明する。定理８によって、ローカルペアリング１２６を、２つのテイトペアリング１２２および１つのヒルベルト記号（「その他のデータ」１３２参照）の適用（application）として評価することができる。一実施形態では、除算を避けるために射影座標を使用し、デノミネータキャンセレーション（denominator cancellation）技法を使用して、テイトペアリングを評価する。
【０１６４】
（例示的なアイデンティティベースの暗号化）
図４に、アーベル多様体のシャファレヴィッチ−テイト群でのカースルズ−テイトペアリングを使用する、アイデンティティベースの暗号化システム１００の例示的プロシージャ４００を示す。プロシージャ４００の動作を、図１のコンポーネントに関して説明する。コンポーネントの符号の左端の桁は、そのコンポーネントが初めて現れる特定の図面を識別する。プロシージャ４００の動作は、次に基づく：ｘが、アーベル多様体のデュアルのシャファレヴィッチ−テイト群１１４の要素、おそらくは生成作用素であるものとし、ｒが、シャファレヴィッチ−テイト群の群位数より小さいランダムな整数であるものとする。
【０１６５】
ブロック４０２で、プログラムモジュール１０６、たとえば署名／暗号化モジュール１１０が、公開鍵にｒ＊ｘをセットする。例示的プロシージャ４００の実施形態では、モジュール１１０は、暗号化モジュールであり、このプロシージャに関してはそのように呼ばれる。整数ｒは、マスタ鍵である。ブロック４０４で、プログラムモジュール１０６が、データ空間｛０，１｝＊からシャファレヴィッチ−テイト群の非０要素への暗号ハッシュ関数ｈ１を選択する。ブロック４０６で、プログラムモジュール１０６が、カースルズ−テイトペアリング１１６のターゲット空間からデータ空間｛０，１｝＊への暗号ハッシュ関数ｈ２を選択する。
【０１６６】
ブロック４０８で、プログラムモジュール１０６が、データ空間｛０，１｝＊の２つのコピーからシャファレヴィッチ−テイト群１１４の群位数を法とする非０整数への第３の暗号ハッシュ関数ｈ３を選択する。ブロック４１０で、プログラムモジュール１０６が、データ空間｛０，１｝＊のコピーからそれ自体への第４の暗号ハッシュ関数ｈ４を選択する。ブロック４１２で、｛０，１｝＊内の所与のアイデンティティ文字列ＩＤに関して、システム１００のオーソリティ（たとえば、暗号化モジュール１１０などのプログラムモジュール１０６）が、アイデンティティ文字列をシャファレヴィッチ−テイト群１１４の要素にハッシュ化しｈ１（ＩＤ）、次に秘密鍵にｒ＊ｈ１（ＩＤ）をセットすることによって、対応する秘密鍵を生成する。例示のために、そのようなアイデンティティ文字列および秘密鍵を、「その他のデータ」１３２のそれぞれの部分に示す。
【０１６７】
ブロック４１４で、公開鍵ＩＤを使用してデータ空間｛０，１｝＊内のメッセージＭを暗号化するために、プログラムモジュール１０６が、シャファレヴィッチ−テイト群へのＩＤのハッシュｈ１（ＩＤ）を計算する。メッセージＭは、「その他のデータ」１３２のそれぞれの部分である。ブロック４１６で、プログラムモジュール１０６が、データ空間｛０，１｝＊内でランダム文字列ｓを選択する。ブロック４１８で、ａ＝ｈ３（ｓ，Ｍ）であるものとする。プログラムモジュール１０６が、Ｅ＝（ａ＊ｘ，ｓ＋ｈ２（ｃＩＤａ），Ｍ＋ｈ４（ｓ））に従うものとしてメッセージ１１８を暗号化する。ただし、ｃＩＤは、ｈ１（ＩＤ）とｒ＊ｘのカースルズ−テイトペアリング１１６であり、＋記号は、ビット列のＸＯＲ演算を表す。
【０１６８】
メッセージの暗号化解除は、次のように達成することができる。デクリプタ（decryptor）１２０は、アイデンティティ列ＩＤに関連する秘密鍵Ｄ＝ｒ＊ｈ１（ＩＤ）を所有する。デクリプタは、暗号文Ｅ＝（Ｆ，Ｇ，Ｈ）を受信する。デクリプタは、ｓ＝Ｇ＋ｈ２（ＣＴ（Ｄ，Ｆ））をセットする。次に、デクリプタは、メッセージＭにＭ＝Ｈ＋ｈ４（ｓ）をセットする。次に、デクリプタは、ａ＝ｈ３（ｓ，Ｍ）をセットし、受信した値Ｆがａ＊ｘと等しいかどうかをテストする。そうでない場合に、デクリプタは、メッセージを拒絶する。
【０１６９】
（例示的オペレーティング環境）
図５に、カースルズ−テイトペアリングに基づくデータの暗号処理を完全にまたは部分的に実施できる適切なコンピューティング環境の例を示す。例示的コンピューティング環境５００は、図１の例示的システムおよび図２〜４の例示的動作に適切なコンピューティング環境の一例にすぎず、本明細書に記載のシステムおよび方法の使用または機能性の範囲に関する制限を示唆することを意図したものではない。コンピューティング環境５００を、コンピューティング環境５００に示されたコンポーネントのいずれかまたはその組合せに関する依存性または要件を有するものと解釈してもならない。
【０１７０】
本明細書に記載の方法およびシステムは、多数の他の汎用または特殊目的のコンピューティングシステム、コンピューティング環境、またはコンピューティング構成と共に動作する。使用に適する可能性がある周知のコンピューティングシステム、コンピューティング環境、および／またはコンピューティング構成の例に、パーソナルコンピュータ、サーバコンピュータ、マルチプロセッサシステム、マイクロプロセッサベースのシステム、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記のシステムまたはデバイスのいずれかを含む分散コンピューティング環境などが含まれるが、これらに制限はされない。このフレームワークのコンパクト版またはサブセット版を、ハンドヘルドコンピュータまたは他のコンピューティングデバイスなどの限られたリソースのクライアントで実施することもできる。本発明は、通信ネットワークを介してリンクされたリモート処理デバイスによってタスクが実行される、分散コンピューティング環境で実践される。分散コンピューティング環境では、プログラムモジュールを、リモートメモリストレージデバイスとローカルメモリストレージデバイスの両方に置くことができる。
【０１７１】
図５を参照すると、カースルズ−テイトペアリングに基づいてデータを暗号処理する例示的システムは、たとえば図１のシステム１００を実施する、コンピュータ５１０の形の汎用コンピューティングデバイスを含む。コンピュータ５１０の次に説明される態様は、図１のコンピューティングデバイス１０２および／または１０４の例示的実施形態である。コンピュータ５１０のコンポーネントは、処理装置５２０、システムメモリ５３０、およびシステムメモリを含むさまざまなシステムコンポーネントを処理装置５２０に結合するシステムバス５２１を含むことができるが、これらには制限されない。システムバス５２１は、メモリバスまたはメモリコントローラ、周辺バス、およびさまざまなバスアーキテクチャのいずれかを使用するローカルバスを含む、複数のタイプのバス構造のいずれかとすることができる。限定ではなく例として、そのようなアーキテクチャには、ＩＳＡ（Industry Standard Architecture）バス、マイクロチャネルアーキテクチャ（ＭＣＡ）バス、ＥＩＳＡ（Enhanced ISA）バス、ＶＥＳＡ（Video Electronics Standards Association）ローカルバス、およびメザニンバスとも呼ばれるＰＣＩ（Peripheral Component Interconnect）バスを含めることができる。
【０１７２】
コンピュータ５１０は、通常、様々なコンピュータ読み取り可能記憶媒体を含む。コンピュータ読み取り可能記憶媒体は、コンピュータ５１０によってアクセスできるすべての使用可能な媒体とすることができ、揮発性および不揮発性の媒体、取り外し可能および取り外し不可能な媒体の両方が含まれる。限定ではなく例として、コンピュータ読み取り可能記憶媒体は、コンピュータ記憶媒体と通信媒体を含むことができる。コンピュータ記憶媒体は、コンピュータ読み取り可能命令、データ構造、プログラムモジュール、または他のデータなどの、情報の記憶に関する任意の方法または技術で実装される、揮発性および不揮発性、取り外し可能および取り外し不可能な媒体を含む。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、または他のメモリテクノロジ、ＣＤ−ＲＯＭ、ディジタル多用途ディスク（ＤＶＤ）、または他の光学ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージ、または他の磁気記憶装置、あるいは、所望の情報を格納するのに使用でき、コンピュータ５１０によってアクセスできる他のすべての媒体を含むが、これらに制限はされない。
【０１７３】
通信媒体は、通常は、搬送波または他のトランスポート機構などの被変調データ信号内で、コンピュータ読み取り可能命令、データ構造、プログラムモジュール、または他のデータを実施し、任意の情報配布媒体を含む。用語「被変調データ信号」は、信号内で情報を符号化する形でその特性の１つまたは複数を設定または変更された信号を意味する。限定ではなく例として、通信媒体は、有線ネットワークまたは直接配線接続などの有線媒体、音響、無線周波数（ＲＦ）、赤外線、および他の無線媒体などの無線媒体を含む。上記のいずれかの組み合わせも、コンピュータ読み取り可能記憶媒体の範囲に含まれるべきである。
【０１７４】
システムメモリ５３０は、読取専用メモリ（ＲＯＭ）５３１およびランダムアクセスメモリ（ＲＡＭ）５３２などの揮発性メモリおよび／または不揮発性メモリの形のコンピュータ記憶媒体を含む。起動中などにコンピュータ５１０内の要素間での情報の転送を助ける基本ルーチンを含む基本入出力システム５３３（ＢＩＯＳ）は、通常はＲＯＭ５３１に格納される。ＲＡＭ５３２は、通常は、処理装置５２０から即座にアクセス可能な、および／または処理装置５２０によって現在操作中のデータおよび／またはプログラムモジュールを含む。限定ではなく例として、図５に、オペレーティングシステム５３４、アプリケーションプログラム５３５、その他のプログラムモジュール５３６、およびプログラムデータ５３７を示す。
【０１７５】
コンピュータ５１０は、他の取り外し可能／取り外し不可能、揮発性／不揮発性のコンピュータ記憶媒体を含むことができる。ほんの一例として、図５に、取り外し不可能な不揮発性磁気媒体から読み取るか、またはこれに書き込むハードディスクドライブ５４１、取り外し可能な不揮発性磁気ディスク５５２から読み取るか、これに書き込む磁気ディスクドライブ５５１、ＣＤ−ＲＯＭまたは他の光媒体などの取り外し可能な不揮発性光ディスク５５６から読み取るか、これに書き込む光ディスクドライブ５５５を示す。例示的なオペレーティング環境で使用できる他の取り外し可能／取り外し不可能、揮発性／不揮発性のコンピュータ記憶媒体は、磁気テープカセット、フラッシュメモリカード、ディジタル多用途ディスク、ディジタルビデオテープ、ソリッドステートＲＡＭ、ソリッドステートＲＯＭなどを含むが、これに限定はされない。ハードディスクドライブ５４１は、通常は、インターフェース５４０などの取り外し不可能なメモリインターフェースを介してシステムバス５２１に接続され、磁気ディスクドライブ５５１および光ディスクドライブ５５５は、通常、インターフェース５５０などの取り外し可能なメモリインターフェースによってシステムバス５２１に接続される。
【０１７６】
上述し、図５に示したドライブおよびそれに関連するコンピュータ記憶媒体は、コンピュータ５１０のコンピュータ読み取り可能命令、データ構造、プログラムモジュール、および他のデータの記憶領域を提供する。図５では、たとえば、ハードドライブ５４１が、オペレーティングシステム５４４、アプリケーションプログラム５４５、その他のプログラムモジュール５４６、およびプログラムデータ５４７を格納するものとして図示されている。これらのコンポーネントを、オペレーティングシステム５３４、アプリケーションプログラム５３５、その他のプログラムモジュール５３６、およびプログラムデータ５３７と同一のまたは異なるもののいずれかとすることができることに留意されたい。アプリケーションプログラム５３５は、たとえば、図１のコンピューティングデバイス１０２または１０４のプログラムモジュールを含む。プログラムデータ５３７は、たとえば、図１のコンピューティングデバイス１０２または１０４のプログラムデータを含む。オペレーティングシステム５４４、アプリケーションプログラム５４５、その他のプログラムモジュール５４６、およびプログラムデータ５４７は、少なくとも異なるコピーであることを示すために、異なる符号を与えられている。
【０１７７】
ユーザは、キーボード５６２および、一般にマウス、トラックボール、またはタッチパッドと呼ばれるポインティングデバイス５６１などの入力デバイスを介して、コンピュータ５１０にコマンドおよび情報を入力することができる。他の入力デバイス（図示せず）には、マイクロホン、ジョイスティック、ゲームパッド、衛星パラボラアンテナ、スキャナなどを含むことができる。上記および他の入力デバイスは、しばしば、システムバス５２１に結合されたユーザ入力インターフェース５６０を介して処理装置５２０に接続されるが、パラレルポート、ゲームポート、またはＵＳＢ（universal serial bus）などの他のインターフェースおよびバス構造によって接続することができる。
【０１７８】
モニタ５９１または他のタイプのディスプレイデバイスも、ビデオインターフェース５９０などのインターフェースを介してシステムバス５２１に接続される。モニタのほかに、コンピュータは、プリンタ５９６およびオーディオデバイス５９７など、出力周辺インターフェース５９５を介して接続できる他の周辺出力デバイスも含むことができる。
【０１７９】
コンピュータ５１０は、リモートコンピュータ５８０などの１つまたは複数のリモートコンピュータへの論理接続を使用して、ネットワーク化された環境で動作する。一実施形態では、リモートコンピュータ５８０は、図１のコンピューティングデバイス１０２またはネットワーク化されたコンピュータ１０４を表す。リモートコンピュータ５８０は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、または他の一般的なネットワークノードとすることができ、その特定の実施形態の機能として、コンピュータ５１０に関して上述した要素の多くまたはすべてを含むことができるが、図５には、メモリストレージデバイス５８１だけを示した。図５に示された論理接続は、ローカルエリアネットワーク（ＬＡＮ）５７１および広域ネットワーク（ＷＡＮ）５７３を含むが、他のネットワークも含むことができる。そのようなネットワーキング環境は、オフィス、企業規模のコンピュータネットワーク、イントラネット、およびインターネットでは一般的なものである。
【０１８０】
ＬＡＮネットワーキング環境で使用される場合に、コンピュータ５１０は、ネットワークインターフェースまたはネットワークアダプタ５７０を介してＬＡＮ５７１に接続される。ＷＡＮネットワーキング環境で使用される場合に、コンピュータ５１０は、通常、インターネットなどのＷＡＮ５７３を介して通信を確立する、モデム５７２または他の手段を含む。モデム５７２は、内蔵または外付けとすることができるが、ユーザ入力インターフェース５６０または他の適当な手段を介して、システムバス５２１に接続することができる。ネットワーク化された環境では、コンピュータ５１０に関して図示されたプログラムモジュールまたはその一部を、リモートメモリストレージデバイスに格納することができる。限定ではなく例として、図５に、メモリデバイス５８１に常駐するものとしてリモートアプリケーションプログラム５８５を示す。図示のネットワーク接続は例示的であり、コンピュータ間の通信リンクを確立する他の手段を使用することができる。
【０１８１】
（結論）
暗号化におけるカースルズ−テイトペアリングのシステムおよび方法を、構造的特徴および／または方法論的動作もしくは行為に固有の言葉で説明したが、請求項で定義される実施形態は、必ずしも説明した特定の特徴または動作に限定されないことを理解されたい。たとえば、署名／暗号化モジュール１１０（図１）および検証／暗号化解除モジュール１２０（図１）は、異なるそれぞれのコンピューティングデバイス（すなわち、デバイス１０２および１０４）上に図示されているが、別の実施形態では、これらのプログラムモジュールに関するロジックを、単一のコンピューティングデバイス１０２で実施することができる。カースルズ−テイトペアリングのシステムおよび方法を、例示的な署名およびアイデンティティベースの実施形態で説明したが、ほかの例では、このシステムおよび方法を、上の段落番号０００９および００１０で示したものなどのシャファレヴィッチ−テイト群におけるペアリングベースのすべてのアプリケーションにも適用可能である。
【０１８２】
さらに別の代替実施形態では、公開要素ｘを、Ａのデュアルのシャファレヴィッチ−テイト群から選択することができ、メッセージＭを、Ａのシャファレヴィッチ−テイト群にハッシュ化することができる。同様に、アイデンティティベースの暗号化および他の応用例について、Ａの役割とＡのデュアルの役割を入れ替えることができる。
【０１８３】
したがって、システム１００の特定の特徴および動作は、請求される対象を実施する例示的な形として開示されたものである。
【図面の簡単な説明】
【０１８４】
【図１】カースルズ−テイトペアリングに基づいてデータを暗号処理する例示的システムを示す図である。
【図２】カースルズ−テイトペアリングに基づいてデータを暗号処理する例示的プロシージャを示す図である。
【図３】カースルズ−テイトペアリングを使用してデータにディジタル署名する例示的プロシージャを示す図である。
【図４】カースルズ−テイトペアリングを使用するアイデンティティベースの暗号化の例示的プロシージャを示す図である。
【図５】カースルズ−テイトペアリングに基づくデータの暗号処理を完全にまたは部分的に実施できる適切なコンピューティング環境の例を示す図である。
【特許請求の範囲】
【請求項１】
コホモロジ群からシャファレヴィッチ−テイト群を生成すること、
前記シャファレヴィッチ−テイト群の要素に基づいてカースルズ−テイトペアリングを判定すること、および、
前記カースルズ−テイトペアリングに基づいてデータを暗号処理すること
を含むことを特徴とする方法。
【請求項２】
前記コホモロジ群は、楕円曲線またはより高い示性数の曲線のヤコビ多様体から選択されたアーベル多様体に関連することを特徴とする請求項１に記載の方法。
【請求項３】
前記カースルズ−テイトペアリングは、ローカルペアリングの合計であることを特徴とする請求項１に記載の方法。
【請求項４】
前記暗号処理することは、署名ベースの検証スキームまたはアイデンティティベースの暗号化スキームであることを特徴とする請求項１に記載の方法。
【請求項５】
前記暗号処理することは、Ａのデュアルのシャファレヴィッチ−テイト群から公開要素ｘを選択し、メッセージＭは、Ａの前記シャファレヴィッチ−テイト群へハッシュ化されることを特徴とする請求項１に記載の方法。
【請求項６】
前記暗号処理することは、Ａのデュアルのシャファレヴィッチ−テイト群に基づき、Ａの役割およびＡの前記デュアルの役割は、入れ替えられることを特徴とする請求項１に記載の方法。
【請求項７】
暗号処理することは、データ空間｛０，１｝＊を操作するハッシング関数ｈを用いて前記データをハッシュ化することによって前記データに署名することをさらに含み、前記データは、
【数１】
へハッシュ化されることを特徴とする請求項１に記載の方法。
【請求項８】
暗号処理することは、
前記シャファレヴィッチ−テイト群から要素ｘを選択すること、
乱数ｒを選択すること、
公開鍵を生成するために前記要素ｘをそれ自体とｒ回合成すること
をさらに含み、
ｒは、秘密として維持されること
を特徴とする請求項１に記載の方法。
【請求項９】
暗号処理することは、
前記シャファレヴィッチ−テイト群から要素ｘを選択すること、
公開鍵を生成するために前記要素ｘをそれ自体とｒ回合成することであって、ｒは秘密であること、および、
前記データを独立のエンティティによって暗号化解除しまたは検証することができるようにするために、前記要素ｘ、前記公開鍵ｒ＊ｘ、および前記アーベル多様体を公開すること
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項１０】
前記カースルズ−テイトペアリングは、様々な入力に対して評価され、その値は比較され、
前記シャファレヴィッチ群の要素の関数として決定された秘密から生成された公開鍵を受信すること、および、
前記公開鍵および前記カースルズ−テイトペアリングの関数として前記データを暗号化解除し、または検証すること
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項１１】
署名σ＝ｒ＊ｈ（Ｍ）およびメッセージＭは送信され、
（ａ）前記データをハッシュ化すること、
（ｂ）第２のカースルズ−テイトペアリングＣＴ（ｒ＊ｘ，ｈ（Ｍ））を計算すること、および、
（ｃ）前記第２のカースルズ−テイトペアリングを第１のカースルズ−テイトペアリングＣＴ（ｘ，σ）と比較すること
によって前記データを検証することをさらに含むことを特徴とする請求項１に記載の方法。
【請求項１２】
暗号処理は、
ｈ（前記データ）が
【数２】
の要素になるように前記データのハッシュｈを計算すること、
ｒ番目の倍数ｒ＊ｈ（前記データ）を判定することであって、ｒは乱数であること、および、
署名σ＝ｒ＊ｈ（Ｍ）を得るために前記カースルズ−テイトペアリングを評価すること
によって前記データに署名することをさらに含むことを特徴とする請求項１に記載の方法。
【請求項１３】
コホモロジ群からシャファレヴィッチ−テイト群を生成すること、
前記シャファレヴィッチ−テイト群の要素に基づいてカースルズ−テイトペアリングを判定すること、および、
前記カースルズ−テイトペアリングに基づいてデータを暗号処理すること
を行うためにプロセッサによって実行可能なコンピュータプログラム命令を含むコンピュータ読み取り可能記憶媒体。
【請求項１４】
前記コホモロジ群は、楕円曲線またはより高い示性数の曲線のヤコビ多様体から選択されたアーベル多様体に関連することを特徴とする請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項１５】
前記カースルズ−テイトペアリングは、ローカルペアリングの合計であることを特徴とする請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項１６】
前記暗号処理することは、署名ベースの検証スキームまたはアイデンティティベースの暗号化スキームであることを特徴とする請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項１７】
暗号処理することについての前記コンピュータプログラム命令は、さらに、データ空間｛０，１｝＊を操作するハッシング関数ｈを用いて前記データをハッシュ化することによって前記データに署名する命令を含み、前記データは、
【数３】
にハッシュ化されることを特徴とする請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項１８】
暗号処理することについての前記コンピュータプログラム命令は、さらに、
前記シャファレヴィッチ−テイト群から要素ｘを選択する命令と、
乱数ｒを選択する命令と、
公開鍵を生成するために前記要素ｘをそれ自体とｒ回合成する命令と
を含み、
ｒは秘密として維持されること
を特徴とする請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項１９】
暗号処理することについての前記コンピュータプログラム命令は、さらに、
前記シャファレヴィッチ−テイト群から要素ｘを選択する命令と、
公開鍵を生成するために前記要素ｘをそれ自体とｒ回合成する命令であって、ｒは秘密であることと、
前記データを独立のエンティティによって暗号化解除しまたは検証することができるようにするために、前記要素ｘ、前記公開鍵ｒ＊ｘ、および前記アーベル多様体を公開する命令と
を含むことを特徴とする請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項２０】
前記カースルズ−テイトペアリングは、様々な入力に対して評価され、その値は、比較され、前記コンピュータプログラム命令は、
前記シャファレヴィッチ群の要素の関数として決定された秘密から生成された公開鍵を受信する命令と、
前記公開鍵および前記カースルズ−テイトペアリングの関数として前記データを暗号化解除し、または検証する命令と
をさらに含むことを特徴とする請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項２１】
署名σ＝ｒ＊ｈ（Ｍ）およびメッセージＭは、送信され、前記コンピュータプログラム命令は、
（ａ）前記データをハッシュ化すること、
（ｂ）第２のカースルズ−テイトペアリングＣＴ（ｒ＊ｘ，ｈ（Ｍ））を計算すること、および、
（ｃ）前記第２のカースルズ−テイトペアリングを第１のカースルズ−テイトペアリングＣＴ（ｘ，σ）と比較すること
によって前記データを検証する命令をさらに含むことを特徴とする請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項２２】
暗号処理することについての前記コンピュータプログラム命令は、さらに、
ｈ（前記データ）が
【数４】
の要素になるように前記データのハッシュｈを計算すること、
ｒ番目の倍数ｒ＊ｈ（前記データ）を判定することであって、ｒは乱数であること、および、
署名σ＝ｒ＊ｈ（Ｍ）を得るために前記カースルズ−テイトペアリングを評価すること
によって前記データに署名する命令をさらに含むことを特徴とする請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項２３】
プロセッサと、
メモリと
を含み、前記メモリは、
コホモロジ群からシャファレヴィッチ−テイト群を生成することと、
前記シャファレヴィッチ−テイト群の要素に基づいてカースルズ−テイトペアリングを判定することと、
前記カースルズ−テイトペアリングに基づいてデータを暗号処理することと
を行うために前記プロセッサによって実行可能なコンピュータプログラム命令を含むこと
を特徴とするコンピューティングデバイス。
【請求項２４】
前記コホモロジ群は、楕円曲線またはより高い示性数の曲線のヤコビ多様体から選択されたアーベル多様体に関連することを特徴とする請求項２３に記載のコンピューティングデバイス。
【請求項２５】
前記カースルズ−テイトペアリングは、ローカルペアリングの合計であることを特徴とする請求項２３に記載のコンピューティングデバイス。
【請求項２６】
前記暗号処理することは、署名ベースの検証スキームまたはアイデンティティベースの暗号化スキームであることを特徴とする請求項２３に記載のコンピューティングデバイス。
【請求項２７】
暗号処理することについての前記コンピュータプログラム命令は、さらに、データ空間｛０，１｝＊を操作するハッシング関数ｈを用いて前記データをハッシュ化することによって前記データに署名する命令を含み、前記データは、
【数５】
へハッシュ化されることを特徴とする請求項２３に記載のコンピューティングデバイス。
【請求項２８】
暗号処理することについての前記コンピュータプログラム命令は、さらに、
前記シャファレヴィッチ−テイト群から要素ｘを選択する命令と、
乱数ｒを選択する命令と、
公開鍵を生成するために前記要素ｘをそれ自体とｒ回合成する命令と
を含み、
ｒは秘密として維持されること
を特徴とする請求項２３に記載のコンピューティングデバイス。
【請求項２９】
暗号処理することについての前記コンピュータプログラム命令は、さらに、
前記シャファレヴィッチ−テイト群から要素ｘを選択する命令と、
公開鍵を生成するために前記要素ｘをそれ自体とｒ回合成する命令であって、ｒは秘密であることと、
前記データを独立のエンティティによって暗号化解除しまたは検証することができるようにするために、前記要素ｘ、前記公開鍵ｒ＊ｘ、および前記アーベル多様体を公開する命令と
を含むことを特徴とする請求項２３に記載のコンピューティングデバイス。
【請求項３０】
前記カースルズ−テイトペアリングは、様々な入力に対して評価され、その値は、比較され、前記コンピュータプログラム命令は、さらに、
前記シャファレヴィッチ群の要素の関数として決定された秘密から生成された公開鍵を受信する命令と、
前記公開鍵および前記カースルズ−テイトペアリングの関数として前記データを暗号化解除し、または検証する命令と
をさらに含むことを特徴とする請求項２３に記載のコンピューティングデバイス。
【請求項３１】
署名σ＝ｒ＊ｈ（Ｍ）およびメッセージＭは、送信され、前記コンピュータプログラム命令は、
（ａ）前記データをハッシュ化すること、
（ｂ）第２のカースルズ−テイトペアリングＣＴ（ｒ＊ｘ，ｈ（Ｍ））を計算すること、および、
（ｃ）前記第２のカースルズ−テイトペアリングを第１のカースルズ−テイトペアリングＣＴ（ｘ，σ）と比較すること
によって前記データを検証する命令をさらに含むことを特徴とする請求項２３に記載のコンピューティングデバイス。
【請求項３２】
暗号処理することについての前記コンピュータプログラム命令は、
ｈ（前記データ）が
【数６】
の要素になるように前記データのハッシュｈを計算すること、
ｒ番目の倍数ｒ＊ｈ（前記データ）を判定することであって、ｒは乱数であること、および、
署名σ＝ｒ＊ｈ（Ｍ）を得るために前記カースルズ−テイトペアリングを評価すること
によって前記データに署名する命令をさらに含むことを特徴とする請求項２３に記載のコンピューティングデバイス。
【請求項３３】
コホモロジ群からシャファレヴィッチ−テイト群を生成する生成手段と、
前記シャファレヴィッチ−テイト群の要素に基づいてカースルズ−テイトペアリングを判定する判定手段と、
前記カースルズ−テイトペアリングに基づいてデータを暗号処理する暗号処理手段と
を含むことを特徴とするコンピューティングデバイス。
【請求項１】
コホモロジ群からシャファレヴィッチ−テイト群を生成すること、
前記シャファレヴィッチ−テイト群の要素に基づいてカースルズ−テイトペアリングを判定すること、および、
前記カースルズ−テイトペアリングに基づいてデータを暗号処理すること
を含むことを特徴とする方法。
【請求項２】
前記コホモロジ群は、楕円曲線またはより高い示性数の曲線のヤコビ多様体から選択されたアーベル多様体に関連することを特徴とする請求項１に記載の方法。
【請求項３】
前記カースルズ−テイトペアリングは、ローカルペアリングの合計であることを特徴とする請求項１に記載の方法。
【請求項４】
前記暗号処理することは、署名ベースの検証スキームまたはアイデンティティベースの暗号化スキームであることを特徴とする請求項１に記載の方法。
【請求項５】
前記暗号処理することは、Ａのデュアルのシャファレヴィッチ−テイト群から公開要素ｘを選択し、メッセージＭは、Ａの前記シャファレヴィッチ−テイト群へハッシュ化されることを特徴とする請求項１に記載の方法。
【請求項６】
前記暗号処理することは、Ａのデュアルのシャファレヴィッチ−テイト群に基づき、Ａの役割およびＡの前記デュアルの役割は、入れ替えられることを特徴とする請求項１に記載の方法。
【請求項７】
暗号処理することは、データ空間｛０，１｝＊を操作するハッシング関数ｈを用いて前記データをハッシュ化することによって前記データに署名することをさらに含み、前記データは、
【数１】
へハッシュ化されることを特徴とする請求項１に記載の方法。
【請求項８】
暗号処理することは、
前記シャファレヴィッチ−テイト群から要素ｘを選択すること、
乱数ｒを選択すること、
公開鍵を生成するために前記要素ｘをそれ自体とｒ回合成すること
をさらに含み、
ｒは、秘密として維持されること
を特徴とする請求項１に記載の方法。
【請求項９】
暗号処理することは、
前記シャファレヴィッチ−テイト群から要素ｘを選択すること、
公開鍵を生成するために前記要素ｘをそれ自体とｒ回合成することであって、ｒは秘密であること、および、
前記データを独立のエンティティによって暗号化解除しまたは検証することができるようにするために、前記要素ｘ、前記公開鍵ｒ＊ｘ、および前記アーベル多様体を公開すること
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項１０】
前記カースルズ−テイトペアリングは、様々な入力に対して評価され、その値は比較され、
前記シャファレヴィッチ群の要素の関数として決定された秘密から生成された公開鍵を受信すること、および、
前記公開鍵および前記カースルズ−テイトペアリングの関数として前記データを暗号化解除し、または検証すること
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項１１】
署名σ＝ｒ＊ｈ（Ｍ）およびメッセージＭは送信され、
（ａ）前記データをハッシュ化すること、
（ｂ）第２のカースルズ−テイトペアリングＣＴ（ｒ＊ｘ，ｈ（Ｍ））を計算すること、および、
（ｃ）前記第２のカースルズ−テイトペアリングを第１のカースルズ−テイトペアリングＣＴ（ｘ，σ）と比較すること
によって前記データを検証することをさらに含むことを特徴とする請求項１に記載の方法。
【請求項１２】
暗号処理は、
ｈ（前記データ）が
【数２】
の要素になるように前記データのハッシュｈを計算すること、
ｒ番目の倍数ｒ＊ｈ（前記データ）を判定することであって、ｒは乱数であること、および、
署名σ＝ｒ＊ｈ（Ｍ）を得るために前記カースルズ−テイトペアリングを評価すること
によって前記データに署名することをさらに含むことを特徴とする請求項１に記載の方法。
【請求項１３】
コホモロジ群からシャファレヴィッチ−テイト群を生成すること、
前記シャファレヴィッチ−テイト群の要素に基づいてカースルズ−テイトペアリングを判定すること、および、
前記カースルズ−テイトペアリングに基づいてデータを暗号処理すること
を行うためにプロセッサによって実行可能なコンピュータプログラム命令を含むコンピュータ読み取り可能記憶媒体。
【請求項１４】
前記コホモロジ群は、楕円曲線またはより高い示性数の曲線のヤコビ多様体から選択されたアーベル多様体に関連することを特徴とする請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項１５】
前記カースルズ−テイトペアリングは、ローカルペアリングの合計であることを特徴とする請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項１６】
前記暗号処理することは、署名ベースの検証スキームまたはアイデンティティベースの暗号化スキームであることを特徴とする請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項１７】
暗号処理することについての前記コンピュータプログラム命令は、さらに、データ空間｛０，１｝＊を操作するハッシング関数ｈを用いて前記データをハッシュ化することによって前記データに署名する命令を含み、前記データは、
【数３】
にハッシュ化されることを特徴とする請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項１８】
暗号処理することについての前記コンピュータプログラム命令は、さらに、
前記シャファレヴィッチ−テイト群から要素ｘを選択する命令と、
乱数ｒを選択する命令と、
公開鍵を生成するために前記要素ｘをそれ自体とｒ回合成する命令と
を含み、
ｒは秘密として維持されること
を特徴とする請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項１９】
暗号処理することについての前記コンピュータプログラム命令は、さらに、
前記シャファレヴィッチ−テイト群から要素ｘを選択する命令と、
公開鍵を生成するために前記要素ｘをそれ自体とｒ回合成する命令であって、ｒは秘密であることと、
前記データを独立のエンティティによって暗号化解除しまたは検証することができるようにするために、前記要素ｘ、前記公開鍵ｒ＊ｘ、および前記アーベル多様体を公開する命令と
を含むことを特徴とする請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項２０】
前記カースルズ−テイトペアリングは、様々な入力に対して評価され、その値は、比較され、前記コンピュータプログラム命令は、
前記シャファレヴィッチ群の要素の関数として決定された秘密から生成された公開鍵を受信する命令と、
前記公開鍵および前記カースルズ−テイトペアリングの関数として前記データを暗号化解除し、または検証する命令と
をさらに含むことを特徴とする請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項２１】
署名σ＝ｒ＊ｈ（Ｍ）およびメッセージＭは、送信され、前記コンピュータプログラム命令は、
（ａ）前記データをハッシュ化すること、
（ｂ）第２のカースルズ−テイトペアリングＣＴ（ｒ＊ｘ，ｈ（Ｍ））を計算すること、および、
（ｃ）前記第２のカースルズ−テイトペアリングを第１のカースルズ−テイトペアリングＣＴ（ｘ，σ）と比較すること
によって前記データを検証する命令をさらに含むことを特徴とする請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項２２】
暗号処理することについての前記コンピュータプログラム命令は、さらに、
ｈ（前記データ）が
【数４】
の要素になるように前記データのハッシュｈを計算すること、
ｒ番目の倍数ｒ＊ｈ（前記データ）を判定することであって、ｒは乱数であること、および、
署名σ＝ｒ＊ｈ（Ｍ）を得るために前記カースルズ−テイトペアリングを評価すること
によって前記データに署名する命令をさらに含むことを特徴とする請求項１３に記載のコンピュータ読み取り可能記憶媒体。
【請求項２３】
プロセッサと、
メモリと
を含み、前記メモリは、
コホモロジ群からシャファレヴィッチ−テイト群を生成することと、
前記シャファレヴィッチ−テイト群の要素に基づいてカースルズ−テイトペアリングを判定することと、
前記カースルズ−テイトペアリングに基づいてデータを暗号処理することと
を行うために前記プロセッサによって実行可能なコンピュータプログラム命令を含むこと
を特徴とするコンピューティングデバイス。
【請求項２４】
前記コホモロジ群は、楕円曲線またはより高い示性数の曲線のヤコビ多様体から選択されたアーベル多様体に関連することを特徴とする請求項２３に記載のコンピューティングデバイス。
【請求項２５】
前記カースルズ−テイトペアリングは、ローカルペアリングの合計であることを特徴とする請求項２３に記載のコンピューティングデバイス。
【請求項２６】
前記暗号処理することは、署名ベースの検証スキームまたはアイデンティティベースの暗号化スキームであることを特徴とする請求項２３に記載のコンピューティングデバイス。
【請求項２７】
暗号処理することについての前記コンピュータプログラム命令は、さらに、データ空間｛０，１｝＊を操作するハッシング関数ｈを用いて前記データをハッシュ化することによって前記データに署名する命令を含み、前記データは、
【数５】
へハッシュ化されることを特徴とする請求項２３に記載のコンピューティングデバイス。
【請求項２８】
暗号処理することについての前記コンピュータプログラム命令は、さらに、
前記シャファレヴィッチ−テイト群から要素ｘを選択する命令と、
乱数ｒを選択する命令と、
公開鍵を生成するために前記要素ｘをそれ自体とｒ回合成する命令と
を含み、
ｒは秘密として維持されること
を特徴とする請求項２３に記載のコンピューティングデバイス。
【請求項２９】
暗号処理することについての前記コンピュータプログラム命令は、さらに、
前記シャファレヴィッチ−テイト群から要素ｘを選択する命令と、
公開鍵を生成するために前記要素ｘをそれ自体とｒ回合成する命令であって、ｒは秘密であることと、
前記データを独立のエンティティによって暗号化解除しまたは検証することができるようにするために、前記要素ｘ、前記公開鍵ｒ＊ｘ、および前記アーベル多様体を公開する命令と
を含むことを特徴とする請求項２３に記載のコンピューティングデバイス。
【請求項３０】
前記カースルズ−テイトペアリングは、様々な入力に対して評価され、その値は、比較され、前記コンピュータプログラム命令は、さらに、
前記シャファレヴィッチ群の要素の関数として決定された秘密から生成された公開鍵を受信する命令と、
前記公開鍵および前記カースルズ−テイトペアリングの関数として前記データを暗号化解除し、または検証する命令と
をさらに含むことを特徴とする請求項２３に記載のコンピューティングデバイス。
【請求項３１】
署名σ＝ｒ＊ｈ（Ｍ）およびメッセージＭは、送信され、前記コンピュータプログラム命令は、
（ａ）前記データをハッシュ化すること、
（ｂ）第２のカースルズ−テイトペアリングＣＴ（ｒ＊ｘ，ｈ（Ｍ））を計算すること、および、
（ｃ）前記第２のカースルズ−テイトペアリングを第１のカースルズ−テイトペアリングＣＴ（ｘ，σ）と比較すること
によって前記データを検証する命令をさらに含むことを特徴とする請求項２３に記載のコンピューティングデバイス。
【請求項３２】
暗号処理することについての前記コンピュータプログラム命令は、
ｈ（前記データ）が
【数６】
の要素になるように前記データのハッシュｈを計算すること、
ｒ番目の倍数ｒ＊ｈ（前記データ）を判定することであって、ｒは乱数であること、および、
署名σ＝ｒ＊ｈ（Ｍ）を得るために前記カースルズ−テイトペアリングを評価すること
によって前記データに署名する命令をさらに含むことを特徴とする請求項２３に記載のコンピューティングデバイス。
【請求項３３】
コホモロジ群からシャファレヴィッチ−テイト群を生成する生成手段と、
前記シャファレヴィッチ−テイト群の要素に基づいてカースルズ−テイトペアリングを判定する判定手段と、
前記カースルズ−テイトペアリングに基づいてデータを暗号処理する暗号処理手段と
を含むことを特徴とするコンピューティングデバイス。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２００６−１７１７１１（Ｐ２００６−１７１７１１Ａ）
【公開日】平成１８年６月２９日（２００６．６．２９）
【国際特許分類】
【出願番号】特願２００５−３２４９３３（Ｐ２００５−３２４９３３）
【出願日】平成１７年１１月９日（２００５．１１．９）
【出願人】（５０００４６４３８）マイクロソフト コーポレーション (3,165)
【Ｆターム（参考）】
【公開日】平成１８年６月２９日（２００６．６．２９）
【国際特許分類】
【出願日】平成１７年１１月９日（２００５．１１．９）
【出願人】（５０００４６４３８）マイクロソフト コーポレーション (3,165)
【Ｆターム（参考）】
[ Back to top ]