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