In querying semantic data, access control must take into account the information that is implicitly entailed by the accessible part of triple stores and ontologies. While there exist inference control frameworks for this purpose, they still have a limitation: the confidentiality criterion does not take into account the probabilistic knowledge of the attacker. Therefore, the existing controlled query evaluation methods may return answers that actually reveal that a secret is true with very high probability. Given that such probabilistic knowledge is becoming more and more widely available as a result of analytics of various sorts, it is important to develop a refined confidentiality framework where probabilistic knowledge is taken into due account. Accordingly, in this paper, we extend and generalize an abstract data filtering framework for confidentiality-preserving, policybased data publishing. The confidentiality requirement is strengthened so that the probability that a secret is true is bounded by a small constant . We formally define such a probabilistic setting, then we study two greedy data publishing methods based on refusals and lies, respectively. The refusal-based method is proved to be secure and maximally cooperative among a class of “reasonable” methods. We prove also that the natural generalization of the lying method is not secure. Furthermore, we extend the complexity hardness results from the deterministic framework to the probabilistic one.
The need for inference-proof data publishing has been discovered well before the semantic web was born. Still, semantic (meta)data, that are expressed with standardized knowledge representation languages such as RDFS and OWL, are by design well-suited to the automated derivation of implied data. The applicable inference engines are becoming more and more powerful and scalable. This makes the need of inference-proof access control techniques particularly crucial in this area.
The literature is rich of data filtering methods for confidentiality-preserving data
publishing (cf. [
For no secret query should a user be able to derive a “yes” answer, no matter how powerful is the rational reasoning method exploited by the user and no matter how many resources are employed. In this framework, confidentiality relies on the assumption that one counterexample suffices to prevent the user from believing that the secret is true.
However, reality may be different. The wide range of analytics tools for semantic data provide rich statistical information about the real world, that may make the available counterexamples unlikely. Moreover, if the majority of the interpretations of a knowledge base agree that a secret is true, the user may be inclined to believe it. To put this in general terms, a variety of probabilistic information may lead the user to believe that a secret is actually true with high probability. Then the aforementioned confidentiality framework should be refined by strengthening its confidentiality criterion so as to accommodate a priori probabilistic information about the domain of discourse.
Accordingly, in this paper, we generalize and extend the setting of [
Example 1. Let us consider a simple artificial situation where the set of data sources contains the 8 possible interpretations of 3 RDF triples p, q and r, represented by the words pqr, pqr, pqr, pqr, pqr, pqr, pqr, pqr. Intuitively speaking, the filtering should keep a joint validity of p and q confidential, formally expressed by the query S = fpqr; pqrg, (the characteristic function of) which returns “yes” (true) for the two interpretations with representation pq , and “no” (false) otherwise. Accordingly, the confidentiality policy is just the singleton fSg.
A straightforward filtering f hides the secret when applied to an interpretation by setting the first variable always to p. Since in general we will allow uncertainty in a generated view, a filtering will return a set of data sources, and thus this filtering is formally defined by generating f (xyz) := fpyzg. However, seeing the verbatim view fpyzg, an intelligent and knowledgeable observer can easily determine the inferred view fpyz; pyzg, each of whose elements might be the actual data source underlying the filtering. Nevertheless, since fpqr; pqrg 6 fpyz; pyzg, an observer will always believe in the possibility that the secret is not valid in the actual data source. For our probabilistic setting we are even more ambitious: we want the observer to believe in a probability of the non-validity of the secret not less than 1 , for some security parameter 2 [0; 1].
So let us further assume that the anticipated observer is knowing a priori the following probability distribution : each of the two protected interpretations occurs only relatively rarely, with probability 116 ; each of the two interpretations containing both p and q are more likely, having probability 136 ; and each of the remaining four interpretations containing either p or q are equally distributed, with probability 126 . Then we have (S) = (fpqr; pqrg) = 116 + 116 = 81 . By similar elementary calculations, for each case we can determine the a posteriori probability of the secret being valid under the condition of the inferred view based on the observation of the verbatim view. For the straightforward filtering f defined above and the assumed probability distribution the calculations show that these probabilities are either 13 or 0, and thus the filtering is seen to be secure for each security parameter in the open interval ( 13 ; 1].
This example is summarized in Table 1, and variants of it are serving throughout the paper.
Popular probabilistic models and approaches have already been introduced.
Differential privacy [
Accordingly, in this paper we provide as a further contribution a maximally cooperative, secure query-answering method based on a greedy refusal-based algorithm. We prove also that – differently from the deterministic case – its lying-based analogue is not secure, instead. Finally, we extend some of the computational hardness results from the deterministic framework to the probabilistic one.
This abstract framework should be regarded as a preliminary, general feasibility study that constitutes the first step towards inference-proof, confidential access control methods for semantic data. Thus the implementation of concrete mechanism still lies beyond the scope of this paper.
The paper is organized as follows. After formally defining the probabilistic setting in Section 2, we analyze the safety of the greedy filtering methods based on refusal and lying in Section 3 and Section 4, respectively. In Section 5, we investigate the degree of cooperativeness of the greedy refusal method (a form of optimality). Section 6 reports the complexity results. Finally, in Section 7, we briefly summarize and evaluate our achievements, discuss related work, and list some challenging open problems. 2
As in the deterministic case presented in [
We refer to [
Some subsets Q of D can be regarded as a Boolean query, indicating whether a data source d satisfies Q, i.e., d 2 Q, or not, i.e., d 62 Q. To comply with the probabilistic framework, each query must be measurable. Let B D be the set of queries considered. Clearly, since queries have to be expressed syntactically, B is countable.
To keep some aspects of his data source secret to the observer, the owner can specify a confidentiality policy consisting of a finite set S B of queries, in this context called (potential) secrets. Informally speaking, if the owner’s data source satisfies a secret then the observer should not be able to learn this fact; conversely, the observer is allowed to know that a secret is not satisfied.
To preserve secrets, the owner applies a filtering f : D ! }(D ) n f;g on his actual data source d and publishes f (d) as a (verbatim) secure view, making the observer uncertain about which data source in f (d) is the actual one, and possibly even misleading the observer by not including the actual data source d in f (d). Assuming that the observer is a rational agent that knows the filtering f , the observer can compute the inferred filtering [ ]f : D ! }D n f;g, defined by
[ d ]f := f d0 j f (d) = f (d0) g :
3 Function is the analogue of the data generation function P of [
Finally, to complete the probabilistic setting, we require that [ d ]f 2 D , i.e., each set [ d ]f of data sources indistinguishable under f is supposed to be measurable. Then we strengthen the security criterion by requiring that the probability that a secret is satisfied by d – given the observable view f (d) – should not exceed a (small) threshold . Definition 1. For a probabilistic setting with a priori knowledge : D ! [0; 1], confidentiality policy S , and threshold 2 [0; 1], a filtering f : D ! }(D ) n f;g with measurable inferred views is ( ; S ; )-secure iff for all data sources d 2 D , for all secrets S 2 S , it holds that Note that inequality (2) means that, whenever defined (i.e., ([ d ]f ) 6= 0), the conditional probability of S under the inferred view [d ]f (S \ [ d ]f )
([ d ]f ) : ( S j [ d ]f ) := (S \ [ d ]f ) ([ d ]f ) (2) (3) (4) 4 Roughly speaking, an ASK form is a query that returns true if the RDF-graph satisfies a specified graph pattern, false otherwise. Graph patterns allow to verify, for example, whether a confidential set of RDF-triples or a specified node denoting some sensible individual occurs in the graph. is bounded by .
The abstract framework presented so far can be embodied in the context of Linked Data as follows: data sources consist of RDF-graphs, Boolean queries are represented by ASK forms of SPARQL4 and secrets are specific Boolean queries, i.e. confidential pieces of information that can be retrieved through (a sequence of) ASK forms. Moreover, the a priori knowledge of the observer is represented by a probability distributions over possible RDF-graphs. More precisely, the set D is the set of all possible RDFgraphs over a given signature of interest and D is the whole powerset }(D ). Then, is determined by a discrete probability distribution over RDF-graphs such that for all A D , (A) = X (d) :
d2A Finally, a Boolean query Qa is the denotation of a ASK form a, that is the set of RDFgraphs where the form a returns true.
In the remainder of this paper, we will study the secure filterings f that result from a greedy construction of a decreasing sequence of sets Li(d) of data sources, for each input data source d 2 D :
D =: L0(d)
L1(d)
Li(d) \ Li(d) := f (d) : i All constructions will be based on an exhaustive enumeration Ben = hQ1; : : : ; Qi; : : : i of all queries in B. Stepwise, each query Qi is submitted to a kind of stateful censor that keeps track of previous answers to determine whether Qi should be answered correctly or distorted. This decision determines Li(d) from Li 1(d).
The sequence hLi(d)ii has also a dynamic interpretation. The observer chooses the queries Q1; Q2; : : : ; Qi; : : : and submits them iteratively to the confidential data source. The query answering system returns for each Qi the corresponding direct answer Ai(d), leaving the computation of the accumulated information represented by Li(d) to the observer. In this dynamic setting, the confidentiality criterion is that at each step i, the accumulated information Li(d) of the direct answers to Q1; Q2; : : : ; Qi should not tell too much about the secrets. 3
Under the refusal approach to data filtering, harmful queries are somehow explicitly notified to be hidden. In a dynamic query-answering environment, this may result in returning the special answer “mum” to a query whose correct answer would violate the confidentiality policy.
In the data filtering framework there is yet another interpretation of the refusal approach: some specific information about the actual data source is hidden by providing a view which contains not only the actual data source but also other data sources. If this generation of uncertainty is properly done, then the observer cannot know which element of the view is the actual one, therefore he is not able to infer that specific information.
A crucial point of the refusal approach is to block so-called meta-inferences. For
instance, if a filtering f refused only the queries that entail a secret, then refused
answers would always correspond to a secret satisfied by the actual data source d. The
basic strategy for blocking this kind of attacks is to make the critical part of the censor
decision independent from the actual data source. This strategy has already been
proposed in the seminal work [
Using the notations of Definition 1 and instantiating (4), for an enumeration Ben = hQ1; : : : ; Qi; : : : i of all queries in B, the (greedy) refusal filtering fre results from the iterative application of the following distortion criterion to each query Qi: IF [censor criterion evaluating Qi’s harmfulness in a d-independent way] for some secret S 2 S , ( S \ Li 1(d) \ Qi) > ( Li 1(d) \ Qi) or ( S \ Li 1(d) \ Qi) > ( Li 1(d) \ Qi) THEN [distortion by refusal]
Li(d) := Li 1(d) ELSE [honest answer w.r.t. d]
Ai(d) := IF d 2 Qi THEN Qi ELSE Qi Li(d) := Li 1(d) \ Ai(d) Example 2. Resuming Example 1 with (S) = (fpqr; pqrg) = 116 + 116 = 126 , we consider the refusal filtering for d := pqr. We choose := 166 as security parameter and take the powerset of the set of all interpretations over the propositional variables p, q and r as the set of all queries.
We start the enumeration of the 28 queries by “p?”, intuitively asking whether p is valid, formalized as Q1 := fpqr; pqr; pqr; pqrg with (Q1) = 166 . Then Q1 := fpqr; pqr; pqr; pqrg with (Q1) = 1106 . Accordingly, (S \ Q1) = (fpqr; pqrg) = 126 a12n0d<(S166\anQd1) (=S j Q(;1)) ==00. E<val1u66a,tianngdththeucsenthseorhinognecsotnadnistiwonerwAe1g(petqr)(S:=j QQ1)1 =is processed to determine L1(d) := Q1.
We continue the enumeration with the query “q?”, intuitively asking whether q is valid, formalized as Q2 := fpqr; pqr; pqr; pqrg. Evaluating the censoring condition, we then get (L1(d) \ Q2) = (fpqr; pqrg) = 126 and (S \ (L1(d) \ Q2)) = (fpqr; pqrg) = 126 , and thus (S \ (L1(d) \ Q2) j(L1(d) \ Q2) ) = 1 leads to a refusal resulting in L2(d) := L1(d) = fpqr; pqr; pqr; pqrg.
Further continuing with “r?”, i.e., Q3 := fpqr; pqr; pqr; pqrg, we get (L2(d) \ Q3) = (fpqr; pqrg) = 136 and (S \(L2(d)\Q3)) = (fpqrg) = 116 and thus (S \ (L2(d) \ Q3) j(L2(d) \ Q3) ) = 13 < 166 as well as (L2(d) \ Q3) = (fpqr; pqrg) = 136 and (S \ (L2(d) \ Q3)) = (fpqrg) = 116 and thus (S \ (L2(d) \ Q3) j(L2(d) \ Q3) ) = 13 < 166 , leading to an honest reaction such that L3(d) := L2(d) \ A3(d) = fpqr; pqrg.
Though somehow tedious to check, all further queries do not change that intermediate view and, thus, for the actual data source pqr we get fpqr; pqrg as the final verbatim view, leaving an observer uncertain whether or not q is valid. One may note that in Example 1 we got the verbatim view fpqr; pqrg leaving the status of p open; we would obtain this result by the refusal filtering if we exchanged the processing of the first two queries.
Clearly, in the context of RDF-graphs considered above, the presented approach requires that an ASK form returns a notification of the kind query_refused in case of refusal.
Example 3. Consider an RDF-graph containing sensible information about medical treatments in a small town of 10 000 citizens. For privacy reasons, we want to enforce anonymity by preventing the identification of any specific person with a confidence larger than 0:5. Then, Oreste Galli, who actually occurs in the data source, wants to verify that the refusal framework works properly by maliciously querying the system about himself. In particular, he considers two queries, the former asks whether there exists an individual in the graph whose name is Oreste, the latter asks for the presence of an individual who has the same address Machiavelli Street. The previous queries may look like:
Q1 = ASK(?x Q2 = ASK(?x ex : given_name
\Oreste") ex : street_address \Machiavelli") The a priori knowledge is that (i) the data source contains the 1% of the whole population, (ii) 10 people are called Oreste, and (iii) 15 people live in Machiavelli Street. Then, by the applying the Bayes’ theorem, the conditional probability to infer the secret S that Oreste Galli occurs in the data source by querying Q1 is given by (S j Q1) = (Q1 j S) (Q1) (S)
: Note that the fact that Oreste Galli occurs in the graph implies that there exists a person called Oreste; in other words, since S Q1, we have that (Q1jS) = 1. Furthermore, (S) is the prior probability that Oreste Galli occurs in the graph, which is equal to the percentage of people occurring in the graph, i.e. 0:01. Finally, (Q1) is the probability that, given a generic graph containing the 1% of the whole population, there exists at least one person in the graph called Oreste. This is given by the formula: (Q1) =
N
N
K
; where N = 10 000 is the number of all possible graphs containing the 1% of the whole 100 population, and K is the number of possible graphs where no Oreste occurs. Since only 10 people over 10 000 are called Oreste, K = 9190900 . Then, we straightforwardly have that (S j Q1) = 0:104.
Note that, since S Q1, it follows that (S j Q1) is equal to zero. Consequently, since (S j Q1) < 0:5, the censor correctly answers to Q1. Then, the user queries Q2. By using again the Bayes’ theorem, the censor estimates the conditional probability of S given Q2, provided that Q1 has been already answered and hence the prior probability is 0:104 instead of 0:01. By similar calculation, the resulting probability is 0:74, subsequently the censor refuses Q2.
Theorem 1. Let Ben be an enumeration of B. For each , S and 2 [0; 1], fre is filtering function with measurable inferred views; moreover, fre is ( ; S ; )-secure, provided the following precondition holds: (S) = (S \ L0(d)) (L0(d)) ; for all S 2 S :5
Fact 1: fre(d) [d]fre . Assume that d0 2 fre(d), we will show by induction on the iterative construction of fre that fre(d0) = fre(d); consequently, d0 2 [d]fre . Since L0(d0) = D = L0(d), the base case i = 0 trivially holds. Let i > 0 and assume by induction hypothesis that Li 1(d) = Li 1(d0). Clearly, then for all S 2 S , both (S j Li 1(d) \ Qi) = (S j Li 1(d0) \ Qi) and (S j Li 1(d) \ Qi) = (S j Li 1(d0) \ Qi); this means that the refusal behavior of the censor to the query Qi will be the same for both d and d0. Moreover, since d0 2 fre(d), we also have that d0 2 Ai(d) and, hence, Ai(d) = Ai(d0). Consequently, Li(d) = Li(d0).
Fact 2: d 2 fre(d). Again, by induction on the iterative construction of fre, the base case, d 2 L0(d) = D , holds. Furthermore, assume that d 2 Li 1(d), where i > 0. 5 This precondition is required since no secret which is violated ex ante can be protected by any filtering. If the censor refuses Qi, then Li(d) = Li 1(d) and the induction hypothesis directly implies that d 2 Li(d). Otherwise, Li(d) = Li 1(d) \ Ai(d). Since by induction hypothesis d 2 Li 1(d) and by construction d 2 Ai(d), also in this case d 2 Li(d).
Fact 3: [d]fre fre(d). Assume d0 2 [ d ]fre , i.e., fre(d) = fre(d0). By Fact 2, d0 2 fre(d0) so we have d0 2 fre(d).
That fre is a filtering function, i.e. fre(d) 6= ; for all d 2 D , directly follows from Fact 2. Moreover, by Fact 1 and 3, fre(d) = [d]fre . Note that, since B D and fre(d) consists of a countable intersection of elements of B or their complements, fre(d) 2 D and hence [d]fre 2 D too. Finally, the statement’s precondition and the definition of fre immediately imply the following invariant: (S \ Li(d))
(Li(d)) ; for all i and for all S 2 S : Hence, taking the limits, it holds that: lim i (S \ Li(d)) lim i (Li(d)) : On the other hand, by the \-continuity of , (fre(d)) = (Ti Li(d)) = limi (Li(d)) and (S \ fre(d)) = (S \ Ti Li(d)) = ( Ti(S \ Li(d))) = limi (S \ Li(d)). Putting all together, we have that (S \ fre(d)) (fre(d)) : The theorem immediately follows by reminding that fre(d) = [d]fre . tu Remark 1. The above theorem and its proof show that the refusal approach is inferenceproof in a very strong sense. Namely, as fre(d) always coincides with [d]fre , inferring does not provide any information beyond what is immediately visible from the verbatim view. Moreover, the two views contains only limited information about the secrets, as specified by the security parameter . 4
Under the lying approach to data filtering a harmful piece of data is implicitly distorted, without any notification, by saying that it is false. In a dynamic query-answering environment, such a distortion consists in returning the complement of the correct answer to a query Q whenever the correct answer violates the confidentiality policy. In the framework of data filterings, lying aims at providing a view that contains a single data source (if necessary, different from the actual one) where all the secrets are false.
A crucial point of the lying approach is to make a current answer consistent with
previously accumulated knowledge and to prepare for being able to provide definite
(though possibly untrue) answers to any further queries. The basic strategy for
achieving these goals is to always protect the disjunction of all secrets (in the abstract
framework, their union). This strategy has already been proposed in the seminal work [
Interestingly, the natural probabilistic generalization of the deterministic greedy
lying approach defined in [
Using the notations of Definition 1 and instantiating (4), for an enumeration Ben = hQ1; : : : ; Qi; : : : i of queries in B, the natural probabilistic generalization of the (greedy) lying filtering fly is obtained by iteratively applying the following distortion mechanism to all queries Qi (i = 1; 2; : : :):
Ai(d) := IF d 2 Qi THEN Qi ELSE Qi IF [censoring by checking harmfulness of the correct (d-dependent) answer] ( S S \ Li 1(d) \ Ai(d)) > (Li 1(d) \ Ai(d)) THEN [distortion by lying]
Li(d) := Li 1(d) \ Ai(d) ELSE [honest answer w.r.t. d]
Li(d) := Li 1(d) \ Ai(d) The precondition for applying the greedy lying method, by analogy with the deterministic case, should be: [ S : Proposition 1. There exist , S and for which the above precondition is satisfied but fly is not ( ; S ; )-secure.
Proof. Let us consider the following setting. The set of data sources D = fd1; d2; d3g. The a priori knowledge for di is described by the following measures: (d1) = 0:7, (d2) = 0:2 and (d3) = 0:1. The confidentiality policy S contains only the secret S = fd2g, i.e., S = ffd2gg. The value of the threshold is given by = 0:5. The set of queries B = }(D ). We employ the following enumeration for the queries Ben = hQ1; : : : ; Q8i, where the Qi are defined as follows: Q1 = fd2g = S, Q2 = fd2; d3g, Q3 = ;, Q4 = fd1g, Q5 = fd3g, Q6 = fd1; d2g, Q7 = fd1; d3g, Q8 = fd1; d2; d3g.
Let us then examine the execution of the filtering fly as defined above. We first show the computation for the data source d2. We start by L0(d2) = D = fd1; d2; d3g. The answers to the queries are computed as follows, where – in order to easy the presentation – we will use the notation i(d) = ( S S j Li 1(d) \ Ai(d)) = (fd2g j Li 1(d) \ Ai(d)): – Q1 = fd2g: Since d2 2 Q1, it follows that A1(d2) = Q1 = fd2g and, thus, L0(d2) \ A1(d2) = fd2g. We obtain that 1(d2) = ( S S j L0(d2) \ A1(d2)) = (fd2g jfd2g) = 1 = 0:5. In this case, the filter lets
L1(d2) = L0(d2) \ A1(d2) = fd1; d2; d3g \ fd1; d3g = fd1; d3g : – Q2 = fd2; d3g: Since d2 2 Q2, it follows that A2(d2) = Q2 = fd2; d3g and, thus, L1(d2) \ A2(d2) = fd3g. We obtain that 2(d2) = (fd2g jfd3g) = 0 and, thus, L2(d2) = L1(d2) \ A2(d2) = fd1; d3g \ fd2; d3g = fd3g :
L3(d2) = L2(d2) \ A3(d2) = fd3g \ fd1; d2; d3g = fd3g :
L4(d2) = L3(d2) \ A4(d2) = fd3g \ fd2; d3g = fd3g : – Q5 = fd3g: Since d2 62 Q5, it follows that A5(d2) = Q5 = fd1; d2g and, thus, L4(d2) \ A5(d2) = ;. In this case the filter computes
L5(d2) = ; : The complete construction of fly is summarized in Table 2. Given the above table, we can write that [d1]fly = fd1g and [d2]fly = [d3]fly = fd2; d3g. This means that ( S S j [d2]fly ) = (fd2g j fd2; d3g) = 23 > , thus the proposition follows. tu
Proposition 1 shows that the natural probabilistic generalization of the greedy lying approach is not secure. The existence of secure probabilistic variants of greedy lying is left as an open problem.
In this section we show that, under some natural assumptions, the greedy method based
on refusals is maximally cooperative, that is, it hides a minimal amount of information.
Maximal cooperativeness is formalized in [
Currently, we do not know whether the greedy refusal filtering fre is optimal in this strong sense. It is difficult to compare fre with arbitrary filterings g because g might exploit partitions (i.e. secure views) that cannot be denoted with the query language (while fre, by construction, can only exploit the expressive power of B). What we are going to prove is that fre is maximally cooperative among the filterings whose views can be defined using B. This class of filtering is formally defined as follows: Definition 4. A filtering g is query-based iff for all d 2 D , there exists a query Q 2 B such that [d]g = Q.
To prove the optimality of fre with respect to query-based filterings, we adopt some mild restrictions. We assume that data sources are countable:
D = fd1; d2; : : : ; di; : : :g: For example, this is true of knowledge bases, as well as database tables whose values range over countable domains such as strings, integers and rational numbers. A property of this discrete framework is that all (possibly infinite) collections of pairwise disjoint subsets of D are countable.6 The cooperativeness theorem is now formalized as follows: Theorem 2. If D is countable, then there exists no ( ; S ; )-secure query-based filtering g such that g fre.
Proof. In the following, for the sake of readability, we abbreviate fre with f . Suppose the theorem does not hold (we will derive a contradiction). Then there exists a ( ; S ; )secure query-based filtering g f . This means that for all d 2 D , [d]g [d]f and for some d0 2 D , [d0]g [d0]f .
Since g is query-based, for some step k of the greedy construction the query Qk satisfies Qk = [d0]g. Note that in f ’s construction, Qk is refused (otherwise [d0]f [d0]g would hold, which is a contradiction). This means that for some secret S0 2 S , either (S0 \ Lk 1(d0) \ Qk) >
(Lk 1(d0) \ Qk); or (S0 \ Lk 1(d0) \ Qk) > (Lk 1(d0) \ Qk) : (5) (6) Note that Lk 1(d0) [d0]f [d0]g = Qk , therefore (5) entails (S0 \ [d0]g) > ([d0]g). This disequality cannot hold, because g is ( ; S ; )-secure by assumption, so (5) does not hold, and hence (6) must hold.
Finally, we prove that the security of g implies that (6) should not hold, instead, which proves the theorem. 6 To see this, associate each X
Let C = f[d]g j d 2 Lk 1(d0) \ Qkg. Recall that C can be enumerated, because its elements are pairwise disjoint: so let C = fX1; X2; : : : ; Xi; : : :g, where each Xi is an equivalence class induced by g.
Since g is ( ; S ; )-secure, for all Xi 2 C we have (S0 \ Xi)
(Xi):
(S0 \ Lk 1(d0) \ Qk) = (S0 \ [ C ) 1 = X i=1 1 X i=1 = = (S0 \ Xi) (Xi)
by (7) ( [ C ) ( Lk 1(d0) \ Qk ) : This contradicts (6). 6
The computational complexity of the non-probabilistic framework has been studied in
[
Proposition 2. For all S
sense of [
B, a filtering is ( 0; S ; 0)-secure iff it is secure in the
Thanks to this proposition, all the computational hardness results of [
Extending recent work [
We proved that a natural, probabilistic generalization of the refusal-based controlled query evaluation approach is both secure and maximally cooperative among a class of “reasonable” filterings, that define their secure views using the query language. Interestingly, the corresponding lying approach is not secure (differently from the deterministic framework). Finally, computational hardness results for some decision problems have been extended from the deterministic case to the probabilistic case.
The security criterion can be easily modified by associating a different threshold i to each secret Si, and adapting the precondition of Theorem 1 accordingly. In this way one can simulate relativistic privacy preservation requirements, where the inferred probability of each secret S remains close to the prior probability (S) of S, just by defining the thresholds as i = (Si) + ~i. Then the precondition of Theorem 1 is satisfied by the definitions. Proofs do not require any significant changes.
Our work continues a long line of research on imposing confidentiality constraints
on computing system, including logic-oriented information systems used for query
answering and data publishing. The research line on refusals and controlled interaction
execution has been devoted to non-probabilistic methods, so far [
Similarly, the non-interference property for inference control in non-logical,
operational settings has originally not been probabilistic [
Other popular methods, such as k-anonymity with l-diversity [
Halpern and O’Neill studied probabilistic secrecy in the context of dynamic
systems [
The methods based on lies (which have been extensively studied in the above
nonprobabilistic contexts) can be regarded as the mainstream method in probabilistic
methods, in the form of random answer perturbations [
Recent more thorough comparisons and discussion of various probabilistic
approaches to enforce confidentiality of sensitive information in provider-consumer
interactions are provided by [
The challenges for future work include dealing with the inherent complexity of
some decision problems of interest (see, e.g., [