This extended abstract summarizes our work recently accepted to the 33rd International Joint Conference on Artificial Intelligence, in which we present a new language for data protection policies in the Controlled Query Evaluation framework, based on the use of an epistemic operator. Controlled Query Evaluation (CQE) is an approach to safeguard sensitive information by filtering query responses to prevent users from inferring data declared confidential by a data protection policy [ 1, 2, 3, 4]. A critical aspect of CQE revolves around the expressiveness of the policy language, which allows to determine the information that must remain undisclosed. Previous literature has mainly considered only policies consisting of sentences, i.e. closed logical formulas, as in [5, 2, 3, 6]. Through this approach, it is only possible to impose that the truth value of a sentence in the policy cannot be inferred by asking queries to the system. For example, in [6] policy statements take the form ∀⃗((⃗) → ⊥), referred to as denial. Enforcing one such denial over the data means refraining from disclosing the inference of the Boolean conjunctive query (BCQ) ∃⃗ (⃗) by the system, even if the inference has occurred. For instance, the rule 1 = ∀, (Patient() ∧ admitted(, ) → ⊥) aims to keep undisclosed the fact that a patient is admitted to a hospital department. One may argue that the above dependency imposes an excessively stringent level of protection, since it denies the presence of any patient in the hospital to protect their identity, which is implausible in practice. A more efective approach could require the system not to answer the open query () : ∃(Patient() ∧ admitted(, )). Intuitively, a rule of this kind expresses that the set of patients that the system knows to be admitted to the hospital must not be disclosed. To properly capture this behaviour, we propose to use an epistemic operator in policy formulas, in the spirit of [7, 8]. This allows us to formalize the epistemic state of the user, i.e., which information can be safely undisclosed for her. In our example, by expressing a rule like one could still allow the end user to infer that some patient has been admitted, while protecting the identities of all such patients. In fact, our proposal enables us to accomplish more than this. In a more advanced scenario, concealing the relationship between a patient and a hospital department should apply only if the patient has not signed a consensus form. This can be expressed by the following formula:
In essence, this formula stipulates that if a user knows a patient has been admitted, she must also know the patient has signed a consent form. Consequently, if a patient has not signed a consent form, the system cannot disclose her admission status.
Hereafter, we employ standard notions of function-free first-order (FO) logics with unary and binary
predicates and, besides the alphabets of predicate names, constants and variables, we assume the
existence of an infinite set of symbols called labeled nulls. As customary when dealing with epistemic
operators, we adopt the standard name assumption [
Formulas as 2 and 3 belong to the language of epistemic dependencies (EDs) which, in general, take
the following form:
∀⃗1, ⃗2((⃗1, ⃗2) → ℎ(⃗2))
(1)
where (⃗1, ⃗2) is a CQ with free variables ⃗1 ∪ ⃗2, ℎ(⃗2) is a CQ with free variables ⃗2, and
is a modal operator. EDs have been originally introduced in [
Intuitively, an ED of form (1) should be read as follows: if the sentence (⃗1, ⃗2) is known to hold, then the sentence ℎ(⃗2) is known to hold, for any sequences of constants ⃗1 and ⃗2 of the same length of ⃗1 and ⃗2, respectively. More formally, we say that a FO theory Φ satisfies an ED (denoted Φ |=EQL ) if, for every sequences of constants ⃗1 and ⃗2 of the same length of ⃗1 and ⃗2, respectively, the fact that eval((⃗1, ⃗2), ℐ) is true for every ℐ ∈ ℳ implies that eval(ℎ(⃗2), ℐ) is true for every ℐ ∈ ℳ, where ℳ is the set of all FO models of Φ . We say that Φ satisfies a policy (denoted Φ |=EQL ) if Φ satisfies every ∈ .
Now, to completely characterize our CQE framework, we need to specify its semantics. This issue is
addressed in CQE through censors. Here, we employ CQ-censors, introduced in [
Definition 1 (CQ-censor). A CQ-censor of a CQE instance ℰ = ⟨ , , ⟩ is a set of BCQs such that () ∪ |=EQL and () ∪ |= for every ∈ . Moreover, is an optimal CQ-censor of ℰ if there does not exist any CQ-censor ′ of ℰ such that ′ ⊃ .
As in [
Example 1. Suppose that company C wants to share certain user-profiling data with a company C for targeted advertising. This is not allowed in general, but only in some countries with a special regulation that enables sharing based on the users’ consent. C may use the following ED in the policy to enable C to access only data compliant with the above requirements:
4 = ∀, (︀ profileActivity(, ) → ∃(citOf(, ) ∧ SR() ∧ Consent()))︀ .
In the rule, profileActivitylinks a user with her profiling-data, citOf relates a user to her country of citizenship, SR denotes countries with special regulation, and Consent denotes users who have given their consent.
Suppose that C also wants C not to be able to associate to a user with her real identity, and that this is possible by collecting the person’s name and her date of birth at the same time. To this aim, C also specifies the ED:
5 = ∀, , (︀ (name(, ) ∧ dateB(, )) → ⊥)︀ .
Now, let ℰ = ⟨ , , ⟩ be a CQE instance, where = ∅, = { 4, 5}, and is as follows: = { profileActivity(u1, a1), Consent(u1), citOf(u1, 1), SR(1), name(u1, ann),
dateB(u1, date1), profileActivity(u2, a2), citOf(u2, 1) }, where 1 is a labeled null and all the other terms used in are constants. Let us also consider the following four BCQs: 1 = ∃ (profileActivity(u1, a1) ∧ citOf(u1, ) ∧ SR()), 2 = profileActivity(u2, a2), 3 = ∃ profileActivity(, a2), 4 = profileActivity(u1, a1) ∧ name(u1, ann).
For ∈ {SC, IC}, one can verify that ℰ |= 1 since user u1 gave the consent and she is a citizen of some country (1) with special regulation. Conversely, ℰ ̸|= 2 since u2 did not give the consent. Nevertheless, one can verify that 3 belongs to each optimal CQ-censor of ℰ , and so ℰ |= 3. Finally, we have that ℰ ̸|= 4 since there is an optimal CQ-censor of ℰ such that dateB(u1, date1) ∈ , implying that name(u1, ann) ̸∈ (otherwise 5 would be violated).
We focus on TBoxes specified in DL-Liteℛ [
Theorem 1. In the case of CQE instances with DL-Liteℛ TBoxes, both SC-entailment and IC-entailment of BUCQs are coNP-complete in data complexity.
We remark that, in the above findings, the hardness for coNP holds already when the TBox is empty and the query is a ground atom. To regain tractability, we then impose an acyclicity condition on the policy w.r.t. a DL-Liteℛ TBox , defined as follows.
Definition 2 (Acyclicity). We call dependency graph of ( , ) the direct graph whose nodes are the predicates occurring in ∪ , and whose edges (1, 2) correspond to the presence of 1 in the left-hand side and 2 in right-hand side of either an ED in (we call such edges P-edge) or a positive inclusion axiom in . We say that is acyclic for if there exists no cycle involving a P-edge in the dependency graph of ( , ).
For this class of epistemic policies, we are able to provide first-order rewriting algorithms for deciding if a BUCQ is SC- or IC-entailed by a CQE instance, thus proving the following result. Theorem 2. In the case of CQE instances with DL-Liteℛ TBoxes and epistemic policies acyclic for , both SC-entailment and IC-entailment of BUCQs are in AC0 in data complexity.
Besides the computational complexity study, we also carry out an analysis of the robustness of the
above-defined entailment semantics w.r.t. confidentiality-preservation. In [
Definition 3 (Confidentiality preservation) . For ∈ {SC, IC}, we say that -entailment preserves confidentiality for BCQs (resp., BUCQs) if, for every CQE instance ⟨ , , ⟩, and for every finite set of BCQs (resp., BUCQs), there exists an ABox ′ such that the following holds: () ∪ ′ |=EQL ; () and ′ are -indistinguishable for X-entailment with respect to ( , ).
In the case of DL-Liteℛ ontologies, we can show that SC-entailment preserves confidentiality for BCQs, but this result does not carry over to BUCQs. We however prove that the property is enjoyed even for BUCQs in the case of IC-entailment.
Acknowledgments 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; the MUR PRIN 2022LA8XBH project Polar (POLicy specificAtion and enfoRcement for privacy-enhanced data management); and by the EU under the H2020-EU.2.1.1 project TAILOR (grant id. 952215). [11] B. Cuenca Grau, E. Kharlamov, E. V. Kostylev, D. Zheleznyakov, Controlled query evaluation for datalog and OWL 2 profile ontologies, in: Proc. of the 24th Int. Joint Conf. on Artificial Intelligence (IJCAI), 2015, pp. 2883–2889. [12] J. Biskup, T. Weibert, Keeping secrets in incomplete databases, Int. J. Inf. Sec. 7 (2008) 199–217. [13] P. A. Bonatti, A false sense of security, Artificial Intelligence 310 (2022).