アクセス制御を開発する方法によるソーシャルネットワークのプライバシー
ソーシャルネットワークにおける共有されたデータに起因した、プライバシーの毀損を抑制する方法およびソフトウエアの製造で、基本的で根本的な前提は、ユーザが、共有データに興味を持ち、および適切なプライバシーポリシーに常に従うことを想定することができないことである。ソーシャルネットワークは、サーバを補助するアクセス制御の追加的な層を配置し、ユーザからの動作がない状態でさえ、ユーザデータにアクセスすることを制限することによって、自動的に開発する。アクセス制御を開発する仕組みは、ユーティリティ（言い換えればユーザが、できるだけ多くの量のデータを他のすべてのユーザと共有すること）およびプライバシー（言い換えればユーザが、低い確率で、長い時間をかけて、センシティブなデータだけの組合せを暴露すること）の形式的で具体的な要求についての重要で定量化できる保証を提供する。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願との相互参照
本出願は、参照によりその全体が本明細書に組み込まれる、２００９年８月１２日に出願した米国仮特許出願第６１／２３３，３２０号明細書の利益を主張する。
【０００２】
本発明は、ソーシャルネットワークにおいて共有されるデータに起因するプライバシーの毀損を抑制することに関する。
【背景技術】
【０００３】
ソーシャルネットワークにおいて近年、ソーシャルネットワーキングウェブサイト（例えば、Facebook（登録商標）, Myspace（登録商標）, Twitter（登録商標））を管理するビジネスが増加する傾向にある。ここでは、ユーザが、自由にユーザのデータ（画像、テキスト、ファイル等の）を投稿することができ、ウェブサイトへのアクセスするユーザの友人、仲間、どんな人とでも、それを共有できる。最も有名なサイトでは、数千万のユーザを惹き付けているので、サイトの悪用の招いた結果が、大手の新聞およびマスコミ関係に毎日のように記事になっている。典型的な悪用は、ユーザが、様々なタイプのセンシティブなデータ（恥ずかしい写真、政治的な非公式の意見、所有権に関する書類）のを偶然共有してしまうことであり、これにより、望まない結果（雇用および解雇についての決定に影響を与えることになる、医療の提供、保険の他の種類等）が引き起こされる。
【０００４】
将来の望まれない結果に対して、データをプライベートに保持するため、ユーザの要求（プライバシーと呼ばれる）と、それらのデータ（ユーティリティと呼ばれる）を共有するというユーザの要望とのバランスを取ることは、実際のソーシャルネットワークにおける大きな問題として理解されている。
【０００５】
理論上は、ユーザは、ユーティリティにかかる費用において（換言すれば、データを共有しないことによって）、プライバシーを維持でき、プライバシーにかかる費用において（換言すれば、すべての共有データのアクセスを制限しないことによって）、ユーティリティを最大限使用することができ、または、理論的に最良の方法であるが、現時点または将来において、望まれるデータのプライバシーを提供するアクセス制御のポリシーを絶え間なく実行することによって、プライバシーとユーティリティとのバランスを取ることができる。
【０００６】
後者の手法は、可能であれば、少なくとも２つの理由で実用的であると期待される。第１に、将来においてプライバシーを保持することが保証されるというポリシーを起草することは、複数の状況において難しい（すなわち、今日は問題ないデータでも明日はそうではない）かもしれないという理由であり、第２に、ソーシャルネットワークの目的に反している可能性はあるが、複雑となり得るプライバシーポリシーに完全に従うように、非常に大きなソーシャルネットワークのユーザに要求することは、複数の状況において、少しの成功もないかもしれないという理由である。事実、完全に遵守する単一のユーザの場合でさえ、このユーザのプライバシーは、他のユーザの動作によって、変更される可能性がある。概して、これは、ユーザを限定する１つのアクセス制御だけでは、受容できるプライバシーの解決とはなり得ないことを示している。
【０００７】
近年、ソーシャルネットワークの使用による信用およびプライバシーの問題の議論が続いている。さらに、新聞雑誌は、毎日これらの問題に注意を向けており、通常、脆弱なプライバシーから生じる望まれない事件について書いている。しかし、素早く実用的なプライバシーの毀損を抑制する“常識的な”の手法についても書かれている。数少ない研究論文は、ソーシャルネットワークにおける異なったプライバシーの問題の解決を、最近試みている。例えば、プライバシー保護における犯罪捜査は、Kerschbaum, F. and Schaad, A. “Privacy-preserving social network analysis for criminal investigations”, In Proc. of the 7th ACM Workshop on Privacy in the Electronic Society. WPES '08. ACM, New York, NY, 9-14において研究され、プライバシーの特徴付けは、Krishnamurthy, B. and Wills, C. “Characterizing Privacy in Online Social Networks”, In Proc.of ACM WOSN 2008において研究され、グラフベースのモデルにおけるプライバシーは、Korolova, A., Motwani, R., Nabar, S. U., and Xu, Y. 2008, “Link privacy in social networks”, In Proceeding of the 17th ACM Conference on Information and Knowledge Management. CIKM '08. ACM, New York, NY, 289-298において研究され、データが共有されている間、トゥルースフルネス（truthfulness）を促進するゲーム理論の構造は、Squicciarini, A. C, Shehab, M., and Paci, F. 2009. “Collective privacy management in social networks”, In Proceedings of the 18th international Conference on World Wide Web. WWW '09. ACM, New York, NY, 521-530.において、提案された。
【発明の概要】
【０００８】
本発明は、ソーシャルネットワーキングウェブサイトにおいて共有するデータに起因してプライバシーの毀損を妨げる方法およびソフトウエアを提供する。詳細には、さらに、上記のユーザ限定のアクセス制御に加えて、ソーシャルネットワークのユーザは、ユーザのデータの幾つかにアクセスすることを知的に限定することにより、ゆっくりと時間をかけて自動的に開発する、サーバ補助のアクセス制御の追加の層が提供され、並びにプライバシーおよびユーティリティについて、無駄のない定量化できる保証を提供する。アクセス制御は、プライバシーに対する確率保証を提供することにより、またはユーザからの任意の追加的な動作を必要としないことにより、ユーザ限定のアクセス制御の２つの言及される欠点を、特別に対象とする（従って、ユーザへの妨害および同じユーザにより偶然に発生した被害を同時に避ける）。いわゆる、本モデルは、一連の時間間隔から外れたらいつでも、プライベート（ソーシャルネットワークの限定された集合の間でだけ共有される）、またはパブリック（すべてのユーザの間で共有される）となることができる属性を有するデータオブジェクトの系として、ユーザが共有するデータベースを表す。このモデルにおいて、提案するサーバを補助するアクセス制御の実例は、プライベートまたはパブリックとしてユーザのデータオブジェクトの幾つかを、ランダムに再設定することによって、或いは過去および将来の属性の設定によって決定することによって各時間間隔において、アクセス制御のポリシーを自動的に更新する。言い換えれば、“開発するアクセス制御”と言われる、この構造は、ユーザが、消極的または不本意にプライバシー問題を取り扱う時間間隔において、データオブジェクトのプライバシーの属性が、設定されることを具体化する。属性は、ユーザ（いわゆる、ユーザは、彼の／彼女のお気に入りのプライバシーおよび／またはアクセス制御のポリシーの構造および実装を消すことができる）に強制せず、またはサーバによって設定される時、ユーティリティ（いわゆる、ユーザは、パブリックに設定された属性を有する、できるだけ多くのデータを残す）またはプライバシー（いわゆる、ユーザは、高い確率を持ったプライベートに設定された属性を有する、センシティブなデータの組み合わせを保持する）に対する、形式的に具体化された要求を定量化できることを保証する。
【０００９】
具体的には、センシティブなデータは、サーバに知られていない、さらに広く一般的には、ユーザに知られていない、ユーザのデータオブジェクトの任意のサブセットとしてモデル化される。
【００１０】
この方法は、確率的で、カバーフリーファミリー（cover-free families）の変化に基づいている。例において、まず、従来のカバーフリーファミリーは、目的に十分ではない（例えば、目的が、ユーティリティの要求を最大化する必要がない）ことが観察される。それから、無駄のない、かつ定量化できるユーティリティおよびプライバシーの特性である証明をすることが可能であるために、ランダム化されたサブセットの選択（後で信頼できる特性を有するカバーフリーファミリーとして分析される）のための既知の構造の変化が提案される。
【００１１】
本発明は、添付図面と併せて以下の明細書を読むと、より明らかに理解されるだろう。
【図面の簡単な説明】
【００１２】
【図１】n = 500, t = m = 10，s = 10 (セットアップ１) n = 400, t = m = 9, s = 10 (セットアップ２), n = 300, t = m = 8, s = 10 (セットアップ３)の時のｌの関数としたεの値の図表示である。ε< 0.001となるようなｌの最大値は、各々47, 41, および35である。
【図２】n = 500, m = 10, s = 10 (セットアップ１), n = 400, m = 9, s = 10 (セットアップ２), n = 300, m = 8, s = 10 (セットアップ３)の時のεの関数としたｌの値の図表示である。ｌ> 35となるようなεの最大値は、各々0.0014, 0.0032, および0.0098である。
【図３】本発明の修正されたフローチャート図である。
【図４】本発明を示した、簡略化したブロックダイアグラム図である。
【発明を実施するための形態】
【００１３】
ソーシャルネットワークは、データタイプに依存する可能性のあるソーシャルネットワークのユーザの異なるデータフォーマット、並びに異なる共有、およびアクセスポリシーを可能にする。次の形式により、我々は、より易しい記述および本発明のより広い適用性を後で促進するため、さらに簡易化された一般的なモデルを確保することを試みる。ソーシャルネットワークおよびネットワークの複数のメンバーの１人であるユーザUについて、集中型のソフトウエアを実行するサーバSを考える。
【００１４】
【００１５】
ここで、bj = パブリック（それぞれ，bj = プライベート）によって、データオブジェクトDjは、すべて（それぞれ限定された集合のみ）のソーシャルネットワークのユーザと共有されることを意味し、ここでは、限定された集合は、Uによって選択される。ソーシャルネットワークへの参加でUによって得られたユーティリティは、Uの具体的な特徴およびインタレストに依存する可能性がある。複数の実生活のソーシャルネットワークの根本的な原理の同意において、設定bj＝パブリックは、Uの視点から、設定bj＝プライベートより高いユーティリティを提供すると想定する。従って、ソーシャルネットワークへの参加におけるUのユーティリティを最大化する方法として設定bj＝パブリックである｛1,..., n｝からjの数を最大化することを考える。
【００１６】
しばしば、単一のデータオブジェクトは、センシティブの資料を十分提供できない可能性がある一方、複数のデータオブジェクトは、相互に関連があれば、そのように提供するとみなされる可能性がある。センシティブなデータについて合理的で単純な、および一般的なモデルを試みるため、データオブジェクトのナンバーｓの結合が、いずれセンシティブとなることが可能であると想定する。従って、s個のデータオブジェクト{Dj|j∈P}の少なくとも１つが、A(Dj) = プライベートを満たす場合、Uのプライバシーを維持することができると理解することにより、P ⊆｛1,..., n｝，|P| = sとしてセンシティブのサブセットを示す。
【００１７】
【００１８】
センシティブのサブセットにおける少なくとも１つのデータオブジェクトは、プライベートの属性を有するため、各時間の部分区間においてアクセス制御のアルゴリズムを、常に適合することによって、ユーザUは、プライバシー問題を解決することに留意すべきである。しかし、上記ですでに部分的に議論されたように、Uは、将来的にセンシティブなデータのオブジェクトのサブセットになるであろうことを知らなくても良いし、または必要ならばいつでも、アクセス制御のアルゴリズムの適合を利用できないとしても良いと想定する。続いて、実用的なアクセス制御のシステム（いわゆる臨時のパスワードの再設定）により、0およびTの経過時間において、Uは、アクセス制御のアルゴリズムの適合を利用できることを想定する。従って、［0，T］として表示される、十分に幅のある時間の区間を考慮し、およびそれをｍの等しい長さの部分区間にさらに分割する。時間依存を組み込むためbj；A(Dj)の上記の表記を補強する。具体的には、bij = A(I, Dj)は、i = 1,..., mおよびj = 1,..., nについて［0，T］のi番目の部分区間において、データオブジェクトDjの属性値を示す。さらに、データオブジェクトの送信時間においてj = 1,..., nにもかかわらずb0j = A(0, Dj) = パブリックを維持すると想定される。
【００１９】
【００２０】
本発明の目的は、ユーティリティおよびプライバシーの特性により、アクセス制御を開発するアルゴリズムを設計することを目的とする。
【００２１】
上記のユーザデータベースの場合において、ユーティリティの概念は、ユーザUに本来備わっており、アクセス制御のアルゴリズムの場合でさえ、i = 1,..., mおよびj = 1,..., nについてbi,1,..., bi,nの一般的な関数に関して、そのようなアルゴリズムのユーティリティを定義付けることができる。形式的に、任意の関数f :{0, 1}mxn →［0，1］について、アクセス制御を開発するアルゴリズムEvACは、f ({bi,1,..., bi,n}mi=1) = yである場合、f -ユーティリティ yを有する。ここでは、{bi,1,..., bi,n}mi=1 = EvAC (D1 ,..., Dn, m)となる。fは、アクセス制御を開発するアルゴリズムEvACのための（fを最適化するために、EvACは、設計され得ることを意味する）効用関数である。
【００２２】
できるだけ多くのソーシャルネットワークのユーザのためにユーティリティを確保することを試みる、より具体的な効用関数f を定義する。我々は、所与の（任意の与えられた時間において、データの値のより高い数の属性が、パブリックに設定されるとき、ユーティリティは、より高くなることを意味する）時間の部分区間におけるドキュメントの数、および（時間の部分区間のより高い数の間で、任意で与えられるドキュメントの属性が、パブリックに設定されるとき、ユーティリティは、より高くなることを意味する）所与のドキュメントのための時間の部分区間の数の両方を超えて、ユーザのデータベースの場合のためになされる結論を拡張する（いわゆる、ユーティリティは、公開してアクセスできるデータの値の数が増える時に、増える）。
【００２３】
まず、bi = (bi,1,..., bi,n)およびbj = (bi,j,..., bm,j)並びに各々のハミング重み、
【００２４】
【数１】
【００２５】
の表記を定義する。また、任意の整数p, x について、I ≧ p(x)に測定器のしきい値関数を表示させ、x ≧ p およびほかの0である場合、1と等しいとして定義される。全ての整数p, q 、およびNから［0，1］までの単調増加関数g, hについて、効用関数を定義する。
【００２６】
【数２】
【００２７】
これは、しきい値ベースの効用関数と言われている。
【００２８】
以下の記載において、目的は、しきい値ベースの効用関数を最大化するアクセス制御を開発するアルゴリズムの設計である。理想的には、より幅広い一般化のため、p, q, g, hについての具体的な設定に独立してなされる。プライバシーの要求が拒否された場合、すべてのi, jについて、bij = パブリックにいつも設定するアルゴリズムは、この目的を自明に達成することに留意すべきである。
【００２９】
ユーザデータベースの場合に議論される直観を拡張して、次に、我々は、アクセス制御を開発するアルゴリズムだけが、多量の時間の部分区間中、或いは全体の時間の区間［0, T］の間、小さな可能性を有するパブリックとしてセンシティブのベクトルのすべての成分を設定するという事実を形式化する。言い換えれば、我々は、｛1,..., m｝におけるi の値の幾つか、或いはすべてについて、アクセス制御を開発するアルゴリズムの出力からベクトルbiを収集するように、プライバシーの侵害を企てる敵対者さえも考慮する。この攻撃でさえ考慮して本発明を使用することにより、この敵対者が、センシティブのベクトルを再構築できる確率を低減する。
【００３０】
形式的に、P ⊆｛1,..., n｝をs −サイズのセンシティブのサブセットとし、tを敵対者の攻撃を被る時間の部分区間の数とする。任意のi1,..., it∈｛1,..., m｝の場合に、すべてのj∈P について、Viti=i1（bij = パブリック）が、成り立つ確率は、εが最大となるとき、任意のε> 0について、アクセス制御を開発するアルゴリズムEvAC は、（t, ε）−プライバシーを満たす。ベクトルP は、任意にモデル化することができ、およびより広い一般化のため、U およびS 両方に不知である（U が理論的に、データがセンシティブであるか否かを示す最良の位置にいるとしても、ニュースの出来事においてよく記録されるように、U は、現在または将来の時間に関してさえも、最良の決定をすることができないと、我々は、より実質的な観察をする）。P のサイズｓは、アクセス制御を開発するアルゴリズムへ知られると想定する（これが、一般に成り立たなくても、この例は、|P|を上限としてｓを設定する必要があることを示すためにも必要である）。結局モデルのベクトルP は、アルゴリズムEvAC、またはその出力によって、独立して選択される（確かに、形式的には、この定義のバージョンを定義するが、P はEvAC によって返された出力に依存する）。
【００３１】
以下の説明の目的は、EvACが、（t, ε）−プライベートであることについて、ｔを最大化すると同時に、εを最小化するアルゴリズムEvACを設計することである。ユーティリティの要求が無視されても、すべてのi; j についてbij = パブリックと常に設定するアルゴリズムは、自明にこの目的を達成する。従って、発明の目的は、（t, ε）−プライベートとｆ−ユーティリティとのトレードオフを達成することである。
【００３２】
以下の例において、簡易なEvACアルゴリズムは、ほぼカバーフリーファミリーの既知の分類の変形に基づいている。
【００３３】
本発明の主な概要は、センシティブのサブセットPにおけるデータオブジェクトの少なくとも１つの属性を、できるだけ多量の時間の部分区間中、或いは全体の時間の区間［0, T］の間、プライベートに設定し続けることを保証することである。目的を達成することについて、カバーフリーファミリーは、自然な解決ツールと考えられる。さらに、プライバシーを侵害する攻撃を実行するのにかかる時間を最大化する、およびすべてのデータオブジェクトが、最終的にパブリックに設定される確率を最小化する、並びに適切なしきい値ベースの効用関数（パブリックに設定されたデータオブジェクトの数の関数として）を最大化する、プライバシーおよびユーティリティの変数に関して、以下の３つの目的をさらに達成することが好ましい。第１の目的は、カバーフリーのサブセットの選択が、[0, T]の時間の部分区間mの各々において変化することを示すことである。第２の目的および第３の目的は、程度の良いカバーフリーである特性を有する、およびカバーフリーの各々のサブセットの最大限のサイズを有するファミリーの選択を示すことである。カバーフリーファミリーの定義は以下の通りである。
【００３４】
n, m, kを正の整数として、Gをサイズｎのグラウンド（ground）の集合とし、およびF = {S1,..., Sk}をGのサブセットのファミリーとする。
【００３５】
【００３６】
そして、Fにおける各々のサブセットが、Fにおける任意のｍの他のサブセットの集合によりカバーされない場合、ファミリーFは、G以上にｍ−カバーフリーとなる。
【００３７】
カバーフリーファミリーについて幾つかの結果が知られている。例えば、Erdos, P., Frankl P. and Furedi Z, “Families of finite sets in which no set is covered by the union of r others”In Israeli Journal of Mathematics, 51 : 79-89, 1985において知られており、決定論的なアルゴリズムが存在し、任意の固定されたｍ, ｌについて、ｌ= [n/4m]and n ≦16m2 (1+log(k/2)/log3)について、m−カバーフリー、ｋ−サイズ、サイズｎのグラウンドの集合以上のｌ−サイズのベクトルのファミリーFを構成する。
【００３８】
本実施例では、カバーフリーファミリーのブラックボックス（a black-box）の適用は、問題を解決できないだろう、３つの理由は以下の通りである。
１．カバーされるサブセット（いわゆるセンシティブのサブセット）は、サイズｓを有し、このとき、サブセット（いわゆるi = 1,..., mについて属性値の集合）をカバーすることは、サイズｌを有し、通常ではｌ≠sとなる（ｌを最大化するよう試みるとき）。
２．カバーされるサブセット（いわゆるセンシティブのサブセット）は、{0, 1}nの任意のサブセットとなり得るが、カバーフリーの設定では、通常では、このケースにはなり得ない。
３．センシティブのサブセットがカバーされない明確な確率が低いのは、確かだが、これは、任意のカバーフリーファミリーにおけるケースではない。
【００３９】
３番目の理由は、カバーフリーファミリーを使用するより良い性能を有する構造を得られるかもしれないことを示唆する。１番目の理由は、知られているカバーフリーファミリーの変形を使用することができるかもしれないことを示唆し、２番目の理由は、これらの間の検索を規制する。この例の構造は、簡易なランダム化された構造のわずかな変形であり、複数の異なるコンテキストにおいてすでに使用されており、Garay, J., Staddon, J.andWool, A. “Long-live Broadcast Encryption”, In Proc. of Crypto 2000, LNCS, Springer- Verlagにおいて示した、（ほとんど）カバーフリーファミリーである。
【００４０】
アクセス制御を開発するアルゴリズムEvACの例は、入力データオブジェクトD1 ,..., Dnおよび時間間隔のmの番号を受け取る。
【００４１】
まず、UのデータオブジェクトD1 ,..., Dnは、ランダムに順序を変える。直感的に、これは、センシティブのサブセットPの分布が、{0, 1}nからｓ−サイズのサブセットの全体にわたって等しくなることを保証する。この事実は、ユーティリティおよびプライバシーの分析をさらに簡略化し、ユーティリティおよびプライバシーの変数の改善を助ける。
【００４２】
次に、アルゴリズムは、以下のように、i = 1,..., m およびｊ = 1,..., n について属性値bijを計算する。i∈{1,..., m}の各々について、確かな値j1,..., jlの数ｌは、均一に、{0, 1}nから独立して選択され、次に、bij は、パブリックと等しく設定されるか、プライベートと等しく設定される。ここで、ｌは変数であり、n, m, s, εに依存し、図のユーティリティの特性の分析において設定される（そして、最大化される）。事実、s の正確な値を知る必要はない。s の上限で十分だろう。
【００４３】
上記記載したプライバシーおよびユーティリティの特性の証明を、図１および図２を参照して示す。図１は、n = 500, t = m = 10， s = 10 (セットアップ１) n = 400, t = m = 9, s = 10 (セットアップ２), n = 300, t = m = 8, s = 10 (セットアップ３)の時のｌの関数としたεの値を表す。ε< 0.001となるようなｌの最大値は、各々47, 41, および35である。図２は、n = 500, m = 10, s = 10 (セットアップ１), n = 400, m = 9, s = 10 (セットアップ２), n = 300, m = 8, s = 10 (セットアップ３)の時のεの関数としたｌの値を表す。ｌ> 35となるようなεの最大値は、各々0.0014, 0.0032, および0.0098である。
【００４４】
原理１
U に、n データオブジェクトを有するソーシャルネットワークのデータベースを待たせる。m 時間間隔を超えて、上記のアルゴリズムEvAC は、与えられた時間≦ｌにおいて保持し、パブリックに設定する属性を記録し、および任意のt ≦ mについて（t, ε）−プライバシーを満たすアクセス制御を開発するアルゴリズムであり、
【００４５】
【数３】
【００４６】
s（上限）は、センシティブのサブセットの長さである。ε1/s＞１−（１−２／n）mの範囲ならばいつでも、アルゴリズムEvACは、ｇ−ユーティリティを満たし、ｇは、しきい値ベースの効用関数であり、
ｌ＜ｎ（１−（１−ε1/s）1/m）
のような一番幅広い値ｌによって最大化される。
【００４７】
この原理は、プライバシーとユーティリティとのトレードオフに関し、および変数設定に関し、以下の通り最適に説明するように貢献する。独立したプライバシーの最大化は、すべてのi, jについて、bij = プライベートに設定されたアクセス制御のアルゴリズムによって与えられ、従って（m, 0）−プライバシーを達成しユーティリティを最小限とする。同様に、独立したユーティリティの最大化は、すべてのi, j について、bij =パブリックに設定されたアクセス制御のアルゴリズムによって与えられ、従って、（しきい値ベースの効用関数を含む）効用関数の幅広い分類について最大限のユーティリティを達成するが、任意のε＜1について（1, ε）−プライバシーは満たさない。その代わり、アルゴリズムEvAC は、プライバシーとユーティリティとの特異なトレードオフを達成する。ここでは、すべてのt ≦ m についてプライバシーに関し、ｌは、εの減少を抑え、およびユーティリティに関し、εは、ｌの増加を抑える、という上記の原理において与えられた正確な制限を達成する。
【００４８】
各時間の部分区間の継続とともになされる変数m の選択は、ソーシャルネットワーキングのウェブサイトの種類に実際に依存すべきである。例えば、時間間隔を１月に設定する場合、選択m ＝10（10月ごとに、彼のアクセス制御の設定の再考させるように、ユーザに明確に要求することを意味する）は、幾つかの有名なソーシャルネットワーキングのウェブサイトについて、かなり品質が良いように見える。
【００４９】
効用関数の選択は、具体的なソーシャルネットワーキングのウェブサイトにも依存すべきである。従って、単一の効用関数を定義し、それのための数字上の結果を示す代わりに、効用関数の十分で一般的な分類を定義し、その分類においてその関数のひとつが使用されると想定して原理１を証明した。
【００５０】
実質的な結果において、sは、１程度に小さくできる（たとえば、１つの写真、１つのコメント、１つのファイル）。一般的には、より小さいsは、同じプライバシーの変数t, εの場合、ユーティリティの変数ｌのより小さな選択が必要となるか、同じｌの場合、t, εはあまり求められないかのどちらかであろう。
【００５１】
図３を参照し、本発明を示すフロー図を示す。t = 0 のとき、ユーザが定義したパブリック／プライベート属性は、ユーザのmオブジェクト３０の各々に適用される。サーバは、ランダムな順列p ３１を各パブリックのオブジェクトd[1],..., d[m]３２へ適用する。結果は、クライアントのパブリックのオブジェクトd[p[1]],..., d[p[m]]３３である。時間の部分区間i（i = 1,..., m）において、サーバは、慎重に選択された値L＜m、およびクライアントのオブジェクトd[p[q[1]]],..., d[p[q[m]]]３５をもたらすランダムな順列q ３４を計算する。サーバは、すべてのオブジェクトの設定を０または後に（３６）となる時間におけるクライアントによりパブリックとみなす。選択された値およびランダムの順列を適用した後、サーバは、第１のLオブジェクトをパブリックとみなし、および残ったm−Lオブジェクトをプライベート３７とみなす。
【００５２】
図４は、上記記載の発明のブロック図を示す。サーバ４０は、ソーシャルネットワークにおけるすべてのオブジェクトを見ることができ、および各々のオブジェクトのパブリック／プライベート属性を再設定できる。クライアント４２1,...,４２cは、それの各々のオブジェクトのパブリック／プライベート属性を再設定できる。ソーシャルネットワーク４４は、各クライアントのプライベートのオブジェクトおよびパブリックのオブジェクトを含む。クライアントは、そのプライベートのオブジェクトだけを見ることができる。各クライアントは、パブリックのオブジェクトを見ることができる。
【００５３】
本開示のさまざまな態様は、コンピュータまたはマシンが使用または読取可能な媒体に具体化されるプログラム、ソフトウエア、またはコンピュータ命令として具体化されてもよく、それらの命令よってコンピュータまたはマシンに、コンピュータ、プロセッサ、および／またはマシン上で実行される場合にその方法のステップを行わせる。
【００５４】
本開示のシステムおよび方法は、汎用のコンピュータまたはコンピュータシステム上で実装および実行されてもよい。コンピュータシステムは、任意のタイプの周知のまたは今後知られるシステムであってもよく、通常は、プロセッサ、メモリデバイス、記憶デバイス、入力／出力デバイス、内部バス、および／または通信ハードウエアおよびソフトウエアと共に他のコンピュータシステムとの通信を行うための通信インタフェースなどを含んでもよい。モジュールは、デバイス、ソフトウエア、プログラムから成るコンポーネント、またはソフトウエア、ハードウエア、ファームウエア、電子回路などとして具体化することができる、ある「機能性」を実装するシステムであってもよい。
【００５５】
本願で使用され得る用語「コンピュータシステム」および「コンピュータネットワーク」は、固定および／またはポータブルなコンピュータハードウエア、ソフトウエア、周辺機器、および記憶デバイスによるさまざまな組み合わせを含んでもよい。コンピュータシステムは、ネットワーク化されるあるいは共同で行うためにリンクされる個々のコンポーネントから成る複数のコンポーネントを含んでもよいし、または１または複数のスタンドアロン型コンポーネントを含んでもよい。本願のコンピュータシステムのハードウエアおよびソフトウエアコンポーネントは、デスクトップ型、ラップトップ型、サーバなどの固定およびポータブルデバイス、および／または組み込みシステムを含んでもよいおよびその中に含まれてもよい。
【００５６】
アクセス制御を開発する手段による、ソーシャルネットワークにおける共有されたデータに起因したプライバシーの毀損を抑制する方法について説明したが、本原理から逸脱しなければ変更およびバリエーションが可能であり、本発明の広範囲の技術は、本特許請求の範囲によって唯一限定されることは当業者には明らかである。
【技術分野】
【０００１】
関連出願との相互参照
本出願は、参照によりその全体が本明細書に組み込まれる、２００９年８月１２日に出願した米国仮特許出願第６１／２３３，３２０号明細書の利益を主張する。
【０００２】
本発明は、ソーシャルネットワークにおいて共有されるデータに起因するプライバシーの毀損を抑制することに関する。
【背景技術】
【０００３】
ソーシャルネットワークにおいて近年、ソーシャルネットワーキングウェブサイト（例えば、Facebook（登録商標）, Myspace（登録商標）, Twitter（登録商標））を管理するビジネスが増加する傾向にある。ここでは、ユーザが、自由にユーザのデータ（画像、テキスト、ファイル等の）を投稿することができ、ウェブサイトへのアクセスするユーザの友人、仲間、どんな人とでも、それを共有できる。最も有名なサイトでは、数千万のユーザを惹き付けているので、サイトの悪用の招いた結果が、大手の新聞およびマスコミ関係に毎日のように記事になっている。典型的な悪用は、ユーザが、様々なタイプのセンシティブなデータ（恥ずかしい写真、政治的な非公式の意見、所有権に関する書類）のを偶然共有してしまうことであり、これにより、望まない結果（雇用および解雇についての決定に影響を与えることになる、医療の提供、保険の他の種類等）が引き起こされる。
【０００４】
将来の望まれない結果に対して、データをプライベートに保持するため、ユーザの要求（プライバシーと呼ばれる）と、それらのデータ（ユーティリティと呼ばれる）を共有するというユーザの要望とのバランスを取ることは、実際のソーシャルネットワークにおける大きな問題として理解されている。
【０００５】
理論上は、ユーザは、ユーティリティにかかる費用において（換言すれば、データを共有しないことによって）、プライバシーを維持でき、プライバシーにかかる費用において（換言すれば、すべての共有データのアクセスを制限しないことによって）、ユーティリティを最大限使用することができ、または、理論的に最良の方法であるが、現時点または将来において、望まれるデータのプライバシーを提供するアクセス制御のポリシーを絶え間なく実行することによって、プライバシーとユーティリティとのバランスを取ることができる。
【０００６】
後者の手法は、可能であれば、少なくとも２つの理由で実用的であると期待される。第１に、将来においてプライバシーを保持することが保証されるというポリシーを起草することは、複数の状況において難しい（すなわち、今日は問題ないデータでも明日はそうではない）かもしれないという理由であり、第２に、ソーシャルネットワークの目的に反している可能性はあるが、複雑となり得るプライバシーポリシーに完全に従うように、非常に大きなソーシャルネットワークのユーザに要求することは、複数の状況において、少しの成功もないかもしれないという理由である。事実、完全に遵守する単一のユーザの場合でさえ、このユーザのプライバシーは、他のユーザの動作によって、変更される可能性がある。概して、これは、ユーザを限定する１つのアクセス制御だけでは、受容できるプライバシーの解決とはなり得ないことを示している。
【０００７】
近年、ソーシャルネットワークの使用による信用およびプライバシーの問題の議論が続いている。さらに、新聞雑誌は、毎日これらの問題に注意を向けており、通常、脆弱なプライバシーから生じる望まれない事件について書いている。しかし、素早く実用的なプライバシーの毀損を抑制する“常識的な”の手法についても書かれている。数少ない研究論文は、ソーシャルネットワークにおける異なったプライバシーの問題の解決を、最近試みている。例えば、プライバシー保護における犯罪捜査は、Kerschbaum, F. and Schaad, A. “Privacy-preserving social network analysis for criminal investigations”, In Proc. of the 7th ACM Workshop on Privacy in the Electronic Society. WPES '08. ACM, New York, NY, 9-14において研究され、プライバシーの特徴付けは、Krishnamurthy, B. and Wills, C. “Characterizing Privacy in Online Social Networks”, In Proc.of ACM WOSN 2008において研究され、グラフベースのモデルにおけるプライバシーは、Korolova, A., Motwani, R., Nabar, S. U., and Xu, Y. 2008, “Link privacy in social networks”, In Proceeding of the 17th ACM Conference on Information and Knowledge Management. CIKM '08. ACM, New York, NY, 289-298において研究され、データが共有されている間、トゥルースフルネス（truthfulness）を促進するゲーム理論の構造は、Squicciarini, A. C, Shehab, M., and Paci, F. 2009. “Collective privacy management in social networks”, In Proceedings of the 18th international Conference on World Wide Web. WWW '09. ACM, New York, NY, 521-530.において、提案された。
【発明の概要】
【０００８】
本発明は、ソーシャルネットワーキングウェブサイトにおいて共有するデータに起因してプライバシーの毀損を妨げる方法およびソフトウエアを提供する。詳細には、さらに、上記のユーザ限定のアクセス制御に加えて、ソーシャルネットワークのユーザは、ユーザのデータの幾つかにアクセスすることを知的に限定することにより、ゆっくりと時間をかけて自動的に開発する、サーバ補助のアクセス制御の追加の層が提供され、並びにプライバシーおよびユーティリティについて、無駄のない定量化できる保証を提供する。アクセス制御は、プライバシーに対する確率保証を提供することにより、またはユーザからの任意の追加的な動作を必要としないことにより、ユーザ限定のアクセス制御の２つの言及される欠点を、特別に対象とする（従って、ユーザへの妨害および同じユーザにより偶然に発生した被害を同時に避ける）。いわゆる、本モデルは、一連の時間間隔から外れたらいつでも、プライベート（ソーシャルネットワークの限定された集合の間でだけ共有される）、またはパブリック（すべてのユーザの間で共有される）となることができる属性を有するデータオブジェクトの系として、ユーザが共有するデータベースを表す。このモデルにおいて、提案するサーバを補助するアクセス制御の実例は、プライベートまたはパブリックとしてユーザのデータオブジェクトの幾つかを、ランダムに再設定することによって、或いは過去および将来の属性の設定によって決定することによって各時間間隔において、アクセス制御のポリシーを自動的に更新する。言い換えれば、“開発するアクセス制御”と言われる、この構造は、ユーザが、消極的または不本意にプライバシー問題を取り扱う時間間隔において、データオブジェクトのプライバシーの属性が、設定されることを具体化する。属性は、ユーザ（いわゆる、ユーザは、彼の／彼女のお気に入りのプライバシーおよび／またはアクセス制御のポリシーの構造および実装を消すことができる）に強制せず、またはサーバによって設定される時、ユーティリティ（いわゆる、ユーザは、パブリックに設定された属性を有する、できるだけ多くのデータを残す）またはプライバシー（いわゆる、ユーザは、高い確率を持ったプライベートに設定された属性を有する、センシティブなデータの組み合わせを保持する）に対する、形式的に具体化された要求を定量化できることを保証する。
【０００９】
具体的には、センシティブなデータは、サーバに知られていない、さらに広く一般的には、ユーザに知られていない、ユーザのデータオブジェクトの任意のサブセットとしてモデル化される。
【００１０】
この方法は、確率的で、カバーフリーファミリー（cover-free families）の変化に基づいている。例において、まず、従来のカバーフリーファミリーは、目的に十分ではない（例えば、目的が、ユーティリティの要求を最大化する必要がない）ことが観察される。それから、無駄のない、かつ定量化できるユーティリティおよびプライバシーの特性である証明をすることが可能であるために、ランダム化されたサブセットの選択（後で信頼できる特性を有するカバーフリーファミリーとして分析される）のための既知の構造の変化が提案される。
【００１１】
本発明は、添付図面と併せて以下の明細書を読むと、より明らかに理解されるだろう。
【図面の簡単な説明】
【００１２】
【図１】n = 500, t = m = 10，s = 10 (セットアップ１) n = 400, t = m = 9, s = 10 (セットアップ２), n = 300, t = m = 8, s = 10 (セットアップ３)の時のｌの関数としたεの値の図表示である。ε< 0.001となるようなｌの最大値は、各々47, 41, および35である。
【図２】n = 500, m = 10, s = 10 (セットアップ１), n = 400, m = 9, s = 10 (セットアップ２), n = 300, m = 8, s = 10 (セットアップ３)の時のεの関数としたｌの値の図表示である。ｌ> 35となるようなεの最大値は、各々0.0014, 0.0032, および0.0098である。
【図３】本発明の修正されたフローチャート図である。
【図４】本発明を示した、簡略化したブロックダイアグラム図である。
【発明を実施するための形態】
【００１３】
ソーシャルネットワークは、データタイプに依存する可能性のあるソーシャルネットワークのユーザの異なるデータフォーマット、並びに異なる共有、およびアクセスポリシーを可能にする。次の形式により、我々は、より易しい記述および本発明のより広い適用性を後で促進するため、さらに簡易化された一般的なモデルを確保することを試みる。ソーシャルネットワークおよびネットワークの複数のメンバーの１人であるユーザUについて、集中型のソフトウエアを実行するサーバSを考える。
【００１４】
【００１５】
ここで、bj = パブリック（それぞれ，bj = プライベート）によって、データオブジェクトDjは、すべて（それぞれ限定された集合のみ）のソーシャルネットワークのユーザと共有されることを意味し、ここでは、限定された集合は、Uによって選択される。ソーシャルネットワークへの参加でUによって得られたユーティリティは、Uの具体的な特徴およびインタレストに依存する可能性がある。複数の実生活のソーシャルネットワークの根本的な原理の同意において、設定bj＝パブリックは、Uの視点から、設定bj＝プライベートより高いユーティリティを提供すると想定する。従って、ソーシャルネットワークへの参加におけるUのユーティリティを最大化する方法として設定bj＝パブリックである｛1,..., n｝からjの数を最大化することを考える。
【００１６】
しばしば、単一のデータオブジェクトは、センシティブの資料を十分提供できない可能性がある一方、複数のデータオブジェクトは、相互に関連があれば、そのように提供するとみなされる可能性がある。センシティブなデータについて合理的で単純な、および一般的なモデルを試みるため、データオブジェクトのナンバーｓの結合が、いずれセンシティブとなることが可能であると想定する。従って、s個のデータオブジェクト{Dj|j∈P}の少なくとも１つが、A(Dj) = プライベートを満たす場合、Uのプライバシーを維持することができると理解することにより、P ⊆｛1,..., n｝，|P| = sとしてセンシティブのサブセットを示す。
【００１７】
【００１８】
センシティブのサブセットにおける少なくとも１つのデータオブジェクトは、プライベートの属性を有するため、各時間の部分区間においてアクセス制御のアルゴリズムを、常に適合することによって、ユーザUは、プライバシー問題を解決することに留意すべきである。しかし、上記ですでに部分的に議論されたように、Uは、将来的にセンシティブなデータのオブジェクトのサブセットになるであろうことを知らなくても良いし、または必要ならばいつでも、アクセス制御のアルゴリズムの適合を利用できないとしても良いと想定する。続いて、実用的なアクセス制御のシステム（いわゆる臨時のパスワードの再設定）により、0およびTの経過時間において、Uは、アクセス制御のアルゴリズムの適合を利用できることを想定する。従って、［0，T］として表示される、十分に幅のある時間の区間を考慮し、およびそれをｍの等しい長さの部分区間にさらに分割する。時間依存を組み込むためbj；A(Dj)の上記の表記を補強する。具体的には、bij = A(I, Dj)は、i = 1,..., mおよびj = 1,..., nについて［0，T］のi番目の部分区間において、データオブジェクトDjの属性値を示す。さらに、データオブジェクトの送信時間においてj = 1,..., nにもかかわらずb0j = A(0, Dj) = パブリックを維持すると想定される。
【００１９】
【００２０】
本発明の目的は、ユーティリティおよびプライバシーの特性により、アクセス制御を開発するアルゴリズムを設計することを目的とする。
【００２１】
上記のユーザデータベースの場合において、ユーティリティの概念は、ユーザUに本来備わっており、アクセス制御のアルゴリズムの場合でさえ、i = 1,..., mおよびj = 1,..., nについてbi,1,..., bi,nの一般的な関数に関して、そのようなアルゴリズムのユーティリティを定義付けることができる。形式的に、任意の関数f :{0, 1}mxn →［0，1］について、アクセス制御を開発するアルゴリズムEvACは、f ({bi,1,..., bi,n}mi=1) = yである場合、f -ユーティリティ yを有する。ここでは、{bi,1,..., bi,n}mi=1 = EvAC (D1 ,..., Dn, m)となる。fは、アクセス制御を開発するアルゴリズムEvACのための（fを最適化するために、EvACは、設計され得ることを意味する）効用関数である。
【００２２】
できるだけ多くのソーシャルネットワークのユーザのためにユーティリティを確保することを試みる、より具体的な効用関数f を定義する。我々は、所与の（任意の与えられた時間において、データの値のより高い数の属性が、パブリックに設定されるとき、ユーティリティは、より高くなることを意味する）時間の部分区間におけるドキュメントの数、および（時間の部分区間のより高い数の間で、任意で与えられるドキュメントの属性が、パブリックに設定されるとき、ユーティリティは、より高くなることを意味する）所与のドキュメントのための時間の部分区間の数の両方を超えて、ユーザのデータベースの場合のためになされる結論を拡張する（いわゆる、ユーティリティは、公開してアクセスできるデータの値の数が増える時に、増える）。
【００２３】
まず、bi = (bi,1,..., bi,n)およびbj = (bi,j,..., bm,j)並びに各々のハミング重み、
【００２４】
【数１】
【００２５】
の表記を定義する。また、任意の整数p, x について、I ≧ p(x)に測定器のしきい値関数を表示させ、x ≧ p およびほかの0である場合、1と等しいとして定義される。全ての整数p, q 、およびNから［0，1］までの単調増加関数g, hについて、効用関数を定義する。
【００２６】
【数２】
【００２７】
これは、しきい値ベースの効用関数と言われている。
【００２８】
以下の記載において、目的は、しきい値ベースの効用関数を最大化するアクセス制御を開発するアルゴリズムの設計である。理想的には、より幅広い一般化のため、p, q, g, hについての具体的な設定に独立してなされる。プライバシーの要求が拒否された場合、すべてのi, jについて、bij = パブリックにいつも設定するアルゴリズムは、この目的を自明に達成することに留意すべきである。
【００２９】
ユーザデータベースの場合に議論される直観を拡張して、次に、我々は、アクセス制御を開発するアルゴリズムだけが、多量の時間の部分区間中、或いは全体の時間の区間［0, T］の間、小さな可能性を有するパブリックとしてセンシティブのベクトルのすべての成分を設定するという事実を形式化する。言い換えれば、我々は、｛1,..., m｝におけるi の値の幾つか、或いはすべてについて、アクセス制御を開発するアルゴリズムの出力からベクトルbiを収集するように、プライバシーの侵害を企てる敵対者さえも考慮する。この攻撃でさえ考慮して本発明を使用することにより、この敵対者が、センシティブのベクトルを再構築できる確率を低減する。
【００３０】
形式的に、P ⊆｛1,..., n｝をs −サイズのセンシティブのサブセットとし、tを敵対者の攻撃を被る時間の部分区間の数とする。任意のi1,..., it∈｛1,..., m｝の場合に、すべてのj∈P について、Viti=i1（bij = パブリック）が、成り立つ確率は、εが最大となるとき、任意のε> 0について、アクセス制御を開発するアルゴリズムEvAC は、（t, ε）−プライバシーを満たす。ベクトルP は、任意にモデル化することができ、およびより広い一般化のため、U およびS 両方に不知である（U が理論的に、データがセンシティブであるか否かを示す最良の位置にいるとしても、ニュースの出来事においてよく記録されるように、U は、現在または将来の時間に関してさえも、最良の決定をすることができないと、我々は、より実質的な観察をする）。P のサイズｓは、アクセス制御を開発するアルゴリズムへ知られると想定する（これが、一般に成り立たなくても、この例は、|P|を上限としてｓを設定する必要があることを示すためにも必要である）。結局モデルのベクトルP は、アルゴリズムEvAC、またはその出力によって、独立して選択される（確かに、形式的には、この定義のバージョンを定義するが、P はEvAC によって返された出力に依存する）。
【００３１】
以下の説明の目的は、EvACが、（t, ε）−プライベートであることについて、ｔを最大化すると同時に、εを最小化するアルゴリズムEvACを設計することである。ユーティリティの要求が無視されても、すべてのi; j についてbij = パブリックと常に設定するアルゴリズムは、自明にこの目的を達成する。従って、発明の目的は、（t, ε）−プライベートとｆ−ユーティリティとのトレードオフを達成することである。
【００３２】
以下の例において、簡易なEvACアルゴリズムは、ほぼカバーフリーファミリーの既知の分類の変形に基づいている。
【００３３】
本発明の主な概要は、センシティブのサブセットPにおけるデータオブジェクトの少なくとも１つの属性を、できるだけ多量の時間の部分区間中、或いは全体の時間の区間［0, T］の間、プライベートに設定し続けることを保証することである。目的を達成することについて、カバーフリーファミリーは、自然な解決ツールと考えられる。さらに、プライバシーを侵害する攻撃を実行するのにかかる時間を最大化する、およびすべてのデータオブジェクトが、最終的にパブリックに設定される確率を最小化する、並びに適切なしきい値ベースの効用関数（パブリックに設定されたデータオブジェクトの数の関数として）を最大化する、プライバシーおよびユーティリティの変数に関して、以下の３つの目的をさらに達成することが好ましい。第１の目的は、カバーフリーのサブセットの選択が、[0, T]の時間の部分区間mの各々において変化することを示すことである。第２の目的および第３の目的は、程度の良いカバーフリーである特性を有する、およびカバーフリーの各々のサブセットの最大限のサイズを有するファミリーの選択を示すことである。カバーフリーファミリーの定義は以下の通りである。
【００３４】
n, m, kを正の整数として、Gをサイズｎのグラウンド（ground）の集合とし、およびF = {S1,..., Sk}をGのサブセットのファミリーとする。
【００３５】
【００３６】
そして、Fにおける各々のサブセットが、Fにおける任意のｍの他のサブセットの集合によりカバーされない場合、ファミリーFは、G以上にｍ−カバーフリーとなる。
【００３７】
カバーフリーファミリーについて幾つかの結果が知られている。例えば、Erdos, P., Frankl P. and Furedi Z, “Families of finite sets in which no set is covered by the union of r others”In Israeli Journal of Mathematics, 51 : 79-89, 1985において知られており、決定論的なアルゴリズムが存在し、任意の固定されたｍ, ｌについて、ｌ= [n/4m]and n ≦16m2 (1+log(k/2)/log3)について、m−カバーフリー、ｋ−サイズ、サイズｎのグラウンドの集合以上のｌ−サイズのベクトルのファミリーFを構成する。
【００３８】
本実施例では、カバーフリーファミリーのブラックボックス（a black-box）の適用は、問題を解決できないだろう、３つの理由は以下の通りである。
１．カバーされるサブセット（いわゆるセンシティブのサブセット）は、サイズｓを有し、このとき、サブセット（いわゆるi = 1,..., mについて属性値の集合）をカバーすることは、サイズｌを有し、通常ではｌ≠sとなる（ｌを最大化するよう試みるとき）。
２．カバーされるサブセット（いわゆるセンシティブのサブセット）は、{0, 1}nの任意のサブセットとなり得るが、カバーフリーの設定では、通常では、このケースにはなり得ない。
３．センシティブのサブセットがカバーされない明確な確率が低いのは、確かだが、これは、任意のカバーフリーファミリーにおけるケースではない。
【００３９】
３番目の理由は、カバーフリーファミリーを使用するより良い性能を有する構造を得られるかもしれないことを示唆する。１番目の理由は、知られているカバーフリーファミリーの変形を使用することができるかもしれないことを示唆し、２番目の理由は、これらの間の検索を規制する。この例の構造は、簡易なランダム化された構造のわずかな変形であり、複数の異なるコンテキストにおいてすでに使用されており、Garay, J., Staddon, J.andWool, A. “Long-live Broadcast Encryption”, In Proc. of Crypto 2000, LNCS, Springer- Verlagにおいて示した、（ほとんど）カバーフリーファミリーである。
【００４０】
アクセス制御を開発するアルゴリズムEvACの例は、入力データオブジェクトD1 ,..., Dnおよび時間間隔のmの番号を受け取る。
【００４１】
まず、UのデータオブジェクトD1 ,..., Dnは、ランダムに順序を変える。直感的に、これは、センシティブのサブセットPの分布が、{0, 1}nからｓ−サイズのサブセットの全体にわたって等しくなることを保証する。この事実は、ユーティリティおよびプライバシーの分析をさらに簡略化し、ユーティリティおよびプライバシーの変数の改善を助ける。
【００４２】
次に、アルゴリズムは、以下のように、i = 1,..., m およびｊ = 1,..., n について属性値bijを計算する。i∈{1,..., m}の各々について、確かな値j1,..., jlの数ｌは、均一に、{0, 1}nから独立して選択され、次に、bij は、パブリックと等しく設定されるか、プライベートと等しく設定される。ここで、ｌは変数であり、n, m, s, εに依存し、図のユーティリティの特性の分析において設定される（そして、最大化される）。事実、s の正確な値を知る必要はない。s の上限で十分だろう。
【００４３】
上記記載したプライバシーおよびユーティリティの特性の証明を、図１および図２を参照して示す。図１は、n = 500, t = m = 10， s = 10 (セットアップ１) n = 400, t = m = 9, s = 10 (セットアップ２), n = 300, t = m = 8, s = 10 (セットアップ３)の時のｌの関数としたεの値を表す。ε< 0.001となるようなｌの最大値は、各々47, 41, および35である。図２は、n = 500, m = 10, s = 10 (セットアップ１), n = 400, m = 9, s = 10 (セットアップ２), n = 300, m = 8, s = 10 (セットアップ３)の時のεの関数としたｌの値を表す。ｌ> 35となるようなεの最大値は、各々0.0014, 0.0032, および0.0098である。
【００４４】
原理１
U に、n データオブジェクトを有するソーシャルネットワークのデータベースを待たせる。m 時間間隔を超えて、上記のアルゴリズムEvAC は、与えられた時間≦ｌにおいて保持し、パブリックに設定する属性を記録し、および任意のt ≦ mについて（t, ε）−プライバシーを満たすアクセス制御を開発するアルゴリズムであり、
【００４５】
【数３】
【００４６】
s（上限）は、センシティブのサブセットの長さである。ε1/s＞１−（１−２／n）mの範囲ならばいつでも、アルゴリズムEvACは、ｇ−ユーティリティを満たし、ｇは、しきい値ベースの効用関数であり、
ｌ＜ｎ（１−（１−ε1/s）1/m）
のような一番幅広い値ｌによって最大化される。
【００４７】
この原理は、プライバシーとユーティリティとのトレードオフに関し、および変数設定に関し、以下の通り最適に説明するように貢献する。独立したプライバシーの最大化は、すべてのi, jについて、bij = プライベートに設定されたアクセス制御のアルゴリズムによって与えられ、従って（m, 0）−プライバシーを達成しユーティリティを最小限とする。同様に、独立したユーティリティの最大化は、すべてのi, j について、bij =パブリックに設定されたアクセス制御のアルゴリズムによって与えられ、従って、（しきい値ベースの効用関数を含む）効用関数の幅広い分類について最大限のユーティリティを達成するが、任意のε＜1について（1, ε）−プライバシーは満たさない。その代わり、アルゴリズムEvAC は、プライバシーとユーティリティとの特異なトレードオフを達成する。ここでは、すべてのt ≦ m についてプライバシーに関し、ｌは、εの減少を抑え、およびユーティリティに関し、εは、ｌの増加を抑える、という上記の原理において与えられた正確な制限を達成する。
【００４８】
各時間の部分区間の継続とともになされる変数m の選択は、ソーシャルネットワーキングのウェブサイトの種類に実際に依存すべきである。例えば、時間間隔を１月に設定する場合、選択m ＝10（10月ごとに、彼のアクセス制御の設定の再考させるように、ユーザに明確に要求することを意味する）は、幾つかの有名なソーシャルネットワーキングのウェブサイトについて、かなり品質が良いように見える。
【００４９】
効用関数の選択は、具体的なソーシャルネットワーキングのウェブサイトにも依存すべきである。従って、単一の効用関数を定義し、それのための数字上の結果を示す代わりに、効用関数の十分で一般的な分類を定義し、その分類においてその関数のひとつが使用されると想定して原理１を証明した。
【００５０】
実質的な結果において、sは、１程度に小さくできる（たとえば、１つの写真、１つのコメント、１つのファイル）。一般的には、より小さいsは、同じプライバシーの変数t, εの場合、ユーティリティの変数ｌのより小さな選択が必要となるか、同じｌの場合、t, εはあまり求められないかのどちらかであろう。
【００５１】
図３を参照し、本発明を示すフロー図を示す。t = 0 のとき、ユーザが定義したパブリック／プライベート属性は、ユーザのmオブジェクト３０の各々に適用される。サーバは、ランダムな順列p ３１を各パブリックのオブジェクトd[1],..., d[m]３２へ適用する。結果は、クライアントのパブリックのオブジェクトd[p[1]],..., d[p[m]]３３である。時間の部分区間i（i = 1,..., m）において、サーバは、慎重に選択された値L＜m、およびクライアントのオブジェクトd[p[q[1]]],..., d[p[q[m]]]３５をもたらすランダムな順列q ３４を計算する。サーバは、すべてのオブジェクトの設定を０または後に（３６）となる時間におけるクライアントによりパブリックとみなす。選択された値およびランダムの順列を適用した後、サーバは、第１のLオブジェクトをパブリックとみなし、および残ったm−Lオブジェクトをプライベート３７とみなす。
【００５２】
図４は、上記記載の発明のブロック図を示す。サーバ４０は、ソーシャルネットワークにおけるすべてのオブジェクトを見ることができ、および各々のオブジェクトのパブリック／プライベート属性を再設定できる。クライアント４２1,...,４２cは、それの各々のオブジェクトのパブリック／プライベート属性を再設定できる。ソーシャルネットワーク４４は、各クライアントのプライベートのオブジェクトおよびパブリックのオブジェクトを含む。クライアントは、そのプライベートのオブジェクトだけを見ることができる。各クライアントは、パブリックのオブジェクトを見ることができる。
【００５３】
本開示のさまざまな態様は、コンピュータまたはマシンが使用または読取可能な媒体に具体化されるプログラム、ソフトウエア、またはコンピュータ命令として具体化されてもよく、それらの命令よってコンピュータまたはマシンに、コンピュータ、プロセッサ、および／またはマシン上で実行される場合にその方法のステップを行わせる。
【００５４】
本開示のシステムおよび方法は、汎用のコンピュータまたはコンピュータシステム上で実装および実行されてもよい。コンピュータシステムは、任意のタイプの周知のまたは今後知られるシステムであってもよく、通常は、プロセッサ、メモリデバイス、記憶デバイス、入力／出力デバイス、内部バス、および／または通信ハードウエアおよびソフトウエアと共に他のコンピュータシステムとの通信を行うための通信インタフェースなどを含んでもよい。モジュールは、デバイス、ソフトウエア、プログラムから成るコンポーネント、またはソフトウエア、ハードウエア、ファームウエア、電子回路などとして具体化することができる、ある「機能性」を実装するシステムであってもよい。
【００５５】
本願で使用され得る用語「コンピュータシステム」および「コンピュータネットワーク」は、固定および／またはポータブルなコンピュータハードウエア、ソフトウエア、周辺機器、および記憶デバイスによるさまざまな組み合わせを含んでもよい。コンピュータシステムは、ネットワーク化されるあるいは共同で行うためにリンクされる個々のコンポーネントから成る複数のコンポーネントを含んでもよいし、または１または複数のスタンドアロン型コンポーネントを含んでもよい。本願のコンピュータシステムのハードウエアおよびソフトウエアコンポーネントは、デスクトップ型、ラップトップ型、サーバなどの固定およびポータブルデバイス、および／または組み込みシステムを含んでもよいおよびその中に含まれてもよい。
【００５６】
アクセス制御を開発する手段による、ソーシャルネットワークにおける共有されたデータに起因したプライバシーの毀損を抑制する方法について説明したが、本原理から逸脱しなければ変更およびバリエーションが可能であり、本発明の広範囲の技術は、本特許請求の範囲によって唯一限定されることは当業者には明らかである。
【特許請求の範囲】
【請求項１】
データを共有するソーシャルネットワークにおけるプライバシーの毀損を抑制する方法であって、
アクセス制御のポリシーに従って、ユーザ間でデータオブジェクトを共有するために該ユーザのデータオブジェクトを含むソーシャルネットワークを提供するステップと、
一連の時間の部分区間に、時間を分割するステップと、
パブリックまたはプライベートとして前記データオブジェクトの幾つかをランダムに再設定することにより、各々の時間の部分区間における前記アクセス制御のポリシーを更新するステップと、
を備えることを特徴とする方法。
【請求項２】
前記更新するステップは、過去の属性の設定に依存することを特徴とする請求項１に記載の方法。
【請求項３】
前記データオブジェクトは、画像であることを特徴とする請求項１に記載の方法。
【請求項４】
前記データオブジェクトは、テキストであることを特徴とする請求項１に記載の方法。
【請求項５】
前記データオブジェクトは、コンピュータファイルであることを特徴とする請求項１に記載の方法。
【請求項６】
データオブジェクトのセンシティブのサブセットは、可能な時間の区間の数の間、プライベートに設定されることを特徴とする請求項１に記載の方法。
【請求項７】
データを共有するソーシャルネットワークにおけるプライバシーの毀損を抑制するコンピュータで動作する、コンピュータで読み取り可能なプログラムコードを有するコンピュータで読取可能な媒体であって、
アクセス制御のポリシーに従って、ユーザ間でデータオブジェクトを共有するために該ユーザのデータオブジェクト含むソーシャルネットワークを提供する手段と、
一連の時間の部分区間に、時間を分割する手段と、
パブリックまたはプライベートとして前記データオブジェクトの幾つかをランダムに再設定することにより、各々の時間の部分区間における前記アクセス制御ポリシーを更新する手段と、
を備えたことを特徴とする媒体。
【請求項８】
前記更新する手段は、過去の属性の設定に依存することを特徴とする請求項７に記載の媒体。
【請求項９】
データオブジェクトのセンシティブのサブセットは、可能な時間の区間の数の間、プライベートに設定されることを特徴とする請求項７に記載の媒体。
【請求項１】
データを共有するソーシャルネットワークにおけるプライバシーの毀損を抑制する方法であって、
アクセス制御のポリシーに従って、ユーザ間でデータオブジェクトを共有するために該ユーザのデータオブジェクトを含むソーシャルネットワークを提供するステップと、
一連の時間の部分区間に、時間を分割するステップと、
パブリックまたはプライベートとして前記データオブジェクトの幾つかをランダムに再設定することにより、各々の時間の部分区間における前記アクセス制御のポリシーを更新するステップと、
を備えることを特徴とする方法。
【請求項２】
前記更新するステップは、過去の属性の設定に依存することを特徴とする請求項１に記載の方法。
【請求項３】
前記データオブジェクトは、画像であることを特徴とする請求項１に記載の方法。
【請求項４】
前記データオブジェクトは、テキストであることを特徴とする請求項１に記載の方法。
【請求項５】
前記データオブジェクトは、コンピュータファイルであることを特徴とする請求項１に記載の方法。
【請求項６】
データオブジェクトのセンシティブのサブセットは、可能な時間の区間の数の間、プライベートに設定されることを特徴とする請求項１に記載の方法。
【請求項７】
データを共有するソーシャルネットワークにおけるプライバシーの毀損を抑制するコンピュータで動作する、コンピュータで読み取り可能なプログラムコードを有するコンピュータで読取可能な媒体であって、
アクセス制御のポリシーに従って、ユーザ間でデータオブジェクトを共有するために該ユーザのデータオブジェクト含むソーシャルネットワークを提供する手段と、
一連の時間の部分区間に、時間を分割する手段と、
パブリックまたはプライベートとして前記データオブジェクトの幾つかをランダムに再設定することにより、各々の時間の部分区間における前記アクセス制御ポリシーを更新する手段と、
を備えたことを特徴とする媒体。
【請求項８】
前記更新する手段は、過去の属性の設定に依存することを特徴とする請求項７に記載の媒体。
【請求項９】
データオブジェクトのセンシティブのサブセットは、可能な時間の区間の数の間、プライベートに設定されることを特徴とする請求項７に記載の媒体。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公表番号】特表２０１３−５０６１６９（Ｐ２０１３−５０６１６９Ａ）
【公表日】平成２５年２月２１日（２０１３．２．２１）
【国際特許分類】
【出願番号】特願２０１２−５２４８６７（Ｐ２０１２−５２４８６７）
【出願日】平成２２年８月１２日（２０１０．８．１２）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０４５３１５
【国際公開番号】ＷＯ２０１１／０１９９１０
【国際公開日】平成２３年２月１７日（２０１１．２．１７）
【出願人】（３９９０４７９２１）テルコーディア テクノロジーズ インコーポレイテッド (61)
【公表日】平成２５年２月２１日（２０１３．２．２１）
【国際特許分類】
【出願日】平成２２年８月１２日（２０１０．８．１２）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０４５３１５
【国際公開番号】ＷＯ２０１１／０１９９１０
【国際公開日】平成２３年２月１７日（２０１１．２．１７）
【出願人】（３９９０４７９２１）テルコーディア テクノロジーズ インコーポレイテッド (61)
[ Back to top ]