Visible to the public Improving Privacy in Graphs Through Node Addition

TitleImproving Privacy in Graphs Through Node Addition
Publication TypeConference Paper
Year of Publication2019
AuthorsTakbiri, Nazanin, Shao, Xiaozhe, Gao, Lixin, Pishro-Nik, Hossein
Conference Name2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)
Keywordsanonymity privacy, anonymization and de-anonymization, Attack Graphs, Autonomous System (AS)level graph, composability, computer security, Computing Theory and Privacy, Control Theory and Privacy, Cyber-physical systems, data privacy, degree attacks, edge addition, fake edges, fake nodes, graph data, graph data necessitates, graph privacy, graph theory, Human Behavior, Inter-domain routing, Internet, k- anonymity, k- automorohism, k- isomorphism, Measurement, Metrics, naïve ID removal, node addition, Peer-to-peer computing, Predictive Metrics, privacy, privacy models and measurement, Privacy-Preserving Mechanism (PPM), privacy-preserving mechanisms, pubcrawl, Resiliency, Routing, Scalability, seed-based attack, strongest attacks, structural attack, structure-based attack, structure-based de-anonymization attacks
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.

DOI10.1109/ALLERTON.2019.8919967
Citation Keytakbiri_improving_2019