Wherefore Art Thou R3579X?: Anonymized Social Networks, Hidden Patterns, and Structural Steganography (WWW'07)

MkECS の応用だ!!!!

• 概要
  • 頂点に適当な ID を割り当てるだけの匿名化は不十分である
  • （タイトルはロミオとジュリエットのセリフで名前をIDに置き換えている）
  • 攻撃
    • b 頂点を特定したい
    • active attack: 匿名化前にグラフを操作して，匿名化後，特定頂点のラベルを特定
    • passive attack: 匿名化前は何もしない
    • semi-passive: ターゲットへの出辺だけ追加できる
  • 結果：少しの操作（７頂点＋辺追加）で攻撃ができた
• active attack
  • 適当に頂点を追加する，適当に辺を追加する，そのサブグラフ H を使って発見
  • walk-based attack, cut-based attack
  • 定理：そこそこの小さいサイズで，唯一な isomorphic なグラフにできる！（すごい）
  • cut-based attack は MkECS を求める感じだ！！！
• passive attack：一人じゃきついので，k 人でグルであることにする
• semi-passive attack: グルからターゲットに辺が張れる