Logical Foundations of Linked Data Anonymisation

Bernardo Cuenca Grau, Egor V. KostylevJAIR 2019 · DOI · OpenReview

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.

Original sensitive RDF graph representing patient-doctor relationships.

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.

Comparison of valid anonymizations ($G^1, G^2$) and an invalid transformation (c) for the original graph.

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

Abstract

The widespread adoption of the Linked Data paradigm has been driven by the increasing demand for information exchange between organisations, as well as by regulations in domains such as health care and governance that require certain data to be published. In this setting, sensitive information is at high risk of disclosure since published data can be often seamlessly linkedwith arbitrary external data sources.In this paper we lay the logical foundations of anonymisation in the context of Linked Data. We consider anonymisations of RDF graphs (and, more generally, relational datasets with labelled nulls) and define notions of policy-compliant and linkage-safe anonymisations. Policy compliance ensures that an anonymised dataset does not reveal any sensitive information as specified by a policy query. Linkage safety ensures that an anonymised dataset remains compliant even if it is linked to (possibly unknown) external datasets available on the Web, thus providing provable protection guarantees against data linkage attacks. We establish the computational complexity of the underpinning decision problems both under the open-world semantics inherent to RDF and under the assumption that an attacker has complete, closed-world knowledge over some parts of the original data.
BibTeX
@article{grau2019logical,
  author = {Bernardo Cuenca Grau and Egor V. Kostylev},
  title = {{Logical Foundations of Linked Data Anonymisation}},
  journal = {J. Artif. Intell. Res.},
  year = {2019},
  doi = {10.1613/jair.1.11355},
}
Figure