(57)【要約】      （修正有）【課題】プライベート分散データベースに対して、データソースの識別情報及び生のデータの詳細な内容等のプライバシーが保全される統計解析を実行する。【解決手段】集約統計は、データＸ及びＹを別々に第１のランダム化をしてランダム化データ(ハット)Ｘ及び(ハット)Ｙを取得する。次に、ランダム化データ(ハット)Ｘ及び(ハット)Ｙは、第２のランダム化がされて、サーバー用のランダム化データ(チルダ)Ｘ及び(チルダ)Ｙと、クライアント用のヘルパー情報Ｔx|x及びＴy|yが取得される。ここで、Ｔは経験分布を表し、第２のランダム化は、データＸ及びＹの集約統計のプライバシーを保全する。次に、サーバーはＴx,yを求める。最後に、クライアントは、ヘルパー情報Ｔx|x及びＴy|yをＴx,yに適用して、推定された(ドット)Ｔx,yを取得する。ここで、ＸとＹとの間の「|」及び「，」は、それぞれ条件付き分布及び結合分布を表す。【選択図】図１
2014098895.tif 000002
【特許請求の範囲】
【請求項１】
プライベートデータに関する集約統計をセキュアに求めるための方法であって、
データＸ及びＹに別々に第１のランダム化を行って、それぞれランダム化データ
【数１】
2014098895.tif 000054
を取得するステップであって、該第１のランダム化は、前記データＸ及びＹのプライバシーを保全するものと、
前記ランダム化データ
【数２】
2014098895.tif 000055
に別々に第２のランダム化を行って、それぞれサーバー用のランダム化データ
【数３】
2014098895.tif 000056
と、クライアント用のヘルパー情報
【数４】
2014098895.tif 000057
とを取得するステップであって、ここで、Ｔは経験分布を表し、該第２のランダム化は、前記データＸ及びＹの前記集約統計の前記プライバシーを保全するものと、
前記サーバーにおいて、
【数５】
2014098895.tif 000058
を求めるステップと、
前記クライアントによって、前記ヘルパー情報
【数６】
2014098895.tif 000059
を
【数７】
2014098895.tif 000060
に適用して推定された
【数８】
2014098895.tif 000061
を取得するステップであって、ここで、ＸとＹとの間の「|」及び「，」は、それぞれ条件付き分布及び結合分布を表すものと、
を含む、方法。
【請求項２】
前記データＸは、第１のデータソースによって生成され、前記データＹは、第２のデータソースによって生成され、前記データＸ及びＹは、分散形式で別々に生成される、請求項１に記載の方法。
【請求項３】
前記ランダム化は、ポストランダム化方法(ＰＲＡＭ)を用いる、請求項１に記載の方法。
【請求項４】
前記第１のランダム化及び前記第２のランダム化は異なるものである、請求項１に記載の方法。
【請求項５】
前記ヘルパー情報は、前記データＸ及びＹよりも大幅に小さい、請求項１に記載の方法。
【請求項６】
前記データＸ及びＹはランダム系列であり、データ対(Ｘｉ，Ｙｉ)は独立同一分布である、請求項１に記載の方法。
【請求項７】
前記ランダム化は、前記データＸ及びＹの差分分散プライバシーを保全する、請求項１に記載の方法。
【請求項８】
前記第２のランダム化は、前記第１のランダム化によって提供される差分プライバシーよりも強い分散プライバシーを提供する、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、包括的には、第三者によるセキュアコンピューティングに関し、より詳細には、プライベート分散データベースに対してセキュアな統計解析を実行することに関する。
【背景技術】
【０００２】
ビッグデータ
毎日、２．５クィンティリオン(１０１８)(２５０京)バイトのデータが生成されていると推定されている。これは、今日の世界の全てのデータの９０％がここ２年で生成されたことを意味する。この「ビッグ」データは、ソーシャルメディア、映像及びビデオ、金融取引、電話、政治、医療機関、学術機関、及び金融機関、並びに民間企業といったあらゆる場所から生じる。言うまでもなく、このデータは、「クラウド」として知られてきているものに高度に分散している。
【０００３】
このデータは、統計的に解析する必要がある。多くの用途の場合、データは、プライベートであり、解析はセキュアであることを要する。セキュアとは、本明細書で用いられるとき、データのソースの識別情報及び生のデータの詳細な内容等のデータのプライバシーが保全されることを意味する。ランダム化応答は、これを行う１つの従来技術の方法である。ランダム化応答は、特定の応答者(respondent：応答側)の応答を明確に明らかにしないが、平均又は分散等の集約統計尺度は、依然として求めることができる。
【０００４】
差分プライバシー(ＤＰ)は、ラプラスノイズ等のランダム化関数を用いることによってプライバシーを保全するもう１つの方法である。非公式には、差分プライバシーは、応答者のデータベース上で求められた関数の結果が特定の応答者の有無の影響をほとんど受けないことを意味する。公式には、その関数が、１人の応答者のみが異なる隣接データベース上で評価される場合、同じ結果を出力する確率は、ほとんど変化しない。
【０００５】
ｋ匿名性等のプライバシーのための従来のメカニズムは、差分プライベートではない。なぜならば、敵対者は、任意の量のヘルパー(サイド)情報を匿名データにリンクして匿名性を無効にすることができるからである。
【０００６】
差分プライバシーを提供するのに用いられる他のメカニズムは、通常、出力摂動を伴い、例えば、ノイズがデータの関数に追加される。それにもかかわらず、ノイズがデータ自体に追加されるこのランダム化応答メカニズムは、ＤＰを提供することを示すことができる。
【０００７】
あいにく、ＤＰは、応答者のプライバシーの厳格で最悪の場合の特徴付けを提供するが、データの経験確率分布又は「タイプ」のプライバシーを定式化するには十分ではない。特に、敵対者が、隣接する匿名データベースにアクセスした場合、ＤＰメカニズムは、敵対者がどの応答者も非匿名化することができないことを保証する。しかしながら、構成によっては、匿名データベースを処理することによって、データの分布が明らかにされる。
【０００８】
したがって、応答者のプライバシーを保全するとともに、経験確率分布も敵対者から保護することが必要とされている。
【０００９】
特許文献１では、出願人は、信頼できない第三者サーバーによってデータを処理するための方法を開示している。このサーバーは、データに関する集約統計を求めることができ、クライアントは、アウトソーシングされたデータを正確に取り出すことができる。このプロセスでは、データは符号化されているので、データベース内の個々のエントリーは、サーバーには明らかにされない。この方法は、誤り訂正符号の組み合わせ及びランダム化応答を用い、これによって、応答の機密性を維持しつつ、当該応答を検知することが可能になる。
【００１０】
特許文献２では、出願人は、信頼できない第三者によってデータをセキュアに処理するための方法を開示している。この方法は、クライアントデータを信頼できないサーバーにアウトソーシングして結果を生成することを可能にする暗号学的にセキュアな擬似乱数発生器を用いる。これらの結果は、データに関する正確な集約統計及びデータに関する監査報告を含むことができる。いずれの場合も、サーバーは、変更されたデータを処理して正確な結果を生成する一方、基礎となるデータ及び結果は、サーバーに明らかにされない。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】米国特許出願第１３／０３２，５２１号
【特許文献２】米国特許出願第１３／０３２，５５２号
【発明の概要】
【発明が解決しようとする課題】
【００１２】
この発明の実施の形態は、データのプライバシーを保全しつつそのデータを統計的に解析するための方法を提供する。
【００１３】
例えば、アリス及びボブは、応答者に関係した情報を含む別々のデータベースの互いに信頼できないソースである。データベースにおける応答者のプライバシーを保持しつつ、認可されたエンティティによるデータの正確な統計解析を可能にするために、データをサニタイズして公開することが望まれている。さらに、敵対者は、データの解析が可能であってはならない。
【課題を解決するための手段】
【００１４】
実施の形態は、このタイプの問題のためのプライバシー及び有用性の理論的定式化を提供する。個々の応答者のプライバシーは、ε差分プライバシー(ε-differential privacy)を用いて定式化される。分散データベースに関する統計のプライバシーは、δ分散プライバシー(δ-distributional privacy)及びε差分プライバシーを用いて定式化される。
【００１５】
具体的には、データＸ及びＹに別々に第１のランダム化をして、ランダム化データ
【００１６】
【数１】
2014098895.tif 000003
【００１７】
を取得することによって、集約統計が求められる。この第１のランダム化は、データＸ及びＹのプライバシーを保全する。
【００１８】
次に、ランダム化データ
【００１９】
【数２】
2014098895.tif 000004
【００２０】
に、第２のランダム化がされて、サーバー用のランダム化データ
【００２１】
【数３】
2014098895.tif 000005
【００２２】
と、クライアント用のヘルパー情報
【００２３】
【数４】
2014098895.tif 000006
【００２４】
とが取得される。ここで、Ｔは経験分布を表し、第２のランダム化は、データＸ及びＹの集約統計のプライバシーを保全する。
【００２５】
次に、サーバーは、
【００２６】
【数５】
2014098895.tif 000007
【００２７】
を求める。最後に、クライアントは、サイド情報(ヘルパー情報)
【００２８】
【数６】
2014098895.tif 000008
【００２９】
を
【００３０】
【数７】
2014098895.tif 000009
【００３１】
に適用して、推定された
【００３２】
【数８】
2014098895.tif 000010
【００３３】
を取得する。ここで、ＸとＹとの間の「|」及び「，」は、それぞれ条件付き分布及び結合分布を表す。
【発明の効果】
【００３４】
この発明の実施の形態は、分散環境において、認可されているがおそらく信頼できないクライアントによってサーバーに格納されているサニタイズされたプライベートデータを統計的に解析するための方法を提供する。
【００３５】
クライアントは、データソースのプライバシーを脅かすことなく、分散データベースに関する経験結合統計を求めることができる。加えて、認可されていない関係者がサニタイズされたデータにアクセスすることに対しては、差分プライバシー保証が提供される。
【図面の簡単な説明】
【００３６】
【図１】この発明の実施の形態によるプライベートデータに関する統計をセキュアに求めるための方法の流れ図である。
【図２】この発明の実施の形態による、操作を受ける２つのソースからのプライベートデータのブロック図である。
【図３】データのプライバシーを脅かすことなく第三者によって図２のデータから統計を導出するためのこの発明の実施の形態による方法の概略図である。
【図４】この発明の実施の形態による方法の適用の概略図である。
【発明を実施するための形態】
【００３７】
方法の概要
図１に示すように、この発明の実施の形態は、プライベートデータに対して統計解析をセキュアに実行するための方法を提供する。これは、実際の生のデータがこのデータのソース以外の誰にも明らかにされないことを意味する。
【００３８】
セキュリティアプリケーション、プライバシーアプリケーション、及びランダム化アプリケーションにおいて、「弱い」及び「強い」は、よく理解され文書化されている専門用語である。弱いとは、基礎となるデータ(例えば、パスワード、ユーザー識別情報等)を、既知の「クラッキング」方法を用いて回復することができることを意味する。強いとは、妥当な時間量及び妥当な計算リソースが与えられた際に、データを回復することが非常に困難であることを意味する。
【００３９】
加えて、ランダム化は、特定の分布に従ってデータをランダム化することを意味する。この用語は次の概念を包含する。第１に、データは、プライバシーを保護するように匿名化される。第２に、データは、操作が、このデータを公開に対して安全にするという目的を果たすという考えを強化するようにサニタイズされる。
【００４０】
データＸ１０１及びＹ１０２が、別々に第１のランダム化がされて(ＲＡＭ１)、それぞれランダム化データ
【００４１】
【数９】
2014098895.tif 000011
【００４２】
が取得される。ランダム化１１０及び１１５は、同じものとすることもできるし、異なるものとすることもできる。好ましい実施の形態では、ポストランダム化方法(ＰＲＡＭ：Post RAandomisation Method)が用いられる。１１０及び１１５によって提供されるセキュリティは、比較的「弱い」。これは、データソースの識別情報は秘匿され、個々のデータプライバシーは保全されるが、データに関する集約統計はおそらく多少の作業で求めることができることを意味する。
【００４３】
ランダム化データ
【００４４】
【数１０】
2014098895.tif 000012
【００４５】
は、再度(第２)のランダム化がされて(ＲＡＭ２)、それぞれ、サーバー用のランダム化データ
【００４６】
【数１１】
2014098895.tif 000013
【００４７】
と、クライアント用のヘルパー情報
【００４８】
【数１２】
2014098895.tif 000014
【００４９】
とが取得される。この第２のランダム化は、第１のランダム化と同じものとすることもできるし、異なるものとすることもできる。ヘルパー情報において、Ｔは真の経験分布を表す。
【００５０】
統計において、経験分布は、データの正規化されたヒストグラムである。ｎ個のデータポイントのそれぞれは、１／ｎずつ経験分布に寄与する。経験分布は、基礎となるデータを代表する。経験分布は、平均、中央値、モード、歪度(skewedness：スキュードネス)、変位値等を含む多数の異なるタイプの統計を求めるのに十分である。
【００５１】
１２０及び１２５によって提供されるセキュリティは、比較的「強い」。すなわち、データＸ及びＹに関する集約統計のプライバシーは保全される。
【００５２】
サーバー１３０は、
【００５３】
【数１３】
2014098895.tif 000015
【００５４】
が組み合わされた後に、
【００５５】
【数１４】
2014098895.tif 000016
【００５６】
を求める。
【００５７】
クライアント１３０ａは、この時点で、サイド情報
【００５８】
【数１５】
2014098895.tif 000017
【００５９】
を
【００６０】
【数１６】
2014098895.tif 000018
【００６１】
に適用して、第２のランダム化を「解除」し、推定された
【００６２】
【数１７】
2014098895.tif 000019
【００６３】
を取得することができる。符号上の「・」によって示される、推定されたデータＸ及びＹの分布は、一次統計、二次統計等を取得するのに十分である。クライアントは、統計を求めることはできるが、弱いセキュリティのために、正確なデータＸ及びＹを回復することはできない。
【００６４】
方法の詳細
この説明を簡略化するために、図２に示すように、２つのデータソースであるアリス及びボブを用いたこの発明の問題定式化及び結果を提示する。しかしながら、この発明の方法は、３つ以上のソースに容易に一般化することができる。また、上記よりも少ないか又は多いランダム化を用いた他のセキュリティレベルも用いることができる。
【００６５】
アリス及びボブは、データ２０１及び２０２を別々にサニタイズして(２１０)、応答者２０５のプライバシーを保護する。本明細書では、サニタイズされたデータから正確なプライベート情報を回復することは不可能である。例えば、ランダムノイズを加えるといった、データをサニタイズするための多くの技法が知られている。
【００６６】
サニタイズされたデータ２１１及び２１２は、組み合わされて(２２０)、「クラウド」サーバーにおけるデータベース２３０に入れられる。サーバーは、公衆ネットワーク(インターネット)に接続することができる。これによって、データは、クライアントの認可されたユーザーによる統計解析に利用可能である。
【００６７】
図３に示すように、アリス及びボブは、サニタイズされたデータをサーバーに格納して、これらの潜在的に大きなデータベース上で必要とされる送信及び計算を容易にする。信頼できない認可されたクライアント３０１は、この時点で、低い割合のヘルパー情報３０３の援助を受けて、データに対して統計解析を実行することができる。このヘルパー情報は、元のデータベース及び／又はランダム化データと比較して相対的に小さいという点で低い割合である。ヘルパー情報３０３によって、認可されたクライアントは、第２のランダム化を本質的に解除することが可能になる。
【００６８】
この解析は、次の要件を条件とする。ソースのプライベートデータは、サーバーにもクライアントにも明らかにされるべきではない。ソース及びボブによって提供されたデータの統計は、サーバーに明らかにされるべきではない。クライアントは、アリス及びボブによって提供されたデータの結合分布、周辺分布及び条件付き分布を求めることができるべきである。これらの分布は、データの一次統計、二次統計等を求めるのに十分である。
【００６９】
問題の枠組み及び表記
アリスのデータは、確率変数系列(太字)Ｘ：＝(Ｘ１，Ｘ２，…，Ｘｎ)である。ここで、各変数Ｘｉは、有限アルファベット(ゴシック)Ｘからの値を取る。同様に、ボブのデータは、確率変数系列(太字)Ｙ：＝(Ｙ１，Ｙ２，…，Ｙｎ)としてモデル化される。ここで、各Ｙｉは、有限アルファベット(ゴシック)Ｙからの値を取る。これらの系列の長さｎは、データベース内の応答者の総数を表し、各(Ｘｉ，Ｙｉ)対は、アリス及びボブによって一括して保持された応答者ｉのデータを表す。ここで、アルファベット(ゴシック)Ｘ×(ゴシック)Ｙは、各応答者のデータの定義域を表す。
【００７０】
データ対(Ｘｉ，Ｙｉ)は、(太字)ｘ：＝(ｘ１，…，ｘｎ)∈(ゴシック)Ｘｎ及び(太字)ｙ：＝(ｙ１，…，ｙｎ)∈(ゴシック)Ｙｎについて、
【００７１】
【数１８】
2014098895.tif 000020
【００７２】
となるように、(ゴシック)Ｘ×(ゴシック)Ｙにわたる結合分布ＰＸ，Ｙに従って、独立同一分布(ｉ．ｉ．ｄ．)である。
【００７３】
プライバシーメカニズムは、条件付き分布ＰＯ|Ｉに従って入力を出力にランダムにマッピング(Ｍ：(ゴシック)Ｉ→(ゴシック)Ｏ)する(３１０)。ポストランダム化方法(ＰＲＡＭ)は、入力及び出力がともに系列、すなわち、アルファベット(ゴシック)Ｄについて(ゴシック)Ｉ＝(ゴシック)Ｏ＝(ゴシック)Ｄｎであり、入力系列の各要素が要素ごとの条件付き分布に従ったｉ．ｉ．ｄ．であるプライバシーメカニズムの一部類である。
【００７４】
アリス及びボブはそれぞれ、ＲＡ：(ゴシック)Ｘｎ→(ゴシック)Ｘｎ及びＲＢ：(ゴシック)Ｙｎ→(ゴシック)Ｙｎとして、それらのデータにＰＲＡＭを別々に適用する。それぞれの出力は、
【００７５】
【数１９】
2014098895.tif 000021
【００７６】
であり、支配分布(governing distribution)は、
【００７７】
【数２０】
2014098895.tif 000022
【００７８】
である。そのため、
【００７９】
【数２１】
2014098895.tif 000023
【００８０】
の式が得られる。
【００８１】
【数２２】
2014098895.tif 000024
【００８２】
によって定義されるＲＡＢ：(ゴシック)Ｘｎ×(ゴシック)Ｙｎ→(ゴシック)Ｘｎ×(ゴシック)Ｙｎを用いて、各個々のメカニズムの連鎖からもたらされるメカニズムも示される。ＲＡＢも、ＰＲＡＭメカニズムであり、条件付き分布
【００８３】
【数２３】
2014098895.tif 000025
【００８４】
によって支配される。
【００８５】
タイプ表記
確率変数系列(太字)Ｘ：＝(Ｘ１，…，Ｘｎ)のタイプ又は経験分布は、
【００８６】
【数２４】
2014098895.tif 000026
【００８７】
によって定義されるマッピングＴ(太字)Ｘ：(ゴシック)Ｘ→［０，１］である。
【００８８】
２つの系列(太字)Ｘ：＝(Ｘ１，…，Ｘｎ)及び(太字)Ｙ：＝(Ｙ１，…，Ｙｎ)の結合タイプは、
【００８９】
【数２５】
2014098895.tif 000027
【００９０】
によって定義されるマッピングＴ(太字)Ｘ，(太字)Ｙ：(ゴシック)Ｘ×(ゴシック)Ｙ→［０，１］である。
【００９１】
別の(太字)Ｘ：＝(Ｘ１，…，Ｘｎ)を所与とした系列(太字)Ｙ：＝(Ｙ１，…，Ｙｎ)の条件付きタイプは、
【００９２】
【数２６】
2014098895.tif 000028
【００９３】
によって定義されるマッピングＴ(太字)Ｙ|(太字)Ｘ：(ゴシック)Ｙ×(ゴシック)Ｘ→［０，１］である。
【００９４】
条件付き分布は、結合分布が周辺分布によって除算されたものである。
【００９５】
これらのタイプマッピングの値は、基礎となる系列を所与として求められ、これらの系列がランダムであるとき、ランダムである。
【００９６】
分布及びタイプのための行列表記
有限アルファベット確率変数の様々な分布及びタイプは、ベクトル又は行列として表すことができる。それらの有限の定義域において一貫した順序付けを固定することによって、これらのマッピングは、それらの定義域によってインデックス付けされたベクトル又は行列とすることができる。分布ＰＸ：(ゴシック)Ｘ→［０，１］は、そのｘ番目の要素(ｘ∈(ゴシック)Ｘ)が(太字)ＰＸ［ｘ］：＝ＰＸ(ｘ)によって与えられる|(ゴシック)Ｘ|×１列ベクトル(太字)ＰＸとして記述することができる。
【００９７】
条件付き分布ＰＹ|Ｘ：(ゴシック)Ｙ×(ゴシック)Ｘ→［０，１］は、(太字)ＰＹ|Ｘ［ｙ，ｘ］：＝ＰＹ|Ｘ(ｙ|ｘ)によって定義される|(ゴシック)Ｙ|×|(ゴシック)Ｘ|行列(太字)ＰＹ|Ｘとして記述することができる。結合分布ＰＸ，Ｙ：(ゴシック)Ｘ×(ゴシック)Ｙ→［０，１］は、(太字)ＰＸ，Ｙ［ｘ，ｙ］：＝ＰＸ，Ｙ(ｘ，ｙ)によって定義される|(ゴシック)Ｘ|×|(ゴシック)Ｙ|行列(太字)ＰＸ，Ｙか、又は(太字)ＰＸ，Ｙの列をスタックすることによって形成される|(ゴシック)Ｘ||(ゴシック)Ｙ|×１列ベクトル
【００９８】
【数２７】
2014098895.tif 000029
【００９９】
とし記述することができる。
【０１００】
対応するタイプマッピングに関して、系列(太字)Ｘ及び(太字)Ｙについて同様に定義される(太字)Ｔ(太字)Ｘ、(太字)Ｔ(太字)Ｙ|(太字)Ｘ、(太字)Ｔ(太字)Ｘ，(太字)Ｙ、及び
【０１０１】
【数２８】
2014098895.tif 000030
【０１０２】
を用いて、タイプのための行列表記を同様に作成することができる。これらのタイプベクトル又はタイプ行列は、ランダム量である。
【０１０３】
プライバシー及び有用性の条件
次に、別々にサニタイズされたデータに関する統計を計算するこの問題のプライバシー及び有用性の要件を定式化することにする。上述したプライバシーの要件によれば、この定式化は、応答者のプライバシー、分布のプライバシー、及び最後にクライアントの有用性を考慮する。
【０１０４】
応答者のプライバシー
応答者に関係したデータは、認可された、おそらく信頼できないあらゆるクライアントを含む他の全ての関係者からプライベートに保たれなければならない。この概念は、応答者用のε差分プライバシーを用いて形式化される。
【０１０５】
定義：ε≧０の場合、ハミング距離ｄＨ((太字)ｄ，(太字)ｄ’)≦１内の全てのデータセット(太字)ｄ，(太字)ｄ’∈(ゴシック)Ｄｎ及び全ての(ゴシック)Ｓ⊆(ゴシック)Ｏについて、
【０１０６】
【数２９】
2014098895.tif 000031
【０１０７】
である場合、ランダム化メカニズムＭ：(ゴシック)Ｄｎ→(ゴシック)Ｏは、ε差分プライバシーを与える。
【０１０８】
応答者が、ｉ．ｉ．ｄ．であるようにサンプリングされると仮定すると、ＤＰを満たすプライバシーメカニズムは、結果として、強いプライバシー保証をもたらす。１人を除く全ての応答者の知識を有する敵対者は、唯一の見つからない応答者のデータを発見することができない。このプライバシーの概念は、厳格であるとともに広く受け入れられ、プライバシーの公理(privacy axioms)を満たす。
【０１０９】
分布のプライバシー
アリス及びボブは、データの統計を敵対者にもサーバーにも明らかにしたくない。したがって、ソース及びサーバーは、経験分布、すなわち、周辺タイプ及び結合タイプを
【０１１０】
【数３０】
2014098895.tif 000032
【０１１１】
から回復することができないことを確保しなければならない。上述したように、εＤＰは、この場合にプライバシーを特徴付けるのに用いることができない。経験確率分布のためのプライバシー概念を定式化するために、以下のようにε差分プライバシーが拡張される。
【０１１２】
定義：(δ分布ε差分プライバシー)ｄ(・，・)を分布の空間における距離メトリックとする。ε，δ≧０の場合、ｄ((太字)Ｔ(太字)ｄ，(太字)Ｔ(太字)ｄ’)≦δである全てのデータセット(太字)ｄ，(太字)ｄ’∈(ゴシック)Ｄｎ及び全ての(ゴシック)Ｓ⊆(ゴシック)Ｏについて、
【０１１３】
【数３１】
2014098895.tif 000033
【０１１４】
である場合、ランダム化メカニズムＭ：(ゴシック)Ｄｎ→(ゴシック)Ｏは、δ分布ε差分プライバシーを与える。
【０１１５】
より大きなδ及びより小さなεは、分布のより良好な保護を提供する。この発明者らの定義は、プライバシーの公理も満たす。
【０１１６】
認可されたクライアントのための有用性
認可されたクライアントは、ランダム化データベース２３０から統計を抽出する。この問題は、結合及び周辺タイプ関数Ｔ(太字)Ｘ，(太字)Ｙ(ｘ，ｙ)、Ｔ(太字)Ｘ(ｘ)、及びＴ(太字)Ｙ(ｙ)、又は(等価的に)行列(太字)Ｔ(太字)Ｘ，(太字)Ｙ、(太字)Ｔ(太字)Ｘ、及び(太字)Ｔ(太字)Ｙの再構成としてモデル化される。サーバーは、サニタイズされたデータ
【０１１７】
【数３２】
2014098895.tif 000034
【０１１８】
に基づく計算を提供することによってこの再構成を容易にする。アリス及びボブは、別々に生成された低い割合のヘルパー情報３０３を提供する。クライアントは、サーバーの計算及びヘルパー情報を用いて、推定値
【０１１９】
【数３３】
2014098895.tif 000035
【０１２０】
を生成する。
【０１２１】
分布の空間にわたる距離メトリックｄ(・，・)について、推定値の期待有用性(expected utility)が、以下のように定義される。
【０１２２】
【数３４】
2014098895.tif 000036
【０１２３】
プライバシーの要件の解析
距離関数ｄは、共通の分布距離尺度によって共有される一般特性を満たすので、データベースの周辺タイプのプライバシー保護は、結合タイプのためのプライバシー保護を含意する。
【０１２４】
補助定理１：ｄ(・，・)を、以下の式となるような距離関数とする。
【０１２５】
【数３５】
2014098895.tif 000037
【０１２６】
ＭＡＢを、ＭＡＢ((太字)Ｘ，(太字)Ｙ)：＝(ＭＡ((太字)Ｘ)，ＭＢ((太字)Ｙ))によって定義されるプライバシーメカニズムとする。ＭＡがδ分布ε１差分プライバシーを満たし、ＭＢがδ分布ε２差分プライバシーを満たす場合、ＭＡＢは、δ分布(ε１＋ε２)差分プライバシーを満たす。
【０１２７】
縦に分割されたデータが別々にサニタイズされ、サニタイズされたテーブルから結合分布を回復することが希望されている場合、プライバシーメカニズムの選択は、ＰＲＡＭ手順の部類に制限される。ＰＲＡＭアルゴリズムがプライバシー制約を満たすようにＰＲＡＭアルゴリズムに課せられるべき制約が解析される。先ず、アリス及びボブのデータベース内の応答者のプライバシーの要件を検討する。
【０１２８】
補助定理２：Ｒ：(ゴシック)Ｘｎ→(ゴシック)Ｘｎを、条件付き分布
【０１２９】
【数３６】
2014098895.tif 000038
【０１３０】
によって支配されるＰＲＡＭメカニズムとする。
【０１３１】
【数３７】
2014098895.tif 000039
【０１３２】
である場合、ＲはεＤＰを満たす。
【０１３３】
補助定理３：ＭＡＢ((太字)ｘ，(太字)ｙ)＝(ＭＡ((太字)ｘ)，ＭＢ((太字)ｙ))であると定義する。ＭＡがε１ＤＰを満たし、ＭＢがε２ＤＰを満たす場合、ＭＡＢは(ε１＋ε２)ＤＰを満たす。
【０１３４】
この補助定理は、ｉ番目のソースのサニタイズされたデータがεｉＤＰを満たす場合に、結合システムが
【０１３５】
【数３８】
2014098895.tif 000040
【０１３６】
を提供するとき、ｋ個のソースに拡張することができる。次に、結合タイプ及び周辺タイプのためのプライバシーの要件を検討する。
【０１３７】
補助定理４：ｄ(・，・)を、分布の空間における距離メトリックとする。Ｒ：(ゴシック)Ｘｎ→(ゴシック)Ｘｎを、条件付き分布
【０１３８】
【数３９】
2014098895.tif 000041
【０１３９】
によって支配されるＰＲＡＭメカニズムとする。
【０１４０】
必要条件：Ｒがδ分布εＤＰを満たす場合、Ｒは、応答者について
【０１４１】
【数４０】
2014098895.tif 000042
【０１４２】
を満たさなければならない。
【０１４３】
十分条件：Ｒが応答者について
【０１４４】
【数４１】
2014098895.tif 000043
【０１４５】
を満たす場合、Ｒは、δ分布εＤＰを満たす。
【０１４６】
例示の実施態様
次に、上記で与えたシステムの枠組みの実現例を説明する。この実現例において、プライバシーメカニズムは、この発明のプライバシー及び有用性の要件を満たすように選択される。このシステムの重要な要件は、以下のように要約することができる。
(I)．ＲＡＢは、δ分布ε差分プライベートメカニズムであり、
(II)．ヘルパー情報は、εＤＰアルゴリズムによって生成され、
(III)．ＲＡ及びＲＢは、ＰＲＡＭメカニズムである。
【０１４７】
サニタイズされたデータは、δ分布ε差分プライベートメカニズムによって生成されるので、ヘルパー情報は、周辺タイプ及び結合タイプを正しく推定するのに必要である。種々のレベルのプライバシーを保全する出力を生成するために、ソースは、マルチレベルプライバシー手法を用いる。
【０１４８】
図４に示すように、データベースは、２パスのランダム化プロセス４１０によってサニタイズされる(図１参照)。第１のパスＲＡＢ，１は、生のソースデータ(太字)Ｘ、(太字)Ｙを入力として取り込み、応答者プライバシーを保証する一方、第２のパスＲＡＢ，２は、第１のパスのサニタイズされた出力
【０１４９】
【数４２】
2014098895.tif 000044
【０１５０】
を入力として取り込み、分散プライバシーを保証する。ヘルパー情報３０３は、第２のパスの間に抽出され、応答者プライバシーを保全する。これらのメカニズムは、以下の制約を用いて構成される。
(i)．ＲＡ，２及びＲＢ，２は(ε／２ｎ)-ＤＰ
(ii)．ＲＡ，１及びＲＢ，１は(ε／２)-ＤＰ
(iii)．ＲＡ，１、ＲＡ，２、ＲＢ，１、及びＲＢ，２はＰＲＡＭメカニズムである。
【０１５１】
補助定理３によって、制約(ii)は、ＲＡＢ，１がεＤＰであることを含意し、したがって、要件(II)を含意する。ＲＡ((太字)Ｘ)は、ＲＡ，２(ＲＡ，１((太字)Ｘ))とみなすことができ、条件付き分布(行列表記による)
【０１５２】
【数４３】
2014098895.tif 000045
【０１５３】
によって支配されることに留意されたい。
【０１５４】
したがって、制約(iii)は、要件(III)が満たされることを含意する。補助定理１及び４によって、制約(i)は、要件(I)が満たされることを含意する。ここで、全てのプライバシーの要件が満たされる。以下では、クライアントが、推定されたタイプをどのように求めることができるのかを説明する。
【０１５５】
ヘルパー情報がない場合、要件(I)に起因して、クライアントは正確なタイプを正しく推定することができないことを想起されたい。この例では、ヘルパー情報は、第２のパスの間に求められた条件付きタイプ
【０１５６】
【数４４】
2014098895.tif 000046
【０１５７】
を含む。
【０１５８】
【数４５】
2014098895.tif 000047
【０１５９】
から求められた(太字)Ｔ(太字)Ｘの不偏推定値が、
【０１６０】
【数４６】
2014098895.tif 000048
【０１６１】
によって与えられ、正確なタイプは、
【０１６２】
【数４７】
2014098895.tif 000049
【０１６３】
によって回復することができる。したがって、以下の識別情報及び推定量が得られる。
【０１６４】
【数４８】
2014098895.tif 000050
【０１６５】
結合タイプを求めるようにこれらの結果を拡張することは、幾つかの課題を提示する。集合的メカニズム(collective mechanism)ＲＡＢの条件付き分布の行列形式は、
【０１６６】
【数４９】
2014098895.tif 000051
【０１６７】
によって与えられる。ここで、
【０１６８】
【数５０】
2014098895.tif 000052
【０１６９】
はクロネッカー積である。結合タイプの不偏推定値は、以下の式
【０１７０】
【数５１】
2014098895.tif 000053
【０１７１】
によって与えられる。
【図１】
2014098895.tif 000062
【図２】
2014098895.tif 000063
【図３】
2014098895.tif 000064
【図４】
2014098895.tif 000065
【外国語明細書】
2014098895.tif 000066
2014098895.tif 000067
2014098895.tif 000068
2014098895.tif 000069
2014098895.tif 000070
2014098895.tif 000071
2014098895.tif 000072
2014098895.tif 000073
2014098895.tif 000074
2014098895.tif 000075
2014098895.tif 000076
2014098895.tif 000077
2014098895.tif 000078
2014098895.tif 000079
2014098895.tif 000080
2014098895.tif 000081
2014098895.tif 000082
2014098895.tif 000083
2014098895.tif 000084
2014098895.tif 000085
2014098895.tif 000086
2014098895.tif 000087
2014098895.tif 000088
2014098895.tif 000089
2014098895.tif 000090