データ処理システム内でデータ項目の集合を示す暗号アキュムレータを提供するための方法、装置、コンピュータ・プログラム、およびデータ処理システム（データ処理システム内のデータ項目の検証）
【課題】 データ処理システム（１）内で暗号クレデンシャルなどのデータ項目の集合を示す暗号アキュムレータを提供するための方法および装置を提供する。
【解決手段】 複数の群要素が生成され、前記集合内のデータ項目とそれぞれの群要素とのマッピングが定義される。暗号アキュムレータが生成され、暗号アキュムレータは集合内のデータ項目にマッピングされた群要素に関するそれぞれの群要素の積を含む。その後、暗号アキュムレータは、データ処理システム（１）で使用中のデータ項目がアキュムレータによって示された集合のメンバであるかどうかを検証する際に関係するシステム・コンポーネント（６、７）による使用のために使用可能になるように、データ処理システム（１）内で公表される。
【解決手段】 複数の群要素が生成され、前記集合内のデータ項目とそれぞれの群要素とのマッピングが定義される。暗号アキュムレータが生成され、暗号アキュムレータは集合内のデータ項目にマッピングされた群要素に関するそれぞれの群要素の積を含む。その後、暗号アキュムレータは、データ処理システム（１）で使用中のデータ項目がアキュムレータによって示された集合のメンバであるかどうかを検証する際に関係するシステム・コンポーネント（６、７）による使用のために使用可能になるように、データ処理システム（１）内で公表される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、データ処理システム内の暗号クレデンシャル（cryptographiccredential）などのデータ項目の検証に関する。データ処理システム内でこのような検証プロセスを容易にするための方法、装置、およびコンピュータ・プログラムが提供される。
【０００２】
データ処理システムに対して何らかの当事者に関連するデータ項目に関して何らかの形の検証プロセスを実行する必要がある場合が多い。たとえば、ある当事者がデータ項目の所有あるいは有効または本物のデータ項目の所有をそのシステムの他の当事者に対して証明することが必要である場合がある。このような証明は、匿名性およびユーザ・プライバシを全般的に保護するために、データ項目自体を開示しないかあるいはデータ項目または証明側当事者に関するその他の情報をまったく明らかにしないような方法で行う必要がある場合もある。一般的な例は暗号クレデンシャルによって提供される。暗号クレデンシャルとは、典型的に、信頼できる当事者（「発行者（issuer）」）によってユーザに発行される、暗号シグニチャ、証明書、またはその他の暗号トークンである。このクレデンシャルは、その後、そのクレデンシャルが発行された情報の証明として、ユーザと他の当事者（「検証者（verifier）」、これは発行者である場合もあれば、そうではない場合もある）との間の通信で使用することができる。典型的なシナリオは、ユーザがデータ通信ネットワークを介してリモート・サーバに接続し、クレデンシャルを使用して、何らかの制限付きサービスまたはその他のリソースにアクセスするための許可を実証することを含む。以下の考察は主に暗号クレデンシャルについて取り上げるが、同様の考慮事項は、それに関する証明を検証者に対して行う必要がある可能性がある、その他のデータ項目、たとえば、任意の秘密のデータに適用することができる。
【０００３】
データ項目の検証プロセスは、しばしば、そのデータ項目がデータ項目の定義済み集合のうちの１つであることを証明することを含む。たとえば、暗号クレデンシャルの場合、クレデンシャルが本物または有効なクレデンシャルのリスト上にあることを証明することが必要である場合がある。特に、限られた期間の間、発行されるかまたは発行後に他の何らかの理由で取り消されるので、クレデンシャルの妥当性は一時的なものである場合がある。前者の場合、満了日は、（たとえば、クレデンシャル内に暗号化されたデータのコンポーネントまたは「属性」の１つとして）クレデンシャルに含まれ、妥当性を保証するために検証者によってチェックされる可能性がある。しかし、後者の場合、予期せぬイベントがクレデンシャルの早期取り消し（無効化）を要求する可能性がある場合、検証者は妥当性を確認するために発行者（またはその他の信頼できる当事者）から追加の情報を要求する。たとえば、ユーザが仕事を辞める場合、そのユーザが職場にアクセスできるようにしているクレデンシャルは無効にしなければならない。より痛切な一例は、違法購入のために悪意のある当事者によって脅かされ使用されたクレジットカード様のクレデンシャルを取り消す必要性である。このような場合、検証者は信頼できる当事者とともにクレデンシャルの妥当性をチェックする必要がある。
【０００４】
検証者がクレデンシャルの妥当性をチェックする必要性は、特にプライバシが主な関心事である場合、様々な問題を提起する。匿名性が問題ではないシナリオでは、クレデンシャルに関連する通し番号などの識別子はトランザクション中に検証者に対して明らかにすることができる。その場合、検証者は、発行者によって定期的に公表される取り消されたクレデンシャルＩＤのリストに照らし合わせてこれをチェックすることができる。他の解決策は、検証者がオンライン発行者に証明書取り消し状況照会を送信することである。前者の解決策は、取り消された証明書のリストが非常に大きいものになる可能性があるので、通信上非効率的であり、後者の解決策は、発行機関が永続的にオンラインであることを要求する。どちらの解決策もすべての当事者がクレデンシャルＩＤを把握していることを必要とし、ユーザ・プライバシを破壊するものである。しかし、匿名クレデンシャル・システムでは、トランザクションを行うために必要な最小量の情報のみをユーザが開示するような方法で、ユーザ、発行者、および検証者間のトランザクションが実行されることを必要とする。その上、発行者はどのクレデンシャル属性が検証者に示されるのかを学習することができず、発行者および検証者はユーザ・トランザクションをリンクすることができない。匿名クレデンシャル・システムは、ユーザの匿名性とトランザクションのリンク不能性（unlinkability）を保護することを目指しているので、発行者および検証者はトランザクション中に証明書ＩＤを学習することができず、代替の取り消し状況チェック技法が必要である。
【０００５】
上記の問題に対処するための既知の技法の１つでは暗号アキュムレータ（cryptographic accumulator）を使用する。暗号アキュムレータは、入力の大きい集合を単一の短い出力、すなわち、アキュムレータにハッシュできるようにするものである。所与の入力が本当にアキュムレータに含まれるという証拠は、アキュムレータ証人（accumulator witness）によって提供される。たとえば、アキュムレータ（ＡＣＣ）が、入力ｘ1〜ｘnの場合にＦ（ｘ1，．．．，ｘn）＝ＡＣＣによって定義される場合、所与の入力ｘiがＡＣＣに含まれることを証明するには、証人ｗiと、Ｖ（ｘi，ｗi）＝ＡＣＣになるような検証関数Ｖの存在が必要である。ｘyがアキュムレータに含まれない場合にＶ（ｘy，ｗy）＝ＡＣＣになるようなｗyを計算することが実行不可能であるという特徴によってセキュリティが保証される。上述のシナリオで適用されると、すべての現在有効なクレデンシャルの通し番号が蓄積され、その結果のアキュムレータが公表される。次にユーザは、自分の証人を使用して、自分のクレデンシャルの通し番号が公表されたアキュムレータに含まれることを（ゼロ知識で）証明することによって、自分のクレデンシャルが依然として有効であることを検証者に対して実証することができる。このようなシステムは、2004年、Springer Verlag発行、Matthew K. Franklin編集、Advances in Cryptology- CRYPTO 2004、LNCSの3152巻、41〜55ページ掲載のBoneh他による「Short group signatures」ならびに2002年、Springer Verlag発行、Moti Yung編集、Advances in Cryptology - CRYPTO 2002、LNCSの2442巻、61〜76ページ掲載のCamenischおよびLysyanskayaによる「Dynamic accumulators and application to efficient revocation ofanonymous credentials」に記載されている。しかし、これらの解決策の欠点は、ユーザが自分のアキュムレータ証人を更新する必要があり、更新には新たに取り消されたクレデンシャルごとに少なくとも１回のモジュラべき乗（modular exponentiation）を必要とすることである。典型的な適用例では多数の取り消されたクレデンシャルが存在する可能性があるので、これらの解決策は相当な計算（および通信）コストを発生し、特に、スマート・カードなどのリソース限定ユーザ・デバイスが処理できるものを大幅に上回るコストを発生する。たとえば、上記のCamenischおよびLysyanskayaの文献では、動的アキュムレータを紹介し、匿名クレデンシャル・システムにおける取り消しならびにアイデンティティ・エスクローおよびグループ・シグニチャに対するその適用性を示している。提案されたアキュムレータならびにユーザ証人の更新は、システムに追加されたかまたはシステムから取り消されたユーザの数において線形の複数回のべき乗を必要とする。このアキュムレータは、2007年、Springer発行、JonathanKatzおよびMoti Yung編集、ACNS、Lecture Notes in Computer Scienceの4521巻、253〜269ページ掲載のJiangtaoLi他による「Universal accumulators with efficientnonmembership proofs」において、値が蓄積されていないという証人および証明を紹介して、拡張されている。
【０００６】
動的アキュムレータは、2005年、Springer発行、AlfredMenezes編集、CT-RSA、Lecture Notesin Computer Scienceの3376巻、275〜292ページ掲載のLan Nguyenによる「Accumulators from bilinear pairings and applications」において、双線形ペアリング（bilinearpairing）から構築される。このシステムを匿名クレデンシャル・システムに適用すると、自分のクレデンシャルの妥当性を証明するために各ユーザが保管する必要のある非常に大きいシステム・パラメータ（蓄積可能な値の数において線形の複数の要素）が発生する。また、このアキュムレータが安全ではなく、いずれの当事者も秘密の知識がなければ匿名識別プロトコルに成功できないことは、2005年、CT-RSA 05におけるZhangおよびChenによる「Cryptanalysis and improvement of anID-based ad-hoc anonymous identification scheme」において指摘されている。その上、証人を更新するにはイベントあたり１回のべき乗を要し、したがって、効率的ではない（この論文では、著者は、双線形マップおよび楕円曲線群に関して時々行われるように、代数群用の基本演算として加算を使用し、乗算を作成している（上記のNguyenの文献を参照されたい））。
【０００７】
バッチ更新のための動的アキュムレータは、2007年、Springer発行、SihanQing他編集、ICICS、Lecture Notes inComputer Scienceの4861巻、98〜112ページ掲載のPeishun Wang他による「A new dynamic accumulator for batch updates」に提案されている。多くの証人更新を逸したユーザは、発行者に対して更新情報を要求し、１回の乗算で自分の証人を更新することができる。しかし、この方式は、クレデンシャル取り消しなどの適用例には使用可能にはならないであろう。たとえば、クレデンシャルの取り消しのためにアキュムレータの使用に必要とされるように、アキュムレータに含まれる要素の知識の効率的証明をどのように達成することになるかは明白ではない。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】2004年、Springer Verlag発行、Matthew K. Franklin編集、Advances in Cryptology - CRYPTO 2004、LNCSの3152巻、41〜55ページ掲載のBoneh他による「Short group signatures」
【非特許文献２】2002年、Springer Verlag発行、Moti Yung編集、Advances in Cryptology - CRYPTO 2002、LNCSの2442巻、61〜76ページ掲載のCamenischおよびLysyanskayaによる「Dynamic accumulators and application to efficient revocation ofanonymous credentials」
【非特許文献３】2007年、Springer発行、Jonathan KatzおよびMoti Yung編集、ACNS、LectureNotes in Computer Scienceの4521巻、253〜269ページ掲載のJiangtaoLi他による「Universal accumulators with efficientnonmembership proofs」
【非特許文献４】2005年、Springer発行、Alfred Menezes編集、CT-RSA、Lecture Notes in Computer Scienceの3376巻、275〜292ページ掲載のLan Nguyenによる「Accumulators from bilinearpairings and applications」
【非特許文献５】2005年、CT-RSA 05におけるZhangおよびChenによる「Cryptanalysis and improvement of anID-based ad-hoc anonymous identification scheme」
【非特許文献６】2007年、Springer発行、Sihan Qing他編集、ICICS、Lecture Notes in Computer Scienceの4861巻、98〜112ページ掲載のPeishun Wang他による「A new dynamic accumulatorfor batch updates」
【非特許文献７】2005年、Springer発行、Lecture Notes in Computer Scienceの3494巻、2005年5月22〜26日デンマークのオルフス開催の24thAnnual International Conference on the Theory and Applications of CryptographicTechniques、Advances in Cryptology - EUROCRYPT 2005の会議録、Cramer編集、440〜456ページ掲載のBoneh他による「Hierarchical identity basedencryption with constant size ciphertext」
【非特許文献８】2004年、Springer発行、Christian CachinおよびJan Camenisch編集、EUROCRYPT、Lecture Notes in Computer Scienceの3027巻、56〜73ページ掲載のDan BonehおよびXavier Boyenによる「Short signatures withoutrandom oracles」
【非特許文献９】2007年、Springer発行、Tatsuaki OkamotoおよびXiaoyunWang編集、Public Key Cryptography、Lecture Notes in Computer Scienceの4450巻、1〜15ページ掲載のBoyenおよびWatersによる「Full-domain subgroup hiding andconstant-size group signatures」
【非特許文献１０】1997年3月、ETHチューリッヒ、TechnicalReport TR 260、Institute for Theoretical ComputerScience、Jan CamenischおよびMarkusStadlerによる「Proof systems for general statements aboutdiscrete logarithms」
【非特許文献１１】2004年、Springer Verlag発行、Matthew K. Franklin編集、Advances in Cryptology - CRYPTO 2004、LNCSの3152巻、56〜72ページ掲載のCamenischおよびLysyanskayaによる「Signature schemes and anonymous credentials from bilinear maps」
【非特許文献１２】2005年、Springer発行、Advances in Cryptology - CRYPTO2005、Lecture Notes in Computer Scienceの3621巻、258〜275ページ掲載のBoneh、Gentry、およびWatersによる「Collusion Resistant Broadcast Encryption with Short Ciphertexts andPrivate Keys」
【非特許文献１３】2004年、Springer発行、Christianson他編集、Security Protocols Workshop、Lecture Notes inComputer Scienceの3957巻、20〜42ページ掲載のBangerter他による「A cryptographic framework for the controlled release of certifieddata」
【非特許文献１４】2003年、Springer Verlag発行、I Cimato他編集、Security in CommunicationNetworks、Third International Conference、SCN 2002、LNCSの2576巻、268〜289ページ掲載のJanCamenischおよびAnna Lysyanskayaによる「A signature scheme with efficient protocols」
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明の一態様は、データ処理システム内でデータ項目の集合を示す暗号アキュムレータを提供するための方法を提供する。この方法は、
複数の群要素を生成することと、
前記集合内のデータ項目とそれぞれの群要素とのマッピングを定義することと、
集合内のデータ項目にマッピングされた群要素に関するそれぞれの群要素の積を含む暗号アキュムレータを生成することと、
データ処理システム内の暗号アキュムレータを公表すること
を含む。
【課題を解決するための手段】
【００１０】
本発明のこの態様を実施する方法は、暗号クレデンシャルなどのデータ項目の検証時に使用するための、特に、データ処理システム内のこのようなデータ項目の特定の集合を示すための高速かつ効率的なアキュムレータベースのシステムを提供することができる。これは、たとえば、データ処理システム内で使用中の本物または現在有効なデータ項目の集合を定義するために使用することができる。この効率により、本発明の諸実施形態がクレデンシャル取り消しに容易に適用可能になる。蓄積は高速であり、複雑さは集合内のデータ項目の数において線形である。アキュムレータ更新の複雑さは、変更の数、すなわち、集合に追加されたかまたは集合から除去されたデータ項目の数において線形である。また、このシステムは、アキュムレータ証人の高速かつ効率的な計算ならびに更新のための基礎を提供する。特に、以下に記載する諸実施形態における証人の計算は集合内のデータ項目の数において線形であり、各証人の更新は変更の数において線形である。したがって、証人更新は単一乗算で達成することができる。この計算上の複雑さの改善により、計算能力が限られているリソース制約形ユーザ・デバイスを伴うデータ処理システムで都合良く適用することができる。これについては以下に詳述する。その上、以下に例により実証する通り、このシステムは、クレデンシャル取り消しなどのプライバシの適用例に必要な集合のメンバシップを証明するための効率的な証明プロトコルのための基礎も提供する。
【００１１】
一般に、本発明が適用されるデータ項目は、それについて何らかの事実、たとえば、データ項目の妥当性、信憑性、または単純所有をアキュムレータを参照することによって検証者に対して証明しなければならないデータの任意の項目にすることができる。データ項目は、たとえば、アキュムレータによって示された集合内にデータ項目が含まれることを実証することにより、データ自体を明らかにせずに、検証者に対して証明すべき特性を備えた秘密のデータを含むことができる。しかし、典型的な適用例では、データ項目は暗号項目になり、特に、すでに述べた暗号クレデンシャルになる。
【００１２】
適用例に応じて、データ項目の集合は動的になる可能性があり、それにより、時間の経過につれて項目を集合に追加するかまたは集合から除去するかあるいはその両方を行うことができる。群要素に対するデータ項目のマッピングおよびおそらく群要素の生成も、新しいデータ項目が動的集合に追加されるときに漸次実行することができる。また、適用例に応じて、集合から除去されたデータ項目に対して前にマッピングされた群要素は、新しいデータ項目に再割り当てされる場合もあれば、されない場合もある。いずれの場合も、動的集合の場合、暗号アキュムレータは、集合内容の変更を反映するために定期的に生成することができる。したがって、いつでもアキュムレータは、現在集合内にある項目にマッピングされた要素に関する群要素の積を含まなければならない。生成されると、アキュムレータは、データ項目のその後の検証にかかわるシステムのコンポーネントによる使用のために使用可能になるように、データ処理システム内で公表される。関連システム・コンポーネントに直接、アキュムレータを伝送することにより公表を実施することができるシステムを構想することもできる。しかし、より一般的には、システム内の１つまたは複数のデータ通信チャネルを介してアキュムレータへのアクセスを可能にすることにより公表が実施され、それにより、検証目的に必要なときにシステム・コンポーネントはアキュムレータにアクセスすることができる。
【００１３】
当業者であれば、代替例を構想することができるだろうが、以下に記載する好ましい諸実施形態のように、（少なくとも）秘密値γおよび群ジェネレータ（group generator）ｇを使用して各群要素を生成することができる。より具体的には、好ましい諸実施形態では、群要素は、ｉ∈｛１，２，３，．．．，ｎ｝の場合にそれぞれの要素
【数１】
を含み、ここでｎは集合内のデータ項目の定義済みの最大数である。（群要素は、後述する通り、システム内で使用するための追加のまたは「補助」値も含むことができる。）次に、集合内のデータ項目とそれぞれの群要素ｇiとの間でマッピングが定義される。これらの実施形態では、暗号アキュムレータは、群要素ｇiが前記集合内のデータ項目にマッピングされるｉの値について群要素ｇn+1-iの積を含む。したがって、蓄積された要素は、集合内の項目にマッピングされた要素ｇiに対してｉ値を介して関連付けられる。
【００１４】
群要素に対するデータ項目のマッピングは、暗号クレデンシャルの通し番号など、各データ項目に関連する数値識別子とそれぞれの群要素との間で定義することができる。この通し番号またはその他の識別子は理想的にはデータ項目自体に定義される。一部の実施形態では、このマッピングは、割り振られた群要素をデータ項目用の識別子として割り当てることによって定義することもできるであろう。
【００１５】
動的集合に関するアキュムレータを更新するプロセスと、データ項目に関する証人を生成し更新するプロセスについては、以下の詳細に説明する。しかし、簡単に言えば、好ましい実施形態では、データ項目に関する証人は群要素のそれぞれの異なる部分集合の積を含み、各証人に関する部分集合は前記集合内のデータ項目とその証人が生成されたデータ項目に依存する。これらの証人の計算および更新は高速かつ効率的である。特に、データ項目の集合内の変更を反映するための証人の更新は、理想的には単一乗算で行うことができる。
【００１６】
本発明の第２の態様は、データ処理システム内でデータ項目の集合を示す暗号アキュムレータを提供するための装置を提供する。この装置は、メモリと、本発明の第１の態様による方法を実行するように適合された制御ロジックとを含み、複数の群要素は前記メモリ内に保管される。
【００１７】
本発明の第３の態様は、それぞれがデータ通信ネットワークを介した通信用に適合されたユーザ・コンピュータ、検証者コンピュータ、およびデータ項目管理コンピュータを含む、データ処理システムを提供する。データ項目管理コンピュータは、前記ユーザ・コンピュータに関連するユーザ・データ項目を含むデータ項目の集合を示す暗号アキュムレータを提供するための本発明の第１の態様による方法を実行するように適合される。ユーザ・コンピュータは、暗号アキュムレータのために、前記ユーザ・データ項目と、そのユーザ・データ項目に対応する証人を保管する。ユーザ・コンピュータおよび検証者コンピュータは、暗号アキュムレータによって示された集合内のデータ項目に対応する証人に関するユーザ・コンピュータによる知識を証明する検証プロコトルを実装するためにネットワークを介した通信用に適合される。検証プロトコルは、好ましくは、ゼロ知識証明プロトコルである。
【００１８】
本発明の第４の態様は、本発明の第１の態様による方法をコンピュータに実行させるためのプログラム・コード手段を含むコンピュータ・プログラムを提供する。「コンピュータ」という用語は本明細書では最も一般的な意味で使用され、コンピュータ・プログラムを実装するためのデータ処理機能を有する任意のデバイス、コンポーネント、またはシステムを含むことが理解されるであろう。その上、本発明を実施するコンピュータ・プログラムは、１つの独立プログラムを構成するかまたはより大きいプログラムの１つの要素になる可能性があり、たとえば、コンピュータにロードするためのディスクまたは電子伝送などのコンピュータ可読媒体に実施して供給することができる。コンピュータ・プログラムのプログラム・コード手段は、直接または（ａ）他の言語、コード、または表記への変換、および（ｂ）異なる物質的形式による複製のいずれか一方または両方の後、当該方法をコンピュータに実行させるための１組の命令を任意の言語、コード、または表記で表した任意の表現を含むことができる。
【００１９】
一般に、本明細書では本発明の一態様の一実施形態に関連して特徴を説明するが、対応する特徴を本発明の他の態様の諸実施形態で示す場合もある。
【００２０】
次に、例として、添付図面に関連して本発明の好ましい諸実施形態について説明する。
【図面の簡単な説明】
【００２１】
【図１】本発明を実施するデータ処理システムの概略図である。
【図２】図１のシステムにおいて発行者コンピュータによって実行されるセットアップ手順を示す図である。
【図３】図１の発行者コンピュータのその後の動作を示す図である。
【図４】図１のシステムにおいてユーザ・コンピュータと検証者コンピュータとの間の対話を示す図である。
【図５】図１のシステムの好ましい実装例においてユーザ・コンピュータと検証者コンピュータとの間の対話を示す図である。
【発明を実施するための形態】
【００２２】
本発明を実施するデータ処理システムについて説明する前に、まず、説明すべき模範的な諸実施形態の動作時に使用されるビルディング・ブロックとして使用される様々な仮定および暗号ツールを提示する。
【００２３】
すべての整数ｃについて、すべてのｋ＞Ｋの場合に｜υ（ｋ）｜＜１／ｋｃになるような整数Ｋが存在する場合、関数υは無視してもよい。それを解くための入力のサイズについて確率的多項式時間（ｐ．ｐ．ｔ．）アルゴリズムがまったく存在しない場合、問題は困難（または至難）であると言われる。
【００２４】
双線形ペアリング。ＧおよびＧTは基本次数（prime order）ｑの群とする。マップｅ：Ｇ×Ｇ→ＧTは以下の特性を満足しなければならない。
（ａ）双線形性： ｅ（ａx，ｂy）ｔ＝ｅ（ａ，ｂ）x,yである場合、マップｅ：Ｇ×Ｇ→ＧTは双線形である。
（ｂ）非退化（non-degeneracy）： すべてのジェネレータｇ，ｈ∈Ｇについて、ｅ（ｇ，ｈ）はＧTを生成する。
（ｃ）効率： 双線形マップを生成するために（ｑ，Ｇ，ＧT，ｅ，ｇ）を出力する効率的なアルゴリズムＢＭＧｅｎ（１k）と、任意のａ，ｂ∈Ｇについてｅ（ａ，ｂ）を計算するための効率的なアルゴリズムが存在する。
【００２５】
セキュリティは以下の数論仮定に基づくものである。説明すべき諸実施形態におけるアキュムレータ構造はDiffie-Hellman Exponent仮定に基づくものである。クレデンシャルの非鍛造性はStrong Diffie-Hellman仮定に基づくものである。クレデンシャルの取り消しの場合、クレデンシャルに関するアキュムレータ証人の所有を証明する必要がある。この証明は、新しいHidden Strong Diffie-Hellman Exponent（SDHE）仮定に基づくものである。
【００２６】
定義１（n-DHE）。Diffie-Hellman Exponent（DHE）仮定： 基本次数ｑの群Ｇ内のn-DHE問題は、以下のように定義される。すなわち、
【数２】
とする。入力
【数３】
のときに、ｇn+1を出力する。
【００２７】
n-DHE仮定では、この問題は解決するのが困難であることを示している。
【００２８】
2005年、Springer発行、Lecture Notes in Computer Scienceの3494巻、2005年5月22〜26日デンマークのオルフス開催の24th Annual InternationalConference on the Theory and Applications of Cryptographic Techniques、Advances in Cryptology - EUROCRYPT 2005の会議録、Cramer編集、440〜456ページ掲載のBoneh他による「Hierarchical identity based encryption with constant size ciphertext」では、著者は、双線形マップについて定義されたBilinear Diffie-Hellman Exponent（BDHE）仮定を紹介している。この場合、相手方は
【数４】
を計算しなければならない。
【００２９】
補助定理１。双線形ペアリングｅ：Ｇ×Ｇ→ＧTを有する群Ｇに関するｎ−ＤＨＥ仮定は、同じ群に関するｎ−ＢＤＨＥ仮定によって暗示される。
【００３０】
BonehおよびBoyenは、2004年、Springer発行、ChristianCachinおよびJan Camenisch編集、EUROCRYPT、Lecture Notes in Computer Scienceの3027巻、56〜73ページ掲載のDan BonehおよびXavier Boyenによる「Short signatures withoutrandom oracles」において、Strong Diffie-Hellman仮定を紹介している。
【００３１】
定義２（n-SDH − 上記の文献「Short signatures withoutrandom oracles」を参照されたい）。入力
【数５】
のときに、（ｇ1/(x+c)，ｃ）を出力することは計算的に実行不可能である。
【００３２】
2007年、Springer発行、Tatsuaki OkamotoおよびXiaoyunWang編集、Public Key Cryptography、Lecture Notes inComputer Scienceの4450巻、1〜15ページ掲載のBoyenおよびWatersによる「Full-domain subgroup hiding and constant-size group signatures」では、著者は、メッセージが不明である状況においてＢＢシグニチャ（上記で参照した「Short signatures without random oracles」を参照されたい）の使用を可能にするためのHidden Strong Diffie-Hellman仮定を紹介している。HiddenStrong Diffie-Hellman Exponent（n-HSDHE）仮定と呼ぶ、Hidden Strong Diffie-Hellman仮定の変形を必要とする。この２つの仮定は今までのところ比較不能である。
【００３３】
定義３（n-HSDHE）。入力
【数６】
および
【数７】
のときに、新しいタプル｛ｇ1/(x+c)，ｇc，ｕc｝を出力することは計算的に実行不可能である。
【００３４】
既知の離散対数ベースのゼロ知識証明
共通パラメータ・モデルでは、離散対数に関するステートメントを証明するためにいくつかの既知の結果を使用する。このような証明に言及する場合、離散対数の知識の様々な証明および離散対数に関するステートメントの妥当性証明のために、CamenischおよびStadlerによって紹介された表記法に従う（1997年3月、ETHチューリッヒ、Technical Report TR 260、Institute forTheoretical Computer Science、Jan CamenischおよびMarkus Stadlerによる「Proof systems for generalstatements about discrete logarithms」）。たとえば、
【数８】
は、
【数９】
が同じ次数を有するいくつかの群Ｇ＝〈ｇ〉＝〈ｈ〉および
【数１０】
の要素である場合に、「ｙ＝ｇαｈβおよび
【数１１】
が成り立つような整数α、β、およびδに関する知識のゼロ知識証明」を示している。（ｙおよび
【数１２】
という表現内のいくつかの要素が等しいことに留意されたい。）規約は、値α、β、およびδはどの知識が証明されているかという量を示し（しかも秘密に保持され）、他のすべての値は検証者にとって既知であることである。ここで考慮するすべての群を含む基本次数群の場合、正常な証明者（prover）からこれらの量を抽出することができる知識抽出者（knowledgeextractor）が存在することは周知のことである。
【００３５】
効率的なプロトコルによるシグニチャ方式
説明すべきクレデンシャル・システムにおけるシグニチャ方式は、2004年、Springer Verlag発行、Matthew K. Franklin編集、Advances in Cryptology - CRYPTO 2004、LNCSの3152巻、56〜72ページ掲載のCamenischおよびLysyanskayaによる「Signature schemes and anonymous credentials from bilinear maps」に詳述されており、n-SDH仮定に基づいて安全であると証明されている。これは、ジェネレータｈ，ｈ0，ｈ1，．．．，ｈl，ｈl+1を有する基本次数ｑの非退化双線形マップｅ：Ｇ×Ｇ→ＧTを仮定する。署名者（signer）の秘密鍵はｘ∈Ｚqであり、公開鍵はｙ＝ｈxである。
【００３６】
メッセージ
【数１３】
上のシグニチャは、
【数１４】
をピックし、
【数１５】
を計算することによって計算される。このシグニチャは（σ，ｃ，ｓ）である。これは、
【数１６】
であるかどうかをチェックすることによって検証される。複数のメッセージ
【数１７】
は、
【数１８】
として署名することができ、
【数１９】
であるかどうかをチェックすることによって検証が行われる。
【００３７】
シグニチャの知識の証明
ここで、メッセージｍ1，．．．，ｍl∈Ｚq上のシグニチャ（σ，ｃ，ｓ）が与えられ、このようなシグニチャを本当に所有することを証明したいと希望していると仮定する。このために、
【数２０】
が既知ではなくなるように、値
【数２１】
で公開鍵を増強する必要がある。
【００３８】
シグニチャの知識は以下のように証明される。
１．ランダム値（random value）ｒ←Ｚqおよびｏｐｅｎ←Ｚqを選択し、コミットメント（commitment）
【数２２】
および目隠しシグニチャ（blinded signature）
【数２３】
を計算する。
２．以下の証明を計算する。
【数２４】
【００３９】
次に、説明すべき諸実施形態の理解を支援するために動的アキュムレータについていくつかの基本を紹介する。要素をそれに加える／それから削除する場合の計算コストがアキュムレータに含まれている要素の数とは無関係である場合、アキュムレータは動的である。安全なアキュムレータは、AccGen、AccAdd、AccUpdate、AccWitUpdate、およびAccVerifyというアルゴリズムで構成される。これらのアルゴリズムは、アキュムレータを管理する機関（「機関」）、ユーザ、および検証者によって使用される。（説明すべき好ましい諸実施形態のいくつかでは、これらのアルゴリズムのうちの特定のものは、信頼できない更新エンティティによって使用される場合もある。）
【００４０】
この機関は、AccGenアルゴリズムを使用して、アキュムレータ鍵のペア（accumulator key pair）（ｓｋA，ｐｋA）、アキュムレータａｃｃφ、および公開状態（publicstate）ｓｔａｔｅφを作成する。証人ｗｉｔiとともに、新しいアキュムレータ
【数２５】
および状態
【数２６】
を入手するために、AccAddアルゴリズムを使用して、アキュムレータａｃｃVに新しい値ｉを追加することができる。AccUpdateアルゴリズムを使用して、所与の集合の値Ｖに関するアキュムレータを計算することができる。
【００４１】
これらの演算全体を通して、ａｃｃVおよびｗｉｔiは一定のサイズである（蓄積された値の数とは無関係である）。この機関は、証人ｗｉｔiが作成されたときにアキュムレータに含まれている値およびアキュムレータの状況について何らかのブックキーピングを実行する。これらの集合はそれぞれＶおよびＶwとして示される。ブックキーピング情報は、公表され、証人を更新するためにのみ必要とされ、値がアキュムレータに含まれていることを検証するためには必要ではない。
【００４２】
アキュムレータが変化するたびに、古い証人は無効になる。しかし、ブックキーピング情報Ｖwからアキュムレータに含まれる値ｉ∈Ｖについてすべての証人を更新することは可能である。この更新は、既存のアキュムレータ・システムにおいて最も性能集約型の動作である。アキュムレータ状態ｓｔａｔｅUは、アキュムレータにこれまでに追加された（が、必ずしも現在のアキュムレータに含まれているわけではない）要素の集合であるブックキーピング情報Ｕも含む。これは、ＶおよびＶwの超集合である。
【００４３】
ユーザが現在のアキュムレータに関する値ｉについて更新された証人ｗｉｔ’iを入手した後、ユーザは、AccVerifyアルゴリズムを使用して、ｉがアキュムレータ内にあることをすべての検証者に対して証明することができる。
【００４４】
ＡｃｃＧｅｎ（１k，ｎ）は、アキュムレータ鍵のペア（ｓｋA，ｐｋA）、空のアキュムレータａｃｃφ（ｎ個の値まで蓄積するため）、および初期状態ｓｔａｔｅφを作成する。
【００４５】
ＡｃｃＡｄｄ（ｓｋA，ｉ，ａｃｃV，ｓｔａｔｅU）は、その機関がアキュムレータにｉを追加できるようにするものである。これは、ｉについて、証人ｗｉｔiとともに、新しいアキュムレータ
【数２７】
および状態
【数２８】
を出力する。
【００４６】
ＡｃｃＵｐｄａｔｅ（ｐｋA，Ｖ，ｓｔａｔｅU）は、値Ｖ⊂Ｕについて、アキュムレータａｃｃVを出力する。
【００４７】
ＡｃｃＷｉｔＵｐｄａｔｅ（ｐｋA，ｗｉｔi，Ｖw，ａｃｃV，Ｖ，ｓｔａｔｅU）は、ｗｉｔiが
【数２９】
に関する証人であり、ｉ∈Ｖである場合に、ａｃｃVに関する証人ｗｉｔ’iを出力する。
【００４８】
ＡｃｃＶｅｒｉｆｙ（ｐｋA，ｉ，ｗｉｔi，ａｃｃV）は、最新の証人ｗｉｔiおよびアキュムレータａｃｃVを使用して、ν∈Ｖであることを検証する。その場合、アルゴリズムは受諾し、そうではない場合、アルゴリズムは拒否する。
【００４９】
添付図面のうちの図１は、本発明を実施する第１のデータ処理システムの簡易概略図であり、システムの動作に関係する主なコンポーネントを示している。データ処理システム１は、データ項目、ここでは暗号クレデンシャルを管理し、説明すべきクレデンシャル検証プロセスで使用するための暗号アキュムレータを管理する役割を担う機関によって操作されるデータ項目管理コンピュータ２を含む。特に、この機関（ここでは「発行者」）は、暗号クレデンシャルをユーザに対して発行し、説明すべきアキュムレータを介してシステム内で有効なクレデンシャルを示す。発行者コンピュータ２は、以下に詳述するプロセスを実装するためのクレデンシャル管理ロジック３と、メモリ４と、通信インターフェース５とを含む。また、システム１は、発行者コンピュータ２から入手した暗号クレデンシャルを使用するためのユーザ・コンピュータ６と、説明すべきアキュムレータを参照することによりユーザ・クレデンシャルを検証するための検証者コンピュータ７も含む。ユーザ・コンピュータ６は、以下に記載する暗号プロセスを実装するための証明者ロジック８と、メモリ９と、通信インターフェース１０とを含む。検証者コンピュータ７は、以下に記載する暗号検証プロセスを実行するための検証者ロジック１１と、メモリ１２と、通信インターフェース１３とを含む。コンピュータ２、６、および７は、それぞれの通信インターフェースを介してデータ通信ネットワーク１５により通信することができる（ネットワーク１５は実際には、複数のコンポーネント・ネットワークあるいはインターネットワークまたはその両方を含むことができる）。加えて、システム１は、ここではネットワーク１５内に示され、すべてのコンピュータ２、６、７にとってアクセス可能な配布者コンピュータ１６を含み、その目的については以下に説明する。
【００５０】
発行者、ユーザ、および検証者コンピュータの制御ロジック３、８、１１は、以下に記載する暗号プロセスの適切なステップを実装するために構成される。一般に、この制御ロジックは、ハードウェアまたはソフトウェアあるいはそれらの組み合わせで実装することができ、ユーザ、検証者、および発行者デバイス２、６、７の正確な形式は説明すべきシステムの基本動作とはほとんど無関係である。しかし、この例では、これらのデバイスは汎用コンピュータで実装され、ユーザ・コンピュータ６はユーザＰＣであり、発行者および検証者コンピュータ２、７はユーザＰＣ６がネットワーク１５により接続可能なサーバであると仮定する。クレデンシャル管理ロジック３、証明者ロジック８、および検証者ロジック１１はここでは、記載されている機能を実行するようにホスト・コンピュータを構成するそれぞれのコンピュータ・プログラムによって実装される。適切なソフトウェアは、本明細書の記述から当業者にとって明らかになるであろう。しかし、コンピュータ２、６、７、および１６の機能性は一般に１つまたは複数のコンポーネント・デバイスによって実装可能であることに留意されたい。たとえば、ユーザ・コンピュータ６の機能性は実際には、ネットワーク１５に通信インターフェースを提供する汎用コンピュータと、スマート・カードなどの個別ユーザ・デバイスとの間に分散することができる。このような個別デバイスは、クレデンシャルおよび暗号ソフトウェアのための安全な記憶域を提供することができ、必要なときに有線または無線リンクを介してユーザ・コンピュータに接続することができる。
【００５１】
この実証例では、システム１はアクセス制御シナリオで使用される。検証者コンピュータ７は、サービス・プロバイダ（ＳＰ）によって操作される。ユーザ・コンピュータ６を操作するユーザは、制限付きサービスへのアクセスを要求するために、ネットワーク１５によりＳＰコンピュータ７に接続することができる。サービスにアクセスするために、ユーザは、発行者２から入手した暗号クレデンシャルの所有を実証しなければならない。ＳＰコンピュータ７は、提示されたクレデンシャルが有効であることを検証しなければならない。これは、そのクレデンシャルが発行者２によって維持されている有効なクレデンシャルの集合のうちの１つであることを確認することを伴う。これは、暗号アキュムレータ構造を使用して達成される。まず、ユーザ・プライバシが最優先の関心事ではない状況でアキュムレータベースのシステムの動作を考慮する。すなわち、ユーザは、有効なクレデンシャルの所有を証明する必要があるが、その他のおそらくアイデンティティを明らかにする情報がこのプロセスによって使用可能になることについては心配しない。この初期アキュムレータ構造の基礎となるアルゴリズムについては、以下に定義されるが、Boneh、Gentry、およびWatersによるブロードキャスト暗号化方式に部分的に基づくものである（2005年、Springer発行、Advancesin Cryptology - CRYPTO 2005、Lecture Notes in ComputerScienceの3621巻、258〜275ページ掲載のBoneh、Gentry、およびWatersによる「Collusion Resistant BroadcastEncryption with Short Ciphertexts and Private Keys」を参照されたい）。特に、説明すべき構造におけるアキュムレータ計算は、参照された方式で暗号化鍵が生成される方法に関連し、証人計算は、参照された方式で復号鍵が生成される方法に関連する。
【００５２】
まず、クレデンシャルが最初に発行者コンピュータ２によってユーザに対して発行される、システムの動作における予備段階について考慮する。発行者コンピュータ２の動作における主要ステップは図２の流れ図に示されている。（一般に、クレデンシャルの発行はオフラインで実行することができるか（たとえば、ユーザに対して発行されたスマート・カード上で供給される）、ユーザによる正常な適用後にネットワーク１５を介してオンラインで発行することができるか、またはその両方であることに留意されたい。図２は、発行プロセスの簡略化を表しているが、関連の動作原理はこの図から理解することができる。）このセットアップ・プロセスはステップ２０から始まり、そこでクレデンシャル管理ロジック３はアキュムレータの動作で使用すべき様々なパラメータを生成する。このパラメータ・セットアップ・プロセスは、ロジック３によって実装される以下のアルゴリズムによって定義される。
【００５３】
ＡｃｃＧｅｎ（１k，ｎ）： ＢＭＧｅｎ（１k）を実行して、双線形マップｅ：Ｇ×Ｇ→ＧTのセットアップｐａｒａｍｓBM＝（ｑ，Ｇ，ＧT，ｅ，ｇ）を入手する。
【００５４】
ランダム値γ∈Ｚqをピックする。安全なシグニチャ方式、たとえば、ＳＤＨ仮定に基づいて安全な上述のＢＢシグニチャ方式のための鍵のペアｓｋおよびｐｋを生成する。
【数３０】
、ｓｋA＝（ｐａｒａｍｓBM，γ，ｓｋ）、ａｃｃφ＝１、および
【数３１】
とする。
【００５５】
このプロセスでは、クレデンシャル管理ロジック３は秘密値γおよび群ジェネレータｇを使用して、群要素
【数３２】
を生成し、ここでｎは、アキュムレータ、すなわち、有効なクレデンシャルの集合内に「含む」べきクレデンシャルの定義済みの最大数である。これらは、以下に説明する通り、クレデンシャルにマッピングされる群要素である。加えて、ロジック３は、後述する通り、証人計算に使用される、補助群要素
【数３３】
を生成する。
【００５６】
次に、図２のステップ２１では、ロジック３は、群要素と発行すべきクレデンシャルとのマッピングを定義する。各クレデンシャルは、クレデンシャル内に定義される通し番号の形の識別子を有し、このマッピングはこれらの通し番号とそれぞれの群要素との間で定義される。ここでは、単純にするため、整数１〜ｎの集合によって通し番号を表すが、当然のことながら、数字と群要素との任意のマッピングに対応することができる。このため、通し番号ｉ∈｛１，２，３，．．．，ｎ｝を有する各クレデンシャルの場合、そのクレデンシャルはここでは群要素
【数３４】
にマッピングされる。
【００５７】
ステップ２２は、ユーザに発行すべきクレデンシャルの初期集合Ｃ（ｉ）のロジック３による生成を表している。これらは、最初にアキュムレータ内に含まれるクレデンシャルである。クレデンシャルは既知の方法で生成することができ、各クレデンシャルはそれぞれの通し番号ｉを含む。次に、ステップ２３では、ロジック３が以下のアルゴリズムによりクレデンシャルの初期集合に関するアキュムレータを生成する。
【００５８】
ＡｃｃＵｐｄａｔｅ（ｐｋA，Ｖ，ｓｔａｔｅU）： Ｖ⊂Ｕであるかどうかをチェックし、そうではない場合に⊥を出力する。このアルゴリズムは
【数３５】
を出力する。
【００５９】
したがって、暗号アキュムレータはここでは、群要素ｇiが有効なクレデンシャルの集合内のクレデンシャルにマッピングされるｉの値について群要素ｇn+1-iの積として生成される。したがって、実際に蓄積された群要素は、有効なクレデンシャルにマッピングされた要素ｇiに対してｉ値を介して関連付けられる。
【００６０】
図２のステップ２４では、クレデンシャル・ロジック３は、署名鍵ｓｋに基づくｇi｜｜ｉについて
【数３６】
およびシグニチャσiを計算することにより、アキュムレータ内の各クレデンシャルＣに関する証人を生成する。
【００６１】
したがって、各クレデンシャルiについて、アキュムレータ証人ｗは、群要素のそれぞれの異なる部分集合の積として計算される。この部分集合は、有効な集合内のクレデンシャルのｉ値に依存し、各証人が生成されるクレデンシャルのｉ値にも依存する。具体的には、群要素ｇiにマッピングされたそれぞれの有効なクレデンシャルについて、証人は、群要素ｇiが他の有効なクレデンシャルにマッピングされるｊのすべての値について群要素ｇn+1-j+iの積を含む。したがって、証人生成は、前に定義された補助群要素ｇn+2，．．．，ｇ2nを利用する。シグニチャσiは、関連クレデンシャルと対応する群要素とのマッピングを示す。証人は、ｗｉｔi＝（ｗ，σi，ｇi）として出力される。
【００６２】
ステップ２５では、各クレデンシャルＣ（ｉ）は、その関連証人ｗｉｔiとともに、ネットワーク１５を介して当該ユーザに送信される。次に、ステップ２６では、クレデンシャル・ロジック３は、ステップ２３で計算されたアキュムレータを配布者コンピュータ（複数も可）１６に送信することにより、暗号アキュムレータを公表する。配布者１６は、任意の接続コンピュータ６、７へのアクセスを可能にすることにより、ネットワーク１５上でアキュムレータを公表する。これで、アキュムレータ・セットアップの初期段階が完了する。
【００６３】
新しいクレデンシャルを発行し、古いクレデンシャルを発行者２によって取り消すことができると仮定すると、クレデンシャル・ロジック３は、有効なクレデンシャルの動的集合における変化を反映するようにアキュムレータを管理しなければならない。このアキュムレータ管理プロセスは、図３の簡易流れ図に表されている。ステップ３０は、定義された「エポック（epoch）」内で行われるクレデンシャルの発行および取り消しを表している。クレデンシャルが発行されるかまたは取り消されるたびに、クレデンシャル・ロジック３は、通し番号ｉとともにこの事実をメモリ４にログ記録する。次の更新プロセスは原則として、クレデンシャルが発行されるかまたは取り消されるたびに実行することができるが、更新は典型的に、一定の間隔をおいて、たとえば、毎日、定期的に実行される。このため、判断ステップ３１では、クレデンシャル・ロジック３は、現在のエポックが終了したかどうかをチェックし、終了していない場合、動作はステップ３０に戻る。しかし、各エポックの終了時には、動作はステップ３２に移行し、そこでロジック３は、有効なクレデンシャルの集合から追加／除去された各クレデンシャルについて説明するためにアキュムレータを更新する。次に、ステップ３３では、有効な集合における変化を反映するために、新たに発行されたクレデンシャルに関する証人を生成し、既存のクレデンシャルに関する古い証人を更新することにより、証人の集合が更新される。新たに発行されたクレデンシャルごとに、これらのプロセスは以下のアルゴリズムによって定義される。
【００６４】
ＡｃｃＡｄｄ（ｓｋA，ｉ，ａｃｃV，ｓｔａｔｅU）： 署名鍵ｓｋに基づくｇi｜｜ｉについて
【数３７】
およびシグニチャσiを計算する。このアルゴリズムは、ｗｉｔi＝（ｗ，σi，ｇi）、更新されたアキュムレータ値
【数３８】
、および状態
【数３９】
を出力する。
【００６５】
アキュムレータへのクレデンシャルｉの追加は、前のａｃｃ値に群要素ｇn+1-iを掛けることによって単純に達成されることが分かる。同様に、クレデンシャルｉの取り消しは、前のａｃｃ値を群要素ｇn+1-iで割ることによって単純に達成される。したがって、アキュムレータ更新は高速かつ効率的であり、複雑さは追加された／取り消されたクレデンシャルの数において線形である。新たに追加されたクレデンシャルに関する証人生成は上記の図２のものと同じである。既存の証人の更新は以下のように定義される。
【００６６】
ＡｃｃＷｉｔＵｐｄａｔｅ（ｐｋA，ｗｉｔi，Ｖw，ａｃｃV，Ｖ，ｓｔａｔｅU）： ｗｉｔiを（ｗ，σi，ｇi）として解析する。ｉ∈ＶおよびＶ∪Ｖw⊂Ｕである場合、
【数４０】
を計算する。更新された証人ｗｉｔ’iを（ｗ’，σi，ｇi）として出力する。そうではない場合、⊥を出力する。
【００６７】
所与のクレデンシャルの追加（または取り消し）に対応するために証人を更新することは単純に古い証人値に対して適切な群要素ｇn+1-j+iで乗算（または除算）することを必要とすることが分かる。これは単一乗算で達成できるので、証人更新も同じく高速かつ効率的であり、複雑さは証人あたりの変更の数において線形である。
【００６８】
図３に戻ると、ステップ３４では、発行者コンピュータ２のクレデンシャル・ロジック３は、ネットワーク１５上で公表するために、更新されたアキュムレータおよび証人を配布者コンピュータ（複数も可）１６に送信する。証人は、個々のユーザが必要なときに自分の特定のクレデンシャルに関する証人を識別できるようにするために何らかの形の識別タグで公表される。次に、動作は新しいエポックのためにステップ３０に戻る。
【００６９】
図４は、ユーザがその後、検証者コンピュータ７を介してオンライン・サービスにアクセスするために自分のクレデンシャルを使用したいと希望するときの手順を示している。この図は、図の左側のユーザ・コンピュータ６と右側の検証者コンピュータ７によって実行される主要ステップを示している。動作は、サービスへのアクセスを要求するためにユーザ・コンピュータ６が検証者コンピュータ７に接続したときに始まる。コンピュータ７の検証者ロジック１１は、ユーザのクレデンシャルを要求することによって応答する。この要求は、ユーザ・コンピュータ６の証明者ロジック８によって受信される。次に、証明者ロジックは、前に発行者２から入手し、メモリ９に保管されていたクレデンシャルＣ（ｉ）に関する証人ｗの現在の値をダウンロードするために配布者コンピュータ１６への接続を確立する。クレデンシャルは図３のステップ３２〜３４に応じて発行されているので、このステップは、アキュムレータにおけるすべての変化を説明するために必要である。更新された証人ｗはメモリ９に保管される。次に、証明者ロジック８は、前述の通り、通し番号ｉを含むクレデンシャルＣ（ｉ）を、上記で定義された完全証人ｗｉｔi（ｗ，σi，ｇi）とともに、検証者７に送信する。次に、検証者ロジック１１は同様に、そのときにメモリ１２に保管されているアキュムレータａｃｃVの現在の値をダウンロードするために配布者コンピュータ１６にアクセスする。次に、検証者ロジック１１は以下の検証プロトコルを実行する。
【００７０】
ＡｃｃＶｅｒｉｆｙ（ｐｋA，ｉ，ｗｉｔi，ａｃｃV）： ｗｉｔi＝（ｗ，σi，ｇi）を解析する。σiが検証鍵ｐｋに基づくｇi｜｜ｉについて有効なシグニチャであり、ｅ（ｇi，ａｃｃV）／ｅ（ｇ，ｗ）＝ｚである場合、受諾を出力する。そうではない場合、拒否を出力する。
【００７１】
このプロセスでは、検証者ロジック１１は、ユーザのクレデンシャルＣ（ｉ）および関連群要素ｇiの通し番号ｉについてシグニチャσiが有効であることをチェックする。（それらがマッピングする値とともにｇiに署名するためにこのシグニチャ方式を使用すると、ｇi値のマッピングを公表する必要性が回避され、したがって、検証中の大規模な公開パラメータを回避することに留意されたい。）また、検証者ロジック１１は、群要素ｇiが現在のアキュムレータａｃｃV内にあることを証人ｗが確認することをチェックする。これは、ユーザのクレデンシャルが有効であることを確認するものである。次に、検証者ロジック１１は、クレデンシャルが有効であると思われるかどうかに応じて、ユーザ・コンピュータ６がサービスにアクセスすることを許可するかまたは拒否する。
【００７２】
現在の証人およびアキュムレータ値の取り出しは図４ではアクセス・プロセスに統合されて示されているが、実際には、各当事者は単純にそれぞれの新しいエポックの開始時に定期的に新しい値を取り出すことができることに留意されたい。
【００７３】
上記の説明はアキュムレータおよび証人の高速かつ効率的な計算および更新による動的アキュムレータ構造に基づく非常に効率的なクレデンシャル検証システムを示していることが分かるであろう。たとえば、証人更新は、アキュムレータに対する変更の数において線形の乗算のみ（べき乗なし）を必要とし、いずれの秘密情報の知識も必要としない。したがって、一般に、証人は、ユーザ自身、発行者、または何らかの第三者によってユーザのために最新のものを保持することができる。しかし、証人更新は従来の方式のようにユーザが個別に実行することができ、好ましい諸実施形態ではそのシステムの効率を活用し、それによりすべての証人をメイン・メモリ内に実行可能に保持することができ、証人計算を中央で実行できるようにする。これは、上記の実施形態では発行者２によって行われる。代替例として、いずれの秘密鍵の知識もなしでブックキーピング情報Ｖwからアキュムレータ内に含まれる値ｉ∈Ｖについてすべての証人を更新することは可能であるので、証人更新は、ＡｃｃＷｉｔＵｐｄａｔｅを実行し、アキュムレータ状態ｓｔａｔｅUおよびブックキーピング情報ＶおよびＶwのみが与えられる信頼できない更新エンティティに対して効率的にオフロードすることができる。たとえば、図１の配布者コンピュータ１６は証人更新コンピュータとしてさらに機能することができる。有効な集合における変更後に発行者コンピュータ２によりアキュムレータを更新するときに、その集合内に残っているクレデンシャルに関する証人更新は、１つまたは複数のこのような配布者コンピュータ１６によって、全体的にまたはバッチ方式で実行することができる。
【００７４】
上記の基本方式は、完全匿名クレデンシャル取り消しシステムにおける動作のための基礎を提供するには十分効率的なものである。以下では、匿名クレデンシャル取り消しシステムの特に好ましい一実施形態を実装するために上記の基本システムに対して行う様々な変更について考察する。
【００７５】
隠し値が蓄積されたという効率的な証明
まず、ユーザがどの値を所有しているか（またはどのインデックスｉがユーザに割り当てられているか）を明らかにせずに、現在のアキュムレータ内に含まれる値をユーザが所有していることをユーザが証明できるようにする効率的なプロトコルについて考慮する。このセクションでは、アキュムレータ構造のためにこれを達成する効率的なプロトコルを示す。上記の実施形態では、上述の通り、それぞれに署名させ、次にユーザがｇiおよびシグニチャを検証者に提供することにより、群要素ｇ1，．．．，ｇnが認証される。この場合、シグニチャまたはｇi値を明らかにせずに証明者が「ユーザの」ｇi上のアキュムレータ発行者によるシグニチャを把握していることを証明することを要求する。このような証明は効率的である必要があり、特別なシグニチャ方式を必要とする。蓄積された値は証明されるだけであって、決して明らかにされないので、ｇiとともにｉに署名せずに行うことができる。このため、より効率的なシグニチャ方式および証明システムが可能になる。
【００７６】
前提条件。新鮮なｕ←Ｇ、秘密鍵ｓｋ←Ｚq、および公開鍵ｐｋ＝ｇskをピックすることにより、ｇiに署名するために使用されるシグニチャ方式をインスタンス化する。シグニチャは、２つの要素
【数４１】
および
【数４２】
で構成され、ｅ（ｐｋ・ｇi，σi）＝ｅ（ｇ，ｇ）であることをチェックすることによって検証される。
【数４３】
、ｓｋA＝（ｐａｒａｍｓBM，γ，ｓｋ）、および
【数４４】
はすでに説明したアキュムレータ動作によって生成されるものとする。また、コミットメントのために追加の
【数４５】
もピックする。ｇに対するｈおよびｕの離散対数は証明者にとって未知のものでなければならない。
【００７７】
知識の証明。任意のＶ⊂｛１，．．．，ｎ｝およびｉ∈Ｖについて、入力
【数４６】
および対応する証人ｗｉｔi＝（ｗ，σi，ｕi，ｇi）のときに、
【数４７】
であり、値ｉについて、証明者は以下の無作為化を実行する。
【００７８】
無作為に、ｒ、ｒ’、ｒ’’、ｒ’’’、ｏｐｅｎ∈Ｚqをピックし、
【数４８】
【数４９】
【数５０】
【数５１】
および
【数５２】
をそれぞれ計算する。次に、証明者は、以下のように証明する。
【数５３】
【００７９】
n-DHEおよびn-HSDHE仮定に基づいて、上記のプロトコルは、Ｇ’を値ｇiに無作為化解除できるようにする無作為化値ｒの知識の証明であり、ここでｉはａｃｃV内に蓄積され、すなわち、ｉ∈Ｖである。
【００８０】
匿名クレデンシャル方式（たとえば、匿名電子マネー、グループ・シグニチャ、匿名証明書システム、仮名システムなど）では、ユーザは、匿名性を保護する方法で使用可能な何らかの形のクレデンシャルを獲得する。2004年、Springer発行、Christianson他編集、Security Protocols Workshop、Lecture Notes inComputer Scienceの3957巻、20〜42ページ掲載のBangerter他による「A cryptographic framework for the controlled release of certifieddata」では、著者は、クレデンシャルで証明された情報の被制御リリースのための暗号フレームワークを示している。これは、ユーザに対して私的証明書（private certificate）を発行するためにCamenisch-Lysyanskaya（ＣＬ）シグニチャという特別なシグニチャ・プロトコルを使用する（2003年、Springer Verlag発行、I Cimato他編集、Security in CommunicationNetworks、Third International Conference、SCN 2002、LNCSの2576巻、268〜289ページ掲載のJanCamenischおよびAnna Lysyanskayaによる「A signature scheme with efficient protocols」を参照されたい）。私的クレデンシャル（ｃｅｒｔ）は、伝統的な証明書のように属性および属性に関するシグニチャで構成され、以下のようにより強力なシグニチャ方式が使用される。
ｃｅｒｔ＝（σ，ｍ1，．．．，ｍl）およびσ＝Ｓｉｇｎ（ｍ1，．．．，ｍl；ｓｋI）
【００８１】
（ｓｋI、ｐｋI）←ＩｓｓｕｅｒＫｅｙｇｅｎ（１k）は証明書発行者の鍵のペアとする。このフレームワークは、１）これらの値を明らかにせずに、コミットされた値上のシグニチャを入手できるようにする対話式証明書発行プロトコルＯｂｔａｉｎＣｅｒｔと、２）シグニチャ所有の知識に関する効率的なゼロ知識証明という２つのタイプのプロトコルをサポートする。
【００８２】
（ｍ1，．．．，ｍl）はデータ項目のリストを示し、Ｈ⊂Ｌ＝｛１，．．．，ｌ｝はデータ項目の部分集合を示すものとする。第１のプロトコルを使用すると、ユーザは、発行者がＨ内のデータ項目に関するいかなる情報も学習しないが、他のデータ項目、すなわち、Ｌ＼Ｈを学習するように、（ｍ1，．．．，ｍl）に関する証明書を入手することができる。
【００８３】
ユーザの私的証明書はユーザにとって私的なままになり、すなわち、他のどの当事者にも（全体として）決してリリースされず、属性情報をアサートするために証明書を使用する（示す）ときに、ユーザは、特定のプロパティを含む証明書を自分が把握している（持っている）ことを証明する。ユーザは、以下のように証明書の残りの部分の知識のみを証明しながら、特定の属性をリリースすることができる。
【数５４】
上記の証明では、
【数５５】
という属性値のみが明らかにされる。
【００８４】
上記のフレームワークを以下のように拡張する。Ｖはエポック情報ｅｐｏｃｈVを含むエポックに関する有効な証明書の集合とする。以前のように、証明書には固有の識別子ｉ（属性の１つとしてそれに埋め込まれる）および証人ｗｉｔiが割り当てられる。ここでは、ｉ∈Ｖである場合のみ、ユーザが取り消されない証明書を所有することを検証者に対して証明できることを要求する。これは、ユーザのクレデンシャルに埋め込まれた識別子が現在のエポックについて有効なものであることをユーザに証明させることによって達成される。したがって、証明に携わる前に、ユーザは自分の証人を更新する必要があり、両方の当事者（ユーザと検証者）はＶについて最も最新のエポック情報ｅｐｏｃｈVを入手する必要がある。好ましいクレデンシャル取り消しシステムは、以下のように、更新されたIssuerKeygenおよびObtainCertプロトコル、取り消しを管理するための新しいアルゴリズムであるUpdateEpochおよびUpdateWitness、ならびに証人ｗｉｔiの所有の証明を可能にする新しい述語VerifyEpochのためのゼロ知識証明システムに基づくものである。
【００８５】
ＩｓｓｕｅｒＫｅｙｇｅｎ（１k；ｎ）は、ｎ個までの証明書を発行するための発行者の鍵のペア（ｓｋI，ｐｋI）、エポック情報ｅｐｏｃｈφ、およびｓｔａｔｅφを作成する。
【００８６】
【数５６】
は、ユーザが発行者から私的証明書ｃｅｒｔiを入手できるようにする。発行者は、ユーザの証人ｗｉｔi、更新されたエポック情報
【数５７】
、および
【数５８】
を計算し公表する。
【００８７】
ＵｐｄａｔｅＥｐｏｃｈ（Ｖ，ｓｔａｔｅU）は、Ｖ⊂Ｕである場合にエポック情報ｅｐｏｃｈVを出力する。そうではない場合、⊥を出力する。
【００８８】
ＵｐｄａｔｅＷｉｔｎｅｓｓ（ｗｉｔi，ｅｐｏｃｈV，ｓｔａｔｅU）は、Ｖ⊂Ｕである場合に更新された証人ｗｉｔ’iを出力する。そうではない場合、⊥を出力する。
【００８９】
証明書ｃｅｒｔiおよび対応する最新の証人ｗｉｔiを把握しているユーザは、以下のように新しい述語VerifyEpochを使用して、現在のエポックに関する証明書の所有およびその妥当性を検証者に対して証明することができる。ユーザの秘密の入力はｃｅｒｔiである。このプロトコルの共通入力は、発行者の公開鍵ｐｋI、エポック情報ｅｐｏｃｈV、および証明ステートメントの指定（これは証明書について明らかにされた情報を含む）である。以下の例では、ユーザは、メッセージの残りの部分を明らかにしながら、最初のｌ個のメッセージを秘密に保持することを選択する。
【数５９】
【００９０】
シグニチャ方式。以下の実施形態では、証明をより効率的なものにするためにクレデンシャルにｇiを含めることにより、ｇiに対するｉのマッピングが暗黙のものになる。したがって、ｇi値は、証明書ｉｄ ｉを表すために私的証明書とアキュムレータの両方で使用される。これには、秘密の指数γiを把握せずに検証を可能にするために上記で示したシグニチャ方式を拡張することが必要である。
１．署名者は、ｇ，ｈ，ｈ0，ｈ1，．．．，ｈl，ｈl+1←Ｇを作成し、鍵ｘ∈Ｚqおよびｙ＝ｈxを作成する。
２．次に、署名者は、シグニチャ内で可能にするリスト
【数６０】
を公表する。
３．署名者は、ｃ，ｓ←Ｚ*qをピックし、シグニチャを
【数６１】
として計算する。
４．メッセージ
【数６２】
上のシグニチャ（σ，ｃ，ｓ）は、
【数６３】
がｇi値のリスト内にあることをチェックし、
【数６４】
であることをチェックすることによって検証される。
（この場合の最後のステップにおける
【数６５】
がｇi値のリスト内にあることのチェックは、上記の実施形態のように後でｇi上のシグニチャ／認証符号（authenticator）で置き換えられる。）
【００９１】
変更された構造では、発行者コンピュータ２のクレデンシャル管理ロジック３によって実行されるセットアップ・プロセス（図２のステップ２０に対応）は以下のように定義される。
ＩｓｓｕｅｒＫｅｙｇｅｎ（１k，ｎ）。（対称形の）双線形マップｅ：Ｇ×Ｇ→ＧTのパラメータｐａｒａｍｓBM＝（ｑ，Ｇ，ＧT，ｅ，ｇ）を生成するためにＢＭＧｅｎ（１k）を実行する。追加の基数
【数６６】
およびｘ，ｓｋ，γ←Ｚqをピックし、ｙ＝ｈxおよびｐｋ＝ｇskを計算する。（相互に対するｇ、ｈ、
【数６７】
、およびｕの離散対数は互いに未知である。）ｇ1，．．．，ｇn，ｇn+2，．．．，ｇ2nを計算するが、ここで
【数６８】
および
【数６９】
である。
【数７０】
、ｅｐｏｃｈφ＝（ａｃｃφ＝１，φ）、およびｓｔａｔｅφ＝（φ，ｇ1，．．．，ｇn，ｇn+2，．．．，ｇ2n）を出力する。
【００９２】
ユーザ証明書および証人の問題（図２のステップ２２、２４、および２５に対応）は以下のように定義される。
【数７１】
ユーザ（ユーザ・コンピュータ６の証明者ロジック８）は発行者から証明書ｃｅｒｔiを入手するために以下のプロトコルを実行する。
１．ユーザは、無作為にｓ’∈Ｚ*qを選択し、
【数７２】
を計算し、Ｘを発行者に送信する。
２．ユーザは（証明者として）発行者を（ここでは検証者として）
【数７３】
という証明に従事させるが、これはＸが正しく形成されることを発行者に確信させることになる。
３．発行者は、ｅｐｏｃｈVを（ａｃｃV，Ｖ）として、ｓｔａｔｅUを（Ｕ，ｇ1，．．．，ｇn，ｇn+2，．．．，ｇ2n）として解析する。次に、発行者は、
【数７４】
および
【数７５】
を計算する。
４．発行者は、無作為にｃ，ｓ’’∈Ｚ*qを選択し、
【数７６】
を計算する。
５．発行者は、
【数７７】
および
【数７８】
を計算し、ｗｉｔi＝（σi，ｕi，ｇi，ｗ，Ｖ∪｛ｉ｝）を設定する。
６．発行者は、
【数７９】
をユーザに送信し、ｗｉｔi、
【数８０】
および
【数８１】
を出力する。
７．ユーザは、入手した証明書を検証し、ｃｅｒｔi＝（σ，ｃ，ｍ1，．．．，ｍl，ｇi，ｓ＝ｓ’＋ｓ’’，ｉ）を出力する。
【００９３】
図２のステップ２３に対応するアルゴリズムは以下のように示される。
ＵｐｄａｔｅＥｐｏｃｈ（Ｖ，ｓｔａｔｅU）： Ｖ⊂Ｕであるかどうかをチェックし、そうではない場合に⊥を出力する。このアルゴリズムは、ｃｅｒｔiの所有、ｉ∈Ｖを証明するためにｅｐｏｃｈVを作成する。
【数８２】
とし、ｅｐｏｃｈV＝（ａｃｃV，Ｖ）を出力する。
【００９４】
図３のステップ３３に対応する古い証人の更新は以下のように定義される。
ＵｐｄａｔｅＷｉｔｎｅｓｓ（ｗｉｔi，ｅｐｏｃｈV，ｓｔａｔｅU）：
【数８３】
である場合に⊥で打ち切る。そうではない場合、ｗｉｔiを（σi，ｕi，ｇi，ｗ，Ｖw）として解析する。
【数８４】
とする。このアルゴリズムは、ｗｉｔ’iを（σi，ｕi，ｇi，ｗ’，Ｖw）として出力する。
【００９５】
図５は、ユーザがその後、関連証人ｗｉｔi＝（σi，ｇi，ｕi，ｗ，Ｖw）とともに自分の匿名クレデンシャルｃｒｅｄi＝（σ，ｃ，ｍ1，．．．，ｍl，ｇi，ｓ，ｉ）を使用したいと希望するときにこの実施形態のユーザ・コンピュータ６と検証者コンピュータ７との間で行われる対話を示している。それぞれの新しいエポックの開始時に、各当事者６、７は、アキュムレータ内の介在変化を説明するために更新された値を配布者コンピュータ１６からダウンロードする。具体的には、証明者ロジック８はユーザのクレデンシャルｃｒｅｄiに関する現在の証人値ｗiを入手し、検証者ロジック１１は現在のアキュムレータ値を含む現在公表されているｅｐｏｃｈV＝（ａｃｃV，Ｖ）を入手する。その後、ユーザのアクセス要求に応答して、検証者ロジック１１は証明者ロジック８に検証要求を送信する。次に、証明者ロジックは、次の証明で使用すべき様々なパラメータを定義する。具体的には、証明者ロジックは、それぞれρおよびｒをコミットするために、ρ，ρ’，ｒ，ｒ’，ｒ’’，ｒ’’’←Ｚqをピックし、オープニングのｏｐｅｎ，ｏｐｅｎ’←Ｚqをピックする。次に、証明者ロジックは、コミットメント
【数８５】
【数８６】
ならびに目隠し値
【数８７】
【数８８】
【数８９】
【数９０】
および
【数９１】
を計算する。次に、証明者ロジックは、Ｃ、Ｃ’、Ａ、Ｇ’、Ｗ’、Ｓ’、およびＵ’を検証者に送信する。次に、証明者ロジック８および検証者ロジック１１は、ゼロ知識（ＺＫ）検証プロトコルを実装するために通信する。このプロトコルの共通入力は、発行者の公開鍵ｐｋI、エポック情報ｅｐｏｃｈV、および証明ステートメントの指定（これは証明書について明らかにされた情報を含む）である。以下の例では、ユーザは、メッセージの残りの部分を明らかにしながら、最初のｌ個のメッセージを秘密に保持することを選択する。
【数９２】
【００９６】
n-HSDHEおよびn-DHE仮定に基づいて、上記のプロトコルは、ｉ∈Ｖになるような（ｍ1，．．．，ｍl，ｇi）上の適応シグニチャの知識の証明である。
【００９７】
上記のプロセスにより、ユーザは、検証者に対して他のいずれの情報も明らかにせずに有効なクレデンシャルの所有を証明することができ、完全な匿名性とトランザクションのリンク不能性を維持することができる。費用のかかる計算を必要とする前の提案とは異なり、上記のシステムは計算上、効率が良く、とりわけ、非常に効率的な証人更新を提供する。多数のユーザを含む取り消しシステム（電子ＩＤ（e-ID）、電子チケット（e-ticket）などの導入によって構想される電子トークンベースのシステムなど）では、エポックあたりの取り消しの数が非常に大きくなる可能性がある。リソース制約形ユーザ・デバイスは典型的に、このような変更に対応するために必要な計算を処理することができない。しかし、上記のシステムでは、単一機関（発行者である場合もあれば、そうではない場合もある）によって更新を処理することは計算的に実行可能であり、それにより、多数のユーザを含むプライバシ保護システムにおいて取り消しのための動的アキュムレータの採用が可能になる。ユーザ・グループに関する証人を更新する役割を担う証人更新エンティティが複数存在することも可能である。たとえば、全国的な電子ＩＤシステムでは、郡ごとまたは都市ごとに証人更新を実行することができる。これは公開パラメータのみを必要とし、更新機関はそれぞれのグループ内のユーザについて証人更新を正しく計算する役割を担うだけである。証人更新エンティティの１つによる悪意のある挙動は、（それらが公開パラメータのみを必要とするので）システム・セキュリティを破壊しないが、単純にサービスの妨害に至る可能性がある。すなわち、証人が正しく計算されない（アキュムレータ内の最新の変更を反映しない）場合、ユーザが自分のクレデンシャルの妥当性を証明するのを妨げることになるであろう。この場合、ユーザは、有効な証人更新を入手し、証人更新エンティティの不正行為を通知するために、発行機関に報告することができる。したがって、従来のシステムと比較して、ユーザははるかに少ない計算を行うだけでよく、更新機関は１桁少ない計算を行うだけでよい。計算上の複雑さという負担をユーザから発行機関などのより強力な当事者に移管することにより、携帯電話またはスマート・カードなどのデバイスを使用してユーザが検証者とのトランザクションに携わるモバイル・シナリオで効率的な証明書取り消し状況チェックを実行することができる。
【００９８】
当然のことながら、上記の模範的な諸実施形態に対して多くの変更を行うことができることが認識されるであろう。たとえば、アキュムレータなどの公表は、独立した配布者１６ではなく発行者２によって実行することができ、上記の諸実施形態において単一コンピュータによって表されるコンポーネントは実際には分散コンピューティング・システムの２つ以上のコンピュータによって実装することができる。加えて、本発明の諸実施形態は、当然のことながら、暗号クレデンシャル以外のデータ項目にも適用することができる。効率をさらに改善するための追加の変更については以下に説明する。
【００９９】
上記の構造では、ＡｃｃＧｅｎアルゴリズムは、ｓｔａｔｅU＝（Ｕ，ｇ1，．．．，ｇn，ｇn+2，．．．，ｇ2n）を定義し、ここでＵはこれまでにアキュムレータに追加された（が、その後、除去された可能性がある）すべての要素を追跡するブックキーピング情報である。この状態の残りの部分は静的である。次に、ｓｔａｔｅUのサイズを削減する変更について説明する。上記の構造における公開パラメータのサイズは蓄積する必要がある可能性のある値の数に関する推定上限において線形である。この上限が推定するのが困難なものであるシナリオでは、過大評価は費用のかかる問題になる可能性がある。しかし、所与の時点で
【数９３】
より大きい値を決して蓄積しないという特別な場合には、このコストを
【数９４】
に下げることができる。アキュムレータ・パラメータの遅延評価によりこれを達成する。
【数９５】
は最大蓄積値とする。値ｉ∈Ｖの場合、（１）アキュムレータにｉを追加するための値ｇn+1-i、（２）アキュムレータ内のメンバシップを検証するための値ｇi、および（３）証人を計算し更新するためのｊ∈Ｖ＼Ｖw）∪（Ｖw＼Ｖ）の場合の値ｇn+1-j+iを必要とする。すべてのｊ∈Ｖ∪Ｖwの場合にｊは
【数９６】
より小さいことに留意されたい。値
【数９７】
はこれらの演算のすべてについて十分であると主張する。明らかに、最初の２つの要件は満たされている。その上、ｊ＞ｉである場合、
【数９８】
である。そうではない場合、１＜ｊ＜ｉかつ
【数９９】
である。これは第３の要件を確立するものである。上記の取り消し方式のＯｂｔａｉｎＣｅｒｔプロトコルでは、
【数１００】
は１だけ増加し、欠落しているアキュムレータ・パラメータがｓｔａｔｅUに追加される。
【数１０１】
であることに留意されたい。次に、更新された状態を使用して、エポック情報ｅｐｏｃｈVおよび証人ｗｉｔiを更新する。本発明の範囲を逸脱せずに、上記の諸実施形態に対してその他の多くの変更及び修正を行うことができる。
【技術分野】
【０００１】
本発明は、一般に、データ処理システム内の暗号クレデンシャル（cryptographiccredential）などのデータ項目の検証に関する。データ処理システム内でこのような検証プロセスを容易にするための方法、装置、およびコンピュータ・プログラムが提供される。
【０００２】
データ処理システムに対して何らかの当事者に関連するデータ項目に関して何らかの形の検証プロセスを実行する必要がある場合が多い。たとえば、ある当事者がデータ項目の所有あるいは有効または本物のデータ項目の所有をそのシステムの他の当事者に対して証明することが必要である場合がある。このような証明は、匿名性およびユーザ・プライバシを全般的に保護するために、データ項目自体を開示しないかあるいはデータ項目または証明側当事者に関するその他の情報をまったく明らかにしないような方法で行う必要がある場合もある。一般的な例は暗号クレデンシャルによって提供される。暗号クレデンシャルとは、典型的に、信頼できる当事者（「発行者（issuer）」）によってユーザに発行される、暗号シグニチャ、証明書、またはその他の暗号トークンである。このクレデンシャルは、その後、そのクレデンシャルが発行された情報の証明として、ユーザと他の当事者（「検証者（verifier）」、これは発行者である場合もあれば、そうではない場合もある）との間の通信で使用することができる。典型的なシナリオは、ユーザがデータ通信ネットワークを介してリモート・サーバに接続し、クレデンシャルを使用して、何らかの制限付きサービスまたはその他のリソースにアクセスするための許可を実証することを含む。以下の考察は主に暗号クレデンシャルについて取り上げるが、同様の考慮事項は、それに関する証明を検証者に対して行う必要がある可能性がある、その他のデータ項目、たとえば、任意の秘密のデータに適用することができる。
【０００３】
データ項目の検証プロセスは、しばしば、そのデータ項目がデータ項目の定義済み集合のうちの１つであることを証明することを含む。たとえば、暗号クレデンシャルの場合、クレデンシャルが本物または有効なクレデンシャルのリスト上にあることを証明することが必要である場合がある。特に、限られた期間の間、発行されるかまたは発行後に他の何らかの理由で取り消されるので、クレデンシャルの妥当性は一時的なものである場合がある。前者の場合、満了日は、（たとえば、クレデンシャル内に暗号化されたデータのコンポーネントまたは「属性」の１つとして）クレデンシャルに含まれ、妥当性を保証するために検証者によってチェックされる可能性がある。しかし、後者の場合、予期せぬイベントがクレデンシャルの早期取り消し（無効化）を要求する可能性がある場合、検証者は妥当性を確認するために発行者（またはその他の信頼できる当事者）から追加の情報を要求する。たとえば、ユーザが仕事を辞める場合、そのユーザが職場にアクセスできるようにしているクレデンシャルは無効にしなければならない。より痛切な一例は、違法購入のために悪意のある当事者によって脅かされ使用されたクレジットカード様のクレデンシャルを取り消す必要性である。このような場合、検証者は信頼できる当事者とともにクレデンシャルの妥当性をチェックする必要がある。
【０００４】
検証者がクレデンシャルの妥当性をチェックする必要性は、特にプライバシが主な関心事である場合、様々な問題を提起する。匿名性が問題ではないシナリオでは、クレデンシャルに関連する通し番号などの識別子はトランザクション中に検証者に対して明らかにすることができる。その場合、検証者は、発行者によって定期的に公表される取り消されたクレデンシャルＩＤのリストに照らし合わせてこれをチェックすることができる。他の解決策は、検証者がオンライン発行者に証明書取り消し状況照会を送信することである。前者の解決策は、取り消された証明書のリストが非常に大きいものになる可能性があるので、通信上非効率的であり、後者の解決策は、発行機関が永続的にオンラインであることを要求する。どちらの解決策もすべての当事者がクレデンシャルＩＤを把握していることを必要とし、ユーザ・プライバシを破壊するものである。しかし、匿名クレデンシャル・システムでは、トランザクションを行うために必要な最小量の情報のみをユーザが開示するような方法で、ユーザ、発行者、および検証者間のトランザクションが実行されることを必要とする。その上、発行者はどのクレデンシャル属性が検証者に示されるのかを学習することができず、発行者および検証者はユーザ・トランザクションをリンクすることができない。匿名クレデンシャル・システムは、ユーザの匿名性とトランザクションのリンク不能性（unlinkability）を保護することを目指しているので、発行者および検証者はトランザクション中に証明書ＩＤを学習することができず、代替の取り消し状況チェック技法が必要である。
【０００５】
上記の問題に対処するための既知の技法の１つでは暗号アキュムレータ（cryptographic accumulator）を使用する。暗号アキュムレータは、入力の大きい集合を単一の短い出力、すなわち、アキュムレータにハッシュできるようにするものである。所与の入力が本当にアキュムレータに含まれるという証拠は、アキュムレータ証人（accumulator witness）によって提供される。たとえば、アキュムレータ（ＡＣＣ）が、入力ｘ1〜ｘnの場合にＦ（ｘ1，．．．，ｘn）＝ＡＣＣによって定義される場合、所与の入力ｘiがＡＣＣに含まれることを証明するには、証人ｗiと、Ｖ（ｘi，ｗi）＝ＡＣＣになるような検証関数Ｖの存在が必要である。ｘyがアキュムレータに含まれない場合にＶ（ｘy，ｗy）＝ＡＣＣになるようなｗyを計算することが実行不可能であるという特徴によってセキュリティが保証される。上述のシナリオで適用されると、すべての現在有効なクレデンシャルの通し番号が蓄積され、その結果のアキュムレータが公表される。次にユーザは、自分の証人を使用して、自分のクレデンシャルの通し番号が公表されたアキュムレータに含まれることを（ゼロ知識で）証明することによって、自分のクレデンシャルが依然として有効であることを検証者に対して実証することができる。このようなシステムは、2004年、Springer Verlag発行、Matthew K. Franklin編集、Advances in Cryptology- CRYPTO 2004、LNCSの3152巻、41〜55ページ掲載のBoneh他による「Short group signatures」ならびに2002年、Springer Verlag発行、Moti Yung編集、Advances in Cryptology - CRYPTO 2002、LNCSの2442巻、61〜76ページ掲載のCamenischおよびLysyanskayaによる「Dynamic accumulators and application to efficient revocation ofanonymous credentials」に記載されている。しかし、これらの解決策の欠点は、ユーザが自分のアキュムレータ証人を更新する必要があり、更新には新たに取り消されたクレデンシャルごとに少なくとも１回のモジュラべき乗（modular exponentiation）を必要とすることである。典型的な適用例では多数の取り消されたクレデンシャルが存在する可能性があるので、これらの解決策は相当な計算（および通信）コストを発生し、特に、スマート・カードなどのリソース限定ユーザ・デバイスが処理できるものを大幅に上回るコストを発生する。たとえば、上記のCamenischおよびLysyanskayaの文献では、動的アキュムレータを紹介し、匿名クレデンシャル・システムにおける取り消しならびにアイデンティティ・エスクローおよびグループ・シグニチャに対するその適用性を示している。提案されたアキュムレータならびにユーザ証人の更新は、システムに追加されたかまたはシステムから取り消されたユーザの数において線形の複数回のべき乗を必要とする。このアキュムレータは、2007年、Springer発行、JonathanKatzおよびMoti Yung編集、ACNS、Lecture Notes in Computer Scienceの4521巻、253〜269ページ掲載のJiangtaoLi他による「Universal accumulators with efficientnonmembership proofs」において、値が蓄積されていないという証人および証明を紹介して、拡張されている。
【０００６】
動的アキュムレータは、2005年、Springer発行、AlfredMenezes編集、CT-RSA、Lecture Notesin Computer Scienceの3376巻、275〜292ページ掲載のLan Nguyenによる「Accumulators from bilinear pairings and applications」において、双線形ペアリング（bilinearpairing）から構築される。このシステムを匿名クレデンシャル・システムに適用すると、自分のクレデンシャルの妥当性を証明するために各ユーザが保管する必要のある非常に大きいシステム・パラメータ（蓄積可能な値の数において線形の複数の要素）が発生する。また、このアキュムレータが安全ではなく、いずれの当事者も秘密の知識がなければ匿名識別プロトコルに成功できないことは、2005年、CT-RSA 05におけるZhangおよびChenによる「Cryptanalysis and improvement of anID-based ad-hoc anonymous identification scheme」において指摘されている。その上、証人を更新するにはイベントあたり１回のべき乗を要し、したがって、効率的ではない（この論文では、著者は、双線形マップおよび楕円曲線群に関して時々行われるように、代数群用の基本演算として加算を使用し、乗算を作成している（上記のNguyenの文献を参照されたい））。
【０００７】
バッチ更新のための動的アキュムレータは、2007年、Springer発行、SihanQing他編集、ICICS、Lecture Notes inComputer Scienceの4861巻、98〜112ページ掲載のPeishun Wang他による「A new dynamic accumulator for batch updates」に提案されている。多くの証人更新を逸したユーザは、発行者に対して更新情報を要求し、１回の乗算で自分の証人を更新することができる。しかし、この方式は、クレデンシャル取り消しなどの適用例には使用可能にはならないであろう。たとえば、クレデンシャルの取り消しのためにアキュムレータの使用に必要とされるように、アキュムレータに含まれる要素の知識の効率的証明をどのように達成することになるかは明白ではない。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】2004年、Springer Verlag発行、Matthew K. Franklin編集、Advances in Cryptology - CRYPTO 2004、LNCSの3152巻、41〜55ページ掲載のBoneh他による「Short group signatures」
【非特許文献２】2002年、Springer Verlag発行、Moti Yung編集、Advances in Cryptology - CRYPTO 2002、LNCSの2442巻、61〜76ページ掲載のCamenischおよびLysyanskayaによる「Dynamic accumulators and application to efficient revocation ofanonymous credentials」
【非特許文献３】2007年、Springer発行、Jonathan KatzおよびMoti Yung編集、ACNS、LectureNotes in Computer Scienceの4521巻、253〜269ページ掲載のJiangtaoLi他による「Universal accumulators with efficientnonmembership proofs」
【非特許文献４】2005年、Springer発行、Alfred Menezes編集、CT-RSA、Lecture Notes in Computer Scienceの3376巻、275〜292ページ掲載のLan Nguyenによる「Accumulators from bilinearpairings and applications」
【非特許文献５】2005年、CT-RSA 05におけるZhangおよびChenによる「Cryptanalysis and improvement of anID-based ad-hoc anonymous identification scheme」
【非特許文献６】2007年、Springer発行、Sihan Qing他編集、ICICS、Lecture Notes in Computer Scienceの4861巻、98〜112ページ掲載のPeishun Wang他による「A new dynamic accumulatorfor batch updates」
【非特許文献７】2005年、Springer発行、Lecture Notes in Computer Scienceの3494巻、2005年5月22〜26日デンマークのオルフス開催の24thAnnual International Conference on the Theory and Applications of CryptographicTechniques、Advances in Cryptology - EUROCRYPT 2005の会議録、Cramer編集、440〜456ページ掲載のBoneh他による「Hierarchical identity basedencryption with constant size ciphertext」
【非特許文献８】2004年、Springer発行、Christian CachinおよびJan Camenisch編集、EUROCRYPT、Lecture Notes in Computer Scienceの3027巻、56〜73ページ掲載のDan BonehおよびXavier Boyenによる「Short signatures withoutrandom oracles」
【非特許文献９】2007年、Springer発行、Tatsuaki OkamotoおよびXiaoyunWang編集、Public Key Cryptography、Lecture Notes in Computer Scienceの4450巻、1〜15ページ掲載のBoyenおよびWatersによる「Full-domain subgroup hiding andconstant-size group signatures」
【非特許文献１０】1997年3月、ETHチューリッヒ、TechnicalReport TR 260、Institute for Theoretical ComputerScience、Jan CamenischおよびMarkusStadlerによる「Proof systems for general statements aboutdiscrete logarithms」
【非特許文献１１】2004年、Springer Verlag発行、Matthew K. Franklin編集、Advances in Cryptology - CRYPTO 2004、LNCSの3152巻、56〜72ページ掲載のCamenischおよびLysyanskayaによる「Signature schemes and anonymous credentials from bilinear maps」
【非特許文献１２】2005年、Springer発行、Advances in Cryptology - CRYPTO2005、Lecture Notes in Computer Scienceの3621巻、258〜275ページ掲載のBoneh、Gentry、およびWatersによる「Collusion Resistant Broadcast Encryption with Short Ciphertexts andPrivate Keys」
【非特許文献１３】2004年、Springer発行、Christianson他編集、Security Protocols Workshop、Lecture Notes inComputer Scienceの3957巻、20〜42ページ掲載のBangerter他による「A cryptographic framework for the controlled release of certifieddata」
【非特許文献１４】2003年、Springer Verlag発行、I Cimato他編集、Security in CommunicationNetworks、Third International Conference、SCN 2002、LNCSの2576巻、268〜289ページ掲載のJanCamenischおよびAnna Lysyanskayaによる「A signature scheme with efficient protocols」
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明の一態様は、データ処理システム内でデータ項目の集合を示す暗号アキュムレータを提供するための方法を提供する。この方法は、
複数の群要素を生成することと、
前記集合内のデータ項目とそれぞれの群要素とのマッピングを定義することと、
集合内のデータ項目にマッピングされた群要素に関するそれぞれの群要素の積を含む暗号アキュムレータを生成することと、
データ処理システム内の暗号アキュムレータを公表すること
を含む。
【課題を解決するための手段】
【００１０】
本発明のこの態様を実施する方法は、暗号クレデンシャルなどのデータ項目の検証時に使用するための、特に、データ処理システム内のこのようなデータ項目の特定の集合を示すための高速かつ効率的なアキュムレータベースのシステムを提供することができる。これは、たとえば、データ処理システム内で使用中の本物または現在有効なデータ項目の集合を定義するために使用することができる。この効率により、本発明の諸実施形態がクレデンシャル取り消しに容易に適用可能になる。蓄積は高速であり、複雑さは集合内のデータ項目の数において線形である。アキュムレータ更新の複雑さは、変更の数、すなわち、集合に追加されたかまたは集合から除去されたデータ項目の数において線形である。また、このシステムは、アキュムレータ証人の高速かつ効率的な計算ならびに更新のための基礎を提供する。特に、以下に記載する諸実施形態における証人の計算は集合内のデータ項目の数において線形であり、各証人の更新は変更の数において線形である。したがって、証人更新は単一乗算で達成することができる。この計算上の複雑さの改善により、計算能力が限られているリソース制約形ユーザ・デバイスを伴うデータ処理システムで都合良く適用することができる。これについては以下に詳述する。その上、以下に例により実証する通り、このシステムは、クレデンシャル取り消しなどのプライバシの適用例に必要な集合のメンバシップを証明するための効率的な証明プロトコルのための基礎も提供する。
【００１１】
一般に、本発明が適用されるデータ項目は、それについて何らかの事実、たとえば、データ項目の妥当性、信憑性、または単純所有をアキュムレータを参照することによって検証者に対して証明しなければならないデータの任意の項目にすることができる。データ項目は、たとえば、アキュムレータによって示された集合内にデータ項目が含まれることを実証することにより、データ自体を明らかにせずに、検証者に対して証明すべき特性を備えた秘密のデータを含むことができる。しかし、典型的な適用例では、データ項目は暗号項目になり、特に、すでに述べた暗号クレデンシャルになる。
【００１２】
適用例に応じて、データ項目の集合は動的になる可能性があり、それにより、時間の経過につれて項目を集合に追加するかまたは集合から除去するかあるいはその両方を行うことができる。群要素に対するデータ項目のマッピングおよびおそらく群要素の生成も、新しいデータ項目が動的集合に追加されるときに漸次実行することができる。また、適用例に応じて、集合から除去されたデータ項目に対して前にマッピングされた群要素は、新しいデータ項目に再割り当てされる場合もあれば、されない場合もある。いずれの場合も、動的集合の場合、暗号アキュムレータは、集合内容の変更を反映するために定期的に生成することができる。したがって、いつでもアキュムレータは、現在集合内にある項目にマッピングされた要素に関する群要素の積を含まなければならない。生成されると、アキュムレータは、データ項目のその後の検証にかかわるシステムのコンポーネントによる使用のために使用可能になるように、データ処理システム内で公表される。関連システム・コンポーネントに直接、アキュムレータを伝送することにより公表を実施することができるシステムを構想することもできる。しかし、より一般的には、システム内の１つまたは複数のデータ通信チャネルを介してアキュムレータへのアクセスを可能にすることにより公表が実施され、それにより、検証目的に必要なときにシステム・コンポーネントはアキュムレータにアクセスすることができる。
【００１３】
当業者であれば、代替例を構想することができるだろうが、以下に記載する好ましい諸実施形態のように、（少なくとも）秘密値γおよび群ジェネレータ（group generator）ｇを使用して各群要素を生成することができる。より具体的には、好ましい諸実施形態では、群要素は、ｉ∈｛１，２，３，．．．，ｎ｝の場合にそれぞれの要素
【数１】
を含み、ここでｎは集合内のデータ項目の定義済みの最大数である。（群要素は、後述する通り、システム内で使用するための追加のまたは「補助」値も含むことができる。）次に、集合内のデータ項目とそれぞれの群要素ｇiとの間でマッピングが定義される。これらの実施形態では、暗号アキュムレータは、群要素ｇiが前記集合内のデータ項目にマッピングされるｉの値について群要素ｇn+1-iの積を含む。したがって、蓄積された要素は、集合内の項目にマッピングされた要素ｇiに対してｉ値を介して関連付けられる。
【００１４】
群要素に対するデータ項目のマッピングは、暗号クレデンシャルの通し番号など、各データ項目に関連する数値識別子とそれぞれの群要素との間で定義することができる。この通し番号またはその他の識別子は理想的にはデータ項目自体に定義される。一部の実施形態では、このマッピングは、割り振られた群要素をデータ項目用の識別子として割り当てることによって定義することもできるであろう。
【００１５】
動的集合に関するアキュムレータを更新するプロセスと、データ項目に関する証人を生成し更新するプロセスについては、以下の詳細に説明する。しかし、簡単に言えば、好ましい実施形態では、データ項目に関する証人は群要素のそれぞれの異なる部分集合の積を含み、各証人に関する部分集合は前記集合内のデータ項目とその証人が生成されたデータ項目に依存する。これらの証人の計算および更新は高速かつ効率的である。特に、データ項目の集合内の変更を反映するための証人の更新は、理想的には単一乗算で行うことができる。
【００１６】
本発明の第２の態様は、データ処理システム内でデータ項目の集合を示す暗号アキュムレータを提供するための装置を提供する。この装置は、メモリと、本発明の第１の態様による方法を実行するように適合された制御ロジックとを含み、複数の群要素は前記メモリ内に保管される。
【００１７】
本発明の第３の態様は、それぞれがデータ通信ネットワークを介した通信用に適合されたユーザ・コンピュータ、検証者コンピュータ、およびデータ項目管理コンピュータを含む、データ処理システムを提供する。データ項目管理コンピュータは、前記ユーザ・コンピュータに関連するユーザ・データ項目を含むデータ項目の集合を示す暗号アキュムレータを提供するための本発明の第１の態様による方法を実行するように適合される。ユーザ・コンピュータは、暗号アキュムレータのために、前記ユーザ・データ項目と、そのユーザ・データ項目に対応する証人を保管する。ユーザ・コンピュータおよび検証者コンピュータは、暗号アキュムレータによって示された集合内のデータ項目に対応する証人に関するユーザ・コンピュータによる知識を証明する検証プロコトルを実装するためにネットワークを介した通信用に適合される。検証プロトコルは、好ましくは、ゼロ知識証明プロトコルである。
【００１８】
本発明の第４の態様は、本発明の第１の態様による方法をコンピュータに実行させるためのプログラム・コード手段を含むコンピュータ・プログラムを提供する。「コンピュータ」という用語は本明細書では最も一般的な意味で使用され、コンピュータ・プログラムを実装するためのデータ処理機能を有する任意のデバイス、コンポーネント、またはシステムを含むことが理解されるであろう。その上、本発明を実施するコンピュータ・プログラムは、１つの独立プログラムを構成するかまたはより大きいプログラムの１つの要素になる可能性があり、たとえば、コンピュータにロードするためのディスクまたは電子伝送などのコンピュータ可読媒体に実施して供給することができる。コンピュータ・プログラムのプログラム・コード手段は、直接または（ａ）他の言語、コード、または表記への変換、および（ｂ）異なる物質的形式による複製のいずれか一方または両方の後、当該方法をコンピュータに実行させるための１組の命令を任意の言語、コード、または表記で表した任意の表現を含むことができる。
【００１９】
一般に、本明細書では本発明の一態様の一実施形態に関連して特徴を説明するが、対応する特徴を本発明の他の態様の諸実施形態で示す場合もある。
【００２０】
次に、例として、添付図面に関連して本発明の好ましい諸実施形態について説明する。
【図面の簡単な説明】
【００２１】
【図１】本発明を実施するデータ処理システムの概略図である。
【図２】図１のシステムにおいて発行者コンピュータによって実行されるセットアップ手順を示す図である。
【図３】図１の発行者コンピュータのその後の動作を示す図である。
【図４】図１のシステムにおいてユーザ・コンピュータと検証者コンピュータとの間の対話を示す図である。
【図５】図１のシステムの好ましい実装例においてユーザ・コンピュータと検証者コンピュータとの間の対話を示す図である。
【発明を実施するための形態】
【００２２】
本発明を実施するデータ処理システムについて説明する前に、まず、説明すべき模範的な諸実施形態の動作時に使用されるビルディング・ブロックとして使用される様々な仮定および暗号ツールを提示する。
【００２３】
すべての整数ｃについて、すべてのｋ＞Ｋの場合に｜υ（ｋ）｜＜１／ｋｃになるような整数Ｋが存在する場合、関数υは無視してもよい。それを解くための入力のサイズについて確率的多項式時間（ｐ．ｐ．ｔ．）アルゴリズムがまったく存在しない場合、問題は困難（または至難）であると言われる。
【００２４】
双線形ペアリング。ＧおよびＧTは基本次数（prime order）ｑの群とする。マップｅ：Ｇ×Ｇ→ＧTは以下の特性を満足しなければならない。
（ａ）双線形性： ｅ（ａx，ｂy）ｔ＝ｅ（ａ，ｂ）x,yである場合、マップｅ：Ｇ×Ｇ→ＧTは双線形である。
（ｂ）非退化（non-degeneracy）： すべてのジェネレータｇ，ｈ∈Ｇについて、ｅ（ｇ，ｈ）はＧTを生成する。
（ｃ）効率： 双線形マップを生成するために（ｑ，Ｇ，ＧT，ｅ，ｇ）を出力する効率的なアルゴリズムＢＭＧｅｎ（１k）と、任意のａ，ｂ∈Ｇについてｅ（ａ，ｂ）を計算するための効率的なアルゴリズムが存在する。
【００２５】
セキュリティは以下の数論仮定に基づくものである。説明すべき諸実施形態におけるアキュムレータ構造はDiffie-Hellman Exponent仮定に基づくものである。クレデンシャルの非鍛造性はStrong Diffie-Hellman仮定に基づくものである。クレデンシャルの取り消しの場合、クレデンシャルに関するアキュムレータ証人の所有を証明する必要がある。この証明は、新しいHidden Strong Diffie-Hellman Exponent（SDHE）仮定に基づくものである。
【００２６】
定義１（n-DHE）。Diffie-Hellman Exponent（DHE）仮定： 基本次数ｑの群Ｇ内のn-DHE問題は、以下のように定義される。すなわち、
【数２】
とする。入力
【数３】
のときに、ｇn+1を出力する。
【００２７】
n-DHE仮定では、この問題は解決するのが困難であることを示している。
【００２８】
2005年、Springer発行、Lecture Notes in Computer Scienceの3494巻、2005年5月22〜26日デンマークのオルフス開催の24th Annual InternationalConference on the Theory and Applications of Cryptographic Techniques、Advances in Cryptology - EUROCRYPT 2005の会議録、Cramer編集、440〜456ページ掲載のBoneh他による「Hierarchical identity based encryption with constant size ciphertext」では、著者は、双線形マップについて定義されたBilinear Diffie-Hellman Exponent（BDHE）仮定を紹介している。この場合、相手方は
【数４】
を計算しなければならない。
【００２９】
補助定理１。双線形ペアリングｅ：Ｇ×Ｇ→ＧTを有する群Ｇに関するｎ−ＤＨＥ仮定は、同じ群に関するｎ−ＢＤＨＥ仮定によって暗示される。
【００３０】
BonehおよびBoyenは、2004年、Springer発行、ChristianCachinおよびJan Camenisch編集、EUROCRYPT、Lecture Notes in Computer Scienceの3027巻、56〜73ページ掲載のDan BonehおよびXavier Boyenによる「Short signatures withoutrandom oracles」において、Strong Diffie-Hellman仮定を紹介している。
【００３１】
定義２（n-SDH − 上記の文献「Short signatures withoutrandom oracles」を参照されたい）。入力
【数５】
のときに、（ｇ1/(x+c)，ｃ）を出力することは計算的に実行不可能である。
【００３２】
2007年、Springer発行、Tatsuaki OkamotoおよびXiaoyunWang編集、Public Key Cryptography、Lecture Notes inComputer Scienceの4450巻、1〜15ページ掲載のBoyenおよびWatersによる「Full-domain subgroup hiding and constant-size group signatures」では、著者は、メッセージが不明である状況においてＢＢシグニチャ（上記で参照した「Short signatures without random oracles」を参照されたい）の使用を可能にするためのHidden Strong Diffie-Hellman仮定を紹介している。HiddenStrong Diffie-Hellman Exponent（n-HSDHE）仮定と呼ぶ、Hidden Strong Diffie-Hellman仮定の変形を必要とする。この２つの仮定は今までのところ比較不能である。
【００３３】
定義３（n-HSDHE）。入力
【数６】
および
【数７】
のときに、新しいタプル｛ｇ1/(x+c)，ｇc，ｕc｝を出力することは計算的に実行不可能である。
【００３４】
既知の離散対数ベースのゼロ知識証明
共通パラメータ・モデルでは、離散対数に関するステートメントを証明するためにいくつかの既知の結果を使用する。このような証明に言及する場合、離散対数の知識の様々な証明および離散対数に関するステートメントの妥当性証明のために、CamenischおよびStadlerによって紹介された表記法に従う（1997年3月、ETHチューリッヒ、Technical Report TR 260、Institute forTheoretical Computer Science、Jan CamenischおよびMarkus Stadlerによる「Proof systems for generalstatements about discrete logarithms」）。たとえば、
【数８】
は、
【数９】
が同じ次数を有するいくつかの群Ｇ＝〈ｇ〉＝〈ｈ〉および
【数１０】
の要素である場合に、「ｙ＝ｇαｈβおよび
【数１１】
が成り立つような整数α、β、およびδに関する知識のゼロ知識証明」を示している。（ｙおよび
【数１２】
という表現内のいくつかの要素が等しいことに留意されたい。）規約は、値α、β、およびδはどの知識が証明されているかという量を示し（しかも秘密に保持され）、他のすべての値は検証者にとって既知であることである。ここで考慮するすべての群を含む基本次数群の場合、正常な証明者（prover）からこれらの量を抽出することができる知識抽出者（knowledgeextractor）が存在することは周知のことである。
【００３５】
効率的なプロトコルによるシグニチャ方式
説明すべきクレデンシャル・システムにおけるシグニチャ方式は、2004年、Springer Verlag発行、Matthew K. Franklin編集、Advances in Cryptology - CRYPTO 2004、LNCSの3152巻、56〜72ページ掲載のCamenischおよびLysyanskayaによる「Signature schemes and anonymous credentials from bilinear maps」に詳述されており、n-SDH仮定に基づいて安全であると証明されている。これは、ジェネレータｈ，ｈ0，ｈ1，．．．，ｈl，ｈl+1を有する基本次数ｑの非退化双線形マップｅ：Ｇ×Ｇ→ＧTを仮定する。署名者（signer）の秘密鍵はｘ∈Ｚqであり、公開鍵はｙ＝ｈxである。
【００３６】
メッセージ
【数１３】
上のシグニチャは、
【数１４】
をピックし、
【数１５】
を計算することによって計算される。このシグニチャは（σ，ｃ，ｓ）である。これは、
【数１６】
であるかどうかをチェックすることによって検証される。複数のメッセージ
【数１７】
は、
【数１８】
として署名することができ、
【数１９】
であるかどうかをチェックすることによって検証が行われる。
【００３７】
シグニチャの知識の証明
ここで、メッセージｍ1，．．．，ｍl∈Ｚq上のシグニチャ（σ，ｃ，ｓ）が与えられ、このようなシグニチャを本当に所有することを証明したいと希望していると仮定する。このために、
【数２０】
が既知ではなくなるように、値
【数２１】
で公開鍵を増強する必要がある。
【００３８】
シグニチャの知識は以下のように証明される。
１．ランダム値（random value）ｒ←Ｚqおよびｏｐｅｎ←Ｚqを選択し、コミットメント（commitment）
【数２２】
および目隠しシグニチャ（blinded signature）
【数２３】
を計算する。
２．以下の証明を計算する。
【数２４】
【００３９】
次に、説明すべき諸実施形態の理解を支援するために動的アキュムレータについていくつかの基本を紹介する。要素をそれに加える／それから削除する場合の計算コストがアキュムレータに含まれている要素の数とは無関係である場合、アキュムレータは動的である。安全なアキュムレータは、AccGen、AccAdd、AccUpdate、AccWitUpdate、およびAccVerifyというアルゴリズムで構成される。これらのアルゴリズムは、アキュムレータを管理する機関（「機関」）、ユーザ、および検証者によって使用される。（説明すべき好ましい諸実施形態のいくつかでは、これらのアルゴリズムのうちの特定のものは、信頼できない更新エンティティによって使用される場合もある。）
【００４０】
この機関は、AccGenアルゴリズムを使用して、アキュムレータ鍵のペア（accumulator key pair）（ｓｋA，ｐｋA）、アキュムレータａｃｃφ、および公開状態（publicstate）ｓｔａｔｅφを作成する。証人ｗｉｔiとともに、新しいアキュムレータ
【数２５】
および状態
【数２６】
を入手するために、AccAddアルゴリズムを使用して、アキュムレータａｃｃVに新しい値ｉを追加することができる。AccUpdateアルゴリズムを使用して、所与の集合の値Ｖに関するアキュムレータを計算することができる。
【００４１】
これらの演算全体を通して、ａｃｃVおよびｗｉｔiは一定のサイズである（蓄積された値の数とは無関係である）。この機関は、証人ｗｉｔiが作成されたときにアキュムレータに含まれている値およびアキュムレータの状況について何らかのブックキーピングを実行する。これらの集合はそれぞれＶおよびＶwとして示される。ブックキーピング情報は、公表され、証人を更新するためにのみ必要とされ、値がアキュムレータに含まれていることを検証するためには必要ではない。
【００４２】
アキュムレータが変化するたびに、古い証人は無効になる。しかし、ブックキーピング情報Ｖwからアキュムレータに含まれる値ｉ∈Ｖについてすべての証人を更新することは可能である。この更新は、既存のアキュムレータ・システムにおいて最も性能集約型の動作である。アキュムレータ状態ｓｔａｔｅUは、アキュムレータにこれまでに追加された（が、必ずしも現在のアキュムレータに含まれているわけではない）要素の集合であるブックキーピング情報Ｕも含む。これは、ＶおよびＶwの超集合である。
【００４３】
ユーザが現在のアキュムレータに関する値ｉについて更新された証人ｗｉｔ’iを入手した後、ユーザは、AccVerifyアルゴリズムを使用して、ｉがアキュムレータ内にあることをすべての検証者に対して証明することができる。
【００４４】
ＡｃｃＧｅｎ（１k，ｎ）は、アキュムレータ鍵のペア（ｓｋA，ｐｋA）、空のアキュムレータａｃｃφ（ｎ個の値まで蓄積するため）、および初期状態ｓｔａｔｅφを作成する。
【００４５】
ＡｃｃＡｄｄ（ｓｋA，ｉ，ａｃｃV，ｓｔａｔｅU）は、その機関がアキュムレータにｉを追加できるようにするものである。これは、ｉについて、証人ｗｉｔiとともに、新しいアキュムレータ
【数２７】
および状態
【数２８】
を出力する。
【００４６】
ＡｃｃＵｐｄａｔｅ（ｐｋA，Ｖ，ｓｔａｔｅU）は、値Ｖ⊂Ｕについて、アキュムレータａｃｃVを出力する。
【００４７】
ＡｃｃＷｉｔＵｐｄａｔｅ（ｐｋA，ｗｉｔi，Ｖw，ａｃｃV，Ｖ，ｓｔａｔｅU）は、ｗｉｔiが
【数２９】
に関する証人であり、ｉ∈Ｖである場合に、ａｃｃVに関する証人ｗｉｔ’iを出力する。
【００４８】
ＡｃｃＶｅｒｉｆｙ（ｐｋA，ｉ，ｗｉｔi，ａｃｃV）は、最新の証人ｗｉｔiおよびアキュムレータａｃｃVを使用して、ν∈Ｖであることを検証する。その場合、アルゴリズムは受諾し、そうではない場合、アルゴリズムは拒否する。
【００４９】
添付図面のうちの図１は、本発明を実施する第１のデータ処理システムの簡易概略図であり、システムの動作に関係する主なコンポーネントを示している。データ処理システム１は、データ項目、ここでは暗号クレデンシャルを管理し、説明すべきクレデンシャル検証プロセスで使用するための暗号アキュムレータを管理する役割を担う機関によって操作されるデータ項目管理コンピュータ２を含む。特に、この機関（ここでは「発行者」）は、暗号クレデンシャルをユーザに対して発行し、説明すべきアキュムレータを介してシステム内で有効なクレデンシャルを示す。発行者コンピュータ２は、以下に詳述するプロセスを実装するためのクレデンシャル管理ロジック３と、メモリ４と、通信インターフェース５とを含む。また、システム１は、発行者コンピュータ２から入手した暗号クレデンシャルを使用するためのユーザ・コンピュータ６と、説明すべきアキュムレータを参照することによりユーザ・クレデンシャルを検証するための検証者コンピュータ７も含む。ユーザ・コンピュータ６は、以下に記載する暗号プロセスを実装するための証明者ロジック８と、メモリ９と、通信インターフェース１０とを含む。検証者コンピュータ７は、以下に記載する暗号検証プロセスを実行するための検証者ロジック１１と、メモリ１２と、通信インターフェース１３とを含む。コンピュータ２、６、および７は、それぞれの通信インターフェースを介してデータ通信ネットワーク１５により通信することができる（ネットワーク１５は実際には、複数のコンポーネント・ネットワークあるいはインターネットワークまたはその両方を含むことができる）。加えて、システム１は、ここではネットワーク１５内に示され、すべてのコンピュータ２、６、７にとってアクセス可能な配布者コンピュータ１６を含み、その目的については以下に説明する。
【００５０】
発行者、ユーザ、および検証者コンピュータの制御ロジック３、８、１１は、以下に記載する暗号プロセスの適切なステップを実装するために構成される。一般に、この制御ロジックは、ハードウェアまたはソフトウェアあるいはそれらの組み合わせで実装することができ、ユーザ、検証者、および発行者デバイス２、６、７の正確な形式は説明すべきシステムの基本動作とはほとんど無関係である。しかし、この例では、これらのデバイスは汎用コンピュータで実装され、ユーザ・コンピュータ６はユーザＰＣであり、発行者および検証者コンピュータ２、７はユーザＰＣ６がネットワーク１５により接続可能なサーバであると仮定する。クレデンシャル管理ロジック３、証明者ロジック８、および検証者ロジック１１はここでは、記載されている機能を実行するようにホスト・コンピュータを構成するそれぞれのコンピュータ・プログラムによって実装される。適切なソフトウェアは、本明細書の記述から当業者にとって明らかになるであろう。しかし、コンピュータ２、６、７、および１６の機能性は一般に１つまたは複数のコンポーネント・デバイスによって実装可能であることに留意されたい。たとえば、ユーザ・コンピュータ６の機能性は実際には、ネットワーク１５に通信インターフェースを提供する汎用コンピュータと、スマート・カードなどの個別ユーザ・デバイスとの間に分散することができる。このような個別デバイスは、クレデンシャルおよび暗号ソフトウェアのための安全な記憶域を提供することができ、必要なときに有線または無線リンクを介してユーザ・コンピュータに接続することができる。
【００５１】
この実証例では、システム１はアクセス制御シナリオで使用される。検証者コンピュータ７は、サービス・プロバイダ（ＳＰ）によって操作される。ユーザ・コンピュータ６を操作するユーザは、制限付きサービスへのアクセスを要求するために、ネットワーク１５によりＳＰコンピュータ７に接続することができる。サービスにアクセスするために、ユーザは、発行者２から入手した暗号クレデンシャルの所有を実証しなければならない。ＳＰコンピュータ７は、提示されたクレデンシャルが有効であることを検証しなければならない。これは、そのクレデンシャルが発行者２によって維持されている有効なクレデンシャルの集合のうちの１つであることを確認することを伴う。これは、暗号アキュムレータ構造を使用して達成される。まず、ユーザ・プライバシが最優先の関心事ではない状況でアキュムレータベースのシステムの動作を考慮する。すなわち、ユーザは、有効なクレデンシャルの所有を証明する必要があるが、その他のおそらくアイデンティティを明らかにする情報がこのプロセスによって使用可能になることについては心配しない。この初期アキュムレータ構造の基礎となるアルゴリズムについては、以下に定義されるが、Boneh、Gentry、およびWatersによるブロードキャスト暗号化方式に部分的に基づくものである（2005年、Springer発行、Advancesin Cryptology - CRYPTO 2005、Lecture Notes in ComputerScienceの3621巻、258〜275ページ掲載のBoneh、Gentry、およびWatersによる「Collusion Resistant BroadcastEncryption with Short Ciphertexts and Private Keys」を参照されたい）。特に、説明すべき構造におけるアキュムレータ計算は、参照された方式で暗号化鍵が生成される方法に関連し、証人計算は、参照された方式で復号鍵が生成される方法に関連する。
【００５２】
まず、クレデンシャルが最初に発行者コンピュータ２によってユーザに対して発行される、システムの動作における予備段階について考慮する。発行者コンピュータ２の動作における主要ステップは図２の流れ図に示されている。（一般に、クレデンシャルの発行はオフラインで実行することができるか（たとえば、ユーザに対して発行されたスマート・カード上で供給される）、ユーザによる正常な適用後にネットワーク１５を介してオンラインで発行することができるか、またはその両方であることに留意されたい。図２は、発行プロセスの簡略化を表しているが、関連の動作原理はこの図から理解することができる。）このセットアップ・プロセスはステップ２０から始まり、そこでクレデンシャル管理ロジック３はアキュムレータの動作で使用すべき様々なパラメータを生成する。このパラメータ・セットアップ・プロセスは、ロジック３によって実装される以下のアルゴリズムによって定義される。
【００５３】
ＡｃｃＧｅｎ（１k，ｎ）： ＢＭＧｅｎ（１k）を実行して、双線形マップｅ：Ｇ×Ｇ→ＧTのセットアップｐａｒａｍｓBM＝（ｑ，Ｇ，ＧT，ｅ，ｇ）を入手する。
【００５４】
ランダム値γ∈Ｚqをピックする。安全なシグニチャ方式、たとえば、ＳＤＨ仮定に基づいて安全な上述のＢＢシグニチャ方式のための鍵のペアｓｋおよびｐｋを生成する。
【数３０】
、ｓｋA＝（ｐａｒａｍｓBM，γ，ｓｋ）、ａｃｃφ＝１、および
【数３１】
とする。
【００５５】
このプロセスでは、クレデンシャル管理ロジック３は秘密値γおよび群ジェネレータｇを使用して、群要素
【数３２】
を生成し、ここでｎは、アキュムレータ、すなわち、有効なクレデンシャルの集合内に「含む」べきクレデンシャルの定義済みの最大数である。これらは、以下に説明する通り、クレデンシャルにマッピングされる群要素である。加えて、ロジック３は、後述する通り、証人計算に使用される、補助群要素
【数３３】
を生成する。
【００５６】
次に、図２のステップ２１では、ロジック３は、群要素と発行すべきクレデンシャルとのマッピングを定義する。各クレデンシャルは、クレデンシャル内に定義される通し番号の形の識別子を有し、このマッピングはこれらの通し番号とそれぞれの群要素との間で定義される。ここでは、単純にするため、整数１〜ｎの集合によって通し番号を表すが、当然のことながら、数字と群要素との任意のマッピングに対応することができる。このため、通し番号ｉ∈｛１，２，３，．．．，ｎ｝を有する各クレデンシャルの場合、そのクレデンシャルはここでは群要素
【数３４】
にマッピングされる。
【００５７】
ステップ２２は、ユーザに発行すべきクレデンシャルの初期集合Ｃ（ｉ）のロジック３による生成を表している。これらは、最初にアキュムレータ内に含まれるクレデンシャルである。クレデンシャルは既知の方法で生成することができ、各クレデンシャルはそれぞれの通し番号ｉを含む。次に、ステップ２３では、ロジック３が以下のアルゴリズムによりクレデンシャルの初期集合に関するアキュムレータを生成する。
【００５８】
ＡｃｃＵｐｄａｔｅ（ｐｋA，Ｖ，ｓｔａｔｅU）： Ｖ⊂Ｕであるかどうかをチェックし、そうではない場合に⊥を出力する。このアルゴリズムは
【数３５】
を出力する。
【００５９】
したがって、暗号アキュムレータはここでは、群要素ｇiが有効なクレデンシャルの集合内のクレデンシャルにマッピングされるｉの値について群要素ｇn+1-iの積として生成される。したがって、実際に蓄積された群要素は、有効なクレデンシャルにマッピングされた要素ｇiに対してｉ値を介して関連付けられる。
【００６０】
図２のステップ２４では、クレデンシャル・ロジック３は、署名鍵ｓｋに基づくｇi｜｜ｉについて
【数３６】
およびシグニチャσiを計算することにより、アキュムレータ内の各クレデンシャルＣに関する証人を生成する。
【００６１】
したがって、各クレデンシャルiについて、アキュムレータ証人ｗは、群要素のそれぞれの異なる部分集合の積として計算される。この部分集合は、有効な集合内のクレデンシャルのｉ値に依存し、各証人が生成されるクレデンシャルのｉ値にも依存する。具体的には、群要素ｇiにマッピングされたそれぞれの有効なクレデンシャルについて、証人は、群要素ｇiが他の有効なクレデンシャルにマッピングされるｊのすべての値について群要素ｇn+1-j+iの積を含む。したがって、証人生成は、前に定義された補助群要素ｇn+2，．．．，ｇ2nを利用する。シグニチャσiは、関連クレデンシャルと対応する群要素とのマッピングを示す。証人は、ｗｉｔi＝（ｗ，σi，ｇi）として出力される。
【００６２】
ステップ２５では、各クレデンシャルＣ（ｉ）は、その関連証人ｗｉｔiとともに、ネットワーク１５を介して当該ユーザに送信される。次に、ステップ２６では、クレデンシャル・ロジック３は、ステップ２３で計算されたアキュムレータを配布者コンピュータ（複数も可）１６に送信することにより、暗号アキュムレータを公表する。配布者１６は、任意の接続コンピュータ６、７へのアクセスを可能にすることにより、ネットワーク１５上でアキュムレータを公表する。これで、アキュムレータ・セットアップの初期段階が完了する。
【００６３】
新しいクレデンシャルを発行し、古いクレデンシャルを発行者２によって取り消すことができると仮定すると、クレデンシャル・ロジック３は、有効なクレデンシャルの動的集合における変化を反映するようにアキュムレータを管理しなければならない。このアキュムレータ管理プロセスは、図３の簡易流れ図に表されている。ステップ３０は、定義された「エポック（epoch）」内で行われるクレデンシャルの発行および取り消しを表している。クレデンシャルが発行されるかまたは取り消されるたびに、クレデンシャル・ロジック３は、通し番号ｉとともにこの事実をメモリ４にログ記録する。次の更新プロセスは原則として、クレデンシャルが発行されるかまたは取り消されるたびに実行することができるが、更新は典型的に、一定の間隔をおいて、たとえば、毎日、定期的に実行される。このため、判断ステップ３１では、クレデンシャル・ロジック３は、現在のエポックが終了したかどうかをチェックし、終了していない場合、動作はステップ３０に戻る。しかし、各エポックの終了時には、動作はステップ３２に移行し、そこでロジック３は、有効なクレデンシャルの集合から追加／除去された各クレデンシャルについて説明するためにアキュムレータを更新する。次に、ステップ３３では、有効な集合における変化を反映するために、新たに発行されたクレデンシャルに関する証人を生成し、既存のクレデンシャルに関する古い証人を更新することにより、証人の集合が更新される。新たに発行されたクレデンシャルごとに、これらのプロセスは以下のアルゴリズムによって定義される。
【００６４】
ＡｃｃＡｄｄ（ｓｋA，ｉ，ａｃｃV，ｓｔａｔｅU）： 署名鍵ｓｋに基づくｇi｜｜ｉについて
【数３７】
およびシグニチャσiを計算する。このアルゴリズムは、ｗｉｔi＝（ｗ，σi，ｇi）、更新されたアキュムレータ値
【数３８】
、および状態
【数３９】
を出力する。
【００６５】
アキュムレータへのクレデンシャルｉの追加は、前のａｃｃ値に群要素ｇn+1-iを掛けることによって単純に達成されることが分かる。同様に、クレデンシャルｉの取り消しは、前のａｃｃ値を群要素ｇn+1-iで割ることによって単純に達成される。したがって、アキュムレータ更新は高速かつ効率的であり、複雑さは追加された／取り消されたクレデンシャルの数において線形である。新たに追加されたクレデンシャルに関する証人生成は上記の図２のものと同じである。既存の証人の更新は以下のように定義される。
【００６６】
ＡｃｃＷｉｔＵｐｄａｔｅ（ｐｋA，ｗｉｔi，Ｖw，ａｃｃV，Ｖ，ｓｔａｔｅU）： ｗｉｔiを（ｗ，σi，ｇi）として解析する。ｉ∈ＶおよびＶ∪Ｖw⊂Ｕである場合、
【数４０】
を計算する。更新された証人ｗｉｔ’iを（ｗ’，σi，ｇi）として出力する。そうではない場合、⊥を出力する。
【００６７】
所与のクレデンシャルの追加（または取り消し）に対応するために証人を更新することは単純に古い証人値に対して適切な群要素ｇn+1-j+iで乗算（または除算）することを必要とすることが分かる。これは単一乗算で達成できるので、証人更新も同じく高速かつ効率的であり、複雑さは証人あたりの変更の数において線形である。
【００６８】
図３に戻ると、ステップ３４では、発行者コンピュータ２のクレデンシャル・ロジック３は、ネットワーク１５上で公表するために、更新されたアキュムレータおよび証人を配布者コンピュータ（複数も可）１６に送信する。証人は、個々のユーザが必要なときに自分の特定のクレデンシャルに関する証人を識別できるようにするために何らかの形の識別タグで公表される。次に、動作は新しいエポックのためにステップ３０に戻る。
【００６９】
図４は、ユーザがその後、検証者コンピュータ７を介してオンライン・サービスにアクセスするために自分のクレデンシャルを使用したいと希望するときの手順を示している。この図は、図の左側のユーザ・コンピュータ６と右側の検証者コンピュータ７によって実行される主要ステップを示している。動作は、サービスへのアクセスを要求するためにユーザ・コンピュータ６が検証者コンピュータ７に接続したときに始まる。コンピュータ７の検証者ロジック１１は、ユーザのクレデンシャルを要求することによって応答する。この要求は、ユーザ・コンピュータ６の証明者ロジック８によって受信される。次に、証明者ロジックは、前に発行者２から入手し、メモリ９に保管されていたクレデンシャルＣ（ｉ）に関する証人ｗの現在の値をダウンロードするために配布者コンピュータ１６への接続を確立する。クレデンシャルは図３のステップ３２〜３４に応じて発行されているので、このステップは、アキュムレータにおけるすべての変化を説明するために必要である。更新された証人ｗはメモリ９に保管される。次に、証明者ロジック８は、前述の通り、通し番号ｉを含むクレデンシャルＣ（ｉ）を、上記で定義された完全証人ｗｉｔi（ｗ，σi，ｇi）とともに、検証者７に送信する。次に、検証者ロジック１１は同様に、そのときにメモリ１２に保管されているアキュムレータａｃｃVの現在の値をダウンロードするために配布者コンピュータ１６にアクセスする。次に、検証者ロジック１１は以下の検証プロトコルを実行する。
【００７０】
ＡｃｃＶｅｒｉｆｙ（ｐｋA，ｉ，ｗｉｔi，ａｃｃV）： ｗｉｔi＝（ｗ，σi，ｇi）を解析する。σiが検証鍵ｐｋに基づくｇi｜｜ｉについて有効なシグニチャであり、ｅ（ｇi，ａｃｃV）／ｅ（ｇ，ｗ）＝ｚである場合、受諾を出力する。そうではない場合、拒否を出力する。
【００７１】
このプロセスでは、検証者ロジック１１は、ユーザのクレデンシャルＣ（ｉ）および関連群要素ｇiの通し番号ｉについてシグニチャσiが有効であることをチェックする。（それらがマッピングする値とともにｇiに署名するためにこのシグニチャ方式を使用すると、ｇi値のマッピングを公表する必要性が回避され、したがって、検証中の大規模な公開パラメータを回避することに留意されたい。）また、検証者ロジック１１は、群要素ｇiが現在のアキュムレータａｃｃV内にあることを証人ｗが確認することをチェックする。これは、ユーザのクレデンシャルが有効であることを確認するものである。次に、検証者ロジック１１は、クレデンシャルが有効であると思われるかどうかに応じて、ユーザ・コンピュータ６がサービスにアクセスすることを許可するかまたは拒否する。
【００７２】
現在の証人およびアキュムレータ値の取り出しは図４ではアクセス・プロセスに統合されて示されているが、実際には、各当事者は単純にそれぞれの新しいエポックの開始時に定期的に新しい値を取り出すことができることに留意されたい。
【００７３】
上記の説明はアキュムレータおよび証人の高速かつ効率的な計算および更新による動的アキュムレータ構造に基づく非常に効率的なクレデンシャル検証システムを示していることが分かるであろう。たとえば、証人更新は、アキュムレータに対する変更の数において線形の乗算のみ（べき乗なし）を必要とし、いずれの秘密情報の知識も必要としない。したがって、一般に、証人は、ユーザ自身、発行者、または何らかの第三者によってユーザのために最新のものを保持することができる。しかし、証人更新は従来の方式のようにユーザが個別に実行することができ、好ましい諸実施形態ではそのシステムの効率を活用し、それによりすべての証人をメイン・メモリ内に実行可能に保持することができ、証人計算を中央で実行できるようにする。これは、上記の実施形態では発行者２によって行われる。代替例として、いずれの秘密鍵の知識もなしでブックキーピング情報Ｖwからアキュムレータ内に含まれる値ｉ∈Ｖについてすべての証人を更新することは可能であるので、証人更新は、ＡｃｃＷｉｔＵｐｄａｔｅを実行し、アキュムレータ状態ｓｔａｔｅUおよびブックキーピング情報ＶおよびＶwのみが与えられる信頼できない更新エンティティに対して効率的にオフロードすることができる。たとえば、図１の配布者コンピュータ１６は証人更新コンピュータとしてさらに機能することができる。有効な集合における変更後に発行者コンピュータ２によりアキュムレータを更新するときに、その集合内に残っているクレデンシャルに関する証人更新は、１つまたは複数のこのような配布者コンピュータ１６によって、全体的にまたはバッチ方式で実行することができる。
【００７４】
上記の基本方式は、完全匿名クレデンシャル取り消しシステムにおける動作のための基礎を提供するには十分効率的なものである。以下では、匿名クレデンシャル取り消しシステムの特に好ましい一実施形態を実装するために上記の基本システムに対して行う様々な変更について考察する。
【００７５】
隠し値が蓄積されたという効率的な証明
まず、ユーザがどの値を所有しているか（またはどのインデックスｉがユーザに割り当てられているか）を明らかにせずに、現在のアキュムレータ内に含まれる値をユーザが所有していることをユーザが証明できるようにする効率的なプロトコルについて考慮する。このセクションでは、アキュムレータ構造のためにこれを達成する効率的なプロトコルを示す。上記の実施形態では、上述の通り、それぞれに署名させ、次にユーザがｇiおよびシグニチャを検証者に提供することにより、群要素ｇ1，．．．，ｇnが認証される。この場合、シグニチャまたはｇi値を明らかにせずに証明者が「ユーザの」ｇi上のアキュムレータ発行者によるシグニチャを把握していることを証明することを要求する。このような証明は効率的である必要があり、特別なシグニチャ方式を必要とする。蓄積された値は証明されるだけであって、決して明らかにされないので、ｇiとともにｉに署名せずに行うことができる。このため、より効率的なシグニチャ方式および証明システムが可能になる。
【００７６】
前提条件。新鮮なｕ←Ｇ、秘密鍵ｓｋ←Ｚq、および公開鍵ｐｋ＝ｇskをピックすることにより、ｇiに署名するために使用されるシグニチャ方式をインスタンス化する。シグニチャは、２つの要素
【数４１】
および
【数４２】
で構成され、ｅ（ｐｋ・ｇi，σi）＝ｅ（ｇ，ｇ）であることをチェックすることによって検証される。
【数４３】
、ｓｋA＝（ｐａｒａｍｓBM，γ，ｓｋ）、および
【数４４】
はすでに説明したアキュムレータ動作によって生成されるものとする。また、コミットメントのために追加の
【数４５】
もピックする。ｇに対するｈおよびｕの離散対数は証明者にとって未知のものでなければならない。
【００７７】
知識の証明。任意のＶ⊂｛１，．．．，ｎ｝およびｉ∈Ｖについて、入力
【数４６】
および対応する証人ｗｉｔi＝（ｗ，σi，ｕi，ｇi）のときに、
【数４７】
であり、値ｉについて、証明者は以下の無作為化を実行する。
【００７８】
無作為に、ｒ、ｒ’、ｒ’’、ｒ’’’、ｏｐｅｎ∈Ｚqをピックし、
【数４８】
【数４９】
【数５０】
【数５１】
および
【数５２】
をそれぞれ計算する。次に、証明者は、以下のように証明する。
【数５３】
【００７９】
n-DHEおよびn-HSDHE仮定に基づいて、上記のプロトコルは、Ｇ’を値ｇiに無作為化解除できるようにする無作為化値ｒの知識の証明であり、ここでｉはａｃｃV内に蓄積され、すなわち、ｉ∈Ｖである。
【００８０】
匿名クレデンシャル方式（たとえば、匿名電子マネー、グループ・シグニチャ、匿名証明書システム、仮名システムなど）では、ユーザは、匿名性を保護する方法で使用可能な何らかの形のクレデンシャルを獲得する。2004年、Springer発行、Christianson他編集、Security Protocols Workshop、Lecture Notes inComputer Scienceの3957巻、20〜42ページ掲載のBangerter他による「A cryptographic framework for the controlled release of certifieddata」では、著者は、クレデンシャルで証明された情報の被制御リリースのための暗号フレームワークを示している。これは、ユーザに対して私的証明書（private certificate）を発行するためにCamenisch-Lysyanskaya（ＣＬ）シグニチャという特別なシグニチャ・プロトコルを使用する（2003年、Springer Verlag発行、I Cimato他編集、Security in CommunicationNetworks、Third International Conference、SCN 2002、LNCSの2576巻、268〜289ページ掲載のJanCamenischおよびAnna Lysyanskayaによる「A signature scheme with efficient protocols」を参照されたい）。私的クレデンシャル（ｃｅｒｔ）は、伝統的な証明書のように属性および属性に関するシグニチャで構成され、以下のようにより強力なシグニチャ方式が使用される。
ｃｅｒｔ＝（σ，ｍ1，．．．，ｍl）およびσ＝Ｓｉｇｎ（ｍ1，．．．，ｍl；ｓｋI）
【００８１】
（ｓｋI、ｐｋI）←ＩｓｓｕｅｒＫｅｙｇｅｎ（１k）は証明書発行者の鍵のペアとする。このフレームワークは、１）これらの値を明らかにせずに、コミットされた値上のシグニチャを入手できるようにする対話式証明書発行プロトコルＯｂｔａｉｎＣｅｒｔと、２）シグニチャ所有の知識に関する効率的なゼロ知識証明という２つのタイプのプロトコルをサポートする。
【００８２】
（ｍ1，．．．，ｍl）はデータ項目のリストを示し、Ｈ⊂Ｌ＝｛１，．．．，ｌ｝はデータ項目の部分集合を示すものとする。第１のプロトコルを使用すると、ユーザは、発行者がＨ内のデータ項目に関するいかなる情報も学習しないが、他のデータ項目、すなわち、Ｌ＼Ｈを学習するように、（ｍ1，．．．，ｍl）に関する証明書を入手することができる。
【００８３】
ユーザの私的証明書はユーザにとって私的なままになり、すなわち、他のどの当事者にも（全体として）決してリリースされず、属性情報をアサートするために証明書を使用する（示す）ときに、ユーザは、特定のプロパティを含む証明書を自分が把握している（持っている）ことを証明する。ユーザは、以下のように証明書の残りの部分の知識のみを証明しながら、特定の属性をリリースすることができる。
【数５４】
上記の証明では、
【数５５】
という属性値のみが明らかにされる。
【００８４】
上記のフレームワークを以下のように拡張する。Ｖはエポック情報ｅｐｏｃｈVを含むエポックに関する有効な証明書の集合とする。以前のように、証明書には固有の識別子ｉ（属性の１つとしてそれに埋め込まれる）および証人ｗｉｔiが割り当てられる。ここでは、ｉ∈Ｖである場合のみ、ユーザが取り消されない証明書を所有することを検証者に対して証明できることを要求する。これは、ユーザのクレデンシャルに埋め込まれた識別子が現在のエポックについて有効なものであることをユーザに証明させることによって達成される。したがって、証明に携わる前に、ユーザは自分の証人を更新する必要があり、両方の当事者（ユーザと検証者）はＶについて最も最新のエポック情報ｅｐｏｃｈVを入手する必要がある。好ましいクレデンシャル取り消しシステムは、以下のように、更新されたIssuerKeygenおよびObtainCertプロトコル、取り消しを管理するための新しいアルゴリズムであるUpdateEpochおよびUpdateWitness、ならびに証人ｗｉｔiの所有の証明を可能にする新しい述語VerifyEpochのためのゼロ知識証明システムに基づくものである。
【００８５】
ＩｓｓｕｅｒＫｅｙｇｅｎ（１k；ｎ）は、ｎ個までの証明書を発行するための発行者の鍵のペア（ｓｋI，ｐｋI）、エポック情報ｅｐｏｃｈφ、およびｓｔａｔｅφを作成する。
【００８６】
【数５６】
は、ユーザが発行者から私的証明書ｃｅｒｔiを入手できるようにする。発行者は、ユーザの証人ｗｉｔi、更新されたエポック情報
【数５７】
、および
【数５８】
を計算し公表する。
【００８７】
ＵｐｄａｔｅＥｐｏｃｈ（Ｖ，ｓｔａｔｅU）は、Ｖ⊂Ｕである場合にエポック情報ｅｐｏｃｈVを出力する。そうではない場合、⊥を出力する。
【００８８】
ＵｐｄａｔｅＷｉｔｎｅｓｓ（ｗｉｔi，ｅｐｏｃｈV，ｓｔａｔｅU）は、Ｖ⊂Ｕである場合に更新された証人ｗｉｔ’iを出力する。そうではない場合、⊥を出力する。
【００８９】
証明書ｃｅｒｔiおよび対応する最新の証人ｗｉｔiを把握しているユーザは、以下のように新しい述語VerifyEpochを使用して、現在のエポックに関する証明書の所有およびその妥当性を検証者に対して証明することができる。ユーザの秘密の入力はｃｅｒｔiである。このプロトコルの共通入力は、発行者の公開鍵ｐｋI、エポック情報ｅｐｏｃｈV、および証明ステートメントの指定（これは証明書について明らかにされた情報を含む）である。以下の例では、ユーザは、メッセージの残りの部分を明らかにしながら、最初のｌ個のメッセージを秘密に保持することを選択する。
【数５９】
【００９０】
シグニチャ方式。以下の実施形態では、証明をより効率的なものにするためにクレデンシャルにｇiを含めることにより、ｇiに対するｉのマッピングが暗黙のものになる。したがって、ｇi値は、証明書ｉｄ ｉを表すために私的証明書とアキュムレータの両方で使用される。これには、秘密の指数γiを把握せずに検証を可能にするために上記で示したシグニチャ方式を拡張することが必要である。
１．署名者は、ｇ，ｈ，ｈ0，ｈ1，．．．，ｈl，ｈl+1←Ｇを作成し、鍵ｘ∈Ｚqおよびｙ＝ｈxを作成する。
２．次に、署名者は、シグニチャ内で可能にするリスト
【数６０】
を公表する。
３．署名者は、ｃ，ｓ←Ｚ*qをピックし、シグニチャを
【数６１】
として計算する。
４．メッセージ
【数６２】
上のシグニチャ（σ，ｃ，ｓ）は、
【数６３】
がｇi値のリスト内にあることをチェックし、
【数６４】
であることをチェックすることによって検証される。
（この場合の最後のステップにおける
【数６５】
がｇi値のリスト内にあることのチェックは、上記の実施形態のように後でｇi上のシグニチャ／認証符号（authenticator）で置き換えられる。）
【００９１】
変更された構造では、発行者コンピュータ２のクレデンシャル管理ロジック３によって実行されるセットアップ・プロセス（図２のステップ２０に対応）は以下のように定義される。
ＩｓｓｕｅｒＫｅｙｇｅｎ（１k，ｎ）。（対称形の）双線形マップｅ：Ｇ×Ｇ→ＧTのパラメータｐａｒａｍｓBM＝（ｑ，Ｇ，ＧT，ｅ，ｇ）を生成するためにＢＭＧｅｎ（１k）を実行する。追加の基数
【数６６】
およびｘ，ｓｋ，γ←Ｚqをピックし、ｙ＝ｈxおよびｐｋ＝ｇskを計算する。（相互に対するｇ、ｈ、
【数６７】
、およびｕの離散対数は互いに未知である。）ｇ1，．．．，ｇn，ｇn+2，．．．，ｇ2nを計算するが、ここで
【数６８】
および
【数６９】
である。
【数７０】
、ｅｐｏｃｈφ＝（ａｃｃφ＝１，φ）、およびｓｔａｔｅφ＝（φ，ｇ1，．．．，ｇn，ｇn+2，．．．，ｇ2n）を出力する。
【００９２】
ユーザ証明書および証人の問題（図２のステップ２２、２４、および２５に対応）は以下のように定義される。
【数７１】
ユーザ（ユーザ・コンピュータ６の証明者ロジック８）は発行者から証明書ｃｅｒｔiを入手するために以下のプロトコルを実行する。
１．ユーザは、無作為にｓ’∈Ｚ*qを選択し、
【数７２】
を計算し、Ｘを発行者に送信する。
２．ユーザは（証明者として）発行者を（ここでは検証者として）
【数７３】
という証明に従事させるが、これはＸが正しく形成されることを発行者に確信させることになる。
３．発行者は、ｅｐｏｃｈVを（ａｃｃV，Ｖ）として、ｓｔａｔｅUを（Ｕ，ｇ1，．．．，ｇn，ｇn+2，．．．，ｇ2n）として解析する。次に、発行者は、
【数７４】
および
【数７５】
を計算する。
４．発行者は、無作為にｃ，ｓ’’∈Ｚ*qを選択し、
【数７６】
を計算する。
５．発行者は、
【数７７】
および
【数７８】
を計算し、ｗｉｔi＝（σi，ｕi，ｇi，ｗ，Ｖ∪｛ｉ｝）を設定する。
６．発行者は、
【数７９】
をユーザに送信し、ｗｉｔi、
【数８０】
および
【数８１】
を出力する。
７．ユーザは、入手した証明書を検証し、ｃｅｒｔi＝（σ，ｃ，ｍ1，．．．，ｍl，ｇi，ｓ＝ｓ’＋ｓ’’，ｉ）を出力する。
【００９３】
図２のステップ２３に対応するアルゴリズムは以下のように示される。
ＵｐｄａｔｅＥｐｏｃｈ（Ｖ，ｓｔａｔｅU）： Ｖ⊂Ｕであるかどうかをチェックし、そうではない場合に⊥を出力する。このアルゴリズムは、ｃｅｒｔiの所有、ｉ∈Ｖを証明するためにｅｐｏｃｈVを作成する。
【数８２】
とし、ｅｐｏｃｈV＝（ａｃｃV，Ｖ）を出力する。
【００９４】
図３のステップ３３に対応する古い証人の更新は以下のように定義される。
ＵｐｄａｔｅＷｉｔｎｅｓｓ（ｗｉｔi，ｅｐｏｃｈV，ｓｔａｔｅU）：
【数８３】
である場合に⊥で打ち切る。そうではない場合、ｗｉｔiを（σi，ｕi，ｇi，ｗ，Ｖw）として解析する。
【数８４】
とする。このアルゴリズムは、ｗｉｔ’iを（σi，ｕi，ｇi，ｗ’，Ｖw）として出力する。
【００９５】
図５は、ユーザがその後、関連証人ｗｉｔi＝（σi，ｇi，ｕi，ｗ，Ｖw）とともに自分の匿名クレデンシャルｃｒｅｄi＝（σ，ｃ，ｍ1，．．．，ｍl，ｇi，ｓ，ｉ）を使用したいと希望するときにこの実施形態のユーザ・コンピュータ６と検証者コンピュータ７との間で行われる対話を示している。それぞれの新しいエポックの開始時に、各当事者６、７は、アキュムレータ内の介在変化を説明するために更新された値を配布者コンピュータ１６からダウンロードする。具体的には、証明者ロジック８はユーザのクレデンシャルｃｒｅｄiに関する現在の証人値ｗiを入手し、検証者ロジック１１は現在のアキュムレータ値を含む現在公表されているｅｐｏｃｈV＝（ａｃｃV，Ｖ）を入手する。その後、ユーザのアクセス要求に応答して、検証者ロジック１１は証明者ロジック８に検証要求を送信する。次に、証明者ロジックは、次の証明で使用すべき様々なパラメータを定義する。具体的には、証明者ロジックは、それぞれρおよびｒをコミットするために、ρ，ρ’，ｒ，ｒ’，ｒ’’，ｒ’’’←Ｚqをピックし、オープニングのｏｐｅｎ，ｏｐｅｎ’←Ｚqをピックする。次に、証明者ロジックは、コミットメント
【数８５】
【数８６】
ならびに目隠し値
【数８７】
【数８８】
【数８９】
【数９０】
および
【数９１】
を計算する。次に、証明者ロジックは、Ｃ、Ｃ’、Ａ、Ｇ’、Ｗ’、Ｓ’、およびＵ’を検証者に送信する。次に、証明者ロジック８および検証者ロジック１１は、ゼロ知識（ＺＫ）検証プロトコルを実装するために通信する。このプロトコルの共通入力は、発行者の公開鍵ｐｋI、エポック情報ｅｐｏｃｈV、および証明ステートメントの指定（これは証明書について明らかにされた情報を含む）である。以下の例では、ユーザは、メッセージの残りの部分を明らかにしながら、最初のｌ個のメッセージを秘密に保持することを選択する。
【数９２】
【００９６】
n-HSDHEおよびn-DHE仮定に基づいて、上記のプロトコルは、ｉ∈Ｖになるような（ｍ1，．．．，ｍl，ｇi）上の適応シグニチャの知識の証明である。
【００９７】
上記のプロセスにより、ユーザは、検証者に対して他のいずれの情報も明らかにせずに有効なクレデンシャルの所有を証明することができ、完全な匿名性とトランザクションのリンク不能性を維持することができる。費用のかかる計算を必要とする前の提案とは異なり、上記のシステムは計算上、効率が良く、とりわけ、非常に効率的な証人更新を提供する。多数のユーザを含む取り消しシステム（電子ＩＤ（e-ID）、電子チケット（e-ticket）などの導入によって構想される電子トークンベースのシステムなど）では、エポックあたりの取り消しの数が非常に大きくなる可能性がある。リソース制約形ユーザ・デバイスは典型的に、このような変更に対応するために必要な計算を処理することができない。しかし、上記のシステムでは、単一機関（発行者である場合もあれば、そうではない場合もある）によって更新を処理することは計算的に実行可能であり、それにより、多数のユーザを含むプライバシ保護システムにおいて取り消しのための動的アキュムレータの採用が可能になる。ユーザ・グループに関する証人を更新する役割を担う証人更新エンティティが複数存在することも可能である。たとえば、全国的な電子ＩＤシステムでは、郡ごとまたは都市ごとに証人更新を実行することができる。これは公開パラメータのみを必要とし、更新機関はそれぞれのグループ内のユーザについて証人更新を正しく計算する役割を担うだけである。証人更新エンティティの１つによる悪意のある挙動は、（それらが公開パラメータのみを必要とするので）システム・セキュリティを破壊しないが、単純にサービスの妨害に至る可能性がある。すなわち、証人が正しく計算されない（アキュムレータ内の最新の変更を反映しない）場合、ユーザが自分のクレデンシャルの妥当性を証明するのを妨げることになるであろう。この場合、ユーザは、有効な証人更新を入手し、証人更新エンティティの不正行為を通知するために、発行機関に報告することができる。したがって、従来のシステムと比較して、ユーザははるかに少ない計算を行うだけでよく、更新機関は１桁少ない計算を行うだけでよい。計算上の複雑さという負担をユーザから発行機関などのより強力な当事者に移管することにより、携帯電話またはスマート・カードなどのデバイスを使用してユーザが検証者とのトランザクションに携わるモバイル・シナリオで効率的な証明書取り消し状況チェックを実行することができる。
【００９８】
当然のことながら、上記の模範的な諸実施形態に対して多くの変更を行うことができることが認識されるであろう。たとえば、アキュムレータなどの公表は、独立した配布者１６ではなく発行者２によって実行することができ、上記の諸実施形態において単一コンピュータによって表されるコンポーネントは実際には分散コンピューティング・システムの２つ以上のコンピュータによって実装することができる。加えて、本発明の諸実施形態は、当然のことながら、暗号クレデンシャル以外のデータ項目にも適用することができる。効率をさらに改善するための追加の変更については以下に説明する。
【００９９】
上記の構造では、ＡｃｃＧｅｎアルゴリズムは、ｓｔａｔｅU＝（Ｕ，ｇ1，．．．，ｇn，ｇn+2，．．．，ｇ2n）を定義し、ここでＵはこれまでにアキュムレータに追加された（が、その後、除去された可能性がある）すべての要素を追跡するブックキーピング情報である。この状態の残りの部分は静的である。次に、ｓｔａｔｅUのサイズを削減する変更について説明する。上記の構造における公開パラメータのサイズは蓄積する必要がある可能性のある値の数に関する推定上限において線形である。この上限が推定するのが困難なものであるシナリオでは、過大評価は費用のかかる問題になる可能性がある。しかし、所与の時点で
【数９３】
より大きい値を決して蓄積しないという特別な場合には、このコストを
【数９４】
に下げることができる。アキュムレータ・パラメータの遅延評価によりこれを達成する。
【数９５】
は最大蓄積値とする。値ｉ∈Ｖの場合、（１）アキュムレータにｉを追加するための値ｇn+1-i、（２）アキュムレータ内のメンバシップを検証するための値ｇi、および（３）証人を計算し更新するためのｊ∈Ｖ＼Ｖw）∪（Ｖw＼Ｖ）の場合の値ｇn+1-j+iを必要とする。すべてのｊ∈Ｖ∪Ｖwの場合にｊは
【数９６】
より小さいことに留意されたい。値
【数９７】
はこれらの演算のすべてについて十分であると主張する。明らかに、最初の２つの要件は満たされている。その上、ｊ＞ｉである場合、
【数９８】
である。そうではない場合、１＜ｊ＜ｉかつ
【数９９】
である。これは第３の要件を確立するものである。上記の取り消し方式のＯｂｔａｉｎＣｅｒｔプロトコルでは、
【数１００】
は１だけ増加し、欠落しているアキュムレータ・パラメータがｓｔａｔｅUに追加される。
【数１０１】
であることに留意されたい。次に、更新された状態を使用して、エポック情報ｅｐｏｃｈVおよび証人ｗｉｔiを更新する。本発明の範囲を逸脱せずに、上記の諸実施形態に対してその他の多くの変更及び修正を行うことができる。
【特許請求の範囲】
【請求項１】
データ処理システム（１）内でデータ項目の集合を示す暗号アキュムレータを提供するための方法であって、
複数の群要素を生成することと、
前記集合内のデータ項目とそれぞれの群要素とのマッピングを定義することと、
前記集合内の前記データ項目にマッピングされた前記群要素に関するそれぞれの群要素の積を含む暗号アキュムレータを生成することと、
前記データ処理システム（１）内の前記暗号アキュムレータを公表すること
を含む、方法。
【請求項２】
秘密値γおよび群ジェネレータｇを使用して各群要素を生成することを含む、請求項１記載の方法。
【請求項３】
前記群要素が、ｉ∈｛１，２，３，．．．，ｎ｝の場合にそれぞれの要素
【数１】
を含み、ここでｎが前記集合内のデータ項目の定義済みの最大数であり、
前記マッピングが前記集合内のデータ項目とそれぞれの群要素ｇiとの間で定義される、請求項２記載の方法。
【請求項４】
前記暗号アキュムレータが、前記群要素ｇiが前記集合内のデータ項目にマッピングされるｉの値について前記群要素ｇn+1-iの積を含む、請求項３記載の方法。
【請求項５】
前記マッピングが、各データ項目に関連する数値識別子と前記それぞれの群要素との間で定義される、請求項１ないし４のいずれかに記載の方法。
【請求項６】
各データ項目が、前記関連数値識別子が定義される暗号クレデンシャルを含み、前記方法が、前記暗号アキュムレータが有効な暗号クレデンシャルの集合を示すように適合される、請求項５記載の方法。
【請求項７】
前記集合がデータ項目の動的集合であり、前記方法が、データ項目の現在の集合に関する前記暗号アキュムレータを定期的に生成し公表することを含む、請求項１ないし６のいずれかに記載の方法。
【請求項８】
前記集合内の各データ項目に関する証人を生成することを含み、各証人が前記群要素のそれぞれの異なる部分集合の積を含み、各証人に関する前記部分集合が前記集合内の前記データ項目とその証人が生成された前記データ項目に依存する、請求項１ないし７のいずれかに記載の方法。
【請求項９】
前記群要素が、補助要素
【数２】
を含み、
群要素ｇiにマッピングされた前記集合内の各データ項目について、前記証人が、群要素ｇjが前記集合内の他のデータ項目にマッピングされるｊのすべての値について前記群要素ｇn+1-j+iの積を含む、請求項８および請求項４記載の方法。
【請求項１０】
データ項目の前記現在の集合に関する前記証人を定期的に生成することを含む、請求項７および請求項８または請求項７および請求項９記載の方法。
【請求項１１】
前記データ処理システム（１）内で各証人を公表することを含む、請求項８ないし１０のいずれか１項記載の方法。
【請求項１２】
請求項１ないし１１のいずれかに記載の方法をコンピュータに実行させるためのプログラム・コード手段を含むコンピュータ・プログラム。
【請求項１３】
データ処理システム（１）内でデータ項目の集合を示す暗号アキュムレータを提供するための装置であって、メモリ（４）と、請求項１ないし１１のいずれか１項記載の方法を実行するように適合された制御ロジック（３）とを含み、前記複数の群要素が前記メモリ（４）内に保管される、装置。
【請求項１４】
それぞれがデータ通信ネットワーク（１５）を介した通信用に適合されたユーザ・コンピュータ（６）、検証者コンピュータ（７）、およびデータ項目管理コンピュータ（２）を含む、データ処理システム（１）であって、
前記データ項目管理コンピュータ（２）が、前記ユーザ・コンピュータ（６）に関連するユーザ・データ項目を含むデータ項目の集合を示す暗号アキュムレータを提供するための請求項１ないし１１のいずれか１項記載の方法を実行するように適合され、
前記ユーザ・コンピュータ（６）が、前記暗号アキュムレータのために、前記ユーザ・データ項目と、前記ユーザ・データ項目に対応する証人を保管し、
前記ユーザ・コンピュータ（６）および検証者コンピュータ（７）が、前記暗号アキュムレータによって示された前記集合内のデータ項目に対応する証人に関する前記ユーザ・コンピュータ（６）による知識を証明する検証プロトコルを実装するために前記ネットワーク（１５）を介した通信用に適合される、データ処理システム（１）。
【請求項１５】
前記検証プロトコルがゼロ知識証明プロトコルである、請求項１４記載のシステム。
【請求項１】
データ処理システム（１）内でデータ項目の集合を示す暗号アキュムレータを提供するための方法であって、
複数の群要素を生成することと、
前記集合内のデータ項目とそれぞれの群要素とのマッピングを定義することと、
前記集合内の前記データ項目にマッピングされた前記群要素に関するそれぞれの群要素の積を含む暗号アキュムレータを生成することと、
前記データ処理システム（１）内の前記暗号アキュムレータを公表すること
を含む、方法。
【請求項２】
秘密値γおよび群ジェネレータｇを使用して各群要素を生成することを含む、請求項１記載の方法。
【請求項３】
前記群要素が、ｉ∈｛１，２，３，．．．，ｎ｝の場合にそれぞれの要素
【数１】
を含み、ここでｎが前記集合内のデータ項目の定義済みの最大数であり、
前記マッピングが前記集合内のデータ項目とそれぞれの群要素ｇiとの間で定義される、請求項２記載の方法。
【請求項４】
前記暗号アキュムレータが、前記群要素ｇiが前記集合内のデータ項目にマッピングされるｉの値について前記群要素ｇn+1-iの積を含む、請求項３記載の方法。
【請求項５】
前記マッピングが、各データ項目に関連する数値識別子と前記それぞれの群要素との間で定義される、請求項１ないし４のいずれかに記載の方法。
【請求項６】
各データ項目が、前記関連数値識別子が定義される暗号クレデンシャルを含み、前記方法が、前記暗号アキュムレータが有効な暗号クレデンシャルの集合を示すように適合される、請求項５記載の方法。
【請求項７】
前記集合がデータ項目の動的集合であり、前記方法が、データ項目の現在の集合に関する前記暗号アキュムレータを定期的に生成し公表することを含む、請求項１ないし６のいずれかに記載の方法。
【請求項８】
前記集合内の各データ項目に関する証人を生成することを含み、各証人が前記群要素のそれぞれの異なる部分集合の積を含み、各証人に関する前記部分集合が前記集合内の前記データ項目とその証人が生成された前記データ項目に依存する、請求項１ないし７のいずれかに記載の方法。
【請求項９】
前記群要素が、補助要素
【数２】
を含み、
群要素ｇiにマッピングされた前記集合内の各データ項目について、前記証人が、群要素ｇjが前記集合内の他のデータ項目にマッピングされるｊのすべての値について前記群要素ｇn+1-j+iの積を含む、請求項８および請求項４記載の方法。
【請求項１０】
データ項目の前記現在の集合に関する前記証人を定期的に生成することを含む、請求項７および請求項８または請求項７および請求項９記載の方法。
【請求項１１】
前記データ処理システム（１）内で各証人を公表することを含む、請求項８ないし１０のいずれか１項記載の方法。
【請求項１２】
請求項１ないし１１のいずれかに記載の方法をコンピュータに実行させるためのプログラム・コード手段を含むコンピュータ・プログラム。
【請求項１３】
データ処理システム（１）内でデータ項目の集合を示す暗号アキュムレータを提供するための装置であって、メモリ（４）と、請求項１ないし１１のいずれか１項記載の方法を実行するように適合された制御ロジック（３）とを含み、前記複数の群要素が前記メモリ（４）内に保管される、装置。
【請求項１４】
それぞれがデータ通信ネットワーク（１５）を介した通信用に適合されたユーザ・コンピュータ（６）、検証者コンピュータ（７）、およびデータ項目管理コンピュータ（２）を含む、データ処理システム（１）であって、
前記データ項目管理コンピュータ（２）が、前記ユーザ・コンピュータ（６）に関連するユーザ・データ項目を含むデータ項目の集合を示す暗号アキュムレータを提供するための請求項１ないし１１のいずれか１項記載の方法を実行するように適合され、
前記ユーザ・コンピュータ（６）が、前記暗号アキュムレータのために、前記ユーザ・データ項目と、前記ユーザ・データ項目に対応する証人を保管し、
前記ユーザ・コンピュータ（６）および検証者コンピュータ（７）が、前記暗号アキュムレータによって示された前記集合内のデータ項目に対応する証人に関する前記ユーザ・コンピュータ（６）による知識を証明する検証プロトコルを実装するために前記ネットワーク（１５）を介した通信用に適合される、データ処理システム（１）。
【請求項１５】
前記検証プロトコルがゼロ知識証明プロトコルである、請求項１４記載のシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公表番号】特表２０１２−５１６６０４（Ｐ２０１２−５１６６０４Ａ）
【公表日】平成２４年７月１９日（２０１２．７．１９）
【国際特許分類】
【出願番号】特願２０１１−５４７０４０（Ｐ２０１１−５４７０４０）
【出願日】平成２２年１月２７日（２０１０．１．２７）
【国際出願番号】ＰＣＴ／ＩＢ２０１０／０５０３６７
【国際公開番号】ＷＯ２０１０／０８６８０３
【国際公開日】平成２２年８月５日（２０１０．８．５）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
【公表日】平成２４年７月１９日（２０１２．７．１９）
【国際特許分類】
【出願日】平成２２年１月２７日（２０１０．１．２７）
【国際出願番号】ＰＣＴ／ＩＢ２０１０／０５０３６７
【国際公開番号】ＷＯ２０１０／０８６８０３
【国際公開日】平成２２年８月５日（２０１０．８．５）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
[ Back to top ]