JP4635009B2 - 通信における証明された秘密値の使用 - Google Patents

Description

［発明の分野］
本発明は、証明された秘密値を提供すること（および取り消すこと）ならびにこのような秘密値を使用する通信に関し、より詳細には、或る関係者が特定の方法で形成された秘密値を所有することを、当該秘密値自体を明らかにすることなく示すことができる通信に関する。本発明は、特に、（例えば、信頼できるコンピューティンググループによって説明されたタイプの）信頼できるコンピューティングに関係する。この信頼できるコンピューティングでは、或る関係者は、第２の関係者が予測されたように振る舞うという或る保証を有する。

［従来技術の説明］
最近の進展は、「信頼できる（trusted）」コンピューティング装置が提供されているということである。すなわち、ユーザは、予測できるように振る舞うこと、および、別のユーザによる破壊が少なくとも明らかになることに対して信頼を置くことができる。信頼できるコンピューティンググループの仕様（www.trustedcomputing.orgで入手される）、および、Siani Pearsonによって編集されてPrentice Hall PTRによって２００２年７月に出版された、関連した書物「Trusted Computing Platforms: TCPA Technology in Context」（これらの内容は、法律の許す範囲で、参照により本明細書に援用される）には、信頼できるコンピューティングの手法が記載されている。この記載された信頼できるコンピューティングの手法は、信頼できるコプロセッサ（破壊から物理的および論理的の双方で保護される）を使用して、信頼できるコプロセッサを含むコンピューティング装置のユーザまたは信頼できるコプロセッサに関連したコンピューティング装置のユーザに、その装置が予測でき、かつ、破壊されないように動作していることを保証するものである。特に有益な構成は、特に、他のコンピュータの情報およびサービスを提供することが望ましい場合に、（通常、プロセスが、他のコンピューティング環境との厳密に制御された相互作用を有する分離されたコンピューティング環境で実行されるような区画された方法で動作することによる）区画されたオペレーティングシステムと、信頼できるコンポーネントを使用する信頼できるコンピューティングハードウェアとの双方を使用することである（このような構成は、例えば、ＥＰ１１８２５５７として公開された出願人の特許出願に説明されている）。

信頼できるプラットフォームを使用することの１つの利点は、その信頼できるプラットフォームが予測されたように振る舞うことを確信する手段を他の関係者が有するので、それら他の関係者が、その信頼できるプラットフォームと相互作用する準備ができるということである。このような他の関係者は、リモートサービスプロバイダ（ＲＳＰ（Remote Service Provider））とすることができる。ＲＳＰは、プラットフォームにサービスを提供できるが、サービスを受け取るプラットフォームが本当に信頼できることを確信できない場合に、このサービスの提供を好まない場合がある。ＲＳＰは、信頼できるコンポーネント（信頼できるコンポーネントは、本明細書では信頼できるプラットフォームモジュールまたはＴＰＭ（Trusted Platform Module）と記載される）の少なくともいくつかの製造業者を信頼するものと仮定することができる。これには、ＲＳＰと相互作用するＴＰＭが信頼できる製造業者によって本当に生産されたということを当該ＲＳＰが確信することに問題が残る。さらなる検討が行われる。プライバシーの理由から、ＲＳＰは、自身がどのＴＰＭと相互作用しているかを見分けることができないことが望ましい（すなわち、望ましくは、ＲＳＰが立証できることは、自身が既知でかつ信頼できる製造業者によって製造された真正のＴＰＭと相互作用しているということだけである）。

このような確信をＲＳＰに提供する現在の手法は、別の第３の関係者である認証局（ＣＡ（Certificate Authority））を使用することである。ＣＡは、プラットフォームの所有者およびＲＳＰの双方に信頼されている。ＴＰＭ製造業者は、当該ＴＰＭの一意の保証鍵（endorsement key）を提供し、次に、それを証明する。ＣＡは、次に、製造業者の証明書を検証した後、ランダムに選ばれた識別情報に関する証明書を発行する。ＣＡは、保証鍵と、対応する証明書との間のマッピングのリストを保持してもよいし、保持しなくてもよい。この証明書は、ＴＰＭの正当性をチェックするためにＲＳＰによって使用されるＣＡの証明書である。証明書が検証されると、ＲＳＰは、ＣＡを信頼するので、ＴＰＭが信頼できる製造業者の適法な製品であると信頼する。ＲＳＰは、証明された特定の識別情報に誤ったものを見出すと、これをＣＡに報告し、ＣＡは、問題の識別情報を取り消しリストに列挙し、次に、このＴＰＭに対する新たなどの識別情報の証明も拒否する。

この方式の問題は、ＣＡが現在のところシステムの弱点であるということである。ＣＡは、ＴＰＭの保証鍵とそのＴＰＭに発行された識別情報との間のマッピング（および、おそらく多数のＴＰＭのマッピング）を所有する可能性がある。ＣＡが、このようなマッピングを保持しない約束を破った場合、または、このようなマッピングが秘密にされる限り、このようなマッピングを保持するようにＣＡが許可されるが、ＣＡのデータベースが危険にさらされた場合、そのＣＡによって証明されたすべてのＴＰＭの識別情報を相関させることが可能になる。

したがって、ＴＰＭは、ＣＡ等の第３の関係者を信頼することなく、製造業者によって当該ＴＰＭに与えられた証明情報で、自身が、信頼できる製造業者の適法な製品であることをＲＳＰに確信させることができるのが望ましい。また、これは、ＲＳＰが任意の所与の時刻において相互作用しているＴＰＭに製造業者により与えられた証明情報に当該ＲＳＰが気付くことを可能にすることなく、ＴＰＭのステータスを取り消すことができるように行われることも望ましい。

これらの問題は、信頼できるコンピューティングプラットフォームに関して本明細書で特定された具体的な問題よりも広い、関係者間の通信への利用を有することが可能であることを理解することができる。例えば、この問題は、秘密の所有者、秘密の保証者、および秘密の正当性を信頼する関係者の間の秘密に関して、同様の信頼関係が存在する時は常に適用することができる。

［発明の概要］
第１の態様によれば、本発明は、取り消し証を有するグループ署名方式によって計算資源へのアクセスを判断する方法を提供し、この方法は、証明書発行者が、グループ秘密鍵を保持し、且つ、グループ公開鍵を提供すること、グループメンバが、メンバーシップ秘密値を得て、証明書発行者が、メンバーシップ秘密値に関するグループメンバのメンバーシップ証明書を提供すること、グループメンバが、メンバーシップ秘密値もメンバーシップ証明書も検証者に明らかにすることなく、署名を提供することによって、自身が正当なメンバーシップ秘密値および正当なメンバーシップ証明書を所有していることを検証者に実証し、且つ、自身のメンバーシップ秘密値および取り消しパラメータから取り消し証を提供すること、および、検証者が、署名および取り消し証から、グループメンバが正当なメンバーシップ秘密値および正当なメンバーシップ証明書を所有していると判断すること、を含む。

さらなる一態様によれば、本発明は、グループ公開鍵を有するグループ署名方式のメンバによって信頼ステータスを実証する方法を提供し、この方法は、グループメンバが、メンバーシップ秘密値を得て、且つ、証明書発行者から、メンバーシップ秘密値に関するグループメンバのメンバーシップ証明書を受け取ること、および、グループメンバが、メンバーシップ秘密値もメンバーシップ証明書も検証者に明らかにすることなく、署名を提供することによって、自身が正当なメンバーシップ秘密値および正当なメンバーシップ証明書を所有していることを検証者に実証し、且つ、自身のメンバーシップ秘密値および取り消しパラメータから取り消し証を提供すること、を含む。

さらなる一態様によれば、本発明は、グループ公開鍵を有するグループ署名方式のメンバの信頼ステータスを検証する方法を提供し、この方法は、検証者が、グループメンバから、グループメンバのメンバーシップ秘密値およびメンバーシップ証明書から生成された署名を受け取り、且つ、グループメンバによって、自身のメンバーシップ秘密値および取り消しパラメータから提供された取り消し証を受け取ること、および、検証者が、署名および取り消し証から、グループメンバが正当なメンバーシップ秘密値および正当なメンバーシップ証明書を所有していると判断すること、を含む。

さらなる一態様によれば、本発明は、プロセッサと、メンバーシップ秘密値、および、グループ公開鍵を有するグループ署名方式の証明書発行者によりメンバーシップ秘密値に対して発行されたメンバーシップ証明書を含むメモリと、を備える信頼できるコンピューティング装置を提供し、この信頼できるコンピューティング装置は、メンバーシップ秘密値もメンバーシップ証明書も検証者に明らかにすることなく、署名を提供することによって、自身が正当なメンバーシップ秘密値および正当なメンバーシップ証明書を所有していることを検証者に実証し、且つ、自身のメンバーシップ秘密値、自身のメンバーシップ証明書、グループ公開鍵、および取り消しパラメータから取り消し証を提供するように適合される。

さらなる一態様によれば、本発明は、第１の関係者が、自身が第３の関係者によって適法に提供された秘密値を所有することを第２の関係者に証明することができる方法を提供し、この方法は、
第３の関係者が、第１の秘密値ｍと、第１の秘密値から関係

に従って計算された第２の秘密値ｃとを第１の関係者に提供するステップであって、ここで、ｎはＲＳＡモジュラスであり、ｅ_１およびｅ_２はＲＳＡ公開指数であり、ｔ_１およびｔ_２はランダムに選ばれた整数であり、それによって、ｄ_１はｅ_１に対応するＲＳＡプライベート指数である、ステップと、
第２の関係者が、第３の関係者からｎ、ｅ_１、ｅ_２、ｔ_１、およびｔ_２を得るステップと、
第１の関係者が第１の秘密値ｍ、および、関係に従って形成された第２の秘密値ｃを有することを第２の関係者に証明するために、第１の関係者が、第１の秘密値を使用する一方向関数の第１の複数の結果、および、第２の秘密値を使用する一方向関数の第２の複数の結果を第２の関係者に提供するステップと、
それによって、第２の関係者が、第１の複数の結果を、ｅ_１を使用する一方向関数の結果と比較し、第２の複数の結果を、ｅ_２を使用する一方向関数の結果と比較し、それによって、第１の関係者が、第１の秘密値ｍも第２の秘密値ｃも受け取ることなく、関係に従って形成された第１の秘密値ｍおよび第２の秘密値ｃを有することを検証するステップと、を含む。

関連する一態様によれば、本発明は、プロセッサと、第１の秘密値ｍ、および、第１の秘密値から関係

に従って計算された第２の秘密値ｃを含むメモリと、を備える信頼できるコンピューティング装置を提供し、ここで、ｎはＲＳＡモジュラスであり、ｅ_１およびｅ_２はＲＳＡ公開指数であり、ｔ_１およびｔ_２はランダムに選ばれた整数であり、それによって、ｄ_１はｅ_１に対応するＲＳＡプライベート指数であり、プロセッサは、第１の秘密値ｍも第２の秘密値ｃも明らかにすることなく、第１の秘密値を使用する一方向関数の第１の複数の結果、および、第２の秘密値を使用する一方向関数の第２の複数の結果を他の関係者に提供することによって、自身が、関係に従って形成された第１の秘密値ｍおよび第２の秘密値ｃを所有していることを他の関係者に証明するようにプログラミングされている。

さらなる一態様によれば、本発明は、第２の関係者によって提供されたサービスへの第１の関係者のアクセスを制御する方法を提供し、第１の関係者は、自身が第３の関係者によって適法に提供された秘密値を所有することを、秘密値を明らかにすることなく別の関係者に証明するように適合され、
第１の関係者が第３の関係者によって適法に提供された秘密値を所有することを、秘密値が第４の関係者に明らかにされない状態で、第１の関係者が証明し、第４の関係者が検証するステップと、
第４の関係者が、第１の関係者に証明書を発行し、第３の関係者によって適法に提供された秘密値であって、或る関係者がその秘密値を所有することを検証する後のステップで再生成されることになる秘密値を、第１の関係者が所有することを検証するステップの識別子を証明書に関連付けるステップと、
第４の関係者が、証明書正当性情報を保持し、それによって、第１の関係者がサービスにアクセスしようと試みる時、第１の関係者が、第４の関係者によって発行された証明書を第２の関係者に提供し、サービスへのアクセスを提供する前に、第２の関係者が、第４の関係者によって提供された証明書正当性情報から、証明書が正当かどうかを判断するステップと、を含む。

好ましくは、グループメンバはコンピューティング装置であり、証明書発行者はそのコンピューティング装置の製造業者である。より具体的には、コンピューティング装置は、好ましくは、認可されていない修正に対して物理的および論理的に耐性を有するように適合された、信頼できるコンピューティングモジュールであり、好ましくは、コンピューティングプラットフォームのコプロセッサとしての使用に適合された、信頼できるコンピューティングモジュールである。

次に、本発明をより良く理解し、有効にする方法を示すために、添付図面に関して、本発明による特定の実施の形態、方法、およびプロセスを単なる例として説明することにする。

［特定の実施の形態の詳細な説明］
信頼できるコンピューティングプラットフォーム連合（Trusted Computing Platform Alliance）の仕様に説明されたタイプの信頼できるプラットフォームについて次に説明する。このようなプラットフォームは、本出願人による先願で説明されており、特に、国際特許出願公開第ＷＯ００／４８０６３号および第ＷＯ００／５４１２６号で説明されている。これらの出願は、適用法の下で可能な最大限まで参照により本明細書に援用される。例示の信頼できるプラットフォームの要素および当該信頼できるプラットフォームのオペレーションを最初に説明することにする。次に、本発明の第２の実施の形態のこれらの要素およびオペレーションを、信頼できるプラットフォームの先の一般的な説明に関して説明することにする。

本明細書では、物理的なコンポーネントまたは論理的なコンポーネントに関して使用される場合の用語「信頼できる」は、その物理的なコンポーネントまたは論理的なコンポーネントが、常に予測されたように振る舞うことを意味するのに使用される。そのコンポーネントの振る舞いは、予測可能であり、かつ、既知である。信頼できるコンポーネントは、認可されていない変更に対して高度の抵抗力を有する。

本明細書では、用語「コンピュータプラットフォーム」は、少なくとも１つのデータプロセッサおよび少なくとも１つのデータストレージ手段を備えるコンピュータシステムを指すのに使用される。このコンピュータシステムは、必ずしもそうとは限らないが、通例、例えば複数のドライバといった関連した通信設備、関連したアプリケーションおよびデータファイルを有する。このコンピュータシステムは、例えば、インターネットへの接続、外部ネットワークへの接続によるか、または、例えばＣＤ ＲＯＭ、フロッピー（登録商標）ディスク、リボンテープ等のデータストレージ媒体に記憶されたデータを受信できる入力ポートを有することによって、例えばユーザまたは別のコンピュータプラットフォームといった外部エンティティと相互作用できる場合がある。用語「コンピュータプラットフォーム」は、コンピュータエンティティのメインデータ処理およびストレージ設備を包含する。

各コンピュータエンティティの信頼できるコンポーネントを使用することによって、異なるコンピューティングプラットフォーム間の或るレベルの信頼が可能にされる。リモートでまたはコンピュータエンティティのモニタを通じてのいずれかによって、このようなプラットフォームにその状態に関して照会することが可能であり、その状態を信頼できる状態と比較することが可能である。このような照会によって収集された情報は、そのプラットフォームのさまざまなパラメータを監視するコンピューティングエンティティの信頼できるコンポーネントによって提供される。信頼できるコンポーネントによって提供された情報は、暗号認証によって認証することができ、信頼することができる。「信頼できるプラットフォーム」は、このように、その機能が、プラットフォームの完全性メトリック（integrity metric）を提供する、信頼できるように測定されたデータにプラットフォームの識別情報を結びつけることである信頼できる物理信頼デバイスをコンピューティングプラットフォームに組み込むことによって達成することができる。この識別情報および完全性メトリックは、プラットフォームの信頼性を保証するように準備された信頼できる関係者（ＴＰ（trusted party））によって提供された予測値と比較される。一致する場合、それは、プラットフォームの少なくとも一部が、完全性メトリックの範囲に応じて正しく動作していることを意味する。

信頼できるコンポーネントが存在することによって、コンピューティングエンティティに対してリモートまたはローカルな１つの第３の関係者のソフトウェアは、自身の認証および同一性の証明を得るために、および、そのコンピューティングエンティティの測定された完全性メトリックを取り出すために、コンピューティングエンティティと通信することが可能になる。人間のユーザが、彼もしくは彼女のコンピューティングエンティティ、または、その者がユーザインターフェースによって対話できる他の任意のコンピューティングエンティティと或るレベルの信頼できる対話を行うために、信頼できるトークンデバイスがユーザにより使用されて、コンピューティングエンティティの信頼できるコンポーネントがインターロゲートされ、信頼できるコンポーネントによって検証された、コンピューティングエンティティの状態に関する報告がユーザに行われる。信頼できるコンポーネントと信頼できるトークンデバイスとの間の認証は、対象となる実際の状況では、相互的である。ユーザは、信頼できるコンポーネントによって認証され、（ユーザが適切な特権を有する場合）信頼できるコンポーネントの制御の許可を受けることができる。信頼できるコンポーネントは、ユーザによって認証され（信頼できるコンポーネントとして認識され、適切な状況では、ユーザにより所有された信頼できるコンポーネント、または、制御可能な信頼できるコンポーネントとして認識される）。

このタイプの信頼できるプラットフォームの利点およびアプリケーションにおける使用は、国際特許出願公開第ＷＯ００／４８０６３号および第ＷＯ００／５４１２６号に多少詳細に説明され、「Trusted Computing Platforms: TCPA Technology in Context」にかなり詳細に説明されており、本明細書ではこれ以上説明しないことにする。

このような構成の信頼できるコンポーネントは、暗号プロセスを使用する。最も望ましいインプリメンテーションは、信頼できるコンポーネントを不正操作できないようにすること、秘密値を他のプラットフォーム機能にアクセス不能にすることによりそれら秘密値を保護すること、および、認可されていない修正に対して強固な免疫を有する環境を提供することである。完全に不正操作できなくすることは不可能であるので、最も近いものは、不正操作の耐性を有するか、または、不正操作を検出する、信頼できるデバイスである。したがって、この信頼できるデバイスは、好ましくは、不正操作の耐性を有する１つの物理的なコンポーネントから構成される。不正操作の耐性の技法は、当業者に既知であり、国際特許出願公開第ＷＯ００／４８０６３号および第ＷＯ００／５４１２６号にさらに説明されている。

信頼できるプラットフォーム１０、４０が、図１の線図に（および図４に写実的に）概略的に示されている。このプラットフォーム１０、４０は、キーボード１４、４５、マウス１６（図４には図示せず）、およびモニタ１８、４４の標準装備を含む。これらの標準装備は、プラットフォームの物理的な「ユーザインターフェース」を提供する。また、信頼できるプラットフォームのこの実施の形態は、スマートカードリーダ１２、４２も含む。スマートカードリーダ１２、４２の横側には、信頼できるプラットフォームとの信頼できるユーザ対話を可能にするためのスマートカード１９、４１が示されている。プラットフォーム１０、４０では、複数のモジュール１５がある（図１に図示されている）。これらのモジュールは、この信頼できるプラットフォームの他の機能要素であって、そのプラットフォームに適した、基本的には任意の種類の機能要素である。このような要素の機能的な意義は、本発明に関係するものではなく、本明細書ではこれ以上説明しないことにする。信頼できるコンピュータエンティティのさらに別のコンポーネントには、通常、１つまたは複数のローカルエリアネットワーク（ＬＡＮ）ポート、１つまたは複数のモデムポート、および１つまたは複数の電源装置、冷却ファン等が含まれる。図４では、以下で説明する本発明の実施の形態に明らかに関連するように、コンピューティングプラットフォーム４０は、ネットワーク４３（このネットワークはＬＡＮ、モデムによってアクセスされる公衆インターネット等のネットワーク、または適切な接続を有する他の任意の形態のネットワークとすることができる）に接続されて示されている。

図２に示すように、信頼できるコンピューティングプラットフォーム１０のマザーボード２０は、（他の標準的なコンポーネントの中でも特に）メインプロセッサ２１、メインメモリ２２、信頼できるデバイス２４（上述した信頼できるコンポーネントの物理的な形態）、データバス２６、ならびに、各制御ライン２７およびライン２８、ＢＩＯＳメモリ２９、ならびに入出力（ＩＯ）デバイス２３を含む。ＢＩＯＳメモリ２９は、プラットフォーム１０のＢＩＯＳプログラムを含む。入出力デバイス２３は、このマザーボードのコンポーネントと、スマートカードリーダ１２、キーボード１４、マウス１６、およびモニタ１８（および、モデム、プリンタ、スキャナ等の追加された任意の周辺デバイス）との間の相互作用を制御する。メインメモリ２２は、通常、ランダムアクセスメモリ（ＲＡＭ）である。動作時に、プラットフォーム１０は、オペレーティングシステム（および、プラットフォームが実行することができるプロセスまたはアプリケーション）をハードディスク（図示せず）からＲＡＭにロードする。このオペレーティングシステムは、例えばＷｉｎｄｏｗｓ ＸＰ（登録商標）である。

コンピュータエンティティは、物理アーキテクチャだけでなく論理アーキテクチャも有するものと考えることができる。論理アーキテクチャは、本明細書において図１から図３で説明する物理アーキテクチャと共に存在するように、コンピュータプラットフォームと信頼できるコンポーネントとの間で同じ基本分割（basic division）を有する。換言すると、信頼できるコンポーネントは、当該コンポーネントが物理的に関係するコンピュータプラットフォームとは論理的に異なる。コンピュータエンティティは、ユーザ空間および信頼できるコンポーネント空間を備える。このユーザ空間は、コンピュータプラットフォーム（第１のプロセッサおよび第１のデータストレージ手段）に物理的に常駐する論理空間である。信頼できるコンポーネント空間は、信頼できるコンポーネントに物理的に常駐する論理空間である。ユーザ空間には、１つまたは複数のドライバ、１つまたは複数のアプリケーションプログラム、ファイルストレージエリア、スマートカードリーダ、スマートカードインターフェース、およびソフトウェアエージェントが存在する。このソフトウェアエージェントは、ユーザ空間でオペレーションを実行でき、信頼できるコンポーネントに報告を返すことができる。信頼できるコンポーネント空間は、信頼できるコンポーネントに基づき、かつ、その信頼できるコンポーネントに物理的に常駐する論理エリアであり、その信頼できるコンポーネントの第２のデータプロセッサおよび第２のメモリエリアによってサポートされる。モニタ１８は、信頼できるコンポーネント空間から直接画像を受け取る。コンピュータエンティティの外部には、例えば、インターネット、およびさまざまなローカルエリアネットワーク、ワイドエリアネットワークといった外部通信ネットワークが存在する。これらのネットワークは、ドライバ（１つまたは複数のモデムポートを含むことができる）を介してユーザ空間に接続される。外部ユーザスマートカードは、ユーザ空間のスマートカードリーダに入力する。

通常、パーソナルコンピュータでは、ＢＩＯＳプログラムが、予約された特別なメモリエリアに配置される。この特別なメモリエリアは、システムメモリの最初のメガバイトの上位６４キロバイト（アドレスＦ０００ｈからＦＦＦＦｈ）である。業界標準によれば、メインプロセッサは、このメモリロケーションを最初に調べるように構成される。

このプラットフォームと従来のプラットフォームとの間の重大な相違は、リセット後、メインプロセッサが、信頼できるデバイスによって最初に制御され、次いで、この信頼できるデバイスが、プラットフォーム特有のＢＩＯＳプログラムに制御を渡し、次に、ＢＩＯＳプログラムがすべての入出力デバイスを通常通り初期化するということである。ＢＩＯＳプログラムが実行された後、制御は、通常通り、ＢＩＯＳプログラムによって、ＷｉｎｄｏｗｓＸＰ（商標）等のオペレーティングシステムプログラムに渡される。このオペレーティングシステムプログラムは、通常、ハードディスクドライブ（図示せず）からメインメモリ２２にロードされる。

明らかに、この通常の手順からの変更によって、業界標準のインプリメンテーションの修正が必要とされる。その修正によって、メインプロセッサ２１は、信頼できるデバイス２４をアドレス指定して、その最初の命令を受け取るように指示される。この変更は、単に、メインプロセッサ２１に異なるアドレスをハードコード化することによって行うことができる。代替的に、信頼できるデバイス２４に、標準ＢＩＯＳプログラムのアドレスを割り当てることができる。この場合、メインプロセッサの構成を修正する必要はない。

一方、比較的安全なプラットフォームは、このような基本変更なしに達成することができる。このようなインプリメンテーションでは、プラットフォームは、電源投入時には依然としてＢＩＯＳにより制御され、したがって、ＢＩＯＳ（または、少なくともＢＩＯＳブートブロック）も信頼できるものでなければならない。これは、信頼の基盤（root-of-trust）が（説明した、好ましい信頼できるプラットフォームの実施の形態におけるように）単一ではなく、２つ存在することを意味し、ＢＩＯＳブートブロックも信頼の基盤となることを意味する。

ＢＩＯＳブートブロックが、信頼できるデバイス２４内に含まれることは非常に望ましい。これによって、完全性メトリックを得ることの破壊（通常ならば、悪性ソフトウェアプロセスが存在する場合に発生し得る）が防止され、悪性ソフトウェアプロセスが、ＢＩＯＳ（たとえ正しくても）がオペレーティングシステムに適した環境を構築できない状況を作り出すことが防止される。

信頼できるデバイス２４は、図３に示すように複数のブロックを備える。システムがリセットされた後、信頼できるデバイス２４は、認証されたブートプロセスを実行して、プラットフォーム１０のオペレーティングシステム（システムクロックおよびモニタ上の表示を含む）が適切にかつ安全な方法で実行されていることを保証する。より正確には、プラットフォームの状態が信頼できるように記録されることを保証する。認証されたブートプロセスの期間中、信頼できるデバイス２４は、コンピューティングプラットフォーム１０の完全性メトリックを取得する。また、信頼できるデバイス２４は、安全なデータ転送、ならびに、例えば、暗号化／解読および署名／検証を介して当該信頼できるデバイスとスマートカードとの間の認証を実行することもできる。また、信頼できるデバイス２４は、ユーザインターフェースのロック等のさまざまなセキュリティ制御ポリシーを安全に実行することもできる。

具体的には、信頼できるデバイスは、コントローラ３０、測定機能３１、暗号機能３２、認証機能３３、およびインターフェース回路部３４を備える。コントローラ３０は、信頼できるデバイス２４の全体的なオペレーションを制御し、且つ信頼できるデバイス２４の他の機能およびマザーボード２０の他のデバイスと相互作用するようにプログラミングされている。測定機能３１は、プラットフォーム１０から完全性メトリックを取得するためのものである。暗号機能３２は、指定されたデータの署名、暗号化、または解読を行うためのものである。認証機能３３は、スマートカードを認証するためのものである。インターフェース回路部３４は、信頼できるデバイス２４を、マザーボード２０のデータバス２６、制御ライン２７、およびアドレスライン２８にそれぞれ接続するための適切なポート（３６、３７および３８）を有する。信頼できるデバイス２４のこれらブロックのそれぞれは、信頼できるデバイス２４の適切な揮発性メモリエリア４および／または不揮発性メモリエリア３に（通常、コントローラ３０を介して）アクセスする。これに加えて、信頼できるデバイス２４は、耐タンパ性を有するように、既知の方法で設計される。

好ましい構成では、モニタ１８は、信頼できるコンポーネント自体に含まれるモニタサブシステムによって直接駆動することができる。この実施の形態では、信頼できるコンポーネント空間には、信頼できるコンポーネント自体が常駐し、表示が、信頼できるコンポーネントによってモニタ１８に生成される。この構成は、本出願人の国際特許出願公開第ＷＯ００／７３８７９号にさらに説明されている。この国際特許出願は、参照により本明細書に援用される。

性能の理由により、信頼できるデバイス２４は、特定用途向け集積回路（ＡＳＩＣ）として実施されることがある。しかしながら、柔軟性のため、信頼できるデバイス２４は、好ましくは、適切にプログラミングされたマイクロコントローラである。ＡＳＩＣおよびマイクロコントローラは、共に、マイクロエレクトロニクスの技術分野において既知であり、本明細書ではこれ以上詳細に考察しないことにする。

信頼できるデバイス２４の不揮発性メモリ３に記憶された１つのデータ項目は、証明書３５０である。この証明書３５０は、少なくとも、信頼できるデバイス２４の公開鍵３５１、および、信頼できる関係者（ＴＰ）によって測定されたプラットフォーム完全性メトリックの認証値３５２を含む。証明書３５０は、信頼できるデバイス２４に記憶される前に、ＴＰのプライベート鍵を使用してＴＰにより署名される。後の通信セッションでは、プラットフォーム１０のユーザは、取得された完全性メトリックを真正な完全性メトリック３５２と比較することによって、プラットフォーム１０の完全性を検証することができる。一致する場合、ユーザは、プラットフォーム１０が破壊されていないことを確信することができる。ＴＰの一般に利用可能な公開鍵を知ることによって、証明書３５０の簡単な検証が可能になる。また、不揮発性メモリ３５は識別（ＩＤ）ラベル３５３も含む。このＩＤラベル３５３は、或る状況において一意である従来のＩＤラベルであり、例えば、連続番号である。ＩＤラベル３５３は、一般に、信頼できるデバイス２４に関連したデータのインデックスおよびラベルに使用されるが、信頼できる状況下においてプラットフォーム１０の同一性を証明するのにそれ自体では不十分である。

信頼できるデバイス２４は、自身が関連付けられているコンピューティングプラットフォーム１０の完全性メトリックを信頼できるように測定または取得する少なくとも１つの方法を備えている。これによって、プラットフォーム１０の潜在的なユーザには、プラットフォーム１０がハードウェアレベルにおいてもＢＩＯＳプログラムレベルにおいても破壊されていないことの高レベルの確信が与えられる。オペレーティングシステムおよびアプリケーションプログラムコードが破壊されていないことをチェックするための他の既知のプロセス、例えばウィルスチェッカが、通常、配置されることになる。

測定機能３１は、信頼できるデバイス２４のハッシュプログラム３５４およびプライベート鍵３５５を記憶するための不揮発性メモリ３、ならびに、取得された完全性メトリックを摘要３６１の形で記憶するための揮発性メモリ４にアクセスする。適切な実施の形態では、揮発性メモリ４は、プラットフォーム１０にアクセスするのに使用できる１つまたは複数の真正なスマートカード１９の公開鍵および関連したＩＤラベル３６０ａ〜３６０ｎを記憶するのに使用することもできる。

完全性メトリックの取得は、本発明にとって必須のものではなく、本明細書ではこれ以上説明しないことにする。このプロセス、および、ユーザまたは第３の関係者による信頼できるプラットフォームの完全性を検証するプロセスは、国際特許出願公開第ＷＯ００／４８０６３号に詳細に説明されるプロセスである。

上述したように、信頼できるプラットフォームに対してユーザを認証するための好ましい手段は、スマートカード１９等のトークンデバイスである（ただし、ユーザは、例えば、ネットワークによって信頼できるプラットフォームと通信するリモートプラットフォームとすることができることに留意すべきである）。ユーザのスマートカード１９は、コンピューティングエンティティとは別個のトークンデバイスである。このトークンデバイスは、スマートカードリーダポート１９を介してコンピューティングエンティティと相互作用する。ユーザは、いくつかの異なるベンダまたはサービスプロバイダによって発行された、いくつかの異なるスマートカードを有することができる。また、ユーザは、本明細書で説明するような複数のコンピューティングエンティティのいずれか１つからインターネットまたは複数のネットワークコンピュータにアクセスすることができる。これら複数のコンピューティングエンティティには、信頼できるコンポーネントおよびスマートカードリーダが提供される。ユーザが使用している個々のコンピューティングエンティティの当該ユーザの信頼は、ユーザの信頼できるスマートカードトークンとそのコンピューティングエンティティの信頼できるコンポーネントとの間の相互作用から得られる。ユーザは、自身の信頼できるスマートカードトークンを頼りにして、信頼できるコンポーネントの信頼性を検証する。

図５は、信頼できる関係者ＴＰによる動作、プラットフォームに組み込まれた信頼できるデバイス２４による動作、および、従来技術の信頼できるプラットフォーム技術に従って信頼できるプラットフォームの完全性を検証したい（リモートプラットフォームの）ユーザによる動作のフローを示している。ユーザがローカルユーザである場合にも、図５に示すステップと実質的に同じステップが含まれることが理解されよう。いずれの場合も、ユーザは、通常、或る形態のソフトウェアアプリケーションを頼りにして、検証を遂行する。リモートプラットフォームまたは信頼できるプラットフォームでソフトウェアアプリケーションを実行することが可能である。しかしながら、リモートプラットフォームであっても、ソフトウェアアプリケーションを何らかの方法で破壊できる機会がある。したがって、高レベルの完全性を得るには、ソフトウェアアプリケーションがユーザのスマートカードに常駐することが好ましい。このユーザは、検証のためにこのスマートカードを適切なリーダに挿入することになる。

最初の段階では、信頼できるプラットフォームを保証するＴＰが、プラットフォームのタイプを検査して、そのプラットフォームを保証すべきかどうかを決定する。これは、ポリシーの問題である。すべてがうまくいくと、ステップ５００において、ＴＰは、プラットフォームの完全性メトリックの値を測定する。次に、ＴＰは、ステップ５０５で、プラットフォームの証明書を生成する。この証明書は、信頼できるデバイスの公開鍵およびオプションとしてそのＩＤラベルを、測定された完全性メトリックに付加すること、および、ＴＰのプライベート鍵でその文字列に署名することによって、ＴＰにより生成される。本発明は、特に、イベントのこの連鎖およびこのような信頼できる関係者（通常、認証局）の役割の改良に関係していることに留意すべきである。

信頼できるデバイス２４は、その後、自身のプライベート鍵を使用して、ユーザから受け取った或る入力データを処理し出力データを生成し、入力／出力の対が、プライベート鍵の知識なしでは生成することが統計的には不可能であるようにすることによって自身の同一性を証明する。したがって、プライベート鍵の知識は、この場合の同一性の基礎を形成する。明らかに、対称暗号化を使用して、同一性の基礎を形成することは実現可能である。しかしながら、対称暗号化を使用する場合の不都合は、ユーザが自身の秘密値を信頼できるデバイスと共有する必要があるということである。さらに、秘密値をユーザと共有する必要がある結果として、対称暗号化は、原則として、ユーザに同一性を証明するには十分であるが、第３の関係者に同一性を証明するには不十分である。第３の関係者は、信頼できるデバイスまたはユーザからもたらされた検証を完全に確信することができない。

