Privacy Preserving Query Answering in Description Logics Through Instance Indistinguishability

Abstract

We study privacy-preserving query answering in Description Logics (DLs). Specifically, we consider the approach of controlled query evaluation (CQE) based on the notion of instance indistinguishability. We derive data complexity results for query answering over DL-Liteℛ ontologies, through a comparison with an alternative, existing confidentiality-preserving approach to CQE. Finally, we identify a semantically well-founded notion of approximated query answering for CQE, and prove that, for DL-Liteℛ ontologies, this form of CQE is tractable with respect to data complexity and is first-order rewritable, i.e., it is always reducible to the evaluation of a first-order query over the data instance.

1. Introduction

We consider controlled query evaluation (CQE), a declarative framework for privacy-preserving query answering investigated in the literature on knowledge representation and database theory [ 1, 2, 3 ]. The basic idea of CQE is defining a data protection policy through logical statements. Consider for instance an organization that wants to keep confidential the fact that it has suppliers involved in both Project A and Project B. This can be expressed over the information schema of the organization through a denial assertion of the form ∀. Supplier() ∧ ProjA() ∧ ProjB() → ⊥

In CQE, two different main approaches can be identified. The first one [ 4, 5, 6 ] models privacy preservation through the notion of indistinguishable data instances. In this approach, a system for CQE enforces data privacy if, for every data instance , there exists a data instance ′ that does not violate the data protection policy and is indistinguishable from for the user, i.e., for every user query , the system provides the same answers to over and over ′. We call this approach (instance) indistinguishability-based (IB). In continuation of the previous example, in the presence of an instance {Supplier(), ProjA(), ProjB()}, an IB system should answer user queries as if the instance were, e.g., {Supplier(), ProjA()} (note that other instances not violating the policy can be considered as indistinguishable, e.g., {Supplier(), ProjB()}).

The second approach [ 7, 8 ] models privacy preservation by considering the whole (possibly infinite) set of answers to queries that the system provides to the user. In this approach, a CQE system protects the data if, for every data instance , the logical theory corresponding to the set of answers provided by the system to all queries over does not entail any violation of the data protection policy. According to [ 8 ], we call this approach confidentiality-preserving (CP) . In our ongoing example, a CP system would entail, e.g., the queries Supplier() ∧ ProjA() and ∃.Supplier() ∧ ProjB(), but not also the query Supplier() ∧ ProjB().

In both approaches, the ultimate goal is to realize optimal CQE systems, i.e., systems maximizing the answers returned to user queries, still respecting the data protection policy. Traditionally, this aim has been pursued through the construction of a single optimal censor, i.e., a specific implementation of the adopted notion of privacy-preservation, either IB or CP. Since, however, in both approaches several optimal censors typically exist, this way of proceeding requires to make a choice on how to obfuscate data, which, in the absence of additional (preference) criteria, may result discretionary. To avoid this, query answering over all optimal censors has been recently studied, limited to the CP approach [ 7, 9 ], whereas query answering over all optimal IB censors has not been investigated so far. Moreover, among the complexity results obtained and the techniques defined so far for CQE, we still miss the identification of cases that are promising towards its practical usage.

In this paper, we aim at filling some of the above mentioned gaps in the context of Description Logic (DL) ontologies. We focus on the approach to CQE based on instance indistinguishability (Section 3), and study its relationship with the CP approach (Section 4). Specifically, we prove that the IB approach to CQE in DLs corresponds to a particular instance of the CP approach to CQE [ 9 ]. Based on such a correspondence, we show that, even in the lightweight DL DL-Liteℛ, query answering in the IB approach is intractable with respect to data complexity, unless one relies on a single optimal censor chosen non-deterministically in the lack of further meta-information about the domain of the dataset.

