Assessing the Exposure to Public Knowledge in Policy-Protected Description Logic Ontologies

1 Introduction

Protecting sensitive knowledge in information systems is a critical and challenging task, often complicated by the existence of information that a potential adversary may already possess or acquire from external sources, also referred to as background knowledge (e.g. in [Biskup and Bonatti, 2004; Bonatti and Sauro, 2013]). Such knowledge can be exploited to compromise individual privacy or infer sensitive data from otherwise protected datasets. In this paper, we focus on scenarios where background knowledge consists of publicly available information, such as that obtained from social networks, websites, or public records; in addition, public knowledge may originate from the system itself, due to security breaches, resulting in previously private information being made public. This may compromise the protection of sensitive data, thus constituting an information leakage.

To formally study this problem, we propose a general framework in which a (first-order logic) knowledge base

(KB) K is coupled with a policy P that protects confidential information in K. Part of K, denoted Kpub, is publicly known, together with P. The policy is given in terms of epistemic dependencies (EDs), which are formulas of the form ∀⃗x (Kϕb(⃗x) → Kϕh(⃗y)), where ϕb(⃗x) and ϕh(⃗y) are queries (i.e. open formulas) over K, ⃗y ⊆ ⃗x, and K is a modal operator. Intuitively, an ED stipulates that if the answers to the query ϕb(⃗x) are known, then also the answers to the query ϕh(⃗y) must be known (note that if ϕh(⃗y) is a contradiction, the answers to ϕb(⃗x) cannot be disclosed at all). EDs were introduced in [Console and Lenzerini, 2020] and employed as constraints within an Ontology-based Data Management setting. Recently, they have been adopted in [Cima et al., 2024a] in the context of Controlled Query Evaluation (CQE), where they serve the same purpose as in our framework. Notably, using EDs in policy design enables highly expressive forms of protection rules that go beyond the policies commonly considered in many studies in privacy-preserving query answering [Bonatti and Sauro, 2013; Cuenca Grau et al., 2015; Cima et al., 2024b].

The example below illustrates our framework and highlights the confidentiality issues that may arise in this context.

Example 1. Consider a KB of patients' genetic data. It is public knowledge that the ∆F508 variant of the CFTR gene may indicate the presence of cystic fibrosis and is thus classified as pathogenic. In contrast, the R577X variant of the ACTN3 gene, which implies improved muscle endurance in individuals, is generally not considered pathogenic. We denote the former variant with v1 and the latter with v2. The KB associates patients to the gene variants they possess (hasVariant predicate). Patients may consent to disclose these associations (consentToShare predicate). Pathogenic variants are classified as sensitive (∀x(pathogenic(x) → sensitive(x)) axiom). The policy stipulates that patientvariant pairs may be disclosed only with patient consent, but pairs involving sensitive variants can never be disclosed.

The KB K, the policy P and the public portion Kpub of K are as follows (where ⊥ denotes a contradiction).

P = {∀p, v (K hasVariant(p, v) → K consentToShare(p, v)), ∀p (K ∃v (hasVariant(p, v) ∧ sensitive(v)) → K⊥)}, Kpub = {∀x (pathogenic(x) → sensitive(x)), pathogenic(v1)}, K = Kpub ∪ {hasVariant(ann, v1), consentToShare(ann, v1), hasVariant(sam, v2), consentToShare(sam, v2), hasVariant(bob, v2)}

It is easy to see that Kpub is compliant with the policy. Kpub might even contain the fact hasVariant(sam, v2), because sam provided his consent for the publication of this data, and v2 is not classified as sensitive. In contrast, hasVariant(bob, v2) cannot be in Kpub, since bob did not provide his consent. Finally, the fact hasVariant(ann, v1) cannot be added to Kpub , even though ann gave her consent, because together with the other formulas in Kpub, this addition causes a violation of the second rule in P.

Let us now introduce the two fundamental decision problems that we study within the framework:

• verifying whether there is a leakage, that is, if the public knowledge implies some confidential information protected by the policy;
• verifying whether there exists a secure view, i.e. a set of sentences inferred by the KB, expressed in a language L, that complies with the policy and the public knowledge.

We adopt a very general approach, according to which the only action that the system can do to protect itself is to provide the user with a view of the KB that complies with the policy. Thus a leakage occurs only if such a secure view does not exist (in this case, Kpub implies some confidential data). The second problem may appear to be the complement of the first, but it has a distinguishing characteristic: it requires views to be expressed in a given language L. Consequently, solving the first problem does not guarantee a solution to the second. The language is a crucial parameter for the practical usage of the notion of secure view, and has an impact on the computational complexity of the problem, as we will show.