ステップ５１０において、信頼できるデバイス２４は、当該信頼できるデバイス２４の適切な不揮発性メモリロケーション３に証明書３５０を書き込むことによって初期化される。これは、好ましくは、信頼できるデバイス２４がマザーボード２０にインストールされた後に、信頼できるデバイス２４との安全な通信によって行われる。信頼できるデバイス２４に証明書を書き込む方法は、プライベート鍵をスマートカードに書き込むことによってスマートカードを初期化するのに使用される方法と類似している。安全な通信は、ＴＰのみが知っている「マスタ鍵」によってサポートされる。この「マスタ鍵」は、製造期間中に信頼できるデバイス（またはスマートカード）に書き込まれ、信頼できるデバイス２４へのデータの書き込みを可能にするのに使用される。マスタ鍵の知識なしで、信頼できるデバイス２４へのデータの書き込みは不可能である。

プラットフォームの動作中の或る後の時点で、例えば、プラットフォームが電源投入されるか、または、リセットされると、ステップ５１５において、信頼できるデバイス２４は、プラットフォームの完全性メトリック３６１を取得して記憶する。

ユーザがプラットフォームと通信したい場合、ステップ５２０において、ユーザは、乱数等のノンスを作成し、ステップ５２５において、信頼できるデバイス２４を誰何する（プラットフォームのオペレーティングシステムまたは適切なソフトウェアアプリケーションは、その誰何を認識し、通常はＢＩＯＳタイプの呼び出しを介して適切な方法で、信頼できるデバイス２４にその誰何を渡すように構成される）。ノンスは、信頼できないプラットフォームによる、古いが本物の署名を再生したもの（「反射攻撃（replay attack）」と呼ばれる）によって引き起こされる詐欺からユーザを保護するのに使用される。ノンスを提供してその応答を検証するプロセスは、既知の「誰何／応答」プロセスの一例である。

ステップ５３０において、信頼できるデバイス２４は、誰何を受け取って、適切な応答を作成する。この応答は、測定された完全性メトリックおよびノンス、ならびにオプションとしてそのＩＤラベルの摘要とすることができる。次に、ステップ５３５において、信頼できるデバイス２４は、そのプライベート鍵を使用して摘要に署名し、署名した摘要を、証明書３５０を添付してユーザに返す。

ステップ５４０において、ユーザは、誰何応答を受け取り、ＴＰの既知の公開鍵を使用して証明書を検証する。次に、ユーザは、ステップ５５０において、信頼できるデバイス２４の公開鍵を証明書から抽出し、その公開鍵を使用して、誰何応答からの署名された摘要を解読する。次に、ステップ５６０において、ユーザは、誰何応答内部のノンスを検証する。次に、ステップ５７０において、ユーザは、計算された完全性メトリックを適切なプラットフォーム完全性メトリックと比較する。計算された完全性メトリックは、ユーザが誰何応答から抽出する。適切なプラットフォーム完全性メトリックは、ユーザが証明書から抽出する。上記検証ステップのいずれかが失敗すると、ステップ５４５、５５５、５６５、または５７５において、プロセス全体がステップ５８０で終了し、それ以上の通信は行われない。

すべてがうまくいくと仮定して、ステップ５８５および５９０において、ユーザおよび信頼できるプラットフォームは、他のプロトコルを使用して、他のデータの安全な通信をセットアップする。ここで、プラットフォームからのデータは、好ましくは、信頼できるデバイス２４によって署名される。

この検証プロセスをさらに洗練することが可能である。誰何者が、誰何を通じて、プラットフォーム完全性メトリックの値、および、そのプラットフォーム完全性メトリックの値が得られた方法の双方を知っていることが望ましい。これら双方の情報は、誰何者がプラットフォームの完全性について適切な判断を行うことを可能にするものであることが望ましい。また、誰何者は、利用可能な多くの異なるオプションを有する。すなわち、誰何者は、完全性メトリックが、信頼できるデバイス２４において正当であると認識されることを容認することができるか、または、完全性メトリックの値が、誰何者によって保持された値と等しい場合に、プラットフォームが、関連したレベルの完全性を有することのみを容認することができる（もしくは、これら２つの場合に、異なるレベルの信頼が存在すると考えることができる）。

証明書への署名、証明書の使用、および誰何／応答の技法、ならびに、それらを使用して同一性を証明する技法は、セキュリティの当業者に既知であり、したがって、本明細書ではこれ以上詳細に説明する必要はない。

前述の構造およびプロトコルを使用し、場合によっては変更する、本発明の特定の実施の形態を次に説明することにする。まず、特に関連した状況を図６に関して説明することにする。図６は、従来の信頼できるコンピューティング技術における、リモートサービスプロバイダ（ＲＳＰ（remote service provider））から信頼できるプラットフォームによるサービスの獲得に関与するか、または、関与する可能性のある異なる関係者、および、それら異なる関係者の信頼関係を概略的に示している。

信頼できるプラットフォーム製造業者６１は、信頼できるプラットフォームモジュール（ＴＰＭ（trusted platform module））６２を製造し、一意の保証鍵をＴＭＰ６２に提供する（ステップ６５）。製造業者はこの一意の保証鍵を証明する。この証明された保証鍵は、次に、信頼できるプラットフォーム製造業者６１によって信頼された認証局（ＣＡ）６３に渡され（ステップ６６）、ランダムに選ばれた識別情報に関する証明書が、ＣＡによって発行される（ステップ６７）。このランダムに選ばれた識別情報は、ＴＰＭの新しい識別情報となる。リモートサービスプロバイダ（ＲＳＰ）６４は、プラットフォームにサービスを提供することができるが、サービスを受け取るプラットフォームが確かに信頼できることが確信できない場合に、このサービスを提供することを好まないことがある。ＴＰＭ６２は、このＲＳＰ６４とのその後の相互作用において、このＣＡ証明書をＲＳＰ６４に提供する（ステップ６８）。ＲＳＰ６４は、次に、ＣＡの公開データを使用することによって、その証明書がＣＡ６２によって正当に発行されたものであることをチェックすることができる。ここで、ＲＳＰは、ＣＡ、および、本物の信頼できるプラットフォームの製造業者の双方を信頼するものと仮定する。そうである場合、ここに、有効な信頼の連鎖（chain of trust）が存在する。すなわち、ＲＳＰはＣＡを信頼し、したがって、（ＴＰＭが、信頼できるプラットフォーム製造業者によって証明されたことを示すものと主張する）証明された情報が正当であることを信頼し、したがって、ＴＰＭ６２が、確かに、既知の信頼できるプラットフォーム製造業者６１の適法な製品であることを信頼する。信頼できるプラットフォームのプライバシーに関連した事項も、ＲＳＰに関して満たすことができる。すなわち、この構成は、ＲＳＰがどのＴＰＭと相互作用しているかをＲＳＰに明らかにする必要はない（すなわち、これは、ＲＳＰが確立できるものは、ＲＳＰが、既知でかつ信頼できる製造業者によって製造された真正なＴＰＭと相互作用しているということだけであるように構成することができる）。

上述したように、この方式に関する深刻な問題は、ＣＡが現在、システムの弱点であるということである。すなわち、ＴＰＭの識別情報（および、場合によっては多数のＴＰＭの識別情報）を相関させることが可能である。ＣＡが、保証鍵を識別情報にマッピングしないとする同意を破るか、または、このようなマッピングを行う許可を有し、ＣＡのデータベースが危険にさらされる場合、そのＣＡによって証明されているすべてのＴＰＭの識別情報も、おそらく危険にさらされていることになる。

この問題に対処する２つの異なる方式および関連したアーキテクチャを次に説明することにする。第１の方式は、信頼できるプラットフォームが、秘密値そのものを明らかにすることなく、信頼できる製造業者によって正当に形成された証明書を所有するということを検証者（リモートサービスプロバイダ等）に直接証明することを、信頼できるプラットフォームモジュールに与えられた証明書の特定の構成が信頼できるプラットフォームにどのように可能にすることができるかを詳述し、次に、取り消しを満足に実行できるシステムアーキテクチャの説明に進む。第２の方式は、取り消しに使用される証拠を提供するように適合されたグループ署名方式である。この第２の方式は、広く説明されるように、一般的な方式とみなすことができ、第１の方式はこの一例でもある（ただし、異なる特定のアルゴリズムを第１の方式に対して使用する、第２の方式の特定のバージョンも説明される）。

＜第１の方式＞
本発明の態様では、この問題を解決するために取られた手法は、検証者が特定のＴＰＭを見分けることができないように、ＴＰＭが信頼できる製造業者の証明を有することを、ＴＰＭ自身が検証者に確信させることを可能にするメカニズムを見つけることである。検証者は、ＲＳＰの場合もあるし、認証局の場合もあるし、取り消し局の場合もある。したがって、ＴＰＭは、単に、その保証鍵をＣＡに与え、次いで、ＲＳＡが（ＣＡを参照することによる）間接的な証明を有するのではなく、自身が適法なＴＰＭであるという直接的な証明を提供することができる。関与する関係は、（同じ要素を参照する場合は、図６と同じ参照番号で）図７に示されている。信頼できるプラットフォーム製造業者６１は、一意の識別情報をＴＰＭ６２に提供し、この識別情報を証明する（ステップ６５）。以下で分かるが、この証明は新しい形態を取る。したがって、このような構成では、ＣＡ６３は、この製造業者の証明書を証明する役割を行う必要がないということが可能である（ただし、取り消しに関して以下で分かるように、ＴＰＭ証明が取り消されたかどうかを判断することをＲＳＰに可能にする際のＣＡの役割は依然として存在する。これは、図７では、破線７３によって表されている）。その代わりに、ＴＰＭが信頼できる製造業者の適法な商品であることを、検証者６４が立証する必要がある場合、相互作用７１が行われる。この相互作用７１では、ＴＰＭは、自身の一意の識別情報を検証者に明らかにしないが、自身の証明書が、信頼できる製造業者による適切な方法以外の何らかの方法で形成された可能性は極めて少ないことを（適切な標準機関（standard）へ）示す。以下でさらに説明するように、この相互作用７１は、検証者６４とＴＰＭ６２との間の反復的な相互作用とすることができる（証明者および検証者を有するこのような相互作用による証明は、ゼロ知識証明として知られている。この証明では、証明者は、或る記述の証明にどのように取り掛かるに関する情報を何ら明らかにすることなく、検証者にその記述を確信させる）。または、この相互作用７１は、検証者による評価について、署名された数学的構造を検証者にＴＰＭによって提供することにより達成することもできる（ＴＰＭに対するいくつかの計算負担を犠牲にして通信効率に明らかな利点を有する）。いずれの場合も、検証者は、信頼できるプラットフォーム製造業者からの公開データを使用して、証明書が、信頼できるプラットフォーム製造業者によって適切な方法で形成されたものに違いないと判断する。

本発明の一態様による直接的な証明方式を次に説明することにする。この方式は、２つのバージョンで説明される。一方のバージョンは、ＴＰＭと検証者との間の反復的な相互作用を必要とするゼロ知識証明である。他方のバージョンは、ＴＰＭによる数学的構造の匿名の署名を含み、検証者は、その後、ＴＰＭの証明書がその数学的構造の解決によって正当に形成されるものと判断することができる。いずれの場合も、製造業者による証明は、条件

を使用する。
ここで、ｍはＴＰＭの識別情報であり、（ｅ_１，ｅ_２，ｎ，ｔ_１，ｔ_２）はＴＰＭ製造業者の公開パラメータである。これらのプライベートコンポーネントのうち、ｎはＲＳＡモジュラスであり、ｅ_１およびｅ_２はＲＳＡの指数であり、ｔ_１およびｔ_２は、ランダムに選ばれた整数である。ｄ_１は、ｅ_１から導出されたプライベートパラメータである。この条件は、ゼロ知識では（ｌｏｇｅ_１）＋（ｌｏｇｅ_２）ラウンドによって証明することができる。ｅ_１もｅ_２もセキュリティパラメータではないので、双方は、合理的に小さな範囲内になるように選ぶことができる（ＴＣＧ仕様の現在のバージョンでは、ｅ＝２^１６＋１であり、ｎは２０４８ビットのサイズを有する）。この方式のセキュリティは、ｎが未知の因数分解を有するＲＳＡモジュラスである場合に、

となるような値ｍおよびｃを計算することが困難となるように、

に２つの整数ｔ_１およびｔ_２が存在し、

に２つの小さな整数ｅ_１およびｅ_２が存在するという仮定（J. CamenischおよびM. Stadler著「Efficient group signature schemes for large groups」, Advances in Cryptology - CRYPTO '97, LNCS 1294, pp. 410-424, Springer-Verlag, 1997によって提案された）に基づいている。

を用いて正当な対（ｍ，ｃ）を偽造するために、攻撃者は、（ａ）ｃを選び、次に、

を計算するか、または、（ｂ）ｍを選び、次に、

を計算することによって開始することができる。いずれの場合も、攻撃者は、ＲＳＡ問題を解かなければならず、したがって、正当な対の偽造は困難であるとみなすことができる。

用語がこの出願で具体的に特定されていない場合、これは、一般的に、それら用語が一般に暗号学で使用されるものであり、当業者に容易に理解されるからである。あるいは、読み手には、適切な暗号学の入門書（http://www.rsasecurity.com/rsalabs/faq/index.htmlで入手される、RSA Laboratories' Frequently Asked Questions About Today's Cryptographyのテキストおよび参考文献で提供される入門書等）が案内される。

各方式は、基本構築ブロックとして、（ｈ，ｘ＝ｈ^ｕ，ｙ＝ｈ^ｖ，ｚ＝ｈ^ｕｖ）がＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ（ＤＨ）タプルであること、および、証明者が秘密値ｖを知っていることを検証するのに使用される技術プリミティブ（technical primitive）を使用する。ゼロ知識証明およびその署名バージョンには、異なる技術プリミティブが使用される。双方のプリミティブは、以下のように同じ入力を使用する。

公開入力：
ｎ−ＲＳＡモジュラス、Ｈ−｜ｎ｜に近い出力サイズを有するハッシュ関数
Ｋ−Ｐ＝Ｋｎ＋１（素数）を満たす最小数
ａ∈Ｚ_ｎ ^＊（ａ≠１），ｈ＝ａ^Ｋ ｍｏｄ Ｐ
ｘ＝ｈ^ｕ ｍｏｄ Ｐ，ｙ＝ｈ^ｖ ｍｏｄ Ｐ，ｚ＝ｈ^ｕｖ ｍｏｄ Ｐ
（証明者の）プライベート入力：ｖ

相互作用方式のプリミティブは、本明細書では、ＤＨ−ｉｎｔｅｒａｃｔｉｏｎ（ｈ，ｘ，ｙ，ｚ）と呼ぶ。これは、以下のステップを含む。
１．検証者は、１＜ａ＜ｎ、１＜ｂ＜ｎをランダムに選び、証明者にＣ＝ｈ^ａｘ^ｂ ｍｏｄ Ｐを送る。
２．証明者は、検証者にＲ＝Ｈ（Ｃ^ｖ ｍｏｄ Ｐ）を送る。
３．検証者は、Ｒ？＝Ｈ（ｙ^ａｚ^ｂ ｍｏｄ Ｐ）である場合は容認し、そうでない場合は拒否する（なお、例えば、「Ａ？＝Ｂ」は、「もしＡ＝Ｂなら真、それ以外は偽」を意味する）。

このプリミティブは、明らかにシミュレーション可能である（ゼロ知識証明の特性は、ゼロ知識証明が、どの第３の関係者にも秘密値に関する情報を提供することなく正確にシミュレーションできることである）。その理由は、誰もが、ｖを知ることなく、Ｃ＝ｈ^ａｘ^ｂ ｍｏｄ ＰおよびＲ＝Ｈ（ｙ^ａｚ^ｂ ｍｏｄ Ｐ）を計算できるからである。このシミュレーションは、実際の証明からの分布（distribution）と同一の分布を有する。

署名方式のプリミティブは、本明細書では、ＤＨ−ｓｉｇｎａｔｕｒｅ（ｈ，ｘ，ｙ，ｚ）と呼ぶ。これは、証明者と検証者との間で以下のように働く。
１．署名者は１＜ｂ＜ｎをランダムに選び、次に、以下を計算する。
ｆ＝ｈ^ｂ ｍｏｄ Ｐ，ｇ＝ｘ^ｂ ｍｏｄ Ｐ
ｗ＝Ｈ（ｘ，ｙ，ｚ，ｆ，ｇ）
ｓ＝ｂ−ｖ＊ｗ ｍｏｄ ｎ
署名者は、ＤＨタプル（ｘ，ｙ，ｚ）に対する署名として、検証者に（ｗ，ｓ）を送る。
２．その署名を検証するために、検証者は以下を計算する。
ｆ'＝ｈ^ｓｙ^ｗ ｍｏｄ Ｐ
ｇ'＝ｘ^ｓｚ^ｗ ｍｏｄ Ｐ
ｗ'＝Ｈ（ｘ，ｙ，ｚ，ｆ'，ｇ'）
検証者は、ｗ'？＝ｗのチェックが成功する場合は容認し、そうでない場合は拒否する。

ＤＨ−ｓｉｇｎａｔｕｒｅ（ｈ，ｘ，ｙ，ｚ）は、鍵（ｖ，ｈ，ｘ，ｙ，ｚ，ｎ，Ｐ）に基づいたＤＨタプル（ｘ，ｙ，ｚ）に署名するＳｃｈｎｏｒｒに基づく署名（C. P. Schnorr著「Efficient identification and signatures for smart cards」, Advances in Cryptology-Crypto '89, LNCS 435, pp. 239-252, Springer-Verlag, 1990を参照されたい）である。ここで、ｖはプライベートパラメータであり、（ｈ，ｘ，ｙ，ｚ，ｎ，Ｐ）は公開パラメータである。

