Protecting Data Buyer Privacy in Data Markets

To protect the true intent as the buyer’s privacy, a data buyer may post a published intent $U_{1}\wedge\cdots\wedge U_{n}$ that is a superset of the true intent, that is, $V_{i}\subseteq U_{i}\subseteq D_{i}$ $(1\leq i\leq n)$, so that potential data providers know the data buyer’s interest. Our first attack model is based on the published intent (PI for short).

Since the published intent is the only information that an attacker has about the buyer’s intent, given a record in $\mathcal{D}$, if the record is outside the published intent, then an attacker knows that the record is not interesting to the buyer. For a record in the published intent, the attacker’s confidence on whether the record is in the buyer’s true intent can be analyzed as follows.

Since the attacker does not have any background information about the data space, such as the probability density, the best that an attacker can assume is that each possible point in $\mathcal{D}$ has the same probability to occur. That is, the data distribution in $\mathcal{D}$ is uniform. Therefore, we also call the published intent-based attack the PI-uniform attack in this article.

Since the true intent is a subset of the published intent, and the minimal size of the true intent is $1$, that is, the true intent contains only one specific value on each dimension specified in the published intent. Thus, the lower bound of the confidence is $\frac{1}{|U_{1}\times\cdots\times U_{n}|}=\prod_{i=1}^{n}\frac{1}{|U_{i}|}$, which is known to both the buyer and any attacker. In the same vein, the upper bound of the confidence is $\frac{|V_{1}\times\cdots\times V_{n}|}{|U_{1}\times\cdots\times U_{n}|}=\prod_{i=1}^{n}\frac{|V_{i}|}{|U_{i}|}$, which is only known to the buyer but not to an attacker. Then, we have

where $Conf_{\text{PI}}^{\text{Uniform}}(x)$ denotes the attacker’s confidence of record $x$ in the data buyer’s true intent given $x$ in the published intent via PI-uniform attack.

One may wonder, as $|V_{i}|$ $(1\leq i\leq n)$ is unknown to an attacker, how the upper bound $\prod_{i=1}^{n}\frac{|V_{i}|}{|U_{i}|}$ takes effect. Please note that in the task of buyer privacy protection, the key is to ensure that even an attacker knows the size of the true intent, the chance that a record in the published intent indeed belongs to the true intent is still lower than some buyer specified threshold. Therefore, $|V_{i}|$ is used in designing the protection mechanisms.

In addition to the observable published intent, an attacker may have some background knowledge about the data, such as the data distribution in $\mathcal{D}$ or the cost of producing or collecting a data record with respect to dimension values. The attacker may use the background knowledge to enhance the confidence on whether a data record belongs to a data buyer’s true intent. The central idea is that, to be economically efficient, a data buyer tends to maximize the efficiency of the published intent. That is, a large part in the published intent is within the buyer’s true intent. Thus, we call this type of attacks the efficiency maximization attacks.

In our running example, suppose the published intent contains two states, NC and SC. If an attacker knows that 80% of the transactions appear in NC, then the attacker may heuristically guess NC is in the true intent.

Specifically, if an attacker knows the data distribution in the subspace of the published intent, then, given a record matching the published intent, an upper bound of the attacker’s confidence about that the record falls in the buyer’s intent is proportional to the probability of the record. That is,

where $f_{\mathcal{D}}(x)$ denotes the probability of the record $x$ based on the data distribution in the data space $\mathcal{D}$.

The above model can be easily extended by incorporating the cost of data records. By betting that the buyer wants to spend the budget in a cost efficient way, an upper bound of the confidence is

Alternatively, if an attacker knows the cost of data records but does not know the density distribution $f_{\mathcal{D}}$, still by betting that the buyer wants to spend the budget in a cost efficient way, an upper bound of the confidence is

In some situations, an attacker observes the records purchased by a data buyer, and tries to infer the data buyer’s intent. To protect the privacy, a data buyer may purchase more records than the true intent. Suppose a data buyer purchases a set of records $\mathcal{X}=\{x_{1},x_{2},\ldots,x_{q}\}$, containing the records in the true intent and some disguising records that the data buyer uses to protect the privacy. An attacker may try to infer whether the data buyer is interested in a given record. We call this type of attacks the purchased record inference attack.

Given a data record, an attacker can infer whether the record is interesting to the data buyer in two steps. In the first step, the attacker can infer a pseudo published intent using the observed set of data records purchased by the data buyer. In order words, the attacker can try to find a minimal intent $\hat{U}_{1}\wedge\cdots\wedge\hat{U}_{n}$ such that every purchased data record is in the intent. That is,

Clearly, the solution to Equation 5 can be written as:

where $x[i]$ is the $i$-th dimensional feature of $x$.

Given a record in $\mathcal{D}$, if the record is outside the pseudo published intent, then an attacker knows that the record is not interesting to the buyer. For a record in the pseudo published intent, the attacker’s confidence on whether the record is in the buyer’s true intent can be analyzed as follows, using the distribution of purchased records in the pseudo published intent and the attacker’s background knowledge.

As in a purchased record inference attack, an attacker can infer the observed data distribution $f_{\mathcal{P}}$ in the purchased set of records, specifically, for a record $x$ in the pseudo published intent, the occurring probability of $x$ in the purchased set can be estimated as

where $h(x)$ denotes the occurring frequency of record $x$ in $\mathcal{X}$, and $|\mathcal{X}|$ denotes the cardinality (total number of records in $\mathcal{X}$).

In the simplest case, the attacker only observes the records purchased by the data buyer and does not have any background knowledge about the data distribution in the data space $\mathcal{D}$. Then, given a record matching the pseudo published intent, an upper bound of the attacker’s confidence about that record falling in the buyer’s true intent is proportional to the occurring probability of the record in $\mathcal{X}$. That is,

If an attacker has the background knowledge about the data distribution in the data space $\mathcal{D}$, i.e. $f_{\mathcal{D}}$, by comparing $f_{\mathcal{D}}$ and the observed distribution $f_{\mathcal{P}}$, the attacker can infer how likely a purchased record $x$ is in the true intent based on the efficiency maximization assumption. The more frequent $x$ in the observed distribution $f_{\mathcal{P}}$ and less likely in $f_{\mathcal{D}}$, the more likely $x$ belongs to the true intent.

Quantitatively, for a purchased record $x$, we measure how unlikely the frequency of $x$ in the observed distribution $f_{\mathcal{P}}$ may happen by chance given the distribution $f_{\mathcal{D}}$, which is indicated by the p-value. We first compute the occurring probability of $x$ in the psedo published intent $\widehat{PI}$ based on $f_{\mathcal{D}}$ as follows:

If $f_{\mathcal{P}}(x)>f_{\mathcal{D},\widehat{PI}}(x)$ and the p-value is small, then likely $x$ belongs to the true intent. To compute its p-value, we conduct a model-less hypothesis testing by leveraging Monte Carlo simulation and permutation testing. More specifically, we sample $\mathcal{L}$ sets of records from the pseudo published intent based on $f_{\mathcal{D},\widehat{PI}}$ each with the same size as the buyer’s purchased set $\mathcal{X}$ (denoted as $\mathcal{X}_{1},...,\mathcal{X}_{\mathcal{L}}$). For each record $x$ in $\mathcal{X}$ satisfying $f_{\mathcal{P}}(x)>f_{\mathcal{D},\widehat{PI}}(x)$, we compute the p-value of $f_{\mathcal{P}}(x)$ (the proportion of sampled sets with record $x$’s occurring probability at least as extreme as $f_{\mathcal{P}}(x)$). With this, an upper bound of the attacker’s confidence about that record falls in the buyer’s intent can be written as:

