Enhancing Controlled Query Evaluation through Epistemic Policies

Gianluca Cima, Domenico Lembo, Lorenzo Marconi, Riccardo Rosati, Domenico Fabio SavoIJCAI 2024

Introduction

Controlled Query Evaluation (CQE) is a critical framework for maintaining data privacy in ontologies. In a typical CQE system, a "censor" intercepts user queries and filters answers to prevent the leakage of sensitive information defined by a security policy. However, traditional CQE systems often rely on "denial" policies—rigid rules that prohibit disclosure regardless of context. This paper addresses the limitations of such blunt instruments by introducing a more expressive framework based on "epistemic dependencies." This approach allows for conditional privacy policies, mirroring real-world requirements like GDPR compliance where data disclosure often depends on the user's existing knowledge.

Methodology

The authors propose the use of Epistemic Dependencies (EDs) as a formal policy language. Central to this framework is the epistemic operator ($K$), which represents the system's model of the user's knowledge. For instance, a policy might specify that a user is only permitted to know a patient's admission status ($K \text{admitted}$) if they also know the patient has provided consent ($K \text{Consent}$).

To enforce these policies, the system employs "optimal CQ-censors"—maximal subsets of the data that satisfy the privacy constraints. The research explores two primary entailment methods:

  1. Skeptical Entailment (SC): An answer is returned only if it holds across all possible optimal ways to hide sensitive data, ensuring maximum security.
  2. Query Rewriting: For a specific class of "acyclic" policies, the authors developed an algorithm to transform standard queries into "privacy-aware" versions that can be executed directly by standard SQL engines.

Theoretical Framework and Insights

As a theoretical study, the paper focuses on computational complexity and algorithmic foundations within the $DL\text{-}Lite_{\mathcal{R}}$ description logic. Several key insights emerge from this analysis:

  • Privacy by Default: The epistemic framework naturally supports the "privacy by default" principle, allowing relationships to remain hidden unless specific "unlocking" information is disclosed.
  • The Acyclicity Sweet Spot: A major finding is the identification of acyclic policies—rules without circular dependencies—as a "sweet spot" for efficiency. While arbitrary policies can be computationally expensive, acyclic ones remain highly scalable.
  • Indistinguishability: The authors prove that for basic conjunctive queries (BCQs), the skeptical entailment method satisfies the "indistinguishability" criterion. This ensures that a user cannot determine whether an answer is missing due to its absence from the database or because it is being intentionally hidden.

Key Results

The paper establishes a clear boundary between tractable and intractable privacy enforcement. The findings demonstrate that while arbitrary epistemic policies lead to coNP-complete data complexity, acyclic policies fall within $AC^0$. This means that for acyclic policies, the overhead of privacy preservation is negligible, as queries can be rewritten into standard First-Order logic (SQL).

Table 1: Complexity results for Controlled Query Evaluation under epistemic policies, showing the distinction between acyclic and arbitrary policies across different query types.

Conclusion and Future Work

While the framework provides a robust foundation for conditional privacy, certain limitations remain. For Unions of Conjunctive Queries (BUCQs), the strictest form of skeptical entailment does not always preserve indistinguishability, leading the authors to propose "IC-entailment" as a sound approximation.

Future research directions include extending the framework to other ontology languages like $\mathcal{EL}$ or full OWL 2 profiles, incorporating external background knowledge that users might possess, and developing "dynamic" censoring techniques to prevent information leakage over multiple query sessions.

Summary updated

BibTeX
@inproceedings{cima2024enhancing,
  author = {Gianluca Cima and Domenico Lembo and Lorenzo Marconi and Riccardo Rosati and Domenico Fabio Savo},
  title = {{Enhancing Controlled Query Evaluation through Epistemic Policies}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure