(57)【要約】      （修正有）【課題】サーバーに記憶されたクライアントデータから、データのプライバシーを保護しながら集約統計を取得する方法を提供する。【解決手段】最初に１つ又は複数のクライアントにおいて独立した第１のデータ及び第２のデータをサンプリングして、サンプリングされたデータを得ることによって、プライベートデータに関する集約統計がセキュアに求められる。ここで、サンプリングパラメーターはデータの長さよりも実質的に小さい。サンプリングされたデータは暗号化されて暗号化データが得られ、次にこの暗号化データが結合される。結合された暗号化データはランダム化され、ランダム化されたデータが得られる。認可された第三者プロセッサにおいて、ランダム化された暗号化データから、第１のデータ及び第２のデータの差分プライバシー要件が満たされるように、それらの第１のデータ及び第２のデータの結合分布が推定される。【選択図】図１
2014178680.tif 000002
【特許請求の範囲】
【請求項１】
プライベートデータに関する集約統計をセキュアに求める方法であって、
１つ又は複数のクライアントプロセッサにおいて、データＸｎ及びＹｎをサンプリングするステップであって、サンプリングされたデータ
【数１】
2014178680.tif 000092
及び
【数２】
2014178680.tif 000093
を取得し、ここで、ｍは前記データの長さｎよりも実質的に小さいサンプリングパラメーターである、ステップと、
前記サンプリングされたデータ
【数３】
2014178680.tif 000094
及び
【数４】
2014178680.tif 000095
を暗号化するステップであって、暗号化データ
【数５】
2014178680.tif 000096
及び
【数６】
2014178680.tif 000097
を得る、ステップと、
前記暗号化データ
【数７】
2014178680.tif 000098
及び
【数８】
2014178680.tif 000099
を結合するステップであって、結合された暗号化データを得る、ステップと、
前記結合された暗号化データをランダム化するステップであって、ランダム化されたデータ
【数９】
2014178680.tif 000100
、
【数１０】
2014178680.tif 000101
を得る、ステップと、
認可された第三者プロセッサにおいて、前記ランダム化された暗号化データ
【数１１】
2014178680.tif 000102
、
【数１２】
2014178680.tif 000103
から、前記データＸｎ及びＹｎに対する差分プライバシー要件が満たされるように該データＸｎ及びＹｎの結合分布
【数１３】
2014178680.tif 000104
を推定するステップと、
を含む、プライベートデータに関する集約統計をセキュアに求める方法。
【請求項２】
前記データＸｎ及びＹｎを前記サンプリングするステップ及び前記暗号化するステップは、前記１つ又は複数のクライアントプロセッサによって実行され、前記結合するステップ及び前記ランダム化するステップはサーバープロセッサによって実行され、前記推定するステップは前記認可された第三者プロセッサによって実行される、請求項１に記載の方法。
【請求項３】
前記暗号化は、前記クライアントプロセッサにおいて前記サンプリングするステップの前に実行される、請求項１に記載の方法。
【請求項４】
前記ランダム化するステップは前記クライアントプロセッサによって実行される、請求項１に記載の方法。
【請求項５】
前記暗号化データ
【数１４】
2014178680.tif 000105
及び
【数１５】
2014178680.tif 000106
はストリーム暗号を用いて前記サンプリングされたデータ
【数１６】
2014178680.tif 000107
及び
【数１７】
2014178680.tif 000108
から得られ、前記ストリーム暗号の復号化パラメーターは前記認可された第三者プロセッサに提供される、請求項１に記載の方法。
【請求項６】
前記ランダム化されたデータ
【数１８】
2014178680.tif 000109
、
【数１９】
2014178680.tif 000110
はランダム化応答メカニズムを用いて前記暗号化データ
【数２０】
2014178680.tif 000111
及び
【数２１】
2014178680.tif 000112
から得られる、請求項１に記載の方法。
【請求項７】
前記推定するステップは、
前記認可された第三者プロセッサにおいて、前記ランダム化されたデータ
【数２２】
2014178680.tif 000113
、
【数２３】
2014178680.tif 000114
に適用された前記暗号化の逆を、前記１つ又は複数のクライアントプロセッサによって該認可された第三者プロセッサに提供される前記復号化パラメーターを用いて行うこと、
を更に含む、請求項５に記載の方法。
【請求項８】
前記１つ又は複数のクライアントプロセッサは、前記サンプリングするステップ、前記暗号化するステップ及び前記ランダム化するステップを実行し、前記第三者プロセッサは前記結合するステップ及び前記推定するステップを実行する、請求項１に記載の方法。
【請求項９】
前記サンプリングするステップ、前記ランダム化するステップ及び前記暗号化するステップは、暗号化パラメーターが１つ又は複数のクライアントプロセッサによって求められ、前記復号化パラメーターが前記認可された第三者プロセッサに提供される限り任意の順序とすることができる、請求項５に記載の方法。
【請求項１０】
プライベートデータに関する集約統計をセキュアに求める方法であって、
１つ又は複数のクライアントプロセッサにおいて、第１のデータ及び第２のデータをサンプリングするステップであって、サンプリングされたデータを取得し、ここで、サンプリングパラメーターは前記データの長さよりも実質的に小さい、ステップと、
前記サンプリングされたデータを暗号化して暗号化データを得るステップと、
前記暗号化データを結合して結合された暗号化データを得るステップと、
前記結合された暗号化データをランダム化して、ランダム化されたデータを得るステップと、
認可された第三者プロセッサにおいて、前記ランダム化された暗号化データから、前記第１のデータ及び前記第２のデータの差分プライバシー要件が満たされるように該第１のデータ及び該第２のデータの結合分布を推定するステップと、
を含む、プライベートデータに関する集約統計をセキュアに求める方法。
【請求項１１】
前記ランダム化されたデータは、前記暗号化データについてランダム化応答メカニズムを用いて得られ、該ランダム応答メカニズムは、
各データ要素をアルファベット集合内の任意の他の値に同じ確率で独立して変更すること、又は代替的にその要素の値を保持すること、
を更に含む、請求項１０に記載の方法。
【請求項１２】
１つ又は複数のクライアントプロセッサは前記暗号化することを実行し、サーバープロセッサは前記結合すること、前記サンプリングすること及び前記ランダム化することを実行する、請求項１０に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはセキュアコンピューティングに関し、より詳細には、第三者によってプライベートデータに関するセキュアな集約的統計解析を実行することに関する。
【背景技術】
【０００２】
最も顕著な技術動向のうちの１つは大規模分散データベースの出現及び拡散である。公営企業及び民間企業は、個人、個人の活動、個人の嗜好、個人のロケーション、消費性向、病歴、金融履歴等に関する大量のデータを収集している。これらの企業には、政府機関、医療機関、金融機関、インターネット検索エンジン、ソーシャルネットワーク、クラウドサービスプロバイダー等が含まれる。当然ながら、当事者は潜在的に、データベースにわたる情報にアクセスしそれらを相関付けることができる場合、有意味なパターンを識別し、価値のある洞察を得ることができる。
【０００３】
例えば、調査員が、個人の収入と、性別、人種、年齢、学歴等の個人的特性との相関を求めることを望む場合もあるし、医療研究者が、罹患率と個人の環境要因との関係を研究することを望む場合もある。そのような用途において、有用な集約統計情報が認可された関係者にしか明らかにされないことを確保しながら個人のプライバシーを保つことが不可欠である。実際に、一般の人々は自身のプライバシーが保護されていることに満足していない限り、自身の個人情報の収集及び使用に合意しないであろう。それに加えて、このデータが複数のデータベースにわたって固有分布していることは、大きな困難を呈する。なぜなら、データを直接共有して集中型で統計解析を容易にすることがプライバシー問題及びプライバシー制約により阻止される可能性が高いためである。このため、これらのプライバシー及び制約の問題に対処しながら大規模な分散データベースに対し統計解析を実行するツールを開発しなければならない。
【０００４】
ｋ匿名性等のプライバシーのための従来のメカニズムは適切なプライバシーを提供しないことがわかっている。特に、知識を有する敵対者は、任意の量のサイド情報を匿名化されたデータベースにリンクし、匿名メカニズムを無効化することができる。単純な匿名メカニズムの脆弱性に対応して、差分プライバシーとして知られるプライバシーのより徹底した概念が開発された。非公式には、差分プライバシーは、応答者のデータベース上で計算された関数の結果が特定の応答者の有無の影響をほとんど受けないことを確実にする。より公式には、その関数が、１人の応答者のみが異なるデータベース上で評価される場合、同じ結果を出力する確率がほとんど変化しないことが述べられている。
【０００５】
差分プライバシーを提供するメカニズムは通常、出力摂動を伴い、例えば、データベース上で計算される関数の結果にラプラスノイズが追加されるとき、このノイズはデータベース内の個々の応答者に差分プライバシーを提供する。その一方で、ランダム化応答メカニズム等の、ノイズがデータに追加される入力摂動手法も、応答者に差分プライバシーを提供することを示すことができる。
【０００６】
データベース内の個々の応答者のプライバシーを保護して、認可されていない関係者がデータの結合経験確率分布又は周辺経験確率分布を計算することを防ぎ、データベースに対しポストランダム化（ＰＲＡＭ：post randomization）を単に実行することと比較して、プライバシーと有用性とのより優れたトレードオフを達成することが望ましい。
【０００７】
群衆混合型（crowd-blending）プライバシーのためにサンプリングを用いることができる。これは差分プライバシーの厳密に緩和された（strictly relaxed）バージョンであるが、群衆混合型プライバシーメカニズムに適用される事前サンプリングステップによって所望の量の差分プライバシーを達成することができることが知られている。
【０００８】
米国特許出願第１３／６７６，５２８号は、データＸ及びＹを独立して第１ランダム化して、ランダム化データ
【数１】
2014178680.tif 000003
及び
【数２】
2014178680.tif 000004
を取得する。この第１ランダム化は、データＸ及びＹのプライバシーを保護する。次に、ランダム化データ
【数３】
2014178680.tif 000005
及び
【数４】
2014178680.tif 000006
が、第２ランダム化されて、サーバー用のランダム化データ
【数５】
2014178680.tif 000007
及び
【数６】
2014178680.tif 000008
と、クライアント用のヘルパー情報
【数７】
2014178680.tif 000009
及び
【数８】
2014178680.tif 000010
とが取得される。ここで、Ｔは経験分布を表し、第２ランダム化は、データＸ及びＹの集約統計のプライバシーを保護する。次に、サーバーは、統計
【数９】
2014178680.tif 000011
を求める。最後に、クライアントは、ヘルパー情報
【数１０】
2014178680.tif 000012
及び
【数１１】
2014178680.tif 000013
を
【数１２】
2014178680.tif 000014
に適用して、推定された
【数１３】
2014178680.tif 000015
を取得する。ここで、ＸとＹとの間の「｜」及び「，」は、それぞれ条件付き分布及び結合分布を表す。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明の実施形態は、サーバーに記憶されたクライアントデータから、データのプライバシーを保護しながら集約統計を取得する方法を提供する。データは垂直に分割されている。
【００１０】
本方法は、サーバーがデータの正確な統計解析を実行するのを可能にしながら、ポストランダム化（ＰＲＡＭ）、暗号化及びランダムサンプリングに基づくデータ解放メカニズムを用いてプライバシーを維持する。ＰＲＡＭ及びサンプリングによって、統計を受け取る第三者に対する個人のプライバシーを確保しながら、暗号化によって、サーバーがクライアントデータに関する情報を一切取得しないことを確保する。
【００１１】
ＰＲＡＭとともにランダムサンプリングを構成することによって、ＰＲＡＭのみを用いることと比較して差分プライバシーがどれだけ増大するかを特徴付ける手段が提供される。方法の統計的有用性は、推定誤差、すなわち真の経験分布と推定される分布との間の予期されるｌ２ノルム誤差を、サンプル数、ＰＲＡＭノイズ及び他のパラメーターの関数として制限することによって解析される。
【００１２】
解析は、ＰＲＡＭノイズを増大させることと、サンプル数を減少させてプライバシーの所望のレベルεを維持することとのトレードオフを示す。このトレードオフのバランスをとり、かつ有用性を最大にする最適サンプル数ｍ＊が求められる。
【００１３】
本発明のメカニズムは、サーバーによって記憶され解析されるクライアントデータのプライバシーを保持する。本発明は、サンプリング及びポストランダム化（ＰＲＡＭ）を伴うプライバシーメカニズムを用いてこれを達成する。ポストランダム化（ＰＲＡＭ）はランダム化応答を一般化したものである。このメカニズムは、認可されていない関係者がデータの結合経験確率分布又は周辺経験確率分布を計算することを防ぐ。本発明は、認可された関係者しか逆に行うことができないランダム暗号化パッドを用いてこれを達成する。このメカニズムは、データに対しＰＲＡＭを単に実行することと比較して、プライバシーと有用性とのより優れたトレードオフを達成する。
【００１４】
クライアントデータをサンプリングすることによって、結合経験確率分布又は周辺経験確率分布に関心を有する認可された第三者に提供される有用性を保ちながら、個々の応答者に関するプライバシーを高める。
【００１５】
本発明は、データを戻すことなく固定レートで一様にサンプリングすることによって、差分プライバシーを高める。本発明は、近傍（隣接）データベースが単一の追加又は削除によってではなく単一の置換によって異なる、差分プライバシーの定義を用いてプライバシーを定式化する。さらに、相互に信頼できないクライアントによって保持される垂直に分割された分散データベースを検討する。結合統計を計算するために、データベースに対する結合演算が必要とされ、これは個々のクライアントが、全てのデータベースにわたる結合統計を変更せずには、独立して自身の応答者を混合させることができないことを意味する。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施形態による、操作を受ける２つのクライアントソースからのプライベートデータのブロック図である。
【図２】本発明の実施形態による、データのプライバシーを脅かすことなく第三者によって図１のデータから統計を導出するシステム及び方法の概略図である。
【図３】本発明の実施形態による、データのプライバシーを脅かすことなく第三者によって図１のデータから統計を導出するシステム及び方法の概略図である。
【図４】統計を復元する解放操作の概略図である。
【図５】３つのプライバシーレベルについての、サンプル数の関数としての予期されるｌ２ノルム誤差のグラフである。
【発明を実施するための形態】
【００１７】
図１は、２つのクライアントであるアリス及びボブによって保持される２つの例示的なデータベース１０１及び１０２を示している。アリス及びボブは単一のクライアントを共有することもできるし、データは１つ又は複数のクライアントにわたって分散させることもできる。データベースは個人に関するセンサス型の（census-type）情報を含む。
【００１８】
データベースは、個々の応答者のプライバシーが保持されることを確保しながら、認可された第三者が、例えば母集団における給与を解析することができるようにサニタイズ及び結合され（１１０）、サーバー１２０に記憶される。クライアントによって他のデータを保持することができることが理解される。
【００１９】
概念上、データ解放メカニズムは、データをサーバーに提供する前に、或る形態の摂動又は変換を介してそれらのデータを「サニタイズ」し、個人のプライバシーを保護することを含む。データをサニタイズするのに用いられる方法の適合性は、厳密に定義されたプライバシー制約が満たされる範囲によって決まる。
【００２０】
本発明の実施形態は、データのプライバシーを保護しながら、サーバーに記憶されるデータから集約統計を取得する方法を提供する。
【００２１】
問題の定式化
このセクションでは汎用設定について述べる。クライアントであるアリス及びボブは、自身のデータを解放して、認可された第三者によるプライバシー保護データ解析を可能にすることを望む。単純にするために、２つのクライアントについて本発明の問題定式化及び結果を説明する。しかしながら、本方法は２つよりも多くのクライアントに対し一般化することができる。
【００２２】
第三者は第三者プロセッサにアクセスする認可された第三者とすることができることも理解すべきである。すなわち、認可された第三者は、プロセッサに、或る特定の機能を実行するように指示する。第三者はまた、プロセッサが必要に応じて復号化を実行することができるように適切なキーをプロセッサに供給する。したがって、認可された第三者及び認可された第三者プロセッサという用語は、本明細書において説明されるとき、本質的に同意義である。当業者であれば、実際の計算がプロセッサによって第三者の指示の下で実行されることを理解するであろう。
【００２３】
アリス及びボブが相互に信頼できないクライアントであるデータマイニング用途を検討する。２つのデータベースは、個々のデータベースに対して又は２つのデータベースの或る組合せに対して統計的尺度を計算することができるように、クライアントによって与えられた認可を有する第三者解析に提供されることになる。クライアントはデータに対し柔軟なアクセス制御を有するべきである。例えば、第三者がアリスによってアクセスを与えられるがボブによって与えられない場合、第三者はアリスのデータにしかアクセスすることができない。それに加えて、サーバーが行うべきはデータのホスティングのみであり、その基礎を成す情報にアクセス可能であるべきでない。したがって、データは解放される前にサニタイズされ、個々のプライバシーが保護される。
【００２４】
以下のプライバシー要件及び有用性要件を有する。
【００２５】
データベースセキュリティ：クライアントによって認可された第三者のみがデータベースから統計情報を抽出することができる。
【００２６】
応答者プライバシー：データに関する応答者の個々のプライバシーが、サーバー及び第三者に対して保持される。
【００２７】
統計的有用性：認可された第三者、すなわち適切なキーを所持する第三者が、クライアントによって提供されるデータの結合分布及び周辺分布を計算することができる。
【００２８】
複雑度：システムの全体的な通信要件及び計算要件は妥当であるべきである。
【００２９】
以下のセクションにおいて、本発明によるシステムの枠組みを説明し、プライバシー及び有用性の概念を定式化する。
【００３０】
タイプ及び行列表記
系列データＸｎのタイプ又は経験分布は、
【数１４】
2014178680.tif 000016
によって与えられるマッピング
【数１５】
2014178680.tif 000017
として定義される。
【００３１】
２つの系列Ｘｎ及びＹｎの結合タイプは、
【数１６】
2014178680.tif 000018
によって与えられるマッピング
【数１７】
2014178680.tif 000019
として定義される。
【００３２】
表記の都合上、有限領域タイプ／分布関数を扱うとき、引数を省いてこれらの関数を表し、ベクトル及び行列として用いる。例えば、分布関数ＰＸ：Ｘ→［０，１］を、Ｘの一貫した固定の順序付けに従って値が配列される｜Ｘ｜×１の列ベクトルＰＸとして表すことができる。このため、表記を僅かに誤用すること（abuse）によりＸの値を用いてベクトルをインデックス付けすると、ベクトルＰＸ［ｘ］のｘ番目の要素はＰＸ（ｘ）によって与えられる。同様に、条件付き分布関数ＰＹ｜Ｘ：Ｙ×Ｘ→［０，１］は、ＰＹ｜Ｘ［ｙ，ｘ］：＝ＰＹ｜Ｘ（ｙ｜ｘ）によって定義される｜Ｙ｜×｜Ｘ｜の行列ＰＹ｜Ｘとして表すことができる。例えば、この表記を用いることにより、基本確率アイデンティティ（elementary probability identity）
【数１８】
2014178680.tif 000020
は行列形式でＰＹ＝ＰＹ｜ＸＰＸとして書くことができる。
【００３３】
システムの枠組み
図２は本発明の実施形態のシステム及び方法の枠組みを示している。
【００３４】
データベースモデル：アリスによって保持されるデータ１０１は、系列Ｘｎ：＝（Ｘ１，Ｘ２，．．．，Ｘｎ）としてモデル化される。ここで、各Ｘｉは、有限アルファベットＸにおける値を取る。同様に、ボブのデータ１０２は、確率変数系列Ｙｎ：＝（Ｙ１，Ｙ２，．．．，Ｙｎ）としてモデル化される。ここで、各Ｙｉは、有限アルファベットＹにおける値を取る。これらの系列の長さｎは、データベース内の応答者の総数を表し、各（Ｘｉ，Ｙｉ）対は、アリス及びボブによって一括して保持される応答者ｉのデータを表す。ここで、アルファベットＸ×Ｙは、各応答者のデータの定義域を表す。
【００３５】
データ処理及び解放：各クライアントは自身のそれぞれのデータにデータ解放メカニズムを適用して、サーバー用のデータの暗号化及び第三者用の暗号化キーを生成する。これらのメカニズムはランダム化されたマッピングＦＡ：Ｘｎ→ＯＡ×ＫＡ及びＦＢ：Ｙｎ→ＯＢ×ＫＢによって表される。ここで、ＫＡ２０１及びＫＢ２０２は適切なキー空間であり、ＯＡ２０３及びＯＢ２０４は適切な暗号化空間である。暗号化及びキーは以下によって生成され与えられる。
【００３６】
【数１９】
2014178680.tif 000021
【００３７】
暗号化ＯＡ及びＯＢは処理を実行するサーバーに渡され、キーＫＡ及びＫＢは第三者２２５に提供され送信される。サーバーはＯＡ及びＯＢを処理し、以下の式によって与えられるように、ランダムマッピングＭ：ＯＡ×ＯＢ→Ｏ  ２２０により出力Ｏを生成する。
【００３８】
【数２０】
2014178680.tif 000022
【００３９】
統計的復元：データベースの統計の復元を可能にするために、処理済みの出力Ｏがサーバーを介して第三者に提供され、暗号化キーＫＡ及びＫＢがクライアントによって第三者に提供される。第三者はアリス及びボブのデータ系列の結合タイプ（経験分布）の推定値（＾）を生成する。これは
【数２１】
2014178680.tif 000023
２５０によって、以下の式により与えられるＯ、ＫＡ、及びＫＢの関数として表される。
【００４０】
【数２２】
2014178680.tif 000024
【００４１】
ここで、ｇ：Ｏ×ＫＡ×ＫＢ→［０，１］Ｘ×Ｙは再構成関数である。
【００４２】
目的は、上記の枠組み内で、システム性能要件を最適化するマッピングＦＡ、ＦＢ、Ｍ及びｇを指定することによってシステムを設計することであり、これらのシステム性能要件は以下に定式化される。
【００４３】
プライバシー及び有用性条件
次に、本発明の枠組みのプライバシー要件及び有用性要件を定式化する。
【００４４】
サーバーに対するプライバシー：システム動作過程中、クライアントは自身のデータに関する情報を、集約統計であっても一切サーバーに明らかにすることを望まない。このセキュリティを保証する強い統計条件は、データと、サーバーに記憶される暗号化されたバージョンとの間の統計的独立性要件である。この統計的独立性要件によって、無制限のリソースを有する敵対サーバーに対してであってもセキュリティが保証され、これは実証されていない仮定を一切必要としない。
【００４５】
応答者プライバシー：データは、統計を復元することを試みる任意の認可された第三者を含む全ての他の関係者からプライベートに保たれるべきである。この概念を応答者のε差分プライバシーを用いて以下のように定式化する。
【００４６】
上記の枠組みを所与として、ハミング距離
【数２３】
2014178680.tif 000025
内のＸｎ×Ｙｎにおける全てのデータ（ｘｎ，ｙｎ）及び
【数２４】
2014178680.tif 000026
並びに全てのＳ⊆Ｏ×ＫＡ×ＫＢについて
【数２５】
2014178680.tif 000027
である場合、システムはε差分プライバシーを与える。
【００４７】
プライバシーのこの厳密な定義は、プライバシーの公理（privacy axioms）を満たす。データがｉ．ｉ．ｄ．であるという仮定の下で、この定義は結果として強いプライバシー保証をもたらす。１人を除く全ての応答者の知識を有する敵対者は、唯一の欠落した応答者のデータを復元することができない。
【００４８】
認可された第三者の有用性：推定の有用性は、以下の式によって与えられるこの推定されたタイプベクトルの予期されるｌ２ノルム誤差によって測定される。
【００４９】
【数２６】
2014178680.tif 000028
【００５０】
ここで、目標はこの誤差を最小にすることである。
【００５１】
システム複雑度：システムの通信複雑度及び計算複雑度も関心事である。計算複雑度は所与のシステムを指定するマッピング（ＦＡ、ＦＢ、Ｍ及びｇ）を実施する複雑度によって表すことができる。理想的には、これらのマッピングの全ての計算複雑度を最小化し、各関係者が実行する演算を簡略化しようと試みる。通信要件は、シンボルアルファベット（ＯＡ、ＯＢ、ＫＡ、ＫＢ及びＯ）の濃度によって与えられる。これらのアルファベットサイズの対数は、本発明のシステムにおいて送信しなければならないメッセージに十分な長さを示す。
【００５２】
提案されるシステム及び解析
本発明のシステムの詳細を説明し、そのプライバシー及び有用性性能を解析する。最初に、本発明のシステムが、第三者に対するサニタイズされたデータの解放を容易にするために、どのようにサンプリング及び加法的暗号化を利用し、サーバーが暗号化データを結合し摂動させることを可能にするかを説明する。次に、本発明のシステムのプライバシーを解析し、本発明のサンプリングがプライバシーを高め、それによって所望のレベルのプライバシーを得るために、摂動ステップ中に加えられるノイズの量を低減することを示す。最後に、結合タイプ再構成の精度を解析し、システムパラメーター、すなわち摂動中に加えられるノイズ及びサンプリング係数の関数として有用性に対する制限を生成する。
【００５３】
システムアーキテクチャ
図２はシステム全体を示しており、データサニタイズ及び解放手順が以下のステップによって概説される。
１．サンプリング：クライアントはそれぞれ自身のデータＸ及びＹをランダムにサンプリングし（２０５）、短縮された系列Ｘｎ及びＹｎを生成する。
２．暗号化：クライアントは、短縮された系列をサーバーに渡す前に、その短縮された系列を暗号化する（２１０）。
３．摂動：第三者プロセッサが暗号化された系列を結合し摂動させる（２２０）。
４．解放：第三者プロセッサ２２５がサーバーからサニタイズされたデータを取得し、クライアントから暗号化キーを取得し、データ統計ＴＸ，Ｙのおおまかな復元２３０を可能にする。
【００５４】
クライアント、サーバー及び第三者がそれぞれ、上記で概説したステップを実行する少なくとも１つのプロセッサを有することが仮定される。プロセッサは、メモリ、例えばデータベース、及び互いに通信するための入出力インターフェースに接続される。
【００５５】
これらのステップの主要な態様は、暗号化方式及び摂動方式が交換可能であり（commute）、これによってサーバーが暗号化された系列に対し本質的に摂動を実行することを可能にし、その後、認可された第三者が摂動されたデータを復号化することを可能にする。このセクションにおいて、数学的抽象化及び仮定を適用することにより、理論的観点から各ステップの詳細を説明する。その後、本発明のシステムを実現することに向けた実際の実施態様を説明する。
【００５６】
本発明の別の態様は、暗号化パラメーターがクライアントプロセッサによって求められ、復号化パラメーターが認可された第三者プロセッサに提供される限り、サンプリング、ランダム化、及び暗号化の順序を変更することができることである。
【００５７】
図３は、抽象化を用いた全体プロセスを示している。
【００５８】
サンプリング：データクライアントは、データをサンプリングして（２０５）、データベース系列（Ｘｎ，Ｙｎ）の長さをｍ個のランダムに取り出されたサンプルに低減する。ここで、ｍは実質的にｎよりも小さい。サンプルは戻すことなく、また双方のクライアントが同じロケーションでサンプリングすることなく、一様に取り出される。
【００５９】
【数２７】
2014178680.tif 000029
がサンプリング後の中間結果を表すものとする。数学的に、サンプリング結果は以下の式によって表される。
【００６０】
【数２８】
2014178680.tif 000030
【００６１】
ここで、Ｉ１，．．．，Ｉｍは｛１，．．．，ｎ｝から戻すことなく一様に取り出される。
【００６２】
暗号化：クライアントはサンプリングされたデータ系列を加法（ワンタイムパッド）暗号化方式を用いて独立して暗号化する（２１０）。アリスは独立した一様キー系列Ｖｍ∈Ｘｍ３０１を用い、以下の暗号化された系列を生成する。
【００６３】
【数２９】
2014178680.tif 000031
【００６４】
ここで、
【数３０】
2014178680.tif 000032
は系列にわたって要素ごとに適用される加法を表す。加法演算は、有限集合に対する任意の適宜定義された群加算演算とすることができる。
【００６５】
同様に、ボブは独立した一様キー系列Ｗｍ∈Ｙｍ３０２を用いて自身のデータを暗号化し、以下の暗号化された系列を生成する。
【００６６】
【数３１】
2014178680.tif 000033
【００６７】
アリス及びボブは、これらの暗号化された系列をサーバーに送信し、第三者にキーを提供してデータ解放を可能にする。
【００６８】
摂動：サーバーは暗号化されたデータ系列を結合し、
【数３２】
2014178680.tif 000034
を形成し、独立ＰＲＡＭメカニズムを適用することによってこの系列を摂動させ（２２０）、摂動結果
【数３３】
2014178680.tif 000035
を生成する。結合され暗号化された各サンプル
【数３４】
2014178680.tif 000036
は、（Ｘ×Ｙ）から（Ｘ×Ｙ）へのランダムマッピングを指定する条件分布
【数３５】
2014178680.tif 000037
に従って独立して同一に摂動される。
【００６９】
行列
【数３６】
2014178680.tif 000038
を用いて条件付き分布を表すと、この演算は以下の式によって表すことができる。
【００７０】
【数３７】
2014178680.tif 000039
【００７１】
設計により、Ａはパラメーターγ＞１について以下の式によって与えられるγ対角線行列であると指定する。
【００７２】
【数３８】
2014178680.tif 000040
【００７３】
ここで、ｑ：＝（γ＋｜Ｘ｜｜Ｙ｜−１）は正規化定数である。
【００７４】
解放：図４に示す統計を復元するために、第三者は、サーバーから、サンプリングされ、暗号化され、摂動されたデータ系列
【数３９】
2014178680.tif 000041
４０１を取得し、クライアントから暗号化キーＶｍ及びＷｍを取得する。第三者は以下の式によって与えられるサニタイズされたデータを復号し（４１０）、復元する。
【００７５】
【数４０】
2014178680.tif 000042
【００７６】
これは事実上、サンプリング及びＰＲＡＭによってサニタイズされたデータである。第三者は以下のように、行列Ａを反転し、行列Ａにサニタイズされたデータの結合タイプを乗算することによって、結合タイプの推定値を生成する。
【００７７】
【数４１】
2014178680.tif 000043
【００７８】
行列Ａのγ対角特性に起因して、ＰＲＡＭ摂動は本質的に、加法的暗号化と交換可能な加法演算である。これによってサーバーは、暗号化が取り除かれるときの摂動を保持しながら、暗号化されたデータを摂動させることが可能になる。第三者によって復元される、復号化され、サニタイズされたデータ
【数４２】
2014178680.tif 000044
は本質的に、ＰＲＡＭによって摂動されたサンプリングデータである。
【００７９】
サンプリングによってプライバシーを高める
本システムのプライバシーを解析する。詳細には、ＰＲＡＭと組み合わせたサンプリングが、ＰＲＡＭのみを用いることと比較して、応答者の全体プライバシーをどのように高めるかを示す。γ対角行列Ａを有するＰＲＡＭのみがデータベース全体に適用された場合、結果として得られる摂動されたデータはｌｎ（γ）差分プライバシーを有することになることに留意されたい。以下において、サンプリング及びＰＲＡＭを組み合わせることによって、結果として、プライバシーが高められたサンプリングされ摂動されたデータが得られることを示す。本発明のシステムは応答者に対しε差分プライバシーを提供する。ここで、
【数４３】
2014178680.tif 000045
である。
【００８０】
可能な全てのサンプリングの集合について以下の表記を用いる。
【００８１】
【数４４】
2014178680.tif 000046
【００８２】
サンプリングロケーション（Ｉ１，．．．，Ｉｍ）は集合Θから一様に取り出される。ロケーションｋを選択するサンプリングの部分集合を表すΘｋ：＝｛π∈Θ｜∃ｉ，πｉ＝ｋ｝を定義し、ロケーションｋを選択しないサンプリングの部分集合を表す
【数４５】
2014178680.tif 000047
を定義する。ただし、π∈Θｋである。
【００８３】
【数４６】
2014178680.tif 000048
を、ロケーションｋの選択を任意の他の選択されていないロケーションで置き換える
【数４７】
2014178680.tif 000049
の部分集合として定義する。π∈Θを、データ系列のサンプリング関数として表し、すなわち
【数４８】
2014178680.tif 000050
であり、π（Ｙｎ）についても同様に表す。上記の表記を用いて、以下の条件付き確率を書き換えることができる。
【００８４】
【数４９】
2014178680.tif 000051
【００８５】
ここで、最後の等式において、
【数５０】
2014178680.tif 000052
にわたる合算を、π∈Θｋにわたる合算に組み込むように合算を再配列した。
【００８６】
全てのπ∈Θｋにわたる合算の範囲内で全てのπ’∈Θｋ（π）にわたって合算することは、全ての
【数５１】
2014178680.tif 000053
をカバーするが、各π’を正確にｍ回オーバーカウントすることに留意されたい。なぜなら、各
【数５２】
2014178680.tif 000054
は全てのπ∈ΘｋにわたってΘｋ（π）集合のｍに属するためである。このため、このオーバーカウントを計上する（１／ｍ）項が加えられている。
【００８７】
上記の展開に関して、合算項の以下の短縮表記を用いる。
【００８８】
【数５３】
2014178680.tif 000055
【００８９】
このため、確率比は以下のように書くことができる。
【００９０】
【数５４】
2014178680.tif 000056
【００９１】
ここで、π＊∈Θｋは比を最大にするサンプリングを表す。行列Ａのγ対角構造を所与とすると、（π＊（ｘｎ），π＊（ｙｎ））及び
【数５５】
2014178680.tif 000057
は１つのロケーションにおいてのみ異なるので、
【数５６】
2014178680.tif 000058
が得られ、（π＊（ｘｎ），π＊（ｙｎ））及び（π’（ｘｎ），π’（ｙｎ））は１つのロケーションにおいてのみ異なるので、
【数５７】
2014178680.tif 000059
が得られ、
【数５８】
2014178680.tif 000060
であるので、
【数５９】
2014178680.tif 000061
が得られる。これらの制約を所与として、ｅεを用いて尤度比を制限することによって、尤度比を以下のように制限することができる。
【００９２】
【数６０】
2014178680.tif 000062
【００９３】
所与のεについてε差分プライバシーを示すためには、上記で行ったように、ｅεによって確率比に上限を設けるだけでよい。当然の疑問は、この制限がタイト（tight）であるか否か、すなわち制限が同様に満たされ、このためシステムをよりプライベートにする、より小さなεが存在するか否かである。以下の実施例は、εの値がタイトであることを示す。
【００９４】
実施例：ａ及びｂを（Ｘ×Ｙ）における２つの別個の要素とする。（ｘｎ，ｙｎ）＝（ｂ，ａ，ａ，．．．，ａ）、
【数６１】
2014178680.tif 000063
及び（ｘｍ，ｙｍ）＝（ｂ，ｂ，．．．，ｂ）とする。Ｅが、第１の要素（２つのデータベースは異なる）がサンプリングされる事象を表すものとする。この事象は確率（ｍ／ｎ）で発生する。尤度比を以下のように求めることができる。
【００９５】
【数６２】
2014178680.tif 000064
【００９６】
したがって、εの値は実際にタイトである。
【００９７】
データベースサイズｎ、サンプル数ｍ及び所望のレベルのプライバシーεの所与のシステムパラメーターのプライバシー解析により、行列Ａのγパラメーターによって指定されるＰＲＡＭ摂動のレベルは以下である。
【００９８】
【数６３】
2014178680.tif 000065
【００９９】
サーバーに対するプライバシーは、サーバーに送信する前にデータに対し実行されるワンタイムパッド暗号化２１０の結果として得られる。サーバーによって受信される暗号化は、キーの独立性及び一様なランダム化の結果として、元のデータベースから統計的に独立している。
【０１００】
有用性解析
このサブセクションでは、本発明のシステムの有用性を解析する。本発明の主な結果は、結合タイプ推定誤差の予期されるｌ２ノルムに対する理論的制限である。この制限の解析は、サンプリングパラメーターｍ及びＰＲＡＭ摂動レベルγの関数としての有用性とプライバシーレベルεとのトレードオフを示す。この誤差限界を所与とすると、固定のプライバシーレベルεを達成しながら、誤差限界を最小にする最適なサンプリングパラメーターｍを計算することができる。
【０１０１】
本発明のシステムの場合、結合タイプ推定値の予期されるｌ２ノルムは以下の式によって制限される。
【０１０２】
【数６４】
2014178680.tif 000066
【０１０３】
ここで、ｃは以下の式によって与えられるγ対角行列Ａの条件数である。
【０１０４】
【数６５】
2014178680.tif 000067
【０１０５】
三角不等式を適用すると、サンプリングによって生じる誤差とＰＲＡＭによって生じる誤差との和としての誤差を以下のように制限することができる。
【０１０６】
【数６６】
2014178680.tif 000068
【０１０７】
サンプリング誤差
【数６７】
2014178680.tif 000069
を、条件付き期待値
【数６８】
2014178680.tif 000070
を制限することによって解析し制限することができる。
【０１０８】
所与の（ｘ，ｙ）∈Ｘ×Ｙの場合、
【数６９】
2014178680.tif 000071
を条件とするサンプリングされたタイプ
【数７０】
2014178680.tif 000072
は、以下によって与えられる期待値及び分散を用いてｍによって正規化される超幾何学的確率変数である。
【０１０９】
【数７１】
2014178680.tif 000073
【０１１０】
条件付きサンプリング誤差にジェンセンの不等式を適用することによって、以下が得られる。
【０１１１】
【数７２】
2014178680.tif 000074
【０１１２】
平滑化定理を適用して、サンプリング誤差は以下によって制限することができる。
【０１１３】
【数７３】
2014178680.tif 000075
【０１１４】
次に、
【数７４】
2014178680.tif 000076
によって与えられるＰＲＡＭ誤差を解析し制限するために、以下の線形代数を用いる。
【０１１５】
Ａが可逆行列を表し、（ｘ，ｙ）がＡｘ＝ｙを満たすベクトルであるものとする。
【数７５】
2014178680.tif 000077
となるような任意のベクトル
【数７６】
2014178680.tif 000078
について、以下の式が得られる。
【０１１６】
【数７７】
2014178680.tif 000079
【０１１７】
ここで、ｃは行列Ａの条件数である。
【０１１８】
ＰＲＡＭ誤差を制限するために、以下の結果を用いる。
【０１１９】
【数７８】
2014178680.tif 000080
【０１２０】
これによって、ＰＲＡＭ誤差の条件付き期待値を以下のように制限することが可能になる。
【０１２１】
【数７９】
2014178680.tif 000081
【０１２２】
（ｘ，ｙ）∈Ｘ×Ｙについて、
【数８０】
2014178680.tif 000082
を条件とする摂動されサンプリングされたタイプ
【数８１】
2014178680.tif 000083
は、以下の式によって与えられる期待値及び分散を用いてｍによって正規化されたポアソン二項確率変数である。
【０１２３】
【数８２】
2014178680.tif 000084
【０１２４】
ジェンセンの不等式を用いて以下の条件付き期待値を制限して以下の式を得ることができる。
【０１２５】
【数８３】
2014178680.tif 000085
【０１２６】
式を組み合せることによって以下の制限が得られる。
【０１２７】
【数８４】
2014178680.tif 000086
【０１２８】
この式に平滑化定理を適用すると、ＰＲＡＭ誤差に対する以下の制限が得られる。
【０１２９】
【数８５】
2014178680.tif 000087
【０１３０】
三角不等式によりサンプリング及びＰＲＡＭ誤差に対する個々の制限を組み合わせることによって、サンプリングされ摂動されたデータから形成されるタイプ推定値の予期されるノルム２誤差に対する以下の制限が得られる。
【０１３１】
【数８６】
2014178680.tif 000088
【０１３２】
Ａはγ対角行列であるので、その条件数ｃは以下によって与えられる。
【０１３３】
【数８７】
2014178680.tif 000089
【０１３４】
最適サンプリングパラメーターｍ＊
固定のＰＲＡＭ摂動パラメーターγを所与とすると、誤差制限は、サンプリングパラメーターｍの関数として約
【数８８】
2014178680.tif 000090
減衰する。しかしながら、ｍが増大すると、式（１）によって与えられるようにεも増大し、プライバシーが減少する。しかしながら、式（２）によって与えられるようにｍの関数としてγを調整することによって全体プライバシーレベルεを固定してプライバシーの所望のレベルを維持するとき、ｍを増大させすぎると誤差限界が拡大することが観察される。図５を参照されたい。
【０１３５】
直感的に、これは、ｍを過度に大きくすることによって、同じレベルのプライバシーを維持するにはγを下げることを通じてＰＲＡＭ摂動を増大させる必要があるとして説明することができる。ＲＰＡＭ摂動を増大させることは、条件数ｃを通じて誤差限界を増大させるという悪影響を有する。
【０１３６】
他方で、ｍを過度に小さくすることにより、取得されるサンプルが少なすぎることになり、結果として不正確なタイプ推定値が得られる。図５を参照されたい。サンプリングパラメーターｍを調整することにおけるこのバランスは、プライバシーの所望のレベルε及び他のシステムパラメーターの関数として最適なサンプルサイズｍが存在することを示している。図５を参照されたい。
【０１３７】
誤差上限の理論的に最適なサンプルサイズｍ＊は以下によって与えられる。式（３）の誤差限界を最適化する最適なサンプリングパラメーターｍ＊は以下である。
【０１３８】
【数８９】
2014178680.tif 000091
【０１３９】
図５は、サンプル数ｍの関数として３つのプライバシーレベル（ε）の実験結果を示している。各データ点は、「一様」分布を有する合成データを用いて、１０００個の独立した実験にわたる経験的平均として推定されるタイプ誤差の予期されるｌ２ノルムを表す。３つの垂直線は、各それぞれのプライバシーレベルにおける理論的に最適な数のサンプルを示す。
【図１】
2014178680.tif 000115
【図２】
2014178680.tif 000116
【図３】
2014178680.tif 000117
【図４】
2014178680.tif 000118
【図５】
2014178680.tif 000119
【外国語明細書】
2014178680.tif 000120
2014178680.tif 000121
2014178680.tif 000122
2014178680.tif 000123
2014178680.tif 000124
2014178680.tif 000125
2014178680.tif 000126
2014178680.tif 000127
2014178680.tif 000128
2014178680.tif 000129
2014178680.tif 000130
2014178680.tif 000131
2014178680.tif 000132
2014178680.tif 000133
2014178680.tif 000134
2014178680.tif 000135
2014178680.tif 000136
2014178680.tif 000137
2014178680.tif 000138
2014178680.tif 000139
2014178680.tif 000140
2014178680.tif 000141
2014178680.tif 000142
2014178680.tif 000143
2014178680.tif 000144
2014178680.tif 000145
2014178680.tif 000146
2014178680.tif 000147
2014178680.tif 000148
2014178680.tif 000149
2014178680.tif 000150
2014178680.tif 000151
2014178680.tif 000152
2014178680.tif 000153
2014178680.tif 000154
2014178680.tif 000155
2014178680.tif 000156
2014178680.tif 000157
2014178680.tif 000158
2014178680.tif 000159
2014178680.tif 000160
2014178680.tif 000161
2014178680.tif 000162