We study the data complexity [Vardi, 1982] of both problems, focusing on certain instantiations of the framework. As for the policy, we consider EDs in which both ϕb(⃗x) and ϕh(⃗y) are conjunctive queries (CQs), considering also the special cases in which ϕh(⃗y) does not contain existentially quantified variables (full CQ-EDs), or the EDs respect an acyclicity condition (acyclic CQ-EDs), or both the previous conditions hold (acyclic full CQ-EDs). As for the KB, we concentrate on two fragments of first-order (FO) logic that are commonly used in contexts involving the management of large amounts of data through ontologies: DL-LiteR [Calvanese et al., 2007b] and EL⊥ [Baader et al., 1999]. These are the logical counterparts of the OWL 2 profiles OWL 2 QL and OWL 2 EL, respectively [Motik et al., 2009]. Finally, regarding the view language L, we analyze the case where L is either the language of Boolean CQs or the language of ground atoms (GA), i.e. when the view is simply a set of facts. Both languages are particularly relevant for the practical usage of the notion of secure view.

All our complexity results are summarized in Table 1. The table also includes the case where both K and Kpub consist of ABoxes (i.e. sets of facts). This scenario corresponds to KBs without an intensional component (the so-called TBox), as in plain databases. We emphasize that our complexity results encompass all possible combinations of the languages mentioned above for the various components of the framework. Notably, we identified many tractable cases, several of which are even in AC0 . This latter result indicates that in these cases, the problem can be efficiently solved by evaluating an FO query over an ABox, a task achievable using standard relational database technology. These findings highlight the potential of our framework for practical applications in confidentiality-preserving knowledge management.

Due to space limitations, complete proofs are deferred to the supplemental material accompanying this submission.

2 RelatedWork

Our work is inspired by research on controlled query evaluation (CQE), a declarative framework for privacy-preserving query answering, where confidential data is protected by a policy, as is the case in our study. Unlike work on CQE, we do not focus here on query answering but instead address the leakage and secure view existence problems in the presence of public knowledge. Public knowledge is often not explicitly considered in CQE research on ontologies (e.g. in [Cuenca Grau et al., 2013; Cuenca Grau et al., 2015; Cima et al., 2024b; Cima et al., 2024a]), although a common assumption is that the TBox of the KB is known to the user, whereas the ABox is treated as private. A distinguishing feature of our approach is that public knowledge may also include extensional knowledge, and the private portion of K may contain parts of the TBox. Two previous papers on CQE over ontologies provide similiar abilities, i.e. [Bonatti and Sauro, 2013; Studer and Werner, 2014]. The settings considered in these papers are incomparable to ours. In particular, their frameworks cannot replicate the expressiveness and flexibility given by the EDs we use for the policy. Other works on CQE have addressed attacks in the presence of users' background knowledge [Biskup and Bonatti, 2001; Biskup and Bonatti, 2004; Biskup and Weibert, 2008], but they consider the context of propositional databases.

Privacy issues in EL ontology publishing are studied in [Baader and Nuradiansyah, 2019], where the knowledge about individuals to be published is an EL instance store, i.e. an ABox instantiating EL concepts only, without a TBox. Both the privacy policy and the potential background knowledge of an attacker are expressed as EL concepts. In [Baader et al., 2019], the background knowledge is represented by concepts in more expressive DLs. The focus of these papers is on verifying compliance and safety of the attackers' background concepts with respect to the policy, problems that differ from those examined here.

Various studies in data and knowledge bases adopt the idea of protecting confidential information through views for users' access control [Calvanese et al., 2012; Stoffel and Studer, 2005; Chirkova and Yu, 2017], an approach that can be somehow considered as complementary to ours. In these papers, the views and their extensions are given, and there is no explicit protection policy. Forms of leakage are also studied in [Benedikt et al., 2018], in the context of ontology-based data integration, where the focus is on establishing whether the system discloses a source query, considered as secret. The same problem is studied in [Benedikt et al., 2019], where an attacker may exploit additional knowledge on source constraints. Note that these studies do not address the case of attackers with extensional public knowledge.

We finally remark that our approach is deterministic, i.e. we study the assessment of exact leakages. Examples of probabilistic approaches to privacy-preserving information management are instead [Miklau and Suciu, 2007; Sweeney, 2002; Dwork, 2011].

3 Preliminaries

We adopt standard notions of function-free first-order (FO) logic and consider pairwise disjoint sets of predicate names Σp, constant (a.k.a. individual) names Σi and variable names Σv. We define Σ as Σp ∪ Σi ∪ Σv. Throughout the paper, an FO formula ϕ is sometimes denoted as ϕ(⃗x), where ⃗x represents the tuple of free variables in ϕ. Closed FO formulas (namely, the ones without free variables) are also called sentences, while variable-free formulas are said to be ground. In particular, ground atoms are called facts. A knowledge base (KB) Φ is defined as a set of FO sentences. Its semantics is provided in terms of FO interpretations over the signature Σp ∪ Σi. We focus on interpretations that share a common infinite countable domain ∆ = Σi, where each element of Σi is mapped to itself. In other words, we assume the use of standard names, a common practice when working with epistemic operators [Calvanese et al., 2007a].

We use eval(ϕ, I) to denote the outcome (i.e. true or false) of the evaluation of an FO sentence ϕ over an FO interpretation I. An FO interpretation I is a model of a KB Φ if every sentence in Φ evaluates to true over I. A KB Φ entails an FO sentence ϕ, denoted by Φ |= ϕ, if eval(ϕ, I) is true, for every model I of Φ. Given a KB Φ′ , we say that Φ entails Φ′ , denoted by Φ |= Φ′ , if Φ entails every sentence in Φ′ .

In this work, we also consider the language of conjunctive queries and their variants. A conjunctive query (CQ) is an FO formula of the form ∃⃗y ϕ(⃗x, ⃗y), where ⃗x ∪ ⃗y ⊆ Σv, and ϕ(⃗x, ⃗y) is a finite, non-empty conjunction of atoms p(⃗t) (with p ∈ Σp and ⃗t ⊆ Σi ∪ ⃗x ∪ ⃗y). We also include the special CQ ⊥, assuming that eval(⊥, I) is false for any FO interpretation I. A union of conjunctive queries (UCQ) is a disjunction of CQs sharing the same free variables. For convenience, we sometimes treat UCQs as sets of CQs. We call Boolean CQs (BCQs) the CQs without free variables.

Given any language L of formulas, we denote by Lb the set of sentences belonging to L. Throughout the paper we refer to the languages FO ⊇ CQ ⊇ CQb ⊇ GA, which are defined as, respectively, the set of FO formulas over Σ, the set of CQs (possibly containing free variables) over Σ, the set of BCQs over Σ, and the set of ground atoms over Σ. Given a language L ⊆ FOb and a KB Φ, we denote by ConsL(Φ) the set of sentences {ϕ ∈ L | Φ |= ϕ}.

A ground substitution for a sequence ⃗x = x1, . . . , xk of variables is a sequence of constants ⃗c = c1, . . . , ck. Furthermore, if ⃗x are the free variables of an FO formula ϕ(⃗x), we indicate as ϕ(⃗c) the FO sentence obtained from ϕ(⃗x) by replacing each xi with ci, for 1 ≤ i ≤ k.

In this paper, we will specifically focus on Description Logics (DLs), i.e. decidable fragments of FO [Baader et al., 2007]. Typically, in such logics, the predicate set Σp is partitioned into two sets: Σc, containing unary predicates (called concepts), and Σr , containing binary predicates (called roles).

A DL ontology K = T ∪ A comprises a TBox T and an ABox A, which are finite sets of assertions that capture intensional and extensional knowledge, respectively. In this paper, ABoxes are defined as sets of ground atoms. As already said, we focus on the DLs DL-LiteR [Calvanese et al., 2007b] and EL⊥, which is an extension EL [Baader et al., 1999] that allows for the use of the empty concept ⊥c.

ADL-LiteR TBox T is a set of axioms, which can either be inclusions of the form C ⊑ C ′ and R ⊑ R′ (concept and role inclusions) or disjointness assertions of the form C ⊑ ¬C ′ and R ⊑ ¬R′ (concept and role disjointnesses). In these axioms, the concepts C and C ′ (respectively, the roles R and R′ ) can take the formA, ∃P , or ∃P - (respectively, P or P -), where A ∈ Σc, P ∈ Σr, and P - denotes the inverse of the role P. Terms ∃P and ∃P -, called unqualified existential restrictions, represent the sets of objects appearing as the first and second argument of P, respectively.

An EL⊥ TBox T is a set of concept inclusions of the form C ⊑ C ′ , where the C and C ′ can take the form A, ∃P.C, C1 ⊓C2, ⊥c, and ⊤c. Here, C and C ′ are called general concepts, which can be an atomic concept A ∈ Σc, a concept of the form ∃P.C, with P ∈ Σr, called qualified existential restriction and denoting the set of objects that the atomic role P relates to some instance of the general concept C, a concept of the form C1 ⊓ C2, i.e. a conjunction of two general concepts, ⊥c, i.e. the empty concept, or ⊤c, i.e. the top concept.

For DL-LiteR ontologies, we make use of the query rewriting algorithm PerfectRef [Calvanese et al., 2007b], which enjoys the following property.

Proposition 1. Let T be a DL-LiteR TBox and let q(⃗x) be a CQ. For every ABox A and every ground substitution ⃗c for ⃗x, we have that T ∪A |= q(⃗c) iff A |= qr(⃗c), where qr(⃗x) is the UCQ returned by PerfectRef(q(⃗x), T ).

All our complexity results pertain to data complexity [Vardi, 1982], which in our context is the complexity computed with respect to the size of the ABox.

4 Framework

We first formalize the policy P of our framework as a finite set of epistemic dependencies, each of which can be seen as an EQL-Lite(FO) sentence [Calvanese et al., 2007a].

Definition 1 (Epistemic dependency, policy). Given a language L ⊆ FO, an L-epistemic dependency (ED) is a sentence τ of the following form:

where ⃗ xh ⊆ ⃗x, ϕb(⃗x) (called the body of τ) is an L-formula with free variables ⃗x, ϕh( ⃗ xh) (called the head of τ) is an Lformula with free variables ⃗ xh, and K is a modal operator. An L-policy is a finite set of L-EDs.

