Controlled Query Evaluation in Description Logics Through Instance Indistinguishability

Gianluca Cima, Domenico Lembo, Riccardo Rosati, Domenico Fabio SavoIJCAI 2020 · DOI

TL;DR

This paper tackles the challenge of privacy-preserving query answering in Description Logics (DLs) by formalizing and analyzing the "instance indistinguishability" approach. They introduce a novel, tractable approximation of this approach for DL-Lite ontologies, making privacy-preserving query answering more practical for data management systems.

What Problem Does This Paper Address?

In today's data-driven world, organizations often need to protect sensitive information while still allowing users to query their data. Controlled Query Evaluation (CQE) is a framework designed to achieve this by defining data protection policies. Two main approaches exist: "confidentiality-preserving" (CP), which focuses on the set of all possible answers, and "instance indistinguishability" (IB), which ensures that a user querying a protected dataset receives the same answers as they would from an altered, non-violating version of the dataset that is indistinguishable to them. While both aim for optimal privacy, the relationship between them and the practical feasibility of the IB approach, especially for complex DL ontologies, remained unclear. This paper specifically investigates the IB approach in the context of DLs, aiming to bridge theoretical gaps and pave the way for practical applications.

Methods

The paper introduces and analyzes the instance indistinguishability (IB) approach to Controlled Query Evaluation (CQE) within Description Logics (DLs). Key methods include:

  • Formalizing IB Censors: Defining IB censors mathematically, ensuring that for any given data instance (ABox), the censor returns a modified instance that is indistinguishable to the user but does not violate the privacy policy.
  • Comparing IB and CP Censors: Establishing a formal relationship between IB and confidentiality-preserving (CP) censors, proving that every IB censor is also a CP censor, but not vice-versa.
  • Complexity Analysis: Deriving data complexity results for query answering under optimal IB censors, showing it to be intractable for DL-Lite ontologies.
  • Introducing Quasi-Optimal IB Censors (QIB): Defining a new notion of a "quasi-optimal" IB censor that is a sound approximation of all optimal IB censors. This QIB censor is shown to be unique and always exists.
  • Developing FO-Rewritability: Proving that query answering using the QIB censor for DL-Lite ontologies is tractable with respect to data complexity and, crucially, is first-order (FO) rewritable. This means privacy-preserving queries can be translated into standard FO queries over the data.
  • Algorithm for Optimal CP Censors: Presenting an algorithm, OptGACensor, to compute an optimal CP censor in the language of ground atoms (GA), which is instrumental in establishing the FO-rewritability of QIB censors.

Datasets

Not discussed in the paper. The paper focuses on theoretical formalisms and complexity analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • IB is a Subset of CP: The paper formally proves that the instance indistinguishability (IB) approach to privacy is a more restrictive form of confidentiality preservation (CP). This means any system that guarantees privacy via IB also guarantees it via CP, but the reverse is not true.
  • Intractability of Optimal IB: Querying under optimal IB censors for DL-Lite ontologies is computationally hard (coNP-complete in data complexity). This suggests that a naive implementation of optimal IB would be impractical for large datasets.
  • The Power of Approximation (QIB): The introduction of the "quasi-optimal IB censor" (QIB) is a significant contribution. This censor, while not strictly optimal, provides a semantically sound approximation that is much more computationally feasible.
  • FO-Rewritability for Practicality: The most impactful insight is that query answering using QIB censors for DL-Lite is first-order rewritable. This is a major step towards practical implementation, as it means privacy-preserving queries can be transformed into standard database queries, allowing existing database systems to handle them.

Key Results

  • IB Censors are CP Censors: Theorem 1 establishes that if a censor is IB, it is also a CP censor.
  • Optimal IB is Intractable: IB-Entailment (querying over all optimal IB censors) is coNP-complete in data complexity for DL-Lite ontologies (Theorem 4).
  • QIB Censors Exist and are Unique: Theorem 5 proves the existence and uniqueness of QIB censors.
  • QIB Entailment is FO-Rewritable: Theorem 7 and Corollary 1 demonstrate that query answering under QIB censors for DL-Lite is FO-rewritable and thus in AC⁰ (polynomial time in data complexity). This is achieved by relating QIB entailment to IAR-entailment and leveraging existing FO-rewriting techniques.

Limitations and Future Work

  • User Model Simplification: The authors acknowledge that their current user model is relatively simple, assuming users only know the TBox and query answers. Future work could involve enriching this model to capture more realistic data protection scenarios.
  • Practical Implementation: While FO-rewritability is a significant theoretical step, the paper points to the need for practical implementations of CQE engines for DL ontologies and Ontology-based Data Access (OBDA).
  • Broader DL Support: The current FO-rewritability results are specific to DL-Lite ontologies. Extending these results to more expressive DLs would be a valuable future direction.

Summary updated

BibTeX
@inproceedings{cima2020controlled,
  author = {Gianluca Cima and Domenico Lembo and Riccardo Rosati and Domenico Fabio Savo},
  title = {{Controlled Query Evaluation in Description Logics Through Instance Indistinguishability}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/248},
}
Figure