説明

時系列データのプライバシー保護アグリゲーション

【課題】ユーザのプライバシーを漏洩することなく、アグリゲータにユーザのデータを集め、プライベートストリームアグリゲーション(PSA)システムを構築する。
【解決手段】システムは、ユーザの組におけるローカルユーザのための秘密鍵を判定することによって開始する。ここでは、ユーザの組及びアグリゲータ104と関連付けられた秘密鍵の合計はゼロである。システムはまた、ローカルユーザと関連付けられたデータ値の組を選択する。そして、システムは、暗号化データ値の組を生成するように、一部において秘密鍵に基づいて個々のデータ値を暗号化し、ユーザの組と関連付けられた個々のデータ値を復号することなく、アグリゲート値を復号し、ユーザの組と情報授受する。システムはまた、アグリゲータ104に対して暗号化データ値の組を送信する。

【発明の詳細な説明】
【発明の概要】
【0001】
システムは、ユーザのプライバシーを漏洩することなく、データアグリゲータに対してユーザのデータを提供する。システムは、ユーザの組におけるローカルユーザのための秘密鍵を判定する。ここで、ユーザの組とデータアグリゲータとに関連付けられた秘密鍵の合計はゼロに等しい。システムはまた、ローカルユーザと関連付けられたデータ値の組を選択する。そして、システムは、暗号化データ値の組を生成するように、一部において秘密鍵に基づいて組における個々のデータ値を暗号化し、それにより、ユーザの組と関連付けられた個々のデータ値を復号することなく且つアグリゲート値を復号しながらユーザの組と情報授受することなく、データアグリゲータがユーザの組にわたってアグリゲート値を復号するのを許容する。システムはまた、データアグリゲータに対して暗号化データ値の組を送信する。
【0002】
いくつかの実施形態において、システムは、信頼できるソースから秘密鍵を受信することによってローカルユーザのための秘密鍵を判定する。
【0003】
いくつかの実施形態において、システムは、安全なマルチパーティプロトコルを使用することによってローカルユーザのための秘密鍵を判定する。
【0004】
いくつかの実施形態において、データ値の組は、データ値の時系列を含む。さらに、システムは、時系列における個々のデータ値の暗号化に先立って秘密鍵を判定してもよい。
【0005】
いくつかの実施形態において、個々のデータ値を暗号化することは、ランダムノイズによって変更されたデータ値の組を生成するように、少なくともデータ値の部分集合に対してランダム値を加算することを含む。ここで、Δはアグリゲート値の機密度であり、nはユーザ数である。
【0006】
いくつかの実施形態において、個々のデータ値を暗号化することは、個々のデータ値の高次モーメントも暗号化し、それにより、データアグリゲータがユーザの組にわたるデータ値の分布を判定するのを許容することを含む。
【0007】
他の実施形態において、システムは、ユーザの組と関連付けられたデータ値の組についてのアグリゲート値を計算する。システムは、データアグリゲータのための秘密鍵を判定する。ここで、ユーザの組とデータアグリゲータとに関連付けられた秘密鍵の合計はゼロに等しい。システムはまた、対応するユーザの組から暗号化データ値の組を受信する。そして、システムは、ユーザの組と関連付けられた個々のデータ値を復号することなく、ユーザの組にわたってアグリゲート値を判定するために秘密鍵を使用し、データアグリゲータに対してアグリゲート値を提供する。
【0008】
いくつかの実施形態において、アグリゲート値は、ユーザの組と関連付けられた個々のデータ値の積を含む。
【図面の簡単な説明】
【0009】
【図1】図1は、実施形態にかかるプライベートストリームアグリゲーションについての典型的な計算環境を示している。
【図2】図2は、実施形態にかかる信頼できないデータアグリゲータと安全にデータを共有するためのプロセスを示すフローチャートを表している。
【図3】図3は、実施形態にかかる参加者の組によって提供される暗号化データからアグリゲート値を判定するためのデータアグリゲータによって実行されるプロセスを示すフローチャートを表している。
【図4】図4は、実施形態にかかる参加者の組とデータアグリゲータとの間における情報の典型的な流れを示す概略図を表している。
【図5】図5は、実施形態にかかるプライバシー保護データアグリゲーションを容易とするコンピューターシステムを示している。
【図6】図6は、実施形態にかかるプライバシー保護データアグリゲーションを容易とする装置を示している。 表1は、実施形態にかかる分散型の差分プライバシーデータランダム化を実行するアルゴリズムを表している。 図において、同様の参照符号は、同一の図面要素を参照している。
【発明を実施するための形態】
【0010】
本発明の実施形態は、ユーザが信頼できないアグリゲータに対して暗号化データのストリームをアップロードするのを許容し且つアグリゲータが各時間間隔のアグリゲート統計値を復号するために秘密鍵を使用するのを許容するプライベートストリームアグリゲーション(PSA)システムを提供する。PSA技術は、アグリゲータが所望の統計値及びその予備知識から推定することができるもの以外の任意の意図されたものでない情報を学習することができないことを意味する記憶しないアグリゲータである。PSA技術は、アグリゲータに公開される統計値が特定の個人が参加するか否かにあまり影響を受けない個々の参加者についての分散型の差分プライバシーを保証する。
【0011】
信頼できないデータアグリゲータは、個々のデータ点に対してアクセスすることなく、時系列データについてのアグリゲート統計値(例えば参加者のデータの合計又は積)を計算することができる。例えば、データアグリゲータは、毎週、n個の企業の総売上高の把握をすることを求めてもよい。本発明の実施形態によって提供されるプライバシーモデルは、個々の企業それぞれがデータアグリゲータに対して毎週それらの収入のノイズのある暗号化をアップロードするのを許容する。さらに、データアグリゲータは、参加企業の収入のノイズのある合計を復号することができるが、個々の企業と関連付けられた毎週の収入データを取得することはできない。それゆえに、データアグリゲータは、個々の企業に特有の付加情報を推測することができない。
【0012】
図1は、実施形態にかかるプライベートストリームアグリゲーションについての典型的な計算環境を示している。具体的には、計算環境100は、コンピュータネットワーク102と、データアグリゲータ104と、参加者106、108及び110とを含むことができる。いくつかの実施形態において、計算環境100はまた、計算環境100についての信頼できるセットアップを実行する信頼できるエンティティ112を含むこともできる。アグリゲータ104、参加者106〜110、及び、信頼できるエンティティ112は、サーバコンピュータ、デスクトップ、ラップトップ、携帯型の計算装置、又は、無線センサ等のコンピュータネットワーク102と連結された計算装置を含むことができる。さらに、コンピュータネットワーク102は、有線ネットワーク、無線ネットワーク、又は、それらの組み合わせを含むことができる。
【0013】
計算システム100は、セットアップ、ノイズのある暗号化、及び、アグリゲートの復号という少なくとも3つのキー動作を経験する。初期セットアップ動作中において、信頼できるエンティティ112は、参加者106〜110のそれぞれに対して秘密鍵を割り当てることができ、アグリゲータ104に復号能力を提供するアグリゲータ104に対して秘密鍵を割り当てることができる。具体的には、アグリゲータ104及び参加者106〜110と関連付けられた秘密鍵についての値の合計は、ゼロに等しい。この特徴は、アグリゲータの秘密鍵のみがアグリゲート値を復号(例えば個々の参加者から受信したデータ値の合計を復号)することができるように、参加者106〜110がそれらのデータを暗号化するのを許容する。
【0014】
アグリゲータ104及び参加者106〜110は、安全なマルチパーティプロトコルを使用して初期セットアップ動作を実行することができ、それにより、信頼できるエンティティ112の助けを必要としない。例えば、アグリゲータ104及び参加者106〜110は、それらの秘密鍵を公開する必要なく、その合計がゼロに等しい秘密鍵の組を判定するために互いにネゴシエートすることができる。
【0015】
ノイズのある暗号化動作中において、参加者(例えば参加者106)は、その秘密鍵を使用してデータ値を暗号化することができる。いくつかの実施形態において、参加者は、データ値を暗号化する前にノイズをデータ値に加えることができる。例えば、参加者が一定時間にわたって時系列データ値のデータ組を暗号化するとき、暗号化データ値の部分集合は、ランダムノイズを含むことができる一方で、暗号化データ値の残りの部分集合がランダムノイズを含まない。
【0016】
さらに、アグリゲート暗号化動作中において、アグリゲータ104は、一部においてその秘密鍵に基づいて、且つ、アグリゲータ104が参加者106〜110から受信した暗号化値の組に基づいて、アグリゲート値を判定する。ここで留意すべきは、アグリゲータ104が参加者106〜110のいずれかについての秘密鍵を知らないことから、アグリゲータ104は、参加者106〜110のいずれかから取得した個々のデータ値を復号することができないということである。しかしながら、本発明の実施形態によって提供されるプライベートストリームアグリゲーション技術は、アグリゲータ104が暗号化データ値の組についてのアグリゲート値を判定するために、その秘密鍵を使用するのを許容する。
【0017】
以下の段落は、計算環境100と関連付けられたプライベートストリームアグリゲーションシステムについての様々な典型的な用途を提供する。典型的なそれぞれの用途において、プライベートストリームアグリゲーション技術は、参加者(例えば個々のユーザ又は機関)が、それらの個々のデータ値をデータアグリゲータに対して公開する必要なく、データアグリゲータに対してそれらの個々のデータを提供するのを許容する。
【0018】
センサネットワークは、建物の安全を監視したり、交通量を測定したり、又は、環境汚染物質を追跡したりする等のために、様々な用途のために一般に配備されている。典型的な用途において、配備されたセンサノードは、それらの読み取り値を、パターンを識別するか又は統計値を判定するためにデータをマイニングする中央ステーションに対して周期的に送信する。多くの状況において、特にセンサが複数の参加機関にわたって配備されている場合には、個々のセンサによって作られる読み取り値は、プライバシーセンシティブであってもよい。本発明の実施形態によって提供されるプライベートストリームアグリゲーション技術は、これらの参加企業に中央ステーション(例えばアグリゲータ104)がいかなる特定のセンサノード(例えば参加者106〜110)からも詳細情報を取得しないというプライバシー保証を提供する。それゆえに、このプライバシー保証は、参加企業がその機関にわたってセンサノードを配備することによって重要な研究プロジェクトに貢献するのを促進することができる。
【0019】
他の例は、電気に関する「スマートグリッド」及び「スマートメータリング」技術の出現である。スマートメータは、月に1回とは対照的に15分毎に電気、ガス、水道使用量を読み取ること等によって従来の計器よりも非常に細かい精度で電気、ガス、水道使用量を読み取る。この電気、ガス、水道のきめの細かいサンプリングは、公共企業に機密情報を推定するのに十分な詳細情報を提供することができる。例えば、公共企業は、特定の家庭用器具の使用量とともに、家庭における個人数及びそれらの睡眠/作業習慣を推定することができてもよい。本発明の実施形態によって提供されるプライベートストリームアグリゲーション技術は、公共企業(例えば図1におけるアグリゲータ104)に、いかなる特定の家庭からも実際のきめの細かい電気、ガス、水道使用量を公開することなく、家庭の組(例えば参加者106〜110)にわたる電気、ガス、水道使用量のきめの細かいサンプリングを取得するための能力を提供することができる。これは、家庭がスマートグリッド技術に対して持つ可能性がある懸念及び心配を軽減することができ、アグリゲート統計値は、スマートグリッドオペレータがそれらの監視労力及び価格最適化を十分達成できるほどであろう。
【0020】
医学研究は、非常に医学データの利益を享受するが、プライバシーの懸念は、このデータが収集されて広められる範囲を制限する。本発明の実施形態によって提供されるプライベートストリームアグリゲーション技術は、介護人又は遠隔測定装置によって絶えずアップロードされるデータから、個人又は機関の群に及ぶ高レベルの統計値及び高レベルの統計値のみを研究者が取得するのを可能とする。
【0021】
多くの研究プロジェクト又はソフトウェア技術は、個人にわたるプライバシー懸念に拍車をかける可能性のある、ある程度の母集団調査、感知、及び、監視を実行する。例えば、ある企業のソフトウェアは、参加者の利用可能性を推定し、同僚が任意の時点でその参加者との通信のために最高の手段を識別するのを助けるために、カメラ、wifi及びコンピュータ処理から取得した参加者のデータを使用することができる。しかしながら、参加者の作業習慣についての詳細情報は、この利用可能性情報から推定されることができる。したがって、何人かのユーザは、それらの利用可能性におけるこの情報が企業管理人によって悪用され得ることを恐れて参加するのを嫌がることがある。本発明の実施形態によって提供されるプライベートストリームアグリゲーション技術は、企業が参加者の群にわたる統計情報を取得するのを可能とする一方で、参加者が選択された個人と詳細な利用可能性情報を共有するのみとするのを許容する。
【0022】
クラウドコンピューティングが人気を得るのにともない、個人及び機関は、第三者のクラウドサービスにおいてデータを保存している量が増加している。クラウドサービスプロバイダーは、様々な社会的及び経済的な目標を実現するためにこのデータにおける有益な統計値を計算することを望む。しかしながら、参加企業は、クラウドサービスのより多くの使用を行わない理由のトップとして、それらのデータのセキュリティ及びプライバシーについての懸念を挙げている。本発明の実施形態によって提供されるプライベートストリームアグリゲーション技術は、クラウドサービスプロバイダーが、個々の参加者から機密情報を取得することなく、経時的に複数の参加者からあるアグリゲート統計値を追跡するのを可能とする。
【0023】
図2は、信頼できないデータアグリゲータと安全にデータを共有するためのプロセスを示すフローチャートを表している。
【0024】
システムは、参加者の組及びデータアグリゲータと関連付けられた秘密鍵の合計がゼロに等しいように、参加者の組におけるローカル参加者のための秘密鍵を判定することによって開始することができる(工程202)。例えば、工程202は、信頼できるソースから秘密鍵を受信すること、又は、データアグリゲータ及び参加者の組のための秘密鍵を判定するために安全なマルチパーティプロトコルを使用することを含むことができる。
【0025】
次に、システムは、データアグリゲータと共有するためにデータ値の組を選択することができ(工程204)、ランダムノイズによって変更されたデータ値の組を生成するように少なくともデータ値の部分集合に対してランダム値を加えることができる(工程206、任意)。ここで留意すべきは、データ値が時系列を含むことができるということである。そして、システムは、組における個々のデータ値を暗号化し(工程208)、データアグリゲータに対して暗号化データ値を送信する(工程210)。
【0026】
アグリゲート値は、特定の期間についての参加者の組と関連付けられた個々の値の合計を含むことができる。この場合において、参加者i及び期間tについての個々のデータ値xi,tを暗号化することは、以下の式を計算することを含む。
【数1】

具体的には、ci,tは、参加者i及び期間tと関連付けられた暗号化値であり、gは、生成元であり、skは、参加者iと関連付けられた秘密鍵であり、H(t)は、ハッシュ関数である。
【0027】
アグリゲート値は、参加者の組と関連付けられた個々の値の積を含む。この場合において、参加者i及び期間tについての個々のデータ値xi,tを暗号化することは、以下の式を計算することを含む。
【数2】

【0028】
図3は、参加者の組によって提供される暗号化データからアグリゲート値を判定するためのデータアグリゲータによって実行されるプロセスを示すフローチャートを表している。
【0029】
システムは、参加者の組及びデータアグリゲータと関連付けられた秘密鍵の合計がゼロに等しいように、データアグリゲータのための秘密鍵を判定することによって開始することができる(工程302)。例えば、工程302は、信頼できるソースから秘密鍵を受信することを含むことができるか、又は、データアグリゲータ及び参加者の組のための秘密鍵を判定するために安全なマルチパーティプロトコルを使用することを含むことができる。
【0030】
次に、システムは、対応する参加者の組から暗号化データ値の組を受信することができる(工程304)。システムは、暗号化データ値の組についてのアグリゲート値を判定するために、データアグリゲータと関連付けられた秘密鍵を使用する(工程306)。そして、システムは、データアグリゲータに対してアグリゲート値を提供する(工程308)。
【0031】
アグリゲート値を推定することは、以下の式を計算することを含む。
【数3】