To simplify our terminology, we call ED an FO-ED and call policy an FO-policy. Also, we use the notation τ(⃗x) to indicate an ED τ whose universally quantified variables are ⃗x. In addition, given a ground substitution ⃗c for ⃗x, we denote by τ(⃗c) the ED obtained from τ by removing the universal quantification of the variables ⃗x and replacing all their occurrences with the corresponding constants in ⃗c. Finally, given an ED τ of the form (1), we denote by body(τ) and head(τ) the formulas ϕb(⃗x) and ϕh( ⃗ xh), respectively.

Intuitively, an ED of form (1) should be read as follows: if the sentence ϕb(⃗c) is known to hold, then the sentence ϕh( ⃗ ch) is known to hold, for every ground substitution ⃗c for ⃗x, where ⃗ ch is the corresponding ground substitution of ⃗ xh .

Formally, we define when a KB Φ satisfies an ED τ, denoted Φ |=EQL τ. To this aim, we consider the set E of all models of Φ, and say that Φ |=EQL τ if, for every ground substitution ⃗c for ⃗x, the fact that eval(ϕb(⃗c), I) is true for every I ∈ E implies that eval(ϕh(⃗ ch), I) is true for every I ∈ E. We say that Φ satisfies a policy P (denoted Φ |=EQL P) if Φ satisfies τ, for each τ ∈ P. We remark that, as already said, EDs of the form (1) have been originally introduced in [Console and Lenzerini, 2020], although in a slightly differnt form.

Following [Calvanese et al., 2007a], given an FO formula ϕ(⃗x) and a KB Φ, we say that ϕ is Φ-range restricted [Calvanese et al., 2007a] if the set of ground substitutions ⃗c for ⃗x such that Φ |= ϕ(⃗c) is finite. Given a policy P and a KB Φ, P is said Φ-range restricted if, for every τ ∈ P of the form (1), the formulas ϕb(⃗x) and ϕh( ⃗ xh) are Φ-range restricted.

Let us now introduce the new notion of KB that we adopt in the paper, in which the information to be protected is specified by the policy as a set of EDs, and the public knowledge is explicitly defined.

Definition 2 (Policy-protected KB with public knowledge). A policy-protected KB with public knowledge (PPKB for short) is a triple E = ⟨K,Kpub,P⟩, where K and Kpub are KBs such that K has at least one model, K |= Kpub , and P is a K-range restricted policy.

Notice that, in the above definition, we assume that the information in Kpub is either contained within or a consequence of the information in K. In other words, we embrace the idea that Kpub represents a portion of the information in K that, in some way, has been publicly exposed. An example of PPKB is the triple ⟨K, Kpub , P⟩ provided in Example 1.

Our aim is to determine whether the sensitive information in K, i.e. the knowledge safeguarded by P, remains secure when the knowledge in Kpub is exposed. To this end, we first provide the following notion of policy violation.

Definition 3 (Policy violation). Given a KB K and a policy P, a policy violation (PV) for ⟨K,P⟩ is a KB Φ for which there exists no KB Φ′ such that K |= Φ′ and Φ∪Φ′ |=EQL P.

Informally, a PV for ⟨K,P⟩ is a fragment of knowledge that conflicts with the policy P and cannot be reconciled by adding further knowledge from K.

Example 2. Consider Example 1. Both the KB Φ1 = {hasVariant(ann, v1), sensitive(v1)} and the KB Φ2 = {hasVariant(bob, v2)} are PVs for ⟨K, P⟩.

When a PV follows from Kpub, it reveals that certain data in K safeguarded by P has been exposed. In such a case, we say that the PV is a leakage in E.

Definition 4 (Leakage). Given a PPKB E = ⟨K,Kpub,P⟩ and a PV Φ for ⟨K,P⟩, we say that Φ is a leakage in E if Kpub |= Φ.

Even if there is no leakage, Kpub alone can still not satisfy the policy. However, this can be overcome by exposing additional knowledge from the system (see Φ′ in Definition 3). In other words, it is still possible to expose a view of K that is secure with respect to P. In practical applications, it is useful to parameterize the view notion to the language chosen to specify it. All of this is formalized in the following definition.

Definition 5 (Secure L-view). Given a PPKB E = ⟨K, Kpub , P⟩ and a language L ⊆ FO, a secure L-view of E is a KB Φ ⊆ L such that K |= Φ and Kpub ∪ Φ |=EQL P.

For the sake of brevity, we may refer to a secure FO-view of E simply as a secure view of E.

Example 3. Recall Example 2. Note that Φ1 is not a leakage in E as Kpub |= Φ1 does not hold. Suppose now that, after a security breach, the data hasVariant(ann, v1) is made public. We thus consider the new PPKB E ′ = ⟨K,K′pub ,P⟩, where K′pub = Kpub ∪ {hasVariant(ann, v1)}. We have that the PV Φ1 of Example 2 is a leakage in E ′ .

Moreover, an example of secure GA-view of E is the set {hasVariant(sam, v2), consentToShare(sam, v2)}, while E ′ has no secure view.

We close this section by outlining the two decision problems that will be the focus of the remainder of the paper.

Leakage-existence (LE) problem: given a PPKB E, deciding whether there exists a leakage in E.

L-view-existence (L-VE) problem: given a PPKB E, deciding whether there exists a secure L-view of E.