The aforementioned model readily lends itself to extension by integrating the cost of data records, following the same logic as the efficiency maximization attack as indicated in Equation 3. For conciseness, we refrain from delving further into the exploration of data record costs in purchased record inference attack.

Given a buyer’s true intent and a buyer-specified maximal confidence threshold $\lambda>0$, the data buyer wants to either release a published intent in the PI-uniform attack and efficiency maximization attack models or purchase data records in a larger scope in the purchased record inference attack, so that any attackers’ confidence is not higher than $\lambda$ on a record in the published intent or purchased by the data buyer belonging to the buyer’s true intent. A published intent is called a $\lambda$-privacy preserving published intent, and a set of data records to be purchased is called a $\lambda$-privacy preserving set of purchased records if they satisfying the requirement.

Since a data buyer has to pay for the records in the published intent or the set of data records to be purchased, for the sake of economic consideration, the published intent and the scope of data records to be purchased should be minimized. The problem of data buyer privacy protection is to compute the minimal $\lambda$-privacy preserving published intent or set of purchased records.

Given space $\mathcal{D}=D_{1}\times\cdots\times D_{n}$ and the buyer’s true intent $V_{1}\wedge\cdots\wedge V_{n}$, we can keep expending the set of feature values $V_{i}$ in the true intent until obtaining a published intent that can protect the true intent sufficiently, that is, the constraint in Equations 11 (PI-uniform attack) or 12 (efficiency maximization attack) is satisfied.

Specifically, we set the initial published intent $PI=U_{1}\wedge\cdots\wedge U_{n}$ to the same as the true intent, that is, $U_{i}=V_{i}$ for $1\leq i\leq n$. In each iteration, we iterate through every dimension in $\mathcal{D}$; for dimension $D_{i}\in\mathcal{D}$ and the corresponding feature value set $U_{i}$ in the published intent, we select the nearest neighbor feature value in $D_{i}\setminus U_{i}$. After iterating through every dimension, we add the best neighbor feature value to the published intent that minimizes Equations 11 (PI-uniform attack) or 12 (efficiency maximization attack).

We need to tackle two challenges in this method, how to find the potential nearest neighbor feature value on each dimension and how to determine the best neighbor feature value among all possible choices.

To illustrate our ideas to tackle those challenges, consider a running example in Figure 1(a), where the published intent is denoted by the red region. Here, $\mathcal{D}=D_{1}\times D_{2}$, where $D_{1}$ (horizontal) is the education level and $D_{2}$ (vertical) the workclass. Let us first look at dimension $D_{1}$, where the feature values in the published intent are $U_{1}=$ {“Masters”, “Doctorate”}. The possible feature values to expand $U_{1}$ include “Pre-school” and “Bachelors.” For each of those two, we compute the accumulated distance between the feature value and all feature values in $U_{1}$. The accumulated distance for a feature value $u\in D_{i}\setminus U_{i}$ is defined as $accu\_dist(u)=\sum_{u^{\prime}\in U_{i}}dist(u,u^{\prime})$. Suppose we assign the indices 1, 2, 3, and 4 to “Pre-school,” “Bachelors,” “Masters,” and “Doctorate,” respectively. The accumulated distance between “Pre-school” and all the features in $U_{1}$ is $5$. Similarly, the accumulated distance for “Bachelors” with respect to $U_{1}$ is 3. The feature value with the shortest accumulated distance is selected as the nearest neighbor feature value on $D_{1}$, which is “Bachelors.” On dimension $D_{2}$, there is no semantic distance among feature values. In other words, every pair of feature values on $D_{2}$ has the same distance. Thus, regarding the features in the published intent on dimension $D_{2}$, which is $U_{2}=$ {“Federal-gov”}, all the remaining features “Without-pay,” “Private,” and “Self-emp-not-inc” are treated as potential expanded feature values.

After iterating through every dimension, we have four neighbor feature values for possible expansion: “Bachelors” on $D_{1}$ (the resulting published intent is indicated in Figure 1(b)), “Without-pay” (Figure 1(c)), “Private” (Figure 1(d)), and “Self-emp-not-inc” (Figure 1(e)) on $D_{2}$.