To overcome the above problems and provide a practical, semantically well-founded solution, we define a quasi-optimal notion of IB censor, which corresponds to the best sound approximation of all the optimal IB censors (Section 5). We then prove that, in the case of DL-Liteℛ ontologies, query answering based on the quasi-optimal IB censor is reducible to the evaluation of a first-order query over the data instance, i.e., it is first-order rewritable . We believe that this result has an important practical impact. Indeed, we have identified a setting in which privacy-preserving query answering formalized in a declarative logic-based framework as CQE, for a DL (i.e., DL-Liteℛ) specifically designed for data management, has the same data complexity as evaluating queries over a database (i.e., in AC0). This opens the possibility of defining algorithms for CQE of practical usage, amenable to implementation on top of traditional (relational) data management systems, as done in [ 10 ] exploiting Ontology-based Data Access engines.

This paper summarizes the results of our IJCAI-20 conference publication [ 11 ].

2. Preliminaries

We use standard notions of function-free first-order (FO) logic, and in particular we consider Description Logics (DLs), which are fragments of FO using only unary and binary predicates, called concepts and roles, respectively.We assume to have the pairwise disjoint countably infinite sets Σ , Σ, Σ and Σ for atomic concepts, atomic roles, constants (a.k.a. individuals), and variables, respectively. A DL ontology = ∪ is constituted by a TBox and an ABox , specifying intensional and extensional knowledge, respectively. The set of atomic concepts and roles occurring in is the signature of . The semantics of is given in terms of FO models over the signature of , in the standard way.In particular, we say that is consistent if it has at least one model, inconsistent otherwise. entails an FO sentence specified over the signature of , denoted |= , if is true in every model of . In this paper, we consider ontologies expressed in DL-Liteℛ, the member of the DL-Lite family [ 12 ] which underpins OWL 2 QL, i.e., the OWL 2 profile specifically designed for efcfiient query answering. A TBox in DL-Liteℛ is a finite set of axioms of the form 1 ⊑ 2 (resp., 1 ⊑ 2), denoting concept (resp., role) inclusion, and 1 ⊑ ¬2 (resp., 1 ⊑ ¬2), denoting concept (resp., role) disjointness, where: 1, 2 are of the form , with ∈ Σ, or its inverse − , and 1, 2 are of the form , with ∈ Σ , ∃ , or ∃ − , i.e., unqualified existential restrictions, which denote the set of objects occurring as first or second argument of , respectively. An ABox is a finite set of ground atoms, i.e., assertions of the form (), (, ), where ∈ Σ , ∈ Σ, and , ∈ Σ . As usual in query answering over DL ontologies, we focus on conjunctive queries. A Boolean conjunctive query (BCQ) is an FO sentence of the form ∃⃗.(⃗), where ⃗ are variables in Σ , and (⃗) is a finite, non-empty conjunction of atoms of the form (⃗), where ∈ Σ ∪ Σ, and each term in ⃗ is either a constant in Σ or a variable in ⃗. We denote by Eval(, ) the result of the evaluation of a query over (the model isomorphic to) an ABox .

A denial assertion (or simply a denial) is an FO sentence of the form ∀⃗.(⃗) → ⊥, such that ∃⃗.(⃗) is a BCQ. Given one such denial and an ontology , we say that ∪ { } is consistent if ̸|= ∃⃗.(⃗), and is inconsistent otherwise.

In the following, with FO, CQ, and GA, we denote the languages of function-free FO sentences, BCQs, and ground atoms, respectively, all specified over the alphabets Σ , Σ, Σ , and Σ . Given an ontology and a language ℒ, with ℒ() we refer to the subset of ℒ whose sentences are built over the signature of and the variables in Σ . For a TBox and a language ℒ, we denote by clℒ (· ) the function that, for an ABox , returns all the sentences ∈ ℒ( ∪ ) such that ∪ |= .

For the sake of presentation, we will limit our technical treatment to languages containing only closed formulas, but our results hold also for open formulas. In particular, the results on entailment of BCQs can be extended to arbitrary (i.e., non-Boolean) CQs in the standard way1 . Our complexity results are for data complexity, i.e., are w.r.t. the size of the ABox only.

