証明書を効率的に無効にする方法及び装置
【課題】特に、証明書をその有効期限前に無効にする必要があることがある場合の、公開鍵インフラストラクチャにおけるデジタル証明書の無効化を開示する。例えば、ある従業員を解雇した場合や職務を変更した場合、現在の証明書はもはや有効であってはならない。従って、この問題に対処するための新規の方法、構成要素及びシステムを提供する。
【解決手段】本明細書に記載の解決法は、グラウンデッド・デンス・ハッシュ木の構成に基づくものである。さらに、グラウンデッド・デンス・ハッシュ木の方法は、ＮＯＶＯＭＯＤＯの基本的なチェーンに基づくバージョンに比べて、時間と通信のトレードオフをもたらし、このトレードオフにより、実際の場面で、計算時間の直接的改善がもたらされる。
【解決手段】本明細書に記載の解決法は、グラウンデッド・デンス・ハッシュ木の構成に基づくものである。さらに、グラウンデッド・デンス・ハッシュ木の方法は、ＮＯＶＯＭＯＤＯの基本的なチェーンに基づくバージョンに比べて、時間と通信のトレードオフをもたらし、このトレードオフにより、実際の場面で、計算時間の直接的改善がもたらされる。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２００３年９月１９日に出願された“ＭＥＴＨＯＤ ＡＮＤ ＡＰＰＡＲＡＴＵＳ ＦＯＲ ＥＦＦＩＣＩＥＮＴ ＣＥＲＴＩＦＩＣＡＴＥ ＲＥＶＯＣＡＴＩＯＮ”という名称の、本出願に対応する仮特許出願第６０／５０４，２５３号に対する優先権を主張し、参照することにより本明細書に含む。
【０００２】
本発明は、暗号分野に関する。特に、本発明は、証明書の無効化に関する。
【背景技術】
【０００３】
世の中がますますオンライン化する傾向は続くにつれて、公開鍵暗号法が一般的によく使用されるようになっていくであろう。かかる使用の基礎として、公開鍵と権限とを関係付けるポリシー、処理、人員、及び施設を構成する公開鍵インフラストラクチャを確立しなければならない。この公開鍵インフラストラクチャは認証局（ＣＡ）によって管理される。認証局は、公開鍵を識別子や権限に関係付けるデジタル証明書を発行するだけでなく、このようなデジタル証明書の管理もしている。証明書を発行する際、認証局は、ユーザの身分証明が正確であるかを必ず確かめなければならない。しかし、証明書を無効にする必要がある場合、処理はもっと複雑になることがある。
【０００４】
証明書の有効性が有効期限によって制限されることがあるが、証明書をその有効期限より前に無効にしなければならない場合がある。例えば、鍵の所有者がその所属や職業を変えることもあれば、さらに悪いことには、その秘密鍵の信用が損なわれていることもある。従って、証明書を無効にする何らかの方法が必要である。
【０００５】
証明書を無効にする一般的な方法の１つは、証明書失効リスト（ＣＲＬ：Ｃｅｒｔｉｆｉｃａｔｅ Ｒｅｖｏｃａｔｉｏｎ Ｌｉｓｔ）を用いるものである。証明書失効リストは、認証局によって発行され、電子的に署名され、タイムスタンプされたリストであり、シリアル番号、名前、メールアドレス等の何らかの識別子により、どの証明書が無効になったかを示している。たとえ変更がなくても、このようなＣＲＬを定期的に配信して、いかなるタイプのリプレイ攻撃も防御しなければならない。この方法は簡単なように見えるかもしれないが、ＣＲＬを管理することは、通信や調査や検証にかかる費用に関して非現実的なことがある。
【０００６】
他の方法には、証明書失効木（ＣＲＴ：Ｃｅｒｔｉｆｉｃａｔｅ Ｒｅｖｏｃａｔｉｏｎ Ｔｒｅｅ）を使用するものがある。ＣＲＴは、Ｍｅｒｋｌｅ木であり、各葉（ｌｅａｆ）が、無効になった証明書のグループに関連付けられている。従って、葉の要素を用いて論理プルーフを形成することができ、プルーフは、Ｍｅｒｋｌｅ木のプロパティにより検証することができる。
【０００７】
認証局は、無効になった証明書の完全なリストを通知するかわりに、オンライン方法を用いて、特定の証明書についてのクエリーに応答するようにしてもよい。この方法は、オンライン証明書状態プロトコル（ＯＣＳＰ：Ｏｎｌｉｎｅ Ｃｅｒｔｉｆｉｃａｔｅ Ｓｔａｔｕｓ Ｐｒｏｔｏｃｏｌ）で使用されている。しかし、この方法には限界がある。第一に、有効プルーフ（ｖａｌｉｄｉｔｙ ｐｒｏｏｆ）は、かなり長くなるものもあるデジタル署名からなる。例えば、ＲＳＡ署名では、１０２４ビットの鍵により、署名は、１０２４ビットの長さになる。さらに、１０２４ビットの鍵は、セキュリティに関して低い。今後長期にわたる必要性のために、２０４８ビットのような鍵を考えなければならないであろう。認証局は、十分信頼できるものでなければならないので、その署名鍵は、それ相応に長くなる。従って、ＲＳＡの２０４８ビットの鍵サイズは、大きすぎることはない。さらに、多数のリクエストを処理しなければならないこともある認証局にとって、応答の１つ１つに署名するのは計算上実行不可能なことがある。認証局がたった１つの集中型装置であれば、全てのリクエストがそこを経由し、固有のリクエストの１つ１つに対しデジタル署名を計算しなければならないので、スケーラビリティに関する大きな問題が生じる。何らかのロードバランシングを取り入れて認証局を分散しようとすると、例えば慎重な扱いを要する署名鍵を複製するなどのセキュリティリスクがもたらされる。
【０００８】
Ｍｉｃａｌｉは、ＮＯＶＯＭＯＤＯという精密かつ簡潔な方式でこれらの問題に対処した。ＮＯＶＯＭＯＤＯ方式は、Ｘ．５０９等のいかなる標準的な認証形式にも使用でき、認証局が、例えば１日や１時間といった所定の時間間隔で、証明書の有効状態を提供することを可能にする。ＮＯＶＯＭＯＤＯは、単一のデジタル署名と共に１つのハッシュチェーンを使用する。その利点は、単一の署名のコストが、多くの有効プルーフで償却されることである。しかし、ＮＯＶＯＭＯＤＯは、２つのクエリーの間に過ぎた周期の数に比例した時間で、ハッシュチェーンを横断する必要がある。Ｎａｏｒ及びＮｉｓｓｉｍが指摘した自然な拡張は、Ｍｅｒｋｌｅ木を使用することである（Ｍ．Ｎａｏｒ及びＫ．Ｎｉｓｓｉｍ著，“Ｃｅｒｔｉｆｉｃａｔｅ Ｒｅｖｏｃａｔｉｏｎ ａｎｄ Ｃｅｒｔｉｆｉｃａｔｅ Ｕｐｄａｔｅ”，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＵＳＥＮＩＸ Ｓｅｃｕｒｉｔｙ，１９９８）。この方法において、検証者は、
【数１】
個のハッシュを計算して、証明書を検証しなければならない。もっとも、有効プルーフは、その時、
【数２】
個のハッシュ値からなるのだが。概して、この方法は、元のＮＯＶＯＭＯＤＯ方法に比べて、平均的な検証複雑性が大幅に減少しているので望ましい。それでも、まだいくつかの不利点がある。
１．検証と検証との間の時間が、
【数３】
よりも短いならば、元のＮＯＶＯＭＯＤＯ方式の方が、検証者が証明書を認証するのに要する時間は短い。
２．元のＮＯＶＯＭＯＤＯ方式におけるプルーフのサイズは、常に１ハッシュ値であり、拡張されたＮＯＶＯＭＯＤＯ方式のプルーフサイズよりもはるかに小さい。
ＮＯＶＯＭＯＤＯに関する詳細については、Ｓ．Ｍｉｃａｌｉ，“ＮＯＶＯＭＯＤＯ：Ｓｃａｌａｂｌｅ Ｃｅｒｔｉｆｉｃａｔｅ Ｖａｌｉｄａｔｉｏｎ ａｎｄ Ｓｉｍｐｌｉｆｉｅｄ ＰＫＩ Ｍａｎａｇｅｍｅｎｔ，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １ｓｔ Ａｎｎｕａｌ ＰＫＩ Ｒｅｓｅａｒｃｈ Ｗｏｒｋｓｈｏｐ，２００２を参照されたい。
【０００９】
ここで、ＡＬＯ方法として言及する他の方法は、Ａｉｅｌｌｏ、Ｌｏｄｈａ及びＯｓｔｒｏｖｓｋｙによるもので、複数のユーザに対する有効プルーフを同時に提供するために、ユーザを部分集合に区分する方法とともにＮＯＶＯＭＯＤＯのような方式を用いるものである。Ｗ．Ａｉｅｌｌｏ，Ｓ．Ｌｏｄｈａ及びＲ．Ｏｓｔｒｏｖｓｋｙ，“Ｆａｓｔ Ｄｉｇｉｔａｌ Ｉｄｅｎｔｉｔｙ Ｒｅｖｏｃａｔｉｏｎ”，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ａｓｉａｃｒｙｐｔ’０１，２００１を参照されたい。
【００１０】
ＡＬＯ方式では、別個のＮＯＶＯＭＯＤＯのようなハッシュチェーンを、かかるユーザ部分集合Ｓｉの各々に割り当てる。次に、一定の間隔で、無効になった証明書を有するユーザの集合をＴで表すとすれば、認証局は、最初に、
【数４】
において、カバーするインデックスｉ１，…，ｉｋを計算する。次に、各部分集合
【数５】
に対する有効プルーフを提供する。これにより、ユーザのグループを同時に検証することができる。この方法には、いくつかの欠点がある。第１に、部分集合を構成して、部分集合ごとにチェーンを備えることに関して付加的なオーバーヘッドが生じる。少なくとも、単集合の部分集合を生成しなければならない（これは、基本的に元のＮＯＶＯＭＯＤＯ方式をもたらす）。従って、ＡＬＯ方式により実際に改良しようとするなら、付加的な部分集合を計算する必要があり、付加的な作業が必要になることになる。第２に、元のＮＯＶＯＭＯＤＯ方式におけるように、ハッシュ計算の回数が有効性チェックの間隔に比例するので、大きくなることがある。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
証明書を無効にする方法及び装置が開示される。一実施形態において、該方法は、有効ターゲット（ｖａｌｉｄｉｔｙ ｔａｒｇｅｔ）と無効ターゲット（ｒｅｖｏｃａｔｉｏｎ ｔａｒｇｅｔ）とを有する証明書データ（ｃｅｒｔｉｆｉｃａｔｅ ｄａｔａ）を生成することを含み、有効ターゲットは、グラウンデッド・デンス・ハッシュ（ｇｒｏｕｎｄｅｄ ｄｅｎｓｅ ｈａｓｈ）木の根の値である。この方法はまた、証明書データを有する証明書（ｃｅｒｔｉｆｉｃａｔｅ）を発行することを含む。
本発明は、以下に与えられる詳細な記載及び本発明の様々な実施形態に付随する図面から、より十分に理解されるであろう。しかしながら、これらは、特定の実施形態に対いて本発明を限定するために用いられるべきではなく、あくまでも説明や理解のためだけのものである。
【課題を解決するための手段】
【００１２】
従って、上述の問題に対処するための方法、構成要素及びシステムを提供する。一実施形態において、Ｍｅｒｋｌｅ木を用いる代わりに、グラウンデッド・デンス・ハッシュ木（ＧＤＨ）を用いる。この方法では、Ｍｅｒｋｌｅ木でそうするように葉から処理を始めるのではなく、木の１つおきの内部ノードから処理を始める。その結果、全般的な検証の複雑性だけでなく、Ｎａｏｒ及びＮｉｓｓｉｍのＭｅｒｋｌｅ木に基づく方式における通信の複雑性の両方がただちに改善される。さらに、有効プルーフ（ｐｒｏｏｆ ｏｆ ｖａｌｉｄｉｔｙ）が小さいので、１つのパケット内に収まる可能性が高く、それにより、実際に必要な追加の通信がごくわずかとなる。
【００１３】
一実施形態において、グラウンデッド・デンス・ハッシュ木を使用して、複数のユーザに同時に適用することもあるプルーフを構成する。これにより、認証局は、少数のプルーフを発行するだけでよく、多数のユーザの証明書を検証するのに使用することができる。
【００１４】
本発明の一実施形態におけるシステムは、現在の周期をｐｔで表し、前回の有効性チェックの計算結果がキャッシュされているとして、有効性がチェックされた前回の周期をｐｃで表わすとして、多くても、
【数６】
の作業により、認証局が発行したオーナに属する証明書の有効性を、検証者Ｖが判断するのを可能にする。前回の有効性チェックがキャッシュされていない場合は、
【数７】
の作業が必要である。いずれの場合も、プルーフサイズは、有効性チェックを実行するのに必要な作業量に比例する。
【００１５】
ある方法の一実施形態が提供されており、かかる方法により認証局は、グラウンデッド・デンス・ハッシュ木を用いて、単一の証明書オーナ（ｃｅｒｔｉｆｉｃａｔｅ ｏｗｎｅｒ）の有効ターゲットを生成する。
【００１６】
本発明の別の実施形態は、ある方法を示すものであり、かかる方法により認証局は、このようなグラウンデッド・デンス・ハッシュ木を用いて、有効プルーフを構成する。有効プルーフのサイズは、ｔを有効期間として（例えば、ｔ＝１４は、３６５日のうちの１４日であることを意味する）、大きくてもＯ（ｌｏｇ（ｔ））である。
【００１７】
本発明の他の実施形態は、ある方法を含み、かかる方法により検証者は、ｔを有効期間として、多くてもＯ（ｌｏｇ（ｔ））の作業だけで、認証局が発行したプルーフの有効性を検証する。
【００１８】
本発明の実施形態は、本明細書に記載の方法のオペレーションを実行する認証局、検証者及びオーナの構成要素を含む。
【００１９】
本発明の一実施形態は、複数の証明書に対する１つの有効プルーフを検証者が発行できるようにすることによって、複数の証明書オーナに属する１つの証明書の有効性を検証者が同時に判断できるようにするシステムを含む。本発明の一実施形態は、複数の証明書の有効性に関し単一のプルーフを認証局が構成する方法を含む。本発明の他の実施形態は、認証局が発行したプルーフを検証者が検証する方法を含む。
【発明を実施するための最良の形態】
【００２０】
以下の説明において、多くの詳細を示すことで、本発明をさらに詳しく説明する。しかしながら、これらの詳細がなくても本発明が実行可能であることは、当業者にとって明らかであろう。他の例では、公知の構造や装置を、詳細図ではなくブロック図形式で示して、本発明が分かりにくくならないようにしている。
【００２１】
以下の詳細な説明のいくつかの部分は、コンピュータ記憶装置内のデータビットの演算のアルゴリズムや記号表現によって示されている。これらのアルゴリズムの記述や表現は、データ処理技術の技術者が、彼らの仕事の実態を他の当業者にもっとも効果的に伝えるのに用いる手段である。本明細書において、また一般的に、アルゴリズムは、望ましい結果に導くセルフコンシステントな一連の工程であるとみなされる。該工程は、物理量の物理的操作を必要とするものである。通常、必ずではないが、これらの量は、記憶、転送、結合、比較、その他の操作ができる電気信号や磁気信号の形態をとる。時には、主に一般的な使用のために、これらの信号をビット、値、要素、記号、文字、項、数字等で表すことは便利である。
【００２２】
しかしながら、これらや類似用語は、全て適切な物理量に関連付けるためのものであり、これらの量にあてはめる単なる便利なラベルと考えるべきである。以下の論述から明らかのように、特に違ったように記述されていないかぎり、本明細書全体において、「処理」、「演算」、「計算」、「判断」、「表示」等の用語を用いた論述は、コンピュータシステムのレジスタや記憶装置内の物理（電子）量で表されるデータを、コンピュータシステムの記憶装置やレジスタ、又は、他のかかる情報記憶装置、送信装置又は表示装置内の物理量で同様に表される他のデータに操作及び変換するコンピュータシステム又は類似の電子計算装置の動作及び処理を述べるものとなっている。
【００２３】
本発明はまた、本明細書のオペレーションを実行する装置に関する。この装置は、必要な目的のために特別に構成されていてもよいし、コンピュータ内に記憶するコンピュータプログラムによって選択的に起動するか再構成する汎用コンピュータを含むものであってもよい。かかるコンピュータプログラムは、例えばフロッピーディスク、光ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、読出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カード又は光カードを含むいかなるタイプのディスクや、電子命令を記憶するのに適したいかなるタイプの媒体など、それぞれコンピュータシステムバスに接続されるコンピュータ読取り可能記憶媒体に記憶されてもよいが、それに限定されない。
【００２４】
本明細書に提示されるアルゴリズムやディスプレイは、特定のコンピュータや他の装置に本質的に関連するものではない。本明細書の教示によるプログラムとともに様々な汎用システムを使用してもよいし、必要な方法段階を実行するためにより専門化した装置を構成すれば便利であるかもしれない。これらの様々なシステムに必要な構造は、以下の記載から明らかである。さらに、本発明は、特定のプログラム言語に関連して述べられていない。本明細書に記載の本発明の教示を実行するのに、様々なプログラム言語を用いることができる。
【００２５】
機械読取り可能媒体は、機械（例えば、コンピュータ）が読み取ることができる形式で情報を記憶又は送信するための構造を含む。例えば、機械読取り可能媒体は、読出し専用メモリ（「ＲＯＭ」）、ランダムアクセスメモリ（「ＲＡＭ」）、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリ装置、電気、光、音響、その他の形態の伝播信号（例えば、搬送波、赤外線信号、デジタル信号等）等を含む。
【００２６】
準備段階
本明細書に記載のモデルでは、認証局と、証明書オーナ又は所有者（オーナ）と、証明書検証者とが存在する。以下の論述において、オーナは、認証局が発行した証明書を有する。当然ながら、認証局という概念は、より一般的に、複数の個人に対してアクセス制御の特権や許可を発行する責任を持ついかなる局にもあてはまる。オーナという概念は、例えばワールドワイドウェブサーバなどのコンピュータやエンティティを操作する特定の人間であることがある。同様に、検証者は、コンピュータを操作する特定の人間であることもあるし、特定のサービスに対するアクセスを許可すべきかどうかを判断するアクセス制御サーバ等のエンティティであることもある。
【００２７】
所定のトランザクションにおいて、証明書検証者は、証明書がその有効期限より前に無効になっていないことを確かめたい。そのため、証明書検証者は、認証局に有効プルーフ（ｐｒｏｏｆ ｏｆ ｖａｌｉｄｉｔｙ）か無効プルーフ（ｐｒｏｏｆ ｏｆ ｒｅｖｏｃａｔｉｏｎ）を求める。
【００２８】
望ましくは、認証局とオーナの両方が公開−秘密鍵のペアを有するように、オープン又はクローズド公開鍵インフラストラクチャを用いる。ここで鍵ペアは（Ｓｋ、Ｐｋ）と呼び、Ｓｋは、メッセージの署名を演算するための秘密署名鍵であり、Ｐｋは、Ｓｋに対応する公開検証鍵である。本明細書における目的のために、等式ＤＳ＝（ＫＧ，Ｓｉｇｎ，Ｖｆ）は、Ｇｏｌｄｗａｓｓｅｒ，Ｍｉｃａｌｉ及びＲｉｖｅｓｔ著，“Ａ Ｄｉｇｉｔａｌ Ｓｉｇｎａｔｕｒｅ Ｓｃｈｅｍｅ Ｓｅｃｕｒｅ Ａｇａｉｎｓｔ Ａｄａｐｔｉｖｅ Ｃｈｏｓｅｎ−Ｍｅｓｓａｇｅ Ａｔｔａｃｋｓ”，ＳＩＡＭ Ｊｏｕｒｎａｌ ｏｎ Ｃｏｍｐｕｔｉｎｇ，１７（２）：２８１−３０８，１９８８、の意味における、適応的な選択メッセージ攻撃のもとで、経験したことのある偽造に対して安全なデジタル署名方式を示す。ＫＧは、鍵生成アルゴリズムを示し、Ｓｉｇｎ（Ｓｋ，Ｍ）は、署名鍵ＳｋのもとでメッセージＭに対する署名σを出力する署名アルゴリズムを示し（署名アルゴリズムはランダムに選んでもよい）、Ｖｆ（Ｐｋ，Ｍ，σ）∈｛０，１｝は、公開鍵Ｐｋに関してメッセージＭの署名σが正確であれば、１と判断する検証アルゴリズムを示す。明確にするために、特定の個人に属する鍵を示すのに下付きを使用する。そうすると、ＨＳＰの鍵ペアは、（ＰｋＨＳＰ，ＳｋＨＳＰ）となり、Ｕの鍵ペアは、（ＰｋＵ，ＳｋＵ）となる。鍵生成アルゴリズムＫＧは、入力として、生成すべき鍵の長さを特定するセキュリティパラメータをとってもよい。その結果、認証者の鍵の長さは、標準的な証明書オーナのものよりも大きくなることがある。なぜなら、特に、前者の鍵の信用を損なう結果は、後者の鍵の信用を損なう結果よりもはるかに損害が大きい可能性が強いからである。
【００２９】
｛０，１｝＊が、全てのビットストリングの集合を示すものとする。ビットストリングｓに関し、その長さは、|ｓ|で示す。Ｈが、入力としてｂビットのペイロードとｖビットの初期ベクトル（ＩＶ）をとり、ｖビットの出力を生成する暗号圧縮関数を示すものとする。一実施形態において、ｂ≧２ｖであり、これは、使用されている公知の構造の全てに当てはまる。本明細書に記載される構造に関し、通常ｂ＝２ｖである。一実施形態において、これらの暗号圧縮関数は、耐衝突性である。すなわち、Ｈ（ＩＶ，ｍ１）＝Ｈ（ＩＶ，ｍ２）となるような２つの異なる入力ｍ１≠ｍ２を見つけるのは難しい。一実施形態において、ＩＶは、一定であり、公知である。表記を簡潔にするために、ＩＶは、ハッシュ関数における独立変数（ａｒｇｕｍｅｎｔ）として常に明記しない。かかる暗号圧縮関数の実際の例は、ＳＨＡ−１やＭＤ５に見られる。前者の圧縮関数は、２０バイトの出力とＩＶサイズであり、一方、後者に関しては、該サイズは１６バイトである。両方とも６４バイトのペイロードサイズである。一実施形態において、圧縮関数ペイロードサイズよりも大きいデータに演算は行われないが、そのためには、反復ハッシュやＭｅｒｋｌｅ木等の数々の標準技術が存在する。簡潔にするために、ハッシュ関数という用語を圧縮関数の代わりに用い、ハッシュ関数は、任意の長さのストリング｛０，１｝＊をとり、｛０，１｝ｖの固定長の出力を生成することができることになっている。記号Ｈは、かかる関数を示すのに用いられる。一方向性で耐衝突性であるハッシュ関数を用いるのが望ましい。
【００３０】
長さ保存関数ｆ：｛０，１｝ｎ→｛０，１｝ｎ、整数ｉ≧１に関して、ｆｉが、そのｆ倍の合成（ｆ-ｆｏｌｄ ｃｏｍｐｏｓｉｔｉｏｎ）を示すものとする。すなわち、ｉ＝１では、ｆｉ（ｘ）＝ｆ（ｘ）であり、ｉ＞１では、ｆｉ（ｘ）＝ｆ（ｆｉ−１（ｘ））である。ｘをランダムに選んだｆ（ｘ）が与えられた時、わずかな可能性を除いて、ｆ（ｚ）＝ｆ（ｘ）となるようなプリイメージ（ｐｒｅ-ｉｍａｇｅ）ｚを見つけるのが難しいならば、関数ｆは、一方向関数である。一方向関数ｆは、ｉに関し、ｆｉ（ｘ）を与えられた時、わずかな可能性を除いて、ｆ（ｚ）＝ｆｉ（ｘ）となるようなプリイメージｚを見つけるのが難しいならば、その反復において一方向であると言われる。実際には、ハッシュ関数Ｈから始めて、長さを保存するためにペイロードの一部をパッドすることによって、その反復において一方向である候補関数を構成することが多い。
【００３１】
最後に、実数ｒに関し、
【数８】
はｒの天井、すなわち、ｒ以上の最小の整数値である。同様に、
【数９】
はｒの床、すなわち、ｒ以下の最大の整数値を示す。
Ｍｅｒｋｌｅ木
【００３２】
重要な概念の１つは、Ｍｅｒｋｌｅ木であり、以下のように説明することができる。ｍ個の値ｘ１，…，ｘｍが存在し、それぞれ｛０，１｝ｎであるとする。簡潔にするために、ｍは、２の累乗とする。Ｈ：｛０，１｝２ｎ→｛０，１｝ｎを、２ｎビットストリングをｎビットストリングにマップする暗号ハッシュ関数とする。ハッシュ関数Ｈのもとのｘ１，…，ｘｍに対応するＭｅｒｋｌｅ木は、均衡な２分木であり、各ノードは、特定の値Ｖａｌｕｅ（ｖ）に関連付けられている。ｍ個の葉が存在し、各葉ｌｉに関して、Ｖａｌｕｅ（ｌｉ）＝Ｈ（ｘｉ），１≦ｉ≦ｍである。ｘｉは、｛０，１｝ｎに含まれるので表記を乱用しているが、Ｈの定義域は、｛０，１｝２ｎであることに注意されたい。この場合、Ｈは、適切にパディングされるものとする。内部頂点に関し、Ｃ０（ｖ）及びＣ１（ｖ）は、その左右の子を示すものとする。“ｏ”は連結演算を示すものとする。すると、Ｖａｌｕｅ（ｖ）＝Ｈ（ＩＶ，Ｖａｌｕｅ（Ｃ０（ｖ））ｏＶａｌｕｅ（Ｃ１（ｖ）））となる。Ｍｅｒｋｌｅ木のみが形式Ｖａｌｕｅｌｉ＝Ｈ（ｘｉ）の値を有する葉を持つものとみなされるが、Ｍｅｒｋｌｅ木は、これらの葉の下に、ｍ個の頂点からなる別の層をさらに有する。この頂点の集合は、値ｘｉを持ち、かかる頂点は、それぞれ、値Ｈ（ｘｉ）の頂点に結合されている。
【００３３】
Ｍｅｒｋｌｅ木は、デジタル署名のデータをダイジェストするのに使用することがあり、署名されたダイジェストは、根に対応付けられた値に相当する。また、基礎となる圧縮関数が耐衝突性であれば、Ｍｅｒｋｌｅ根の値が同一である２つの異なるメッセージを見つけるのは困難である。
グラウンデッド・デンス・ハッシュ木
【００３４】
グラウンデッド・デンス・ハッシュ（ＧＤＨ）木を構成する処理を以下に述べる。ＧＤＨ木は、表面上、内部頂点のいくつかを慎重に番号付けする以外は、Ｍｅｒｋｌｅ木のように見える。かかる木を使用する効力は、証明書無効化方式において、内部ノードの部分集合を直接利用することができることにある。その要点は、かかる方式の時間複雑性や通信複雑性の両方を改善することにある。この場合もまた、処理は、ｍ個の値、ｘ１，…，ｘｍから始まる。簡潔にするために、ある正の整数ｋに関して、ｍは、２ｋと同等であるものとする。木は、以下のように構成される。最下層にｍ個の頂点があり、それらは兄弟がいないという意味で一人子である頂点である。次に、Ｍｅｒｋｌｅ木でそうするように、深さｋ＋１の均衡２分木を構成し、各頂点に値を割り当てる。この木は、最下位のｍ個の頂点の上に存在する。値は、以下のように割り当てられる。最下位のｍ個の頂点は、それぞれ、値ｘ１，…，ｘｍをとる。最下層の上に直接乗っている層に、ｍ個の頂点を構成し、ｎビットの値ｆ（ｘｉ）をｉ番目のかかる頂点に割り当てる。ｆ：｛０，１｝ｎ→｛０，１｝ｎは、長さ保存一方向関数である。すなわち、ｌｉが、かかる頂点であれば、１≦ｉ≦ｍに関し、Ｖａｌｕｅｌｉ＝ｆ（ｘｉ）となる。次に、Ｈ：｛０，１｝２ｎ→｛０，１｝ｎを暗号ハッシュ関数とする。すると、２つの最下層の上にある内部ノードｖは、Ｖａｌｕｅ（ｖ）＝Ｈ（ＩＶ，Ｖａｌｕｅ（Ｃ０（ｖ））ｏＶａｌｕｅ（Ｃ１（ｖ）））となる。
【００３５】
同じ木が、以下のように別の方法で特徴付けられる。３ｍ−１個の頂点が存在する。これらは、それぞれ、ｌ１，…，ｌｍ，ｌ´１，…，ｌ´ｍ，及びｖ１，…，ｖｍ−１である。その値は、以下のように割り当てられる。１≦ｉ≦ｍに関し、Ｖａｌｕｅ（ｌｉ）＝ｘｉ及びＶａｌｕｅ（ｌ´ｍ）＝ｆ（ｘｉ）。次に、λ（ｉ）＝２（ｉ−ｍ／２）＋１とし、ρｉ＝２（ｉ−ｍ／２）＋２とする。ｉ∈｛ｍ／２，ｍ／２＋１，…，ｍ−１｝に関し、以下が適用できる。
【数１０】
最後に、ｉ∈｛１，…，ｍ／２−１｝に関し、
【数１１】
となる。
これにより、値が、頂点に割り当てられる。以下は、有向辺（ｄｉｒｅｃｔｅｄ ｅｄｇｅｓ）の説明である。高位では、Ｖａｌｕｅ（ｕ）が、Ｖａｌｕｅ（ｗ）の計算に明白に使用された場合、有向辺は、頂点ｕに隣接し、頂点ｗへのびる。より正確には、有向辺は、このように説明できる。１≦ｉ≦ｍに関し、ｌｉからｌ´ｉまで有向辺が存在する。ｉ∈｛ｍ／２，ｍ／２＋１，…，ｍ−１｝に関し、ｌ´λ（ｉ）からｖｉまで有向辺が存在し、ｌ´ρ（ｉ）からｖｉまで有向辺が存在する。最後に、ｉ∈｛１，…，ｍ／２−１｝に関し、ｖ２ｉからｖｉまで有向辺が存在し、ｖ２ｉ＋１からｖｉまで有向辺が存在する。
【００３６】
次に、以下の２つの着色を木のノードに施す。根は、白に着色する。根の左側の子は、灰色にし、根の右側の子は、白色にする。各頂点に向かって木を降りながら、各頂点は、その親の左側の子であれば、灰色に着色し、その親の右側の子であれば、白色に着色する。（ｌｉの頂点の場合のように）頂点が兄弟を持たない場合、灰色に着色する。すなわち、一人子は、同時に左側の頂点であり右側の頂点であるとみなすことができる。兄弟である２つの頂点に関し、一方のみを着色できるならば、他の着色方式を用いてもよいことに注意されたい。同様に、他の数でもよい。
【００３７】
最後に、灰色のノードを幅優先方法で番号付けする。すなわち、木の上端から始め、連続する位に１つ１つ降りていきながら、灰色ノードは、それぞれ左から右へ連続的に番号付けされる。説明例として、ｍ＝４の場合を考える。かかる場合、番号１は、根の左側の子に割り当てられる。番号２は、根の左側の子の左側の子に割り当てられる。番号３は、根の右側の子の左側の子に割り当てられる。番号４は、根の左側の子の左側の子の一人子に割り当てられる。番号５は、根の左側の子の右側の子の一人子に割り当てられる。番号６は、根の右側の子の左側の子の一人子に割り当てられる。最後に、番号７は、根の右側の子の右側の子の一人子に割り当てられる。一見、灰色頂点を番号付けするという考えは、何か不自然なようであるかもしれないが、周期ｉの有効プルーフにｉ番目の灰色頂点を含むことがその目的である。
【００３８】
ｉ番目の灰色頂点は、ｇｖ（ｉ）と呼ぶ。図７及び図８は、７周期の無効化方式に適応することができるグラウンデッド・デンス・ハッシュ木のラベリングの比較を示している。図７は、１１個の頂点を持つグラウンデッド・デンス・ハッシュであり、７周期間使用することができる。内部ノードは、それぞれ、その子どもたちの値のハッシュである値を持つ。灰色頂点は、それぞれ、幅優先順で連続的に番号付けされる。図８は、８周期を可能にするＭｅｒｋｌｅ木である。この木の基本部分は、１５の頂点を有するが、８つの付加的な陰の頂点が存在し、下位ハッシュの木の底辺から垂れ下がっている。木は、８周期間使用することができる。内部ノードを用いれば、よりコンパクトな木が見られる。すなわち、８周期に適応するＭｅｒｋｌｅ木は、グラウンデッド・デンス・ハッシュ木の２倍以上の頂点を必要とする。
【００３９】
一般に、ｍ個の葉を持つグラウンデッド・デンス・ハッシュ木は、３ｍ−１個の頂点を持ち、２ｍ−１周期に適応できる。ｍ個の葉を持つＭｅｒｋｌｅ木もまた、３ｍ−１個の頂点を持つが、ｍ周期にしか適応できない。グラウンデッド・デンス・ハッシュ木によるパフォーマンスの向上は２−１／ｍであり、ｍが大きくなるにつれて２に近づく。
【００４０】
ＧＤＨ木の所定の頂点の補ノード（ｃｏ-ｎｏｄｅ）という概念が、以下で用いられる。頂点ｖに関し、ＣｏＮｏｄｅｓ（ｖ）は、ｖから根までの経路上にある頂点の兄弟の集合である。より正式には、Ｓｉｂ（ｖ）とＰａｒｅｎｔ（ｖ）がそれぞれｖの兄弟と親を示すならば、
【数１２】
ここで、Ｖが根である場合、上式の値を取り、その他の場合、下式の値を取る。
最後に、補ノードの集合に関し、Ｖａｌｕｅ（ＣｏＮｏｄｅｓ（ｖ））は、頂点ｖの補ノードに対応する値を示す。補ノードに類似した概念は、Ｍｅｒｋｌｅ木に存在する。
【００４１】
補ノードが与えられた時、根の値を計算する一実施形態の方法は、以下のとおりである。ｉ番目の灰色頂点に対応する値をｖとし、ｉ番目の灰色頂点から根の頂点までの経路上にある全ての頂点の兄弟の値をｖ１，…，ｖとする。すると、根の値は、ｈとして計算することができ、ｈ１＝Ｈ（ｖｏｖ１）及びｈｉ＝Ｈ（［ｈｉ−１，ｖｉ］）であり、ｖｉが左側の子であれば、［ｈｉ，ｖｉ］は、ｖｉｏｈｉとなり、ｖｉが右側の子であれば、ｈｉｏｖｉである。
【００４２】
グラウンデッド・デンス・ハッシュ木の概念は、ｋ個のチェーンでつながれたグラウンデッド・デンス・ハッシュ木に以下のように拡張される。最下位の頂点は、長さ１のハッシュチェーンとみなす。それらは、長さｋのハッシュチェーンに置き換えることができる。この拡張により、グラウンデッド・デンス・ハッシュ木と通常のハッシュチェーンから得られるトレードオフ間の中間点がもたらされる。説明のために図９を参照されたい。図９は、ｋ個のチェーンにつながれたグラウンデッド・デンス・ハッシュであり、ｋ＝３である。図９の木は、最下位の頂点がハッシュチェーンに置き換えられていることを除き、グラウンデッド・デンス・ハッシュ木のように見えることに注目されたい。
ＮＯＶＯＭＯＤＯ
【００４３】
ＭｉｃａｌｉのＮＯＶＯＭＯＤＯ方式について、以下に説明する。この方式は、認証局がユーザに証明書を発行する設定段階と、認証局が無効又は有効の効率的なプルーフを提供する更新段階と、オーナの証明書の状態をユーザが判断する検証段階の、３つの段階に分割できる。
設定
【００４４】
ｆを、その反復において一方向である関数とする。Ｄを、従来の証明書データを示すものとする（例えば、シリアル番号、ユーザのＩＤとなるストリング、発行日、有効期限）。ｐを、認証方式における周期数を示すものとする。簡潔にするために、一実施形態において、ｐは、３６５とする。認証局は、２つの数字を証明書データＤに関連付ける。これら２つの数字、ｙｐとＮは、以下のように計算される。認証局は、｛０，１｝ｎからｙ０とＮ０の値をランダムに選択し、ｙｐ＝ｆｐ（ｙ０）、Ｎ１＝ｆ（Ｎ０）に設定する。値ｙｐは、有効ターゲットであり、Ｎ１は、無効ターゲットであるが、その理由は、以下で明らかにする。証明書は、増補されたデータ｛Ｄ，ｙｐ，Ｎ１｝と、このデータに対する認証局の署名とからなる。
定期的な証明書の更新
【００４５】
ディレクトリは、周期ごとに更新される（例えば、ｐ＝３６５ならば、１年間有効である証明書の更新間隔は１日のことがある）。周期ｉで証明書が有効であれば、認証局は、ｙｐ−ｉ＝ｆｐ−ｉ（ｙ０）を送信する。証明書が無効になっている場合、認証局は、Ｎ０を送信する。
証明書状態の検証
【００４６】
ユーザが、周期ｉで証明書の状態を検証したいものとする。証明書は、無効になっていると認証局が言っている場合、ユーザは、認証局が送信した値Ｎ０を取り出し、確かにＮ１＝ｆ（Ｎ０）であるかどうかチェックする。Ｎ１は、証明書中にあるので、ユーザは、それを知っていることに注意されたい。同様に、証明書が無効になっていないと認証局が言っている場合、ユーザは、認証局が送信した値ｙｐ−ｉを取り出し、ｆｉ（ｙｐ−ｉ）＝ｙｐであるかどうかチェックする。この場合も、ユーザは、ｙｐを知っていることに注意されたい。
Ｍｅｒｋｌｅ木を用いたＮＯＶＯＭＯＤＯ
【００４７】
以下は、ＮＯＶＯＭＯＤＯをＭｅｒｋｌｅ木に直接拡張したものであり、Ｍ．Ｎａｏｒ及びＫ．Ｎｉｓｓｉｍ著，“Ｃｅｒｔｉｆｉｃａｔｅ Ｒｅｖｏｃａｔｉｏｎ ａｎｄ Ｃｅｒｔｉｆｉｃａｔｅ Ｕｐｄａｔｅ”，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＵＳＥＮＩＸ Ｓｅｃｕｒｉｔｙ，１９９８，と、Ｉ．Ｇａｓｓｋｏ他著、“Ｅｆｆｉｃｉｅｎｔ ａｎｄ Ｆｒｅｓｈ Ｃｅｒｔｉｆｉｃａｔｉｏｎ”，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＰＫＣ ２０００，２０００において説明されたものである。認証局は、擬似乱数値をそれぞれ割り当てられた２ｐ個の葉ｌ１，…，ｌ２ｐを有するＭｅｒｋｌｅ木を作成し、その根に署名する。葉は、左から右へ１から２ｐまで番号付けされる。時間周期ｉで証明書が有効ならば、認証局は、Ｖａｌｕｅ（ｌ２ｉ）とＶａｌｕｅ（ＣｏＮｏｄｅｓ（ｌ２ｉ））を送信する。
基本的デンス・ハッシュ木を用いたＮＯＶＯＭＯＤＯ
【００４８】
Ｅｌｗａｉｌｌｙ及びＲａｍｚａｎが、Ｆ．Ｅｌｗａｉｌｌｙ及びＺ．Ｒａｍｚａｎ著，“ＱｕａｓｉＭｏｄｏ：Ｍｏｒｅ Ｅｆｆｉｃｉｅｎｔ Ｈａｓｈ Ｔｒｅｅ−Ｂａｓｅｄ Ｃｅｒｔｉｆｉｃａｔｅ Ｒｅｖｏｃａｔｉｏｎ”，Ｍａｎｕｓｃｒｉｐｔ，２００３で指摘したように、ＮＯＶＯＭＯＤＯにおけるＭｅｒｋｌｅ木は、デンス・ハッシュ木に置き換えることができる。この木は、最下層の葉が欠けていることを除けば、グラウンデッド・デンス・ハッシュ木のように見える。デンス・ハッシュ木を用いることにより、Ｍｅｒｋｌｅ木に対し１．５倍の改善がもたらされるのに対し、本明細書に記載のグラウンデッド・デンス・ハッシュ木では、２倍の改善がもたらされる。
単一の証明書を無効にするためのデンス・ハッシュ木
【００４９】
本発明の実施形態は、認証局が、コンパクトで検証しやすい有効プルーフ又は無効プルーフを生成するのを可能にする、安全で効率的な証明書無効化方法、構成要素及びシステムを提供するよう構成されている。本発明の一実施形態は、ＭｉｃａｌｉのＮＯＶＯＭＯＤＯシステムを改良したものである。Ｍｉｃａｌｉの構成のハッシュチェーンをグラウンデッド・デンス・ハッシュ木に置き換えることによって、多数の望ましいトレードオフが得られる。
【００５０】
ＮＯＶＯＭＯＤＯ方式については、すでに説明したので、グラウンデッド・デンス・ハッシュ木を利用する本発明の一実施形態について説明する。本発明の実施形態は、高位において、ＮＯＶＯＭＯＤＯハッシュチェーンをグラウンデッド・デンス・ハッシュ木に置き換える。すでに述べたように、検証において内部ノードも用いることを除いて、この木は、Ｍｅｒｋｌｅ木に類似している。
設定
【００５１】
ＮＯＶＯＭＯＤＯにおけるように、Ｄが従来の証明書データを示すものとする。認証局は、２つの数字を証明書データＤに関連付ける。これら２つの数字、ｙｒとＮ１は、以下のように計算される。認証局は、グラウンデッド・デンス・ハッシュ木を構成し、ｙｒをその木の根に割り当てられた値に設定する。認証局は、ＮＯＶＯＭＯＤＯでそうしたように、Ｎ１＝ｆ（Ｎ０）に設定する。証明書は、増幅されたデータ（Ｄ，ｙｒ，Ｎ１）と、このデータに対する認証局の署名とからなる。
【００５２】
図１は、認証局が設定段階に行う処理の一実施形態のフロー図である。この処理は、処理ロジックによって実行する。処理ロジックは、ハードウェア（例えば、回路、専用ロジック等）やソフトウェア（汎用コンピュータシステムや専用機で実行するもの等）、又は、両者の組み合わせからなるものがある。
【００５３】
図１について、該処理は、処理ロジックが多数の有効期間を設定することから始まる（処理ブロック１０１）。次に、処理ロジックは、ユーザごとにグラウンデッド・デンス・ハッシュ木を生成する（処理ブロック１０２）。その際、処理ロジックは、変数Ｙに等しい根の値を示す。次に、処理ロジックは、根の値を有効ターゲットに設定する（処理ブロック１０３）。処理ロジックは、無効ターゲットＮ１を生成する（処理ブロック１０４）。
【００５４】
有効ターゲットと無効ターゲットを生成した後、処理ロジックは、上述したような従来の証明書データと、有効ターゲットと無効ターゲットとからなる証明書データを構成する（処理ブロック１０５）。その後、処理ロジックは、増やされた証明書データ（有効ターゲットと無効ターゲットを有する従来の証明書データ）と、この増やされた証明書データに対する認証局の署名とからなる証明書を構成する（処理ブロック１０６）。次に、処理ロジックは、オーナに証明書を発行する（処理ブロック１０７）。
【００５５】
図５は、システム構成要素の一実施形態のブロック図である。このシステム構成要素は、認証局要素や、検証者要素や、オーナ要素であることがある。各構成要素は、記憶装置と双方向に通信する処理装置を含む。処理装置は、上記の処理を実行するのに適切なプログラムコードを実行して、証明書を発行し、無効化し、認証し、検証する。処理装置は、また、他の構成要素に送信する情報を生成するのに適切なプログラムコードを実行する。適切なプログラムコードは、当該技術において公知の方法によって作成することがある。記憶装置は、プログラムコードと、証明書の発行処理、無効化処理、認証処理、及び検証処理の実行中に使用する中間結果や他の情報を記憶する。
【００５６】
図５において、構成要素は、処理装置５０１と記憶装置５０２とを含む。これらの要素は、協働して、本明細書に記載のオペレーションを実行する。例えば、処理装置５０１と記憶装置５０２が認証局要素からなる場合、それらは協働して、図１に示すフロー図のオペレーションを実行する。同様に、処理装置５０１と記憶装置５０２が検証者要素からなる場合、協働して図４に示すフロー図の機能を実行する。また、処理装置５０１と記憶装置５０２がオーナ要素として協働する場合、図３に示すオペレーションを実行する。
【００５７】
通信ネットワークが設けられ、その上でこれらの構成要素は通信できる。通信ネットワークは、例えば、ＬＡＮコンピュータネットワーク、ＷＡＮコンピュータネットワーク、及び／又は移動電話ネットワーク等の、様々な一般的形態であることがある。
【００５８】
図３は、証明書オーナが実用で行う処理の一実施形態のフロー図である。この処理は、処理ロジックによって行われる。処理ロジックは、ハードウェア（例えば、回路、専用ロジック等）やソフトウェア（汎用コンピュータシステムや専用機で実行するもの等）、又は、両者の組み合わせからなるものがある。
【００５９】
図３において、該処理は、処理ロジックが認証局に登録し、身分証明を提供することによって始まる（処理ブロック３０１）。次に、処理ロジックは、認証局からデジタル証明書を受信する（処理ブロック３０２）。デジタル証明書を受信した後、処理ロジックは、証明書情報が正確であるかどうか判断する（処理ブロック３０３）。正確でない場合、処理ロジックは、処理ブロック３０１に戻り、処理を繰り返す。証明書情報が正確である場合、処理ロジックは、認証局の署名が有効であるかどうかを判断する（処理ブロック３０４）。有効でない場合、処理は、処理ブロック３０１に移り、処理を繰り返す。認証局の署名が有効である場合、処理は終了する。
定期的な証明書の更新
【００６０】
一実施形態において、ディレクトリは、周期ごとに更新される。周期ｉで、認証局は、以下のように計算される値ｃを証明書ごとに送信する。一実施形態において、証明書が有効ならば、認証局は、Ｖａｌｕｅ（ｇｖ（ｉ））を、Ｖａｌｕｅ（ＣｏＮｏｄｅｓ（ｇｖ（ｉ）））と共に送信する。証明書が無効になっているならば、認証局は、Ｎ０を送信する。
【００６１】
図２は、認証局が実用で行う処理の一実施形態のフロー図である。処理は、処理ロジックによって実行される。処理ロジックは、ハードウェア（例えば、回路、専用ロジック等）やソフトウェア（汎用コンピュータシステムや専用機で実行するもの等）、又は、両者の組み合わせからなるものがある。
【００６２】
図２において、該処理は、処理ロジックが特定の間隔ｉで、証明書オーナに関する有効状態の情報に対するリクエストを受信することによって始まる（処理ブロック２０１）。次に、処理ロジックは、オーナの証明書が無効になっているかどうかを判断する（処理ブロック２０２）。無効になっている場合、処理ロジックは、処理ブロック２０３に移行する。そこで、処理ロジックは、無効ターゲットのプリイメージを取り出して、その値をリクエスト元に送信し（処理ブロック２０４）、処理は終了する。オーナの証明書が無効になっていない場合、処理ロジックは、ｉ番目の灰色頂点の補ノードの値を計算し（処理ブロック２０５）、リクエスト元がどの補ノードの値が必要であるかを示しているか判断する（処理ブロック２０６）。示していなかった場合、処理ロジックは、全ての補ノードの値をリクエスト元に送信し（処理ブロック２０８）、処理は終了する。リクエスト元がどの補ノードの値が必要であるかを示しているならば、処理ロジックは、リクエストされた補ノードの値をリクエスト元に送信し（処理ブロック２０７）、処理は終了する。
証明書状態の検証
【００６３】
ユーザが、周期ｉで証明書の状態を検証したいものとする。証明書は無効になっていると認証局が言っている場合、ユーザは、認証局が送信した値Ｎ０を取り出し、確かにＮ１＝ｆ（Ｎ０）であるかどうか判定する。証明書は無効になっていないと認証局が言っている場合、ユーザは、Ｖａｌｕｅ（ｇｖ（ｉ））とＶａｌｕｅ（ＣｏＮｏｄｅｓ（ｇｖ（ｉ）））の値を取り出し、それらを用いてグラウンデッド・デンス・ハッシュ木の根の値を計算する。計算したＭｅｒｋｌｅ根が値ｙｒと一致すれば、証明書は有効である。
【００６４】
或いは、ユーザがすでに前の周期ｊで証明書を検証しており、関連する検証情報を得ていて、証明書ｉに関連する頂点が、周期ｊの証明書に関連する頂点に根付いた部分木に存在するならば、ユーザは、補ノードを用いてその根まで計算するだけでよい。
【００６５】
図４は、実用で証明書検証者が行う処理の一実施形態のフロー図である。該処理は、処理ロジックによって実行される。処理ロジックは、ハードウェア（例えば、回路、専用ロジック等）やソフトウェア（汎用コンピュータシステムや専用機で実行するもの等）、又は、両者の組み合わせからなるものがある。
【００６６】
図４において、該処理は、処理ロジックがオーナに属する証明書を取得することから始まる（処理ブロック４０１）。次に、処理ロジックは、証明書が期限切れかどうかを判断する（処理ブロック４０２）。期限切れであれば、処理ロジックは、証明書を拒否し（処理ブロック４０４）、処理は終了する。証明書が期限切れでなければ、処理ロジックは、証明書情報が正確であるかどうか判断する（処理ブロック４０３）。正確でなければ、処理ロジックは、証明書を拒否し（処理ブロック４０４）、処理は終了する。証明書情報が正確であれば、処理ロジックは、認証局の署名が有効であるかどうか判断する（処理ブロック４０５）。有効でなければ、処理ロジックは、証明書を拒否し（処理ブロック４０４）、処理は終了する。認証局の署名が有効であれば、処理ロジックは有効プルーフか無効プルーフを取得する（処理ブロック４１１）。
【００６７】
その後、処理ロジックは、有効プルーフを受信したかどうかを判断する（処理ブロック４０７）。受信していない場合、処理ロジックは、証明書を拒否し（処理ブロック４０６）、処理は終了する。処理ロジックが有効プルーフを受信している場合、処理ロジックは、プルーフが正確であるかどうか判断する（処理ブロック４０８）。正確でなければ、処理ロジックは、証明書を拒否し（処理ブロック４０６）、処理は終了する。プルーフが正確であれば、処理ロジックは、証明書を受け取り（処理ブロック４０９）、処理は終了する。
【００６８】
図６は、本発明の一実施形態による、認証局と、証明書検証者と、証明書オーナとを含むシステム構成である。図６において、認証局要素６０１は、１つ又は複数の通信ネットワークを介して、検証者要素６０２とオーナ要素６０３とに通信可能に連結されている。検証者要素６０２は、通信ネットワークを介してオーナ要素６０３に通信可能に連結されている。一実施形態において、これらの要素はそれぞれ、図５に示す要素からなる。認証局要素６０１は、証明書と証明書データ６１１とをオーナ要素６０３に送信する。検証者要素６０２とオーナ要素６０３は、オーナ証明書６１０をやりとりする。検証者要素６０２と認証局要素６０１は、有効プルーフ又は無効プルーフ６２０をやりとりする。
複数の証明書を無効にするためのデンス・ハッシュ木
【００６９】
本発明の他の実施形態において、複数の証明書を同時に無効にすることができる。
【００７０】
複数の証明書を同時に無効にする一般的方式を以下に説明し、それをインスタンス化する方法例を続けて説明する。この方式を説明するために、補集合カバーファミリ（ｃｏｍｐｌｅｍｅｎｔ ｃｏｖｅｒ ｆａｍｉｌｙ）という概念を考慮する。全ての証明書所有者の集合を（証明書が通常より早く無効になっているかどうかに関わらず）Ｕで示すものとする。ＲをＵの部分集合とし、証明書が有効期限前に無効になった証明書所有者の集合を示す。
【数１３】
とする。すなわち、
【数１４】
は、証明書が現在無効ではない証明書所有者の集合である。
【００７１】
定義１．Ｕの部分集合からなる集合をＳとする。
【数１５】
であれば、Ｓは、Ｒの補集合カバーである。
【００７２】
定義２．Ｕの部分集合からなる集合をＦとする。Ｕの部分集合Ｒごとに、ＦがＲの補集合カバーを含むならば、その場合に限り、Ｆは、Ｕの補集合カバーファミリとなる。すなわち、Ｕの部分集合Ｒごとに、ＳがＲの補集合カバーとなるように、Ｆの部分集合Ｓが存在する。
【００７３】
補集合カバーファミリの簡単な例の１つは、全てが単集合の集合である。すなわち、Ｕ＝｛ｕ１，…，ｕＮ｝であれば、集合Ｆ＝｛｛ｕ１｝，…，｛ｕＮ｝｝が補集合カバーであることは、当業者であれば容易に分かる。同様に、どの集合のベキ集合も補集合カバーファミリであることは自明である。ある集合のベキ集合は、全ての部分集合の集合である。
【数１６】
【００７４】
高位において、認証局は、まず証明書所有者の全体集合に対し、補集合カバーファミリを構成する。次に、認証局は、補集合カバーファミリの各要素にハッシュチェーンを割り当てる。特定の証明書オーナに関し、ユーザが属するＦの要素の集合をＦ（Ｏｗｎｅｒ）で示すものとする。認証局は、ユーザの証明書に、Ｆ（Ｏｗｎｅｒ）の要素に対応するハッシュチェーンの根を有効ターゲットとして含める。次に、周期ｉでユーザの集団の有効プルーフを提供するために、認証局は、まず、無効にされたユーザＲの集合を決定する。次に、認証局は、Ｆに含まれるＲの補集合カバーを計算し、ここではＳと呼ぶ。Ｆが全体集合Ｕの補集合カバーファミリであるので、かかる補集合カバーＳが存在することに注意されたい。認証局は、Ｓの要素ごとに、関連するハッシュチェーンのｉ番目の値を生成する。ユーザの証明書の有効性を確認するのに、検証者は、Ｓの少なくとも１つの要素がＦ（Ｏｗｎｅｒ）に含まれるかどうか確認するだけでよい。
設定
【００７５】
反復において一方向である関数をｆとする。全ての証明書所有者の全体集合をＵで示すものとする。次に認証局は、補集合カバーファミリを構成する。これをＵの中のＦと呼ぶ。認証局は、Ｆの要素ごとに、ｐ周期を可能にする独立したグラウンデッド・デンス・ハッシュ木を構成する。
【００７６】
従来の証明書データをＤで示すものとする（例えば、シリアル番号、ユーザのＩＤとなるストリング、発行日、及び有効期限）。証明書方式における周期数をｐで示すものとする。認証局は、証明書データに、有効ターゲットの集合と単一の無効ターゲットとを以下のように関連付ける。認証局は、｛０，１｝ｎから値Ｎ０をランダムに選ぶ。Ｎ１＝ｆ（Ｎ０）に設定する。Ｎ１は、無効ターゲットを示す。
【００７７】
次に、認証局は、証明書オーナに対し有効ターゲットの集合を以下のように構成する。認証局は、Ｆ（Ｏｗｎｅｒ）を計算する。Ｆ（Ｏｗｎｅｒ）は、オーナが一員であるＦの要素からなる集合である。ｋ個のＦ（Ｏｗｎｅｒ）の要素が存在するものとし、Ｆ１；…；Ｆｋと呼ぶ。Ｆ１…Ｆｋに関連するグラウンデッド・デンス・ハッシュ木の根の値をｒ１；…；ｒｋで示すものとする。
【００７８】
証明書は、増補されたデータ〈Ｄ，ｒ１；…；ｒｋ；Ｎ１〉と、このデータに対する認証局の署名とからなる。
定期的な証明書の更新
【００７９】
ディレクトリは、周期ごとに更新される。認証局は、周期ｉで、以下の値を送信する。ある証明書が無効であるならば、認証局は、その無効ターゲットのプリイメージを送信する。これは、各証明書に関連するＮ０値である。証明書が有効であれば、認証局は、以下を実行する。認証局は、まず、無効とされた所有者の集合Ｒを決定する。認証局は、ＳがＲの補集合カバーとなるように、要素Ｓ∈Ｆを計算する。Ｆは、全体集合Ｕの補集合カバーであるので、かかるＳが存在する。認証局は、Ｓの要素ごとに、その要素に対応する木に関連する値Ｖａｌｕｅ（ｇｖ（ｉ））を、Ｖａｌｕｅ（ＣｏＮｏｄｅｓ（ｇｖ（ｉ）））と共に送信する。
証明書状態の検証
【００８０】
ユーザが周期ｉで、オーナに属する証明書の状態を検証したいものとする。ユーザは、まず、証明書それ自体が期限切れになっておらず、認証局による署名が有効であるか確認する。次に、証明書が無効になっていると認証局が言っている場合、ユーザは、認証局が送信した値Ｎ０を取り出し、確かにＮ１＝ｆ（Ｎ０）であるか確認する。証明書が無効になっていないと認証局が言っている場合、ユーザは、Ｆ（Ｏｗｎｅｒ）に含まれる補集合カバーの要素に関連するＶａｌｕｅ（ｇｖ（ｉ））とＶａｌｕｅ（ＣｏＮｏｄｅｓ（ｇｖ（ｉ）））の値を取り出す。ユーザは、グラウンデッド・デンス・ハッシュ木の根の値を計算する。計算した根が証明書に含まれる根と一致すれば、証明書は有効である。
【００８１】
或いは、ユーザがすでに前の周期ｊで証明書を検証していて、関連する検証情報を持っており、証明書ｉに関連する頂点が、周期ｊの証明書に関連する頂点に根付いた部分木に含まれるならば、ユーザは、補ノードを用いてその根まで計算するだけでよい。
補集合カバーファミリの木構造
【００８２】
補集合カバーファミリの構造の１つは、２分木階層である。かかる補集合カバーファミリは、以下のように構成される。簡潔にするために、非負整数ｋに関し、証明書所有者の数は２ｋであるとする。２ｋの葉を持つ二分木を作成する。次に、証明書所有者の全体集合の１つの部分集合が各頂点に割り当てられる。２ｋの葉が存在するので、各葉は、単一の証明書所有者に対応することができる。各葉は、単一の証明書所有者からなる単集合に割り当てられる。次に、各内部ノードでは、その子供たちのノードの部分集合の和集合に相当する部分集合が割り当てられる。すなわち、ある頂点の部分集合は、その頂点に根付いた部分木の葉の証明書所有者に相当する。さて、その根に関連する部分集合が全体集合全体からなることを見てみよう。補集合カバーファミリＦは、全ての頂点に割り当てられた集合からなるだろう。Ｆが補集合カバーファミリを形成することは明らかである。特に、各証明書所有者は、葉において単集合として示されるので、任意の部分集合を構成することができる。しかし、それらの葉が完全な部分木を形成するオーナが、その部分木の根に関連する集合を用いてカバーを形成すればより効率的である。特に、最小サイズの（すなわち、最小数の集合を含む）部分集合Ｒ⊆Ｕの補集合カバーを構成するために、以下のステップを行う。
１．第１に、
【数１７】
の１要素に対応する各葉の頂点に「印を付ける」。
２．第２に、印を付けられた葉の頂点から根までの経路に沿う各内部頂点に「印をつける」。
３．第３に、印を付けられていないが、その親は、印を付けられている頂点を決定する。
４．第４に、これらの頂点に関連する部分集合を考慮する。
これらの部分集合は、最小サイズである
【数１８】
の補集合カバーを形成する。この方法は２分木に限定する必要はなく、実際には一般的な木に直接拡張する。
標準的なコンピュータシステム
【００８３】
図１０は、本明細書に記載の１つ又は複数のオペレーションを実行することができる、標準的なコンピュータシステムのブロック図である。図１０において、コンピュータシステム１０００は、標準的なクライアント１０５０やサーバ１０００のコンピュータシステムからなるものがある。コンピュータシステム１０００は、情報を通信するための通信機構、すなわちバス１０１１と、バス１０１１に接続されている情報を処理する処理装置１０１２とを含む。処理装置１０１２はマイクロプロセッサを含むが、例えば、ＰｅｎｔｉｕｍＴＭ、ＰｏｗｅｒＰＣＴＭ、ＡｌｐｈａＴＭ等のマイクロプロセッサに限定されない。
【００８４】
さらに、システム１０００は、バス１０１１に接続されている情報や処理装置１０１２が実行する命令を記憶するランダムアクセスメモリ（ＲＡＭ）や、他の動的記憶装置１００４（主記憶装置と呼ぶ）を含む。主記憶装置９０４は、処理装置１０１２が命令を実行している間に一時的数値変数や他の中間情報を記憶するのに用いることがある。
【００８５】
さらに、コンピュータシステム１０００は、バス１０１１に接続されている処理装置１０１２用の静的情報や命令を記憶する読出し専用メモリ（ＲＯＭ）及び／又は他の静的記憶装置１００６と、磁気ディスクや光ディスクなどのデータ記憶装置１００７と、それに対応するディスクドライブとを含む。データ記憶装置１００７はバス１０１１に接続され、情報や命令を記憶する。
【００８６】
さらに、コンピュータシステム１０００は、バス１０１１に接続されている情報をコンピュータユーザに表示する陰極線管（ＣＲＴ）や液晶表示装置（ＬＣＤ）等の表示装置１０２１に接続してもよい。英数字や他のキーを含む、英数字入力装置１０２２をバス１０１１に接続して、情報及び命令の選択を処理装置１０１２に通信するようにしてもよい。付加的なユーザ入力装置として、マウス、トラックボール、トラックパッド、スタイラス、カーソル方向キー等のカーソルコントロール１０２３があり、バス１０１１に接続して方向情報及び命令の選択を処理装置１０１２に通信し、表示装置１０２１でカーソルの動きを制御する。
【００８７】
バス１０１１に接続することがある他の装置としてハードコピー装置１０２４があり、紙、フィルム等の媒体や、同様の種類の媒体に、命令やデータや他の情報を印刷するのに用いてもよい。さらに、スピーカー及び／又はマイクロフォン等の録音及び再生装置をバス１０１１に随意接続して、コンピュータシステム１０００の音声インターフェースとしてもよい。バス１０１１に接続することがある他の装置として有線／無線通信機能１０２５があり、電話や携帯装置と通信する。
【００８８】
システム１０００の構成要素及び関連ハードウェアのいずれも、本発明において使用してもよいことに注意されたい。しかし、他の構成のコンピュータシステムが該装置のいくつか又は全てを含むことがあると考えることができる。
【００８９】
上述の説明を読んだ当業者であれば、本発明の様々な変更や修正は明らかに違いないが、例として示し説明した特定の実施形態が限定的なものであると見なされることは全く意図していないことを理解すべきである。従って、様々な実施形態の詳細に対する言及はクレームの範囲を限定するためのものではなく、クレームはそれ自体で、本発明に不可欠と考えられる特徴だけを記載している。
【図面の簡単な説明】
【００９０】
【図１】設定段階における認証局の処理の一実施形態のフロー図を示す。
【図２】設定段階における認証局の処理の一実施形態のフロー図を示す。
【図３】実用における証明書オーナの処理の一実施形態のフロー図を示す。
【図４】実用における証明書検証者の処理の一実施形態のフロー図を示す。
【図５】本発明の一実施形態による、認証局要素や、検証者要素や、オーナ要素を表す要素を示す。
【図６】本発明の一実施形態による、認証局と、証明書検証者と、証明書オーナとを有するシステム構成を示す。
【図７】Ｍｅｒｋｌｅ木と比較したグラウンデッド・デンス・ハッシュ木の例を示す。
【図８】Ｍｅｒｋｌｅ木と比較したグラウンデッド・デンス・ハッシュ木の例を示す。
【図９】ｋ個のチェーンにつながれたグラウンデッド・デンス・ハッシュ木を示す。
【図１０】標準的なコンピュータシステムのブロック図を示す。
【技術分野】
【０００１】
本出願は、２００３年９月１９日に出願された“ＭＥＴＨＯＤ ＡＮＤ ＡＰＰＡＲＡＴＵＳ ＦＯＲ ＥＦＦＩＣＩＥＮＴ ＣＥＲＴＩＦＩＣＡＴＥ ＲＥＶＯＣＡＴＩＯＮ”という名称の、本出願に対応する仮特許出願第６０／５０４，２５３号に対する優先権を主張し、参照することにより本明細書に含む。
【０００２】
本発明は、暗号分野に関する。特に、本発明は、証明書の無効化に関する。
【背景技術】
【０００３】
世の中がますますオンライン化する傾向は続くにつれて、公開鍵暗号法が一般的によく使用されるようになっていくであろう。かかる使用の基礎として、公開鍵と権限とを関係付けるポリシー、処理、人員、及び施設を構成する公開鍵インフラストラクチャを確立しなければならない。この公開鍵インフラストラクチャは認証局（ＣＡ）によって管理される。認証局は、公開鍵を識別子や権限に関係付けるデジタル証明書を発行するだけでなく、このようなデジタル証明書の管理もしている。証明書を発行する際、認証局は、ユーザの身分証明が正確であるかを必ず確かめなければならない。しかし、証明書を無効にする必要がある場合、処理はもっと複雑になることがある。
【０００４】
証明書の有効性が有効期限によって制限されることがあるが、証明書をその有効期限より前に無効にしなければならない場合がある。例えば、鍵の所有者がその所属や職業を変えることもあれば、さらに悪いことには、その秘密鍵の信用が損なわれていることもある。従って、証明書を無効にする何らかの方法が必要である。
【０００５】
証明書を無効にする一般的な方法の１つは、証明書失効リスト（ＣＲＬ：Ｃｅｒｔｉｆｉｃａｔｅ Ｒｅｖｏｃａｔｉｏｎ Ｌｉｓｔ）を用いるものである。証明書失効リストは、認証局によって発行され、電子的に署名され、タイムスタンプされたリストであり、シリアル番号、名前、メールアドレス等の何らかの識別子により、どの証明書が無効になったかを示している。たとえ変更がなくても、このようなＣＲＬを定期的に配信して、いかなるタイプのリプレイ攻撃も防御しなければならない。この方法は簡単なように見えるかもしれないが、ＣＲＬを管理することは、通信や調査や検証にかかる費用に関して非現実的なことがある。
【０００６】
他の方法には、証明書失効木（ＣＲＴ：Ｃｅｒｔｉｆｉｃａｔｅ Ｒｅｖｏｃａｔｉｏｎ Ｔｒｅｅ）を使用するものがある。ＣＲＴは、Ｍｅｒｋｌｅ木であり、各葉（ｌｅａｆ）が、無効になった証明書のグループに関連付けられている。従って、葉の要素を用いて論理プルーフを形成することができ、プルーフは、Ｍｅｒｋｌｅ木のプロパティにより検証することができる。
【０００７】
認証局は、無効になった証明書の完全なリストを通知するかわりに、オンライン方法を用いて、特定の証明書についてのクエリーに応答するようにしてもよい。この方法は、オンライン証明書状態プロトコル（ＯＣＳＰ：Ｏｎｌｉｎｅ Ｃｅｒｔｉｆｉｃａｔｅ Ｓｔａｔｕｓ Ｐｒｏｔｏｃｏｌ）で使用されている。しかし、この方法には限界がある。第一に、有効プルーフ（ｖａｌｉｄｉｔｙ ｐｒｏｏｆ）は、かなり長くなるものもあるデジタル署名からなる。例えば、ＲＳＡ署名では、１０２４ビットの鍵により、署名は、１０２４ビットの長さになる。さらに、１０２４ビットの鍵は、セキュリティに関して低い。今後長期にわたる必要性のために、２０４８ビットのような鍵を考えなければならないであろう。認証局は、十分信頼できるものでなければならないので、その署名鍵は、それ相応に長くなる。従って、ＲＳＡの２０４８ビットの鍵サイズは、大きすぎることはない。さらに、多数のリクエストを処理しなければならないこともある認証局にとって、応答の１つ１つに署名するのは計算上実行不可能なことがある。認証局がたった１つの集中型装置であれば、全てのリクエストがそこを経由し、固有のリクエストの１つ１つに対しデジタル署名を計算しなければならないので、スケーラビリティに関する大きな問題が生じる。何らかのロードバランシングを取り入れて認証局を分散しようとすると、例えば慎重な扱いを要する署名鍵を複製するなどのセキュリティリスクがもたらされる。
【０００８】
Ｍｉｃａｌｉは、ＮＯＶＯＭＯＤＯという精密かつ簡潔な方式でこれらの問題に対処した。ＮＯＶＯＭＯＤＯ方式は、Ｘ．５０９等のいかなる標準的な認証形式にも使用でき、認証局が、例えば１日や１時間といった所定の時間間隔で、証明書の有効状態を提供することを可能にする。ＮＯＶＯＭＯＤＯは、単一のデジタル署名と共に１つのハッシュチェーンを使用する。その利点は、単一の署名のコストが、多くの有効プルーフで償却されることである。しかし、ＮＯＶＯＭＯＤＯは、２つのクエリーの間に過ぎた周期の数に比例した時間で、ハッシュチェーンを横断する必要がある。Ｎａｏｒ及びＮｉｓｓｉｍが指摘した自然な拡張は、Ｍｅｒｋｌｅ木を使用することである（Ｍ．Ｎａｏｒ及びＫ．Ｎｉｓｓｉｍ著，“Ｃｅｒｔｉｆｉｃａｔｅ Ｒｅｖｏｃａｔｉｏｎ ａｎｄ Ｃｅｒｔｉｆｉｃａｔｅ Ｕｐｄａｔｅ”，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＵＳＥＮＩＸ Ｓｅｃｕｒｉｔｙ，１９９８）。この方法において、検証者は、
【数１】
個のハッシュを計算して、証明書を検証しなければならない。もっとも、有効プルーフは、その時、
【数２】
個のハッシュ値からなるのだが。概して、この方法は、元のＮＯＶＯＭＯＤＯ方法に比べて、平均的な検証複雑性が大幅に減少しているので望ましい。それでも、まだいくつかの不利点がある。
１．検証と検証との間の時間が、
【数３】
よりも短いならば、元のＮＯＶＯＭＯＤＯ方式の方が、検証者が証明書を認証するのに要する時間は短い。
２．元のＮＯＶＯＭＯＤＯ方式におけるプルーフのサイズは、常に１ハッシュ値であり、拡張されたＮＯＶＯＭＯＤＯ方式のプルーフサイズよりもはるかに小さい。
ＮＯＶＯＭＯＤＯに関する詳細については、Ｓ．Ｍｉｃａｌｉ，“ＮＯＶＯＭＯＤＯ：Ｓｃａｌａｂｌｅ Ｃｅｒｔｉｆｉｃａｔｅ Ｖａｌｉｄａｔｉｏｎ ａｎｄ Ｓｉｍｐｌｉｆｉｅｄ ＰＫＩ Ｍａｎａｇｅｍｅｎｔ，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １ｓｔ Ａｎｎｕａｌ ＰＫＩ Ｒｅｓｅａｒｃｈ Ｗｏｒｋｓｈｏｐ，２００２を参照されたい。
【０００９】
ここで、ＡＬＯ方法として言及する他の方法は、Ａｉｅｌｌｏ、Ｌｏｄｈａ及びＯｓｔｒｏｖｓｋｙによるもので、複数のユーザに対する有効プルーフを同時に提供するために、ユーザを部分集合に区分する方法とともにＮＯＶＯＭＯＤＯのような方式を用いるものである。Ｗ．Ａｉｅｌｌｏ，Ｓ．Ｌｏｄｈａ及びＲ．Ｏｓｔｒｏｖｓｋｙ，“Ｆａｓｔ Ｄｉｇｉｔａｌ Ｉｄｅｎｔｉｔｙ Ｒｅｖｏｃａｔｉｏｎ”，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ａｓｉａｃｒｙｐｔ’０１，２００１を参照されたい。
【００１０】
ＡＬＯ方式では、別個のＮＯＶＯＭＯＤＯのようなハッシュチェーンを、かかるユーザ部分集合Ｓｉの各々に割り当てる。次に、一定の間隔で、無効になった証明書を有するユーザの集合をＴで表すとすれば、認証局は、最初に、
【数４】
において、カバーするインデックスｉ１，…，ｉｋを計算する。次に、各部分集合
【数５】
に対する有効プルーフを提供する。これにより、ユーザのグループを同時に検証することができる。この方法には、いくつかの欠点がある。第１に、部分集合を構成して、部分集合ごとにチェーンを備えることに関して付加的なオーバーヘッドが生じる。少なくとも、単集合の部分集合を生成しなければならない（これは、基本的に元のＮＯＶＯＭＯＤＯ方式をもたらす）。従って、ＡＬＯ方式により実際に改良しようとするなら、付加的な部分集合を計算する必要があり、付加的な作業が必要になることになる。第２に、元のＮＯＶＯＭＯＤＯ方式におけるように、ハッシュ計算の回数が有効性チェックの間隔に比例するので、大きくなることがある。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
証明書を無効にする方法及び装置が開示される。一実施形態において、該方法は、有効ターゲット（ｖａｌｉｄｉｔｙ ｔａｒｇｅｔ）と無効ターゲット（ｒｅｖｏｃａｔｉｏｎ ｔａｒｇｅｔ）とを有する証明書データ（ｃｅｒｔｉｆｉｃａｔｅ ｄａｔａ）を生成することを含み、有効ターゲットは、グラウンデッド・デンス・ハッシュ（ｇｒｏｕｎｄｅｄ ｄｅｎｓｅ ｈａｓｈ）木の根の値である。この方法はまた、証明書データを有する証明書（ｃｅｒｔｉｆｉｃａｔｅ）を発行することを含む。
本発明は、以下に与えられる詳細な記載及び本発明の様々な実施形態に付随する図面から、より十分に理解されるであろう。しかしながら、これらは、特定の実施形態に対いて本発明を限定するために用いられるべきではなく、あくまでも説明や理解のためだけのものである。
【課題を解決するための手段】
【００１２】
従って、上述の問題に対処するための方法、構成要素及びシステムを提供する。一実施形態において、Ｍｅｒｋｌｅ木を用いる代わりに、グラウンデッド・デンス・ハッシュ木（ＧＤＨ）を用いる。この方法では、Ｍｅｒｋｌｅ木でそうするように葉から処理を始めるのではなく、木の１つおきの内部ノードから処理を始める。その結果、全般的な検証の複雑性だけでなく、Ｎａｏｒ及びＮｉｓｓｉｍのＭｅｒｋｌｅ木に基づく方式における通信の複雑性の両方がただちに改善される。さらに、有効プルーフ（ｐｒｏｏｆ ｏｆ ｖａｌｉｄｉｔｙ）が小さいので、１つのパケット内に収まる可能性が高く、それにより、実際に必要な追加の通信がごくわずかとなる。
【００１３】
一実施形態において、グラウンデッド・デンス・ハッシュ木を使用して、複数のユーザに同時に適用することもあるプルーフを構成する。これにより、認証局は、少数のプルーフを発行するだけでよく、多数のユーザの証明書を検証するのに使用することができる。
【００１４】
本発明の一実施形態におけるシステムは、現在の周期をｐｔで表し、前回の有効性チェックの計算結果がキャッシュされているとして、有効性がチェックされた前回の周期をｐｃで表わすとして、多くても、
【数６】
の作業により、認証局が発行したオーナに属する証明書の有効性を、検証者Ｖが判断するのを可能にする。前回の有効性チェックがキャッシュされていない場合は、
【数７】
の作業が必要である。いずれの場合も、プルーフサイズは、有効性チェックを実行するのに必要な作業量に比例する。
【００１５】
ある方法の一実施形態が提供されており、かかる方法により認証局は、グラウンデッド・デンス・ハッシュ木を用いて、単一の証明書オーナ（ｃｅｒｔｉｆｉｃａｔｅ ｏｗｎｅｒ）の有効ターゲットを生成する。
【００１６】
本発明の別の実施形態は、ある方法を示すものであり、かかる方法により認証局は、このようなグラウンデッド・デンス・ハッシュ木を用いて、有効プルーフを構成する。有効プルーフのサイズは、ｔを有効期間として（例えば、ｔ＝１４は、３６５日のうちの１４日であることを意味する）、大きくてもＯ（ｌｏｇ（ｔ））である。
【００１７】
本発明の他の実施形態は、ある方法を含み、かかる方法により検証者は、ｔを有効期間として、多くてもＯ（ｌｏｇ（ｔ））の作業だけで、認証局が発行したプルーフの有効性を検証する。
【００１８】
本発明の実施形態は、本明細書に記載の方法のオペレーションを実行する認証局、検証者及びオーナの構成要素を含む。
【００１９】
本発明の一実施形態は、複数の証明書に対する１つの有効プルーフを検証者が発行できるようにすることによって、複数の証明書オーナに属する１つの証明書の有効性を検証者が同時に判断できるようにするシステムを含む。本発明の一実施形態は、複数の証明書の有効性に関し単一のプルーフを認証局が構成する方法を含む。本発明の他の実施形態は、認証局が発行したプルーフを検証者が検証する方法を含む。
【発明を実施するための最良の形態】
【００２０】
以下の説明において、多くの詳細を示すことで、本発明をさらに詳しく説明する。しかしながら、これらの詳細がなくても本発明が実行可能であることは、当業者にとって明らかであろう。他の例では、公知の構造や装置を、詳細図ではなくブロック図形式で示して、本発明が分かりにくくならないようにしている。
【００２１】
以下の詳細な説明のいくつかの部分は、コンピュータ記憶装置内のデータビットの演算のアルゴリズムや記号表現によって示されている。これらのアルゴリズムの記述や表現は、データ処理技術の技術者が、彼らの仕事の実態を他の当業者にもっとも効果的に伝えるのに用いる手段である。本明細書において、また一般的に、アルゴリズムは、望ましい結果に導くセルフコンシステントな一連の工程であるとみなされる。該工程は、物理量の物理的操作を必要とするものである。通常、必ずではないが、これらの量は、記憶、転送、結合、比較、その他の操作ができる電気信号や磁気信号の形態をとる。時には、主に一般的な使用のために、これらの信号をビット、値、要素、記号、文字、項、数字等で表すことは便利である。
【００２２】
しかしながら、これらや類似用語は、全て適切な物理量に関連付けるためのものであり、これらの量にあてはめる単なる便利なラベルと考えるべきである。以下の論述から明らかのように、特に違ったように記述されていないかぎり、本明細書全体において、「処理」、「演算」、「計算」、「判断」、「表示」等の用語を用いた論述は、コンピュータシステムのレジスタや記憶装置内の物理（電子）量で表されるデータを、コンピュータシステムの記憶装置やレジスタ、又は、他のかかる情報記憶装置、送信装置又は表示装置内の物理量で同様に表される他のデータに操作及び変換するコンピュータシステム又は類似の電子計算装置の動作及び処理を述べるものとなっている。
【００２３】
本発明はまた、本明細書のオペレーションを実行する装置に関する。この装置は、必要な目的のために特別に構成されていてもよいし、コンピュータ内に記憶するコンピュータプログラムによって選択的に起動するか再構成する汎用コンピュータを含むものであってもよい。かかるコンピュータプログラムは、例えばフロッピーディスク、光ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、読出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カード又は光カードを含むいかなるタイプのディスクや、電子命令を記憶するのに適したいかなるタイプの媒体など、それぞれコンピュータシステムバスに接続されるコンピュータ読取り可能記憶媒体に記憶されてもよいが、それに限定されない。
【００２４】
本明細書に提示されるアルゴリズムやディスプレイは、特定のコンピュータや他の装置に本質的に関連するものではない。本明細書の教示によるプログラムとともに様々な汎用システムを使用してもよいし、必要な方法段階を実行するためにより専門化した装置を構成すれば便利であるかもしれない。これらの様々なシステムに必要な構造は、以下の記載から明らかである。さらに、本発明は、特定のプログラム言語に関連して述べられていない。本明細書に記載の本発明の教示を実行するのに、様々なプログラム言語を用いることができる。
【００２５】
機械読取り可能媒体は、機械（例えば、コンピュータ）が読み取ることができる形式で情報を記憶又は送信するための構造を含む。例えば、機械読取り可能媒体は、読出し専用メモリ（「ＲＯＭ」）、ランダムアクセスメモリ（「ＲＡＭ」）、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリ装置、電気、光、音響、その他の形態の伝播信号（例えば、搬送波、赤外線信号、デジタル信号等）等を含む。
【００２６】
準備段階
本明細書に記載のモデルでは、認証局と、証明書オーナ又は所有者（オーナ）と、証明書検証者とが存在する。以下の論述において、オーナは、認証局が発行した証明書を有する。当然ながら、認証局という概念は、より一般的に、複数の個人に対してアクセス制御の特権や許可を発行する責任を持ついかなる局にもあてはまる。オーナという概念は、例えばワールドワイドウェブサーバなどのコンピュータやエンティティを操作する特定の人間であることがある。同様に、検証者は、コンピュータを操作する特定の人間であることもあるし、特定のサービスに対するアクセスを許可すべきかどうかを判断するアクセス制御サーバ等のエンティティであることもある。
【００２７】
所定のトランザクションにおいて、証明書検証者は、証明書がその有効期限より前に無効になっていないことを確かめたい。そのため、証明書検証者は、認証局に有効プルーフ（ｐｒｏｏｆ ｏｆ ｖａｌｉｄｉｔｙ）か無効プルーフ（ｐｒｏｏｆ ｏｆ ｒｅｖｏｃａｔｉｏｎ）を求める。
【００２８】
望ましくは、認証局とオーナの両方が公開−秘密鍵のペアを有するように、オープン又はクローズド公開鍵インフラストラクチャを用いる。ここで鍵ペアは（Ｓｋ、Ｐｋ）と呼び、Ｓｋは、メッセージの署名を演算するための秘密署名鍵であり、Ｐｋは、Ｓｋに対応する公開検証鍵である。本明細書における目的のために、等式ＤＳ＝（ＫＧ，Ｓｉｇｎ，Ｖｆ）は、Ｇｏｌｄｗａｓｓｅｒ，Ｍｉｃａｌｉ及びＲｉｖｅｓｔ著，“Ａ Ｄｉｇｉｔａｌ Ｓｉｇｎａｔｕｒｅ Ｓｃｈｅｍｅ Ｓｅｃｕｒｅ Ａｇａｉｎｓｔ Ａｄａｐｔｉｖｅ Ｃｈｏｓｅｎ−Ｍｅｓｓａｇｅ Ａｔｔａｃｋｓ”，ＳＩＡＭ Ｊｏｕｒｎａｌ ｏｎ Ｃｏｍｐｕｔｉｎｇ，１７（２）：２８１−３０８，１９８８、の意味における、適応的な選択メッセージ攻撃のもとで、経験したことのある偽造に対して安全なデジタル署名方式を示す。ＫＧは、鍵生成アルゴリズムを示し、Ｓｉｇｎ（Ｓｋ，Ｍ）は、署名鍵ＳｋのもとでメッセージＭに対する署名σを出力する署名アルゴリズムを示し（署名アルゴリズムはランダムに選んでもよい）、Ｖｆ（Ｐｋ，Ｍ，σ）∈｛０，１｝は、公開鍵Ｐｋに関してメッセージＭの署名σが正確であれば、１と判断する検証アルゴリズムを示す。明確にするために、特定の個人に属する鍵を示すのに下付きを使用する。そうすると、ＨＳＰの鍵ペアは、（ＰｋＨＳＰ，ＳｋＨＳＰ）となり、Ｕの鍵ペアは、（ＰｋＵ，ＳｋＵ）となる。鍵生成アルゴリズムＫＧは、入力として、生成すべき鍵の長さを特定するセキュリティパラメータをとってもよい。その結果、認証者の鍵の長さは、標準的な証明書オーナのものよりも大きくなることがある。なぜなら、特に、前者の鍵の信用を損なう結果は、後者の鍵の信用を損なう結果よりもはるかに損害が大きい可能性が強いからである。
【００２９】
｛０，１｝＊が、全てのビットストリングの集合を示すものとする。ビットストリングｓに関し、その長さは、|ｓ|で示す。Ｈが、入力としてｂビットのペイロードとｖビットの初期ベクトル（ＩＶ）をとり、ｖビットの出力を生成する暗号圧縮関数を示すものとする。一実施形態において、ｂ≧２ｖであり、これは、使用されている公知の構造の全てに当てはまる。本明細書に記載される構造に関し、通常ｂ＝２ｖである。一実施形態において、これらの暗号圧縮関数は、耐衝突性である。すなわち、Ｈ（ＩＶ，ｍ１）＝Ｈ（ＩＶ，ｍ２）となるような２つの異なる入力ｍ１≠ｍ２を見つけるのは難しい。一実施形態において、ＩＶは、一定であり、公知である。表記を簡潔にするために、ＩＶは、ハッシュ関数における独立変数（ａｒｇｕｍｅｎｔ）として常に明記しない。かかる暗号圧縮関数の実際の例は、ＳＨＡ−１やＭＤ５に見られる。前者の圧縮関数は、２０バイトの出力とＩＶサイズであり、一方、後者に関しては、該サイズは１６バイトである。両方とも６４バイトのペイロードサイズである。一実施形態において、圧縮関数ペイロードサイズよりも大きいデータに演算は行われないが、そのためには、反復ハッシュやＭｅｒｋｌｅ木等の数々の標準技術が存在する。簡潔にするために、ハッシュ関数という用語を圧縮関数の代わりに用い、ハッシュ関数は、任意の長さのストリング｛０，１｝＊をとり、｛０，１｝ｖの固定長の出力を生成することができることになっている。記号Ｈは、かかる関数を示すのに用いられる。一方向性で耐衝突性であるハッシュ関数を用いるのが望ましい。
【００３０】
長さ保存関数ｆ：｛０，１｝ｎ→｛０，１｝ｎ、整数ｉ≧１に関して、ｆｉが、そのｆ倍の合成（ｆ-ｆｏｌｄ ｃｏｍｐｏｓｉｔｉｏｎ）を示すものとする。すなわち、ｉ＝１では、ｆｉ（ｘ）＝ｆ（ｘ）であり、ｉ＞１では、ｆｉ（ｘ）＝ｆ（ｆｉ−１（ｘ））である。ｘをランダムに選んだｆ（ｘ）が与えられた時、わずかな可能性を除いて、ｆ（ｚ）＝ｆ（ｘ）となるようなプリイメージ（ｐｒｅ-ｉｍａｇｅ）ｚを見つけるのが難しいならば、関数ｆは、一方向関数である。一方向関数ｆは、ｉに関し、ｆｉ（ｘ）を与えられた時、わずかな可能性を除いて、ｆ（ｚ）＝ｆｉ（ｘ）となるようなプリイメージｚを見つけるのが難しいならば、その反復において一方向であると言われる。実際には、ハッシュ関数Ｈから始めて、長さを保存するためにペイロードの一部をパッドすることによって、その反復において一方向である候補関数を構成することが多い。
【００３１】
最後に、実数ｒに関し、
【数８】
はｒの天井、すなわち、ｒ以上の最小の整数値である。同様に、
【数９】
はｒの床、すなわち、ｒ以下の最大の整数値を示す。
Ｍｅｒｋｌｅ木
【００３２】
重要な概念の１つは、Ｍｅｒｋｌｅ木であり、以下のように説明することができる。ｍ個の値ｘ１，…，ｘｍが存在し、それぞれ｛０，１｝ｎであるとする。簡潔にするために、ｍは、２の累乗とする。Ｈ：｛０，１｝２ｎ→｛０，１｝ｎを、２ｎビットストリングをｎビットストリングにマップする暗号ハッシュ関数とする。ハッシュ関数Ｈのもとのｘ１，…，ｘｍに対応するＭｅｒｋｌｅ木は、均衡な２分木であり、各ノードは、特定の値Ｖａｌｕｅ（ｖ）に関連付けられている。ｍ個の葉が存在し、各葉ｌｉに関して、Ｖａｌｕｅ（ｌｉ）＝Ｈ（ｘｉ），１≦ｉ≦ｍである。ｘｉは、｛０，１｝ｎに含まれるので表記を乱用しているが、Ｈの定義域は、｛０，１｝２ｎであることに注意されたい。この場合、Ｈは、適切にパディングされるものとする。内部頂点に関し、Ｃ０（ｖ）及びＣ１（ｖ）は、その左右の子を示すものとする。“ｏ”は連結演算を示すものとする。すると、Ｖａｌｕｅ（ｖ）＝Ｈ（ＩＶ，Ｖａｌｕｅ（Ｃ０（ｖ））ｏＶａｌｕｅ（Ｃ１（ｖ）））となる。Ｍｅｒｋｌｅ木のみが形式Ｖａｌｕｅｌｉ＝Ｈ（ｘｉ）の値を有する葉を持つものとみなされるが、Ｍｅｒｋｌｅ木は、これらの葉の下に、ｍ個の頂点からなる別の層をさらに有する。この頂点の集合は、値ｘｉを持ち、かかる頂点は、それぞれ、値Ｈ（ｘｉ）の頂点に結合されている。
【００３３】
Ｍｅｒｋｌｅ木は、デジタル署名のデータをダイジェストするのに使用することがあり、署名されたダイジェストは、根に対応付けられた値に相当する。また、基礎となる圧縮関数が耐衝突性であれば、Ｍｅｒｋｌｅ根の値が同一である２つの異なるメッセージを見つけるのは困難である。
グラウンデッド・デンス・ハッシュ木
【００３４】
グラウンデッド・デンス・ハッシュ（ＧＤＨ）木を構成する処理を以下に述べる。ＧＤＨ木は、表面上、内部頂点のいくつかを慎重に番号付けする以外は、Ｍｅｒｋｌｅ木のように見える。かかる木を使用する効力は、証明書無効化方式において、内部ノードの部分集合を直接利用することができることにある。その要点は、かかる方式の時間複雑性や通信複雑性の両方を改善することにある。この場合もまた、処理は、ｍ個の値、ｘ１，…，ｘｍから始まる。簡潔にするために、ある正の整数ｋに関して、ｍは、２ｋと同等であるものとする。木は、以下のように構成される。最下層にｍ個の頂点があり、それらは兄弟がいないという意味で一人子である頂点である。次に、Ｍｅｒｋｌｅ木でそうするように、深さｋ＋１の均衡２分木を構成し、各頂点に値を割り当てる。この木は、最下位のｍ個の頂点の上に存在する。値は、以下のように割り当てられる。最下位のｍ個の頂点は、それぞれ、値ｘ１，…，ｘｍをとる。最下層の上に直接乗っている層に、ｍ個の頂点を構成し、ｎビットの値ｆ（ｘｉ）をｉ番目のかかる頂点に割り当てる。ｆ：｛０，１｝ｎ→｛０，１｝ｎは、長さ保存一方向関数である。すなわち、ｌｉが、かかる頂点であれば、１≦ｉ≦ｍに関し、Ｖａｌｕｅｌｉ＝ｆ（ｘｉ）となる。次に、Ｈ：｛０，１｝２ｎ→｛０，１｝ｎを暗号ハッシュ関数とする。すると、２つの最下層の上にある内部ノードｖは、Ｖａｌｕｅ（ｖ）＝Ｈ（ＩＶ，Ｖａｌｕｅ（Ｃ０（ｖ））ｏＶａｌｕｅ（Ｃ１（ｖ）））となる。
【００３５】
同じ木が、以下のように別の方法で特徴付けられる。３ｍ−１個の頂点が存在する。これらは、それぞれ、ｌ１，…，ｌｍ，ｌ´１，…，ｌ´ｍ，及びｖ１，…，ｖｍ−１である。その値は、以下のように割り当てられる。１≦ｉ≦ｍに関し、Ｖａｌｕｅ（ｌｉ）＝ｘｉ及びＶａｌｕｅ（ｌ´ｍ）＝ｆ（ｘｉ）。次に、λ（ｉ）＝２（ｉ−ｍ／２）＋１とし、ρｉ＝２（ｉ−ｍ／２）＋２とする。ｉ∈｛ｍ／２，ｍ／２＋１，…，ｍ−１｝に関し、以下が適用できる。
【数１０】
最後に、ｉ∈｛１，…，ｍ／２−１｝に関し、
【数１１】
となる。
これにより、値が、頂点に割り当てられる。以下は、有向辺（ｄｉｒｅｃｔｅｄ ｅｄｇｅｓ）の説明である。高位では、Ｖａｌｕｅ（ｕ）が、Ｖａｌｕｅ（ｗ）の計算に明白に使用された場合、有向辺は、頂点ｕに隣接し、頂点ｗへのびる。より正確には、有向辺は、このように説明できる。１≦ｉ≦ｍに関し、ｌｉからｌ´ｉまで有向辺が存在する。ｉ∈｛ｍ／２，ｍ／２＋１，…，ｍ−１｝に関し、ｌ´λ（ｉ）からｖｉまで有向辺が存在し、ｌ´ρ（ｉ）からｖｉまで有向辺が存在する。最後に、ｉ∈｛１，…，ｍ／２−１｝に関し、ｖ２ｉからｖｉまで有向辺が存在し、ｖ２ｉ＋１からｖｉまで有向辺が存在する。
【００３６】
次に、以下の２つの着色を木のノードに施す。根は、白に着色する。根の左側の子は、灰色にし、根の右側の子は、白色にする。各頂点に向かって木を降りながら、各頂点は、その親の左側の子であれば、灰色に着色し、その親の右側の子であれば、白色に着色する。（ｌｉの頂点の場合のように）頂点が兄弟を持たない場合、灰色に着色する。すなわち、一人子は、同時に左側の頂点であり右側の頂点であるとみなすことができる。兄弟である２つの頂点に関し、一方のみを着色できるならば、他の着色方式を用いてもよいことに注意されたい。同様に、他の数でもよい。
【００３７】
最後に、灰色のノードを幅優先方法で番号付けする。すなわち、木の上端から始め、連続する位に１つ１つ降りていきながら、灰色ノードは、それぞれ左から右へ連続的に番号付けされる。説明例として、ｍ＝４の場合を考える。かかる場合、番号１は、根の左側の子に割り当てられる。番号２は、根の左側の子の左側の子に割り当てられる。番号３は、根の右側の子の左側の子に割り当てられる。番号４は、根の左側の子の左側の子の一人子に割り当てられる。番号５は、根の左側の子の右側の子の一人子に割り当てられる。番号６は、根の右側の子の左側の子の一人子に割り当てられる。最後に、番号７は、根の右側の子の右側の子の一人子に割り当てられる。一見、灰色頂点を番号付けするという考えは、何か不自然なようであるかもしれないが、周期ｉの有効プルーフにｉ番目の灰色頂点を含むことがその目的である。
【００３８】
ｉ番目の灰色頂点は、ｇｖ（ｉ）と呼ぶ。図７及び図８は、７周期の無効化方式に適応することができるグラウンデッド・デンス・ハッシュ木のラベリングの比較を示している。図７は、１１個の頂点を持つグラウンデッド・デンス・ハッシュであり、７周期間使用することができる。内部ノードは、それぞれ、その子どもたちの値のハッシュである値を持つ。灰色頂点は、それぞれ、幅優先順で連続的に番号付けされる。図８は、８周期を可能にするＭｅｒｋｌｅ木である。この木の基本部分は、１５の頂点を有するが、８つの付加的な陰の頂点が存在し、下位ハッシュの木の底辺から垂れ下がっている。木は、８周期間使用することができる。内部ノードを用いれば、よりコンパクトな木が見られる。すなわち、８周期に適応するＭｅｒｋｌｅ木は、グラウンデッド・デンス・ハッシュ木の２倍以上の頂点を必要とする。
【００３９】
一般に、ｍ個の葉を持つグラウンデッド・デンス・ハッシュ木は、３ｍ−１個の頂点を持ち、２ｍ−１周期に適応できる。ｍ個の葉を持つＭｅｒｋｌｅ木もまた、３ｍ−１個の頂点を持つが、ｍ周期にしか適応できない。グラウンデッド・デンス・ハッシュ木によるパフォーマンスの向上は２−１／ｍであり、ｍが大きくなるにつれて２に近づく。
【００４０】
ＧＤＨ木の所定の頂点の補ノード（ｃｏ-ｎｏｄｅ）という概念が、以下で用いられる。頂点ｖに関し、ＣｏＮｏｄｅｓ（ｖ）は、ｖから根までの経路上にある頂点の兄弟の集合である。より正式には、Ｓｉｂ（ｖ）とＰａｒｅｎｔ（ｖ）がそれぞれｖの兄弟と親を示すならば、
【数１２】
ここで、Ｖが根である場合、上式の値を取り、その他の場合、下式の値を取る。
最後に、補ノードの集合に関し、Ｖａｌｕｅ（ＣｏＮｏｄｅｓ（ｖ））は、頂点ｖの補ノードに対応する値を示す。補ノードに類似した概念は、Ｍｅｒｋｌｅ木に存在する。
【００４１】
補ノードが与えられた時、根の値を計算する一実施形態の方法は、以下のとおりである。ｉ番目の灰色頂点に対応する値をｖとし、ｉ番目の灰色頂点から根の頂点までの経路上にある全ての頂点の兄弟の値をｖ１，…，ｖとする。すると、根の値は、ｈとして計算することができ、ｈ１＝Ｈ（ｖｏｖ１）及びｈｉ＝Ｈ（［ｈｉ−１，ｖｉ］）であり、ｖｉが左側の子であれば、［ｈｉ，ｖｉ］は、ｖｉｏｈｉとなり、ｖｉが右側の子であれば、ｈｉｏｖｉである。
【００４２】
グラウンデッド・デンス・ハッシュ木の概念は、ｋ個のチェーンでつながれたグラウンデッド・デンス・ハッシュ木に以下のように拡張される。最下位の頂点は、長さ１のハッシュチェーンとみなす。それらは、長さｋのハッシュチェーンに置き換えることができる。この拡張により、グラウンデッド・デンス・ハッシュ木と通常のハッシュチェーンから得られるトレードオフ間の中間点がもたらされる。説明のために図９を参照されたい。図９は、ｋ個のチェーンにつながれたグラウンデッド・デンス・ハッシュであり、ｋ＝３である。図９の木は、最下位の頂点がハッシュチェーンに置き換えられていることを除き、グラウンデッド・デンス・ハッシュ木のように見えることに注目されたい。
ＮＯＶＯＭＯＤＯ
【００４３】
ＭｉｃａｌｉのＮＯＶＯＭＯＤＯ方式について、以下に説明する。この方式は、認証局がユーザに証明書を発行する設定段階と、認証局が無効又は有効の効率的なプルーフを提供する更新段階と、オーナの証明書の状態をユーザが判断する検証段階の、３つの段階に分割できる。
設定
【００４４】
ｆを、その反復において一方向である関数とする。Ｄを、従来の証明書データを示すものとする（例えば、シリアル番号、ユーザのＩＤとなるストリング、発行日、有効期限）。ｐを、認証方式における周期数を示すものとする。簡潔にするために、一実施形態において、ｐは、３６５とする。認証局は、２つの数字を証明書データＤに関連付ける。これら２つの数字、ｙｐとＮは、以下のように計算される。認証局は、｛０，１｝ｎからｙ０とＮ０の値をランダムに選択し、ｙｐ＝ｆｐ（ｙ０）、Ｎ１＝ｆ（Ｎ０）に設定する。値ｙｐは、有効ターゲットであり、Ｎ１は、無効ターゲットであるが、その理由は、以下で明らかにする。証明書は、増補されたデータ｛Ｄ，ｙｐ，Ｎ１｝と、このデータに対する認証局の署名とからなる。
定期的な証明書の更新
【００４５】
ディレクトリは、周期ごとに更新される（例えば、ｐ＝３６５ならば、１年間有効である証明書の更新間隔は１日のことがある）。周期ｉで証明書が有効であれば、認証局は、ｙｐ−ｉ＝ｆｐ−ｉ（ｙ０）を送信する。証明書が無効になっている場合、認証局は、Ｎ０を送信する。
証明書状態の検証
【００４６】
ユーザが、周期ｉで証明書の状態を検証したいものとする。証明書は、無効になっていると認証局が言っている場合、ユーザは、認証局が送信した値Ｎ０を取り出し、確かにＮ１＝ｆ（Ｎ０）であるかどうかチェックする。Ｎ１は、証明書中にあるので、ユーザは、それを知っていることに注意されたい。同様に、証明書が無効になっていないと認証局が言っている場合、ユーザは、認証局が送信した値ｙｐ−ｉを取り出し、ｆｉ（ｙｐ−ｉ）＝ｙｐであるかどうかチェックする。この場合も、ユーザは、ｙｐを知っていることに注意されたい。
Ｍｅｒｋｌｅ木を用いたＮＯＶＯＭＯＤＯ
【００４７】
以下は、ＮＯＶＯＭＯＤＯをＭｅｒｋｌｅ木に直接拡張したものであり、Ｍ．Ｎａｏｒ及びＫ．Ｎｉｓｓｉｍ著，“Ｃｅｒｔｉｆｉｃａｔｅ Ｒｅｖｏｃａｔｉｏｎ ａｎｄ Ｃｅｒｔｉｆｉｃａｔｅ Ｕｐｄａｔｅ”，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＵＳＥＮＩＸ Ｓｅｃｕｒｉｔｙ，１９９８，と、Ｉ．Ｇａｓｓｋｏ他著、“Ｅｆｆｉｃｉｅｎｔ ａｎｄ Ｆｒｅｓｈ Ｃｅｒｔｉｆｉｃａｔｉｏｎ”，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＰＫＣ ２０００，２０００において説明されたものである。認証局は、擬似乱数値をそれぞれ割り当てられた２ｐ個の葉ｌ１，…，ｌ２ｐを有するＭｅｒｋｌｅ木を作成し、その根に署名する。葉は、左から右へ１から２ｐまで番号付けされる。時間周期ｉで証明書が有効ならば、認証局は、Ｖａｌｕｅ（ｌ２ｉ）とＶａｌｕｅ（ＣｏＮｏｄｅｓ（ｌ２ｉ））を送信する。
基本的デンス・ハッシュ木を用いたＮＯＶＯＭＯＤＯ
【００４８】
Ｅｌｗａｉｌｌｙ及びＲａｍｚａｎが、Ｆ．Ｅｌｗａｉｌｌｙ及びＺ．Ｒａｍｚａｎ著，“ＱｕａｓｉＭｏｄｏ：Ｍｏｒｅ Ｅｆｆｉｃｉｅｎｔ Ｈａｓｈ Ｔｒｅｅ−Ｂａｓｅｄ Ｃｅｒｔｉｆｉｃａｔｅ Ｒｅｖｏｃａｔｉｏｎ”，Ｍａｎｕｓｃｒｉｐｔ，２００３で指摘したように、ＮＯＶＯＭＯＤＯにおけるＭｅｒｋｌｅ木は、デンス・ハッシュ木に置き換えることができる。この木は、最下層の葉が欠けていることを除けば、グラウンデッド・デンス・ハッシュ木のように見える。デンス・ハッシュ木を用いることにより、Ｍｅｒｋｌｅ木に対し１．５倍の改善がもたらされるのに対し、本明細書に記載のグラウンデッド・デンス・ハッシュ木では、２倍の改善がもたらされる。
単一の証明書を無効にするためのデンス・ハッシュ木
【００４９】
本発明の実施形態は、認証局が、コンパクトで検証しやすい有効プルーフ又は無効プルーフを生成するのを可能にする、安全で効率的な証明書無効化方法、構成要素及びシステムを提供するよう構成されている。本発明の一実施形態は、ＭｉｃａｌｉのＮＯＶＯＭＯＤＯシステムを改良したものである。Ｍｉｃａｌｉの構成のハッシュチェーンをグラウンデッド・デンス・ハッシュ木に置き換えることによって、多数の望ましいトレードオフが得られる。
【００５０】
ＮＯＶＯＭＯＤＯ方式については、すでに説明したので、グラウンデッド・デンス・ハッシュ木を利用する本発明の一実施形態について説明する。本発明の実施形態は、高位において、ＮＯＶＯＭＯＤＯハッシュチェーンをグラウンデッド・デンス・ハッシュ木に置き換える。すでに述べたように、検証において内部ノードも用いることを除いて、この木は、Ｍｅｒｋｌｅ木に類似している。
設定
【００５１】
ＮＯＶＯＭＯＤＯにおけるように、Ｄが従来の証明書データを示すものとする。認証局は、２つの数字を証明書データＤに関連付ける。これら２つの数字、ｙｒとＮ１は、以下のように計算される。認証局は、グラウンデッド・デンス・ハッシュ木を構成し、ｙｒをその木の根に割り当てられた値に設定する。認証局は、ＮＯＶＯＭＯＤＯでそうしたように、Ｎ１＝ｆ（Ｎ０）に設定する。証明書は、増幅されたデータ（Ｄ，ｙｒ，Ｎ１）と、このデータに対する認証局の署名とからなる。
【００５２】
図１は、認証局が設定段階に行う処理の一実施形態のフロー図である。この処理は、処理ロジックによって実行する。処理ロジックは、ハードウェア（例えば、回路、専用ロジック等）やソフトウェア（汎用コンピュータシステムや専用機で実行するもの等）、又は、両者の組み合わせからなるものがある。
【００５３】
図１について、該処理は、処理ロジックが多数の有効期間を設定することから始まる（処理ブロック１０１）。次に、処理ロジックは、ユーザごとにグラウンデッド・デンス・ハッシュ木を生成する（処理ブロック１０２）。その際、処理ロジックは、変数Ｙに等しい根の値を示す。次に、処理ロジックは、根の値を有効ターゲットに設定する（処理ブロック１０３）。処理ロジックは、無効ターゲットＮ１を生成する（処理ブロック１０４）。
【００５４】
有効ターゲットと無効ターゲットを生成した後、処理ロジックは、上述したような従来の証明書データと、有効ターゲットと無効ターゲットとからなる証明書データを構成する（処理ブロック１０５）。その後、処理ロジックは、増やされた証明書データ（有効ターゲットと無効ターゲットを有する従来の証明書データ）と、この増やされた証明書データに対する認証局の署名とからなる証明書を構成する（処理ブロック１０６）。次に、処理ロジックは、オーナに証明書を発行する（処理ブロック１０７）。
【００５５】
図５は、システム構成要素の一実施形態のブロック図である。このシステム構成要素は、認証局要素や、検証者要素や、オーナ要素であることがある。各構成要素は、記憶装置と双方向に通信する処理装置を含む。処理装置は、上記の処理を実行するのに適切なプログラムコードを実行して、証明書を発行し、無効化し、認証し、検証する。処理装置は、また、他の構成要素に送信する情報を生成するのに適切なプログラムコードを実行する。適切なプログラムコードは、当該技術において公知の方法によって作成することがある。記憶装置は、プログラムコードと、証明書の発行処理、無効化処理、認証処理、及び検証処理の実行中に使用する中間結果や他の情報を記憶する。
【００５６】
図５において、構成要素は、処理装置５０１と記憶装置５０２とを含む。これらの要素は、協働して、本明細書に記載のオペレーションを実行する。例えば、処理装置５０１と記憶装置５０２が認証局要素からなる場合、それらは協働して、図１に示すフロー図のオペレーションを実行する。同様に、処理装置５０１と記憶装置５０２が検証者要素からなる場合、協働して図４に示すフロー図の機能を実行する。また、処理装置５０１と記憶装置５０２がオーナ要素として協働する場合、図３に示すオペレーションを実行する。
【００５７】
通信ネットワークが設けられ、その上でこれらの構成要素は通信できる。通信ネットワークは、例えば、ＬＡＮコンピュータネットワーク、ＷＡＮコンピュータネットワーク、及び／又は移動電話ネットワーク等の、様々な一般的形態であることがある。
【００５８】
図３は、証明書オーナが実用で行う処理の一実施形態のフロー図である。この処理は、処理ロジックによって行われる。処理ロジックは、ハードウェア（例えば、回路、専用ロジック等）やソフトウェア（汎用コンピュータシステムや専用機で実行するもの等）、又は、両者の組み合わせからなるものがある。
【００５９】
図３において、該処理は、処理ロジックが認証局に登録し、身分証明を提供することによって始まる（処理ブロック３０１）。次に、処理ロジックは、認証局からデジタル証明書を受信する（処理ブロック３０２）。デジタル証明書を受信した後、処理ロジックは、証明書情報が正確であるかどうか判断する（処理ブロック３０３）。正確でない場合、処理ロジックは、処理ブロック３０１に戻り、処理を繰り返す。証明書情報が正確である場合、処理ロジックは、認証局の署名が有効であるかどうかを判断する（処理ブロック３０４）。有効でない場合、処理は、処理ブロック３０１に移り、処理を繰り返す。認証局の署名が有効である場合、処理は終了する。
定期的な証明書の更新
【００６０】
一実施形態において、ディレクトリは、周期ごとに更新される。周期ｉで、認証局は、以下のように計算される値ｃを証明書ごとに送信する。一実施形態において、証明書が有効ならば、認証局は、Ｖａｌｕｅ（ｇｖ（ｉ））を、Ｖａｌｕｅ（ＣｏＮｏｄｅｓ（ｇｖ（ｉ）））と共に送信する。証明書が無効になっているならば、認証局は、Ｎ０を送信する。
【００６１】
図２は、認証局が実用で行う処理の一実施形態のフロー図である。処理は、処理ロジックによって実行される。処理ロジックは、ハードウェア（例えば、回路、専用ロジック等）やソフトウェア（汎用コンピュータシステムや専用機で実行するもの等）、又は、両者の組み合わせからなるものがある。
【００６２】
図２において、該処理は、処理ロジックが特定の間隔ｉで、証明書オーナに関する有効状態の情報に対するリクエストを受信することによって始まる（処理ブロック２０１）。次に、処理ロジックは、オーナの証明書が無効になっているかどうかを判断する（処理ブロック２０２）。無効になっている場合、処理ロジックは、処理ブロック２０３に移行する。そこで、処理ロジックは、無効ターゲットのプリイメージを取り出して、その値をリクエスト元に送信し（処理ブロック２０４）、処理は終了する。オーナの証明書が無効になっていない場合、処理ロジックは、ｉ番目の灰色頂点の補ノードの値を計算し（処理ブロック２０５）、リクエスト元がどの補ノードの値が必要であるかを示しているか判断する（処理ブロック２０６）。示していなかった場合、処理ロジックは、全ての補ノードの値をリクエスト元に送信し（処理ブロック２０８）、処理は終了する。リクエスト元がどの補ノードの値が必要であるかを示しているならば、処理ロジックは、リクエストされた補ノードの値をリクエスト元に送信し（処理ブロック２０７）、処理は終了する。
証明書状態の検証
【００６３】
ユーザが、周期ｉで証明書の状態を検証したいものとする。証明書は無効になっていると認証局が言っている場合、ユーザは、認証局が送信した値Ｎ０を取り出し、確かにＮ１＝ｆ（Ｎ０）であるかどうか判定する。証明書は無効になっていないと認証局が言っている場合、ユーザは、Ｖａｌｕｅ（ｇｖ（ｉ））とＶａｌｕｅ（ＣｏＮｏｄｅｓ（ｇｖ（ｉ）））の値を取り出し、それらを用いてグラウンデッド・デンス・ハッシュ木の根の値を計算する。計算したＭｅｒｋｌｅ根が値ｙｒと一致すれば、証明書は有効である。
【００６４】
或いは、ユーザがすでに前の周期ｊで証明書を検証しており、関連する検証情報を得ていて、証明書ｉに関連する頂点が、周期ｊの証明書に関連する頂点に根付いた部分木に存在するならば、ユーザは、補ノードを用いてその根まで計算するだけでよい。
【００６５】
図４は、実用で証明書検証者が行う処理の一実施形態のフロー図である。該処理は、処理ロジックによって実行される。処理ロジックは、ハードウェア（例えば、回路、専用ロジック等）やソフトウェア（汎用コンピュータシステムや専用機で実行するもの等）、又は、両者の組み合わせからなるものがある。
【００６６】
図４において、該処理は、処理ロジックがオーナに属する証明書を取得することから始まる（処理ブロック４０１）。次に、処理ロジックは、証明書が期限切れかどうかを判断する（処理ブロック４０２）。期限切れであれば、処理ロジックは、証明書を拒否し（処理ブロック４０４）、処理は終了する。証明書が期限切れでなければ、処理ロジックは、証明書情報が正確であるかどうか判断する（処理ブロック４０３）。正確でなければ、処理ロジックは、証明書を拒否し（処理ブロック４０４）、処理は終了する。証明書情報が正確であれば、処理ロジックは、認証局の署名が有効であるかどうか判断する（処理ブロック４０５）。有効でなければ、処理ロジックは、証明書を拒否し（処理ブロック４０４）、処理は終了する。認証局の署名が有効であれば、処理ロジックは有効プルーフか無効プルーフを取得する（処理ブロック４１１）。
【００６７】
その後、処理ロジックは、有効プルーフを受信したかどうかを判断する（処理ブロック４０７）。受信していない場合、処理ロジックは、証明書を拒否し（処理ブロック４０６）、処理は終了する。処理ロジックが有効プルーフを受信している場合、処理ロジックは、プルーフが正確であるかどうか判断する（処理ブロック４０８）。正確でなければ、処理ロジックは、証明書を拒否し（処理ブロック４０６）、処理は終了する。プルーフが正確であれば、処理ロジックは、証明書を受け取り（処理ブロック４０９）、処理は終了する。
【００６８】
図６は、本発明の一実施形態による、認証局と、証明書検証者と、証明書オーナとを含むシステム構成である。図６において、認証局要素６０１は、１つ又は複数の通信ネットワークを介して、検証者要素６０２とオーナ要素６０３とに通信可能に連結されている。検証者要素６０２は、通信ネットワークを介してオーナ要素６０３に通信可能に連結されている。一実施形態において、これらの要素はそれぞれ、図５に示す要素からなる。認証局要素６０１は、証明書と証明書データ６１１とをオーナ要素６０３に送信する。検証者要素６０２とオーナ要素６０３は、オーナ証明書６１０をやりとりする。検証者要素６０２と認証局要素６０１は、有効プルーフ又は無効プルーフ６２０をやりとりする。
複数の証明書を無効にするためのデンス・ハッシュ木
【００６９】
本発明の他の実施形態において、複数の証明書を同時に無効にすることができる。
【００７０】
複数の証明書を同時に無効にする一般的方式を以下に説明し、それをインスタンス化する方法例を続けて説明する。この方式を説明するために、補集合カバーファミリ（ｃｏｍｐｌｅｍｅｎｔ ｃｏｖｅｒ ｆａｍｉｌｙ）という概念を考慮する。全ての証明書所有者の集合を（証明書が通常より早く無効になっているかどうかに関わらず）Ｕで示すものとする。ＲをＵの部分集合とし、証明書が有効期限前に無効になった証明書所有者の集合を示す。
【数１３】
とする。すなわち、
【数１４】
は、証明書が現在無効ではない証明書所有者の集合である。
【００７１】
定義１．Ｕの部分集合からなる集合をＳとする。
【数１５】
であれば、Ｓは、Ｒの補集合カバーである。
【００７２】
定義２．Ｕの部分集合からなる集合をＦとする。Ｕの部分集合Ｒごとに、ＦがＲの補集合カバーを含むならば、その場合に限り、Ｆは、Ｕの補集合カバーファミリとなる。すなわち、Ｕの部分集合Ｒごとに、ＳがＲの補集合カバーとなるように、Ｆの部分集合Ｓが存在する。
【００７３】
補集合カバーファミリの簡単な例の１つは、全てが単集合の集合である。すなわち、Ｕ＝｛ｕ１，…，ｕＮ｝であれば、集合Ｆ＝｛｛ｕ１｝，…，｛ｕＮ｝｝が補集合カバーであることは、当業者であれば容易に分かる。同様に、どの集合のベキ集合も補集合カバーファミリであることは自明である。ある集合のベキ集合は、全ての部分集合の集合である。
【数１６】
【００７４】
高位において、認証局は、まず証明書所有者の全体集合に対し、補集合カバーファミリを構成する。次に、認証局は、補集合カバーファミリの各要素にハッシュチェーンを割り当てる。特定の証明書オーナに関し、ユーザが属するＦの要素の集合をＦ（Ｏｗｎｅｒ）で示すものとする。認証局は、ユーザの証明書に、Ｆ（Ｏｗｎｅｒ）の要素に対応するハッシュチェーンの根を有効ターゲットとして含める。次に、周期ｉでユーザの集団の有効プルーフを提供するために、認証局は、まず、無効にされたユーザＲの集合を決定する。次に、認証局は、Ｆに含まれるＲの補集合カバーを計算し、ここではＳと呼ぶ。Ｆが全体集合Ｕの補集合カバーファミリであるので、かかる補集合カバーＳが存在することに注意されたい。認証局は、Ｓの要素ごとに、関連するハッシュチェーンのｉ番目の値を生成する。ユーザの証明書の有効性を確認するのに、検証者は、Ｓの少なくとも１つの要素がＦ（Ｏｗｎｅｒ）に含まれるかどうか確認するだけでよい。
設定
【００７５】
反復において一方向である関数をｆとする。全ての証明書所有者の全体集合をＵで示すものとする。次に認証局は、補集合カバーファミリを構成する。これをＵの中のＦと呼ぶ。認証局は、Ｆの要素ごとに、ｐ周期を可能にする独立したグラウンデッド・デンス・ハッシュ木を構成する。
【００７６】
従来の証明書データをＤで示すものとする（例えば、シリアル番号、ユーザのＩＤとなるストリング、発行日、及び有効期限）。証明書方式における周期数をｐで示すものとする。認証局は、証明書データに、有効ターゲットの集合と単一の無効ターゲットとを以下のように関連付ける。認証局は、｛０，１｝ｎから値Ｎ０をランダムに選ぶ。Ｎ１＝ｆ（Ｎ０）に設定する。Ｎ１は、無効ターゲットを示す。
【００７７】
次に、認証局は、証明書オーナに対し有効ターゲットの集合を以下のように構成する。認証局は、Ｆ（Ｏｗｎｅｒ）を計算する。Ｆ（Ｏｗｎｅｒ）は、オーナが一員であるＦの要素からなる集合である。ｋ個のＦ（Ｏｗｎｅｒ）の要素が存在するものとし、Ｆ１；…；Ｆｋと呼ぶ。Ｆ１…Ｆｋに関連するグラウンデッド・デンス・ハッシュ木の根の値をｒ１；…；ｒｋで示すものとする。
【００７８】
証明書は、増補されたデータ〈Ｄ，ｒ１；…；ｒｋ；Ｎ１〉と、このデータに対する認証局の署名とからなる。
定期的な証明書の更新
【００７９】
ディレクトリは、周期ごとに更新される。認証局は、周期ｉで、以下の値を送信する。ある証明書が無効であるならば、認証局は、その無効ターゲットのプリイメージを送信する。これは、各証明書に関連するＮ０値である。証明書が有効であれば、認証局は、以下を実行する。認証局は、まず、無効とされた所有者の集合Ｒを決定する。認証局は、ＳがＲの補集合カバーとなるように、要素Ｓ∈Ｆを計算する。Ｆは、全体集合Ｕの補集合カバーであるので、かかるＳが存在する。認証局は、Ｓの要素ごとに、その要素に対応する木に関連する値Ｖａｌｕｅ（ｇｖ（ｉ））を、Ｖａｌｕｅ（ＣｏＮｏｄｅｓ（ｇｖ（ｉ）））と共に送信する。
証明書状態の検証
【００８０】
ユーザが周期ｉで、オーナに属する証明書の状態を検証したいものとする。ユーザは、まず、証明書それ自体が期限切れになっておらず、認証局による署名が有効であるか確認する。次に、証明書が無効になっていると認証局が言っている場合、ユーザは、認証局が送信した値Ｎ０を取り出し、確かにＮ１＝ｆ（Ｎ０）であるか確認する。証明書が無効になっていないと認証局が言っている場合、ユーザは、Ｆ（Ｏｗｎｅｒ）に含まれる補集合カバーの要素に関連するＶａｌｕｅ（ｇｖ（ｉ））とＶａｌｕｅ（ＣｏＮｏｄｅｓ（ｇｖ（ｉ）））の値を取り出す。ユーザは、グラウンデッド・デンス・ハッシュ木の根の値を計算する。計算した根が証明書に含まれる根と一致すれば、証明書は有効である。
【００８１】
或いは、ユーザがすでに前の周期ｊで証明書を検証していて、関連する検証情報を持っており、証明書ｉに関連する頂点が、周期ｊの証明書に関連する頂点に根付いた部分木に含まれるならば、ユーザは、補ノードを用いてその根まで計算するだけでよい。
補集合カバーファミリの木構造
【００８２】
補集合カバーファミリの構造の１つは、２分木階層である。かかる補集合カバーファミリは、以下のように構成される。簡潔にするために、非負整数ｋに関し、証明書所有者の数は２ｋであるとする。２ｋの葉を持つ二分木を作成する。次に、証明書所有者の全体集合の１つの部分集合が各頂点に割り当てられる。２ｋの葉が存在するので、各葉は、単一の証明書所有者に対応することができる。各葉は、単一の証明書所有者からなる単集合に割り当てられる。次に、各内部ノードでは、その子供たちのノードの部分集合の和集合に相当する部分集合が割り当てられる。すなわち、ある頂点の部分集合は、その頂点に根付いた部分木の葉の証明書所有者に相当する。さて、その根に関連する部分集合が全体集合全体からなることを見てみよう。補集合カバーファミリＦは、全ての頂点に割り当てられた集合からなるだろう。Ｆが補集合カバーファミリを形成することは明らかである。特に、各証明書所有者は、葉において単集合として示されるので、任意の部分集合を構成することができる。しかし、それらの葉が完全な部分木を形成するオーナが、その部分木の根に関連する集合を用いてカバーを形成すればより効率的である。特に、最小サイズの（すなわち、最小数の集合を含む）部分集合Ｒ⊆Ｕの補集合カバーを構成するために、以下のステップを行う。
１．第１に、
【数１７】
の１要素に対応する各葉の頂点に「印を付ける」。
２．第２に、印を付けられた葉の頂点から根までの経路に沿う各内部頂点に「印をつける」。
３．第３に、印を付けられていないが、その親は、印を付けられている頂点を決定する。
４．第４に、これらの頂点に関連する部分集合を考慮する。
これらの部分集合は、最小サイズである
【数１８】
の補集合カバーを形成する。この方法は２分木に限定する必要はなく、実際には一般的な木に直接拡張する。
標準的なコンピュータシステム
【００８３】
図１０は、本明細書に記載の１つ又は複数のオペレーションを実行することができる、標準的なコンピュータシステムのブロック図である。図１０において、コンピュータシステム１０００は、標準的なクライアント１０５０やサーバ１０００のコンピュータシステムからなるものがある。コンピュータシステム１０００は、情報を通信するための通信機構、すなわちバス１０１１と、バス１０１１に接続されている情報を処理する処理装置１０１２とを含む。処理装置１０１２はマイクロプロセッサを含むが、例えば、ＰｅｎｔｉｕｍＴＭ、ＰｏｗｅｒＰＣＴＭ、ＡｌｐｈａＴＭ等のマイクロプロセッサに限定されない。
【００８４】
さらに、システム１０００は、バス１０１１に接続されている情報や処理装置１０１２が実行する命令を記憶するランダムアクセスメモリ（ＲＡＭ）や、他の動的記憶装置１００４（主記憶装置と呼ぶ）を含む。主記憶装置９０４は、処理装置１０１２が命令を実行している間に一時的数値変数や他の中間情報を記憶するのに用いることがある。
【００８５】
さらに、コンピュータシステム１０００は、バス１０１１に接続されている処理装置１０１２用の静的情報や命令を記憶する読出し専用メモリ（ＲＯＭ）及び／又は他の静的記憶装置１００６と、磁気ディスクや光ディスクなどのデータ記憶装置１００７と、それに対応するディスクドライブとを含む。データ記憶装置１００７はバス１０１１に接続され、情報や命令を記憶する。
【００８６】
さらに、コンピュータシステム１０００は、バス１０１１に接続されている情報をコンピュータユーザに表示する陰極線管（ＣＲＴ）や液晶表示装置（ＬＣＤ）等の表示装置１０２１に接続してもよい。英数字や他のキーを含む、英数字入力装置１０２２をバス１０１１に接続して、情報及び命令の選択を処理装置１０１２に通信するようにしてもよい。付加的なユーザ入力装置として、マウス、トラックボール、トラックパッド、スタイラス、カーソル方向キー等のカーソルコントロール１０２３があり、バス１０１１に接続して方向情報及び命令の選択を処理装置１０１２に通信し、表示装置１０２１でカーソルの動きを制御する。
【００８７】
バス１０１１に接続することがある他の装置としてハードコピー装置１０２４があり、紙、フィルム等の媒体や、同様の種類の媒体に、命令やデータや他の情報を印刷するのに用いてもよい。さらに、スピーカー及び／又はマイクロフォン等の録音及び再生装置をバス１０１１に随意接続して、コンピュータシステム１０００の音声インターフェースとしてもよい。バス１０１１に接続することがある他の装置として有線／無線通信機能１０２５があり、電話や携帯装置と通信する。
【００８８】
システム１０００の構成要素及び関連ハードウェアのいずれも、本発明において使用してもよいことに注意されたい。しかし、他の構成のコンピュータシステムが該装置のいくつか又は全てを含むことがあると考えることができる。
【００８９】
上述の説明を読んだ当業者であれば、本発明の様々な変更や修正は明らかに違いないが、例として示し説明した特定の実施形態が限定的なものであると見なされることは全く意図していないことを理解すべきである。従って、様々な実施形態の詳細に対する言及はクレームの範囲を限定するためのものではなく、クレームはそれ自体で、本発明に不可欠と考えられる特徴だけを記載している。
【図面の簡単な説明】
【００９０】
【図１】設定段階における認証局の処理の一実施形態のフロー図を示す。
【図２】設定段階における認証局の処理の一実施形態のフロー図を示す。
【図３】実用における証明書オーナの処理の一実施形態のフロー図を示す。
【図４】実用における証明書検証者の処理の一実施形態のフロー図を示す。
【図５】本発明の一実施形態による、認証局要素や、検証者要素や、オーナ要素を表す要素を示す。
【図６】本発明の一実施形態による、認証局と、証明書検証者と、証明書オーナとを有するシステム構成を示す。
【図７】Ｍｅｒｋｌｅ木と比較したグラウンデッド・デンス・ハッシュ木の例を示す。
【図８】Ｍｅｒｋｌｅ木と比較したグラウンデッド・デンス・ハッシュ木の例を示す。
【図９】ｋ個のチェーンにつながれたグラウンデッド・デンス・ハッシュ木を示す。
【図１０】標準的なコンピュータシステムのブロック図を示す。
【特許請求の範囲】
【請求項１】
有効ターゲットと無効ターゲットとを有する証明書データを生成する工程と、
前記証明書データを含む証明書を発行する工程とを含み、
前記有効ターゲットは、グラウンデッド・デンス・ハッシュ木の根の値であることを特徴とする方法。
【請求項２】
前記証明書データは、公開鍵と、シリアル番号と、前記証明書のオーナのＩＤとなるストリングと、発行日と、有効期限とからなるグループのうちの１つ又は複数をさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記グラウンデッド・デンス・ハッシュ木は、ハッシュチェーンで増やされた最下列の葉を含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記グラウンデッド・ハッシュ木は、最下位の頂点の上の均衡した２分木と、前記最下位の頂点の上層の頂点ごとに一方向関数の結果として生成される値とを含み、
前記最下位の頂点には、ランダムに選ばれた値が割り当てられることを特徴とする請求項１に記載の方法。
【請求項５】
前記証明書は、前記有効ターゲットと前記無効ターゲットとを有する前記証明書データに対する認証局の署名をさらに含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記証明書の有効性を定期的に更新する工程をさらに含み、
前記更新する工程において、前記無効ターゲットに対する新たな値を発行することを特徴とする請求項１に記載の方法。
【請求項７】
命令を記憶する１つ又は複数の記録可能媒体を有する製品であって、
前記命令は、システムによって実行されると、ある方法を前記システムに実行させるものであり、
前記方法は、
有効ターゲットと無効ターゲットとを有する証明書データを構成する工程と、
前記証明書データを含む証明書を発行する工程とを含み、
前記有効ターゲットは、グラウンデッド・デンス・ハッシュ木の根の値であることを特徴とする製品。
【請求項８】
前記証明書データは、公開鍵と、シリアル番号と、前記証明書のオーナのＩＤとなるストリングと、発行日と、有効期限とからなるグループのうちの１つ又は複数をさらに含むことを特徴とする請求項７に記載の製品。
【請求項９】
前記グラウンデッド・デンス・ハッシュ木は、ハッシュチェーンで増やされた最下列の葉を含むことを特徴とする請求項７に記載の製品。
【請求項１０】
前記グラウンデッド・デンス・ハッシュ木は、最下位の頂点の上の均衡した２分木と、前記最下位の頂点の上層の頂点ごとに一方向関数の結果として生成される値とを含み、
前記最下位の頂点には、ランダムに選ばれた値が割り当てられることを特徴とする請求項７に記載の製品。
【請求項１１】
前記証明書は、前記有効ターゲットと無効ターゲットとを有する前記証明書データに対する認証局の署名をさらに含むことを特徴とする請求項７に記載の製品。
【請求項１２】
前記証明書の有効性を定期的に更新する工程をさらに含み、
前記更新する工程において、前記無効ターゲットに対する新たな値を発行することを特徴とする請求項７に記載の製品。
【請求項１３】
外部ネットワークインターフェースと、
記憶装置と、
前記外部ネットワークインターフェースと前記記憶装置とに接続されている処理装置とを含み、
前記処理装置は、有効ターゲットと無効ターゲットとを含む証明書データを有する証明書を発行し、
前記有効ターゲットは、グラウンデッド・デンス・ハッシュ木の根の値であることを特徴とする装置。
【請求項１４】
有効ターゲットと無効ターゲットとを有する証明書データを生成する手段と、
前記証明書データを含む証明書を発行する手段とを含み、
前記有効ターゲットは、グラウンデッド・デンス・ハッシュ木の根の値であることを特徴とする装置。
【請求項１５】
特定の間隔で、証明書の有効状態情報に対するリクエストを受信する工程と、
前記特定の間隔に対応する灰色頂点の補ノードの値を計算する工程と、
前記リクエスト元に前記補ノードの値を送信する工程とを含む方法。
【請求項１６】
前記リクエスト元に補ノードの値を送信する工程において、
前記リクエスト元がどの補ノードの値が必要であるかを示していない場合、全ての補ノードの値を前記リクエスト元に送信し、
前記リクエスト元がどの補ノードの値が必要であるかを示している場合、リクエストされた補ノードの値を前記リクエスト元に送信することを特徴とする請求項１５に記載の方法。
【請求項１７】
前記特定の間隔に対応する灰色頂点の補ノードの値を計算する工程は、前記証明書が無効になっている場合に実行されることを特徴とする請求項１５に記載の方法。
【請求項１８】
無効ターゲットに対応する値を取り出す工程と、
前記値を前記リクエスト元に送信する工程とをさらに含むことを特徴とする請求項１５に記載の方法。
【請求項１９】
前記無効ターゲットに対応する値を取り出す工程、及び、前記値を前記リクエスト元に送信する工程は、前記証明書が無効になっている場合に生じることを特徴とする請求項１８に記載の方法。
【請求項２０】
前記無効ターゲットに対応する値を取り出す工程において、前記無効ターゲットのプリイメージを取り出すことを特徴とする請求項１８に記載の方法。
【請求項２１】
命令を記憶する１つ又は複数の記録可能媒体を有する製品であって、
前記命令は、システムによって実行されると、ある方法を前記システムに実行させるものであり、
前記方法は、
特定の間隔で、証明書の有効状態情報に対するリクエストを受信する工程と、
前記特定の間隔に対応する灰色頂点の補ノードの値を計算する工程と、
前記リクエスト元に前記補ノードの値を送信する工程とを含むことを特徴とする製品。
【請求項２２】
前記リクエスト元に補ノードの値を送信する工程において、
前記リクエスト元がどの補ノードの値が必要であるかを示していない場合、全ての補ノードの値を前記リクエスト元に送信し、
前記リクエスト元がどの補ノードの値が必要であるかを示している場合、リクエストされた補ノードの値を前記リクエスト元に送信することを特徴とする請求項２１に記載の製品。
【請求項２３】
前記特定の間隔に対応する灰色頂点の補ノードの値を計算する工程は、前記証明書が無効になっている場合に実行されることを特徴とする請求項２１に記載の製品。
【請求項２４】
無効ターゲットに対応する値を取り出す工程と、
前記値を前記リクエスト元に送信する工程とをさらに含むことを特徴とする請求項２１に記載の製品。
【請求項２５】
前記無効ターゲットに対応する値を取り出す工程、及び、前記値を前記リクエスト元に送信する工程は、前記証明書が無効になっている場合に生じることを特徴とする請求項２４に記載の製品。
【請求項２６】
前記無効ターゲットに対応する値を取り出す工程において、前記無効ターゲットのプリイメージを取り出すことを特徴とする請求項２４に記載の製品。
【請求項２７】
特定の間隔で、証明書の有効状態情報に対するリクエストが行われる外部ネットワークインターフェースと、
記憶装置と、
前記外部ネットワークインターフェースと前記記憶装置とに接続されている処理装置とを含み、
前記処理装置は、特定の間隔で証明書の有効状態情報に対する前記リクエストを受信し、前記特定の間隔に対応する灰色頂点の補ノードの値を計算し、前記リクエスト元に前記補ノードの値を送信することを特徴とする装置。
【請求項２８】
オーナに属する証明書を取得する工程と、
前記証明書が有効期限切れかどうか、前記証明書中の証明書情報が正確かどうか、前記証明書中の認証局の署名が有効であるかどうかを判断する工程と、
有効プルーフを取得する工程と、
前記プルーフが正確かどうか判断する工程と、
前記プルーフが正確であると判断された場合、前記証明書を受け付ける工程とを含む方法。
【請求項２９】
前記証明書は、有効ターゲットと無効ターゲットとを有する証明書データを含み、前記有効ターゲットは、木の根の値であることを特徴とする請求項２８に記載の方法。
【請求項３０】
前記木の根を計算する工程と、
前記計算した木の根と前記有効ターゲットとを比較する工程と、
前記計算した根が前記有効ターゲットに一致する場合、前記証明書が有効であると判断する工程とをさらに含むことを特徴とする請求項２９に記載の方法。
【請求項３１】
前記木の根を計算する工程は、ｉ番目の灰色頂点の値と、前記ｉ番目の灰色頂点の補ノードの値とを用いて実行されることを特徴とする請求項３０に記載の方法。
【請求項３２】
前記証明書中の無効ターゲットと、元の無効ターゲット値に適用した関数を示す値とを比較する工程をさらに含むことを特徴とする請求項３０に記載の方法。
【請求項３３】
前記証明書が有効期限切れである場合や、前記証明書情報が正確ではない場合や、前記認証局の署名が有効ではない場合、前記証明書を拒否する工程をさらに含むことを特徴とする請求項２９に記載の方法。
【請求項３４】
前記有効についてのプルーフを受信していない場合や、前記有効プルーフが正確ではない場合、前記証明書を拒否する工程をさらに含むことを特徴とする請求項２９に記載の方法。
【請求項３５】
命令を記憶する１つ又は複数の記録可能媒体を有する製品であって、
前記命令は、システムによって実行されると、ある方法を前記システムに実行させるものであり、
前記方法は、
オーナに属する証明書を取得する工程と、
証明書が有効期限切れかどうか、前記証明書中の証明書情報が正確かどうか、前記証明書中の認証局の署名が有効であるかどうかを判断する工程と、
有効プルーフを取得する工程と、
前記プルーフが正確かどうか判断する工程と、
前記プルーフが正確であると判断された場合、前記証明書を受け付ける工程とを含むことを特徴とする製品。
【請求項３６】
前記証明書は、有効ターゲットと無効ターゲットとを有する証明書データを含み、前記有効ターゲットは、木の根の値であることを特徴とする請求項３５に記載の方法。
【請求項３７】
前記木の根を計算する工程と、
前記計算した木の根と前記有効ターゲットとを比較する工程と、
前記計算した根が前記有効ターゲットに一致する場合、前記証明書が有効であると判断する工程とをさらに含むことを特徴とする請求項３５に記載の方法。
【請求項３８】
前記木の根を計算する工程は、ｉ番目の灰色頂点の値と、前記ｉ番目の灰色頂点の補ノードの値とを用いて実行されることを特徴とする請求項３７に記載の方法。
【請求項３９】
前記証明書中の無効ターゲットと、元の無効ターゲット値に適用した関数を示す値とを比較する工程をさらに含むことを特徴とする請求項３５に記載の方法。
【請求項４０】
前記証明書が有効期限切れである場合や、前記証明書情報が正確ではない場合や、前記認証局の署名が有効ではない場合、前記証明書を拒否する工程をさらに含むことを特徴とする請求項３５に記載の方法。
【請求項４１】
前記有効プルーフを受信していない場合や、前記有効プルーフが正確ではない場合、前記証明書を拒否する工程をさらに含むことを特徴とする請求項３５に記載の方法。
【請求項４２】
特定の間隔で、証明書の有効状態情報に対するリクエストが行われる外部ネットワークインターフェースと、
記憶装置と、
前記外部ネットワークインターフェースと前記記憶装置とに接続されている処理装置とを含み、
前記処理装置は、
オーナに属する証明書を取得し、
証明書が有効期限切れかどうか、前記証明書中の証明書情報が正確かどうか、前記証明書中の認証局の署名が有効であるかどうかを判断し、
有効プルーフを取得し、
前記プルーフが正確かどうか判断し、
前記プルーフが正確であると判断された場合、前記証明書を受け付けることを特徴とする装置。
【請求項４３】
複数の証明書に対する有効プルーフにアクセスする工程と、
デンス・ハッシュ木を用いて、前記複数の証明書のうちの複数の証明書の有効性を判断する工程とを含む方法。
【請求項４４】
前記デンス・ハッシュ木は、グラウンデッド・デンス・ハッシュ木からなることを特徴とする請求項４３に記載の方法。
【請求項４５】
特定の間隔で、証明書の有効状態情報に対するリクエストが行われる外部ネットワークインターフェースと、
記憶装置と、
前記外部ネットワークインターフェースと前記記憶装置とに接続されている処理装置とを含む装置であって、
前記処理装置は、複数の証明書に対する有効プルーフにアクセスし、デンス・ハッシュ木を用いて前記複数の証明書のうちの複数の証明書の有効性を判断することを特徴とする装置。
【請求項４６】
デンス・ハッシュ木を用いて、証明書が有効かどうか判断する工程と、
複数の有効プルーフで償却される単一のデジタル署名によって、無効プルーフを処理する工程とを含む方法。
【請求項４７】
特定の間隔で、証明書の有効状態情報に対するリクエストが行われる外部ネットワークインターフェースと、
記憶装置と、
前記外部ネットワークインターフェースと前記記憶装置とに接続されている処理装置とを含み、
前記処理装置は、デンス・ハッシュ木を用いて有効プルーフを処理し、デジタル署名によって無効プルーフを処理することを特徴とする装置。
【請求項４８】
証明書の有効プルーフにアクセスする工程と、
グラウンデッド・デンス・ハッシュ木を用いて、前記証明書の有効性を判断する工程とを含む方法。
【請求項４９】
特定の間隔で、証明書の有効状態情報に対するリクエストが行われる外部ネットワークインターフェースと、
記憶装置と、
前記外部ネットワークインターフェースと前記記憶装置とに接続されている処理装置とを含み、
前記処理装置は、証明書の有効プルーフにアクセスし、グラウンデッド・デンス・ハッシュ木を用いて、前記証明書の有効性を判断することを特徴とする装置。
【請求項１】
有効ターゲットと無効ターゲットとを有する証明書データを生成する工程と、
前記証明書データを含む証明書を発行する工程とを含み、
前記有効ターゲットは、グラウンデッド・デンス・ハッシュ木の根の値であることを特徴とする方法。
【請求項２】
前記証明書データは、公開鍵と、シリアル番号と、前記証明書のオーナのＩＤとなるストリングと、発行日と、有効期限とからなるグループのうちの１つ又は複数をさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記グラウンデッド・デンス・ハッシュ木は、ハッシュチェーンで増やされた最下列の葉を含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記グラウンデッド・ハッシュ木は、最下位の頂点の上の均衡した２分木と、前記最下位の頂点の上層の頂点ごとに一方向関数の結果として生成される値とを含み、
前記最下位の頂点には、ランダムに選ばれた値が割り当てられることを特徴とする請求項１に記載の方法。
【請求項５】
前記証明書は、前記有効ターゲットと前記無効ターゲットとを有する前記証明書データに対する認証局の署名をさらに含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記証明書の有効性を定期的に更新する工程をさらに含み、
前記更新する工程において、前記無効ターゲットに対する新たな値を発行することを特徴とする請求項１に記載の方法。
【請求項７】
命令を記憶する１つ又は複数の記録可能媒体を有する製品であって、
前記命令は、システムによって実行されると、ある方法を前記システムに実行させるものであり、
前記方法は、
有効ターゲットと無効ターゲットとを有する証明書データを構成する工程と、
前記証明書データを含む証明書を発行する工程とを含み、
前記有効ターゲットは、グラウンデッド・デンス・ハッシュ木の根の値であることを特徴とする製品。
【請求項８】
前記証明書データは、公開鍵と、シリアル番号と、前記証明書のオーナのＩＤとなるストリングと、発行日と、有効期限とからなるグループのうちの１つ又は複数をさらに含むことを特徴とする請求項７に記載の製品。
【請求項９】
前記グラウンデッド・デンス・ハッシュ木は、ハッシュチェーンで増やされた最下列の葉を含むことを特徴とする請求項７に記載の製品。
【請求項１０】
前記グラウンデッド・デンス・ハッシュ木は、最下位の頂点の上の均衡した２分木と、前記最下位の頂点の上層の頂点ごとに一方向関数の結果として生成される値とを含み、
前記最下位の頂点には、ランダムに選ばれた値が割り当てられることを特徴とする請求項７に記載の製品。
【請求項１１】
前記証明書は、前記有効ターゲットと無効ターゲットとを有する前記証明書データに対する認証局の署名をさらに含むことを特徴とする請求項７に記載の製品。
【請求項１２】
前記証明書の有効性を定期的に更新する工程をさらに含み、
前記更新する工程において、前記無効ターゲットに対する新たな値を発行することを特徴とする請求項７に記載の製品。
【請求項１３】
外部ネットワークインターフェースと、
記憶装置と、
前記外部ネットワークインターフェースと前記記憶装置とに接続されている処理装置とを含み、
前記処理装置は、有効ターゲットと無効ターゲットとを含む証明書データを有する証明書を発行し、
前記有効ターゲットは、グラウンデッド・デンス・ハッシュ木の根の値であることを特徴とする装置。
【請求項１４】
有効ターゲットと無効ターゲットとを有する証明書データを生成する手段と、
前記証明書データを含む証明書を発行する手段とを含み、
前記有効ターゲットは、グラウンデッド・デンス・ハッシュ木の根の値であることを特徴とする装置。
【請求項１５】
特定の間隔で、証明書の有効状態情報に対するリクエストを受信する工程と、
前記特定の間隔に対応する灰色頂点の補ノードの値を計算する工程と、
前記リクエスト元に前記補ノードの値を送信する工程とを含む方法。
【請求項１６】
前記リクエスト元に補ノードの値を送信する工程において、
前記リクエスト元がどの補ノードの値が必要であるかを示していない場合、全ての補ノードの値を前記リクエスト元に送信し、
前記リクエスト元がどの補ノードの値が必要であるかを示している場合、リクエストされた補ノードの値を前記リクエスト元に送信することを特徴とする請求項１５に記載の方法。
【請求項１７】
前記特定の間隔に対応する灰色頂点の補ノードの値を計算する工程は、前記証明書が無効になっている場合に実行されることを特徴とする請求項１５に記載の方法。
【請求項１８】
無効ターゲットに対応する値を取り出す工程と、
前記値を前記リクエスト元に送信する工程とをさらに含むことを特徴とする請求項１５に記載の方法。
【請求項１９】
前記無効ターゲットに対応する値を取り出す工程、及び、前記値を前記リクエスト元に送信する工程は、前記証明書が無効になっている場合に生じることを特徴とする請求項１８に記載の方法。
【請求項２０】
前記無効ターゲットに対応する値を取り出す工程において、前記無効ターゲットのプリイメージを取り出すことを特徴とする請求項１８に記載の方法。
【請求項２１】
命令を記憶する１つ又は複数の記録可能媒体を有する製品であって、
前記命令は、システムによって実行されると、ある方法を前記システムに実行させるものであり、
前記方法は、
特定の間隔で、証明書の有効状態情報に対するリクエストを受信する工程と、
前記特定の間隔に対応する灰色頂点の補ノードの値を計算する工程と、
前記リクエスト元に前記補ノードの値を送信する工程とを含むことを特徴とする製品。
【請求項２２】
前記リクエスト元に補ノードの値を送信する工程において、
前記リクエスト元がどの補ノードの値が必要であるかを示していない場合、全ての補ノードの値を前記リクエスト元に送信し、
前記リクエスト元がどの補ノードの値が必要であるかを示している場合、リクエストされた補ノードの値を前記リクエスト元に送信することを特徴とする請求項２１に記載の製品。
【請求項２３】
前記特定の間隔に対応する灰色頂点の補ノードの値を計算する工程は、前記証明書が無効になっている場合に実行されることを特徴とする請求項２１に記載の製品。
【請求項２４】
無効ターゲットに対応する値を取り出す工程と、
前記値を前記リクエスト元に送信する工程とをさらに含むことを特徴とする請求項２１に記載の製品。
【請求項２５】
前記無効ターゲットに対応する値を取り出す工程、及び、前記値を前記リクエスト元に送信する工程は、前記証明書が無効になっている場合に生じることを特徴とする請求項２４に記載の製品。
【請求項２６】
前記無効ターゲットに対応する値を取り出す工程において、前記無効ターゲットのプリイメージを取り出すことを特徴とする請求項２４に記載の製品。
【請求項２７】
特定の間隔で、証明書の有効状態情報に対するリクエストが行われる外部ネットワークインターフェースと、
記憶装置と、
前記外部ネットワークインターフェースと前記記憶装置とに接続されている処理装置とを含み、
前記処理装置は、特定の間隔で証明書の有効状態情報に対する前記リクエストを受信し、前記特定の間隔に対応する灰色頂点の補ノードの値を計算し、前記リクエスト元に前記補ノードの値を送信することを特徴とする装置。
【請求項２８】
オーナに属する証明書を取得する工程と、
前記証明書が有効期限切れかどうか、前記証明書中の証明書情報が正確かどうか、前記証明書中の認証局の署名が有効であるかどうかを判断する工程と、
有効プルーフを取得する工程と、
前記プルーフが正確かどうか判断する工程と、
前記プルーフが正確であると判断された場合、前記証明書を受け付ける工程とを含む方法。
【請求項２９】
前記証明書は、有効ターゲットと無効ターゲットとを有する証明書データを含み、前記有効ターゲットは、木の根の値であることを特徴とする請求項２８に記載の方法。
【請求項３０】
前記木の根を計算する工程と、
前記計算した木の根と前記有効ターゲットとを比較する工程と、
前記計算した根が前記有効ターゲットに一致する場合、前記証明書が有効であると判断する工程とをさらに含むことを特徴とする請求項２９に記載の方法。
【請求項３１】
前記木の根を計算する工程は、ｉ番目の灰色頂点の値と、前記ｉ番目の灰色頂点の補ノードの値とを用いて実行されることを特徴とする請求項３０に記載の方法。
【請求項３２】
前記証明書中の無効ターゲットと、元の無効ターゲット値に適用した関数を示す値とを比較する工程をさらに含むことを特徴とする請求項３０に記載の方法。
【請求項３３】
前記証明書が有効期限切れである場合や、前記証明書情報が正確ではない場合や、前記認証局の署名が有効ではない場合、前記証明書を拒否する工程をさらに含むことを特徴とする請求項２９に記載の方法。
【請求項３４】
前記有効についてのプルーフを受信していない場合や、前記有効プルーフが正確ではない場合、前記証明書を拒否する工程をさらに含むことを特徴とする請求項２９に記載の方法。
【請求項３５】
命令を記憶する１つ又は複数の記録可能媒体を有する製品であって、
前記命令は、システムによって実行されると、ある方法を前記システムに実行させるものであり、
前記方法は、
オーナに属する証明書を取得する工程と、
証明書が有効期限切れかどうか、前記証明書中の証明書情報が正確かどうか、前記証明書中の認証局の署名が有効であるかどうかを判断する工程と、
有効プルーフを取得する工程と、
前記プルーフが正確かどうか判断する工程と、
前記プルーフが正確であると判断された場合、前記証明書を受け付ける工程とを含むことを特徴とする製品。
【請求項３６】
前記証明書は、有効ターゲットと無効ターゲットとを有する証明書データを含み、前記有効ターゲットは、木の根の値であることを特徴とする請求項３５に記載の方法。
【請求項３７】
前記木の根を計算する工程と、
前記計算した木の根と前記有効ターゲットとを比較する工程と、
前記計算した根が前記有効ターゲットに一致する場合、前記証明書が有効であると判断する工程とをさらに含むことを特徴とする請求項３５に記載の方法。
【請求項３８】
前記木の根を計算する工程は、ｉ番目の灰色頂点の値と、前記ｉ番目の灰色頂点の補ノードの値とを用いて実行されることを特徴とする請求項３７に記載の方法。
【請求項３９】
前記証明書中の無効ターゲットと、元の無効ターゲット値に適用した関数を示す値とを比較する工程をさらに含むことを特徴とする請求項３５に記載の方法。
【請求項４０】
前記証明書が有効期限切れである場合や、前記証明書情報が正確ではない場合や、前記認証局の署名が有効ではない場合、前記証明書を拒否する工程をさらに含むことを特徴とする請求項３５に記載の方法。
【請求項４１】
前記有効プルーフを受信していない場合や、前記有効プルーフが正確ではない場合、前記証明書を拒否する工程をさらに含むことを特徴とする請求項３５に記載の方法。
【請求項４２】
特定の間隔で、証明書の有効状態情報に対するリクエストが行われる外部ネットワークインターフェースと、
記憶装置と、
前記外部ネットワークインターフェースと前記記憶装置とに接続されている処理装置とを含み、
前記処理装置は、
オーナに属する証明書を取得し、
証明書が有効期限切れかどうか、前記証明書中の証明書情報が正確かどうか、前記証明書中の認証局の署名が有効であるかどうかを判断し、
有効プルーフを取得し、
前記プルーフが正確かどうか判断し、
前記プルーフが正確であると判断された場合、前記証明書を受け付けることを特徴とする装置。
【請求項４３】
複数の証明書に対する有効プルーフにアクセスする工程と、
デンス・ハッシュ木を用いて、前記複数の証明書のうちの複数の証明書の有効性を判断する工程とを含む方法。
【請求項４４】
前記デンス・ハッシュ木は、グラウンデッド・デンス・ハッシュ木からなることを特徴とする請求項４３に記載の方法。
【請求項４５】
特定の間隔で、証明書の有効状態情報に対するリクエストが行われる外部ネットワークインターフェースと、
記憶装置と、
前記外部ネットワークインターフェースと前記記憶装置とに接続されている処理装置とを含む装置であって、
前記処理装置は、複数の証明書に対する有効プルーフにアクセスし、デンス・ハッシュ木を用いて前記複数の証明書のうちの複数の証明書の有効性を判断することを特徴とする装置。
【請求項４６】
デンス・ハッシュ木を用いて、証明書が有効かどうか判断する工程と、
複数の有効プルーフで償却される単一のデジタル署名によって、無効プルーフを処理する工程とを含む方法。
【請求項４７】
特定の間隔で、証明書の有効状態情報に対するリクエストが行われる外部ネットワークインターフェースと、
記憶装置と、
前記外部ネットワークインターフェースと前記記憶装置とに接続されている処理装置とを含み、
前記処理装置は、デンス・ハッシュ木を用いて有効プルーフを処理し、デジタル署名によって無効プルーフを処理することを特徴とする装置。
【請求項４８】
証明書の有効プルーフにアクセスする工程と、
グラウンデッド・デンス・ハッシュ木を用いて、前記証明書の有効性を判断する工程とを含む方法。
【請求項４９】
特定の間隔で、証明書の有効状態情報に対するリクエストが行われる外部ネットワークインターフェースと、
記憶装置と、
前記外部ネットワークインターフェースと前記記憶装置とに接続されている処理装置とを含み、
前記処理装置は、証明書の有効プルーフにアクセスし、グラウンデッド・デンス・ハッシュ木を用いて、前記証明書の有効性を判断することを特徴とする装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公表番号】特表２００７−５０６３６５（Ｐ２００７−５０６３６５Ａ）
【公表日】平成１９年３月１５日（２００７．３．１５）
【国際特許分類】
【出願番号】特願２００６−５２６９５５（Ｐ２００６−５２６９５５）
【出願日】平成１６年９月９日（２００４．９．９）
【国際出願番号】ＰＣＴ／ＵＳ２００４／０２９７６４
【国際公開番号】ＷＯ２００５／０２９４４５
【国際公開日】平成１７年３月３１日（２００５．３．３１）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．フロッピー
【出願人】（３９２０２６６９３）株式会社エヌ・ティ・ティ・ドコモ (5,876)
【Ｆターム（参考）】
【公表日】平成１９年３月１５日（２００７．３．１５）
【国際特許分類】
【出願日】平成１６年９月９日（２００４．９．９）
【国際出願番号】ＰＣＴ／ＵＳ２００４／０２９７６４
【国際公開番号】ＷＯ２００５／０２９４４５
【国際公開日】平成１７年３月３１日（２００５．３．３１）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．フロッピー
【出願人】（３９２０２６６９３）株式会社エヌ・ティ・ティ・ドコモ (5,876)
【Ｆターム（参考）】
[ Back to top ]