これらのプリミティブを使用して、図７で述べた信頼関係に適した直接証明方式を提供することを次に説明することにする。信頼できるプラットフォームモジュールの信頼できる製造業者（以下、ＴＰＭ製造業者）は、自身が生成するＴＰＭを証明できるようにするために次のことを必要とする。すなわち、１つのＲＳＡモジュラスｎ、２つの公開パラメータｅ_１およびｅ_２、ならびにｅ_１＊ｄ_１＝１ ｍｏｄ φ（ｎ）となるように計算された１つのプライベートパラメータｄ_１を必要とする。値Ｋは、Ｐ＝Ｋｎ＋１が素数となるように選ばれる。ｎは２０４８ビットよりも僅かに小さく、ＫはＰを素数とする最小の値であり、Ｐは約２０４８ビットであることが望ましい。ｔ_１およびｔ_２は、それらのｅ_１乗根およびｅ_２乗根を計算するのが困難であるように、

においてランダムに選ばれる。

ＴＰＭ製造業者は、次に、自身が生成するＴＰＭを次のように証明する。すなわち、まず、識別情報ｍが１＜ｍ＜ｎとなるように選ばれる。この後、ＴＰＭ製造業者は、

を計算することによってｍを証明する。ｍおよびｃは、次に、ＴＰＭに記憶される。オプションとして、ＴＰＭ製造業者がｍの値もｃの値も知らないように、ＣｈａｕｍのＲＳＡブラインド署名方式（D. Chaum著「Blind signatures for untraceable payments」, Advances in Cryptology - Crypto '82, Springer-Verlag (1983), 199-203を参照されたい）を使用することが可能である。

本明細書で説明した直接証明方式は、以下の目標を達成するように設計される。すなわち、この方式の実行終了時に、
１．検証者は、要求されたＴＰＭがｍおよびｃを知っていると確信する。ここで、

である。
２．検証者はｍもｃも知らない。

検証者に上記１）を確信させるために、ＴＰＭは、

および

を検証者に送り、次に、ｘおよびｙの構造を検証者に確信させる。ここで、（ｈ，ｅ_１，ｅ_２）はＴＰＭからの公開入力であり、（ｍ，ｃ）はＴＰＭからのプライベート入力である。その後、検証者は、

である場合は１）を容認し、そうでない場合は１）を拒否する。

ｘおよびｙの構造のこのような証明を得るための一般的な場合のプロトコルは、以下の通りである。このプロトコルは、ゼロ知識バージョンおよび匿名署名バージョンの双方に適用され、これら２つのバージョンにおけるこのプロトコルの適用の相違が示される。ゼロ知識バージョンは、２００１年２月２０日に出願された本出願人の先願の英国特許出願第０１０４１４０．９号に一部由来するのに対して、署名バージョンは、Ｓｃｈｎｏｒｒ署名方式（C. P. Schnorr著「Efficient identification and signatures for smart cards」, Advances in Cryptology-Crypto '89, LNCS 435, pp. 239-252, Springer-Verlag, 1990を参照されたい）に一部由来する。ゼロ知識バージョンでは、ＤＨ−ｉｎｔｅｒａｃｔｉｏｎがこのプロトコルで使用されることになり、署名バージョンでは、ＤＨ−ｓｉｇｎａｔｕｒｅが代わりに使用されることになる。

このプロトコルは、具体的にｅ_１およびｅ_２に適用されるのではなく、一般的に任意のｅに適用される。したがって、ｅが、ｅ_１またはｅ_２の代わりに使用され、

が、

または

の代わりに使用される。このように、指定されたプロトコルは、ｘおよびｙの双方を証明するのに適している。

プロトコル

証明者は、公開入力（ｅ，ｎ，Ｐ，ｈ，λ，δ（ｅ））が

およびλ＝ｈ^βを満たすこと、ならびに、証明者がαおよびβを知っていることを検証者に確信させる。

このプロトコルでは、

である。このプロトコルは、ＤＨ−ｉｎｔｅｒａｃｔｉｏｎまたはＤＨ−ｓｉｇｎａｔｕｒｅのいずれかのチェックが成功しない場合に中止される。

証明者および検証者は、以下のプロトコルを、γ＝ｅから開始することによって実行する。

ｗｈｉｌｅ γ＞１ ｄｏ
｛
１．証明者は以下のステップを実行する。

ｔが偶数の場合：ｙ←δ（γ），ｘを検証者に送る。
ｔが奇数の場合：ｙ←δ（γ−１），ｘおよびｙを検証者に送る。
２．ｔが偶数の場合：双方がＤＨ−ｉｎｔｅｒａｃｔｉｏｎ（ｈ，ｘ，ｘ，δ（γ））またはＤＨ−ｓｉｇｎａｔｕｒｅ（ｈ，ｘ，ｘ，δ（γ））を実行する。
ｔが奇数の場合：双方がＤＨ−ｉｎｔｅｒａｃｔｉｏｎ（ｈ，ｘ，ｘ，ｙ）またはＤＨ−ｓｉｇｎａｔｕｒｅ（ｈ，ｘ，ｘ，ｙ）、および、ＤＨ−ｉｎｔｅｒａｃｔｉｏｎ（ｈ，ｙ，λ，δ（γ））またはＤＨ−ｓｉｇｎａｔｕｒｅ（ｈ，ｙ，λ，δ（γ））を実行する。
３．双方が

を実行し、次に、（δ（γ）←ｘ）を実行する。
｝
γ＝１の場合、双方がＤＨ−ｉｎｔｅｒａｃｔｉｏｎ（ｈ，ｈ，δ（１），λ）またはＤＨ−ｓｉｇｎａｔｕｒｅ（ｈ，ｈ，δ（１），λ）を実行する。

検証者は、上記プロセスのすべてが成功した場合は容認し、そうでない場合は拒否する。

上記プロトコルを、一方は

により、他方は、

により、２回実行した後、検証者は、第１回の実行からのδ（ｅ_１）（すなわちｙ）および第２回の実行からのδ（ｅ_２）（すなわちｘ）が、

を満たす場合に、

の構造を容認する。

ゼロ知識バージョンと署名バージョンとの間の一方の基本的な相違は、（上述したように）異なるプリミティブが使用されるということである。他方の基本的な相違は、相互作用バージョンが、或る意味で、プロトコル中、同期した動作を含む（プロトコル中の動作に、証明者と検証者との間の相互作用のストリームが存在する）が、署名バージョンは基本的に非同期である（証明者は、プロトコル中、数学的構造を生成するように動作し、この数学的構造に署名し、そして、それを検証者に提供する。検証者は、その署名をチェックして、数学的構造の間、検証を得るように動作する）。

ゼロ知識方式の場合、各ＤＨ−ｉｎｔｅｒａｃｔｉｏｎは、３モジュロ累乗法（modulo exponentiation）を必要とする。ＴＰＭが１つを計算し、検証者が２つを計算する。全体の相互作用証明は、約５．５＊（（ｌｏｇｅ_１）＋（ｌｏｇｅ_２））モジュロ累乗法のコストを要する。ＴＰＭが約２．５＊（（ｌｏｇｅ_１）＋（ｌｏｇｅ_２））を計算し、検証者が約３＊（（ｌｏｇｅ_１）＋（ｌｏｇｅ_２））を計算する。通信ラウンドは（ｌｏｇｅ_１）＋（ｌｏｇｅ_２）である。｜ｅ_１｜＝｜ｅ_２｜＝１６を選ぶ場合、ＴＰＭは、７２モジュロ累乗法を計算し、かつ検証者と３２ラウンドで通信する必要がある。

署名方式の場合、各ＤＨ−ｓｉｇｎａｔｕｒｅは６モジュロ累乗法を必要とする。ＴＰＭが２つを計算し、検証者が４つを計算する。署名を行うことは約４＊（（ｌｏｇｅ_１）＋（ｌｏｇｅ_２））モジュロ累乗法のコストを要し、署名を検証することは約６＊（（ｌｏｇｅ_１）＋（ｌｏｇｅ_２））のコストを要する。通信コストは、約２．５＊（（ｌｏｇｅ_１）＋（ｌｏｇｅ_２））＊（ｌｏｇＰ）ビットを有する単一のメッセージのコストのみである。

署名方式の具体的なケースを次に説明することにする。このケースは、特に、既存の信頼できるプラットフォーム技術の修正に特に適するように選ばれる。本明細書では、出願人は、ｅ_１＝２^１６＋１およびｅ_２＝２を選ぶこととする。

ＴＰＭは、まず、ａ∈_Ｒ（１，ｎ−１］をランダムに選んで、かつｈ＝ａ^Ｋ ｍｏｄ Ｐ、

および

を計算することによってｈ、ｘ、およびｙを生成する。ＴＰＭは、検証者がｈ、ｘ、およびｙを得ることができるように、これらを利用可能にする（なお、例えば、ｃについて「［ａ，ｂ］」と記した場合、ａ＜＝ｃ＜＝ｂを意味し、同じく「］ａ，ｂ［」と記した場合、ａ＜ｃ＜ｂを意味し、同じく「］ａ，ｂ］」と記した場合、ａ＜ｃ＜＝ｂを意味する。）

ＴＰＭは、以下のように、ｘおよびｙに２つの署名をそれぞれ行う。

１．

ＴＰＭは１＜ｂ＜ｎをランダムに選び、次に、以下を計算する。
ｚ＝ｈ^ｍ ｍｏｄ ｎ
ｆ＝ｈ^ｂ ｍｏｄ Ｐ，ｇ＝ｚ^ｂ ｍｏｄ Ｐ
ｕ＝Ｈ（ｚ，ｘ，ｆ，ｇ）
ｓ＝ｂ−ｍ＊ｕ ｍｏｄ ｎ
ＴＰＭは、

の構造に対する署名として、（ｚ，ｕ，ｓ）を刻む（chip）。

この署名を検証するために、検証者は以下を計算する。
ｆ'＝ｈ^ｓ＊ｚ^ｕ ｍｏｄ Ｐ
ｇ'＝ｚ^ｓ＊ｘ^ｕ ｍｏｄ Ｐ
ｕ'＝Ｈ（ｚ，ｘ，ｆ'，ｇ'）
検証者は、ｕ'？＝ｕのチェックが成功する場合は

を容認し、そうでない場合は拒否する。

２．

ＴＰＭは、

を計算する。これらの値は、ＴＰＭの長期秘密値として使用することができる。ＴＰＭは、例えば、ＴＭＰの外部にこのような秘密値の暗号化されたバージョンのみを記憶して、このような秘密値を安全に記憶する必要がある。

署名を行うために、ＴＰＭは、ｂ_ｉ∈_Ｒ（１，ｎ−１］（０≦ｉ≦１５）をランダムに選んで、以下を計算する。

ｖ＝Ｈ（ｈ，ｋ，ｈ_０，ｈ_１，…，ｈ_１６，ｆ_０，ｆ_１，…，ｆ_１５，ｇ_０，ｇ_１，…，ｇ_１６）
ｓ_ｉ＝ｂ_ｉ−ｒ_ｉ＊ｖ ｍｏｄ ｎ （０≦ｉ≦１５）

ＴＰＭは、

の構造に対する署名として以下のデータを刻む。

ｈ_ｉ（０≦ｉ≦１６），ｖ，ｓ_ｉ（０≦ｉ≦１５）

この署名を検証するために、検証者は以下を計算する。

ｖ'＝Ｈ（ｈ，ｋ，ｈ_０，ｈ_１，…，ｈ_１６，ｆ_０'，ｆ_１'，…，ｈ_１５，ｇ_０'，ｇ_１'，…，ｇ_１６'）
次に、検証者は、ｖ'？＝ｖをチェックする。

これらの署名の検証に基づいて、検証者は、以下を確信する。
（１）ＤＨ−ｓｉｇｎａｔｕｒｅから、検証者は、ｖのｆ_０'およびｇ_０'をチェックすることによって、

を確信する。

（２）ＤＨ−ｓｉｇｎａｔｕｒｅおよび（１）から、検証者は、ｖのｆ_ｉ'およびｇ_ｉ'をチェックすることによって、

を確信する。

（３）ＤＨ−ｓｉｇｎａｔｕｒｅおよび（１）から、検証者は、ｖのｆ_０'およびｇ_１６'をチェックすることによって、
ｃ∈（１，ｎ−１］，ｈ_０＝ｈ^ｃ ｍｏｄ Ｐ，ｙ＝ｈ_１６ ^ｃ ｍｏｄ Ｐ
を確信する。

（１）、（２）、および（３）から、検証者は以下を確信する。

および

のそれぞれに対する２つの検証が成功した後、検証者としての検証者は、その結果、

である場合に、

の構成を容認することができる。ＴＰＭは、その結果、自身が、証明ｃを有する秘密値ｍを有することを検証者に直接証明したことになり、ｍの値もｃの値も明らかにすることなくそれを行ったことになる。ここで、

である。

２０４８ビットに近い出力サイズを有するハッシュ関数Ｈを実施するのに特に適した方法は、既知のハッシュアルゴリズムＳＨＡ−１（その理由は、ＳＨＡ−１は、現在、従来のＴＰＭにすでに使用されているからである）を、結果を結合して１２回使用することである。すなわち、Ｈ（ｘ）＝ＳＨＡ−１（ｘ＋１）‖ＳＨＡ−１（ｘ＋２）‖…‖ＳＨＡ−１（ｘ＋１２）である。ここで、‖は結合である。

本発明の一態様による直接証明方式のこの特別なケースでは、ｅ_１＝２^１６＋１、ｅ_２＝２、および｜Ｐ｜＝２０４８である。

の構成に署名するために、ＴＰＭは以下のことを行う必要がある。
１．２０４８ビットサイズを有する１８個の乱数を生成すること。
２．５４個が２０４８ビット長のモジュラスおよび指数を有し、１つが２０４８ビットのモジュラスおよび（ｌｏｇＫ）ビットの指数を有する５５個のＲＳＡモジュロ累乗法を計算すること。
３．２０４８ビットモジュラスを有する１７個の乗算モジュロ、１７個の減算モジュロ、および１つの除算モジュロを計算すること。
４．２４個のＳＨＡ−１関数と等価な２つのハッシュ関数を計算すること。
５．２１＊（ｌｏｇＰ）＋１９＊（ｌｏｇｎ）ビットのサイズであるほぼ８０ｋビットのサイズを有する署名を送ること。

例示の従来のＴＰＭは、２０４８ビットのＲＳＡ署名を５００ｍｓで計算することができる暗号アクセラレータを含む。ＴＰＭは、

の構造に１回署名するために、５５個のＲＳＡモジュロ累乗法を計算する必要がある。これには、約３０秒を要する。しかしながら、これは事前に計算することができ、したがって、ＴＰＭ−検証者の相互作用にとって許容できないオーバーヘッドを提供するものではない。

このような直接証明方式を使用してＴＰＭの同一性をＲＳＰに証明することは、システム全体の弱点であることから認証局を取り除くという明らかな利点を有するが、潜在的な不都合も伴う。この不都合は、ＴＰＭの秘密値の証明を取り消すことが直接的ではないことである（これは、従来技術では、ＣＡによって直接的に行うことができた。ＣＡは、単に、自身が許可した証明書を取り消さなければならないだけであった）。ＴＰＭは、自身が、信頼できる製造業者の証明書を有することをＲＳＰに確信させることができるが、ＲＳＰが特定のＴＰＭを見分けることを可能にしない。各ＲＳＰは、悪性ＴＰＭの自身のブラックリストを構築することができる（以下でさらに説明するように、直接証明方式によって、ＲＳＰは、自身が相互作用した或るＴＰＭを、自身が相互作用した他のＴＰＭと区別することが可能になるので）が、各ＲＳＰは、自身がそのＴＰＭについて知っているような情報を、別のＲＳＰ（または他の任意の関係者）に役立つように転送することはできない。そのＲＳＰ自身のブラックリストを他の任意のブラックリストと一致させる方法はない。その理由は、ＲＳＰは、ＴＰＭの識別情報を知らず、関連した転送可能なデータを有しないからである。攻撃者が、例えば、或るＴＰＭを物理的に破壊することによって、或る識別情報を得た場合、その攻撃者は、この識別情報の記録を自身のブラックリストに有していなかったＲＳＰに、この識別情報が正当であることを確信させることができる。

定義によれば、悪性プラットフォームの秘密プリミティブが適法なコミュニティに明らかにされていない限り、直接証明方式の使用によって、グローバルに分散された取り消しリストを作成することは不可能である。信頼できるプラットフォームが使用される場合、これが発生する可能性は低い。したがって、どの所与のプラットフォームも、他のプラットフォームの悪い経験から直接学習することはできないと仮定することができる。したがって、ピアツーピアアーキテクチャが高度化した将来の世界では、抽出されたプリミティブが適法なコニュニティに知られていない限り、たとえプラットフォームが悪性ＴＰＭの突発的な発生があったことを知っても、そのプラットフォームには、（新しいウィルス定義と類似した）新しい「悪性の定義（rogue definition）」を与えることができず、それらの悪性のものを検出することはできない。したがって、ネットワーク全体が、信頼が破壊される不安のためにシャットダウンするおそれがある。プリミティブがブラインド方式を通じて作成されている（製造業者でさえもそれらプリミティブを知らず、したがって、どのＴＰＭになりすますこともできないようになっている）場合、この問題ははるかに深刻なものになる。