To determine the best feature value, we develop a scoring function to comprehensively measure the effectiveness of adding the feature value to the published intent. Given a potential feature value $u_{ij}$ to be added, which is a feature value on dimension $D_{i}$, the scoring considers two factors. First, we consider the additional number of records added to the buyer’s published intent after adding the feature value. Given feature value $u_{ij}$ and the current published intent $U_{1}\wedge\cdots\wedge U_{i}\wedge\cdots\wedge U_{n}$, the addition can be expressed as $addition(u_{ij})=|\{x_{k}\}|_{x_{k}\in U_{1}\wedge\cdots\wedge\{u_{ij}\}\cdots\wedge U_{n}}$. Second, we also consider the contribution to satisfy the constraints in Equation 11 (PI-uniform attack) or Equation 12 (efficiency maximization attack), which is measured as the increase in the right-hand side of the constraint after adding the feature value and can be expressed as follows. For the PI-uniform attack,

For the efficiency maximization attack,

For each neighbor feature value, we apply min-max normalization to the associated addition of records and increase in satisfying the constraint. Then, we compute the score of the neighbor feature value $u_{ij}$ by

where $\alpha$ is the weight assigned to the evaluation factor, $\widehat{addition}(u_{ij})$ and $\widehat{increase}(u_{ij})$ are the normalized addition of records and increase in satisfying the constraint for $u_{ij}$, respectively, $\max_{u\in\cup_{i=1}^{n}(D_{i}\setminus U_{i})}\{{\widehat{addition}(u)}\}$ is the maximum of the addition of all possible neighbor feature values.

For the efficiency maximization attack, in the worst case, the buyer has to claim the entire dataset as the published intent and the attainable lower bound of the attacker’s confidence is

The ideas can be extended to tackle the problem of privacy protection against purchased record inference attacks.

Given the objective in Equation 13, in order to make the p-value of $f_{\mathcal{P}}(x)$ greater than or equal to $1-\lambda$ for any $x\in V_{1}\times\cdots\times V_{n}$, we first need to decide the buyer’s published intent (the attacker infers it as the pseudo published intent $\widehat{PI}$). Thus, given the buyer’s true intent, we first leverage the proposed expansion method to derive the published intent.

Then, given the total number of records, $q$, the buyer aims to buy and the published intent $PI=U_{1}\wedge\ldots\wedge U_{n}$, how to allocate the $q$ records to every feature value combination in $U_{1}\wedge\ldots\wedge U_{n}$ becomes a challenge. To solve the challenge, we propose four allocation methods:

Monte Carlo Simulation (MC Simulation): Generate $Z$ sets, $\mathcal{X}_{1},\mathcal{X}_{2},\mathcal{X}_{3},...\mathcal{X}_{Z}$, with each set containing $q$ records sampled from the published intent. Then, remove sets that do not satisfy the privacy constraint, i.e. the p-value of $f_{\mathcal{P}}(x)$ less than $1-\lambda$ for any $x\in V_{1}\times\cdots\times V_{n}$.

For each set remaining, we compute the utility, i.e. the ratio of the number of records in the true intent against that in the published intent. Given one of the remaining sets denoted as $\mathcal{X}_{i}$, we have:

Considering utility as a primary consideration, where the buyer seeks to maximize the ratio of the number of records in the true intent against that in the published intent, the set with the highest utility is selected as the purchased set of records.

Markov Chain Monte Carlo (MCMC): We first initialize the purchased set $\mathcal{X}=\{x_{1},x_{2},...,x_{q}\}$ by sampling $q$ records based on data distribution $f_{\mathcal{D},\widehat{PI}}$ as indicated in Equation 9.