具体的には、ci,tは、参加者i及び期間tと関連付けられた暗号化値であり、nは、参加者の総数であり、skは、データアグリゲータと関連付けられた秘密鍵であり、H(t)は、ハッシュ関数である。
【0032】
アグリゲート値は、アグリゲート値を判定することがさらにVの離散対数を計算することを含むように、参加者の組と関連付けられた個々のデータ値の合計を含む。いくつかの実施形態において、アグリゲート値は、参加者の組と関連付けられた個々のデータ値の積を含む。
【0033】
汎用の用途において、1つのデータアグリゲータ及びn人の参加者がいてもよい。表記の便宜のために、参加者は、1,・・・,nに番号付けられ、データアグリゲータは、0に番号付けられる。例えば、秘密鍵ski≠0は、参加者と関連付けられ、秘密鍵skは、データアグリゲータと関連付けられる。さらに、[n]:={1,2,・・・,n}及びDを、参加者のデータについての許容値の所定領域を表すものとする。それゆえに、期間t∈Nについて、参加者i∈[n]と関連付けられたデータは、値xi,t∈Dを有する。
【0034】
説明を簡単にするために、参加者のデータ値についての表記は、必ずしも下付き文字tを含まなくてもよく、i∈[n]についてのデータ値xの組は、共通の期間と対応すると考えられることができる。それゆえに、x=(x,・・・,x)∈Dを、ある一定期間における全ての参加者からの値のベクトルを意味するものとする。さらに、アグリゲータは、範囲Oに属している所望の統計値を計算するために関数f(x)を使用する。それゆえに、アグリゲータは、関数f:D→Oによって表されるアグリゲート統計値を計算する。
【0035】
各参加者は、アグリゲータがユーザの入力について任意の補足情報を有し得るときでさえも、強いプライバシー保証を達成するために独立したランダムノイズを発生させることができる。具体的には、各参加者は、標本空間Ωからのノイズrがr:=(r,・・・,r)∈Ωによって表されるように、他の参加者から独立したランダムノイズrを発生させることができる。表記目的のために、ハット付きの変数は、(例えばランダム値r及びランダム関数χと関連付けられた)参加者のデータのランダム化されたバージョンを意味し、ハット付きでない変数は、元の参加者データを意味する。それゆえに、χ:D×Ω→Dを、アグリゲータに対して値を暗号化してアップロードする前に、データのノイズのあるバージョンx:=χ(x,r)を計算するために参加者によって使用されることができるランダム化関数を意味するものとする。そして、アグリゲータは、所望の統計値f(x)に導入されるノイズが所定レベルの範囲内であるように、x^:=(x^,x^,・・・,x^)の暗号化値からノイズのある統計値f(x^)を計算する。
【0036】
参加者iは、その参加者にとっての習慣である所望のデータ分布にしたがってノイズrを発生させることができる。さらに、各参加者iは、データxに対して異なるランダム化関数χ(x,r)を適用することができる。さらにより一般的なシナリオにおいて、各参加者は、暗号化された入力におけるランダム化されたアグリゲート関数f:D×Ω→Oを計算することができるアグリゲータに対してデータx及びランダム度rを送信する前に、別個にx及びrを暗号化してもよい。しかしながら、説明を簡単にするために、以下の段落は、f^(x,r)=f(x^)であるときの特別な場合を考える。さらにまた、以下の段落は、データを暗号化する前に参加者が同じランダム関数χを適用するシナリオをカバーする。
【0037】
本発明の実施形態によって提供されるプライベートストリームアグリゲーション(PSA)機構は、Setup()、NoisyEnc()及びAggrDec()といういくつかのキー関数から構成される。
【0038】
Setup(1λ):Setup()関数は、セキュリティパラメータλを取り入れ、各期間においてアグリゲート統計値を復号するためにアグリゲータによって使用されるアグリゲータskについての秘密鍵とともに、公開パラメータparam、各参加者についての秘密鍵skを出力する。各参加者iは、秘密鍵skを取得し、データアグリゲータは、能力skを取得する。信頼できるセットアップ段階の後、さらなる相互通信は、データアグリゲータに対して暗号化データ値をアップロードすることを除いて、参加者とデータアグリゲータとの間で必要とされない。
【0039】
NoisyEnc(param,sk,t,x,r):時間ステップtの間、各参加者は、ノイズrでそのデータxを符号化するためにNoisyEnc関数を呼び出す。結果は、ノイズrによってランダム化されたデータ点xのノイズのある暗号化である。NoisyEnc関数は、時々NoisyEnc(param,sk,t,x^)として書かれる。ここで、x^:=χ(x,r)は、参加者のデータのノイズのあるバージョンであり、χは、基礎となるランダム化関数である。
【0040】
AggrDec(param,sk,t,c,c,・・・,c):復号アルゴリズムは、同じ期間tについての公開パラメータparam、能力sk、及び、暗号文c,c,・・・,cを取り入れる。各i∈[n]について、c=NoisyEnc(sk,t,x^)とする。ここで、それぞれ、x^:=χ(x,r)である。x:=(x,・・・,x)及びx^:=(x^,・・・,x^)とする。復号アルゴリズムは、ターゲットとされた統計値f(x)のノイズのあるバージョンであるf(x^)を出力する。
【0041】
いくつかの実施形態において、アグリゲート関数f(x^)は、参加者の組についてのデータ値のノイズのある合計を生成する。この文脈において、参加者のデータxは、素数pについてのZに属し、アグリゲート関数は、以下として定義される。
【数4】

さらに、各参加者は、整数の組からノイズrを発生させることができ、ランダム化関数χ(x,r):=x+rmodpを適用することができる(すなわち、参加者はデータを暗号化する前に付加的ノイズを組み入れる)。
【0042】
同様に、他のいくつかの実施形態において、アグリゲート関数f(x^)は、参加者の組についてのデータ値のノイズのある積を生成する。この文脈において、アグリゲート関数は、以下として定義される。
【数5】

【0043】
図4は、本発明の実施形態にかかる参加者の組とデータアグリゲータとの間における情報の典型的な流れを示す概略図を表している。具体的には、参加者402〜406は、参加者が対応する暗号化データ値cを生成するために秘密鍵skを使用する前にノイズrをデータ値xに加えることができるように、対応する暗号化データ値を生成することができる。さらに、アグリゲータ408は、参加者402〜406から暗号化データ値を受信し、アグリゲート値410を生成するためにその秘密鍵skを使用する。
【0044】
アグリゲータ不記憶要件は、アグリゲータが、公開された統計値f(x^)から推論されることができること及び既に知っているいかなる補足データ以外の何も学習しないという保証を提供する。さらに、この要件を達成することは、適切なアグリゲータ能力(例えばアグリゲータの秘密鍵sk)がない関係者が何も学習しないということを保証する。
【0045】
直観的に、アグリゲータ不記憶要件は、以下のセキュリティ概念を満たす。
・アグリゲータは、各期間についてのノイズのある合計のみを学習することができ、それ以上は何も学習することができない。例えば、アグリゲータは、全ての参加者の暗号文の真部分集合からいかなる部分的な情報も学習することができない。
・アグリゲータの秘密鍵を知ることなく、数人の参加者が残りのユーザに対して連携を形成する場合であっても、敵対者は、暗号化データについて何も学習しない。
・アグリゲータが参加者の部分集合と共謀した場合、又は、暗号化データの部分集合が漏洩された場合、アグリゲータは、必然的に残りの参加者の合計を学習することができる。しかしながら、アグリゲータは、残りの参加者についての個々のデータ値を学習することができない。
【0046】
アグリゲータ不記憶セキュリティの概念は、合計以外の一般的な統計値まで広げられてもよい。しかしながら、敵対者が成功裏の攻撃から取得することができる情報を制限するのに格別の注意が払われなければならない。例えば、敵対者が参加者の組K⊆[n]を漏洩した場合、敵対者は、その後、これらの参加者に代わって何でも暗号化することが可能である。したがって、敵対者は、漏洩された参加者Kの組についてのいかなる所望の平文ベクトルx^={x^|i∈K}も入力することができ、平文ベクトルを暗号化することができ、そして、x^に基づいてアグリゲート統計値を復号するためにAggrDec関数を呼び出すことができる。それゆえに、セキュリティ定義は、これが敵対者についての最良且つ唯一の戦略であるという事実を反映しなければならない(すなわち、敵対者は、この攻撃から収集される情報以外の他の情報を学習することができない)。この要件は、以下の段落によって定義される。
【0047】
定義1(アグリゲータ不記憶セキュリティ):挑戦者によってどの平文ベクトル(すなわち、x又はx’)が暗号化されているかについて区別する際の無視できる程度の利点以上を有する確率的多項式時間敵対者がない場合、PSAは、記憶しないアグリゲータである。2つの平文ベクトルがそれらのアグリゲート値に対して同等であるとき、この要件は、通常満たされる。合計統計値について、この要件は、以下として定義される。
【数6】

この状態は、他の統計値と関連付けられた一般的なクエリーを満たすのがより困難であり得る。
【0048】
定義2(1回暗号化セキュリティ):それぞれの正当な参加者は、期間につき1回のみ暗号化すると期待されている。PSAは、
1)上述したセキュリティゲームにおいて無視できる程度の利点以上を有する確率的多項式時間敵対者がない。
2)以下の制約が∀i∈U、∀(x,r)∈D×Ωを保持する場合、「1回暗号化」モデルにおいて記憶しないアグリゲータであるといわれる。ここで、タプル(i,t*,x,r)は、いかなる暗号化クエリーにおいても現れない。
【0049】
以下の段落は、アグリゲータ不記憶セキュリティを達成するための暗号化構築を記述する。Gを、ディフィー・ヘルマン判定法が困難である素数の位数pの巡回群を意味するものとする。さらに、H:Z→Gを、整数を数学的群Gに写像する(ランダムオラクルとしてモデル化された)ハッシュ関数を意味するものとする。
【0050】
Setup(1λ):信頼できるセットアップ段階の間、信頼できるディーラーは、以下であるようにランダム発生器g∈G及びn+1個のランダム秘密sk∈Zを選択する。
【数7】