5 General Results

In this section, we study the problems introduced earlier, focusing on PPKBs whose components are expressed in a generic language L ⊆ FO.

First, given an ED τ and a PPKB E = ⟨K, Kpub , P⟩, we denote by Ground(τ, E) the set of EDs obtained through all possible ground substitutions of the universally quantified variables of τ with constants occurring in E. We also denote by GroundPol(E) the set {Ground(τ, E) | τ ∈ P}.

The following property immediately follows from the assumption that P is K-range restricted.

Lemma 1. Let E = ⟨K,Kpub,P⟩ be a PPKB. For every KB Φ such that K |= Φ, Φ |=EQL P iff Φ |=EQL GroundPol(E).

We now provide a notion of consequences of a KB Φ with respect to (the EDs of) a PPKB E. Such a notion will be used throughout the rest of the paper.

Definition 6. Given a PPKB E = ⟨K,Kpub,P⟩ and a KB Φ such that K |= Φ, we define ED-Cons(Φ, E) as the minimal set Φ′ of FO sentences such that, for every τ ∈ GroundPol(E), if Φ∪Φ′ |= body(τ) then head(τ) ∈ Φ′ .

Example 4. Recall Example 1. Given the KB Φ3 = {hasVariant(sam, v2)}, the set ED-Cons(Φ3, E) is equal to {consentToShare(sam, v2)}. Now, let Φ4 = {hasVariant(ann, v1)} ∪ Kpub. In this case, ED-Cons(Φ4, E) contains consentToShare(ann, v1) and ⊥, due to the first and the second ED in P, respectively.

Observe that, if P is a set of L-EDs for some L ⊆ FO, then ED-Cons(Φ, E) ⊆ Lb for every Φ ⊆ FOb.

We now exploit Lemma 1 for proving the following important property of the ED-Cons function.

Lemma 2. Let E = ⟨K,Kpub,P⟩ be a PPKB. For every KB Φ such that K |= Φ, Φ |=EQL P iff Φ |= ED-Cons(Φ, E).

The above result allows us to derive the next property, which relates the notion of ED-Cons(Φ, E) to the one of PV.

Lemma 3. Let E = ⟨K,Kpub,P⟩ be a PPKB. For every KB Φ such that K |= Φ, Φ is a PV for ⟨K,P⟩ iff K ̸|= ED-Cons(Φ, E).

In turn, as an immediate consequence of Lemma 3, we obtain the following key property.

Theorem 1. Given a PPKB E = ⟨K, Kpub , P⟩, there exists a leakage in E iff K ̸|= ED-Cons(Kpub, E).

The previous theorem is crucial for establishing a general decidability result for the LE problem.

Theorem 2. If E = ⟨K,Kpub,P⟩ is such that P is a set of L-EDs and deciding entailment of Lb-formulas with respect to theories in K ∪ Lb is decidable, then the LE problem is decidable for E.

The next two properties establish an important connection between the LE and L-VE problems.

Theorem 3. Let E = ⟨K, Kpub, P⟩ be a PPKB, let L ⊆ FO and let P be a set of L-EDs. Then, there exists a leakage in E iff there exists no secure Lb-view of E.

For L = FO, the above theorem specializes as follows.

Corollary 1. Let E = ⟨K,Kpub,P⟩ be a PPKB. Then, there exists a leakage in E iff there exists no secure view of E.

Finally, as a corollary of Theorem 2 and Theorem 3, we obtain the following property.

Corollary 2. If E = ⟨K,Kpub,P⟩ is such that P is a set of L-EDs and deciding entailment of Lb-formulas with respect to theories in K ∪ Lb is decidable, then the L-VE problem is decidable for E.

6 Results for DLOntologies

In this section, we study the computational properties of the LE and L-VE problems, focusing on PPKBs where K and Kpub are DL ontologies and P is a finite set of CQ-EDs. As is customary in the context of DLs, we distinguish between intensional and extensional knowledge. A DL PPKB is thus defined as a triple E = ⟨T ∪ A, Tpub ∪ Apub,P⟩, where T and Tpub are TBoxes, A and Apub are ABoxes, such that T |= Tpub, and T ∪A |= Tpub ∪Apub. The triple S = ⟨T , Tpub, P⟩ is named PPKB specification. Specifically, we focus on the DLs DL-LiteR and EL⊥, referring to a PPKB ⟨K,Kpub,P⟩ as a DL-LiteR PPKB or EL⊥ PPKB when both K and Kpub are in DL-LiteR or in EL⊥, respectively.

We call full L-policy a finite set of full L-EDs, where a full L-ED is an L-ED without existential variables in its head.

Also, for a DL-LiteR TBox T , we recall the subclass of the policy language consisting in EDs that are acyclic for T , originally introduced in [Cima et al., 2024a].

