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

MkECS の応用だ!!!!

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