Then, we define a set of possible moves. Given the initialized set of record $\mathcal{X}$ containing the records that the data buyer really wants (records in the buyer’s true intent) and some disguising records that the data buyer uses to hide the privacy, all the possible moves can be summarized into 4 groups: 1) remove a disguising record and add a record in the buyer’s true intent, 2) remove a disguising record and add a different disguising record, 3) remove a record in the buyer’s true intent and add a disguising record, 4) remove a record in the buyer’s true intent and add a different record in the buyer’s true intent. Note that multiple move choices exist under each group by selecting different disguising records or records in the buyer’s true intent.

For each iteration, we randomly select one move and change the current $\mathcal{X}$ to $\hat{\mathcal{X}}$ based on the move. We first check whether $\hat{\mathcal{X}}$ satisfies the privacy constraint. If the privacy constraint is satisfied, we compute the acceptance probability of $\hat{\mathcal{X}}$ as follows:

where the utility function is elaborated in Equation 17.

We accept $\hat{\mathcal{X}}$ with the computed acceptance probability, i.e. there is a $accept\_prob$ probability of transitioning from $\mathcal{X}$ to $\hat{\mathcal{X}}$.

We continue selecting the next move and updating the purchased set of records until the privacy constraint is no longer satisfied, i.e. the p-value of $f_{\mathcal{P}}(x)$ less than $1-\lambda$ for any $x\in V_{1}\times\cdots\times V_{n}$. Note that during implementation, the MCMC Algorithm terminates when the minimum difference between the privacy threshold $\lambda$ and the current confidence of an attacker on a record $x\in V_{1}\times\cdots\times V_{n}$ is less than a threshold $\epsilon$.

Greedy Markov Chain Monte Carlo (G-MCMC): The only difference between this approach and normal Markov Chain Monte Carlo is that when we define the set of possible moves, we only define the most greedy moves that improve the utility, i.e. remove a disguising record and add a record in the buyer’s true intent.

Genetic Sampling: Initialize $T$ parent sets $\mathcal{X}_{1},\mathcal{X}_{2},...,\mathcal{X}_{T}$ where each set contains $q$ records sampled from the published intent. Then, remove sets that do not satisfy the privacy constraint, i.e. the p-value of $f_{\mathcal{P}}(x)$ less than $1-\lambda$ for any $x\in V_{1}\times\cdots\times V_{n}$. For the remaining sets, we compute the utility based on the utility expression in Equation 17.

Then, we select top $R$ sets in terms of utility to form a group. For every pair (parent A, B) of sets in the group, we leverage crossover to generate two children sets (children A, B). We add all the generated children to a new population pool.

We repeat the above steps on the new population pool for a specified number of iterations $W$.

Finally, among all the sets satisfying the privacy constraint in the ultimate population pool, we select the set with the highest utility to be the buyer’s purchased set.

The Adult Dataset [28] is adopted from the UC Irvine machine learning repository [29] derived from US census data. Our analysis focuses on five attributes: age, ethnicity, gender, hours-per-week, and income. The age attribute is transformed into an ordinal scale: {“childhood” (0-17], “young adult” (17-24], “working adult” (24-61], “retirement” $>$61}. Similarly, attribute hours-per-week is discretized into: {“part-time” [0-34], “full-time” (34-40], “overtime” $>$40}. After removing the records with missing values, the dataset comprises 30,162 valid records. As the cost of each record is unspecified, a uniform cost of 1 is assigned to each record.

We generated a synthetic dataset mimicking the structure of the Adult Dataset, sharing the five attributes. The number of distinct feature values per dimension matches the Adult Dataset. The same data processing technique is applied. Regarding the data distribution, the record frequencies are sampled from a Gaussian distribution (mean=1000, std=300). The associated record costs are sampled from another Gaussian distribution (mean=20, std=5, lower bound=1).

