(57)【要約】【課題】仮署名スキームの一部を実現する方法及び装置が開示されている。【解決手段】証明書有効性検証者（１１０）によって、スーパーターゲットを計算する方法を用いて、デジタル証明書の相異なるターゲット（ｃ０，Ｎ１）を「スーパーターゲット」にマップする。証明書には、ターゲットの代わりに、スーパーターゲットが含まれる。また、複数のターゲットを有する証明書は、証明書認証局（ＣＡ１２０）による編集可能な署名で署名することができる。証明書の所有者が、証明書を有効性証明と共に検証者に提供すると、所有者は、証明書を編集して不要なターゲットを削除する。マルチキャストグループ（２０１０）が集合に対応するように形成されている場合、マルチキャスト伝送を介して証明書の集合（Ｆ）ごとに単一の有効性証明（ｃｉ（Ｆ））を証明書の所有者に提供してもよい。検証者（１１０）は、集合ごとの有効性証明をキャッシュするかを決定し、キャッシュした証明を他の利用者に提供してもよい。キャッシングの決定は、集合Ｆのキャッシングの優先順位による。優先順位は、証明書の数、集合Ｆにおける証明書の残りの有効期限の和及び他の要素に基づくものであってよい。設定フェーズにおいて、ＣＡは、証明書の最大有効期限よりも長い検証証明データ構造を生成する。そのため、設定フェーズ後に、新規証明書を既存のデータ構造に追加することができる。配布された証明書の認証局には、ＣＡ及び多くのＳｕｂ-ＣＡ（２６１０）が含まれる。Ｓｕｂ-ＣＡは、秘密の証明書検証データを有するが、異なるデータが、証明書ごとに異なるＳｕｂＣＡに提供される。Ｓｕｂ-ＣＡが危殆化している場合、Ｓｕｂ-ＣＡの有効性証明は、ＣＡによって保留され、検証者に、このＳｕｂ−ＣＡからのデータを使用しないように警告する。また、秘密データは、Ｓｕｂ-ＣＡに配布される際に暗号化される。時間「区分」ごとの復号鍵（ＤＫ．ｊ．ｋ）が、区分の開始時、又は、その少し前に、ＣＡごとに配布される。敵は、その後の区分に対する復号鍵を取得することができないので、危殆化したＳｕｂ-ＣＡは、区分の終了時に再開される。【選択図】図８
2008512066.tif 000002
【特許請求の範囲】
【請求項１】
第１のデジタル証明書を含む１つ以上の暗号化されたデジタル証明書の有効性及び／又は無効性を検証するためにデータキャリア上で具現化されたコンピュータデータであって、
各デジタル証明書は、暗号鍵が１つのエンティティに関連付けられていることを証明し、
前記コンピュータデータは、少なくとも前記第１のデジタル証明書の有効性又は無効性を検証者コンピュータシステムに対して証明し、
前記コンピュータデータは、
（ａ）第１の複数の集合を含む複数の集合を定義する第１のデータと、
（ｂ）少なくとも前記第１の複数の集合ごとに、複数の期間の各々に対する期間データを定義し、前記集合に対する第１のターゲットを定義する第２のデータと、
（ｃ）前記第１の複数の集合の前記第１のターゲットから計算可能な第２のターゲットを定義する第３のデータとを含み、
前記第１のデジタル証明書は、前記第１の複数の集合の各々に属し、
前記第１のターゲットは、前記期間の各々に関連する前記集合における証明書の有効性及び／又は無効性を検証するために、前記期間のうちの１つに対する前記期間データから前記検証者コンピュータシステムにより計算可能であることを特徴とするコンピュータデータ。
【請求項２】
データキャリアにおいて具現化され、コンピュータシステムに請求項１に記載のコンピュータデータを生成させるように操作可能な１つ以上のコンピュータ命令を含むことを特徴とするコンピュータプログラム。
【請求項３】
第１のデジタル証明書を含む１つ以上の暗号化されたデジタル証明書の有効性及び／又は無効性の証明を提供する第１のコンピュータシステムであって、
各デジタル証明書は、暗号鍵が１つのエンティティに関連付けられていることを証明し、
前記コンピュータシステムは、コンピュータストレージを含み、
前記コンピュータシステムは、
（ａ）前記第１のデジタル証明書を第１の複数の集合に関連付ける第１のデータと、
（ｂ）少なくとも前記第１の複数の集合ごとに、複数の期間のうちの１つに対する期間データについてのネットワーク受信のための１つ以上のコンピュータ命令と、
（ｃ）前記第１の複数の集合の第１のターゲットから計算可能な第２のターゲットを定義するデータとを含み、
前記第１のデジタル証明書は、前記第１の複数の集合の各々に属し、
前記集合の各々は、前記第１のターゲットに関連付けられており、
前記期間の各々に関連した前記集合における証明書の有効性及び／又は無効性を検証するために、前記第１のターゲットは、検証者コンピュータシステムによって前記期間の１つに対する前記期間データから計算可能であることを特徴とする第１のコンピュータシステム。
【請求項４】
第１のデジタル証明書を含む１つ以上の暗号化されたデジタル証明書の有効性及び／又は無効性を証明するコンピュータに実装された方法であって、
各デジタル証明書は、暗号鍵が１つのエンティティに関連付けられていることを証明し、
前記方法は、
（ａ）ネットワーク上で
（ａ１）前記第１のデジタル証明書を第１の複数の集合に関連付ける第１のデータと、
（ａ２）前記第１の複数の集合ごとに、第１のターゲットを定義し、前記第１の複数の集合の前記第１のターゲットから計算可能な第２のターゲットを定義するデータとを受信する工程と、
（ｂ）少なくとも前記第１の複数の集合ごとに、複数の期間に対する期間データをネットワーク上で定期的に受信する工程と、
（ｃ）各期間において、要求があれば、少なくとも前記第１のデジタル証明書の有効性及び／又は無効性の証明を提供する工程とを有し、
前記第１のデジタル証明書は、前記第１の複数の集合の各々に属し、
前記期間の各々に関連する前記集合における証明書の有効性及び／又は無効性を検証するために、前記第１のターゲットは、検証者コンピュータシステムによって前記期間のうちの１つに対する前記期間データから計算可能であり、
前記証明は、前記期間に対する前記期間データ、及び、前記証明において提供された前記期間データによって定義される前記第１のターゲットから前記第２のターゲットを計算するためのデータを含むことを特徴とする方法。
【請求項５】
暗号鍵が１つのエンティティに関連付けられていることを証明する第１のデジタル証明書の有効性又は無効性を検証するためのコンピュータに実装された方法であって、
（ａ）ネットワーク上で、
（ａ１）第１のターゲットを計算するための期間に対する期間データと、
（ａ２）前記第１のターゲットから第２のターゲットを計算するための第２のターゲット計算データとを受信する工程と、
（ｂ）前記期間データから、（ａ１）の前記第１のターゲットを計算する工程と、
（ｃ）（ｂ）で計算した前記第１のターゲット及び前記ターゲット計算データから、前記第２のターゲットを計算する工程と、
（ｄ）前記第２のターゲットと前記第１のデジタル証明書とを整合して、前記第１のデジタル証明書の有効性又は無効性を決定する工程とを有し、
前記期間は、それぞれが期間データと関連付けられている複数の期間のうちの１つであり、
前記第１のターゲットは、前記期間の１つと関連付けられた前記期間データから計算可能であり、
前記第２のターゲットは、それぞれが前記第１のデジタル証明書を含む集合と関連付けられている複数の第１のターゲットの関数であることを特徴とする方法。
【請求項６】
暗号鍵が１つのエンティティに関連付けられていることを証明する第１のデジタル証明書に対する有効性又は無効性の証明を含むコンピュータデータを含むデータキャリアであって、
（ａ１）第１のターゲットを計算するための期間に対する期間データと、
（ａ２）前記第１のターゲットから第２のターゲットを計算するための第２のターゲット計算データとを含み、
前記期間は、それぞれが期間データに関連付けられた複数の期間のうちの１つであり、
前記第１のターゲットは、前記期間のいずれかに関連付けられた前記期間データから計算可能であり、
前記第２のターゲットは、それぞれが前記第１のデジタル証明書を含む集合と関連付けられた複数の第１のターゲットの関数であることを特徴とするデータキャリア。
【請求項７】
データキャリアにおいて具現化され、暗号鍵が１つのエンティティに関連付けられていることを証明する第１のデジタル証明書を含むコンピュータデータであって、
前記第１のデジタル証明書は、編集可能なデジタル署名を含むことを特徴とするコンピュータデータ。
【請求項８】
請求項７に記載のコンピュータデータを生成するように構成されていることを特徴とするコンピュータシステム。
【請求項９】
データキャリアにおいて具現化され、コンピュータシステムに請求項７に記載のコンピュータデータを生成させるように操作可能な１つ以上のコンピュータ命令を含むことを特徴とするコンピュータデータ。
【請求項１０】
請求項７に記載のコンピュータデータを処理するコンピュータに実装された方法であって、
前記第１のデジタル証明書の一部分を削除して、前記削除された一部分を用いることなく、前記署名を検証するための署名証明を有する編集されたデジタル証明書を取得する工程と、
前記編集されたデジタル証明書をネットワーク上で送信する工程とを有することを特徴とする方法。
【請求項１１】
暗号鍵が１つのエンティティに関連付けられていることを証明する第１のデジタル証明書の有効性又は無効性を検証するコンピュータに実装された方法であって、
前記第１のデジタル証明書は、編集可能な署名を含み、
前記方法は、
前記デジタル署名の署名証明を有する編集されたデジタル証明書を受信する工程と、
前記第１のデジタル証明書を用いることなく、前記編集されたデジタル証明書及び前記署名証明を用いて前記署名を検証する工程と、
ターゲット値を計算し、前記ターゲット値と前記編集されたデジタル証明書におけるターゲットとを整合する工程とを有することを特徴とする方法。
【請求項１２】
複数の集合｛Ｆ｝のシステムを生成するためにコンピュータに実装された方法であって、
各集合Ｆは、１つ以上のデジタル証明書ＤＣ及び／又はデジタル証明書に割り当て可能なデジタル証明書スロットであり、
各デジタル証明書ＤＣ＝ＤＣ（ＣＫ，ＥＮ）は、対応する暗号鍵ＣＫが、コンピュータシステムに関連付けられたエンティティＥＮに関連付けられていることを証明し、
前記方法は、
（１）マルチキャスティンググループ用の１つ又は複数の表示を取得する工程と、
（２）前記表示のうちの少なくとも１つに関して、少なくとも２つのデジタル証明書ＤＣ（ＣＫ，ＥＮ）を含む集合Ｆ∈｛Ｆ｝を生成する工程と、
（３）前記集合Ｆに対する有効性証明を定義するデータを生成する工程とを有し、
前記表示の各々は、複数のエンティティを示し、
前記複数のエンティティが関連付けられているコンピュータシステムは、単一のマルチキャスティンググループに属しており、又は、単一のマルチキャスティンググループに属するようになっており、
前記デジタル証明書ＤＣ（ＣＫ，ＥＮ）が関連付けられているエンティティＥＮは、前記表示によって表示されることを特徴とする方法。
【請求項１３】
失効したデジタル証明書の集合Ｒに対するコンプリメントカバーＣＣＲを選択するコンピュータに実装された方法であって、
各デジタル証明書は、暗号鍵が、コンピュータシステムに関連付けられているエンティティに関連付けられていることを証明し、
前記方法は、
マルチキャスティンググループ用の１つ以上の表示を取得する工程と、
集合Ｆの優先順位を考慮して、前記コンプリメントカバーＣＣＲに対する有効なデジタル証明書の集合Ｆを選択する工程とを有し、
前記表示の各々は、複数のエンティティを示し、
前記複数のエンティティが関連付けられているコンピュータシステムは、単一のマルチキャスティンググループに属しており、又は、単一のマルチキャスティンググループに属するようになっており、
前記集合Ｆが、２つ以上のデジタル証明書を含む場合、該集合Ｆの優先順位は、増加し、
前記デジタル証明書のエンティティは、前記表示のいずれか１つによって単一のマルチキャスティンググループに対して表示されることを特徴とする方法。
【請求項１４】
ネットワークにおけるコンピュータシステムのマルチキャスティンググループを形成する方法であって、
各コンピュータシステムは、暗号鍵が、コンピュータシステムに関連付けられたエンティに関連付けられていることを証明するデジタル証明書の少なくとも１つと関連付けられており、
複数の前記デジタル証明書の集合ごとに、有効性証明又は無効性証明が定義されており、
前記集合の各々は、複数のデジタル証明書を含み、
前記集合の各々は、優先順位と関連付けられており、
前記方法は、
（１）前記優先順位に応じて、１つ以上の集合を選択する工程と、
（２）集合ごとに、
（２ａ）前記集合のデジタル証明書と関連付けられているコンピュータシステムを含むマルチキャスティンググループを形成する工程、及び／又は、（ｉｉ）前記デジタル証明書の少なくとも１つと関連付けられているコンピュータシステムに対して、前記集合に対応するマルチキャスティンググループに参加する前記コンピュータシステムを形成する工程とを有することを特徴とする方法。
【請求項１５】
複数のデジタル証明書の有効性及び／又は無効性を証明する方法であって、
前記複数のデジタル証明書の各々は、暗号鍵が１つのエンティティに関連付けられていることを証明し、
各デジタル証明書は、コンピュータシステムに関連付けられており、
前記方法は、
（１）各集合における全ての証明書が同じ有効状況を有するように、１つ又は複数の集合を決定する工程と、
（２）第１の集合における証明書に関連付けられている複数のコンピュータシステムを含むネットワークマルチキャスティンググループを検索する工程と、
（３）（２）において前記ネットワークマルチキャスティンググループが見つかった場合、前記第１の集合に対する前記有効状況を、マルチキャスト伝送を介して前記マルチキャスティンググループに送信する工程とを有し、
各集合は、複数の証明書を含む少なくとも前記第１の集合を含む１つ以上の証明書の有効状況証明と関連付けられていることを特徴とする方法。
【請求項１６】
暗号鍵が１つのエンティティに関連付けられていることを証明するデジタル証明書の有効性又は無効性を証明する有効状況証明を処理する方法であって、
ネットワーク上のコンピュータシステムで、１つ以上のデジタル証明書の有効状況証明を受け取る工程と、
前記コンピュータシステムが、前記コンピュータシステムが前記有効状況証明の将来のネットワーク送信を実行することができるように、前記有効状況証明をキャッシュするかどうかを決定するキャッシング決定を行う工程と、
前記キャッシング決定に従って、前記有効状況証明のキャッシングを行う又は行わない工程とを有し、
前記キャッシング決定は、前記１つ以上のデジタル証明書の前記優先順位に基づいていることを特徴とする方法。
【請求項１７】
連続する期間におけるデジタル証明書の有効性証明又は無効性証明を生成するためのコンピュータデータを含むデータキャリアであって、
各デジタル証明書は、暗号鍵が１つのエンティティに関連付けられていることを証明し、
相異なる証明は、相異なる期間に対して生成されるように操作可能であり、
前記コンピュータデータは、第１の所定数の前記期間を含む第１の時間間隔に対する証明のための第１のコンピュータデータを含み、
前記第１の時間間隔は、前記第１のコンピュータデータと共に使用される証明書に対する最小の有効期限より長いことを特徴とするデータキャリア。
【請求項１８】
コンピュータシステムを用いて、請求項１７に記載のコンピュータデータを生成することを特徴とするコンピュータに実装された方法。
【請求項１９】
複数のデジタル証明書の各々の有効性又は無効性を証明するためのコンピュータデータを含むデータキャリアであって、
各デジタル証明書は、暗号鍵が１つのエンティティに関連付けられていることを証明し、
前記コンピュータデータは、第１のデータ及び第２のデータを定義し、
前記第１のデータは、デジタル証明書ごとに、第１のコンピュータシステムによって、１つ以上の第１の証明を生成するためのものであり、
前記第１の証明の各々は、前記デジタル証明書の有効性及び無効性の証明であり、
前記第２のデータは、デジタル証明書ごとに、第２のコンピュータシステムによって、１つ以上の第２の証明を生成するためのものであり、
前記第２の証明の各々は、前記デジタル証明書の有効性又は無効性の証明であり、
前記第１のデータは、前記第２のデータと異なり、
少なくとも１つのデジタル証明書に対する少なくとも１つの第１の証明は、各第２の証明とは異なり、
少なくとも１つの第２の証明は、各第１の証明とは異なることを特徴とするデータキャリア。
【請求項２０】
請求項１９に記載のコンピュータデータをコンピュータシステムによって生成することを特徴とするコンピュータに実装された方法。
【請求項２１】
コンピュータデータを含むデータキャリアであって、
暗号鍵が１つのエンティティに関連付けられていることを証明する複数のデジタル証明書の各々の有効性又は無効性を証明する第１のコンピュータデータと、
前記第１のコンピュータデータの第１の部分を復号するための第１の復号鍵と、
前記第１の復号鍵とは異なる前記第１のコンピュータデータの第２の部分を復号するための第２の復号鍵とを含む事を特徴とするデータキャリア。
【請求項２２】
請求項２１に記載のコンピュータデータをコンピュータシステムによって生成することを特徴とするコンピュータに実装された方法。
【請求項２３】
複数のデジタル証明書の各々の有効性又は無効性を証明するためのコンピュータデータを含むデータキャリアであって、
各デジタル証明書は、暗号鍵が１つのエンティティに関連付けられていることを証明し、
前記コンピュータデータは、前記デジタル証明書の各々の有効性又は無効性を証明するための第１の暗号データを含むことを特徴とするデータキャリア。
【請求項２４】
前記第１の暗号データは、
第１の期間における前記デジタル証明書の有効性又は無効性を証明する第１の復号鍵で復号するために暗号化された第１の部分と、
第２の期間における前記デジタル証明書の有効性又は無効性を証明する前記第１の復号鍵とは異なる第２の復号鍵で復号するために暗号化された第２の部分とを含むことを特徴とする請求項２３に記載のデータキャリア。
【請求項２５】
コンピュータシステムが、請求項２４に記載のコンピュータデータをネットワーク上で受け取る工程と、
前記コンピュータシステムが、第１の期間中又は該第１の期間の前に、前記第１の復号鍵を受け取る工程と、
前記コンピュータシステムが、前記第１の期間における有効性又は無効性を証明するために、前記第１の復号鍵を用いて前記第１の部分を復号する工程と、
前記コンピュータシステムが、第２の期間中又は該第２の期間の前、及び、前記第１の期間の終了時又は該第１の期間の終了後に、前記第２の復号鍵を受け取る工程と、
前記コンピュータシステムが、前記第２の期間における有効性又は無効性を証明するために、前記第２の復号鍵を用いて前記第２の部分を復号する工程とを有することを特徴とするコンピュータに実装された方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、２００４年８月３１日出願の米国仮特許出願第６０/６０６,２１３号に基づく優先権を主張し、その全内容を参照により本明細書に組み入れるものとする。
【背景技術】
【０００２】
本発明は、公開鍵暗号方式に関し、特に、デジタル証明書の失効に関する。
【０００３】
デジタル証明書１０４（図１）は、公開鍵暗号基盤（ＰＫＩ）で利用されており、ネットワーク化したコンピュータ環境において、公開鍵の安全な利用と管理を容易にしている。ユーザＵ１、Ｕ２…は、それぞれのコンピュータシステム１１０.１、１１０.２…を利用して、それぞれの鍵ペア（ＰＫ、ＳＫ）を生成する。ここで、ＰＫは、公開鍵であり、ＳＫは、秘密鍵である。図１は、ユーザＵ１に対する鍵ペア（ＰＫＵ１、ＳＫＵ１）を示す。ユーザは、自分の公開鍵ＰＫを、ネットワーク上で、認証局（ＣＡ）１２０に登録する。或いは、ＣＡ１２０が、公開鍵を生成してユーザに送信することもできる。ＣＡ１２０は、安全で信頼のおけるコンピュータシステムである。ＣＡ１２０は、各公開鍵ＰＫに対して、デジタル証明書１０４を生成する。証明書１０４は、公開鍵ＰＫ及びユーザ名を含むが、ユーザのメールアドレスや、住所や、証明書のシリアル番号ＳＮ（証明書の管理を容易にするために、ＣＡによって生成されたもの）や、証明書発行日Ｄ１や、証明書有効期限Ｄ２や、公開鍵及び秘密鍵に使用するアルゴリズムの識別情報や、ＣＡ１２０の識別情報や、他のデータ等を含めても良い。上述したデータを、１０４Ｄに示す。証明書１０４は、データ１０４Ｄに対するＣＡの署名１０４−ＳｉｇＣＡも含む。その署名は、ＣＡの秘密鍵ＳＫＣＡを使って生成し、ＣＡ１２０は、証明書１０４をユーザ（鍵の所有者）のコンピュータシステム１１０に送信する。所有者及びＣＡ１２０は、他者に証明書を配布し、ユーザの公開鍵ＰＫを知らせることができる。そのような他者は、証明書の公開鍵ＰＫが、名前及びメールアドレスが証明書に記載されている人物に実際に属していることを確認するために、ＣＡの署名１０４−ＳｉｇＣＡを、ＣＡの公開鍵ＰＫＣＡで検証することができる。
【０００４】
以下の非特許文献の全ては、参照により、本明細書に引用したものとする。
【非特許文献１】Ｗ．Ａｉｅｌｌｏ、Ｓ．Ｌｏｄｈａ及びＲ．  Ｏｓｔｒｏｖｓｋｙ）著、「Ｆａｓｔ  ｄｉｇｉｔａｌ  ｉｄｅｎｔｉｔｙ  ｒｅｖｏｃａｔｉｏｎ」、議事録、ＣＲＹＰＴＯ９８、１９９８年
【非特許文献２】Ｇ．  Ａｔｅｎｉｅｓｅ）、Ｊ．Ｃａｍｅｎｉｓｃｈ、Ｍ．Ｊｏｙｅ及びＧ．Ｔｓｕｄｉｋ著、「Ａ  Ｐｒａｃｔｉｃａｌ  ａｎｄ  Ｐｒｏｖａｂｌｙ  Ｓｅｃｕｒｅ  Ｃｏａｌｉｔｉｏｎ−Ｒｅｓｉｓｔａｎｔ  Ｇｒｏｕｐ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅ」、議事録、ＣＲＹＰＴＯ２０００、２０００年
【非特許文献３】Ｍ．Ｂｅｌｌａｒｅ及びＰ．Ｒｏｇａｗａｙ著、「Ｒａｎｄｏｍ  ｏｒａｃｌｅｓ  ａｒｅ  ｐｒａｃｔｉｃａｌ：  Ａ  ｐａｒａｄｉｇｍ  ｆｏｒ  ｄｅｓｉｇｎｉｎｇ  ｅｆｆｉｃｉｅｎｔ  ｐｒｏｔｏｃｏｌｓ」、議事録、Ｆｉｒｓｔ  Ａｎｎｕａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｅｃｕｒｉｔ）、ＡＣＭ、１９９３年
【非特許文献４】Ｄ．Ｂｏｎｅｈ、Ｂ．Ｌｙｎｎ及びＨ．Ｓｈａｃｈａｍ、「Ｓｈｏｒｔ  ｓｉｇｎａｔｕｒｅｓ  ｆｒｏｍ  ｔｈｅ  Ｗｅｉｌ  ｐａｉｒｉｎｇ」、議事録、Ａｓｉａｃｒｙｐｔ’０１、２００１年
【非特許文献５】Ｆ．Ｅｌｗａｉｌｌｙ及びＺ．Ｒａｍｚａｎ著、「ＱｕａｓｉＭｏｄｏ：  Ｍｏｒｅ  Ｅｆｆｉｃｉｅｎｔ  Ｈａｓｈ  Ｔｒｅｅ−Ｂａｓｅｄ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｒｅｖｏｃａｔｉｏｎ」、原稿、２００３年
【非特許文献６】Ｉ．Ｇａｓｓｋｏ、Ｐ．Ｓ．Ｇｅｍｍｅｌｌ及びＰ．ＭａｃＫｅｎｚｉｅ著、「Ｅｆｆｉｃｉｅｎｔ  ａｎｄ  ｆｒｅｓｈ  ｃｅｒｔｉｆｉｃａｔｉｏｎ」、議事録、ＰＫＣ２０００、２０００年
【非特許文献７】Ｓ．Ｇｏｌｄｗａｓｓｅｒ）、Ｓ．Ｍｉｃａｌｉ及びＲ．Ｌ．Ｒｉｖｅｓｔ著、「Ａ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅ  Ｓｅｃｕｒｅ  Ａｇａｉｎｓｔ  Ａｄａｐｔｉｖｅ  Ｃｈｏｓｅｎ−Ｍｅｓｓａｇｅ  Ａｔｔａｃｋｓ」、ＳＩＡＭ、Ｊｏｕｒｎａｌ  ｏｎ  Ｃｏｍｐｕｔｉｎｇ、１７（２）巻、２８１-３０８ページ、１９８８年
【非特許文献８】Ｙ-Ｃ．Ｈｕ、Ａ．Ｐｅｒｒｉｇ及びＤ．Ｊｏｈｎｓｏｎ著、「Ｅｆｆｉｃｉｅｎｔ  ｓｅｃｕｒｉｔｙ  ｍｅｃｈａｎｉｓｍｓ  ｆｏｒ  ｒｏｕｔｉｎｇ  ｐｒｏｔｏｃｏｌｓ」、議事録、ｔｈｅ  １０ｔｈ  Ａｎｎｕａｌ  Ｎｅｔｗｏｒｋ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍ  Ｓｅｃｕｒｉｔｙ  Ｓｙｍｐｏｓｉｕｍ  （ＮＤＳＳ）、２００３年
【非特許文献９】Ｍ．Ｊａｋｏｂｓｓｏｎ、Ｊ-Ｐ．Ｈｕｂａｕｘ及びＬ．Ｂｕｔｔｙａｎ著、「Ａ  ｍｉｃｒｏｐａｙｍｅｎｔ  ｓｃｈｅｍｅ  ｅｎｃｏｕｒａｇｉｎｇ  ｃｏｌｌａｂｏｒａｔｉｏｎ  ｉｎ  ｍｕｌｔｉ−ｈｏｐ  ｃｅｌｌｕｌａｒ  ｎｅｔｗｏｒｋｓ」、議事録、ｔｈｅ  ７ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｆｉｎａｎｃｉａｌ  Ｃｒｙｐｔｏｇｒａｐｈｙ、２００３年
【非特許文献１０】Ｍ．Ｊａｋｏｂｓｓｏｎ、Ｔ．Ｌｅｉｇｈｔｏｎ、Ｓ．Ｍｉｃａｌｉ及びＭ．Ｓｚｙｄｌｏ著、「Ｆｒａｃｔａｌ  ｍｅｒｋｌｅ  ｔｒｅｅ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎ  ａｎｄ  ｔｒａｖｅｒｓａｌ」、議事録、(ｔｈｅ  Ｃｒｙｐｔｏｇｒａｐｈｅｒ’ｓ  Ｔｒａｃｋ  ＲＳＡ  Ｃｏｎｆｅｒｅｎｃｅ、２００３年
【非特許文献１１】Ｓ．Ｊａｒｅｃｋｉ及びＡ．Ｏｄｌｙｚｋｏ著、「Ａｎ  ｅｆｆｉｃｉｅｎｔ  ｍｉｃｒｏｐａｙｍｅｎｔ  ｓｙｓｔｅｍ  ｂａｓｅｄ  ｏｎ  ｐｒｏｂａｂｉｌｉｓｔｉｃ  ｐｏｌｌｉｎｇ」、議事録、ｔｈｅ  １ｓｔ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｆｉｎａｎｃｉａｌ  Ｃｒｙｐｔｏｇｒａｐｈｙ、１９９７年
【非特許文献１２】Ｒｏｂｅｒｔ  Ｊｏｈｎｓｏｎ、Ｄａｖｉｄ  Ｍｏｌｎａｒ、Ｄａｗｎ  Ｘｉａｏｄｏｎｇ  Ｓｏｎｇ及びＤａｖｉｄ  Ｗａｇｎｅｒ著、「Ｈｏｍｏｍｏｒｐｈｉｃ  ｓｉｇｎａｔｕｒｅ  ｓｃｈｅｍｅｓ」、ＣＴ−ＲＳＡ、２４４-２６２ページ、２００２年
【非特許文献１３】Ｃ．Ｊｕｔｌａ及びＭ．Ｙｕｎｇ著、「Ｐａｙ  Ｔｒｅｅ：  Ａｍｏｒｔｉｚｅｄ  ｓｉｇｎａｔｕｒｅｓ  ｆｏｒ  ｆｌｅｘｉｂｌｅ  ｍｉｃｒｏｐａｙｍｅｎｔｓ」、議事録、ｔｈｅ  ｓｅｃｏｎｄ  ＵＳＥＮＩＸ  ｗｏｒｋｓｈｏｐ  ｏｎ  ｅｌｅｃｔｒｏｎｉｃ  ｃｏｍｍｅｒｃｅ、１９９６年
【非特許文献１４】Ｓ．Ｋｉｍ及びＨ．Ｏｈ著、「(Ａｎ  ａｔｏｍｉｃ  ｍｉｃｒｏｐａｙｍｅｎｔ  ｓｙｓｔｅｍ  ｆｏｒ  ａ  ｍｏｂｉｌｅ  ｃｏｍｐｕｔｉｎｇ  ｅｎｖｉｒｏｎｍｅｎｔ)、ＩＥＩＣＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｆ  Ｉｎｆｏｒｍａｔｉｏｎ  ａｎｄ  Ｓｙｓｔｅｍｓ、Ｅ８４-Ｄ（６）、７０９-７１６ページ、２００１年
【非特許文献１５】Ｐ．Ｋｏｃｈｅｒ著、「Ｏｎ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｒｅｖｏｃａｔｉｏｎ  ａｎｄ  Ｖａｌｉｄａｔｉｏｎ」、議事録、ｔｈｅ  ２ｎｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｆｉｎａｎｃｉａｌ  Ｃｒｙｐｔｏｇｒａｐｈｙ、１９９８年
【非特許文献１６】Ｓａｔｏｓｈｉ  Ｋｏｇａ及びＫｏｕｉｃｈｉ  Ｓａｋｕｒａｉ著、「Ａ  ｄｉｓｔｒｉｂｕｔｅｄ  ｃｅｒｔｉｆｉｃａｔｅ  ｓｔａｔｕｓ  ｐｒｏｔｏｃｏｌ  ｗｉｔｈ  ｓｉｎｇｌｅ  ｐｕｂｌｉｃ  ｋｅｙ」、議事録、ＰＫＣ２００４、３８９-４０１ページ、２００４年
【非特許文献１７】Ｒ．Ｊ．Ｌｉｐｔｏｎ及びＲ．Ｏｓｔｒｏｖｓｋｙ著、「Ｍｉｃｒｏ-Ｐａｙｍｅｎｔｓ  ｖｉａ  Ｅｆｆｉｃｉｅｎｔ  Ｃｏｉｎ  Ｆｌｉｐｐｉｎｇ」、議事録、ｔｈｅ  ２ｎｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｆｉｎａｎｃｉａｌ  Ｃｒｙｐｔｏｇｒａｐｈｙ、１９９８年
【非特許文献１８】Ａ．Ｍａｌｐａｎｉ、Ｒ．Ｈｏｕｓｅｌｙ及びＴ．Ｆｒｅｅｍａｎ著、「Ｓｉｍｐｌｅ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｖａｌｉｄａｔｉｏｎ  Ｐｒｏｔｏｃｏｌ  −  （ＳＣＶＰ）」、ＩＥＴＦ  Ｄｒａｆｔ、ｄｒａｆｔ-ｉｅｔｆ-ｐｋｉｘ-ｓｃｖｐ-１２.ｔｘｔ、２００３年６月
【非特許文献１９】Ｒ．Ｃ．Ｍｅｒｋｌｅ著、「Ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ」、ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｐｒｉｖａｃｙ、１９８０年
【非特許文献２０】Ｓ．Ｍｉｃａｌｉ著、「Ｅｆｆｉｃｉｅｎｔ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｒｅｖｏｃａｔｉｏｎ」、ＭＩＴ/ＬＣＳ/ＴＭ  ５４２ｂ、Ｍａｓｓａｃｈｕｓｅｔｔｓ  Ｉｎｓｔｉｔｕｔｅ  ｏｔ  ｌ  ｅｃｈｎｏｌｏｇｙ、１９９６年
【非特許文献２１】Ｓ．Ｍｉｃａｌｉ著、「Ｅｆｆｉｃｉｅｎｔ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｒｅｖｏｃａｔｉｏｎ」、議事録、ｔｈｅ  ＲＳＡ  Ｄａｔａ  Ｓｅｃｕｒｉｔｙ  Ｃｏｎｆｅｒｅｎｃｅ  １９９７、及び、米国特許第５６６６４１６
【非特許文献２２】Ｓ．Ｍｉｃａｌｉ著、「ＮＯＶＯＭＯＤＯ：  ｓｃａｌａｂｌｅ  ｃｅｒｔｉｆｉｃａｔｅ  ｖａｌｉｄａｔｉｏｎ  ａｎｄ  ｓｉｍｐｌｉｆｉｅｄ  ＰＫＩ  ｍａｎａｇｅｍｅｎｔ」、議事録、ｔｈｅ  １ｓｔ  Ａｎｎｕａｌ  ＰＫＩ  Ｒｅｓｅａｒｃｈ  Ｗｏｒｋｓｈｏｐ、２００２年
【非特許文献２３】Ｍ．Ｍｙｅｒｓ、Ｒ．Ａｎｋｎｅｙ、Ａ．Ｍａｌｐａｎｉ、Ｓ．Ｇａｌｐｅｒｉｎ及びＣ．Ａｄａｍｓ著、「Ｘ．５０９  ｉｎｔｅｒｎｅｔ  ｐｕｂｌｉｃ  ｋｅｙ  ｉｎｆｒａｓｔｒｕｃｔｕｒｅ  Ｏｎｌｉｎｅ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｓｔａｔｕｓ  Ｐｒｏｔｏｃｏｌ−ＯＣＳＰ」、Ｉｎｔｅｒｎｅｔ  ＲＦＣ  ２５６０、１９９９年６月
【非特許文献２４】Ｍ．Ｎａｏｒ及びＫ．Ｎｉｓｓｉｍ著、「Ｃｅｒｔｉｆｉｃａｔｅ  Ｒｅｖｏｃａｔｉｏｎ  ａｎｄ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｕｐｄａｔｅ」、議事録、ＵＳＥＮＩＸ  Ｓｅｃｕｒｉｔｙ、１９９８年
【非特許文献２５】Ｎａｔｉｏｎａｌ  Ｂｕｒｅａｕ  ｏｆ  Ｓｔａｎｄａｒｄｓ発行、「ＮＢＳ  ＦＩＰＳ  ＰＵＢ  ８１：ＤＥＳ  ｍｏｄｅｓ  ｏｆ  ｏｐｅｒａｔｉｏｎ」、１９８０年
【非特許文献２６】Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ発行、「ＦＩＰＳ  １８０-１：  Ｓｅｃｕｒｅ  ｈａｓｈ  ｓｔａｎｄａｒｄ」、１９９５年
【非特許文献２７】Ｍ．Ｐｉｅｒｃｅ及びＤ．Ｏ’Ｍａｈｏｎｙ著、「Ｍｉｃｒｏｐａｙｍｅｎｔｓ  ｆｏｒ  Ｍｏｂｉｌｅ  Ｎｅｔｗｏｒｋｓ」、議事録、Ｅｕｒｏｐｅａｎ  Ｗｉｒｅｌｅｓｓ、１９９９年、Ｗｉｎｎｅｒ  ｏｆ  Ｂｅｓｔ  Ｐａｐｅｒ  Ａｗａｒｄ
【非特許文献２８】Ｒ．Ｌ．Ｒｉｖｅｓｔ著、「Ｔｈｅ  ＭＤ５  ｍｅｓｓａｇｅ  ｄｉｇｅｓｔ  ａｌｇｏｒｉｔｈｍ」、Ｉｎｔｅｒｎｅｔ  ＲＦＣ  １３２１、１９９２年４月
【非特許文献２９】Ｒ．Ｌ．Ｒｉｖｅｓｔ著、「Ｅｌｅｃｔｒｏｎｉｃ  Ｌｏｔｔｅｒｙ  Ｔｉｃｋｅｔｓ  ａｓ  Ｍｉｃｒｏｐａｙｍｅｎｔｓ」、議事録、ｔｈｅ  ２ｎｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｆｉｎａｎｃｉａｌ  Ｃｒｙｐｔｏｇｒａｐｈｙ、１９９７年
【非特許文献３０】Ｒ．Ｌ．Ｒｉｖｅｓｔ及びＡ．Ｓｈａｍｉｒ著、「Ｐａｙ  Ｗｏｒｄ  ａｎｄ  ＭｉｃｒｏＭｉｎｔ-Ｔｗｏ  Ｓｉｍｐｌｅ  Ｍｉｃｒｏｐａｙｍｅｎｔ  Ｓｃｈｅｍｅｓ」、ＣｒｙｐｔｏＢｙｔｅｓ、ＲＳＡ  Ｌａｂｏｒａｔｏｒｉｅｓ、２（１）、１９９６年、議事録、１９９６  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｓｅｃｕｒｉｔｙ  Ｐｒｏｔｏｃｏｌｓ
【非特許文献３１】Ｒ．Ｌ．Ｒｉｖｅｓｔ、Ａ．Ｓｈａｍｉｒ及びＬ．Ａｄｌｅｍａｎ著、「Ａ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｏｂｔａｉｎｉｎｇ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅｓ  ａｎｄ  Ｐｕｂｌｉｃ-Ｋｅｙ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ」、Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ、２１：１２０-１２６ページ、１９７８年
【非特許文献３２】Ｒｏｎ  Ｓｔｅｉｎｆｅｌｄ、Ｌａｕｒｅｎｃｅ  Ｂｕｌｌ及びＹｕｌｉａｎｇ  Ｚｈｅｎｇ著、「Ｃｏｎｔｅｎｔ  ｅｘｔｒａｃｔｉｏｎ  ｓｉｇｎａｔｕｒｅｓ」、議事録、ｔｈｅ  ４ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  Ｓｅｏｕｌ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｃｒｙｐｔｏｌｏｇｙ、２８５-３０４ページ、Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ社、２００２年
【非特許文献３３】Ｈ．Ｔｅｗａｒｉ及びＤ．Ｏ’Ｍａｈｏｎｙ著、「Ｍｕｌｔｉｐａｒｔｙ  Ｍｉｃｒｏｐａｙｍｅｎｔｓ  ｆｏｒ  Ａｄ-Ｈｏｃ  Ｎｅｔｗｏｒｋｓ」、議事録、ｔｈｅ  ＩＥＥＥ  Ｗｉｒｅｌｅｓｓ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ａｎｄ  Ｎｅｔｗｏｒｋｉｎｇ  Ｃｏｎｆｅｒｅｎｃｅ  （ＷＣＮＣ）、２００３年
【非特許文献３４】Ｈ．Ｔｅｗａｒｉ及びＤ．Ｏ’Ｍａｈｏｎｙ著、「Ｒｅａｌ-Ｔｉｍｅ  Ｐａｙｍｅｎｔｓ  ｆｏｒ  Ｍｏｂｉｌｅ  ＩＰ」、ＩＥＥＥ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ、４１（２）：１２６-１３６、２００３年
【非特許文献３５】Ｄ．Ｗｈｅｅｌｅｒ著、「Ｔｒａｎｓａｃｔｉｏｎｓ  Ｕｓｉｎｇ  Ｂｅｔｓ」、議事録、Ｆｏｕｒｔｈ  Ｃａｍｂｒｉｄｇｅ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｓｅｃｕｒｉｔｙ  Ｐｒｏｔｏｃｏｌｓ、１９９６年
【非特許文献３６】Ｊ．Ｚｈｏｕ及びＫ-Ｙ．Ｌａｍ著、「Ｕｎｄｅｎｉａｂｌｅ  Ｂｉｌｌｉｎｇ  ｉｎ  Ｍｏｂｉｌｅ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ」、議事録、ＭＯＢＩＣＯＭ、１９９８年
【発明の開示】
【発明が解決しようとする課題】
【０００５】
証明書は、その有効期限日Ｄ２より前に失効されなければならない。例えば、証明書の所有者Ｕが、所属や役職を変えるかもしれないし、所有者の秘密鍵ＳＫＵが、危殆化しているかもしれない。証明書が失効した場合、他者が、所有者の公開鍵を使えないようにしなければならない。
【０００６】
失効した証明書の公開鍵の使用を防ぐ１つの手法として、「証明書失効リスト（ＣＲＬ）」によるものがある。ＣＲＬは、ＣＡ１２０が発行する署名及びタイムスタンプが記され、失効した証明書をそれぞれのシリアル番号ＳＮによって特定するリストである。これらのＣＲＬは、新規に失効した証明書がない場合でも、いかなるタイプのリプレイ攻撃をも防止するために、定期的に配布されなければならない。通信、検索、及び検証のための費用の観点から見ると、ＣＲＬの管理は、やっかいなものかも知れない。非特許文献１５に示したように、ＣＲＬの代わりに、証明書失効ツリー（ＣＲＴ）を使用することができる。
【０００７】
ＣＲＬ及びＣＲＴの代わりに、ＣＡ１２０は、特定の証明書についてのクエリに答えることができる。図１では、ユーザＵ２は、ユーザＵ１の証明書１０４のシリアル番号ＳＮを有するクエリ１５０を発行する。ＣＡ１２０は、シリアル番号ＳＮや、有効状況フィールド１６０ＶＳ（「有効」「無効」或いは「不明」）や、タイムスタンプ「時間」を含む有効状況情報１６０で返信する。この返信は、ＣＡによって署名される（フィールド１６０−ＳｉｇＣＡ）。この手法は、オンライン証明書状態プロトコル（ＯＣＳＰ）に利用されている（非特許文献２３参照）。ＣＡのデジタル証明書１６０-ＳｉｇＣＡには、特に、ＣＡは、非常に安全でなくてはならないため、とても長く（ＲＳＡの場合、１０２４ビット超）なってしまうという欠点がある。また、ＣＡが集中している場合、ＣＡは、認証の障害になってしまい、ＣＡが、分散化（複製）されている場合、ＣＡの署名鍵ＳＫＣＡが複製されるために安全性が弱くなる。
【０００８】
図２は、ＣＡ１２０が署名していない有効状況を予め特定した時間間隔（例えば、毎日、又は毎時、など）で信頼できないディレクトリ２１０を通して提供することができる「ＮＯＶＯＭＯＤＯ」による手法を図示している。ディレクトリ２１０は、秘密情報を格納しないコンピュータシステムである。このシステムは、以下のように機能する。
【０００９】
ｆを、予め定義された公開長を保存する関数とする。
【００１０】
ｆ：  ｛０，ｌ｝ｎ→｛０，ｌ｝ｎ
ここで、｛０，ｌ｝ｎは、長さｎの全ての２進法の文字列の集合である。ｆｉが、ｆ倍の合成を示すとする。つまり、ｉ＝０に対して、ｆｉ（ｘ）＝ｘであり、ｉ＞０に対して、ｆｉ（ｘ）＝ｆ（ｆｉ−１（Ｘ））である。ｆを、一方向とする。ｘがランダムに選択されるｆ（ｘ）が与えられると、無視できる程度の確率を除いて、ｆ（ｘ）＝ｆ（ｘ）となるようなプリイメージｚを見つけることは困難（実行不可能）である。すなわち、ｘをランダムに選択するｆ（ｘ）が「実行不可能である」とは、安全性のパラメータｋ（例えばｋ＝ｎ）が与えられているので、無視できる程度の可能性を除いて、ｋにおける予め定義されている多項式と同じ時間内に、プリイメージｚを計算することができないということである。さらに、ｆは、その反復において、一方向であるであると仮定すると、すなわち、任意のｉに対して、ｙをｙ＝ｆｉ（ｘ）と仮定すると、ｆ（ｚ）＝ｙであるようなｚを見つけることは実行不可能である。
【００１１】
一般性を失うことなく、ＣＡは、新しい有効状況を毎日提供し、証明書は、一年、すなわち３６５日間有効であること（Ｄ２-Ｄ１＝３６５日）が要求されていると仮定することができる。証明書１０４（図２）を生成するために、ＣＡ１２０は、ランダムな「シード」となる数ｘを拾い、「ハッシュ連鎖」ｃ０、ｃ１、・・・ｃ３６５を生成する。
【００１２】
ｃ３６５＝ｆ（ｘ），ｃ３６４＝ｆ（ｆ（ｘ）），．．．ｃ１＝ｆ３６５（ｘ），ｃ０＝ｆ３６６（ｘ）…（１）
シリアル番号ＳＮを有する証明書に対して、ｘをｘ（ＳＮ）とし、また同様に、ｉ＝０、１、・・・であるｃｉ＝Ｃｉ（ＳＮ）として示すことがある。この値ｃ０は、「検証ターゲット」と呼ばれる。ＣＡ１２０は、ｃ０を、証明書１０４にデータ１０４Ｄとともに挿入する（図１）。ＣＡ１２０は、ランダムな失効シード番号Ｎ０も生成し、「失効ターゲット」Ｎｉ＝ｆ（Ｎ０）を計算し、Ｎｉを証明書１０４に挿入する。ＣＡ１２０は、ｉ＞０に対して、全てのｃｉの秘密を維持する。値ｘ及びＮ０も秘密である。Ｃｉの全てが、ｘから計算可能であり、検証ターゲットｃ０が、任意のｃｉから計算可能であることは明らかである。ＣＡ１２０は、個別のストレージに、各証明書１０４に対する値ｘ及びＮ０を記憶し、（必ずしも必要ではないが）可能であれば、そのｃｉの値をキャッシュする。
【００１３】
ＣＡは、毎日ｉ（ｉ＝１，２，・・・３６５）、証明書１０４ごとに有効状況を示す（図２においては図示しないが、「有効」、又は、「失効」を示す）もの以外に、
１．証明書が、ある日ｉにおいて有効である場合は、証明書の「ｉ-トークン（ｉ-ｔｏｋｅｎ）」ｃｉを含み、
２．証明書が失効している場合は、失効シードＮ０を含む有効性証明データ構造をディレクトリ２１０に配布する。
【００１４】
この情報は、署名無しに配布される。各ディレクトリ２１０は、有効状況要求１５０に応答して、この情報を、署名無しで、要求者のシステム１１０に提供する（図１）。検証するために、要求者（検証者）１１０は、以下の作業を実行する。
【００１５】
１．有効状況が「有効」である場合は、検証者１１０は、ｆｉ（ｃｉ）＝ｃ０を確認する。
【００１６】
２．有効状況が「失効」である場合は、検証者１１０は、ｆ（Ｎ０）＝Ｎ１を確認する。
【００１７】
たとえ、ｃｉが与えられたとしても、それに続くトークンｃｉ＋１、ｃｉ＋２・・・を計算することが不可能なため、その有効性情報が署名されていないにも係わらず、スキームは安全である。
【００１８】
ＣＡ１２０とディレクトリ２１０との間の通信を減らすために、証明書１０４の集合に対して、ハッシュ連鎖（１）を生成することができ、その集合が「失効していない」（すなわち、全ての証明証が集合の中で失効していない）場合は、その集合に対して単一のｉ-トークンｃｉを配布することができる。図３は、証明書の集合Ｆ１からＦ４までを図示する。Ｆ１は、全ての証明書１０４の集合（Ｆ２⊂Ｆ３⊂Ｆ１及びＦ４⊂Ｆ１）である。証明書１０４ごとのシード番号x、Ｎ０に加えて、ＣＡ１２０は、各集合Ｆｉのためにランダムなシード番号ｘ（Ｆｉ）、Ｎ０（Ｆｉ）をランダムに生成し、有効性ターゲットｃ０（Ｆｉ）＝ｆ３６６（ｘ（Ｆｉ））を用いて、それぞれの数ｘ（Ｆｉ）からハッシュ連鎖（１）を作成する。各証明書１０４は、証明書を含む各集合Ｆｉに対して、ターゲットｃ０（Ｆｉ）と共に増大する。
【００１９】
全ての証明書が有効である場合、毎日ｉ、ＣＡ１２０は、ｉ-トークンｃｉ（Ｆ１）だけをディレクトリ２１０に配布する。もし、集合Ｆ３が、無効な証明書を持っている場合、ＣＡ１２０は、Ｆ４と、集合Ｆ２における全ての有効な証明書に対して、ｉ-トークンを配布する。集合Ｆ２‐Ｆ３が、無効な証明書を持っている場合、ＣＡ１２０は、集合Ｆ３及び集合Ｆ４と、集合Ｆ２‐Ｆ３とにおける全ての有効な証明書に対して、ｉ-トークンを配布する。
【００２０】
証明書１０４に対する有効状況要求に応答して、ディレクトリ１２０は、要求者（検証者）に対して、
１．証明書が有効である場合は、証明書及び証明書を含む集合Ｆｉに対して、ｉ-トークンｃｉを送信し、
２．証明書が失効している場合は、証明書の失効番号Ｎ０を送信する。
【００２１】
証明書が有効であることを示す応答の場合、検証者は、ｆｉ（ｃｉ）が証明書の検証ターゲットの１つと等しいことを確認する。証明書が失効していることを示す応答の場合、検証者は、証明書に対するｆ（Ｎ０）＝Ｎ１を確認する。
【００２２】
失効証明書（図４）の各集合Ｒに対して、有効な証明書Ｒ’をカバーする集合Ｆｉのうちの最小の集合を見つけることが望ましいことは明らかである。この明細書の定義により、和集合Ｕが、Ｆｉ＝Ｒ’である場合、｛Ｆｉ｝は、Ｒ’を「カバー」する。｛Ｆｉ｝は、Ｒを「コンプリメントカバー」と言う。ＲのコンプリメントカバーをＣＣＲで示す。
【００２３】
また、任意の集合体系Ｒ、又は、少なくとも多くの可能な集合Ｒに対する補足的な小さいカバーを含む集合｛Ｆ｝を見つけることが望ましい。｛Ｆ｝が、証明書の各集合Ｒに対するカバーを含む場合、｛Ｆ｝を全ての証明書の集合に対するコンプリメントカバーと呼び、このコンプリメントカバーをＣＣ（Ｕ）、又は、単にＣＣとして示す。
【００２４】
統一するために、各証明書１０４は、その証明書からなる単集合に対応することとする。単集合に対するハッシュ連鎖は、証明書に対するものと同じである。
【００２５】
｛Ｆ｝が、各証明書に対する単集合を含む場合、｛Ｆ｝が、全ての証明書の集合に対するコンプリメントカバーであることは明らかである。
【００２６】
コンプリメントカバーは、ツリーを使って構成することができる。図５は、番号１から８までの８つの証明書に対するバイナリツリー５１０である。各ノードは、集合Ｆｉを表す。（１、２、・・・とラベルが付けられた）各リーフノードは、それぞれ証明書１、２、・・・に対する単集合を表す。各ハイレベルのノードは、その子ノードの和集合を表す。例えば、ノード１乃至４は、証明書１から証明書４までの集合を表す。ルートは、全ての証明書を表す（ツリーとコンプリメントカバーの両方を表す符号として５１０を使用する）。
【００２７】
証明書が失効している場合は、対応するリーフも失効している。すなわち、ｉ-トークンの配布のために使用することができない集合を表す。また、リーフからルートへのパスにおける各ノードは失効している。図６の例では、（「ｘ」の記号で示されているように）証明書３及び証明書８は失効している。よって、集合３-４、１-４、１-８、７-８、５-８は失効している。失効証明書の最小のコンプリメントカバーＣＣＲは、ノード１-２、４、５-６、７から構成される。一般的に、最小のコンプリメントカバーＣＣＲは、失効したノードの子供である全てのノードで構成されている。証明書が失効すると失効モードをマークし、失効したノードの失効していないごく近い子ノードを見つけるために、ＣＡ１２０に実装可能であるコンピュータツリーを走査するアルゴリズムが公知である。ＣＡ１２０は、ごく近い子ノードに対してｉ‐トークンを毎日配布し、失効したリーフに対してＮ０のトークンを配布する。
【課題を解決するための手段】
【００２８】
ここでは、本発明の特徴について、いくつか概要を述べる。他の特徴については、後述する。本発明は、参照により、ここに引用する添付した請求の範囲によって定義される。
【００２９】
本発明の１つの特徴は、証明書のサイズを小さくするようになっていることである。図３における証明書１０４は、複数のターゲットｃ０を含んでいてもよい。いくつかの実施形態において、そのような複数のターゲットを単一の「スーパーターゲット」にマップするための方法を使う。証明書は、複数のターゲットではなく、スーパーターゲットを含む。
【００３０】
本発明の他の特徴は、不必要なターゲットを削除することで、証明書を編集するようになっていることである。図３において、各証明書１０４には、複数のターゲットｃ０の他に取り消しターゲットＮ１が含まれている。検証者は、有効か無効かの証明として、これらのターゲットのうちの１つだけを必要とする。検証者は、証明書及び証明を他者から入手することができる。他者は、不必要なターゲットを削除して証明書を編集することが望ましいが、その他者が、編集済みの証明書にＣＡの署名１０４−ＳｉｇＣＡを生成することはできない。本発明の一実施形態において、ＣＡは、編集可能な署名を使用し、ＣＡの署名鍵（秘密鍵ＳＫＣＡ）無しで、不要なターゲットを削除できるようにしている。それでもなお、他者は、ＣＡの署名を検証者に提供することができる。
【００３１】
本発明の他の特徴は、証明書が有効である証明を効率的に配布するようになっていることである。いくつかの実施形態において、有効性の証明（例えば、ｉ-トークン）は、証明書の所有者に配布される。システム１１０が、有効性の証明の要求１５０を発行した場合、有効性証明は、ＣＡやディレクトリではなく、所有者によって提供される。対応するコンピュータシステム１１０が、マルチキャスティンググループを構成する場合、複数の証明書を含む集合Ｆに対する有効性証明（例えば、ｉ-トークン）は、マルチキャスト伝送を介して証明書の所有者に配布することができる。いくつかの実施形態において、集合Ｆ及びマルチキャスティンググループは整合され、マルチキャスト伝送を容易にする。例えば、マルチキャスティンググループは、集合Ｆに対して作成することができる、又は、集合Ｆは、ＣＡによって、マルチキャスティンググループの設定時に作成することができる。また、コンプリメントカバーＣＣＲは、マルチキャスティンググループがそのために存在する集合Ｆの数を最大にするように選択することができる。
【００３２】
本発明の他の特徴は、有効性証明を効率的にキャッシングするようになっていることである。いくつかの実施形態において、システム１１０（例えば、１１０.１）が、証明書に対する有効性証明を取得する場合、システム１１０.１は、有効性証明をキャッシュしてもよい。他のシステム１１０.２は、ＣＡやディレクトリからではなく、システム１１０.１から有効性証明を取得してもよい。いくつかの実施形態において、集合Ｆに対して有効性証明をキャッシュするかどうか決定する時に、システム１１０.１が考慮する優先順位をキャッシングして証明書の集合Ｆを割り当てる。キャッシングの優先順位は、集合Ｆにおける証明書の数、及び／又は、Ｆにおける証明書の残りの有効期限内の合計、及び／又は、他の要素に基づくものであってよい。
【００３３】
本発明の他の特徴は、ＣＡが、証明書有効性データ構造（ハッシュ連鎖シードｘなど）を生成するようになっていることである。例えば、ハッシュ連鎖（１）に対して、データ構造は、期間ｉに対応する各ｉ-トークンを有する期間の所定数（例えば、３６５日）だけ生成される。証明書の発行日Ｄ１と失効日Ｄ２によって定義されているように、期間の数は、証明書の最大有効期間によって定義される。期間の数は、ターゲットｃ０に組み込まれる。このために、とりわけ、コンプリメントカバーが使われている場合、コンプリメントカバーは、複数の証明書に対する有効性証明を相互に関係付けるため、新規証明書の追加が困難になる。一実施形態では、設定時に、ＣＡが、証明書の最大有効期間によって要求される以上の長い時間のデータ構造を生成する。例えば、ＣＡは、期間のある数Ｔｄに対して、予め定義された数Ｍの証明書のデータ構造を生成することができる。ここで、Ｔｄは、最大有効期間よりも大きいものとする。設定時に生成された証明書の実際の数は、Ｍより少なくてよい。ＣＡは、設定の後に新規証明書を追加することができる。ただし、それは、新規証明書が最終の期間Ｔｄの前、又は、最終の期間Ｔｄ中に失効する限りにおいてである。有効性証明は、ｉ‐トークンｃｉ（Ｆ）を含んでもよいし、また、ターゲットｃ０（Ｆ）を求めるために関数ｆを、ｉ-トークンに適用する必要がある時間の数ｊを含んでもよい。検証者は、ｆｊ（ｃ１（Ｆ））＝ｃ０（Ｆ）を確認する。ハッシュ連鎖は、他の構造、例えば、以下に説明するように、ハッシュツリーに置き換えることができる。
【００３４】
本発明の他の特徴は、配布された証明書に権限を提供するようになっていることである。ＣＡは、検証データ（例えば、ｉ-トークン）を、有効性証明を生成し、それらを検証者に提供する「Ｓｕｂ-ＣＡ」コンピュータシステムに配布する。ＣＡは、秘密データをＳｕｂ-ＣＡに予め配布する。例えば、ＣＡは、設定時に全ての証明書に対して、全てのｉ-トークンを配布する。多くの技術のうち１つ以上の技術を使って、たとえ、Ｓｕｂ-ＣＡが危殆化したとしても、有効性を確実なものにしている。
【００３５】
１つの技術には、異なったＳｕｂ-ＣＡの同じ証明書に対して、異なったデータを生成することが含まれる。よって、個別の有効シードｘ及び個別の失効シードＮ０は、各Ｓｕｂ-ＣＡの各証明書のために生成することができる。証明書は、それぞれの有効ターゲット及び失効ターゲットの全てを含んでもよい。或いは、有効ターゲットは、公開関数によって、単一の「スーパーターゲット」にマップされてもよいし、証明書は、有効「スーパーターゲット」だけを有してもよい。失効ターゲットも、同じように取り扱うことができる。或いは、全ての有効ターゲット及び失効ターゲットは、単一のスーパーターゲットにマップされることができる。
【００３６】
さらに、各期間ｉにおいて、Ｓｕｂ-ＣＡの有効性証明は、ＣＡによって、期間ｉの間、各Ｓｕｂ-ＣＡに対して入手可能になる。Ｓｕｂ-ＣＡが、危殆化している場合、ＣＡは、Ｓｕｂ-ＣＡの有効性証明を保留するので、検証者は、Ｓｕｂ-ＣＡが無効であることを知り、Ｓｕｂ-ＣＡの証明書の有効性証明を使用しない。残りのＳｕｂ-ＣＡが、危殆化していない場合、各Ｓｕｂ-ＣＡは、上述したように、それ自体の証明書の有効データを持っているので、それらのデータは秘密のままである。
【００３７】
さらに、危殆化しているＳｕｂ-ＣＡの制御を回復するためのメカニズムが提供されている。そのメカニズムは、データをＳｕｂ-ＣＡに伝送する前に、証明書の有効データを暗号化することが含まれる。各期間ｉに対して、又は、いくつかの連続する期間ｉ（このような連続する期間ｉを「パーティション」と呼ぶ）に対して、個別の暗号/復号鍵が用いられる（暗号化は、対称的でも非対称的でもよい）。さらに、異なったＳｕｂ-ＣＡに対して、異なった復号鍵が用いられる。パーティションごとに、パーティションの開始時、又は、パーティションの開始の少し前に、復号鍵を、Ｓｕｂ-ＣＡに提供する。パーティションにおいて、Ｓｕｂ-ＣＡが、危殆化している場合、敵が、現在のパーティションに対する復号したデータ（例えば、ｉ-トークン）を持っているかもしれないが、それ以降のパーティションに対するデータは、暗号化されているので安全である。ＣＡが、再びＳｕｂ-ＣＡを制御できる場合、ＣＡは、Ｓｕｂ-ＣＡが復号鍵を受信した最終のパーティションの終了時又は終了後に、再びＳｕｂ-ＣＡを起動させてもよい。ＣＡは、復号鍵を危殆化しているＳｕｂ-ＣＡには提供しない。
【００３８】
本発明は、上述した特徴及び利点に限定されるものではなく、他の特徴については、以下に説明する。本発明は、添付した請求の範囲によって定義される。
【発明を実施するための最良の形態】
【００３９】
ここに説明する実施形態は、本発明を示すものであり、本発明を制限するものではない。本発明は、添付した請求の範囲によって定義される。
【００４０】
ＣＡ１２０、ディレクトリ２１０、システム１１０は、１つ以上のネットワーク上で互いに通信し合うコンピュータシステムであると仮定する。これらのシステムの各々が、それ自体ネットワーク上で通信を行う構成要素を有するコンピュータシステムであってよい。各コンピュータシステムには、コンピュータの命令を実行し、上記及び下記に説明するように、コンピュータデータを操作する１つ以上のコンピュータプロセスを含む。「データ」という用語には、「コンピュータデータ」が含まれ、コンピュータ命令及び命令によって操作されるコンピュータデータの両方をカバーしている。命令及びデータは、コンピュータストレージ、すなわち、コンピュータで読み取り可能な媒体（例えば、磁気、又は、光学ディスク、半導体メモリ、及び、他のタイプの公知である又は発明される媒体）等のデータキャリアに記憶することができる。データキャリアには、ケーブルを、又は、他の手段によって空間を伝送される電磁気のキャリア波を含んでもよい。「キャッシュ」は、どのコンピュータストレージでもよい。命令及びデータは、コンピュータに上述した適切なアルゴリズムを実行させるように操作可能である。
【００４１】
我々は、次のような表記を使用する。ＤＳ＝（ＫＧ，Ｓｉｎｇ，Ｖｆ）が、デジタル署名スキームを表すようにする。ここで、ＫＧは、鍵生成アルゴリズムであり、Ｓｉｎｇ（ＳＫ，Ｍ）は、署名鍵Ｓｋの下、メッセージＭ上に、署名σを出力する署名アルゴリズムを示す。Ｖｆ（Ｐｋ，Ｍ，σ）は、メッセージＭ上の署名σが公開鍵に関して正しいかどうかを示すバイナリの値を評価する検証アルゴリズムを示す。｛０，１｝＊が、全てのビット列の集合を示すようにする。｜ｓ｜は、ビット列ｓの長さを示す。Ｈが、入力としてｂビットのペイロード及びｖビットの初期化ベクトルＩＶを取り、ｖビットの出力を生成する暗号圧縮関数を示す。いくつかの実施形態において、ｂ＞２ｖである。以下に説明する暗号圧縮関数は、衝突に対して耐性を持つ、すなわち、Ｈ（ＩＶ，ｍ１）＝Ｈ（ＩＶ，ｍ２）となるような２つの異なる入力値ｍ１、ｍ２を見つけることは困難である。ＩＶは、固定されており公知であると仮定する。また、説明を簡潔にするために、それらを時々省略する。そのような暗号圧縮関数の現実的な例としては、ＳＨＡ-１[２６]（出力サイズは、２０ビット）及びＭＤ５[２８]（出力サイズは、１６ビット）があり、共に、６４ビットのペイロードを有する。説明を簡単にするために、圧縮関数の代わりに、「ハッシュ関数」という用語を使用する。この「ハッシュ関数」という用語は、ある固定されたｖに対する｛０，１｝ｖへのマッピング形式｛０，１｝＊を示す。ハッシュ関数は、典型的には一方向であり、衝突に対して耐性を持っているが、本発明は、そのような関数に限らない。
【００４２】
＜ターゲット上のハッシュツリー＞
図３の証明書１０４のサイズを減らすために、検証者が、共通の「スーパーターゲット」値ｒへの各検証ターゲットをマップすることができる、あるアルゴリズムＡを定義することができる。
【００４３】
ｒ←この証明書に対する全てのターゲットｃ０のためのＡ（ｃ０）…（２）
そして、ターゲットｃ０は、証明書から削除することができ、値ｒに置き換えられる。
【００４４】
いくつかの実施形態において、アルゴリズムＡは、ハッシュツリーデータ構造を使って定義される。ハッシュツリーは、各ノード（「頂点」）ｖには、値Ｖａｌｕｅ（ｖ）が割り当てられている。ハッシュツリーは、証明書１０４ごとに作成されている。図７Ａは、証明書番号５に対する図５乃至図６の証明書失効スキームの例を示す。ツリーのノードは、頂点から底へ、そして左から右へまで番号付けがなされており、横優先型である。そのため、ルートは、「ｖ０」とし、その子ノードは、「ｖ１」及び「ｖ２」等である。ラベル付けスキームは、説明のためのものであり、制限するためのものではない。証明書番号５は、４つの集合Ｆ、つまり、｛５｝、｛５，６｝、｛５，６，７，８｝、｛１，２，３，４，５，６，７，８｝のそれぞれに属す。それぞれのターゲットを、ｃ０（５）、ｃ０（５-６）、ｃ０（５-８）、ｃ０（１-８）と示す。ターゲットの値は、ツリーリーフｖ３、ｖ４、ｖ５、ｖ６が順不同に割り当てられる。
【００４５】
Ｖａｌｕｅ（ｖ３）＝ｃ０（５）、Ｖａｌｕｅ（ｖ４）＝ｃ０（５-６）等
ハイレベルなノードの値は、例えば、ｖが、ハイレベルなノードであり、Ｈは、公開ハッシュ関数であり、「０」は、文字列の連鎖を示す、
Ｖａｌｕｅ（ｖ）＝Ｈ（Ｖａｌｕｅ（ｖの左の子ノード）ｏＶａｌｕｅ（ｖの右の子ノード））…（３）
等の公開アルゴリズムを使って計算する。証明書１０４（図７Ｂ）は、ルート値Ｖａｌｕｅ（ｖ０）を含んでいるが、ターゲットｃ０については含まない。いくつかの実施形態において、各ターゲットｃ０は、Ｖａｌｕｅ（ｖ０）、例えば、２０バイトと同じサイズである。よって、証明書のサイズは、小さくなっている。
【００４６】
図８は、ＣＡ１２０及びディレクトリ２１０におけるデータ構造を示す。設定時に（図９に図示）、ＣＡ１２０は、失効シードＮ０を証明書１０４ごとに生成する（図９のステップ９１０）。また、ＣＡ１２０は、コンプリメントカバーＣＣを生成する（ステップ９１４）。コンプリメントカバーは、図５に示すように生成されることとするが、これは必ずしも必要ではない。コンプリメントカバーについては、公知である又は発明される他の方法を用いて生成することもできるし、ＣＡ１２０は、コンプリメントカバー５１０における集合Ｆごとに、検証シードｘ（Ｆ）を生成する（ステップ９１８）。これらのステップについては、従来技術と同じように実行することができる（図５及び図６）。また、ＣＡ１２０は、証明書１０４ごとに、ハッシュツリー７１０を生成する（ステップ９２２）。ステップ９３０において、ＣＡ１２０は、ディレクトリが、証明書（各シリアル番号ＳＮ）ごとに、（ｉ）証明書（図８の８０４に示す）を含む全ての集合Ｆ、及び（ｉｉ）対応するハッシュツリー７１０を決定できるようにする情報を、各ディレクトリ２１０に対して配布する。
【００４７】
各期間ｐｉ（「期間ｐｉ」及び「期間ｉ」は、交換可能に使用する）の開始時、又は、期間ｐｉの少し前に、ＣＡ１２０は、失効した証明書Ｒの最小のコンプリメントカバーＣＣＲを決定する（例えば、図４乃至図６に図示する）。ＣＡ１２０は、ＣＣＲにおける集合Ｆごとの署名されていない可能性のあるデータ構造８１０（図８）、及び、無効な証明書１０４ごとの署名されていない可能性のあるデータ構造８２０を、ディレクトリ２１０に対して配布する。これらの構造は、図５及び図６に示す従来技術と同じとすることができる。構造８１０には、集合Ｆ及びトークンｃｉ（Ｆ）の識別子を含んでいる（ｃｉ（Ｆ）を、期間ｃｉに対する「期間データ」と呼ぶこととする。「期間データ」は、それから検証者がターゲットを計算することができるデータである）。構造８１０は、期間ｐｉの識別子及び／又は関数ｆの識別子も含んでいてよい。構造８２０は、証明書のシリアル番号ＳＮ、証明書の値Ｎ０、及び、証明書失効の表示を含んでいる。
【００４８】
検証システム１１０からの要求に対して、ディレクトリ２１０は、証明書が有効である場合、署名されていない可能性のあるデータ構造８３０で応答し、証明書が無効の場合は、署名されていない可能性のあるデータ構造８４０で応答する。要求発行前であっても、検証者は、証明書が失効していないことを確実にするために、証明書上のＣＡの署名及び失効日Ｄ２を確認することができる（図１０のステップ１００４）。ディレクトリの応答８３０又は８４０の受信を、１００６に示す。構造８３０は、有効状況を「有効」であると特定し、証明書のハッシュツリー７１０のルート値ｒ＝Ｖａｌｕｅ（ｖ０）を計算するために、フィールド８３０Ｖに、ｉ-トークンｃｉ（Ｆ）及び十分な情報を含む。上述した等式（２）に留意されたい。応答が（ステップ１０１０で決定されるように）構造８３０である場合、すなわち、証明書が有効であると申請された場合、検証者は、ステップ１０２０において、ハッシュ連鎖の等式（１）を使って、ｃｉ（Ｆ）からターゲットｃ０（Ｆ）を計算する。ステップ１０３０において、検証者は、追加的な情報からフィールド８３０Ｖにおけるルート値Ｖａｌｕｅ（ｖ０）を計算する。いくつかの実施形態において（図８及び図１０には不図示）、この情報には、リーフ値（図７Ａにおける、ｃ０（５）、ｃ０（５-６）、ｃ０（５-８）、ｃ０（１-８）等）。検証者は、等式（３）を使用して、ルート値を計算する。実際、検証者は、全てのリーフ値が必要な訳ではない。例えば、コンプリメントカバーは、図５及び図７Ａに示すようなものであるし、Ｆ＝｛５-６｝とする。ｃ０（５-６）からＶａｌｕｅ（ｖ０）を計算するために、検証者は、ノードｖ３及びｖ２の値だけを必要とする。以下、ノードｖ３及びｖ２を、ｖ４の共通ノードと呼び、併せてＣｏＮｏｄｅｓ（ｖ４）として示す。より一般的に言えば、この共通ノードは、ルート値を計算するために必要な全てのノードである。ＣｏＮｏｄｅｓ（Ｖ）は、ノードｖからルートへのパス上にあるノードの全ての兄弟ノードの集合として定義されている。ＣｏＮｏｄｅｓ（Ｖ）は、以下のように、バイナリ及び非バイナリのツリーに対して定義することができる。
【００４９】
ｖがルートの場合、ＣｏＮｏｄｅｓ（Ｖ）＝Φ（空集合）…（４）
ここで、Ｓｉｂ（ｖ）は、ｖの全ての兄弟ノードの（おそらく空である）集合であり、Ｐａｒｅｎｔ（ｖ）は、ｖの親ノードである。
【００５０】
いくつかの実施形態において、構造８３０には、図８に、Ｖａｌｕｅ（ＣｏＮｏｄｅｓ（Ｌｅａｆ（Ｆ、ＳＮ）））として示した共通ノードの値が含まれる。ここで、Ｌｅａｆ（Ｆ、ＳＮ）は、シリアル番号ＳＮを有する証明書のツリー７１０における集合Ｆに対応するリーフノードである。Ｖａｌｕｅ（ＣｏＮｏｄｅｓ（Ｌｅａｆ（Ｆ，ＳＮ）））という表記は、ツリー７１０に対するルート値Ｖａｌｕｅ（ｖ０）を計算するために必要な共通ノード情報を示す。共通ノード情報には、共通ノード値だけでなく、共通ノード値が等式（３）のために連結されなければならない順番も含んでよい。例えば、図７Ａでは、Ｖａｌｕｅ（ＣｏＮｏｄｅｓ（ｖ４））は、リストとして表すことができる。
【００５１】
（Ｌ，ｖ３）；（Ｒ，ｖ２）…（５）
ここで、Ｌ及びＲは、共通ノードが、連結されたものの中で、左にあるべきか、右にあるべきかを示す１ビットフラッグの値である。例えば、式において、
Ｖａｌｕｅ（ｖｌ）＝Ｈ（Ｖａｌｕｅ（ｖ３）  ｏ  Ｖａｌｕｅ（ｖ４））
であり、Ｖａｌｕｅ（ｖ３）は、Ｖａｌｕｅ（ｖ４）の左の方へ、そのため、ｖ３のフラッグ値は、Ｌである。
【００５２】
注目すべきは、検証者は、ツリー５１０又はツリー７１０のジオメトリを知る必要がないということである。なぜならば、リスト（５）は、ルート値Ｖａｌｕｅ（ｖ０）を計算するのに十分だからである。ルート値は、以下の要領で計算することができる。
【００５３】
＜リスティング１：ルート値の計算＞
１．ルート値  ←  開始値（すなわち、Ｖａｌｕｅ（Ｌｅａｆ（Ｆ，ＳＮ＝ｃ０（Ｆ））
２．リストＶａｌｕｅ（ＣｏＮｏｄｅｓ（Ｌｅａｆ（Ｆ，ＳＮ）））（リスト（５）等）を左から右に横切る。
【００５４】
各共通ノードに対して、
Ｌ又はＲのフラッグ値が、Ｌの場合は、
ルート値  ←  Ｈ（Ｖａｌｕｅ（共通ノード）  ｏ  ルート値）であり、
そうでなければ、
ルート値  ←  Ｈ（ｔｅｍｐ  ｏ  Ｖａｌｕｅ（共通ノード））
＜リスティング１終了＞
検証者は、ルート値をステップ１０３０において計算する（図１０）。ルート値は、図１０においては、Ｖａｌｕｅ（ｖ０（Ｆ，ＳＮ））として示す。検証者は、計算したルート値と証明書のＶａｌｕｅ（ｖ０）とを比較し、２つの値が等しい場合は、証明書は有効であるとみなされる。等しくない場合は、有効性証明は失敗する（証明書が無効であるとみなされるか、検証者が他の証明を要求してもよい）。
【００５５】
無効な証明書の構造８４０は、従来技術と同じようにでき、構造８２０と同じ情報を所有することができる。検証者は、ステップ１０４０において、従来技術と同じように、ｆ（Ｎ０）＝Ｎ１を確認する。
【００５６】
本発明は、図７Ａの形式のハッシュツリー７１０に限定されるものではない。例えば、リーフノード値ｃ０は、Ｈ（ｃ０）と入れ換えることができる。これは、図１１のツリー７１０を使うのと同様である。ここで、ノードｖ７乃至ｖ１０の追加のレイヤが、リーフとして機能するように底に追加されている。各リーフは、単一の子ノードであり、それぞれの集合Ｆに対して値ｃ０（Ｆ）を有する。よって、ノードｖ３乃至ｖ７の値は、Ｈ（ｃ０）である。ここで、ｃ０は、対応するｃ０に対するものである。関数Ｈが、ｋを各ターゲットｃ０の長さとする集合｛０，１｝２ｋにおいてのみ定義される場合、ｃ０の値は、任意の適当な方法で長さ２ｋまで引き伸ばすことができ、Ｈ（ｃ０）を定義している。他のツリー構造も使用することができる。与えられた各証明書を含む集合Ｆの数は、２の累乗数である必要はない。例えば、あるノードは、あるランダム又は疑似ランダムな値を割り当てられたダミーのノードである。また、非バイナリツリー又は非バランスツリーを用いることができる。値ｃ０は、非リーフノードに割り当てることができる。さらに、親ノード値は、等式（３）のように計算する必要がない。例えば、子ノードの値は、いくつかの追加の値と連結して、親ノード値を計算することができる。又は、子ノードの値は、追加の処理又は他の処理を施すことができる。異なるハッシュ関数Ｈを同じツリーの異なる親ノードに用いることができる。非バイナリツリーに関しては、親ノードの値は、全ての子ノードの値の連結のハッシュ関数、或いは、全ての子ノードの値の全て、又は、全ての子ノードの値より小さい他の関数である。ツリーで表されていない等式（２）における他のアルゴリズムＡも適当である。
【００５７】
「ツリー」という語は、子ノードから親ノードを決定、又は、親ノードから子ノードを決定する方法と共に、コンピュータデータ構造を示す。データ構造には、子ノードから親ノード、及び／又は、親ノードから子ノードのポインターを含んでもよい。或いは、ノードは、配列、又は、他の構造でポインターなしで配置されてもよいが、コンピュータの命令によって実行され、子ノードから親ノードを決定する、又は、親ノードから子ノードを決定する方法で配置されてもよい。
【００５８】
いくつかの実施形態において、ハッシュ連鎖（１）を、ハッシュツリー１２１０と入れ換える（図１２乃至図１４）。例えば、参照により、ホン明細書に引用したものとする非特許文献２４、及び、２００５年３月３１日に公開されたＰＣＴ公報ＷＯ２００５/０２９４４５を参照にされたい。図１２では、リーフｖ１５乃至ｖ２２が、それぞれ期間ｐｉと関連付けられている。この例では、８つの連続する期間ｐ１乃至ｐ８がある。例えば、証明証は、８日間有効であり、各期間ｐ１からｐ８は、それぞれ一日である。ｇｖ（ｉ）が、期間ｐ１に対応するノードを表すようにすると、ｇｖ（１）＝ｖ１５、及び、ｇｖ（２）＝ｖ１６である。これらのノードを、本明細書では「グレイ」ノードと呼ぶ。各グレイノードｇｖ（ｉ）は、それぞれの親ノードｖ７乃至ｖ１４の単一の子ノードである。リーフレベルがｖ１５乃至ｖ２２よりも上のツリー１２１０は、バランスバイナリツリーである。
【００５９】
各リーフｇｖ（ｉ）は、ランダム又は疑似ランダムな値が割り当てられている。残りのノードの値は、例えば、等式（３）を使って子ノードの値によって定義される。すなわち、各親ノードの値は、子ノードの値の連結のハッシュ関数であり、底のレベルでは、各ノードｖ７乃至ｖ１４の値は、対応する子ノードのハッシュ関数である。ルート値Ｖａｌｕｅ（ｖ０）は、ターゲットと呼ばれ、ｃ０によって示す。個別のツリー１２１０は、ツリー１２１０ごとに個別に生成された異なるランダムなリーフ値を有するコンプリメントカバーＣＣ（例えば、ＣＣ５１０）の集合Ｆごとに、ＣＡ１２０によって構成されている。図１５は、ＣＡ１２０におけるハッシュ連鎖情報を置き換えるツリー１２１０を示す。
【００６０】
証明書１０４ごとに、ハッシュツリー７１０（図７Ａのように）は、証明書を含む全ての集合Ｆに対応するツリー１２１０のターゲットｃ０（Ｆ）であるリーフ値を持つＣＡによって構成されている。各証明書１０４は、図７Ｂのような形式をしている。ツリー１２１０のハッシュ関数Ｈは、異なるツリーごとに同じでも異なっていてもよく、ツリー７１０のハッシュ関数Ｈと同じでも異なっていてもよい。ハッシュ関数Ｈは、全て公開である。
【００６１】
ＣＡの設定手順（図１６）は、ステップ９１８において、ＣＡが、リーフごとに、ツリー１２１０を生成することを除いて、図９と同様である。
【００６２】
各期間ｐｉにおいて、ＣＡ１２０は、図８の説明と同じ手順を用いて、失効した証明書Ｒの最小のコンプリメントカバーＣＣＲを決定する。ＣＡ１２０は、ＣＣＲにおける集合Ｆごとの署名されていない可能性のある構造８１０、及び、無効な証明書１０４ごとのおそらく署名されていない構造８２０を、ディレクトリ２１０に配布する。構造８１０には、集合Ｆの識別子が含まれ、また、フィールド８３０Ｖに、ｇｖ（ｉ，Ｆ）が集合Ｆに対応するツリー１２１０のノードｇｖ（ｉ）とするＶａｌｕｅ（ｇｖ（ｉ，Ｆ））及びＶａｌｕｅ（ＣｏＮｏｄｅｓ（ｇｖ（ｉ，Ｆ）））からなる期間データも含まれる。構造８１０には、ツリー１２１０又はツリー７１０を構成するために用いる関数Ｈの期間ｐｉの識別子等の他の情報が含まれていてもよい。構造８２０は、証明書のシリアル番号ＳＮ、証明書のための値Ｎ０、及び、証明書が失効したことを示すものを含む。
【００６３】
検証システム１１０からの要求に応答して、ディレクトリ２１０は、証明書が有効である場合、署名されていない可能性のあるデータ構造８３０で応答し、証明書が無効である場合は、署名されていない可能性のあるデータ構造８４０で応答する。構造８３０は、証明書のシリアル番号ＳＮ、証明書有効の表示、及び、値Ｖａｌｕｅ（ｇｖ（ｉ，Ｆ））、Ｖａｌｕｅ（ＣｏＮｏｄｅｓ（ｇｖ（ｉ，Ｆ））、及び、Ｖａｌｕｅ（ＣｏＮｏｄｅｓ（Ｌｅａｆ（Ｆ，ＳＮ）））を含む。ここで、Ｆは、ＳＮ証明書を含むＣＣＲの要素であり、Ｌｅａｆ（Ｆ，ＳＮ）は、証明書のツリー７１０の集合Ｆに対応するリーフノードである。検証の手順を、図１７に示す。ステップ１００４、ステップ１００６、ステップ１０１０、ステップ１０４０は、図１０と同じである。ステップ１０２０において、検証者は、構造８３０において与えられたＶａｌｕｅ（ｇｖ（ｉ，Ｆ））、Ｖａｌｕｅ（ＣｏＮｏｄｅｓ（ｇｖ（ｉ，Ｆ））からｃ０（Ｆ）を計算する。計算は、上述したリスティング１と同じように行うことができる。ステップ１０３０において、検証者は、ステップ１０２０で計算したｃ０（Ｆ）、及び、構造８３０において与えられたからＶａｌｕｅ（ＣｏＮｏｄｅｓ（Ｌｅａｆ（Ｆ，ＳＮ）））からＶａｌｕｅ（ｖ０（Ｆ，ＳＮ））を計算する。この計算は、リスティング１と同じように行うことができる。計算した値が証明書のＶａｌｕｅ（ｖ０）と等しい場合、証明書は有効であるとみなされる。等しくない場合は、証明書は無効とみなされるか、検証者は、証明書の状況の他の証拠を探してもよい。
【００６４】
図１３は、図１２のツリーの代わりに用いることができる「密なハッシュツリー」１２１０を示す。図１１のツリーは、バランスバイナリツリーである。期間ｐｉは、「グレイ」なノードｇｖ（ｉ）と関連付けられている。非グレイノードを「ホワイト」と呼ぶ。グレイノード及びホワイトノードを、以下のように決定する。ルートｖ０は、ホワイトであり、その左の子ノードｖ１は、グレイであり、右の子ノードｖ２は、ホワイトである。一般的に、各左の子ノードは、グレイであり、右の子ノードは、ホワイトである。グレイノードは、上から下へ、左から右へ横優先に横切り、それに連続するグレイノードは、連続する期間ｐｉが割り当てられている。よって、ｇｖ（１）＝ｖ１、ｇｖ（２）＝ｖ７、ｇｖ（３）＝ｖ９等である。全てのリーフは、ランダム又は疑似ランダムな値が割り当てられており、親ノードの値は、図１２又は図１３のように、子ノードの値から計算されている。ＣＡ１２０、ディレクトリ２１０及び検証者の演算は、図１２のものと同じである。
【００６５】
図１４は、図１２及び図１３のツリーの代わりに用いることができる「接地した密なハッシュツリー」１２１０を示す。図１４のツリーは、図１３のツリーと同様であるが、図１４のツリーは、ｖ７乃至ｖ１０として示す単一の子ノードの追加的な底の層を有する。グレイノードｇｖ（ｉ）は、左の子ノードと単一の子ノードであり、上から下、左から右へ、横優先に番号が付けられている。ＣＡ１２０、ディレクトリ２１０及び検証者の演算は、図１２のものと同じである。
【００６６】
Ｎ＝２ｋ個の証明書があると仮定すると、ツリー５１０は、（１＋ｋ）のレベルを有し、各証明書は、（１＋ｋ）の集合Ｆに属する。これは、検証ターゲットｃ０（Ｆ）の数である。よって、ハッシュツリー７１０には、共通ノードの数と大体同じである、およそｌｏｇ２（１＋ｋ）のレベルがある。証明書の所有者が、証明書及び有効性証明を要求者に提供すると仮定すると、ハッシュツリー７１０を用いることで、Ｏ（ｋ／ｌｏｇ２ｋ）だけ向上する。これは、大きなｋにとっては重大なことである。
【００６７】
いくつかの実施形態において、証明書のターゲットｃ０は、ターゲットのグループに細分され、個別のハッシュツリー７１０は、グループごとに定義される。証明書は、そのようハッシュツリーごとのルート値Ｖａｌｕｅ（ｖ０）を含む。他のバリエーションも可能である。
【００６８】
＜証明書の編集＞
図１８に示したように、証明書ごとの有効性証明（１８１０）は、それぞれの証明書の所有者に配布することができる（１１０.１）。有効性証明については、ＣＡ、ディレクトリ２１０又は他者によって配布することができる。証明書１０４を検証したいと望む第三者（１１０.２）は、ＣＡよりもむしろ証明書の所有者から有効性証明１８１０を受け取ることができる。有効性証明要求１５０（図１）は、時々削除される。例えば、証明書の所有者１１０.１（すなわち、システム１１０.１のユーザ）が、所有者によって署名された文書（図示せず）を通信相手１１０.２に送信すると、所有者１１０.１は、その文書に証明書１０４を添付し、たとえ通信相手１１０.２が所有者の証明書を要求していない場合でも、通信相手１１０.２が文書に記された所有者の署名を検証できるようにする。所有者１１０.１は、所有者の証明書１０４の有効性証明１８１０を通信相手１１０.２に送信することもできる。参照により本明細書に引用したものとするＧｅｎｔｒｙ著「Ｃｅｒｔｉｆｉｃａｔｅ-Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  ａｎｄ  ｔｈｅ  Ｃｅｒｔｉｆｉｃａｔｅ  ａｎｄ  Ｒｅｖｏｃａｔｉｏｎ  Ｐｒｏｂｌｅｍ」、ＥＵＲＯＣＲＹＰＴ  ２００３議事録、２７２-２９３ページを参照にされたい。
【００６９】
図１８において、証明書１０４には、複数のターゲットＴａｒ-１、…Ｔａｒ-ｎが含まれている。各ターゲットは、図３のように、ハッシュ連鎖ターゲットｃ０（Ｆ）、又は、ツリー１２１０のルート値であってもよい。ハッシュツリー７１０は用いない。或いは、ツリー７１０検証ターゲットｃ０のいくつかに対しては使えるが、全てに対してではない。また、ターゲットＴａｒ-ｉは、ツリー７１０のルート値であってもよい。ターゲットＴａｒ-ｉには、失効ターゲットＮ１も含まれてよい（図３及び図７Ｂ）。公知である又は発明される他の証明書スキームも、本発明に用いることができる。ターゲットは、証明書が有効か無効かを決定するために検証者１１０.２が計算可能な値である。
【００７０】
各期間ｐｉの開始時又は少し前に、証明書１０４の有効性証明１８１０が、証明書の所有者のコンピュータシステム１１０.１に提供される（場合によりプッシュ型配信される）。検証証明１８１０は、図８及び図１５のデータ８１０と同じ形式であってもよい。図１５の場合、検証者リスティング１と同じように、期間データからツリー１２１０のルート値を計算し、そのルート値とターゲットＴａｒ-ｉとを比較する。他の有効検証スキームを用いることもできる。検証者は、証明書の有効性を検証するために、ターゲットＴａｒ-ｉの全てを必要としているわけではない。図１８のように、検証者は、１つのターゲットＴａｒ-ｉだけ、又は、１つ以上のターゲットであるが、全てより少ないターゲットを必要としてもよい。
【００７１】
証明書の所有者システム１１０.１は、証明書１０４と共に、有効性証明１８１０を通信相手（コンピュータシステム）１１０.２に提供する。本発明のいくつかの態様によれば、通信相手１１０.１は、不必要なターゲットを削除して証明書を編集し、通信相手１１０.２に提供されるデータ量を減らす。編集された証明書１０４Ｒには、署名証明１０４Ｒ-ＳｉｇＣＡが含まれており、通信相手１１０.２が証明書のＣＡの署名を検証できるようにしている。通信相手１１０.１は、ＣＡの秘密鍵を所持していない。ＣＡ１２０は、編集可能な署名スキームを用いて、通信相手１１０.１が署名証明書１０４Ｔ-ＳｉｇＣＡを提供できるようにする。非特許文献１２には、適切な編集可能な署名スキームが説明されており、公知である又は発明される他のスキームも適切であってもよい。１つのスキームを、図１９に示す。このスキームは、編集可能であってもなくてもよい署名スキームである他の署名スキームＳｉｇ０の上に構築されている。メッセージｘ上に編集可能な署名を構成するためには、メッセージは、ブロックｘ０、ｘ１、…に分割される（図１９では、８つのブロックに分割）。これらのブロックのそれぞれは、メッセージを編集するために削除することが可能である。メッセージｘが、証明書１０４であれば、１つのブロックが、標準データ１０４Ｄとなることができ、他のブロックのそれぞれを、１つ以上のターゲットＴａｒ-ｉから構成することが可能である。或いは、データ１０４Ｄは、いくつかのブロックに対応してもよく、各ターゲットも同様である。バイナリツリー１９１０は、少なくともメッセージｘのブロックと同じ数のリーフを持って構成されている。参照のために、ツリーのノードは、以下のように、バイナリ文字列でラベル付けが成されている。ルートノードは、空文字列Ｅでラベル付けが成されている。ルートの左と右の子ノードは、それぞれ「０」及び「１」でラベル付けが成されている。一般的に、文字列ｓでラベル付けが成されているノードについては、左の子ノードが、ｓ０（０を加える）のラベル付けが成されており、右の子ノードは、ｓ１のラベル付けが成されている。
【００７２】
メッセージｘの各ブロックは、ｋビット（又は、ｋビット未満）であるとする。Ｇ：｛０，１｝ｋ→｛０，１｝２ｋを、疑似ランダムジェネレータとする。ｋビット番号ｋｓを、以下のように、各ノードに割り当てる。
【００７３】
＜リスティング２＞
１．｛０，１｝ｋから均一にランダムにｋＥを拾う。
【００７４】
２．再帰的に、各ノードｓに対して、ｋｓ０をＧ（ｋｓ）の最初のｋビットとして定義し、ｋｓ１を残りのｋビットとして定義する。
【００７５】
＜リスティング２の終了＞
各リーフノードｓは、メッセージｘの対応するブロックｘｓに割り当てられている（ここで、「ｓ」は、文字列及びバイナリ番号の両方として解釈される）。以下のように、各ノードに割り当てられた値ｖｓを有する、ある予め定義したハッシュ関数Ｈを用いて、ツリー１９１０のハッシュツリー構造を定義する。リーフノードについては、
ｖｓ＝Ｈ（０，ｋｓ，ｘｓ）  …（６）
である（エンティティである０、ｋｓ、ｘｓは連結される）。ブロックｘｓよりも多くのリーフノードがある場合、対応するｖｓ値は、ランダムに生成することができる、又は、予め割り当てることができる（例えば、０に設定）。全ての非リーフノードｓについては、
ｖｓ＝Ｈ（１，ｖｓ０，ｖｓ１）  …(７)
メッセージｘの編集可能な署名Ｓｉｇ（Ｘ）は、
Ｓｉｇ（Ｘ）＝＜ｋＥ，Ｓｉｇ０（ｖＥ）＞  …（８）
である。
【００７６】
メッセージｘが、ある文字列Ｌに対するあるブロックｘＬの削除によって編集される場合、署名証明（Ｓｉｇ（Ｘ）としても表示）は、
Ｓｉｇ（ｘ）＝＜ｋ＿Ｖａｌｕｅ（ＣｏＮｏｄｅｓ（Ｌ）），ｖＬ，Ｓｉｇ０（ｖＥ）＞  …（９）
である。ここで、ｋ＿Ｖａｌｕｅ（ＣｏＮｏｄｅｓ（Ｌ））は、ＣｏＮｏｄｅｓ（Ｌ）におけるノードに対するｋｓの値の集合である。ｋ＿Ｖａｌｕｅ（ＣｏＮｏｄｅｓ（Ｌ））は、検証者にとって、Ｌ以外のリーフに対するｋｓを計算するのに十分であるのは明らかである。したがって、検証者は、これらのリーフに対するｖｓを計算する。値ｖＬは、署名証明（９）の一部なので、検証者は、等式（７）からｖＥを計算し、ベース署名Ｓｉｇ（ｖＥ）を検証することができる。
【００７７】
複数のターゲットは、順次削除することができる。或いは、以下の技術を用いることもある。Ｔａｒ-ｉ以外の全てのターゲット（すなわち、図１９におけるリーフ０１０からリーフ１１１に対する全てのメッセージブロック）を削除すると仮定すると、リーフ１００からリーフ１１１に対するｖｓの値は、ｖ１に置き換えることができ、リーフ０１０からリーフ０１１に対しては、ｖ０１に置き換えることができる。一般的に、サブツリーのリーフが全て「削除」される（すなわち、削除されたブロックに対応する）場合、サブツリーのルートに対するｖｓの値は、リーフに対するｖｓの値の代わりに署名証明に挿入される。我々の例では（ブロックｘ０１０からブロックｘ１１１までを削除し）、署名証明は、
Ｓｉｇ（ｘ）＝＜ｋ００、ｖ０１、ｖ１，  Ｓｉｇ０（ｖE）＞  …（１０）
である。（署名証明Ｓｉｇ（ｘ）には、各ｋｓの値、及び、ｖｓの値に対するラベルｓと、署名証明の構成要素を解釈するために必要な他のデータとを含んでいてもよい）。この署名証明は、検証のために必要な情報を全て持っている。Ｔａｒ-７以外の全てのターゲットが削除された場合、署名証明は、
Ｓｉｇ（ｘ）＝＜ｋ０００，ｖ００１，ｖ０１，ｋ１１１，ｖ１１０，ｖ０１，Ｓｉｇ０（ｖE）＞  …（１１）
ここで、６つのターゲットを削除し、５つのｋビット値を、オリジナルのメッセージｘに対する署名証明（８）と比較される署名証明に加える。ｋ０００及びｋ１１１の代わりに、ｋEを提供する場合は、この署名証明（１１）を短くすることができる。いくつかの先行する出願において、削除したメッセージｘに対するｋｓ値を隠して削除したブロックの内容を判定することが難しくなるように、値ｖEを提供しなかった。しかしながら、いくつかの実施形態においては、証明書の所有者１１０.１は、削除したターゲットを隠そうとしないため、短い署名証明が構成される。さらに、署名の安全性は、ベース署名スキームＳｉｇ０によるので、ｋEは、ランダムに生成されたものというよりは公開定数である。この場合、ｋEの値は、署名証明の一部として提供される必要はなく、関数Ｇは、疑似ランダムジェネレータである必要もない。
【００７８】
いくつかの実施形態において、証明書の所有者１１０.１は、編集した証明書１０４Ｒが編集されていない証明書１０４より小さいかどうかをまず確認する。証明書の所有者は、２つの証明書のうち最も短いものを通信相手１１０.２に送信する。他の実施形態では、証明書の所有者１１０.１は、証明書１０４及びターゲットＴａｒ-ｉを含む編集された証明書の中で最も短いものを送信する（不必要なターゲットを全て削除するよりも不必要なターゲットを全てよりも少なく削除することにより、短い証明書を提供してもよい）。
【００７９】
＜有効性証明のマルチキャスト配布＞
有効状況のプッシュ情報には、アドホックネットワークにおいて利点を持ち得る。アドホックネットワークは、システム１１０の自己構築型無線ネットワーク（図２０）であり、ルーターとしても機能する。各期間ｐｉにおいて、１つ又は複数のディレクトリ２１０は、それぞれの証明書の所有者のシステム１１０に対して、有効性証明をプッシュする。大きいよく選択されるコンプリメントカバーのファミリに対して、配布するために必要な有効性証明１８１０の数は、比較的小さいので、定期的な検証状態情報ネットワーク上で効率的に配布することができる。効率的に配布するために、ブロードキャスティング及びマルチキャスティングを用いることができる。いくつかの実施形態において、集合Ｆが、１つより多い証明書又は少なくとも証明書の最小数を有する場合、システム１１０のマルチキャスティンググループ２０１０は、コンプリメントカバーＣＣ（Ｕ）における集合Ｆごとに生成される。集合Ｆにおける証明書１０４を有する証明書の所有者１１０は、対応するマルチキャスティンググループに署名する。マルチキャスト伝送を介して、集合Ｆの有効性証明１８１０をグループに効率的に配布することができる。集合Ｆが、全ての証明書を含む場合、有効性証明１８１０をブロードキャストすることができる。本明細書で使用する「マルチキャスティング」という語には、ブロードキャスティングが含まれる。
【００８０】
いくつかの実施形態において、ＣＡ１２０は、マルチキャスティンググループ２０１０の可能性を考慮して、コンプリメントカバーＣＣ（Ｕ）を生成する。例えば、個別の集合Ｆをマルチキャスティンググループ２０１０ごとに作成することができる。集合Ｆは、マルチキャスティンググループ２０１０におけるステーション１１０のオペレータが所有する証明書１０４によって構成される。また、ＣＡ１２０が、失効した証明書のコンプリメントカバーＣＣＲを生成すると、ＣＡ１２０は、マルチキャスティンググループ２０１０に対応する集合Ｆを優先的に選択する。いくつかの実施形態において、集合Ｆは、マルチキャスティンググループ２０１０に対応する集合Ｆに割り当てられた高い優先順位を有する優先順位である。優先順位は、他の要因に基づいていてもよい。いくつかの実施形態において、
Ｆ１⊇Ｆ２の場合、Ｐｒｉｏｒｉｔｙ（Ｆ1）≧Ｐｒｉｏｒｉｔｙ（Ｆ２）  …（１２）
である。コンプリメントカバーＣＣＲを生成すると、ＣＡ１２０は、まず、優先順位の最も高い集合Ｆを選択し、その後、次に高い優先順位の集合Ｆを生成する。他の実施形態において、ＣＡ１２０は、ＣＣＲにおける集合Ｆの優先順位の合計を最大にする。マルチキャスティンググループを考慮する他のスキームを用いることもできる。
【００８１】
例えば、コンプリメントカバーＣＣ（Ｕ）には、図５及び図６の集合Ｆが含まれ、証明書｛１，５｝からなる集合Ｆ０も含まれるとする。証明書１及び証明書５の所有者のコンピュータシステム１１０を含む、又は、証明書１及び証明書５の所有者のコンピュータシステム１１０からなるマルチキャスティンググループ２０１０があるとする。失効した証明書の集合は、図６に示すように、｛３，８｝であるとする。最小のコンポーネントカバーＣＣＲは、上述したように、集合｛１-２｝、｛４｝、｛５-６｝、｛７｝からなる。これら４つの集合のうち、マルチキャスティンググループ２０１０に対応するものがない場合、ディレクトリ２１０は、６回のユニキャスト伝送（有効な証明書ごとに１つの伝送）を実行し、（各証明書は、個別のシステム１１０を操作する異なる所有者によって所有されているという仮定して）有効性証明１８１０を証明書の所有者にプッシュする。集合Ｆ０の優先順位が高い場合、ＣＡは、集合｛１，５｝、｛２｝、｛４｝、｛６｝、｛７｝からなるコンプリメントカバーＣＣＲを形成してもよい。マルチキャスト伝送を介して、集合｛１，５｝の証明をプッシュすることができるので、ディレクトリ２１０は、証明１８１０の証明書の所有者への伝送を、５回だけ行う必要があるだろう。
【００８２】
いくつかの実施形態において、集合Ｆは、ほとんどマルチキャスティンググループ２０１０だけに対応してもよい。集合Ｆは、グループ２０１０に関連付けられている証明書のいくつかを含むが、その全てを含むわけではない。Ｆが、システム１１０のマルチキャスティンググループ２０１０に関連付けられている証明書を１つ以上含む場合、集合Ｆは、高い優先順位を受け取る。いくつかの実施形態において、Ｐｒｉｏｒｉｔｙ（Ｆ）は、そのような証明書の数に比例する（「比例する」は、「伴って増加する」ことを意味し、「直接的に比例する」ことを必ずしも意味するものではない）。
【００８３】
いくつかの実施形態において、ＣＡ１２０は、マルチキャスティンググループを考慮しても、考慮しなくてもよいが、ステーション１１０のネットワークが、集合Ｆに基づいて、マルチキャスティンググループの少なくともいくつかを構成する。例えば、マルチキャスティンググループ２０１０を、１つより多い証明書を含む集合Ｆごとに構成してもよい。他の実施形態において、１つより多い証明書を含む各集合Ｆには、予想される頻度を表す優先順位Ｐｒｔ（Ｆ）、又は、ＦがＣＣＲのエレメントとなる期間ｐｉの予測される数が割り当てられている。マルチキャスティンググループ２０１０は、高い優先順位Ｐｒｔの集合Ｆのためだけに作成される。優先順位Ｐｒｔ（Ｆ）は、制限されることなく、
１．集合Ｆにおける証明書の数、
２．期間ｐｉにおいて集合Ｆにおける証明書の残りの失効していない期間の和Σ（Ｄ２−ｐｉ）、又は、ΣＤ２
等の多くの要因によって決まっても、多くの要因に比例してもよい。Ｄ２が、無限である場合、この和を計算する時に、ある予め定義した大きい数字を対応する証明書に割り当てることができる。
【００８４】
システム１１０が、ネットワークに加わると、システム１１０は、１つ以上のそのような集合Ｆに対して、例えば、システム１１０のオペレータが所有する証明書１０４を含む少なくとも１つの集合Ｆに対して、マルチキャスティンググループ２０１０を構成してもよい。或いは、マルチキャスティンググループは、予め形成することもでき、ネットワークに加わるシステム１１０は、システム１１０に対応する証明書を含む集合Ｆと関連付けられているマルチキャスティンググループ２０１０の１つ以上、そして、可能であれば、その全てに署名してもよい。
【００８５】
本発明は、アドホックネットワークに限定されるものではない。
【００８６】
＜有効性証明のキャッシング＞
少なくともいくつかのシステム１１０がルーターとして機能するアドホックネットワーク及び他のネットワークにおいて、検証者システム１１０（例えば、１１０.１）が、（可能性としては、システム１１０.１のオペレータが所有していない証明書に対する）証明書の有効状況を必要とする時、検証者の要求１５０（図１）は、ディレクトリ２１０又はＣＡ１２０へのパス上のいくつかの他のシステム１１０上を移動してもよい。そのため、いくつかの実施形態において、検証者システム１１０.１が、有効性証明１８１０を受信すると、システム１１０.１は、キャッシュ２１１０における有効性証明をキャッシュしてもよい（図２１Ａ）。他の検証者システム１１０.２が、同じ証明書又は（コンプリメントカバーが用いられる場合）同じ集合Ｆにおける証明書に対して、要求１５０を発行し、かかる要求が、キャッシングシステム１１０.１に到達すると、システム１１０.１は、キャッシュした応答を、ディレクトリ２１０又はＣＡ１２０に転送せずに、システム１１０.２に送信してもよい。キャッシュ２１１０は、サイズに制限があるので、キャッシングシステム１１０.１は、当該期間ｐｉに発行された多くの要求１５０を満たすと期待される選択した有効性証明１８１０だけをキャッシュしてもよい。いくつかの実施形態において、システム１１０.１は、システム１１０.１が他のシステム１１０に最後に提供した有効性証明の証明書の有効性証明１８１０に対して、優先順位を与える「最も長時間使用されなかったデータから削除される」というキャッシングポリシーを用いる。公知である又は発明される他のキャッシングの方針も用いることができる。いくつかの実施形態において、集合Ｆには、各証明１８１０をキャッシュすることが望ましいことを表すキャッシングの優先順位Ｐｒｔ（Ｆ）が割り当てられている。いくつかの実施形態において、キャッシングの優先順位Ｐｒｔ（Ｆ）は、
１．集合Ｆにおける証明書の数、
２．期間ｐｉにおいて、集合Ｆにおける証明書の残りの失効していない期間の和Σ（Ｄ２−ｐｉ）、又は、ΣＤ２、
に比例する。Ｄ２が、無限である場合、この和を計算する時に、予め定された大きい数字を、対応する証明書に割り当てることができる。
【００８７】
システム１１０.１が、証明１８１０を受信すると（図２１Ｂのステップ２１２０）、検証者１１０.１は、証明１８１０を処理し、証明書の有効性を検証する（本発明は、どの検証方法にも限定されない）。また、システム１１０.１は、ステップ２１３０において、証明１８１０をキャッシュするべきかどうかを決定する。キャッシングの決定は、証明１８１０に対応する集合Ｆのキャッシングの優先順位Ｐｒｔ１（Ｆ）に基づいているが、キャッシュ２１１０のメモリの空き容量等の他の要因に基づいてもよい。いくつかの実施形態において、証明１８１０が、ステップ２１２０において、証明書の有効性を証明することができない場合、キャッシングの決定は、否定的である。キャッシングの決定が、肯定的である場合、証明１８１０は、システム１１０.１のキャッシュ２１１０にキャッシュされ（ステップ２１４０）、キャッシングの決定が、肯定的でなければ、証明１８１０は、廃棄される（ステップ２１５０）。
【００８８】
キャッシングは、有効性証明が証明書の所有者にプッシュされる場合に限定されない。有効性証明１８１０は、図８又は図１５に示す証明８３０と同一であってもよいし違っていてもよい。キャッシングは、他のシステム１１０からの要求１５０を取得する非ルーターシステム１１０.１によって行ってもよい。例えば、システム１１０.２が、ＣＡ又はディレクトリ２１０から有効性証明を取得することに（ネットワークの問題、又は、他の理由で）失敗した場合、又は、システム１１０.２が、有効性証明を取得したが、有効性証明に失敗した場合（例えば、計算したターゲットが、証明書のターゲットと一致しなかった場合）、システム１１０.２は、ブロードキャスト要求を、ローカルネットワークに対して発行し、証明をキャッシュしている他のシステム１１０.１から、有効性証明１８１０を受信してもよい。
【００８９】
いくつかの実施形態において、有効性証明が、証明書の所有者に対してプッシュされ、証明書の所有者（例えば、１１０.２）が、ある期間ｐｉの間の有効状況の情報１８１０が配布されてからネットワークに入るシステムにおいて、図２１のキャッシングスキームが用いられている。証明書の所有者１１０.２は、要求１５０を通じて、ＣＡ１２０からの有効性証明１８１０を要求する（図１）。中間ノード１１０.１が、有効状況情報のキャッシュ２１１０を保持する場合、かかる中間ノードは、要求された証明書の有効状況情報のキャッシュを検索する。かかる検索が成功した場合、各有効状況情報は、要求者に送信される。かかる検索が成功しなかった場合、要求は、ＣＡ１２０に転送される。
【００９０】
＜新規証明書のダイナミックな導入＞
設定段階後に、新規証明書を追加できるようにすることが望ましい（例えば、図９及び図１６で図示した段階）。ハッシュ連鎖（１）及びハッシュツリー１２１０（図１２乃至図１４）は、それぞれ予め決められた数の期間ｐｉを収容する。いくつかの実施形態において、設定後のタイミングでも新規証明書を追加のｐｉの期間と共に追加することができる証明書失効システムが提供されている。Ｍは、設定フェーズにおける証明書の最大数であるものとし、各証明書は、期間ｐｉの番号Ｔｖに対して発行されるものとする（Ｔｖは、最大有効期間Ｄ２-Ｄ１であり、ｐｉの期間の数として表される）。期間ｐｉは、図２２の時間軸２２１０に記されている。設定フェーズでは、証明書の実際の数が、Ｍよりも少ない場合でも、ＣＡ１２０は、Ｍ個の証明書スロットを作成する。いくつかのスロットには、実際の証明書が割り当てられ、残りのスロットは空いている。図２３Ａは、図９及び図１６の設定ステップが、どのように新規証明書をダイナミックに導入するようになっているのかを示す。残りのステップは、図示していないが、図９及び図１６と同じである。ステップ９１４において、ＣＡ１２０は、（コンプリメントカバーを使う場合は）Ｍ個の証明書スロットのコンプリメントカバーＣＣ（Ｕ）を作成する（しかし、本発明は、コンプリメントカバーを使用することに限定されるものではない）。ステップ９１８において、ＣＡ１２０は、カバーＣＣ（Ｕ）における集合Ｆごとの期間ｐｉの数Ｔｄに対して、ハッシュ連鎖（１）又はハッシュツリー１２１０を生成する。ここで、Ｔｄ＞Ｔｖとする。図２２の例においては、Ｔｄ＝２＊Ｔｖである。残りの設定ステップ９２２及びステップ９３０を実行してもよい。或いは、本発明について、ハッシュツリー７１０無しで実行することもできる。
【００９１】
ハッシュ連鎖（１）を用いる場合、ｘをシードとすると、ターゲットｃ０＝ｆＴｄ（ｘ）である。検証者１１０に提供された有効性証明には、トークンｃｉ及び関数ｆがｉ-トークンｃｉ（Ｆ）に適用される回数ｊが含まれている。検証者は、ｆｊ（ｃｉ）＝ｃ０を確認する。
【００９２】
本明細書では、期間１から期間Ｔｖまでを「Ｔｖウィンドウ」と呼ぶ。証明書が、このウィンドウにおいて生成された場合、かかる証明書は、Ｔｄの時点又はＴｄの時点よりも前に失効するので、ＣＡ１２０がステップ９１８において生成したデータ構造（ハッシュ連鎖（１）又はハッシュツリー１２１０）と共に用られることができる。より一般的には、Ｔｖウィンドウとは、多くのｐｉの期間のうちの予め決められた時間間隔で既存のデータ構造に新規証明書を収容できる、すなわち、証明書がそのデータ構造によって提供された最後のｐｉの期間を越えて存続することのないウィンドウのことである。図２２の実施形態において、最初のＴｖウィンドウは、ｐｉ＝１からＰｉ＝Ｔｄ-Ｔｖまでのウィンドウである。図２２において、証明書の失効する時間Ｄ２を×印で示す。
【００９３】
「Ｔｄウィンドウ」は、対応するＴｖウィンドウと同時に始まり、後のＴｄ期間で終わるが、これは、Ｔｄウィンドウで作成された各新規証明書の最大有効期限の外側の境界を示している。
【００９４】
図２３Ｂは、設定段階後のＣＡ１２０のオペレーションを示す。新規証明書が、ステップ２３３０で、現行のＴｖウィンドウにおいて要求されている場合、及び、空の証明書スロットが、存在する場合（ステップ２３４０）、ＣＡ１２０は、新規証明書を空のスロットに割り当てる（ステップ２３５０）。新規証明書は、現行のｐｉで始まるＴｖ期間ｐｉに対して有効であり、現行のＴｖウィンドウの後に失効してもよい。空のスロットがない場合、ＣＡ１２０は、設定を再び行う（ステップ２３６０）。特に、新規のコンプリメントカバーＣＣ（Ｕ）をＭ個の新規証明書のスロット用に作成し、ハッシュ連鎖（１）又はハッシュツリー１２１０を、現行（又は、次の）期間ｐｉで始まるＴｄ期間ｐｉの新規のＴｖウィンドウ用の新規のコンプリメントカバーＣＣの新規の集合Ｆ用に作成する。新規Ｔｖウィンドウは、現行のＴｖウィンドウになる。残りの設定ステップ（例えば、ツリー７１０の作成）を実行することもできる。制御は、ステップ２３３０に戻る。ステップ２３４０に空のスロットが存在するので（Ｍ個の新規スロットが作成したばかりなので）、新規証明書は、新規スロットのうちの１つに割り当てられる。制御は、ステップ２３３０に戻る。
【００９５】
現行のＴｖウィンドウが終了するまで、ＣＡ１２０で空のスロットが不足しなかったので、ステップ２３６０は、ウィンドウの最後で行われた。
【００９６】
ＣＡ１２０及びディレクトリ２１０は、現行のＴｖウィンドウ及び期限がまだ失効していない先行するＴｄウィンドウの全ての両方に対して有効性及び証明を提供する。Ｔｄウィンドウが失効すると、対応するデータ構造は再び使えるようになる。失効した証明書と関連付けられているデータ構造（例えば、ハッシュ連鎖（１）又はハッシュツリー１２１０）については、対応するＴｄウィンドウが失効する前であっても再利用することができる。
【００９７】
図２４は、相異なる証明書１０４が、相異なる最大有効期限Ｄ２-Ｄ１（図１）を持つ実施形態を示す。最大有効期限を、それぞれの時間ｔ１、ｔ２において作成された証明書に対して、Ｔｖ１、Ｔｖ２として示す。本実施形態において、最大有効期限は、少なくとも予め決められた数Ｔｖｍｉｎと同じ長さであることが要求される。図２５は、設定ステップ９１８が、本実施形態用にどのように修正されたかを示す。ステップ９１８において、ＣＡ１２０は、Ｍ個の証明書スロットに対する期間ｐｉの決められた数Ｔｄ＞Ｔｖｍｉｎに対するハッシュ連鎖（１）又はハッシュツリー１２１０を作成する。そのため、証明書は、時間（Ｔｄ−Ｔｖｍｉｎ）まで設定データ構造に追加することができ、それにより、第１のＴｖウィンドウが終了する。任意の期間ｐｉにおいて、ハッシュ連鎖、又は、ハッシュツリーデータ構造に付け加えられた証明書を、ｐｉ期間のうちの（Ｔｄ-ｐｉ）までのデータ構造が収容することができる。いくつかの実施形態において、例えば、Ｄ２を（Ｄ１+Ｔｄ-ｐｉ）を設定することによって、証明書の最大有効時間は、（Ｔｄ-ｐｉ）に設定される。他の実施形態において、最大有効時間は、ｐｉ期間のうちの予め決められた数Ｔｖｍａｘ＞Ｔｖｍｉｎを越えてはならない。いくつかの実施形態においては、Ｔｄ＞Ｔｖｍａｘである。設定段階の後のＣＡのオペレーションを、図２３に示す。
【００９８】
本発明は、ハッシュツリー１２１０、又は、ハッシュ連鎖に限定されない。
【００９９】
＜配布された証明書認証局＞
単一のＣＡ１２０は、サービス拒絶攻撃に脆弱であり、ネットワークエラーの場合においては、使用不能である。いくつかの実施形態においては、以下に説明する配布された証明書認証局（Ｄｉｓｔｒｉｂｕｔｅｄ  Ｃｅｒｔｉｆｉｃａｔｅ  Ａｕｔｈｏｒｉｔｙ）（ｄｉｓｔＣＡ）が、システム全体の安全性を維持しながら、そのような欠点を最小化している。
【０１００】
ｄｉｓｔＣＡには、ＣＡ１２０（図２６）及びＳｕｂ-ＣＡ２６１０の番号「Ｓ」（すなわち、２６１０.１…２６１０.Ｓ）が含まれる。設定フェーズにおいて、Ｓｕｂ-ＣＡ２６１０は、ＣＡ１２０から秘密のデータを受け取るが、かかるデータは、暗号化されている。相異なる期間ｐｉに対応するデータは、復号化のために相異なる鍵が必要となるように暗号化されている。ＣＡ１２０は、期間ｐｉの開始時又はその少し前に、期間ｐｉごとの要求された復号鍵を配布する。いくつかの実施形態においては、配布されたＣＡは、以下の優れた点を有する。
【０１０１】
１．検証者１１０が、Ｓｕｂ-ＣＡ２６１０から証明書の有効性証明又は無効性の証明を取得できるので、ネットワークに不具合が起こった場合に、有効性又は無効性の証明を取得する機会が多くなる。
【０１０２】
２．以下に説明するように、各期間ｐｉにおいてＣＡ１２０と交換するデータが少なくて済むので、各期間ｐｉおいて成功したサービス拒絶攻撃に対してより強い（Ｓｕｂ-ＣＡ２６１０に配布された復号鍵は、ｉ-トークン等の全期間データよりも小さい）。
【０１０３】
３．Ｓｕｂ-ＣＡ２６１０の１つを危険に曝すことで、システム全体を危険に曝さない。
【０１０４】
４．危殆化したＳｕｂ-ＣＡ２６１０は、ＣＡ１２０の制御に戻った後に再開することができる。
【０１０５】
５．検証者が、証明書を検証するために行う追加的な計算作業は、デジタル証明書の計算に比べると楽である。
【０１０６】
いくつかの実施形態では、上述した全ての利点が提供されるわけではない。また、いくつかの実施形態では、以下に説明するように更なる利点が提供される。
【０１０７】
図２７は、ＣＡの設定フェーズを示す。ステップ２７１０において、ＣＡ１２０は、ｔに対する有効期限ｐ１、ｐ２、…ｐｔを構築する。ステップ２７１４において、ＣＡ１２０は、期間ｐｉごとに、Ｓｕｂ-ＣＡを検証するためのデータ構造を生成する。ここで、証明書の検証と同じ種類の構造を用いることができる。例えば、図１乃至図１７を参照にされたい。図２６及び図２７の例では、ハッシュツリー２６１４.１…２６１４.Ｓは、Ｓｕｂ-ＣＡ２６１０.１…Ｓｕｂ-ＣＡ２６１０.Ｓのそれぞれに対して作成されている。各ツリー２６１４は、図１２乃至図１４のうちの１つにおけるそれぞれの期間ｐ１…ｐｔに対するグレイ頂点ｇｖ（１）…ｇｖ（ｔ）を有するツリー１２１０と同じ形式である。図２６において、ツリー２６１４は、接地した密なハッシュツリー（図１４における「ＧＤＨ」）であるが、他の種類のツリー又は単なるハッシュ連鎖（１）を用いてもよい。リーフ値は、ツリー２６１４ごとにランダムに個別に生成される。Ｗｊが、ツリー２６１４.ｊのルート値を示すものとする。ここで、Ｗｊの値を有効ターゲットと呼ぶ。そのリーフ値が有効ターゲットＷｊである（図７Ａ又は図１１に示すツリー７１０と同じ形式である）ハッシュツリー２６１８が定義されている。Ｒｓｕｂは、各証明書１０４に挿入されるツリー２６１８.Ｒｓｕｂのルート値を示すものとする。
【０１０８】
本実施形態では、Ｓｕｂ-ＣＡに対する失効ターゲットＮ１を使用しない。有効性証明が不足していることは、Ｓｕｂ-ＣＡが無効であることの証明であると見なされる。他の実施形態では、Ｓｕｂ-ＣＡに対して明確な失効の証明を用いる。上述したように、いくつかの実施形態では、無効なＳｕｂ-ＣＡは、連続する期間ｐｉにおいて再開することができるので、いくつかの実施形態では、失効証明は、有効性証明に適切な技術を用いて構築される。例えば、２６１４及び２６１８のようなツリーは、各期間ｐｉにおけるＳｕｂ-ＣＡの無効性を証明するために用いられることができる。
【０１０９】
ステップ２７１８において、ＣＡ１２０は、証明書の検証及び失効のためのデータ構造を作成する。証明書を検証する技術及び証明書を失効する技術は、図１乃至図２５に関して上述した技術や公知である又は発明される他の技術を含み、そのどれを用いてもよい。図２６の例では、個別のデータ構造２６２２.ｊが、それぞれのＳｕｂ-ＣＡ２６１０.ｊに対する証明書ごとに作成される（その結果、１つのＳｕｂ-ＣＡが危殆化している場合、残りのＳｕｂ-ＣＡのデータ構造２６２２は、安全なままである）。例えば、各構造２６２２.ｊには、（コンプリメントカバーが使用されなければ、）証明書の期間ｐｉの間のツリー１２１０、又は、（ａ）証明書を含むコンプリメントカバーの集合Ｆのツリー１２１０と（ｂ）ツリー１２１０のターゲット上のハッシュツリー７１０との組み合わせを含むことができる。図７Ａ乃至図１７を参照にされたい。構造２６１２.ｊごとに、対応するツリー１２１０は、異なっておりランダムに生成されたリーフ値を有するので、相異なる構造２６１６.ｊは、お互いに回復不可能である。図２６において、各構造２６２２.ｊは、自分の検証ターゲットＹｊ(Ｙｊは、対応するツリー７１０、ツリー１２１０のルート値又はハッシュ連鎖のターゲット)、失効シードＮ０ｊ、及び、失効ターゲットＮ１ｊ＝ｆ（Ｎ０ｊ）を有する。ＣＡ１２０は、ルート値Ｙｊ上のハッシュツリー２６２６（例えば、図７Ａ又は図１１）を定義する。ＲＣが、ツリー２６２６のルート値を表すものとする。ＲＣは、証明書に挿入される。
【０１１０】
また、ＣＡ１２０は、失効ターゲットＮｉｊ上のハッシュツリー２６３０（例えば、図７Ａ又は図１１）も定義する。ＮＣが、ツリー２６３０のルート値を示すとする。ＮＣは、証明書に挿入される。証明書は、１０４-ＳｉｇＣＡにおいて示したように、ＣＡ１２０によって署名される。
【０１１１】
証明書検証構造には、Ｓｕｂ-ＣＡに共通する構造、例えば、同じコンプリメントカバーが全てのＳｕｂ-ＣＡに対して用いられる場合に、コンプリメントカバーＣＣ（Ｕ）を隠す構造を含んでもよい。
【０１１２】
いくつかの実施形態では、個別の構造２６２２.ｊが、証明書ごとに作成されるのではなく、コンプリメントカバーの集合ごとに作成されている。これは、例えば、図４乃至図６のシステムに対して行うことができる。また、各構造２６２２.ｊは、複数の検証ターゲット及び／又は失効ターゲットを含んでいてもよい。個別のハッシュツリー２６２６を、各構造２６２２.ｊからのターゲットの１つを含むターゲットの集合に対して作成することができる。例えば、証明書にターゲットｃ０（Ｆ）が含まれる場合、個別のハッシュツリー２６２６を、全てのＳｕｂ-ＣＡに対して与えられた集合Ｆに対する全てのターゲットｃ０（Ｆ）の上に作成することができる。或いは、単一のツリー２６２６を、全てのターゲットに対して作成することもできる。いくつかの実施形態は、ターゲットを持たず、ツリー２６２６もない。多くの検証構造の種類を用いることができる。
【０１１３】
ステップ２７２２において、ＣＡ１２０は、Ｓｕｂ-ＣＡ２６１０.ｊごとに、暗号鍵及び復号鍵２６４０.ｊを生成する。本実施形態では、Ｓｕｂ-ＣＡ２６１０.ｊごとに、１つの復号鍵を、いくつかの連続する期間ｐｉに対して用いる。例えば、Ｐ＝２５の論理区分に細分化された３６５個の期間ｐｉがあるとする。
【数１】
2008512066.tif 000003
【０１１４】
なので、期間ｐ１から期間ｐ１５までを区分１に、期間ｐ１６から期間ｐ３０を区分２に、といった具合に位置づけることができる。最後の区分２５は、期間ｐ３６１から期間３６５までを持つ。本発明は、特定の数の期間を有する区分に限定されるものではない。各Ｓｕｂ-ＣＡ２６１０.ｊ及び各区分ｋに対して、ＣＡ１２０は、復号鍵ＤＫ.ｊ.ｋを生成する。暗号スキームは、対称（すなわち、暗号鍵が復号鍵と同じ）であっても、非対称であってもよい。
【０１１５】
ステップ２７２６において、ＣＡ１２０は、データ２６２２及びデータ２６２６を使って、Ｓｕｂ-ＣＡ２６１０．ｊごとの証明書検証データ２６５０.ｊを作成する。ＣＡ１２０は、データ２６５０.ｊを暗号化して、それぞれのＳｕｂ-ＣＡ２６１０.ｊに送信する。ｊごとに、データ２６５０.ｊは、各期間ｐｉに対するデータ構造２６６０を含む。いくつかの実施形態では、データ２６６０は、有効性証明８３０に対するデータ８３０Ｖ（図８及び図１５）と同じである。証明書１０４ごとに、ツリー１２１０を用い、コンプリメントカバーを使用しない例において、データ２６６０は、Ｖａｌｕｅ（ｇｖ（ｉ））及びＶａｌｕｅ（ＣｏＮｏｄｅｓ（ｇｖ（ｉ））から構成される。いくつかの実施形態では、期間ｐｉごとのデータ２６６０の大きさを、共通ノード値及び先行する期間ｐｉに対するデータ２６６０に存在する他の情報を削除することで縮小してもよい。
【０１１６】
Ｓｕｂ-ＣＡ２６１０.ｊごと及び区分ｋごとに、データ２６６０は、鍵ＤＫ.ｊ.ｋで復号されるために暗号化される。
【０１１７】
オプションとして、証明書１０４ごとに、ＣＡ１２０は、各Ｓｕｂ-ＣＡ２６１０.ｊ、証明書の所有者、及び／又は、他者に対して、対応するターゲットＹｊから検証ターゲットＲｃを計算するために必要なデータ２６６２を配布する。データ２６６２は、Ｖａｌｕｅ（ＣｏＮｏｄｅｓ（Ｌｅａｆ（Ｙｊ）））を含んでいてもよい。ここで、Ｌｅａｆ（Ｙｊ）は、Ｓｕｂ−ＣＡ２６１０.ｊに対応するツリー２６２６のリーフである。オプションとして、証明書１０４ごとに、ＣＡ１２０は、各Ｓｕｂ-ＣＡ２６１０.ｊ、証明書の所有者、及び／又は、他者に対して、対応するターゲットＮｉｊから失効ターゲットＮＣを計算するために必要なデータ２６６４を配布する。データ２６６４は、Ｖａｌｕｅ（ＣｏＮｏｄｅｓ（Ｌｅａｆ（Ｎｉｊ）））を含んでいてもよい。ここで、Ｌｅａｆ（Ｎｉｊ）は、Ｓｕｂ-ＣＡ２６１０.ｊに対応するツリー２６３０のリーフである。オプションとして、ＣＡ１２０は、各Ｓｕｂ-ＣＡ２６１０.ｊ、各証明書の所有者、及び／又は、他者に対して、対応するターゲットＷｊからターゲットＲｓｕｂを計算するために必要なデータ２６６８を配布する。データ２６６４は、Ｖａｌｕｅ（ＣｏＮｏｄｅｓ（Ｌｅａｆ（Ｗｊ）））を含んでいてもよい。ここで、Ｌｅａｆ（Ｗｊ）は、Ｓｕｂ-ＣＡ２６１０.ｊに対応するツリー２６１８のリーフである。データ２６６２、データ２６６４、データ２６６８は、暗号化する必要がない。オプションとして、ＣＡ１２０は、検証ターゲットＷｊ、Ｙｊ、Ｎｉｊの全て、又は、いくつかを公開することができる。ＣＡ１２０は、これらのターゲットを、ｊごとに、それぞれのＳｕｂ-ＣＡ２６１０.ｊに対して提供することもできる。
【０１１８】
各期間ｐｉの開始時又はその少し前に、ｐｉが、区分ｋにおいて最初の期間の場合、ＣＡ１２０は、ｊごとに、復号鍵ＤＫ.ｊ.ｋを、Ｓｕｂ-ＣＡ２６１０.ｊに対して配布する。Ｓｕｂ-ＣＡが危殆化し、ＣＡ１２０の制御に戻らない場合、ＣＡ１２０は、ＣＡからの復号鍵を保留にしてもよい。
【０１１９】
Ｓｕｂ-ＣＡ２６１０.ｊが、危殆化している場合、敵が全てのデータ構造２６５０.ｊへのアクセスを持っているかもしれない。しかしながら、データ２６６０は、暗号化されており、敵は、後の区分に対するデータ２６６０を復号できないので、Ｓｕｂ-ＣＡ２６１０.ｊが、ＣＡの制御に一旦戻ったら、ＣＡ１２０は、次の区分の最初の期間ｐｉにおけるＳｕｂ-ＣＡを再開することができる。再開とは、ＣＡ１２０が、（ａ）Ｓｕｂ-ＣＡの有効性証明２６７２を提供し、かつ、（ｂ）Ｓｕｂ-ＣＡが、ＣＡの制御下にないときに保留する場合、及び、先行する区分に対するデータ２６６０が、証明書の有効性証明を構成するために必要な場合に、（ｂ１）現行の区分ｋに対する復号鍵ＤＫ.ｊ.ｋ、及び、（ｂ２）全ての先行する区分に対する復号鍵を、Ｓｕｂ-ＣＡに提供することを意味する。
【０１２０】
各期間ｐｉにおいて又はその少し前に、ＣＡは、各Ｓｕｂ-ＣＡ２６１０.ｊ、各証明書の所有者、及び／又は、他者に対して、期間ｐｉにおけるＣＡの有効性を証明するために、有効性証明２６７２を送信する。有効性証明２６７２には、対応するツリー２６１４に対するＶａｌｕｅ（ｇｖ（ｉ））及びＶａｌｕｅ（ＣｏＮｏｄｅｓ（ｇｖ（ｉ））が含まれる。また、ＣＡ１２０は、各Ｓｕｂ-ＣＡ２６１０.ｊに対して、先行する期間ｐｉ（又は、先行する期間のうちのどこか）において失効した証明書１４０ごとの失効シード値Ｎ０ｊを送信する。
【０１２１】
区分の最初の期間である各期間ｐｉにおいて又はその少し前に、危殆化していない各Ｓｕｂ-ＣＡ２６１０は、対応する復号鍵を使って、区間に対する検証データ２６６０を復号する。
【０１２２】
期間ｐｉにおいて、検証者１１０（図２８）は、Ｓｕｂ-ＣＡ２６１０.ｊ又は他の認証局から、Ｓｕｂ-ＣＡの検証証明２８１０を受け取る。検証者は、また、興味のある証明書に対して、証明書有効性証明２８２０か証明書失効証明２６３０のどちらかも受け取る。有効性証明２８１０には、Ｓｕｂ-ＣＡ２６１０.ｊに対するデータ２６６８及びデータ２６７２（図２６）を含む。検証者は、データ２６７２からＳｕｂ-ＣＡのターゲットＷｊを計算し（リスティング１参照）、データ２６６８からターゲットＲｓｕｂを計算する。計算した値Ｒｓｕｂが、証明書のＲｓｕｂの値と一致する場合、Ｓｕｂ-ＣＡは有効であるとみなされる。一致しなかった場合、検証者は、他のソースからＳｕｂ-ＣＡの有効証明を探してもよいし、又は、単にＳｕｂ-ＣＡは無効であるとみなし、他のＳｕｂ-ＣＡから証明書の有効性データを探してもよい。
【０１２３】
証明書有効性証明２８２０には、有効性証明８３０が含まれる。有効性証明８３０は、復号化されたデータ２６６０から構成されている。証明８３０の形式は、基礎となる証明書有効性スキームにより、例えば、図８又は図１５のようなものでよい。例えば、図２のスキーム、及び、公知である又は発明されるスキームを含む他の検証スキームを用いることもできる。検証者が、有効性証明２８２０を受け取る場合、かかる検証者は、データ８３０からターゲットＹｊを計算し、データ２６６２からターゲットＲＣを計算する。計算した値ＲＣが、証明書のＲＣの値と一致する場合、かかる証明書は有効であるとみなされる。一致しなかった場合、かかる証明書は、無効であるとみなされるか、又は、検証者は、例えば、他のＳｕｂ-ＣＡと接続して他の証明を探してもよい。
【０１２４】
証明書失効証明２８３０には、失効シード値Ｎ０ｊ及びデータ２６６４が含まれる。検証者が、失効証明２８３０を受け取る場合、かかる検証者は、失効ターゲットＮ１ｊ＝ｆ（Ｎ０ｊ）を計算し、データ２６６４からターゲットＮＣを計算する。計算したＮＣの値が、証明書のＮＣの値と一致する場合、かかる証明書は失効したとみなられる。一致しなかった場合、検証者は、証明書は失効したとみなしてもよいし、又は、例えば、他のＳｕｂ-ＣＡと接続して他の証明を探してもよい。
【０１２５】
ターゲットが、共通ノードの値から計算される場合（例えば、ターゲットＷｊを計算する必要がある時）において、検証者が、先行する期間ｐｉに対する同じ証明書を既に検証し共通ノードの値をキャッシュしている場合、及び、期間ｐｉ及び現行の期間ｐｉに対するグレイ頂点が、共通ノードのうちの１つの値として、ルート値がキャッシュされる共通のサブツリーにある場合、検証者は、サブツリーに対するルート値を計算し、ツリーに対するルート値を計算するのではなく、それをキャッシュした値と比較するだけでよい。例えば、サブツリーのルート値を、ツリー２６１４.ｊに対してキャッシュしている場合、（検証者が、ツリー構造及びタイプ（５）の単なるリスティングでないものに関する全ての関連情報を持つという条件において）検証者は、Ｗｊ、又は、Ｒｓｕｂを計算する必要がない。
【０１２６】
いくつかの実施形態では、ディレクトリ２１０（図１５）を用いる。Ｓｕｂ-ＣＡは、有効性証明８１０、失効証明８２０、及び、可能性としてはＳｕｂ-ＣＡの有効性証明２８１０を形成し、それらを、ディレクトリ２１０に対して各期間ｐｉにおいて配布する。ディレクトリは、証明２８２０及び証明２８３０を構成し、それらを検証者に送信する。いくつかの実施形態において、検証者は、１つの有効なＳｕｂ-ＣＡのみからの有効性証明を必要とするので、ディレクトリ２１０は、データを、１つ又は２つのＳｕｂ-ＣＡからのみ受け取る。他の証明の配布スキームも可能である。特に、データ２８１０、データ２８２０、データ２８３０のいくつか、又は、全てを、他のシステムが、キャッシュしている場合、ＣＡ、証明書の所有者、又は、他者、例えば、アドホックネットワークの他のシステム１１０等によって、データ２８１０、データ２８２０、データ２８３０のいくつか、又は、全てが提供される。
【０１２７】
いくつかの実施形態において、各区分は、１つの期間ｐｉから成る。相異なるＳｕｂ-ＣＡ２６１０は、相異なる復号鍵ＤＫ.ｊ.ｉを、期間ｐｉごとに有する。そして、Ｓｕｂ-ＣＡの有効性を検証することは省略される。Ｓｕｂ-ＣＡが危殆化している場合、ＣＡ１２０は、復号鍵をＳｕｂ-ＣＡに送信することを停止して、かかるＳｕｂ-ＣＡを失効させる。Ｓｕｂ-ＣＡが、ＣＡの制御下に戻ったら、ＣＡは、保持している復号鍵を、かかるＳｕｂ-ＣＡに送信して、かかるＳｕｂ-ＣＡを再開することができる。よって、データ２６１４、データ２６１８、データ２６６８は省略することができる。
【０１２８】
本発明は、上述した実施形態に限定されるものではない。本発明は、如何なる特定のハッシュ関数、又は、（計算は容易だが一方向であり、衝突に対して耐性を持つ）暗号化関数に限定されるものではない。いくつかの実施形態において、関数ｆ又はＨは、同じイメージに異なるｘ及びｙを見つけることが困難であるという意味においてではなく、ｘ及びｙが、関数のドメインから一様に引き出された場合において、両者が、同じイメージを持つであろう確率は低いことが望ましい。すなわち、
ｐ｛Ｈ（ｘ）＝Ｈ（ｙ）｝≦α
である。ここで、αは、小さい定数（例えば、１/１０、又は、１/１００、又は、２−２５、又は、２−５０、又は、２−８０、又は、２−１６０、又は、その他の値）である。有効性証明に用いた技術のいくつか又は全ては、無効性証明にも用いることができ、その逆も可能である。ＣＡ、Ｓｕｂ-ＣＡ、ディレクトリ、及びシステム１１０は、１つのネットワーク又は複数のネットワークを介して組み込まれたソフトウェアでプログラム可能なコンピュータシステム、又は、配線で接続されたコンピュータシステムを含んでもよい。各関数ｆ又はＨは、コンピュータシステムが実行する評価方法を表す。本発明は、フローチャートに示したステップの順番に限定されるものではない。なぜならば、ステップの順番は、交換可能なこともあり、異なるステップを、さらに並行して実行してもよい。他の実施形態及び変形例も、添付した請求の範囲によって定義される様に発明の範囲内にある。
【図面の簡単な説明】
【０１２９】
【図１】従来技術による証明書失効スキームを示す図である。
【図２】従来技術による証明書失効スキームを示す図である。
【図３】従来技術による証明書失効スキームのための証明書の集合を示す図である。
【図４】従来技術による証明書失効スキームのための証明書の集合を示す図である。
【図５】従来技術による証明書失効スキームのためのコンピュータデータ構造を示す図である。
【図６】従来技術による証明書失効スキームのためのコンピュータデータ構造を示す図である。
【図７Ａ】本発明のいくつかの実施形態による証明書失効スキームのためのコンピュータデータ構造を示す図である。
【図７Ｂ】本発明のいくつかの実施形態による証明書失効スキームのためのコンピュータデータ構造を示す図である。
【図８】本発明のいくつかの実施形態による証明書失効スキームのためのネットワーク化されたコンピュータシステム及びデータ構造を示すブロック図である。
【図９】本発明のいくつかの実施形態による証明書失効スキームのためのフローチャートである。
【図１０】本発明のいくつかの実施形態による証明書失効スキームのためのフローチャートである。
【図１１】本発明のいくつかの実施形態による証明書失効スキームのためのコンピュータデータ構造を示す図である。
【図１２】本発明のいくつかの実施形態による証明書失効スキームのためのコンピュータデータ構造を示す図である。
【図１３】本発明のいくつかの実施形態による証明書失効スキームのためのコンピュータデータ構造を示す図である。
【図１４】本発明のいくつかの実施形態による証明書失効スキームのためのコンピュータデータ構造を示す図である。
【図１５】本発明のいくつかの実施形態による証明書失効スキームのためのネットワーク化されたコンピュータシステム及びデータ構造を示すブロック図である。
【図１６】本発明のいくつかの実施形態による証明書失効スキームのフローチャートである。
【図１７】本発明のいくつかの実施形態による証明書失効スキームのフローチャートである。
【図１８】本発明のいくつかの実施形態による証明書失効スキームのためのネットワーク化されたコンピュータシステム及びデータ構造を示すブロック図である。
【図１９】本発明のいくつかの実施形態による証明書失効スキームのためのコンピュータデータ構造を示す図である。
【図２０】本発明のいくつかの実施形態による証明書失効スキームのためのネットワーク化されたコンピュータシステム及びデータ構造を示すブロック図である。
【図２１Ａ】本発明のいくつかの実施形態によるデータを有するコンピュータシステムを示す図である。
【図２１Ｂ】本発明のいくつかの実施形態による証明書失効スキームのフローチャートである。
【図２２】本発明のいくつかの実施形態による証明書失効スキームのためのタイミング図である。
【図２３Ａ】本発明のいくつかの実施形態による証明書失効スキームのフローチャートである。
【図２３Ｂ】本発明のいくつかの実施形態による証明書失効スキームのフローチャートである。
【図２４】本発明のいくつかの実施形態による証明書失効スキームのタイミング図である。
【図２５】本発明のいくつかの実施形態による証明書失効スキームのフローチャートである。
【図２６】本発明のいくつかの実施形態による証明書失効スキームのネットワーク化されたコンピュータシステム及びデータ構造を示すブロック図である。
【図２７】本発明のいくつかの実施形態による証明書失効スキームのフローチャートである。
【図２８】本発明のいくつかの実施形態による証明書失効スキームのネットワーク化されたコンピュータシステム及びデータ構造を示すブロック図である。
【図１】
2008512066.tif 000004
【図２】
2008512066.tif 000005
【図３】
2008512066.tif 000006
【図４】
2008512066.tif 000007
【図５】
2008512066.tif 000008
【図６】
2008512066.tif 000009
【図７Ａ】
2008512066.tif 000010
【図７Ｂ】
2008512066.tif 000011
【図８】
2008512066.tif 000012
【図９】
2008512066.tif 000013
【図１０】
2008512066.tif 000014
【図１１】
2008512066.tif 000015
【図１２】
2008512066.tif 000016
【図１３】
2008512066.tif 000017
【図１４】
2008512066.tif 000018
【図１５】
2008512066.tif 000019
【図１６】
2008512066.tif 000020
【図１７】
2008512066.tif 000021
【図１８】
2008512066.tif 000022
【図１９】
2008512066.tif 000023
【図２０】
2008512066.tif 000024
【図２１Ａ】
2008512066.tif 000025
【図２１Ｂ】
2008512066.tif 000026
【図２２】
2008512066.tif 000027
【図２３Ａ】
2008512066.tif 000028
【図２３Ｂ】
2008512066.tif 000029
【図２４】
2008512066.tif 000030
【図２５】
2008512066.tif 000031
【図２６】
2008512066.tif 000032
【図２７】
2008512066.tif 000033
【図２８】
2008512066.tif 000034
【手続補正書】
【提出日】平成19年6月11日(2007.6.11)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
第１のデジタル証明書を含む１つ以上の暗号化されたデジタル証明書の有効性及び／又は無効性を検証するためにデータキャリア上で具現化されたコンピュータデータであって、
各デジタル証明書は、暗号鍵が１つのエンティティに関連付けられていることを証明し、
前記コンピュータデータは、少なくとも前記第１のデジタル証明書の有効性又は無効性を検証者コンピュータシステムに対して証明し、
前記コンピュータデータは、
（ａ）第１の複数の集合を含む複数の集合を定義する第１のデータと、
（ｂ）少なくとも前記第１の複数の集合ごとに、複数の期間の各々に対する期間データを定義し、前記集合に対する第１のターゲットを定義する第２のデータと、
（ｃ）前記第１の複数の集合の前記第１のターゲットから計算可能な第２のターゲットを定義する第３のデータとを含み、
前記第１のデジタル証明書は、前記第１の複数の集合の各々に属し、
前記第１のターゲットは、前記期間の各々に関連する前記集合における証明書の有効性及び／又は無効性を検証するために、前記期間のうちの１つに対する前記期間データから前記検証者コンピュータシステムにより計算可能であることを特徴とするコンピュータデータ。
【請求項２】
前記第１のデジタル証明書は、前記第１の複数の集合の前記ターゲット値のうちの少なくとも１つを含まないことを特徴とする請求項１に記載のコンピュータデータ。
【請求項３】
前記第１の証明書は、前記第２のターゲットを含むことを特徴とする請求項１に記載のコンピュータデータ。
【請求項４】
データキャリアにおいて具現化され、コンピュータシステムに請求項１に記載のコンピュータデータを生成させるように操作可能な１つ以上のコンピュータ命令を含むことを特徴とするコンピュータプログラム。
【請求項５】
請求項１に記載のコンピュータデータを生成するように構成されていることを特徴とするコンピュータシステム。
【請求項６】
第１のデジタル証明書を含む１つ以上の暗号化されたデジタル証明書の有効性及び／又は無効性の証明を提供する第１のコンピュータシステムであって、
各デジタル証明書は、暗号鍵が１つのエンティティに関連付けられていることを証明し、
前記コンピュータシステムは、コンピュータストレージを含み、
前記コンピュータシステムは、
（ａ）前記第１のデジタル証明書を第１の複数の集合に関連付ける第１のデータと、
（ｂ）少なくとも前記第１の複数の集合ごとに、複数の期間のうちの１つに対する期間データについてのネットワーク受信のための１つ以上のコンピュータ命令と、
（ｃ）前記第１の複数の集合の第１のターゲットから計算可能な第２のターゲットを定義するデータとを含み、
前記第１のデジタル証明書は、前記第１の複数の集合の各々に属し、
前記集合の各々は、前記第１のターゲットに関連付けられており、
前記期間の各々に関連した前記集合における証明書の有効性及び／又は無効性を検証するために、前記第１のターゲットは、検証者コンピュータシステムによって前記期間の１つに対する前記期間データから計算可能であることを特徴とする第１のコンピュータシステム。
【請求項７】
前記コンピュータストレージは、少なくとも前記第１のデジタル証明書に対する有効性又は無効性の証明を、ネットワークで送信するための１つ以上のコンピュータ命令を更に含み、
前記証明は、
前記期間のうちの１つに対する前記期間データと、
前記証明において提供された前記期間データによって定義される前記第１のターゲットから前記第２のターゲットを計算するためのデータとを含むことを特徴とする請求項６に記載の第１のコンピュータシステム。
【請求項８】
第１のデジタル証明書を含む１つ以上の暗号化されたデジタル証明書の有効性及び／又は無効性を証明するコンピュータに実装された方法であって、
各デジタル証明書は、暗号鍵が１つのエンティティに関連付けられていることを証明し、
前記方法は、
（ａ）ネットワーク上で
（ａ１）前記第１のデジタル証明書を第１の複数の集合に関連付ける第１のデータと、
（ａ２）前記第１の複数の集合ごとに、第１のターゲットを定義し、前記第１の複数の集合の前記第１のターゲットから計算可能な第２のターゲットを定義するデータとを受信する工程と、
（ｂ）少なくとも前記第１の複数の集合ごとに、複数の期間に対する期間データをネットワーク上で定期的に受信する工程と、
（ｃ）各期間において、要求があれば、少なくとも前記第１のデジタル証明書の有効性及び／又は無効性の証明を提供する工程とを有し、
前記第１のデジタル証明書は、前記第１の複数の集合の各々に属し、
前記期間の各々に関連する前記集合における証明書の有効性及び／又は無効性を検証するために、前記第１のターゲットは、検証者コンピュータシステムによって前記期間のうちの１つに対する前記期間データから計算可能であり、
前記証明は、前記期間に対する前記期間データ、及び、前記証明において提供された前記期間データによって定義される前記第１のターゲットから前記第２のターゲットを計算するためのデータを含むことを特徴とする方法。
【請求項９】
請求項８に記載の方法を実行するように構成されていることを特徴とするコンピュータシステム。
【請求項１０】
コンピュータシステムに請求項８に記載の方法を実行させるように操作可能な１つ以上のコンピュータ命令を含むことを特徴とするデータキャリア。
【請求項１１】
暗号鍵が１つのエンティティに関連付けられていることを証明する第１のデジタル証明書の有効性又は無効性を検証するためのコンピュータに実装された方法であって、
（ａ）ネットワーク上で、
（ａ１）第１のターゲットを計算するための期間に対する期間データと、
（ａ２）前記第１のターゲットから第２のターゲットを計算するための第２のターゲット計算データとを受信する工程と、
（ｂ）前記期間データから、（ａ１）の前記第１のターゲットを計算する工程と、
（ｃ）（ｂ）で計算した前記第１のターゲット及び前記ターゲット計算データから、前記第２のターゲットを計算する工程と、
（ｄ）前記第２のターゲットと前記第１のデジタル証明書とを整合して、前記第１のデジタル証明書の有効性又は無効性を決定する工程とを有し、
前記期間は、それぞれが期間データと関連付けられている複数の期間のうちの１つであり、
前記第１のターゲットは、前記期間の１つと関連付けられた前記期間データから計算可能であり、
前記第２のターゲットは、それぞれが前記第１のデジタル証明書を含む集合と関連付けられている複数の第１のターゲットの関数であることを特徴とする方法。
【請求項１２】
コンピュータシステムに請求項１１に記載の方法を実行させるように操作可能な１つ以上のコンピュータ命令を含むことを特徴とするデータキャリア。
【請求項１３】
請求項１１に記載の方法を実行するように構成されていることを特徴とするコンピュータシステム。
【請求項１４】
暗号鍵が１つのエンティティに関連付けられていることを証明する第１のデジタル証明書に対する有効性又は無効性の証明を含むコンピュータデータを含むデータキャリアであって、
（ａ１）第１のターゲットを計算するための期間に対する期間データと、
（ａ２）前記第１のターゲットから第２のターゲットを計算するための第２のターゲット計算データとを含み、
前記期間は、それぞれが期間データに関連付けられた複数の期間のうちの１つであり、
前記第１のターゲットは、前記期間のいずれかに関連付けられた前記期間データから計算可能であり、
前記第２のターゲットは、それぞれが前記第１のデジタル証明書を含む集合と関連付けられた複数の第１のターゲットの関数であることを特徴とするデータキャリア。
【請求項１５】
データキャリアにおいて具現化され、暗号鍵が１つのエンティティに関連付けられていることを証明する第１のデジタル証明書を含むコンピュータデータであって、
前記第１のデジタル証明書は、編集可能なデジタル署名を含むことを特徴とするコンピュータデータ。
【請求項１６】
前記第１のデジタル証明書は、該第１のデジタル証明書の有効性及び／又は無効性を検証するために、各々が検証者コンピュータシステムによって計算可能な複数のターゲットを含み、
前記検証者コンピュータシステムによる有効性及び／又は無効性の検証には、前記ターゲットの全てより少ないターゲットが必要であることを禿頭とする請求項１５に記載のコンピュータデータ。
【請求項１７】
削除された１つ以上の前記ターゲットを用いることなく、前記署名を検証するための署名証明を含む編集されたデジタル証明書を取得できるように、少なくとも前記ターゲットのうちの１つが削除されるように操作可能であることを特徴とする請求項１６に記載のコンピュータデータ。
【請求項１８】
請求項１５に記載のコンピュータデータを生成するように構成されていることを特徴とするコンピュータシステム。
【請求項１９】
データキャリアにおいて具現化され、コンピュータシステムに請求項１５に記載のコンピュータデータを生成させるように操作可能な１つ以上のコンピュータ命令を含むことを特徴とするコンピュータデータ。
【請求項２０】
請求項１５に記載のコンピュータデータを処理するコンピュータに実装された方法であって、
前記第１のデジタル証明書の一部分を削除して、前記削除された一部分を用いることなく、前記署名を検証するための署名証明を有する編集されたデジタル証明書を取得する工程と、
前記編集されたデジタル証明書をネットワーク上で送信する工程とを有することを特徴とする方法。
【請求項２１】
前記検証者コンピュータシステムが、前記削除された一部分を用いることなく、前記編集されたデジタル証明書から、前記第１のデジタル証明書の有効性又は無効性を検証することを可能とするために、有効性証明又は無効性証明を送信する工程を更に含むことを特徴とする請求項２０に記載の方法。
【請求項２２】
前記証明書は、前記第１のデジタル証明書の有効性及び／又は無効性を検証するために、各々が前記検証者コンピュータシステムによって計算可能である複数のターゲットを含み、
前記検証者コンピュータシステムによる有効性及び／又は無効性の検証には、前記ターゲットの全てより少ないターゲットを必要とし、
前記編集されたデジタル証明書は、前記ターゲットの全てよりは少ないターゲットを含むことを特徴とする請求項２０に記載の方法。
【請求項２３】
請求項２０に記載の方法を実行するように構成されていることを特徴とするコンピュータシステム。
【請求項２４】
データキャリアに統合され、コンピュータシステムに請求項２０に記載の方法を実行させるように操作可能な１つ以上のコンピュータ命令を含むことを特徴とするコンピュータデータ。
【請求項２５】
暗号鍵が１つのエンティティに関連付けられていることを証明する第１のデジタル証明書の有効性又は無効性を検証するコンピュータに実装された方法であって、
前記第１のデジタル証明書は、編集可能な署名を含み、
前記方法は、
前記デジタル署名の署名証明を有する編集されたデジタル証明書を受信する工程と、
前記第１のデジタル証明書を用いることなく、前記編集されたデジタル証明書及び前記署名証明を用いて前記署名を検証する工程と、
ターゲット値を計算し、前記ターゲット値と前記編集されたデジタル証明書におけるターゲットとを整合する工程とを有することを特徴とする方法。
【請求項２６】
請求項２５に記載の方法を実行するように構成されていることを特徴とするコンピュータシステム。
【請求項２７】
データキャリアに統合され、コンピュータシステムに請求項２５に記載の方法を実行させるように操作可能な１つ以上のコンピュータ命令を含むことを特徴とするコンピュータデータ。
【請求項２８】
複数の集合｛Ｆ｝のシステムを生成するためにコンピュータに実装された方法であって、
各集合Ｆは、１つ以上のデジタル証明書ＤＣ及び／又はデジタル証明書に割り当て可能なデジタル証明書スロットであり、
各デジタル証明書ＤＣ＝ＤＣ（ＣＫ，ＥＮ）は、対応する暗号鍵ＣＫが、コンピュータシステムに関連付けられたエンティティＥＮに関連付けられていることを証明し、
前記方法は、
（１）マルチキャスティンググループ用の１つ又は複数の表示を取得する工程と、
（２）前記表示のうちの少なくとも１つに関して、少なくとも２つのデジタル証明書ＤＣ（ＣＫ，ＥＮ）を含む集合Ｆ∈｛Ｆ｝を生成する工程と、
（３）前記集合Ｆに対する有効性証明を定義するデータを生成する工程とを有し、
前記表示の各々は、複数のエンティティを示し、
前記複数のエンティティが関連付けられているコンピュータシステムは、単一のマルチキャスティンググループに属しており、又は、単一のマルチキャスティンググループに属するようになっており、
前記デジタル証明書ＤＣ（ＣＫ，ＥＮ）が関連付けられているエンティティＥＮは、前記表示によって表示されることを特徴とする方法。
【請求項２９】
前記集合Ｆは、関連付けられているエンティティＥＮが前記表示によって表示される前記デジタル証明書の全てを含むことを特徴とする請求項２８に記載の方法。
【請求項３０】
前記集合Ｆは、関連付けられているエンティティＥＮが前記表示によって表示される前記デジタル証明書の全てからなることを特徴とする請求項２８に記載の方法。
【請求項３１】
請求項２８に記載の方法を実行するように構成されていることを特徴とするコンピュータシステム。
【請求項３２】
コンピュータシステムに請求項２８に記載の方法を実行させるように操作可能な１つ以上のコンピュータ命令を含むことを特徴とするデータキャリア。
【請求項３３】
失効したデジタル証明書の集合Ｒに対するコンプリメントカバーＣＣＲを選択するコンピュータに実装された方法であって、
各デジタル証明書は、暗号鍵が、コンピュータシステムに関連付けられているエンティティに関連付けられていることを証明し、
前記方法は、
マルチキャスティンググループ用の１つ以上の表示を取得する工程と、
集合Ｆの優先順位を考慮して、前記コンプリメントカバーＣＣＲに対する有効なデジタル証明書の集合Ｆを選択する工程とを有し、
前記表示の各々は、複数のエンティティを示し、
前記複数のエンティティが関連付けられているコンピュータシステムは、単一のマルチキャスティンググループに属しており、又は、単一のマルチキャスティンググループに属するようになっており、
前記集合Ｆが、２つ以上のデジタル証明書を含む場合、該集合Ｆの優先順位は、増加し、
前記デジタル証明書のエンティティは、前記表示のいずれか１つによって単一のマルチキャスティンググループに対して表示されることを特徴とする方法。
【請求項３４】
請求項３３に記載の方法を実行するように構成されていることを特徴とするコンピュータシステム。
【請求項３５】
コンピュータシステムに請求項３３に記載の方法を実行させるように操作可能な１つ以上のコンピュータ命令を含むデータキャリア。
【請求項３６】
ネットワークにおけるコンピュータシステムのマルチキャスティンググループを形成する方法であって、
各コンピュータシステムは、暗号鍵が、コンピュータシステムに関連付けられたエンティに関連付けられていることを証明するデジタル証明書の少なくとも１つと関連付けられており、
複数の前記デジタル証明書の集合ごとに、有効性証明又は無効性証明が定義されており、
前記集合の各々は、複数のデジタル証明書を含み、
前記集合の各々は、優先順位と関連付けられており、
前記方法は、
（１）前記優先順位に応じて、１つ以上の集合を選択する工程と、
（２）集合ごとに、
（２ａ）前記集合のデジタル証明書と関連付けられているコンピュータシステムを含むマルチキャスティンググループを形成する工程、及び／又は、（ｉｉ）前記デジタル証明書の少なくとも１つと関連付けられているコンピュータシステムに対して、前記集合に対応するマルチキャスティンググループに参加する前記コンピュータシステムを形成する工程とを有することを特徴とする方法。
【請求項３７】
各集合の優先順位は、１つ以上の前記集合の証明書の期限切れでない期間の和に比例することを特徴とする請求項３６に記載の方法。
【請求項３８】
各集合の優先順位は、前記集合の証明書の数に比例することを特徴とする請求項３６に記載の方法。
【請求項３９】
請求項３６に記載の方法を実行するためにネットワークに参加するように構成されていることを特徴とするコンピュータシステム。
【請求項４０】
コンピュータシステムを、請求項３６に記載の方法に従ってネットワークに参加させるように操作可能な１つ以上のコンピュータ命令を含むことを特徴とするデータキャリア。
【請求項４１】
複数のデジタル証明書の有効性及び／又は無効性を証明する方法であって、
前記複数のデジタル証明書の各々は、暗号鍵が１つのエンティティに関連付けられていることを証明し、
各デジタル証明書は、コンピュータシステムに関連付けられており、
前記方法は、
（１）各集合における全ての証明書が同じ有効状況を有するように、１つ又は複数の集合を決定する工程と、
（２）第１の集合における証明書に関連付けられている複数のコンピュータシステムを含むネットワークマルチキャスティンググループを検索する工程と、
（３）（２）において前記ネットワークマルチキャスティンググループが見つかった場合、前記第１の集合に対する前記有効状況を、マルチキャスト伝送を介して前記マルチキャスティンググループに送信する工程とを有し、
各集合は、複数の証明書を含む少なくとも前記第１の集合を含む１つ以上の証明書の有効状況証明と関連付けられていることを特徴とする方法。
【請求項４２】
請求項４１に記載の方法を実行するように構成されていることを特徴とするコンピュータシステム。
【請求項４３】
コンピュータシステムに請求項４１に記載の方法を実行させるように操作可能な１つ以上のコンピュータ命令を含むコンピュータデータを含むことを特徴とするデータキャリア。
【請求項４４】
暗号鍵が１つのエンティティに関連付けられていることを証明するデジタル証明書の有効性又は無効性を証明する有効状況証明を処理する方法であって、
ネットワーク上のコンピュータシステムで、１つ以上のデジタル証明書の有効状況証明を受け取る工程と、
前記コンピュータシステムが、前記コンピュータシステムが前記有効状況証明の将来のネットワーク送信を実行することができるように、前記有効状況証明をキャッシュするかどうかを決定するキャッシング決定を行う工程と、
前記キャッシング決定に従って、前記有効状況証明のキャッシングを行う又は行わない工程とを有し、
前記キャッシング決定は、前記１つ以上のデジタル証明書の前記優先順位に基づいていることを特徴とする方法。
【請求項４５】
前記優先順位は、１つ以上の前記証明書の期限切れでない期間に比例し、
前記証明書のために、前記有効状況証明を受け取ることを特徴とする請求項４４に記載の方法。
【請求項４６】
前記優先順位は、前記デジタル証明書の数に比例し、
前記デジタル署名のために、前記有効状況を受け取ることを特徴とする請求項４４に記載の方法。
【請求項４７】
請求項４４に記載の方法を実行するように構成されていることを特徴とするコンピュータシステム。
【請求項４８】
コンピュータシステムに請求項４４に記載の方法を実行させるように操作可能な１つ以上のコンピュータ命令を含むコンピュータデータを含むことを特徴とするデータキャリア。
【請求項４９】
連続する期間におけるデジタル証明書の有効性証明又は無効性証明を生成するためのコンピュータデータを含むデータキャリアであって、
各デジタル証明書は、暗号鍵が１つのエンティティに関連付けられていることを証明し、
相異なる証明は、相異なる期間に対して生成されるように操作可能であり、
前記コンピュータデータは、第１の所定数の前記期間を含む第１の時間間隔に対する証明のための第１のコンピュータデータを含み、
前記第１の時間間隔は、前記第１のコンピュータデータと共に使用される証明書に対する最小の有効期限より長いことを特徴とするデータキャリア。
【請求項５０】
前記コンピュータデータは、複数の期間を含む第２の時間間隔に対する証明のための第２のコンピュータデータを更に含み、
前記第２の時間間隔は、前記第１の時間間隔において始まり、前記第１の時間間隔が終了した後に終了することを特徴とする請求項４９に記載のデータキャリア。
【請求項５１】
コンピュータシステムを用いて、請求項４９に記載のコンピュータデータを生成することを特徴とするコンピュータに実装された方法。
【請求項５２】
前記第２のコンピュータデータと共に使用するための新規証明書を作成する工程を更に含み、
前記新規証明書は、前記第１の時間間隔の終了後に失効することを特徴とする請求項５１に記載の方法。
【請求項５３】
請求項５１に記載の方法を実行するように構成されていることを特徴とするコンピュータシステム。
【請求項５４】
コンピュータシステムに請求項５１に記載の方法を実行させるように操作可能な１つ以上のコンピュータ命令を含むコンピュータデータを含むことを特徴とするデータキャリア。
【請求項５５】
複数のデジタル証明書の各々の有効性又は無効性を証明するためのコンピュータデータを含むデータキャリアであって、
各デジタル証明書は、暗号鍵が１つのエンティティに関連付けられていることを証明し、
前記コンピュータデータは、第１のデータ及び第２のデータを定義し、
前記第１のデータは、デジタル証明書ごとに、第１のコンピュータシステムによって、１つ以上の第１の証明を生成するためのものであり、
前記第１の証明の各々は、前記デジタル証明書の有効性及び無効性の証明であり、
前記第２のデータは、デジタル証明書ごとに、第２のコンピュータシステムによって、１つ以上の第２の証明を生成するためのものであり、
前記第２の証明の各々は、前記デジタル証明書の有効性又は無効性の証明であり、
前記第１のデータは、前記第２のデータと異なり、
少なくとも１つのデジタル証明書に対する少なくとも１つの第１の証明は、各第２の証明とは異なり、
少なくとも１つの第２の証明は、各第１の証明とは異なることを特徴とするデータキャリア。
【請求項５６】
前記第１のデータは、前記第２のデータからコンピュータシステムによって回復させることができず、
前記第２のデータは、前記第１のデータからコンピュータシステムによって回復させることができないことを特徴とする請求項５５に記載のデータキャリア。
【請求項５７】
請求項５５に記載のコンピュータデータをコンピュータシステムによって生成することを特徴とするコンピュータに実装された方法。
【請求項５８】
前記第１のデータ及び前記第２のデータをそれぞれ暗号化して、第１の暗号データ及び第２の暗号データを取得する工程と、
前記第1の暗号データを、前記第１のコンピュータシステムに対してネットワークを介して送信する工程と、
前記第２の暗号データを、前記第２のコンピュータシステムに対してネットワークを介して送信する工程と更に含むことを特徴とする請求項５７に記載の方法。
【請求項５９】
前記第１のデータ及び前記第２のデータは、暗号化され、暗号化された形式で送信されることを特徴とする請求項５７に記載の方法。
【請求項６０】
前記第１のデータは、１つ以上の復号鍵の第１の集合を用いて復号するために暗号化され、
前記第２のデータは、１つ以上の復号鍵の第２の集合を用いて復号するために暗号化され、
前記第１の集合の少なくとも１つの鍵は、前記第２の集合の各鍵とは異なり、
前記第２の集合の少なくとも１つの鍵は、前記第１の各鍵とは異なることを特徴とする請求項５９に記載の方法。
【請求項６１】
デジタル証明書ごとに、前記１つ以上の第１の証明は、連続する期間ｐｉの各々に対する少なくとも１つの第１の証明を含み、前記１つ以上の第２の証明は、前記期間ｐｉの各々に対して少なくとも１つの第２の証明を含み、
少なくとも１つの期間ｐｉに対して、各第１の証明は、各第２の証明とは異なり、
期間ｐｉごとに、前記第１のデータ及び前記第２のデータの各々は、前記期間ｐｉにおける前記第１及び第２の各々の証明を提供するデータ部分を含み、
前記期間ｐｉの１つである期間ｐｉ１に対する前記第１のデータ及び前記第２のデータの前記データ部分は、前記期間ｐｉの他の期間ｐｉ２に対する前記第１のデータ及び前記第２のデータの前記データ部分を復号するための１つ以上の復号鍵と異なる１つ以上の復号鍵を用いて復号するために暗号化され、
前記方法は、
少なくとも１つの期間ｐｉに対して、
前記第１のコンピュータシステム及び前記第２のコンピュータシステムが危殆化しているかどうかを決定する工程と、
前記期間ｐｉに対して、前記第１のコンピュータシステム及び前記第２のコンピュータシステムのうちの一方が、危殆化していないと決定された場合、前記期間ｐｉに対応する前記第１及び前記第２の各々のデータの前記データ部分を復号するために、前記第１のコンピュータシステム及び前記第２のコンピュータシステムの前記一方に復号鍵を送付する工程とを更に含むことを特徴とする請求項５９に記載の方法。
【請求項６２】
前記第１のコンピュータシステム及び前記第２のコンピュータシステムの一方が、前記期間ｐｉに対して危殆化していると見なされた場合、前記第１のコンピュータシステム及び前記第２のコンピュータシステムの前記一方からの前記各復号鍵を保留する工程を含むことを特徴とする請求項６１に記載の方法。
【請求項６３】
前記第１のデータを復号するための１つ以上の復号鍵の第１の集合と、前記第２のデータを復号するための１つ以上の復号鍵の第２の集合とを更に含み、
前記第１の集合の少なくとも１つの鍵は、前記第２の集合の各鍵とは異なり、
前記第２の集合の少なくとも１つの鍵は、前記第１の集合の各鍵とは異なることを特徴とする請求項５５に記載のデータキャリア。
【請求項６４】
前記第１の集合及び前記第２の集合の各々は、複数の前記復号鍵を含み、
各鍵は、連続する期間の１つ以上の各集合に提供される有効性又は無効性の証明のためのものであることを特徴とする請求項６３に記載のデータキャリア。
【請求項６５】
連続する期間の各々における前記第１のコンピュータシステム及び前記第２のコンピュータシステムの各々の有効性又は無効性を証明するための有効性又は無効性を提供するコンピュータデータを更に含むことを特徴とする請求項５５に記載のデータキャリア。
【請求項６６】
請求項５５に記載のコンピュータデータを生成するように構成されていることを特徴とするコンピュータシステム。
【請求項６７】
コンピュータシステムに請求項５７に記載の方法を実行させるように操作可能な１つ以上のコンピュータ命令を含むデータキャリア。
【請求項６８】
コンピュータデータを含むデータキャリアであって、
暗号鍵が１つのエンティティに関連付けられていることを証明する複数のデジタル証明書の各々の有効性又は無効性を証明する第１のコンピュータデータと、
前記第１のコンピュータデータの第１の部分を復号するための第１の復号鍵と、
前記第１の復号鍵とは異なる前記第１のコンピュータデータの第２の部分を復号するための第２の復号鍵とを含む事を特徴とするデータキャリア。
【請求項６９】
前記第１のコンピュータデータの前記第１の部分は、第１の期間における前記デジタル証明書の少なくとも１つの有効性又は無効性の証明を提供するためのものであり、
前記第１のコンピュータデータの前記第２の部分は、第２の期間における前記デジタル証明書の少なくとも１つの有効性又は無効性の証明を提供するためのものであることを特徴とする請求項６８に記載のデータキャリア。
【請求項７０】
請求項６８に記載のコンピュータデータをコンピュータシステムによって生成することを特徴とするコンピュータに実装された方法。
【請求項７１】
請求項７０に記載の方法を実行するように構成されていることを特徴とするコンピュータシステム。
【請求項７２】
コンピュータシステムに請求項７０に記載の方法を実行させるように操作可能な１つ以上のコンピュータ命令を含むことを特徴とするデータキャリア。
【請求項７３】
複数のデジタル証明書の各々の有効性又は無効性を証明するためのコンピュータデータを含むデータキャリアであって、
各デジタル証明書は、暗号鍵が１つのエンティティに関連付けられていることを証明し、
前記コンピュータデータは、前記デジタル証明書の各々の有効性又は無効性を証明するための第１の暗号データを含むことを特徴とするデータキャリア。
【請求項７４】
前記第１の暗号データは、
第１の期間における前記デジタル証明書の有効性又は無効性を証明する第１の復号鍵で復号するために暗号化された第１の部分と、
第２の期間における前記デジタル証明書の有効性又は無効性を証明する前記第１の復号鍵とは異なる第２の復号鍵で復号するために暗号化された第２の部分とを含むことを特徴とする請求項７３に記載のデータキャリア。
【請求項７５】
コンピュータシステムが、請求項７４に記載のコンピュータデータをネットワーク上で受け取る工程と、
前記コンピュータシステムが、第１の期間中又は該第１の期間の前に、前記第１の復号鍵を受け取る工程と、
前記コンピュータシステムが、前記第１の期間における有効性又は無効性を証明するために、前記第１の復号鍵を用いて前記第１の部分を復号する工程と、
前記コンピュータシステムが、第２の期間中又は該第２の期間の前、及び、前記第１の期間の終了時又は該第１の期間の終了後に、前記第２の復号鍵を受け取る工程と、
前記コンピュータシステムが、前記第２の期間における有効性又は無効性を証明するために、前記第２の復号鍵を用いて前記第２の部分を復号する工程とを有することを特徴とするコンピュータに実装された方法。
【請求項７６】
請求項７５に記載の方法を実行するように構成されていることを特徴とするコンピュータシステム。
【請求項７７】
コンピュータシステムに請求項７５に記載の方法を実行させるように操作可能な１つ以上のコンピュータ命令を含むことを特徴とするデータキャリア。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正の内容】
【００１０】
ｆ：  ｛０，ｌ｝ｎ→｛０，ｌ｝ｎ
ここで、｛０，ｌ｝ｎは、長さｎの全ての２進法の文字列の集合である。ｆｉが、ｉ倍の合成（ｉ-ｆｏｌｄ  ｃｏｍｐｏｓｉｔｉｏｎ）を示すものとする。つまり、ｉ＝０に対して、ｆｉ（ｘ）＝ｘであり、ｉ＞０に対して、ｆｉ（ｘ）＝ｆ（ｆｉ−１（Ｘ））である。ｆを、一方向とする。ｘがランダムに選択されるｆ（ｘ）が与えられると、無視できる程度の確率を除いて、ｆ（ｘ）＝ｆ（ｘ）となるようなプリイメージｚを見つけることは困難（実行不可能）である。すなわち、ｘをランダムに選択するｆ（ｘ）が「実行不可能である」とは、安全性のパラメータｋ（例えばｋ＝ｎ）が与えられているので、無視できる程度の可能性を除いて、ｋにおける予め定義されている多項式と同じ時間内に、プリイメージｚを計算することができないということである。さらに、ｆは、その反復において、一方向であるであると仮定すると、すなわち、任意のｉに対して、ｙをｙ＝ｆｉ（ｘ）と仮定すると、ｆ（ｚ）＝ｙであるようなｚを見つけることは実行不可能である。
【国際調査報告】
2008512066.tif 000035