複数データベースのための差分プライバシー集合分類器
【課題】１組のデータベースのための差分プライバシー集合分類器を求めるためのシステムを提供する。
【解決手段】１組のデータベース１１０内の各データベース１２０、１３０は分類器１２１、１３１及び雑音値１２２、１３２に関連付けられる。該分類器及び該雑音値は、該分類器及び該雑音値の組み合わせが該データベースの差分データプライバシーを保証するように、データベース毎にローカルに求められる。差分プライバシー集合分類器は、１組のデータベース内の最も小さなデータベースに対応する雑音値を用いて変更された、該１組のデータベースの分類器の組み合わせであり、各データベースの差分データプライバシーを保護する。
【解決手段】１組のデータベース１１０内の各データベース１２０、１３０は分類器１２１、１３１及び雑音値１２２、１３２に関連付けられる。該分類器及び該雑音値は、該分類器及び該雑音値の組み合わせが該データベースの差分データプライバシーを保証するように、データベース毎にローカルに求められる。差分プライバシー集合分類器は、１組のデータベース内の最も小さなデータベースに対応する雑音値を用いて変更された、該１組のデータベースの分類器の組み合わせであり、各データベースの差分データプライバシーを保護する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は包括的には差分データプライバシー(differential data privacy)に関し、より詳細には、複数データベースのための差分プライバシー集合分類器(differentially private aggregate classifier)を求めることに関する。
【背景技術】
【０００２】
データ収集は種々の学問、産業、商業及び政治目的のための情報を提供する。たとえば、データ収集は社会学研究、市場調査及び国勢調査において必要である。収集されたデータの有用性を最大にするために、全てのデータを蓄積し、如何なるプライバシーコントロールも用いることなく、解析のために利用されるようにすることができる。当然、大部分の人々及び組織(「プライバシー当事者」)は、データが容易に交換され、許可されない人がアクセスできるときに特に、全てのデータを開示することを好まない。プライバシーを保証することは、プライバシー当事者がデータを快く提供できるようにし、かつ不正行為、個人情報盗難、脅迫、及び十分なプライバシー保護を用いることなくデータを共有することから生じる可能性がある他の問題を軽減することができる。
【０００３】
プライバシーを保護するための方法は、収集されたデータに関して実行されたクエリ(問合せ)の集合的結果を計算し、関与しているプライバシー当事者の入力を開示することなく、そのような集合的結果を開示することである。たとえば、医療データベースにクエリして、データベース内の何人がＨＩＶ陽性であるかを判断することができる。ＨＩＶ陽性の個人の名前を開示することなく、ＨＩＶ陽性の全人数を開示することができる。このようにして、当事者のプライバシーを明示的に或る程度まで保護しながら、有用なデータが抽出される。
【０００４】
しかしながら、敵対者は種々の技法を適用して、医療データベースからＨＩＶ陽性である可能性が高い１組の個人を予測するか、又はその範囲を絞ることができる。たとえば、敵対者は、ＨＩＶを有しかつジョンスミスという名前でない人の数を尋ねる別のクエリを実行する可能性がある。その後、その敵対者は、第１のクエリ出力から第２のクエリ出力を引くことができ、それにより、プライバシー当事者の名前に関してデータベースに直に尋ねることなく、ジョンスミスのＨＩＶ状態を突き止めることができる。機密に関わるデータの場合、検証可能なプライバシー保証を提供することが有用である。たとえば、最初に知られていたこと以外に、いかなる特定のプライバシー当事者に関しても何も探り出すことができないことを検証可能に保証することが有用であろう。
【０００５】
クエリ出力に雑音を付加することによって、当事者のプライバシーを高めることができる。上記の例を用いるとき、ＨＩＶ陽性当事者の開示される数に或る乱数を付加することができる。その雑音は開示された出力の精度を低下させることになるが、それに応じてプライバシーに関する利益があるので、この損失を正当化することができる。
【０００６】
クエリ結果に雑音を付加して当事者のプライバシーを保護するという概念は一般的に知られている。１つの方法は、付加された雑音を用いて個々のデータインスタンスのプライバシーを保護するために差分プライバシー分類器を用いる。或るデータベース内の任意の個々のデータインスタンスの存否に関わらず、分類器が特定の出力を生成する確率が概ね同じであるなら、そのデータベースに関して評価される分類器は、差分プライバシーを満たすと言われる。
【０００７】
しかしながら、従来の差分プライバシー分類器は、データベース毎にローカルに求められ、その分類器を複数のデータベースにわたって用いる必要があるとき、プライバシーを提供できない。したがって、１組のデータベースに対して、各データベースの差分データプライバシーを保護するそのような分類器を求める必要がある。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
差分プライバシーが、分類器の出力が個々のデータインスタンスについての情報を含まないという統計的保証を提供する。しかしながら、マルチパーティーの応用例では、分類器を求めるためのデータがいくつかのデータベースにわたって分散され、従来の差分プライバシー法は、複数の寄与しているパーティーのための差分データプライバシーを保護しない。
【０００９】
これは、従来の方法が本来、分類器がデータベースの全データへのアクセスに基づいて求められ、データに関して計算された雑音値によって分類器を変更して、そのデータに専用の差分プライバシー分類器を生成するように設計されるためである。しかしながら、マルチパーティーの応用例では、セキュリティ制約に起因して、多くの場合に、異なるデータベースのデータにアクセスすることはできない。
【００１０】
この発明の実施の形態は、１組のデータベースについて、データベースのデータへのアクセスを許可することなく、１組のデータベース内の個々のデータベースの分類器及び雑音値から、各データベースの差分データプライバシーを保護する差分プライバシー集合分類器を求めることができるという認識に基づいている。
【００１１】
しかしながら、マルチパーティーの応用例では、分類器に雑音値を付加することはもはや簡単ではない。これは、雑音を付加した結果として各データベースの差分データプライバシーが達成されるという保証がないためである。たとえば、全ての分類器及び雑音値の集合は、論理的手法と見なされることになり、組み合わせられたデータに対する差分プライバシーを満たさない。
【００１２】
この発明の実施の形態は、１組のデータベース内の最も小さなデータベースに対応する雑音値によって変更される各データベースの分類器の集合として、差分プライバシー集合分類器を求めることができるという別の認識に基づいている。最も小さなデータベースは、最も少ないエントリ数を有し、各エントリのデータ構造は全てのデータベースにわたって同じである。この認識が正しいことの裏付けは、付録において提供される。
【課題を解決するための手段】
【００１３】
したがって、この発明の１つの実施の形態は、１組のデータベースのための差分プライバシー集合分類器を求めるための方法であって、該１組のデータベース内の各データベースは分類器及び雑音値に関連付けられ、該分類器及び該雑音値は、該分類器及び該雑音値の組み合わせが前記データベースの差分データプライバシーを保証するように、前記データベース毎にローカルに求められ、前記差分プライバシー集合分類器は各前記データベースの前記差分データプライバシーを保護し、該方法は、各前記データベースの前記分類器を組み合わせて集合分類器を求めるステップと、前記１組のデータベース内の最も小さなデータベースに対応する雑音値を用いて前記集合分類器を変更するステップとを含み、前記最も小さなデータベースは最も少ないエントリ数を有し、各エントリのデータ構造は全てのデータベースについて同じである、方法を開示する。
【００１４】
さらに、この発明の種々の実施の形態は、暗号プロトコルを用いてセキュア(安全)に差分プライバシー集合分類器を求める。それらの実施の形態は、各データベースのデータがいかなる他のパーティーとも共有されないこと、及び差分プライバシー集合分類器をリバースエンジニアリングによって解析していかなるデータベースのいかなる個々のデータも突き止めることができないことを保証する。
【００１５】
別の実施の形態は、１組のデータベースのための差分プライバシー集合分類器を求めるためのシステムであって、該１組のデータベース内の各データベースは分類器及び雑音値に関連付けられ、該分類器及び該雑音値は、該分類器及び該雑音値の組み合わせが該データベースの差分データプライバシーを保証するように、前記データベース毎にローカルに求められ、前記差分プライバシー集合分類器は各前記データベースの前記差分データプライバシーを保護し、該システムは、前記分類器を組み合わせて集合分類器を求める手段と、前記１組のデータベース内の最も小さなデータベースに対応する雑音値を用いて前記集合分類器を変更して、前記差分プライバシー集合分類器を生成する手段とを備える、システムを開示する。
【００１６】
さらに別の実施の形態は、１組のデータベースのための差分プライバシー集合分類器を格納するコンピューター読み取り可能な記憶媒体であって、該１組のデータベース内の各データベースは分類器及び雑音値に関連付けられ、該分類器及び該雑音値は、該分類器及び該雑音値の組み合わせが前記データベースの差分データプライバシーを保証するように、前記データベース毎にローカルに求められ、前記差分プライバシー集合分類器は、前記１組のデータベース内の最も小さなデータベースに対応する雑音値を用いて変更された、該１組のデータベースの前記分類器の組み合わせである、コンピューター読み取り可能な記憶媒体を開示する。
【発明の効果】
【００１７】
この発明の実施の形態は、差分プライバシー集合分類器を求め、複数データベースの差分プライバシーを保証する。この発明は、マルチパーティー差分プライバシーを達成するのに、最も小さなデータベースのサイズに基づいて確率的成分を選択すれば十分であるという認識に基づいている。いくつかの実施の形態は、この認識のために、ＳＭＣ法を介して雑音値の選択をセキュアに実行することができることをさらに認めている。
【００１８】
しかしながら、従来の方法とは異なり、それらの実施の形態は分類器を構成するのにＳＭＣを使用しない。それゆえ、この発明の実施の形態は、組み合わせられたデータにおいて分類器を計算する任意のＳＭＣ法よりもはるかに簡単である。
【図面の簡単な説明】
【００１９】
【図１】この発明による差分プライバシー集合分類器を求めるための方法のブロック図である。
【図２Ａ】取り得る雑音値の指数分布のグラフである。
【図２Ｂ】取り得る雑音値の正規分布のグラフである。
【図２Ｃ】取り得る雑音値の混成分布のグラフである。
【図３】この発明の一実施の形態による、差分プライバシー集合分類器をセキュアに求めるための方法のブロック図である。
【発明を実施するための形態】
【００２０】
定義
この発明の実施の形態を説明する際に、全体を通して(上記の説明も含む)以下の定義が適用可能である。
【００２１】
「コンピューター」は、構造化された入力を受け取り、構造化された入力を所定の規則に従って処理し、処理結果を出力として生成することができる任意の装置を指している。コンピューターの例には、コンピューター；汎用コンピューター；スーパーコンピューター；メインフレーム；スーパーミニコンピューター；ミニコンピューター；ワークステーション；マイクロコンピューター；サーバー；双方向テレビ；コンピューター及び双方向テレビの種々の組み合わせ；並びにコンピューター及び／又はソフトウエアをエミュレートする専用ハードウエアが含まれる。コンピューターは単一のプロセッサ又は複数のプロセッサを有することができ、それらのプロセッサは並列に、かつ／又は非並列に動作することができる。また、コンピューターは、コンピューター間で情報を送信又は受信するためのネットワークを介して共に接続される２つ以上のコンピューターも指している。そのようなコンピューターの例には、ネットワークによってリンクされるコンピューターを介して情報を処理するための分散コンピューターシステムが含まれる。
【００２２】
「中央演算装置(ＣＰＵ)」又は「プロセッサ」は、ソフトウエア命令を読み出し、実行するコンピューター、又はコンピューターの構成要素を指している。
【００２３】
「メモリ」又は「コンピューター可読媒体」は、コンピューターによってアクセス可能なデータを格納するための任意の記憶装置を指している。その例には、磁気ハードディスク；フロッピィディスク；ＣＤ−ＲＯＭ又はＤＶＤのような光ディスク；磁気テープ；メモリチップ；電子メールを送受信する際に、又はネットワークにアクセスする際に用いられるような、コンピューター可読電子データを搬送するために用いられる搬送波、並びにコンピューターメモリ、たとえば、ランダムアクセスメモリ(ＲＡＭ)が含まれる。
【００２４】
「ソフトウエア」は、コンピューターを動作させるための所定の規則を指している。ソフトウエアの例には、ソフトウエア；コードセグメント；命令；コンピュータープログラム；及びプログラムされたロジックが含まれる。インテリジェントシステムのソフトウエアは、自己学習できる場合もある。
【００２５】
「モジュール」又は「ユニット」は、タスク又はタスクの一部を実行するコンピューター内の基本構成要素を指している。それはソフトウエア又はハードウエアのいずれかによって実装することができる。
【００２６】
図１に示されるように、この発明の実施の形態は、１組のデータベース１１０のための差分プライバシー集合分類器１７０であって、該１組のデータベース内の各データベースの差分データプライバシーを保護するような差分プライバシー集合分類器１７０を求めるためのシステム及び方法１００を開示する。この発明の実施の形態は、当該技術分野において既知であるように、メモリ及び入力／出力インターフェースを含むプロセッサ１０１によって実施することができる。
【００２７】
１組のデータベース１１０内の各データベース１２０〜１３０は、分類器、たとえば、分類器１２１及び１３１、並びに雑音値、たとえば、雑音値１２２及び１３２に関連付けられる。たとえば、データベースはＤ１、…、ＤＫと表される。ただし、Ｄｉ＝(ｘ，ｙ)｜ｊは１組のエントリｘと、対応する２値ラベルｙとを含む。分類器及び雑音値の組み合わせがデータベースの差分データプライバシー１２５又は１３５を保証するように、分類器及び雑音値はデータベース毎にローカルに求められる。「ローカルに求められる」は、分類器及び雑音値が、方法１００の実行前に、又は実行と同時にデータベースの各所有者によって独立して求められることを意味する。
【００２８】
通常、差分プライバシーを保証するために、雑音値はデータベースのサイズ１２３又は１３３に依拠してデータベースの全データエントリにわたって求められる。本明細書において用いられるときに、「データベースのサイズ」は、エントリの数に基づいている。エントリは任意のデータ構造を有することができる。しかしながら、各エントリのデータ構造は全てのデータベースにわたって同じである。エントリの例は、フィールド、表内の行、表自体、ファイル、又は別のデータベースである。
【００２９】
この発明の実施の形態は、データベースの和集合Ｄ１∪Ｄ２…∪ＤＫからの差分プライバシー集合分類器を、１組のデータベース内の最も小さなデータベースに対応する雑音値によって変更される各データベースの分類器の集合として求めることができるという認識に基づいている。最も小さなデータベースは最も少ないエントリ数を有し、各エントリのデータ構造は全てのデータベースについて同じである。この認識が正しいことの裏付けは、付録Ａにおいて提供される。
【００３０】
したがって、一実施の形態は、各データベースの分類器を組み合わせて、集合分類器１４５を求める(１４０)。さらに、それらの実施の形態は、最も小さなデータベースに対応する雑音値１５５を求める(１５０)。次に、雑音値１５５を用いて集合分類器１４５を変更し(１６０)、差分プライバシー集合分類器１７０を生成する。差分プライバシー集合分類器は公開され、たとえば、メモリ１７５に格納されるか、又はインターネット上で配布される。
【００３１】
差分プライバシー
差分プライバシーモデルの定義によれば、１つの要素だけ異なる任意の２つのデータベースＤ及びＤ’、すなわち、隣接するデータベースが与えられたとすると、関数ＭがデータベースＤにおいて応答Ｓを生成する確率が、関数ＭがデータベースＤ’において同じ応答Ｓを生成する確率と同様である場合には、ランダム化クエリ関数Ｍによって定義される分類器は差分プライバシーを有する。個々のエントリの存在又は不在時に、クエリ出力が高い確率で概ね同じであるので、出力からいかなる個々のエントリについてもほとんど何も突き止めることはできない。
【００３２】
全ての隣接するデータベースＤ及びＤ’の場合に、かつ任意のＳ∈ｒａｎｇｅ(Ｍ)の場合に、以下の式が成り立つ場合には、明確な確率密度Ｐを有するランダム化関数Ｍは、ε差分プライバシーを満たす。
【００３３】
【数１】
【００３４】
したがって、差分プライバシー分類器は、アプリオリの背景知識以外に、学習アルゴリズムの出力から確信を持って個々のエントリについてのさらに詳しい事柄を得ることができないことを保証する。差分プライバシーは、特定の１組の攻撃及び敵対的挙動に対して「その場限りの(ad hoc)」保証を与える大部分の他のモデルとは対照的に、「全てに通じる(ad omina)」保証を与える。多数のエントリにわたって差分プライバシー分類器を評価しても、敵対者は、そのデータの厳密な形を突き止めることはできない。
【００３５】
図２Ａ〜図２Ｃは、横軸に沿って雑音値を、縦軸においてそのような雑音値に関連付けられた確率を示す。したがって、高い確率を有する雑音値が、選択される可能性が高い。それらの分布は全て、絶対値が大きくなると、所与の雑音値の確率が小さくなるという有益な特徴を共有する。過度に高い雑音値の確率が起こる可能性は小さいので、この特徴によれば、雑音を含む出力を有用にすることができる。
【００３６】
図２Ａは、雑音値の指数分布２１０を示す。図２Ｂは、雑音値の正規分布２２０を示す。図２Ｃは、雑音値の混成分布２３０を示す。図２Ｃの混成分布は、最も確からしい雑音値を含む分布の部分、すなわち、より高い確率を有する部分を正規分布が定義し、最も確からしくない雑音値を含む分布の部分、すなわち、より大きな絶対雑音値に対応する低い確率を有する部分を指数分布が定義するような、正規分布及び指数分布である。
【００３７】
図２Ａ〜図２Ｃにおいて各分布を計算する際に、差分直径２４０及びプライバシーパラメーターεを用いることができる。大きな差分直径値は分布を広くし、より高い雑音値が用いられる確率を高める。逆に、小さな差分直径は、大きな雑音値が選択される可能性を小さくする。プライバシーパラメーターが分布関数の分母にあるとき、小さい値のプライバシーパラメーターεが強いプライバシーに対応し、その逆も成り立つ。上記の例示的な式は満足できるものであり、それを用いて無限の様々な分布を構成することができ、それらの分布は差分直径測定値及びプライバシーパラメーターを利用して、満足できる雑音分布を作り出すのに成功する。たとえば、図２Ａ〜図２Ｃにおいて示される分布に対して無数の小さな変更を加えることができる。
【００３８】
通常、それらの分類器は、分類器の重みに雑音値を加算することによって、差分プライバシーを有するように設計される。ただし、雑音値は上記の分布から選択される。さらに、分布のパラメーターは、イプシロンεによって表される所望のプライバシー度に依存し、それは通常、データベースのサイズに、かつ分類器の関数のタイプ、たとえば、平均関数、最大関数又は対数関数に依存する。一実施の形態では、雑音値はラプラス分布を有する。
【００３９】
個々のデータベースにおいて分類器をローカルに求める
各データベース所有者Ｐｊが、そのデータベース(ｘ，ｙ)｜ｊを用いて、重みｗｊを有する分類器を求める。ただし、ｊはデータベースのインデックスである。一実施の形態は、分類器のために、正則化ロジスティック回帰関数ｌ(エル)２を用いる。たとえば、分類器ｗｊは、以下の目的関数を最小にすることによって求めることができる。
【００４０】
【数２】
【００４１】
ただし、λ＞０は正則化パラメーターであり、Ｔは転置演算子である。しかしながら、それらの分類器は個々のデータベース毎にローカルに求められ、データ又は情報は共有されない。
【００４２】
差分プライバシー集合分類器の例
この発明の一実施の形態は、以下の式に従って、差分プライバシー集合分類器ｗＳ１７０を定義する。
【００４３】
【数３】
【００４４】
ただし、Ｋは１組のデータベース内のデータベースの数であり、ｊはデータベースのインデックスであり、ηはパラメーター２／(ｎ(１)ελ)を用いてスケーリングされるラプラス(Ｌａｐ)分布からサンプリングされるｄ次元確率変数であり、ｎ(１)は最も小さなデータベースに対応する雑音値、すなわち、ｎ(１)＝ｍｉｎｊｎｊであり、λはラプラス分布のパラメーターであり、εは差分プライバシーパラメーターである。
【００４５】
差分プライバシー集合分類器ｗＳは、パーティーがそのプライバシーを保持できるようにしながら、全てのデータの和集合において分類器を直にトレーニングすることによって、十分に制限された過剰リスクのみを受ける。雑音値ηは、分類器ｗＳが差分プライバシーを満たすことを、すなわち、分類器から個々のデータインスタンスを判別できないことを保証する。
【００４６】
上記の雑音値ηの定義は直観的ではなく、この発明によれば、ローカルにトレーニングされた分類器を集めることによって構成された差分プライバシー集合分類器が、最も少ない数のエントリを有する個々の分類器の性能によって制限されることが証明された。
【００４７】
ローカルにトレーニングされた分類器を集めても、差分プライバシーを保証する正しい雑音値
【００４８】
【数４】
【００４９】
を与えないので、この発明のいくつかの実施の形態は、データベースＰｊの所有者は、単にそのような分類器ｗｊを取り込み、雑音ベクトルを用いてそれらの分類器を摂動させて、摂動した分類器を公開することはできないという認識に基づいている。また、個々のデータベース所有者は、他の全ての分類器に対して差分プライバシーを課すために、それらの分類器に単に雑音を加算することはできないので、個々の分類器、又は各データベース内のエントリの数が暴かれないように、実際の平均化演算を実行しなければならない。したがって、いくつかの実施の形態は、プロセッサとインタラクトして平均化を実行するために、セキュアマルチパーティー計算(ＳＭＣ)法を用いる。その方法の結果として、データベース所有者のそれぞれが所望の差分プライバシー分類器ｗＳの加法的持分(additive share)を得るようになり、差分プライバシー集合分類器を得るために、これら持分を加算しなければならないようになっている。
【００５０】
セキュアマルチパーティー計算(ＳＭＣ)法
それらの実施の形態は、非対称鍵加法的準同型暗号化を用いる。そのような暗号化の所望の特性は、暗号文要素において実行される演算が同じ平文要素における既知の演算に写像することである。加法的準同型暗号化関数の場合、ξ(・)は、任意のａ及びｂに対して、ξ(ａ)ξ(ｂ)＝ξ(ａ＋ｂ)、ξ(ａ)ｂ＝ξ(ａｂ)であることを意味する。
【００５１】
加法的準同型暗号化は強秘匿性であり、すなわち、同じ平文を繰返し暗号化しても、結果として、異なる暗号文が生成される。ＳＭＣ法の場合、暗号鍵は、公開されていると考えられ、解読鍵は、指定されたデータベース所有者によって非公開で所有される。
【００５２】
図３は、ＳＭＣ法を用いて、差分プライバシー集合分類器１７０を求めるための方法３００のブロック図を示す。その方法はプロセッサ３０１によって実行することができる。
【００５３】
最も小さなデータベースの不明瞭化インデックスを求める
プロセッサは、データベースのインデックスの置換から生じる置換済みインデックス３２０に基づいて最も小さなデータベースの不明瞭化インデックス３１５を求める(３１０)。たとえば、各データベース所有者、すなわち、パーティーＰｊが、ｎｊ＝ａｊ＋ｂｊを計算する。ただし、ａｊ及びｂｊはデータベース長ｎｊの加法的持分を表す整数であり、ｊ＝１、２、…、Ｋである。加法的持分のＫ長ベクトルはそれぞれａ及びｂと定義される。
【００５４】
パーティーＰｊは、インデックスベクトル(１，２，…，Ｋ)に関する置換π１に互いに合意する。この置換はプロセッサには未知である。その後、各パーティーＰｊは、その持分ａｊを代表するパーティー
【００５５】
【数５】
【００５６】
に送信し、置換に従ってインデックスが変更されている自身の持分ｂｊをプロセッサに送信する。したがって、そのステップの後に、そのパーティーは、π１(ａ)によって与えられる置換済み加法的持分を有し、一方、プロセッサは、置換済み加法的持分π１(ｂ)を有する。
【００５７】
パーティーＰｊは鍵対(ｐｋ，ｓｋ)を生成する。ただし、ｐｋは準同型暗号化のための公開鍵であり、ｓｋはパーティーにのみ知られており、プロセッサには知られていない秘密解読鍵である。ａの要素単位の暗号化はξ(ａ)と定義される。パーティーは、プロセッサに、ξ(π１(ａ))＝π１(ξ(ａ))を送信する。
【００５８】
プロセッサは、ランダムベクトルｒ＝(ｒ１，ｒ２，…，ｒＫ)を生成する。ただし、要素ｒｉは無作為に均等に選択される整数であり、同程度に正又は負である可能性がある。その後、プロセッサは、ξ(π１(ａｊ))ξ(ｒｊ)＝ξ(π１(ａｊ)＋ｒｊ)を計算する。ベクトル表記では、プロセッサはξ(π１(ａ)＋ｒ)を計算する。
【００５９】
同様に、受信された加法的持分と同じ順序において同じ乱数整数を減算することによって、プロセッサはπ１(ｂ)−ｒを得て、無作為に置換π２を選択し、信号
【００６０】
【数６】
【００６１】
及び信号π２(π１(ｂ)−ｒ)を得る。プロセッサは信号ξ(π２(π１(ｂ)＋ｒ))を個々のパーティーに順に、たとえば、第１のパーティーＰ１に第１の要素を、第２のパーティーＰ２に第２の要素を、第ＫのパーティーＰＫに第Ｋの要素を送信する。
【００６２】
各パーティーは、プロセッサから受信された信号を解読する。すなわち、パーティーＰ１、Ｐ２、…、ＰＫはそれぞれ、ベクトルπ２(π１(ａ)＋ｒ)の要素を有し、一方、プロセッサはベクトルπ２(π１(ｂ)−ｒ)を有する。π１はプロセッサには未知であり、π２はパーティーには未知であるので、両方のベクトル内のインデックスは不明瞭化される。
【００６３】
【数７】
【００６４】
かつ
【００６５】
【数８】
【００６６】
である場合には、以下の式が成り立つ。
【００６７】
【数９】
【００６８】
(ｉ，ｊ)対毎に(ただし、ｉ、ｊ∈｛１、２、…、Ｋ｝)、セキュアな億万長者プロトコルを実施することによって、これらの比較を解くことができる。全ての比較が行われたとき、プロセッサは、
【００６９】
【数１０】
【００７０】
が成り立つようなインデックス
【００７１】
【数１１】
【００７２】
３２５を求める。しかしながら、最も小さなデータセットに対応する真のインデックスは不明瞭化される。
【００７３】
最も小さなデータベースの雑音値の第１の加法的持分をオブリビアスに(obliviously：気付かずに)選択する
不明瞭化インデックス３１５に基づいて、プロセッサは、全ての雑音値の加法的持分３４０から、最も小さなデータベースに関連付けられた雑音値の第１の加法的持分３３５をオブリビアスに選択する(３３０)。最も小さなデータベースに関連付けられた雑音値の第２の加法的持分３６０が１つ又は複数のデータベースによって格納される。
【００７４】
たとえば、プロセッサは、
【００７５】
【数１２】
【００７６】
であり、かつ他の全ての要素が０であるような、長さＫのインジケーターベクトルｕを構成する。その後、プロセッサは、インジケーターベクトルを置換して、置換済みベクトルπ２−１(ｕ)を生成する。ただし、π２−１はπ２を反転する。次に、プロセッサは、加法的準同型関数ζ(・)のための鍵対(ｐｋ’，ｓｋ’)を生成し、パーティーＰｊにζ(π２−１(ｕ))＝π２−１(ζ(ｕ))を送信する。ただし、暗号鍵ｐｋ’だけが、パーティーＰｊが利用できるように公開される。
【００７７】
パーティーは、置換済みベクトルπ１−１(π２−１(ζ(ｕ)))＝ζ(ｖ)を互いに入手する。ただし、π１−１は、パーティーＰｊによって当初に適用された置換π１を反転し、ｖは基底ベクトルである。ここで両方の置換が除去されたので、インジケーターベクトルｖ内の０以外の要素のインデックスは、最も小さなデータベースの真のインデックスに対応する。しかしながら、パーティーＰｊはζ(・)を解読することができないので、パーティーはこのインデックスを見つけ出すことはできない。
【００７８】
ｊ＝１、…、Ｋについて、パーティーＰｊは雑音値ηｊを選択する。一実施の形態では、雑音値は、パラメーター２／(ｎｊελ)を有するラプラス(Ｌａｐ)分布からサンプリングされるｄ次元雑音ベクトルである。別の実施の形態では、異なる分布から雑音ベクトルが選択される。さらに別の実施の形態では、雑音ベクトルは予め決定される。その後、パーティーはｄ次元ベクトルΨｊを入手する。ただし、ｉ＝１、…、ｄについて、以下の式が成り立つ。
【００７９】
【数１３】
【００８０】
全てのパーティーＰｊが、ｉ＝１、…、ｄについて、以下の式が成り立つようなｄ次元雑音ベクトルΨを計算する。
【００８１】
【数１４】
【００８２】
構成によって、上記の式は、他の全てのデータベースのための雑音値を拒否しながら、最も小さなデータベースのための雑音値のみを選択する。これは、ｖが最も小さなデータベースに対応するインデックスにおいて値１を有する要素を有し、他の全ての場所において０を有するためである。
【００８３】
パーティーのうちの１つ、たとえば、Ｐ１が、ｄ次元乱数整数雑音ベクトルＳを生成し、それにより、全てのｉ＝１、…、ｄについて第１の加法的持分３３５ψ(ｉ)ζ(ｓ(ｉ))を生成し、第１の加法的持分をプロセッサに送信する。また、パーティーＰ１は、たとえば、ｗ１−Ｋｓを計算することによって、雑音値の第２の加法的持分３６０を格納する。ただし、ｗ１はそのパーティーの分類器である。付加的に又は代替的に、第２の加法的持分は複数のデータベースによって格納される。
【００８４】
プロセッサは、ｉ＝１、…、ｄについて、ψ(ｉ)ξ(ｓ(ｉ))を解読して、η(ｉ)＋ｓ(ｉ)を入手する。したがって、プロセッサは、最も小さなデータベースに関連付けられた雑音値の第１の加法的持分をＫ(η＋ｓ)として格納し、選択されたパーティーＰ１が雑音値の第２の加法的持分及び分類器をｗ１−Ｋｓとして格納し、他の全てのパーティーＰｊ(ｊ＝２、…、Ｋ)が分類器ｗｊを格納する。
【００８５】
分類器、第１の加法的持分及び第２の加法的持分をオブリビアスに組み合わせる
種々の実施の形態において、プロセッサ、及びデータベースを所有するＫ個のパーティーは、Ｋ＋１人の関係者のそれぞれが差分プライバシー集合分類器ＫｗＳの加法的持分を入手するように、セキュアな関数評価プロトコルを実行する。いくつかの実施の形態では、加法的持分は、計算上セキュアなプロトコルを用いて生成される。他の実施の形態では、加法的持分は、無条件にセキュアなプロトコルを用いて生成される。結果として生成されるＫ＋１個の持分は、差分プライバシー集合分類器を形成し、公開され、たとえば、メモリ１７５に格納される。
【００８６】
付録Ａ
マルチパーティー環境における差分プライバシーのための理論的証明
最も小さなデータベースのサイズに基づいて確率的成分を選択すれば十分である。以下において、これが事実であるという理論的証明が与えられる。
【００８７】
差分プライバシーの証明
この発明における摂動集合分類器は差分プライバシーを満たすことを示す。正則化回帰分類器の感度に関する以下の限界を用いる。
【００８８】
定理１ 半径１の球体内に存在するｎ個のデータインスタンスの集合を与えるとき、正則化ロジスティック回帰関数の感度は高くても２／(ｎλ)である。ｗ１及びｗ２が正則化パラメーターλを用いてサイズｎの隣接するデータベースにおいてトレーニングされた関数(分類器)であるとすると、以下の式が成り立つ。
【００８９】
【数１５】
【００９０】
この限界は、Kamalika Chaudhuri及びClaire Monteleoni「Privacy-preserving logistic regression」(Neural Information Processing Systems, pages 289-296, 2008)によって証明されており、その文献は参照により本明細書に援用される。この発明における摂動関数又は分類器が差分プライバシーを満たすことを示すために、以下のように進める。
【００９１】
定理２ 分類器ｗＳはε差分プライバシーを保護する。任意の２つの隣接するデータベースＤ及びＤ’について、以下の式が成り立つ。
【００９２】
【数１６】
【００９３】
証明 トレーニングデータベースＤの１つのインスタンスが変更され、結果として隣接するデータベースＤ’が生成される場合について考える。これは、 １つのパーティーのトレーニングデータベース内の１つの要素の変更、それにより、対応する学習されたベクトルｗＳｊ内の変更を意味するであろう。その変更がパーティーＰｊのデータベース内にあると仮定すると、学習されたベクトルの変更はｗｊ内に入るだけである。新たな分類器をｗｊ’によって表すものとする。定理１において、ｗｊの感度を｜｜ｗｊ−ｗｊ’ ｜｜１≦２／(ｎｊελ)と制限する。トレーニングデータベースＤ及びＤ’のいずれかを用いて同じベクトルｗＳを学習することを考えるとき、関数感度の定義によって、以下の式が得られる。
【００９４】
【数１７】
【００９５】
同様に、ｅｘｐ(−ε)によって、その比の下限を設定することができる。
【００９６】
過剰誤差の解析
予想されるように、摂動雑音項を付加することによって、関数評価において誤差が導入される。分類器として用いられる関数の場合、この誤差は過剰誤差又は過剰リスクと呼ばれる。それは、差分プライバシーに対して支払われる対価である。差分プライバシー分類器が有用であるためには、過剰リスクは小さいことが望ましい。言い換えると、雑音を付加することによって、分類性能をあまりにも劣化させないことが望ましい。
【００９７】
上記の検討において、トレーニングデータ全体においてトレーニングされた非プライバシー非摂動分類器ｗ＊に対して、この発明における(差分プライバシーを満たす)摂動集合分類器ｗＳを用いるときに、どの程度の誤差が導入されるかを考える。また、(非プライバシー)非摂動集合分類器ｗに対して、どの程度の誤差が導入されるかも考える。
【００９８】
最初に、集合分類器ｗと、トレーニングデータ全体にわたってトレーニングされた分類器ｗ＊との間の差のｌ(エル)２ノルムに関する限界を確立する。その限界を証明するために、以下の補助定理を適用する。
【００９９】
補助定理１ Ｇ(ｗ)及びｇ(ｗ)をｗの２つの区別可能な凸関数とする。
【０１００】
【数１８】
【０１０１】
とすると、｜｜ｗ１−ｗ２｜｜≦ｇ１／Ｇ２である。ただし、任意の単位ベクトルｖ∈Ｒｄについて、ｇ１＝ｍａｘｗ｜｜∇ｇ(ｗ)｜｜及びＧ２＝ｍｉｎｖｍｉｎｗｖＴ∇２Ｇ(ｗ)ｖである。
【０１０２】
補助定理１は、Kamalika Chaudhuri及びClaire Monteleoni「Privacy-preserving logistic regression」(Neural Information Processing Systems, pages 289-296, 2008)から得られたものであり、その文献は参照により本明細書に援用される。最初に、非プライバシー非摂動集合分類器ｗと、データベース全体において調整された非プライバシー分類器ｗ＊との間の過剰リスクを制限する以下の定理を考える。
【０１０３】
定理３ 集合分類器ｗ、トレーニングデータ全体にわたってトレーニングされた分類器ｗ＊が与えられ、ｎ(１)が最も小さなトレーニングデータベースのサイズであるとすると、以下の式が成り立つ。
【０１０４】
【数１９】
【０１０５】
証明：
２つの区別可能な凸関数ｇ(ｗ)及びＧ(ｗ)を最小にすることに関して、個々の分類器ｗｊ及びトレーニングデータ全体にわたってトレーニングされた分類器ｗ＊を推定するという問題を定式化する。
【０１０６】
【数２０】
【０１０７】
補助定理６．２におけるｇ１及びＧ２に関する限界を代入すると、以下の式が成り立つ。
【０１０８】
【数２１】
【０１０９】
三角不等式を適用すると、以下の式が成り立つ。
【０１１０】
【数２２】
【０１１１】
ただし、ｎ(１)＝ｍｉｎｊｎｊである。
【０１１２】
その限界は、最も小さなデータベース内のインスタンスの数に反比例する。これは、データベースが異なるサイズからなるとき、ｗはｗ＊とは大きくことなることを示す。ｎ(１)が取り得る最も大きな値はｎ／Ｋであり、その場合、全てのパーティーが等しい量のトレーニングデータを有し、ｗはｗ＊に最も近くなるであろう。Ｋ＝１の場合の１つのパーティーの事例では、その限界は、差のノルムの上限が０に設定されることを示し、それは、集合分類器ｗがｗ＊と同じであるときに有効なサニティーチェックである。
【０１１３】
この結果を用いて、以下の定理において、非摂動分類器ｗ＊の経験的リスクを上回る摂動集合分類器ｗＳ＝ｗ＋ηの経験的リスクに関する限界を確立する。
【０１１４】
定理４ 全てのデータインスタンスｘｉが、少なくとも１−δの確率で単位球内に存在する場合には、トレーニングデータ全体にわたってトレーニングされた分類器ｗ＊を上回る摂動集合分類器ｗＳの経験的正則化過剰リスクは以下の通りである。
【０１１５】
【数２３】
【０１１６】
証明：或る
【０１１７】
【数２４】
【０１１８】
について、関数Ｊのテイラー級数展開を用いて、以下の式が得られる。
【０１１９】
【数２５】
【０１２０】
定義により、∇Ｊ(ｗ＊)＝０である。
【０１２１】
両辺のｌ(エル)２ノルムを取り、コーシー−シュワルツ不等式を適用すると、以下の式が得られる。
【０１２２】
【数２６】
【０１２３】
ロジスティック回帰のための正則化損失関数の第二勾配は以下の通りである。
【０１２４】
【数２７】
【０１２５】
ロジスティック関数項は常に１未満であり、かつ全てのｘｉが単位球内に存在するので、｜｜∇２Ｊ(ｗ＊) ｜｜≦λ＋１である。これを式８に代入し、
【０１２６】
【数２８】
【０１２７】
の場合に、Ｊ(ｗ＊)≦Ｊ(ｗ)であるという事実を用いるとき、以下の式が成り立つ。
【０１２８】
【数２９】
【０１２９】
分類器ｗＳは、雑音項η：Ｌａｐ(２／(ｎ(１)ελ))を有する摂動集合分類器であり、すなわち、ｗＳ＝ｗ＋ηである。少なくとも１−δの確率で｜｜η｜｜を制限するために、Kamalika Chaudhuri及びClaire Monteleoni「Privacy-preserving logistic regression」(Neural Information Processing Systems, pages 289-296, 2008)からの以下の補助定理を適用し、その文献は参照により本明細書に援用される。
【０１３０】
補助定理２ 少なくとも１−δの確率を有するｄ次元の確率変数η：Ｌａｐ(β)、すなわち、
【０１３１】
【数３０】
【０１３２】
が与えられたとすると、その確率変数のｌ(エル)２ノルムは以下のように制限される。
【０１３３】
【数３１】
【０１３４】
これを式９に代入すると、以下の式が得られる。
【０１３５】
【数３２】
【０１３６】
最後の項においてコーシー−シュワルツ不等式を用いると、以下の式が得られる。
【０１３７】
【数３３】
【０１３８】
その限界は、２つの要因：集合及び摂動による誤差を示唆する。εの値が小さいほど、同じ意味で、差分プライバシーの定義が厳しいほど、その限界は増大し、プライバシーと有用性との間に明らかなトレードオフがあることを示す。また、その限界はｎ(１)２に反比例し、それは、パーティーが異なるサイズのトレーニングデータベースを有するときに、過剰リスクが増加することを意味する。
【０１３９】
極端な事例ε→∞では、無限小の分散のラプラシアン分布からサンプリングされる摂動項ηを加算しており、結果として、その摂動分類器は、差分プライバシーのあまり厳密でない定義を満たす非摂動集合分類器ｗを用いるのと概ね同じである。そのようなε値の場合、この発明の限界は以下のようになる。
【０１４０】
【数３４】
【０１４１】
定理３の解析と同じように、集合分類器を用いる際の過剰誤差は最も小さなデータベースｎ(１)のサイズに反比例し、１パーティーの事例Ｋ＝１では、集合分類器ｗがｗ＊と同じであるので、その限界は０になる。
【０１４２】
上記の定理は所与のトレーニングデータベースを上回る経験的過剰リスクに関する限界を与えるが、ｗ＊を上回るｗＳの真の過剰リスクに関する限界について考えることが重要である。分類器ｗＳの真のリスクを
【０１４３】
【数３５】
【０１４４】
によって表し、同様に、分類器ｗ＊の真のリスクを
【０１４５】
【数３６】
【０１４６】
によって表すことにする。
【０１４７】
定理５ 全てのトレーニングデータインスタンスｘｉが、少なくとも１−δの確率で単位球内に存在する場合には、トレーニングデータ全体にわたってトレーニングされた分類器ｗ＊を上回る摂動集合分類器ｗＳの真の過剰リスクは以下の通りである。
【０１４８】
【数３７】
【０１４９】
証明：
ｗｒを真のリスク
【０１５０】
【数３８】
【０１５１】
を最小にする分類器とする。項を並べ替えることによって、以下の式が得られる。
【０１５２】
【数３９】
【０１５３】
さらに進むために、最初に、分類器のための正則化経験的リスクに関する限界の表現としての任意の分類器の真の過剰リスクと、正則化経験的リスクを最小にする分類器の真の過剰リスクとの間の限界を必要とする。少なくとも１−δの確率で、以下の式が成り立つ。
【０１５４】
【数４０】
【０１５５】
定理４からの限界を代入すると、以下の式が得られる。
【０１５６】
【数４１】
【０１５７】
この限界を式１０に代入することによって、分類器ｗ＊を上回る分類器ｗＳの真の過剰リスクに関する限界が与えられる。
【技術分野】
【０００１】
この発明は包括的には差分データプライバシー(differential data privacy)に関し、より詳細には、複数データベースのための差分プライバシー集合分類器(differentially private aggregate classifier)を求めることに関する。
【背景技術】
【０００２】
データ収集は種々の学問、産業、商業及び政治目的のための情報を提供する。たとえば、データ収集は社会学研究、市場調査及び国勢調査において必要である。収集されたデータの有用性を最大にするために、全てのデータを蓄積し、如何なるプライバシーコントロールも用いることなく、解析のために利用されるようにすることができる。当然、大部分の人々及び組織(「プライバシー当事者」)は、データが容易に交換され、許可されない人がアクセスできるときに特に、全てのデータを開示することを好まない。プライバシーを保証することは、プライバシー当事者がデータを快く提供できるようにし、かつ不正行為、個人情報盗難、脅迫、及び十分なプライバシー保護を用いることなくデータを共有することから生じる可能性がある他の問題を軽減することができる。
【０００３】
プライバシーを保護するための方法は、収集されたデータに関して実行されたクエリ(問合せ)の集合的結果を計算し、関与しているプライバシー当事者の入力を開示することなく、そのような集合的結果を開示することである。たとえば、医療データベースにクエリして、データベース内の何人がＨＩＶ陽性であるかを判断することができる。ＨＩＶ陽性の個人の名前を開示することなく、ＨＩＶ陽性の全人数を開示することができる。このようにして、当事者のプライバシーを明示的に或る程度まで保護しながら、有用なデータが抽出される。
【０００４】
しかしながら、敵対者は種々の技法を適用して、医療データベースからＨＩＶ陽性である可能性が高い１組の個人を予測するか、又はその範囲を絞ることができる。たとえば、敵対者は、ＨＩＶを有しかつジョンスミスという名前でない人の数を尋ねる別のクエリを実行する可能性がある。その後、その敵対者は、第１のクエリ出力から第２のクエリ出力を引くことができ、それにより、プライバシー当事者の名前に関してデータベースに直に尋ねることなく、ジョンスミスのＨＩＶ状態を突き止めることができる。機密に関わるデータの場合、検証可能なプライバシー保証を提供することが有用である。たとえば、最初に知られていたこと以外に、いかなる特定のプライバシー当事者に関しても何も探り出すことができないことを検証可能に保証することが有用であろう。
【０００５】
クエリ出力に雑音を付加することによって、当事者のプライバシーを高めることができる。上記の例を用いるとき、ＨＩＶ陽性当事者の開示される数に或る乱数を付加することができる。その雑音は開示された出力の精度を低下させることになるが、それに応じてプライバシーに関する利益があるので、この損失を正当化することができる。
【０００６】
クエリ結果に雑音を付加して当事者のプライバシーを保護するという概念は一般的に知られている。１つの方法は、付加された雑音を用いて個々のデータインスタンスのプライバシーを保護するために差分プライバシー分類器を用いる。或るデータベース内の任意の個々のデータインスタンスの存否に関わらず、分類器が特定の出力を生成する確率が概ね同じであるなら、そのデータベースに関して評価される分類器は、差分プライバシーを満たすと言われる。
【０００７】
しかしながら、従来の差分プライバシー分類器は、データベース毎にローカルに求められ、その分類器を複数のデータベースにわたって用いる必要があるとき、プライバシーを提供できない。したがって、１組のデータベースに対して、各データベースの差分データプライバシーを保護するそのような分類器を求める必要がある。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
差分プライバシーが、分類器の出力が個々のデータインスタンスについての情報を含まないという統計的保証を提供する。しかしながら、マルチパーティーの応用例では、分類器を求めるためのデータがいくつかのデータベースにわたって分散され、従来の差分プライバシー法は、複数の寄与しているパーティーのための差分データプライバシーを保護しない。
【０００９】
これは、従来の方法が本来、分類器がデータベースの全データへのアクセスに基づいて求められ、データに関して計算された雑音値によって分類器を変更して、そのデータに専用の差分プライバシー分類器を生成するように設計されるためである。しかしながら、マルチパーティーの応用例では、セキュリティ制約に起因して、多くの場合に、異なるデータベースのデータにアクセスすることはできない。
【００１０】
この発明の実施の形態は、１組のデータベースについて、データベースのデータへのアクセスを許可することなく、１組のデータベース内の個々のデータベースの分類器及び雑音値から、各データベースの差分データプライバシーを保護する差分プライバシー集合分類器を求めることができるという認識に基づいている。
【００１１】
しかしながら、マルチパーティーの応用例では、分類器に雑音値を付加することはもはや簡単ではない。これは、雑音を付加した結果として各データベースの差分データプライバシーが達成されるという保証がないためである。たとえば、全ての分類器及び雑音値の集合は、論理的手法と見なされることになり、組み合わせられたデータに対する差分プライバシーを満たさない。
【００１２】
この発明の実施の形態は、１組のデータベース内の最も小さなデータベースに対応する雑音値によって変更される各データベースの分類器の集合として、差分プライバシー集合分類器を求めることができるという別の認識に基づいている。最も小さなデータベースは、最も少ないエントリ数を有し、各エントリのデータ構造は全てのデータベースにわたって同じである。この認識が正しいことの裏付けは、付録において提供される。
【課題を解決するための手段】
【００１３】
したがって、この発明の１つの実施の形態は、１組のデータベースのための差分プライバシー集合分類器を求めるための方法であって、該１組のデータベース内の各データベースは分類器及び雑音値に関連付けられ、該分類器及び該雑音値は、該分類器及び該雑音値の組み合わせが前記データベースの差分データプライバシーを保証するように、前記データベース毎にローカルに求められ、前記差分プライバシー集合分類器は各前記データベースの前記差分データプライバシーを保護し、該方法は、各前記データベースの前記分類器を組み合わせて集合分類器を求めるステップと、前記１組のデータベース内の最も小さなデータベースに対応する雑音値を用いて前記集合分類器を変更するステップとを含み、前記最も小さなデータベースは最も少ないエントリ数を有し、各エントリのデータ構造は全てのデータベースについて同じである、方法を開示する。
【００１４】
さらに、この発明の種々の実施の形態は、暗号プロトコルを用いてセキュア(安全)に差分プライバシー集合分類器を求める。それらの実施の形態は、各データベースのデータがいかなる他のパーティーとも共有されないこと、及び差分プライバシー集合分類器をリバースエンジニアリングによって解析していかなるデータベースのいかなる個々のデータも突き止めることができないことを保証する。
【００１５】
別の実施の形態は、１組のデータベースのための差分プライバシー集合分類器を求めるためのシステムであって、該１組のデータベース内の各データベースは分類器及び雑音値に関連付けられ、該分類器及び該雑音値は、該分類器及び該雑音値の組み合わせが該データベースの差分データプライバシーを保証するように、前記データベース毎にローカルに求められ、前記差分プライバシー集合分類器は各前記データベースの前記差分データプライバシーを保護し、該システムは、前記分類器を組み合わせて集合分類器を求める手段と、前記１組のデータベース内の最も小さなデータベースに対応する雑音値を用いて前記集合分類器を変更して、前記差分プライバシー集合分類器を生成する手段とを備える、システムを開示する。
【００１６】
さらに別の実施の形態は、１組のデータベースのための差分プライバシー集合分類器を格納するコンピューター読み取り可能な記憶媒体であって、該１組のデータベース内の各データベースは分類器及び雑音値に関連付けられ、該分類器及び該雑音値は、該分類器及び該雑音値の組み合わせが前記データベースの差分データプライバシーを保証するように、前記データベース毎にローカルに求められ、前記差分プライバシー集合分類器は、前記１組のデータベース内の最も小さなデータベースに対応する雑音値を用いて変更された、該１組のデータベースの前記分類器の組み合わせである、コンピューター読み取り可能な記憶媒体を開示する。
【発明の効果】
【００１７】
この発明の実施の形態は、差分プライバシー集合分類器を求め、複数データベースの差分プライバシーを保証する。この発明は、マルチパーティー差分プライバシーを達成するのに、最も小さなデータベースのサイズに基づいて確率的成分を選択すれば十分であるという認識に基づいている。いくつかの実施の形態は、この認識のために、ＳＭＣ法を介して雑音値の選択をセキュアに実行することができることをさらに認めている。
【００１８】
しかしながら、従来の方法とは異なり、それらの実施の形態は分類器を構成するのにＳＭＣを使用しない。それゆえ、この発明の実施の形態は、組み合わせられたデータにおいて分類器を計算する任意のＳＭＣ法よりもはるかに簡単である。
【図面の簡単な説明】
【００１９】
【図１】この発明による差分プライバシー集合分類器を求めるための方法のブロック図である。
【図２Ａ】取り得る雑音値の指数分布のグラフである。
【図２Ｂ】取り得る雑音値の正規分布のグラフである。
【図２Ｃ】取り得る雑音値の混成分布のグラフである。
【図３】この発明の一実施の形態による、差分プライバシー集合分類器をセキュアに求めるための方法のブロック図である。
【発明を実施するための形態】
【００２０】
定義
この発明の実施の形態を説明する際に、全体を通して(上記の説明も含む)以下の定義が適用可能である。
【００２１】
「コンピューター」は、構造化された入力を受け取り、構造化された入力を所定の規則に従って処理し、処理結果を出力として生成することができる任意の装置を指している。コンピューターの例には、コンピューター；汎用コンピューター；スーパーコンピューター；メインフレーム；スーパーミニコンピューター；ミニコンピューター；ワークステーション；マイクロコンピューター；サーバー；双方向テレビ；コンピューター及び双方向テレビの種々の組み合わせ；並びにコンピューター及び／又はソフトウエアをエミュレートする専用ハードウエアが含まれる。コンピューターは単一のプロセッサ又は複数のプロセッサを有することができ、それらのプロセッサは並列に、かつ／又は非並列に動作することができる。また、コンピューターは、コンピューター間で情報を送信又は受信するためのネットワークを介して共に接続される２つ以上のコンピューターも指している。そのようなコンピューターの例には、ネットワークによってリンクされるコンピューターを介して情報を処理するための分散コンピューターシステムが含まれる。
【００２２】
「中央演算装置(ＣＰＵ)」又は「プロセッサ」は、ソフトウエア命令を読み出し、実行するコンピューター、又はコンピューターの構成要素を指している。
【００２３】
「メモリ」又は「コンピューター可読媒体」は、コンピューターによってアクセス可能なデータを格納するための任意の記憶装置を指している。その例には、磁気ハードディスク；フロッピィディスク；ＣＤ−ＲＯＭ又はＤＶＤのような光ディスク；磁気テープ；メモリチップ；電子メールを送受信する際に、又はネットワークにアクセスする際に用いられるような、コンピューター可読電子データを搬送するために用いられる搬送波、並びにコンピューターメモリ、たとえば、ランダムアクセスメモリ(ＲＡＭ)が含まれる。
【００２４】
「ソフトウエア」は、コンピューターを動作させるための所定の規則を指している。ソフトウエアの例には、ソフトウエア；コードセグメント；命令；コンピュータープログラム；及びプログラムされたロジックが含まれる。インテリジェントシステムのソフトウエアは、自己学習できる場合もある。
【００２５】
「モジュール」又は「ユニット」は、タスク又はタスクの一部を実行するコンピューター内の基本構成要素を指している。それはソフトウエア又はハードウエアのいずれかによって実装することができる。
【００２６】
図１に示されるように、この発明の実施の形態は、１組のデータベース１１０のための差分プライバシー集合分類器１７０であって、該１組のデータベース内の各データベースの差分データプライバシーを保護するような差分プライバシー集合分類器１７０を求めるためのシステム及び方法１００を開示する。この発明の実施の形態は、当該技術分野において既知であるように、メモリ及び入力／出力インターフェースを含むプロセッサ１０１によって実施することができる。
【００２７】
１組のデータベース１１０内の各データベース１２０〜１３０は、分類器、たとえば、分類器１２１及び１３１、並びに雑音値、たとえば、雑音値１２２及び１３２に関連付けられる。たとえば、データベースはＤ１、…、ＤＫと表される。ただし、Ｄｉ＝(ｘ，ｙ)｜ｊは１組のエントリｘと、対応する２値ラベルｙとを含む。分類器及び雑音値の組み合わせがデータベースの差分データプライバシー１２５又は１３５を保証するように、分類器及び雑音値はデータベース毎にローカルに求められる。「ローカルに求められる」は、分類器及び雑音値が、方法１００の実行前に、又は実行と同時にデータベースの各所有者によって独立して求められることを意味する。
【００２８】
通常、差分プライバシーを保証するために、雑音値はデータベースのサイズ１２３又は１３３に依拠してデータベースの全データエントリにわたって求められる。本明細書において用いられるときに、「データベースのサイズ」は、エントリの数に基づいている。エントリは任意のデータ構造を有することができる。しかしながら、各エントリのデータ構造は全てのデータベースにわたって同じである。エントリの例は、フィールド、表内の行、表自体、ファイル、又は別のデータベースである。
【００２９】
この発明の実施の形態は、データベースの和集合Ｄ１∪Ｄ２…∪ＤＫからの差分プライバシー集合分類器を、１組のデータベース内の最も小さなデータベースに対応する雑音値によって変更される各データベースの分類器の集合として求めることができるという認識に基づいている。最も小さなデータベースは最も少ないエントリ数を有し、各エントリのデータ構造は全てのデータベースについて同じである。この認識が正しいことの裏付けは、付録Ａにおいて提供される。
【００３０】
したがって、一実施の形態は、各データベースの分類器を組み合わせて、集合分類器１４５を求める(１４０)。さらに、それらの実施の形態は、最も小さなデータベースに対応する雑音値１５５を求める(１５０)。次に、雑音値１５５を用いて集合分類器１４５を変更し(１６０)、差分プライバシー集合分類器１７０を生成する。差分プライバシー集合分類器は公開され、たとえば、メモリ１７５に格納されるか、又はインターネット上で配布される。
【００３１】
差分プライバシー
差分プライバシーモデルの定義によれば、１つの要素だけ異なる任意の２つのデータベースＤ及びＤ’、すなわち、隣接するデータベースが与えられたとすると、関数ＭがデータベースＤにおいて応答Ｓを生成する確率が、関数ＭがデータベースＤ’において同じ応答Ｓを生成する確率と同様である場合には、ランダム化クエリ関数Ｍによって定義される分類器は差分プライバシーを有する。個々のエントリの存在又は不在時に、クエリ出力が高い確率で概ね同じであるので、出力からいかなる個々のエントリについてもほとんど何も突き止めることはできない。
【００３２】
全ての隣接するデータベースＤ及びＤ’の場合に、かつ任意のＳ∈ｒａｎｇｅ(Ｍ)の場合に、以下の式が成り立つ場合には、明確な確率密度Ｐを有するランダム化関数Ｍは、ε差分プライバシーを満たす。
【００３３】
【数１】
【００３４】
したがって、差分プライバシー分類器は、アプリオリの背景知識以外に、学習アルゴリズムの出力から確信を持って個々のエントリについてのさらに詳しい事柄を得ることができないことを保証する。差分プライバシーは、特定の１組の攻撃及び敵対的挙動に対して「その場限りの(ad hoc)」保証を与える大部分の他のモデルとは対照的に、「全てに通じる(ad omina)」保証を与える。多数のエントリにわたって差分プライバシー分類器を評価しても、敵対者は、そのデータの厳密な形を突き止めることはできない。
【００３５】
図２Ａ〜図２Ｃは、横軸に沿って雑音値を、縦軸においてそのような雑音値に関連付けられた確率を示す。したがって、高い確率を有する雑音値が、選択される可能性が高い。それらの分布は全て、絶対値が大きくなると、所与の雑音値の確率が小さくなるという有益な特徴を共有する。過度に高い雑音値の確率が起こる可能性は小さいので、この特徴によれば、雑音を含む出力を有用にすることができる。
【００３６】
図２Ａは、雑音値の指数分布２１０を示す。図２Ｂは、雑音値の正規分布２２０を示す。図２Ｃは、雑音値の混成分布２３０を示す。図２Ｃの混成分布は、最も確からしい雑音値を含む分布の部分、すなわち、より高い確率を有する部分を正規分布が定義し、最も確からしくない雑音値を含む分布の部分、すなわち、より大きな絶対雑音値に対応する低い確率を有する部分を指数分布が定義するような、正規分布及び指数分布である。
【００３７】
図２Ａ〜図２Ｃにおいて各分布を計算する際に、差分直径２４０及びプライバシーパラメーターεを用いることができる。大きな差分直径値は分布を広くし、より高い雑音値が用いられる確率を高める。逆に、小さな差分直径は、大きな雑音値が選択される可能性を小さくする。プライバシーパラメーターが分布関数の分母にあるとき、小さい値のプライバシーパラメーターεが強いプライバシーに対応し、その逆も成り立つ。上記の例示的な式は満足できるものであり、それを用いて無限の様々な分布を構成することができ、それらの分布は差分直径測定値及びプライバシーパラメーターを利用して、満足できる雑音分布を作り出すのに成功する。たとえば、図２Ａ〜図２Ｃにおいて示される分布に対して無数の小さな変更を加えることができる。
【００３８】
通常、それらの分類器は、分類器の重みに雑音値を加算することによって、差分プライバシーを有するように設計される。ただし、雑音値は上記の分布から選択される。さらに、分布のパラメーターは、イプシロンεによって表される所望のプライバシー度に依存し、それは通常、データベースのサイズに、かつ分類器の関数のタイプ、たとえば、平均関数、最大関数又は対数関数に依存する。一実施の形態では、雑音値はラプラス分布を有する。
【００３９】
個々のデータベースにおいて分類器をローカルに求める
各データベース所有者Ｐｊが、そのデータベース(ｘ，ｙ)｜ｊを用いて、重みｗｊを有する分類器を求める。ただし、ｊはデータベースのインデックスである。一実施の形態は、分類器のために、正則化ロジスティック回帰関数ｌ(エル)２を用いる。たとえば、分類器ｗｊは、以下の目的関数を最小にすることによって求めることができる。
【００４０】
【数２】
【００４１】
ただし、λ＞０は正則化パラメーターであり、Ｔは転置演算子である。しかしながら、それらの分類器は個々のデータベース毎にローカルに求められ、データ又は情報は共有されない。
【００４２】
差分プライバシー集合分類器の例
この発明の一実施の形態は、以下の式に従って、差分プライバシー集合分類器ｗＳ１７０を定義する。
【００４３】
【数３】
【００４４】
ただし、Ｋは１組のデータベース内のデータベースの数であり、ｊはデータベースのインデックスであり、ηはパラメーター２／(ｎ(１)ελ)を用いてスケーリングされるラプラス(Ｌａｐ)分布からサンプリングされるｄ次元確率変数であり、ｎ(１)は最も小さなデータベースに対応する雑音値、すなわち、ｎ(１)＝ｍｉｎｊｎｊであり、λはラプラス分布のパラメーターであり、εは差分プライバシーパラメーターである。
【００４５】
差分プライバシー集合分類器ｗＳは、パーティーがそのプライバシーを保持できるようにしながら、全てのデータの和集合において分類器を直にトレーニングすることによって、十分に制限された過剰リスクのみを受ける。雑音値ηは、分類器ｗＳが差分プライバシーを満たすことを、すなわち、分類器から個々のデータインスタンスを判別できないことを保証する。
【００４６】
上記の雑音値ηの定義は直観的ではなく、この発明によれば、ローカルにトレーニングされた分類器を集めることによって構成された差分プライバシー集合分類器が、最も少ない数のエントリを有する個々の分類器の性能によって制限されることが証明された。
【００４７】
ローカルにトレーニングされた分類器を集めても、差分プライバシーを保証する正しい雑音値
【００４８】
【数４】
【００４９】
を与えないので、この発明のいくつかの実施の形態は、データベースＰｊの所有者は、単にそのような分類器ｗｊを取り込み、雑音ベクトルを用いてそれらの分類器を摂動させて、摂動した分類器を公開することはできないという認識に基づいている。また、個々のデータベース所有者は、他の全ての分類器に対して差分プライバシーを課すために、それらの分類器に単に雑音を加算することはできないので、個々の分類器、又は各データベース内のエントリの数が暴かれないように、実際の平均化演算を実行しなければならない。したがって、いくつかの実施の形態は、プロセッサとインタラクトして平均化を実行するために、セキュアマルチパーティー計算(ＳＭＣ)法を用いる。その方法の結果として、データベース所有者のそれぞれが所望の差分プライバシー分類器ｗＳの加法的持分(additive share)を得るようになり、差分プライバシー集合分類器を得るために、これら持分を加算しなければならないようになっている。
【００５０】
セキュアマルチパーティー計算(ＳＭＣ)法
それらの実施の形態は、非対称鍵加法的準同型暗号化を用いる。そのような暗号化の所望の特性は、暗号文要素において実行される演算が同じ平文要素における既知の演算に写像することである。加法的準同型暗号化関数の場合、ξ(・)は、任意のａ及びｂに対して、ξ(ａ)ξ(ｂ)＝ξ(ａ＋ｂ)、ξ(ａ)ｂ＝ξ(ａｂ)であることを意味する。
【００５１】
加法的準同型暗号化は強秘匿性であり、すなわち、同じ平文を繰返し暗号化しても、結果として、異なる暗号文が生成される。ＳＭＣ法の場合、暗号鍵は、公開されていると考えられ、解読鍵は、指定されたデータベース所有者によって非公開で所有される。
【００５２】
図３は、ＳＭＣ法を用いて、差分プライバシー集合分類器１７０を求めるための方法３００のブロック図を示す。その方法はプロセッサ３０１によって実行することができる。
【００５３】
最も小さなデータベースの不明瞭化インデックスを求める
プロセッサは、データベースのインデックスの置換から生じる置換済みインデックス３２０に基づいて最も小さなデータベースの不明瞭化インデックス３１５を求める(３１０)。たとえば、各データベース所有者、すなわち、パーティーＰｊが、ｎｊ＝ａｊ＋ｂｊを計算する。ただし、ａｊ及びｂｊはデータベース長ｎｊの加法的持分を表す整数であり、ｊ＝１、２、…、Ｋである。加法的持分のＫ長ベクトルはそれぞれａ及びｂと定義される。
【００５４】
パーティーＰｊは、インデックスベクトル(１，２，…，Ｋ)に関する置換π１に互いに合意する。この置換はプロセッサには未知である。その後、各パーティーＰｊは、その持分ａｊを代表するパーティー
【００５５】
【数５】
【００５６】
に送信し、置換に従ってインデックスが変更されている自身の持分ｂｊをプロセッサに送信する。したがって、そのステップの後に、そのパーティーは、π１(ａ)によって与えられる置換済み加法的持分を有し、一方、プロセッサは、置換済み加法的持分π１(ｂ)を有する。
【００５７】
パーティーＰｊは鍵対(ｐｋ，ｓｋ)を生成する。ただし、ｐｋは準同型暗号化のための公開鍵であり、ｓｋはパーティーにのみ知られており、プロセッサには知られていない秘密解読鍵である。ａの要素単位の暗号化はξ(ａ)と定義される。パーティーは、プロセッサに、ξ(π１(ａ))＝π１(ξ(ａ))を送信する。
【００５８】
プロセッサは、ランダムベクトルｒ＝(ｒ１，ｒ２，…，ｒＫ)を生成する。ただし、要素ｒｉは無作為に均等に選択される整数であり、同程度に正又は負である可能性がある。その後、プロセッサは、ξ(π１(ａｊ))ξ(ｒｊ)＝ξ(π１(ａｊ)＋ｒｊ)を計算する。ベクトル表記では、プロセッサはξ(π１(ａ)＋ｒ)を計算する。
【００５９】
同様に、受信された加法的持分と同じ順序において同じ乱数整数を減算することによって、プロセッサはπ１(ｂ)−ｒを得て、無作為に置換π２を選択し、信号
【００６０】
【数６】
【００６１】
及び信号π２(π１(ｂ)−ｒ)を得る。プロセッサは信号ξ(π２(π１(ｂ)＋ｒ))を個々のパーティーに順に、たとえば、第１のパーティーＰ１に第１の要素を、第２のパーティーＰ２に第２の要素を、第ＫのパーティーＰＫに第Ｋの要素を送信する。
【００６２】
各パーティーは、プロセッサから受信された信号を解読する。すなわち、パーティーＰ１、Ｐ２、…、ＰＫはそれぞれ、ベクトルπ２(π１(ａ)＋ｒ)の要素を有し、一方、プロセッサはベクトルπ２(π１(ｂ)−ｒ)を有する。π１はプロセッサには未知であり、π２はパーティーには未知であるので、両方のベクトル内のインデックスは不明瞭化される。
【００６３】
【数７】
【００６４】
かつ
【００６５】
【数８】
【００６６】
である場合には、以下の式が成り立つ。
【００６７】
【数９】
【００６８】
(ｉ，ｊ)対毎に(ただし、ｉ、ｊ∈｛１、２、…、Ｋ｝)、セキュアな億万長者プロトコルを実施することによって、これらの比較を解くことができる。全ての比較が行われたとき、プロセッサは、
【００６９】
【数１０】
【００７０】
が成り立つようなインデックス
【００７１】
【数１１】
【００７２】
３２５を求める。しかしながら、最も小さなデータセットに対応する真のインデックスは不明瞭化される。
【００７３】
最も小さなデータベースの雑音値の第１の加法的持分をオブリビアスに(obliviously：気付かずに)選択する
不明瞭化インデックス３１５に基づいて、プロセッサは、全ての雑音値の加法的持分３４０から、最も小さなデータベースに関連付けられた雑音値の第１の加法的持分３３５をオブリビアスに選択する(３３０)。最も小さなデータベースに関連付けられた雑音値の第２の加法的持分３６０が１つ又は複数のデータベースによって格納される。
【００７４】
たとえば、プロセッサは、
【００７５】
【数１２】
【００７６】
であり、かつ他の全ての要素が０であるような、長さＫのインジケーターベクトルｕを構成する。その後、プロセッサは、インジケーターベクトルを置換して、置換済みベクトルπ２−１(ｕ)を生成する。ただし、π２−１はπ２を反転する。次に、プロセッサは、加法的準同型関数ζ(・)のための鍵対(ｐｋ’，ｓｋ’)を生成し、パーティーＰｊにζ(π２−１(ｕ))＝π２−１(ζ(ｕ))を送信する。ただし、暗号鍵ｐｋ’だけが、パーティーＰｊが利用できるように公開される。
【００７７】
パーティーは、置換済みベクトルπ１−１(π２−１(ζ(ｕ)))＝ζ(ｖ)を互いに入手する。ただし、π１−１は、パーティーＰｊによって当初に適用された置換π１を反転し、ｖは基底ベクトルである。ここで両方の置換が除去されたので、インジケーターベクトルｖ内の０以外の要素のインデックスは、最も小さなデータベースの真のインデックスに対応する。しかしながら、パーティーＰｊはζ(・)を解読することができないので、パーティーはこのインデックスを見つけ出すことはできない。
【００７８】
ｊ＝１、…、Ｋについて、パーティーＰｊは雑音値ηｊを選択する。一実施の形態では、雑音値は、パラメーター２／(ｎｊελ)を有するラプラス(Ｌａｐ)分布からサンプリングされるｄ次元雑音ベクトルである。別の実施の形態では、異なる分布から雑音ベクトルが選択される。さらに別の実施の形態では、雑音ベクトルは予め決定される。その後、パーティーはｄ次元ベクトルΨｊを入手する。ただし、ｉ＝１、…、ｄについて、以下の式が成り立つ。
【００７９】
【数１３】
【００８０】
全てのパーティーＰｊが、ｉ＝１、…、ｄについて、以下の式が成り立つようなｄ次元雑音ベクトルΨを計算する。
【００８１】
【数１４】
【００８２】
構成によって、上記の式は、他の全てのデータベースのための雑音値を拒否しながら、最も小さなデータベースのための雑音値のみを選択する。これは、ｖが最も小さなデータベースに対応するインデックスにおいて値１を有する要素を有し、他の全ての場所において０を有するためである。
【００８３】
パーティーのうちの１つ、たとえば、Ｐ１が、ｄ次元乱数整数雑音ベクトルＳを生成し、それにより、全てのｉ＝１、…、ｄについて第１の加法的持分３３５ψ(ｉ)ζ(ｓ(ｉ))を生成し、第１の加法的持分をプロセッサに送信する。また、パーティーＰ１は、たとえば、ｗ１−Ｋｓを計算することによって、雑音値の第２の加法的持分３６０を格納する。ただし、ｗ１はそのパーティーの分類器である。付加的に又は代替的に、第２の加法的持分は複数のデータベースによって格納される。
【００８４】
プロセッサは、ｉ＝１、…、ｄについて、ψ(ｉ)ξ(ｓ(ｉ))を解読して、η(ｉ)＋ｓ(ｉ)を入手する。したがって、プロセッサは、最も小さなデータベースに関連付けられた雑音値の第１の加法的持分をＫ(η＋ｓ)として格納し、選択されたパーティーＰ１が雑音値の第２の加法的持分及び分類器をｗ１−Ｋｓとして格納し、他の全てのパーティーＰｊ(ｊ＝２、…、Ｋ)が分類器ｗｊを格納する。
【００８５】
分類器、第１の加法的持分及び第２の加法的持分をオブリビアスに組み合わせる
種々の実施の形態において、プロセッサ、及びデータベースを所有するＫ個のパーティーは、Ｋ＋１人の関係者のそれぞれが差分プライバシー集合分類器ＫｗＳの加法的持分を入手するように、セキュアな関数評価プロトコルを実行する。いくつかの実施の形態では、加法的持分は、計算上セキュアなプロトコルを用いて生成される。他の実施の形態では、加法的持分は、無条件にセキュアなプロトコルを用いて生成される。結果として生成されるＫ＋１個の持分は、差分プライバシー集合分類器を形成し、公開され、たとえば、メモリ１７５に格納される。
【００８６】
付録Ａ
マルチパーティー環境における差分プライバシーのための理論的証明
最も小さなデータベースのサイズに基づいて確率的成分を選択すれば十分である。以下において、これが事実であるという理論的証明が与えられる。
【００８７】
差分プライバシーの証明
この発明における摂動集合分類器は差分プライバシーを満たすことを示す。正則化回帰分類器の感度に関する以下の限界を用いる。
【００８８】
定理１ 半径１の球体内に存在するｎ個のデータインスタンスの集合を与えるとき、正則化ロジスティック回帰関数の感度は高くても２／(ｎλ)である。ｗ１及びｗ２が正則化パラメーターλを用いてサイズｎの隣接するデータベースにおいてトレーニングされた関数(分類器)であるとすると、以下の式が成り立つ。
【００８９】
【数１５】
【００９０】
この限界は、Kamalika Chaudhuri及びClaire Monteleoni「Privacy-preserving logistic regression」(Neural Information Processing Systems, pages 289-296, 2008)によって証明されており、その文献は参照により本明細書に援用される。この発明における摂動関数又は分類器が差分プライバシーを満たすことを示すために、以下のように進める。
【００９１】
定理２ 分類器ｗＳはε差分プライバシーを保護する。任意の２つの隣接するデータベースＤ及びＤ’について、以下の式が成り立つ。
【００９２】
【数１６】
【００９３】
証明 トレーニングデータベースＤの１つのインスタンスが変更され、結果として隣接するデータベースＤ’が生成される場合について考える。これは、 １つのパーティーのトレーニングデータベース内の１つの要素の変更、それにより、対応する学習されたベクトルｗＳｊ内の変更を意味するであろう。その変更がパーティーＰｊのデータベース内にあると仮定すると、学習されたベクトルの変更はｗｊ内に入るだけである。新たな分類器をｗｊ’によって表すものとする。定理１において、ｗｊの感度を｜｜ｗｊ−ｗｊ’ ｜｜１≦２／(ｎｊελ)と制限する。トレーニングデータベースＤ及びＤ’のいずれかを用いて同じベクトルｗＳを学習することを考えるとき、関数感度の定義によって、以下の式が得られる。
【００９４】
【数１７】
【００９５】
同様に、ｅｘｐ(−ε)によって、その比の下限を設定することができる。
【００９６】
過剰誤差の解析
予想されるように、摂動雑音項を付加することによって、関数評価において誤差が導入される。分類器として用いられる関数の場合、この誤差は過剰誤差又は過剰リスクと呼ばれる。それは、差分プライバシーに対して支払われる対価である。差分プライバシー分類器が有用であるためには、過剰リスクは小さいことが望ましい。言い換えると、雑音を付加することによって、分類性能をあまりにも劣化させないことが望ましい。
【００９７】
上記の検討において、トレーニングデータ全体においてトレーニングされた非プライバシー非摂動分類器ｗ＊に対して、この発明における(差分プライバシーを満たす)摂動集合分類器ｗＳを用いるときに、どの程度の誤差が導入されるかを考える。また、(非プライバシー)非摂動集合分類器ｗに対して、どの程度の誤差が導入されるかも考える。
【００９８】
最初に、集合分類器ｗと、トレーニングデータ全体にわたってトレーニングされた分類器ｗ＊との間の差のｌ(エル)２ノルムに関する限界を確立する。その限界を証明するために、以下の補助定理を適用する。
【００９９】
補助定理１ Ｇ(ｗ)及びｇ(ｗ)をｗの２つの区別可能な凸関数とする。
【０１００】
【数１８】
【０１０１】
とすると、｜｜ｗ１−ｗ２｜｜≦ｇ１／Ｇ２である。ただし、任意の単位ベクトルｖ∈Ｒｄについて、ｇ１＝ｍａｘｗ｜｜∇ｇ(ｗ)｜｜及びＧ２＝ｍｉｎｖｍｉｎｗｖＴ∇２Ｇ(ｗ)ｖである。
【０１０２】
補助定理１は、Kamalika Chaudhuri及びClaire Monteleoni「Privacy-preserving logistic regression」(Neural Information Processing Systems, pages 289-296, 2008)から得られたものであり、その文献は参照により本明細書に援用される。最初に、非プライバシー非摂動集合分類器ｗと、データベース全体において調整された非プライバシー分類器ｗ＊との間の過剰リスクを制限する以下の定理を考える。
【０１０３】
定理３ 集合分類器ｗ、トレーニングデータ全体にわたってトレーニングされた分類器ｗ＊が与えられ、ｎ(１)が最も小さなトレーニングデータベースのサイズであるとすると、以下の式が成り立つ。
【０１０４】
【数１９】
【０１０５】
証明：
２つの区別可能な凸関数ｇ(ｗ)及びＧ(ｗ)を最小にすることに関して、個々の分類器ｗｊ及びトレーニングデータ全体にわたってトレーニングされた分類器ｗ＊を推定するという問題を定式化する。
【０１０６】
【数２０】
【０１０７】
補助定理６．２におけるｇ１及びＧ２に関する限界を代入すると、以下の式が成り立つ。
【０１０８】
【数２１】
【０１０９】
三角不等式を適用すると、以下の式が成り立つ。
【０１１０】
【数２２】
【０１１１】
ただし、ｎ(１)＝ｍｉｎｊｎｊである。
【０１１２】
その限界は、最も小さなデータベース内のインスタンスの数に反比例する。これは、データベースが異なるサイズからなるとき、ｗはｗ＊とは大きくことなることを示す。ｎ(１)が取り得る最も大きな値はｎ／Ｋであり、その場合、全てのパーティーが等しい量のトレーニングデータを有し、ｗはｗ＊に最も近くなるであろう。Ｋ＝１の場合の１つのパーティーの事例では、その限界は、差のノルムの上限が０に設定されることを示し、それは、集合分類器ｗがｗ＊と同じであるときに有効なサニティーチェックである。
【０１１３】
この結果を用いて、以下の定理において、非摂動分類器ｗ＊の経験的リスクを上回る摂動集合分類器ｗＳ＝ｗ＋ηの経験的リスクに関する限界を確立する。
【０１１４】
定理４ 全てのデータインスタンスｘｉが、少なくとも１−δの確率で単位球内に存在する場合には、トレーニングデータ全体にわたってトレーニングされた分類器ｗ＊を上回る摂動集合分類器ｗＳの経験的正則化過剰リスクは以下の通りである。
【０１１５】
【数２３】
【０１１６】
証明：或る
【０１１７】
【数２４】
【０１１８】
について、関数Ｊのテイラー級数展開を用いて、以下の式が得られる。
【０１１９】
【数２５】
【０１２０】
定義により、∇Ｊ(ｗ＊)＝０である。
【０１２１】
両辺のｌ(エル)２ノルムを取り、コーシー−シュワルツ不等式を適用すると、以下の式が得られる。
【０１２２】
【数２６】
【０１２３】
ロジスティック回帰のための正則化損失関数の第二勾配は以下の通りである。
【０１２４】
【数２７】
【０１２５】
ロジスティック関数項は常に１未満であり、かつ全てのｘｉが単位球内に存在するので、｜｜∇２Ｊ(ｗ＊) ｜｜≦λ＋１である。これを式８に代入し、
【０１２６】
【数２８】
【０１２７】
の場合に、Ｊ(ｗ＊)≦Ｊ(ｗ)であるという事実を用いるとき、以下の式が成り立つ。
【０１２８】
【数２９】
【０１２９】
分類器ｗＳは、雑音項η：Ｌａｐ(２／(ｎ(１)ελ))を有する摂動集合分類器であり、すなわち、ｗＳ＝ｗ＋ηである。少なくとも１−δの確率で｜｜η｜｜を制限するために、Kamalika Chaudhuri及びClaire Monteleoni「Privacy-preserving logistic regression」(Neural Information Processing Systems, pages 289-296, 2008)からの以下の補助定理を適用し、その文献は参照により本明細書に援用される。
【０１３０】
補助定理２ 少なくとも１−δの確率を有するｄ次元の確率変数η：Ｌａｐ(β)、すなわち、
【０１３１】
【数３０】
【０１３２】
が与えられたとすると、その確率変数のｌ(エル)２ノルムは以下のように制限される。
【０１３３】
【数３１】
【０１３４】
これを式９に代入すると、以下の式が得られる。
【０１３５】
【数３２】
【０１３６】
最後の項においてコーシー−シュワルツ不等式を用いると、以下の式が得られる。
【０１３７】
【数３３】
【０１３８】
その限界は、２つの要因：集合及び摂動による誤差を示唆する。εの値が小さいほど、同じ意味で、差分プライバシーの定義が厳しいほど、その限界は増大し、プライバシーと有用性との間に明らかなトレードオフがあることを示す。また、その限界はｎ(１)２に反比例し、それは、パーティーが異なるサイズのトレーニングデータベースを有するときに、過剰リスクが増加することを意味する。
【０１３９】
極端な事例ε→∞では、無限小の分散のラプラシアン分布からサンプリングされる摂動項ηを加算しており、結果として、その摂動分類器は、差分プライバシーのあまり厳密でない定義を満たす非摂動集合分類器ｗを用いるのと概ね同じである。そのようなε値の場合、この発明の限界は以下のようになる。
【０１４０】
【数３４】
【０１４１】
定理３の解析と同じように、集合分類器を用いる際の過剰誤差は最も小さなデータベースｎ(１)のサイズに反比例し、１パーティーの事例Ｋ＝１では、集合分類器ｗがｗ＊と同じであるので、その限界は０になる。
【０１４２】
上記の定理は所与のトレーニングデータベースを上回る経験的過剰リスクに関する限界を与えるが、ｗ＊を上回るｗＳの真の過剰リスクに関する限界について考えることが重要である。分類器ｗＳの真のリスクを
【０１４３】
【数３５】
【０１４４】
によって表し、同様に、分類器ｗ＊の真のリスクを
【０１４５】
【数３６】
【０１４６】
によって表すことにする。
【０１４７】
定理５ 全てのトレーニングデータインスタンスｘｉが、少なくとも１−δの確率で単位球内に存在する場合には、トレーニングデータ全体にわたってトレーニングされた分類器ｗ＊を上回る摂動集合分類器ｗＳの真の過剰リスクは以下の通りである。
【０１４８】
【数３７】
【０１４９】
証明：
ｗｒを真のリスク
【０１５０】
【数３８】
【０１５１】
を最小にする分類器とする。項を並べ替えることによって、以下の式が得られる。
【０１５２】
【数３９】
【０１５３】
さらに進むために、最初に、分類器のための正則化経験的リスクに関する限界の表現としての任意の分類器の真の過剰リスクと、正則化経験的リスクを最小にする分類器の真の過剰リスクとの間の限界を必要とする。少なくとも１−δの確率で、以下の式が成り立つ。
【０１５４】
【数４０】
【０１５５】
定理４からの限界を代入すると、以下の式が得られる。
【０１５６】
【数４１】
【０１５７】
この限界を式１０に代入することによって、分類器ｗ＊を上回る分類器ｗＳの真の過剰リスクに関する限界が与えられる。
【特許請求の範囲】
【請求項１】
１組のデータベースのための差分プライバシー集合分類器を求めるための方法であって、該１組のデータベース内の各データベースは分類器及び雑音値に関連付けられ、該分類器及び該雑音値は、該分類器及び該雑音値の組み合わせが前記データベースの差分データプライバシーを保証するように、前記データベース毎にローカルに求められ、前記差分プライバシー集合分類器は各前記データベースの前記差分データプライバシーを保護し、該方法は、
前記分類器を組み合わせて集合分類器を求めるステップと、
前記１組のデータベース内の最も小さなデータベースに対応する雑音値を用いて前記集合分類器を変更して前記差分プライバシー集合分類器を生成するステップとを含み、該方法の該ステップはプロセッサによって実行される、方法。
【請求項２】
前記最も小さなデータベースは最も少ない数のエントリを有し、前記エントリのデータ構造は全てのデータベースについて同一である、請求項１に記載の方法。
【請求項３】
前記データベースのインデックスの置換から生じる前記最も小さなデータベースの不明瞭化インデックスを求めるステップと、
全ての雑音値の加法的持分から、前記不明瞭化インデックスに基づいて、前記最も小さなデータベースに関連付けられた雑音値の第１の加法的持分をオブリビアスに選択するステップであって、第２の加法的持分が１つ又は複数のデータベース内に格納されるものと、
各前記分類器、前記雑音値の前記第１の加法的持分及び前記第２の加法的持分をオブリビアスに組み合わせることによって前記差分プライバシー集合分類器を求めるステップとをさらに含む、請求項１に記載の方法。
【請求項４】
前記雑音値はラプラス分布に従って分布する、請求項１に記載の方法。
【請求項５】
前記データベース毎の前記雑音値は前記データベースのサイズに基づいて求められる、請求項１に記載の方法。
【請求項６】
前記分類器は２値ロジスティック回帰分類器である、請求項１に記載の方法。
【請求項７】
前記分類器は、２値ロジスティック回帰分類器の組み合わせから構成されるマルチクラス分類器である、請求項６に記載の方法。
【請求項８】
前記差分プライバシー分類器を求めることは、暗号プロトコルによって実行される、請求項３に記載の方法。
【請求項９】
前記差分プライバシー分類器を求めることは、秘密共有プロトコルによって実行される、請求項３に記載の方法。
【請求項１０】
１組のデータベースのための差分プライバシー集合分類器を求めるためのシステムであって、該１組のデータベース内の各データベースは分類器及び雑音値に関連付けられ、該分類器及び該雑音値は、該分類器及び該雑音値の組み合わせが該データベースの差分データプライバシーを保証するように、前記データベース毎にローカルに求められ、前記差分プライバシー集合分類器は各前記データベースの前記差分データプライバシーを保護し、該システムは、
前記分類器を組み合わせて集合分類器を求める手段と、
前記１組のデータベース内の最も小さなデータベースに対応する雑音値を用いて前記集合分類器を変更して、前記差分プライバシー集合分類器を生成する手段とを備える、システム。
【請求項１１】
前記最も小さなデータベースは最も少ない数のエントリを有し、前記エントリのデータ構造は全てのデータベースについて同一である、請求項１０に記載のシステム。
【請求項１２】
前記データベースのインデックスの置換から生じる前記最も小さなデータベースの不明瞭化インデックスを求める手段と、
全ての雑音値の加法的持分から、前記不明瞭化インデックスに基づいて、前記最も小さなデータベースに関連付けられた雑音値の第１の加法的持分をオブリビアスに選択する手段であって、第２の加法的持分が１つ又は複数のデータベース内に格納されるものと、
各前記分類器、前記雑音値の前記第１の加法的持分及び前記第２の加法的持分をオブリビアスに組み合わせることによって前記差分プライバシー集合分類器を求める手段とをさらに備える、請求項１０に記載のシステム。
【請求項１３】
前記雑音値はラプラス分布に従って分布する、請求項１０に記載のシステム。
【請求項１４】
前記データベース毎の前記雑音値は前記データベースのサイズに基づいて求められる、請求項１０に記載のシステム。
【請求項１５】
１組のデータベースのための差分プライバシー集合分類器を格納するコンピューター読み取り可能な記憶媒体であって、該１組のデータベース内の各データベースは分類器及び雑音値に関連付けられ、該分類器及び該雑音値は、該分類器及び該雑音値の組み合わせが前記データベースの差分データプライバシーを保証するように、前記データベース毎にローカルに求められ、前記差分プライバシー集合分類器は、前記１組のデータベース内の最も小さなデータベースに対応する雑音値を用いて変更された、該１組のデータベースの前記分類器の組み合わせである、コンピューター読み取り可能な記憶媒体。
【請求項１】
１組のデータベースのための差分プライバシー集合分類器を求めるための方法であって、該１組のデータベース内の各データベースは分類器及び雑音値に関連付けられ、該分類器及び該雑音値は、該分類器及び該雑音値の組み合わせが前記データベースの差分データプライバシーを保証するように、前記データベース毎にローカルに求められ、前記差分プライバシー集合分類器は各前記データベースの前記差分データプライバシーを保護し、該方法は、
前記分類器を組み合わせて集合分類器を求めるステップと、
前記１組のデータベース内の最も小さなデータベースに対応する雑音値を用いて前記集合分類器を変更して前記差分プライバシー集合分類器を生成するステップとを含み、該方法の該ステップはプロセッサによって実行される、方法。
【請求項２】
前記最も小さなデータベースは最も少ない数のエントリを有し、前記エントリのデータ構造は全てのデータベースについて同一である、請求項１に記載の方法。
【請求項３】
前記データベースのインデックスの置換から生じる前記最も小さなデータベースの不明瞭化インデックスを求めるステップと、
全ての雑音値の加法的持分から、前記不明瞭化インデックスに基づいて、前記最も小さなデータベースに関連付けられた雑音値の第１の加法的持分をオブリビアスに選択するステップであって、第２の加法的持分が１つ又は複数のデータベース内に格納されるものと、
各前記分類器、前記雑音値の前記第１の加法的持分及び前記第２の加法的持分をオブリビアスに組み合わせることによって前記差分プライバシー集合分類器を求めるステップとをさらに含む、請求項１に記載の方法。
【請求項４】
前記雑音値はラプラス分布に従って分布する、請求項１に記載の方法。
【請求項５】
前記データベース毎の前記雑音値は前記データベースのサイズに基づいて求められる、請求項１に記載の方法。
【請求項６】
前記分類器は２値ロジスティック回帰分類器である、請求項１に記載の方法。
【請求項７】
前記分類器は、２値ロジスティック回帰分類器の組み合わせから構成されるマルチクラス分類器である、請求項６に記載の方法。
【請求項８】
前記差分プライバシー分類器を求めることは、暗号プロトコルによって実行される、請求項３に記載の方法。
【請求項９】
前記差分プライバシー分類器を求めることは、秘密共有プロトコルによって実行される、請求項３に記載の方法。
【請求項１０】
１組のデータベースのための差分プライバシー集合分類器を求めるためのシステムであって、該１組のデータベース内の各データベースは分類器及び雑音値に関連付けられ、該分類器及び該雑音値は、該分類器及び該雑音値の組み合わせが該データベースの差分データプライバシーを保証するように、前記データベース毎にローカルに求められ、前記差分プライバシー集合分類器は各前記データベースの前記差分データプライバシーを保護し、該システムは、
前記分類器を組み合わせて集合分類器を求める手段と、
前記１組のデータベース内の最も小さなデータベースに対応する雑音値を用いて前記集合分類器を変更して、前記差分プライバシー集合分類器を生成する手段とを備える、システム。
【請求項１１】
前記最も小さなデータベースは最も少ない数のエントリを有し、前記エントリのデータ構造は全てのデータベースについて同一である、請求項１０に記載のシステム。
【請求項１２】
前記データベースのインデックスの置換から生じる前記最も小さなデータベースの不明瞭化インデックスを求める手段と、
全ての雑音値の加法的持分から、前記不明瞭化インデックスに基づいて、前記最も小さなデータベースに関連付けられた雑音値の第１の加法的持分をオブリビアスに選択する手段であって、第２の加法的持分が１つ又は複数のデータベース内に格納されるものと、
各前記分類器、前記雑音値の前記第１の加法的持分及び前記第２の加法的持分をオブリビアスに組み合わせることによって前記差分プライバシー集合分類器を求める手段とをさらに備える、請求項１０に記載のシステム。
【請求項１３】
前記雑音値はラプラス分布に従って分布する、請求項１０に記載のシステム。
【請求項１４】
前記データベース毎の前記雑音値は前記データベースのサイズに基づいて求められる、請求項１０に記載のシステム。
【請求項１５】
１組のデータベースのための差分プライバシー集合分類器を格納するコンピューター読み取り可能な記憶媒体であって、該１組のデータベース内の各データベースは分類器及び雑音値に関連付けられ、該分類器及び該雑音値は、該分類器及び該雑音値の組み合わせが前記データベースの差分データプライバシーを保証するように、前記データベース毎にローカルに求められ、前記差分プライバシー集合分類器は、前記１組のデータベース内の最も小さなデータベースに対応する雑音値を用いて変更された、該１組のデータベースの前記分類器の組み合わせである、コンピューター読み取り可能な記憶媒体。
【図１】
【図２Ａ】
【図２Ｂ】
【図２Ｃ】
【図３】
【図２Ａ】
【図２Ｂ】
【図２Ｃ】
【図３】
【公開番号】特開２０１２−１３３３２０（Ｐ２０１２−１３３３２０Ａ）
【公開日】平成２４年７月１２日（２０１２．７．１２）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１１−２１９２５２（Ｐ２０１１−２１９２５２）
【出願日】平成２３年１０月３日（２０１１．１０．３）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
【公開日】平成２４年７月１２日（２０１２．７．１２）
【国際特許分類】
【出願番号】特願２０１１−２１９２５２（Ｐ２０１１−２１９２５２）
【出願日】平成２３年１０月３日（２０１１．１０．３）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
[ Back to top ]