As case studies, we define two distinct buyer true intents: [(“working adult”, “Black”, “Female”, “full-time”, “$>$50K”)] with size 1 and [(“working adult”, “Black”, “Female”, “full-time”, “$>$50K”), (“working adult”, “Asian-Pac-Islander”, “Female”, “full-time”, “$>$50K”)] with size 2. We set $\lambda$ to 30%. To maximize the utility of the published intents, i.e. the ratio of the number of records in the true intent against that in the published intent, for the Adult Dataset with a true intent size of 1, we set $\alpha$ to 0.5 for PI-uniform attack, EM attack-fc, EM attack-f, and EM attack-c, where EM attack-fc, EM attack-f, and EM attack-c refer to efficiency maximization attacks given the attacker background knowledge about both the data distribution and cost, only the data distribution, and only the cost. For the Adult Dataset with a true intent size of 2, we set $\alpha$ to 1.0, 0.6, 0.6, and 0.5 for PI-uniform attack, EM attack-fc, EM attack-f, and EM attack-c, respectively. For the synthetic dataset with a true intent size of 1, we set $\alpha$ to 0.8, 0.4, 0.4, and 0.8 for PI-uniform attack, EM attack-fc, EM attack-f, and EM attack-c, respectively. For the synthetic dataset with a true intent size of 2, we set $\alpha$ to 0.6, 0.5, 0.4, and 0.7 for PI-uniform attack, EM attack-fc, EM attack-f, and EM attack-c, respectively.

For purchased record inference attack, $\mathcal{L}$, which denotes the number of sets used for Monte Carlo simulation and permutation testing, is set to 100,000.

For MC Simulation, the total number of sets $Z$ is set to 100,000. For MCMC, the minimum difference between the privacy threshold and the current confidence of the attacker $\epsilon$ is set to 0.001 for all case studies, while for G-MCMC, $\epsilon$ is set to 0.07, 0.01, 0.005, and 0.01 for the Adult Dataset with a true intent size of 1, Adult Dataset with a true intent size of 2, synthetic dataset with a true intent size of 1, and synthetic dataset with a true intent size of 2, respectively. For genetic sampling, the number of parents $T$ is set to 50, the number of top utility sets selected for crossover $R$ is set to 10, and the number of iterations $W$ is set to 30.

The experimental results are shown in Table 1 for the Adult Dataset and Table 2 for the synthetic dataset.

In PI-uniform attacks, the absence of protection results in the attacker’s upper bound confidence reaching 100% for both datasets and for both true intent sizes of 1 and 2. This underscores the crucial role of the expansion method in safeguarding privacy. Employing the expansion method to counter PI-uniform attacks leads to significant reduction of the confidence upper bound. At the same time, this privacy protection strategy comes with a tradeoff – it requires the acquisition of additional disguise data, resulting in a slight decrease in utility. On the Adult Dataset, the utility decreases slightly.

For the synthetic dataset, the utility decreases by 53% when the true intent size is 1 and by 63.5% when the true intent size is 2. Notably, the more pronounced reduction in the utility of published intents in the synthetic dataset, compared to the Adult Dataset, can be attributed to the presence of “empty” feature value combinations. For example, in the Adult Dataset, there are 0 records falling into the group of (“childhood”, “white”, “female”, “overtime”, “$>$50k”). In a PI-uniform attack, where an attacker lacks of the knowledge of the ground truth data distribution. Such “empty” groups in the published intent enhance privacy without incurring additional disguise records. Such “empty” groups are rare in the synthetic dataset, resulting in a greater drop in the utility of published intent. In efficiency maximization attacks, the “empty” groups also result in significantly higher utility of the published intent after the expansion method, given the attacker’s background knowledge about costs alone. This utility exceeds the utility of the published intent after the expansion method when the attacker has background knowledge about both data distribution and costs, or only data distribution, by over 86% for the Adult Dataset and over 20% for the synthetic dataset.