1We also notice that, since DL-Liteℛ is insensitive to the adoption of the unique name assumption (UNA) for CQ answering,our results hold both with and without UNA.

3. CQE through Instance Indistinguishability

A CQE framework consists of a TBox and a policy over , i.e., a finite set of denial assertions over the signature of . An ABox for is such that and have the same signature. In the following, when a TBox is given, we always assume that the coupled policy is specified over , that each considered ABox is for , and that ∪ and ∪ are consistent. A censor is a function that taken an ABox for as input alters standard query answering over ∪ so that on the basis of the answers (even a possibly infinite set thereof) and the TBox, a user can never infer a BCQ ∃⃗.(⃗) such that ∀⃗.(⃗) → ⊥ belongs to .

We here propose a notion of censor which is the natural application to our framework of the analogous definitions given in [ 4, 5, 6, 13, 14 ]. The basic idea of this approach is that for every underlying instance (an ABox in our framework) and every query, a censor returns to the user the same answers it would return on another (possibly identical) instance that does not contain confidential data, so that she cannot understand which of the two instances she is querying. This is formalized as follows.

Definition 1. [Indistinguishability-based censor] Let be a DL TBox and be a policy. An indistinguishability-based (IB) censor for and is a function cens(· ) that, for each ABox , returns a set cens() ⊆ clCQ() such that there exists an ABox ′ for which () cens() = clCQ(′) (in this case we say that and ′ are indistinguishable w.r.t. cens) and () ∪ ∪ ′ is a consistent FO theory.

Example 1. The TBox signature consists of the atomic concepts Supplier, ProjA, and ProjB, denoting the set of suppliers of the company, suppliers involved in Project A and those involved in Project B, respectively, and contains the axioms ProjA ⊑ Supplier and ProjB ⊑ Supplier, stating that each individual instance of ProjA or ProjB is also instance of Supplier. Data protection is specified through the policy = {∀.ProjA() ∧ ProjB() → ⊥}. The following functions are IB censors for and : • cens1: given an ABox , cens1() returns the set clCQ(PA ) of BCQs, where PA is obtained from by removing the assertion ProjA(), for each individual such that both ProjA() and ProjB() are in (note that for every ABox , and PA are indistinguishable w.r.t. cens1. Similarly in the following censors). • cens2: given an ABox , cens2() returns the set clCQ(PB ) of BCQs, where PB is obtained from by removing the assertion ProjB(), for each individual such that both ProjA() and ProjB() are in . • cens3: given an ABox , cens3() returns the set clCQ(sup ) of BCQs, where is obtained from by adding the assertion Supplier() and removing ProjA() and ProjB(), for each individual such that both ProjA() and ProjB() are in .

It is easy to see that an IB censor always exists, but, as Example 1 shows, there may be many IB censors for and , and so it is reasonable to look for censors preserving as much information as possible. Formally, given two IB censors cens and cens′ for and , we say that cens′ is more informative than cens if: (i) for every ABox , cens() ⊆ cens′(), and (ii) there exists an ABox ′ such that cens(′) ⊂ cens′(′). Optimal censors are then defined as follows. Definition 2. Let be a DL TBox and be a policy. An IB censor cens for and is optimal if there does not exist any other IB censor for and that is more informative than cens. We denote by OptIBCens , the set of the optimal IB censors for and .

Example 2. Among the censors of Example 1, cens3 ̸∈ OptIBCens , , since both cens1 and cens2 are more informative than cens3. It can be then verified that cens1 and cens2 are the only optimal IB censors for and .

4. IB Censors vs. CP Censors