ここで留意すべきは、公開パラメータは、param:=gとして初期化されるということである。さらに、データアグリゲータは、能力skを取得し、参加者iは、秘密鍵skを取得する。
【0051】
それゆえに、期間tの間、各参加者は、i∈[n]についてRi,t=H(t)skiを計算し、アグリゲータは、R0,t=H(t)sk0を計算する。ここで留意すべきは、skについての合計がゼロに等しいことから、それは、以下にしたがうということである。
【数8】

この特性は、参加者が信頼できるセットアップ段階の後に互いに通信するのを必要とすることなく、NoisyEnc()及びAggrDec()演算が独立して機能するのを許容する。さらに、ディフィー・ヘルマン判定法が巡回群Gについて困難であると仮定すると、それは、数Ri,tが外見的にはランダムオラクルモデルの下でランダムであるということになる。
【0052】
NoisyEnc(param,sk,t,x^):参加者iが時間ステップtについての値x^∈Zを暗号化するため、参加者は、以下の暗号文を計算する。
【数9】

各参加者がデータ値を暗号化する前にデータ値に対してノイズを加えるとみなされると仮定すると、ランダム化された平文値は、用語x^=x+rmodpによって表される。
【0053】
AggrDec(param,sk,t,c,c,・・・,c):アグリゲータは、以下のようにアグリゲート値Vを計算する。
【数10】

その際、ここで留意すべきは、i∈[n]についてc=NoisyEnc(param,sk,t,x^)であるということである。さらに、アグリゲータ及び参加者の組についてのskがゼロになることから、以下である。
【数11】

したがって、それは、Vが以下の形式からなることになる。
【数12】

【0054】
以下の合計を復号するために、アグリゲータは、gを底とするVの離散対数を計算する。
【数13】

平文空間が小さいとき、復号は、総当たり調査によって達成されることができる。より良好なアプローチは、おおよそ平文空間における平方根の復号時間を必要とするポラードのラムダ法を使用することである。例えば、各参加者の入力が範囲{0,1,・・・,Δ}にあると仮定する。そして、参加者の合計は、範囲{0,1,・・・,nΔ}に含まれる。この場合において、復号は、ポラードの方法を使用して√(nΔ)時間を必要とする。換言すれば、nΔが多項式時間において成功裏の復号を確実にするためにセキュリティパラメータλにおける多項式であることが必要とされる。ここで留意すべきは、付加準同形の暗号化スキーム(例えば、エルガマル暗号化及びBGN 準同形暗号化)として使用されるとき、小さい平文空間の制限は、ディフィー・ヘルマンベースの暗号化スキームに特有であるということである。
【0055】
定理1:ディフィー・ヘルマン判定法の問題が群Gにおいて困難であり、ハッシュ関数Hがランダムオラクルであると仮定すると、上述した段落において提供された構築は、「1回暗号化」モデルにおいてアグリゲータ不記憶セキュリティを満たす。
【0056】
提案された暗号構築において、暗号化は、1つのディフィー・ヘルマン群における少なくとも1つのハッシュ演算(例えばSHA−256)、2つのモジュラー指数、及び、乗算を含む。実行時間は、ハッシュ関数及び群乗算を計算するための時間が指数についての時間と比較して非常に小さいことから、2つのモジュラー指数によって支配される。eBACSプロジェクトによって報告されたベンチマーク数によれば、最新の64ビットデスクトップコンピュータにおいて、古典的なディフィー・ヘルマン群モジュラー1024ビット素数を使用してモジュラー指数を計算するためにおおよそ3msかかる。「curve25519」等の高速楕円曲線を使用して、モジュラー指数を計算するために0.3msのみかかる。したがって、暗号化は、最新のコンピュータにおいておおよそ0.6msで行われることができる。アグリゲート統計値の復号は、離散対数をとることを必要とし、総当たり法を使用する場合、それぞれの可能な平文を試みるのに0.3ms必要とする1つのモジュラー指数をとる。したがって、本発明の実施形態によって提供されるPSA技術は、平文空間が小さい状況において実用的である。例えば、各参加者の平文が通信のための利用可能性を示す1ビットを含むとき、且つ、おおよそ1000人の参加者がいるとき、復号は、総当たりアプローチを使用して約0.3sで行われることができる。復号のためにポラードのラムダ法を適応することは、さらなる速度向上を提供することができ、それゆえに、約√(nΔ)まで実行時間を短縮する。ここで、nは参加者数であり、各参加者の値が組{0,1,・・・,Δ}にあると仮定する。
【0057】
本発明の実施形態は、アグリゲータが各個人の値ではなくノイズのある統計値のみを学習するということを保証する。それゆえに、個々の参加者についてのプライバシーは、最後の統計値f(x^)が十分なランダム度を累積する限り保証される。これは、各個人がより少ないランダムノイズを個々のデータ値に対して加えるのを許容する。さらに、参加者のある一部が漏洩されてデータアグリゲータと共謀することを決定したとき、それらは、それらのデータ又はランダム度をアグリゲータに対して公開することがある。この場合において、残りの漏洩されていない参加者のランダム度がそれらのプライバシーを保護するのに十分であることが望ましい。
【0058】
このプライバシーの概念は、公開された統計値におけるノイズが参加者から収集されるという事実を反映する分散型の差分プライバシー(DDプライバシー)と称される。以下の段落は、分散型の差分プライバシーの概念を定義する。
【0059】
アグリゲータが以下のようにして発生させられるn人の参加者のランダム化されたデータx^∈Dにおいて関数f:D→Oを評価するということを思い出してみよう。各参加者(i)は、ある一定の分布にしたがって独立したランダム度r∈Ωを発生させ、x:=χ(x,r)を生成するようにデータxにおいてランダム化関数χ:D×Ω→Dを適用する。x∈D及びr∈Ωを考えると、表記x^=x^(r):=(χ(x,r),χ(x,r),・・・,χ(x,r))は、いかにrにおけるx^の従属が間接的であるかを表す。さらに、参加者の部分集合Kを考えると、以下の式(数14)をKの補集合であるものとする(すなわち、以下の式(数15)である)。
【数14】

【数15】

