Session 17: Privacy and Protection 【VLDB2011勉強会】 Session 17: Privacy and Protection 担当： 李重頡，駒水孝裕，冨山克裕　（筑波大学）

1. Yuan et al. Personalized Privacy Protection in Social Networks Data publishing of Social Network data set Privacy concerns in data publishing The service provider of SN (e.g. Facebook) is responsible for protecting the privacy of data while providing useful data Personalized privacy requirements Different attackers have different background knowledge Different users may have different privacy requirements Multi-level privacy protection (3 level) Address the shortcoming of single-level protection in previous research Session 17: Privacy and Protection 担当：李，駒水，冨山（筑波大）

1. Yuan et al. Personalized Privacy Protection in Social Networks Target: k-anonymous graph For each node u, the probability that an attacker re-identifies u is at most 1/k Level 1 protection Attacker knows u’s label  Grouping nodes under SGC (safety grouping condition, pp3) Level 2 protection Attacker also knows u’s degree  Adding noise node and edges Level 3 protection Attacker also knows u’s edge labels  Generalizing the edges Bob is a 26-year-old guy Session 17: Privacy and Protection 担当：李，駒水，冨山（筑波大）

1. Yuan et al. Personalized Privacy Protection in Social Networks Experiments Utility measurement Average relative error -- querying anonymized data Degree distribution Conclusion Varied privacy requirements Combination of structure techniques(graph editing) and micro data protection techniques(generalization) Session 17: Privacy and Protection 担当：李，駒水，冨山（筑波大）

2. Chen et al. Publishing Set-Valued Data via Differential Privacy Publishing set-valued data for data mining tasks Set-valued data: each record is a set of items drawn from a universe of items High dimensionality K-anonimity/ Differential Privacy (Stronger) An approach for non-interactive algorithm under differential privacy model Differential Privacy Outcome of any analysis should not depend on single record Session 17: Privacy and Protection 担当：李，駒水，冨山（筑波大）

2. Chen et al. Publishing Set-Valued Data via Differential Privacy Main idea Add noise to input data Top-down partitioning with taxonomy tree Divide the privacy budget(noise) to groups Session 17: Privacy and Protection 担当：李，駒水，冨山（筑波大）

3. Karwa et al. Private Analysis of Graph Structure グラフ構造を持つデータにおけるプライバシー保護 想定するクエリ：サブグラフ (triangles, k-triangles, k-star) のカウント 差分プライバシー (differential privacy) Aさんが入っているDBとAさんが入っていないDBに対してある計算を したときに結果があまり変わらないようにするプライバシー保護手法． 今回の場合：グラフのエッジがAさんに相当 Output Perturbation で差分プライバシーを実現する． ラプラス分布やコーシー分布に基づいたノイズを結果に与える． この論文がしたこと 2つのアルゴリズム，NP困難の証明，差分プライバシー手法の評価 サンプル triangle: 3 2-triangle: 2 3-triangle: 0 2-star: 18 3-star: 12 Session 17: Privacy and Protection 担当：李，駒水，冨山（筑波大）

3. Karwa et al. Private Analysis of Graph Structure Sensitivity を入力としてラプラス（コーシー）分布で計算したノ イズを結果に足し合わせる． Local Sensitivity あるグラフ G との距離（異なるエッジの本数）が 1 のグラフ G’ との間であ るユーザクエリ f の値の差の最大値 Smooth Sensitivity Local Sensitivity にグラフ間距離に基づいたノイズを合わせたもの． 論文の内容 Smooth Sensitivityを計算するアルゴリズム triangles, k-star グラフデータにおける差分プライバシーのアルゴリズム 詳しくはフルバージョンのペーパーで  [9] Session 17: Privacy and Protection 担当：李，駒水，冨山（筑波大）

Session 17: Privacy and Protection 担当：李，駒水，冨山（筑波大） ※図は論文から引用 4. Blaustein et al. Surrogate Parenthood: Protected and Informative Graphs グラフ構造データ センシティブ情報を含むことが多い 隠蔽方法：センシティブ情報を含むノード/エッジを消去 ⇒僅かなノード/エッジの消去が，多くのパスを到達不能にする （有用性 “低”） この論文でしたこと センシティブ情報を保護しつつ，元のグラフGの接続性を最大限に 維持したグラフG’を作成する グラフの有用性を測るための指標の導入 オリジナルのグラフG ユーザの権利を示したグラフ ”High-2”に対して公開される 保護されたグラフG’ Session 17: Privacy and Protection 担当：李，駒水，冨山（筑波大）

Session 17: Privacy and Protection 担当：李，駒水，冨山（筑波大） 4. Blaustein et al. Surrogate Parenthood: Protected and Informative Graphs Surrogate Node 元のグラフに対して，センシティブ情報を削ったノード Surrogate Edge 元グラフGから，複数の保護されたグラフG’を作ることが可能 有用性が最大のものを選ぶ必要がある Name: Joe Phone: 123-456-7890 Original Hide Surrogate Original Hide Surrogate Session 17: Privacy and Protection 担当：李，駒水，冨山（筑波大）

Session 17: Privacy and Protection 担当：李，駒水，冨山（筑波大） ※式は論文から引用 4. Blaustein et al. Surrogate Parenthood: Protected and Informative Graphs Utility Measure オリジナルのグラフGと保護されたグラフG’とでエッジの接続性と ノードの情報量を比較し，グラフG’の有用性を評価 Opacity Measure 攻撃者が保護されたグラフG’を基に，削除されたパスを復元できる 可能性を評価 Session 17: Privacy and Protection 担当：李，駒水，冨山（筑波大）

Session 17: Privacy and Protection 担当：李，駒水，冨山（筑波大） ※図は論文から引用 4. Blaustein et al. Surrogate Parenthood: Protected and Informative Graphs Evaluation 単純な７種類のグラフを用意 それぞれ１本のセンシティブなエッジを持つ センシティブなエッジを削除／サロゲート したグラフでUtilityとOpacityを比較 サロゲートエッジを用いた場合の方が Utility・Opacityの値いずれも同等以上 論文中では，これらのグラフを組合わせた 複雑なグラフについても評価 Original Hide Surrogate Session 17: Privacy and Protection 担当：李，駒水，冨山（筑波大）