In [ 8 ], a different notion of censor, named confidentiality-preserving (CP) censor, has been proposed. Intuitively, a CP censor establishes which are the BCQs entailed by a TBox and a given ABox that can be disclosed without violating the policy. We report below the definition given in [ 9 ], which generalizes CP censors to any language ℒ ⊆ FO, called the censor language. Definition 3. [Confidentiality-preserving censor] Let be a DL TBox, be a policy, and ℒ ⊆ FO be a language. A confidentiality-preserving (CP) censor in ℒ for and is a function cens(· ) that, for each ABox , returns a set cens() ⊆ clℒ () such that ∪ ∪ cens() is a consistent FO theory.

The notion of more informative censor previously given for IB censors can be naturally extended to CP censors, and so we can define optimal censors also in this case. We denote by ℒ-OptCPCens , the set of the optimal CP censors in ℒ for and .

Example 3. Consider and as defined in Example 1. An optimal CP censor cens4 in CQ for and is defined as follows: given an ABox , cens4() returns the set of BCQs obtained by removing from clCQ() every query containing the atom ProjA(), for each individual such that both ProjA() and ProjB() are in .

We notice that the CP censor cens4 is not an IB censor. Indeed, consider the ABox = {ProjA(), ProjB()}. We have that cens4() = { | ∈ CQ and ∪ |= }, where = {∃.ProjA(), ProjB()}. It is not hard to see that there exists no ABox ′ such that ′ and are indistinguishable w.r.t. cens4 and ∪ ∪ ′ is consistent.

Let be an ABox and cens be either an IB or a CP censor, the set cens() is called theory of the censor cens for .

The following theorems explain the relation between IB censors and CP censors. Theorem 1. Let be a DL TBox and be a policy. If cens is an IB censor for and , then it is a CP censor in CQ for and . The converse does not necessarily hold.

Theorem 2. Let be a DL TBox and be a policy. Then, ib_cens ∈ OptIBCens , iff there exists a CP censor cp_cens ∈ GA-OptCPCens , such that, for each ABox , clCQ(cp_cens()) = ib_cens().

From Theorem 2 and the results given in [ 9 ], it follows that, given a DL-Liteℛ TBox , a policy , an ABox , and a BCQ , deciding whether ∈ cens() for every cens ∈ OptIBCens , is coNP-complete in data complexity.

5. Approximating Optimal IB Censors

Towards a practical approach to CQE, in this section we consider a different entailment problem that approximates entailment under each optimal censor, and we show that its data complexity is in AC0 (i.e., the same complexity of evaluating FO queries over a database). The approximation we propose consists in considering a non-necessarily optimal IB censor whose theory, for every ABox, is as close as possible to the theories of all the optimal IB censors. We call such censor quasi-optimal IB (QIB) censor.

Definition 4. [QIB censor] Let be a DL TBox, let be a policy, and let cens be an IB censor for and . We say that cens is a QIB censor if: (i) cens() ⊆ cens′(), for each cens′ ∈ OptIBCens , , and (ii) there exists no IB censor cens′ for and which is more informative than cens and that satisfies condition.

Example 4. The IB censor cens3 of Example 1 is a QIB censor for and (but cens3 ̸∈ OptIBCens , ).

It is not hard to see that a QIB censor for a DL TBox and a policy always exists and it is unique. Hereinafter, we denote with qib_cens , the QIB censor for and . Definition 5. Let be a DL TBox, be a policy, be an ABox, and be a BCQ. QIB-Entailment( , , , ) is the problem of deciding whether ∈ qib_cens , ().

We now focus on the case of DL-Liteℛ TBoxes and prove that, in this case, entailment of BCQs under QIB censors is FO-rewritable. Formally, we say that QIB-entailment in a DL ℒ is FO-rewritable, if for every TBox expressed in ℒ, every policy and every BCQ , one can effectively compute an FO query such that for every ABox , QIB-Entailment( , , , ) is true iff |= . We call the QIB-perfect reformulation of w.r.t. and .