【0060】
以下の分散型の差分プライバシー要件は、各期間t∈Nに適用される。
【0061】
定義3((ε,δ)−DDプライバシー):ε>0、0≦δ<1、及び、0<γ≦1と仮定する。データランダム化手順(すなわち、結合分布r:=(r,・・・,r)及びランダム化関数χによって与えられる)は、以下の状態が保持する場合には、関数fに関し且つ割合γの漏洩されていない一部の参加者の下で(ε,δ)−分散型の差分プライバシー(DDプライバシー)を達成する。任意の隣接ベクトルx,y≦Dについて、任意の部分集合S⊆Oについて、及び、少なくとも以下の式(数16)のγn人の大きさの漏洩されていない参加者の任意の以下の式(数17)の部分集合について。
【数16】

【数17】

【0062】
定義3において、2つのベクトルx,y∈Dは、それらが厳密に1つの座標において異なる場合、近傍又は隣接ベクトルであるといわれる。これは、厳密に1人のユーザがデータ値を変えるときにシナリオに対応する。
【0063】
Kが漏洩されたノードの組であるとき、上述した定義は、残りの正当な参加者のランダム度が差分プライバシーを確実にするのに十分であることを必要とする。したがって、確率は、漏洩された参加者からのランダム度rが条件とされている。換言すれば、確率は、正当な参加者からの以下のランダム度が引き継がれる。
【数18】

DDプライバシーの定義は、以下の式(数19)である限り、漏洩されていない参加者の任意の以下の式(数20)の組について、定義3の式が保持することを必要とする。
【数19】

【数20】

【0064】
以下の段落は、(ε,δ)−差分プライバシー保証を達成する暗号構築を構成する方法を示している。この暗号技術は、それを暗号化する前に、データ値に対してノイズを加えることによってそれら自身のデータの差分プライバシーを確実にすることに参加者を関与させる。分散型の差分プライバシー保証を達成するために、以下の2つの課題は、対処される必要がある。
【0065】
参加者個人についての差分プライバシーを確実にするために、公開された統計値は、適切な大きさのランダムノイズrを含まなければならない。現実の設定において、参加者は、互いに信頼しないことがあり、参加者の部分集合が漏洩されて、データアグリゲータと共謀することがあり得る。最悪の場合において、あらゆる参加者が他のn−1人の参加者が漏洩されてアグリゲータと共謀すると思っている場合には、参加者は、それ自身のデータのプライバシーを確実にするために十分なノイズを加えることを必要とするであろう。しかしながら、これにより、アグリゲータが所望値を超えてエラーを累積した統計値を計算する結果をもたらすであろう。
【0066】
少なくとも割合γの一部の参加者が正当であって漏洩されていない場合、ノイズ発生タスクは、これらの参加者間で分散されることができる。各参加者は、より少ないノイズを加えてもよく、最後の統計値におけるノイズが十分に大きい限り、個々のプライバシーは保護される。それゆえに、参加者がγについて下界の事前推定を有すると考えられる。しかしながら、それらは、どの参加者が漏洩されるかを厳密に知っている必要はない。各参加者は、γに依存する分布からノイズを発生させることになっている。正当な参加者は、このプロトコルにしたがうが、漏洩された参加者は、それらのノイズをデータアグリゲータに対して公開してもよく、又は、ノイズを加えないことを選択してもよい。この構築は、高確率で、公開された統計値が正当な参加者からの十分なノイズを累積することを保証する一方で、許容レベルの範囲内で最後の統計値のエラーを保持する。
【0067】
他の挑戦は、暗号構築と関連付けられた代数制約の範囲内での作業を含む。典型的な暗号化スキームは、平文値が離散値の群から抽出されることを必要とする。したがって、暗号構築は、離散群の範囲内でデータ及びノイズ値を符号化することが可能でなければならない。さらに、記憶しないアグリゲータを達成する暗号構築技術は、小さい平文空間において機能しなければならない。したがって、より共通に使用されるラプラス分布を使用する代わりに、対称幾何分布を使用することにより、そのような離散群によって作業することが可能である。
【0068】
本発明の実施形態は、離散データ値の群によって作業するために対称幾何分布を使用する。ここで留意すべきは、対称幾何分布は制限されないことから、それは、群の大きさ又は平文空間の大きさからオーバーフローすることがあるということである。それゆえに、本発明の実施形態は、そのようなオーバーフローの確率が、アグリゲータが高い成功確率でノイズのある統計値を成功裏に復号するのを許容するのに十分小さいということを確実にする。
【0069】
定義4(幾何分布):α>1とし、Geom(α)を、kにおける確率質量関数が以下であるように整数値をとる対称幾何分布を意味するものとする。
【数21】

さらに、Geom(α)を、kにおける確率質量関数が以下であるように正の整数値をとる片側幾何分布を意味するものとする。
【数22】

【0070】
対称幾何分布Geom(α)は、その確率密度関数が以下の式(数23)であるラプラス分布Lap(b)の離散バージョンとしてみられることができる(αは以下の式(数24)である)。
【数23】

【数24】

Geom分布の以下の特性は、整数値を出力する差分プライベート機構を設計するのに役に立つ。
【0071】
特性1:ε>0とし、u及びvが|u−v|≦Δであるような2つの整数であると仮定する。さらに、rを以下の分布を有する確率変数であるとする。
【数25】

そして、任意の整数kについて、Pr[u+r=k]≦exp(ε)・Pr[v+r=k]とする。
【0072】
特性1は、ターゲットとされた統計値f(x)が機密度Δを有する場合、Δに比例する大きさを有する幾何ノイズを加えることは、差分プライバシーを達成するのに十分であることを示唆する。上述したように、参加者は、アグリゲータ又は互いを信頼しない。それゆえに、アグリゲータは、アグリゲータに対して真の統計値を公開することは差分プライバシーを明らかに違反することから、ノイズ発生のタスクによって信頼されてはならない。さらに、個々の参加者は、さもなければこの指定された参加者は真の統計値も学習することが可能であることから、このタスクによっても信頼されてはならない。
【0073】
合計についてのDDプライバシーを達成するために、x=(x,・・・,x)∈D及びr=(r,・・・,r)∈Ωを、所定期間における全ての参加者からのデータ及びノイズ値をそれぞれ表すものとする。それゆえに、D=O=Z(すなわち、加法モジュロpを備える巡回群)であり、Ω=Zである。また、以下を有するアグリゲート関数sum:D→Oを考える。
【数26】

さらに、各参加者は、以下の同じランダム化関数を使用する。
【数27】