Given a DL-LiteR TBox T and a policy P, the dependency graph of T and P, denoted by G(T , P), is the directed graph defined as follows: (i) the set of nodes of G(T ,P) is the set of predicates occurring in T ∪P; (ii) there is a P-edge from node p1 to node p2 in G(T ,P) if and only if there exists an epistemic dependency of the form (1) in P such that p1 occurs in ϕb and p2 occurs in ϕh; (iii) there is a T-edge from node p1 to node p2 in G(T ,P) if and only if there is a concept or role inclusion in T such that p1 occurs in the left-hand side and p2 occurs in the right-hand side of the inclusion.

Definition 7. Given a DL-LiteR TBox T and a policy P, we say that P is acyclic for T if G(T ,P) contains no cycle involving a P-edge. When P is acyclic for the empty TBox, we simply say that P is acyclic.

Informally, the graph G(T ,P) represents the logical dependencies between the predicates in T and P: a P-edge (resp., a T-edge) from p1 to p2 means that predicate p1 may have a direct implication on p2 through P (resp., through T ). The notion of acyclicity given above ensures that, if (p1, p2) is a P-edge in G(T ,P), then there is no path from p2 to p1, i.e. p2 has no (direct or indirect) implication on p1.

Then, let us define the following classes of DL PPKBs:

• ABox PPKB: a DL PPKB ⟨K,Kpub,P⟩ where both K and Kpub are ABoxes, i.e. it has the form ⟨A,Apub,P⟩;
• policy-full PPKB: a DL-LiteR or EL⊥ PPKB ⟨K, Kpub , P⟩ where P is a full policy;
• policy-acyclic PPKB: a DL-LiteR PPKB ⟨T ∪A, Tpub ∪ Apub, P⟩ where P is acyclic for Tpub .

We are now ready to present our initial complexity results for the LE problem, proving that it is tractable in general.

Theorem 4. LE is (i) PTIME-hard in data complexity for ABox policy-full PPKBs, and (ii) in PTIME in data complexity for both DL-LiteR PPKBs and EL⊥ PPKBs.

Next, we examine policy-acyclic PPKBs. The main computational result that we will present for these PPKBs (Theorem 5) is obtained through the definition of an FO sentence (Definition 10) whose evaluation on the ABox of the PPKB decides the LE problem in the PPKB. To arrive at such a definition, we resort to two transformations of the policy (Definition 8 and Definition 9), which augment the policy with EDs that are logically implied by the PPKB.

First, we make use of known results for tuple-generating dependencies (TGDs) [Abiteboul et al., 1995] (a.k.a. existential rules). We are able to translate EDs into TGDs (and vice versa), in a way such that we can use known reasoning methods for TGDs in the context of PPKBs. In the following, we denote by UCQRewrite(q,D) the set of CQs returned by the algorithm presented in [K¨onig et al., 2015] for rewriting a conjunctive query q with respect to a set of TGDs D.

For technical reasons, we hereafter assume the existence of a predicate Ind ∈ Σp that never occurs in a policy or a PPKB, although it may occur in CQs. Given a CQ ϕ(⃗x), we denote by ϕ+(⃗x) the CQ ϕ(⃗x) ∧ ∧x∈⃗x Ind(x), and denote by ϕ-(⃗x) the CQ obtained from ϕ(⃗x) deleting all the Ind atoms occurring in it. Moreover, for a policy P, we denote by Ptgd the following set of TGDs:

{∀⃗x (ϕ+b (⃗x) → ϕh( ⃗ xh)) | ∀⃗x (Kϕb(⃗x) →Kϕh( ⃗ xh)) ∈ P}

For such a set Ptgd, we define TGDClosure(Ptgd) as the following set of TGDs:

Definition 8. Given an acyclic policy P, we define PExp(P) as the following policy:

Intuitively, PExp(P) expands P using its own EDs as inference rules. As a simple example, consider the policy P = {∀x(K(B(x) ∧ D(x)) → KA(x)), ∀x(KC(x) → KB(x))}. Then, PExp(P) results in the policy P ∪ {∀x (K(C(x) ∧ D(x)) → KA(x))}.

The next lemma formalizes the key property of PExp(P) for our purposes.

Lemma 4. Given a KB K, an acyclic policy P, and a KB Φ such that K |= Φ, Φ is a PV in ⟨K, P⟩ iff there exists an ED τ(⃗x) ∈ PExp(P) and a ground substitution ⃗c of ⃗x such that Φ |= body(τ (⃗c)) and K ̸|= head(τ (⃗c)).

Proof (sketch). Suppose that Φ is a PV in ⟨K,P⟩. Then, by Lemma 3, K ̸|= ED-Cons(Φ, E). Consequently, there exist a sequence of EDs τ1( ⃗ x1), . . . , τj( ⃗ xj) in P and ground instantiations ⃗ c1, . . . , ⃗ cj of ⃗ x1, . . . , ⃗ xj and a sequence of sets of BCQs Ψ0 = ∅.Ψ1, . . . ,Ψj-1 such that: (i) for every i such that 1 ≤ i ≤ j - 1, Φ ∪ Ψi-1 |= body(τi(⃗ ci)) and K |= head(τi(⃗ ci)) and Ψi = Ψi-1 ∪ {head(τi(⃗ ci))}; (ii) Φ∪Ψj-1 |= body(τj(⃗ cj)) and K ̸|= head(τj(⃗ cj )).