We prove FO-rewritability of entailment of BCQs under QIB censors in DL-Liteℛ by exploiting a correspondence between this problem and entailment of BCQs under IAR-semantics for DL ontologies, which is indeed FO-rewritable for DL-Liteℛ,, i.e., DL-Liteℛ enriched with denial assertions [ 15 ]. We recall that the IAR-semantics is an inconsistency-tolerant semantics that allows for meaningful entailment also when the ABox contradicts the TBox of an ontology. The entailment under IAR-semantics is defined as follows: give a DL , an ABox , and BCQ , IAR-Entailment( , , ) is the problem of verifying whether ∪ ℛ |= , where ℛ is the intersection of all the maximal subsets of such that ∪ is consistent. Theorem 3. Let be a DL-Liteℛ TBox, be a policy, be an ABox, and be a BCQ. QIB-Entailment( , , , ) is true iff IAR-Entailment( ∪ , clGA(), ) is true.

Theorem 3 actually states that, to solve QIB-entailment, we can resort to the query rewriting techniques used to establish IAR-entailment given in [ 15 ], provided that we compute clGA(). We recall that query entailment under IAR-semantics in a DL ℒ is FO-rewritable if for every TBox expressed in ℒ and every BCQ , one can effectively compute an FO query such that for every ABox , IAR-Entailment( , , ) is true iff |= . The query is called the IAR-perfect reformulation of w.r.t. .

To establish FO-rewritability of QIB-entailment in DL-Liteℛ, however, we still need to address the above mentioned computation of clGA(), and turn it into an additional query reformulation step. To this aim, we can exploit the fact that, for a DL-Liteℛ, ontology ∪ , an FO query evaluates to true over clGA() iff ′ evaluates to true over , where ′ is obtained by suitably rewriting each atom of according to the positive inclusions of . Intuitively, in this way we cast into the query all the possible causes of the facts that are contained in the closure of the ABox w.r.t. the TBox.

To compute such a query ′, we use the function atomRewr(, ), which substitutes each atom of with the formula ( ) defined as follows (where , are atomic concepts and , are atomic roles): (()) =⋁︀ |=⊑ () ∨ ⋁︀ |=∃⊑(∃.(, )) ∨ ⋁︀ |=∃− ⊑(∃.(, )) ((1, 2)) = ⋁︀ |=⊑ (1, 2) ∨ ⋁︀ |=− ⊑ (2, 1).

The following lemma, whose proof can be immediately obtained from the definitions of clGA(· ) and atomRewr(· , · ), states the property we are looking for.

Lemma 1. Let be a DL-Liteℛ, TBox, be an ABox, and be an FO sentence. Then Eval(, clGA()) = Eval(atomRewr(, ), ).

We are now able to extablish FO-rewritability of QIB-entailment.

Theorem 4. Let be a DL-Liteℛ TBox, be a policy, be a BCQ, and be an FO sentence that is a IAR-perfect reformulation of w.r.t. the DL-Liteℛ, TBox ∪ . Then, the FO sentence atomRewr(, ) is a QIB-perfect reformulation of w.r.t. and .

Since IAR-entailment is actually FO rewritable, as shown in [ 15 ], the above theorem proves the FO rewritability of QIB-entailment for DL-Liteℛ TBoxes. Moreover, the above theorem identifies a technique for obtaining the QIB-perfect reformulation of a CQ, based on a simple combination of the IAR-perfect reformulation algorithm of [ 15 ] and the atomRewr reformulation defined above. Therefore: Corollary 1. Let be a DL-Liteℛ TBox, be a policy, be an ABox, and be a BCQ. The problem QIB-Entailment( , , , ) is in AC0 in data complexity.

6. Conclusions

In this paper, we have studied the approach to CQE based on instance indistinguishability and identified a semantically well-founded notion of CQE that enjoys first-order rewritability in the case of DL-Liteℛ ontologies.