直接証明方式の目的は、識別情報の相関を防止することであるので、この問題は、直接証明方式にとって基本的なものである。直接証明方式が有効である場合、或る関係者が、第２の関係者の対応するものが第１の関係者の対応するものでもあることを当該第２の関係者が認識することを可能にする情報を当該第２の関係者に与えることは不可能である。したがって、ＴＰＭが破壊され、その秘密プリミティブが抽出されて、ＴＰＭのソフトウェアシミュレーションに複製された場合、それら抽出されたプリミティブが、悪性コミュニティだけでなく、適法なコミュニティにも知られない限り、分散リストにそのＴＰＭを列挙することは不可能である。

したがって、本発明のさらに別の態様では、改良されたシステムアーキテクチャが提案される。このシステムアーキテクチャは、たとえ、ＴＰＭがその証明書をＲＳＰに明らかにすることなく、かつ、取り消しを行う認証局がＴＰＭの保証識別情報（endorsement identity）を所有する必要なく、当該ＴＰＭがＲＳＰに対する正当に形成された証明書を有するという直接証明を、当該ＴＰＭが提供するように適合されていても、有効な取り消しを可能にするものである。このシステムは、上記で説明した直接証明の形態に関して説明される。しかし、このアーキテクチャは、一般に、任意の構成に適用可能であることが理解されるべきである。この任意の構成とは、ＴＰＭが検証者に対する正当に形成された証明書を検証者に明らかにしない状態で当該ＴＰＭがその証明書を有するという直接証明を提供するように、ＴＰＭが適合される構成である。また、上記で使用された特定の直接証明が以下で参照される場合、このような参照は、この態様における本発明を越えることなく、他の任意の直接証明への参照に置き換え可能であることが理解されるべきである。

システムは、図７に示すように、ＴＰＭ製造業者６１、ＴＰＭ６２、認証局（ＣＡ）６３、およびＲＳＰ６４の４組のエンティティを含む。ＣＡ６３は、取り消し局の役割も果たす。

上述したように、例示の直接証明方式を実施するために、各ＴＰＭ製造業者は、パラメータｎ、Ｋ、Ｐ、ｅ_２、ｅ_２、ｄ_１、ｔ_１、およびｔ_２を有する。ここで、ｎ、Ｋ、Ｐ、ｅ_２、ｅ_２、ｔ_１、およびｔ_２は公開パラメータであり、ｄ_１はプライベートパラメータである。各ＴＰＭは、

を満たす秘密パラメータｍおよびｃを有する。異なる直接証明方式が使用される場合、ＴＰＭ製造業者およびＴＰＭは、異なるパラメータを使用することができる。

この構成では、各ＣＡは、従来の非対称鍵対Ｐ_ＣＡおよびＳ_ＣＡを有する。また、各ＣＡは、複数の公開識別情報ＩＤ_ＣＡも有する。これらの公開識別情報ＩＤ_ＣＡは、特定の目的Ｐ_Ａの識別情報と結合したＣＡの公開名ｎ_ＣＡ、すなわちＩＤ_ＣＡ＝ｎ_ＣＡ‖Ｐ_Ａとすることができる。各ＲＳＰは、Ｐ_ＣＡの認証されたバージョンを有する。

対象となるシナリオでは、信頼できるプラットフォームデバイス（ＴＰＭ）は、リモートサービスプロバイダ（ＲＳＰ）と通信して、目的（本明細書では、１群の指定されたサービス）Ｐ_Ａにアクセスする必要があり、認証局（ＣＡ）は、ＲＳＰによって信頼されて、Ｐ_Ａの証明書を発行し、Ｐ_Ａにアクセスすることを可能にすべきでないＴＰＭのブラックリストを保持する。これは、次のようにして行うことができる。

ＴＰＭは、まず、従来の非対称鍵対Ｐ_ＴＰＭおよびＳ_ＴＰＭ（例えば、ＲＳＡ鍵対）を作成し、次いで、ｍおよびｃの秘密値に基いて、

の構造に署名する。
上述したように、これを行うために、ＴＰＭは、ｈをランダムに選び、ｘおよびｙを計算し、２つ署名

および

を行う。
ここで、

であり、

である。
ＴＰＭは、ｘおよびｙを含む署名をＰ_ＴＰＭと共にＣＡに送る。ＣＡは、署名の検証が成功した後、ＴＰＭが、

を満たす対（ｍ，ｃ）を有すること、および、所与のｈおよびｘが

を満たすことを確信する。
これは、単に、上述した直接証明方式を、ＴＰＭによる証明およびＲＳＰによる検証にさらに使用したものにすぎないことに留意されたい。ここでの唯一の重要な相違は、検証がＣＡによるということである。また、この結果として、このステップを実行するのに、他の任意の有効な直接証明方式を使用できることになる。

ＣＡは、次に、ＴＰＭにＩＤ_ＣＡを送る（オプションとして、ＴＰＭは、信頼できるパブリックドメインからのＩＤ_ＣＡに簡単にアクセスすることができる）。ＴＰＭは、ｈ_ＣＡ＝Ｈ（ＩＤ_ＣＡ）および

となるようなｈ_ＣＡおよびｘ'を計算する。ＴＰＭは、上述したようなＤＨ−ｓｉｇｎａｔｕｒｅ（ｈ，ｈ_ＣＡ，ｘ，ｘ'）を計算し、この署名をＣＡに送る。ＣＡは、まず、ＤＨ−ｓｉｇｎａｔｕｒｅ（ｈ，ｈ_ＣＡ，ｘ，ｘ'）を検証する。この検証が成功しない場合、ＣＡは、ＴＰＭの証明書の要求を拒否する。そうでない場合、ＣＡは、ｘ'がブラックリストにあるかどうかをチェックする。ｘ'がブラックリストにある場合、ＣＡは、このＴＰＭも拒否する。そうでない場合、ＣＡは、（ＴＣＧ仕様の現在のバージョンにおけるプライベートＣＡと同じように）Ｐ_ＣＡおよびＳ_ＣＡを通常の方法で使用することによってＰ_ＴＰＭを証明し、ｘ'およびＰ_ＴＰＭの証明書を記録する。これを管理する適切な方法は、ＣＡが、内部アクセスのみのためにｘ'をＰ_ＴＰＭと共に記録し、公にアクセスできる取り消しリストにＰ_ＴＰＭを列挙することである。

この場合も、ＤＨ−ｓｉｇｎａｔｕｒｅを使用する直接証明方式に対する代替的な直接証明方式を、本発明のこの態様の範囲から逸脱することなく、ここでも使用できることに留意すべきである。必要なことは、ＣＡが、ＴＰＭに発行された証明書を有するそれらＴＰＭのリストを自ら確立できるように、直接証明方式のプロセスが、ＴＰＭ秘密値を表すｘ'等の値を、その秘密値を明らかにすることなく生成できることだけである。

ＴＣＧ仕様の現在のバージョンと同じように、ＴＰＭは、ＲＳＰによって提供されたＰ_Ａのグループのサービスにアクセスするために、Ｐ_ＴＰＭの証明書でＲＳＰに対して自身を認証する。ＲＳＰは、その証明書を検証し、また、この証明書がＣＡの取り消しリストにあるかどうかもチェックする。例えば、これは、従来の証明書取り消しリスト（ＣＲＬ（Certificate Revocation List））を使用することによって行うことができる。

ＣＡは、一般に、自身が発行した証明書Ｐ_ＴＰＭを、例えば、ＴＰＭ識別情報が正当でないか、または、正当であるべきでないことが明らかであるような方法で、これらの証明書が特定のサービスにアクセスするのに使用されたＲＳＰ（または、悪性ＴＰＭと相互作用した他の関係者）から受け取ることによって悪性ＴＰＭを知ることになる。ＣＡは、次に、証明書Ｐ_ＴＰＭを、関連したＴＰＭの検証で提供された関連したｘ'と照合することができる。証明書Ｐ_ＴＰＭは、次に、ＣＲＬに置くことができる。悪性ＰＴＭは、ｘ'の同じ値が検証プロセス中に生成されることになるので、さらなる証明書を得ることができない。上述したように、ＣＡは、検証中にこれを検出し、悪性ＰＴＭへの証明書の提供を拒否する。

＜第２の方式＞
上述したように、第２の方式は、取り消し証を有するグループ署名方式である。以下で説明するように、説明する特定の方式は、Advances in Cryptology - CRYPT 2000, LNCS 1880, pp. 255-270, Springer-Verlag, 2000のG. Ateniese、J. Camenisch、M. Joye，およびG. Tsudik著「A practical and provably secure coalition-resistant group signature scheme」に記載された方式をさらに発展させたバージョンである。以下で述べる方式では、各ＴＰＭは、一意の保証鍵ｚ、および、ｕ^ｅ＝ａ^ｚｂ ｍｏｄ ｎを満たす対応する鍵証明書（ｕ，ｅ）を有する。ここで、（ａ，ｂ，ｎ）は、ＴＰＭ製造業者の公開パラメータであり、ｎはＲＳＡモジュラスであり、ａおよびｂはランダムに選ばれた整数である。この方式のセキュリティは、強ＲＳＡ仮定および決定的（decisional）Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定に基づいている。このグループ署名方式は、特に効率的であり、Ateniese他（上記参照）のランダムオラクルモデルの既存のセキュリティ証明からの利益を得る。

取り消し証を生成する特性を有する一般的なグループ署名方式を次に説明することにする。この一般的な方式は６つのプロシージャを含む。

ＳＥＴＵＰ（セットアップ）：セキュリティパラメータ１の入力に対して、この確率的アルゴリズムは、グループ公開鍵ＰＫ（すべてのシステムパラメータを含む）およびグループメンバーシップ証明書発行者（ＣＩ）用のグループ秘密鍵ＳＫを出力する。

ＪＯＩＮ（ジョイン）：或るユーザが新たなグループメンバになる、ＣＩとそのユーザとの間のプロトコル。このユーザの出力は、メンバーシップ秘密値およびメンバーシップ証明書である。

ＲＥＶＯＣＡＴＩＯＮ ＥＶＩＤＥＮＣＥ ＣＲＥＡＴＥ（取り消し証作成）：グループ公開鍵、メンバーシップ秘密値、メンバーシップ証明書、および取り消しパラメータの入力に対して、取り消し証を出力する確率的アルゴリズム。

ＳＩＧＮ（署名）：グループ公開鍵、メンバーシップ証明書、メンバーシップ秘密値、取り消し証、およびメッセージｍの入力に対して、取り消し証を有するｍのグループ署名を出力する確率的アルゴリズム。

ＶＥＲＩＦＹ（検証）：グループ公開鍵および取り消しパラメータに関して、取り消し証を有するメッセージの主張されたグループ署名の正当性を立証するためのアルゴリズム。

ＲＥＶＯＣＡＴＩＯＮ（取り消し）：グループ署名から取り消しリストに取り消し証を列挙するためのアルゴリズム。

このタイプの好ましい方式では、以下の特性がすべて満たされるべきである。
正当性（correctness）。ＳＩＧＮを使用してグループメンバにより生成された署名は、ＶＥＲＩＦＹによって容認されなければならない。
偽造不能性（unforgeability）。グループメンバのみが、グループを代表してメッセージに署名することができる。
匿名性（anonymity）。或るメッセージの正当な署名が与えられると、実際のグループメンバを特定することは、そのグループメンバーシップ証明書発行者を含めてあらゆる者にとって計算が困難である。
リンク可能性（linkability）。異なる取り消し証を有する２つの異なる正当な署名が同じグループメンバによって計算されたかどうかを判断することは計算が困難である。しかしながら、２つの異なる正当な署名が同じ取り消し証で計算されたかどうかを判断することは容易である。
トレース可能性／取り消し可能性（traceability/revocability）。グループメンバ秘密値およびそのメンバーシップ証明書が公開されると、あらゆる者が、この秘密値および証明書に基づいて署名された正当な署名を開くことができる。グループメンバ秘密値およびメンバーシップ証明書がないと、誰も、実際のグループメンバに対する正当な署名をトレースすることができない。しかしながら、誰もが取り消し証に対する任意のグループ署名をトレースすることができ、したがって、取り消し証により対処される指定された利用目的に対するグループメンバーシップは、取り消すことができる。
結託耐性（coalition-resistance）。グループメンバの共謀した一部（グループ全体で構成された場合でも）は、特別なグループメンバ秘密値および対応する正当なメンバーシップ証明書に基づいて署名された正当な署名を生成することができない。

１対のメンバ秘密値およびメンバーシップ証明書を得た攻撃者がいると、その攻撃者は、多くの「正当な」コピーを作成できることは明らかである。グループメンバの一般的な署名機能は、そのグループメンバ秘密値およびそのメンバーシップ証明書が公開されない限り、取り消すことができない。一方、取り消し証を有するグループ署名は、メンバーシップ証明書のトレース可能性を有しないグループ署名であるが、取り消し証に関するメンバーシップのトレース可能性は存在する。グループ署名（特定の目的でのグループメンバによる署名）の特定の使用のための取り消し証は、特定のグループメンバ秘密値およびメンバーシップ証明書ならびに目的にとって一意である。したがって、特定の目的での取り消し証とグループ署名との間のリンクは、一般に検証可能である。したがって、出願人は、秘密値または証明書の取り消しの通常の方法の取り消し手法の上下に取り消し手法を構築することができる。

本方式を達成するための修正を説明する前に、Ateniese他のグループ署名方式（「ＡＣＪＴ署名方式」）を次に述べることにする。

グループ管理者（ＧＭ）は、公開鍵ＰＫ＝（ｎ，ａ，ｂ，ｇ，ｈ，ｙ，ｌ，Γ，Δ）を有する。ここで、ｎは２つの安全な素数ｐとｑとの積であり、ａ、ｂ、ｇ、ｈ、およびｙは、平方剰余モジュロｎであり、ｌはセキュリティパラメータであり、ΓおよびΔは２つの区間である。ＧＭは、対応するプライベート鍵ＳＫ＝（ｐ，ｑ，ｘ）を有する。ここで、ｐおよびｑは、グループメンバーシップ証明書を発行するのに使用され、ｘ＝ｌｏｇ_ｇｙは、メンバーシップ取り消しに使用される。

グループメンバＰ_ｉは、メンバーシップ秘密値ｚ_ｉ、および、

を満たすメンバーシップ証明書（ｕ_ｉ，ｅ_ｉ）を有する。値ｚ_ｉは、適切な整数範囲ΔからＰ_ｉおよびＧＭによって共同で選択される。値ｚ_ｉは、（１）ＧＭがこの値に関する情報を得ないこと、ならびに、（２）Ｐ_ｉおよびＧＭの双方が、互いが自身の貢献を正しく行わなければならないことを検証できること、を保証する安全な方法で選択される。値ｅ_ｉは、別の適切な範囲ΓからＧＭによって選択された素数である。ＧＭは、Ｐ_ｉを特定するために（ｕ_ｉ，ｅ_ｉ）の記録を保持する。

Ｐ_ｉがグループを代表してメッセージに署名する時、Ｐ_ｉは、グループにおけるメンバーシップを証明する。これを行うために、Ｐ_ｉは、（ｚ_ｉ，ｕ_ｉ，ｅ_ｉ）を知っていることを効果的に証明する。例えば、グループを代表してメッセージｍに署名するために、Ｐ_ｉは、まず、ｗ∈_Ｒ｛０，１｝^２ｌを選び、Ｔ_１＝ｕ_ｉｙ^ｗ ｍｏｄ ｎ、Ｔ_２＝ｇ^ｗ ｍｏｄ ｎ、および

を計算する。
次に、Ｐ_ｉは、ｂ＝Ｔ_１ ^αａ^−βｙ^−χ ｍｏｄ ｎ、１＝Ｔ_２ ^αｇ^−χ ｍｏｄ ｎ、Ｔ_２＝ｇ^δ ｍｏｄ ｎ、およびＴ_３＝ｇ^αｈ^δ ｍｏｄ ｎがメッセージｍで維持されるような整数α、β、χ、およびδを知っていることの署名を作成する。ここで、α∈Γであり、β∈Δである。［ＣＳ９７］におけるCamenischおよびStadlerによって導入された表記法を使用することによって、この署名は次のように表記することができる。
ＰＫ［（α，β，χ，δ）：ｂ＝Ｔ_１ ^αａ^−βｙ^−χ∧１＝Ｔ_２ ^αｇ^−χ∧Ｔ_２＝ｇ^δ∧Ｔ_３＝ｇ^αｈ^δ∧α∈Γ∧β∈Δ］（ｍ）

この署名を検証することによって、検証者は以下を確信する。
ａ^βｂ＝Ｔ_１ ^αｙ^−χ＝Ｔ_１ ^αｙ^−αδ＝（Ｔ_１ｙ^−δ）^α ｍｏｄ ｎ
さらに、

このグループ署名は、
（１）

が、ｅ_ｉ乗根を有する値であるような値ｚ_ｉ∈Δ、および、
（２）

が、ｙに基づいて（Ｔ_１，Ｔ_２）でＥ１Ｇａｍａｌ暗号化されたものであるようなそのｅ_ｉ乗根、を知っていることの署名とみなすことができる。ここで、ｅ_ｉは、Ｔ_３ｗ．ｒ．ｔ．ｇおよびｈの表現の最初の部分であり、そのｅ_ｉはΓに存在する。

