(57)【要約】【課題】本発明の目的は、有効性の再検証を行うために、全ての失効証明書の集合に対してではなく、直前の期間ｊ−１において失効した証明書の集合に対してコンプリメントカバーを構成して、コンプリメントカバーのサイズを小さくすることである。【解決手段】認証局（ＣＡ１２０）は、複数のデジタル証明書に対するコンプリメントカバー（８０４）における集合（Ｆ）ごとに復号鍵データ（Ｋ’Ｆ）を生成する。ＣＡは、有効性証明が提供される期間ｊごとの各デジタル証明書（１４０．ｉ）に対する有効性証明データ（ｃｊ（i））の全て、又は、部分を暗号化する。各証明書に対して、証明書を含む任意の集合に対する復号鍵データ（Ｋ’Ｆ）から求めることができる復号鍵（Ｋｉ，ｊ）を用いて復号化を実行することができる。ＣＡは、有効性証明データの暗号化した部分を期間ｊにおける有効性証明を提供する証明者システムに配布する。期間ｊにおいて証明書の有効性を再検証するために、ＣＡは、失効証明書の集合に対するコンプリメントカバーを構築し、そのコンプリメントカバーにおける集合に対して、復号鍵データ（Ｋ’Ｆ）を配布する。いくつかの実施形態において、各期間ｊに対して、復号鍵（Ｋｉ）は、先行する期間に対して提供された復号鍵データの関数でもある。そのため、有効性の再検証を行うために、ＣＡは、全ての失効証明書の集合に対してではなく、直前の期間ｊ−１において失効した証明書の集合に対してコンプリメントカバーを構築する。【選択図】図７
2008524931.tif 000002
【特許請求の範囲】
【請求項１】
複数の期間における複数のデジタル証明書の有効性、及び／又は、無効性を検証するためのコンピュータデータを生成するコンピュータに実装された方法であって、
それぞれの前記デジタル証明書は、暗号鍵がエンティティに関連付けられていることを証明し、
前記デジタル証明書は、第１のデジタル証明書を含み、
前記方法は、
（ａ）前記デジタル証明書をひとつ以上含む集合において、複数の集合を定義する第１のデータを取得する工程と、
（ｂ）前記デジタル証明書及び前記期間ごとに、前記期間における前記デジタル証明書の有効性、又は、無効性を証明するため、関連付けられた証明データを定義する第２のデータを取得する工程と、
（ｃ）前記集合及び前記期間ごとに、前記期間及び前記集合におけるそれぞれの前記デジタル証明書と関連付けられた前記証明データの暗号を復号するための復号鍵を提供するための復号鍵データを取得する工程とを含み、
前記複数の集合は、第１の複数の集合を含み、
前記第１のデジタル証明書は、前記第１の複数の集合に含まれるそれぞれの前記集合に属しており、
前記第１の複数の集合の少なくともひとつの前記集合は、２つ以上の前記デジタル証明書を含み、
少なくとも前記第１のデジタル証明書及び少なくともひとつの前記期間に対して関連付けられた少なくともひとつの復号鍵が、前記第１の複数の集合に属し、
それぞれの前記復号鍵が複数のデジタル証明書を含むひとつ以上の前記集合に関連付けられた前記復号鍵データから計算可能である
ことを特徴とする方法。
【請求項２】
請求項１に記載の方法を実行するコンピュータシステム。
【請求項３】
請求項１に記載の方法を実行するように操作可能なひとつ以上のコンピュータ命令を備えるデータキャリア。
【請求項４】
デジタル証明書の有効性、又は、無効性の証明の生成を可能とし、一の期間における前記証明を提供するコンピュータに実装された方法であって、
それぞれの前記デジタル証明書は、暗号鍵がエンティティと関連付けられていることを証明し、
無効なデジタル証明書の集合に対するコンプリメントカバーを定義するデータを取得する工程と、
前記コンプリメントカバーにおける前記集合ごとに、前記集合に関連付けられ、前記集合における前記デジタル証明書ごとに前記期間と関連付けられた有効性証明データの暗号を復号するためのひとつ以上の復号鍵を取得するための復号鍵データをネットワーク上で送信する工程とを含むことを特徴とする方法。
【請求項５】
請求項４に記載の方法を実行するコンピュータシステム。
【請求項６】
請求項４に記載の方法を実行するように操作可能なひとつ以上のコンピュータ命令を備えるデータキャリア。
【請求項７】
暗号鍵がエンティティと関連付けられていることを証明する第１のデジタル証明書の有効性、又は、無効性の証明を生成する方法であって、
ネットワーク上で、複数のデジタル証明書の集合と関連付けられた復号鍵データを受信し、
前記集合は、前記第１のデジタル証明書を含み、
前記第１のデジタル証明書の有効性、又は、無効性の証明を提供するための復号証明データを復号化し、
前記復号化は、前記復号鍵データを用いて取得する復号鍵を用いて実行されることを特徴とする方法。
【請求項８】
請求項７に記載の方法を実行するコンピュータシステム。
【請求項９】
請求項７に記載の方法を実行するように操作可能なひとつ以上のコンピュータ命令を備えるデータキャリア。
【請求項１０】
デジタル証明書の集合及び、期間に関連付けられた復号鍵データを提供する第１のコンピュータデータを備えるデータキャリアであって、
それぞれの前記デジタル証明書は、暗号鍵がエンティティと関連付けられていることを証明し、
前記復号鍵データは、前記期間における前記デジタル証明書の有効性、又は、無効性を証明するための暗号化された証明を復号するための復号鍵を提供するためのものであり、
少なくともひとつのデジタル証明書及び、少なくとも一の期間に対して、少なくともひとつの関連付けられた復号鍵が、それぞれが前記デジタル証明書を含み、
前記復号鍵は、複数のデジタル証明書を含む集合のひとつ以上と関連付けられた前記復号鍵データから計算可能であるデータキャリア。
【請求項１１】
複数の期間におけるデジタル証明書の有効性、又は、無効性を証明するための暗号化された証明データを含むコンピュータデータを備えるデータキャリアであって、
それぞれのデジタル証明証は、暗号鍵がエンティティと関連付けられていることを証明し、
前記暗号化された証明データは、復号鍵で復号するために暗号化されており、
少なくともひとつのデジタル証明書及び、少なくとも一の期間に対して、少なくともひとつの関連付けられた前記復号鍵が、前記デジタル証明書のひとつ以上の集合と関連付けられた復号鍵データから計算可能であり、
それぞれの前記集合は、前記少なくともひとつのデジタル証明書及び、少なくともひとつの他のデジタル証明書を含むデータキャリア。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の説明）
本願は、２００４年１２月１７日出願の米国仮特許出願第６０６３７１７７号に基づく優先権を主張し、その全内容を参照により本明細書に引用するものとする。  
本発明は、公開鍵暗号方式に関し、特に、デジタル証明書の失効に関する。
【背景技術】
【０００２】
デジタル証明書１０４（図１）は、公開鍵暗号基盤（ＰＫＩ）で利用されており、ネットワーク化したコンピュータ環境において公開鍵の安全な利用と管理を容易にしている。ユーザＵ１、Ｕ２、・・・は、それぞれのコンピュータシステム１１０．１、１１０．２・・・を利用してそれぞれの鍵ペア（ＰＫ、ＳＫ）を生成する。ここで、ＰＫは、公開鍵であり、ＳＫは、秘密鍵である。図１は、ユーザＵ１に対する鍵ペア（ＰＫＵ１、ＳＫＵ１）を示す。ユーザは、自分の公開鍵ＰＫをネットワーク上で認証局（ＣＡ）１２０に登録する。あるいは、ＣＡ１２０が鍵ペアを生成しユーザに送信することもできる。ＣＡ１２０は、安全で信頼のおけるコンピュータシステムである。ＣＡ１２０は、各公開鍵ＰＫに対してデジタル証明書１０４を生成する。証明書１０４は、公開鍵ＰＫ含み、さらに、ユーザ名及び／又はユーザのメールアドレスと住所のうち一方を含むが、証明書のシリアル番号ＳＮ（証明書の管理を容易にするためにＣＡによって生成されたもの）、証明書発行日Ｄ１、証明書有効期限Ｄ２、公開鍵及び秘密鍵に使用するアルゴリズムの識別、ＣＡ１２０の識別、及び他のデータ等を含めても良い。上述したデータを１０４Ｄに示す。証明書１０４は、データ１０４Ｄ上にＣＡの署名１０４−ＳｉｇＣＡも含む。その署名は、ＣＡの秘密鍵ＳＫＣＡを使って生成し、ＣＡ１２０は、証明書１０４をユーザ（鍵の所有者）のコンピュータシステム１１０に送信する。所有者及びＣＡ１２０は、ユーザの公開鍵ＰＫを他社に知らせるため、他者に証明書を配布することができる。そのような他者は、証明書の公開鍵ＰＫが、名前及びメールアドレスが証明書に記載されている人物に実際に属していることを確認するために、ＣＡの署名１０４−ＳｉｇＣＡをＣＡの公開鍵ＰＫＣＡで検証することができる。
【０００３】
証明書は、その有効期限日Ｄ２より前に失効されなければならなくなるかもしれない。例えば、証明書の所有者Ｕが、所属や役職を変えるかもしれないし、所有者の秘密鍵ＳＫＵが、危殆化しているかもしれない。証明書が失効した場合、他者が所有者の公開鍵を使えないようにしなければならない。
【０００４】
失効した証明書の公開鍵の使用を防ぐひとつの手法として、証明書失効リスト（ＣＲＬ）によるものがある。ＣＲＬは、ＣＡ１２０が発行する署名及びタイムスタンプが記され、失効した証明書をそれぞれのシリアル番号ＳＮによって特定するリストである。これらのＣＲＬは、新規に失効した証明書がない場合でも、いかなるタイプのリプレイ攻撃をも防止するために、定期的に配布されなければならない。通信、検索及び、検証に要するコストの観点から見ると、ＣＲＬの管理はやっかいなものかもしれない。［１５］に示したようにＣＲＬの代わりに、証明書失効ツリー（ＣＲＴ）を使用することができる。（鉤カッコで示した数字は、明細書の末尾に一覧にした参考文献の番号を示す。）
ＣＲＬ及びＣＲＴの代わりに、ＣＡ１２０は、特定の証明書についてのクエリに答えることができる。図１では、ユーザＵ２は、ユーザＵ１の証明書１０４のシリアル番号ＳＮを有するクエリ１５０を発行する。ＣＡ１２０は、シリアル番号ＳＮ、有効状況フィールド１６０ＶＳ（「有効」「無効」あるいは「不明」）、及びタイムスタンプ「時間」を含む有効状況情報１６０を以って返信する。この返信は、ＣＡによって署名される（フィールド１６０−ＳｉｇＣＡ）。この手法は、オンライン証明書状態プロトコル（ＯＣＳＰ）に利用されている。［２３］を参照。ＣＡのデジタル証明書１６０−ＳｉｇＣＡでは、特にＣＡが非常に安全でなくてはならないため、とても長く（ＲＳＡの場合１０２４ビット超）なってしまうという欠点がある。また、ＣＡが集中している場合、ＣＡは、認証の障害になってしまい、ＣＡが、分散化（複製）されている場合、ＣＡの署名鍵ＳＫＣＡが複製されるために安全性が低くなる。
【０００５】
図２は、ＣＡ１２０が、署名していない有効状況を予め特定した時間間隔（例えば、毎日、又は、毎時など）で信頼できないディレクトリ２１０を通して提供することができる「ＮＯＶＯＭＯＤＯ」による手法を図示している。ディレクトリ２１０は、秘密情報を格納しないコンピュータシステムである。このシステムは以下のように機能する。
【０００６】
ｆを予め定義された長さを保存する公開関数とする。
【０００７】
ｆ：  ｛０，ｌ｝ｎ→｛０，ｌ｝ｎ
ここで、｛０，ｌ｝ｎは、長さｎの全ての２進法の文字列の集合である。ｆｉがｆ倍の合成を示すとする。つまり、ｉ＝０に対してｆｉ（ｘ）＝ｘであり、ｉ＞０に対してｆｉ（ｘ）＝ｆ（ｆｉ−１（Ｘ））である。ｆを一方向とする。すなわち、ｘがランダムに選択されるｆ（ｘ）が与えられると、無視できる程度の確率を除いて、ｆ（ｚ）＝ｆ（ｘ）となるようなプレイメージｚを見つけることは困難（実行不可能）である。ここで「実行不可能である」とは、安全性のパラメータｋ（例えばｋ＝ｎ）が与えられると、無視できるほどの可能性を除いて、ｋにおける予め定義されている多項式と同じ時間内にプレイメージｚを計算することができないということである。さらに、ｆは、その反復において一方向である、すなわち、任意のｉに対してｙ＝ｆｉ（ｘ）であるとすると、ｆ（ｚ）＝ｙであるようなｚを見つけることは実行不可能であると仮定する。
【０００８】
一般性を失うことなく、ＣＡは、新しい有効状況を毎日提供し、証明書は一年、すなわち３６５日間（Ｄ２−Ｄ１＝３６５日）有効であることが要求されていると仮定することができる。証明書１０４（図２）を生成するために、ＣＡ１２０は、ランダムな「シード」番号ｘを選び、「ハッシュ連鎖」ｃ０、ｃ１、・・・ｃ３６５を生成する。ここで、
ｃ３６５＝ｆ（ｘ），ｃ３６４＝ｆ（ｆ（ｘ）），．．．ｃ１＝ｆ３６５（ｘ），ｃ０＝ｆ３６６（ｘ）    (1)
である。
【０００９】
シリアル番号ＳＮを有する証明書に対してｘをｘ（ＳＮ）、また同様にｉ＝０、１、・・・であるｃｉ＝ｃｉ（ＳＮ）として示すことがある。値ｃ０は、「検証ターゲット」と呼ばれる。ＣＡ１２０は、ｃ０を証明書１０４にデータ１０４Ｄ（図１）とともに挿入する。ＣＡ１２０は、ランダムな失効シード番号Ｎ０も生成し、「失効ターゲット」Ｎｉ＝ｆ（Ｎ０）を計算し、Ｎｉを証明書１０４に挿入する。ＣＡ１２０は、ｉ＞０に対して全てのｃｉを秘密にしておく。値ｘ及びＮ０も秘密である。全てのＣｉがｘから計算可能であり、検証ターゲットｃ０が任意のｃｉから計算可能であることは明らかである。ＣＡ１２０は、個別のストレージに、各証明書１０４に対する値ｘ及びＮ０を記憶し、（必ずしも必要ではないが）できる限り、そのｃｉの値をキャッシュする。
【００１０】
毎日ｉ（ｉ＝１，２，・・・３６５）、次のようにして有効な証明書に対して証明書の有効性再検証を実行する。ＣＡは、証明書１０４ごとに有効状況を示す（図２においては図示しないが、「有効」、又は、「失効」を示す）ものに加え、
１．証明書が、ある日ｉにおいて有効である場合は、証明書の「ｉ‐トークン」ｃｉを含み、
２．証明書が失効している場合は、失効シードＮ０を含む、
有効性データ構造をディレクトリ２１０に配布する。
【００１１】
（ｃｉを「有効性証明」、Ｎ０を「失効証明」と呼ぶ。）この情報は、署名無しに配布される。各ディレクトリ２１０は、有効状況リクエスト１５０（図１）に応答して、この情報を署名無しでリクエスタシステム１１０に提供する。検証するために、リクエスタ（ベリファイヤ）１１０は、以下のオペレーションを実行する。
【００１２】
１．有効状況が「有効」である場合は、ベリファイヤ１１０はｆｉ（ｃｉ）＝ｃ０を確認する。
【００１３】
２．有効状況が「失効」である場合は、ベリファイヤ１１０は、ｆ（Ｎ０）＝Ｎ１を確認する。
【００１４】
ｃｉが与えられると、それに続くトークンｃｉ＋１、ｃｉ＋２・・・を計算することが不可能なため、有効性情報が署名されていないにも係わらず、スキームは安全である。
【００１５】
ＣＡ１２０とディレクトリ２１０との間の通信を減らすために、証明書１０４の集合に対してハッシュ連鎖（１）を生成することができ、その集合が「失効していない」（すなわち、その集合の中の全ての証明証が失効していない）場合は、その集合に対してひとつのｉ‐トークンｃｉを配布することができる。図３は、証明書の集合Ｆ１からＦ４までを図示する。Ｆ１は、全ての証明書１０４の集合であり、Ｆ２⊂Ｆ３⊂Ｆ１及びＦ４⊂Ｆ１である。証明書１０４ごとのシード番号x、Ｎ０に加えて、ＣＡ１２０は、検証ターゲットｃ０（Ｆｉ）＝ｆ３６６（ｘ（Ｆｉ））を用いて、各集合Ｆｉに対してランダムなシード番号ｘ（Ｆｉ）、Ｎ０（Ｆｉ）を生成し、それぞれの数ｘ（Ｆｉ）からハッシュ連鎖（１）を作成する。各証明書１０４は、証明書を含む各集合Ｆｉに対してターゲットｃ０（Ｆｉ）とともに増大する。
【００１６】
全ての証明書が有効である場合、ＣＡ１２０は、毎日ｉ、ｉ‐トークンｃｉ（Ｆ１）だけをディレクトリ２１０に配布する。集合Ｆ３だけが無効な証明書を持っている場合、ＣＡ１２０は、集合Ｆ４と、集合Ｆ２における全ての有効な証明書に対してｉ‐トークンを配布する。集合Ｆ２‐Ｆ３だけが無効な証明書を持っている場合、ＣＡ１２０は、集合Ｆ３及び集合Ｆ４と、集合Ｆ２‐Ｆ３における全ての有効な証明書に対してｉ‐トークンを配布するなどというふうになる。
【００１７】
証明書１０４に対する有効状況リクエストに応答して、ディレクトリ１２０は、リクエスタ（ベリファイヤ）に対して、
１．証明書が有効である場合は、証明書及び証明書を含む集合Ｆｉに対してｉ‐トークンｃｉを送信し、
２．証明書が失効している場合は、証明書の失効番号Ｎ０を送信する。
【００１８】
証明書が有効であることを示す応答の場合、ベリファイヤは、ｆｉ（ｃｉ）が証明書の検証ターゲットのひとつと等しいことを確認する。証明書が失効していることを示す応答の場合、ベリファイヤは、証明書に対するｆ（Ｎ０）＝Ｎ１を確認する。
【００１９】
失効証明書の各集合Ｒ（図４）に対して、有効な証明書Ｒ’をカバーする集合Ｆｉのうちの最小の集合を見つけることが望ましいことは明らかである。この明細書中で自明のこととして、和集合ＵがＦｉ＝Ｒ’である場合、集合｛Ｆｉ｝はＲ’を「カバー」する。｛Ｆｉ｝は、Ｒの「コンプリメントカバー」と言う。このＲのコンプリメントカバーをＣＣＲで示す。
【００２０】
また、任意の集合Ｒ、又は、少なくとも可能な限り多くの集合Ｒに対する小さいコンプリメントカバーを含む集合｛Ｆ｝を見つけることが望ましい。｛Ｆ｝が、証明書の各集合Ｒに対するカバーを含む場合、｛Ｆ｝を全ての証明書の集合に対するコンプリメントカバーと呼び、このコンプリメントカバーをＣＣ（Ｕ）、又は、単にＣＣとして示す。
【００２１】
統一するために、各証明書１０４は、その証明書からなる単集合に対応することとする。単集合に対するハッシュ連鎖は証明書に対するものと同じである。
【００２２】
｛Ｆ｝が各証明書に対する単集合を含む場合、｛Ｆ｝が全ての証明書の集合に対するコンプリメントカバーであることは明らかである。
【００２３】
コンプリメントカバーは、ツリーを使って構成することができる。図５は、番号１から８までの８つの証明書に対するバイナリーツリー５１０である。各ノードは、集合Ｆｉを表わす。（１、２、・・・とラベルが付けられた）各リーフノードは、それぞれ証明書１、２、・・・に対する単集合を表わす。ハイレベルのノードは、その子ノードの和集合を表わす。例えば、ノード１乃至４は、証明書１から証明書４までの集合を表わす。ルートは、全ての証明書を表わす。（ツリーとコンプリメントカバーの両方を表わす符号として５１０を使用する。）
証明書が失効している場合は、対応するリーフも失効している。すなわち、ｉ‐トークンの配布のために使用することができない集合を表わす。また、リーフからルートへのパスにおける各ノードも失効している。図６の例では、（「ｘ」の記号で示されているように）証明書３及び証明書８は失効している。よって、集合３−４、１−４、１−８、７−８、５−８は失効している。失効証明書の最小のコンプリメントカバーＣＣＲはノード１−２、４、５−６、７から構成される。一般的に、最小のコンプリメントカバーＣＣＲは、失効したノードの子供である全てのノードで構成されている。コンピュータツリーを走査するアルゴリズムは、証明書が失効すると失効したノードをマークし、失効したノードの失効していない直接の子ノードを見つけるために、ＣＡ１２０に実装可能であることが知られている。ＣＡ１２０は、毎日、直接の子ノードに対してｉ‐トークンを、失効したリーフに対してＮ０トークンを配布する。  
【発明の開示】
【発明が解決しようとする課題】
【００２４】
本発明の目的は、有効性の再検証を行うために、全ての失効証明書の集合に対してではなく、直前の期間ｊ−１において失効した証明書の集合に対してコンプリメントカバーを構成して、コンプリメントカバーのサイズを小さくすることである。
【課題を解決するための手段】
【００２５】
ここでは、本発明のいくつかの特徴について概要を述べる。他の特徴については、後述する。本発明は、参照によりここに引用する添付した請求の範囲によって定義される。
【００２６】
本発明のいくつかの実施形態において、有効性証明は、ＣＡによって暗号化され、セットアップ時に、暗号化された形式で「証明者」システムに提供される。証明者システムは、ベリファイヤ１１０に有効性証明を提供するシステムである。証明者システムは、ディレクトリ２１０、又は、証明書の所有者のシステム１１０であってもよい。ｃｊ（ｉ）は、証明書１４０．ｉが有効であることの有効性証明を示すものとし、この有効性証明は、期間ｊにおいて提供されるものとする。証明ｃｊ（ｉ）は、図２のような他の証明書有効性検証システム用のトークンｃｊであってもよく、その他の証明であってもよい。各証明書１４０．ｉに対して、ＣＡは、全ての期間ｊに対する全ての有効性証明ｃｊ（ｉ）を暗号化し、暗号化した証明Ｅｉ，ｊ（ｃｊ（ｉ））を証明者に提供する。いくつかの実施形態において、Ｅｉ，ｊ（ｃｊ（ｉ））の複合には、証明書１４０．ｉと期間ｊごとに異なる鍵Ｋｉ，ｊが必要となる。対称鍵暗号方式が使用できるが、必ずしも用いる必要はない。
【００２７】
証明書の有効性再検証は、以下のように行う。各期間ｊの開始時、又は、その少し前に、ＣＡ１２０は、証明者が用いた復号鍵データを配布し、有効な証明書１４０．ｉに対する復号鍵Ｋｉ，ｊを入手する。証明者は、暗号化された有効性証明ｃｊ（ｉ）を復号し、その証明ｃｊ（ｉ）をベリファイヤに適宜提供する。
【００２８】
いくつかの実施形態において、複数の証明書の失効は、図４又は図５のようにコンプリメントカバーＣＣを用いて行う。セットアップ時に、ＣＡ１２０は、ＣＣにおける各集合Ｆ及び各期間ｊを復号鍵ＫＦ，ｊと関連付ける。また、ＣＡ１２０は、各証明書１４０．ｉに対して、期間ｊごとに、証明書１４０．ｉを含む集合Ｆに対する鍵ＫＦ,ｊを用いて復号することができるように、証明ｃｊ（ｉ）をＥｉ，ｊ（ｃｊ（ｉ））に暗号化する。暗号化された証明Ｅｉ，ｊ（ｃｊ（ｉ））は、証明者に送信される。期間ｊにおける有効性再検証のため、ＣＡ１２０は、失効された証明書の集合Ｒに対するコンプリメントカバーＣＣＲを構成し、このコンプリメントカバーの集合Ｆに対する鍵ＫＦ，ｊを発行する。
【００２９】
証明ｃｊ（ｉ）が等式（１）のようであれば、各証明書１４０．ｉは、ひとつの失効ターゲットｃ０しか必要としないという利点がある。より一般的には、いくつかの実施形態において、複数証明書失効システムは、証明書の形式を変更することなく、単一証明書失効システムの上に構成することができる。
【００３０】
いくつかの実施形態において、鍵は、次にように生成される。セットアップ時に、各証明書１４０．ｉに対して、各有効性証明ｃｊ（ｉ）は、証明書に対応するそれぞれの鍵Ｋｉ，ｊ、すなわち、証明書を含む単集合Ｆに対応する鍵ＫＦ，ｊのもと暗号化される。鍵は、各期間ｊに対する証明書１４０．に対する鍵Ｋｉ，ｊを、証明を含む集合Ｆの鍵ＫＦ，,ｊから入手できるように設定される。証明者は、有効性再検証の間に、証明書を含むある集合Ｆに対する期間ｊの鍵ＫＦ，ｊを受信する。証明者は、鍵Ｋｉ，ｊを計算し、それを使って暗号化されたｃｊ（ｉ）の値を復号する。
【００３１】
いくつかの実施形態において、期間ｊごとに、対応する鍵Ｋｉ，ｊは、単に期間ｊに対するだけのものではなく、先行する期間１から期間ｊ−１のいくつか、又は、その全てに対して、ＣＡ１２０によって配布された鍵データに基づいて構成される。有効性再検証の間に、ＣＡ１２０は、各期間ｊにおいて、先行する期間ｊ−１で失効した証明書の集合に対するコンプリメントカバーＣＣｊ−１を構成する。このコンプリメントカバーは、ＣＣＲより小さくてもよい。ＣＡ１２０は、ＣＣｊ−１の集合のためだけの鍵データを配布する。ＣＣｊ−１がＣＣＲよりも小さい場合、有効性再検証の間にＣＡ１２０が配布する情報量は、減少する。コンプリメントカバーＣＣｊ−１が無効な証明書を含む場合、ＣＡ１２０が先行する期間１から期間ｊ−１までのうちの少なくとも一期間に対して無効な証明書に対する復号鍵データを提供しなかったため、証明書の有効性証明は、復号することができない。
【００３２】
本発明のいくつかの実施形態は、特にアドホックネットワークに適している。アドホックネットワークは、モバイルルータ１１０の自己構築型無線ネットワークである。例としては、いくつかのノード１１０が物理的な状態を感知するためのセンサを備える無線センサネットワークが含まれ、また、地震センサも含まれる。これらのノードは、地理的領域にランダムに投下することができる。これらのノードは、送信用ノードの近傍にあるノードのみが「聞く」ことができる弱い信号を送信することが可能とされているため、限られた接続性を持っていると考えられる。また、ノードは、ネットワークトポロジーの不完全な知識だけを有していると考えられる。ネットワークは、より大きなネットワークの一部であってもよい。また、アドホックネットワークを、移動中の車両（例えば、車、飛行機など）に実装されるコンピュータ１１０によって構成してもよい。いくつかの実施形態において、復号鍵データは、マルチキャスト送信を介して物理的に近接する（集合した）ノードに配布される。コンプリメントカバーＣＣＲ又は、ＣＣｊ−１は、物理的に近接したノードがコンプリメントカバーにおいて同じ集合Ｆに含まれる証明書の証明者となるように構成される。同じ集合Ｆにおける証明書の証明者は、同じ復号鍵データを受信するので、これらの証明者がお互いに通信可能なように物理的に近い場合、復号鍵データの配布は、ＣＡの観点からみると効率的になる。この場合、ＣＡ１２０は、これらのノードに対する復号鍵データを、これらのノードのうちのひとつだけに送信する。このノードは、復号鍵データを群の残りの証明者に送信する。
【００３３】
本発明は、上述した特徴及び利点に制限されるものではない。他の特徴を以下に説明する。本発明は、添付した請求の範囲によって定義される。
【発明を実施するための最良の形態】
【００３４】
このセクションにおいて説明する実施形態は、本発明を説明するものであるが、本発明を制限するものではない。本発明は、添付の請求の範囲によって定義される。
【００３５】
以下の説明において、多数の詳細について説明する。しかしながら、本発明は、これらの詳細なしに実施してもよい。以下に続く詳細な説明のいくつかの箇所は、アルゴリズムやコンピュータメモリ内のデータビットにおけるオペレーションの記号表現で表わされている。これらのアルゴリズム的説明及び、表現方法は、データ処理技術の分野の当業者によって利用される手段であり、彼らの研究内容を他の当業者に最も効果的に伝えるものである。ここでのアルゴリズムは、また、一般的にも、所望する結果へ導く自己無撞着型の一連のステップであると考えられている。これらのステップには、物理量の物理的な操作が必要である。通常、必ずそうであるというわけではないが、これらの物理量は、記憶、転送、結合、比較が可能、又は、その他の操作が可能な電気的、又は、磁気的信号の形式をとる。主に共同利用のために、これらの信号をビット、値、エレメント、符号、記号、用語、数字などとして参照することが時には便利であると証明されている。
【００３６】
しかしながら、これら全て、又は、同様の用語が、適当な物理量に関連付けられ、これらの物理量に適用した便利なラベルに過ぎないことに留意する必要がある。以下の議論から明らかなように、特別に言及しない限り、明細書を通して、「処理する（ｐｒｏｃｅｓｓｉｎｇ）」、「計算する（ｃｏｍｐｕｔｉｎｇ）」、「計算する（ｃａｌｃｕｌａｔｉｎｇ）」、「決定する（ｄｅｔｅｒｍｉｎｉｎｇ）」、「表示する（ｄｉｓｐｌａｙｉｎｇ）」などの用語を利用する議論は、コンピュータシステムのレジストリやメモリ内の物理的（電気的）量として表わされるデータを操作し、コンピュータシステムのメモリ、通信、又は、表示装置内の物理量として同様に表わされる他のデータに変換するコンピュータシステム、又は、同様の電子計算装置のアクションやプロセスに言及していると考えるものとする。
【００３７】
本発明は、本明細書においてオペレーションを実行する装置にも関する。この装置は、要求される目的のために特別に構成されてもよいし、コンピュータに記憶されたコンピュータプログラムによって選択的に稼働させたり、又は、再構築されたりした汎用コンピュータによって構成してもよい。そのようなコンピュータプログラムは、限定されるわけではないが、フロッピィディスク、光学ディスク、ＣＤ−ＲＯＭ、及び光磁気ディスクなどのコンピュータ可読記憶媒体、読み取り専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気、又は、光学カード、又は、電気的命令を記憶するのに適している全ての種類の媒体、及びコンピュータシステムに連結されたそれぞれに記憶してもよい。
【００３８】
本明細書に表わすアルゴリズムは、本質的に、特定のコンピュータ、又は、その他の装置に関するものではない。様々な汎用コンピュータシステムは、本明細書の教示に従ってプログラムを用いて使用してもよいし、必要な操作を実行するために、より特殊な装置を構成することが好都合となるかもしれない。様々なこれらのシステムに対して必要な構造は以下の説明から明らかとなる。また、本発明は、特定のプログラム言語を用いて説明することはしない。本明細書に説明するように、様々なプログラム言語を用いて本発明の教示を実施することが可能であることが理解されるであろう。機械で読み取り可能な媒体には、情報を機械（例えば、コンピュータ）で読み取り可能な形式で記憶したり送信したりする全てのメカニズムが含まれる。例えば、機械で読み取り可能な媒体には、読み取り専用メモリ（「ＲＯＭ」）、ランダムアクセスメモリ（「ＲＡＭ」）、磁気ディスクストレージ媒体、光学ストレージ媒体、フラッシュメモリ装置、電気的、光学的、音響的、又は、他の形式の伝搬シグナル（例えば、キャリアウェーブ、赤外信号、デジタル信号等）等が含まれる。
【００３９】
図７は、本発明のいくつかの実施形態におけるＣＡのセットアップ段階を説明する図である。ステップ７０４において、ＣＡ１２０は、全ての証明書１０４の集合（又は、生成される証明書のための空のスロットを有するより大きい集合）に対するコンプリメントカバーＣＣを定義するコンプリメントカバーデータ８０４（図８）を生成する（ここに参照することで引用に含まれる、２００５年８月３１日出願、米国特許出願第１１／２１８０９３号及び、同じく２００５年８月３１日出願、ＰＣＴ出願ＰＣＴ／ＵＳ２００５／０３１２５１号を参照のこと）。ステップ７１０において、証明書１４０．ｉごとに、ＣＡ１２０は、全ての期間ｊの有効性証明ｃｊ（ｉ）を生成する。ＣＡ１２０は、その有効性証明ｃｊ（ｉ）、又は、有効性証明を生成可能な有効性証明データの一方を、ＣＡのストレージ８２４（図８）に記憶する。例えば、等式（１）に関して、有効性証明データは、シード値ｘから構成されてもよい。ＣＡ１２０は、失効証明データ（例えば、Ｎ０）も記憶することができる。
【００４０】
ステップ７２０において、ＣＡ１２０は、期間ｊごとの各証明書１４０．ｉに適した暗号鍵Ｋｉ，ｊを生成する。簡潔にするために、対称鍵暗号、すなわち、暗号鍵が復号鍵でもあると仮定する。ＣＡ１２０は、図８の８３４において示したように、復号鍵、又は、復号鍵を生成することができる復号鍵データを記憶する。ステップ７３０（図７）において、ＣＡ１２０は、各証明ｃｊ（ｉ）を、対応する鍵Ｋｉ，ｊで暗号化し、暗号化された証明Ｅｉ，ｊ（ｃｊ（ｉ））を入手する。ステップ７４０において、各証明書１４０．ｉに対して、ＣＡ１２０は、全ての期間ｊに対する暗号化された証明Ｅｉ，ｊ（ｃｊ（ｉ））を、関連付けられた証明者８３８に送信する（図８）。証明者８３８は、証明書１４０．ｉに対する有効性証明を提供する。いくつかの実施形態において、暗号化された証明書Ｅｉ，ｊ（ｃｊ（ｉ））は、ＣＡ１２０によって署名され、その署名も証明者に送信される。証明者は、暗号化された証明を図８の８４０において示したように証明者のストレージに記憶する（図８は、ｊの指標は、１から、ある数字Ｔまで変化するものと仮定する）。
【００４１】
図９は、ある期間ｊに対する証明書の有効性再検証を説明する図である。期間ｊの開始時、又は、その少し前に実行されるステップ９１０において、ＣＡ１２０は、失効した証明書の集合に対するコンプリメントカバーＣＣＲを構成する。ステップ９２０において、コンプリメントカバーにおける集合Ｆごとに、ＣＡ１２０は、復号鍵データＫ’Ｆｊを、集合Ｆの証明書１４０と関連付けられている証明者８３８に送信する。いくつかの実施形態において、復号鍵データＫ’Ｆｊは、平文で配布される。ステップ９３０において、各証明書１４０．ｉに対して、対応する証明者８３８は、復号鍵Ｋｉ，ｊを、復号鍵データＫ’Ｆ,ｊから入手する。いくつかの実施形態において、Ｋ’Ｆ,ｊ＝Ｋｉ，ｊ（例えば、暗号化Ｅｉ，ｊ（ｃｊ（ｉ））には、集合Ｆが証明書１４０．ｉを含むようにＣＣの各集合Ｆに対する鍵Ｋ’Ｆｊの下にｃｊ（ｉ）の暗号化を含んでもよい）が、以下により詳細に説明するように、これは、必ずしも必要ではない。ステップ９４０において、証明者は、鍵Ｋｉ，ｊを用いてＥｉ，ｊ（ｃｊ（ｉ））を復号して、証明ｃｊ（ｉ）を入手する。証明者は、証明ｃｊ（ｉ）をベリファイヤに適宜（例えば、リクエストに応答して、又は、他の事象に基づいて）提供する。ベリファイヤは、基礎をなす証明書検証システムのために確立された手順を用いて証明書の有効性を確認することができる。
【００４２】
無効な証明書ごとに、ＣＡ１２０は、対応する失効証明（例えば、基礎となる有効性検証スキームが図２のような場合、Ｎ０）を配布する。失効証明は、リクエスト、又は、他の事象のどちらかに基づいて、対応する証明者８３８、又は、ベリファイヤ１１０に配布することができる。他の実施形態において、ＣＡ１２０は、失効した証明書に対して何のアクションも実行しない。ベリファイヤは、証明書の有効性証明が入手できない場合、証明書が失効されたと推定する。
【００４３】
証明書証明が図２のような場合、各証明書１４０が失効ターゲットｃ０をひとつしか含むことがでないという利点がある。また、図７乃至図９の複数証明書失効スキームを、単一証明書に対する有効性証明ｃｊ（ｉ）を用いて、証明書を変更することなく、単一証明書失効スキームの上に構成することができる。
【００４４】
ここで、復号鍵Ｋｉ，ｊを構成するいくつかの実施形態について説明する。いくつかの実施形態において、ＣＣにおける任意の集合Ｆに対して、任意の期間ｊに対する鍵データＫ’Ｆ,ｊは、同じ期間ｊに対するＦの任意の部分集合に対する鍵データを導出するのに十分である。その導出は、例えば、公開ハッシュ関数Ｈなどの公開情報を用いて実行することができる。関数Ｈは、入力としてｂ−ビットのペイロード及び、ｖ−ビットの初期設定ベクトルＩＶを取り、ｖ−ビットの出力を生成する暗号圧縮関数であってもよい。いくつかの実施形態において、
【数１】
2008524931.tif 000003
【００４５】
である。以下に説明する暗号圧縮関数は、衝突耐性を持つ、すなわち、Ｈ（ＩＶ，ｍ１）＝Ｈ（ＩＶ，ｍ２）となるような２つの異なる入力値ｍ１≠ｍ２を見つけることは困難である、と仮定する。ＩＶは、固定されており、公知であると仮定し、表示を簡潔にするために、それを省略することがある。そのような暗号圧縮関数の実践的例は、ＳＨＡ−１［２６］（出力サイズは、２０バイト）及び、ＭＤ５[２８]（出力サイズは、１６バイト）であり、両者とも６４バイトのペイロードを有する。簡潔にするために、圧縮関数の代わりに「ハッシュ関数」という用語を使用する。「ハッシュ関数」という用語は、ある固定されたｖに対する｛０，１｝＊から｛０，１｝ｖへのマッピングを示すこともできる。ここで、｛０，１｝＊は、全ての２進列の集合を示す。ハッシュ関数は、典型的には一方向であり、衝突耐性を持つが、本発明は、そのような関数に限定されるものではない。
【００４６】
ここで、鍵の構成を、図５のコンプリメントカバーと同様な図１０のツリーのコンプリメントカバー８０４に基づいて説明する。集合Ｆ（ツリーノード）は、利便性のために、ビット文字列ｂを用いてラベル付けされる。ルートは、空のビット文字列ｂ＝εに関連付けられる。ルートの左の子ノードには、ｂ＝０のラベルが付けられ、右の子ノードにはｂ＝１のラベルが付けられる。一般に、ラベルｂを有する任意の親ノードに対して、左の子は、ｂ０のラベル（右側に０を添える）が付けられ、右の子には、ｂ１のラベルが付けられる。
【００４７】
このラベル付けスキームを用いて、ｂが複数の証明書を含む集合Ｆのラベルである場合、これらの証明書のそれぞれ（すなわち、対応する単集合のそれぞれ）は、ｂで始まるラベルを有する。例えば、集合ｂ＝１１は、ともに１１で始まるラベルｂ＝１１０及び、ｂ＝１１１を有する証明書からなる。
【００４８】
Ｋ’ｂ,ｊが期間ｊに対してｂのラベルが付けられた集合に対する復号鍵データを示すものとする。これらのデータは、次のようにステップ７２０において、ＣＡ１２０によって生成される。ＣＡ１２０は、期間ｊに対する秘密シード値ｓｊを選択する。値ｓｊは、ランダムに生成する、又は、単一のシード値から計算してストレージを節約する、もしくは、他の適切な方法で選択することができる。そして、ルートノードｂ＝εに対して、ＣＡ１２０は、
Ｋ’εｊ＝ｓｊ    （２）
と設定する。他の全てのラベルｂに対して、ｂ（ｋ）が、ｂのｋ番目のビットを示すものとする。ｂが、ある数ｈのビット、すなわち、ｂ＝ｂ（１）ｂ（２）．．．ｂ（ｈ）を有するものと仮定すると、ＣＡ１２０は、
Ｋ’ｂ,ｊ＝Ｈ（ｂ（ｈ），．．．，Ｈ（ｂ（２），Ｈ（ｂ（１）,ｓｊ））．．．）    （３）
を計算する。つまり、関数Ｈが、反復的にｈ回適用される。次の反復ごとに、先行する反復において求められたＨの値で連結されたｂ（ｉ）の次のビットに、Ｈが適用される。ビット文字列ｂ１が部分列ｂ２で始まる（すなわち、集合ｂ１がｂ２の部分集合である）場合、所与の任意のｊに対して、
【数２】
2008524931.tif 000004
【００４９】
から
【数３】
2008524931.tif 000005
【００５０】
を導出することができる。例えば、ｂ１＝ｂ２ｂ（ｍ）．．．ｂ（ｈ）の場合、
【数４】
2008524931.tif 000006
【００５１】
である。等式（４）は、ｂ２＝ε（空の文字列）である場合でも真であることに留意すること。
【００５２】
ステップ７２０において、ＣＡ１２０は、単集合に対する暗号／復号鍵Ｋｂ,ｊを次のように計算する。
【００５３】
Ｋｂ,ｊ＝Ｈ（Ｋ’ｂ，ｊ，．．．．，Ｋ’ｂ，１）    （５）
（５）における関数Ｈは、（３）におけるものと同じである、又は、異なるハッシュ関数であってもよい。いくつかの実施形態において、（５）における関数Ｈは、ハッシュ関数ではなく、単に、鍵データＫ’ｂ，ｊ，．．．，Ｋ’ｂ，１を連結する関数である。例えば、（５）における関数Ｈは、鍵データＫ’ｂｊ，．．．，Ｋ’ｂ，１に関する加法、又は、排他的ＯＲ演算であってもよい。
【００５４】
全ての鍵Ｋｉ，ｊは、ｊ＝１，．．．，Ｔに対してＫ’ε，ｊから生成することができるので、ＣＡの復号鍵データストレージ８３４は、いくつかの実施形態において、鍵データＫ’ε，ｊだけしか記憶しない。
【００５５】
証明書の有効性再検証は、次のように実行される。ステップ９１０（図９）において、各期間ｊの開始時、又は、その少し前に、ＣＡ１２０は、直前の期間ｊ−１において失効していない証明書の全ての集合のコンプリメントカバーＣＣｊ−１を決定する（ｊ＝１の場合、ＣＣｊ−１は、ルートノードε、すなわち、全ての証明書の集合から構成されていてもよい）。これは、全ての失効証明書の集合に対するカバーＣＣＲよりも小さいカバーとなることもある。例えば、期間ｊ−１において失効している証明書がなかった場合、ＣＣｊ−１は、全ての証明書の単一の集合からなる。ステップ９２０において、ＣＣｊ−１におけるｂとラベル付けされた集合ごとに、ＣＡは、ペア（ｂ，Ｋ’ｂ，ｊ）を発行する。ペア（ｂ，Ｋ’ｂ，ｊ）を発行することには、ＣＡ１２０が集合ｂにおける証明書１４０と関連付けられている証明者８３８に鍵ペアを送信することが含まれていてもよい。いくつかの実施形態において、ＣＡ１２０は、平文のこれらのペアを配布し、及び／又は、それをシステム１１０及び、システム２１０に対して公に入手可能にする。
【００５６】
ステップ９３０において、ラベルｂ１を有する単集合に対応する有効な証明書１４０．ｉに対して、対応する証明者８３８は、鍵データ
【数５】
2008524931.tif 000007
【００５７】
を次のように入手する。ｂ１が、ＣＣｊ−１の中にある場合、証明者は、ステップ９２０において、
【数６】
2008524931.tif 000008
【００５８】
を受信していた。ｂ１がＣＣｊ−１の中にない場合、ｂ１は、ラベルｂ１がｂで始まるようにＣＣｊ−１の中の集合ｂに属している。証明者は、（ｂ，Ｋ’ｂ，ｊ）をステップ９２０において受信した。この場合、証明者は、ｂ１がｂで始まることを確認し、等式（４）を用いてＫ’ｂ，ｊから
【数７】
2008524931.tif 000009
【００５９】
を計算する。
【００６０】
証明書が有効なので、証明者は、証明書を含むいくつかの集合Ｆ（ｍ）に対して、期間ｍ＝１，．．．，ｊ−１ごとの証明書に対する鍵データＫ’Ｆ（ｍ），ｍを受信したに違いない。そのため、証明者８３８は、期間ｍ＝１，．．．，ｊ−１に対する鍵データ
【数８】
2008524931.tif 000010
【００６１】
を計算している、又は、計算することができる。ステップ９３０において、証明者は、等式（５）から鍵
【数９】
2008524931.tif 000011
【００６２】
を求める。そして、ステップ９４０（復号）は、上述したように証明者によって実行される。
【００６３】
いくつかの実施形態において、証明者が有効性再検証を実行できるようにするために、証明者に、ＣＡのセットアップ時に、証明書に対するｂ１の値が提供される。ステップ７０４（図７）において、図１０のツリーにおけるリーフ位置ｂ１を、各証明書１４０．ｉに割り当てる。ステップ７４０において、ＣＡ１２０は、ユーザのシステム１１０（又は、他の証明者システム８３８）に対して次のデータを送信する。
【数１０】
2008524931.tif 000012
【００６４】
ここで、Ｕｉは、証明書のシリアル番号、又は、証明書に埋め込まれ、かつ／又は、証明者が使用可能な他の識別子であり、Ｓｉｇ（Ｕｉ，ｂ１，ｃ０）は、データ（Ｕｉ，ｂ１，ｃ０）とＣＡの秘密鍵ＳＫＣＡを有するこれらのデータ上の署名との組み合わせを示し、
【数１１】
2008524931.tif 000013
【００６５】
は、鍵
【数１２】
2008524931.tif 000014
【００６６】
の下のｃｊ（ｉ）の対称鍵暗号を示す。（６）における第一の項ｃ０は、証明者システム８３８が証明書を有する場合、証明書の一部なので省略することができる。システム８３８は、これらのデータをストレージ８４０に記憶する。
【００６７】
いくつかの実施形態において、ユーザは、図７の初期セットアップ手順の後に、システムに加わることができる。上述したように、コンプリメントカバー８０４には、後から加わったユーザに対する空のスロットを含んでもよい。図７のセットアップ手順は、後から加わったユーザのために繰り返される。
【００６８】
等式（２）乃至等式（６）は、様々な方法で修正することができる。例えば、等式（３）において、関数Ｈの応用及び、ｂのビットとの連結は、互いに入れ替えることができる（Ｋ＝ｂ（ｈ）Ｈ（．．．ｂ（２）Ｈ（ｂ（１）Ｈ（ｓｊ））．．．）。他の変形例も可能である。
【００６９】
ユーザの観点からみると、このスキームには、任意の証明書有効性検証スキームに関連してこの暗号化の手法を用いることができるという利点がある。例えば、図２のＮｏｖｏｍｏｄｏスキームとともに用いられる場合、ユーザは、コンパクトな検証ターゲットｃｊ（どれくらいの期間があり、どれくらいのユーザがいるのかに関係ない、単なる単一のハッシュ・プレイメージ）というＮｏｖｏｍｏｄｅの利点を保持しつつ、同時に、ＣＡは、複数証明書の有効性検証の効率的な利点を享受することができる。さらに、所与の期間ｊにおけるコンプリメントカバーのサイズが、（複数の期間にわたる）失効システムの寿命の間に起こる失効ｒの総数によってではなくむしろ、直前の期間ｊ−１内に起こる失効ｒｊの数によって決まるので、等式（２）乃至等式（６）の実施形態の方が、ＣＡの観点からみて、図４に関連した上記実施形態より、より効率的に遂行する。よって、漸近的に、ＣＡが期間ごとに送信する必要がある情報量は、いくつかの実施形態において、大きい値Ｏ（ｒｌｏｇ（ｎ／ｒ））ではなく、本質的にＯ（ｒｊｌｏｇ（ｎ／ｒｊ））である。もちろん、各証明者８３８（例えば、各ユーザシステム１１０）は、関連付けられた暗号化された証明Ｅｉ，ｊ（ｃｊ（ｉ））をキャッシュしなければならない。しかしながら、これは一回限りのセットアップに必要なものなので、かつ、これらの値は変更する必要がないので、不揮発性ＲＯＭに記憶するなどの効率的な技術を用いて処理することができる。
【００７０】
いくつかの実施形態において、図７乃至図１０の技術は、ハッシュ連鎖（１）がツリー構造と入れ替わっているハッシュツリー検証スキーム、例えば、接地した密なハッシュツリーと共に用いられる。例えば、ここに参照することで引用に含まれる２００５年３月３１日公開のＰＣＴ公開番号ＷＯ２００５／０２９４４５を参照のこと。本発明は、上述した基礎となる検証スキームに制限されるものではない。
【００７１】
アドホックネットワークなどのネットワークにおいて、ＣＡの観点から見ると、鍵データＫ’ｉ，ｊを配布するための最も適切な方法は、ネットワーク内のユーザシステム１１０．ｉ（各証明者８３８は、ユーザシステム１１０．ｉと仮定）の可動性や、ＣＡがネットワークのトポロジーに関してどのくらいの情報を持っているか、などの特定の要素によって決まるかもしれない（新規ノードは、偶数回にネットワークに加わることができ、ＣＡは、まだ新規ノードに気がついていないかもしれない）。ＣＡが完全なトポロジー情報を有する場合、ＣＡは、復号鍵データを、ネットワーク内の関連付けられた証明者に送信してもよい。
【００７２】
ある時点より後に、証明者１１０が本質的に静的（不動）である場合、ＣＡは、この事実を用いて、配布効率を改善することができる。この状況は、例えば、飛行機から投下され地面に落下し、その後本質的に静止する移動センサノードの無線ネットワークに関わるものであると考えられる。図１０の有効性検証スキームでは、ステップ７０４（図７）において、ＣＡ１２０が、ユーザシステム（すなわち、各ユーザシステム１１０は単一の証明書に対応すると仮定した証明書）を（例えば）バイナリツリーのリーフのように配置する。そして、証明書の有効性を再検証する間、あるユーザシステム１１０同士がバイナリツリーの中で互いに「近い」場合、これらのユーザシステムは、同じ鍵データＫ’ｉ，ｊを受信してもよい。そのため、バイナリツリーにおけるユーザシステムを、ユーザシステムが、トポロジー的にどのように位置付けされているかと整合するように位置付けることが望ましい。物理的に互いに近いユーザシステムは、図１０のツリー８０４において互いに近く位置付けされなければならない。そして、適当なコンプリメントカバーＣＣＲ又は、ＣＣｊ−１を見つけ、関連付けられた復号鍵データＫ’Ｆ，ｊを生成した後で、ＣＡは、集合Ｆごとの復号鍵データＫ’Ｆ，ｊを、集合Ｆに属するノード１１０の集団の一要素に対して一度だけ送信する必要があるであろう。この要素は、復号鍵データを同じ集団の中の近傍のノードに伝送することができる。概して言えば、この状況で、ＣＡは、以下の証明書有効性検証手法を用いることができる。
【００７３】
１．トポロジーが決まる前、ＣＡは、システム１１０同士が互いにどの程度近いかに関する情報を使わない何らかの方法で構成されたバイナリツリーを有する初期証明書スキームを用いる。
【００７４】
２．トポロジーは、その後、相対的に決定される。
【００７５】
３．ノード１１０は、署名鍵と、ノード自体を認証する初期証明書スキームを用いて、ノード自体の位置報告をＣＡに返す。
【００７６】
４．その後、ＣＡは、（ツリー８０４において、物理的に近接するノードが互いに近い）ネットワークのトポロジーと整合するようにバイナリツリーを再構成する。その結果、集団となったシステム１１０の少なくとも一群に対して、その群を含む集合Ｆの数は、コンプリメントカバーにおける集合Ｆの総数を変更することなく増加する。
【００７７】
５．ＣＡは、新規データ（６）をノードに対して送信し、その後、新規のトポロジーに基づいたバイナリツリーを用いて証明書の有効性検証を行う。
【００７８】
ＣＡがネットワークトポロジーと整合したバイナリツリーを作成することが可能となる、別の方法がある。ノード１１０がノードの局所的な接続性（すなわち、ノードがノードの位置から「聞く」ことができるノードのアイデンティティ）の報告を返す場合、ＣＡは、その情報を用いて、まず、ネットワークをイントラ接続された同等の大きさのものに２等分し、それぞれをバイナリツリーの半分のものと関連付け、半分のものをそれぞれイントラ接続された同等の大きさのものにさらに２等分して、そのそれぞれをバイナリツリーの適当なものと関連付けたりするなどして、ネットワークを接続されたサブネットワークに再帰的に２等分することができる。ＣＡがこのツリーを構成しているので、ＣＡは、証明書有効性情報が、例えば、ツリー、又はトポロジーの集線ハブとして指定されたノードから、それぞれが属するサブツリーのハブとして指定された２つのノードへのように、トラバース可能な効率的なルートを記録することもできる。ＣＡは、その後、この利用可能なルート情報をノードに送信することができる。
【００７９】
上記の実施形態において、ＣＡ１２０、ディレクトリ２１０、システム１１０、証明者８３８は、１つ以上のネットワーク上で互いに通信し合うコンピュータシステムであってもよい。これらのシステムの各々がそれ自体ネットワーク上で通信を行う構成要素を有するコンピュータシステムであってよい。各コンピュータシステムには、上述したようにコンピュータの命令を実行し、コンピュータデータを操作するひとつ以上のコンピュータプロセスを含む。「データ」という用語には、「コンピュータデータ」が含まれ、コンピュータ命令及び、命令によって操作されるコンピュータデータの両方をカバーしている。命令及びデータは、コンピュータストレージ、すなわち、コンピュータ可読媒体（例えば、磁気、又は、光学ディスク、半導体メモリ、及び他のタイプの公知の、又は、発明される媒体）などのデータキャリアに記憶することができる。データキャリアには、空間を通して、もしくは、ケーブル、又は、他の手段によってネットワーク上を伝送される電磁気のキャリア波を含んでもよい。上述したように、命令及びデータは、コンピュータに上述したように適切なアルゴリズムを実行させるように操作可能である。
【００８０】
本発明は、上述した実施形態に限定されるものではない。例えば、値ｃｊ（ｉ）は、有効性証明の一部分だけを表わすものでもよい。他の部分は、ＣＡ１２０によって、証明書の有効性再検証の間に送信されてもよいし、他の方法において証明者８３８、又は、ベリファイヤ１１０によって入手されてもよい。また、有効性証明は、値ｃｊ（ｉ）自体よりもむしろｃｊ（ｉ）の関数であってもよい。ここでは、ｃｊ（ｉ）を一般的に「有効性証明データ」、すなわち、有効性証明を入手するために用いるデータとする。
【００８１】
本発明は、特定の数の証明書に限定されるものではない。証明書の数は、図１０のように２の倍数である必要はない。図１０のコンプリメントカバーは、非バイナリツリー型カバー及び、ツリーとして表されないコンプリメントカバーと入れ替えることができる。本発明は、如何なる特定のハッシュ関数、又は、（計算は容易だが一方向であり、衝突耐性を持つ）暗号化関数に限定されるものではない。いくつかの実施形態において、関数ｆ、又は、Ｈは、同じイメージに異なるｘ及びｙを見つけることが困難であるという意味においてではなく、ｘ及びｙが関数のドメインから一様に引き出された場合において、両者が同じイメージを持つであろう確率は低いという意味において、衝突耐性を備えていることが望ましい。すなわち、
【数１３】
2008524931.tif 000015
【００８２】
である。ここで、αは、小さい定数（例えば、１／１０、又は、１／１００、又は、２−２５、又は、２−５０、又は、２−８０、又は、２−１６０、又は、その他の値）である。有効性証明に用いた技術のいくつか、又は、全ては、無効性証明にも用いることができ、その逆も可能である。ＣＡ、Ｓｕｂ−ＣＡs、ディレクトリ、及びシステム１１０は、ひとつのネットワーク、又は、複数のネットワークを介して相互に連結したソフトウェアでプログラム可能なコンピュータシステム、又は、配線で接続されたコンピュータシステムを含んでもよい。各関数ｆ、又は、Ｈはコンピュータシステムが実行する評価方法を表わす。本発明は、フローチャートに示したステップの順番に限定されるものではない。なぜならば、ステップの順番は、交換可能なこともあり、さらに異なるステップを平行して実行してもよい。他の実施形態及び変形例も、添付した請求の範囲によって定義される様に発明の範囲内にある。
【００８３】
以下の参考文献の全ては、参照によりここに引用したものとする。
【００８４】
［１］アイエロ（Ｗ．Ａｉｅｌｌｏ）、ロダ（Ｓ．Ｌｏｄｈａ）、及びオストロフスキ（Ｒ．  Ｏｓｔｒｏｖｓｋｙ）著、「デジタルアイデンティティの高速失効（Ｆａｓｔ  ｄｉｇｉｔａｌ  ｉｄｅｎｔｉｔｙ  ｒｅｖｏｃａｔｉｏｎ）」、予稿集、クリプト９８(ＣＲＹＰＴＯ９８)、１９９８年
［２］アテニーズ（Ｇ．  Ａｔｅｎｉｅｓｅ）、カメニッシュ（Ｊ．Ｃａｍｅｎｉｓｃｈ）、ジョイ（Ｍ．Ｊｏｙｅ）、及びツディック（Ｇ．Ｔｓｕｄｉｋ）著、「実用的で安全と思われる衝突耐性を持つグループ署名スキーム(Ａ  Ｐｒａｃｔｉｃａｌ  ａｎｄ  Ｐｒｏｖａｂｌｙ  Ｓｅｃｕｒｅ  Ｃｏａｌｉｔｉｏｎ−Ｒｅｓｉｓｔａｎｔ  Ｇｒｏｕｐ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅ)」、予稿集、クリプト２０００(ＣＲＹＰＴＯ２０００)、２０００年
［３］バラレ（Ｍ．Ｂｅｌｌａｒｅ）及びロガウェイ（Ｐ．Ｒｏｇａｗａｙ）著、「ランダムオラクルは実用的である:効率的なプロトコルのデザイン用パラダイム(Ｒａｎｄｏｍ  ｏｒａｃｌｅｓ  ａｒｅ  ｐｒａｃｔｉｃａｌ：  Ａ  ｐａｒａｄｉｇｍ  ｆｏｒ  ｄｅｓｉｇｎｉｎｇ  ｅｆｆｉｃｉｅｎｔ  ｐｒｏｔｏｃｏｌｓ”、予稿集、第1回コンピュータ・通信セキュリティ年次大会（Ｆｉｒｓｔ  Ａｎｎｕａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｅｃｕｒｉｔｙ）、エイ・シー・エム(ＡＣＭ)、１９９３年
［４］ボネ（Ｄ．Ｂｏｎｅｈ）、リン（Ｂ．Ｌｙｎｎ）及びシャッハム（Ｈ．Ｓｈａｃｈａｍ）、「ワイルペアリングからの短い署名(Ｓｈｏｒｔ  ｓｉｇｎａｔｕｒｅｓ  ｆｒｏｍ  ｔｈｅ  Ｗｅｉｌ  ｐａｉｒｉｎｇ”、予稿集、アジアクリプト’０１(Ａｓｉａｃｒｙｐｔ’０１)、２００１年
［５］エルワイリ（Ｆ．Ｅｌｗａｉｌｌｙ）及びラムザン（Ｚ．Ｒａｍｚａｎ）著、「クワジモード:より効率的なハッシュツリーに基づく証明書失効(ＱｕａｓｉＭｏｄｏ：  Ｍｏｒｅ  Ｅｆｆｉｃｉｅｎｔ  Ｈａｓｈ  Ｔｒｅｅ−Ｂａｓｅｄ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｒｅｖｏｃａｔｉｏｎ)」、原稿、２００３年
［６］ガスコ（Ｉ．Ｇａｓｓｋｏ）、ゲメル（Ｐ．Ｓ．Ｇｅｍｍｅｌｌ）及びマッケンンジー（Ｐ．ＭａｃＫｅｎｚｉｅ）著、「効率的新規認証(Ｅｆｆｉｃｉｅｎｔ  ａｎｄ  ｆｒｅｓｈ  ｃｅｒｔｉｆｉｃａｔｉｏｎ)」、予稿集、ピー・ケイ・シー２０００(ＰＫＣ２０００)、２０００年
［７］ゴールドワッサー（Ｓ．Ｇｏｌｄｗａｓｓｅｒ）、ミカリ（Ｓ．Ｍｉｃａｌｉ）、リベスト（Ｒ．Ｌ．Ｒｉｖｅｓｔ）著、「適応型選択メッセージ攻撃に対して安全なデジタル署名スキーム(Ａ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅ  Ｓｅｃｕｒｅ  Ａｇａｉｎｓｔ  Ａｄａｐｔｉｖｅ  Ｃｈｏｓｅｎ−Ｍｅｓｓａｇｅ  Ａｔｔａｃｋｓ)」、シャム(ＳＩＡＭ)、コンピューティングに関するジャーナル(Ｊｏｕｒｎａｌ  ｏｎ  Ｃｏｍｐｕｔｉｎｇ)、１７（２）巻、２８１−３０８ページ、１９８８年
［８］フ（Ｙ−Ｃ．Ｈｕ）、ペリング（Ａ．Ｐｅｒｒｉｇ）及びジョンソン（Ｄ．Ｊｏｈｎｓｏｎ）著、「ルーティングプロトコル用の効率的な安全性メカニズム(Ｅｆｆｉｃｉｅｎｔ  ｓｅｃｕｒｉｔｙ  ｍｅｃｈａｎｉｓｍｓ  ｆｏｒ  ｒｏｕｔｉｎｇ  ｐｒｏｔｏｃｏｌｓ)」、予稿集、ネットワーク及び分散型システムの安全性に関する第１０回シンポジウム(ｔｈｅ  １０ｔｈ  Ａｎｎｕａｌ  Ｎｅｔｗｏｒｋ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍ  Ｓｅｃｕｒｉｔｙ  Ｓｙｍｐｏｓｉｕｍ  （ＮＤＳＳ）)、２００３年
［９］ヤコブソン（Ｍ．Ｊａｋｏｂｓｓｏｎ）、ヒューボウ（Ｊ−Ｐ．Ｈｕｂａｕｘ）及びバッタイアン（Ｌ．Ｂｕｔｔｙａｎ）著、「マルチ・ホップセルラーネットワークにおいてコラボレーションを促すマイクロペイメントスキーム(Ａ  ｍｉｃｒｏｐａｙｍｅｎｔ  ｓｃｈｅｍｅ  ｅｎｃｏｕｒａｇｉｎｇ  ｃｏｌｌａｂｏｒａｔｉｏｎ  ｉｎ  ｍｕｌｔｉ−ｈｏｐ  ｃｅｌｌｕｌａｒ  ｎｅｔｗｏｒｋｓ)」、予稿集、金融暗号技術に関する第７回国際会議(ｔｈｅ  ７ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｆｉｎａｎｃｉａｌ  Ｃｒｙｐｔｏｇｒａｐｈｙ)、２００３年
［１０］ヤコブソン（Ｍ．Ｊａｋｏｂｓｓｏｎ）、レイトン（Ｔ．Ｌｅｉｇｈｔｏｎ）、ミカリ（Ｓ．Ｍｉｃａｌｉ）及びジドロ（Ｍ．Ｓｚｙｄｌｏ）著、「フラクタルメルケルツリーリプリゼーション及びトラバーサル(Ｆｒａｃｔａｌ  ｍｅｒｋｌｅ  ｔｒｅｅ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎ  ａｎｄ  ｔｒａｖｅｒｓａｌ)」、予稿集、暗号使用者のトラックＲＳＡ会議(ｔｈｅ  Ｃｒｙｐｔｏｇｒａｐｈｅｒ’ｓ  Ｔｒａｃｋ  ＲＳＡ  Ｃｏｎｆｅｒｅｎｃｅ)、２００３年
［１１］ジャレッキ（Ｓ．Ｊａｒｅｃｋｉ）及びオドリスコ（Ａ．Ｏｄｌｙｚｋｏ）著、「確率的ポーリングに基づく効率的なマイクロペイメントシステム(Ａｎ  ｅｆｆｉｃｉｅｎｔ  ｍｉｃｒｏｐａｙｍｅｎｔ  ｓｙｓｔｅｍ  ｂａｓｅｄ  ｏｎ  ｐｒｏｂａｂｉｌｉｓｔｉｃ  ｐｏｌｌｉｎｇ)」、予稿集、金融暗号技術に関する第１回国際会議(ｔｈｅ  １ｓｔ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｆｉｎａｎｃｉａｌ  Ｃｒｙｐｔｏｇｒａｐｈｙ)、１９９７年
［１２］ロバート・ジョンソン（Ｒｏｂｅｒｔ  Ｊｏｈｎｓｏｎ）及びデイビッド・モルナ（Ｄａｖｉｄ  Ｍｏｌｎａｒ）、ダウン・シャオドン・ソン（Ｄａｗｎ  Ｘｉａｏｄｏｎｇ  Ｓｏｎｇ）及びデイビッド・ワグナー（Ｄａｖｉｄ  Ｗａｇｎｅｒ）著、「準同形署名スキーム(Ｈｏｍｏｍｏｒｐｈｉｃ  ｓｉｇｎａｔｕｒｅ  ｓｃｈｅｍｅｓ)」、シー・ティーＲＳＡ(ＣＴ−ＲＳＡ)、２４４−２６２ページ、２００２年
［１３］ジャルタ（Ｃ．Ｊｕｔｌａ）及びユン（Ｍ．Ｙｕｎｇ）著、「ペイツリー：フレキシブルなマイクロペイメントのための、ならし署名(ＰａｙＴｒｅｅ：  Ａｍｏｒｔｉｚｅｄ  ｓｉｇｎａｔｕｒｅｓ  ｆｏｒ  ｆｌｅｘｉｂｌｅ  ｍｉｃｒｏｐａｙｍｅｎｔｓ)」、予稿集、電子商取引に関する第２回ＵＳＥＮＩＸワークショップ(ｔｈｅ  ｓｅｃｏｎｄ  ＵＳＥＮＩＸ  ｗｏｒｋｓｈｏｐ  ｏｎ  ｅｌｅｃｔｒｏｎｉｃ  ｃｏｍｍｅｒｃｅ)、１９９６年
［１４］キム（Ｓ．Ｋｉｍ）及びオウ（Ｈ．Ｏｈ）著、「モバイルコンピューティング環境のためのアトミックマイクロペイメントシステム(Ａｎ  ａｔｏｍｉｃ  ｍｉｃｒｏｐａｙｍｅｎｔ  ｓｙｓｔｅｍ  ｆｏｒ  ａ  ｍｏｂｉｌｅ  ｃｏｍｐｕｔｉｎｇ  ｅｎｖｉｒｏｎｍｅｎｔ)」、ＩＥＩＣＥ情報及びシステムの取引(ＩＥＩＣＥＴｒａｎｓａｃｔｉｏｎｓ  ｏｆ  Ｉｎｆｏｒｍａｔｉｏｎ  ａｎｄ  Ｓｙｓｔｅｍｓ)、Ｅ８４−Ｄ（６）、７０９−７１６ページ、２００１年
［１５］コッハー（Ｐ．Ｋｏｃｈｅｒ）著、「証明書の失効及び検証に関して(Ｏｎ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｒｅｖｏｃａｔｉｏｎ  ａｎｄ  Ｖａｌｉｄａｔｉｏｎ)」、予稿集、金融暗号技術に関する第2回国際会議(ｔｈｅ  ２ｎｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｆｉｎａｎｃｉａｌ  Ｃｒｙｐｔｏｇｒａｐｈｙ)、１９９８年
［１６］サトシ・コガ（Ｓａｔｏｓｈｉ  Ｋｏｇａ）及びコウイチ・サクライ（Ｋｏｕｉｃｈｉ  Ｓａｋｕｒａｉ）著、「単一の公開鍵を有する分散型証明書状態プロトコル(Ａ  ｄｉｓｔｒｉｂｕｔｅｄ  ｃｅｒｔｉｆｉｃａｔｅ  ｓｔａｔｕｓ  ｐｒｏｔｏｃｏｌ  ｗｉｔｈ  ｓｉｎｇｌｅ  ｐｕｂｌｉｃ  ｋｅｙ)」、予稿集、ピィ・ケイ・シィ２００４(ＰＫＣ２００４)、３８９−４０１ページ、２００４年
［１７］リプトン（Ｒ．Ｊ．Ｌｉｐｔｏｎ）及びオストロフスキ（Ｒ．Ｏｓｔｒｏｖｓｋｙ）著、「効率的なコインフリッピングによるマイクロペイメント(Ｍｉｃｒｏ−Ｐａｙｍｅｎｔｓ  ｖｉａ  Ｅｆｆｉｃｉｅｎｔ  Ｃｏｉｎ  Ｆｌｉｐｐｉｎｇ)」、予稿集、金融暗号技術に関する第２回国際会議(ｔｈｅ  ２ｎｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｆｉｎａｎｃｉａｌ  Ｃｒｙｐｔｏｇｒａｐｈｙ)、１９９８年
［１８］マルパーニ（Ａ．Ｍａｌｐａｎｉ）、ハウスリィ（Ｒ．Ｈｏｕｓｅｌｙ）、及びフリーマン（Ｔ．Ｆｒｅｅｍａｎ）著、「簡単な証明書検証プロトコル(Ｓｉｍｐｌｅ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｖａｌｉｄａｔｉｏｎ  Ｐｒｏｔｏｃｏｌ  −  （ＳＣＶＰ）)」、ＩＥＴＦドラフト(ＩＥＴＦ  Ｄｒａｆｔ)、ｄｒａｆｔ−ｉｅｔｆ−ｐｋｉｘ−ｓｃｖｐ−１２．ｔｘｔ、２００３年６月
［１９］メルクル（Ｒ．Ｃ．Ｍｅｒｋｌｅ）著、「公開鍵暗号技術用プロトコル(Ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ)」、安全性及びプライバシーに関するＩＥＥＥシンポジウム(ＩＥＥＥＳｙｍｐｏｓｉｕｍ  ｏｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｐｒｉｖａｃｙ)、１９８０年
［２０］ミカリ（Ｓ．Ｍｉｃａｌｉ）著、「効率的な証明書の失効(Ｅｆｆｉｃｉｅｎｔ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｒｅｖｏｃａｔｉｏｎ)」、ＭＩＴ／ＬＣＳ／ＴＭ  ５４２ｂ、マサチュウセッツ工科大学(Ｍａｓｓａｃｈｕｓｅｔｔｓ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｔｅｃｈｎｏｌｏｇｙ)、１９９６年
［２１］ミカリ（Ｓ．Ｍｉｃａｌｉ）著、「効率的な証明書の失効(Ｅｆｆｉｃｉｅｎｔ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｒｅｖｏｃａｔｉｏｎ)」、予稿集、ＲＳＡデータセキュリティ会議 (ｔｈｅ  ＲＳＡ  Ｄａｔａ  Ｓｅｃｕｒｉｔｙ  Ｃｏｎｆｅｒｅｎｃｅ)、１９９７年、及び米国特許第５６６６４１６
［２２］ミカリ（Ｓ．Ｍｉｃａｌｉ）著、「ＮＯＶＯＭＯＤＯ：スケーラブル証明書有効性検証及び簡略化したＰＫＩマネージメント(ＮＯＶＯＭＯＤＯ：  ｓｃａｌａｂｌｅ  ｃｅｒｔｉｆｉｃａｔｅ  ｖａｌｉｄａｔｉｏｎ  ａｎｄ  ｓｉｍｐｌｉｆｉｅｄ  ＰＫＩ  ｍａｎａｇｅｍｅｎｔ)」、予稿集、第１回ＰＫＩ研究ワークショップ年次会議(ｔｈｅ  １ｓｔ  Ａｎｎｕａｌ  ＰＫＩ  Ｒｅｓｅａｒｃｈ  Ｗｏｒｋｓｈｏｐ)、２００２年
［２３］メイヤーズ(Ｍ．Ｍｙｅｒｓ)、アンクネイ(Ｒ．Ａｎｋｎｅｙ)、マルパーニ(Ａ．  Ｍａｌｐａｎｉ)、ガルペリン(Ｓ．  Ｇａｌｐｅｒｉｎ)、及びアダムス(Ｃ．  Ａｄａｍｓ)著、「Ｘ．５０９インターネット公開鍵インフラオンライン証明書状態プロトコル(Ｘ．５０９  ｉｎｔｅｒｎｅｔ  ｐｕｂｌｉｃ  ｋｅｙ  ｉｎｆｒａｓｔｒｕｃｔｕｒｅ  Ｏｎｌｉｎｅ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｓｔａｔｕｓ  Ｐｒｏｔｏｃｏｌ−ＯＣＳＰ)」、インターネットＲＦＣ２５６０(Ｉｎｔｅｒｎｅｔ  ＲＦＣ  ２５６０)、１９９９年６月
［２４］ナオル(Ｍ．Ｎａｏｒ)及びニッシム(Ｋ．Ｎｉｓｓｉｍ)著、「(Ｃｅｒｔｉｆｉｃａｔｅ  Ｒｅｖｏｃａｔｉｏｎ  ａｎｄ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｕｐｄａｔｅ)」、予稿集、ＵＳＥＮＩＸセキュリティ(ＵＳＥＮＩＸ  Ｓｅｃｕｒｉｔｙ)、  １９９８年
［２５］アメリカ標準局(Ｎａｔｉｏｎａｌ  Ｂｕｒｅａｕ  ｏｆ  Ｓｔａｎｄａｒｄｓ)発行、「ＮＢＳ  ＦＩＰＳ  ＰＵＢ  ８１：オペレーションのＤＥＳモデル(ＮＢＳ  ＦＩＰＳ  ＰＵＢ  ８１：ＤＥＳ  ｍｏｄｅｓ  ｏｆ  ｏｐｅｒａｔｉｏｎ)」、１９８０年
［２６］アメリカ標準局(Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ)発行、「ＦＩＰＳ  １８０−１：安全なハッシュ基準(ＦＩＰＳ  １８０−１：  Ｓｅｃｕｒｅ  ｈａｓｈ  ｓｔａｎｄａｒｄ)」、１９９５年
［２７］ピアス(Ｍ．Ｐｉｅｒｃｅ)、及びオーマホニー(Ｄ．Ｏ’Ｍａｈｏｎｙ)著、「モバイルネットワークのためのマイクロペイメント(Ｍｉｃｒｏｐａｙｍｅｎｔｓ  ｆｏｒ  Ｍｏｂｉｌｅ  Ｎｅｔｗｏｒｋｓ)」、予稿集、ヨーロピアン無線(Ｅｕｒｏｐｅａｎ  Ｗｉｒｅｌｅｓｓ)、１９９９年、最優秀論文賞受賞(Ｗｉｎｎｅｒ  ｏｆ  Ｂｅｓｔ  Ｐａｐｅｒ  Ａｗａｒｄ)
［２８］リベスト（Ｒ．Ｌ．Ｒｉｖｅｓｔ）著、「ＭＤ５メッセージダイジェストアルゴリズ(Ｔｈｅ  ＭＤ５  ｍｅｓｓａｇｅ  ｄｉｇｅｓｔ  ａｌｇｏｒｉｔｈｍ)」、インターネット  アール・エフ・シー１３２１(Ｉｎｔｅｒｎｅｔ  ＲＦＣ  １３２１)、１９９２年４月
［２９］リベスト(Ｒ．Ｌ．Ｒｉｖｅｓｔ)著、「マイクロペイメントとしての電子ロトチケット(Ｅｌｅｃｔｒｏｎｉｃ  Ｌｏｔｔｅｒｙ  Ｔｉｃｋｅｔｓ  ａｓ  Ｍｉｃｒｏｐａｙｍｅｎｔｓ)」、予稿集、金融暗号技術に関する第２回国際会議(ｔｈｅ  ２ｎｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｆｉｎａｎｃｉａｌ  Ｃｒｙｐｔｏｇｒａｐｈｙ)、１９９７年
［３０］リベスト(Ｒ．Ｌ．  Ｒｉｖｅｓｔ)、及びシャミール(Ａ．  Ｓｈａｍｉｒ)著、「ペイワード及びマイクロミント−2つのシンプルなマイクロペイメントスキーム(ＰａｙＷｏｒｄ  ａｎｄ  ＭｉｃｒｏＭｉｎｔ−Ｔｗｏ  Ｓｉｍｐｌｅ  Ｍｉｃｒｏｐａｙｍｅｎｔ  Ｓｃｈｅｍｅｓ)」、クリプトバイト(ＣｒｙｐｔｏＢｙｔｅｓ)、ＲＳＡラボラトリィズ（ＲＳＡ  Ｌａｂｏｒａｔｏｒｉｅｓ）、２（１）巻、１９９６年、予稿集、１９９６年セキュリティプロトコルに関する国際ワークショップ(１９９６ Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｓｅｃｕｒｉｔｙ  Ｐｒｏｔｏｃｏｌｓ)
［３１］リベスト（Ｒ．Ｌ．Ｒｉｖｅｓｔ）、シャミール（Ａ．Ｓｈａｍｉｒ）及びアドルマン（Ｌ．Ａｄｌｅｍａｎ）著、「デジタル署名及び公開鍵クリプトシステムを取得するための方法(Ａ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｏｂｔａｉｎｉｎｇ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅｓ  ａｎｄ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ)」、エイ・シー・エム通信(Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ)、２１：１２０−１２６ページ、１９７８年
［３２］ロン・シュタインフィールド(Ｒｏｎ  Ｓｔｅｉｎｆｅｌｄ)、ローレンス・ブル(Ｌａｕｒｅｎｃｅ  Ｂｕｌｌ)、及びユリアン・ツェン(Ｙｕｌｉａｎｇ  Ｚｈｅｎｇ)著、「コンテンツ抽出署名(Ｃｏｎｔｅｎｔ  ｅｘｔｒａｃｔｉｏｎ  ｓｉｇｎａｔｕｒｅｓ)」、予稿集、ソウル情報セキュリティ及び暗号に関する第4回国際会議 (ｔｈｅ  ４ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  Ｓｅｏｕｌ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｃｒｙｐｔｏｌｏｇｙ)、２８５−３０４ページ、シュプリンガ−フェアラーク(Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ)社、２００２年
［３３］テワリ(Ｈ．Ｔｅｗａｒｉ)、及びオーマホニー(Ｄ．Ｏ’Ｍａｈｏｎｙ)著、「アドホックネットワーク用マルチパーティ・マイクロペイメント(Ｍｕｌｔｉｐａｒｔｙ  Ｍｉｃｒｏｐａｙｍｅｎｔｓ  ｆｏｒ  Ａｄ−Ｈｏｃ  Ｎｅｔｗｏｒｋｓ)」、予稿集、ＩＥＥＥ無線通信及びネットワークに関する会議(ｔｈｅ  ＩＥＥＥ  Ｗｉｒｅｌｅｓｓ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ａｎｄ  Ｎｅｔｗｏｒｋｉｎｇ  Ｃｏｎｆｅｒｅｎｃｅ  （ＷＣＮＣ）)、２００３年
［３４］テワリ(Ｈ．Ｔｅｗａｒｉ)及びオーマホニー(Ｄ．Ｏ’Ｍａｈｏｎｙ)著、「モバイルＩＰ用リアルタイムペイメント(Ｒｅａｌ−Ｔｉｍｅ  Ｐａｙｍｅｎｔｓ  ｆｏｒ  Ｍｏｂｉｌｅ  ＩＰ)」、ＩＥＥＥ通信(ＩＥＥＥ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ)、４１（２）巻：１２６−１３６、２００３年
［３５］ウィーラー（Ｄ．Ｗｈｅｅｌｅｒ）著、「賭けを用いた取引(Ｔｒａｎｓａｃｔｉｏｎｓ  Ｕｓｉｎｇ  Ｂｅｔｓ)」、予稿集、セキュリティプロトコルに関する第4回ケンブリッジワークショップ(Ｆｏｕｒｔｈ  Ｃａｍｂｒｉｄｇｅ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｓｅｃｕｒｉｔｙ  Ｐｒｏｔｏｃｏｌｓ)、１９９６年
［３６］ツォウ（Ｊ．Ｚｈｏｕ）及びラム（Ｋ−Ｙ．Ｌａｍ）著、「モバイル通信における優れたビリング(Ｕｎｄｅｎｉａｂｌｅ  Ｂｉｌｌｉｎｇ  ｉｎ  Ｍｏｂｉｌｅ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ”、予稿集、モビコム(ＭＯＢＩＣＯＭ)、１９９８年  
【図面の簡単な説明】
【００８５】
【図１】図１は、従来技術による証明書失効スキームを説明するブロック図である。
【図２】図２は、従来技術による証明書失効スキームを説明するブロック図である。
【図３】図３は、従来技術による証明書失効スキーム用の証明書の集合を説明する図である。
【図４】図４は、従来技術による証明書失効スキーム用の証明書の集合を説明する図である。
【図５】図５は、従来技術による証明書失効スキーム用のコンピュータデータ構造を説明する図である。
【図６】図６は、従来技術による証明書失効スキーム用のコンピュータデータ構造を説明する図である。
【図７】図７は、本発明のいくつかの実施形態による認証局が実行するオペレーションのフローチャートである。
【図８】図８は、本発明のいくつかの実施形態による証明書失効スキーム用のコンピュータシステム及び、コンピュータデータ構造を説明する図である。
【図９】図９は、本発明のいくつかの実施形態により実行するオペレーションのフローチャートである。
【図１０】図１０は、本発明のいくつかの実施形態による証明書失効スキーム用のコンピュータデータ構造を説明する図である。
【符号の説明】
【００８６】
１０４、１４０  証明書
１１０  コンピュータシステム
１２０  認証局
１５０  クエリ
１６０  有効状況情報
２１０  ディレクトリ
８０４  コンプリメントカバー
８２４  有効性証明データストレージ
８３４  復号鍵データストレージ
８３８  証明者
５１０  バイナリツリー
【図１】
2008524931.tif 000016
【図２】
2008524931.tif 000017
【図３】
2008524931.tif 000018
【図４】
2008524931.tif 000019
【図５】
2008524931.tif 000020
【図６】
2008524931.tif 000021
【図７】
2008524931.tif 000022
【図８】
2008524931.tif 000023
【図９】
2008524931.tif 000024
【図１０】
2008524931.tif 000025
【手続補正書】
【提出日】平成19年11月21日(2007.11.21)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の期間における複数のデジタル証明書の有効性、及び／又は、無効性を検証するためのコンピュータデータを生成するコンピュータに実装された方法であって、
それぞれの前記デジタル証明書は、暗号鍵がエンティティに関連付けられていることを証明し、
前記デジタル証明書は、第１のデジタル証明書を含み、
前記方法は、
（ａ）前記デジタル証明書をひとつ以上含む集合において、複数の集合を定義する第１のデータを取得する工程と、
（ｂ）前記デジタル証明書及び前記期間ごとに、前記期間における前記デジタル証明書の有効性、又は、無効性を証明するため、関連付けられた証明データを定義する第２のデータを取得する工程と、
（ｃ）前記デジタル証明書及び前記期間Ｔ１ごとに、前記デジタル証明書及び前記期間Ｔ１と関連付けられた前記証明データを暗号化及び復号化するための暗号鍵及び対応する復号鍵を定義する第３のデータを取得する工程とを含み、
前記複数の集合は、第１の複数の集合を含み、
前記第１のデジタル証明書は、前記第１の複数の集合に含まれるそれぞれの前記集合に属しており、
前記第１の複数の集合の少なくともひとつの前記集合は、２つ以上の前記デジタル証明書を含み、
(ｃ１) 前記第３のデータは、前記デジタル証明書を含む前記集合ごとに、前記集合及び前記期間Ｔ１と関連付けられた復号鍵データを定義し、
前記デジタル証明書及び前記期間Ｔ１と関連付けられた前記復号鍵は、前記デジタル証明書を含む前記集合のうちの所定のいずれか一つ及び前記期間Ｔ１を含むひとつ以上の前記期間に関連付けられた前記復号鍵データから計算可能であり、
(ｄ)少なくとも一期間に対して、前記第1の複数の集合のうちの少なくとも2つの集合は、それぞれ異なる復号鍵データと関連付けられており、
前記第1の複数の集合のうちの少なくともひとつの集合において、前記第1のデジタル証明書及び少なくとも一つの他のデジタル証明書は、それぞれ異なる復号鍵と関連付けられていることを特徴とする方法。
【請求項２】
前記デジタル証明書及び前記期間ごとに、ひとつ以上の前記復号鍵で復号するために関連付けられた前記証明データを暗号化する工程をさらに含むことを特徴とする請求項1に記載の方法。
【請求項３】
少なくともひとつのデジタル証明書及び、少なくとも一期間に対して、関連付けられた前記証明データを復号するための関連付けられた前記復号鍵は、複数の期間と関連付けられた復号鍵データによって決まることを特徴とする請求項1に記載の方法。
【請求項４】
請求項１に記載の方法を実行するコンピュータシステム。
【請求項５】
請求項１に記載の方法を実行するように操作可能なひとつ以上のコンピュータ命令を備えるデータキャリア。
【請求項６】
複数のデジタル証明書の有効性、又は、無効性の証明の生成を可能とし、複数の期間のうちの一期間である第１の期間における前記証明を提供するコンピュータに実装された方法であって、
それぞれの前記デジタル証明書は、暗号鍵がエンティティと関連付けられていることを証明し、前記デジタル証明書は、第1のデジタル証明書を含み、
前記方法は、
(ａ)前記デジタル証明書の全てを含む集合に対して、第1の複数の集合を含む第1のコンプリメントカバーを定義する第1のデータを取得する工程を含み、
前記第1のデジタル証明書は、前記第1の複数の集合における各集合に属し、
前記第1の複数の集合の少なくともひとつは、2つ以上のデジタル証明書を含み、
(ａ１)前記デジタル証明書のそれぞれ、及び、前記期間のそれぞれは、前記期間における前記デジタル証明書の有効性、又は、無効性を証明するための証明データを復号するための復号鍵と関連付けられており、
(ａ２)前記集合のそれぞれ、及び、前記期間のぞれぞれは、復号鍵データと関連付けられており、
(ａ３)前記証明書及び前記期間Ｔ１ごとに、前記関連付けられた復号鍵は、前記証明書を含む前記集合のうちの所与のいずれかひとつ、及び、前記期間Ｔ１を含む前記期間の一期間以上と関連付けられた前記復号鍵データから計算可能であり、
(ａ４)前記期間のうちの少なくとも一期間に対して、前記第1の複数の集合うちの少なくとも2つの集合は、それぞれ異なる復号鍵データと関連付けられており、前記第1の複数のうちの少なくともひとつの集合において、前記第1のデジタル証明書及び、少なくともひとつの他のデジタル証明書は、相異なる復号鍵と関連付けられており、
前記方法は、
(ｂ)前記第1のコンプリメントカバーから、無効なデジタル証明書の集合に対するコンプリメントカバーである第2のコンプリメントカバーを選択する工程と、
(ｃ)前記第2のコンプリメントカバーにおける集合ごとに、前記集合と少なくとも前記第1の期間とに関連付けられた復号鍵データをネットワーク上で送信する工程とを含み、
前記無効なデジタル証明書の集合には、前記第1のデジタル証明書を含まず、前記第2のコンプリメントカバーは、前記第1の複数の集合のうち少なくともひとつの集合を含むことを特徴とする方法。
【請求項７】
前記第1の複数の集合のうちの少なくともひとつは、前記第2のコンプリメントカバーにあり、かつ、それぞれ異なる復号鍵と関連付けられている複数のデジタル証明書を含むことを特徴とする請求項6に記載の方法。
【請求項８】
無効なデジタル証明書の前記集合は、前記デジタル証明書が失効するように操作可能である時よりも後に始まる第1の間隔において失効した前記デジタル証明書の全ての集合であり、
前記集合には、前記第1の間隔の前に失効したデジタル証明書は含まれないことを特徴とする請求項６に記載の方法。
【請求項９】
各デジタル証明書は、前記デジタル証明書が有効である場合、前記デジタル証明書のための前記復号鍵を受け取るためのコンピュータシステムと関連付けられており、
前記第2のコンプリメントカバーにおける少なくともひとつの集合に対して、前記集合は、複数の前記コンピュータシステムと関連付けられた複数の前記デジタル証明書を含むが、前記集合のための前記復号鍵は、ひとつ以上だが全て未満の前記コンピュータシステムの前記複数の残りのコンピュータシステムに対して再送信するために、前記複数のコンピュータシステムの全て未満のものに対して送信されることを特徴とする請求項６に記載の方法。
【請求項１０】
前記第1のコンプリメントカバーを定義する工程と、
前記コンピュータシステムは、物理的に互いに近い第1の複数のコンピュータシステムを含むことを示すデータを受け取る工程と、
(ｂ)の工程の前に、それぞれが第1のコンプリメントカバーに属し、前記コンピュータシステムの前記第1の複数のコンピュータシステムと関連付けられた前記デジタル証明書を含む集合Ｆの数が増大するように前記第1のコンプリメントカバーを再定義する工程とをさらに含むことを特徴とする請求項９に記載の方法。
【請求項１１】
前記第1のコンプリメントカバーを、前記第1のコンプリメントカバーにおける前記集合の総数を変えることなく再定義することを特徴とする請求項１０に記載の方法。
【請求項１２】
請求項６に記載の方法を実行するコンピュータシステム。
【請求項１３】
請求項６に記載の方法を実行するように操作可能なひとつ以上のコンピュータ命令を備えるデータキャリア。
【請求項１４】
複数の期間のうちの一期間である第1の期間において、複数のデジタル証明書のうちのひとつである第１のデジタル証明書の有効性、又は、無効性の証明を生成する、コンピュータに実装された方法であって、
それぞれのデジタル証明書は、暗号鍵がエンティティと関連付けられていることを証明し、
複数の集合が定義されており、
それぞれの集合は、前記デジタル証明書のひとつ以上の集合であり、
前記複数の集合は、第１の複数の集合を含み、
前記第１のデジタル証明書は、前記第1の複数の各集合に属し、
前記第1の複数のうちの少なくともひとつの集合は、２つ以上のデジタル証明書を含み、
前記方法は、
(ａ)少なくとも前記第1のデジタル証明書及び前記期間のそれぞれに対して、前記期間における第1のデジタル証明書の有効性、又は、無効性を証明するための関連した証明データの暗号を取得する工程を含み、
(ａ１)前記証明書及び前記期間ごとに、前記証明書及び、前記期間と関連付けられた前記証明データを暗号化し、復号するための暗号鍵及び、対応する復号鍵が定義されており、
(ａ２)前記証明書及び前記期間Ｔ１ごとに、前記証明書を含む前記集合のそれぞれに対して、復号鍵データが、前記集合及び前記期間Ｔ１に関連付けられて定義され、前記証明書及び、前記期間Ｔ１と関連付けられた前記復号鍵は、前記証明書を含む前記集合のうちの所与のいずれかのもの、及び、前記期間Ｔ１を含む前記期間の一期間以上と関連付けられた前記復号鍵データから計算可能であり、
(ａ３)少なくとも前記第1の期間に対して、前記第1の複数の集合のうちの少なくとも２つの集合は、それぞれ異なる復号鍵データと関連付けられており、前記第1の集合のうちの少なくともひとつの集合において、前記第1のデジタル証明書と、少なくともひとつの他のデジタル証明書とが、相異なる復号鍵と関連付けられており、
前記方法は、
(ｂ)前記第１の複数の集合のうちの前記少なくとも2つの集合のうちの一方と関連付けられた前記復号鍵データをネットワーク上で受信する工程と、
(ｃ) 前記第1のデジタル証明書と、前記第1の期間とに関連付けられた前記復号鍵を計算するように、(ｂ)の操作で受信した前記復号鍵データを用いる工程と、
(ｄ)前記第1の期間における前記第1のデジタル証明書の有効性、又は、無効性の証明を提供するための前記証明データを復号する工程とをさらに含み、
前記復号する工程は、取得した前記復号鍵のもとで行われることを特徴とする方法。
【請求項１５】
（ｅ）前記第1の複数の集合のうちの一つ及び前記第１の期間に先行する第２の期間と関連付けられた復号鍵データを受信する工程を含み、
(ｃ)の工程において計算した前記復号鍵は、(ｂ)の工程において受信した前記復号鍵データ及び、(ｅ)の工程において受信した前記復号鍵データから求めることを特徴とする請求項１４に記載の方法。
【請求項１６】
請求項１４に記載の方法を実行するコンピュータシステム。
【請求項１７】
請求項１４に記載の方法を実行するように操作可能なひとつ以上のコンピュータ命令を備えるデータキャリア。
【請求項１８】
デジタル証明書の集合及び、期間に関連付けられた復号鍵データを提供する第１のコンピュータデータを備えるデータキャリアであって、
それぞれのデジタル証明書は、暗号鍵がエンティティと関連付けられていることを証明し、
前記復号鍵データは、前記期間における前記デジタル証明書の有効性、又は、無効性を証明するために暗号化された証明データを復号するための復号鍵を提供するためのものであり、
少なくともひとつのデジタル証明書及び、少なくとも一期間Ｔ１に対して、少なくともひとつの関連付けられた復号鍵は、それぞれが前記デジタル証明書を含み、且つ、複数のデジタル証明書を含む集合のうちの所与のいずれかと、前記期間Ｔ１を含む前記期間の一期間以上と関連付けられた前記復号鍵データとから計算可能であり、
少なくとも前記一期間に対して、前記少なくともひとつのデジタル証明書を含む前記集合のうちの少なくとも２つは、それぞれ異なる復号鍵データと関連付けられており、
前記少なくともひとつのデジタル証明書を含む前記集合のうちの少なくともひとつにおいて、前記少なくともひとつのデジタル証明書及び、少なくともひとつの他のデジタル証明書は、それぞれ異なる復号鍵と関連付けられていることを特徴とするデータキャリア。
【請求項１９】
複数の期間におけるデジタル証明書の有効性、又は、無効性を証明するための暗号化された証明データを含むコンピュータデータを含むデータキャリアであって、
それぞれのデジタル証明証は、暗号鍵がエンティティと関連付けられていることを証明し、
前記暗号化された証明データは、復号鍵で復号するために暗号化されており、
少なくともひとつのデジタル証明書及び、少なくとも一期間Ｔ１に対して、少なくともひとつの関連付けられた復号鍵は、デジタル証明書の複数の集合のうちの所与のいずれかの集合と、前記期間Ｔ１を含む前記期間の一期間以上とに関連付けられた復号鍵データから計算可能であり、それぞれの集合には、前記少なくともひとつのデジタル証明書及び、少なくともひとつの他のデジタル証明書を含まれており、
前記集合のうちの少なくとも2つは、それぞれ異なる復号鍵データと関連付けられており、前記集合のうちの少なくともひとつにおいて、前記少なくともひとつのデジタル証明書及び、少なくともひとつの他のデジタル証明書は、それぞれ異なる復号鍵と関連付けられていることを特徴とするデータキャリア。
【請求項２０】
前記期間のうちのいずれかの期間Ｔ１及び、前記複数の集合のうち、Ｓ１がＳ２の部分集合であるような任意の２つの集合Ｓ１及びＳ２に対して、Ｓ１及びＴ１と関連付けられた前記復号鍵データは、Ｓ２及びＴ１と関連付けられた前記復号鍵から計算可能であることを特徴とする請求項1に記載の方法。
【請求項２１】
前記デジタル証明書ごと及び前記期間ごとに、前記対応する復号鍵は、前記デジタル証明書を含む前記集合のうちのいずれかひとつと関連付けられた復号鍵データから計算可能であることを特徴とする請求項1に記載の方法。
【請求項２２】
前記第1の複数の集合は、Ｓ１がＳ２の正式な部分集合である集合Ｓ１及び集合Ｓ２を含み、前記期間の少なくとも一期間Ｔ１に対して、Ｓ１及びＴ１と関連付けられた前記復号鍵データは、Ｓ２及びＴ１と関連付けられた前記復号鍵のビットサイズと同じビットサイズを有することを特徴とする請求項1に記載の方法。
【請求項２３】
前記第1の複数の集合は、Ｓ１がＳ２の正式な部分集合である集合Ｓ１及び集合Ｓ２を含み、前記期間の少なくとも一期間Ｔ１に対して、Ｓ１及びＴ１と関連付けられた前記復号鍵は、Ｓ２及びＴ１と関連付けられた前記復号鍵のビットサイズと同じビットサイズを有することを特徴とする請求項６に記載の方法。
【請求項２４】
前記期間ごとに、任意の2つの相違なる証明書が、相違なる証明データと関連付けられていることを特徴とする請求項１４に記載の方法。
【請求項２５】
全ての前記復号鍵及び前記復号鍵データは、同じビットサイズを有することを特徴とする請求項１４に記載の方法。
【請求項２６】
複数の期間におけるデジタル証明書の有効性、及び／又は、無効性を検証するためのコンピュータデータを生成するコンピュータに実装された方法であって、
それぞれの前記デジタル証明書は、暗号鍵がエンティティに関連付けられていることを証明し、
(ａ)前記期間ごとに、前記期間におけるひとつ以上の前記デジタル証明書の有効性、及び／又は、無効性を証明するための関連付けられた証明データを定義するデータを取得する工程と、
(ｂ)前記期間ごとに、前記証拠データを暗号化及び復号化するためのひとつ以上の暗号鍵及び対応するひとつ以上の復号鍵を定義する暗号／復号データを取得する工程とを含み、
それぞれの復号鍵は、前記期間のうちの一期間において前記証明データを復号するために、前記期間のうちの一期間と関連付けられており、
（ｂ１）前記期間ごとに、前記暗号／復号データは、前記期間と関連付けられた復号鍵データを定義し、前記復号鍵データは、前記期間において、前記期間と関連付けられた前記復号鍵を計算するためのものであり、
（ｂ２）少なくとも前記一期間Ｔ１に対して、前記復号鍵は、
前記期間Ｔ１と関連付けられているが、(ｉ)前記期間Ｔ１と関連付けられた前記復号鍵データと、(ｉｉ)一期間以上のＴ１にを先行する前記期間と関連付けられた復号鍵データとによって決まる復号鍵、またそれらの前記復号鍵データから計算可能である復号鍵を含むことを特徴とする方法。
【請求項２７】
ぞれぞれの集合がひとつ以上の前記デジタル証明書のうちのひとつの集合である、複数の集合を定義するデータを取得する工程をさらに含み、
ひとつ以上の前記集合は、それぞれ、２つ以上の前記デジタル証明書を含み、
前記期間ごとに、前記関連付けられた復号鍵データは、前記集合のそれぞれと関連付けられた個別の復号鍵データを含み、
少なくとも前記期間Ｔ１に対して、（ｂ２）における前記復号鍵は、ひとつ以上の前記デジタル証明書と関連付けられた証明を復号するためのものであり、（ｂ２）における前記復号鍵は、（ｉ）前記期間Ｔ１及び、ひとつ以上の前記証明書を含む前記集合のうちの所与のいずれかの集合と関連付けられた前記復号鍵データ、及び（ｉｉ）Ｔ１に先行する一期間以上及び、それぞれが前記ひとつ以上の前記デジタル証明書を含む前記集合のいずれかひとつ以上と関連付けられた前記復号鍵データによって決まり、かつ、それらの復号鍵データから計算可能であることを特徴とする請求項２６に記載の方法。
【請求項２８】
Ｔ１に先行する前記期間のうちの前記ひとつ以上の期間は、Ｔ１に先行する各期間を含むことを特徴とする請求項２６に記載の方法。
【請求項２９】
Ｔ１が最初の期間以外の前記期間のうちのいずれかの一期間である時に(ｂ２)が真であることを特徴とする請求項２６に記載の方法。
【請求項３０】
請求項２６の方法を実行するコンピュータシステム。
【請求項３１】
請求項２６の方法を実行するように操作可能なコンピュータプログラムを含む、コンピュータ可読媒体。
【請求項３２】
請求項２７の方法を実行するように操作可能なコンピュータプログラムを、ネットワークによって送信することを含むネットワーク送信方法。
【請求項３３】
デジタル証明書の有効性、又は、無効性の証明の生成を可能とし、期間における前記証明を提供する、コンピュータに実装された方法であって、
それぞれのデジタル証明書は、暗号鍵がエンティティと関連付けられていることを証明し、
（ａ）前記デジタル証明書の全てを含む集合に対してコンプリメントカバーを定義する第１のデータを取得する工程を含み、
（ａ１）前記証明書のそれぞれ、及び、前記期間のそれぞれは、前記期間における前記証明書の有効性、又は、無効性を証明するための証明データを復号するための復号鍵と関連付けられており、
（ａ２）前記集合のそれぞれ及び、前記期間のそれぞれは、復号鍵データと関連付けられており、
（ａ３）前記デジタル証明書及び前記期間Ｔ１ごとに、前記関連付けられた復号鍵は、
（ｉ）前記証明書を含むひとつ以上の前記集合と、及び（ｉｉ）前記期間Ｔ１を含む、前記一期間以上の期間とに関連付けられた前記復号鍵データから計算可能であり、かつ前記期間Ｔ１が最初の期間でない場合は、Ｔ１よりも前の期間も含み、
前記方法は、
（ｂ）前記期間ごと、又は、最初の期間以外の前記期間ごとに、
（ｂ１）前記第１のコンプリメントカバーから無効なデジタル証明書の集合に対するコンプリメントカバーである第２のコンプリメントカバーを選択する工程と、
（ｂ２）前記第２のコンプリメントカバーの各集合に対して、前記集合及び前記期間に関連付けられている前記復号鍵データをネットワーク上で送信する工程とを更に含むことを特徴とする方法。
【請求項３４】
無効なデジタル証明書の前記集合は、最初の期間よりも後に始まる第１の間隔において失効したデジタル証明書の全ての集合であることを特徴とする請求項３３に記載の方法。
【請求項３５】
請求項３３の方法を実行するコンピュータシステム。
【請求項３６】
請求項３３の方法を実行するように操作可能なコンピュータプログラムを含むコンピュータ可読媒体。
【請求項３７】
請求項３３の方法を実行するように操作可能なコンピュータプログラムを、ネットワークにより送信することを含むネットワーク送信方法。
【請求項３８】
デジタル証明書の有効性、又は、無効性の証明の生成を可能とし、期間における前記証明を提供する、コンピュータに実装された方法であって、
それぞれのデジタル証明書は、暗号鍵がエンティティと関連付けられていることを証明し、
（ａ）第１のコンプリメントカバーから、前記期間ごとに、ゼロ以上の有効なデジタル証明書、又は、ゼロ以上の無効なデジタル証明書を選択し、かつ、前記期間ごとに、コンピュータシステムに対して前記期間と関連付けられた前記証明を決定するデータを提供するために、前記デジタル証明書の全てを含む集合に対する前記第１のコンプリメントカバーを定義する第１のデータを取得する工程と、
（ｂ）前記コンピュータシステムには、マルチキャスト伝送を受信できる第１の複数のコンピュータシステムを含むことを示すデータを受信する工程と、
（ｃ）それぞれが前記第１のコンプリメントカバーに属し、前記第１の複数のコンピュータシステムと関連付けられた前記証明書を含む集合の数を増大するように前記第１のコンプリメントカバーを再定義する工程とを含むことを特徴とする方法。
【請求項３９】
前記第１のコンプリメントカバーを、前記コンプリメントカバーにおける集合の総数を変えることなく再定義することを特徴とする請求項３８に記載の方法。
【請求項４０】
請求項３８の方法を実行するコンピュータシステム。
【請求項４１】
請求項３８の方法を実行するように操作可能なコンピュータプログラムを含む、コンピュータ可読媒体。
【請求項４２】
請求項３８に記載の方法を実行するように操作可能なコンピュータプログラムを、ネットワークにより送信することを含むネットワーク送信方法。
【手続補正書】
【提出日】平成20年3月12日(2008.3.12)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の期間における複数のデジタル証明書の有効性、及び／又は、無効性を検証するためのコンピュータデータを生成するコンピュータに実装された方法であって、
それぞれの前記デジタル証明書は、暗号鍵がエンティティに関連付けられていることを証明し、
前記デジタル証明書は、第１のデジタル証明書を含み、
前記方法は、
（ａ）前記デジタル証明書を1つ以上含む集合において、複数の集合を定義する第１のデータを取得する工程と、
（ｂ）前記デジタル証明書及び前記期間ごとに、前記期間における前記デジタル証明書の有効性、又は、無効性を証明するため、関連付けられた証明データを定義する第２のデータを取得する工程と、
（ｃ）前記デジタル証明書及び前記期間Ｔ１ごとに、前記デジタル証明書及び前記期間Ｔ１と関連付けられた前記証明データを暗号化するための暗号鍵を定義する第３のデータを取得する工程とを含み、
前記複数の集合は、第１の複数の集合を含み、
前記第１のデジタル証明書は、前記第１の複数の集合に含まれるそれぞれの前記集合に属しており、
前記第１の複数の集合の少なくとも1つの前記集合は、２つ以上の前記デジタル証明書を含み、
(ｃ１) 前記第３のデータは、前記デジタル証明書を含む前記集合ごとに、前記集合及び前記期間Ｔ１と関連付けられた復号鍵データを定義し、
前記復号鍵データは、前記期間Ｔ１及び、前記期間Ｔ１より以前の1つ以上の前記期間、及び前記集合と関連付けられた前記復号鍵データから、前記期間Ｔ１及び前記集合内の各前記デジタル証明書のための復号鍵を計算し、
前記デジタル証明書及び前記期間Ｔ１と関連付けられた前記復号鍵は、前記デジタル証明書を含む前記集合のうちの所定のいずれか一つ、及び前記期間Ｔ１を含み、かつ前記期間Ｔ１より以前の1つ以上の前記期間に関連付けられた前記復号鍵データから計算可能であり、
(ｄ)少なくとも一期間に対して、前記第1の複数の集合のうちの少なくとも2つの集合は、それぞれ異なる復号鍵データと関連付けられており、
前記第1の複数の集合のうちの少なくとも1つの集合において、前記第1のデジタル証明書及び少なくとも一つの他のデジタル証明書は、それぞれ異なる復号鍵と関連付けられていることを特徴とする方法。
【請求項２】
前記デジタル証明書及び前記期間ごとに、1つ以上の前記復号鍵で復号するために関連付けられた前記証明データを暗号化する工程をさらに含むことを特徴とする請求項1に記載の方法。
【請求項３】
少なくとも1つのデジタル証明書及び、少なくとも一期間に対して、関連付けられた前記証明データを復号するための関連付けられた前記復号鍵は、複数の期間と関連付けられた復号鍵データによって決まることを特徴とする請求項1に記載の方法。
【請求項４】
複数のデジタル証明書の有効性、又は、無効性の証明の生成を可能とし、複数の期間のうちの一期間である第１の期間における前記証明を提供するコンピュータに実装された方法であって、
それぞれの前記デジタル証明書は、暗号鍵がエンティティと関連付けられていることを証明し、前記デジタル証明書は、第1のデジタル証明書を含み、
前記方法は、
(ａ)前記デジタル証明書の全てを含む集合に対して、第1の複数の集合を含む第1のコンプリメントカバーを定義する第1のデータを取得する工程を含み、
前記第1のデジタル証明書は、前記第1の複数の集合における各集合に属し、
前記第1の複数の集合の少なくとも1つは、2つ以上のデジタル証明書を含み、
(ａ１)前記デジタル証明書のそれぞれ、及び、前記期間のそれぞれは、前記期間における前記デジタル証明書の有効性、又は、無効性を証明するための証明データを復号するための復号鍵と関連付けられており、
(ａ２)前記集合のそれぞれ、及び、前記期間のぞれぞれは、復号鍵データと関連付けられており、
(ａ３)前記証明書及び前記期間Ｔ１ごとに、前記関連付けられた復号鍵は、前記証明書を含む前記集合のうちの所与のいずれか1つ、及び、前記期間Ｔ１を含む前記期間の一期間以上と関連付けられた前記復号鍵データから計算可能であり、
(ａ４)前記期間のうちの少なくとも一期間に対して、前記第1の複数の集合うちの少なくとも2つの集合は、それぞれ異なる復号鍵データと関連付けられており、前記第1の複数のうちの少なくとも1つの集合において、前記第1のデジタル証明書及び、少なくとも1つの他のデジタル証明書は、相異なる復号鍵と関連付けられており、
前記方法は、
(ｂ)前記第1のコンプリメントカバーから、無効なデジタル証明書の集合に対するコンプリメントカバーである第2のコンプリメントカバーを選択する工程と、
(ｃ)前記第2のコンプリメントカバーにおける集合ごとに、前記集合と少なくとも前記第1の期間とに関連付けられた復号鍵データをネットワーク上で送信する工程とを含み、
前記無効なデジタル証明書の集合には、前記第1のデジタル証明書を含まず、前記第2のコンプリメントカバーは、前記第1の複数の集合のうち少なくとも1つの集合を含むことを特徴とする方法。
【請求項５】
前記第1の複数の集合のうちの少なくとも1つは、前記第2のコンプリメントカバーにあり、かつ、それぞれ異なる復号鍵と関連付けられている複数のデジタル証明書を含むことを特徴とする請求項４に記載の方法。
【請求項６】
無効なデジタル証明書の前記集合は、前記第1の期間より前の第1の間隔において失効した全ての前記デジタル証明書の集合であり、
前記集合には、前記第1の間隔の前に失効したデジタル証明書は含まれないことを特徴とする請求項４に記載の方法。
【請求項７】
各デジタル証明書は、前記デジタル証明書が有効である場合、前記デジタル証明書のための前記復号鍵を受け取るためのコンピュータシステムと関連付けられており、
前記第2のコンプリメントカバーにおける少なくとも1つの集合に対して、前記集合は、複数の前記コンピュータシステムと関連付けられた複数の前記デジタル証明書を含むが、前記集合のための前記復号鍵は、1つ以上だが全て未満の前記コンピュータシステムの前記複数の残りのコンピュータシステムに対して再送信するために、前記複数のコンピュータシステムの全て未満のものに対して送信されることを特徴とする請求項４に記載の方法。
【請求項８】
前記第1のコンプリメントカバーを定義する工程と、
前記コンピュータシステムは、物理的に互いに近い第1の複数のコンピュータシステムを含むことを示すデータを受け取る工程と、
(ｂ)の工程の前に、それぞれが第1のコンプリメントカバーに属し、前記コンピュータシステムの前記第1の複数のコンピュータシステムと関連付けられた前記デジタル証明書を含む集合Ｆの数が増大するように前記第1のコンプリメントカバーを再定義する工程とをさらに含むことを特徴とする請求項７に記載の方法。
【請求項９】
前記第1のコンプリメントカバーを、前記第1のコンプリメントカバーにおける前記集合の総数を変えることなく再定義することを特徴とする請求項８に記載の方法。
【請求項１０】
複数の期間のうちの一期間である第1の期間において、複数のデジタル証明書のうちの1つである第１のデジタル証明書の有効性、又は、無効性の証明を生成する、コンピュータに実装された方法であって、
それぞれのデジタル証明書は、暗号鍵がエンティティと関連付けられていることを証明し、
複数の集合が定義されており、
それぞれの集合は、前記デジタル証明書の1つ以上の集合であり、
前記複数の集合は、第１の複数の集合を含み、
前記第１のデジタル証明書は、前記第1の複数の各集合に属し、
前記第1の複数のうちの少なくとも1つの集合は、２つ以上のデジタル証明書を含み、
前記方法は、
(ａ)少なくとも前記第1のデジタル証明書及び前記期間のそれぞれに対して、前記期間における第1のデジタル証明書の有効性、又は、無効性を証明するための関連した証明データの暗号を取得する工程を含み、
(ａ１)前記証明書及び前記期間ごとに、前記証明書及び、前記期間と関連付けられた前記証明データを暗号化し、復号するための暗号鍵及び、対応する復号鍵が定義されており、
(ａ２)前記証明書及び前記期間Ｔ１ごとに、前記証明書を含む前記集合のそれぞれに対して、復号鍵データが、前記集合及び前記期間Ｔ１に関連付けられて定義され、前記証明書及び、前記期間Ｔ１と関連付けられた前記復号鍵は、前記証明書を含む前記集合のうちの所与のいずれかのもの、及び、前記期間Ｔ１を含む前記期間の一期間以上と関連付けられた前記復号鍵データから計算可能であり、
(ａ３)少なくとも前記第1の期間に対して、前記第1の複数の集合のうちの少なくとも２つの集合は、それぞれ異なる復号鍵データと関連付けられており、前記第1の集合のうちの少なくとも1つの集合において、前記第1のデジタル証明書と、少なくとも1つの他のデジタル証明書とが、相異なる復号鍵と関連付けられており、
前記方法は、
(ｂ)前記第１の複数の集合のうちの前記少なくとも2つの集合のうちの一方と関連付けられた前記復号鍵データをネットワーク上で受信する工程と、
(ｃ) 前記第1のデジタル証明書と、前記第1の期間とに関連付けられた前記復号鍵を計算するように、(ｂ)の操作で受信した前記復号鍵データを用いる工程と、
(ｄ)前記第1の期間における前記第1のデジタル証明書の有効性、又は、無効性の証明を提供するための前記証明データを復号する工程とをさらに含み、
前記復号する工程は、取得した前記復号鍵のもとで行われることを特徴とする方法。
【請求項１１】
（ｅ）前記第1の複数の集合のうちの一つ及び前記第１の期間に先行する第２の期間と関連付けられた復号鍵データを受信する工程を含み、
(ｆ)   (ｃ)の工程において計算した前記復号鍵は、(ｂ)の工程において受信した前記復号鍵データ及び、(ｅ)の工程において受信した前記復号鍵データから求めることを特徴とする請求項１０に記載の方法。
【請求項１２】
デジタル証明書の集合及び、期間に関連付けられた復号鍵データを提供する第１のコンピュータデータを備えるコンピュータ可読媒体であって、
それぞれのデジタル証明書は、暗号鍵がエンティティと関連付けられていることを証明し、
前記復号鍵データは、前記期間における前記デジタル証明書の有効性、又は、無効性を証明するために暗号化された証明データを復号するための復号鍵を提供するためのものであり、
少なくとも1つのデジタル証明書及び、少なくとも一期間Ｔ１に対して、少なくとも1つの関連付けられた復号鍵は、それぞれが前記デジタル証明書を含み、且つ、複数のデジタル証明書を含む集合のうちの所与のいずれかと、前記期間Ｔ１を含む前記期間の一期間以上と関連付けられた前記復号鍵データとから計算可能であり、
少なくとも前記一期間に対して、前記少なくとも1つのデジタル証明書を含む前記集合のうちの少なくとも２つは、それぞれ異なる復号鍵データと関連付けられており、
前記少なくとも1つのデジタル証明書を含む前記集合のうちの少なくとも1つにおいて、前記少なくとも1つのデジタル証明書及び、少なくとも1つの他のデジタル証明書は、それぞれ異なる復号鍵と関連付けられていることを特徴とするコンピュータ可読媒体。
【請求項１３】
複数の期間におけるデジタル証明書の有効性、又は、無効性を証明するための暗号化された証明データを含むコンピュータデータを含むコンピュータ可読媒体であって、
それぞれのデジタル証明証は、暗号鍵がエンティティと関連付けられていることを証明し、
前記暗号化された証明データは、復号鍵で復号するために暗号化されており、
少なくとも1つのデジタル証明書及び、少なくとも一期間Ｔ１に対して、少なくとも1つの関連付けられた復号鍵は、デジタル証明書の複数の集合のうちの所与のいずれかの集合と、前記期間Ｔ１を含む前記期間の一期間以上とに関連付けられた復号鍵データから計算可能であり、それぞれの集合には、前記少なくとも1つのデジタル証明書及び、少なくとも1つの他のデジタル証明書を含まれており、
前記集合のうちの少なくとも2つは、それぞれ異なる復号鍵データと関連付けられており、前記集合のうちの少なくとも1つにおいて、前記少なくとも1つのデジタル証明書及び、少なくとも1つの他のデジタル証明書は、それぞれ異なる復号鍵と関連付けられていることを特徴とするコンピュータ可読媒体。
【請求項１４】
前記期間のうちのいずれかの期間Ｔ１及び、前記複数の集合のうち、Ｓ１がＳ２の部分集合であるような任意の２つの集合Ｓ１及びＳ２に対して、Ｓ１及びＴ１と関連付けられた前記復号鍵データは、Ｓ２及びＴ１と関連付けられた前記復号鍵から計算可能であることを特徴とする請求項1に記載の方法。
【請求項１５】
前記デジタル証明書ごと及び前記期間ごとに、前記対応する復号鍵は、前記デジタル証明書を含む前記集合のうちのいずれか1つと関連付けられた復号鍵データから計算可能であることを特徴とする請求項1に記載の方法。
【請求項１６】
前記第1の複数の集合は、Ｓ１がＳ２の正式な部分集合である集合Ｓ１及び集合Ｓ２を含み、前記期間の少なくとも一期間Ｔ１に対して、Ｓ１及びＴ１と関連付けられた前記復号鍵データは、Ｓ２及びＴ１と関連付けられた前記復号鍵のビットサイズと同じビットサイズを有することを特徴とする請求項1に記載の方法。
【請求項１７】
前記第1の複数の集合は、Ｓ１がＳ２の正式な部分集合である集合Ｓ１及び集合Ｓ２を含み、前記期間の少なくとも一期間Ｔ１に対して、Ｓ１及びＴ１と関連付けられた前記復号鍵は、Ｓ２及びＴ１と関連付けられた前記復号鍵のビットサイズと同じビットサイズを有することを特徴とする請求項６に記載の方法。
【請求項１８】
前記期間ごとに、任意の2つの相違なる証明書が、相違なる証明データと関連付けられていることを特徴とする請求項１２に記載の方法。
【請求項１９】
全ての前記復号鍵及び前記復号鍵データは、同じビットサイズを有することを特徴とする請求項１２に記載の方法。
【請求項２０】
複数の期間におけるデジタル証明書の有効性、及び／又は、無効性を検証するためのコンピュータデータを生成するコンピュータに実装された方法であって、
それぞれの前記デジタル証明書は、暗号鍵がエンティティに関連付けられていることを証明し、
(ａ)前記期間ごとに、前記期間における1つ以上の前記デジタル証明書の有効性、及び／又は、無効性を証明するための関連付けられた証明データを定義するデータを取得する工程と、
(ｂ)前記期間ごとに、前記証拠データを暗号化及び復号化するための1つ以上の暗号鍵及び対応する1つ以上の復号鍵を定義する暗号／復号データを取得する工程とを含み、
それぞれの復号鍵は、前記期間のうちの一期間において前記証明データを復号するために、前記期間のうちの一期間と関連付けられており、
（ｂ１）前記期間ごとに、前記暗号／復号データは、前記期間と関連付けられた復号鍵データを定義し、前記復号鍵データは、前記期間において、前記期間と関連付けられた前記復号鍵を計算するためのものであり、
（ｂ２）少なくとも前記一期間Ｔ１に対して、前記復号鍵は、
前記期間Ｔ１と関連付けられているが、(ｉ)前記期間Ｔ１と関連付けられた前記復号鍵データと、(ｉｉ)一期間以上のＴ１にを先行する前記期間と関連付けられた復号鍵データとによって決まる復号鍵、またそれらの前記復号鍵データから計算可能である復号鍵を含むことを特徴とする方法。
【請求項２１】
ぞれぞれの集合が1つ以上の前記デジタル証明書のうちの1つの集合である、複数の集合を定義するデータを取得する工程をさらに含み、
1つ以上の前記集合は、それぞれ、２つ以上の前記デジタル証明書を含み、
前記期間ごとに、前記関連付けられた復号鍵データは、前記集合のそれぞれと関連付けられた個別の復号鍵データを含み、
少なくとも前記期間Ｔ１に対して、（ｂ２）における前記復号鍵は、1つ以上の前記デジタル証明書と関連付けられた証明を復号するためのものであり、（ｂ２）における前記復号鍵は、（ｉ）前記期間Ｔ１及び、1つ以上の前記証明書を含む前記集合のうちの所与のいずれかの集合と関連付けられた前記復号鍵データ、及び（ｉｉ）Ｔ１に先行する一期間以上及び、それぞれが前記1つ以上の前記デジタル証明書を含む前記集合のいずれか1つ以上と関連付けられた前記復号鍵データによって決まり、かつ、それらの復号鍵データから計算可能であることを特徴とする請求項２０に記載の方法。
【請求項２２】
Ｔ１に先行する前記期間のうちの前記1つ以上の期間は、Ｔ１に先行する各期間を含むことを特徴とする請求項２０に記載の方法。
【請求項２３】
Ｔ１が最初の期間以外の前記期間のうちのいずれかの一期間である時に(ｂ２)が真であることを特徴とする請求項２０に記載の方法。
【請求項２４】
デジタル証明書の有効性、又は、無効性の証明の生成を可能とし、期間における前記証明を提供する、コンピュータに実装された方法であって、
それぞれのデジタル証明書は、暗号鍵がエンティティと関連付けられていることを証明し、
（ａ）前記デジタル証明書の全てを含む集合に対してコンプリメントカバーを定義する第１のデータを取得する工程を含み、
（ａ１）前記証明書のそれぞれ、及び、前記期間のそれぞれは、前記期間における前記証明書の有効性、又は、無効性を証明するための証明データを復号するための復号鍵と関連付けられており、
（ａ２）前記集合のそれぞれ及び、前記期間のそれぞれは、復号鍵データと関連付けられており、
（ａ３）前記デジタル証明書及び前記期間Ｔ１ごとに、前記関連付けられた復号鍵は、
（ｉ）前記証明書を含む1つ以上の前記集合と、及び（ｉｉ）前記期間Ｔ１を含む、前記一期間以上の期間とに関連付けられた前記復号鍵データから計算可能であり、かつ前記期間Ｔ１が最初の期間でない場合は、Ｔ１よりも前の期間も含み、
前記方法は、
（ｂ）前記期間ごと、又は、最初の期間以外の前記期間ごとに、
（ｂ１）前記第１のコンプリメントカバーから無効なデジタル証明書の集合に対するコンプリメントカバーである第２のコンプリメントカバーを選択する工程と、
（ｂ２）前記第２のコンプリメントカバーの各集合に対して、前記集合及び前記期間に関連付けられている前記復号鍵データをネットワーク上で送信する工程とを更に含むことを特徴とする方法。
【請求項２５】
無効なデジタル証明書の前記集合は、最初の期間よりも後に始まる第１の間隔において失効したデジタル証明書の全ての集合であることを特徴とする請求項２４に記載の方法。
【請求項２６】
デジタル証明書の有効性、又は、無効性の証明の生成を可能とし、期間における前記証明を提供する、コンピュータに実装された方法であって、
それぞれのデジタル証明書は、暗号鍵がエンティティと関連付けられていることを証明し、
（ａ）第１のコンプリメントカバーから、前記期間ごとに、ゼロ以上の有効なデジタル証明書、又は、ゼロ以上の無効なデジタル証明書を選択し、かつ、前記期間ごとに、コンピュータシステムに対して前記期間と関連付けられた前記証明を決定するデータを提供するために、前記デジタル証明書の全てを含む集合に対する前記第１のコンプリメントカバーを定義する第１のデータを取得する工程と、
（ｂ）前記コンピュータシステムには、マルチキャスト伝送を受信できる第１の複数のコンピュータシステムを含むことを示すデータを受信する工程と、
（ｃ）それぞれが前記第１のコンプリメントカバーに属し、前記第１の複数のコンピュータシステムと関連付けられた前記証明書を含む集合の数を増大するように前記第１のコンプリメントカバーを再定義する工程とを含むことを特徴とする方法。
【請求項２７】
前記第１のコンプリメントカバーを、前記コンプリメントカバーにおける集合の総数を変えることなく再定義することを特徴とする請求項２６に記載の方法。
【請求項２８】
複数のデジタル証明書の集合、及び複数の期間に関連付けられた復号鍵データを提供する第1のコンピュータデータを、ネットワークにより送信することを含むネットワーク送信方法であり、
それぞれのデジタル証明書は、暗号鍵がエンティティと関連付けられていることを証明し、
前記暗号鍵データは前記期間における前記デジタル証明書の有効性、または無効性を証明するために暗号化された証明データを復号するためのものであり、
少なくとも1つのデジタル証明書及び、少なくとも一期間Ｔ１に対して、少なくとも1つの関連付けられた復号鍵は、デジタル証明書の複数の集合のうちの所与のいずれかの集合と、前記期間Ｔ１を含む前記期間の一期間以上とに関連付けられた前記復号鍵データから計算可能であり、
少なくとも前記一期間に対して、前記少なくとも1つのデジタル証明書を含む前記集合のうちの少なくとも２つは、それぞれ異なる復号鍵データと関連付けられており、
前記少なくとも1つのデジタル証明書を含む前記集合のうちの少なくとも1つにおいて、前記少なくとも1つのデジタル証明書及び、少なくとも1つの他のデジタル証明書は、それぞれ異なる復号鍵と関連付けられていることを特徴とするネットワーク送信方法。
【請求項２９】
複数の期間におけるデジタル証明書の有効性、又は、無効性を証明するための暗号化された証明データを含むコンピュータデータを、ネットワークにより送信することを含むネットワーク送信方法であり、
それぞれのデジタル証明書は、暗号鍵がエンティティと関連付けられていることを証明し、
前記暗号化された証明データは復号鍵で復号するために暗号化されており、
少なくとも1つのデジタル証明書及び、少なくとも一期間Ｔ１に対して、少なくとも1つの関連付けられた復号鍵は、デジタル証明書の複数の集合のうちの所与のいずれかの集合と。前記期間Ｔ１を含む前記期間の一期間以上とに関連付けられた復号鍵データから計算可能であり、それぞれの集合には、前記少なくとも1つのデジタル証明書及び、前記集合のうちの少なくとも２つは、それぞれ異なる復号鍵データと関連付けられており、前記集合のうちの少なくとも1つにおいて、前記少なくとも1つのデジタル証明書及び、少なくとも1つの他のデジタル証明者は、それぞれ異なる復号鍵と関連付けられていることを特徴とするネットワーク送信方法。
【請求項３０】
請求項１、４、１０、２０、２４、又は２６のいずれか１項に記載の方法を実行するコンピュータシステム。
【請求項３１】
請求項１、４、１０、２０、２４、又は２６のいずれか１項に記載の方法を実行するように操作可能な1つ以上のコンピュータ命令を備えるコンピュータ可読媒体。
【請求項３２】
請求項１、４、１０、２０、２４、又は２６のいずれか１項に記載の方法を実行するように操作可能なコンピュータプログラムを、ネットワークによって送信することを含むネットワーク送信方法。
【国際調査報告】
2008524931.tif 000026