(57)【要約】本実施形態は、いくつかの効用を得ることを期待して、彼のプライベートデータと相関関係がある、いくつかのパブリックデータを分析者に公開することを願うユーザによって直面されるプライバシー効用トレードオフに焦点を当てる。多数のデータが１又は複数の分析者に公開されるとき、我々は分散化された様式でプライバシー保護写像を設計する。特に、各プライバシー保護写像は、公開されるデータのそれぞれからの推論に対して別個に保護するように設計される。分散化は、多くの変数を有する１つの大きな最適化問題を、より少ない変数を有するいくつかのより小さい最適化に分解することによって、設計を単純にする。
2016535898.tif 000002
【特許請求の範囲】
【請求項１】
ユーザに関するユーザデータを処理するための方法であって、
プライベートデータ、第１のパブリックデータ、および第２のパブリックデータを含む前記ユーザデータにアクセスするステップであって、前記第１のパブリックデータは、第１のカテゴリのデータに対応し、前記第２のパブリックデータは、第２のカテゴリのデータに対応する、前記ステップと、
前記プライベートデータと第１の公開されるデータおよび第２の公開されるデータとの間の第１の情報漏出境界を決定するステップ（２２０、３２０）と、
前記第１の境界に応じて、前記プライベートデータと前記第１の公開されるデータとの間の第２の情報漏出境界、および前記プライベートデータと前記第２の公開されるデータとの間の第３の情報漏出境界を決定するステップと、
前記第２の境界に応じて前記第１の公開されるデータに前記第１のカテゴリのデータを写像する第１のプライバシー保護写像、および前記第３の境界に応じて前記第２の公開されるデータに前記第２のカテゴリのデータを写像する第２のプライバシー保護写像を決定するステップ（２３０、２３５、３３０、３３５）と、
前記第１および第２の公開されるデータを形成するために、それぞれ、前記第１および第２のプライバシー保護写像に基づいて、前記ユーザに関する前記第１および第２のパブリックデータを修正するステップ（２４０、２４５、３４０、３４５）と、
前記修正された第１および第２のパブリックデータを、サービスプロバイダとデータ収集エージェンシとの少なくとも一方へ公開するステップ（２５０、２５５、３５０、３５５）と、
を含む、前記方法。
【請求項２】
前記第２の境界及び前記第３の境界の組み合わせは、前記第１の境界に実質的に対応する、請求項１に記載の方法。
【請求項３】
前記第２の境界及び前記第３の境界の各々は、前記第１の境界と実質的に等しい、請求項１に記載の方法。
【請求項４】
前記公開するステップは、前記修正された第１のパブリックデータを第１の受信者に公開し、前記修正された第２のパブリックデータを第２の受信者に公開し、前記第１および第２の受信者は、前記修正された第１および第２のパブリックデータについての情報を交換するように構成される、請求項１に記載の方法。
【請求項５】
前記公開するステップは、前記修正された第１および第２のパブリックデータを同一の受信者に公開する、請求項１に記載の方法。
【請求項６】
結託又は合成がサービスプロバイダとデータ収集エージェンシとの少なくとも一方に生じたかを決定するステップをさらに含む、請求項１に記載の方法。
【請求項７】
前記第１および第２のプライバシー保護写像を決定するステップは、最大相関技術に基づく、請求項１に記載の方法。
【請求項８】
前記プライベートデータは、第１のプライベートデータおよび第２のプライベートデータを含み、前記第２の情報漏出境界を決定するステップは、前記第１のプライベートデータと前記第１のパブリックデータとの間の前記第２の境界、および前記第２のプライベートデータと前記第２のパブリックデータとの間の前記第３の境界を決定する、請求項１に記載の方法。
【請求項９】
ユーザに関するユーザデータを処理するための装置であって、
プライベートデータ、第１のパブリックデータ、および第２のパブリックデータを含む前記ユーザデータにアクセスするように構成されたプロセッサであって、前記第１のパブリックデータは、第１のカテゴリのデータに対応し、前記第２のパブリックデータは、第２のカテゴリのデータに対応する、前記プロセッサと、
前記プライベートデータと第１の公開されるデータおよび第２の公開されるデータとの間の第１の情報漏出境界を決定し、
前記第１の境界に応じて、前記プライベートデータと前記第１の公開されるデータとの間の第２の情報漏出境界、および前記プライベートデータと前記第２の公開されるデータとの間の第３の情報漏出境界を決定し、
前記第２の境界に応じて前記第１の公開されるデータに前記第１のカテゴリのデータを写像する第１のプライバシー保護写像、および前記第３の境界に応じて前記第２の公開されるデータに前記第２のカテゴリのデータを写像する第２のプライバシー保護写像を決定する
ように構成されたプライバシー保護写像判断モジュール（４３０）と、
前記第１および第２の公開されるデータを形成するために、それぞれ、前記第１および第２のプライバシー保護写像に基づいて、前記ユーザに関する前記第１および第２のパブリックデータを修正し、
前記修正された第１および第２のパブリックデータを、サービスプロバイダとデータ収集エージェンシとの少なくとも一方へ公開する
ように構成されたプライバシー保護モジュール（４４０）と、
を含む、前記装置。
【請求項１０】
前記第２の境界及び前記第３の境界の組み合わせは、前記第１の境界に実質的に対応する、請求項９に記載の装置。
【請求項１１】
前記第２の境界及び前記第３の境界の各々は、前記第１の境界と実質的に等しい、請求項９に記載の装置。
【請求項１２】
前記プライバシー保護モジュール（４４０）は、前記修正された第１のパブリックデータを第１の受信者に公開し、前記修正された第２のパブリックデータを第２の受信者に公開し、前記第１および第２の受信者は、前記修正された第１および第２のパブリックデータについての情報を交換するように構成される、請求項９に記載の装置。
【請求項１３】
前記プライバシー保護モジュール（４４０）は、前記修正された第１および第２の公開されるデータを同一の受信者に公開する、請求項９に記載の装置。
【請求項１４】
前記プライバシー保護写像判断モジュール（４３０）は、結託又は合成がサービスプロバイダとデータ収集エージェンシとの少なくとも一方に生じたかを決定するようにさらに構成される、請求項９に記載の装置。
【請求項１５】
前記プライバシー保護写像判断モジュール（４３０）は、最大相関技術に基づく前記第１および第２のプライバシー保護写像を決定する、請求項９に記載の装置。
【請求項１６】
前記プライベートデータは、第１のプライベートデータおよび第２のプライベートデータを含み、前記プライバシー保護写像判断モジュール（４３０）は、前記第１のプライベートデータと前記第１のパブリックデータとの間の前記第２の情報漏出境界、および前記第２のプライベートデータと前記第２のパブリックデータとの間の前記第３の情報漏出境界を決定する、請求項９に記載の装置。
【請求項１７】
請求項１から８のいずれかに記載の方法による、ユーザに関するユーザデータを処理するための命令を格納したコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プライバシーを保護するための方法および装置に関し、より詳細には、結託（collusion）または合成を考慮したユーザデータのプライバシーを保護するための方法および装置に関する。
【背景技術】
【０００２】
関連出願の相互参照
本出願は、あらゆる目的で参照によりその全体が本明細書に組み込まれる、２０１３年８月１９日に出願された米国特許仮出願第６１／８６７，５４４号明細書、名称「Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｕｔｉｌｉｔｙ−Ａｗａｒｅ  Ｐｒｉｖａｃｙ  Ｐｒｅｓｅｒｖｉｎｇ  Ｍａｐｐｉｎｇ  ｉｎ  Ｖｉｅｗ  ｏｆ  Ｃｏｌｌｕｓｉｏｎ  ａｎｄ  Ｃｏｍｐｏｓｉｔｉｏｎ」の出願日の利益を主張する。
【０００３】
本出願は、２０１２年８月２０日に出願された米国特許仮出願第６１／６９１，０９０号明細書、名称「Ａ  Ｆｒａｍｅｗｏｒｋ  ｆｏｒ  Ｐｒｉｖａｃｙ  ａｇａｉｎｓｔ  Ｓｔａｔｉｓｔｉｃａｌ  Ｉｎｆｅｒｅｎｃｅ」（以下、「Ｆａｗａｚ」）に関連付けられる。この仮出願は、明示的に参照によりその全体が本明細書に組み込まれる。
【０００４】
加えて、本出願は、以下の出願、（１）代理人整理番号第ＰＵ１３０１２０号、名称「Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｕｔｉｌｉｔｙ−Ａｗａｒｅ  Ｐｒｉｖａｃｙ  Ｐｒｅｓｅｒｖｉｎｇ  Ｍａｐｐｉｎｇ  ａｇａｉｎｓｔ  Ｉｎｆｅｒｅｎｃｅ  Ａｔｔａｃｋｓ」、および（２）代理人整理番号第ＰＵ１３０１２２号、名称「Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｕｔｉｌｉｔｙ−Ａｗａｒｅ  Ｐｒｉｖａｃｙ  Ｐｒｅｓｅｒｖｉｎｇ  Ｍａｐｐｉｎｇ  ｔｈｒｏｕｇｈ  Ａｄｄｉｔｉｖｅ  Ｎｏｉｓｅ」に関連付けられ、これらは、同一譲受人に譲渡され、それら全体が参照により組み込まれ、本明細書と共に出願される。
【０００５】
ビッグデータの時代において、ユーザデータの収集およびマイニングは、多数の民間および公共機関により、急速に成長している一般的行為となっている。たとえば、技術会社は、ユーザデータを利用してそれらの顧客に個別化されたサービスを提供し、政府機関は、データに依拠して、様々な課題、たとえば、国家安全保障、国民健康、予算および基金配分に取り組み、または医療機関は、データを分析して病気の発端および潜在的治療法を発見する。場合によっては、ユーザのデータの収集、分析または第三者との共有は、ユーザの同意または認識なしに行われる。他の場合、データは、見返りにサービスを得るために、ユーザによって特定の分析者に自発的に公開され、たとえば、推奨を得るために製品評価が公開される。ユーザのデータにアクセスすることを許可することからユーザが得るこのサービスまたは他の利益は、効用（utility）と呼ばれることがある。いずれの場合も、プライバシーリスクが生じ、その理由は、収集されたデータの一部は、センシティブ（sensitive）であるとユーザがみなすことがある（たとえば、政治的意見、健康状態、所得レベル）、または、一見無害に見えることがある（たとえば、製品評価）が、それが相関付けられたよりセンシティブなデータの推定につながるからである。後者の脅威は、推論攻撃、すなわち、プライベートデータを、それの公然と公開されるデータ（released data）との相関を利用することによって推論する技法を指す。
【発明の概要】
【０００６】
本原理は、ユーザに関するユーザデータを処理するための方法であって、プライベートデータ、第１のパブリックデータ、および第２のパブリックデータを含む上記ユーザデータにアクセスするステップであって、上記第１のパブリックデータは、第１のカテゴリのデータに対応し、上記第２のパブリックデータは、第２のカテゴリのデータに対応する、ステップと、上記プライベートデータと第１の公開されるデータおよび第２の公開されるデータとの間の第１の情報漏出境界を決定するステップと、上記第１の情報漏出境界に応じて、上記プライベートデータと上記第１の公開されるデータとの間の第２の情報漏出境界、および上記プライベートデータと上記第２の公開されるデータとの間の第３の情報漏出境界を決定するステップと、上記第２の境界に応じて上記第１の公開されるデータに上記第１のカテゴリのデータを写像する第１のプライバシー保護写像、および上記第３の境界に応じて上記第２の公開されるデータに上記第２のカテゴリのデータを写像する第２のプライバシー保護写像を決定するステップと、上記第１の公開されるデータおよび上記第２の公開されるデータを形成するために、それぞれ、上記第１のプライバシー保護写像および上記第２のプライバシー保護写像に基づいて、上記ユーザに関する上記第１のパブリックデータおよび上記第２のパブリックデータを修正するステップと、後述されるように、上記修正された第１のパブリックデータおよび第２のパブリックデータを、サービスプロバイダとデータ収集エージェンシとの少なくとも一方へ公開するステップと、を含む、上記方法を提供する。本原理はまた、これらのステップを実施するための装置を提供する。
【０００７】
本原理はまた、ユーザに関するユーザデータを処理するための方法であって、プライベートデータ、第１のパブリックデータ、および第２のパブリックデータを含む上記ユーザデータにアクセスするステップであって、上記第１のパブリックデータは、第１のカテゴリのデータに対応し、上記第２のパブリックデータは、第２のカテゴリのデータに対応する、ステップと、上記プライベートデータと第１の公開されるデータおよび第２の公開されるデータとの間の第１の情報漏出境界を決定するステップと、上記第１の情報漏出境界に応じて、上記プライベートデータと上記第１の公開されるデータとの間の第２の情報漏出境界、および上記プライベートデータと上記第２の公開されるデータとの間の第３の情報漏出境界を決定するステップであって、上記第２の境界および上記第３の境界のそれぞれは、上記第１の境界と実質的に等しい、ステップと、上記第２の境界に応じて上記第１の公開されるデータに上記第１のカテゴリのデータを写像する第１のプライバシー保護写像、および上記第３の境界に応じて上記第２の公開されるデータに上記第２のカテゴリのデータを写像する第２のプライバシー保護写像を決定するステップと、上記第１の公開されるデータおよび上記第２の公開されるデータを形成するために、それぞれ、上記第１のプライバシー保護写像および上記第２のプライバシー保護写像に基づいて、上記ユーザに関する上記第１のパブリックデータおよび上記第２のパブリックデータを修正するステップと、後述されるように、上記修正された第１のパブリックデータおよび第２のパブリックデータを、サービスプロバイダとデータ収集エージェンシとの少なくとも一方へ公開するステップと、を含む、上記方法を提供する。本原理はまた、これらのステップを実行するための装置を提供する。
【０００８】
本原理はまた、上述された上記方法による、ユーザに関するユーザデータを処理するための命令を格納したコンピュータ可読記憶媒体を提供する。
【図面の簡単な説明】
【０００９】
【図１】結託および合成を示す図例である。
【図２】本原理の実施形態による、プライバシーを保護するための例示的方法を示すフロー図である。
【図３】本原理の実施形態による、プライバシーを保護するための別の例示的方法を示すフロー図である。
【図４】本原理の実施形態による、例示的プライバシーエージェントを示すブロック図である。
【図５】本原理の実施形態による、複数のプライバシーエージェントを有する例示的システムを示すブロック図である。
【発明を実施するための形態】
【００１０】
差分プライバシーが生じるデータベースおよび暗号文において、焦点はアルゴリズムに関するものとなっている。特に、研究者は、推論アルゴリズム、転送、およびデータ問合わせのためのプライバシー保護機構を設計するために差分プライバシーを使用している。より最近の研究は、統計的推論と差分プライバシーとの関係に焦点を当てている。差分プライバシーは情報漏出の制限を保証しないことが示されている。差分プライバシーに類似する他のフレームワーク、たとえば、Pufferfishフレームワーク（たとえば、Ｄ．Ｋｉｆｅｒ  ａｎｄ  Ａ．Ｍａｃｈａｎａｖａｊｊｈａｌａによる記事、”Ａ  ｒｉｇｏｒｏｕｓ  ａｎｄ  ｃｕｓｔｏｍｉｚａｂｌｅ  ｆｒａｍｅｗｏｒｋ  ｆｏｒ  ｐｒｉｖａｃｙ，”  ｉｎ  ＡＣＭ  ＰＯＤＳ，２０１２を参照）が存在するが、これは効用保護に焦点を当てていない。
【００１１】
多くのアプローチは、情報理論的技法に依拠して、プライバシー精度トレードオフをモデリングおよび分析する。これらの情報理論的モデルのほとんどは、主にデータベースのエントリの全部または一部についての集団的プライバシーに焦点を当てており、出力公開後のデータベースエントリごとの平均残余不確実性または入力変数ごとの曖昧度に対する漸近的保証を提供する。対照的に、本出願で検討されるフレームワークは、公開された出力を観測することによって分析者が達成する情報漏出に対する境界の観点でプライバシーを提供する。
【００１２】
我々は、Ｆａｗａｚに説明された設定を検討し、この設定では、ユーザが、相関付けられた２種類のデータを有し、すなわち、ユーザがプライベートのままにしたい一部のデータと、ユーザが分析者に積極的に公開し、そこからユーザがある種の効用を得られ得る、たとえば、メディア選好をサービスプロバイダに公開して、より精密なコンテンツ推奨を受け取る、一部の非プライベートデータとを有する。
【００１３】
本出願で使用されるとき、分析者という用語は、たとえば、サービスプロバイダのシステムの一部であってよく、ユーザへの効用を提供するためにデータを表向き使用する、公開されるデータの受信者を指す。多くの場合、分析者は、公開されるデータの正当な受信者である。しかしながら、分析者が、公開されるデータを不法に利用し、ユーザのプライベートデータに関するある種の情報を推論する可能性もあり得る。これは、プライバシーと効用の必要条件の間の緊張をもたらす。効用を保持しながら推論脅威を低減するために、ユーザは、効用制約下で設計された「プライバシー保護写像（privacy preserving mapping）」と呼ばれる条件付き確率的写像によって生成されたデータの「歪められたバージョン」を公開することができる。
【００１４】
本出願において、我々は、ユーザがプライベートのままにしたいデータを「プライベートデータ」と呼び、ユーザが積極的に公開しようとするデータを「パブリックデータ」と呼び、ユーザが実際に公開するデータを「公開されるデータ（released data）」と呼ぶ。たとえば、ユーザは、ユーザの政治的意見をプライベートに維持したいことがあり、修正を伴うユーザのＴＶ評価を積極的に公開する（たとえば、番組に関するユーザの実際の評価は４であるが、ユーザは評価を３として公開する）。この場合、ユーザの政治的意見はこのユーザのプライベートデータとみなされ、ＴＶ評価はパブリックデータとみなされ、公開された修正されたＴＶ評価は公開されるデータとみなされる。別のユーザが政治的意見とＴＶ評価の両方を修正なしに積極的に公開しようとすることもあり、したがって、この他のユーザの場合、政治的意見とＴＶ評価のみが考慮されるとき、プライベートデータ、パブリックデータ、および公開されるデータの間の区別がないことに留意されたい。多くの人々が政治的意見およびＴＶ評価を公開する場合、分析者は、政治的意見とＴＶ評価との間の相関を得ることができ、したがって、それをプライベートに維持したいユーザの政治的意見を推論できることがある。
【００１５】
プライベートデータに関して、これは、公然と公開されるべきでないことをユーザが示すのみならず、ユーザが公開することになる他のデータから推論されたくもないデータを指す。パブリックデータは、場合によってはプライベートデータの推論を防止するために歪められた方法で、プライバシーエージェントが公開することをユーザが許可するデータである。
【００１６】
一実施形態では、パブリックデータは、ユーザにサービスを提供するためにサービスプロバイダがユーザに要求するデータである。しかしながら、ユーザは、それをサービスプロバイダに公開する前に、それを歪める（すなわち修正する）。別の実施形態では、パブリックデータは、公開がプライベートデータの推論を防止する形態をとる限りはユーザがそれを公開するのを気にしないという意味で「パブリック」であるとユーザが示すデータである。
【００１７】
上述されたように、特定のカテゴリのデータがプライベートデータとみなされるかそれともパブリックデータとみなされるかは、特定のユーザの視点に基づく。表記を簡単にするために、我々は、特定のカテゴリのデータを、現在のユーザの視点から、プライベートデータまたはパブリックデータと呼ぶ。たとえば、自身の政治的意見をプライベートに維持したい現在のユーザに関するプライバシー保護写像を設計しようとするとき、我々は、現在のユーザと、自身の政治的意見を積極的に公開しようとする別のユーザとの両方に関して、政治的意見をプライベートデータと呼ぶ。
【００１８】
本原理では、我々は、公開されるデータとパブリックデータとの間の歪みを、効用の測度として使用する。歪みがより大きいとき、公開されるデータは、よりいっそうパブリックデータとは異なり、よりプライバシーが保護されるが、歪められたデータから得られる効用は、ユーザにとって、より小さくなり得る。他方で、歪みがより小さいとき、公開されるデータは、パブリックデータのより精密な表現となり、ユーザは、より大きい効用、たとえば、より精密なコンテンツ推奨を受け取る可能性がある。
【００１９】
一実施形態では、統計的推論に対してプライバシーを保護するために、我々は、歪み制約を受けるプライベートデータと公開されるデータとの間の相互情報量として定義される情報漏出を最小化する最適化問題を解くことにより、プライバシー効用トレードオフをモデリングし、プライバシー保護写像を設計する。
【００２０】
Ｆａｗａｚでは、プライバシー保護写像を求めることは、プライベートデータと公開されるデータとをリンクする事前同時分布（prior joint distribution）が知られていて最適化問題に対する入力として提供され得るという基本的仮定に依拠する。実際には、真の事前分布は知られていなくてよく、いくつかの事前統計値が、観測され得るサンプルデータのセットから推定されてよい。たとえば、事前同時分布は、プライバシーの懸念を持たず、異なるカテゴリのデータを公然と公開するユーザのセットから推定されてよく、それらのデータは、彼らのプライバシーを懸念するユーザによってプライベートデータまたはパブリックデータとみなされ得る。あるいは、プライベートデータが観測できないとき、公開されるべきパブリックデータの周辺分布、または単純にその２次統計値が、彼らのパブリックデータのみを公開するユーザのセットから推定され得る。このサンプルのセットに基づいて推定された統計値は、次いで、彼らのプライバシーを懸念する新しいユーザに適用されるプライバシー保護写像機構を設計するために使用される。実際には、たとえば、観測可能サンプルが少数のため、または観測可能データの不完全性のため、推定された事前統計値と真の事前統計値との間の不一致が存在することもある。
【００２１】
問題を定式化するために、パブリックデータは、確率分布Ｐxを有する確率変数
【００２２】
【数１】
2016535898.tif 000003
【００２３】
によって示される。Ｘは、確率変数
【００２４】
【数２】
2016535898.tif 000004
【００２５】
によって示されるプライベートデータと相関付けられる。ＳとＸの相関は、同時分布ＰS,Xによって定義される。確率変数
【００２６】
【数３】
2016535898.tif 000005
【００２７】
によって示される公開されるデータは、Ｘの歪められたバージョンである。Ｙは、ＸをカーネルＰY|Xに通すことによって実現される。本出願では、用語「カーネル」は、データＸをデータＹに確率的に写像する条件付き確率を指す。すなわち、カーネルＰY|Xは、我々が設計するのを望むプライバシー保護写像である。Ｙは、Ｘのみの確率的関数であるので、本出願では、我々は、Ｓ→Ｘ→Ｙがマルコフ連鎖を形成すると仮定する。したがって、ＰY|Xを定義すると、同時分布ＰS,X,Y＝ＰY|XＰS,X、特に同時分布ＰS,Yが得られる。
【００２８】
以下では、我々は、まずプライバシー概念を定義し、次いで精度概念を定義する。
定義１．Ｓ→Ｘ→Ｙを仮定する。カーネルＰY|Xは、同時分布ＰS,X,Y＝ＰY|XＰS,Xから得られる分布ＰS,Yが以下の式を満たす場合、ε−発散プライベートと呼ばれる。
【００２９】
【数４】
2016535898.tif 000006
【００３０】
上式において、Ｄ（．）はＫ−Ｌ発散であり、
【００３１】
【数５】
2016535898.tif 000007
【００３２】
は確率変数の期待値であり、Ｈ（．）はエントロピーであり、ε∈［０，１］は漏出係数と呼ばれ、相互情報量Ｉ（Ｓ；Ｙ）は情報漏出を表す。
【００３３】
我々は、ε＝０の場合に、機構が完全プライバシーを有すると言う。極値の場合、ε＝０は、公開された確率変数Ｙがプライベート確率変数Ｓから独立していることを暗示し、ε＝１は、ＳがＹから完全に復元可能である（ＳはＹの確定関数である）ことを暗示する。Ｙは、完全にＳから独立して完全プライバシーを有する（ε＝０）と仮定することができるが、これは、低い精度レベルをもたらす可能性があることに留意されたい。我々は、精度を以下のように定義する。
【００３４】
定義２．
【００３５】
【数６】
2016535898.tif 000008
【００３６】
を歪み測度とする。カーネルＰY|Xは、
【００３７】
【数７】
2016535898.tif 000009
【００３８】
であるならば、Ｄ−精度があると呼ばれる。
【００３９】
任意の歪み測定基準、たとえば、ＸおよびＹがバイナリベクトルである場合にハミング距離、ＸおよびＹが実ベクトルの場合にユークリッドノルム、または、ユーザがＸの代わりにＹの公開から得る効用の変動をモデリングするさらに複雑な測定基準が使用されてもよいことに留意されたい。後者は、たとえば、ユーザの真の選好Ｘの代わりにユーザの歪められたメディア選好Ｙの公開に基づいてユーザに推奨されるコンテンツの品質の差を表すことができる。
【００４０】
プライバシー保護写像の漏出係数εと歪みレベルＤとの間にトレードオフがある。一実施形態では、我々の目的は、効用制約が与えられたとして、推論され得るプライベート情報の量を制限することである。プライベートデータと公開されるデータとの間の情報漏出によって推論が測定され、パブリックデータと公開されるデータとの間の歪みによって効用が示されるとき、目的は、歪み制約が与えられたとして、最大情報漏出Ｉ（Ｓ；Ｙ）を最小化する確率写像ＰY|Xを求めるように数学的に定式化することができ、最大値は、以下のようにプライバシーエージェントで入手可能な分布ＰS,Xの統計的知識の不確実性において得られる：
【００４１】
【数８】
2016535898.tif 000010
【００４２】
確率分布ＰS,Yは、同時分布ＰS,X,Y＝ＰY|XＰS,X＝ＰY|XＰS|XＰXから得ることができる。
【００４３】
以下で、我々は、最大相関と呼ばれる統計的推論のいくつかの技法に基づいて、歪み制約を受けるプライバシーを達成する（すなわち情報漏出を最小化する）方式を提案する。我々は、この理論を使用して、同時確率測度ＰS,Xの完全な知識なしにプライバシー保護写像をどのように設計できるかを示す。特に、我々は、情報漏出に関する可分結果（separability result）を証明し、より詳細には、カーネルＰY|Xによって決定されるＩ（Ｓ；Ｙ）倍の最大相関係数の観点での情報漏出の上限境界（upper bound）を提供する。これは、同時確率測度ＰS,Xの完全な知識なしに最適写像を定式化することを可能にする。
【００４４】
次に、我々は、分離結果（decoupling result）を記述する際に使用される定義を提供する。
【００４５】
定義３．所与の同時分布ＰX,Yについて、
【００４６】
【数９】
2016535898.tif 000011
【００４７】
として、式中、ｒ（ｙ）は、Ｙに対するｐ（ｙ｜ｘ）ｒ（ｘ）の限界測度である。
【００４８】
発散に関するデータ処理不等式により、Ｓ*（Ｘ；Ｙ）≦１であることに留意されたい。以下は、Ｖ．Ａｎａｎｔｈａｒａｍ，Ａ．Ｇｏｈａｒｉ，Ｓ．Ｋａｍａｔｈ，ａｎｄ  Ｃ．Ｎａｉｒによる記事、”Ｏｎ  ｍａｘｉｍａｌ  ｃｏｒｒｅｌａｔｉｏｎ，ｈｙｐｅｒｃｏｎｔｒａｃｔｉｖｉｔｙ，ａｎｄ  ｔｈｅ  ｄａｔａ  ｐｒｏｃｅｓｓｉｎｇ  ｉｎｅｑｕａｌｉｔｙ  ｓｔｕｄｉｅｄ  ｂｙ  Ｅｒｋｉｐ  ａｎｄ  Ｃｏｖｅｒ，”  ａｒＸｉｖ  ｐｒｅｐｒｉｎｔ  ａｒＸｉｖ：１３０４．６１３３，２０１３（以下、「Ａｎａｎｔｈａｒａｍ」）による結果である。
【００４９】
定理１．Ｓ→Ｘ→Ｙがマルコフ連鎖を形成する場合、以下の境界が成立し：
Ｉ（Ｓ；Ｙ）≦Ｓ*（Ｘ；Ｙ）Ｉ（Ｓ；Ｘ）      （６）
境界は、Ｓを変化させるときにタイト（tight）である。換言すると、Ｉ（Ｓ；Ｘ）≠０を仮定して、
【００５０】
【数１０】
2016535898.tif 000012
【００５１】
が得られる。
【００５２】
定理１は、ＹおよびＳの依存関係を２つの項に分離し、１つはＳおよびＸを関係付け、１つはＸおよびＹを関係付ける。したがって、ＸおよびＹを関係付ける項を最小化することによって、ＰS,Xを知らなくても、情報漏出に上限境界を付けることができる。我々の問題におけるこの結果の適用は、以下のようになる。
【００５３】
我々が、ＰS,Xが既知でなく、あるΔ∈［０，Ｈ（Ｓ）］についてＩ（Ｓ；Ｘ）≦Δである状況にあると仮定する。Ｉ（Ｓ；Ｘ）は、我々が制御を有しないＳに関するＸに埋め込まれた固有情報である。Δの値は、我々が求める写像に影響しないが、Δの値は、この写像からもたらされる（漏出係数の観点で）プライバシー保証であると我々が考えるものに影響する。Δ境界がタイトである場合、プライバシー保証がタイトとなる。Δ境界がタイトでない場合、我々は、目的の漏出係数に実際に必要であるよりも大きい歪みを受けることがあるが、これは、プライバシー保証に影響しない。
【００５４】
定理１を使用すると、
【００５５】
【数１１】
2016535898.tif 000013
【００５６】
が得られる。
【００５７】
したがって、最適化問題は、以下の目的関数を最小化するＰY|Xを求めることとなる：
【００５８】
【数１２】
2016535898.tif 000014
【００５９】
この最適化問題をより詳細に検討するために、我々は、最大相関文献のいくつかの結果を吟味する。最大相関（またはＲｅｎｙｉ相関）は、情報理論とコンピュータサイエンスの両方で用途を有する２つの確率変数の間の相関の測度である。以下では、我々は、最大相関を定義し、そのＳ*（Ｘ；Ｙ）との関係を提供する。
【００６０】
定義４．２つの確率変数ＸおよびＹが与えられたとして、（Ｘ，Ｙ）の最大相関は、
【００６１】
【数１３】
2016535898.tif 000015
【００６２】
となり、式中、τは、
【００６３】
【数１４】
2016535898.tif 000016
【００６４】
かつ
【００６５】
【数１５】
2016535898.tif 000017
【００６６】
となるような、実数値の確率変数ｆ（ｘ）およびｇ（ｙ）の対の集合である。
【００６７】
この測度は、最初にＨｉｒｓｃｈｆｅｌｄ（Ｈ．Ｏ．Ｈｉｒｓｃｈｆｅｌｄ，”Ａ  ｃｏｎｎｅｃｔｉｏｎ  ｂｅｔｗｅｅｎ  ｃｏｒｒｅｌａｔｉｏｎ  ａｎｄ  ｃｏｎｔｉｎｇｅｎｃｙ，”  ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｃａｍｂｒｉｄｇｅ  Ｐｈｉｌｏｓｏｐｈｉｃａｌ  Ｓｏｃｉｅｔｙ，ｖｏｌ．３１）およびＧｅｂｅｌｅｉｎ（Ｈ．Ｇｅｂｅｌｅｉｎ，”Ｄａｓ  ｓｔａｔｉｓｔｉｓｃｈｅ  Ｐｒｏｂｌｅｍ  ｄｅｒ  Ｋｏｒｒｅｌａｔｉｏｎ  ａｌｓ  Ｖａｒｉａｔｉｏｎｓ−  ｕｎｄ  Ｅｉｇｅｎｗｅｒｔ−ｐｒｏｂｌｅｍ  ｕｎｄ  ｓｅｉｎ  Ｚｕｓａｍｍｅｎｈａｎｇ  ｍｉｔ  ｄｅｒ  Ａｕｓｇｌｅｉｃｈｕｎｇｓｒｅｃｈｎｕｎｇ，”  Ｚｅｉｔｓｃｈｒｉｆｔ  ｆｕｒ  ａｎｇｅｗ．Ｍａｔｈ．ｕｎｄ  Ｍｅｃｈ．２１，ｐｐ．３６４−３７９  （１９４１））によって導入され、次いで、Ｒｅｎｙｉ（Ａ．Ｒｅｎｙｉ，”Ｏｎ  ｍｅａｓｕｒｅｓ  ｏｆ  ｄｅｐｅｎｄｅｎｃｅ，”  Ａｃｔａ  Ｍａｔｈｅｍａｔｉｃａ  Ｈｕｎｇａｒｉｃａ，ｖｏｌ．１０，Ｎｏ．３）によって研究された。最近、ＡｎａｎｔｈａｒａｍらおよびＫａｍａｔｈら（Ｓ．Ｋａｍａｔｈ  ａｎｄ  Ｖ．Ａｎａｎｔｈａｒａｍ，”Ｎｏｎ−ｉｎｔｅｒａｃｔｉｖｅ  ｓｉｍｕｌａｔｉｏｎ  ｏｆ  ｊｏｉｎｔ  ｄｉｓｔｒｉｂｕｔｉｏｎｓ：Ｔｈｅ  ｈｉｒｓｃｈｆｅｌｄ−ｇｅｂｅｌｅｉｎ−ｒｅｎｙｉ  ｍａｘｉｍａｌ  ｃｏｒｒｅｌａｔｉｏｎ  ａｎｄ  ｔｈｅ  ｈｙｐｅｒｃｏｎｔｒａｃｔｉｖｉｔｙ  ｒｉｂｂｏｎ，”  ｉｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ，Ｃｏｎｔｒｏｌ，ａｎｄ  Ｃｏｍｐｕｔｉｎｇ  （Ａｌｌｅｒｔｏｎ），２０１２  ５０ｔｈ  Ａｎｎｕａｌ  Ａｌｌｅｒｔｏｎ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ（以下、「Ｋａｍａｔｈ」））が、最大相関を研究し、この量の幾何学的解釈を提供した。以下は、Ｒ．Ａｈｌｓｗｅｄｅ  ａｎｄ  Ｐ．Ｇａｃｓによる記事、”Ｓｐｒｅａｄｉｎｇ  ｏｆ  ｓｅｔｓ  ｉｎ  ｐｒｏｄｕｃｔ  ｓｐａｃｅｓ  ａｎｄ  ｈｙｐｅｒｃｏｎｔｒａｃｔｉｏｎ  ｏｆ  ｔｈｅ  ｍａｒｋｏｖ  ｏｐｅｒａｔｏｒ，”  Ｔｈｅ  Ａｎｎａｌｓ  ｏｆ  Ｐｒｏｂａｂｉｌｉｔｙ（以下、Ａｈｌｓｗｅｄｅ）の結果である：
【００６８】
【数１６】
2016535898.tif 000018
【００６９】
（８）に（１０）を代入すると、プライバシー保護写像は、
【００７０】
【数１７】
2016535898.tif 000019
【００７１】
の解である。
【００７２】
エントリ
【００７３】
【数１８】
2016535898.tif 000020
【００７４】
を有するマトリックスＱの２番目に大きい特異値によって最大相関ρm（Ｘ；Ｙ）が特徴付けられることが、Ｈ．Ｓ．Ｗｉｔｓｅｎｈａｕｓｅｎの記事、”Ｏｎ  ｓｅｑｕｅｎｃｅｓ  ｏｆ  ｐａｉｒｓ  ｏｆ  ｄｅｐｅｎｄｅｎｔ  ｒａｎｄｏｍ  ｖａｒｉａｂｌｅｓ，”  ＳＩＡＭ  Ｊｏｕｒｎａｌ  ｏｎ  Ａｐｐｌｉｅｄ  Ｍａｔｈｅｍａｔｉｃｓ，ｖｏｌ．２８，ｎｏ．１に示されている。最適化問題は、マトリックスの特異値を求めるためのべき乗法アルゴリズムまたはランチョスアルゴリズムによって解くことができる。
【００７５】
上記では、我々は、定理１における可分結果を使用してプライバシー保護写像がどのように設計され得るかを論じている。上記に論じられた方法は、１または複数の分析者に対する複数のデータの公開が行われるときに生じるプライバシー保護写像機構の設計における新しい課題に対処するために使用され得る技法のうちのいくつかである。本出願では、我々は、結託または合成を考慮したプライバシー写像機構を提供する。
【００７６】
以下では、我々は、結託および合成に照らして課題を定義する。
【００７７】
結託：プライベートデータＳは、２つのパブリックデータＸ1およびＸ2と相関付けられる。２つのプライバシー保護写像がこれらのパブリックデータ上に適用されて、２つの公開されるデータＹ1およびＹ2がそれぞれ得られ、次いで、それらは２つの分析者に公開される。我々は、分析者がＹ1およびＹ2を共有するとき、Ｓにおける累積的プライバシー保証を分析することを望む。本出願では、我々は、Ｙ1およびＹ2を共有する分析者を結託エンティティとも呼ぶ。
【００７８】
我々は、２つのプライバシー保護写像が分散化された様式で設計される場合に焦点を当てる。すなわち、各プライバシー保護写像は、公開されるデータのそれぞれからのＳの推論に対して別個に保護するように設計される。分散化は、多くの変数を有する１つの大きな最適化（結合設計）を、より少ない変数を有するいくつかのより小さい最適化に分解することによって、設計を単純にする。
【００７９】
合成：プライベートデータＳは、同時確率分布Ｐ（Ｓ；Ｘ1；Ｘ2）を介してパブリックデータＸ1およびＸ2と相関付けられる。我々は、別個に２つのプライバシー保護写像を設計することができ、一方の写像はＸ1をＹ1に変換し、他方の写像はＸ2をＹ2に変換することを仮定する。分析者は、対（Ｘ1，Ｘ2）を要求する。我々は、これら２つの別個のプライバシー写像を再使用して、やはりあるレベルのプライバシーを保証する、対（Ｘ1，Ｘ2）に対するプライバシー保護写像を生成することを望む。
【００８０】
図１は、以下の結託および合成の例を提供する。
−例１：単一のプライベートデータおよび複数のパブリックデータが考慮されるときの結託
−例２：複数のプライベートデータおよび複数のパブリックデータが考慮されるときの結託
−例３：単一のプライベートデータおよび複数のパブリックデータが考慮されるときの合成
−例４：複数のプライベートデータおよび複数のパブリックデータが考慮されるときの合成
【００８１】
例１では、プライベートデータＳが、２つのパブリックデータＸ1およびＸ2と相関付けられる。この例では、我々は、政治的意見をプライベートデータＳ、ＴＶ評価をパブリックデータＸ1、スナック評価をパブリックデータＸ2とみなす。２つのプライバシー保護写像がこれらのパブリックデータ上に適用されて、２つのエンティティに提供される２つの公開されるデータＹ1およびＹ2がそれぞれ得られる。たとえば、歪められたＴＶ評価（Ｙ1）がネットフリックス（Netflix）に提供され、歪められたスナック評価（Ｙ2）がクラフトフーズ（Kraft Foods）に提供される。プライバシー保護写像は、分散化された様式で設計される。プライバシー保護写像方式のそれぞれは、Ｓを対応する分析者から保護するように設計される。ネットフリックスが情報（Ｙ1）をクラフト（Ｙ2）と交換する場合、ユーザのプライベートデータ（Ｓ）は、それらがＹ1またはＹ2のみに依存する場合よりも精度良く回復され得る。我々は、分析者がＹ1およびＹ2を共有するときにプライバシー保証を分析することを望む。この例では、ネットフリックスは、ＴＶ評価に関する情報の正当な受信者であるが、スナック評価についてはそうでなく、クラフトフーズは、スナック評価に関する情報の正当な受信者であるが、ＴＶ評価についてはそうでない。しかしながら、それらは、ユーザのプライベートデータに関してより多く推論するために情報を共有し得る。
【００８２】
例２では、プライベートデータＳ1がパブリックデータＸ1と相関付けられ、プライベートデータＳ2がパブリックデータＸ2と相関付けられる。この例では、我々は、所得をプライベートデータＳ1、性別をプライベートデータＳ2、ＴＶ評価をパブリックデータＸ1、スナック評価をパブリックデータＸ2とみなす。２つのプライバシー保護写像がこれらのパブリックデータ上に適用されて、２つの分析者に提供される２つの公開されるデータＹ1およびＹ2がそれぞれ得られる。
【００８３】
例３では、プライベートデータＳが、同時確率分布
【００８４】
【数１９】
2016535898.tif 000021
【００８５】
を介してパブリックデータＸ1およびＸ2と相関付けられる。この例では、我々は、政治的意見をプライベートデータＳ、Ｆｏｘニュースに関するＴＶ評価をパブリックデータＸ1、ＡＢＣニュースに関するＴＶ評価をパブリックデータＸ2とみなす。分析者、たとえば、コムキャスト（Comcast）は、Ｘ1とＸ2の両方を要求する。やはり、プライバシー保護写像が別個に設計され、我々は、プライバシーエージェントがＳ1およびＳ2両方に関するその情報Ｙ1およびＹ2を組み合わせるときにプライバシー保証を分析したい。この例では、コムキャストは、ＦｏｘニュースおよびＡＢＣニュースの両方のＴＶ評価の正当な受信者である。
【００８６】
例４では、プライベートデータＳ1およびＳ2が、同時確率分布
【００８７】
【数２０】
2016535898.tif 000022
【００８８】
を介してパブリックデータＸ1およびＸ2と相関付けられる。この例では、我々は、所得をプライベートデータＳ1、性別をプライベートデータＳ2、ＴＶ評価をパブリックデータＸ1、スナック評価をパブリックデータＸ2とみなす。
【００８９】
上述されたように、結託または合成があるときに複数の確率変数（たとえば、Ｘ1およびＸ2）が用いられる。しかしながら、プライバシー写像の解を提供する最適化問題の複雑さはベクトルのサイズＸに比例するため、大きいサイズＸ（複数の変数を有する大きいベクトル）の写像は、小さいサイズＸ（場合によっては１つの変数または小さいベクトル）の写像よりも設計するのが困難である。
【００９０】
一実施形態では、我々は、多数の変数を有する１つの大きな最適化をより少ない変数を有するいくつかのより小さい最適化に分解することによって、最適化問題の設計を単純にする。
【００９１】
結託と合成の両方の問題を以下の設定で捉えることができる。
【００９２】
プライベート確率変数ＳがＸ1およびＸ2と相関付けられると仮定する。Ｘ1およびＸ2の歪められたバージョンがそれぞれＹ1およびＹ2で示される。我々は、歪み制約が与えられたとして、２つの別個のプライバシー保護写像Ｐ（Ｙ1｜Ｘ1）およびＰ（Ｙ2｜Ｘ2）をＸ1およびＸ2に対して行ってＹ1およびＹ2をそれぞれ得る。個々の情報漏出は、Ｉ（Ｓ；Ｙ1）およびＩ（Ｓ；Ｙ2）である。結託エンティティによって、または合成を介したプライバシーエージェントによって、Ｙ1およびＹ2が対（Ｙ1，Ｙ2）として一緒に組み合わされると仮定する。
【００９３】
本原理では、我々は、複数の公開においてどのようにプライバシー保証が組み合わさるかの問題、すなわち、合成または結託を介して、複数の公開されるデータが組み合わされるときに、結果の累積的情報漏出を得る問題に対処する。プライバシー保証の組合せのルールは、プライベートデータのそれらによる推論を改善するために個々にそれらに公開されるデータを共有する結託エンティティの課題に対処するのに役立つ。組合せルールはまた、複数のデータのための結合設計を個々のデータのためのいくつかのより単純な設計問題に分解することを可能にすることによって、プライバシー保護写像機構の設計に役立つ。
【００９４】
プライバシー保護方式の組合せが、いくつかの既存の研究で研究されている。これらの研究の焦点は、結託または合成の存在下の差分プライバシーに当てられる。しかしながら、本原理は、情報理論的プライバシー測定基準のもとで結託または合成の存在下のプライバシーを考慮する。
【００９５】
以下では、我々は、まず、同じプライベートデータに公開が関係付けられた場合（たとえば、例１および例３）を論じ、次に、異なるが相関付けられたプライベートデータに公開が関係付けられた場合（たとえば、例２および例４）に分析を拡張する。
【００９６】
単一プライベートデータ、複数パブリックデータ
プライベート確率変数ＳがＸ1およびＸ2と相関付けられると仮定する。Ｘ1およびＸ2の歪められたバージョンがそれぞれＹ1およびＹ2で示される。我々は、２つの別個のプライバシー保護写像をＸ1およびＸ2に対して行ってＹ1およびＹ2をそれぞれ得る。所与の歪み制約と共に
【００９７】
【数２１】
2016535898.tif 000023
【００９８】
および
【００９９】
【数２２】
2016535898.tif 000024
【０１００】
が設計され、個々の情報漏出はそれぞれＩ（Ｓ；Ｙ1）およびＩ（Ｓ；Ｙ2）である。結託エンティティによって、または合成を介したプライバシーエージェントによって、２つの公開されるデータＹ1およびＹ2が対（Ｙ1，Ｙ2）として一緒に組み合わされると仮定する。我々は、情報のこの組合せのもとで、結果の累積的情報漏出Ｉ（Ｓ；Ｙ1，Ｙ2）を分析したい。
【０１０１】
補助定理１．Ｙ1、Ｙ2、およびＳが任意の順序のマルコフ連鎖を形成すると仮定する。プライバシー保護写像がそれぞれＹ1およびＹ2によりＩ（Ｙ1；Ｓ）およびＩ（Ｙ2；Ｓ）ビットを漏出する場合、対Ｙ1およびＹ2により最大でＩ（Ｙ1；Ｓ）＋Ｉ（Ｙ2；Ｓ）ビットの情報が漏出される。換言すると、Ｉ（Ｙ1，Ｙ2；Ｓ）≦Ｉ（Ｙ1；Ｓ）＋Ｉ（Ｙ2；Ｓ）である。さらに、Ｓ→Ｙ1→Ｙ2である場合、Ｉ（Ｓ；Ｙ1，Ｙ2）≦Ｉ（Ｙ1；Ｓ）である。Ｓ→Ｙ2→Ｙ1である場合、Ｉ（Ｓ；Ｙ1，Ｙ2）≦Ｉ（Ｙ2；Ｓ）である。
【０１０２】
証明：３つの確率変数がマルコフ連鎖Ａ→Ｂ→Ｃを形成する場合、我々は、Ｉ（Ａ；Ｂ）≧Ｉ（Ａ；Ｂ｜Ｃ）、Ｉ（Ｂ；Ｃ）≧Ｉ（Ｂ；Ｃ｜Ａ）、およびＩ（Ａ；Ｃ｜Ｂ）＝０を有することに留意されたい。証明は、この事実から得られる。□
【０１０３】
補助定理１は、写像が設計されるときにＰS,Xに関するどのくらいの知識が入手可能であるかに関わらず適用される。補助定理１における境界は、ＰS,Xが知られているときに成立する。また、定理１における可分結果に基づく方法を使用してプライバシー保護写像が設計される場合に成立する。
【０１０４】
Ｙ1とＹ2を一緒に使用することがＳの完全な回復をもたらし得ることに留意されたい。たとえば、Ｓ、Ｙ1、およびＹ2を、
【０１０５】
【数２３】
2016535898.tif 000025
【０１０６】
および
【０１０７】
【数２４】
2016535898.tif 000026
【０１０８】
であるような３つの
【０１０９】
【数２５】
2016535898.tif 000027
【０１１０】
確率変数とする。その場合、Ｉ（Ｙ1；Ｓ）＝Ｉ（Ｙ2；Ｓ）＝０が得られる一方、Ｉ（Ｙ1，Ｙ2；Ｓ）＝１ビットであり、Ｓは（Ｙ1，Ｙ2）から完全に回復可能である。別の例は、Ｙ1＝Ｓ＋Ｎであり、ここでＮは何らかのノイズであり、Ｙ2＝Ｓ−Ｎである場合である。我々は、Ｙ1とＹ2を足すことによりＳを完全に回復することができる。
【０１１１】
図２は、本原理の実施形態による、結託または合成を考慮したプライバシーを保護するための例示的方法２００を示す。方法２００は、ステップ２０５から開始する。ステップ２１０で、それは、単一のプライベートデータＳならびにパブリックデータＸ1およびＸ2に基づいて統計情報を収集する。ステップ２２０で、それは、公開されるデータＹ1およびＹ2の結託または合成を考慮して、プライベートデータＳに対する累積的プライバシー保証を判断する。すなわち、それは、Ｉ（Ｓ；Ｙ1，Ｙ2）についての漏出係数εを判断する。
【０１１２】
補助定理１に従って、プライバシー保護写像がパブリックデータＸ1およびＸ2について分散化された様式で設計される。ステップ２３０で、それは、Ｉ（Ｓ；Ｙ1）についての漏出係数ε1を与えられたとして、パブリックデータＸ1についてのプライバシー保護写像
【０１１３】
【数２６】
2016535898.tif 000028
【０１１４】
を決定する。同様に、ステップ２３５で、それは、Ｉ（Ｓ；Ｙ2）についての漏出係数ε2を与えられたとして、パブリックデータＸ2についてのプライバシー保護写像
【０１１５】
【数２７】
2016535898.tif 000029
【０１１６】
を決定する。
【０１１７】
一実施形態では、我々は、ε＝ε1＋ε2、たとえば、ε1＝ε2＝ε／２を設定してよい。ステップ２３０および２３５で設計されたプライバシー保護写像によると、
Ｉ（Ｓ；Ｙ1）≦ε1Ｈ（Ｓ），Ｉ（Ｓ；Ｙ2）≦ε2Ｈ（Ｓ）
補助定理１を使用して、
Ｉ（Ｙ1，Ｙ2；Ｓ）≦Ｉ（Ｙ1；Ｓ）＋Ｉ（Ｙ2；Ｓ）≦ε1Ｈ（Ｓ）＋ε2Ｈ（Ｓ）≦εＨ（Ｓ）
が得られる。
【０１１８】
ステップ２４０および２４５で、我々は、それぞれプライバシー保護写像
【０１１９】
【数２８】
2016535898.tif 000030
【０１２０】
および
【０１２１】
【数２９】
2016535898.tif 000031
【０１２２】
によってデータＸ1およびＸ2を歪める。ステップ２５０および２５５で、歪められたデータはそれぞれＹ1およびＹ2として公開される。
【０１２３】
前述されたように、公開されるデータＹ1（Ｙ2ではない）の正当な受信者が、Ｙ2に関する情報を、公開されるデータＹ2（Ｙ1ではない）の正当な受信者と交換するときに、結託が生じ得る。他方で、合成に関しては、両方の公開されるデータは、同じ受信者によって正当に受け取られ、また受信者が、両方の公開されるデータからの情報を組み合わせてユーザに関するより多くの情報を推論するときに、合成が生じる。
【０１２４】
次に、我々は、最大相関に関する結果を使用して、対Ｙ1およびＹ2により漏出される情報の累積量の上限境界を付ける。
【０１２５】
定理４．
【０１２６】
【数３０】
2016535898.tif 000032
【０１２７】
および
【０１２８】
【数３１】
2016535898.tif 000033
【０１２９】
が別個に設計され、すなわち、
【０１３０】
【数３２】
2016535898.tif 000034
【０１３１】
であり、λ＝ｍａｘ｛Ｓ*（Ｘ1；Ｙ1），Ｓ*（Ｘ2；Ｙ2）｝とする。Ｉ（Ｙ1；Ｙ2）≧λＩ（Ｘ1；Ｘ2）である場合、
Ｉ（Ｓ；Ｙ1，Ｙ2）≦Ｉ（Ｓ；Ｘ1，Ｘ2）ｍａｘ｛Ｓ*（Ｘ1；Ｙ1），Ｓ*（Ｘ2；Ｙ2）｝      （１９）
が得られる。
【０１３２】
証明：定理を証明するために、我々は以下を与える。
【０１３３】
命題４．
【０１３４】
【数３３】
2016535898.tif 000035
【０１３５】
であり、λ＝ｍａｘ｛Ｓ*（Ｘ1；Ｙ1），Ｓ*（Ｘ2；Ｙ2）｝とする。Ｉ（Ｙ1；Ｙ2）≧λＩ（Ｘ1；Ｘ2）である場合、
Ｓ*（Ｘ1，Ｘ2；Ｙ1，Ｙ2）≦ｍａｘ｛Ｓ*（Ｘ1；Ｙ1），Ｓ*（Ｘ2；Ｙ2）｝      （２０）
が得られる。
【０１３６】
さらに、Ｘ1とＸ2が独立している（または同等に（Ｘ1，Ｙ1）と（Ｘ2，Ｙ2）が独立している）場合、
Ｓ*（Ｘ1，Ｘ2；Ｙ1，Ｙ2）＝ｍａｘ｛Ｓ*（Ｘ1；Ｙ1），Ｓ*（Ｘ2；Ｙ2）｝
が得られる。
【０１３７】
まず、我々は、この命題を証明する。独立が成立する特定の場合はＡｎａｎｔｈａｒａｍで既に証明されており、一般的場合の証明は、Ｉ（Ｙ1；Ｙ2）≧λＩ（Ｘ1；Ｘ2）のみが、Ａｎａｎｔｈａｒａｍで述べられたように不等式（２０）を得るために必要とされる不等式であることに留意することによって（Ａｎａｎｔｈａｒａｍ，１０頁、パートＣ参照）、Ｓ*（Ｘ；Ｙ）のテンソル化の証明の同じラインに従う。
【０１３８】
定理４の証明に戻る。定理１を使用して、マルコフ連鎖Ｓ→（Ｘ1，Ｘ2）→（Ｙ1，Ｙ2）が得られるので、
Ｉ（Ｓ；Ｙ1，Ｙ2）≦Ｉ（Ｓ；Ｘ1，Ｘ2）Ｓ*（Ｘ1，Ｘ2；Ｙ1，Ｙ2）
を得る。
【０１３９】
ここで、命題４を使用して証明を終了する。□
したがって、両方の写像が小さい最大相関によって別個に設計される場合、我々は、やはり、対Ｙ1およびＹ2によって漏出される情報の蓄積量を境界付けることができる。
系１．上限境界（１９）の初項、すなわち、Ｉ（Ｘ1，Ｘ2；Ｓ）は、以下のように境界付けられ得る。
【０１４０】
Ｘ1、Ｘ2、およびＳが任意の順序のマルコフ連鎖を形成する場合、Ｉ（Ｘ1，Ｘ2；Ｓ）≦Ｉ（Ｘ；Ｓ）＋Ｉ（Ｘ；Ｓ）である。さらに、Ｓ→Ｘ1→Ｘ2である場合、Ｉ（Ｓ；Ｘ1，Ｘ2）≦Ｉ（Ｘ1；Ｓ）である。Ｓ→Ｘ2→Ｘ1である場合、Ｉ（Ｓ；Ｘ1，Ｘ2）≦Ｉ（Ｘ2；Ｓ）である。
【０１４１】
証明：証明は、補助定理１のそれと同様である。
【０１４２】
Ｉ（Ｓ；Ｙ1）、Ｉ（Ｓ；Ｙ2）およびＩ（Ｓ；Ｙ1，Ｙ2）は、Ｈ（Ｓ）以下であることに留意されたい。
【０１４３】
Ｓ*（Ｘ1；Ｙ1）＜ε，Ｓ*（Ｘ2；Ｙ2）＜ε
を選択した場合、
Ｉ（Ｓ；Ｙ1，Ｙ2）≦（Ｓ；Ｘ1，Ｘ2）ｍａｘ｛Ｓ*（Ｘ1；Ｙ1），Ｓ*（Ｘ2；Ｙ2）｝≦Ｈ（Ｓ）ｍａｘ｛Ｓ*（Ｘ1；Ｙ1），Ｓ*（Ｘ2；Ｙ2）｝＜εＨ（Ｓ）
が得られる。
【０１４４】
図３は、本原理の実施形態による、結託または合成を考慮してプライバシーを保護するための例示的方法３００を示す。方法３００は、Ｓ*（Ｘ1；Ｙ1）＜ε（３３０）およびＳ*（Ｘ2；Ｙ2）＜ε（３３５）を除いて、方法２００と同様である。方法２００は、補助定理１で述べられたいくつかのマルコフ連鎖仮定のもとで作用するのに対し、方法３００は、より一般的に作用することに留意されたい。
【０１４５】
複数のプライベートデータ、複数のパブリックデータ
我々は、それぞれＸ1およびＸ2と相関付けられる２つのプライベート確率変数Ｓ1およびＳ2を有すると仮定する。我々は、Ｘ1およびＸ2を歪めてＹ1およびＹ2をそれぞれ得る。分析者は、Ｙ1およびＹ2にアクセスし、（Ｓ1，Ｓ2）を発見することを望む。
定理５．
【０１４６】
【数３４】
2016535898.tif 000036
【０１４７】
および
【０１４８】
【数３５】
2016535898.tif 000037
【０１４９】
が別個に設計され、すなわち、
【０１５０】
【数３６】
2016535898.tif 000038
【０１５１】
であり、λ＝ｍａｘ｛Ｓ*（Ｘ1；Ｙ1），Ｓ*（Ｘ2；Ｙ2）｝とする。Ｉ（Ｙ1；Ｙ2）≧λＩ（Ｘ1；Ｘ2）である場合、我々は、
Ｉ（Ｓ１，Ｓ２；Ｙ1，Ｙ2）≦Ｉ（Ｓ１，Ｓ２；Ｘ1，Ｘ2）ｍａｘ｛Ｓ*（Ｘ1；Ｙ1），Ｓ*（Ｘ2；Ｙ2）｝      （２１）
を得る。
【０１５２】
証明：定理４の証明と同様である。□
したがって、対Ｙ1およびＹ2の累積的情報漏出は、（２１）によって境界付けられる。特に、Ｘ1とＸ2が独立である場合、この境界が成立する。
【０１５３】
図２では、我々は、結託または合成を考慮して、単一のプライベートデータおよび２つのパブリックデータを考慮に入れるプライバシー保護写像を決定する方法２００を論じる。２つのプライベートデータがある場合、方法２００は、いくつかの修正と共に適用され得る。具体的には、ステップ２１０で、我々は、Ｓ1、Ｓ2、Ｘ1、およびＸ2に基づいて統計情報を収集する。ステップ２３０で、我々は、Ｉ（Ｓ1；Ｙ1）についての漏出係数ε1を与えられたとして、パブリックデータＸ1についてのプライバシー保護写像
【０１５４】
【数３７】
2016535898.tif 000039
【０１５５】
を設計する。ステップ２３５で、我々は、Ｉ（Ｓ2；Ｙ2）についての漏出係数ε2を与えられたとして、パブリックデータＸ2についてのプライバシー保護写像
【０１５６】
【数３８】
2016535898.tif 000040
【０１５７】
を設計する。
【０１５８】
同様に、図３では、我々は、結託または合成を考慮して、単一のプライベートデータおよび２つのパブリックデータを考慮に入れるプライバシー保護写像を決定する方法３００を論じる。２つのプライベートデータがある場合、方法３００は、いくつかの修正と共に適用され得る。具体的には、ステップ３１０で、我々は、Ｓ1、Ｓ2、Ｘ1、およびＸ2に基づいて統計情報を収集する。ステップ３３０で、我々は、Ｉ（Ｓ1；Ｙ1）についての漏出係数εを与えられたとして、パブリックデータＸ1についてのプライバシー保護写像
【０１５９】
【数３９】
2016535898.tif 000041
【０１６０】
を設計する。ステップ３３５で、我々は、Ｉ（Ｓ2；Ｙ2）についての漏出係数εを与えられたとして、パブリックデータＸ2についてのプライバシー保護写像
【０１６１】
【数４０】
2016535898.tif 000042
【０１６２】
を設計する。
【０１６３】
上記では、我々は、２つのプライベートデータまたは２つのパブリックデータに関して論じている。本原理は、２つよりも多いプライベートまたはパブリックデータがあるときにも適用され得る。
【０１６４】
プライバシーエージェントは、プライバシーサービスをユーザに提供するエンティティである。プライバシーエージェントは、以下の任意のものを行うことができる：
−  ユーザから、どんなデータをユーザがプライベートであるとみなすか、どんなデータをユーザがパブリックであるとみなすか、およびユーザが求めるプライバシーのレベルを受け取る；
−  プライバシー保護写像を計算する；
−  ユーザのためのプライバシー保護写像を実装する（すなわち、写像によりユーザのデータを歪める）；および
−  歪められたデータを、たとえば、サービスプロバイダまたはデータ収集エージェンシに公開する。
【０１６５】
本原理は、ユーザデータのプライバシーを保護するプライバシーエージェントにおいて使用され得る。図４は、プライバシーエージェントが使用され得る例示的システム４００のブロック図を示す。パブリックユーザ４１０は、彼らのプライベートデータ（Ｓ）および／またはパブリックデータ（Ｘ）を公開する。前述されたように、パブリックユーザは、パブリックデータをそのままで公開する、すなわちＹ＝Ｘである。パブリックユーザによって公開された情報は、プライバシーエージェントに有用な統計情報となる。
【０１６６】
プライバシーエージェント４８０は、統計収集モジュール４２０、プライバシー保護写像判断モジュール４３０、およびプライバシー保護モジュール４４０を含む。統計収集モジュール４２０は、同時分布ＰS,X、限界確率測度Ｐx、ならびに／またはパブリックデータの平均および共分散を収集するために使用され得る。統計収集モジュール４２０は、ｂｌｕｅｋａｉ．ｃｏｍなどのデータアグリゲータから統計値を受け取ってもよい。入手可能な統計情報に応じて、プライバシー保護写像判断モジュール４３０は、いくつかのプライバシー保護写像機構を設計する。プライバシー保護モジュール４４０は、条件付き確率によって、プライベートユーザ４６０のパブリックデータをそれが公開される前に歪める。パブリックデータが多次元であるとき、たとえば、ＸがＸ1とＸ2の両方を含むとき、プライバシー保護モジュールは、合成の観点から、Ｘ1およびＸ2に対する別個のプライバシー保護写像をそれぞれ設計することができる。結託があるとき、各結託エンティティは、システム４００を使用して別個のプライバシー保護写像を設計することができる。
【０１６７】
プライバシーエージェントは、データ収集モジュールに収集され統計値を計算することを許可された、データ全体の知識なしに作用するための統計値のみを必要とすることに留意されたい。したがって、別の実施形態では、データ収集モジュールは、データを収集し次いで統計値を計算する独立したモジュールであってもよく、プライバシーエージェントの一部である必要はない。データ収集モジュールは、プライバシーエージェントと統計値を共有する。
【０１６８】
プライバシーエージェントは、ユーザとユーザデータの受信者（たとえばサービスプロバイダ）との間に存在する。たとえば、プライバシーエージェントは、ユーザデバイス、たとえば、コンピュータまたはセットトップボックス（ＳＴＢ）に配置されてよい。別の例では、プライバシーエージェントは別個のエンティティであってよい。
【０１６９】
プライバシーエージェントのすべてのモジュールは、１つのデバイスに配置されてもよく、または異なるデバイスにわたって分散されてもよく、たとえば、統計収集モジュール４２０は、統計値をモジュール４３０に単に公開するデータアグリゲータに配置されてもよく、プライバシー保護写像判断モジュール４３０は、「プライバシーサービスプロバイダ」に、またはモジュール４２０に接続されたユーザデバイス上のユーザ端に配置されてもよく、プライバシー保護モジュール４４０は、ユーザ間の媒介として働くプライバシーサービスプロバイダ、およびユーザがデータを公開したい先のサービスプロバイダ、またはユーザデバイス上のユーザ端に配置されてもよい。
【０１７０】
プライベートユーザ４６０が受け取るサービスを公開されるデータに基づいて改善するために、プライバシーエージェントは、公開されるデータを、サービスプロバイダ、たとえば、コムキャストまたはネットフリックスに提供することができ、たとえば、推奨システムが、その公開された映画ランキングに基づいてユーザに映画の推奨を提供する。
【０１７１】
図５では、我々は、システム内に複数のプライバシーエージェントがあることを示す。異なる変形形態では、プライバシーエージェントはプライバシーシステムが作用するための必要条件でないので、それはすべての場所にある必要がない。たとえば、プライバシーエージェントは、ユーザデバイスもしくはサービスプロバイダのみ、または両方にあってもよい。図５では、我々は、ネットフリックスとフェイスブック（Facebook）の両方に対して同じプライバシーエージェント「Ｃ」を示す。別の実施形態では、フェイスブックとネットフリックスにおけるプライバシーエージェントは、同じにすることができるが必ずしも同じでなくてよい。
【０１７２】
本明細書に説明される実装形態は、たとえば、方法もしくはプロセス、装置、ソフトウェアプログラム、データストリーム、または信号において実装されてよい。単一形態の実装形態の文脈でのみ論じられた（たとえば、方法としてのみ論じられた）場合でも、論じられた特徴の実装形態は、他の形態（たとえば、装置またはプログラム）で実装されてもよい。装置は、たとえば、適切なハードウェア、ソフトウェア、およびファームウェアで実装されてよい。方法は、たとえばコンピュータ、マイクロプロセッサ、集積回路、またはプログラマブル論理デバイスを含む、一般に処理デバイスを指すたとえばプロセッサなどの、たとえば装置において実装されてよい。プロセッサはまた、エンドユーザ間の情報の通信を促進する、たとえば、コンピュータ、セルフォン、ポータブル／パーソナルディジタルアシスタント（「ＰＤＡ」）、および他のデバイスなどの、通信デバイスを含む。
【０１７３】
本原理の「一実施形態」または「実施形態」または「一実装形態」または「実装形態」、およびそれらの他の変形形態への参照は、その実施形態に関連して説明される特定の特徴、構造、および特性などが本原理の少なくとも１つの実施形態に含まれることを意味する。したがって、本明細書を通して様々な箇所で出現する表現「一実施形態では」または「実施形態では」または「一実装形態では」または「実装形態では」、および任意の他の変形形態の出現は、必ずしもすべて同じ実施形態を参照するものではない。
【０１７４】
加えて、本出願またはその特許請求の範囲は、様々な情報片を「決定すること」を参照することがある。情報を決定することは、たとえば、情報を推定すること、情報を計算すること、情報を予測すること、またはメモリから情報を取り出すことのうちの１または複数を含み得る。
【０１７５】
さらに、本出願またはその特許請求の範囲は、様々な情報片に「アクセスすること」を参照することがある。情報にアクセスすることは、たとえば、情報を受け取ること、（たとえばメモリから）情報を取り出すこと、情報を記憶すること、情報を処理すること、情報を送信すること、情報を移動すること、情報をコピーすること、情報を消去すること、情報を計算すること、情報を決定すること、情報を予測すること、または情報を推定することのうちの１または複数を含み得る。
【０１７６】
加えて、本出願またはその特許請求の範囲は、様々な情報片を「受け取る」ことを参照することがある。受け取ることは、「アクセスすること」と同様に広義の用語になるように意図されている。情報を受け取ることは、たとえば、情報にアクセスすること、または（たとえばメモリから）情報を取り出すことのうちの１または複数を含み得る。さらに、「受け取ること」は、通常は、何らかの形で、たとえば、情報を記憶すること、情報を処理すること、情報を送信すること、情報を移動すること、情報をコピーすること、情報を消去すること、情報を計算すること、情報を決定すること、情報を予測すること、または情報を推定することなどの動作の際に行われる。
【０１７７】
当業者には明らかなように、実装形態は、たとえば、記憶または送信され得る情報を搬送するようにフォーマットされた様々な信号を生成し得る。情報は、たとえば、方法を実施するための命令、または説明された実装形態の１つによって生成されたデータを含み得る。たとえば、信号は、説明された実施形態のビットストリームを搬送するようにフォーマット化されてよい。そのような信号は、たとえば、電磁波として（たとえば、スペクトルの無線周波数部分を使用する）、またはベースバンド信号としてフォーマットされてよい。フォーマッティングは、たとえば、データストリームを符号化し、符号化されたデータストリームを用いて搬送波を変調することを含むことができる。信号が搬送する情報は、たとえば、アナログまたはディジタル情報であってよい。信号は、知られている様々な異なる有線またはワイヤレスリンクを介して送信されてよい。信号は、プロセッサ可読媒体に記憶されてよい。
【図１】
2016535898.tif 000043
【図２】
2016535898.tif 000044
【図３】
2016535898.tif 000045
【図４】
2016535898.tif 000046
【図５】
2016535898.tif 000047
【国際調査報告】
2016535898.tif 000048
2016535898.tif 000049