【0074】
任意の2つの要素u,v∈Zについて、|u−v|を、u=v+sp又はv=u+spであるように最小の非負整数sであるとする。さらに、Zにおける要素に対して整数を加えるとき、加算は、モジュロpを使用して実行されると考えられることができる。
【0075】
また、各参加者の元データが領域{0,1,・・・,Δ}に含まれると仮定する。それゆえに、合計の機密度は、1人の参加者の変更に関してΔである。換言すれば、単一の参加者がデータを変える場合、合計は、最大でΔだけ変わる。以下のノイズが出力に組み込まれる場合、ε−差分プライバシーが達成されるということを特性1から思い出してみよう。
【数28】

この場合において、参加者は、最後の出力統計値に対して共同してノイズを与える。目標は、少なくともγn人の参加者が正当で且つ漏洩されていない場合、同様の大きさのノイズが累積されることを確実にすることである。このようにして、差分プライバシーが保証されるのみならず、累積されたノイズは、エラーが小さいように最後の出力において制限されることを確実にされる。
【0076】
それゆえに、本発明の実施形態によって提供される暗号化機構は、(ε,δ)−DDプライバシーを保証し、その一方で、おおよそ以下の大きさの小さいエラーを確実にする。
【数29】

割合γの一定の一部の参加者が正当である限り、誤差項は、参加者数nから独立している。以下の大きさの累積されたノイズが差分プライバシーを確実するのに必要であることを考えれば、結果は最適に近い。
【数30】

さらにまた、以下の式(数31)であるときの極端な場合(すなわち、他の全ての参加者が漏洩されることがあると各参加者が考える、又は、一定数のそれらのみが正当である)を考えると、累積されたノイズは、以下の式(数32)であろう。
【数31】

【数32】

各参加者がこの場合においてプライバシーを確実にするために以下の大きさの対称ノイズを加えなければならないことから、これはまた直観的にうなずける。
【数33】

したがって、以下の式(数34)の大きさのn個の独立した対称ノイズの合計は、高確率で以下の式(数35)の大きさの最後のノイズをもたらすことにつながる。
【数34】

【数35】

【0077】
定理2(低いエラーを有するDDプライベート手順):ε>0及び0<δ<1とする。各参加者のデータがZにおける幅Δの間隔内の整数から到来すると仮定する。ここで、Δは以下である。
【数36】

また、以下であるように少なくともn人の参加者の割合γの一部が漏洩されていないと仮定する。
【数37】

