(57)【要約】【課題】本発明の目的は、アドホックネットワークなどのネットワーク上でのアキュムレータデータの配布を容易にすることである。【解決手段】予め特定されたプロパティを所有する（例えば、有効である）又は、所有しないとしてエレメント（例えば、デジタル証明書１４０）の認証を、（１）相異なる整数ｐｉを各エレメントに割り当て、（２）プロパティを有するエレメント、又は、所有しないエレメントを、予め定義された合成数ｎを法とする整数ｕのP乗根であるｕ１／ｐ（ｎを法とする）を用いて累算することによって実行する。ここで、Pは、累算されたエレメントと関連づけられた整数の積である。あるいは、そのようなアキュムレータではなく、アキュムレータに関連づけられたウィットネスを用いて、認証を実行することもできる。ウィットネスは、複数の期間においてプロパティを所有することを証明するデータを暗号化する暗号鍵及び／又は復号鍵を導出するために用いる。暗号化されたデータは、予め配布される。各期間に対して、その期間及び、その期間内に認証されるエレメントと関連づけられた復号鍵が公開される。認証は、各エレメントの関数であるが、エレメント数とは無関係なサイズのデータにエレメントを累算し、アキュムレータデータを、コンピュータシステムに対してネットワーク上で送信することによって実行することができる。このコンピュータシステムは、他のコンピュータシステムによって必要とされるエレメントと関連づけられたデータだけを再送信するために必要に応じていくつかのエレメントをディアキュムレートする。【選択図】図５
2008524930.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに実装され、複数のエレメントが予め特定されたプロパティを所有しているかどうかの認証を提供する認証方法であって、
それぞれの前記エレメントは、予め特定された前記プロパティを取得するか失わせるかの少なくとも一方のために動作可能で、１よりも大きい相異なる整数と関連づけられており、
前記複数のエレメントの集合Ｐ１に対して、前記集合Ｐ１の全ての前記エレメントが前記プロパティを所有する、又は、所有しないことを証明する第１のデータＡ１（Ｐ１）を取得する工程を含み、
前記第１のデータＡ１（Ｐ１）は、予め定義された合成数ｎを法とする整数ｕのＰ乗根であるｕ１／Ｐ（ｎを法とする）を表し、
前記Pは、前記集合Ｐ１の要素に関連づけられた前記整数の積であることを特徴とする方法。
【請求項２】
コンピュータに実装され、複数のエレメントが予め特定されたプロパティを所有しているかどうかの認証を提供する認証方法であって、
それぞれの前記エレメントは、予め特定された前記プロパティを取得するか失わせるかの少なくとも一方のために動作可能で、１よりも大きい相異なる整数と関連づけられており、
第１のコンピュータシステムが、前記複数のエレメントのひとつであるエレメントＥ１と関連づけられた整数ＰＥ１を生成する工程と、
前記第１のコンピュータシステムが、予め定義された合成数を法とする基数のｐＥ１乗根を表すデータを取得する工程と、
第１のコンピュータシステムが、前記データを第２のコンピュータシステムに提供し、前記第２のコンピュータシステムに前記エレメントＥ１が前記予め特定されたプロパティを所有することを証明させる工程とを含むことを特徴とする方法。
【請求項３】
コンピュータに実装され、複数のエレメントが予め特定されたプロパティを所有しているかどうかの認証を提供する認証方法であって、
それぞれの前記エレメントは、予め特定された前記プロパティを取得するか失わせるかの少なくとも一方のために動作可能で、１よりも大きい相異なる整数と関連づけられており、
前記集合Ｐ１の全ての前記エレメントが前記プロパティを所有する、又は、所有しないことを証明する第１のデータＡ１（Ｐ１）を取得する工程と、
各部分集合Ｐ１．ｉ(ｉ＝１，．．．，ｋ)に対して、第１のデータＡ１(Ｐ１．ｉ)を求めることで、前記集合Ｐ１を２つ以上の空でない部分集合Ｐ１．１，．．．，Ｐ１．ｋに分割する工程とを含み、
前記第１のデータＡ１(Ｐ１)は、前記集合Ｐ1の各エレメントの関数であり、前記集合Ｐ１におけるエレメント数とは無関係なサイズを有することを特徴とする方法。
【請求項４】
コンピュータに実装され、複数のエレメントが予め特定されたプロパティを所有しているかどうかの認証を提供する認証方法であって、
それぞれの前記エレメントは、予め特定された前記プロパティを取得するか失わせるかの少なくとも一方のために動作可能で、１よりも大きい相異なる整数と関連づけられており、
前記集合Ｐ１の全ての前記エレメントが前記プロパティを所有する、又は、所有しないことを証明する第１のデータＡ１（Ｐ１）を取得する工程と、
各部分集合Ｐ１．ｉ(ｉ＝１，．．．，ｋ)に対して、前記部分集合Ｐ１．ｉにではなく前記集合Ｐ１に属する前記エレメントに関連づけられた整数の積である指数で、Ｐ乗根であるｕ１／Ｐ（ｍｏｄ ｎ）をべき乗して第１のデータＡ１(Ｐ１．ｉ)を求めることで、前記集合Ｐ１を２つ以上の空でない部分集合Ｐ１．１，．．．，Ｐ１．ｋに分割する工程とを含み、
前記第１のデータＡ１（Ｐ１）は、予め定義された合成数ｎを法とする整数ｕのＰ乗根であるｕ１／Ｐ（ｍｏｄ ｎ）であり、
前記Pは、前記集合Ｐ１の要素に関連づけられた前記整数の積であることを特徴とする方法。
【請求項５】
コンピュータに実装され、複数のエレメントが予め特定されたプロパティを所有しているかどうかの認証を提供する認証方法であって、
それぞれの前記エレメントは、予め特定された前記プロパティを取得するか失わせるかの少なくとも一方のために動作可能で、前記認証は、複数の連続する期間のそれぞれに提供され、
前記エレメントのひとつであるエレメントＥ１に対する前記期間に対して、エレメントＥ１が前記それぞれの期間ｊにおいて前記プロパティを所有することの証明である認証データ片ｃｊ（Ｅ１）を複数生成する工程と、
整数ＰＥ１を前記エレメントＥ１に割り当て、
前記エレメントＥ１に対する各期間ｊに対して、ｕ（ｊ）がｊによって決まる予め定義された合成数ｎを法とする整数ｕ（ｊ）のｐＥ１乗根であるｕ（ｊ）１／ＰＥ１（ｍｏｄ ｎ）から生成された暗号鍵Ｋｊ（Ｅ１）を生成する工程と、
前記それぞれの鍵Ｋｊ（Ｅ１）で各片ｃｊ（Ｅ１）の少なくとも一部分を暗号化する工程とを含むことを特徴とする方法。
【請求項６】
コンピュータに実装され、複数のエレメントが予め特定されたプロパティを所有しているかどうかの認証を提供する認証方法であって、
それぞれの前記エレメントは、予め特定された前記プロパティを取得するか失わせるかの少なくとも一方のために動作可能で、前記認証は、複数の連続する期間のそれぞれに提供され、
前記複数の連続する期間の各期間ｊに対して、エレメントＥ１が、前記期間ｊにおいて前記プロパティを所持しているとして認証されるかを決定する工程と、
前記エレメントＥ１が、前記期間ｊにおいて前記プロパティを所有するとして認証される場合は、前記エレメントＥ１が前記プロパティを所有するという前記期間ｊにおける証明データｃｊ（Ｅ１）を提供する各コンピュータシステムに対して、ｕ（ｊ）がｊによって決まり、ｐＥ１が前記エレメントＥ１に割り当てられた整数である、予め定義された合成数ｎを法とする整数ｕ（ｊ）のｐＥ１乗根であるｕ（ｊ）１／ＰＥ１（ｍｏｄ ｎ）から生成され、前記証明データｃｊ（Ｅ１）を少なくとも部分的に復号するための復号鍵ＤＫｊ（Ｅ１）を提供する工程とを含み、
前記エレメントＥ１が、前記期間ｊにおいて前記プロパティを所有するとして認証されない場合、前記復号鍵ＤＫｊ（Ｅ１）を前記コンピュータシステムの少なくともひとつに対して提供しないことを特徴とする方法。
【請求項７】
コンピュータに実装され、複数のエレメントが予め特定されたプロパティを所有しているかどうかの認証を提供する認証方法であって、
それぞれの前記エレメントは、予め特定された前記プロパティを取得するか失わせるかの少なくとも一方のために動作可能であり、前記認証は、連続する期間のそれぞれに提供され、
コンピュータシステムが、前記エレメントのひとつであるエレメントＥ１が連続する期間のひとつである前記期間ｊにおいて前記プロパティを所有することを証明する認証データｃｊ（Ｅ１）を少なくとも部分的に暗号化する、連続する期間に対する複数のデータ片ＥＮｊ（ｃｊ（Ｅ１））を受信する工程と、
各期間ｊに対する前記複数のデータ片ＥＮ（ｃｊ（Ｅ１））を受信した後で、前記エレメントＥ１が、前記期間ｊにおいて前記プロパティを所有するとして認証される場合、
（ａ）前記コンピュータシステムは、ｐＥ１が前記エレメントＥ１と関連づけられた整数である、予め定義された合成数ｎを法とする整数ｕ（ｊ）のｐＥ１乗根であるｕ（ｊ）１／ＰＥ１（ｎを法とする）から生成される復号鍵ＤＫｊ（Ｅ１）を受信する工程と、
（ｂ）前記コンピュータシステムは、前記データ片ＥＮ（ｃｊ（Ｅ１））を前記鍵ＤＫｊ（Ｅ１）で復号する工程とを含むことを特徴とする方法。
【請求項８】
請求項１の方法を実行するコンピュータシステムであって、前記第１のデータＡ１（Ｐ１）を生成するコンピュータシステム。
【請求項９】
前記第１のデータＡ１（Ｐ１）を生成するように、コンピュータシステムを請求項１の方法を実行するようにプログラムするひとつ以上のコンピュータ命令を備えるデータキャリア。
【請求項１０】
請求項１に記載のように第１のデータＡ１（Ｐ１）を備えるデータキャリア。
【請求項１１】
請求項２の方法を実行するコンピュータシステム。
【請求項１２】
請求項２の方法をコンピュータシステムに実行させるひとつ以上のコンピュータ命令を備えるデータキャリア。
【請求項１３】
請求項３の方法を実行するコンピュータシステム。
【請求項１４】
請求項３の方法をコンピュータシステムに実行させるひとつ以上のコンピュータ命令を備えるデータキャリア。
【請求項１５】
請求項４の方法を実行するコンピュータシステム。
【請求項１６】
請求項４の方法をコンピュータシステムに実行させるひとつ以上のコンピュータ命令を備えるデータキャリア。
【請求項１７】
請求項５の方法を実行するコンピュータシステム。
【請求項１８】
請求項５の方法をコンピュータシステムに実行させるひとつ以上のコンピュータ命令を備えるデータキャリア。
【請求項１９】
請求項５に記載のように、鍵Ｋｊ（Ｅ１）と、前記鍵Ｋｊ（Ｅ１）のもとに一片ｃｊ（Ｅ１）を少なくとも部分的に暗号化する方式の少なくとも一方を備えるデータキャリア。
【請求項２０】
請求項６の方法を実行するコンピュータシステム。
【請求項２１】
請求項６の方法をコンピュータシステムに実行させるひとつ以上のコンピュータ命令を備えるデータキャリア。
【請求項２２】
請求項６に記載のように、復号鍵ＤＫｊ（Ｅ１）を備えるデータキャリア。
【請求項２３】
請求項７の方法を実行するコンピュータシステム。
【請求項２４】
請求項７の方法をコンピュータシステムに実行させるひとつ以上のコンピュータ命令を備えるデータキャリア。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の説明）
本願は、この参照により引用に含まれる、２００４年１２月１７日出願の米国仮特許出願第６０６３７１７７号の優先権を主張する。
【０００２】
本発明は、エレメントが予め特定されたプロパティを所有しているかどうかの認証に関する。例えば、公開鍵暗号基盤におけるデジタル失効の有効性認証、又は、リソースを使用する（例えば、ウェブサイト上において署名する）権利の有効性認証である。
【背景技術】
【０００３】
図１は公開鍵暗号基盤におけるデジタル証明書の認証と失効について図示している。デジタル証明書１０４は、公開鍵暗号基盤（ＰＫＩ）で利用されており、ネットワーク化したコンピュータ環境において公開鍵の安全な利用と管理を容易にしている。ユーザＵ１、Ｕ２、・・・は、それぞれのコンピュータシステム１１０．１、１１０．２・・・を利用してそれぞれの鍵ペア（ＰＫ、ＳＫ）を生成する。ここで、ＰＫは、公開鍵であり、ＳＫは、秘密鍵である。図１は、ユーザＵ１に対する鍵ペア（ＰＫＵ１、ＳＫＵ１）を示す。ユーザは、自分の公開鍵ＰＫをネットワーク上で認証局（ＣＡ）１２０に登録する。あるいは、ＣＡ１２０が公開鍵を生成しユーザに送信することもできる。ＣＡ１２０は、安全で信頼のおけるコンピュータシステムである。ＣＡ１２０は、各公開鍵ＰＫに対してデジタル証明書１０４を生成する。証明書１０４は、公開鍵ＰＫ及びユーザ名、及び／又は、ユーザのメールアドレス又は住所を含むが、証明書のシリアル番号ＳＮ（証明書の管理を容易にするためにＣＡによって生成されたもの）、証明書発行日Ｄ１、証明書有効期限Ｄ２、公開鍵及び秘密鍵に使用するアルゴリズムの識別、ＣＡ１２０の識別、及び他のデータ等を含めても良い。上述したデータを１０４Ｄに示す。証明書１０４は、データ１０４ＤのＣＡの署名１０４−ＳｉｇＣＡも含む。その署名は、ＣＡの秘密鍵ＳＫＣＡを使って生成し、ＣＡ１２０は、証明書１０４をユーザ（鍵の所有者）のコンピュータシステム１１０に送信する。所有者及びＣＡ１２０は、ユーザの公開鍵ＰＫを他者に知らせるため、他者に証明書を配布することができる。そのような他者は、証明書の公開鍵ＰＫが、名前及びメールアドレスが証明書に記載されている人物に実際に属していることを確認するために、ＣＡの署名１０４−ＳｉｇＣＡをＣＡの公開鍵ＰＫＣＡで検証することができる。
【０００４】
証明書は、その有効期限Ｄ２より前に失効されなければならなくなるかもしれない。例えば、証明書の所有者Ｕが、所属や役職を変えるかもしれないし、所有者の秘密鍵ＳＫＵが、危殆化しているかもしれない。証明書が失効した場合、他者が所有者の公開鍵を使えないようにしなければならない。
【０００５】
失効した証明書の公開鍵の使用を防ぐひとつの手法として、証明書失効リスト（ＣＲＬ）によるものがある。ＣＲＬは、ＣＡ１２０が発行する署名及びタイムスタンプが記され、失効した証明書をそれぞれのシリアル番号ＳＮによって特定するリストである。これらのＣＲＬは、新規に失効した証明書がない場合でも、いかなるタイプのリプレイ攻撃をも防止するために、定期的に配布されなければならない。通信、検索、及び検証のための費用の観点から見ると、ＣＲＬの管理はやっかいなものかもしれない。ＣＲＬの手法は、（すべての期間中のものではなく）直前の期間において失効した証明書のリストだけを送信するＣＡを有する、いわゆるデルタＣＲＬを用いて、最適化することができる。デルタＣＲＬの手法には、ベリファイヤによって証明書がいずれのデルタＣＲＬにも含まれていないことを確認しなければならないため、証明書がその時点で有効であることを認証するための計算量は基本的に期間数に比例するという点において未だ欠点がある。
【０００６】
［１５］に示したようにＣＲＬsの代わりに、証明書失効ツリー（ＣＲＴs）を使用することができる。（大括弧で示した数字は、明細書の末尾において一覧にした参考文献の番号を示す。）
ＣＲＬs及びＣＲＴsの代わりに、ＣＡ１２０は、特定の証明書についてのクエリに答えることができる。図１では、ユーザＵ２は、ユーザＵ１の証明書１０４のシリアル番号ＳＮを有するクエリ１５０を発行する。ＣＡ１２０は、シリアル番号ＳＮ、有効状況フィールド１６０ＶＳ（「有効」「無効」あるいは「不明」）、及びタイムスタンプ「時間」を含む有効状況情報１６０を以って返信する。この返信は、ＣＡによって署名される（フィールド１６０−ＳｉｇＣＡ）。この手法は、オンライン証明書状態プロトコル（ＯＣＳＰ）に利用されている。［２３］を参照。ＣＡのデジタル署名１６０−ＳｉｇＣＡでは、特にＣＡが非常に安全でなくてはならないため、とても長く（ＲＳＡの場合１０２４ビット超）なってしまうという欠点がある。また、ＣＡが集中している場合、ＣＡは、認証の障害になってしまい、ＣＡが分散化（複製）されている場合、ＣＡの署名鍵ＳＫＣＡが複製されるために安全性が低くなる。
【０００７】
図２は、ＣＡ１２０が署名していない有効状況を予め特定した時間間隔（例えば、毎日、又は毎時、など）で信頼できないディレクトリ２１０を通して提供することができる「ＮＯＶＯＭＯＤＯ」による手法を図示している。ディレクトリ２１０は、秘密情報を格納しないコンピュータシステムである。このシステムは以下のように、機能する。
【０００８】
ｆを予め定義され、長さを保存する公開関数とする。
【０００９】
ｆ：  ｛０，ｌ｝ｎ→｛０，ｌ｝ｎ
ここで、｛０，ｌ｝ｎは、長さｎの全ての２進法の文字列の集合である。ｆｉがｆ倍の合成を示すとする。つまり、ｉ＝０に対してｆｉ（ｘ）＝ｘであり、ｉ＞０に対してｆｉ（ｘ）＝ｆ（ｆｉ−１（Ｘ））である。ｆを一方向とする。すなわち、ｘがランダムに選択されるｆ（ｘ）が与えられると、無視できる程度の確率を除いて、ｆ（ｚ）＝ｆ（ｘ）となるようなプリイメージｚを見つけることは困難（実行不可能）である。ｘをランダムに選択するｆ（ｘ）が「実行不可能である」とは、セキュリティパラメータｋ（例えばｋ＝ｎ）が与えられると、無視できるほどの可能性を除いて、ｋにおける予め定義されている多項式と同じ時間内にプリイメージｚを計算することができないということである。さらに、ｆは、その反復において一方向である、すなわち、任意のｉに対してｙをｙ＝ｆｉ（ｘ）と仮定すると、ｆ（ｚ）＝ｙであるようなｚを見つけることは実行不可能である。
【００１０】
一般性を欠くことなく、ＣＡは、新しい有効状況を毎日提供し、証明書は一年、すなわち３６５日間（Ｄ２−Ｄ１＝３６５日）有効であることが要求されていると仮定することができる。証明書１０４（図２）を生成するために、ＣＡ１２０は、ランダムな「シード」となる数ｘを拾い、「ハッシュ連鎖」ｃ０、ｃ１、・・・ｃ３６５を生成する。ここで、
【数１】
2008524930.tif 000003
【００１１】
である。
【００１２】
シリアル番号ＳＮを有する証明書に対してｘをｘ（ＳＮ）、また同様にｉ＝０、１、・・・であるｃｉ＝Ｃｉ（ＳＮ）として示すことがある。この値ｃ０は、「検証ターゲット」と呼ばれる。ＣＡ１２０は、ｃ０を証明書１０４にデータ１０４Ｄとともに挿入する（図１）。ＣＡ１２０は、ランダムな失効シード番号Ｎ０も生成し、「失効ターゲット」Ｎｉ＝ｆ（Ｎ０）を計算し、Ｎｉを証明書１０４に挿入する。ＣＡ１２０は、ｉ＞０に対して全てのｃｉの秘密を維持する。値ｘ及びＮ０も秘密である。ｃｉの全てが、ｘから計算可能であり、検証ターゲットｃ０が、任意のｃｉから計算可能であることは明らかである。ＣＡ１２０は、各証明書１０４に対する値ｘ及びＮ０を個別のストレージに記憶し、（必ずしも必要ではないが）可能な限り、そのｃｉの値をキャッシュする。
【００１３】
下記のとおり、毎日ｉ（ｉ＝１、２、・・・３６５）、有効な証明書に対して証明書有効性再検証が行われる。ＣＡは、ディレクトリ２１０に証明書１０４ごとの有効性検証データ構造を配布し、その構造は有効状況を示す（図２においては図示しないが、「有効」、又は、「失効」を示す）もの以外に、
１．証明書が、ある日ｉにおいて有効である場合は、証明書の「ｉ‐トークン」ｃｉを含み、
２．証明書が失効している場合は、失効シードＮ０を含む。
【００１４】
（ｃｉを「有効性検証証明」、Ｎ０を「失効証明」と呼ぶ。）この情報は、署名無しに配布される。各ディレクトリ２１０は、有効状況リクエスト１５０に応答して、この情報を署名無しでリクエスタのシステム１１０に提供する（図１）。検証するために、リクエスタ（ベリファイヤ）１１０は、以下の工程を実行する。
【００１５】
１．有効状況が「有効」である場合は、ベリファイヤ１１０はｆｉ（ｃｉ）＝ｃ０であることを確認する。
【００１６】
２．有効状況が「失効」である場合は、ベリファイヤ１１０は、ｆ（Ｎ０）＝Ｎ１であることを確認する。
【００１７】
ｃｉが与えられると、それに続くトークンｃｉ＋１、ｃｉ＋２・・・を計算することが不可能なため、有効性情報が署名されていないにも係わらず、スキームは安全である。
【００１８】
ＣＡ１２０とディレクトリ２１０との間の通信を減らすために証明書１０４の集合に対してハッシュ連鎖（１）を生成することができ、その集合が「失効していない」（すなわち、全ての証明証が集合の中で失効していない）場合は、その集合に対して単一のｉ‐トークンｃｉを配布することができる。証明書１４０は、証明書を含みハッシュ連鎖に関連づけられた各集合に対する別個のターゲットｃ０を含む（[１]を参照）。
【００１９】
証明書の失効は、アキュムレータを用いて行うことができる。[３７]を参照。アキュムレータは、値の集合（例えば、有効な証明書の集合）を組み合わせてより短い値にする方法である。「安全な」アキュムレータの正式な定義は、明細書の末尾の付録Ａを参照のこと。アキュムレータの例は、以下のように構成することができる。累算可能な値のすべてをｐ１・・・ｐｔとして示すこととする（例えば、各ｐｉが証明書に割り当てられた個別の数字であることができ、有効な証明書に対応する値を累算したい）。ｖ０を空集合のアキュムレータ値と仮定し、ｆを一方向性関数とする。ｐ１を累算するために、アキュムレータで以下のように計算する。
【数２】
2008524930.tif 000004
【００２０】
そして、ｐ２を計算するために、アキュムレータをｖ２＝ｆ（ｖ１，ｐ２）などに設定する。より一般的には、ある集合｛Ｐｉ１，・・・，Ｐｉｍ｝に対するアキュムレータ値は
【数３】
2008524930.tif 000005
【００２１】
である。関数ｆは、累算の順番が関係ないように選択される。すなわち、
【数４】
2008524930.tif 000006
【００２２】
（これは、「準可換な」プロパティである）。
【００２３】
それぞれの期間ｊにおいて、ＣＡ１２０は、ディレクトリ２１０に対して、ペア（ｖｊ，ｔ）を送信することができる。ここで、ｖｊは、有効な証明書の集合に対するアキュムレータ値であり、ｔは、タイムスタンプである。ディレクトリは、アキュムレータ値ｖｊが、関心のある証明書に対応する値ｐｉを累算することを証明することでクエリ１５０に応答することができる。
【００２４】
一般的なアキュムレータは、以下のように定義されるＲＳＡアキュムレータである。
【数５】
2008524930.tif 000007
【００２５】
ここで、ｐは、正の整数、及びｎ＝ｑ１ｑ２は、大きい素数ｑ１とｑ２の積である。この場合、
【数６】
2008524930.tif 000008
【００２６】
である。
【００２７】
証明書の有効性検証は、次のように行われる。一般性を失うことなく、値Ｐ１，・・・，ｐｍは、期間ｊにおける有効な証明書に対応するものと仮定すると、ＣＡ１２０によってディレクトリ２１０に配布されるアキュムレータ値は、
【数７】
2008524930.tif 000009
【００２８】
である。
【００２９】
ベリファイヤ１１０が、Ｐ１，・・・，Ｐｍのうちの一の値ｐｉに対応する証明書のステータスをディレクトリ２１０に照会する場合、ディレクトリは、ベリファイヤにアキュムレータ値ｖｊ及び、「ウィットネス（ｗｉｔｎｅｓｓ）」値、
【数８】
2008524930.tif 000010
【００３０】
を送信する。
【００３１】
ベリファイヤは、
【数９】
2008524930.tif 000011
【００３２】
を確認する。
【００３３】
この等式が成り立つ場合、証明書は、有効であると考えられる。
【００３４】
ウィットネス（ｗｉｔｎｅｓｓ）は、ｖｊのｐｉ乗根を計算することが困難であるという条件において、偽造が困難である。敵がｎの因数分解を知らず、強ＲＳＡ仮定が有効である場合、（この仮定については、付録Ａにおいて定義する）ｐｉ乗根の計算は、困難である。しかしながら、ｐｉ及びｓｉ,ｊを秘密の状態に保つことは可能である。例えば、値ｓｉ,ｊ及びｐｉをベリファイヤに提供する代わりに、そのような値が存在し、そのような値を証明書の所有者が知っているという証明をベリファイヤに提供することができる。
【００３５】
アキュムレータは、エレメントが予め特定されたプロパティを満たすことを証明することにおいて、より一般的に用いることができる。
【発明の開示】
【発明が解決しようとする課題】
【００３６】
本発明の目的は、アドホックネットワークなどのネットワーク上でのアキュムレータデータの配布を容易にすることである。
【課題を解決するための手段】
【００３７】
このセクションでは、本発明のいくつかの特徴を要約する。他の特徴については、本明細書の他の箇所に記載する。本発明は、添付の請求項によって定義される。
【００３８】
本発明のいくつかの実施形態において、アキュムレータは、累積値に対応する指数を有するモジュラルートを使用して構成される。例えば、あるプロパティを有する全てのエレメント（例えば、全ての有効な証明書）、又は、そのプロパティを持たない全てのエレメント（例えば、全ての失効した証明書）を累算するためのアキュムレータが必要であると仮定する。各エレメントを１よりも大きい整数と関連づける。ＰＰｍ＝｛ｐ１，・・・，ｐｍ｝を、累算されるエレメントに関連づけられた整数の集合とし、これらの整数の積をＰｍ：
【数１０】
2008524930.tif 000012
【００３９】
として記す。
【００４０】
（本明細書では、ＰＰｍが空である場合、数字の空集合の積は１、すなわち、Ｐｍ＝１であると定義する）。いくつかの実施形態において、アキュムレータ値は、ある値ｕのＰｍ乗根、例えば、
【数１１】
2008524930.tif 000013
【００４１】
を表す。
【００４２】
いくつかの実施形態において、次のような利点が得られる。
【００４３】
値（１１）は、有効なデジタル証明書を累算するものと仮定する。値（１１）は、べき乗することにより修正し、所与の値ｐｉ以外の全ての値ｐｌをディアキュムレートすることができる。すなわち、
【数１２】
2008524930.tif 000014
【００４４】
を計算することができる。
【００４５】
このべき乗は、絶対値ｎの因数分解を知らなくても、ディレクトリ２１０、又は、証明書の所有者のシステム１１０によって実行することができる。値（１２）は、ｐｉがあたかも唯一の累積値であるようなアキュムレータ値である。検証に必要とされるウィットネス値も、ｐｉがあたかも唯一の累積値であるかのように計算することができる。検証（認証）は、ｐｉ以外の累積値に依存しない値を用いて行うことができる。あるいは、検証は、必ずしも全ての累積値ではなく、いくつかの他の累積値を組み込むアキュムレータ値及び、ウィットネス値を用いて行うことができる。そのため、ディレクトリ２１０、又は、ユーザ１１０が、全て未満の証明書に対して有効証明を提供することを請け負う場合、ディレクトリ２１０、又は、ユーザ１１０（「有効証明者」）は、全て未満の有効な証明書を累算するアキュムレータを使用することができる。いくつかの実施形態において、この特徴によって、全ての証明者が実行する必要がある計算の数が減少する。
【００４６】
いくつかの実施形態において、値ｕ＝ｕ（ｊ）は（（７）のＶ０とは異なり）、認証が提供される期間ｊによって決めることができる。そのため、タイムスタンプｔを省略することができる。
【００４７】
いくつかの実施形態において、アキュムレータは、有効な証明書よりも失効した証明書を累算し、他の実施形態においては、整数ｐｉに対するウィットネス値は、他のｐの値によって決まる。
【００４８】
いくつかの実施形態において、ウィットネス値を、有効証明を暗号化するための暗号鍵として使用する。有効証明は、例えば、図２に示すような非アキュムレータ型検証システムを用いて構成することができる。例えば、ｃｊ（ｉ）が、証明書１４０．ｉに対する期間ｊのトークンｃｊを示すものとする。ここで、ｃｊは、（１）のように構成される。ユーザシステム１１０が、証明書検証システムに加わるセットアップ時に、ＣＡは、ユーザに対して全ての期間ｊに対するトークンｃｊ（ｉ）を生成する。また、ＣＡは、全ての期間ｊに対するウィットネス値も生成する。ＣＡは、対称暗号方式の下、期間ｊのウィットネス値と同一（又は、ウィットネス値から得られる）鍵の下に各トークンｃｊ（ｉ）を暗号化する。ＣＡ１２０はこの暗号化された全ての値をユーザへ送信する。
【００４９】
各期間ｊにおいて、証明書１４０.ｉが、まだ有効である場合、ＣＡ１２０が、期間ｊの復号鍵（ウィットネス値）をユーザに対して送信することによって、ユーザは、トークンｃｊ（ｉ）を回復することができる。ユーザは、図２に関連して上記に説明したような証明書の有効性を証明するためにトークンをベリファイヤに提供する。
【００５０】
本発明のいくつかの実施形態は、例えば、アドホックネットワークのように、ノード１１０の計算処理能力及び、送信電力が低く、また、ノードが、ネットワークのトポロジーについて不完全な情報しか持ち合わせていない制限付き帯域幅、又は、信頼性の低いネットワークに対して適当である。（アドホックネットワークは、モバイルルータの自己構築型無線ネットワークである）
いくつかの実施形態は、通信及び、記憶に有効である。
【００５１】
本発明は、上述した特徴や利点に限定されるものではない。他の特徴については、以下に説明する。本発明は、添付の請求項によって定義される。
【発明を実施するための最良の形態】
【００５２】
このセクションにおいて説明する実施形態は、本発明を説明するものであるが、本発明を制限するものではない。本発明は、添付の請求項によって定義される。
【００５３】
以下の説明において、詳細を明記する。しかしながら、本発明は、これらの詳細がなくても実施できる。以下に続く詳細な説明のいくつかの箇所は、アルゴリズムやコンピュータメモリ内のデータビットにおけるオペレーションの記号表現で表わされている。これらのアルゴリズム的説明及び表現方法は、データ処理技術の分野の当業者によって利用される手段であり、彼らの研究内容を他の当業者に最も効果的に伝えるものである。ここでのアルゴリズムは、また、一般的にも、所望する結果へ導く自己無撞着な一連のステップであると考えられる。これらのステップには、物理量の物理的な操作が必要である。必ずそうであるというわけではないが、通常、これらの量は、記憶、転送、結合、比較が可能、又は、その他の操作が可能な電気的、又は、磁気的信号の形式をとる。主に共同利用のために、これらの信号をビット、値、エレメント、記号、特徴、用語、数字などとして参照することが時には便利であるとされている。
【００５４】
しかしながら、これら全て、又は、同様の用語が、適当な物理量に関連づけられ、これらの物理量に適用した便利なラベルに過ぎないことを留意する必要がある。以下の議論から明らかなように、特別に言及しない限り、明細書を通して、「処理する（ｐｒｏｃｅｓｓｉｎｇ）」、「計算する（ｃｏｍｐｕｔｉｎｇ）」、「計算する（ｃａｌｃｕｌａｔｉｎｇ）」、「決定する（ｄｅｔｅｒｍｉｎｉｎｇ）」、「表示する（ｄｉｓｐｌａｙｉｎｇ）」などの用語を利用する議論は、コンピュータシステムのレジストリやメモリ内の物理的（電気的）量として表わされるデータを操作し、コンピュータシステムメモリ、レジストリ、他の情報ストレージ、あるいは通信、又は、表示装置内の物理量として同様に表わされる他のデータに変換するコンピュータシステムのアクションやプロセス、又は、同様の電子計算装置に言及していると考えるものとする。
【００５５】
本発明は、本明細書においてオペレーションを実行する装置にも関する。この装置は、要求される目的のために特別に構成されてもよいし、コンピュータに記憶されたコンピュータプログラムによって選択的に稼働させたり、又は、再構築されたりした汎用コンピュータによって構成してもよい。限定されるわけではないが、フロッピィディスク、光学ディスク、ＣＤ−ＲＯＭ、及び光磁気ディスクを含む各種ディスク、読み取り専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気、又は、光学カードなどのコンピュータで読み取り可能な記憶媒体、又は、電気的命令を記憶するのに適している全ての種類の媒体、及びコンピュータシステムに連結されたそれぞれに、そのようなコンピュータプログラムを記憶してもよい。
【００５６】
本明細書に表わすアルゴリズムは、本質的に、特定のコンピュータ、又は、その他の装置に関するものではない。様々な汎用コンピュータシステムは、本明細書の教示に従ってプログラムを使って使用してもよいが、必要な動作を実行するために、より特殊な装置を構成することが好都合となることもある。これらの様々なシステムに対して必要な構造は以下の説明から明らかとなる。また、本発明は、特定のプログラム言語を用いて説明することはしない。機械で読み取り可能な媒体には、情報を機械（例えば、コンピュータ）で読み取り可能な形式で記憶したり送信したりする全てのメカニズムが含まれる。例えば、機械で読み取り可能な媒体には、読み取り専用メモリ（「ＲＯＭ」）、ランダムアクセスメモリ（「ＲＡＭ」）、磁気ディスクストレージ媒体、光学ストレージ媒体、フラッシュメモリ装置、及び、電気的、光学的、音響的、又は、他の形式の伝搬シグナル（例えば、キャリアウェーブ、赤外信号、デジタル信号等）等が含まれる。
【００５７】
前  提
モデル及び表記法
本発明のモデルでは、認証局ＣＡ、証明書の所有者又は保持者であるオーナー、及び証明書ベリファイヤＶＶを所有している。ここで、オーナーは、ＣＡが発行した証明書を持っている。認証局の概念を、より一般的に、アクセス制御特権や認証を複数の個人に対して発行する権限を有する任意の発行局に当てはめてもよい。所有者の概念は、特定の人間、又は、コンピュータを動作する組織、もしくは、例えば、ワールドワイドウェブサーバなどのコンピュータ自体に関係している。同様に、ベリファイヤは、特定の人間、又は、コンピュータを動作する組織、もしくは、あるサービスへのアクセスを許可すべきかどうかを決定するアクセス制御サーバなどのコンピュータ自体に関係している。
【００５８】
所与のトランスアクションにおいて、ＶＶは、証明書が、その有効期限前に失効していないことを確実にしたいと望んでいる。そのためには、ＶＶは、認証局ＣＡによって発行される、又は、発行済みの有効性証明、あるいは、失効証明を入手しなければならない。ＶＶは、この証明を、ＣＡから直接、又は、他の配布機構を介して入手することができる。
【００５９】
｛０，１｝＊が、全てのビット文字列の集合を示すものとする。ビット文字列ｓに対して、その長さを｜ｓ｜で示す。Ｈが、ｂ−ビットのペイロード及び、ｖ−ビットの初期設定ベクトル、又は、ＩＶを入力として取り、ｖ−ビットの出力を生成する暗号学的な圧縮関数を示すものとする。
【数１３】
2008524930.tif 000015
【００６０】
と仮定するが、これは、使用している公知の構造の全てに対して成り立っている。ここで説明する構造に対しては、基本的には、ｂ＝２ｖを取る。これらの暗号学的な圧縮関数は、衝突耐性を持つものと仮定する。すなわち、Ｈ（ＩＶ，ｍ１）＝Ｈ（ＩＶ，ｍ２）となるような２つの異なる入力値ｍ１≠ｍ２を見つけることは困難である。ＩＶは、固定されており、公知であると仮定する。説明を簡潔にするために、ハッシュ関数における引数としてＩＶを常に詳細に一覧にすることはしない。そのような暗号学的な圧縮関数の実際の例は、ＳＨＡ−１［２６］である。ＳＨＡ−１の圧縮関数は、出力、及び、ペイロードサイズが２０−バイトと６４−バイトのＩＶサイズを有する。多くの実施形態において、この圧縮関数のペイロードサイズより大きいデータに関して操作する必要はない。しかしながら、そのようなデータを操作するための反復したハッシング、又は、メルクル−ツリー［１９］などの数多くの標準的な技術が存在している。説明を簡単にするために、圧縮関数の代わりにハッシュ関数という用語を使用するが、ここでは、ハッシュ関数が任意の長さの文字列｛０，１｝＊をとることができ、｛０，１｝ｖにおける固定された長さの出力を生成すると認識するものとする。
【００６１】
実際、長さを保存するために、ハッシュ関数Ｈで始まり、ペイロードの部分を埋め込むことによるその反復において一方向である長さを保存する関数を構成することがよくある。
【００６２】
最後に、実数ｒに対して、
【数１４】
2008524930.tif 000016
【００６３】
が、ｒの天井関数、すなわち、ｒ以上の最小整数値となるようにする。同様に、
【数１５】
2008524930.tif 000017
【００６４】
は、ｒの床関数、すなわち、ｒ以下の最大整数値を示す。
【００６５】
Ａをアルゴリズムとする。Ａ（・）によって、Ａが、ひとつの入力を有することを示す。Ａ（・，．．．，・）によって、Ａがいくつかの入力を有することを示す。Ａ（・）によって、Ａがアルゴリズムの指標付き群であることを示す。ｙ←Ａ（ｘ）は、ｙが、Ａを入力ｘ上で実行することによって求められたことを示す。Ａが決定的である場合、このｙは、一意であり、Ａが確率的である場合、ｙは、ランダム変数である。Ｓが集合である場合、ｙ←Ｓは、ｙが、Ｓから均一にランダムに選択されたことを示す。ｂをブール関数とする。（ｙ←A(ｘ)：ｂ（ｙ））という表記は、ｙが、Ａを入力ｘ上で実行することによって生成した後に、ｂ（ｙ）が真である事象を示す。最後に、
【数１６】
2008524930.tif 000018
【００６６】
という表現は、値ｘｎを、アルゴリズムＡ１，．．．，Ａｎを入力ｙ１，．．．，ｙｎ上で実行することにより求めた後に、ｂ（ｘｎ）が真である確率を示す。
【００６７】
有効な証明書のアキュムレーション
以下、いくつかのアキュムレータスキームを、デジタル証明書の認証に関して説明する。これらのスキームは、上述したように、他の認証オペレーションに用いることもできる。
【００６８】
説明を簡潔にするために、各証明書の所有者Ｕｉが、ひとつのシステム１１０．ｉだけを操作し、多くともひとつの証明書を所有するものと仮定する。これは、実際には必要ない。
【００６９】
ＣＡのセットアップ
ＣＡ１２０は、合成数ｎを生成する。いくつかの実施形態において、ｎは、２つの素数の積であるが、ｎは、３つ以上の素数の積とすることもできる。いくつかの実施形態において、ｎは公開されているが、ｎを因数分解することは困難であり、その因数分解は、ＣＡ１２０だけが知っているものである。
【００７０】
初期証明書（図４）
ｉ−番目のユーザｕｉが、ある期間ｊ０に、又は、その後にシステムに参加したとする。ステップ４１０において、ＣＡは、正の整数ｐｉをｕｉに割り当てる。数字ｐｉは、法（ｍｏｄ）ｎで互いに素となるように選択される。また、各ｐｉは、残りの数字ｐｌ（ｌ≠ｉ）のＬＣＭ（最小公倍数）を除法しない。例えば、数字ｐ１，．．．，ｐｉは、相異なる素数、又は、２つずつ互いに素であってもよい。
【００７１】
ＣＡは、ユーザｕ１に対して固有の公開値ｍｉ∈（Ｚ／ｎＺ）＊を計算する（Ｚ／ｎＺは、ｎを法とするすべての剰余環であり、（Ｚ／ｎＺ）＊は、Ｚ／ｎＺの可逆元、すなわち、ｎで互いに素である整数によって定義される元の乗法群である）。
【数１７】
2008524930.tif 000019
【００７２】
ここで、Ｈ１は、予め定義された、例えば、一方向の衝突耐性をもつ関数であり、ｕiは、ユーザを識別するもの（例えば、ユーザ名）であり、ｗｉは、任意の文字列（ｕiの公開鍵、及び／又は、他の情報を含んでいてもよい）である。よって、ｍｌ値は、ｐｉをｕｉのアイデンティティに設定する。必要に応じて、値ｊ０、ｐ１、ｍｌのいずれかひとつ以上の値、及び、関数Ｈ１の識別を、証明書１４０の一部とすることができる。ｍｌとｊ０を含み、関数Ｈ１とＨ２（Ｈ２については、以下に説明する）を特定する証明書１４０を示す図３を参照のこと。
【００７３】
ステップ４２０において、ＣＡは、「初期証明書」の値を計算する。
【数１８】
2008524930.tif 000020
【００７４】
ＣＡは、この値を秘密に保ち、それを暗号化した形式でユーザｕ１のシステム１１０に送信する。
【００７５】
期間ｊにおけるＣＡによる証明書有効性再検証（図５）
期間ｊの始まり、又は、その少し前に、ＣＡは、以下の動作を行う。ｔが、システムにおけるユーザの総数（すなわち、図４の初期証明書が実行されているユーザの総数）を示すものとする。ＵＵが、これらのユーザの集合を示すものとする。つまり、ＵＵ＝｛ｕ１，．．．，ｕｉ｝。ＰＰが、対応するｐの数の集合を示すものとする。つまり、ＰＰ＝｛ｐ１，．．．，ｐｉ｝。ＵＵｊ⊆ＵＵを、期間ｊにおいて有効性再検証されるユーザの部分集合とし、ＰＰｊ⊆ＰＰを、数ｐの対応する集合とし、
【数１９】
2008524930.tif 000021
【００７６】
とする。
【００７７】
すなわち、Ｐｊは、ＰＰｊにおける整数の積である（数の空集合の積は１であると定義する）。ＣＡは、
【数２０】
2008524930.tif 000022
【００７８】
を計算する。ここで、Ｈ２は、Ｈ１と同じ関数、又は、他の関数である。また、ＣＡは、アキュムレータも計算する。
【数２１】
2008524930.tif 000023
【００７９】
いくつかの実施形態において、（１７）のルートは、非常に高い確率で存在していることに注目すべきである。
【００８０】
ＣＡは、以下のデータをＵＵｌにおける各ユーザのシステム１１０に送信する（このデータは、通信の観点からより効率的である場合、より大きいユーザ集合に対して一斉通信することができる）。
【００８１】
１．ｖｊ
２．ＰＰｊにおける単なる数ｐｉの一覧である、ＵＵｊにおけるユーザの一覧（異なる期間ｊでの一覧同士は重複することがあるので、ＣＡは、直前の期間から変更された情報だけを送信することができる。この場合、ＣＡは、ＰＰｊにおける数の一覧を、図４のステップ４３０において新規の各ユーザに送信する。）
パーソナルアキュムレータ及びユーザによるウィットネスの導出
ステップ６１０において、ＵＵｊにおける各ユーザｕｉは、「パーソナルアキュムレータ」ｖｊ（ｐｉ）、すなわち、ユーザのｐｉ値だけを累算するアキュムレータを計算する。
【数２２】
2008524930.tif 000024
【００８２】
この値は、累乗法によりｖｊの値（１７）から計算される。
【数２３】
2008524930.tif 000025
【００８３】
ステップ６２０において、ユーザは、このパーソナルアキュムレータを先行するパーソナルアキュムレータと合計して、期間ｊのウィットネスを求める。
【数２４】
2008524930.tif 000026
【００８４】
等式（２０）及び（１４）は、
【数２５】
2008524930.tif 000027
【００８５】
を意味する。
【００８６】
ユーザ認証（図７）
ユーザｕｉは、ｓｉ，ｊを、（必要であれば）（ｕｉ，ｐｉ，ｊ０，ｗｉ）に対する値とともに、ベリファイヤに提供することができる。ステップ７１０において、ベリファイヤは、
１．（１３）からｍｉを計算する、又は、それを証明書１４０（図３）から入手する
２．ｈｊ＝Ｈ２（ｊ）及び、
【数２６】
2008524930.tif 000028
【００８７】
を計算する（（１６）参照）
３．
【数２７】
2008524930.tif 000029
【００８８】
を確認する。
【００８９】
代替ユーザ認証
ウィットネスｓｉｊをベリファイヤに与える代わりに、ユーザは、ｓｉｊを、識別に基づくＧＱ（ギユ・キスケータ（Ｇｕｉｌｌｏｕ−Ｑｕｉｓｑｕａｔｅｒ））署名方式における秘密鍵として用いることができる。この方式は、明細書の末尾の付録Ｂにおいて説明する。ＣＡは、ＧＱのＰＫＧ（秘密鍵ジェネレータ）の関数を実行する。ＧＱのパラメータは、Ｂ＝ｓｉｊ、V=ｐｉ、及びＪ＝ｍｉ−１ ｍｏｄ nと設定される。認証は、以下のように進む。
【００９０】
ベリファイヤは、ユーザにランダムなメッセージｍを送信する。
【００９１】
ユーザは、ランダムな数字ｒを生成し、
【数２８】
2008524930.tif 000030
【００９２】
を計算する。ここで、Ｈは、予め定義されたある公開関数（例えば、Ｈ１又はＨ２）である。ユーザは、値ｍ、
【数２９】
2008524930.tif 000031
【００９３】
、及びＤをベリファイヤに送信する。
【００９４】
ベリファイヤは、
【数３０】
2008524930.tif 000032
【００９５】
を計算し、次の等式が成り立つことを確かめる。
【数３１】
2008524930.tif 000033
【数３２】
2008524930.tif 000034
【００９６】
ベリファイヤは、証明書１４０を必要としないので、このスキームは、全帯域幅を減らすことが可能である。ＧＱ署名方式を安全なものとするために、ｐｉ＞２１６０であることが望ましいことに留意されたい。
【００９７】
備考
１．まず、
【数３３】
2008524930.tif 000035
【００９８】
は、必ずしも（１４）でなくとも他の方法で計算することができる。
【００９９】
２．匿名認証
ユーザノード１１０が、メッセージに匿名で署名できるようにしたい場合、すなわち、ユーザノード自体をＣＡが証明したユーザとして、実際のアイデンティティを明かすことなく認証することができるようにしたい場合、本発明では、初期証明書を別の方法で取り扱うことができる。例えば、（１３）の代わりに、ＣＡは、ｍｉをユーザのアイデンティティから独立するものとして設定することができる。例えば、
【数３４】
2008524930.tif 000036
【０１００】
そして、ｍｉ値が、ユーザに提供される。ｍｉ値が、ユーザに提供されるという事実を隠すために、ｍｉ値を、セキュアチャンネルを介して（例えば、この値をｕｉだけが復号できるように暗号化することによって）ユーザに送信してもよい。そして、それは、（１４）及び（２１）に続き、
【数３５】
2008524930.tif 000037
【０１０１】
となる。
【０１０２】
以下、付録Ａに説明するように、それによってユーザｕｉがｊ番目の期間に整数の特定された区間Ｉに含まれる（明かされていない）数ｐに対して、ｎを法とするｊｉのｐ乗根、すなわち、
【数３６】
2008524930.tif 000038
【０１０３】
を知っていることを証明することができる有効なゼロ知識（ＺＫ）証明が存在している。
【０１０４】
［４１］及び［４２］参照。区間Ｉは、全ての数ｐｉを含む区間となることができる。このスキームを用いることで、ユーザは、初期証明書ｓｉ，ｊ０及び、その後に続くパーソナル累積値ｖｊ（ｐｉ）を入手した場合、ユーザ自体を匿名のうちに認証することができ、匿名のうちに認証することができるのは、その場合に限る。（（１８）及び（１９）を参照）。
【０１０５】
ＣＡは、以前のように、すなわち、ユーザを有効性再検証せずに（図５の積Ｐｊにおけるｐｉは含まずに）、ユーザを取り消すことができる。
【０１０６】
上述したように、アキュムレータの技術は、単一の証明書を所有するユーザ、又は、デジタル証明書の失効に限定されるものではない。例えば、ユーザｕｉは、ひとつ以上の権利ｅ１，ｅ２，．．．，ｅｒを保有しても、保有しなくてもよい。初期証明の間に、ユーザｕｉが、権利ｅｋを与えられる場合は、ユーザには固有の整数ｐｉ，ｋが割り当てられる。権利証明は、ｐｉ，ｋによって取って代わられる数ｐｉ及び、ｓｉ，ｋ，ｊによって取って代わられるｓｉ，ｊなどのように、等式（１３）乃至（２６）に関して上述したように進む。
【０１０７】
しかしながら、これらの実施形態のいくつかにおいて、値ｐｉは、ｐｉ，ｋの積として計算される。例えば、ユーザが、初めに全ての権利を与えられた場合、
【数３７】
2008524930.tif 000039
【０１０８】
である。
【０１０９】
いくつかの実施形態において、整数ｐｉ，ｋは、互いに素であり、かつ、ＣＡの法ｎに対しても素である。ユーザｕｉの初期証明書は、（１４）のように
【数３８】
2008524930.tif 000040
【０１１０】
であり、ユーザｕｉは、べき乗を用いて、任意のｋに対する選択された値ｐｉ，ｋを除く全ての値ｐｉ，ｌをディアキュムレートすることができる。
【数３９】
2008524930.tif 000041
【０１１１】
ユーザは、この値を用いて、ユーザの他の権利を明らかにすることなく、ユーザが、素数ｐｉ，ｋに対応する権利を有することを示すことができる。ＣＡは、ユーザの他の権利を取り消すことなく、ｐｉ，ｋを累算しない（１７）における有効性アキュムレータを発行する（すなわち、ｐｉが、ｐｉ／ｐｉ，ｋによって置換されることを除いて、積ｐｊが、（１５）のように計算される（数ｐｉ，ｋは積には含まれない））だけで、ユーザに対する特定の権利ｅｋを取り消すことができる。ユーザが、リンクできないように匿名で署名したい場合、ユーザは、その特定のｐｉ，ｋの値を明らかにすることができないが、（ベリファイヤが、特定のｐｉ，ｋの値を見られない場合）、ユーザがどの権利を請求しているかをベリファイヤが断定することを困難にしているように思われる。例えば、各権利ｅｋを整数Ｉｉの範囲に関連づけることで、この問題を回避することができる。この範囲は、初期に権利ｅｋを所与した全てのユーザに対する全てのｐｉ，ｋ値を含む。範囲Ｉｋは、いくつかの実施形態において重複することはない。そして、ユーザは、ＺＫにおいて、（範囲Ｉｋにおいて明らかにされていない数ｐに対する）適当な値のモジュールのｐ乗根を所有していることを証明することができる。すなわち、ユーザは、次の知識証明を提供することができる。
【数４０】
2008524930.tif 000042
【０１１２】
ここで、Ｃ＝ｍｉｈｊ／ｈｊ−１、又は、Ｃ＝ｈｊ（（２１）及び（２６）参照）である。［４１］及び［４２］を参照。また、ユーザは、例えば、請求されている権利に対応する範囲における（例えば）２つの整数ｐ１とｐ２の積である任意のｐに対するｐ乗根を所有していることを証明することによって、複数の権利を同時に所有していることも証明するができる。
【数４１】
2008524930.tif 000043
【０１１３】
［４１］及び［４２］を参照のこと。
【０１１４】
ネットワークからネットワークへ移動するユーザ
ＣＡが、相異なるネットワーク上にユーザ（証明書所有者システム）１１０を有し、ユーザは、ネットワークから（例えば、ネットワークのうちのいくつかは、アドホックネットワークでもよい）他のネットワークへ移動するものと仮定する。ＣＡは、各ネットワークに対して個別のアキュムレータ（（１７）など）を計算することができる。各アキュムレータは、各ネットワークにおけるユーザの現在の構成についてのＣＡの知識に基づいて、対応するネットワーク上の有効なユーザだけを累算する。各ユーザは、（例えば、（１８）、（２０）（２６）、及び／又は、（２８）のように）それぞれのパーソナルアキュムレータ値、及び／又は、ウィットネス値を計算する。ユーザは、別のネットワークに移動することができ、他のネットワークにおいて同じパーソナルアキュムレータ値、及び／又は、ウィットネ値を使うことができる。
【０１１５】
パーソナルアキュムレータの集約
複数のパーソナルアキュムレータは、帯域幅を節約するために、単一の値に集約することができる。この集約した値から、ベリファイヤは、複数のユーザが実際に承認されていることをバッチ検証することができる。例えば、等式（１７）及び等式（２２）のスキームにおいて、ユーザｕｉは、（まだ有効である場合）
【数４２】
2008524930.tif 000044
【０１１６】
を満たすパーソナル値ｓｉ，ｊを所有している。ここで、ｍｉは、（１３）と同様であり、ｊ０，１は、ユーザｕｉに対する期間ｊ０である。
【数４３】
2008524930.tif 000045
【０１１７】
を示す。
【０１１８】
そして、期間ｊにおける複数のユーザに対して、ユーザのパーソナル値は、単純に一緒に積算することができる。
【数４４】
2008524930.tif 000046
【０１１９】
ここで、ｔ’は、集約に加わっているユーザの数（あるいは、各ｕｉが、証明書、又は、権利である場合、証明書、又は、ユーザに属する権利の数）である。ベリファイヤは、値（３３）を用いて、
【数４５】
2008524930.tif 000047
【０１２０】
であることを確認することによって、ユーザ(あるいは、証明書、又は、権利)（ｕ１，．．．，ｕｉ）が、有効であることを確認することができる。
【０１２１】
ディアキュムレーション
ここでは、ＣＡによって計算されたアキュムレータからの値をディアキュムレートする具体的な手法について議論する。しかしながら、ＣＡは、ネットワーク上の全ての有効なノード１１０に関連づけられた全ての値を累算する単一のアキュムレータ値を計算する必要がないことを記しておく。その代わりに、ＣＡは、次に説明するトレードオフを使用することができる。ディアキュムレーションは、幾分、計算上不経済である。以下の手順Ｓｐｌｉｔ（ｖ，Ｐ）は、ｔ個のｋ−ビット数Ｐ＝｛ｐｉ｝を累算するアキュムレータｖにおいてディアキュムレーションを実行する。この手順の出力は、ｔ個のパーソナルアキュムレータであり、実行時間は、Ｏ（ｔｌｏｇ２ｔ）（ここでは、ｋは一定であると見なす）である。空集合の値を累算するアキュムレータをｕとして示す（等式（１７）において、ｕ＝ｈ（ｊ）／ｈ（ｊ−１））。
【０１２２】
そして、
【数４６】
2008524930.tif 000048
【０１２３】
手順Ｓｐｌｉｔ（ｖ，Ｐ）
１．集合Ｐを２つの独立した２つのＰ１とＰ２に等分する。
【０１２４】
２．
【数４７】
2008524930.tif 000049
【０１２５】
を計算する。これは、集合Ｐ１に対するアキュムレータである。
【０１２６】
３． 
【数４８】
2008524930.tif 000050
【０１２７】
を計算する。これは、集合Ｐ２に対するアキュムレータである。
【０１２８】
４．Ｐ１が、ひとつの要素だけを持つ場合、（ｖ１，Ｐ１）を出力し、そうでなければ、Ｓｐｌｉｔ（ｖ１，Ｐ１）を呼び出す。
【０１２９】
５．Ｐ２が、ひとつの要素だけを持つ場合、（ｖ２，Ｐ２）を出力し、そうでなければ、Ｓｐｌｉｔ（ｖ２，Ｐ２）を呼び出す。
【０１３０】
Ｓｐｌｉｔ（ｖ，Ｐ）の終了
経験的に述べると、ｎを法とする数をｔ’個の数の積によって累乗することは、ｔ’に比例して時間がかかるので、最初の分割動作（手順Ｓｐｌｉｔ（ｖ，Ｐ）におけるステップ２とステップ３）は、上記の反復において最も不経済なものである。（実際、ｔ個の相異なる数字（ｐ１，．．．，ｐｔ）が存在するので、ｐiは、平均でそれぞれＯ（ｌｏｇｔ）ビットであるため、累乗は、ｔ’ｌｏｇｔ’に比例し、分割アルゴリズムは、ｌｏｇｔ’の深さまで再帰することができるので、全体の計算処理量は、ｔｌｏｇ２ｔである。）実行しなければならないディアキュムレーションの量を減らすため、ＣＡは、（例えば）Ｐの２つに分割したＰ１とＰ２のそれぞれに対する２つのアキュムレータを計算し、これらの２つのアキュムレータをユーザに送信することによって、ユーザが、最初の分割動作を行わず、計算量を減らすことができる。ＣＡは、さらに小規模なユーザの部分集合のそれぞれに対する、さらに多くのアキュムレータを送信することによって、計算量をさらに減少させることができる。複数のアキュムレータを計算する際に、ＣＡが、現在のネットワークトポロジーの知識を用いることは、スキームのパフォーマンスを高めるために有利である。例えば、ユーザが、いくつか（例えば、１０）のトポロジー領域に分割されているものとする。そして、（１５）のように整数Ｐｊのひとつの積を用いる代わりに、ＣＡは、１０のそのような値Ｐｊ，１，．．．，Ｐｊ，１０及び、１０領域の特定されたアキュムレータ
【数４９】
2008524930.tif 000051
【０１３１】
を計算することができる。その後、ＣＡは、これら１０の領域の特定されたアキュムレータのそれぞれを、それぞれの１０のトポロジー領域に対して（その領域における有効性再検証したユーザの一覧とともに）送信する。所与の領域におけるユーザは、パーソナルアキュムレータ及びウィットネスを、領域の特定されたアキュムレータから計算することができる。
【０１３２】
ディアキュムレーションも、パーソナルアキュムレータ（１８）及び（１９）がどのように計算されるかに関連している。計算処理という点からすると、ディアキュムレーション（１８）とディアキュムレーション（１９）を独立して実行することは、ｔ人の各ユーザにとって最適でないことはあきらかである。なぜなら、この方法をとった場合、Ｏ（ｔ２）の計算をが必要となるからである（実際には、ｐｉのサイズは、少なくともｌｏｇｔと同じだけ早く増加しなければならないため、一層不利である）。いくつかの実施形態において、ユーザは、例えば、図８に図示し、以下に説明するように、パーソナルアキュムレータを協同的に計算する。
【０１３３】
性能測定基準が最小通信である場合、アキュムレータ（１７）のＣＡによるｔ人のユーザに対する簡単な一斉通信（図５参照）は、アキュムレータ配布の好適な方法である。これにより、全体の通信がＯ（ｔ）となるが、ｔ人のユーザのそれぞれが、同じアキュムレータに関してｔ−１の累乗を実行しなければならないので、全体の計算は少なくともＯ（ｔ２）である。
【０１３４】
図８において、ＰＰｊを有効なユーザの集合（すなわち、有効なユーザに対応するｐの数の集合）とする。図５（有効性再検証）のステージにおいて、ＣＡは、アキュムレータｖｊ（ＰＰｊ）（例えば、（１７）参照）及び、集合ＰＰｊにおける数ｐを指定され（及び、図８においてＤと印され）たノード１１０に送信する。ノードＤは、集合ＰＰｊを部分群（部分集合）に分割する。一例において、部分群ＰＰｊ−０には、ノード１１０．０、１１０．００、１１０．０１のうちひとつ以上が含まれ、部分群ＰＰｊ−１には、ノード１１０．１、１１０．１０、１１０．１１のうちひとつ以上が含まれ、第３の部分群は、ノード１１０が有効なノードである場合は、ノード１１０から構成される。ノードＤは、部分群ＰＰｊ−０に対するアキュムレータｖｊ（ＰＰｊ−０）及び、部分群ＰＰｊ−１に対するアキュムレータｖｊ（ＰＰｊ−１）を計算する。この計算は、部分群の要素ではないノードをディアキュムレートすることによって実行することができる。例えば、等式（１９）及び手順Ｓｐｌｉｔ（ｖ，Ｐ）のステップ１とステップ２を参照のこと。ノードＤが有効である場合（すなわち、数ｐが、ＰＰｊの中にある場合）、ノードＤは、図６のようにパーソナルアキュムレータを計算する。ノードＤは、アキュムレータｖｊ（ＰＰｊ−０）及び、集合ＰＰｊ−０におけるｐ個の数をノード１１０．０に送信する。ノード１１０．０及び、ノード１１０．１は、ノードＤと同じ動作を実行する。特に、ノード１１０．０は、有効なユーザＰＰｊ−０を部分群に分割する。一例において、ノード１１０．０、１１０．００、１１０．１は有効であり、部分群ＰＰｊ−０−０は、ノード１１０．００から成り、部分群ＰＰｊ−０−１は、ノード１１０．０１から成り、第３の部分群は、ノード１１０．０から成る。部分群は、ＰＰｊ−０におけるｐ個の数からノード１１０．０によって決定される。ノード１１０．０は、それぞれの部分群ＰＰｊ−０−０及び、ＰＰｊ−０−１に対するアキュムレータｖｊ（ＰＰｊ−０−０）及びｖｊ（ＰＰｊ−０−１）を計算し、図６のように自身のパーソナルアキュムレータも計算する。ノード１１０．０は、アキュムレータｖｊ（ＰＰｊ−０−０）及び、対応するｐの数を、ノード１１０．００に送信する。ノード１１０．０は、アキュムレータｖｊ（ＰＰｊ−０−１）及び、対応するｐの値をノード１１０．０１に送信する。アキュムレータｖｊ（ＰＰｊ−０−０）及び、ｖｊ（ＰＰｊ−０−１）は、パーソナルアキュムレータなので、ノード１１０．００及び、ノード１１０．０１は、自身のパーソナルアキュムレータを計算し、導き出す必要はない。
【０１３５】
ノード１１０．１は、ノード１１０．０に対するものと同様の動作を実行する。
【０１３６】
この手順は、どのような数のノードに対しても再帰的に拡張することができる。手順は、図８の「二分木」型に限定されるものではない。ノードは、それ自体の他に、ユーザの集合をどのような数の部分群にも分割することができ、その結果、非二分木型動作となる可能性がある。また、いくつかの実施形態において、アキュムレータは、有効なノードに対してだけ送信される。例えば、ノード１１０が無効である場合、ＣＡ１２０は、代わりにアキュムレータｖｊ（ＰＰｊ）を有効なノードに送信する。通信効率のために、部分群を通信が各部分群内において有効であるように選択する。例えば、アドホックネットワークの場合、部分群は、近接したノードを一緒に分類した状態で、地理的近接性に基づいて選択することができる。
【０１３７】
ここで、ノードがローカルなトポロジー情報だけを有する部分群を選択するひとつの手法について説明する。大雑把に言うと、概念は次の通りである。ネットワークの（一部分を）分割するために、指定されたノードＤは、図８におけるノード１１０．０及び、ノード１１０．１のような、ネットワークにおける２つの「群のヘッド」を選択する。（３つ以上の群のヘッドを選択することもできる。）これらの群のヘッドは、ランダムに選択することができる。あるいは、指定されたノードが、何らかのトポロジー情報を有する場合は、そのノードは、その情報を用いて、トポロジー的に離れている、できれば互いに相異なるネットワークに属するような、２つの群のヘッドを選択しようと試みることができる。指定されたノードＤは、２つの群のヘッドを選択した後で、その２つの群のヘッドに異なったメッセージを送信するように命令する。例えば、指定されたノードは、第１の群のヘッドに‘０’を送信するように命令し、第２の群のヘッドには、‘１’を送信するように命令する。そして、各群のヘッド（例えば、１１０．０と１１０．１）は、その特定のメッセージでネットワークを「氾濫させる」。これが起こった場合、ネットワーク上の他のノードは、まず、‘０’を受け取るか、又は、‘１’を受け取る。‘０’を先に受け取ったノード（例えば、ノード１１０．００及び、ノード１１０．０１）は、自身が０−群の要素であることを指定されたノードＤ（又は、群のヘッド１１０．０）に折り返し報告する。1−群に属する要素も同様に報告する。指定されたノードＤ（又は、それぞれの群のヘッド）は、この情報を受信し、アキュムレータを、一方の半分を０−群、他方の半分を1−群とする２つのアキュムレータにディアキュムレートする。指定されたノードが、このディアキュムレーションを（図８に図示した手順のように）行った場合、対応する群のヘッド（１１０．０及び、１１０．１）に適当なアキュムレータを伝える。そして、各群のヘッドは、対応するサブネットワークの指定されたノードとなり、上述したプロセス全体が、サブネットワークに対して繰り返される。ここで、一実施形態のより詳細を説明する。
【０１３８】
初めは、全ネットワークをカバーするユーザの単一群ＰＰだけが存在する。各再帰ステップは、図９に描写したように４つのフェーズにおいて実施される。第１の再帰ステップは、好ましくは、ネットワークの中心に位置するノードによって開始される。このノードを現在指定されているノードＤと呼ぶ。ノードＤは、以下の４フェーズの再帰を実行する。
【０１３９】
検索群ヘッド（状態９１０）
ノードＤは、群ヘッドＣＨ０及びＧＨ１としての群の中からランダムに２つのノードを選択する。（説明のために、ノードＧＨ０は、図８又は図１０のノード１１０．０、ノードＧＨ１は、ノード１１０．１と仮定する。）ノードＤは、その群のＩＤ、ＧＨ０とＧＨ１のアドレス、及びＤのアドレスを含むパス変数とともに一斉通信のメッセージｍｓｅａｒｃｈＧＨを送出する。同じ群内の全ての受信用パスは、パスのコピーを入手し、それらが、ＧＨ０かＧＨ１のどちらか一方であるかどうかを確認する。ＧＨ０又はＧＨ１でなかった場合、メッセージにおけるパス変数に自身のアドレスを追加し、それを一度転送（一斉通信）する。パス変数は、各ノードにＤまでのパスを提供する。図１０は、ノードＤ、ノード１１０．０１、ノード１１０．１０、ノード１１０．１１が送信したメッセージｍｓｅａｒｃｈＧＨを示す。
【０１４０】
構成群（状態９２０）
ｍｓｅａｒｃｈＧＨの受信者がＧＨ０やＧＨ１である場合、部分群のアドレスを含むメッセージｍｂｕｉｌｄＧを一斉通信することにより部分群を構成し始める。同じ群に属するｍｂｕｉｌｄＧの受信者が群ヘッドからのメッセージをまだ受信しておらず、そのため、部分群にまだ加わっていない場合、受信者は、ｍｂｕｉｌｄＧに通知された部分群に加入し、そのメッセージを一度転送する。図１０は、ノード１１０．０１が、ＧＨ０からメッセージｍｂｕｉｌｄＧをまず受信し、ノード１１０．１０及びノード１１０．１１が、ＧＨ１からメッセージｍｂｕｉｌｄＧをまず受信すると仮定して、ノードＧＨ０、ノードＧＨ１、ノード１１０．０１、ノード１１０．１０、ノード１１０．１１によって一斉通信されるメッセージｍｂｕｉｌｄＧを示したものである。
【０１４１】
報告群（状態９３０）
定められた時間の後、両方の部分群の全ての要素は、メンバーシップのステータスをＤに報告し始める。そのため、それらには、メッセージｍｒｅｐｏｒｔＧにおける部分集合ＩＤ０又は、部分集合ＩＤ１とともに、そのアドレスが含まれ、それを、フェーズ１で得られたパスを通してＤに送信する。この報告をより効率的にするために、Ｄからより離れているノードが、まず報告し始める。ｍｒｅｐｏｒｔＧのパス上のノードは、その部分集合のメンバーシップ情報をメッセージに追加し、それを、Ｄまでのパスに従って転送する。メッセージｍｒｅｐｏｒｔＧを転送したノード、それ自体は、報告を開始することはしない。
【０１４２】
送信アキュムレータ（状態９４０）
Ｄが全ての報告を受け取った後、Ｄは、受け取った報告に含まれるＧＨ０までのパスｐ０及び、ＧＨ１までのパスｐ１を調べ、その群に対するアキュムレータｖｊをべき乗してそれぞれの部分集合に対するアキュムレータｖｊ（０）及び、アキュムレータｖｊ（１）を求める。そして、それぞれのメッセージｍｔｒａｎｓｍｉｔｖ０におけるアキュムレータをｐ０を通してＧＨ０に対して送信し、メッセージｍｔｒａｎｓｍｉｔｖ０をｐ１を通してＧＨ１にそれぞれ送信する。アキュムレータｖｊ（０）及び、アキュムレータｖｊ（１）の他に、メッセージには、対応する部分群の要素の一覧が含まれる。ｍｔｒａｎｓｍｉｔｖ０又は、ｍｔｒａｎｓｍｉｔｖ１をそれぞれ受信した後、ＧＨ０及びＧＨ１は、その部分集合の指定されたノードＤに成り、次の再帰ステップであるフェーズ９１０に入る。再帰は、部分集合のアキュムレータがパーソナルアキュムレータである場合、終了する。
【０１４３】
基数｜ＵＵ｜＝２Ｒ＝ｔを有する全てのユーザＵＵの集合及び、各群ＰＰを、同一サイズ｜ＰＰ｜／２の２つの群に均等に分配することを考えると、再帰は、Ｒ個のステップの後に、サイズが１のｔ個の部分群の総数を以って終了する。ここで、各ステップにおいて、分割が略等しく半分に成るものと仮定して、スキームの計算処理量や通信計算量のいくつかの態様について言及する。
【０１４４】
検索群ヘッド
サイズｔ’のサブネットワーク内において、このステップは、それぞれのサイズがｌｏｇｔであるＯ（ｔ’）のメッセージを必要とする（なぜならば、ｔ個のエレメントの群の単一要素を特定化するために、平均してｌｏｇｔビットを必要とするためである）。各メッセージには、平均長
【数５０】
2008524930.tif 000052
【０１４５】
を有するパスが含まれるので、このサブネットワークの通信は、
【数５１】
2008524930.tif 000053
【０１４６】
である。常に同じサイズに分割されると仮定する場合、再帰手順全体の全通信量も、
【数５２】
2008524930.tif 000054
【０１４７】
である。
【０１４８】
構成群
このステップには、通信計算量Ｏ（ｔ）に対して、それぞれが一定のサイズである合計ｔ個のメッセージを含む。
【０１４９】
報告群
ノードの群メンバーシップ情報は、 
【数５３】
2008524930.tif 000055
【０１５０】
ホップ上を送信される。ここで、Ｃ３は、ネットワーク密度に基づき、かつ、開始された報告の数を反映する定数である。この結果、通信は、
【数５４】
2008524930.tif 000056
【０１５１】
となる。
【０１５２】
送信アキュムレータ
ｔ個のノードの群メンバーシップ情報とともにアキュムレータは、
【数５５】
2008524930.tif 000057
【０１５３】
ホップ上を送信される。ここで、Ｃ４は、ネットワーク密度に基づいた定数である。この結果、通信は、
【数５６】
2008524930.tif 000058
【０１５４】
となり、計算は、Ｏ（ｔＲｌｏｇｔ）＝Ｏ（ｔｌｏｇ２ｔ）となる。
【０１５５】
概して、通信は、
【数５７】
2008524930.tif 000059
【０１５６】
であり、計算は、Ｏ（ｔｌｏｇ２ｔ）である。
【０１５７】
認証局自体などのような計算能力やエネルギーに関して制限の少ないネットワークのエンティティＥが存在すると仮定する場合、別の興味深い機会が生じる。あるトポロジーの知識を取得することによって、このエンティティは、アキュムレータを一定サイズの群に対するアキュムレータに予めディアキュムレートすると考えられる。詳細には、そのようなスキームは、次のように機能する。全てのユーザに対する現在のアキュムレータを保持し、Ｅに対する接続性を持つノードＣは、図９の分散型クラスタリングアルゴリズムを開始する。第２のステップにおいて、Ｃは、クラスタリング情報をＥに提供し、Ｅに全てのクラスタに対して予めディアキュムレートさせる。そして、Ｃは、アキュムレータをクラスタに分散する。適当なクラスタリングアルゴリズムは、
【数５８】
2008524930.tif 000060
【０１５８】
の通信計算量を持つが、おそらく、上述した手法よりも小さい一定の係数を持つ。
【０１５９】
簡潔に、接続されたネットワークを、２つの接続されたサブネットワークに分割する分散型アプローチについて言及する。ここで、いずれのサブネットワークも他方のサイズの２倍より小さい。上記のように、指定されたノードを有するサブネットワークから始める。サブネットワークは接続され、そのトポロジーは、（期間によって大きく異なるが）アキュムレータを配布する間は基本的に一定であると仮定する。Ｏ（ｔｌｏｇｔ）の通信及び、Ｏ（ｔｌｏｇｔ）の計算を実現するための好適なアルゴリズムにおける第１のステップは、分散型の形式において、サブネットワークのノードが、それ自体の一覧を構成することである。これは、以下のようにして達成可能である。指定されたノードは、メッセージを一斉通信することによって手順を開始する。そのメッセージを受信するノードは、受信通知メッセージを指定されたノードに送り返し、そこからメッセージを受信したとしてノードを記録する。指定されたノードは、そのメッセージを受信したノードとして受信通知するノードをログする。このプロセスは、ネットワーク全体を通して再帰する。特に、指定されたノードからのメッセージを受信したノードは、メッセージを一斉通信する。メッセージをまだ送信していない、又は、受信していないノードは、メッセージを受信したノードのアイデンティティを記録し、受信通知メッセージを送り返す。その後、送信用ノードは受信容認者を記録する。ノードがメッセージを一回以上受信する場合、ノードが記録し返信するのは、メッセージを最初に送ってきたノードに対してのみである。このように、サブネットワークは接続され、サブネットワーク上の（指定されたノード以外の）全てのノードは、メッセージを受信した固有のノード及び、メッセージをそこから直接受信したノードの一覧を有する。容認者の空でない一覧を有する各ノードは、容認者たちの任意の一覧を選択する。実質的に、この手順から、ネットワークからのツリー（ループのないグラフ）及び、ツリーの縦型前順走査によって所与の全てのツリーノードの一覧を形成した。サブネットワークが、ｔ’個のノードを有する場合、この手順は、Ｏ（ｔ’）の通信と計算によって達成可能である。
【０１６０】
アルゴリズムの次の段階では、サブネットワークをほぼ２等分するために一覧を使う。これを行うためには、さまざまな方法が存在する。ひとつは、容認者を持たないノードで始まる各ノードは、それ自体も含んだサブツリーにおけるノード数を（一覧に応じて後から）遡って送信することができる。このように、各ノードは、そのサブツリーにおけるノードの数を計算する。サブツリーのノードの少なくとも半分のノードを持つが、どの子ノードも少なくとも半分を持たないようなちょうどひとつのノードがなくてはならない。このノードは、サブネットワークの中間点に指定されている。ここで、この中間点をツリーのルートとして見ると、このノードは、第１の群の子のうちのひとつから発出するサブツリーにおけるノード数が、第２の群の子のうちのひとつから発出するサブツリーにおけるノード数とほぼ等しくなるように、子を２つの群に分割している。（これは、２つの数の間の比率が、多くても２であるように、いつでも達成可能である。）よって、中間点を除く全てのネットワークノードは、２つの群のうちの一方の要素になる。中間点は、両方の群の要素であると見なされている。各サブツリーにどのくらいのノードが存在するかを計算するステップでは、（ある特定のサブツリーにどれくらいのノードが存在するかを表す１とｔ’の間の数である）各送信サイズがｌｏｇｔ’バイトであるｔ回の送信が存在するので、Ｏ（ｔ’ｌｏｇｔ’）の通信量が必要とされる。中間点のノードをルートノードと見なすと、第１の群におけるノードで始まる、メッセージのイニシエータとしての中間点ノードによってノードの新規一覧を構成することができる。（この新規一覧は、上述したように計算することができるし、以前の一覧から非直接的に導出することも実際に可能である。どちらの方法も、概してｔｌｏｇ２ｔであるプロトコルの漸近的通信計算量を増加させるものではない。）
有効性証明のアキュムレータに基づく暗号化
パーソナルアキュムレータｖｊ（ｐｉ）及び／又は、ウィットネス値ｓｉｊ（等式（１７）、（２０）、（２１）、（２６）を参照）は、ユーザが他の有効化システム下の有効性証明を復号するために用いることができる対称鍵を入手するために用いることができる。ここで、図２、図４乃至図７のシステムを組む合わせることにより得られた有効化システムに対する一例を説明するが、これは、制限するものではない。
【０１６１】
初期証明書
ユーザｕｉがシステムに加わると、ＣＡは、
１．図２のように、有効シードｘ及び、失効シードＮ０を生成し、
２．全ての期間ｊに対する全てのトークンｃｊを生成（図２及び等式（１）を参照）し、
３．図２のような証明書１４０を生成し、その証明書をユーザｕｉに送信し、
４．図４のステップを実行、すなわち、値ｐｉ、ｍｉ、
【数５９】
2008524930.tif 000061
【０１６２】
を生成し、
【数６０】
2008524930.tif 000062
【０１６３】
を（ユーザｕｉ及び／又は、ディレクトリ２１０であってもよい）有効性証明者に送信し、値ｐｉ、ｍｉも、証明者に送信することができ、
５．全てのウィットネス値ｓｉ，ｊをユーザｕｉに対して（全ての期間ｊにおいて）生成し、また、それぞれがｓｉ，ｊ又は、ｓｉ，ｊの関数である暗号鍵Ｋｉ，ｊも生成し、
６．（この手順のステップ２で生成した）各トークンｃｊを、（対称暗号スキームなどの）暗号化スキーム下において暗号鍵Ｋｉ，ｊで暗号化し、ここで、暗号化されたｃｊの値をＥｉ，ｊとして示し、
７．（全てのｊに対する）全ての値Ｅｉ，ｊを証明者（すなわち、ディレクトリ２１０及び／又は、証明書の所有者ｕｉ）に送信する。
【０１６４】
ＣＡによる有効性再検証
各期間ｊの開始時、又は、その少し前に、ＣＡは、
１．図５の手順を実行、すなわち、アキュムレータ値ｖｊ及び有効なｐ個の数の一覧を計算し、証明者に一斉通信し、
２．ユーザｕｉの証明書が無効である場合、ＣＡは、失効シードＮ０を証明書に対応する証明者（例えば、ユーザｕｉ、及び／又は、ディレクトリ２１０）に送信する。
【０１６５】
証明者による証明の導出
ユーザｕｉの証明書が、（ステップ１における有効性再検証の手順における数ｐｉの送信によって示されるように）有効である場合、証明者は、
１．図６の手順を実行し、ウィットネス値ｓｉｊを導出し、
２．復号鍵Ｋｉｊをｓｉｊから求め
３．Ｅｉｊを復号してｃｊを回復する。
【０１６６】
認証（有効性証明）
図２に示すとおり。多くのバリエーションが可能である。例えば、復号鍵は、暗号鍵とは異なったｓｉ，ｊの何らかの関数であってもよい。
【０１６７】
無効な証明書のアキュムレーション
以上、アキュムレータが有効な証明書を累算する手法について説明した。代替の手法として、失効した証明書を累算するものがある。有効な証明書の所有者（又は、有効性証明者）は、ダイナミックアキュムレータの「動的」な特徴を用いて、有効なノードに対する新規のアキュムレータを計算し、新規アキュムレータに関するパーソナルアキュムレータを計算する。
【０１６８】
これまでのとおり、説明のために各ユーザが対応するコンピュータシステム１１０を操作し、多くてもひとつの証明書１４０を所有するものと仮定する。ユーザは複数の証明書を所有、及び／又は、複数のシステム１１０を操作してもよいので、これは制限するものではない。また、このスキームは、リソースアクセス及び、他の種類の認証制御にも適用可能である。混乱が生じない限り、システム１１０とシステムのオペレータの両方を示す「ユーザ」という用語を用いる。以下に説明するように、各ユーザｕｉは、図４乃至図７のスキームと同じプロパティを有する正の整数ｐｉを割り当てられる（例えば、ｐｉは、ＣＡの公開合成数ｎに対して、かつｐｉ間で互いに素である）。シンボルｎ，ＰＰ，ｐｉは、図４乃至図７のスキームと同様である。特に、ＰＰは、ｐｉ個の数の集合である。
【０１６９】
各期間ｊに対して、シンボルＱＱｊが、失効されたｐｉ個の数の集合（すなわち、期間ｊにおいて無効とされたとして宣言される証明書に対応するｐｉ個の数の集合）を示す。Ｑｊは、ＱＱｊにおける数の積を示す。
【数６１】
2008524930.tif 000063
【０１７０】
シンボルａは、法ｎで互い素である整数であるアキュムレータシードを示す。Ｑｊにおける値のアキュムレータは、
【数６２】
2008524930.tif 000064
【０１７１】
である。
【０１７２】
ＲＲｊ＝ＱＱｊ−ＱＱｊ―１、すなわち、ＲＲｊは期間ｊ−１においてではなく、期間ｊにおいて無効と宣言された証明書に対応するｐ個の数の集合であり、これらの証明書は、期間ｊ−１において有効であると宣言されたか、又は、まだ認証システムに加わってなかったものとする。ＲｊがＲＲｊにおける数の積を示すものとする。
【数６３】
2008524930.tif 000065
【０１７３】
各証明書が「無効の取り消し」をすることはできない（すなわち、一旦無効とされると有効とすることができない）場合、
【数６４】
2008524930.tif 000066
【０１７４】
であることは、（３７）から容易に理解できる。
【０１７５】
ＣＡの設定
ＣＡは、法ｎ及び、アキュムレータシードａを生成する。ＣＡは、初期期間ｊに対する初期アキュムレータ値ｖｊ＝ａを設定する。
【０１７６】
初期証明書（図１１）
ユーザｕｉが、期間ｊ０においてシステムに参加して、次の期間ｊ０＋１を開始させることで検証したいと考えているものと仮定する。ステップ１１１０において、ＣＡ１２０は、図４のステップ４１０のようにｐｉ、ｍｉを生成する。これらの数字は、ユーザの証明書１４０（図３）の一部分に成ることができる。ステップ１１２０において、ＣＡは、以下の秘密の数を計算する。
【数６５】
2008524930.tif 000067
【数６６】
2008524930.tif 000068
【０１７７】
ここで、
【数６７】
2008524930.tif 000069
【０１７８】
は、期間ｊ０に対するアキュムレータ値である（ＱＱｊ０が空のときｖｊ０＝ａである）。ステップ１１３０において、ＣＡは、ユーザｕｉに対して、値ｔｉと
【数６８】
2008524930.tif 000070
【０１７９】
を暗号化した形式で送信する。後に説明するように、ユーザは、値
【数６９】
2008524930.tif 000071
【０１８０】
を、証明書が有効である各期間ｊ＞ｊ０に対して導出することができる。
【０１８１】
証明書有効性再検証（図１２）
期間ｊにおいて、ｖｊ−１∈Ｚ／ｎＺが、期間ｊ−１に対するアキュムレータ値であるとする。期間ｊにおける有効性検証に対し、ＣＡは、
１．（例えば、等式（３７）又は（３９）を用いて）ｖｊを計算し、
２．値ｖｊを、（おそらく集合ＲＲｊによって表される）新規に無効とされた証明書の一覧とともに、ユーザに対して送信し、所望であれば、ＣＡは、ペア（ｖｊ，ｊ）に署名し、その署名をユーザに送信することもできる。
【０１８２】
ウィットネス導出（図１３）
ユーザｕｉが、期間ｊに対して有効である場合、ユーザは、値
【数７０】
2008524930.tif 000072
【０１８３】
を有する。（４１）及び（４２）を参照のこと。ステップ１３１０において、ユーザは、
【数７１】
2008524930.tif 000073
【０１８４】
を次のように計算する。
【０１８５】
１．ユーザは、
ａｐｉ＋ｂＲｊ＝１    （４３）
となるように拡張ユークリッドアルゴリズムを適用し、整数ａと整数ｂを計算する（これが可能なのは、
【数７２】
2008524930.tif 000074
【０１８６】
であるからであり、ｐｉとＲｊは互いに素である）。
【０１８７】
２．ユーザは、ｓｉ，ｊを値
【数７３】
2008524930.tif 000075
【０１８８】
に設定する。
【０１８９】
この値は、実際には、ｎを法とするｖｊのｐｉ乗根である。なぜならば、（等式（３９）に留意）
【数７４】
2008524930.tif 000076
【０１９０】
であるからである。ステップ１３２０において、ユーザは、ウィットネス
【数７５】
2008524930.tif 000077
【０１９１】
を計算する。
【０１９２】
ユーザ認証（図１４）
ユーザｕｉは、ｔｉｓｉ，ｊ（ｍｏｄ ｎ）を、（必要であれば）（ｕｉ、ｐｉ、ｊ０、ｗｉ）に対する値とともにベリファイヤに対して提供する。また、ユーザは、ベリファイヤに、アキュムレータ値ｖｊ及び、ＣＡの（ｖｊ，ｊ）における署名を提供する。ステップ１４１０において、ベリファイヤは、ＣＡの署名を確認し、
【数７６】
2008524930.tif 000078
【０１９３】
であることを確認する。
【０１９４】
代替ユーザ認証
秘密鍵としてｗｉ，ｊを用いる等式（２３）及び等式（２４）に関連して上述したように、アイデンティティに基づいたＧＱ署名スキームを用いて認証を行うことができる。ＣＡは、ＧＱのＰＫＧ（秘密鍵ジェネレータ）の関数を実行し、ＧＱのパラメータは、次の、Ｂ＝ｗｉ，ｊ，ｖ＝ｐｉ及び、
【数７７】
2008524930.tif 000079
【０１９５】
のように設定される。認証は、次のように進む。
【０１９６】
ベリファイヤは、ユーザに対してランダムなメッセージｍを送信する。
【０１９７】
ユーザは、ランダムな数ｒを生成し、
【数７８】
2008524930.tif 000080
【０１９８】
を計算する。ここで、Ｈは、予め定義された公開関数である。ユーザは、値ｍ、ｍｉ、
【数７９】
2008524930.tif 000081
【０１９９】
、及びＤをベリファイヤに送信する。
【０２００】
ベリファイヤは、
【数８０】
2008524930.tif 000082
【０２０１】
を計算し、次の等式が成り立つことを確認する。
【数８１】
2008524930.tif 000083
【数８２】
2008524930.tif 000084
【０２０２】
このスキームは、ベリファイヤが、証明書１４０を必要としないので、全帯域幅を減らすことが可能である。ＧＱ署名スキームを安全なものとするために、ｐｉ＞２１６０であることが望ましいことに留意。
【０２０３】
アキュムレータｖｊの使用によって、ユーザは、ＣＡの助けなしにユーザ自体を無効とすることができる。期間ｊにおいてユーザ自体を無効とするために、ユーザｕｉは、単に
【数８３】
2008524930.tif 000085
【０２０４】
を一斉通信し、その後、他の全てのユーザｕｋは、アキュムレータを
【数８４】
2008524930.tif 000086
【０２０５】
と更新することができ、かつ、（４３）乃至（４５）のようにパーソナルなｓｋ，ｊ及びｗｋ，ｊの値を再計算することができる。ｐｉによって前のＲｊ値を乗法することでＲｊを再計算することができることに留意すること。
【０２０６】
いくつかの実施形態において、ＣＡは、全てのユーザに同じ情報を送信するので、このスキームによって、図１２の段階におけるＣＡに対する効率的な配布（一斉通信）が可能となる。この情報は、Ｏ（ｔ）の通信だけを必要とする。一方で、各通信のサイズは、ＲＲｊのサイズに比例している。ＣＡのクライアントには、対象としている特別なｔ−要素ネットワーク上に存在しない多くのユーザが含まれていてもよい。ＣＡのクライアントの「スーパーネットワーク」が、ｔに比例して非常に大きい場合、これは、あまりよい解決策ではないと考えられる。例えＣＡがｔ−要素ネットワークだけを管理したとしても、所与の期間におけるネットワーク内の失効数が、ユーザ総数の一定の割合と成る傾向にあるので、各通信のＣＡのサイズは、厳密に言って、まだｔに比例している。この意味において、このスキームにおける証明書配布の通信計算量は、デルタＣＲＬスキームの通信計算量に近似している。デルタＣＲＬスキームにおいて、ＣＡは、所与の期間において無効とされたユーザの一覧を、その一覧上の署名とともに全てのユーザに対して送信したことを思い出して欲しい。一方で、パーソナルアキュムレータのサイズは、期間の数とは無関係であるので、このスキームは、デルタＣＲＬスキームよりも認証のためにより合理的な通信計算量を持っている。なぜならば、デルタＣＲＬスキームにおいては、ベリファイヤは、全ての期間に対するデルタＣＲＬを個別に確認し、所与のユーザが、これらの期間のいずれかの間に無効とされていないことを確認しなければならないためである。
【０２０７】
本発明は、上述した実施形態に制限されるものではない。本発明は、安全、又は、ダイナミックアキュムレータに限定されるものではない。アキュムレータは、いくつかのエレメントを累算するいかなるデータであってもよい。さらに、本発明は、上述したアキュムレータに限定されるものではない。例えば、等式（１７）におけるアキュムレータシードｈ（ｊ）／ｈ（ｊ−１）は、期間ｊと無関係な値と入れ換えることができ、アキュムレータ（３７）におけるアキュムレータシードａは、ｊの関数と入れ換えることができる。アキュムレータの方法は、集合、又は、あるプロパティの所有におけるメンバーシップの証明（認証）に用いることができる。その例としては、有効な権利の認証や、ある組織の要素である人々の認証が含まれる。
【０２０８】
いくつかの実施形態において、ＣＡ１２０、ディレクトリ２１０、システム１１０は、１つ以上のネットワーク上で互いに通信し合うコンピュータシステムである。これらのシステムの各々がそれ自体ネットワーク上で通信を行う構成要素を有するコンピュータシステムであってよい。各コンピュータシステムには、コンピュータの命令を実行し、上述したようにコンピュータデータを操作するひとつ以上のコンピュータプロセスを含む。「データ」という用語には、「コンピュータデータ」が含まれ、コンピュータ命令及び、その命令によって操作されるコンピュータデータの両方をカバーしている。命令及びデータは、コンピュータストレージ、すなわち、コンピュータで読み取り可能な媒体（例えば、磁気、又は、光学ディスク、半導体メモリ、及び他のタイプの公知の、又は、発明される媒体）などのデータキャリアに記憶することができる。データキャリアには、空中を通して、もしくは、ケーブル、又は、他の手段によってネットワーク上を伝送される電磁気のキャリア波を含んでもよい。命令及びデータは、コンピュータに上述したように適切なアルゴリズムを実行させるように動作可能である。
【０２０９】
本発明は、いかなる特定のハッシュ関数、又は、（計算は容易だが一方向であり、衝突耐性を持つ）暗号化関数に限定されるものではない。いくつかの実施形態において、関数ｆ、又は、Ｈが、同じイメージに異なるｘ及びｙを見つけることが困難であるという意味においてではなく、ｘ及びｙが関数のドメインから一様に引き出された場合において、両者が同じイメージを持つであろう確率が低いことが望ましい。すなわち、
【数８５】
2008524930.tif 000087
【０２１０】
である。ここで、αは、小さい定数（例えば、１／１０、又は、１／１００、又は、２−２５、又は、２−５０、又は、２−８０、又は、２−１６０、又は、その他の値）である。有効性証明に用いた技術のいくつか、又は、全ては、無効性証明にも用いることができ、その逆も可能である。ＣＡ、ディレクトリ及び、システム１１０は、ひとつのネットワーク、又は、複数のネットワークを介して組み込まれたソフトウェアでプログラム可能なコンピュータシステム、又は、配線で接続されたコンピュータシステムを含んでもよい。各関数ｆ、又は、Ｈは、コンピュータシステムが実行する評価方法を表わす。本発明は、フローチャートに示したステップの順番に限定されるものではない。なぜならば、ステップの順番は、交換可能なこともあり、異なるステップをさらに平行して実行してもよい。他の実施形態及び変形例も、添付した請求の範囲によって定義されるように発明の範囲内に含まれる。
【０２１１】
以下の参考文献の全ては、参照によりここに引用したものとする。
【０２１２】
［１］アイエロ（Ｗ．Ａｉｅｌｌｏ）、ロダ（Ｓ．Ｌｏｄｈａ）、及びオストロフスキ（Ｒ．  Ｏｓｔｒｏｖｓｋｙ）著、「デジタルアイデンティティの高速失効（Ｆａｓｔ  ｄｉｇｉｔａｌ  ｉｄｅｎｔｉｔｙ  ｒｅｖｏｃａｔｉｏｎ）」、予稿集、クリプト９８(ＣＲＹＰＴＯ９８)、１９９８年
［２］アテニーズ（Ｇ．  Ａｔｅｎｉｅｓｅ）、カメニッシュ（Ｊ．Ｃａｍｅｎｉｓｃｈ）、ジョイ（Ｍ．Ｊｏｙｅ）、及びツディック（Ｇ．Ｔｓｕｄｉｋ）著、「実用的で安全と思われる衝突耐性を持つグループ署名スキーム(Ａ  Ｐｒａｃｔｉｃａｌ  ａｎｄ  Ｐｒｏｖａｂｌｙ  Ｓｅｃｕｒｅ  Ｃｏａｌｉｔｉｏｎ−Ｒｅｓｉｓｔａｎｔ  Ｇｒｏｕｐ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅ)」、予稿集、クリプト２０００(ＣＲＹＰＴＯ２０００)、２０００年
［３］バラレ（Ｍ．Ｂｅｌｌａｒｅ）及びロガウェイ（Ｐ．Ｒｏｇａｗａｙ）著、「ランダムオラクルは実用的である:効率的なプロトコルのデザイン用パラダイム(Ｒａｎｄｏｍ  ｏｒａｃｌｅｓ  ａｒｅ  ｐｒａｃｔｉｃａｌ：  Ａ  ｐａｒａｄｉｇｍ  ｆｏｒ  ｄｅｓｉｇｎｉｎｇ  ｅｆｆｉｃｉｅｎｔ  ｐｒｏｔｏｃｏｌｓ”、予稿集、第1回コンピュータ・通信セキュリティ年次大会（Ｆｉｒｓｔ  Ａｎｎｕａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｅｃｕｒｉｔｙ）、ＡＣＭ、１９９３年
［４］ボネ（Ｄ．Ｂｏｎｅｈ）、リン（Ｂ．Ｌｙｎｎ）及びシャッハム（Ｈ．Ｓｈａｃｈａｍ）、「ワイルペアリングからの短い署名(Ｓｈｏｒｔ  ｓｉｇｎａｔｕｒｅｓ  ｆｒｏｍ  ｔｈｅ  Ｗｅｉｌ  ｐａｉｒｉｎｇ”、予稿集、アジアクリプト’０１(Ａｓｉａｃｒｙｐｔ’０１)、２００１年
［５］エルワイリ（Ｆ．Ｅｌｗａｉｌｌｙ）及びラムザン（Ｚ．Ｒａｍｚａｎ）著、「クワジモード:より効率的なハッシュツリーに基づく証明書失効(ＱｕａｓｉＭｏｄｏ：  Ｍｏｒｅ  Ｅｆｆｉｃｉｅｎｔ  Ｈａｓｈ  Ｔｒｅｅ−Ｂａｓｅｄ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｒｅｖｏｃａｔｉｏｎ)」、原稿、２００３年
［６］ガスコ（Ｉ．Ｇａｓｓｋｏ）、ゲメル（Ｐ．Ｓ．Ｇｅｍｍｅｌｌ）及びマッケンンジー（Ｐ．ＭａｃＫｅｎｚｉｅ）著、「効率的新規認証(Ｅｆｆｉｃｉｅｎｔ  ａｎｄ  ｆｒｅｓｈ  ｃｅｒｔｉｆｉｃａｔｉｏｎ)」、予稿集、ピー・ケイ・シー２０００(ＰＫＣ２０００)、２０００年
［７］ゴールドワッサー（Ｓ．Ｇｏｌｄｗａｓｓｅｒ）、ミカリ（Ｓ．Ｍｉｃａｌｉ）、リベスト（Ｒ．Ｌ．Ｒｉｖｅｓｔ）著、「適応型選択メッセージ攻撃に対して安全なデジタル署名スキーム(Ａ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅ  Ｓｅｃｕｒｅ  Ａｇａｉｎｓｔ  Ａｄａｐｔｉｖｅ  Ｃｈｏｓｅｎ−Ｍｅｓｓａｇｅ  Ａｔｔａｃｋｓ)」、シャム(ＳＩＡＭ)、コンピューティングに関するジャーナル(Ｊｏｕｒｎａｌ  ｏｎ  Ｃｏｍｐｕｔｉｎｇ)、１７（２）巻、２８１−３０８ページ、１９８８年
［８］フ（Ｙ−Ｃ．Ｈｕ）、ペリング（Ａ．Ｐｅｒｒｉｇ）及びジョンソン（Ｄ．Ｊｏｈｎｓｏｎ）著、「ルーティングプロトコル用の効率的な安全性メカニズム(Ｅｆｆｉｃｉｅｎｔ  ｓｅｃｕｒｉｔｙ  ｍｅｃｈａｎｉｓｍｓ  ｆｏｒ  ｒｏｕｔｉｎｇ  ｐｒｏｔｏｃｏｌｓ)」、予稿集、ネットワーク及び分散型システムの安全性に関する第１０回シンポジウム(ｔｈｅ  １０ｔｈ  Ａｎｎｕａｌ  Ｎｅｔｗｏｒｋ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍ  Ｓｅｃｕｒｉｔｙ  Ｓｙｍｐｏｓｉｕｍ  （ＮＤＳＳ）)、２００３年
［９］ヤコブソン（Ｍ．Ｊａｋｏｂｓｓｏｎ）、ヒューボウ（Ｊ−Ｐ．Ｈｕｂａｕｘ）及びバッタイアン（Ｌ．Ｂｕｔｔｙａｎ）著、「マルチ・ホップセルラーネットワークにおいてコラボレーションを促すマイクロペイメントスキーム(Ａ  ｍｉｃｒｏｐａｙｍｅｎｔ  ｓｃｈｅｍｅ  ｅｎｃｏｕｒａｇｉｎｇ  ｃｏｌｌａｂｏｒａｔｉｏｎ  ｉｎ  ｍｕｌｔｉ−ｈｏｐ  ｃｅｌｌｕｌａｒ  ｎｅｔｗｏｒｋｓ)」、予稿集、金融暗号技術に関する第７回国際会議(ｔｈｅ  ７ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｆｉｎａｎｃｉａｌ  Ｃｒｙｐｔｏｇｒａｐｈｙ)、２００３年
［１０］ヤコブソン（Ｍ．Ｊａｋｏｂｓｓｏｎ）、レイトン（Ｔ．Ｌｅｉｇｈｔｏｎ）、ミカリ（Ｓ．Ｍｉｃａｌｉ）及びジドロ（Ｍ．Ｓｚｙｄｌｏ）著、「フラクタルメルケルツリーリプリゼーション及びトラバーサル(Ｆｒａｃｔａｌ  ｍｅｒｋｌｅ  ｔｒｅｅ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎ  ａｎｄ  ｔｒａｖｅｒｓａｌ)」、予稿集、暗号使用者のトラックＲＳＡ会議(ｔｈｅ  Ｃｒｙｐｔｏｇｒａｐｈｅｒ’ｓ  Ｔｒａｃｋ  ＲＳＡ  Ｃｏｎｆｅｒｅｎｃｅ)、２００３年
［１１］ジャレッキ（Ｓ．Ｊａｒｅｃｋｉ）及びオドリスコ（Ａ．Ｏｄｌｙｚｋｏ）著、「確率的ポーリングに基づく効率的なマイクロペイメントシステム(Ａｎ  ｅｆｆｉｃｉｅｎｔ  ｍｉｃｒｏｐａｙｍｅｎｔ  ｓｙｓｔｅｍ  ｂａｓｅｄ  ｏｎ  ｐｒｏｂａｂｉｌｉｓｔｉｃ  ｐｏｌｌｉｎｇ)」、予稿集、金融暗号技術に関する第１回国際会議(ｔｈｅ  １ｓｔ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｆｉｎａｎｃｉａｌ  Ｃｒｙｐｔｏｇｒａｐｈｙ)、１９９７年
［１２］ロバート・ジョンソン（Ｒｏｂｅｒｔ  Ｊｏｈｎｓｏｎ）及びデイビッド・モルナ（Ｄａｖｉｄ  Ｍｏｌｎａｒ）、ダウン・シャオドン・ソン（Ｄａｗｎ  Ｘｉａｏｄｏｎｇ  Ｓｏｎｇ）及びデイビッド・ワグナー（Ｄａｖｉｄ  Ｗａｇｎｅｒ）著、「準同形署名スキーム(Ｈｏｍｏｍｏｒｐｈｉｃ  ｓｉｇｎａｔｕｒｅ  ｓｃｈｅｍｅｓ)」、シー・ティーＲＳＡ(ＣＴ−ＲＳＡ)、２４４−２６２ページ、２００２年
［１３］ジャルタ（Ｃ．Ｊｕｔｌａ）及びユン（Ｍ．Ｙｕｎｇ）著、「ペイツリー：フレキシブルなマイクロペイメントのための、ならし署名(ＰａｙＴｒｅｅ：  Ａｍｏｒｔｉｚｅｄ  ｓｉｇｎａｔｕｒｅｓ  ｆｏｒ  ｆｌｅｘｉｂｌｅ  ｍｉｃｒｏｐａｙｍｅｎｔｓ)」、予稿集、電子商取引に関する第２回ＵＳＥＮＩＸワークショップ(ｔｈｅ  ｓｅｃｏｎｄ  ＵＳＥＮＩＸ  ｗｏｒｋｓｈｏｐ  ｏｎ  ｅｌｅｃｔｒｏｎｉｃ  ｃｏｍｍｅｒｃｅ)、１９９６年
［１４］キム（Ｓ．Ｋｉｍ）及びオウ（Ｈ．Ｏｈ）著、「モバイルコンピューティング環境のためのアトミックマイクロペイメントシステム(Ａｎ  ａｔｏｍｉｃ  ｍｉｃｒｏｐａｙｍｅｎｔ  ｓｙｓｔｅｍ  ｆｏｒ  ａ  ｍｏｂｉｌｅ  ｃｏｍｐｕｔｉｎｇ  ｅｎｖｉｒｏｎｍｅｎｔ)」、ＩＥＩＣＥ情報及びシステムの取引(ＩＥＩＣＥＴｒａｎｓａｃｔｉｏｎｓ  ｏｆ  Ｉｎｆｏｒｍａｔｉｏｎ  ａｎｄ  Ｓｙｓｔｅｍｓ)、Ｅ８４−Ｄ（６）、７０９−７１６ページ、２００１年
［１５］コッハー（Ｐ．Ｋｏｃｈｅｒ）著、「証明書の失効及び検証に関して(Ｏｎ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｒｅｖｏｃａｔｉｏｎ  ａｎｄ  Ｖａｌｉｄａｔｉｏｎ)」、予稿集、金融暗号技術に関する第2回国際会議(ｔｈｅ  ２ｎｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｆｉｎａｎｃｉａｌ  Ｃｒｙｐｔｏｇｒａｐｈｙ)、１９９８年
［１６］サトシ・コガ（Ｓａｔｏｓｈｉ  Ｋｏｇａ）及びコウイチ・サクライ（Ｋｏｕｉｃｈｉ  Ｓａｋｕｒａｉ）著、「単一の公開鍵を有する配布済み証明書状態プロトコル(Ａ  ｄｉｓｔｒｉｂｕｔｅｄ  ｃｅｒｔｉｆｉｃａｔｅ  ｓｔａｔｕｓ  ｐｒｏｔｏｃｏｌ  ｗｉｔｈ  ｓｉｎｇｌｅ  ｐｕｂｌｉｃ  ｋｅｙ)」、予稿集、ピィ・ケイ・シィ２００４(ＰＫＣ２００４)、３８９−４０１ページ、２００４年
［１７］リプトン（Ｒ．Ｊ．Ｌｉｐｔｏｎ）及びオストロフスキ（Ｒ．Ｏｓｔｒｏｖｓｋｙ）著、「効率的なコインフリッピングによるマイクロペイメント(Ｍｉｃｒｏ−Ｐａｙｍｅｎｔｓ  ｖｉａ  Ｅｆｆｉｃｉｅｎｔ  Ｃｏｉｎ  Ｆｌｉｐｐｉｎｇ)」、予稿集、金融暗号技術に関する第２回国際会議(ｔｈｅ  ２ｎｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｆｉｎａｎｃｉａｌ  Ｃｒｙｐｔｏｇｒａｐｈｙ)、１９９８年
［１８］マルパーニ（Ａ．Ｍａｌｐａｎｉ）、ハウスリィ（Ｒ．Ｈｏｕｓｅｌｙ）、及びフリーマン（Ｔ．Ｆｒｅｅｍａｎ）著、「簡単な証明書検証プロトコル(Ｓｉｍｐｌｅ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｖａｌｉｄａｔｉｏｎ  Ｐｒｏｔｏｃｏｌ  −  （ＳＣＶＰ）)」、ＩＥＴＦドラフト(ＩＥＴＦ  Ｄｒａｆｔ)、ｄｒａｆｔ−ｉｅｔｆ−ｐｋｉｘ−ｓｃｖｐ−１２．ｔｘｔ、２００３年６月
［１９］メルクル（Ｒ．Ｃ．Ｍｅｒｋｌｅ）著、「公開鍵暗号技術用プロトコル(Ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ)」、安全性及びプライバシーに関するＩＥＥＥシンポジウム(ＩＥＥＥＳｙｍｐｏｓｉｕｍ  ｏｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｐｒｉｖａｃｙ)、１９８０年
［２０］ミカリ（Ｓ．Ｍｉｃａｌｉ）著、「効率的な証明書の失効(Ｅｆｆｉｃｉｅｎｔ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｒｅｖｏｃａｔｉｏｎ)」、ＭＩＴ／ＬＣＳ／ＴＭ  ５４２ｂ、マサチュウセッツ工科大学(Ｍａｓｓａｃｈｕｓｅｔｔｓ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｔｅｃｈｎｏｌｏｇｙ)、１９９６年
［２１］ミカリ（Ｓ．Ｍｉｃａｌｉ）著、「効率的な証明書の失効(Ｅｆｆｉｃｉｅｎｔ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｒｅｖｏｃａｔｉｏｎ)」、予稿集、ＲＳＡデータセキュリティ会議 (ｔｈｅ  ＲＳＡ  Ｄａｔａ  Ｓｅｃｕｒｉｔｙ  Ｃｏｎｆｅｒｅｎｃｅ)、１９９７年、及び米国特許第５６６６４１６
［２２］ミカリ（Ｓ．Ｍｉｃａｌｉ）著、「ＮＯＶＯＭＯＤＯ：スケーラブル証明書検証及び簡略化したＰＫＩマネージメント(ＮＯＶＯＭＯＤＯ：  ｓｃａｌａｂｌｅ  ｃｅｒｔｉｆｉｃａｔｅ  ｖａｌｉｄａｔｉｏｎ  ａｎｄ  ｓｉｍｐｌｉｆｉｅｄ  ＰＫＩ  ｍａｎａｇｅｍｅｎｔ)」、予稿集、第１回ＰＫＩ研究ワークショップ年次会議(ｔｈｅ  １ｓｔ  Ａｎｎｕａｌ  ＰＫＩ  Ｒｅｓｅａｒｃｈ  Ｗｏｒｋｓｈｏｐ)、２００２年
［２３］メイヤーズ(Ｍ．Ｍｙｅｒｓ)、アンクネイ(Ｒ．Ａｎｋｎｅｙ)、マルパーニ(Ａ．  Ｍａｌｐａｎｉ)、ガルペリン(Ｓ．  Ｇａｌｐｅｒｉｎ)、及びアダムス(Ｃ．  Ａｄａｍｓ)著、「Ｘ．５０９インターネット公開鍵インフラオンライン証明書状態プロトコル(Ｘ．５０９  ｉｎｔｅｒｎｅｔ  ｐｕｂｌｉｃ  ｋｅｙ  ｉｎｆｒａｓｔｒｕｃｔｕｒｅ  Ｏｎｌｉｎｅ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｓｔａｔｕｓ  Ｐｒｏｔｏｃｏｌ−ＯＣＳＰ)」、インターネットＲＦＣ２５６０(Ｉｎｔｅｒｎｅｔ  ＲＦＣ  ２５６０)、１９９９年６月
［２４］マオル(Ｍ．Ｎａｏｒ)及びニッシム(Ｋ．Ｎｉｓｓｉｍ)著、「(Ｃｅｒｔｉｆｉｃａｔｅ  Ｒｅｖｏｃａｔｉｏｎ  ａｎｄ  Ｃｅｒｔｉｆｉｃａｔｅ  Ｕｐｄａｔｅ)」、予稿集、ＵＳＥＮＩＸセキュリティ(ＵＳＥＮＩＸ  Ｓｅｃｕｒｉｔｙ)、  １９９８年
［２５］アメリカ標準局(Ｎａｔｉｏｎａｌ  Ｂｕｒｅａｕ  ｏｆ  Ｓｔａｎｄａｒｄｓ)発行、「ＮＢＳ  ＦＩＰＳ  ＰＵＢ  ８１：オペレーションのＤＥＳモデル(ＮＢＳ  ＦＩＰＳ  ＰＵＢ  ８１：ＤＥＳ  ｍｏｄｅｓ  ｏｆ  ｏｐｅｒａｔｉｏｎ)」、１９８０年
［２６］アメリカ標準局(Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ)発行、「ＦＩＰＳ  １８０−１：安全なハッシュ基準(ＦＩＰＳ  １８０−１：  Ｓｅｃｕｒｅ  ｈａｓｈ  ｓｔａｎｄａｒｄ)」、１９９５年
［２７］ピアス(Ｍ．Ｐｉｅｒｃｅ)、及びオーマホニー(Ｄ．Ｏ’Ｍａｈｏｎｙ)著、「モバイルネットワークのためのマイクロペイメント(Ｍｉｃｒｏｐａｙｍｅｎｔｓ  ｆｏｒ  Ｍｏｂｉｌｅ  Ｎｅｔｗｏｒｋｓ)」、予稿集、ヨーロピアン無線(Ｅｕｒｏｐｅａｎ  Ｗｉｒｅｌｅｓｓ)、１９９９年、最優秀論文賞受賞(Ｗｉｎｎｅｒ  ｏｆ  Ｂｅｓｔ  Ｐａｐｅｒ  Ａｗａｒｄ)
［２８］リベスト（Ｒ．Ｌ．Ｒｉｖｅｓｔ）著、「ＭＤ５メッセージダイジェストアルゴリズ(Ｔｈｅ  ＭＤ５  ｍｅｓｓａｇｅ  ｄｉｇｅｓｔ  ａｌｇｏｒｉｔｈｍ)」、インターネット  アール・エフ・シー１３２１(Ｉｎｔｅｒｎｅｔ  ＲＦＣ  １３２１)、１９９２年４月
［２９］リべスト(Ｒ．Ｌ．Ｒｉｖｅｓｔ)著、「マイクロペイメントとしての電子ロトチケット(Ｅｌｅｃｔｒｏｎｉｃ  Ｌｏｔｔｅｒｙ  Ｔｉｃｋｅｔｓ  ａｓ  Ｍｉｃｒｏｐａｙｍｅｎｔｓ)」、予稿集、金融暗号技術に関する第２回国際会議(ｔｈｅ  ２ｎｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｆｉｎａｎｃｉａｌ  Ｃｒｙｐｔｏｇｒａｐｈｙ)、１９９７年
［３０］リベスト(Ｒ．Ｌ．  Ｒｉｖｅｓｔ)、及びシャミール(Ａ．  Ｓｈａｍｉｒ)著、「ペイワード及びマイクロミント−2つのシンプルなマイクロペイメントスキーム(ＰａｙＷｏｒｄ  ａｎｄ  ＭｉｃｒｏＭｉｎｔ−Ｔｗｏ  Ｓｉｍｐｌｅ  Ｍｉｃｒｏｐａｙｍｅｎｔ  Ｓｃｈｅｍｅｓ)」、クリプトバイト(ＣｒｙｐｔｏＢｙｔｅｓ)、ＲＳＡラボラトリィズ（ＲＳＡ  Ｌａｂｏｒａｔｏｒｉｅｓ）、２（１）巻、１９９６年、予稿集、１９９６年セキュリティプロトコルに関する国際ワークショップ(１９９６ Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｓｅｃｕｒｉｔｙ  Ｐｒｏｔｏｃｏｌｓ)
［３１］リベスト（Ｒ．Ｌ．Ｒｉｖｅｓｔ）、シャミール（Ａ．Ｓｈａｍｉｒ）及びアドルマン（Ｌ．Ａｄｌｅｍａｎ）著、「デジタル署名及び公開鍵クリプトシステムを取得するための方法(Ａ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｏｂｔａｉｎｉｎｇ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅｓ  ａｎｄ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ)」、ＡＣＭ通信(Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ)、２１：１２０−１２６ページ、１９７８年
［３２］ロン・シュタインフィールド(Ｒｏｎ  Ｓｔｅｉｎｆｅｌｄ)、ローレンス・ブル(Ｌａｕｒｅｎｃｅ  Ｂｕｌｌ)、及びユリアン・ツェン(Ｙｕｌｉａｎｇ  Ｚｈｅｎｇ)著、「コンテンツ抽出署名(Ｃｏｎｔｅｎｔ  ｅｘｔｒａｃｔｉｏｎ  ｓｉｇｎａｔｕｒｅｓ)」、予稿集、ソウル情報セキュリティ及び暗号に関する第4回国際会議 (ｔｈｅ  ４ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  Ｓｅｏｕｌ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｃｒｙｐｔｏｌｏｇｙ)、２８５−３０４ページ、シュプリンガ−フェアラーク(Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ)社、２００２年
［３３］テワリ(Ｈ．Ｔｅｗａｒｉ)、及びオーマホニー(Ｄ．Ｏ’Ｍａｈｏｎｙ)著、「アドホックネットワーク用マルチパーティ・マイクロペイメント(Ｍｕｌｔｉｐａｒｔｙ  Ｍｉｃｒｏｐａｙｍｅｎｔｓ  ｆｏｒ  Ａｄ−Ｈｏｃ  Ｎｅｔｗｏｒｋｓ)」、予稿集、ＩＥＥＥ無線通信及びネットワークに関する会議(ｔｈｅ  ＩＥＥＥ  Ｗｉｒｅｌｅｓｓ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ａｎｄ  Ｎｅｔｗｏｒｋｉｎｇ  Ｃｏｎｆｅｒｅｎｃｅ  （ＷＣＮＣ）)、２００３年
［３４］テワリ(Ｈ．Ｔｅｗａｒｉ)及びオーマホニー(Ｄ．Ｏ’Ｍａｈｏｎｙ)著、「モバイルＩＰ用リアルタイムペイメント(Ｒｅａｌ−Ｔｉｍｅ  Ｐａｙｍｅｎｔｓ  ｆｏｒ  Ｍｏｂｉｌｅ  ＩＰ)」、ＩＥＥＥ通信(ＩＥＥＥ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ)、４１（２）巻：１２６−１３６、２００３年
［３５］ウィーラー（Ｄ．Ｗｈｅｅｌｅｒ）著、「賭けを用いた取引(Ｔｒａｎｓａｃｔｉｏｎｓ  Ｕｓｉｎｇ  Ｂｅｔｓ)」、予稿集、セキュリティプロトコルに関する第4回ケンブリッジワークショップ(Ｆｏｕｒｔｈ  Ｃａｍｂｒｉｄｇｅ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｓｅｃｕｒｉｔｙ  Ｐｒｏｔｏｃｏｌｓ)、１９９６年
［３６］ツォウ（Ｊ．Ｚｈｏｕ）及びラム（Ｋ−Ｙ．Ｌａｍ）著、「モバイル通信における優れたビリング(Ｕｎｄｅｎｉａｂｌｅ  Ｂｉｌｌｉｎｇ  ｉｎ  Ｍｏｂｉｌｅ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ”、予稿集、モビコム(ＭＯＢＩＣＯＭ)、１９９８年  
［３７］グッドリッチ（Ｍ．  Ｇｏｏｄｒｉｃｈ）及びタマシア（Ｒ．Ｔａｍａｓｓｉａ）著、「ダイナミックな配布された有効な暗号化アキュムレータ（Ａｎ  Ｅｆｆｉｃｉｅｎｔ  Ｄｙｎａｍｉｃ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ａｃｃｕｍｕｌａｔｏｒ）」、２００１年
［３８］ベナロウ（Ｊ．Ｂｅｎａｌｏｈ）及びデマーレ（Ｍ．ｄｅ  Ｍａｒｅ）著、「一方向アキュムレータ：分散型のデジタル証明書に代わるもの（Ｏｎｅ−Ｗａｙ  Ａｃｃｕｍｕｌａｔｏｒｓ：  Ａ  Ｄｅｃｅｎｔｒａｌｉｚｅｄ  Ａｌｔｅｒｎａｔｉｖｅ  ｔｏ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅｓ」
［３９］カメニッシュ（Ｊ．Ｃａｍｅｎｉｓｃｈ）及びリスヤンスカヤ（Ａ．Ｌｙｓｙａｎｓｋａｙａ）著、「ダイナミックアキュムレータ及び、匿名の証明書の効率的な無効化への応用（Ｄｙｎａｍｉｃ  Ａｃｃｕｍｕｌａｔｏｒｓ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  Ｅｆｆｉｃｉｅｎｔ  Ｒｅｖｏｃａｔｉｏｎ  ｏｆ  Ａｎｏｎｙｍｏｕｓ  Ｃｒｅｄｅｎｔｉａｌｓ）」、２００２年  
［４０］ゴクヘール（Ｓ．Ｇｏｋｈａｌｅ）及びダスガプタ（Ｐ．Ｄａｓｇｕｐｔａ）著、「ピアツーピアネットワークに対して配布された認証（Ｄｉｓｔｒｉｂｕｔｅｄ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ｆｏｒ  Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ  Ｎｅｔｗｏｒｋｓ）」、  アプリケーションに関するシンポジウム及びインターネットワークショップ（Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ａｐｐｌｉｃａｔｉｏｎｓ  ａｎｄ  ｔｈｅ  Ｉｎｔｅｒｎｅｔ  Ｗｏｒｋｓｈｏｐｓ）、ＳＡＩＮＴ２００３年ワークショップ（ＳＡＩＮＴ‘０３  Ｗｏｒｋｓｈｏｐｓ）、２００３年
［４１］ゴールドライヒ（Ｏ．Ｇｏｌｄｒｅｉｃｈ）、ミカリ（Ｓ．Ｍｉｃａｌｉ）及びウィダーソン（Ａ．Ｗｉｇｄｅｒｓｏｎ）著、「有効性を放棄するにすぎない証明及び、暗号プロトコル設計の方法（Ｐｒｏｏｆｓ  ｔｈａｔ  Ｙｉｅｌｄ  Ｎｏｔｈｉｎｇ  Ｂｕｔ  ｔｈｅｉｒ  Ｖａｌｉｄｉｔｙ  ａｎｄ  ａ  Ｍｅｔｈｏｄｏｌｏｇｙ  ｏｆ  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｐｒｏｔｏｃｏｌ  Ｄｅｓｉｇｎ）」、拡大予稿集（Ｅｘｔｅｎｄｅｄ  Ａｂｓｔｒａｃｔ）、２７回ＦＯＣＳ（２７ｔｈ  ＦＯＣＳ）、１９８６年、（ＩＥＥＥ）
［４２］ゴールドライヒ（Ｏ．Ｇｏｌｄｒｅｉｃｈ）及びカリアン（Ａ．Ｋａｌｉａｎ）著、「ＮＰに対するシステムの一定の丸いゼロ知識証明システムの構成方法（Ｈｏｗ  ｔｏ  Ｃｏｎｓｔｒｕｃｔ  Ｃｏｎｓｔａｎｔ−Ｒｏｕｎｄ  Ｚｅｒｏ−Ｋｎｏｗｌｅｄｇｅ  Ｐｒｏｏｆ  Ｓｙｓｔｅｍｓ  ｆｏｒ  ＮＰ）」、暗号学会誌（Ｊｏｕｒｎａｌ  ｏｆ  Ｃｒｙｐｔｏｌｏｇｙ）、第９巻Ｎｏ．３（Ｖｏｌｕｍｅ  ９、Ｎｏ．３）、１９９６年、１６７−１９０ページ  
【０２１３】
付録Ａ
アキュムレータ及び知識の証明
定義（安全なアキュムレータ）
入力群｛ＸＸｋ｝のファミリーに対する安全なアキュムレータは、以下のプロパティを有する関数群ＧＧ＝｛ＦＦｋ｝のうちの一群である。すなわち、
効率的な生成：入力ｌｋにおいて、｛ＦＦｋ｝のランダムなエレメントｆを生成する効率的な確率的アルゴリズムＧがある。また、Ｇは、ａｕｘｆで示されるｆに関する補助的な情報も出力する。
【０２１４】
効率的な評価：ｆ∈｛ＦＦｋ｝は、入力（ｕ，ｘ）∈ＵＵｆｘＸＸｋにおいて、値ｖ∈ＵＵｆを出力する多項式サイズの回路である。ここで、ＵＵｆは、関数ｆに対して効率的にサンプリングすることが可能な入力ドメインであり、｛ＸＸｋ｝は、そのエレメントが累算される対象となる入力ドメインである。
【０２１５】
準可換：全てのｋ、全てのｆ∈ＦＦｋ、全てのｕ∈ＵＵｆ、全てのｘ１ｘ２∈ＸＸｋに対して、ｆ（ｆ（ｕ，ｘ１），ｘ２）＝ｆ（ｆ（ｕ，ｘ２），ｘ１）である。Ｘ＝｛ｘ１，．．．，ｘｍ｝⊂ＸＸｋの場合、ｆ（ｕ，Ｘ）で、ｆ（ｆ．．．（ｕ，ｘ１），．．．），ｘｍ）を示す。
【０２１６】
ウィットネス：ｖ∈ＵＵｆ及びｘ∈ＸＸｋとする。値、ｗ∈ＵＵｆは、ｖ＝ｆ（ｗ，ｘ）の場合、ｆの下のｖにおけるｘに対するウィットネスと呼ばれる。
【０２１７】
安全性：ＵＵ’ｆｘＸＸ’ｋは、関数ｆ∈ＦＦｋの計算手順が、そのために定義されるドメインを示すこととする（よって、ＵＵｆ⊆ＵＵ’ｆ，ＸＸｋ⊆ＸＸ’ｋ）。全ての確率的多項式時間の敵Ａｋに対して、
【数８６】
2008524930.tif 000088
【０２１８】
である。
【０２１９】
カメニッシュ（Ｃａｍｅｎｉｓｃｈ）及びリスヤンスカヤ（Ｌｙｓｙａｎｓｋａｙａ）（［３９］）は、ダイナミックアキュムレータの概念を次のように定義している。
【０２２０】
定義（ダイナミックアキュムレータ）
次のプロパティを有する場合、安全なアキュムレータは、ダイナミックである。
【０２２１】
効率的な削除：ｖ＝ｆ（ｕ，Ｘ）、及び、ｘ，ｘ’∈Ｘ及びｆ（ｗ、ｘ）＝ｖとなる場合、
ｖ’＝ｆ（ｕ，Ｘ−｛ｘ’｝）となるようなＤ（ａｕｘｆ，ｖ，ｘ’）及び、
ｆ（ｗ’，ｘ）＝ｖ’となるようなＷ（ｆ，ｖ，ｖ’，ｘ，ｘ’）
であるような効率的なアルゴリズムＤ及びアルゴリズムＷが存在する。
【０２２２】
ゼロ知識証明：アキュムレータ（少なくとも、以下に説明するＲＳＡに基づくアキュムレータ）の利点は、値が累算されている効率的なゼロ知識証明（ＺＫ証明）を構成することが可能であることである。ＮＰ（非確定的多項式時間）におけるステートメントのいずれもＺＫにおいて証明することができることが証明されているが、いくつかのステートメントは、ＺＫにおいて他よりもさらに効率的に証明することができる。ブラッサード（Ｂｒａｓｓａｒｄ）、チャウム（Ｃｈａｕｍ）及びクレポウ（Ｃｒｅｐｅａｕ）、また、ゴールドワッサー（Ｇｏｌｄｗａｓｓｅｒ）、ミカリ（Ｍｉｃａｌｉ）及びラクコ（Ｒａｃｋｏ）によって別々に導入され、さらにベラレ（Ｂｅｌｌａｒｅ）及びゴールドライヒ（Ｇｏｌｄｒｅｉｃｈ）によってさらに洗練されたＺＫ証明の概念を簡潔に説明する。
【０２２３】
ｘを入力、Rを多項式的に計算可能な関係式とする。大雑把に言うと、Ｒ（ｘ，ｗ）＝１となるようなウィットネスｗの知識のゼロ知識証明は、プロトコルの後に、ベリファイヤＶが、証明者Ｐは、そのようなウィットネスｗを知っていることを確信するが、Ｖは、ｗに対する具体的な情報を何も入手していないような、P及びＶの間の確率的多項式時間で計算可能なプロトコルである。すなわち、Ｒ（ｘ，ｗ）＝１となるようなウィットネスｗを知っていることを「証明する」のとは別に、Ｐは、Ｖに「ゼロ知識」を通知する。
【０２２４】
その後、相異なる対数に関する知識のさまざまな証明及び、相異なる対数についてのステートンメントの有効性の証明に対して、カメニッシュ（Ｃａｍｅｎｉｓｃｈ）及びスタッドラー（Ｓｔａｄｌｅｒ）によって導入された表記を用いてもよい。例えば、
【数８７】
2008524930.tif 000089
【０２２５】
であり、
【数８８】
2008524930.tif 000090
【０２２６】
とｇ、ｇ’、ｈ、ｈ’、ｙ、ｙ’を、群Ｇ＝＜ｇ＞＝＜ｈ＞及びＧ’＝＜ｇ’＞＝＜ｈ’＞のエレメントとする、ｙ＝ｇαｈβ及びｙ’＝ｇ’αｈ’γとなるような整数α、β、γの知識のゼロ知識証明を示す。この規約は、ギリシャ文字が、証明されている知識の量を示し、一方、他の全てのパラメータは、ベリファイヤに公知である。この表記を用いて、全ての詳細を隠しながらその目的を指摘するだけで、証明プロトコルを説明することができる。
【０２２７】
しばしば、これらの知識の証明は、証明者がベリファイヤにある値へのコミットメント（ｃｏｍｍｉｔｍｅｎｔ）をまず送信し、その後、ベリファイヤが証明者にチャレンジ（ｃｈａｌｌｅｎｇｅ）ビット文字列を送り、そして最終的に、証明者が、ベリファイヤが証明者の知識を確信していると確信させるようにコミット値及びチャレンジ値の両方の「公知の値」を組み込んだ応答（ｒｅｓｐｏｎｓｅ）を送信する、３パスプロトコルによってインスタンス化されている。
【０２２８】
これらの知識の証明は、フィアット−シャミール（Ｆｉａｔ−Ｓｈａｍｉｒ）ヒューリスティックを介して、署名スキームへ変換することができる。つまり、証明者は、衝突耐性を持つハッシュ関数Ｈを、コミットメント及び、署名され、従来通り応答を計算するメッセージｍに適用することによってチャレンジｃを決定する。そのような知識の署名証明書を、例えば、ＳＰＫ｛α：ｙ＝ｆ（α）｝（ｍ）の表記によって示す。根底にある知識の証明の安全性をがあるとすれば、そのようなＳＰＫは、ランダムオラクルモデルにおいて安全であると証明することができる。
【０２２９】
ＺＫ証明は、コミットメントスキームの助けを受けて達成できることがよくある。コミットメントスキームは、次のプロパティを有するアルゴリズムＣｏｍｍｉｔ及び、アルゴリズムＶｅｒｉｆｙＣｏｍｍｉｔから構成される。コミットメントアルゴリズムのＣｏｍｍｉｔは、入力としてメッセージｍ、ランダムな文字列ｒを取り、コミットメントＣ、すなわち、Ｃ＝Ｃｏｍｍｉｔ（ｍ，ｒ）を出力する。（コミットメント）検証アルゴリズムＶｅｒｉｆｙＣｏｍｍｉｔは、入力として、（Ｃ，ｍ，ｒ）を取り、ＣがＣｏｍｍｉｔ（ｍ，ｒ）と等しい場合は、１（受信）を出力し、そうでなければ、０（拒否）を出力する。コミットメントスキームの安全のプロパティは、次の通りである。隠しプロパティとは、コミットメントＣ＝Ｃｏｍｍｉｔ（ｍ，ｒ）が、ｍに関する（計算処理上の）情報を含まないということである。結合プロパティとは、１＝ＶｅｒｉｆｙＣｏｍｍｉｔ（Ｃ，ｍ，ｒ）であるＣ，ｍ，ｒが与えられた場合、１＝ＶｅｒｉｆｙＣｏｍｍｉｔ（Ｃ，ｍ0，ｒ０）となるようなメッセージｍ０及び文字列ｒ０を見つけることは（計算処理上）不可能であるということである。
【０２３０】
ＺＫにおいて、累算されている、すなわち、ｖをアキュムレータ値とするｆ（ｗ，ｘ）＝ｖである値ｘのウィットネスｗの知識を証明するための通常の方法は、ランダムな文字列ｒを選択し、コミットメントＣ＝Ｃｏｍｍｉｔ（ｘ，ｒ）を構成し、そして、次の知識の証明を提供する。
【０２３１】
ＰＫ｛（α，β，γ）：ｃ＝Ｃｏｍｍｉｔ（α，γ）∧ｆ（α，γ）＝ｖ｝
上記αは、（隠し）ｘの値を表し、βは、ｒを、γは、ｗを表す。
【０２３２】
ＲＳＡに基づくアキュムレータ
ここで、一般的で具体的なアキュムレータのインスタンス化を、リベスト（Ｒｉｖｅｓｔ）、シャミール（Ｓｈａｍｉｒ）及び、アドルマン（Ａｄｌｅｍｅｎ）が１９７７年に発明した公知のＲＳＡ公開鍵暗号システムに関連する数学を用いて説明する。ここまで、ＲＳＡに基づくアキュムレータのインスタンス化を中心に説明してきたが、これらの説明に制限されるものと見なされるべきではない。本発明のアキュムレータに基づく証明書失効スキームは、どのようなタイプのアキュムレータにでも用いることができる。アキュムレータ構造は、そのサイズが、累算されたエレメント数に基づかないという利点がある。ＲＳＡに基づくアキュムレータは、因数分解することが困難であるように選択されなければならないモジュラスと呼ばれる合成数ｎを利用する。上記に定義したスキームのいくつかの実施形態において、モジュラスは、次のように定義されるＲＳＡモジュラスである。
【０２３３】
定義（ＲＳＡモジュラス）
２ｋ−ビット数ｎは、ｎ＝ｐｑの場合、ＲＳＡモジュラスと呼ばれる。ここで、ｐ及びｑは、ｋ−ビットの素数である。
【０２３４】
もちろん、ｎを異なる方法で、例えば、３つの素数の積として、又は、相異なるサイズの２つの素数の積として選択することもできる。
【０２３５】
定義（オイラー関数）
ｎを整数とする。オイラー関数φ（ｎ）は、集合
【数８９】
2008524930.tif 000091
【０２３６】
の基数である（ｎを法とする整数の環Ｚｎにおける逆数を有するエレメントの乗法群、
【数９０】
2008524930.tif 000092
【０２３７】
は、ｎと互いに素である全てのエレメントの集合である）。
【０２３８】
ｎ＝ｐｑが、２つの素数の積である場合、φ（ｎ）＝（ｐ−１）（ｑ−１）である。
【０２３９】
ＲＳＡに基づくアキュムレータの安全性は、以下の仮定に基づいている。
【０２４０】
定義（強ＲＳＡ仮定）
強ＲＳＡ仮定は、入力であるＲＳＡモジュラスｎ及び、エレメント
【数９１】
2008524930.tif 000093
【０２４１】
上の、値ｅ＞１及びｖを、ｖｅ＝ｕ（ｎを法とする）となるように計算することは「難しい」というものである。「難しい」とは、全ての多項式時間回路群｛Ａｋ｝に対して、
【数９２】
2008524930.tif 000094
【０２４２】
となるような、無視することのできる関数ｎｅｇ（ｋ）が存在するということである。ここで、ＲＳＡｍｏｄｕｌｕｓ１ｋは、ＲＳＡモジュラスを２つのランダムなｋ−ビットの素数の積として生成するアルゴリズムであり、無視することのできる関数ｎｅｇ（ｋ）は、全ての多項式ｐ（ｋ）に対して、全てのｋ＞ｋ０に対してｎｅｇ（ｋ）＜１／ｐ（ｋ）であるような値ｋ０が存在するような関数である。上記のように生成された組（ｎ，ｕ）は、強ＲＳＡ問題の一般例である。
【０２４３】
コロラリー１
強ＲＳＡ仮定の下では、入力であるフレキシブルなＲＳＡインスタンス（ｎ，ｕ）上の、整数ｅ＞１及びｖを、ｖｅ＝ｕ（ｍｏｄ ｎ）となるように計算することは難しい。
【０２４４】
最も一般的なアキュムレータの具体的なインスタンス化は、上記の強ＲＳＡ仮定に基づいている。大雑把に言うと、その考え方は次のようになる。固定された底ｕ（ｎを法とする）を与えられると、（例えば）値ｘ１とｘ２のアキュムレータを
【数９３】
2008524930.tif 000095
【０２４５】
として計算することができる。（例えば）ｘ１が累算されていることを証明するために、ウィットネス
【数９４】
2008524930.tif 000096
【０２４６】
を転送することができ、ベリファイヤは、実際に
【数９５】
2008524930.tif 000097
【０２４７】
であることを確認することができる。
【０２４８】
ここで、アキュムレータの公式な説明を具体的なＲＳＡに基づく構造に関係付ける。入力群Ｘｋに対する安全なＲＳＡに基づくアキュムレータは、特定の関数ｆ∈ＦＦｋが、モジュラスｎが何かによって決まる関数群ＦＦｋである。以下で明らかになる理由によって、Ｘｋのエレメントをペアの互いに素である整数であると仮定する。そして、ａｕｘｆは、ｎの（秘密）因数分解である。上述したように、初期アキュムレータ値ｖ’が与えられると、追加的値ｘは、新規アキュムレータ値ｖ＝ｖ’ｘ（ｍｏｄ ｎ）を計算することによってアキュムレータに加えられる。このアルゴリズムの計算処理量は、累算されている先行する値の数とは無関係であることに留意すること。ＲＳＡに基づくアキュムレータは、例えば、ｘ１とｘ２が、初期アキュムレータｖ’に組み込まれる順番とは関係なく、準可換なプロパティを所有し、その結果は、
【数９６】
2008524930.tif 000098
【０２４９】
である。アキュムレータｖ（ｍｏｄ ｎ）を与えられているので、値ｘが累算されたウィットネスは、ｖ＝ｗｘ（ｍｏｄ ｎ）を確認することによって容易に検証可能なｗ＝ｖ１／ｘ（ｍｏｄ ｎ）である。反復するために、構成の安全性は、強ＲＳＡ問題が解決不可能であるという仮定に基づいている。
【０２５０】
ＲＳＡに基づくアキュムレータは、ダイナミックにすることができる。アキュムレータは、集合Ｘの値を累算するアキュムレータｖを与えられ、秘密情報ａｕｘｆを与えらるとして、値ｘ’∈Ｘを「ディアキュムレート」することができる、すなわち、集合Ｘ−｛ｘ’｝の値を累算する新規のアキュムレータｖ’を計算できる場合、ダイナミックであることを思い出して欲しい。さらに、値ｘが（集合Ｘの要素を累算するアキュムレータｖに関して）累算されているウィットネスｗを与えられ、Ｘ−｛ｘ’｝の要素だけを累算するアキュムレータｖ’が与えられると、アキュムレータｖ’に関してｘに対する新規ウィットネスｗを計算することができる。特に、ＲＳＡに基づくアキュムレータに対して、ｎの因数分解を用いてｖ’＝ｖ１／ｘ’（ｍｏｄ ｎ）を計算することによって、ｘ’をディアキュムレートすることができる。また、ｖに関してｘに対するウィットネスｗが与えられ、すなわち、ｗｘ＝ｖ（ｍｏｄ ｎ）であり、ｖ’の値も与えられている場合、以下のように、ｖ’に関して、ｘに対するウィットネスｗ’、 すなわち、
【数９７】
2008524930.tif 000099
【０２５１】
を計算することができる。ｘとｘ’は、互いに素であると仮定すると、ａｘ＋ｂｘ’＝１となるような整数（ａ，ｂ）を、拡張ユークリッドアルゴリズムを用いて計算することができる。そして、
【数９８】
2008524930.tif 000100
【０２５２】
である。ｗ’の計算は、効率的であり、（ｖ’が計算された後に）（例えば、ｎの因数分解など）秘密の知識を何も必要としないことに留意。
【０２５３】
（アキュムレータｖ（ｍｏｄ ｎ）に関して）値ｘが累算されるウィットネスｗを与えられているので、（ベリファイヤから、ｗとｘの両方の値を隠す）ｗｘ＝ｖ（ｍｏｄ ｎ）を満たすペア（ｗ，ｘ）の知識のＺＫ証明をどのように構成するかは、当業者には公知である。
【０２５４】
以上付録Ａ
付録B
ギユ・キスケータ（Ｇｕｉｌｌｏｕ−Ｑｕｉｓｑｕａｔｅｒ（ＧＱ））
認証方式に基づく署名スキーム
設定
１．公開鍵ジェネレータ（ＰＫＧ、信頼できる関係者）は、その公開鍵（ｖ，ｎ）を発行する。ここで、ｎ＝ｑ１ｑ２（２つの素数の積）であり、その因数分解を見つけるのは難しく、ｖはφ（ｎ）＝（ｐ−１）（ｑ−１）よりも小さい素数である。
【０２５５】
２．アイデンティティＩＤ（例えば、電子メールアドレス）を有するユーザに対して、ＰＫＧは、ＪＢｖ≡１ｍｏｄ ｎと成るように秘密署名鍵Ｂを計算する。ここで、Ｊ＝Ｒ（ＩＤ）であり、Ｒは、例えば、冗長関数などの予め定義された公知の関数である。いくつかの実施形態において、関数Ｒは、ＩＤをＺｎのエレメントにマップする。関数Ｒは、有効なＩＤからのマッピングに対応するＺｎにおけるエレメント数が小さくなるようなものである。ＰＫＧは、Ｂをユーザに対して安全な（例えば、暗号化された）チャンネルを介して送信する。
【０２５６】
署名
メッセージＭに署名するために、ユーザは、
１．Ｊ＝Ｒ（ＩＤ）を計算し、
２．ランダムな数ｒを生成し、
ｄ＝Ｈ（ｍ｜｜ｒｖ），Ｄ＝ｒＢｄ    （Ｂ−１）
を計算する。ここで、Ｈは、（例えば、ハッシュ関数などの）予め定義された公開関数であり、
３．値Ｍ、ｒｖ、ｄ、Ｄをベリファイヤに送信する。
【０２５７】
検証
ベリファイヤは、
１．Ｊ＝Ｒ（ＩＤ）を計算し、 
２．ｄ＝Ｈ（ｍ｜｜ｒｖ）を確認し、
３．ＪｄＤｖ＝ｒｖを確認する
以上付録Ｂ 
【図面の簡単な説明】
【０２５８】
【図１】図１は、従来技術による証明書失効スキームを説明するブロック図である。
【図２】図２は、従来技術による証明書失効スキームを説明するブロック図である。
【図３】図３は、本発明のいくつかの実施形態によるデジタル証明書を示す図である。
【図４】図４は、本発明のいくつかの実施形態による初期証明書における認証局（ＣＡ）が実行する動作のフローチャートである。
【図５】図５は、本発明のいくつかの実施形態によるＣＡが実行する証明書の有効性再検証の動作を示すブロック図である。
【図６】本発明のいくつかの実施形態によるウィットネス導出動作のフローチャートである。
【図７】図７は、本発明のいくつかの実施形態による認証のフローチャートである。
【図８】図８は、本発明のいくつかの実施形態によるディアキュムレーション動作においてネットワーク上で送信されたデータを示すブロック図である。
【図９】図９は、本発明のいくつかの実施形態によるアキュムレータ送信を説明する状態図である。
【図１０】図１０は、本発明のいくつかの実施形態によるネットワークパスを決定する際のデータ送信を説明するブロック図である。
【図１１】図１１は、本発明のいくつかの実施形態による初期証明書における認証局（ＣＡ）によって実行される動作のフローチャートである。
【図１２】図１２は、本発明のいくつかの実施形態によるＣＡによって実行される証明書の再検証動作を説明するブロック図である。
【図１３】図１３は、本発明のいくつかの実施形態によるウィットネス導出動作のフローチャートである。
【図１４】図１４は、本発明のいくつかの実施形態による認証のフローチャートである。
【符号の説明】
【０２５９】
１０４、１４０  デジタル証明書
１１０  コンピュータシステム
１２０  認証局
１５０  クエリ
１６０  フィールド
【図１】
2008524930.tif 000101
【図２】
2008524930.tif 000102
【図３】
2008524930.tif 000103
【図４】
2008524930.tif 000104
【図５】
2008524930.tif 000105
【図６】
2008524930.tif 000106
【図７】
2008524930.tif 000107
【図８】
2008524930.tif 000108
【図９】
2008524930.tif 000109
【図１０】
2008524930.tif 000110
【図１１】
2008524930.tif 000111
【図１２】
2008524930.tif 000112
【図１３】
2008524930.tif 000113
【図１４】
2008524930.tif 000114
【手続補正書】
【提出日】平成19年11月21日(2007.11.21)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のエレメントが、前記プロパティを所有しているかどうかの認証を、複数の予め定義された期間のそれぞれにおいて提供するコンピュータに実装された認証方法であって、
それぞれの前記エレメントは、予め特定されたプロパティを取得するか失効させるかの少なくとも一方のために動作可能で、１よりも大きい相異なる整数と関連づけられており、
前記期間の各期間ｊ、及び、前記エレメントの集合Ｐ１ｊに対して、前記集合Ｐ１ｊの全ての前記エレメントが前記期間ｊにおいて前記プロパティを所有する、又は、所有しないことを証明する第１のデータＡ１（Ｐ１ｊ）を取得する工程を含み、
前記第１のデータＡ１（Ｐ１ｊ）は、予め定義された合成数ｎを法とする整数ｕのＰｊ乗根
【数１】
2008524930.tif 000115
を表し、Pｊは、前記集合Ｐ１ｊのメンバーに関連づけられた前記整数の積であり、ｕは、一定、又は、前記期間の予め定義された関数であることを特徴とする方法。
【請求項２】
前記エレメントは、（ａ）暗号鍵がエンティティに関連づけられていることを証明するデジタル証明書のそれぞれか、（ｂ）ひとつ以上のリソースを用いるための権利のどちらかであり、前記プロパティは、デジタル証明書、又は、権利の有効性であることを特徴とする請求項１に記載の方法。
【請求項３】
前記認証を連続する期間のそれぞれにおいて提供するように動作可能であり、前記整数ｕは、前記期間の前記関数であることを特徴とする請求項１に記載の方法。
【請求項４】
少なくともひとつの期間ｊに対する前記第１のデータＡ１（Ｐ１ｊ）から、第２のデータＷ１（Ｅ１ｊ）を取得する工程をさらに含み、
前記第２のデータＷ１（Ｅ１ｊ）は、前記エレメントのうちの選択されたエレメントＥ１が、前記期間ｊにおいて前記プロパティを所有することを証明し、
（ａ）ｐＥ１が前記エレメントＥ１に関係づけられた前記整数である、ｎを法とする前記整数ｕのＰＥ１乗根
【数２】
2008524930.tif 000116
か、又は、
（ｂ）ｎを法とする前記整数の（ＰｊＰＥ１）乗根
【数３】
2008524930.tif 000117
のどちらか一方の倍数を表すことを特徴とする請求項１に記載の方法。
【請求項５】
前記第２のデータは、Ｅ１以外のエレメントが前記期間ｊにおいて前記プロパティを所有するかどうかとは無関係であることを特徴とする請求項４に記載の方法。
【請求項６】
前記少なくともひとつの期間ｊに対して、第２のデータＷ１（Ｅ１，ｊ）＊．．．＊Ｗ１（Ｅｋ，ｊ）のｎを法とする積として総計した第２のデータを取得する工程をさらに含み、
それぞれの第２のデータＷ１（Ｅｉ，ｊ）（ｉ＝１，．．．，ｋ）は、前記第１のデータＡ１（Ｐ１）から取得され、
それぞれの第２のデータＷ１（Ｅｉ）は、対応するエレメントＥｉが前記少なくともひとつの期間ｊにおいて前記プロパティを所有することを証明し、
前記総計した第2のデータは、全ての前記エレメントＥ１，．．．，Ｅｋが前記プロパティを所有することを証明することを特徴とする請求項４に記載の方法。
【請求項７】
複数のエレメントに対して、前記プロパティを所有するとして認証を提供するコンピュータに実装された認証方法であって、
それぞれの前記エレメントは、予め特定されたプロパティを取得するか失効させるかの少なくとも一方のために動作可能で、１よりも大きい相異なる整数と関連づけられており、
第１のコンピュータシステムが、前記エレメントのひとつであるエレメントＥ１と関連づけられた整数ｐＥ１を生成する工程と、
前記第１のコンピュータシステムが、予め定義された合成数を法とする基数のＰＥ１乗根を表すデータを取得する工程と、
前記第１のコンピュータシステムが、第２のコンピュータシステムに前記エレメントＥ１が前記予め特定されたプロパティを所有することを証明させるように、前記データを前記第２のコンピュータシステムに提供する工程とを含むことを特徴とする方法。
【請求項８】
前記エレメントは、（ａ）暗号鍵がエンティティに関連づけられていることを証明するデジタル証明書のそれぞれか、又は、（ｂ）ひとつ以上のリソースを用いるための権利のどちらかであり、
前記プロパティは、デジタル証明書、又は、権利の有効性であることを特徴とする請求項７に記載の方法。
【請求項９】
複数のエレメントに対して、前記プロパティを所有するとして認証を提供するコンピュータに実装された認証方法であって、
それぞれの前記エレメントは、予め特定されたプロパティを取得するか失効させるかの少なくとも一方のために動作可能で、１よりも大きい相異なる整数と関連づけられており、
前記エレメントの集合Ｐ１に対して、集合Ｐ１の全ての前記エレメントが前記プロパティを所有する、又は、所有しないことを証明する第１のデータＡ１（Ｐ１）を取得する工程と、
前記集合Ｐ１のうちの２つ以上の空でない真部分集合Ｐ１．１，．．．，Ｐ１．ｋを決定する工程と、
各部分集合Ｐ１．ｉ(ｉ＝１，．．．，ｋ)に対して、Ａ１（Ｐ１）から第１のデータＡ１(Ｐ１．ｉ)を計算する工程と、
少なくともひとつのｉに対して、Ａ１（Ｐ１．ｉ）をコンピュータシステムＣＳ．ｉに対してネットワーク上で送信する工程とを含み、
Ａ１()は、前記エレメントの各集合を、前記集合の各エレメントに基づくデータにマッピングする関数であり、前記集合におけるエレメント数とは無関係なサイズを有し、前記データは、前記集合の全ての前記エレメントが前記プロパティを所有する、又は、所有しないことを証明し、
それぞれの部分集合Ｐ１．ｉは、前記部分集合Ｐ１．ｉの全ての前記エレメントが、前記プロパティを所有する、又は、所有しないことを、Ａ１（Ｐ１．ｉ）を用いて、他の関係者に対して証明することができる少なくともひとつのコンピュータシステムＣＳ．ｉに関連づけられていることを特徴とする方法。
【請求項１０】
前記エレメントは、（ａ）暗号鍵がエンティティに関連づけられていることを証明するデジタル証明書のそれぞれか、（ｂ）ひとつ以上のリソースを用いるための権利のどちらかであり、前記プロパティは、デジタル証明書、又は、権利の有効性であることを特徴とする請求項９に記載の方法。
【請求項１１】
複数の前記部分集合Ｐ１．ｉは、互いに独立しており、
それぞれの集合Ｐ１．ｉ（ｉ＝１，．．．，ｋ）に対して、前記関連づけられた第１のデータＡ１（Ｐ１．ｉ）を前記コンピュータシステムＣＳ．ｉにネットワーク上で送信する工程をさらに含むことを特徴とする請求項９に記載の方法。
【請求項１２】
複数のエレメントに対して、前記プロパティを所有するとして認証を提供するコンピュータに実装された認証方法であって、
それぞれの前記エレメントは、それぞれが予め特定されたプロパティを取得するか失効させるかの少なくとも一方のために動作可能で、１よりも大きい相異なる整数と関連づけられており、
前記集合Ｐ１の全ての前記エレメントが前記プロパティを所有する、又は、所有しないことを証明する第１のデータＡ１（Ｐ１）を取得する工程と、
前記集合Ｐ１のうちの２つ以上の空でない真部分集合Ｐ１．１，．．．，Ｐ１．ｋを決定する工程と、
それぞれの部分集合Ｐ１．ｉ(ｉ＝１，．．．，ｋ)に対して、前記部分集合Ｐ１．ｉにではなく前記集合Ｐ１に属する前記エレメントに関連づけられた整数の積である指数でＰ乗根ｕ１／Ｐ（ｍｏｄ ｎ）をべき乗することによって、第１のデータＡ１(Ｐ１．ｉ)を取得する工程とを含み、
前記第１のデータＡ１（Ｐ１）は、予め定義された合成数ｎを法とする整数ｕのＰ乗根ｕ１／Ｐ（ｍｏｄ ｎ）を表し、Pは、前記集合Ｐ１のメンバーに関連づけられた前記整数の積であり、
Ａ１（）は、前記エレメントの各集合ＳをＰｓ乗根
【数４】
2008524930.tif 000118
を表すデータにマッピングする関数であり、Ｐｓは、前記集合Ｐ１のメンバーと関連づけられた前記整数の積であり、
それぞれの部分集合Ｐ１．ｉは、前記部分集合Ｐ１．ｉの全ての前記エレメントが、前記プロパティを所有する、又は、所有しないことを、Ａ１（Ｐ１．ｉ）を用いて、他の関係者に対して証明することができる少なくともひとつのコンピュータシステムＣＳ．ｉに関連づけられていることを特徴とする方法。
【請求項１３】
前記エレメントは、（ａ）暗号鍵がエンティティに関連づけられていることを証明するデジタル証明書のそれぞれか、（ｂ）ひとつ以上のリソースを用いるための権利のどちらかであり、前記プロパティは、デジタル証明書、又は権利の有効性であることを特徴とする請求項１２に記載の方法。
【請求項１４】
複数のエレメントが予め特定されたプロパティを所有しているかどうかの認証を提供するコンピュータに実装された認証方法であって、
それぞれの前記エレメントは、予め特定された前記プロパティを取得するか失効させるかの少なくとも一方のために動作可能で、前記認証は、連続する複数の期間のそれぞれに提供され、
前記エレメントのひとつであるエレメントＥ１に対する前記期間に対して、前記エレメントＥ１が前記それぞれの期間ｊにおいて前記プロパティを所有することの証明である認証データ片ｃｊ（Ｅ１）を複数生成する工程と、
整数ｐＥ１を前記エレメントＥ１に割り当てる工程と、
前記エレメントＥ１に対する各期間ｊに対して、ｕ（ｊ）がｊによって決まる予め定義された合成数ｎを法とする整数ｕ（ｊ）のｐＥ１乗根ｕ（ｊ）１／ＰＥ１（ｍｏｄ ｎ）から生成された暗号鍵Ｋｊ（Ｅ１）を生成する工程と、
前記それぞれの鍵Ｋｊ（Ｅ１）で各片ｃｊ（Ｅ１）の少なくとも一部分を暗号化する工程とを含むことを特徴とする方法。
【請求項１５】
複数のエレメントが、予め特定されたプロパティを所有しているかどうかの認証を提供するコンピュータに実装された認証方法であって、
それぞれの前記エレメントは、予め特定された前記プロパティを取得するか失効させるかの少なくとも一方のために動作可能で、前記認証は、連続する複数の期間のそれぞれに提供され、
前記複数の連続する期間の各期間ｊに対して、エレメントＥ１が、前記期間ｊにおいて前記プロパティを所有しているとして認証されるかを決定する工程と、
前記エレメントＥ１が、前記期間ｊにおいて前記プロパティを所有するとして認証される場合は、前記エレメントＥ１が前記プロパティを所有するという前記期間ｊにおける証明データｃｊ（Ｅ１）を提供する各コンピュータシステムに対して、ｕ（ｊ）がｊによって決まり、ｐＥ１が前記エレメントＥ１に割り当てられた整数である予め定義された合成数ｎを法とする整数ｕ（ｊ）のｐＥ１乗根ｕ（ｊ）１／ＰＥ１（ｍｏｄ ｎ）から生成され、前記証明データｃｊ（Ｅ１）を少なくとも部分的に復号するための復号鍵ＤＫｊ（Ｅ１）を提供する工程とを含み、
前記エレメントＥ１が、前記期間ｊにおいて前記プロパティを所有するとして認証されない場合、前記復号鍵ＤＫｊ（Ｅ１）を前記コンピュータシステムの少なくともひとつに対して提供しないことを特徴とする方法。
【請求項１６】
複数のエレメントが、予め特定されたプロパティを所有しているかどうかの認証を提供するコンピュータに実装された認証方法であって、
それぞれの前記エレメントは、予め特定されたプロパティを取得するか失効させるかの少なくとも一方のために動作可能であり、前記認証は、連続する複数の期間のそれぞれに提供され、
コンピュータシステムが、前記エレメントのひとつであるエレメントＥ１が連続する期間のひとつである前記期間ｊにおいて前記プロパティを所有することを証明する認証データｃｊ（Ｅ１）を少なくとも部分的に暗号化する、連続する期間に対する複数のデータ片ＥＮｊ（ｃｊ（Ｅ１））を受信する工程と、
各期間ｊに対する前記複数のデータ片ＥＮ（ｃｊ（Ｅ１））を受信した後で、前記エレメントＥ１が、前記期間ｊにおいて前記プロパティを所有するとして認証される場合、
（ａ）前記コンピュータシステムは、ｐＥ１が前記エレメントＥ１と関連づけられた整数である、予め定義された合成数ｎを法とする整数ｕ（ｊ）のｐＥ１乗根ｕ（ｊ）１／ＰＥ１（ｍｏｄ ｎ）から生成される復号鍵ＤＫｊ（Ｅ１）を受信する工程と、
（ｂ）前記コンピュータシステムは、前記データ片ＥＮ（ｃｊ（Ｅ１））を前記鍵ＤＫｊ（Ｅ１）で復号する工程とを含むことを特徴とする方法。
【請求項１７】
請求項１の方法を実行するコンピュータシステムであって、前記第１のデータＡ１（Ｐ１）を生成するコンピュータシステム。
【請求項１８】
前記第１のデータＡ１（Ｐ１）を生成するように、コンピュータシステムを請求項１の方法を実行するようにプログラムされたひとつ以上のコンピュータ命令を備えるコンピュータで読み取り可能な媒体。
【請求項１９】
（削除）
【請求項２０】
請求項４の方法を実行するコンピュータシステムであって、前記第２のデータＷ１（Ｅ１）を生成するコンピュータシステム。
【請求項２１】
請求項４に記載のように、第２のデータＷ１（Ｅ１）を備えるデータキャリア。
【請求項２２】
請求項７の方法を実行するコンピュータシステム。
【請求項２３】
請求項７の方法をコンピュータシステムに実行させるひとつ以上のコンピュータ命令を備えるデータキャリア。
【請求項２４】
請求項９の方法を実行するコンピュータシステム。
【請求項２５】
請求項９の方法をコンピュータシステムに実行させるひとつ以上のコンピュータ命令を備えるコンピュータで読み取り可能な媒体。
【請求項２６】
請求項１２の方法を実行するコンピュータシステム。
【請求項２７】
請求項１２の方法をコンピュータシステムに実行させるひとつ以上のコンピュータ命令を備えるコンピュータで読み取り可能な媒体。
【請求項２８】
請求項１４の方法を実行するコンピュータシステム。
【請求項２９】
請求項１４の方法をコンピュータシステムに実行させるひとつ以上のコンピュータ命令を備えるデータキャリア。
【請求項３０】
請求項１４に記載のように、鍵Ｋｊ（Ｅ１）と、前記鍵Ｋｊ（Ｅ１）のもとでデータ片ｃｊ（Ｅ１）を少なくとも部分的に暗号化することとの少なくとも一方を含むデータキャリア。
【請求項３１】
請求項１５の方法を実行するコンピュータシステム。
【請求項３２】
請求項１５の方法をコンピュータシステムに実行させるひとつ以上のコンピュータ命令を備えるデータキャリア。
【請求項３３】
請求項１５に記載のように、復号鍵ＤＫｊ（Ｅ１）を備えるデータキャリア。
【請求項３４】
請求項１６の方法を実行するコンピュータシステム。
【請求項３５】
請求項１６の方法をコンピュータシステムに実行させるひとつ以上のコンピュータ命令を備えるデータキャリア。
【請求項３６】
前記エレメントに関連づけられた前記整数のそれぞれは、ｎに対して互いに素であり、前記エレメントに関連づけられた残りの整数の最小公倍数を分割しないことを特徴とする請求項１に記載の方法。
【請求項３７】
前記第１のデータＡ１（Ｐ１ｊ）を取得する工程には、前記ルート
【数５】
2008524930.tif 000119
を計算する工程を含み、
前記第１のデータＡ１（Ｐ１ｊ）を、前記集合Ｐ１ｊの前記エレメントに関連づけられたひとつ以上のコンピュータシステムにネットワーク上で送信する工程をさらに含み、
前記ひとつ以上のコンピュータシステムに対して、前記集合Ｐ１ｊのひとつ以上の前記エレメントが、前記プロパティを所有する、又は、所有しないことの証明を提供することを特徴とする請求項３に記載の方法。
【請求項３８】
前記第１のデータＡ１（Ｐ１ｊ）を取得する工程には、前記第１のデータＡ１（Ｐ１ｊ）をネットワーク上で受信する工程を含み、
前記第１のデータＡ１（Ｐ１ｊ）は、前記集合Ｐ１ｊの各エレメントが前記プロパティを所有することを証明し、
前記集合Ｐ１ｊは、２つ以上のエレメントを有し、
前記第２のデータＷ１（Ｅ１ｊ）を取得する工程には、Ｅ１以外のＰ１ｊの前記エレメントに関連づけられた前記整数の積に等しい指数で
【数６】
2008524930.tif 000120
をべき乗して、
【数７】
2008524930.tif 000121
を計算する工程を含むことを特徴とする請求項４に記載の方法。
【請求項３９】
前記第１のデータＡ１（Ｐ１ｊ）は、前記集合Ｐ１ｊの各エレメントが前記プロパティを所有することを証明し、
各エレメントは、前記プロパティを取得するためにではなく、失効させるために動作可能であり、
前記期間の最初の期間以外の少なくとも各期間ｊに対する前記第２のデータＷ１（Ｅ１，ｊ）を取得する工程には、ｊよりも前の期間ｊ１に対する前記第２のデータＷ１（Ｅ１，ｊ１）によって表される値によって、
【数８】
2008524930.tif 000122
を乗じる工程を含むことを特徴とする請求項４に記載の方法。
【請求項４０】
前記整数ｕは、前記期間の前記関数であることを特徴とする請求項３９に記載の方法。
【請求項４１】
ｕ＝H（ｊ）／H（ｊ−１）であり、Ｈ（）は、値（Ｚ／ｎＺ）＊を有する予め定義された関数であることを特徴とする請求項４０に記載の方法。
【請求項４２】
前記期間の最初の期間以外の少なくとも各期間ｊに対して、Ｗ１（Ｅ１，ｊ）は、
（ａ）ｊを含めそれまでの期間に対してｕの全ての値の積のｐＥ１乗根、及び
（ｂ）前記データＷ１（Ｅ１，ｊ）を計算するコンピュータシステムによって、ネットワーク上で受信した値
【数９】
2008524930.tif 000123
におけるｎを法とする積を表し、
ｍは、前記期間とは無関係に予め定義された値であることを特徴とする請求項４１に記載の方法。
【請求項４３】
ｍは、前記エレメントＥ１に関連づけられており、前記エレメントＥ１のアイデンティティの関数であることを特徴とする請求項４２に記載の方法。
【請求項４４】
前記第２のデータＷ１（Ｅ１，ｊ）を取得する工程には、前記エレメントＥ１に関連づけられた第１の関係者によって前記第２のデータＷ１（Ｅ１，ｊ）を生成する工程を含み、
ｍは、前記エレメントＥ１と無関係な値であり、
前記第１の関係者は、前記第１の関係者が前記エレメントの少なくともひとつに関係づけられていることを、第２の関係者に対して、匿名で証明することを含み、
匿名で証明することには、前記第１の関係者が、ｎを法とするβ乗根ｈｊ１／βを前記第１の関係者が所有する証明を前記第２の関係者に送信することを含み、
ｈｊは、前記期間ｊの関数で前記第２の関係者に公知であり、
βは、前記第１の関係者によって前記第２の関係者に提供された整数ではなく、前記第２の関係者に公知である予め定義された間隔に属し、前記エレメントに関連づけられた前記整数の全てを含むことを特徴とする請求項４２に記載の方法。
【請求項４５】
前記エレメントが前記期間ｊにおいて前記プロパティを所有する、又は、所有しないことを他の関係者に証明する工程をさらに含み、
前記証明する工程には、
メッセージＭを生成する工程と、
前記第２のデータＷ１（Ｅ１，ｊ）によって表される前記値を含む署名鍵で前記メッセージＭ上の署名を計算する工程と、
前記署名を前記他の関係者に送信する工程とが含まれ、
前記署名は、前記エレメントＥ１の識別及び前記期間ｊの識別から計算可能な値Ｊを有することにより証明可能であることを特徴とする請求項４に記載の方法。
【請求項４６】
前記エレメントが前記期間ｊにおいて前記プロパティを所有する、又は、所有しないことを他の関係者に証明する工程をさらに含み、
前記証明する工程には、ランダムメッセージＭ及び、ランダム整数ｒを生成する工程と、
【数１０】
2008524930.tif 000124
を計算する工程と、
Ｍ、
【数１１】
2008524930.tif 000125
、及び、Ｄを前記他の関係者に送信することが含まれる、方法であって、
ｓＳ１ｊは、前記第２のデータＷ１（Ｅ１，ｊ）によって表される値であり、Ｈ（）は、予め定義された関数であることを特徴とする請求項４に記載の方法。
【請求項４７】
少なくともひとつの前記期間ｊに対して、前記第１のデータＡ１（Ｐ１，ｊ）から第２のデータＷ１（Ｓ１，ｊ）を取得する工程をさらに含み、
Ｓ１は、Ｐ１ｊの部分集合であり、
前記第２のデータＷ１（Ｓ１，ｊ）は、前記部分集合Ｓ１の各エレメントが前記期間ｊにおいて前記プロパティを所有することを証明し、
前記第２のデータは、ｎを法とする前記整数ｕのｐＳ１乗根
【数１２】
2008524930.tif 000126
の倍数を表し、
ｐＳ１が、前記部分集合Ｓ１の前記エレメントに関連づけられた前記整数の積であることを特徴とする請求項１に記載の方法。
【請求項４８】
前記部分集合Ｓ１は、ひとつ以上の前記エレメントからなる予め定義された部分集合Ｓ２の部分集合であり、Ｓ１＝Ｓ２∩Ｐ１ｊであり、
Ｓ１は、前記データＡ１（Ｐ１ｊ）が前記プロパティを所有するか所有しないかを証明するＳ２の全ての前記エレメントの集合であることを特徴とする請求項４７に記載の方法。
【請求項４９】
前記部分集合Ｓ２は、ユーザに関連づけられており、それぞれが前記ユーザの権利である複数のエレメントからなり、
前記集合Ｐ１ｊは、前記部分集合の有効な権利のみ、又は、無効な権利のみを含むことを特徴とする請求項４８に記載の方法。
【請求項５０】
前記整数ｕは、前記期間の前記関数であることを特徴とする請求項４８に記載の方法。
【請求項５１】
前記期間の前記最初の期間に対して、Ｗ１（Ｓ１，ｊ）は、
（ａ）ｊを含めそれまでの期間に対するｕの全ての値の積のｐＳ１乗根、及び
（ｂ）前記データＷ１（Ｓ１，ｊ）を計算するコンピュータシステムによってネットワーク上で受信した値
【数１３】
2008524930.tif 000127
をべき乗して求めた値
【数１４】
2008524930.tif 000128
、におけるｎを法とする積を表し、
ｐＳ２は、前記部分集合Ｓ２の前記エレメントに関連づけられた前記整数の積であり、
ｍは、前記期間とは無関係な予め定義された値であることを特徴とする請求項５０に記載の方法。
【請求項５２】
ｍは、前記部分集合Ｓ２に関連づけられた関係者に関係づけられていることを特徴とする請求項５１に記載の方法。
【請求項５３】
前記第２のデータＷ１（Ｓ１，ｊ）を取得する工程には、前記部分集合Ｓ２に関連づけられた第１の関係者によって前記第２のデータＷ１（Ｓ１，ｊ）を生成する工程を含み、
ｍは、前記部分集合Ｓ２と無関係な値であり、
前記第１の関係者は、前記第１の関係者がＳ１のメンバーであるエレメントＥ１に関連づけられていることを、第２の関係者に対して、匿名で証明することを含み、
匿名で証明することには、前記第１の関係者が、ｎを法とするβ乗根α１／βを前記第１の関係者が所有する証明を前記第２の関係者に送信することを含み、
αとβは、前記第２の関係者には知られていない整数であるが、
（ａ）βは、前記第２の関係者に公知である予め定義された間隔に属し、前記エレメントに関連づけられた複数の整数を含むか、又は
（ｂ）βは、それぞれが、前記第２の関係者には知られていない整数であるが、前記第２の関係者に公知であるそれぞれの間隔に属している整数の積であり、前記エレメントに関連づけられた複数の整数を含むかのどちらかであることを特徴とする請求項５１に記載の方法。
【請求項５４】
Ｐ１ｊの前記エレメントは、前記プロパティを所有せず、
前記第１のデータＡ１（Ｐ１ｊ）を取得する工程には、前記第１のデータをコンピュータシステムによってネットワーク上で受信する工程を含み、
前記コンピュータシステムは、少なくともひとつの前記期間ｊに対して、前記第１のデータＡ１（Ｐ１ｊ）から第２のデータＷ１（Ｅ１，ｊ）を取得する工程を含み、
前記第２のデータＷ１（Ｅ１，ｊ）は、前記エレメントの選択されたエレメントＥ１が前記期間ｊにおいて前記プロパティを所有することを証明し、
前記第２のデータは、
【数１５】
2008524930.tif 000129
であり、ＰＥ１が、前記エレメントＥ１に関連づけられている前記整数であり、ｐＥ１乗根
【数１６】
2008524930.tif 000130
の倍数を表すことを特徴とする請求項１に記載の方法。
【請求項５５】
ｕは、前記一定値であることを特徴とする請求項５４に記載の方法。
【請求項５６】
前記第１のデータＡ１（Ｐ１ｊ）は、前記集合Ｐ１ｊの各エレメントが前記プロパティを所有しないことを証明し、
各エレメントは、前記プロパティを取得するためではなく、失効させるために動作可能であり、
少なくともひとつの前記期間ｊに対して、前記第２のデータＷ１（Ｅ１，ｊ）を取得する工程には、ｊよりも前の期間に対する前記第２のデータによって表される前記値のＲｊ乗根を計算する工程を含み、
Ｒｊは、ｊよりも前の前記期間の後で前記プロパティを失効させた前記エレメントに関連づけられた前記整数の積であることを特徴とする請求項５４に記載の方法。
【請求項５７】
前記期間の前記最初の期間以外の少なくとも各期間ｊに対して、Ｗ１（Ｅ１，ｊ）は、
【数１７】
2008524930.tif 000131
及び、
前記データＷ１（Ｅ１，ｊ）を計算するコンピュータシステムによってネットワーク上で受信した値
【数１８】
2008524930.tif 000132
、におけるｎを法とする積を表し、
ｊ１は、ｊよりも前の期間であり、ｍは、前記期間とは無関係な予め定義された値であることを特徴とする請求項５４に記載の方法。
【請求項５８】
前記集合Ｐ１の各エレメントは、前記エレメントが前記プロパティを所有する、又は、所有しないことを他の関係者に対して証明することが可能となるコンピュータシステムに関連づけられており、
前記部分集合Ｐ１．１，．．．，Ｐ１．ｋを決定する工程には、
前記集合Ｐ１のひとつ以上の前記エレメントに関連づけられている、ひとつ以上の前記コンピュータシステムを含むトポロジー領域ＡＲ．１，．．．，ＡＲ．ｋのそれぞれを決定する工程と、
各ｉ＝１，．．．，ｋに対して、前記トポロジー領域ＡＲ．ｉにおいて少なくともひとつのコンピュータシステムに関連づけられている前記集合Ｐ１の全ての前記エレメントの前記集合として前記部分集合Ｐ１．ｉを決定する工程とを含むことを特徴とする請求項９に記載の方法。
【請求項５９】
前記集合Ｐ１の各エレメントは、前記エレメントが前記プロパティを所有する、又は、所有しないことを他の関係者に対して証明することが可能となるコンピュータシステムに関連づけられており、
前記部分集合Ｐ１．１，．．．，Ｐ１．ｋを決定する工程には、
前記集合Ｐ１のひとつ以上の前記エレメントに関連づけられている、ひとつ以上の前記コンピュータシステムを含むトポロジー領域ＡＲ．１，．．．，ＡＲ．ｋのそれぞれを決定する工程と、
各ｉ＝１，．．．，ｋに対して、前記トポロジー領域ＡＲ．ｉにおいて少なくともひとつのコンピュータシステムに関連づけられている前記集合Ｐ１の全ての前記エレメントの前記集合として前記部分集合Ｐ１．ｉを決定する工程とを含むことを特徴とする請求項１２に記載の方法。
【請求項６０】
前記部分集合Ｐ１．ｉが独立しており、
それぞれの集合Ｐ１．ｉ（ｉ＝１，．．．，ｋ）に対して関連づけられた第１のデータＡ１（Ｐ１．ｉ）を前記コンピュータシステムＣＳ．ｉに対して、ネットワーク上で送信する工程をさらに含むことを特徴とする請求項５９に記載の方法。
【請求項６１】
複数のエレメントが、前記プロパティを所有しているかどうかの認証を提供するコンピュータに実装された認証方法であって、
それぞれの前記エレメントは、予め特定されたプロパティを取得するか失効させるかの少なくとも一方のために動作可能で、１よりも大きい相異なる整数と関連づけられており、
集合Ｐ１における各エレメントが前記プロパティを所有する、又は、所有しないように２つ以上の前記エレメントの前記集合Ｐ１を選択する工程と、
予め定義された合成数ｎを法とする整数ｕのＰ乗根ｕ１／Ｐ(ｍｏｄ ｎ)を計算する工程と、
前記Ｐ乗根を、前記集合Ｐ１の各エレメントが前記プロパティを所有する、又は、所有しないことの証明として、ひとつ以上のコンピュータシステムに対してネットワーク上で送信する工程とを含み、
Ｐは、前記集合Ｐ１の前記エレメントに関連づけられた前記整数の積であることを特徴とする方法。
【請求項６２】
前記エレメントは、
（ａ）暗号鍵がエンティティに関連づけられていることを証明するデジタル証明書か、又は
（ｂ）ひとつ以上のリソースを用いるための権利のどちらかであり、
前記プロパティのそれぞれは、デジタル証明書、又は、権利の有効性であることを特徴とする請求項6１に記載の方法。
【請求項６３】
エレメントに関連づけられた前記整数のそれぞれは、ｎに対して互いに素であり、前記エレメントに関係づけられた残りの整数の最小公倍数を分割しないことを特徴とする請求項６１に記載の方法。
【請求項６４】
複数のエレメントが、前記プロパティを所有しているかどうかの認証を提供するコンピュータに実装された認証方法であって、
それぞれの前記エレメントは、予め特定されたプロパティを取得するか失効させるかの少なくとも一方のために動作可能で、１よりも大きい相異なる整数と関連づけられており、
予め定義された合成数ｎを法とする整数ｕのＰ乗根ｕ１／Ｐ(ｍｏｄ ｎ)をネットワーク上で受信する工程と、
前記Ｐ乗根を、前記集合Ｐ１の前記エレメントの全てよりも少ないひとつ以上のエレメントを含む部分集合のエレメントに関連づけられた前記整数の積に等しい指数で、べき乗する工程と、
前記部分集合ではなく、前記集合Ｐ１における各エレメントが前記プロパティを所有する、又は、所有しないことを証明するために前記累乗演算の結果を用いる工程とを含み、
Ｐは、２つ以上の前記エレメントを含む前記集合Ｐ１のエレメントに関連づけられた前記整数の積であることを特徴とする方法。
【請求項６５】
前記エレメントは、
（ａ）暗号鍵がエンティティに関連づけられていることを証明するデジタル証明書か、又は
（ｂ）ひとつ以上のリソースを用いるための権利のどちらかであり、
前記プロパティのそれぞれは、デジタル証明書、又は、権利の有効性であることを特徴とする請求項６４に記載の方法。
【請求項６６】
エレメントに関連づけられた前記整数のそれぞれは、ｎに対して互いに素であり、前記エレメントに関係づけられた残りの整数の最小公倍数を分割しないことを特徴とする請求項６４に記載の方法。
【請求項６７】
エレメントＥ１が、複数の予め定義された期間のうちのひとつである期間ｊにおいて予め特定されたプロパティを所有することを検証するコンピュータに実装された方法であって、
値Ｍ、Ｒ、Ｄをネットワーク上で受信する工程と、
【数１９】
2008524930.tif 000133
を検証する工程とを含み、
ｎは、予め定義された合成数であり、
【数２０】
2008524930.tif 000134
、ｄ＝Ｈ（Ｍ｜｜Ｒ）であり、
ｐＥ１は、各エレメントが相異なる整数に関連づけられているシステムにおいて前記エレメントＥ１に関連づけられた整数であり、
ｓＥ１ｊは、前記エレメントＥ１及び、前記期間ｊに関連づけられた値であり、
Ｈ（）は、予め定義された関数であり、
前記検証する工程において、前記値ｒ及びｓＥ１ｊは、用いず、
前記検証する工程には、
ｎを法とするＪ＝ｍＥ１−１を計算する工程と、
【数２１】
2008524930.tif 000135
を確認する工程とを含み、
ｍＥ１は、前記エレメントＥ１に関連づけられているが、前記期間とは無関係な予め定義された値であり、
【数２２】
2008524930.tif 000136
であり、Ｈ（ｊ）は、
【数２３】
2008524930.tif 000137
となるようなjの予め定義された関数であることを特徴とする方法。
【請求項６８】
エレメントＥ１が、複数の予め定義された期間のうちのひとつである期間ｊにおいて予め特定されたプロパティを所有することを検証するコンピュータに実装された方法であって、
値Ｍ、Ｒ、Ｄをネットワーク上で受信する工程と、
【数２４】
2008524930.tif 000138
を検証する工程とを含み、
ｎは、予め定義された合成数であり、
【数２５】
2008524930.tif 000139
、ｄ＝Ｈ（Ｍ｜｜Ｒ）であり、
ｐＥ１は、各エレメントが相異なる整数に関連づけられているシステムにおいて前記エレメントＥ１に関連づけられた整数であり、
Ｈ（）は、予め定義された関数であり、
【数２６】
2008524930.tif 000140
であり、
ｍＥ１は、前記エレメントＥ１に関連づけられているが、前記期間とは無関係な予め定義された整数であり、
【数２７】
2008524930.tif 000141
であり、
ｕは、予め定義された一定値であり、
Ｐｊは、前記期間ｊによって前記プロパティを所有しないエレメントに関連づけられた整数の積であり、
前記検証する工程において、前記値ｒ及びｗＥ１ｊは、用いず、
前記検証する工程には、
ｎを法とするＪ＝ｍＥ１−１を計算する工程と、
【数２８】
2008524930.tif 000142
として、
【数２９】
2008524930.tif 000143
を確認する工程とが含まれることを特徴とする方法。
【請求項６９】
前記第１のデータＡ１（Ｐ１）を生成するために請求項１の方法を実行するコンピュータプログラムをネットワーク上で送信する工程を含むネットワーク送信方法。
【請求項７０】
請求項１に記載したように、第１のデータＡ１（Ｐ１）をネットワーク上で送信する工程を含むネットワーク送信方法。
【請求項７１】
請求項４に記載したように、第２のデータＷ１（Ｅ１）をネットワーク上で送信する工程を含むネットワーク送信方法。
【請求項７２】
請求項９の方法を実行するコンピュータプログラムをネットワーク上で送信する工程を含むネットワーク送信方法。
【請求項７３】
請求項１２の方法を実行するコンピュータシステム。
【請求項７４】
コンピュータシステムを、請求項１２の方法を実行するようにプログラムするひとつ以上のコンピュータ命令を備えるコンピュータ可読媒体。
【請求項７５】
請求項１２の方法を実行するコンピュータプログラムをネットワーク上で送信する工程を含むネットワーク送信方法。
【請求項７６】
請求項６１の方法を実行するコンピュータシステム。
【請求項７７】
コンピュータシステムを、請求項６１の方法を実行するようにプログラムするひとつ以上のコンピュータ命令を備えるコンピュータ可読媒体。
【請求項７８】
請求項６１の方法を実行するコンピュータプログラムをネットワーク上で送信する工程を含むネットワーク送信方法。
【請求項７９】
請求項６４の方法を実行するコンピュータシステム。
【請求項８０】
コンピュータシステムを、請求項６４の方法を実行するようにプログラムするひとつ以上のコンピュータ命令を備えるコンピュータ可読媒体。
【請求項８１】
請求項６４の方法を実行するコンピュータプログラムをネットワーク上で送信する工程を含むネットワーク送信方法。
【請求項８２】
請求項６７の方法を実行するコンピュータシステム。
【請求項８３】
コンピュータシステムを、請求項６７の方法を実行するようにプログラムするひとつ以上のコンピュータ命令を備えるコンピュータで読み取り可能な媒体。
【請求項８４】
請求項６７の方法を実行するコンピュータプログラムをネットワーク上で送信する工程を含むネットワーク送信方法。
【請求項８５】
請求項６８の方法を実行するコンピュータシステム。
【請求項８６】
コンピュータシステムを、請求項６８の方法を実行するようにプログラムするひとつ以上のコンピュータ命令を備えるコンピュータ可読媒体。
【請求項８７】
請求項６８の方法を実行するコンピュータプログラムをネットワーク上で送信する工程を含むネットワーク送信方法。
【手続補正書】
【提出日】平成20年3月12日(2008.3.12)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のエレメントが、前記プロパティを所有しているかどうかの認証を、複数の予め定義された期間のそれぞれにおいて提供するコンピュータに実装された認証方法であって、
それぞれの前記エレメントは、予め特定されたプロパティを取得するか失効させるかの少なくとも一方のために動作可能で、１よりも大きい相異なる整数と関連づけられており、
前記期間の各期間ｊ、及び、前記エレメントの集合Ｐ１ｊに対して、前記集合Ｐ１ｊの全ての前記エレメントが前記期間ｊにおいて前記プロパティを所有する、又は、所有しないことを証明する第１のデータＡ１（Ｐ１ｊ）を取得する工程を含み、
前記第１のデータＡ１（Ｐ１ｊ）は、予め定義された合成数ｎを法とする整数ｕのＰｊ乗根
【数１】
2008524930.tif 000144
を表し、Pｊは、前記集合Ｐ１ｊのメンバーに関連づけられた前記整数の積であり、ｕは、一定、又は、前記期間の予め定義された関数であることを特徴とする方法。
【請求項２】
前記認証を連続する期間のそれぞれにおいて提供するように動作可能であり、前記整数ｕは、前記期間の前記関数であることを特徴とする請求項１に記載の方法。
【請求項３】
前記第１のデータＡ１（Ｐ１ｊ）を取得する工程には、前記ルート
【数２】
2008524930.tif 000145
を計算する工程を含み、
前記第１のデータＡ１（Ｐ１ｊ）を、前記集合Ｐ１ｊの前記エレメントに関連づけられた1つ以上のコンピュータシステムにネットワーク上で送信する工程をさらに含み、
前記1つ以上のコンピュータシステムに対して、前記集合Ｐ１ｊの1つ以上の前記エレメントが、前記プロパティを所有する、又は、所有しないことの証明を提供することを特徴とする請求項２に記載の方法。
【請求項４】
少なくとも1つの期間ｊに対する前記第１のデータＡ１（Ｐ１ｊ）から、第２のデータＷ１（Ｅ１ｊ）を取得する工程をさらに含み、
前記第２のデータＷ１（Ｅ１ｊ）は、前記エレメントのうちの選択されたエレメントＥ１が、前記期間ｊにおいて前記プロパティを所有することを証明し、
（ａ）ｐＥ１が前記エレメントＥ１に関係づけられた前記整数である、ｎを法とする前記整数ｕのＰＥ１乗根
【数３】
2008524930.tif 000146
か、又は、
（ｂ）ｎを法とする前記整数の（ＰｊＰＥ１）乗根
【数４】
2008524930.tif 000147
のどちらか一方の倍数を表すことを特徴とする請求項１に記載の方法。
【請求項５】
前記第２のデータは、Ｅ１以外のエレメントが前記期間ｊにおいて前記プロパティを所有するかどうかとは無関係であることを特徴とする請求項４に記載の方法。
【請求項６】
前記少なくとも1つの期間ｊに対して、第２のデータＷ１（Ｅ１，ｊ）＊．．．＊Ｗ１（Ｅｋ，ｊ）のｎを法とする積として総計した第２のデータを取得する工程をさらに含み、
それぞれの第２のデータＷ１（Ｅｉ，ｊ）（ｉ＝１，．．．，ｋ）は、前記第１のデータＡ１（Ｐ１）から取得され、
それぞれの第２のデータＷ１（Ｅｉ）は、対応するエレメントＥｉが前記少なくとも1つの期間ｊにおいて前記プロパティを所有することを証明し、
前記総計した第2のデータは、全ての前記エレメントＥ１，．．．，Ｅｋが前記プロパティを所有することを証明することを特徴とする請求項４に記載の方法。
【請求項７】
請求項４の方法を実行するコンピュータシステムであって、前記第２のデータＷ１（Ｅ１）を生成するコンピュータシステム。
【請求項８】
前記第１のデータＡ１（Ｐ１ｊ）を取得する工程には、前記第１のデータＡ１（Ｐ１ｊ）をネットワーク上で受信する工程を含み、
前記第１のデータＡ１（Ｐ１ｊ）は、前記集合Ｐ１ｊの各エレメントが前記プロパティを所有することを証明し、
前記集合Ｐ１ｊは、２つ以上のエレメントを有し、
前記第２のデータＷ１（Ｅ１ｊ）を取得する工程には、Ｅ１以外のＰ１ｊの前記エレメントに関連づけられた前記整数の積に等しい指数で
【数５】
2008524930.tif 000148
をべき乗して、
【数６】
2008524930.tif 000149
を計算する工程を含むことを特徴とする請求項４に記載の方法。
【請求項９】
前記第１のデータＡ１（Ｐ１ｊ）は、前記集合Ｐ１ｊの各エレメントが前記プロパティを所有することを証明し、
各エレメントは、前記プロパティを取得するためにではなく、失効させるために動作可能であり、
前記期間の最初の期間以外の少なくとも各期間ｊに対する前記第２のデータＷ１（Ｅ１，ｊ）を取得する工程には、ｊよりも前の期間ｊ１に対する前記第２のデータＷ１（Ｅ１，ｊ１）によって表される値によって、
【数７】
2008524930.tif 000150
を乗じる工程を含むことを特徴とする請求項４に記載の方法。
【請求項１０】
前記整数ｕは、前記期間の前記関数であることを特徴とする請求項９に記載の方法。
【請求項１１】
ｕ＝H（ｊ）／H（ｊ−１）であり、Ｈ（）は、値（Ｚ／ｎＺ）＊を有する予め定義された関数であることを特徴とする請求項１０に記載の方法。
【請求項１２】
前記期間の最初の期間以外の少なくとも各期間ｊに対して、Ｗ１（Ｅ１，ｊ）は、
（ａ）ｊを含めそれまでの期間に対してｕの全ての値の積のｐＥ１乗根、及び
（ｂ）前記データＷ１（Ｅ１，ｊ）を計算するコンピュータシステムによって、ネットワーク上で受信した値
【数８】
2008524930.tif 000151
におけるｎを法とする積を表し、
ｍは、前記期間とは無関係に予め定義された値であることを特徴とする請求項１１に記載の方法。
【請求項１３】
ｍは、前記エレメントＥ１に関連づけられており、前記エレメントＥ１のアイデンティティの関数であることを特徴とする請求項１２に記載の方法。
【請求項１４】
前記第２のデータＷ１（Ｅ１，ｊ）を取得する工程には、前記エレメントＥ１に関連づけられた第１の関係者によって前記第２のデータＷ１（Ｅ１，ｊ）を生成する工程を含み、
ｍは、前記エレメントＥ１と無関係な値であり、
前記第１の関係者は、前記第１の関係者が前記エレメントの少なくとも1つに関係づけられていることを、第２の関係者に対して、匿名で証明することを含み、
匿名で証明することには、前記第１の関係者が、ｎを法とするβ乗根ｈｊ１／βを前記第１の関係者が所有する証明を前記第２の関係者に送信することを含み、
ｈｊは、前記期間ｊの関数で前記第２の関係者に公知であり、
βは、前記第１の関係者によって前記第２の関係者に提供された整数ではなく、前記第２の関係者に公知である予め定義された間隔に属し、前記エレメントに関連づけられた前記整数の全てを含むことを特徴とする請求項１２に記載の方法。
【請求項１５】
前記エレメントが前記期間ｊにおいて前記プロパティを所有する、又は、所有しないことを他の関係者に証明する工程をさらに含み、
前記証明する工程には、
メッセージＭを生成する工程と、
前記第２のデータＷ１（Ｅ１，ｊ）によって表される前記値を含む署名鍵で前記メッセージＭ上の署名を計算する工程と、
前記署名を前記他の関係者に送信する工程とが含まれ、
前記署名は、前記エレメントＥ１の識別及び前記期間ｊの識別から計算可能な値Ｊを有することにより証明可能であることを特徴とする請求項４に記載の方法。
【請求項１６】
前記エレメントが前記期間ｊにおいて前記プロパティを所有する、又は、所有しないことを他の関係者に証明する工程をさらに含み、
前記証明する工程には、ランダムメッセージＭ及び、ランダム整数ｒを生成する工程と、
【数９】
2008524930.tif 000152
を計算する工程と、
Ｍ、
【数１０】
2008524930.tif 000153
、及び、Ｄを前記他の関係者に送信することが含まれる、方法であって、
ｓＳ１ｊは、前記第２のデータＷ１（Ｅ１，ｊ）によって表される値であり、Ｈ（）は、予め定義された関数であることを特徴とする請求項４に記載の方法。
【請求項１７】
請求項４に記載したように、第２のデータＷ１（Ｅ１）をコンピュータシステムによってネットワーク上で送信する工程を含むネットワーク送信方法。
【請求項１８】
コンピュータ命令を実行するための1つ以上のコンピュータ演算処理装置及び、請求項１の方法を実行するための1つ以上のコンピュータ命令を備えるコンピュータ記憶装置を備えるコンピュータシステムであって、
前記1つ以上のコンピュータ命令は、前記第１のデータＡ１（Ｐ１）を生成する1つ以上の命令を備えるコンピュータシステム。
【請求項１９】
前記第１のデータＡ１（Ｐ１）を生成するように、コンピュータシステムを請求項１の方法を実行するようにプログラムされた1つ以上のコンピュータ命令を備えるコンピュータ可読記憶媒体。
【請求項２０】
少なくとも1つの前記期間ｊに対して、前記第１のデータＡ１（Ｐ１，ｊ）から第２のデータＷ１（Ｓ１，ｊ）を取得する工程をさらに含み、
Ｓ１は、Ｐ１ｊの部分集合であり、
前記第２のデータＷ１（Ｓ１，ｊ）は、前記部分集合Ｓ１の各エレメントが前記期間ｊにおいて前記プロパティを所有することを証明し、
前記第２のデータは、ｎを法とする前記整数ｕのｐＳ１乗根
【数１１】
2008524930.tif 000154
の倍数を表し、
ｐＳ１が、前記部分集合Ｓ１の前記エレメントに関連づけられた前記整数の積であることを特徴とする請求項１に記載の方法。
【請求項２１】
前記部分集合Ｓ１は、1つ以上の前記エレメントからなる予め定義された部分集合Ｓ２の部分集合であり、Ｓ１＝Ｓ２∩Ｐ１ｊであり、
Ｓ１は、前記データＡ１（Ｐ１ｊ）が前記プロパティを所有するか所有しないかを証明するＳ２の全ての前記エレメントの集合であることを特徴とする請求項２０に記載の方法。
【請求項２２】
前記部分集合Ｓ２は、ユーザに関連づけられており、それぞれが前記ユーザの権利である複数のエレメントからなり、
前記集合Ｐ１ｊは、前記部分集合の有効な権利のみ、又は、無効な権利のみを含むことを特徴とする請求項２１に記載の方法。
【請求項２３】
前記整数ｕは、前記期間の前記関数であることを特徴とする請求項２１に記載の方法。
【請求項２４】
前記期間の前記最初の期間に対して、Ｗ１（Ｓ１，ｊ）は、
（ａ）ｊを含めそれまでの期間に対するｕの全ての値の積のｐＳ１乗根、及び
（ｂ）前記データＷ１（Ｓ１，ｊ）を計算するコンピュータシステムによってネットワーク上で受信した値
【数１２】
2008524930.tif 000155
をべき乗して求めた値
【数１３】
2008524930.tif 000156
、におけるｎを法とする積を表し、
ｐＳ２は、前記部分集合Ｓ２の前記エレメントに関連づけられた前記整数の積であり、
ｍは、前記期間とは無関係な予め定義された値であることを特徴とする請求項２３に記載の方法。
【請求項２５】
ｍは、前記部分集合Ｓ２に関連づけられた関係者に関係づけられていることを特徴とする請求項２４に記載の方法。
【請求項２６】
前記第２のデータＷ１（Ｓ１，ｊ）を取得する工程には、前記部分集合Ｓ２に関連づけられた第１の関係者によって前記第２のデータＷ１（Ｓ１，ｊ）を生成する工程を含み、
ｍは、前記部分集合Ｓ２と無関係な値であり、
前記第１の関係者は、前記第１の関係者がＳ１のメンバーであるエレメントＥ１に関連づけられていることを、第２の関係者に対して、匿名で証明することを含み、
匿名で証明することには、前記第１の関係者が、ｎを法とするβ乗根α１／βを前記第１の関係者が所有する証明を前記第２の関係者に送信することを含み、
αとβは、前記第２の関係者には知られていない整数であるが、
（ａ）βは、前記第２の関係者に公知である予め定義された間隔に属し、前記エレメントに関連づけられた複数の整数を含むか、又は
（ｂ）βは、それぞれが、前記第２の関係者には知られていない整数であるが、前記第２の関係者に公知であるそれぞれの間隔に属している整数の積であり、前記エレメントに関連づけられた複数の整数を含むかのどちらかであることを特徴とする請求項２４に記載の方法。
【請求項２７】
Ｐ１ｊの前記エレメントは、前記プロパティを所有せず、
前記第１のデータＡ１（Ｐ１ｊ）を取得する工程には、前記第１のデータをコンピュータシステムによってネットワーク上で受信する工程を含み、
前記コンピュータシステムは、少なくとも1つの前記期間ｊに対して、前記第１のデータＡ１（Ｐ１ｊ）から第２のデータＷ１（Ｅ１，ｊ）を取得する工程を含み、
前記第２のデータＷ１（Ｅ１，ｊ）は、前記エレメントの選択されたエレメントＥ１が前記期間ｊにおいて前記プロパティを所有することを証明し、
前記第２のデータは、
【数１４】
2008524930.tif 000157
であり、ＰＥ１が、前記エレメントＥ１に関連づけられている前記整数であり、ｐＥ１乗根
【数１５】
2008524930.tif 000158
の倍数を表すことを特徴とする請求項１に記載の方法。
【請求項２８】
ｕは、前記一定値であることを特徴とする請求項２７に記載の方法。
【請求項２９】
前記第１のデータＡ１（Ｐ１ｊ）は、前記集合Ｐ１ｊの各エレメントが前記プロパティを所有しないことを証明し、
各エレメントは、前記プロパティを取得するためではなく、失効させるために動作可能であり、
少なくとも1つの前記期間ｊに対して、前記第２のデータＷ１（Ｅ１，ｊ）を取得する工程には、ｊよりも前の期間に対する前記第２のデータによって表される前記値のＲｊ乗根を計算する工程を含み、
Ｒｊは、ｊよりも前の前記期間の後で前記プロパティを失効させた前記エレメントに関連づけられた前記整数の積であることを特徴とする請求項２７に記載の方法。
【請求項３０】
前記期間の前記最初の期間以外の少なくとも各期間ｊに対して、Ｗ１（Ｅ１，ｊ）は、
【数１６】
2008524930.tif 000159
及び、
前記データＷ１（Ｅ１，ｊ）を計算するコンピュータシステムによってネットワーク上で受信した値
【数１７】
2008524930.tif 000160
、におけるｎを法とする積を表し、
ｊ１は、ｊよりも前の期間であり、ｍは、前記期間とは無関係な予め定義された値であることを特徴とする請求項２７に記載の方法。
【請求項３１】
前記第１のデータＡ１（Ｐ１）を生成するために請求項１の方法を実行するコンピュータプログラムをコンピュータシステムによってネットワーク上で送信する工程を含むネットワーク送信方法。
【請求項３２】
請求項１に記載したように、第１のデータＡ１（Ｐ１）をコンピュータシステムによってネットワーク上で送信する工程を含むネットワーク送信方法。
【請求項３３】
複数のエレメントに対して、前記プロパティを所有するとして認証を提供するコンピュータに実装された認証方法であって、
それぞれの前記エレメントは、予め特定されたプロパティを取得するか失効させるかの少なくとも一方のために動作可能で、１よりも大きい相異なる整数と関連づけられており、
前記エレメントの集合Ｐ１に対して、集合Ｐ１の全ての前記エレメントが前記プロパティを所有する、又は、所有しないことを証明する第１のデータＡ１（Ｐ１）を取得する工程と、
前記集合Ｐ１のうちの２つ以上の空でない真部分集合Ｐ１．１，．．．，Ｐ１．ｋを決定する工程と、
各部分集合Ｐ１．ｉ(ｉ＝１，．．．，ｋ)に対して、Ａ１（Ｐ１）から第１のデータＡ１(Ｐ１．ｉ)を計算する工程と、
少なくとも1つのｉに対して、Ａ１（Ｐ１．ｉ）をコンピュータシステムＣＳ．ｉに対してネットワーク上で送信する工程とを含み、
Ａ１()は、前記エレメントの各集合を、前記集合の各エレメントに基づくデータにマッピングする関数であり、前記集合におけるエレメント数とは無関係なサイズを有し、前記データは、前記集合の全ての前記エレメントが前記プロパティを所有する、又は、所有しないことを証明し、
それぞれの部分集合Ｐ１．ｉは、前記部分集合Ｐ１．ｉの全ての前記エレメントが、前記プロパティを所有する、又は、所有しないことを、Ａ１（Ｐ１．ｉ）を用いて、他の関係者に対して証明することができる少なくとも1つのコンピュータシステムＣＳ．ｉに関連づけられていることを特徴とする方法。
【請求項３４】
複数の前記部分集合Ｐ１．ｉは、互いに独立しており、
それぞれの集合Ｐ１．ｉ（ｉ＝１，．．．，ｋ）に対して、前記関連づけられた第１のデータＡ１（Ｐ１．ｉ）を前記コンピュータシステムＣＳ．ｉにネットワーク上で送信する工程をさらに含むことを特徴とする請求項３３に記載の方法。
【請求項３５】
前記集合Ｐ１の各エレメントは、前記エレメントが前記プロパティを所有する、又は、所有しないことを他の関係者に対して証明することが可能となるコンピュータシステムに関連づけられており、
前記部分集合Ｐ１．１，．．．，Ｐ１．ｋを決定する工程には、
前記集合Ｐ１の1つ以上の前記エレメントに関連づけられている、1つ以上の前記コンピュータシステムを含むトポロジー領域ＡＲ．１，．．．，ＡＲ．ｋのそれぞれを決定する工程と、
各ｉ＝１，．．．，ｋに対して、前記トポロジー領域ＡＲ．ｉにおいて少なくとも1つのコンピュータシステムに関連づけられている前記集合Ｐ１の全ての前記エレメントの前記集合として前記部分集合Ｐ１．ｉを決定する工程とを含むことを特徴とする請求項３３に記載の方法。
【請求項３６】
複数のエレメントに対して、前記プロパティを所有するとして認証を提供するコンピュータに実装された認証方法であって、
それぞれの前記エレメントは、それぞれが予め特定されたプロパティを取得するか失効させるかの少なくとも一方のために動作可能で、１よりも大きい相異なる整数と関連づけられており、
前記集合Ｐ１の全ての前記エレメントが前記プロパティを所有する、又は、所有しないことを証明する第１のデータＡ１（Ｐ１）を取得する工程と、
前記集合Ｐ１のうちの２つ以上の空でない真部分集合Ｐ１．１，．．．，Ｐ１．ｋを決定する工程と、
それぞれの部分集合Ｐ１．ｉ(ｉ＝１，．．．，ｋ)に対して、前記部分集合Ｐ１．ｉにではなく前記集合Ｐ１に属する前記エレメントに関連づけられた整数の積である指数でＰ乗根ｕ１／Ｐ（ｍｏｄ ｎ）をべき乗することによって、第１のデータＡ１(Ｐ１．ｉ)を取得する工程とを含み、
前記第１のデータＡ１（Ｐ１）は、予め定義された合成数ｎを法とする整数ｕのＰ乗根ｕ１／Ｐ（ｍｏｄ ｎ）を表し、Pは、前記集合Ｐ１のメンバーに関連づけられた前記整数の積であり、
Ａ１（）は、前記エレメントの各集合ＳをＰｓ乗根
【数１８】
2008524930.tif 000161
を表すデータにマッピングする関数であり、Ｐｓは、前記集合Ｐ１のメンバーと関連づけられた前記整数の積であり、
それぞれの部分集合Ｐ１．ｉは、前記部分集合Ｐ１．ｉの全ての前記エレメントが、前記プロパティを所有する、又は、所有しないことを、Ａ１（Ｐ１．ｉ）を用いて、他の関係者に対して証明することができる少なくとも1つのコンピュータシステムＣＳ．ｉに関連づけられていることを特徴とする方法。
【請求項３７】
前記集合Ｐ１の各エレメントは、前記エレメントが前記プロパティを所有する、又は、所有しないことを他の関係者に対して証明することが可能となるコンピュータシステムに関連づけられており、
前記部分集合Ｐ１．１，．．．，Ｐ１．ｋを決定する工程には、
前記集合Ｐ１の1つ以上の前記エレメントに関連づけられている、1つ以上の前記コンピュータシステムを含むトポロジー領域ＡＲ．１，．．．，ＡＲ．ｋのそれぞれを決定する工程と、
各ｉ＝１，．．．，ｋに対して、前記トポロジー領域ＡＲ．ｉにおいて少なくとも1つのコンピュータシステムに関連づけられている前記集合Ｐ１の全ての前記エレメントの前記集合として前記部分集合Ｐ１．ｉを決定する工程とを含むことを特徴とする請求項３６に記載の方法。
【請求項３８】
前記部分集合Ｐ１．ｉが独立しており、
それぞれの集合Ｐ１．ｉ（ｉ＝１，．．．，ｋ）に対して関連づけられた第１のデータＡ１（Ｐ１．ｉ）を前記コンピュータシステムＣＳ．ｉに対して、ネットワーク上で送信する工程をさらに含むことを特徴とする請求項３７に記載の方法。
【請求項３９】
複数のエレメントが、前記プロパティを所有しているかどうかの認証を提供するコンピュータに実装された認証方法であって、
それぞれの前記エレメントは、予め特定されたプロパティを取得するか失効させるかの少なくとも一方のために動作可能で、１よりも大きい相異なる整数と関連づけられており、
集合Ｐ１における各エレメントが前記プロパティを所有する、又は、所有しないように２つ以上の前記エレメントの前記集合Ｐ１を選択する工程と、
予め定義された合成数ｎを法とする整数ｕのＰ乗根ｕ１／Ｐ(ｍｏｄ ｎ)を計算する工程と、
前記Ｐ乗根を、前記集合Ｐ１の各エレメントが前記プロパティを所有する、又は、所有しないことの証明として、1つ以上のコンピュータシステムに対してネットワーク上で送信する工程とを含み、
Ｐは、前記集合Ｐ１の前記エレメントに関連づけられた前記整数の積であることを特徴とする方法。
【請求項４０】
複数のエレメントが、前記プロパティを所有しているかどうかの認証を提供するコンピュータに実装された認証方法であって、
それぞれの前記エレメントは、予め特定されたプロパティを取得するか失効させるかの少なくとも一方のために動作可能で、１よりも大きい相異なる整数と関連づけられており、
予め定義された合成数ｎを法とする整数ｕのＰ乗根ｕ１／Ｐ(ｍｏｄ ｎ)をネットワーク上で受信する工程と、
前記Ｐ乗根を、前記集合Ｐ１の前記エレメントの全てよりも少ない1つ以上のエレメントを含む部分集合のエレメントに関連づけられた前記整数の積に等しい指数で、べき乗する工程と、
前記部分集合ではなく、前記集合Ｐ１における各エレメントが前記プロパティを所有する、又は、所有しないことを証明するために前記累乗演算の結果を用いる工程とを含み、
Ｐは、２つ以上の前記エレメントを含む前記集合Ｐ１のエレメントに関連づけられた前記整数の積であることを特徴とする方法。
【請求項４１】
エレメントＥ１が、複数の予め定義された期間のうちの1つである期間ｊにおいて予め特定されたプロパティを所有することを検証するコンピュータに実装された方法であって、
値Ｍ、Ｒ、Ｄをネットワーク上で受信する工程と、
【数１９】
2008524930.tif 000162
を検証する工程とを含み、
ｎは、予め定義された合成数であり、
【数２０】
2008524930.tif 000163
、ｄ＝Ｈ（Ｍ｜｜Ｒ）であり、
ｐＥ１は、各エレメントが相異なる整数に関連づけられているシステムにおいて前記エレメントＥ１に関連づけられた整数であり、
Ｈ（）は、予め定義された関数であり、
【数２１】
2008524930.tif 000164
であり、
ｍＥ１は、前記エレメントＥ１に関連づけられているが、前記期間とは無関係な予め定義された整数であり、
【数２２】
2008524930.tif 000165
であり、
ｕは、予め定義された一定値であり、
Ｐｊは、前記期間ｊによって前記プロパティを所有しないエレメントに関連づけられた整数の積であり、
前記検証する工程において、前記値ｒ及びｗＥ１ｊは、用いず、
前記検証する工程には、
ｎを法とするＪ＝ｍＥ１−１を計算する工程と、
【数２３】
2008524930.tif 000166
として、
【数２４】
2008524930.tif 000167
を確認する工程とが含まれることを特徴とする方法。
【請求項４２】
エレメントＥ１が、複数の予め定義された期間のうちの1つである期間ｊにおいて予め特定されたプロパティを所有することを検証するコンピュータに実装された方法であって、
値Ｍ、Ｒ、Ｄをネットワーク上で受信する工程と、
【数２５】
2008524930.tif 000168
を検証する工程とを含み、
ｎは、予め定義された合成数であり、
【数２６】
2008524930.tif 000169
、ｄ＝Ｈ（Ｍ｜｜Ｒ）であり、
ｐＥ１は、各エレメントが相異なる整数に関連づけられているシステムにおいて前記エレメントＥ１に関連づけられた整数であり、
ｓＥ１ｊは、前記エレメントＥ１及び、前記期間ｊに関連づけられた値であり、
Ｈ（）は、予め定義された関数であり、
前記検証する工程において、前記値ｒ及びｓＥ１ｊは、用いず、
前記検証する工程には、
ｎを法とするＪ＝ｍＥ１−１を計算する工程と、
【数２７】
2008524930.tif 000170
を確認する工程とを含み、
ｍＥ１は、前記エレメントＥ１に関連づけられているが、前記期間とは無関係な予め定義された値であり、
【数２８】
2008524930.tif 000171
であり、Ｈ（ｊ）は、
【数２９】
2008524930.tif 000172
となるようなjの予め定義された関数であることを特徴とする方法。
【請求項４３】
前記エレメントは、（ａ）暗号鍵がエンティティに関連づけられていることを証明するデジタル証明書のそれぞれか、（ｂ）1つ以上のリソースを用いるための権利のどちらかであり、前記プロパティは、デジタル証明書、又は、権利の有効性であることを特徴とする請求項１、３３、３６、３９、又は４０のいずれか１項に記載の方法。
【請求項４４】
前記エレメントに関連づけられた前記整数のそれぞれは、ｎに対して互いに素であり、前記エレメントに関連づけられた残りの整数の最小公倍数を分割しないことを特徴とする請求項１、３９、又は４０のいずれか１項に記載の方法。
【請求項４５】
コンピュータ命令を実行するための1つ以上のコンピュータ演算処理装置及び、請求項３３、３６、３９、４０、４１、又は４２のいずれか１項に記載の方法を実行するための1つ以上のコンピュータ命令を備えるコンピュータ記憶装置とを備えるコンピュータシステム。
【請求項４６】
請求項３３、３６、３９、４０、４１、又は４２のいずれか１項に記載の方法をコンピュータシステムに実行するようにプログラムされた1つ以上のコンピュータ命令を備えるコンピュータ可読記憶媒体。
【請求項４７】
請求項３３、３６、３９、４０、４１、又は４２のいずれか１項に記載の方法を実行するコンピュータプログラムをコンピュータシステムによってネットワーク上で送信する工程を含むネットワーク送信方法。
【国際調査報告】
2008524930.tif 000173
2008524930.tif 000174
2008524930.tif 000175