In efficiency maximization attacks, given the attacker’s background knowledge about both the data distribution and costs, without protection an attacker’s confidence upper bound reaches 100% when the true intent size is 1 and 67.5% when the true intent size is 2 for the Adult Dataset. Regarding the synthetic dataset, without protection an attacker’s confidence upper bound reaches 100% when the true intent size is 1 and 54.7% when the true intent size is 2. The difference in confidence upper bound between true intent size of 1 and true intent size of 2 arises from the inherent characteristics of the efficiency maximization attack. The attack confidence is calculated based on the maximum $f_{\mathcal{D}}(r)$ for record $r$ in the buyer’s true intent, divided by the sum of $f_{\mathcal{D}}(t)$ for every record $t$ in the published intent, as indicated in Equation 12. Without protection and with a true intent size of 1, the confidence is necessarily 100% since the published intent contains only this single true intent. However, with a true intent size of 2 and no protection, the numerator is the maximum between the two true intents, while the denominator is the sum of the two, resulting in a lower attack confidence. In essence, the presence of multiple true intents balances each other, leading to a lower attacker confidence even without protection.

For the Adult Dataset, upon implementing the expansion method, the attack confidence decreases by 89.9% when the true intent size is 1 and by 59.1% when the true intent size is 2. The increase in privacy comes at the cost of utility, i.e. a decrease by 89.9% and 87.6%, respectively. Regarding the synthetic dataset, the attack confidence decreases by 70.5% when the true intent size is 1 and by 29.5% when the true intent size is 2. The increase in privacy comes at the cost of utility, i.e. a decrease by 73.5% and 53.4%, respectively.

Concerning purchased record inference attacks, we assess the effectiveness of four proposed allocation methods in generating privacy-preserving and high-utility set of records for purchase by the data buyer. The experimental results are shown in Table 3.

In purchased record inference attacks, the absence of protection results in the attacker’s upper bound confidence reaching 100% for both datasets. This underscores the crucial role of the allocation method in safeguarding privacy.

For the Adult Dataset, MC Simulation, G-MCMC, and Genetic Sampling exhibit comparable results in terms of utility, measured by the ratio of the number of records in the true intent against that in the published intent. MCMC has the worst utility, exhibiting a 3.1% and 7.5% decrease for true intent sizes of 1 and 2, respectively. Concerning time, MC Simulation’s runtime, requiring 24 seconds for true intent size 1 and 47 seconds for true intent size 2, is notably longer than that of other methods. G-MCMC has the fastest runtime, requiring only 0.001 seconds, while Genetic Sampling requires approximately 1 second. Concerning privacy, MC Simulation, G-MCMC, and Genetic Sampling show an attacker confidence upper bound of 23.6% and around 29.0% for true intent sizes of 1 and 2, respectively, all closely approaching the privacy threshold of 30%. MCMC excels in privacy, exhibiting decreases in attacker confidence of 17.2% and 26.3%, respectively.

The synthetic dataset exhibits a similar trend to the Adult Dataset. A slight difference lies in the higher utility of MC Simulation and G-MCMC compared to Genetic Sampling. Another observation is a more apparent gap in runtime between MC Simulation, G-MCMC, and Genetic Sampling, where G-MCMC only requires 0.01 seconds and 0.1 seconds for true intent sizes of 1 and 2, respectively. Genetic Sampling requires 6 seconds and 12 seconds, respectively. MC Simulation performs the worst in runtime, requiring 333 seconds and 640 seconds, respectively.

In summary, our findings indicate that MC Simulation, G-MCMC, and Genetic Sampling consistently achieve comparable results in utility, but G-MCMC consistently outperforms the other two in terms of runtime. Notably, MC Simulation exhibits poor runtime performance. MCMC has the worst performance in utility but is able to generate a more privacy-preserving set of records for purchase by the buyer.

