Distributed Transition Systems with Tags
for Privacy Analysis

Data anonymization has been investigated for decades, and many privacy models have been proposed ($k$-anonymity, differential privacy, …) whose goals are to protect sensitive information. Our goal in this paper is not to define a new anonymization model, but rather to propose a logical framework to formally model how the information stored in a database can get captured progressively by any agent repeatedly querying the database. This model can also be used to quantify reidentification attacks on a database.

The logical framework we propose below formally models how the information stored in a database can get captured progressively, by an agent/adversary querying repeatedly the database. The data can be of any following types: numerical, non-numerical,or literal. In practice however, some of the literals representing ‘sensitive data’ could be in a taxonomical relation; and part of the data could be presented, for ‘anonymization’ purposes, as finite intervals or sets, over the basic types. We shall therefore agree to consider the types of the data in an extended ‘overloaded’ sense. Cf. Example 1 below. (Only tree-structured taxonomies will be considered in this work.)

We assume given a data base $D$, with its attributes set ${\mathcal{A}}$, usually divided in three disjoint groups: the subgroup ${\mathcal{A}}^{(i)}$ of identifiers, ${\mathcal{A}}^{(qi)}$ of quasi-identifiers, and ${\mathcal{A}}^{(s)}$ of sensitive attributes. The tuples of the base $D$ will be generally denoted as $t$, and their attributes denoted respectively as $t^{i},t^{qi},$ and $t^{s}$ in the three subgroups of ${\mathcal{A}}$. The attributes $t^{i}$ on any tuple $t$ of $D$ are conveniently viewed as defining a ‘user’ or a ‘client’ of the database $D$. Quasi-identifiers¹¹1A formal definition of quasi-identifier attributes does not seem to be known. For our purposes, it suffices to see them as those that are not identifiers nor sensitive. are informally defined in general, as a set of public attributes, which in combination with other attributes and/or external information, can allow to re-identify all or some of the users to whom the information refers. The base $D$ itself could be ‘distributed probabilistically’ over a finite set (referred to then, as ‘universe’, and its elements named as possible ‘worlds’).

By a privacy policy $P=P_{A}(D)$ on $D$ with respect to a given agent/adversary $A$ is meant the stipulation that for a certain given set of tuples $\{t\in P\subset D\}$, the sensitive attributes $t^{s}$ on any such $t$ shall remain inaccessible (‘even after further deduction’ – see below) to $A$. It is assumed that $A$ is not the user identified by the attributes $t^{i}$ on these $t$’s.