すべてのグループ署名方式と同様に、ＧＭは、Ｅ１Ｇａｍａｌ解読鍵ｘを有し、したがって、ＧＭがＰ_ｉを特定する値ｕ'＝Ｔ_１／（Ｔ_２）^ｘ＝ｕ_ｉを計算できるので、ＧＭのみが、Ｐ_ｉに対する署名を行使することができる。

取り消し証を有するグループ署名方式を提供するためのこの方式に対する修正を次に説明することにする。関与する関係者およびプロセスが図８（取り消し局を使用するバージョンについて）および図９（取り消し局を使用しないバージョンについて）に概略的に示されている。この新しい方式は、ＡＣＪＴグループ署名方式に対して以下の３つの変更を行う。

１．出願人は、ＴＰＭ８２自身を除くどのエンティティにも、保証鍵証明書を署名から取り出すことを可能にしない。そうでない場合には、このエンティティは、匿名性を破る可能性がある。したがって、出願人は、ＧＭのメンバーシップの開く機能を削除し、証明書発行機能のみを維持する。出願人は、このエンティティを保証鍵証明書発行者（ＣＩ）と呼ぶ。ＣＩ８１は、本物のＴＰＭの製造業者であることが好ましい。
２．特定の目的でのグループ署名の取り消しを可能にするために、出願人は、グループメンバ８２が、例えば、その特定の目的の取り消しを専門とする取り消し局８３を使用して、その特定の目的で、自己証明した取り消し証を作成することを必要とする。この取り消し局８３は、同じ利用目的の同じＴＰＭ保証鍵および鍵証明書に基づいて署名された異なる署名を相関させることができる。代替的に、悪性ＴＰＭの検出者がこのような情報を公に（または、そうでない場合には適切に）利用可能にすると、検証者は自身の取り消しリストを保持することができる。
３．出願人は、ＴＰＭ保証鍵の作成およびその証明書の発行を行うプロセスを簡単化する。ＡＣＪＴグループ署名は、ＧＭおよびＰ_ｉが、互いが適切にこの方式を実行するものと信頼できない場合の利用向けに設計されている。このＴＣＧの利用では、このプロセスは、本物のＴＰＭの製造中に行われ、ＴＰＭ製造業者であるＣＩがそれらによって作成されたＴＰＭを信頼することは当然である。

検証者８４は、ＴＰＭの真正性を立証する必要のある任意の関係者とすることができ、通常、これは、リモートサービスプロバイダ（ＲＳＰ）となる。

次に、出願人は、上記例示で一般的に説明した６つのプロシージャでこの方式を説明する。

１．セットアップ（ステップ８０１）
システムを開始するために、アーキテクチャ全体の定義者は、次のように動作する。
１．パラメータεが統計的なゼロ知識の堅固さ（tightness）を適切に制御でき、パラメータｌが、使用するモジュラスのサイズのセキュリティ要件の必要性を満たすようなε＞１、ｋ、およびｌをセキュリティパラメータとして選ぶ。
２．λ_１＞ε（λ_２＋ｋ）＋２、λ_２＞４ｌ、およびγ_１＞ε（γ_２＋ｋ）＋２、γ_２＞λ_１＋２を満たすλ_１、λ_２、γ_１、およびγ_２を長さとして選ぶ。整数範囲Δ＝］２^λ１−２^λ２，２^λ１＋２^λ２［およびΓ＝］２^γ１−２^γ２，２^γ１＋２^γ２［を定義する。
３．衝突困難ハッシュ関数Ｈ：｛０，１｝^＊→｛０，１｝^ｋを選ぶ。

ＴＰＭ製造業者（ＣＩと呼ぶ）をセットアップするために、ＣＩは、以下のように動作することによって、自身の公開鍵（ｎ，ａ，ｂ，ｇ，ｙ，ｈ）および対応するプライベート鍵（ｐ'，ｑ'）を作成する。
１．ｐ＝２ｐ'＋１およびｑ＝２ｑ'＋１が素数となるようなランダムな秘密のｌビット素数ｐ'、ｑ'を選択する。モジュラスｎ＝ｐｑを設定する。
２．ランダムな要素ａ'、ｂ'、ｃ'∈_ＲＺ_ｎ ^＊を選択し、ｇ'＝Ｈ（ｃ'‖１）、ｙ'＝Ｈ（ｃ'‖２）、およびｈ'＝Ｈ（ｃ'‖３）を計算し、ｇｃｄ（ａ'±１，ｎ）＝１、ｇｃｄ（ｂ'±１，ｎ）＝１、ｇｃｄ（ｇ'±１，ｎ）＝１、ｇｃｄ（ｙ'±１，ｎ）＝１、およびｇｃｄ（ｈ'±１，ｎ）＝１が維持されるかどうかをチェックし、チェックが成功すると、ａ＝ａ'^２ ｍｏｄ ｎ、ｂ＝ｂ'^２ ｍｏｄ ｎ、ｇ＝ｇ'^２ ｍｏｄ ｎ、ｙ＝ｙ'^２ ｍｏｄ ｎ、およびｈ＝ｈ'^２ ｍｏｄ ｎを計算し、そうでない場合は、「すみません。私はあなたのモジュラスを因数分解した。」をＣＩに報告する。これは、ａ、ｂ、ｇ、ｙ、ｈ∈位数（order）ｐ'ｑ'のＱＲ（ｎ）を保証し、また、誰も、ｎを法とする、ｙ（ｈまたはｇ）の離散対数ｗ．ｒ．ｔ．底ｇまたはｈ（ｇもしくはｙ、または、ｈもしくはｙ）を知らないことを保証する。

ＣＩの公開鍵は、通常の手段を介して利用可能にされる（すなわち、信頼できる局によって署名された或る形態の公開鍵証明書に実施される）。実際には、フレーム攻撃（framing attack）を防止するために、この公開鍵を証明する前に、信頼できる局は、（ｎ，ａ，ｂ，ｇ，ｙ，ｈ）の構成要素を検証しなければならない。詳細には、（１）ＣＩは、ｎが２つの安全な素数の積であることの証明を信頼できる局に提供する必要があり、（２）ＣＩは、ａ'、ｂ'、およびｃ'を信頼できる局に送信し、信頼できる局は、次に、ｇｃｄ（ａ'±１，ｎ）＝１、ｇｃｄ（ｂ'±１，ｎ）＝１、ｇｃｄ（Ｈ（ｃ'‖１）±１，ｎ）＝１、ｇｃｄ（Ｈ（ｃ'‖２）±１，ｎ）＝１、およびｇｃｄ（Ｈ（ｃ'‖３）±１，ｎ）＝１が維持されることをチェックし、ａ＝ａ'^２ ｍｏｄ ｎ、ｂ＝ｂ'^２ ｍｏｄ ｎ、ｇ＝Ｈ（ｃ'‖１）^２ ｍｏｄ ｎ、ｙ＝Ｈ（ｃ'‖２）^２ ｍｏｄ ｎ、およびｈ＝Ｈ（ｃ'‖３）^２ ｍｏｄ ｎを計算する。

２．ジョイン（ステップ８０２）
ＴＰＭ（ＴＰＭと呼ぶ）をＴＰＭグループのメンバにするための、従うことができる複数の可能な手法が存在する。一例示の形態では、ＴＰＭおよびＣＩは次のように動作することができる。
１．ＴＰＭは、秘密指数ｚ∈_ＲΔを自身の保証鍵として生成し、ｖ＝ａ^ｚ ｍｏｄ ｎを計算し、ｖをＣＩに送る。
２．ＣＩは、ランダムな素数ｅ∈_ＲΓを選択し、ｕ＝（ｖｂ）^１／ｅ ｍｏｄ ｎを計算することによって保証鍵証明書（ｕ，ｅ）を発行する。ＣＩはＴＰＭに（ｕ，ｅ）を記憶する。

特に、ＣＩとＴＰＭとの間のタスクの分割においては、ジョインプロセスの多くの可能な代わりの形態が存在することに留意すべきである。以下の３つのバージョンは例示である。

バージョン１．
１．ＣＩは、指数ｚ∈_Ｒ］１，２^ｌ２］をＴＰＭの保証プライベート鍵としてランダムに選択し、ｖ＝ａ^ｚを計算する。
２．ＣＩは、ランダムな素数

を選択し、ｕ＝（ｖｂ）^１／ｅを計算することによって保証鍵証明書（ｕ，ｅ）を生成する。
３．ＣＩはＴＰＭに（ｚ，ｕ，ｅ）を記憶する。
４．ＣＩは、（ｚ，ｕ，ｅ）の自身の知識のすべてを消去する。

バージョン２．
１．ＴＰＭは、秘密指数ｚ∈_Ｒ］１，２^ｌ２］を自身の保証プライベート鍵として生成し、ｖ＝ａ^ｚを計算し、ｖをＣＩに送る。
２．ＣＩは、ランダムな素数

を選択し、ｕ＝（ｖｂ）^１／ｅを計算することによって保証鍵証明書（ｕ，ｅ）を発行する。
３．ＣＩはＴＰＭに（ｕ，ｅ）を記憶する。
４．ＣＩは、（ｕ，ｅ）の自身の知識のすべてを消去する。

バージョン３．
１．ＴＰＭは、秘密指数ｚ∈_Ｒ］１，２^ｌ２］を自身の保証プライベート鍵として生成する。
２．ＴＰＭは、ｖ＝ａ^ｚを計算する。
３．ＴＰＭは、ランダムな素数

を選択する。
４．ＴＰＭは、一時的な秘密値（ｐ'，ｑ'）をインポートし、ｄ＝１／ｅ ｍｏｄ ４ｐ'ｑ'を計算する。
５．ＴＰＭは、ｕ＝（ｖｂ）^ｄを計算する。
ＴＰＭは、（ｐ'，ｑ'）の自身の知識のすべてを消去する。

このジョインプロセスにおいて、出願人は以下のことを仮定することに留意されたい。
・ＴＰＭとＣＩとの間の通信は安全である。すなわち、プライベートであり、かつ、信頼できる。
・ＣＩは、ＴＰＭが秘密値ｚを正確に選択することを確信する。そうでない場合、ＣＩおよびＴＰＭは、Ateniese他（上記参照）に記載されたＪＯＩＮプロトコルを実行しなければならない。ここで、ｚは、ＴＰＭおよびＣＩによって共同で選択される。
・ＴＰＭも、ＣＩが証明書を正確に計算することを確信する。そうでない場合、ＴＰＭは、（ｕ，ｅ）の受信後、ｕ^ｅ＝ａ^ｚｂ ｍｏｄ ｎかどうかを検証することになる。

３．取り消し証作成（ステップ８０３）
これは、取り消し局を使用するモデルに関して説明することにする。しかしながら、この手法を使用すると、どの対応するものも、取り消し局として動作することができ、したがって、各検証者は、自身の取り消しリストを保持することが可能であることに留意することができる。これを効果的に行うために、検証者（または、システムの全体としての効果的なオペレーションの望ましさに関心のある他の関係者）は、自身の取り消しリストに追加されるべき詳細に気付くと、これら詳細を他の潜在的な検証者に利用可能にする。各取り消し局は、一意の名前である取り消し局名（RevocationAgencyName）を有するものと仮定する。この一意の名前は、利用目的識別情報、属性、取り消し局の情報、および或るランダム性で生成することができる（このタイプの名前は、取り消し局の情報がなくても生成することができ、単に、この名前がどの種類の取り消し情報であるかを特定する情報とすることができ、したがって、明示的な取り消し局のないモデルでこの名前を使用することが可能であることに留意することができる）。取り消し証ｗ．ｒ．ｔ．この名前は、以下のように動作することによって作成される。２つの代替的なバージョンが以下に与えられる。

バージョン１
１．ＣＩの公開モジュラスｎ、ＴＰＭの保証プライベート鍵ｚ、および取り消し局名を入力する。
２．ｆ'＝Ｈ（取り消し局名）を計算し、ｇｃｄ（ｆ'±１，ｎ）＝１が維持されるかどうかをチェックし、チェックが成功した場合には、ｆ＝ｆ'^２を計算し、そうでない場合には、「すみません。私はあなたのモジュラスを因数分解した。」をＣＩに報告する。
２'．代替的に、ＴＰＭが、取り消し局名を与えられて、偶然にｆを生成した場合、ＴＰＭは、単純にｆ＝Ｈ（取り消し局名）^２を計算する。ｇｃｄ（ｆ'±１，ｎ）≠１となる確率は無視できる。
３．取り消し証Ｅ＝ｆ^ｚを計算する。
４．（ｆ，Ｅ）を出力する。

バージョン２
１．ＣＩの公開パラメータａおよびモジュラスｎ、ならびに、取り消し局名を入力する。また、ＴＰＭの保証プライベート鍵ｚも入力する。
２．ｆ'＝Ｈ（取り消し局名）を計算し、ｇｃｄ（ｆ'±１，ｎ）＝１が維持されるかどうかをチェックし、チェックが成功した場合には、ｆ＝ｆ'^２ ｍｏｄ ｎを計算し、そうでない場合には、「すみません。私はあなたのモジュラスを因数分解した。」をＣＩに報告する。
２'．代替的に、ＴＰＭが、取り消し局名を与えられて、偶然にｆを生成した場合、ＴＰＭは、単純にｆ＝Ｈ（取り消し局名）^２ ｍｏｄ ｎを計算する。ｇｃｄ（ｆ'±１，ｎ）≠１となる確率は無視できる。
３．取り消し証Ｃ＝（ａｆ）^ｚ ｍｏｄ ｎを計算する。
４．（ｆ，Ｃ）を出力する。

離散対数の仮定に基づくと、すべてｎを法とする、底ｇまたはｙもしくはｈに対するｆの離散対数、および、底ｆに対するｇまたはｙもしくはｈの離散対数を誰も知らないということが仮定されることに留意されたい。

４．署名（ステップ８０４）
保証鍵ｚおよび保証鍵証明書（ｕ，ｅ）を知っていることを証明するために、ＴＰＭは、以下のように動作することによって、一般的なメッセージｍ∈｛０，１｝^＊上に、取り消し証を有するグループ署名を生成する。
１．ｗ∈_Ｒ｛０，１｝^２ｌをランダムに選ぶ。
２．Ｔ_１＝ｕｙ^ｗ ｍｏｄ ｎ、Ｔ_２＝ｇ^ｗ ｍｏｄ ｎ、およびＴ_３＝ｇ^ｅｈ^ｗ ｍｏｄ ｎを計算する。
３．ｒ_１∈_Ｒ±｛０，１｝^{ε（γ２＋ｋ）}、ｒ_２∈_Ｒ±｛０，１｝^{ε（λ２＋ｋ）}、ｒ_３∈_Ｒ±｛０，１｝^{ε（γ１＋２ｌ＋ｋ＋１）}、およびｒ_４∈_Ｒ±｛０，１｝^{ε（２ｌ＋ｋ）}をランダムに選ぶ。
４．ｄ_１＝Ｔ_１ ^ｒ１／（ａ^ｒ２ｙ^ｒ３） ｍｏｄ ｎ、ｄ_２＝Ｔ_２ ^ｒ１／ｇ^ｒ３ ｍｏｄ ｎ、ｄ_３＝ｇ^ｒ４ ｍｏｄ ｎ、ｄ_４＝ｇ^ｒ１ｈ^ｒ４ ｍｏｄ ｎ、およびｄ_５＝（ａｆ）^ｒ２ ｍｏｄ ｎを計算する。
５．ｃ＝Ｈ（ｇ‖ｈ‖ｙ‖ａ‖ｂ‖Ｔ_１‖Ｔ_２‖Ｔ_３‖Ｃ‖ｄ_１‖ｄ_２‖ｄ_３‖ｄ_４‖ｄ_５‖ｍ）を計算する。
６．ｓ_１＝ｒ_１−ｃ（ｅ−２^γ１）、ｓ_２＝ｒ_２−ｃ（ｚ−２^λ１）、ｓ_３＝ｒ_３−ｃｅｗ、およびｓ_４＝ｒ_４−ｃｗ（すべてＺにおいて）を計算する。
７．（ｃ，ｓ_１，ｓ_２，ｓ_３，ｓ_４，Ｔ_１，Ｔ_２，Ｔ_３，Ｃ）を出力する。

これは、第１の方式で使用したようなＳｃｈｎｏｒｒに類似した署名であり、この場合も、第１の方式の場合と同様に、署名は、オンライン時に必要とされる作業を最小にするために大部分は事前に計算することができる。この方式では、署名生成に、７個（または１１個）のモジュロ累乗法が必要とされ、出願人は、それらのうちの１個のみが事前に計算できないことに留意する。したがって、ｃ、ｓ_１、ｓ_２、ｓ_３、ｓ_４、およびｄ_４の計算のみが（ｍおよびＥの発見後に）オンラインで行われる。

最小のオンライン計算を有する従来の誰何／応答プロトコルの場合、出願人は、オンラインになる前に、４）におけるｄ_４の計算を除いて、ＴＰＭに上記項目１）〜４）を準備させる。後に誰何者（すなわち検証者）と通信する時に、その誰何者は、取り消し局に関する情報である取り消し局名および新たなメッセージｍを誰何として送る。ＴＰＭは、（既存の取り消し証を再利用できない場合に）取り消し証Ｅ＝Ｈ（取り消し局名）^２ｚ ｍｏｄ ｎを作成し、次いで、４）におけるｄ_４と共に項目５）〜７）を実行することによって署名を終了する。