Now. using the known properties of UCQRewrite [K¨onig et al., 2015], we can prove that there exists τ ′ ( ⃗ xj) ∈ TGDClosure(Ptgd) such that body(τ ′ ( ⃗ xj)) = q( ⃗ xj) and head(τ ′ ( ⃗ xj)) = head(τj( ⃗ xj)), therefore Φ |= body(τ ′ (⃗ cj )) and K ̸|= head(τ ′ ( ⃗ cj)), thus proving the thesis.

Then, it is easy to verify that, for every KB Φ′ , Φ |=EQL PExp(P) iff Φ′ |=EQL P. This immediately implies that, if Φ is such that there exists an ED τ(⃗x) ∈ PExp(P) and a ground substitution ⃗c of ⃗x such that Φ |= body(τ(⃗c)) and K ̸|= head(τ(⃗c)), then Φ is a PV in ⟨K, P⟩.

We now define a transformation that "compiles" the effect of a TBox T in a policy.

Definition 9. Given a policy P and a DL-LiteR TBox T , we define TExp(P, T ) as the following policy: 1

Example 5. Consider the TBox T = {D ⊑ B, E ⊑ A} and the policy P = {∀x(KB(x) → KA(x)), ∀x(KC(x) → KB(x))}. Now, observe that PerfectRef(B(x), T ) = B(x)∨ D(x) and PerfectRef(C(x), T ) = C(x). Thus, TExp(P, T ) equals P ∪ ∀x (KD(x) → KA(x)).

From now on, given a DL-LiteR PPKB E = ⟨K, Kpub , P⟩, where Kpub = Tpub ∪ Apub, we denote by Eexp the PPKB ⟨K, Apub, TExp(P, Tpub)⟩.

Based on the above definition of TExp, we are able to prove the following property.

1 Recall that PerfectRef(body(τ), T ) is a UCQ, i.e. a set of CQs.

Lemma 5. Let E = ⟨K, Kpub, P⟩ be a policy-acyclic PPKB. There exists a leakage in E iff there exists a leakage in Eexp.

Proof (sketch). First, it is possible to prove that ED-Cons(Kpub, E) = ED-Cons(Apub, Eexp). Then, recall that there exists a leakage in E iff Kpub is a leakage in E, and there exists a leakage in Eexp iff Apub is a leakage in Eexp. But, since ED-Cons(Kpub, E) = ED-Cons(Apub, Eexp), by Lemma 3 it follows that Kpub is a leakage in E iff Apub is a leakage in Eexp, which proves the thesis.

Hereinafter, we use the notation I(A) to refer to the Herbrand model of a given ABox A.

Lemma 4 and Lemma 5 imply the following property.

Lemma 6. Let S = ⟨T , Tpub,P⟩ be a policy-acyclic PPKB specification. For every PPKB E of the form ⟨T ∪ A, Tpub ∪ Apub,P⟩, there exists a leakage in E iff there exist τ(⃗x) ∈ PExp(TExp(P, Tpub)) and a ground substitution ⃗c of ⃗x such that eval(body(τ(⃗c)), I(Apub)) is true and eval(ψ( ⃗ ch), I(A)) is false, where ψ( ⃗ xh) is the UCQ returned by PerfectRef(head(τ ), T ).

The above property allows us to define an FO sentence whose evaluation on A and Apub is able to decide the LE problem for a PPKB ⟨K,Kpub,P⟩. To this aim, given a formula ϕ, we denote by Pr(ϕ) the formula obtained from ϕ replacing every predicate (concept or role) symbol p with its primed version p′ (we assume that the auxiliary set of primed predicates is disjoint from Σp), and for a set of formulas Φ we denote by Pr(Φ) the set {Pr(ϕ) | ϕ ∈ Φ}.

Definition 10. Given a PPKB specification S =

The next property, whose proof relies on Lemma 6, establishes the FO-rewritability of the LE problem for policyacyclic PPKBs.

Lemma 7. Let S = ⟨T , Tpub,P⟩ be a PPKB specification such that T and Tpub are DL-LiteR TBoxes and P is acyclic for Tpub. For every pair of ABoxes A, Apub such that T ∪A |= Tpub∪Apub, there exists a leakage in the PPKB ⟨T ∪A, Tpub∪ Apub, P⟩ iff eval(ϕleak (S), I(Apub ∪ Pr(A))) is true.

The following result is an immediate consequence of the FO-rewritability property provided by the above lemma.

Theorem 5. LE is in AC0 in data complexity for policyacyclic PPKBs.

Example 6. Consider Example 3, and recall that Φ1 is a leakage in the PPKB E ′ = ⟨K′ ,Kpub,P⟩. In the following, we call A, Apub, T and Tpub the ABoxes and DL-LiteR TBoxes such that K′ = T ∪ A, Kpub = Tpub ∪ Apub, and T = Tpub only contains the concept inclusion pathogenic ⊑ sensitive introduced (in FOL syntax) in Example 1. Now, we have that PExp(TExp(P, Tpub)) = TExp(P, Tpub) = P ∪ {τ}, where