そして、合計に関して(ε,δ)−DDプライベートであるr=(r,・・・,r)を発生させるようにランダム化された手順が存在する。さらに、全てのx∈(Zについて、以下の式(数38)であるように全ての0<η<1について、rのランダム選択にわたる少なくとも1−ηの確率で、以下の式(数39)である。
【数38】

【数39】

ここで、x^:=x^(r):=(x+r,x+r,・・・,x+r)pである。
【0078】
表1は、定理2における保証を達成する手順を記載している。さらなる分析は、補助定理1及び定理3の下で以下に提供される。具体的には、定理3は、どの程度ノイズのある統計値sum(x^)が真の出力sum(x)から偏差を有するかを分析する。x^以後、それは以下の大きさを制限するのに十分である。
【数40】

【表1】

【0079】
補助定理1:ε>0及び0<δ<1とする。少なくとも参加者の割合γの一部が漏洩されていないと仮定する。そして、上述したランダム化手順は、以下について、合計に関して(ε,δ)−DDプライバシーを達成する。
【数41】

【0080】
定理3(制限エラー):ε>0及び0<δ<1とする。各参加者のデータが幅Δの間隔内の整数から到来すると仮定する。ここで、Δは以下である。
【数42】

少なくともn人の参加者の以下の一部が漏洩されていないと仮定する。
【数43】

表1におけるランダム化された手順が、以下によってr:=(r,・・・,r)を生成するように実行されると仮定する。
【数44】

そして、以下の式(数45)であるように全ての0<η<1について、少なくとも1−ηの確率で、以下の式(数46)であると仮定する。
【数45】

【数46】

【0081】
定理3によれば、累積エラーは、高確率で以下によって制限される。
【数47】

各参加者の値が領域D={0,・・・,Δ}から抽出されると仮定する。そして、アグリゲータは、単に、以下の範囲内で合計を復号しようとしなければならない。ここで、pは、使用中の数学的群の大きさである。
【数48】

復号は、高確率で成功するはずである。
【0082】
定理3は、各rの積率母関数を分析することによって証明される測定濃度結果である。漏洩されていない参加者の一定の割合γの一部がある限り、エラー制限はnから独立していることに注目する。Geom(α)分布の分散が以下であることから、高確率で、エラーは、最後の回答に対して、多くてもGeom(α)の1つのコピーを加えるよりも悪い固定要因であり、それは、ε−差分プライバシーを確実にするのに必要とされるノイズの最小量である。
【数49】

【0083】
分析者は、大抵は、母集団にわたる分布を調査したいであろう。いくつかの実施形態において、PSAシステムは、アグリゲータがn人の参加者のデータの近似分布を周期的に評価するのを許容するために拡張されることができる。例えば、分布がガウシアンであると知られていると仮定すると、各参加者がその2乗と元の値を暗号化するのに十分である。これらの暗号化値を使用して、アグリゲータは、平均及び分散(又は二次モーメント)を介して分布を回収することができる。他の分布について、参加者は、より高次モーメントを暗号化することを必要としてもよい。一般に、各参加者がより多くのモーメントを暗号化するほど、アグリゲータは、より良好に分布を評価することができる。
【0084】
いくつかの実施形態において、PSAシステムは、個々の値に対してではなく、アグリゲート値(例えば個々の値の合計)に対して公開アクセスするのを可能とする。例えば、アグリゲータ能力は、sk=0に設定されることができ、それゆえに、アグリゲータの能力を公開とすることができる。また、n人の参加者は、ゼロになる値sk,・・・,skを受信する。n人の参加者及び任意の公開アグリゲータは、通常通りアグリゲート統計値の暗号化及び復号を実行する。アグリゲート合計を取得するために、離散対数が計算されなければならず、そのため、平文空間は小さくなければならない。
【0085】
いくつかの実施形態において、PSAシステムについてのプロトコルは、アクセス制御階層を提供するためにネストさせられることができ、より高レベルのエンティティは、それらの下で全ての葉ノードを介してプールされる統計値に対してアクセスする。セットアップ段階において、レベルj>1におけるエンティティは、レベル未満におけるエンティティの秘密の合計が与えられる。また、j=1(すなわち、1つのネストレベルのみ)である場合、葉ノードより上の各エンティティは、それ未満の参加者の秘密の合計の負が与えられる。
【0086】
いくつかの実施形態において、PSA機構は、合計の代わりに積の記憶しない計算をサポートする。これを達成するために、参加者は、以下としてデータ値χを暗号化する。
【数50】

もはや平文が指数ではないことから、積についてのこのスキームは、平文空間が小さいことを必要としない。
【0087】
図5は、本発明の実施形態にかかるプライバシー保護データアグリゲーションを容易とするコンピューターシステムを示している。コンピューターシステム502は、プロセッサ504と、メモリ506と、記憶装置508とを含む。さらにまた、コンピューターシステム502は、表示装置510、キーボード512、及び、ポインティングデバイス513と接続されることができる。記憶装置508は、オペレーティングシステム514、アプリケーション516、及び、データ526を記憶することができる。
【0088】
アプリケーション516は、コンピューターシステム502によって実行されるとき、コンピューターシステム502にこの開示に記載されている方法及び/又は処理を実行させる命令を含むことができる。具体的には、アプリケーション516は、秘密鍵を判定するための命令(セットアップモジュール520)と、平文値を暗号化するための命令(暗号化モジュール522)と、暗号化データ値の組からアグリゲート値を復号するための命令(アグリゲート復号モジュール524)とを含むことができる。
【0089】
データ526は、この開示において記載された方法及び/又は処理によって入力として必要とされる又は出力として生成される任意のデータを含むことができる。具体的には、データ526は、少なくとも、秘密鍵、平文データ値、ランダムノイズ値、暗号化データ値、及び、アグリゲート値を記憶することができる。
【0090】
図6は、本発明の実施形態にかかるプライバシー保護データアグリゲーションを容易とする装置を示している。装置600は、有線又は無線通信チャネルを介して互いに通信してもよい複数の機構を備えることができる。装置600は、1つ以上の集積回路を使用して実現されてもよく、また、装置600は、図6に示されるものよりも少しの又は多くの機構を含んでもよい。さらに、装置600は、コンピューターシステムにおいて一体化されてもよく、又は、他のコンピューターシステム及び/又は装置と通信することができる別個の装置として実現されてもよい。具体的には、装置600は、通信機構602と、セットアップ機構604と、暗号化機構606と、アグリゲート復号機構608とを備えることができる。
【0091】
いくつかの実施形態において、通信機構602は、データアグリゲータに対して暗号化データ値を送信し、及び/又は、参加者の組から暗号化データ値を受信するように構成されてもよい。さらに、セットアップ機構604は、秘密鍵を判定するように構成されてもよく、暗号化機構606は、平文値を暗号化するように構成されてもよく、アグリゲート復号機構608は、暗号化データ値の組からアグリゲート値を復号するように構成されてもよい。

【特許請求の範囲】
【請求項1】
データアグリゲータと機密データを共有する方法において、
ユーザの組及びデータアグリゲータと関連付けられた秘密鍵の合計がゼロに等しい、ユーザの組におけるローカルユーザのための秘密鍵を判定することと、
クライアントコンピュータにおいて、ローカルユーザと関連付けられたデータ値の組を選択することと、
暗号化データ値の組を生成するように、一部において秘密鍵に基づいて組における個々のデータ値を暗号化し、それにより、ユーザの組と関連付けられた個々のデータ値を復号することなく且つアグリゲート値を復号しながらユーザの組と情報授受することなく、データアグリゲータがユーザの組にわたってアグリゲート値を復号するのを許容することと、
データアグリゲータに対して暗号化データ値の組を送信することとを備える、方法。
【請求項2】
ローカルユーザのための秘密鍵を判定することが、信頼できるソースから秘密鍵を受信することを備える、請求項1記載の方法。
【請求項3】
ローカルユーザのための秘密鍵を判定することが、安全なマルチパーティプロトコルを使用することを備える、請求項1記載の方法。
【請求項4】
データ値の組が時系列を含み、秘密鍵が時系列における個々のデータ値の暗号化に先立って判定される、請求項1記載の方法。
【請求項5】
個々のデータ値を暗号化することが、ランダムノイズによって変更されたデータ値の組を生成するように、少なくともデータ値の部分集合に対してランダム値を加算することを含む、請求項1記載の方法。
【請求項6】
個々のデータ値を暗号化することが、個々のデータ値の高次モーメントも暗号化し、それにより、データアグリゲータがユーザの組にわたるデータ値の分布を判定するのを許容することを含む、請求項1記載の方法。
【請求項7】
コンピュータによって実行されたとき、データアグリゲータと機密データを共有する方法をコンピュータに実行させる命令を記憶する持続性コンピュータ読み取り可能な記憶媒体において、方法が、
ユーザの組及びデータアグリゲータと関連付けられた秘密鍵の合計がゼロに等しい、ユーザの組におけるローカルユーザのための秘密鍵を判定することと、
ローカルユーザと関連付けられたデータ値の組を選択することと、
暗号化データ値の組を生成するように、一部において秘密鍵に基づいて組における個々のデータ値を暗号化し、それにより、ユーザの組と関連付けられた個々のデータ値を復号することなく且つアグリゲート値を復号しながらユーザの組と情報授受することなく、データアグリゲータがユーザの組にわたってアグリゲート値を復号するのを許容することと、
データアグリゲータに対して暗号化データ値の組を送信することとを備える、方法。
【請求項8】
データアグリゲータと機密データを共有する装置において、
ユーザの組及びデータアグリゲータと関連付けられた秘密鍵の合計がゼロに等しい、ユーザの組におけるローカルユーザのための秘密鍵を判定するように構成されたセットアップ機構と、
暗号化機構と、
データアグリゲータに対して暗号化データ値の組を送信するように構成された通信機構とを備え、
暗号化機構が、
ローカルユーザと関連付けられたデータ値の組を選択し、
暗号化データ値の組を生成するように、一部において秘密鍵に基づいて組における個々のデータ値を暗号化し、それにより、ユーザの組と関連付けられた個々のデータ値を復号することなく且つアグリゲート値を復号しながらユーザの組と情報授受することなく、データアグリゲータがユーザの組にわたってアグリゲート値を復号するのを許容するように構成されている、装置。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate


【公開番号】特開2012−165374(P2012−165374A)
【公開日】平成24年8月30日(2012.8.30)
【国際特許分類】
【出願番号】特願2012−10211(P2012−10211)
【出願日】平成24年1月20日(2012.1.20)
【出願人】(502096543)パロ・アルト・リサーチ・センター・インコーポレーテッド (393)
【氏名又は名称原語表記】Palo Alto Research Center Incorporated
【Fターム(参考)】