Wherefore Art Thou R3579X? Anonymized Social Networks, Hidden Patterns, and ... - todo314 @ ウィキ

Wherefore Art Thou R3579X? Anonymized Social Networks, Hidden Patterns, and Structural Steganography

• Lars Backstrom, Cynthia Dwork, Jon Kleinberg
• In WWW 2007

概要

• ネットワークを公開する際、その匿名性は名前を隠すだけで十分か？
• 攻撃者が事前に複数のノード、リンクを仕込んでいた場合、ばれちゃう
• 実験では意外と少ないノードを用意するだけで同定できることを示した

Walk-Based Attack

概要

• グラフをG=(V,E)
• x1,x2,…,xk: 作ったノード、Hをxiからなるグラフとする
• w1,w2,…,wk: リンク関係を知りたいノード
  • {wi,wj}があるかを知りたい
• {xi,wi}をそれぞれ結ぶ
  • 友達申請とか、アドレス帳登録とかフォローとか色々
• x同士は基本ランダムグラフにする
• さらに、{xi,xi+1}をリンクしたり、次数を変えてやったりする
  • 同定しやすくするため
• 良いグラフHとは？

1. 他のノード集合S \subset Vとisomorphicでない
2. Vから簡単に見つけられる
3. 自身とも自明にisomorphicになる写像がない

定理

• 定理2.1
  • k: (2+δ)log n
  • 高確率でX={xi}はユニーク（同型なのない）
• 定理2.2
  • 探索木の大きさはO(n^{1+eps})

実験

• LiveJournalでやる
• kの値
  • 6で0.5になって、7で一気に上る
  • 意外と小さくて良い
• 効率
  • 次数がおなじになるのが少ないせいか速い？

Cut-Based Attack

• O(√log n)でできる！
• Hの構築に工夫
• min-cut使う

Passive Attack

• ノード、リンクは作れない
• 自分がどこか見つける

まとめ

• ネトストが捗る
• Facebookで謎の友達申請とかもこういうのができるからだよなー
  • （Twitterは知らんが
• ランダムグラフはこういうところで上手く使えるんだなーとおもった
  • 与えられたグラフが何であろうと問題ない

WWW anonymization

2013-10-23 14:41:31 (Wed)