τ = ∀p (K∃v (hasVariant(p, v) ∧ pathogenic(v)) → K⊥)

For such a τ , we have that PerfectRef(head(Pr(τ )), T ) = ⊥. Then, one of the disjuncts of ϕleak (⟨T , Tpub, P⟩) is:

Algorithm 1: ExistsGAView

input: A DL-LiteR or EL⊥ PPKB E = ⟨K, Kpub , P⟩

1 if there exists A′ ⊆ ConsGA(K) such that

2 Kpub ∪A′ |= ED-Cons(Kpub ∪A′ , E)

• 3 then return true;
• 4 return false

which is such that eval(ψ, I(Apub ∪ Pr(A))) is true.

As a corollary of Theorem 3, we get the following property. Corollary 3. Let E = ⟨K,Kpub,P⟩ be either a DL-LiteR

or an EL⊥ PPKB. Then, there exists a leakage in E iff there exists no secure CQb-view of E.

A notable implication of this finding is that all the complexity results established earlier for the LE problem also apply to (the complement of) the CQb-VE problem.

In the rest of this section, we focus on verifying the existence of a secure view that can be expressed in a language suitable for materialization. Specifically, we address the GAVE problem. We begin our discussion by providing an example that highlights the differences between secure CQb-views and secure GA-views, showing that the latter may not exist even in scenarios where the former is definable.

Example 7. Consider the following simple PPKB E = ⟨K, Kpub , P⟩ concerning patients' medical records and their participation in medical research trials.

One can verify that no secure GA-view of E exists, while E has the secure CQb-view {∃y inResTrial(r1, y)}.

Now, for DL-LiteR or EL⊥ PPKBs that are policy-full, we derive the following property as a corollary of Theorem 3.

Corollary 4. Let E = ⟨K,Kpub,P⟩ be either a policy-full DL-LiteR PPKB or a policy-full EL⊥ PPKB. Then, there exists a leakage in E iff there exists a secure GA-view of E.

From Theorem 4 and Corollary 4 it immediately follows that the GA-VE problem is PTIME-complete in data complexity in the case the given PPKB is either a policy-full DL-LiteR PPKB or a policy-full EL⊥ PPKB. More precisely, the PTIME-hardness already holds for ABox policy-full PPKBs. It is worth noting, however, that Theorem 5 and Corollary 4 imply that in all such cases the problem is in AC0 if the given PPKB is also policy-acyclic.

Then, we provide a general upper bound for the GA-VE problem, which can be demonstrated using of Algorithm 1.

Theorem 6. GA-VE is in NP in data complexity for DL-LiteR PPKBs and for EL⊥ PPKBs.

We then show that GA-VE is harder than CQb-VE (or, equivalently, the complement of LE problem) in many cases.

Theorem 7. GA-VE is NP-hard in data complexity for policy-acyclic ABox PPKBs.

Proof (sketch). We can prove the NP-hardness via a reduction from 3SAT. Specifically, given a 3CNF ψ, one can construct an ABox A that contains two facts representing the assignment of both values 1 and 0 for every propositional variable of ψ, and such that Apub contains all the facts for representing the structure of ψ. Then, P can be used for stating that every propositional variable of ψ must be assigned to a value (among the ones in A), distinct values can not be assigned to the same variable, and for every clause c there must exist a variable whose value is 1 iff it does not occur negated in c. Intuitively, an interpretation I satisfying ψ exists iff one can safely disclose a set of facts that is isomorphic to I.

7 Conclusions

In this paper, we introduced the PPKB framework for assessing the exposure of sensitive information to public knowledge. In studying the framework, we focused on two fundamental decision problems, namely the data leakage existence problem and the secure view existence problem, providing results for DL-LiteR and EL⊥ PPKBs. Our findings, summarized in Table 1, provide a detailed analysis of the data complexity of these problems across various scenarios. Notably, we proved that the problems are tractable in many cases, and even in AC0 for acyclic policies in the case of DL-LiteR.

The results we presented open several directions for future research. A natural extension involves studying these problems within the context of different ontology languages and/or richer policy languages that go beyond CQ-EDs to offer more flexible protection mechanisms. Furthermore, there is an opportunity to investigate approaches to privacypreserving query answering (such as CQE) in the presence of public knowledge. Specifically, it would be worth investigating forms of privacy-preserving query answering that are tolerant to leakages. That is, in situations where public knowledge "irrecoverably" violates the protection policy, computing views that, at the same time, are maximal in terms of disclosed information and do not expose further sensitive data.

Acknowledgements

This work was partially supported by: projects FAIR (PE0000013) and SERICS (PE00000014) under the MUR National Recovery and Resilience Plan funded by the EU - NextGenerationEU; GLACIATION project funded by the EU (N. 101070141); ANTHEM (AdvaNced Technologies for Human-centrEd Medicine) project (CUP B53C22006700001) funded by the National Plan for NRRP Complementary Investments; by the MUR PRIN 2022LA8XBH project Polar (POLicy specificAtion and enfoRcement for privacy-enhanced data management); and by the EU under the HORIZON.2.1.5 project dAIbetes (grant id. 101136305).