代替的に、最小のＴＰＭストレージを作製するため、ｃ＝Ｈ（ｇ‖ｈ‖ａ‖ｂ‖Ｔ_１‖Ｔ_２‖Ｔ_３‖ｄ_１‖ｄ_２‖ｄ_３‖Ｅ‖ｄ_４‖ｍ）の代わりに、ＴＰＭは以下のようにｃを計算することができる。
ｃ_１＝Ｈ（ｇ‖ｈ‖ａ‖ｂ）
ｃ_２＝Ｈ（ｃ_１‖Ｔ_１）
ｃ_３＝Ｈ（ｃ_２‖Ｔ_２）
ｃ_４＝Ｈ（ｃ_３‖Ｔ_３）
ｃ_５＝Ｈ（ｃ_４‖ｄ_１）
ｃ_６＝Ｈ（ｃ_５‖ｄ_２）
ｃ_７＝Ｈ（ｃ_６‖ｄ_３）
ｃ_８＝Ｈ（ｃ_７‖Ｅ）
ｃ_９＝Ｈ（ｃ_８‖ｄ_４）
ｃ＝Ｈ（ｃ_９‖ｍ）

したがって、署名プロセスは、以下のように実施することができる。
１．ＴＰＭは、ａ、ｂ、ｇ、ｈ（３２０ビット）、ｎ（２０４８ビット）をインポートする。
２．ＴＰＭは、ｃ_１（１６０ビット）をインポートする。

オフライン計算
１．ＴＰＭは、ＴＰＭ特有の秘密値ｗ_１（１６０ビット）をＲＮＧから得る。
２．ＴＰＭは、ＴＰＭ特有の秘密値ｗ_２（１６０ビット）をＲＮＧから得る。
３．ＴＰＭは、ＴＰＭ特有の秘密値ｒ_１（３８０ビット）をＲＮＧから得る。
４．ＴＰＭは、ＴＰＭ特有の秘密値ｒ_２（３８０ビット）をＲＮＧから得る。
５．ＴＰＭは、ＴＰＭ特有の秘密値ｒ_３（３８０ビット）をＲＮＧから得る。
６．ＴＰＭは、ＴＰＭ特有の秘密値ｒ_４（３８０ビット）をＲＮＧから得る。
７．ＴＰＭは、ｗ_１、ｗ_２、ｒ_１、ｒ_２、ｒ_３、ｒ_４を新たな集合Ａの一部として記憶する。
８．ＴＰＭは、秘密でない値

を計算する。
９．ＴＰＭは、ｃ_２＝Ｈ（ｃ_１‖Ｔ_１）を計算する。
１０．ＴＰＭは、Ｔ_１をエクスポートする。
１１．ＴＰＭは、秘密でない値

を計算する。
１２．ＴＰＭは、ｃ_３＝Ｈ（ｃ_２‖Ｔ_２）を計算する。
１３．ＴＰＭは、Ｔ_２をエクスポートする。
１４．ＴＰＭは、秘密でない値

を計算する。（ｈ^ｅは１回だけ計算することができ、恒久的に秘密に記憶することができる。）
１５．ＴＰＭは、ｃ_４＝Ｈ（ｃ_３‖Ｔ_３）を計算する。
１６．ＴＰＭは、Ｔ_３をエクスポートする。
１７．ＴＰＭは、秘密でない値

を計算する。
１８．ＴＰＭは、ｃ_５＝Ｈ（ｃ_４‖ｄ_１）を計算する。
１９．ＴＰＭは、秘密でない値

を計算する。
２０．ＴＰＭは、ｃ_６＝Ｈ（ｃ_５‖ｄ_２）を計算する。
２１．ＴＰＭは、秘密でない値

を計算する。
２２．ＴＰＭは、ｃ_７＝Ｈ（ｃ_６‖ｄ_３）を計算する。
２３．ＴＰＭは、ｃ_７を集合Ａの一部として記憶する。

オンライン計算
１．ＴＰＭは、取り消し局名（任意の長さ）をインポートする。
２．ＴＰＭは、ｆ（３２０ビット）＝（Ｈ（取り消し局名））^２を計算する。
３．ＴＰＭは、ｆを集合Ａの一部として保存する。
４．ＴＰＭは、秘密でない値Ｅ（２０４８ビット）＝ｆ^ｚを計算する。
５．ＴＰＭは、ｃ_８＝Ｈ（ｃ_７‖Ｅ）を計算する。
６．ＴＰＭは、Ｅをエクスポートして、Ｅを消去する。
７．ＴＰＭは、

を生成する。
８．ＴＰＭは、ｃ_９＝Ｈ（ｃ_８‖ｄ_４）を計算する。
９．ＴＰＭは、ｄ_４を消去する。
１０．ＴＰＭは、誰何ｍ（任意の長さ）をインポートする。
１１．ＴＰＭは、秘密でない値ｃ_１０＝Ｈ（ｃ_９‖ｍ）を計算する。
１２．ＴＰＭは、ｃ＝ｃ_１０に設定する。
１３．ＴＰＭは、ｃを集合Ａの一部として保存する。
１４．ＴＰＭは、ｃをエクスポートする。
１５．ＴＰＭは、秘密でない値ｓ_１（３８０ビット）＝ｒ_１−ｃ＊（ｅ−２^４００）を計算する。
１６．ＴＰＭは、ｓ_１をエクスポートする。
１７．ＴＰＭは、秘密でない値ｓ_２（３８０ビット）＝ｒ_２＋ｃ＊ｚを計算する。
１８．ＴＰＭは、ｓ_２をエクスポートする。
１９．ＴＰＭは、秘密でない値ｓ_３（３８０ビット）＝ｒ_３−ｃ＊ｗ_２を計算する。
２０．ＴＰＭは、ｓ_３をエクスポートする。
２１．ＴＰＭは、秘密でない値ｓ_４（３８０ビット）＝ｒ_４＋ｃ＊ｗ_１を計算する。
２２．ＴＰＭは、ｓ_４をエクスポートする。
ＴＰＭは集合Ａを消去する。

５．検証（ステップ８０５）
検証者は、以下のように動作することによって、メッセージｍの署名（ｃ，ｓ_１，ｓ_２，ｓ_３，ｓ_４，Ｔ_１，Ｔ_２，Ｔ_３，Ｃ）の正当性をチェックする。このチェックには、取り消し証の第２のバージョンの例が使用されるが、第１のバージョンも、同様に適切に使用することができる。
１．Ｃが、信頼できる取り消し局によって保持された取り消しリストにあるかどうかをチェックする。この信頼できる取り消し局は、取り消し局名という名前を有する。このチェックがイエスである場合、署名を拒否し、そうでない場合、続行する。（上述したように、検証者は、このようなリスト自体を保持することができる。）
２．

を計算する。
３．ｃ＝ｃ'であり、かつ、ｓ_１∈±｛０，１｝^{ε（γ２＋ｋ）＋１}、ｓ_２∈±｛０，１｝^{ε（λ２＋ｋ）＋１}、ｓ_３∈±｛０，１｝^{ε（λ１＋２ｌ＋ｋ＋１）＋１}、およびｓ_４∈±｛０，１｝^{ε（２ｌ＋ｋ）＋１}である場合にのみ、署名を容認する。

６．取り消し（ステップ８０６）
いかなる理由であろうと、ＴＰＭが、取り消し局名によって特定された特定の目的で取り消されるべきである場合、Ｃは取り消しリストに置かれる。異なる実施の形態では、これは、取り消し局によって保持されたリストとすることもできるし、潜在的な検証者が自身のリストを保持するように、それら検証者に利用可能にすることもできる。

この方式のセキュリティを次に検討することにする。ＡＣＪＴグループ署名方式のセキュリティは、強ＲＳＡ仮定および決定的Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定に基づいている。

強ＲＳＡ仮定（例えば、Advances in Cryptology - EUROCRYPT '97, LNCS 1233, pp. 480-494, Springer-Verlag, 1997のN. BaricおよびB. Pfitzmann著「Collision-free accumulators and fail-stop signature schemes without trees」、Advances in Cryptology - CRYPTO '97, LNCS 1297, pp. 16-30, Springer-Verlag, 1997のE. FujisakiおよびT. Okamoto著「Statistical zero knowledge protocols to prove modular polynomial relations」を参照されたい）は、ｅが公開値であり、したがって一定の指数である場合にｎを法とするｅ乗根を見つけることが困難であるという広く容認されたＲＳＡ仮定を、任意のｅ＞１についてｎを法とするｅ乗根を見つけることが困難であるという仮定にまで強化したものである。

強ＲＳＡ問題の定義 − ｎ＝ｐｑを、ＲＳＡに類似したモジュラスとし、Ｇを、

である位数＃ＧのＺ_ｎ ^＊の巡回部分群とする。
ｎおよびｚ∈Ｇが与えられると、ストリングＲＳＡ問題は、ｚ≡ｕ^ｅ ｍｏｄ ｎを満たすｕ∈Ｇおよびｅ∈Ｚ_＞１を見つけることから構成される。

強ＲＳＡ仮定の定義 − 入力に対して、セキュリティパラメータｌ_Ｇが、すべての確率的多項式時間アルゴリズムＰについて、Ｐが強ＲＳＡ問題を解くことができる確率は無視できるような対（ｎ，ｚ）を出力する確率的多項式時間アルゴリズムＫが存在する。。

Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定（W. DiffieおよびM. E. Hellman著「New directions in cryptography」, IEEE Transactions on Information Theory, IT-22(6): 644-654, 1976）は、（ｉ）計算的Ｄｉｆｆｉｅ−Ｈｅｌｌｍｍａｎ仮定（ＣＤＨ（Computational Diffie-Hellmman Assumption）および（ｉｉ）決定的Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定（ＤＤＨ（Decisional Diffie-Hellman Assumption））の２つの「特徴」に現れる（Algorithmic Number Theory (ANTS-III), LNCS 1423, pp. 48-63, Springer-Verlag, 1998のD. Boneh著「The decision Diffie-Hellman problem」を参照されたい）。

決定的Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題の定義 − Ｇ＝＜ｇ＞を、

である位数＃Ｇのｇによって生成された巡回群とする。ｇ、ｇ^ｘ、ｇ^ｙ、およびｇ^ｚ∈Ｇが与えられると、決定的Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題は、要素ｇ^ｘｙおよびｇ^ｚが等しいかどうかを判断することから構成される。

この問題は、決定的Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定の元となるものである。このことは、それより前の暗号方式ですでに暗黙的に仮定されてはいたが、最初に明示的に述べたのはBrandsである（S Brands著「An efficient off-line electronic cash system based on the representation problem」, Technical Report CS-R9323, Centrum voor Wiskunde en Infomatica, April 1993）。

決定的Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定の定義 − 分布ＤとＲとを無視できない確率で区別する非確率的多項式時間アルゴリズムがある。ここで、Ｄ＝（ｇ，ｇ^ｘ，ｇ^ｙ，ｇ^ｚ）であり、ｘ，ｙ，ｚ∈_ＲＺ_＃Ｇであり、Ｒ＝（ｇ，ｇ^ｘ，ｇ^ｙ，ｇ^ｘｙ）であり、ｘ，ｙ∈_ＲＺ_＃Ｇである。

Ateniese他は、以下の２つの定理および１つの系を証明することによって、ＡＣＪＴグループ署名方式のセキュリティ証明を与える。

定理１（結託耐性）。強ＲＳＡ仮定の下では、ｘ_ｉ∈Δおよびｅ_ｉ∈Γであるグループ証明書

は、グループ管理者が発行したＫ個の証明書が多項式的に限定されているという条件で、グループ管理者のみが生成することができる。

定理２。強ＲＳＡ仮定の下では、グループ署名方式の基礎を成す対話型プロトコルは、メンバーシップ証明書および対応するメンバーシップ秘密鍵を知っていることの統計的ゼロ知識（正直な検証者）証明である。

系。ランダムオラクルモデルでは、ＡＣＪＴグループ署名方式は、強ＲＳＡ仮定および決定的Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定の下では安全である。

Ateniese他によるＡＣＪＴグループ署名方式のセキュリティ証明に基づくと、出願人は、ランダムオラクルモデルにおいて、前の節で提示された取り消し証を有するグループ署名方式が、強ＲＳＡ仮定および決定的Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定の下で安全であると主張することができる。

（上述したような）取り消し証を有する一般的なグループ署名方式のほとんどのセキュリティ特性は、上記２つの定理および１つの系から直接得られる。（ｃ，ｓ_１，ｓ_２，ｓ_３，ｓ_４，Ｔ_１，Ｔ_２，Ｔ_３）により明らかにされた、グループメンバの秘密値および証明書に関する情報の量は無視できる（すなわち、（ｃ，ｓ_１，ｓ_２，ｓ_３，ｓ_４，Ｔ_１，Ｔ_２，Ｔ_３）は統計的に隠蔽コミットメント（hiding commitment）であり、ＰＫプロトコルは統計的にゼロ知識である）ので、ＡＣＪＴグループ署名方式のすべての特性は維持されることに留意されたい。Ｃを開示することによりさらに明らかにされた、グループメンバの秘密値および証明書に関する情報の量も、決定的Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ仮定に基づいて無視できると主張することが残されている。

上記で提示された取り消し証を有する特定のグループ署名方式は効率的であり、ＡＣＪＴグループ署名方式が非常に効率的であることから利益を受ける。

通信：出願人の提案は、署名方式であって、対話型ゼロ知識証明方式ではない。反射攻撃を回避するために、検証者は、一意のメッセージｍを選ぶことができ、ｍを取り消し局名（これも検証者によって選ばれる）と共に、誰何として署名者に送ることができる。その後、署名者は、応答として署名を返信する。ＲＳＡモジュラスｎのサイズが、現在のＴＣＧ仕様で勧告された２０４８である場合、署名のサイズは９×ｌｏｇ（ｎ）＝４．５ｋビットである。

計算：署名を行うために、署名者は９つのモジュロ累乗法を必要とする。署名を検証するために、検証者は５つのモジュロ累乗法を必要とする。

ＴＰＭが９つのモジュロ累乗法を使用する必要があることによって、ＴＰＭの識別情報を検証するプロセスに時間遅延が導入される場合がある。この時間遅延は、ランダムに選ばれたデータに関するＴＰＭのグループ署名を事前に計算し、次いで、誰何／応答を使用して、その署名がＴＰＭによって生成されたことを証明することによって最小にすることができる。次に、この誰何／応答には、ＴＰＭによる２つのオンラインモジュロ累乗法、および、検証者による７つのオンラインモジュロ累乗法（元の５つに特別な２つを加えたもの）が必要とされる。ＤＰ方式と基本的に同じアイデアを使用すると、出願人は、存在しない取り消し局についてのランダムに選ばれたメッセージｍ'およびランダムに選ばれた取り消し局名'に対して上記方式を使用して、ＴＰＭにグループ署名を作成させる。その署名では、ｆ'＝Ｈ（取り消し局名'）^２ ｍｏｄ ｎであり、Ｃ'＝（ａｆ）^ｚ ｍｏｄ ｎである。後に、誰何者との実際の通信中に、誰何者は、実際の取り消し局に関する情報である取り消し局名、および、新たなメッセージｍを誰何として送る。次に、ＴＰＭは、実際の取り消し証Ｃ＝（ａｆ）^ｚ ｍｏｄ ｎを作成する。ここで、ｆ＝Ｈ（取り消し局名）^２ ｍｏｄ ｎである。ＴＰＭは、次に、以下のように動作することによって、署名を作成し、底ａｆおよびａｆ'をそれぞれ有するＣおよびＣ'の２つの離散対数を知っていることおよびこれら離散対数が等しいことを示す。
１．

をランダムに選ぶ。
２．ｃ＝Ｈ（ａ‖ｆ‖ｆ'‖Ｃ‖Ｃ'‖（ａｆ）^ｒ ｍｏｄ ｎ‖（ａｆ'）^ｒ ｍｏｄ ｎ‖ｍ）を計算する。
３．（Ｚにおいて）

を計算する。
４．（ｃ，ｓ，Ｃ）を出力する。

この署名を検証するために、誰何者は以下のように動作する。
１．名前−取り消し局名を有する（例えば、選ばれた取り消し局によって保持されたような）関連した取り消しリストにＣがあるかどうかをチェックする。このチェックがイエスである場合、署名を拒否し、そうでない場合、続行する。
２．

を計算する。
３．ｃ＝ｃ'であり、かつ、

である場合にのみ、署名を容認する。

この第２の方式における取り消しの手法は、第１の方式で述べたものと広く類似している。この場合も、システムは、ＴＰＭ製造業者、ＴＰＭ、取り消し局（ＲＡ）、およびリモートサービスプロバイダＲＳＰの４組のエンティティを含む。

上記のように、出願人は、利用のシナリオを述べた。すなわち、ＴＰＭは、特定の利用目的Ｐ_ＡにアクセスするためにＲＳＰとの通信を望む。ＲＳＰは、ＲＡが、Ｐ_Ａへのアクセスを許可されるべきでないＴＰＭの取り消しリストを保持しているとの信頼を受けていると考える。取り消しリストは、取り消し局名＝Ｐ_Ａ‖ＲＡの識別情報‖満了日‖…という一意の識別情報を有する。

上記で指定したような取り消し証を有する出願人のグループ署名方式では、ＲＡは、値Ｃがそれら悪性ＴＰＭに属するこのような取り消しリストを保持し、その取り消しリストをＲＳＰに利用可能にする。署名の検証中、各ＲＳＰは、まず、Ｃが取り消しリストにあるかどうかをチェックする。イエスである場合、ＲＳＰはこのＴＰＭを拒否する。