The logical framework we propose in this work, to model the evolution of the ‘knowledge’ that an adversary $A$ can gain by repeatedly querying the given database $D$ – with a view to get access to sensitive data meant to remain hidden for him/her under the given privacy policy $P$ –, will be called Distributed Labeled-Tagged Transition System (DLTTS); The underlying logic for DLTTS is first-order, with countably many variables and finitely many constants (including certain usual dummy symbols like ‘$\star,\$,\#$’). In this work, the basic signature $\Sigma$ for the framework is assumed to have no non-constant function symbols. By ‘knowledge’ of $A$ we shall mean the data that $A$ retrieves as answers to his/her successive queries, as well as other data that can be deduced/derived, under relational operations on these answers; and in addition, some others derivable from these, using relational combinations with data (possibly involving some of the users of $D$) from finitely many external DBs given in advance, denoted as $B_{1},\dots,B_{m}$, to which the adversary $A$ is assumed to have free access. These relational and querying operations are all assumed done with a well-delimited fragment of the language SQL ; it is assumed that this fragment of SQL is part of the signature $\Sigma$ underlying the DLTTSs. In addition, if $n\geq 1$ is the length of the tuples forming the data in $D$, finitely many predicate symbols ${\mathcal{K}}_{i},1\leq i\leq n$, each $K_{i}$ of arity $i$, will be part of the signature $\Sigma$; in the work presented here they will be the only predicate symbols in $\Sigma$. The role of these symbols is to allow us to see any data tuple of length $r,1\leq r\leq n$, as a variable-free first-order formula with top symbol ${\mathcal{K}}_{r}$, with all arguments assumed typed implicitly (with the help of the headers of the base $D$). In practice however, we shall drop these top symbols ${\mathcal{K}}_{i}$, and see any data tuple that is not part of the given privacy policy $P_{A}(D)$, directly as a first-order variable-free formula over $\Sigma$; data tuples $t$ that are elements of the policy $P_{A}(D)$ will in practice be just written as $\neg t$.

As we shall see, the DLTTS framework is well suited for capturing the ideas on acquiring knowledge and on policy violation, in an elegant and abstract setup. A preliminary definition of this framework (Section 2) considers only the case where the data, as well as the answers to the queries, do not involve any notion of ‘noise’. (By ‘noise’ we shall mean the perturbation of data by some external random (probabilistic mechanism.) But we shall extend this definition in a later section, as an option to also handle noisy data.The notion of violation of any given privacy policy on a database can then be (optionally) extended into a notion of violation up to some given $\epsilon\geq 0$ ($\epsilon$-violation, for short). In the first part of the work, we will be modeling the lookout for the sensitive attributes of certain given users, by a single adversary. In the second part of the work (Section 5 onwards), we propose a method for comparing the evolution of knowledge of an adversary at two different nodes on a given run, or on two different possible runs; the same method also applies for comparing the evolution of knowledge of two different adversaries $A_{1},A_{2}$, both querying repeatedly (and independently) the given database.

But before formally defining the DLTTS, a couple of examples might help; they will also throw some light on how to delimit properly the fragment of SQL that we want included in our logical setup.

The DLTTS framework presented in this section synthesizes ideas coming from various domains, such as the Probabilistic Automata of Segala ([13], Probabilistic Concurrent Systems, Probabilistic labelled transition systems ([3, 4]. Although the underlying signature for the DLTTS can be rich in general, for the purposes of our current work we shall be working with a limited first-order signature (as mentioned in the Introduction) denoted $\Sigma$, with countably many variables, finitely many constants (including some ‘standard dummies’), no non-constant function symbols, and a finite limited set of predicate (propositional) symbols. Let ${\mathcal{E}}$ be the set of all variable-free formulas over $\Sigma$, and $\mathtt{Ext}$ a given subset of ${\mathcal{E}}$. We assume given a decidable procedure ${\mathcal{C}}$ whose role is to ‘saturate’ any finite set $G$ of variable-free formulas into a finite set $\overline{G}$, by adding a finite (possibly empty) set of variable-free formulas, using relational operations on $G$ and $\mathtt{Ext}$. This procedure ${\mathcal{C}}$ will be internal at every node on a DLTTS; in addition, there will also be a ‘blackbox’ mechanism ${\mathcal{O}}$, acting as an oracle telling if the given privacy policy on a given database is violated at the current node. More details will be given in Section 5 on the additional role the oracle will play in a privacy analysis procedure (for any querying sequence on a given DB), based on a novel data-based metric, which will be defined in that section.

A (probabilistic) transition ${\mathfrak{t}}\in{\mathcal{T}}$ will generally be written as a triple $(s,a,{\mathfrak{t}}(s))$; and ${\mathfrak{t}}$ will be said to be ‘from’ (or ‘at’) the state $s$, the states of ${\mathfrak{t}}(s)$ will be the ‘successors’ of $s$ under ${\mathfrak{t}}$. The formulas in the tag $\overline{\tau}(s)$ attached to any state $s$ will all be assigned the same probability as the state $s$ in $Distr(S)$. If the set $\overline{\tau}(s)$ of formulas turns out to be inconsistent, then the oracle mechanism ${\mathcal{O}}$ will (intervene and) impose $(s,\delta,\otimes)$ as the only transition from $s$, standing for ‘violation’ and ‘fail’, by definition,

Nondeterminism of transitions can be defined without difficulty on DLTTS, as a nondeterministic choice between the possible probabilistic transitions at any given state. We shall assume that nondeterminism is managed by the choice of a suitable scheduler; and in addition, that at most one probabilistic transition is firable from any state $s\in S\smallsetminus\{\otimes\}$, and none from the halting state $\otimes$.

Note that we make no assumption on whether the repeated queries by $A$ on $D$ are treated interactively, or non-interactively, by the DBMS. It appears that the logical framework would function exactly alike, in both cases.

Remark 2: (a) Suppose ${\mathfrak{t}}$ is a transition from a state $s$, on the DLTTS corresponding to a querying sequence by an adversary $A$, and $s^{\prime}$ is one of the successors of $s$ under ${\mathfrak{t}}$; then, by definition, the ‘fresh’ knowledge $\tau(s^{\prime})$ of $A$ at $s^{\prime}$ resulting from this transition, is the addition to $A$’s saturated knowledge $\overline{\tau}(s)$ at $s$, the part of the response of the DBMS’s answering mechanism for $A$’s current query, represented by the branch of ${\mathfrak{t}}$ going from $s$ to $s^{\prime}$.

(b) As already mentioned, we assume that the relational operations needed for gaining further knowledge are done using a well delimited finite subset of the functionalities of SQL; and that ‘no infinite set can get generated from a finite set’ under these functionalities, assumed included in the signature $\Sigma$. (This corresponds to the bounded inputs outputs assumption, as in e.g., [1, 2].) $\Box$

Our objective now is to extend the result of Proposition 1 to the case when the violation to be considered can be up to some given $\epsilon\geq 0$, in a sense to be made precise. We stick to the same notation as above. The set ${\mathcal{E}}$ of all variable-free formulas over $\Sigma$ is thus a disjoint union of subsets of the form ${\mathcal{E}}=\cup\{{\mathcal{E}}^{{\mathcal{K}}}_{i}\mid 0<i\leq n,{\mathcal{K}}\in\Sigma\}$, the index $i$ in ${\mathcal{E}}^{{\mathcal{K}}}_{i}$ standing for the common length of the formulas in the subset, and ${\mathcal{K}}$ for the common root symbol of its formulas; each set ${\mathcal{E}}^{{\mathcal{K}}}_{i}$ will be seen as a database of $i$-tuples.

We shall first look at the situation where the queries intend to capture certain (sensitive) values on a given tuple $t$ in the database $D$. Two different tuples in ${\mathcal{E}}$ might correspond to two likely answers to such a query, but with possibly different probabilities in the distribution assigned for the transitions, by the probabilistic mechanism ${\mathcal{M}}$ (e.g., as in Example 1).

Given two such instances, and a real $\epsilon\geq 0$, we can also define a notion of their $\epsilon$-local-indistinguishabilty, wrt the tuple $t$ and the mechanism ${\mathcal{M}}$ answering the queries. This can be done in a slightly extended setup, where the answering mechanism may, as an option, also add ‘noise’ to certain numerical data values, for several reasons among which the safety of data. We shall then assume that the internal procedure ${\mathcal{C}}$ of the DLTTS at each of its states (meant to saturate the current knowledge of the adversary querying the database) incorporates the following three well-known noise adding mechanisms: the Laplace, Gauss, and exponential mechanisms. With the stipulation that this optional noise additions to numerical values can be done in a bounded fashion, so as to be from a finite prescribed domain around the values; it will then be assumed that tuples formed of such noisy data are also in ${\mathcal{E}}$.

We shall also be needing the following notion of $\epsilon$-indistinguishability (and of $\epsilon$-distinguishability) of two different outputs of the mechanism ${\mathcal{M}}$: These definitions – as well that of $\epsilon$-DP given below – are essentially reformulations of the same (or similar) notions defined in [7, 8].

Remark 3: Given an $\epsilon\geq 0$, one may assume as an option, that at every state on the DLTTS the retrieval of answers to the current query (from the mechanism ${\mathcal{M}}$) is done up to $\epsilon$-indistinguishabilty; this will then be implicitly part of what was called the saturation procedure ${\mathcal{C}}$ at that state. The procedure thus enhanced for saturating the tags at the states, will then be denoted as $\epsilon{\mathcal{C}}$, when necessary (it will still be decidable, under the finiteness asumptions of Remark-2 (b)). Inconsistency of the set of formulas, in the ‘$\epsilon{\mathcal{C}}$-saturated’ tag at any state, will be checked up to $\epsilon$-indistinguishabilty, and referred to as $\epsilon$-inconsistency, or $\epsilon$-failure. The notion of privacy policy will not need to be modified; that of its violation will be referred to as $\epsilon$-violation, Under these optional extensions of $\epsilon$-failure and $\epsilon$-violation, it must be clear that the statements of Proposition 1 continue to be valid. $\Box$

Two small examples of $\epsilon$-local-indistinguishability, before closing this section.

(i) The two sub-tuples ([50–60], M, Maths) and ([40–50], M, Physics), from the last two tuples on the Hospital’s published record in Example 1 (Table 2), both point to Viral–Infection as output; they can thus be seen as $log(2)$-local-indististinguishable, for the adversary $A$.

(ii) The ‘Randomized Response’ mechanism $RR$ ([14]) can be modelled as follows. Input is ($X,F_{1},F_{2}$) where $X$ is a Boolean, and $F_{1},F_{2}$ are flips of a coin ($H$ or $T$). $RR$ outputs $X$ if $F_{1}=H$, $True$ if $F_{1}=T$ and $F_{2}=H$, and $False$ if $F_{1}=T$ and $F_{2}=T$. This mechanism is $log(3)$-LDP : the instances ($True,H,H$), ($True,H,T$), ($True,T,H$) and ($True,T,T$) are $log(3)$-indistinguishable for output $True$. ($False,H,H$), ($False,H,T$), ($False,T,H$)and ($False,T,T$) are $log(3)$-indistinguishable for output $False$.

The notion of $\epsilon$-indistinguishability of two given databases $D,D^{\prime}$ for an adversary, is more general than that of $\epsilon$-local-indistinguishability (of pairs of instances of a probabilistic answering mechanism giving the same output, defined in the previous section). $\epsilon$-indistinguishability is usually defined only for pairs of databases $D,D^{\prime}$ that are adjacent in a certain sense (cf. below).

There is no uniquely defined notion of adjacence on pairs of databases; in fact, several are known, and in use in the literature. Actually, a notion of adjacence can be defined in a generic parametrizable manner (as in e.g., [5]), as follows. We assume given a map $\mathbf{f}$ from the set ${\mathcal{D}}$ of all databases of $m$-tuples (for some given $m>0$), into some given metric space $(X,d_{X})$. The binary relation on pairs of databases in ${\mathcal{D}}$, defined by $\mathbf{f}_{adj}(D,D^{\prime})=d_{X}(\mathbf{f}(D),\mathbf{f}(D^{\prime}))$ is then said to define a measure of adjacence on these databases. The relation $\mathbf{f}_{adj}$ is said to define an ‘adjacency relation’.

(ii) In Section 6, we propose a more general notion of adjacency, based on a different metric defined ‘value-wise’, to serve other purposes as well.

(iii) On disjoint databases, one can work with different adjacency relations, using different maps to the same (or different) metric space(s),

(iv) The mechanism $RR$ described above is actually $log(3)$-DP, not only $log(3)$-LDP. To check $DP$, we have to check all possible pairs of numbers of the form $(Prob[{\mathcal{M}}(x)=y],Prob[{\mathcal{M}}(x^{\prime})=y])$, $(Prob[{\mathcal{M}}(x)=y^{\prime}],Prob[{\mathcal{M}}(x^{\prime})=y])$, $(Prob[{\mathcal{M}}(x)=y],Prob[{\mathcal{M}}(x^{\prime})=y^{\prime}])$, etc., where the $x,x^{\prime}....$ are the input instances for $RR$, and $y,y^{\prime},...$ the outputs. The mechanism $RR$ has $2^{3}$ possible input instances for ($X,F_{1},F_{2}$) and two outputs (True, False); thus 16 pairs of numbers, the distinct ones being $(1/4,1/4),(1/4,3/4),(3/4,1/4)$, $(3/4,3/4)$; if $(a,b)$ is any such pair, obviously $a\leq e^{log(3)}b$. Thus $RR$ is indeed $log(3)$-DP. $\Box$

In the previous two sections, we looked at the issue of ‘quantifying’ the indistinguishability of two data tuples or databases, under repeated queries of an adversary $A$. In this section, our concern will be in a sense ‘orthogonal’: the issue will be that of quantifying how different the probabilistic mechanism’s answers can be, at different moments of $A$’s querying sequence. Remember that the knowledge of $A$, at any node on the DLTTS of the run corresponding to the query sequence, is represented as a set of tuples; and also that the data forming any tuple are assumed implicitly typed, ‘labeled with’ (i.e., under) the headers of the database $D$. To be able to compare two tuples of the same length, we shall assume that there is a natural, injective, type-preserving map from one of them onto the other; this map will remain implicit in general; two such tuples will be said to be type-compatible. If the two tuples are not of the same length, one of them will be projected onto (or restricted to) a suitable subtuple, so as to be type-compatible and comparable with the other; if this turns out to be impossible, the two tuples will be said to be uncomparable.

The quantification looked for will be based on a suitable notion of ‘distance’ between two sets of type-compatible tuples. For that, we shall first define ‘distance’ between any two type-compatible tuples; more precisely, define such a notion of distance between any two data values under every given header of $D$. As a first step, we shall therefore begin by defining, for every given header of $D$, a binary ‘distance’ function on the set of all values that get assigned to the attributes under that header, along the sequence of $A$’s queries. This distance function to be defined will be a metric: non-negative, symmetric, and satisfying the so-called Triangle Inequality (cf. below). The ‘direct-sum’ of these metrics, taken over all the headers of $D$, will then define a metric $d$ on the set of all type-compatible tuples of data assigned to the various attributes, under all the headers of $D$, along the sequence of $A$’s queries. The ‘distance’ $d(t,t^{\prime})$, from any given tuple $t$ in this set to another type-compatible tuple $t^{\prime}$, will be defined as the value of this direct-sum metric on the pair of tuples $(t,t^{\prime})$; it will, by definition, be calculated ‘column-wise’ on the base $D$, and also on the intermediary databases along $A$’s query sequence; note that it will give us a priori an $m$-tuple of numbers, where $m$ is the number of headers (or columns) in the database $D$.

A single number can then be derived as the sum of the entries in the $m$-tuple $d(t,t^{\prime})$. This sum will be denoted as $\overline{d}(t,t^{\prime})$, and defined as the distance from the tuple $t$ to the tuple $t^{\prime}$ in the database $D$. Finally, if $S,S^{\prime}$ are any two given finite sets of type-compatible tuples, of data that get assigned to the various attributes (along the queries), we shall define the distance from the set $S$ to the set $S^{\prime}$ as the number $\rho(S,S^{\prime})=min\{\,\overline{d}(t,t^{\prime})\mid t\in S,\,t^{\prime}\in S^{\prime}\,\}$

Some preliminaries are needed before we can define the ‘distance’ function between the data values under every given header of $D$. We begin by dividing the headers of the base $D$ into four classes classes, for clarity of presentation:

• .

  ‘Nominal’: identities, names, attributes receiving literal data not in any taxonomy (e.g., gender, city, …), finite sets of such data;

• .

  ‘Numerval’ : attributes receiving numerical values, or bounded intervals of (finitely many) numerical values;

• .

  ‘Numerical’: attributes receiving single numerical values (numbers).

• .

  ‘Taxoral’: attributes receiving literal data in a taxonomy relation.

For defining the ‘distance’ between any two values $v,v^{\prime}$ assigned to an attribute under a given ‘Nominal’ header of $D$, for the sake of uniformity we agree to consider every value as a finite set of singleton values. (In particular, a singleton value ‘$x$’ will be seen as the set $\{x\}$.) Given two such values $v,v^{\prime}$, note first that the so-called Jaccard Index between them is the number $jacc(v,v^{\prime})=|(v\cap v^{\prime})/(v\cup v^{\prime})|$, which is a ‘measure of their similarity’; but this index is not a metric: the triangle inequality is not satisfied; however, the Jaccard metric $d_{Nom}(v,v^{\prime})=1-jacc(v,v^{\prime})=|(v\Delta v^{\prime})/(v\cup v^{\prime})|$ does satisfy that property, and will suit our purposes. Thus defined, $d_{Nom}(v,v^{\prime})$ is a ‘measure of the dissimilarity’ between the sets $v$ and $v^{\prime}$.

Let $\scalerel*{\tau}{T}\!\!_{Nom}$ be the set of all data assigned to the attributes under the ‘Nominal’ headers of $D$, along the sequence of $A$’s queries. Then the above defined binary function $d_{Nom}$ extends to a metric on the set of all type-compatible data-tuples from $\scalerel*{\tau}{T}\!\!_{Nom}$, defined as the ‘direct-sum’ taken over the ‘Nominal’ headers of $D$.

If $\scalerel*{\tau}{T}\!\!_{Num}$ is the set of all data assigned to the attributes under the ‘Numerval’ headers along the sequence of queries by $A$, we also define a ‘distance’ metric $d_{Num}$ on the set of all type-compatible data-tuples from $\scalerel*{\tau}{T}\!\!_{Num}$, in a similar manner. We first define $d_{Num}$ on any couple of values $u,v$ assigned to the attributes under a given ‘Numerval’ header of $D$, then extend it to the set of all type-compatible data-tuples from $\scalerel*{\tau}{T}\!\!_{Num}$ (as the direct-sum taken over the ‘Numerval’ headers of $D$). This will be done exactly as under the ‘Nominal’ headers: suffices to visualize any finite interval value as a particular way of presenting a set of numerical values (integers, usually). (In particular, a single value ‘$a$’ under a ‘Numerval’ header will be seen as the interval value $[a]$.) Thus defined the (Jaccard) metric distance $d_{Nom}([a,b],[c,d])$ is a measure of ‘dissimilarity’ between $[a,b]$ and $[c,d]$. .

Between numerical data $x,x^{\prime}$ under the ‘Numerical’ headers, the distance we shall work with is the euclidean metric $|x-x^{\prime}|$, normalized as: $d_{eucl}(x,x^{\prime})=|x-x^{\prime}|/D$, where $D>0$ is a fixed finite number, bigger than the maximal euclidean distance between the numerical data on the databases and on the answers to $A$’s queries.

On the data under the ‘Taxoral’ headers, we choose as distance function the metric $d_{wp}$, defined in Lemma 1 (cf. Appendix) between the nodes of any Taxonomy tree.

Note that the ‘datawise distance functions’ defined above are all with values in the real interval $[0,1]$. (This is also one reason for our choice of the distance metric on Taxonomy trees.) This fact is of importance, for comparing the metric $\rho$ we defined above with the Hamming metric, cf. Section  6.

Before presenting the comparison schema, here is an example to illustrate how the notions developed above operate in practice.

We compute now the distance $\overline{d}$ between the target $T$, and the three tuples $l_{2},l_{4},l_{5}$. This involves only the subtuple $L=(46,M,\#,CoVid)$ of $T$:

. $\overline{d}(l_{2},L)=d_{Num}(l_{2},L)+d_{Nom}(l_{2},L)+d_{wp}(L_{2},L)$

$=(1-1/10)+0+(1-2/5)=9/10+3/5=15/10$

. $\overline{d}(l_{4},L)=d_{Num}(l_{2},L)+d_{Nom}(l_{4},L)+d_{wp}(L_{4},L)$

$=(1-0)+0+(1-4/5)=1+1/5=6/5$

. $\overline{d}(l_{5},L)=d_{Num}(l_{5},L)+d_{Nom}(l_{5},L)+d_{wp}(L_{5},L)$

$=(1-1/10)+0+(1-4/5)=9/10+1/5=11/10$

Given a randomized/probabilistic mechanism ${\mathcal{M}}$ answering the queries on databases, and an $\epsilon\geq 0$, recall that the $\epsilon$-indistinguishability of any two given databases under ${\mathcal{M}}$, and the notion of $\epsilon$-DP for ${\mathcal{M}}$, were both defined in Definition 4 (Section 4), based first on a hypothetical map $\mathbf{f}$ from the set of all the databases concerned, into some given metric space $(X,d_{X})$, and an ‘adjacency relation’ on databases defined as $\mathbf{f}_{adj}(D,D^{\prime})=d_{X}(\mathbf{f}D,\mathbf{f}D^{\prime})$, which was subsequently instantiated to $\mathbf{f}_{adj}=\epsilon d_{h}$, where $d_{h}$ is the Hamming metric between databases. It must be observed here, that the Hamming metric is defined only between databases with the same number of columns, and usually only with all data of the same type.

In this subsection, our objective is to propose a more general notion of adjacency, based on the distance metric $\rho$ defined above, between type-compatible tuples on databases with data of multiple types. In other words, our ${\mathcal{D}}$ here will be the set of all databases, not necessarily all with the same number of columns, and with data of several possible types as mentioned in the Introduction. We define then a binary relation $\mathbf{f}^{\rho}_{adj}(D,D^{\prime})$ between $D,D^{\prime}$ in the set ${\mathcal{D}}$ by setting $\mathbf{f}^{\rho}_{adj}(D,D^{\prime})=\rho(D,D^{\prime})$, visualizing $D,D^{\prime}$ as sets of type-compatible data tuples.

Given $\epsilon$, we can then define the notion of $\epsilon_{\rho}$-indistinguishabilty of two databases $D,D^{\prime}$ under a (probabilistic) answering mechanism ${\mathcal{M}}$, as well as the notion of $\epsilon_{\rho}$-DP for ${\mathcal{M}}$, exactly as in Definition 4, by replacing $\mathbf{f}_{adj}$ first with the relation $\mathbf{f}^{\rho}_{adj}$, and subsequently with $\epsilon\rho$. The notions thus defined are more general than those presented earlier in Section 4 with the choice $\mathbf{f}_{adj}=\epsilon d_{h}$. An example will illustrate this point.

The output $l_{2}$, with probability $0$, will be $\epsilon_{\rho}$-distinguishable for any $\epsilon\geq 0$. Only the two other outputs $l_{4},l_{5}$ need to be considered. We first compute the $\rho$-distances between these two tuples: $\overline{d}(l_{4},l_{5})=(1-\frac{1}{20})+0+1+0=39/20$. The condition for $l_{4}$ and $l_{5}$ to be $\epsilon_{\rho}$-indistinguishable under ${\mathcal{M}}$ is thus:

$(2/5)\leq e^{(39/20)\epsilon}*(3/5)\;\;and\;\;(3/5)\leq e^{(39/20)\epsilon}*(2/5)$,

i.e., $\epsilon\geq(20/39)*ln(3/2)$. In other words, for any $\epsilon\geq(20/39)*ln(3/2)$, the two tuples $l_{4}$ and $l_{5}$ will be $\epsilon_{\rho}$-indistinguishable; and for values of $\epsilon$ with $0\leq\epsilon<(20/39)*ln(3/2)$, these tuples will be $\epsilon_{\rho}$-distinguishable.

For the $\epsilon$-indistinguishabilty of these tuples wrt the Hamming metric $d_{h}$, we proceed similarly: the distance $d_{h}(l_{4},l_{5})$ is by definition the number of ‘records’ where these tuples differ, so $d_{h}(l_{4},l_{5})=2$. So the condition on $\epsilon\geq 0$ for their $\epsilon$-indistinguishabilty wrt $d_{h}$ is: $(3/5)\leq e^{2\epsilon}*(2/5)$,  i.e.,   $\epsilon\geq(1/2)*ln(3/2)$ .

In other words, if these two tuples are $\epsilon_{\rho}$-indistinguishables wrt $\rho$ under ${\mathcal{M}}$ for some $\epsilon$, then they will be $\epsilon$-indistinguishable wrt $d_{h}$ for the same $\epsilon$. But the converse is not true, since $(1/2)*ln(3/2)<(20/39)*ln(3/2)$. Said otherwise: ${\mathcal{M}}$ $\epsilon$-distinguishes more finely with $\rho$, than with $d_{h}$. $\Box$

Remark 4: The statement¡‘${\mathcal{M}}$ $\epsilon$-distinguishes more finely with $\rho$, than with $d_{h}$”, is always true (not just in Example 4). For the following reasons: The records that differ ‘at some given position’ on two bases $D,D^{\prime}$ are always at distance $1$ for the Hamming metric $d_{h}$, by definition, whatever be the type of data stored at that position. Now, if the data stored at that position ‘happened to be’ numerical, the usual euclidean distance between the two data could have been (much) bigger than their Hamming distance $1$; precisely to avoid such a situation, our definition of the metric $d_{eucl}$ on numerical data ‘normalized’ the euclidean distance, to ensure that their $d_{eucl}$-distance will not exceed their Hamming distance. Thus, all the ‘record-wise’ metrics we have defined above have their values in $[0,1]$, as we mentioned earlier; so, whatever the type of data at corresponding positions on any two bases $D,D^{\prime}$, the $\rho$-distance between the records will never exceed their Hamming distance. That suffices to prove our statement above. The Proposition below formulates all this, more precisely:

The idea of ‘normalizing’ the Hamming metric between numerical databases (with the same number of columns) was already suggested in [5] for the same reasons. When only numerical databases are considered, the metric $\rho$ that we have defined above is the same as the ‘normalized Hamming metric’ of [5]. Our metric $\rho$ must actually be seen as a generalization of that notion, to directly handle bases with more general types of data: anonymized, taxonomies, …

A starting point for the work presented is the observation that databases could be distributed over several ‘worlds’ in general, so querying such bases leads to answers which would also be distributed; to such distributed answers one could conceivably assign probability distributions of relevance to the query. The probabilistic automata of Segala ([12, 13]) are among the first logical structures proposed to model such a vision, in particular with outputs. Distributed Transition Systems (DTS) appeared a little later, with as objective the behavioral analysis of the distributed transitions, based on traces or on simulation/bisimulation, using quasi- or pseudo- or hemi- metrics as in [3, 4, 6]. Our lookout in this work was for a syntax-based metric in the mathematical sense, that can directly handle data of ‘mixed’ types – which can be numbers or literals, but can also be ‘anonymized’ as intervals or sets; they can also be taxonomically related to each other in a tree structure. (The metric $d_{wp}$ we have defined in the Appendix on the nodes of a taxonomy tree is novel.) Data-wise metrics as defined in our work can express more precisely, in a mathematical sense, the ‘estimation errors’ of an adversary wrt the given privacy policies on the database, at any point of his/her querying process. (In  [10], such estimations are expressed in terms of suitably defined ‘probability measures’.) Implementation and experimentation are part of our future work, where we also hope to define a ‘divergence measure’ between two given nodes on a DLTTS modeling a querying process, in terms of the knowledge distributions at the two nodes – independently of any notion of a given target data set.

Taxonomies are frequent in machine learning. Data mining and clustering techniques employ reasonings based on measures of symmetry, or on metrics, depending on the objective. The Wu-Palmer symmetry measure on tree-structured taxonomies is one among those in use; it is defined as follows ([15]): Let ${\mathcal{T}}$ be a given taxonomy tree. For any node $x$ on ${\mathcal{T}}$, define its depth $c_{x}$ as the number of nodes from the root to $x$ (both included), along the path from the root to $x$. For any pair $x,y$ of nodes on ${\mathcal{T}}$, let $c_{xy}$ be the depth of the common ancestor of $x,y$ that is farthest from the root. The Wu-Palmer symmetry measure between the nodes $x,y$ on ${\mathcal{T}}$ is then defined as WP$(x,y)=\frac{2\,c_{xy}}{c_{x}+c_{y}}$. This measure, although considered satisfactory for many purposes, is known to have some disadvantages such as not being conform to semantics in several situations.

What we are interested in, for the purposes of our current paper, is a metric between the nodes of a taxonomy tree, which in addition will suit our semantic considerations. This is the objective of our Lemma below. (A result that seems to be unknown, to our knowledge.)