Improving Privacy in Graphs Through Node Addition
Title | Improving Privacy in Graphs Through Node Addition |
Publication Type | Conference Paper |
Year of Publication | 2019 |
Authors | Takbiri, Nazanin, Shao, Xiaozhe, Gao, Lixin, Pishro-Nik, Hossein |
Conference Name | 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton) |
Keywords | anonymity 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. |
DOI | 10.1109/ALLERTON.2019.8919967 |
Citation Key | takbiri_improving_2019 |
- Privacy-Preserving Mechanism (PPM)
- k- automorohism
- k- isomorphism
- Measurement
- Metrics
- naïve ID removal
- node addition
- Peer-to-peer computing
- Predictive Metrics
- privacy
- privacy models and measurement
- k- anonymity
- privacy-preserving mechanisms
- pubcrawl
- Resiliency
- Routing
- Scalability
- seed-based attack
- strongest attacks
- structural attack
- structure-based attack
- structure-based de-anonymization attacks
- edge addition
- anonymity privacy
- anonymization and de-anonymization
- attack graphs
- Autonomous System (AS)level graph
- composability
- computer security
- Control Theory and Privacy
- cyber-physical systems
- data privacy
- degree attacks
- Computing Theory and Privacy
- fake edges
- fake nodes
- graph data
- graph data necessitates
- graph privacy
- graph theory
- Human behavior
- Inter-domain routing
- internet