Abstract
This paper establishes the first formal logical framework for anonymizing Linked Data (RDF) with provable guarantees. It introduces "linkage safety," a rigorous standard ensuring that anonymized data remains private even when combined with arbitrary external datasets. The authors map out the computational complexity of verifying and optimizing these anonymizations under both open-world and closed-world assumptions.
The Challenge of Linked Data Privacy
The Linked Data paradigm facilitates data connectivity across the web, which, while beneficial for research, presents significant privacy risks. Traditional anonymization techniques, such as removing names, often fail due to linkage attacks. In these scenarios, an attacker combines a seemingly "safe" dataset (e.g., anonymized medical records) with public information (e.g., voter registration lists) to re-identify individuals.
Existing privacy techniques like $k$-anonymity were designed for structured relational tables and do not translate effectively to the graph-based, "open-world" nature of RDF. In RDF, it is assumed that facts not explicitly stated might still be true. This research addresses the challenge of defining a "safe" graph in an environment where an attacker may have access to unknown external data or "closed-world" knowledge (e.g., knowing a specific list is complete).
Formalizing Anonymization via Suppressor Functions
The authors utilize formal logic to define a framework for Privacy-Preserving Data Publishing (PPDP). Central to this framework are Suppressor Functions, which replace specific occurrences of sensitive constants (IRIs) with "labelled nulls" or blank nodes. This approach weakens the data logically while preserving its structural integrity.
Sensitive information is defined using SPARQL-like conjunctive queries. If a query returns a sensitive answer (e.g., "Alice has Cancer"), the dataset is deemed non-compliant. The goal is to find an anonymization that is both compliant and cost-effective, minimizing information loss based on the number of nulls introduced.
Linkage Safety and Attacker Knowledge
The core innovation of the paper is the concept of Linkage Safety. A dataset is considered linkage-safe if it remains policy-compliant when merged with any external dataset that is itself compliant.
Key insights include:
- Open-World Advantage: Under standard open-world RDF semantics, safety is more manageable because blank nodes are "local," preventing external datasets from easily re-identifying them.
- Closed-World Danger: Complexity increases significantly when an attacker possesses "closed-world" knowledge (represented as "closures"). If an attacker knows a specific registry is complete, they can use the process of elimination to re-identify blank nodes.
- Strict vs. Non-Strict Suppressors: The paper distinguishes between "strict" suppressors (where every instance of a constant becomes the same blank node) and "non-strict" ones, noting that strict suppressors change the underlying mathematics of privacy guarantees.
Computational Complexity and Results
The paper provides a comprehensive "complexity map" for the field:
- Compliance Checking: Ranges from coNP-complete in open-world settings to $\Pi^p_3$-complete when closures are involved.
- Linkage Safety: In the general case with closures, this problem is coNExpTime-complete, indicating it is extremely computationally expensive to guarantee safety against a well-informed attacker.
- Data Complexity: When the privacy policy is fixed, many problems become more manageable, typically landing in NP or $\Pi^p_2$.
- Tractability: Checking linkage safety in a pure open-world setting is surprisingly efficient (solvable in $AC^0$), suggesting that RDF's native blank nodes are a strong foundation for privacy.
Conclusion and Future Directions
While the paper establishes a solid theoretical foundation, several areas remain for future work. These include addressing the "Critical Tuple" gap in complexity bounds, exploring the impact of dropping the Unique Name Assumption (UNA), and accounting for OWL 2 ontologies where automated reasoning (e.g., "Doctor" implies "Person") adds layers of re-identification risk. Ultimately, the goal is to develop practical, optimized algorithms capable of handling real-world, web-scale data despite the inherent computational intractability of the general problem.
Summary updated