No-Go Theorems for Data Privacy

Controlled query evaluation (CQE) refers to a data privacy mechanism where the database (or knowledge base) is equipped with a censor function. This censor checks for each query whether the answer to the query would reveal sensitive information to a user. If this is the case, then the censor will distort the answer. Essentially, there are two possibilities how an answer may be distorted:

1. 1.

   the CQE-system may refuse to answer the query [18] or

2. 2.

   the CQE-system may give an incorrect answer, i.e. it lies [10].

This censor based approach has the advantage that the task of maintaining privacy is separated from the task of keeping the data. This gives more flexibility than an integrated approach (like hiding rows in a database) and guarantees than no information is leaked through otherwise unidentified inference channels. Controlled query evaluation has been applied to a variety of data models and control mechansims, see, e.g. [5, 6, 7, 8, 9, 21].

No-go theorems are well-known in theoretical physics where they describe particular situations that are not physically possible. Often the term is used for results in quantum mechanics like Bell’s theorem [4], the Kochen–Specker theorem [15], or, for a more recent example, the Frauchiger–Renner paradox [12]. Nurgalieva and del Rio  [16] provide a modal logic analysis of the latter paradox. Arrow’s theorem [2] in social choice theory also is a no-go theorem stating that no voting system can be designed that meets certain given fairness conditions. Pacuit and Yang  [17] present a version of independence logic in which Arrow’s theorem is derivable.

In the present paper we develop a highly abstract model for dynamic query evaluation systems like CQE. We formulate several desirable properties of CQE-systems in our framework and establish two no-go theorems saying that certain combinations of those properties are impossible. The main contribution of this paper is the presentation of the abstract logical framework as well as the high-level formulation of the no-go theorems. Note that some particular instances of our results have already been known [5, 21].

There are many different notions of privacy available in the literature. For our results, we rely on provable privacy [19, 20], which is a rather weak notion of data privacy. Note that using a weak definition of privacy makes our impossibility theorems actually stronger since they state that under certain conditions not even this weak form of privacy can be achieved.

Clearly our work is also connected to the issues of lying and deception. Logics dealing with these notions are introduced and studied, e.g., in [1, 22, 13].

Let $X$ be a set. We use $\mathcal{P}(X)$ to denote the power set of $X$. For sets $\Gamma$ and $\Delta$ we use $\Gamma,\Delta$ for $\Gamma\cup\Delta$. Moreover, in such a context we write $A$ for the singleton set $\{A\}$. Hence $\Gamma,A$ stands for $\Gamma\cup\{A\}$.

Transitivity is sometimes called cut. The previous definition gives us single conclusion consequence relations, which is sufficient for the purpose of this paper. For other notions of consequence relations see, e.g., [3] and [14].

As usual, we write $\vdash_{\mathsf{L}}A$ for $\emptyset\vdash_{\mathsf{L}}A$. A formula $A$ is called a theorem of $\mathsf{L}$ if $\vdash_{\mathsf{L}}A$.

We do not specify the logic $\mathsf{L}$ any further. The only thing we need is a consequence relation as given above. For instance, $\mathsf{L}$ may be classical propositional logic with $\vdash_{\mathsf{L}}$ being the usual derivation relation (see Section 4) or $\mathsf{L}$ may be a description logic with $\vdash_{\mathsf{L}}$ being its semantic consequence relation [21].

We need a simple modal logic $\mathsf{M}$ over $\mathsf{L}$.

We define the remaining classical connectives $\top$, $\land$, $\lor$, and $\lnot$ as usual. Note that $\mathsf{M}$ is not a fully-fledged modal logic. For instance, it does not include nested modalities.

We give semantics to $\mathsf{Fml}_{\mathsf{M}}$-formulas as follows.

We use the following standard definition.

Note that in the above definition, $\mathsf{KB}$ and $\mathsf{Sec}$ are sets of $\mathsf{Fml}_{\mathsf{L}}$-formulas while $\mathsf{AK}$ is a set of $\mathsf{Fml}_{\mathsf{M}}$-formulas. Thus $\mathsf{AK}$ may not only contain domain knowledge but also knowledge about the structure of $\mathsf{KB}$. This is further explained in Section 4.

A query to a knowledge base $\mathsf{KB}$ is simply a formula of $\mathsf{Fml}_{\mathsf{L}}$.

Given a logic $\mathsf{L}$, we can evaluate a query $q$ over a knowledge base $\mathsf{KB}$. There are two possible answers: $t$ (true) and $u$ (unknown).

If the language of the logic $\mathsf{L}$ includes negation, then one may also consider an evaluation function that can return the value $f$ (false), i.e. one defines $\mathsf{eval}(\mathsf{KB},q):=f$ if $\mathsf{KB}\vdash_{\mathsf{L}}\lnot q$. However, in the general setting of this paper, we cannot include this case.

A censor has to hide the secrets. In order to achieve this, it can not only answer $t$ and $u$ to a query but also $r$ (refuse to answer). We denote the set of possible answers of a censor by

Let $X$ be a set. Then $X^{\omega}$ denotes the set of infinite sequences of elements of $X$.

Usually, the privacy configuration will be clear from the context. In that case we simply use $\mathsf{Cens}$ instead of $\mathsf{Cens}_{(\mathsf{KB},\mathsf{AK},\mathsf{Sec})}$.

