1. Improving Privacy in Graphs Through Node Addition
- Author
-
Lixin Gao, Xiaozhe Shao, Hossein Pishro-Nik, and Nazanin Takbiri
- Subjects
FOS: Computer and information sciences ,Information privacy ,Computer Science - Cryptography and Security ,Degree (graph theory) ,Computer science ,business.industry ,Computer Science - Information Theory ,Information Theory (cs.IT) ,Data_MISCELLANEOUS ,020206 networking & telecommunications ,02 engineering and technology ,Adversary ,16. Peace & justice ,Computer security ,computer.software_genre ,Graph ,0202 electrical engineering, electronic engineering, information engineering ,Peer to peer computing ,020201 artificial intelligence & image processing ,The Internet ,business ,computer ,Cryptography and Security (cs.CR) ,Anonymity - Abstract
The rapid growth of computer systems which generate graph data necessitates employing privacy-preserving mechanisms to protect users' identity. Since structure-based de-anonymization attacks can reveal users' identity's even when the graph is simply anonymized by employing naive ID removal, recently, $k-$anonymity is proposed to secure users' privacy against the structure-based attack. Most of the work ensured graph privacy using fake edges, however, in some applications, edge addition or deletion might cause a significant change to the key property of the graph. Motivated by this fact, in this paper, we introduce a novel method which ensures privacy by adding fake nodes to the graph. First, we present a novel model which provides $k-$anonymity against one of the strongest attacks: seed-based attack. In this attack, the adversary knows the partial mapping between the main graph and the graph which is generated using the privacy-preserving mechanisms. We show that even if the adversary knows the mapping of all of the nodes except one, the last node can still have $k-$anonymity privacy. Then, we turn our attention to the privacy of the graphs generated by inter-domain routing against degree attacks in which the degree sequence of the graph is known to the adversary. To ensure the privacy of networks against this attack, we propose a novel method which tries to add fake nodes in a way that the degree of all nodes have the same expected value., Comment: Graph Privacy
- Published
- 2019
- Full Text
- View/download PDF