We conduct experiments by removing dimensions “Age,” “Ethnicity,” “Gender,” “Hours-per-week,” and “Income,” respectively, to examine the effect on attacker confidence. The true intent in the reduced space is the projection of the original data space. That is, with true intent $V_{1}\wedge\cdots\wedge V_{n}$ in the original data space, after dimension $D_{i}$ is removed, the true intent becomes $V_{1}\wedge\cdots V_{i-1}\wedge V_{i+1}\wedge\cdots V_{n}$. The experiments are conducted on the Adult Dataset with a true intent size of 2. The efficiency maximization attack is conducted given the attacker’s background knowledge of both the data distribution and associated costs.

A published intent can also be projected into the subspace reduced, but may no longer meet the privacy threshold. Consequently, we update the projected published intent using our proposed expansion method and compare its utility with that of the initially projected published intent. The results are shown in Table 4.

In the PI-uniform attack, the removal of the “Age” dimension has a significant effect, resulting in a substantial increase in the attacker’s confidence, both the lower bound (37.5%) and upper bound (75%). With the privacy threshold set to 30%, the projected published intent no longer meets the privacy threshold, necessitating the addition of more disguise records into the published intent. As a consequence, the updated projected number of records in the published intent increases. The updated projected ratio of the number of records in the true intent against that in the published intent decreases by 15.8%. This observation indicates that, prior to projection, a significant portion of the disguise records used to safeguard the true intent through the expansion method is distributed along the “Age” dimension. Thus, the removal of the “Age” dimension results in a dramatic increase in attacker confidence.

In the efficiency maximization attack, the removal of the “Gender” dimension results in a substantial increase (25.3%) in attacker confidence, surpassing the 30% privacy threshold. Consequently, to enhance the protection of the projected published intent, additional disguise records must be incorporated, leading to an increase of the number of records in the published intent. Thus, there is an associated decrease of 43.3% in the utility.

A noteworthy observation is the comparison between the size of the projected published intent and the size of the updated projected published intent after expansion, specifically after removing the “Age” dimension for PI-uniform attack and the “Gender” dimension for efficiency maximization attack. In the case of PI-uniform attack, the size increases from 2 to 8, reflecting the expansion method’s incorporation of additional feature values into the published intent; thus, the size of the published intent expands. In contrast, for the efficiency maximization attack, the size decreases from 36 to 3. This reduction can be attributed to its inherent characteristics, which necessitates obtaining more records to ensure a sufficiently substantial sum of $f_{\mathcal{D}}(t)$ for record $t$ in the published intent, as indicated in Equation 12. Consequently, the size of the updated projected published intent may not necessarily increase, given that there are now more records falling within a specific intent due to projection.

We investigate the effect of buyer’s true intent size on the resulting published intent for PI-uniform attack and efficiency maximization attack. For each dimension, we augment the true intent by adding feature values within that dimension. The results are shown in Figures 2. In each figure, each feature value on the x-axis denotes that the buyer’s true intent on that dimension encompasses the current feature value and all feature values to its left. The experiments are conducted on the Adult Dataset with a true intent size of 1. The efficiency maximization attack is conducted given the attacker’s background knowledge of both the data distribution and associated costs.

In the PI-uniform attack, we observe that the sizes of the published intent and true intent often consistently increase in the same ratio, with no change in the upper bound confidence. Nevertheless, certain instances deviate from this pattern, where the size of the published intent does not increase despite an increase in the attacker confidence upper bound, which is because the original confidence is excessively low. Moreover, it is evident that the attacker’s confidence lower bound decreases as the size of the published intent increases.

In the efficiency maximization attack, in most instances, the size of the published intent either remains constant or experiences a slight increase with an enlargement of the true intent, all while maintaining a consistent confidence level.

Notably, when expanding on a new feature value, the new published intent may exhibit higher utility, i.e. lower number of disguise records, even if the original true intent is a proper subset of the expanded true intent. This phenomenon arises due to the greedy nature of the expansion method, whereby, at each iteration, the feature value deemed the best may not necessarily be the globally optimal one.

Sensitivity analyses are conducted on the Adult Dataset with a true intent size of 2. The efficiency maximization attack is conducted given the attacker’s background knowledge of both the data distribution and associated costs.