An important future research direction is a deeper study of the user model. Our framework inherits from its predecessors a relatively simple model, which assumes that the user knows (at most) the TBox and all the query answers returned by the system, and considers only the deductive abilities of the user over such knowledge. This user model might need to be enriched to capture more realistic data protection scenarios. This work was partly supported by the ANR AI Chair INTENDED (ANR-19-CHIA-0014), by MIUR under the PRIN 2017 project “HOPE” (prot. 2017MMJJRE), by the EU within the H2020 Programme under the grant agreement 834228 (ERC Advanced Grant WhiteMec) and the grant agreement 825333 (MOSAICrOWN), by Regione Lombardia within the Call Hub Ricerca e Innovazione under the grant agreement 1175328 (WATCHMAN), and by Sapienza Università di Roma (2019 project CQEinOBDM).

References

[1] G. L. Sicherman , W. de Jonge, R. P. van de Riet, Answering queries without revealing secrets , ACM Trans. Database Syst . 8 ( 1983 ) 41 - 59 .

[2] P. A. Bonatti , S. Kraus , V. S. Subrahmanian , Foundations of secure deductive databases , IEEE Trans. Knowl. Data Eng . 7 ( 1995 ) 406 - 422 .

[3] J. Biskup , For unknown secrecies refusal is better than lying, Data and Knowl . Eng. 33 ( 2000 ) 1 - 23 .

[4] J. Biskup , P. A. Bonatti , Controlled query evaluation for known policies by combining lying and refusal , Ann. Math. Artif. Intell. 40 ( 2004 ) 37 - 62 .

[5] J. Biskup , T. Weibert, Keeping secrets in incomplete databases , Int. J. of Information Security 7 ( 2008 ) 199 - 217 .

[6] P. A. Bonatti , L. Sauro , A confidentiality model for ontologies , in: Proc. of ISWC , volume 8218 of LNCS , 2013 , pp. 17 - 32 .

[7] B. Cuenca Grau , E. Kharlamov , E. V. Kostylev , D. Zheleznyakov , Controlled query evaluation over OWL 2 RL ontologies , in: Proc. of ISWC , volume 8218 , 2013 , pp. 49 - 65 .

[8] B. Cuenca Grau , E. Kharlamov , E. V. Kostylev , D. Zheleznyakov , Controlled query evaluation for datalog and OWL 2 profile ontologies , in: Proc. of IJCAI , 2015 , pp. 2883 - 2889 .

[9] D. Lembo , R. Rosati , D. F. Savo , Revisiting controlled query evaluation in description logics , in: Proc. of IJCAI , 2019 , pp. 1786 - 1792 .

[10] G. Cima , D. Lembo , L. Marconi , R. Rosati , D. F. Savo , Controlled query evaluation in ontology-based data access , in: Proc. of ISWC , volume 12506 of LNCS , 2020 , pp. 128 - 146 .

[11] G. Cima , D. Lembo , R. Rosati , D. F. Savo , Controlled query evaluation in description logics through instance indistinguishability , in: Proc. of IJCAI , 2020 , pp. 1791 - 1797 .

[12] D. Calvanese , G. De Giacomo, D. Lembo , M. Lenzerini , R. Rosati , Tractable reasoning and efcfiient query answering in description logics: The DL-Lite family , J. of Automated Reasoning 39 ( 2007 ) 385 - 429 .

[13] M. Benedikt , B. Cuenca Grau , E. V. Kostylev , Logical foundations of information disclosure in ontology-based data integration, Artif . Intell. J. 262 ( 2018 ) 52 - 95 .

[14] M. Benedikt , P. Bourhis , L. Jachiet , M. Thomazo , Reasoning about disclosure in data integration in the presence of source constraints , in: Proc. of IJCAI , 2019 , pp. 1551 - 1557 .

[15] D. Lembo , M. Lenzerini , R. Rosati , M. Ruzzi , D. F. Savo , Inconsistency-tolerant query answering in ontology-based data access , J. of Web Semantics 33 ( 2015 ) 3 - 29 .