Given a sequence $s$, we use $s_{i}$ to denote its $i$-th element. That is for a query sequence $q\in\mathsf{Fml}_{\mathsf{L}}^{\omega}$, we use $q_{i}$ to denote the $i$-th query and $\mathsf{Cens}(q)_{i}$ to denote the $i$-th answer of the censor.

In this paper, we will consider continuous censors only, which are given as follows.

Continuity means that the answer of a censor to a query does not depend on future queries, see also Lemma 14.

A censor is called truthful if it does not lie.

Hence a truthful censor may refuse to answer a query in order to protect a secret but it will not give an incorrect answer.

In the modal logic $\mathsf{M}$ over $\mathsf{L}$, we can express what knowledge one can gain from the answers of a censor to a query. This is called the content of the answer.

The following is a trivial observation showing the role of continuity.

We call a censor credible if it does not return contradicting answers.

The following corollary is a generalization of Cor. 30 in [21].

There are several properties that a ‘good’ censor should fulfil. We call a censor effective if it protects all secrets.

A ‘good’ censor should only distort an answer to a query when it is absolutely necessary, i.e. when giving the correct answer would leak a secret. We call such a censor minimally invasive.

It is a trivial observation that a truthful, effective and minimally invasive censor has to answer the same query always in the same way.

Consider a truthful, effective, continuous and minimally invasive censor and a given query sequence. If the censor lies to answer some query, then giving the correct answer would immediately reveal a secret.

Next we define the notion of a repudiating censor, which garantees that there is always a knowledge base in which no secret holds and which, given as input to the answering function, produces the same results as the actual knowledge base. Hence this definition provides a version of plausible deniability for all secrets.

Now we can establish our first no-go theorem, which is a generalization of Th. 50 in [21].

In this section we study censors that do not refuse to answer a query.

Of course, a non-refusing censor has to lie in order to keep the secrets. That means if a censors of this kind shall be effective, then it cannot be truthful.

Even if we consider lying censors, we work with the assumption that

Otherwise, we are in a situation where an attacker cannot believe any answer because the attacker does not know which answers are correct and which are wrong, which means that any answer could be a lie. In that case, querying a knowledge base would not make any sense at all.¹¹1This is, of course, not completely true. It is possible to distort knowledge bases in such a way that privacy is preserved but statistical inferences are still informative, see, e.g. [11].

Because of the assumption (7), we can use our notions of effectiveness (Definition 20) and credibility (Definition 15) also in the context of lying censors: an attacker should not believe any secret and the beliefs should be satisfiable.

Theorem 25 about truthful censors did not make any assumptions on the underlying logic $\mathsf{L}$. The next theorem about non-refusing censors is less general as it is based on classical logic. We will use $a,b,c,\ldots$ for atomic propositions and $A,B,C,\ldots$ for arbitrary formulas.

Moreover, we assume that the knowledge base $\mathsf{KB}$ only contains atomic facts (we say $\mathsf{KB}$ is atomic). That is if $F\in\mathsf{KB}$, then $F$ is either of the form $p$ or of the form $\lnot p$ where $p$ is an atomic proposition. Hence we find that if $\mathsf{KB}\vdash_{\mathsf{L}}a\to b$ for two distinct atomic propositions $a$ and $b$, then $\mathsf{KB}\vdash_{\mathsf{L}}\lnot a$ or $\mathsf{KB}\vdash_{\mathsf{L}}b$. We can formalize this using the set of a priori knowledge by letting

Now we can establish our second no-go theorem, which is a generalization of the results of [5].

To avoid this problem, a censor must not only protect the single elements of $\mathsf{Sec}$ but also their disjunction [5]. For the privacy configuration of the previous proof that means $\mathsf{Cens}$ must also protect $a\lor b$. Then, already the second query, $\lnot c\to b$ would be answered with $u$ because the answer $t$, as shown above, reveals $a\lor b$.

Note that protecting the disjunction of all secrets is not as simple as it sounds. Consider, for instance, a hospital information system that should protect the disease a patient is diagnosed with. In this case, protecting the disjunction of all secrets means protecting the information that the patient has some disease. This, however, is not feasible as it is general background knowledge that everybody who is a patient in a hospital has some disease. Worse than that, sometimes the disjunction of all secrets may even be a logical tautology, which cannot be protected.

In this paper, we have established two no-go theorems for data privacy using tools from modal logic. We are confident that logical methods will play an important role for finding new impossibility theorems or for better understanding already known ones, see, e.g., the logical analyses carried out in [16] and [17].

Another line of future research relates to the fact that refusing to answer a query can give away the information that there exists a secret that could be infered from some other answer. Similar phenomena may occur in multi-agent systems when one of the agents refuses to communicate. For example, imagine the situation of an oral exam where the examiner asks a question and the student keeps silent. In this case the examiner learns that the student does not know the answer to the question for otherwise the student would have answered.

It is also possible that refusing an answer can lead to knowing that someone else knows a certain fact. Consider the following scenario. A father enters a room where his daughter is playing and he notices that one of the toys is in pieces. So he asks who has broken the toy. The daughter does not want to betray her brother (who actually broke it) and she also does not want to lie. Therefore, she refuses to answer her father’s question. Of course, then the father knows that his daughter knows who broke the toy for otherwise the daughter could have said that she does not know.

We believe that it is worthwhile to study the above situations using general communication protocols that include the possibility of refusing an answer and to investigate the implications of refusing in terms of higher-order knowledge.