オプションとして、このＲＡは、認証局の役割を果たすこともできる（出願人は、これをＲＡ／ＣＡと呼ぶ）。この場合、ＲＡ／ＣＡは、取り消し証を有するグループ署名の方式における検証者である。ＲＡ／ＣＡは、従来の非対称鍵対Ｐ_{ＲＡ／ＣＡ}およびＳ_{ＲＡ／ＣＡ}を有する。これらの鍵は、ＲＳＰによってアクセス可能である。ＴＰＭのグループ署名の検証が成功した後、ＲＡ／ＣＡは、（ＴＣＧ仕様の現在のバージョンにおけるプライベートＣＡと同じように）通常の方法でＰ_{ＲＡ／ＣＡ}およびＳ_{ＲＡ／ＣＡ}を使用することによって、ランダムに選ばれた識別情報を非対称鍵対Ｐ_ＴＰＭおよびＳ_ＴＰＭで証明し、ＣおよびＰ_ＴＰＭの証明書を記録する。オプションとして、ＲＡ／ＣＡは、内部アクセスのみのためにＰ_ＴＰＭと共にＣを記録し、公にアクセス可能な取り消しリストにＰ_ＴＰＭを列挙する。これは、このＲＡ／ＣＡにどのＴＰＭの保証鍵証明書も与えられない点で、ＴＣＧ仕様の現在のバージョンと異なることに留意されたい。

ＴＣＧ仕様の現在のバージョンと同様に、ＲＳＰによって提供されたサービスにアクセスするために、ＴＰＭは、Ｐ_ＴＰＭの証明書でＲＳＰに対して自身を認証する。ＲＳＰは、その証明書を検証し、また、この証明書がＲＡ／ＣＡの取り消しリストにあるかどうかもチェックする。

明らかに、ＴＰＭが、目的Ｐ_ＡとリンクされたＲＡ_１の取り消しリストに列挙されている場合であっても、ＴＰＭは、（１）同様にＲＡ_１によって管理された目的Ｐ_Ｂ、（２）ＲＡ_２によって管理された目的Ｐ_Ａ、および、もちろん（３）ＲＡ_２によって管理された目的Ｐ_Ｂにアクセスすることができる。

もちろん、複数の取り消しリストを使用することが可能である。例えば、或る利用において、一方が取り消し局名_１に基づくものであり、他方が取り消し局名_２に基づくものである２つの取り消しリストをチェックする必要がある場合、ＴＰＭは、２つの取り消し証を作成しなければならない。一方は、取り消し局名_１に基づいてＣ_１と呼ばれ、他方は、取り消し局名_２に基づいてＣ_２と呼ばれる。

この方式では、悪性ＴＰＭの保証鍵および鍵証明書が公開されている場合、どの検証者も、取り消し証を有する所与のグループ署名が、その保証鍵および証明書に基づいて署名されたものであるかどうかをチェックすることができる。

この方式を使用すると、ＴＰＭ所有権の発行に対処することができるさまざまな異なる方法が存在する。第１に、ＯＥＭ（相手先商標による製品製造業者）証明書の使用が考えられる。このＯＥＭは、製造されたＴＰＭを取り込み、それらＴＰＭをコンピューティングプラットフォームホストに実装する。以下のように、このための少なくとも３つの可能なソリューションが存在する。

ソリューション１。このソリューションでは、ＴＰＭ製造業者は証明書発行者としての役割を果たし、ＯＥＭは取り消し局としての役割を果たす。ＴＰＭは、一定のＯＥＭに関連した特別な証拠を有する。この証拠は、（上述した証拠の第１のバージョンを使用して）Ｅ_ＯＥＭ＝（Ｈ（ＯＥＭ名））^２ｚである。この証拠は、ＴＰＭセットアッププロセスにおいてＣＩ（ＴＰＭ製造業者）が製造することもできるし、ＴＰＭが代わりに製造することもできる。ＴＰＭが本物のＴＰＭであることをＯＥＭに確信させるために、ＴＰＭは、ＥとしてＥ_ＯＥＭを有する、上述したような署名をＯＥＭに送る。その署名を検証した後、ＯＥＭは、Ｅ_ＯＥＭに関する証明書を発行する。この証明書は、従来のＰＫＩ証明書とすることができる。このソリューションは、Ｅ_ＯＥＭがＴＰＭに一意であるので、匿名性を提供しない。

ソリューション２。このソリューションでは、ＴＰＭ製造業者およびＯＥＭの双方が、この方式におけるＣＩとしての役割を果たす。ＴＰＭは、１つのプライベート保証鍵ｚおよび２つの関連した証明書（ｕ，ｅ）および（ｕ'，ｅ'）を有する。この第１の証明書は、第３節で説明したようにＴＰＭ製造業者によって発行され、第２の証明書は、同様に、ＯＥＭによって発行される。ＴＰＭ製造業者は公開鍵（ａ，ｂ，ｇ，ｈ，ｎ）を有し、ＴＰＭは（第３節で説明したように）関連した（ｕ，ｅ）を有する。ＯＥＭは公開鍵（ａ'，ｂ'，ｇ'，ｈ'，ｎ'）を有する。ＴＰＭの正確さをＯＥＭに確信させるために、ＴＰＭは、（ｚ，ｅ，ｕ）に基づく第２の方式の署名をメッセージｍ＝ａ'^ｚ ｍｏｄ ｎ'（これはＯＥＭからの誰何と結合することができる）でＯＥＭに送る。第２の方式の署名の検証が成功した後、ＯＥＭは、ＴＰＭに（ｕ'，ｅ'）を発行する。ここで、ｕ'^ｅ'＝ａ'^ｚｂ' ｍｏｄ ｎ'が維持される。その後、ＴＰＭは、（ｚ，ｕ，ｅ）および（ａ，ｂ，ｇ，ｈ，ｎ）に基づく第２の方式の署名を送ることによって、ＴＰＭ製造業者の証明書の要求についてのあらゆる誰何に応答し、（ｚ，ｕ'，ｅ'）および（ａ'，ｂ'，ｇ'，ｈ'，ｎ'）に基づく第２の方式の署名を送ることによって、ＯＥＭの証明書のあらゆる誰何要求に応答する。このソリューションは、第２の方式の署名が異なる取り消し証を有する場合に、匿名性を提供することができる。起こり得る問題は、ＴＰＭとＯＥＭとの間の処理に多大な費用を要するということである。

ソリューション３。このソリューションでは、ＴＰＭ製造業者はＴＣＧの現在のバージョンと同じ役割を果たし、ＯＥＭは第２の方式のＣＩとしての役割を果たす。ＴＰＭの製造中、ＴＰＭは、通常の保証鍵対（既存のＴＣＧ仕様に記載されているようなものであるが、本明細書では、事前保証鍵（pre-endorsement key）対と呼ぶ）を得る。ＴＰＭ製造業者は、ＯＥＭに対してＴＰＭを刻むと、保証公開鍵のリストを送る。ＯＥＭは、上述したＪＯＩＮプロセスのバージョン１を使用することによって各ＴＰＭの交換される保証鍵および証明書を作成する。

１．ＯＥＭは、ＴＰＭの保証プライベート鍵として、指数

をランダムに選び、ｖ＝ａ^ｚを計算する。
２．ＯＥＭは、ランダムな素数

を選択して、かつｕ＝（ｖｂ）^１／ｅを計算することにより、保証鍵証明書（ｕ，ｅ）を生成する。
３．ＯＥＭは、ＴＰＭの事前保証公開鍵で（ｚ，ｕ，ｅ）を暗号化する。
４．ＯＥＭは、暗号化された（ｚ，ｕ，ｅ）および事前保証公開鍵のハッシュ値をパブリックドメインに公開する。
５．ＯＥＭは、自身の（ｚ，ｕ，ｅ）の知識のすべてを消去する。
６．ＴＰＭを有するＴＣＧプラットフォームが、ユーザによって受け取られると、そのプラットフォームは、ＯＥＭのパブリックドメインから暗号化された（ｚ，ｕ，ｅ）をダウンロードし、ＴＰＭは、事前保証プライベート鍵を使用することによって（ｚ，ｕ，ｅ）を解読する。

第２の方式を使用して所有権を取得するための少なくとも２つの可能なソリューションがある。これらソリューションの双方とも、上記ＯＥＭ証明書のソリューションに基づいており、次の通りである。

ソリューション１。このソリューション１は、上記ソリューション１および２の双方に適している。ＴＣＧプラットフォームの所有者は、ＴＰＭの公開Ｅ１Ｇａｍａｌ暗号鍵として（ｆ_ＯＥＭ＝（Ｈ（ＯＥＭ名））^２，Ｅ_ＯＥＭ，ｎ）を使用する。対応するプライベートＥ１Ｇａｍａｌ解読鍵は、ＴＰＭの保証プライベート鍵ｚである。所有者とＴＰＭとの間で実行される所有権取得プロトコルは次の通りである。

１．所有者は、所有権秘密値ｓ∈_Ｒ［１，２^１６０］をランダムに選ぶ。
２．所有者は、Ｅ１Ｇａｍａｌ暗号化を使用することによって（ｆ_ＯＥＭ，Ｅ_ＯＥＭ，ｎ）に基づきｓを暗号化する。これを行うために、所有者は、セッション秘密値ｘ∈_Ｒ［１，２^１６０］をランダムに選び、Ｕ＝ｆ_ＯＥＭ ^（−ｘ）およびＶ＝ｓ＊Ｅ_ＯＥＭ ^ｘを計算する。
３．所有者は（Ｕ，Ｖ）をＴＰＭに送る。
４．ＴＰＭは、ｓ＝Ｖ＊Ｕ^ｚを計算することによってｓを解読する。

解読プロセスは、１つのモジュラ累乗法および１つのモジュラ乗算を必要とする。ＴＰＭにとって新たな機能は必要とされない。

ソリューション２。このソリューション２は、上記ソリューション３に適している。ＴＣＧプラットフォームの所有者は、事前保証公開鍵をＴＰＭの暗号鍵として使用する。対応する解読鍵は、ＴＰＭの事前保証プライベート鍵である。所有者とＴＰＭとの間で実行される所有権を取得するプロトコルは、既存のＴＣＧ仕様と同様である。

本発明の実施の形態を実施することができるシステムを概略的に示す図である。 スマートカードリーダを介してスマートカードと通信し、かつ、１群のモジュールと通信するように構成された、信頼できるデバイスを含むマザーボードを示す図である。 図２の信頼できるデバイスをより詳細に示す図である。 本発明の実施の形態を実行するのに適したコンピュータシステムの要素を示す図である。 信頼できるコンピューティングプラットフォームと、リモートプラットフォームとの間の通信を確立することに関与するステップを、この信頼できるプラットフォームが、従来の信頼できるプラットフォーム技術に従って自身の完全性を検証することを含めて、示すフロー図である。 従来の信頼できるコンピューティング技術の信頼関係を概略的に示す図である。 本発明の実施の形態による信頼できるコンピューティング技術で使用される信頼関係を概略的に示す図である。 本発明の実施の形態による信頼できるコンピューティング技術のアーキテクチャに関与する関係者を、グループ署名方式によるこれらの関係者間の相互作用と共に概略的に示す図である。 取り消し局を使用しない、図８の構成に対する修正を示す図である。

符号の説明

１０，４０・・・信頼できるプラットフォーム，
１８・・・モニタ１８，４４，
１２，４２・・・スマートカードリーダ，
１９，４１・・・スマートカード，
１５・・・モジュール，
２０・・・マザーボード，
２１・・・メインプロセッサ，
２２・・・メインメモリ，
２３・・・入出力（ＩＯ）デバイス，
２４・・・信頼できるデバイス，
２６・・・データバス，
２７・・・各制御ライン２７，
２８・・・ライン２８，
２９・・・ＢＩＯＳメモリ，
３０・・・コントローラ，
３１・・・測定機能，
３２・・・暗号機能，
３３・・・認証機能，
３４・・・インターフェース回路部，
３５０・・・証明書，
３５２・・・完全性メトリック，
３５３・・・識別（ＩＤ）ラベル，
３５５・・・プライベート鍵，
３６０・・・ＩＤラベル，
３６１・・・摘要，
６２・・・信頼できるプラットフォーム
６３・・・認証局
６４・・・リモートサービスプロバイダ

Claims (13)

1. 取り消し証を有するグループ署名方式によって計算資源へのアクセスを判断する方法であって、
   証明書発行者が、グループ秘密鍵を保持し、グループ公開鍵を提供することと、
   グループメンバが、メンバーシップ秘密値を得て、前記証明書発行者が、前記メンバーシップ秘密値に関するグループメンバのメンバーシップ証明書を提供することと、
   前記グループメンバが、前記メンバーシップ秘密値も前記メンバーシップ証明書も検証者に明らかにすることなく、署名を提供することによって、自身が正当なメンバーシップ秘密値および正当なメンバーシップ証明書を所有していることを前記検証者に実証し、自身のメンバーシップ秘密値および取り消しパラメータから取り消し証を提供することと、
   前記検証者が、前記署名および前記取り消し証から、前記グループメンバが正当なメンバーシップ秘密値および正当なメンバーシップ証明書を所有していると判断することと
   を含み、
   前記グループメンバは、信頼できるコンピューティングデバイスであり、
   前記証明書発行者は、前記信頼できるコンピューティングデバイスの製造業者である
   方法。
2. 前記グループメンバは、前記メンバーシップ秘密値を生成する
   請求項１に記載の方法。
3. 前記証明書発行者は、前記メンバーシップ秘密値および前記メンバーシップ証明書を生成する
   請求項１に記載の方法。
4. 前記取り消し証は、前記検証者によって、前記取り消しパラメータに関連した取り消し機関により保持された取り消しリストと比較される
   請求項１に記載の方法。
5. 前記取り消し証は、前記検証者によって、前記検証者により保持された取り消しリストと比較される
   請求項１に記載の方法。
6. グループ公開鍵を有するグループ署名方式のメンバによって信頼ステータスを実証する方法であって、
   前記グループメンバが、メンバーシップ秘密値を得て、且つ、証明書発行者から、前記メンバーシップ秘密値に関するグループメンバのメンバーシップ証明書を受け取ることと、
   前記グループメンバが、前記メンバーシップ秘密値も前記メンバーシップ証明書も検証者に明らかにすることなく、署名を提供することによって、自身が正当なメンバーシップ秘密値および正当なメンバーシップ証明書を所有していることを前記検証者に実証し、自身のメンバーシップ秘密値および取り消しパラメータから取り消し証を提供することと
   を含み、
   前記取り消し証Ｅは、Ｅ＝ｆｚという形態を有し、ここで、ｆは前記取り消しパラメータに対して実行される一方向関数であり、ｚは前記メンバーシップ秘密値である
   方法。
7. 前記署名の少なくとも一部は、前記署名が検証者によって要求される前に、前記グループメンバによって事前に計算される
   請求項６に記載の方法。
8. 前記取り消し証の少なくとも一部は、前記取り消し証が検証者によって要求される前に、前記グループメンバによって事前に計算される
   請求項６に記載の方法。
9. グループ公開鍵を有するグループ署名方式のメンバの信頼ステータスを検証する方法であって、
   前記検証者が、グループメンバから、前記グループメンバのメンバーシップ秘密値およびメンバーシップ証明書から生成された署名を受け取り、且つ、前記グループメンバによって、自身のメンバーシップ秘密値および取り消しパラメータから提供された取り消し証を受け取ることと、
   前記検証者が、前記署名および前記取り消し証から、前記グループメンバが正当なメンバーシップ秘密値および正当なメンバーシップ証明書を所有していると判断することと
   を含み、
   前記グループ公開鍵は、証明書発行者が保持し、
   前記グループメンバは、信頼できるコンピューティングデバイスであり、
   前記証明書発行者は、前記信頼できるコンピューティングデバイスの製造業者である
   方法。
10. 前記検証者が、前記グループメンバが正当なメンバーシップ秘密値および正当なメンバーシップ証明書を所有していると判断することは、
    前記取り消し証を１つまたは複数の取り消しリストと照合することと、
    前記取り消し証および前記署名が一致すると判断することと、
    前記署名が、適切に形成されたメンバーシップ秘密値および適切に形成されたメンバーシップ証明書からの構成と一致すると判断することと
    を含む
    請求項９に記載の方法。
11. 前記１つまたは複数の取り消しリストの少なくとも１つは、取り消し局（revocation agency）によって保持される
    請求項１０に記載の方法。
12. 前記１つまたは複数の取り消しリストの少なくとも１つは、前記検証者によって保持される
    請求項１０に記載の方法。
13. プロセッサと、
    メンバーシップ秘密値、および、グループ公開鍵を有するグループ署名方式の証明書発行者により前記メンバーシップ秘密値に対して発行されたメンバーシップ証明書を含むメモリと
    を備える信頼できるコンピューティング装置であって、
    前記信頼できるコンピューティング装置は、
    前記メンバーシップ秘密値も前記メンバーシップ証明書も検証者に明らかにすることなく、署名を提供することによって、自身が正当なメンバーシップ秘密値および正当なメンバーシップ証明書を所有していることを前記検証者に実証し、
    自身のメンバーシップ秘密値、自身のメンバーシップ証明書、前記グループ公開鍵、および取り消しパラメータから取り消し証を提供する
    ように適合され、
    前記証明書発行者は、前記信頼できるコンピューティング装置の製造業者である
    信頼できるコンピューティング装置。

Images