# Social Security and Privacy for Social IoT Polymorphic Value Set: A Solution to Inference Attacks on Social Networks

Authors: Yunpeng Gao; Nan Zhang
Journal: Security and Communication Networks
 (2019)

---

## Abstract

Social Internet of Things (SIoT) integrates social network schemes into Internet of Things (IoT), which provides opportunities for IoT objects to form social communities. Existing social network models have been adopted by SIoT paradigm. The wide distribution of IoT objects and openness of social networks, however, make it more challenging to preserve privacy of IoT users. In this paper, we present a novel framework that preserves privacy against inference attacks on social network data through ranked retrieval models. We propose PVS, a privacy-preserving framework that involves the design of polymorphic value sets and ranking functions. PVS enables polymorphism of private attributes by allowing them to respond to different queries in different ways. We begin this work by identifying two classes of adversaries, authenticity-ignorant adversary, and authenticity-knowledgeable adversary, based on their knowledge of the distribution of private attributes. Next, we define the measurement functions of utility loss and propose PVSV and PVST that preserve privacy against authenticity-ignorant and authenticity-knowledgeable adversaries, respectively. We take into account the utility loss of query results in the design of PVSV and PVST. Finally, we show that PVSV and PVST meet the privacy guarantee with acceptable utility loss in extensive experiments over real-world datasets.


---

## Body

## 1. Introduction

### 1.1. Motivation

SIoT integrates social network schemes into IoT systems, which provides opportunities for IoT objects to form social networks. The SIoT paradigm is promising as it is believed that SIoT structures are helpful in enhancing the navigability of IoT networks, identifying levels of trustworthiness and reusing existing social network models [5]. In this scenario, privacy and security issues have been extensively studied [6, 7, 24, 48]. However, current studies in privacy preservation of IoT systems focus on access control [23, 46], communication and authentication protocols [4, 34, 44], and attribute-based encryption [39, 43]. The features of social network have not been thoroughly considered.The nature of online social networks (OSN) requires sharing of information. User information, including activity patterns and descriptive attributes, is mined and analyzed to improve user experience of OSN applications. Third party users also take advantage of the huge amount of data collected by social networks [21]. As part of the improvement of user experience, ranked retrieval models have been extensively studied and applied to many OSN features, e.g., link prediction and recommendation systems [32, 36, 47]. For instance, given a user’s information (which can be a tuple in a database), a ranked retrieval model returns a ranking result that serves OSN features, e.g., “People you may know” and “Recommended for you.” Furthermore, many OSN providers improve the accuracy of ranked results by taking into account private attributes of users in the ranked retrieval model. For example, sensitive demographics such as race, religion, and income can help in friend recommendation features as intuitively people sharing similar demographics are more likely to be interested in each other.OSN providers relieve users’ concern of privacy leakage by allowing them to mark attributes as “private” and hiding private attributes from profiling pages and ranked results. Users believe that their privacy is well protected since private attributes are invisible to the public in their profiles or any ranked results. However, Rahman et al. [35] proposed Rank Inference and showed that privacy of private attributes in the ranked retrieval model is not guaranteed. In their approach, the value of a private attribute can be inferred through a ranked retrieval interface given the premises that the domain of the private attribute is finite and that the ranking function has both monotonicity property and additivity property [35]. To be more specific, given monotonicity and additivity conditions, an adversary is always able to find a pair of differential queries, qθ and qθ′, such that (a) qθ and qθ′ share the same predicate on all attributes except for a private attribute B1, (b) the value of B1 in qθ′ is θ while the value of B1 in qθ is not, and (c) the ranked result of qθ contains the victim tuple v while the ranked result of qθ′ does not. Rahman et al. showed that given the above conditions, the adversary was able to conclude that the value of v’s B1 is not equal to θ. Furthermore, the adversary was able to infer the value of v’s B1 by finding more differential queries and excluding more values from the domain of B1, as long as the domain is finite.Privacy issues arise when private attributes of users are taken into account in the ranked retrieval model. Intuitively, the issues can be solved by removing private attributes from ranking functions, which decreases the utility of many OSN features, the recommendation system cannot provide accurate results. From OSN providers’ perspective, removing private attributes is not a practical solution. Therefore, this work aims not only to address the issue of rank inference but also to propose a framework that preserves the privacy of users against all inference attacks through the ranked retrieval model while minimizes utility loss.


### 1.2. Related Work

Encryption technologies have been used throughout history in security and privacy preservation. Searching on encrypted data [10, 38] has been introduced to ensure data privacy. Cao et al. [9] proposed a scheme that allows privacy-preserving ranked search over encrypted data. A query consisting of multiple keywords is conducted by searching over encrypted documents with secure k-nearest neighbor (kNN) technique. Chen et al. [11] took into consideration correlations between documents before conducting a search query and achieved better performance. Vertical fragmentation [13, 15, 16, 22] has been applied to encrypted data, which hides identities of users by separating identifier attributes with descriptive attributes. However, encrypted searching is developed to preserve privacy against adversaries in a cloud computing environment. Adversaries can still access decrypted searching results from which private attribute values can be inferred.As ONS has been emerging as an important source for big data, many studies have been carried out for privacy-preserving data mining (PPDM) and privacy-preserving data publishing (PPDP). Perturbative methods implement the “camouflage” paradigm where original data are directly modified [28]. Agrawal et al. [3] proposed an algorithm that perturbs data with random additive noise. Liu et al. proposed data perturbation with multiplicative noise. However, random noise has predictable structures in the spectral domain, and thus, privacy provided by additive noise is questionable [25]. Furthermore, additive or multiplicative noise can only be applied to numerical data. Data swapping approaches [19, 30, 31] perturb data by swapping values between records that are close to each other. Other distance-based approaches include [12] in which data points are perturbed without changing their relevant closeness relationships and [2] in which data points are clustered and each data point’s value is replaced by the value of the cluster center. However, those approaches rely on a universal measurement of closeness between data points in multidimensional space. Furthermore, they are limited by the distributions of data points.Generalization is the process of replacing a group of values with a more general value that can represent the group. Suppression is the ultimate state of generalization such that the representative value is “not applicable” and as a result, the group of values is removed from the dataset [45]. k-anonymity [40, 41] is a widely studied approach that preserves privacy of records by grouping at least k records into an equivalence class. The attribute values of the k records are suppressed so that the k records are indistinguishable from adversaries. Machanavajjhala et al. [27] proposed L-diversity that focuses on attribute privacy. L-diversity forces each equivalent class to have at least l different values for each attribute. Li et al. [26] proposed T-closeness that further considers the distribution of attribute values. T-closeness sets a threshold for the variance between the distribution of a private attribute in each equivalence class and the distribution of the same attribute in the entire dataset. However, those approaches are developed to preserve privacy of published data, while the ranked retrieval model of ONS does not directly reveal private attributes to the public. Furthermore, suppression of private attribute values introduces unnecessary utility loss to the ranked retrieval model. Equivalent Set [20] was proposed to preserve privacy against inference attacks through the ranked retrieval model. This approach groups different tuples into a set such that they are indistinguishable in ranked results. However, this approach requires that tuples in the same equivalent set have different values in every private attribute and have the same value in every public attribute. Assume that a kNN query q is sent to a ranked retrieval interface protected by Equivalent Set and that a tuple t is equal to q in most private attributes. Since the other tuples in the same equivalent set of t are different from t in every private attribute, they must be different from q in most private attributes too. Therefore, the original rank of t given q should be much higher than that of any other tuple in the same equivalent set. In this case, the rank of t given q will be significantly lowered by Equivalent Set in order to achieve indistinguishability, which reduces the accuracy of the ranked result of q. Furthermore, it is possible that there is no t′ such that t′ is different from t in every private attribute and is same with t in every public attribute. In this case, we have to suppress the private attribute values of t, which further introduces utility loss.Differential privacy [8, 17, 18] is another widely studied framework that preserves privacy of published datasets or hidden databases. It imposes a strong guarantee of privacy on tuples in statistical databases by adding noise to the process of query results. However, the ranked retrieval model outputs ranks of tuples, instead of their values or aggregate statistics. We cannot directly add noise to ranked results as the rank of a tuple is determined by not only the tuple itself but also by other tuples in the database. Furthermore, the optimization of the ranked retrieval model has not been considered.


### 1.3. Contributions

This work presents a novel scheme for privacy-preserving the ranked retrieval model. We start with an introduction to the adversary model and introduce our definition of privacy guarantee. We identify two categories of adversaries based on their prior knowledge and assume that adversaries can launch optimal inference attacks through ranked results.We propose the polymorphic value set (PVS), a privacy-preserving framework for the ranked retrieval model. Different from existing methods, PVS does not directly modify values of tuples or query results. Instead, PVS enables polymorphism of private attributes such that a private attribute of a tuple can respond to different queries in different ways. We prove that our framework meets the privacy guarantee stated in Problem Statement. For adversaries with and without prior knowledge, we design and implement the polymorphic value set with true values (PVST) and polymorphic value set with Virtual Values (PVSV), respectively. In the design of PVST and PVSV, we consider utility loss in the ranked retrieval model and propose a practical measurement of utility loss. We prove that the task of minimizing utility loss is NP-hard and present two heuristic algorithms that implement PVST and PVSV, respectively. We run our implementations of PVST and PVSV on a real-world dataset from eHarmony [29] that contains 486,464 tuples. The experiments yield excellent results with respect to privacy guarantee and utility loss.The remainder of this paper is organized as follows. Problem Statement introduces the adversary model and the privacy guarantee. Privacy-Preserving Framework introduces our privacy-preserving framework. Framework with Virtual Values presents the design and implementation of PVSV, along with our analysis of utility loss. The implementation of PVST and analysis of utility loss are presented in Framework with True Values. Experimental Results contains our experimental evaluation of PVSV and PVST. In Conclusions, we conclude this paper with a summary of our key contributions and a discussion of some open problems.


## 1.1. Motivation

SIoT integrates social network schemes into IoT systems, which provides opportunities for IoT objects to form social networks. The SIoT paradigm is promising as it is believed that SIoT structures are helpful in enhancing the navigability of IoT networks, identifying levels of trustworthiness and reusing existing social network models [5]. In this scenario, privacy and security issues have been extensively studied [6, 7, 24, 48]. However, current studies in privacy preservation of IoT systems focus on access control [23, 46], communication and authentication protocols [4, 34, 44], and attribute-based encryption [39, 43]. The features of social network have not been thoroughly considered.The nature of online social networks (OSN) requires sharing of information. User information, including activity patterns and descriptive attributes, is mined and analyzed to improve user experience of OSN applications. Third party users also take advantage of the huge amount of data collected by social networks [21]. As part of the improvement of user experience, ranked retrieval models have been extensively studied and applied to many OSN features, e.g., link prediction and recommendation systems [32, 36, 47]. For instance, given a user’s information (which can be a tuple in a database), a ranked retrieval model returns a ranking result that serves OSN features, e.g., “People you may know” and “Recommended for you.” Furthermore, many OSN providers improve the accuracy of ranked results by taking into account private attributes of users in the ranked retrieval model. For example, sensitive demographics such as race, religion, and income can help in friend recommendation features as intuitively people sharing similar demographics are more likely to be interested in each other.OSN providers relieve users’ concern of privacy leakage by allowing them to mark attributes as “private” and hiding private attributes from profiling pages and ranked results. Users believe that their privacy is well protected since private attributes are invisible to the public in their profiles or any ranked results. However, Rahman et al. [35] proposed Rank Inference and showed that privacy of private attributes in the ranked retrieval model is not guaranteed. In their approach, the value of a private attribute can be inferred through a ranked retrieval interface given the premises that the domain of the private attribute is finite and that the ranking function has both monotonicity property and additivity property [35]. To be more specific, given monotonicity and additivity conditions, an adversary is always able to find a pair of differential queries, qθ and qθ′, such that (a) qθ and qθ′ share the same predicate on all attributes except for a private attribute B1, (b) the value of B1 in qθ′ is θ while the value of B1 in qθ is not, and (c) the ranked result of qθ contains the victim tuple v while the ranked result of qθ′ does not. Rahman et al. showed that given the above conditions, the adversary was able to conclude that the value of v’s B1 is not equal to θ. Furthermore, the adversary was able to infer the value of v’s B1 by finding more differential queries and excluding more values from the domain of B1, as long as the domain is finite.Privacy issues arise when private attributes of users are taken into account in the ranked retrieval model. Intuitively, the issues can be solved by removing private attributes from ranking functions, which decreases the utility of many OSN features, the recommendation system cannot provide accurate results. From OSN providers’ perspective, removing private attributes is not a practical solution. Therefore, this work aims not only to address the issue of rank inference but also to propose a framework that preserves the privacy of users against all inference attacks through the ranked retrieval model while minimizes utility loss.


## 1.2. Related Work

Encryption technologies have been used throughout history in security and privacy preservation. Searching on encrypted data [10, 38] has been introduced to ensure data privacy. Cao et al. [9] proposed a scheme that allows privacy-preserving ranked search over encrypted data. A query consisting of multiple keywords is conducted by searching over encrypted documents with secure k-nearest neighbor (kNN) technique. Chen et al. [11] took into consideration correlations between documents before conducting a search query and achieved better performance. Vertical fragmentation [13, 15, 16, 22] has been applied to encrypted data, which hides identities of users by separating identifier attributes with descriptive attributes. However, encrypted searching is developed to preserve privacy against adversaries in a cloud computing environment. Adversaries can still access decrypted searching results from which private attribute values can be inferred.As ONS has been emerging as an important source for big data, many studies have been carried out for privacy-preserving data mining (PPDM) and privacy-preserving data publishing (PPDP). Perturbative methods implement the “camouflage” paradigm where original data are directly modified [28]. Agrawal et al. [3] proposed an algorithm that perturbs data with random additive noise. Liu et al. proposed data perturbation with multiplicative noise. However, random noise has predictable structures in the spectral domain, and thus, privacy provided by additive noise is questionable [25]. Furthermore, additive or multiplicative noise can only be applied to numerical data. Data swapping approaches [19, 30, 31] perturb data by swapping values between records that are close to each other. Other distance-based approaches include [12] in which data points are perturbed without changing their relevant closeness relationships and [2] in which data points are clustered and each data point’s value is replaced by the value of the cluster center. However, those approaches rely on a universal measurement of closeness between data points in multidimensional space. Furthermore, they are limited by the distributions of data points.Generalization is the process of replacing a group of values with a more general value that can represent the group. Suppression is the ultimate state of generalization such that the representative value is “not applicable” and as a result, the group of values is removed from the dataset [45]. k-anonymity [40, 41] is a widely studied approach that preserves privacy of records by grouping at least k records into an equivalence class. The attribute values of the k records are suppressed so that the k records are indistinguishable from adversaries. Machanavajjhala et al. [27] proposed L-diversity that focuses on attribute privacy. L-diversity forces each equivalent class to have at least l different values for each attribute. Li et al. [26] proposed T-closeness that further considers the distribution of attribute values. T-closeness sets a threshold for the variance between the distribution of a private attribute in each equivalence class and the distribution of the same attribute in the entire dataset. However, those approaches are developed to preserve privacy of published data, while the ranked retrieval model of ONS does not directly reveal private attributes to the public. Furthermore, suppression of private attribute values introduces unnecessary utility loss to the ranked retrieval model. Equivalent Set [20] was proposed to preserve privacy against inference attacks through the ranked retrieval model. This approach groups different tuples into a set such that they are indistinguishable in ranked results. However, this approach requires that tuples in the same equivalent set have different values in every private attribute and have the same value in every public attribute. Assume that a kNN query q is sent to a ranked retrieval interface protected by Equivalent Set and that a tuple t is equal to q in most private attributes. Since the other tuples in the same equivalent set of t are different from t in every private attribute, they must be different from q in most private attributes too. Therefore, the original rank of t given q should be much higher than that of any other tuple in the same equivalent set. In this case, the rank of t given q will be significantly lowered by Equivalent Set in order to achieve indistinguishability, which reduces the accuracy of the ranked result of q. Furthermore, it is possible that there is no t′ such that t′ is different from t in every private attribute and is same with t in every public attribute. In this case, we have to suppress the private attribute values of t, which further introduces utility loss.Differential privacy [8, 17, 18] is another widely studied framework that preserves privacy of published datasets or hidden databases. It imposes a strong guarantee of privacy on tuples in statistical databases by adding noise to the process of query results. However, the ranked retrieval model outputs ranks of tuples, instead of their values or aggregate statistics. We cannot directly add noise to ranked results as the rank of a tuple is determined by not only the tuple itself but also by other tuples in the database. Furthermore, the optimization of the ranked retrieval model has not been considered.


## 1.3. Contributions

This work presents a novel scheme for privacy-preserving the ranked retrieval model. We start with an introduction to the adversary model and introduce our definition of privacy guarantee. We identify two categories of adversaries based on their prior knowledge and assume that adversaries can launch optimal inference attacks through ranked results.We propose the polymorphic value set (PVS), a privacy-preserving framework for the ranked retrieval model. Different from existing methods, PVS does not directly modify values of tuples or query results. Instead, PVS enables polymorphism of private attributes such that a private attribute of a tuple can respond to different queries in different ways. We prove that our framework meets the privacy guarantee stated in Problem Statement. For adversaries with and without prior knowledge, we design and implement the polymorphic value set with true values (PVST) and polymorphic value set with Virtual Values (PVSV), respectively. In the design of PVST and PVSV, we consider utility loss in the ranked retrieval model and propose a practical measurement of utility loss. We prove that the task of minimizing utility loss is NP-hard and present two heuristic algorithms that implement PVST and PVSV, respectively. We run our implementations of PVST and PVSV on a real-world dataset from eHarmony [29] that contains 486,464 tuples. The experiments yield excellent results with respect to privacy guarantee and utility loss.The remainder of this paper is organized as follows. Problem Statement introduces the adversary model and the privacy guarantee. Privacy-Preserving Framework introduces our privacy-preserving framework. Framework with Virtual Values presents the design and implementation of PVSV, along with our analysis of utility loss. The implementation of PVST and analysis of utility loss are presented in Framework with True Values. Experimental Results contains our experimental evaluation of PVSV and PVST. In Conclusions, we conclude this paper with a summary of our key contributions and a discussion of some open problems.


## 2. Problem Statement

### 2.1. Ranked Retrieval Model

In information retrieval, we have witnessed extensive research in the ranked retrieval model. Unlike the Boolean retrieval model where only results that exactly match the predicates can be returned, the ranked retrieval model allows users to retrieve a list of records sorted by a proprietary ranking function. Therefore, the ranked retrieval model provides an alternative solution for users seeking results sorted by their relevance to the query.As discussed in the introduction, many OSN applications have been using the ranked retrieval model to process incoming queries. Upon a queryq, the ranked retrieval model would calculate each tuple t’s score according to a proprietary score function st∣q and return top-k tuples in descending order of their scores. The attributes of tuples could be either categorical or numerical. In this paper, we consider only categorical data, which does not limit the scope of our research. Actually, numerical data can be treated as categorical data by categorizing the numerical domain into small intervals such that no more than one tuple in the database falls into the same interval. Without loss of generality, we also assume that there is no duplicate tuple that is equal to another tuple in every attribute.We now formalize our ranked retrieval model with categorical attributes. Consider ann-tuple database D with m public attributes A1,…,Am and m′ private attributes B1,…,Bm′. Let ViA(resp. VjB) denote the value domain of Ai(resp. Bj). Let tAi(resp. tBj) denote the value of t in Ai(resp. Bj). Upon query q, the score function st∣q computes a score for each tuple t∈D. The ranked retrieval model will then sort all tuples in D in the descending order and return them as the ranked result. We consider the case where the score function is linear. Therefore, st∣q can be defined as(1)st∣q=∑i=1mwiAρqAi,tAi+∑j=1m′wiBρqBi,tBi,where wiA(resp. wjB) ∈0,1 is the weight of attribute Ai(resp. Bj) in the score function, and the matching function ρqAi,tAi, (resp. ρqBi,tBi) indicates if t matches q in attribute Ai (resp. Bj). Therefore, the value of ρβ1,β2 is 1 if β1 is equal to β2, and the value of ρβ1,β2 is 0 if β1 is not equal to β2. Note that our ranked retrieval model satisfies the monotonicity and additivity properties defined in [35].


### 2.2. Adversary Model

In Motivation, we mentioned that we do not make any assumption about the method adopted by an adversary when attacking a database. We also assume that the adversary has prior knowledge about the metadata of tables in the database, as well as the proprietary ranking function. Furthermore, the adversary is assumed to be able to issue queries to the ranked retrieval model, view ranked results, and insert tuples to the database. As a result, the adversary is able to retrieve all public attribute values by crawling the database through the query interface [37]. We denote the set of queries issued by the adversary as QA, the set of tuples inserted by the adversary as IA, and the corresponding set of ranked results as RD. RD is fully determined by QA and IA given fixed D. We name all information regarding a tuple t∈D that an adversary can find in RD as the trace of t and denote the trace of t as Tt. The trace of t includes, but not limited to, the rank of t and the relationship between t and any other tuple (e.g., t has a higher or lower rank than another tuple t′) in a ranked result. Therefore, given fixed D, IA and QA, Tt is fully determined by the attribute values of t.Another capability of the adversary we model is the adversary’s prior knowledge. Consider an extreme case where the adversary knows the equivalence relation between two attributesB1 and A1. In this case, even without RD, the adversary is still able to infer the value of B1 of any t∈D. In reality, an adversary can acquire such attribute correlations by being or consulting an expert in the domain of the dataset or by adopting data mining methods [42]. For example, based on the personal information (e.g., gender, ethnicity, age, and blood type which can be used to infer the gene) stored as public attributes and published in public medical data repositories, genetic epidemiologists can generally conclude that an individual does not have some diseases, merely based on the fact that these diseases would never be found by the candidate gene among historic medical datasets. Therefore, an adversary with prior knowledge could eliminate the possibility of a certain tuple in the database. We model prior knowledge as a function PKt∣D that takes as input t and D and returns either 0 or 1. PKt∣D=0 indicates that, given prior knowledge, the possibility of t∈D is zero. PKt∣D=1 indicates that the adversary cannot eliminate the possibility of t∈D. As prior knowledge helps adversaries in launching an inference attack, adversaries can be partitioned into two classes: adversaries with prior knowledge and adversaries without prior knowledge of the dataset.Definition 1.
We name adversaries without prior knowledge of the authenticity of any tuple as authenticity-ignorant adversaries. For authenticity-ignorant adversaries,PKt∣D always outputs 1. We name adversaries with such prior knowledge as authenticity-knowledgeable adversaries. For authenticity-knowledgeable adversaries, PKt∣D=1 if t∈D and PKt∣D=0 if t∉D.The objective of both classes of adversaries is to maximize the followinggv,Bj value when inferring the value of victim tuple v in attribute Bj:(2)gv,Bj=PrvBj=a,where PrvBj=a is the probability of vBj=a and a is the value inferred by the adversary given prior knowledge and ranked results.For authenticity-ignorant adversaries,PKt∣D always outputs 1 regardless of t and D. We only assume the cases where users input true information to the databases. Therefore, for authenticity-knowledgeable adversaries, PKt∣D=1 if t∈D and PKt∣D=0 if t∉D. In this paper, we assume a strong adversary that can infer the private attribute values of an arbitrary tuple, given the premise that the trace of the target tuple is unique. The premise can be easily met because as long as there is no duplicate tuple in the dataset, the adversary can always construct well-designed IA and QA such that the trace of the target tuple is different from the trace of any other tuple. Therefore, the adversary can always find a such that PrvBj=a=100%.


### 2.3. Problem Statement

A privacy breach can be described by a successful inference of a private attribute value in the database. We view privacy ofvBj as the upper bound on the possibility that an adversary succeeds in inferring the value of vBj. Note that we do not make any assumption about the adversary’s attacking method. Our objective in this paper is to present a framework that sets an upper bound on the probability of successful inference of an arbitrary private attribute for tuple t∈D. Therefore, we define the objective of the framework as(3)∀t∈D,j∈1,…,m′,gv,Bj≤ε.We present the upper boundϵ as our privacy guarantee.However, a privacy-preserving framework should provide not only a privacy guarantee but also a notion of utility—after all, a framework that removes all private attribute values or replaces them with randomly generated values can surely preserve privacy. Therefore, we use a measurement based on the variance of ranked results before and after adopting our framework. GivenD and a set of all possible queries denoted as Q, we define the utility loss for our ranked retrieval model as follows:(4)U=∑t∈D∑q∈QRankt∣q−Rank′t∣q,where Rankt∣q and Rank′t∣q refer to the ranks of tuple t in the ranked result given query q before and after applying our frameworks, respectively.


## 2.1. Ranked Retrieval Model

In information retrieval, we have witnessed extensive research in the ranked retrieval model. Unlike the Boolean retrieval model where only results that exactly match the predicates can be returned, the ranked retrieval model allows users to retrieve a list of records sorted by a proprietary ranking function. Therefore, the ranked retrieval model provides an alternative solution for users seeking results sorted by their relevance to the query.As discussed in the introduction, many OSN applications have been using the ranked retrieval model to process incoming queries. Upon a queryq, the ranked retrieval model would calculate each tuple t’s score according to a proprietary score function st∣q and return top-k tuples in descending order of their scores. The attributes of tuples could be either categorical or numerical. In this paper, we consider only categorical data, which does not limit the scope of our research. Actually, numerical data can be treated as categorical data by categorizing the numerical domain into small intervals such that no more than one tuple in the database falls into the same interval. Without loss of generality, we also assume that there is no duplicate tuple that is equal to another tuple in every attribute.We now formalize our ranked retrieval model with categorical attributes. Consider ann-tuple database D with m public attributes A1,…,Am and m′ private attributes B1,…,Bm′. Let ViA(resp. VjB) denote the value domain of Ai(resp. Bj). Let tAi(resp. tBj) denote the value of t in Ai(resp. Bj). Upon query q, the score function st∣q computes a score for each tuple t∈D. The ranked retrieval model will then sort all tuples in D in the descending order and return them as the ranked result. We consider the case where the score function is linear. Therefore, st∣q can be defined as(1)st∣q=∑i=1mwiAρqAi,tAi+∑j=1m′wiBρqBi,tBi,where wiA(resp. wjB) ∈0,1 is the weight of attribute Ai(resp. Bj) in the score function, and the matching function ρqAi,tAi, (resp. ρqBi,tBi) indicates if t matches q in attribute Ai (resp. Bj). Therefore, the value of ρβ1,β2 is 1 if β1 is equal to β2, and the value of ρβ1,β2 is 0 if β1 is not equal to β2. Note that our ranked retrieval model satisfies the monotonicity and additivity properties defined in [35].


## 2.2. Adversary Model

In Motivation, we mentioned that we do not make any assumption about the method adopted by an adversary when attacking a database. We also assume that the adversary has prior knowledge about the metadata of tables in the database, as well as the proprietary ranking function. Furthermore, the adversary is assumed to be able to issue queries to the ranked retrieval model, view ranked results, and insert tuples to the database. As a result, the adversary is able to retrieve all public attribute values by crawling the database through the query interface [37]. We denote the set of queries issued by the adversary as QA, the set of tuples inserted by the adversary as IA, and the corresponding set of ranked results as RD. RD is fully determined by QA and IA given fixed D. We name all information regarding a tuple t∈D that an adversary can find in RD as the trace of t and denote the trace of t as Tt. The trace of t includes, but not limited to, the rank of t and the relationship between t and any other tuple (e.g., t has a higher or lower rank than another tuple t′) in a ranked result. Therefore, given fixed D, IA and QA, Tt is fully determined by the attribute values of t.Another capability of the adversary we model is the adversary’s prior knowledge. Consider an extreme case where the adversary knows the equivalence relation between two attributesB1 and A1. In this case, even without RD, the adversary is still able to infer the value of B1 of any t∈D. In reality, an adversary can acquire such attribute correlations by being or consulting an expert in the domain of the dataset or by adopting data mining methods [42]. For example, based on the personal information (e.g., gender, ethnicity, age, and blood type which can be used to infer the gene) stored as public attributes and published in public medical data repositories, genetic epidemiologists can generally conclude that an individual does not have some diseases, merely based on the fact that these diseases would never be found by the candidate gene among historic medical datasets. Therefore, an adversary with prior knowledge could eliminate the possibility of a certain tuple in the database. We model prior knowledge as a function PKt∣D that takes as input t and D and returns either 0 or 1. PKt∣D=0 indicates that, given prior knowledge, the possibility of t∈D is zero. PKt∣D=1 indicates that the adversary cannot eliminate the possibility of t∈D. As prior knowledge helps adversaries in launching an inference attack, adversaries can be partitioned into two classes: adversaries with prior knowledge and adversaries without prior knowledge of the dataset.Definition 1.
We name adversaries without prior knowledge of the authenticity of any tuple as authenticity-ignorant adversaries. For authenticity-ignorant adversaries,PKt∣D always outputs 1. We name adversaries with such prior knowledge as authenticity-knowledgeable adversaries. For authenticity-knowledgeable adversaries, PKt∣D=1 if t∈D and PKt∣D=0 if t∉D.The objective of both classes of adversaries is to maximize the followinggv,Bj value when inferring the value of victim tuple v in attribute Bj:(2)gv,Bj=PrvBj=a,where PrvBj=a is the probability of vBj=a and a is the value inferred by the adversary given prior knowledge and ranked results.For authenticity-ignorant adversaries,PKt∣D always outputs 1 regardless of t and D. We only assume the cases where users input true information to the databases. Therefore, for authenticity-knowledgeable adversaries, PKt∣D=1 if t∈D and PKt∣D=0 if t∉D. In this paper, we assume a strong adversary that can infer the private attribute values of an arbitrary tuple, given the premise that the trace of the target tuple is unique. The premise can be easily met because as long as there is no duplicate tuple in the dataset, the adversary can always construct well-designed IA and QA such that the trace of the target tuple is different from the trace of any other tuple. Therefore, the adversary can always find a such that PrvBj=a=100%.


## 2.3. Problem Statement

A privacy breach can be described by a successful inference of a private attribute value in the database. We view privacy ofvBj as the upper bound on the possibility that an adversary succeeds in inferring the value of vBj. Note that we do not make any assumption about the adversary’s attacking method. Our objective in this paper is to present a framework that sets an upper bound on the probability of successful inference of an arbitrary private attribute for tuple t∈D. Therefore, we define the objective of the framework as(3)∀t∈D,j∈1,…,m′,gv,Bj≤ε.We present the upper boundϵ as our privacy guarantee.However, a privacy-preserving framework should provide not only a privacy guarantee but also a notion of utility—after all, a framework that removes all private attribute values or replaces them with randomly generated values can surely preserve privacy. Therefore, we use a measurement based on the variance of ranked results before and after adopting our framework. GivenD and a set of all possible queries denoted as Q, we define the utility loss for our ranked retrieval model as follows:(4)U=∑t∈D∑q∈QRankt∣q−Rank′t∣q,where Rankt∣q and Rank′t∣q refer to the ranks of tuple t in the ranked result given query q before and after applying our frameworks, respectively.


## 3. Privacy-Preserving Framework

The only information an adversary can obtain from a database through the ranked retrieval model is public attribute values and ranked results. For an adversary without prior knowledge, information regarding private attribute values can only be retrieved from ranked results. Therefore, in order to preserve privacy, we have to modify the ranked retrieval model such that the adversary cannot retrieve any useful information about private attributes from ranked results.An idea is to group different tuples together in ranked results. As in our prior work [20], we can group two tuples v1 and v2 together such that they share the same rank in any ranked result. This can be achieved by adopting a new ranking function s′t∣q such that s′v1∣q=s′v2∣q for all q. If v1 and v2 have different values on every private attributes, then the adversary is unable to infer the private values of v1 since v1 and v2 are indistinguishable in any ranked results. However, this method suffers from high utility loss. In order to preserve the privacy of all private attributes, v1 and v2 have to be different over all private attributes. Thus, the original scores of v1 and v2, i.e., sv1∣q and sv2∣q, differ a lot, which leads to a higher variance between the rank of v1 before and after adopting this method.In this work, we present a novel framework that preserves privacy of private attributes while minimizes the utility loss. We observe that for a tuplev’s private attribute vBj if there are at least two potential values for vBj and an adversary cannot differentiate any one of them, then the privacy of vBj can be preserved. For instance, if the probability of vBj=a is equal to the probability of vBj=a′, given ranked results and prior knowledge, then the adversary cannot exclude any one of them. If both the probabilities are 50%, then the adversary may choose to randomly pick a value from a and a′ as the inferred result. In this case, gv,Bj will not exceed 50% and privacy of vBj can be preserved. To prove this statement, suppose that v is an arbitrary tuple in database D, and we want to preserve the privacy of vBj. Let βjB be an arbitrary value in VjB\vBj. We construct tuple v′ such that v′ and v differ in only one attribute Bj: v′Bj=βjB. We also construct database D′ such that D and D′ differ in only one tuple v∈D while v′∈D′. We define a new score function s′t∣q:(5)s′t∣q=∑i=1mwiAρqAi,tAi+∑j=1m′wiBρ′qBj,tBj,where(6)ρ′qBj,tBj=ρqBj,tBj,ift≠vandt≠v′,ρ′qBj,tBj=MaxρqBj,vBj,ρqBj,v′Bj,if t=vort=v′Imagine a case where an adversary queriesD and D′ with the same query workload QA. We denote the ranked results from D as RD and the ranked results from D′ as RD′. As in the new score function, s′v∣q=s′v′∣q for ∀q∈QA, RD is identical to RD′. Therefore, given only ranked results, the adversary cannot tell the difference between the two databases being queried. Furthermore, even if we exchange the values of v and v′, the adversary still cannot observe any change in RD or RD′. As a result, the value of vBj and βjB are equivalent from the perspective of the adversary, and the privacy of vBj can be well preserved. Intuitively, v can be seen as a tuple that has two polymorphic forms in Bj: vBj and βjB. When calculating the score of v with s′t∣q, we always choose the value that can maximize s′v∣q.We can further extend the statement to a more general case. For each tuplev∈D and each private attribute Bj, we can select e distinct values β1, β2, …, βe from VjB\vBj, e<VjB−1. The new score function can be defined as(7)s′t∣q=∑i=1mwiAρqAi,tAi+∑j=1m′wiBρ′qBj,tBj,where(8)ρ′qBj,tBj=ρqBj,tBj,ift≠v,ρ′qBj,tBj=MaxρqBj,tBj,ρqBj,β1,…,ρqBj,βe,ift=v.Considere tuples v1′,…,ve′ which are identical to v in all attributes except for Bj. Let vi′Bj be βi, ∀i=1,…,e. Then for ∀q, we have s′v∣q=s′vi′∣q. As a result, from the adversary’s perspective, there are e+1 potential values for vBj: vBj, β1,…,βe, which are indistinguishable from each other from any ranked results. The privacy of vBj can be preserved by grouping it with e equivalent values.As such, we introduce the construction of the polymorphic value set (PVS). We putvBj into a set in which all values are indistinguishable when calculating the score with respect to Bj in the ranking function, i.e., ρ′qBj,vBj. We name the above set as the polymorphic value set and denote the polymorphic value set of tuple v in attribute Bj as PvBj. We define PvBj as follows.Definition 2.
P
v
B
j is a set containing all indistinguishable values of tuple v’s private attribute Bj. Assigning vBj with an arbitrary value in PvBj will not change the value of s′v∣q∀q, i.e., ρ′qBj,vBj=ρ′qBj,β,∀β∈PvBj and ∀q.Since the adversary cannot distinguish different values inPvBj by launching any inference attacks based only on ranked results, the privacy guarantee of vBj is(9)ε=1PvBj.In order to achieve the privacy guarantee defined in (3), for each v∈D and each private attribute Bj, we have to ensure that (a) there is one and only one polymorphic value set PvBj for v’s attribute Bj and (b) the privacy guarantee defined in (9) is always valid.


## 4. Framework with Virtual Values

### 4.1. Design

In this section, we introduce how polymorphic value sets can be constructed with generated values to meet the privacy guarantee in (9) against authenticity-ignorant adversaries. We name values generated by our framework as virtual values.As we proved in Privacy-Preserving Framework, an authenticity-ignorant adversary cannot distinguish the value ofvBj from other valid values in PvBj, given ranked results. Since an adversary without prior knowledge cannot validate the authenticity of any value in PvBj, all values in PvBj are “valid” in the perspective of the adversary, no matter if they are generated by our framework or collected from real data in D. Therefore, we observe that PvBj can be formed by any values in VjB.In order to achieve the privacy guarantee ofε,, we have to ensure that PvBj>1/ε, ∀v∈D, and ∀j∈1,…,m′. An intuitive algorithm to generate PvBj of size 1/ε is to randomly pick 1/ε−1 values from VjB\vBj. Specifically, let the initial PvBj=vBj. Then, we can randomly pick distinct values from VjB\vBj and insert them into PvBj until PvBj contains at least 1/ε distinct values. In the same manner, we can construct a polymorphic value set for each tuple’s each private attribute.


#### 4.1.1. Privacy Guarantee

For a databaseD where every tuple v’s every private attribute Bj is included by one polymorphic value set with virtual values (PVSV) whose size is at least l, if the adversary has no prior knowledge of D, a privacy level of ε=1/l is achieved.For an authenticity-ignorant adversary,PKv∣D=1 ∀v. As proved in Privacy-Preserving Framework, for an authenticity-ignorant adversary, it is impossible to distinguish vBj with at least l−1 other values. Thus we have gv,Bj≤1/l for ∀v∈D and ∀j∈1,…,m′. According to equation (3), a privacy guarantee of 1/l can be achieved.


### 4.2. Utility Optimization

In this section, we discuss how to reduce utility loss caused by polymorphic value sets. We introduced a metric of utility loss in (4) that calculates the sum of difference in ranked results given all possible queries. To practically calculate utility loss, we limit the range of queries to a finite set named query workload. In practice, the query workload of a database D can be a set of queries that are more frequently issued than any other queries. A query workload may contain duplicate queries, which reflect the distribution of frequent queries. With a query workload, denoted as Q, we can define the practical utility loss as(10)UQ=∑q∈Q∑v∈DRankv∣q−Rank′v∣q.In order to reduce utility loss, we have to find assignments ofPvBj for ∀v∈D and ∀j∈1,…,m′ such that the overall UQ can be minimized. Without loss of generality, we only consider constructing polymorphic value sets of size 2. In this case, the privacy guarantee is 1/2. For each vBj, we need to find a value that is indistinguishable from vBj. We denote the polymorphic value of vBj as v′Bj.Definition 3.
We define the 2-PVSV problem as follows: given databaseD and query workload Q, find a polymorphic value v′Bj from VjB\vBj for each vBj, ∀v∈D and ∀j∈1,…,m′, such that UQ defined in (10) is minimized.Theorem 1.
The 2-PVSV problem is NP-hard.The proof of Theorem 1 in detail can be found in AppendixA.


### 4.3. Heuristic Algorithm

We have proved that the 2-PVSV problem is an NP-hard problem that may not be solved in polynomial time. Therefore, we propose PVSV-Constructor, a heuristic algorithm that can return an approximate solution in polynomial time.We observe thatsv∣q−s′v∣q is relevant to Rankv∣q−Rank′v∣q. A smaller difference between sv∣q and s′vq leads to a smaller difference between Rankv∣q and Rank′v∣q. Therefore, Rankv∣q−Rank′v∣q can be approximately minimized by a solution that minimizes sv∣q−s′v∣q. As such, we propose an approximation of UQ that calculates the score difference before and after adopting our framework. We denote the score difference as UQS and define UQS as follows:(11)UQS=∑q∈Q∑v∈Dsv∣q−s′v∣q.As shown in Algorithm1, given input database D, the number of public and private attributes m and m′ respectively, query workload Q and privacy guarantee ϵ, PVSV-Constructor constructs an equivalent value set for each v∈D and j∈1,…,m′ that minimizes UQS. Recall the definition of s′tq in (7), and we have(12)UQS=∑v∈D∑j=1m′∑q∈QwjBρ′qBj,vBj−ρqBj,vBj.Algorithm 1:PVSV-Constructor.
(i)
Input: ε, D, m, m′, Q
(ii)
Output: PvBj, ∀v∈D and ∀j∈1,…,m′
(1)
k
=
1
/
ε
−
1
(2)
for
t in Ddo
(3)
for j∈1,…,m′ do
(4)
PvBj  =  vBj
(5)
Set  =  VjB\vBj
(6)
Sort elements ofSet by their frequencies in qBjq∈Q in ascending order.
(7)
Remove the lastSet−k+1 elements in Set.
(8)
PvBj=PvBj∪Set
(9)
end
(10)
endWe denote the score difference ofvBj contributed by PvBj as UPvBj.(13)UPvBj=∑q∈QwjBρ′qBj,vBj−ρqBj,vBj.Therefore,UQS is the sum of UPvBj over all tuples and private attributes:(14)UQS=∑v∈D∑j=1m′UPvBj.Since the construction of eachPvBj is independent from other polymorphic value sets, we can minimize UQS by minimizing the score difference contributed by each PvBj for ∀j∈1,…,m′ and ∀v∈D. Note that ρ′qBj,vBj−ρqBj,vBj=0 if qBj=vBj or qBj∉PvBj. Also note that ρ′qBj,vBj−ρqBj,vBj=1 when qBj≠vBj and qBj∈PvBj. Therefore, if ∀q∈Q, vBj=qBj, then any assignment of PvBj cannot contribute to a higher UPvBj since ρ′qBj,vBj=1, ρqBj,vBj=1, and ρ′qBj,vBj−ρqBj,vBj is always zero. In this situation, UPvBj=0. On the contrary, if ∃q∈Q, vBj≠qBj, then ρqBj,vBj=0, and thus, ρ′qBj,vBj−ρqBj,vBj=ρ′qBj,vBj. According to equation (13), the value of UPvBj is(15)∑q∈QwjBρ′qBj,vBj−ρqBj,vBj=∑q∈Q,qBj≠vBjwjBρ′qBj,vBj.In order to minimizeUPvBj, we have to find an assignment of PvBj which minimizes q∈Q∣qBj≠vBj,∃β∈PvBj,qBj=β. Consider the simplest case where we want to construct PvBj of size 2: vBj,β. We have(16)∑q∈Q,qBj≠vBjwjBρ′qBj,vBj=wjBq∈Q∣qBj=β.In this case,β has to be a value in VjB\vBj such that β has the lowest frequency among all qBj values for q∈Q. Note that β does not have to be an element of qBj∣q∈Q. If β∉qBj∣q∈Q, its frequency is 0. Similarly, if we want to construct PvBj of size k, then we should insert the k−1 least frequent values among all qBj values into PvBj.In line 4 of Algorithm1, we initialize the polymorphic value set of vBj by inserting vBj into PvBj. For vBj, a set Set is constructed from VjB\vBj, which contains all values that can be inserted into PvBj. In order to minimize UPvBj, we insert the k−1 least frequent values from Set into PvBj by their frequencies in qBj∣q∈Q. The above construction of PvBj is repeated for each t∈D and j∈1,…,m′. The computational complexity of Algorithm 1 is OD⋅Q⋅m′.


## 4.1. Design

In this section, we introduce how polymorphic value sets can be constructed with generated values to meet the privacy guarantee in (9) against authenticity-ignorant adversaries. We name values generated by our framework as virtual values.As we proved in Privacy-Preserving Framework, an authenticity-ignorant adversary cannot distinguish the value ofvBj from other valid values in PvBj, given ranked results. Since an adversary without prior knowledge cannot validate the authenticity of any value in PvBj, all values in PvBj are “valid” in the perspective of the adversary, no matter if they are generated by our framework or collected from real data in D. Therefore, we observe that PvBj can be formed by any values in VjB.In order to achieve the privacy guarantee ofε,, we have to ensure that PvBj>1/ε, ∀v∈D, and ∀j∈1,…,m′. An intuitive algorithm to generate PvBj of size 1/ε is to randomly pick 1/ε−1 values from VjB\vBj. Specifically, let the initial PvBj=vBj. Then, we can randomly pick distinct values from VjB\vBj and insert them into PvBj until PvBj contains at least 1/ε distinct values. In the same manner, we can construct a polymorphic value set for each tuple’s each private attribute.


### 4.1.1. Privacy Guarantee

For a databaseD where every tuple v’s every private attribute Bj is included by one polymorphic value set with virtual values (PVSV) whose size is at least l, if the adversary has no prior knowledge of D, a privacy level of ε=1/l is achieved.For an authenticity-ignorant adversary,PKv∣D=1 ∀v. As proved in Privacy-Preserving Framework, for an authenticity-ignorant adversary, it is impossible to distinguish vBj with at least l−1 other values. Thus we have gv,Bj≤1/l for ∀v∈D and ∀j∈1,…,m′. According to equation (3), a privacy guarantee of 1/l can be achieved.


## 4.1.1. Privacy Guarantee

For a databaseD where every tuple v’s every private attribute Bj is included by one polymorphic value set with virtual values (PVSV) whose size is at least l, if the adversary has no prior knowledge of D, a privacy level of ε=1/l is achieved.For an authenticity-ignorant adversary,PKv∣D=1 ∀v. As proved in Privacy-Preserving Framework, for an authenticity-ignorant adversary, it is impossible to distinguish vBj with at least l−1 other values. Thus we have gv,Bj≤1/l for ∀v∈D and ∀j∈1,…,m′. According to equation (3), a privacy guarantee of 1/l can be achieved.


## 4.2. Utility Optimization

In this section, we discuss how to reduce utility loss caused by polymorphic value sets. We introduced a metric of utility loss in (4) that calculates the sum of difference in ranked results given all possible queries. To practically calculate utility loss, we limit the range of queries to a finite set named query workload. In practice, the query workload of a database D can be a set of queries that are more frequently issued than any other queries. A query workload may contain duplicate queries, which reflect the distribution of frequent queries. With a query workload, denoted as Q, we can define the practical utility loss as(10)UQ=∑q∈Q∑v∈DRankv∣q−Rank′v∣q.In order to reduce utility loss, we have to find assignments ofPvBj for ∀v∈D and ∀j∈1,…,m′ such that the overall UQ can be minimized. Without loss of generality, we only consider constructing polymorphic value sets of size 2. In this case, the privacy guarantee is 1/2. For each vBj, we need to find a value that is indistinguishable from vBj. We denote the polymorphic value of vBj as v′Bj.Definition 3.
We define the 2-PVSV problem as follows: given databaseD and query workload Q, find a polymorphic value v′Bj from VjB\vBj for each vBj, ∀v∈D and ∀j∈1,…,m′, such that UQ defined in (10) is minimized.Theorem 1.
The 2-PVSV problem is NP-hard.The proof of Theorem 1 in detail can be found in AppendixA.


## 4.3. Heuristic Algorithm

We have proved that the 2-PVSV problem is an NP-hard problem that may not be solved in polynomial time. Therefore, we propose PVSV-Constructor, a heuristic algorithm that can return an approximate solution in polynomial time.We observe thatsv∣q−s′v∣q is relevant to Rankv∣q−Rank′v∣q. A smaller difference between sv∣q and s′vq leads to a smaller difference between Rankv∣q and Rank′v∣q. Therefore, Rankv∣q−Rank′v∣q can be approximately minimized by a solution that minimizes sv∣q−s′v∣q. As such, we propose an approximation of UQ that calculates the score difference before and after adopting our framework. We denote the score difference as UQS and define UQS as follows:(11)UQS=∑q∈Q∑v∈Dsv∣q−s′v∣q.As shown in Algorithm1, given input database D, the number of public and private attributes m and m′ respectively, query workload Q and privacy guarantee ϵ, PVSV-Constructor constructs an equivalent value set for each v∈D and j∈1,…,m′ that minimizes UQS. Recall the definition of s′tq in (7), and we have(12)UQS=∑v∈D∑j=1m′∑q∈QwjBρ′qBj,vBj−ρqBj,vBj.Algorithm 1:PVSV-Constructor.
(i)
Input: ε, D, m, m′, Q
(ii)
Output: PvBj, ∀v∈D and ∀j∈1,…,m′
(1)
k
=
1
/
ε
−
1
(2)
for
t in Ddo
(3)
for j∈1,…,m′ do
(4)
PvBj  =  vBj
(5)
Set  =  VjB\vBj
(6)
Sort elements ofSet by their frequencies in qBjq∈Q in ascending order.
(7)
Remove the lastSet−k+1 elements in Set.
(8)
PvBj=PvBj∪Set
(9)
end
(10)
endWe denote the score difference ofvBj contributed by PvBj as UPvBj.(13)UPvBj=∑q∈QwjBρ′qBj,vBj−ρqBj,vBj.Therefore,UQS is the sum of UPvBj over all tuples and private attributes:(14)UQS=∑v∈D∑j=1m′UPvBj.Since the construction of eachPvBj is independent from other polymorphic value sets, we can minimize UQS by minimizing the score difference contributed by each PvBj for ∀j∈1,…,m′ and ∀v∈D. Note that ρ′qBj,vBj−ρqBj,vBj=0 if qBj=vBj or qBj∉PvBj. Also note that ρ′qBj,vBj−ρqBj,vBj=1 when qBj≠vBj and qBj∈PvBj. Therefore, if ∀q∈Q, vBj=qBj, then any assignment of PvBj cannot contribute to a higher UPvBj since ρ′qBj,vBj=1, ρqBj,vBj=1, and ρ′qBj,vBj−ρqBj,vBj is always zero. In this situation, UPvBj=0. On the contrary, if ∃q∈Q, vBj≠qBj, then ρqBj,vBj=0, and thus, ρ′qBj,vBj−ρqBj,vBj=ρ′qBj,vBj. According to equation (13), the value of UPvBj is(15)∑q∈QwjBρ′qBj,vBj−ρqBj,vBj=∑q∈Q,qBj≠vBjwjBρ′qBj,vBj.In order to minimizeUPvBj, we have to find an assignment of PvBj which minimizes q∈Q∣qBj≠vBj,∃β∈PvBj,qBj=β. Consider the simplest case where we want to construct PvBj of size 2: vBj,β. We have(16)∑q∈Q,qBj≠vBjwjBρ′qBj,vBj=wjBq∈Q∣qBj=β.In this case,β has to be a value in VjB\vBj such that β has the lowest frequency among all qBj values for q∈Q. Note that β does not have to be an element of qBj∣q∈Q. If β∉qBj∣q∈Q, its frequency is 0. Similarly, if we want to construct PvBj of size k, then we should insert the k−1 least frequent values among all qBj values into PvBj.In line 4 of Algorithm1, we initialize the polymorphic value set of vBj by inserting vBj into PvBj. For vBj, a set Set is constructed from VjB\vBj, which contains all values that can be inserted into PvBj. In order to minimize UPvBj, we insert the k−1 least frequent values from Set into PvBj by their frequencies in qBj∣q∈Q. The above construction of PvBj is repeated for each t∈D and j∈1,…,m′. The computational complexity of Algorithm 1 is OD⋅Q⋅m′.


## 5. Framework with True Values

### 5.1. Authenticity-Knowledgeable Adversaries

As we mentioned in the adversary model, an authenticity-knowledgeable adversary is able to tell ift∈D is possible. As a result, the authenticity-knowledgeable adversary can launch a more efficient attack on private attributes by examining the authenticity of values learned from RA. We show a simple case where an authenticity-knowledgeable adversary breaks the privacy guarantee provided by polymorphic values sets constructed with virtual values. Consider that the objective of the adversary is to infer the value of vB0 and B0 is the only private attribute in D. PvB0 is the polymorphic value set generated for vB0 and PvB0=1/ε. Without prior knowledge, PvB0=ε and the privacy guarantee is achieved. However, for a value β∈PvB0\vB0, if the adversary can conclude that PKv′∣D=0 for any tuple v′ such that v′ is equal to v in all public attributes and v′B0=β, then the adversary can exclude β from PvB0. Therefore,(17)gvB0=ε1−ε>ε,and equation (9) no longer holds.As shown above, if values inPvB0 are marked by an adversary as invalid for v given PKv′D, then the adversary can successfully break the privacy guarantee defined in framework with virtual values.


### 5.2. Design

In this section, we propose polymorphic value sets with true values (PVST) that construct polymorphic value sets with values that cannot be excluded byPKt∣D. PVST considers nontrivial prior knowledge of adversaries and presents the same degree of privacy guarantee introduced in (9).We have shown above that the implementation with virtual values can be compromised by adversaries with prior knowledge. Consider a tuplev∈D. Given privacy guarantee ϵ, we construct m′ polymorphic values sets PvB0,…,PvBm′ for each private attributes of v where PvBj≥1/ε. Let set MvA be(18)MvA=vA0×⋯×vAm×PvB0×⋯×PvBm′.M
v
A is the Cartesian product of sets each of which contains v’s all equivalent values in an attribute. For public attribute Ai, the corresponding set is vAi since public attribute values are open to the adversary. For private attribute Bj, the corresponding set is PvBj. Therefore, MvA contains all possible tuples that are indistinguishable with v with respect to RA (including v itself).With prior knowledge onPKt∣D, an adversary is able to exclude a value β from PvBj if(19)∀t∈t∣t∈MvA,tBj=β,PKt∣D=0.As described above, it is safe for the adversary to conclude thatβ≠vBj, if there is no t∈MvA such that tBj=β and PKt∣D=1. Alternatively, if for every β in PvBj, there is a t such that tBj=β and PKt∣D=1, then the adversary cannot exclude any value in PvBj, and therefore, PvBj≤ε is guaranteed. Since PKt∣D=1 iff t∈D, we construct polymorphic value sets with true values from t∈D.Definition 4.
If there existsl distinct values β1,…,βl∈PvBj such that ∀r∈1,…,l, βr holds the following property:(20)∃t∈MvA,tBj=βrandt∈D.
Then, we say thatPvBj covers l true values. We denote TvBj=β1,…,βl as the true value set of t in Bj.
Privacy guarantee: for a databaseD where every tuple’s every private attribute is included by one equivalent value set which covers at least l true values, a privacy level of ε=1/l is achieved.
Assume that the adversary’s objective is to infer the value ofvBj. As mentioned in the adversary model, we make no assumption on the attacking methods adopted by an adversary. Consider MvA defined in (18), ∀t, t′∈MvA and ∀q∈QA, st∣q=st′∣q. Therefore, the adversary cannot distinguish tuples in MvA by observing RA. In this situation, the adversary would use PKt∣D to exclude all tuple t in MvA such that PKt∣D=0. However, as PvBj covers l true values, there exists l tuples t1,…,tl∈MvA such that PKt∣D=1 and trBj≠tsBj for arbitrary r,s∈1,…,l. As a result, values in t1Bj,…,tlBj are indistinguishable given RA and PKt∣D. Thus, PvBj=1/l. According to (3), a privacy level of 1/l is achieved.


### 5.3. Utility Optimization

An intuitive method of constructingPvBj is to insert the value of Bj of all tuples that share the same public attribute values with v into PvBj, i.e., PvBj= PvBj=v′Bj∀iandv′∈D,v′Ai=vAi. The privacy guarantee is met if PvBj covers at least 1/ε true values. Nevertheless, utility loss cannot be ignored as in the intuitive method, sv′q would be the same for all v′∈v′∀iandv′∈D,v′Ai=vAi, and thus information of private attributes are missing in the ranked result of v′. Therefore, the size of PvBj is critical in balancing privacy and utility. With no loss of generality, we limit the size of each polymorphic value set to 2. We show that constructing such polymorphic value sets is an NP-hard problem.Definition 5.
We define the 2-PVST problem as follows: given databaseD and a query workload Q, construct PvBj of size 2 for each tuple v∈D, ∀j∈1,…,m′, and minimize UQ defined in (10).Theorem 2.
The 2-PVST problem is NP-hard.The proof of Theorem 2 can be found in AppendixB.


### 5.4. Heuristic Algorithm

We have shown that the 2-PVST problem is NP-hard. In this subsection, we present PVST-Constructor, a heuristic algorithm that constructs PVST within polynomial time. PVST-Constructor tries to minimizePvBj and ∑q∈Qs′v∣q−sv∣q for each v∈D and j∈1,…,m′ with the greedy algorithm.The pseudo-code of PVST-Constructor is shown in Algorithm2. In lines 2 to 6, we initialize each PvBj with vBj. Then, for each v∈D, PVST-Constructor constructs PvB1,…,PvBm′ by finding a v′ with the greedy algorithm and inserting v′Bj into PvBj, ∀j∈1,…,m′. The above process will be taken multiple times until PvBj≥1/ε. Since every v′ is a real tuple existing in D and we insert at least k tuples in the above processes, PvBj covers at least k+1 true values, and thus, the privacy guarantee is met. As mentioned in Utility Optimization, the size of PvBj is critical in minimizing utility loss. Therefore, the heuristic algorithm tries to minimize the utility loss by minimizing the size of each PvBj. We count the number of polymorphic value sets of v, if the set contains less than k values, that can be enlarged by inserting v′’s private attribute values. We denote this count as coverv′:(21)coverv′=j∣PvBj<k,v′Bj∉PvBj.Algorithm 2:PVST-Constructor.
(i)
Input: ɛ, D, m, m′, Q
(ii)
Output: PvBj, ∀v and ∀Bj
(1)
k
=
1
/
ε
−
1
(2)
for v in Ddo
(3)
for j∈1,…,m′ do
(4)
PvBj=vBj
(5)
end
(6)
end
(7)
for v in Ddo
(8)
while ∃j∈1,…,m′,PvBj<k+1 do
(9)
for v′∈t∈D∀Ai,tAi=vAi do
(10)
computecoverv′, lossv′
(11)
scorev′=coverv′=1/1+exp−lossv′  =
(12)
end
(13)
vmax=argmaxv′∈t∈D∀Ai,tAi=vAiscorev′
(14)
for j∈1,…,m′ do
(15)
PvBj=PvBj∪tmaxBj
(16)
end
(17)
end
(18)
endTuplev′ with a higher coverv′ value can enlarge the size of more polymorphic value sets of v, and thus, we can reduce the number of tuples that we have to insert into PvB1,…,PvBm′.Furthermore, we take into consideration queries inQ. In order to minimize UQ, we have to minimize s′v∣q−sv∣q for q∈Q. Note that for each attribute Bj, ρ′qBj,vBj−ρqBj,vBj=1 if vBj≠qBj and qBj∈PvBj. We denote the value of ∑jρ′qBj,vBj−ρqBj,vBj as lossv′. Thus, we have(22)lossv′=∑q∈Q∑j=1,…,m′ρ′qBj,vBj−ρqBj,vBj=∑q∈Q∑j=1,…,m′δv,v′,q,j,where δv,v′,q,j=1 if vBj≠qBj and v′Bj=qBj and δv,v′,q,j=0 otherwise. Therefore, tuple v′ with a smaller lossv′ can reduce the value of ∑jρ′qBj,vBj−ρqBj,vBj, and thus, we can reduce the value of UQ.The computation ofcoverv′ and lossv′ is done in line 11. Then, we compute scorev′, the score of v′ that indicates how preferable v′ is, relative to other tuples in D\v. We adopt the greedy algorithm to find the next v′ for PvB1,…,PvBm′, i.e., in each iteration, we choose the tuple that has the highest score value. In line 15, we insert the private attribute values of the chosen tuple (denoted as vmax) into PvB1,…,PvBm′. The above process is repeated until the sizes of PvB1,…,PvBm′ are no less than k.


## 5.1. Authenticity-Knowledgeable Adversaries

As we mentioned in the adversary model, an authenticity-knowledgeable adversary is able to tell ift∈D is possible. As a result, the authenticity-knowledgeable adversary can launch a more efficient attack on private attributes by examining the authenticity of values learned from RA. We show a simple case where an authenticity-knowledgeable adversary breaks the privacy guarantee provided by polymorphic values sets constructed with virtual values. Consider that the objective of the adversary is to infer the value of vB0 and B0 is the only private attribute in D. PvB0 is the polymorphic value set generated for vB0 and PvB0=1/ε. Without prior knowledge, PvB0=ε and the privacy guarantee is achieved. However, for a value β∈PvB0\vB0, if the adversary can conclude that PKv′∣D=0 for any tuple v′ such that v′ is equal to v in all public attributes and v′B0=β, then the adversary can exclude β from PvB0. Therefore,(17)gvB0=ε1−ε>ε,and equation (9) no longer holds.As shown above, if values inPvB0 are marked by an adversary as invalid for v given PKv′D, then the adversary can successfully break the privacy guarantee defined in framework with virtual values.


## 5.2. Design

In this section, we propose polymorphic value sets with true values (PVST) that construct polymorphic value sets with values that cannot be excluded byPKt∣D. PVST considers nontrivial prior knowledge of adversaries and presents the same degree of privacy guarantee introduced in (9).We have shown above that the implementation with virtual values can be compromised by adversaries with prior knowledge. Consider a tuplev∈D. Given privacy guarantee ϵ, we construct m′ polymorphic values sets PvB0,…,PvBm′ for each private attributes of v where PvBj≥1/ε. Let set MvA be(18)MvA=vA0×⋯×vAm×PvB0×⋯×PvBm′.M
v
A is the Cartesian product of sets each of which contains v’s all equivalent values in an attribute. For public attribute Ai, the corresponding set is vAi since public attribute values are open to the adversary. For private attribute Bj, the corresponding set is PvBj. Therefore, MvA contains all possible tuples that are indistinguishable with v with respect to RA (including v itself).With prior knowledge onPKt∣D, an adversary is able to exclude a value β from PvBj if(19)∀t∈t∣t∈MvA,tBj=β,PKt∣D=0.As described above, it is safe for the adversary to conclude thatβ≠vBj, if there is no t∈MvA such that tBj=β and PKt∣D=1. Alternatively, if for every β in PvBj, there is a t such that tBj=β and PKt∣D=1, then the adversary cannot exclude any value in PvBj, and therefore, PvBj≤ε is guaranteed. Since PKt∣D=1 iff t∈D, we construct polymorphic value sets with true values from t∈D.Definition 4.
If there existsl distinct values β1,…,βl∈PvBj such that ∀r∈1,…,l, βr holds the following property:(20)∃t∈MvA,tBj=βrandt∈D.
Then, we say thatPvBj covers l true values. We denote TvBj=β1,…,βl as the true value set of t in Bj.
Privacy guarantee: for a databaseD where every tuple’s every private attribute is included by one equivalent value set which covers at least l true values, a privacy level of ε=1/l is achieved.
Assume that the adversary’s objective is to infer the value ofvBj. As mentioned in the adversary model, we make no assumption on the attacking methods adopted by an adversary. Consider MvA defined in (18), ∀t, t′∈MvA and ∀q∈QA, st∣q=st′∣q. Therefore, the adversary cannot distinguish tuples in MvA by observing RA. In this situation, the adversary would use PKt∣D to exclude all tuple t in MvA such that PKt∣D=0. However, as PvBj covers l true values, there exists l tuples t1,…,tl∈MvA such that PKt∣D=1 and trBj≠tsBj for arbitrary r,s∈1,…,l. As a result, values in t1Bj,…,tlBj are indistinguishable given RA and PKt∣D. Thus, PvBj=1/l. According to (3), a privacy level of 1/l is achieved.


## 5.3. Utility Optimization

An intuitive method of constructingPvBj is to insert the value of Bj of all tuples that share the same public attribute values with v into PvBj, i.e., PvBj= PvBj=v′Bj∀iandv′∈D,v′Ai=vAi. The privacy guarantee is met if PvBj covers at least 1/ε true values. Nevertheless, utility loss cannot be ignored as in the intuitive method, sv′q would be the same for all v′∈v′∀iandv′∈D,v′Ai=vAi, and thus information of private attributes are missing in the ranked result of v′. Therefore, the size of PvBj is critical in balancing privacy and utility. With no loss of generality, we limit the size of each polymorphic value set to 2. We show that constructing such polymorphic value sets is an NP-hard problem.Definition 5.
We define the 2-PVST problem as follows: given databaseD and a query workload Q, construct PvBj of size 2 for each tuple v∈D, ∀j∈1,…,m′, and minimize UQ defined in (10).Theorem 2.
The 2-PVST problem is NP-hard.The proof of Theorem 2 can be found in AppendixB.


## 5.4. Heuristic Algorithm

We have shown that the 2-PVST problem is NP-hard. In this subsection, we present PVST-Constructor, a heuristic algorithm that constructs PVST within polynomial time. PVST-Constructor tries to minimizePvBj and ∑q∈Qs′v∣q−sv∣q for each v∈D and j∈1,…,m′ with the greedy algorithm.The pseudo-code of PVST-Constructor is shown in Algorithm2. In lines 2 to 6, we initialize each PvBj with vBj. Then, for each v∈D, PVST-Constructor constructs PvB1,…,PvBm′ by finding a v′ with the greedy algorithm and inserting v′Bj into PvBj, ∀j∈1,…,m′. The above process will be taken multiple times until PvBj≥1/ε. Since every v′ is a real tuple existing in D and we insert at least k tuples in the above processes, PvBj covers at least k+1 true values, and thus, the privacy guarantee is met. As mentioned in Utility Optimization, the size of PvBj is critical in minimizing utility loss. Therefore, the heuristic algorithm tries to minimize the utility loss by minimizing the size of each PvBj. We count the number of polymorphic value sets of v, if the set contains less than k values, that can be enlarged by inserting v′’s private attribute values. We denote this count as coverv′:(21)coverv′=j∣PvBj<k,v′Bj∉PvBj.Algorithm 2:PVST-Constructor.
(i)
Input: ɛ, D, m, m′, Q
(ii)
Output: PvBj, ∀v and ∀Bj
(1)
k
=
1
/
ε
−
1
(2)
for v in Ddo
(3)
for j∈1,…,m′ do
(4)
PvBj=vBj
(5)
end
(6)
end
(7)
for v in Ddo
(8)
while ∃j∈1,…,m′,PvBj<k+1 do
(9)
for v′∈t∈D∀Ai,tAi=vAi do
(10)
computecoverv′, lossv′
(11)
scorev′=coverv′=1/1+exp−lossv′  =
(12)
end
(13)
vmax=argmaxv′∈t∈D∀Ai,tAi=vAiscorev′
(14)
for j∈1,…,m′ do
(15)
PvBj=PvBj∪tmaxBj
(16)
end
(17)
end
(18)
endTuplev′ with a higher coverv′ value can enlarge the size of more polymorphic value sets of v, and thus, we can reduce the number of tuples that we have to insert into PvB1,…,PvBm′.Furthermore, we take into consideration queries inQ. In order to minimize UQ, we have to minimize s′v∣q−sv∣q for q∈Q. Note that for each attribute Bj, ρ′qBj,vBj−ρqBj,vBj=1 if vBj≠qBj and qBj∈PvBj. We denote the value of ∑jρ′qBj,vBj−ρqBj,vBj as lossv′. Thus, we have(22)lossv′=∑q∈Q∑j=1,…,m′ρ′qBj,vBj−ρqBj,vBj=∑q∈Q∑j=1,…,m′δv,v′,q,j,where δv,v′,q,j=1 if vBj≠qBj and v′Bj=qBj and δv,v′,q,j=0 otherwise. Therefore, tuple v′ with a smaller lossv′ can reduce the value of ∑jρ′qBj,vBj−ρqBj,vBj, and thus, we can reduce the value of UQ.The computation ofcoverv′ and lossv′ is done in line 11. Then, we compute scorev′, the score of v′ that indicates how preferable v′ is, relative to other tuples in D\v. We adopt the greedy algorithm to find the next v′ for PvB1,…,PvBm′, i.e., in each iteration, we choose the tuple that has the highest score value. In line 15, we insert the private attribute values of the chosen tuple (denoted as vmax) into PvB1,…,PvBm′. The above process is repeated until the sizes of PvB1,…,PvBm′ are no less than k.


## 6. Experimental Results

### 6.1. Experimental Setup

To validate PVSV-Constructor and PVST-Constructor algorithms, we conducted experiments on a real world dataset [29] from eHarmony which contains 58 attributes and 486,464 tuples. We removed 5 noncategorical attributes and randomly picked 20 categorical attributes from the remaining 53 attributes. The domain sizes of the 20 attributes range from 2 to 15. After removing duplicate tuples, we randomly picked 300,000 tuples as our testing bed.By default, we use the ranking function from the ranked retrieval model with all weights set to 1. All experimental results were obtained on a Mac machine running Mac OS with 8 GB of RAM. The algorithms were implemented inPython.


### 6.2. Privacy

The privacy guarantee of PVSV-Constructor and PVST-Constructor were tested by performing Ranked Inference attack [35], including Point-Query, In-Query, Point-Query&Insert, and In-Query&Insert attacking methods, on the dataset. From a total of 20 attributes, 5 attributes were randomly chosen as public attributes and another 5 attributes were randomly chosen as private attributes. We randomly picked 20,000 distinct tuples from the dataset as the testing bed and randomly generated 10 tuples as the query workload. For PVSV-Constructor, we constructed a polymorphic value set of size 2 for each private attribute and each tuple in the testing bed. For PVST-Constructor, we constructed a polymorphic value set that covers at least two true values for each private attribute and each tuple. We randomly picked 1,000 tuples from the testing bed as our targets and performed 1,000 Rank Inference attacks (250 attacks for each of the four methods) on the five private attributes of target tuples. We measured the attack success guess rates based on the frequency of successful inference among all inference attempts. Figure 1 shows the success guess rates of Rank Inference attacks on the unprotected testing bed, the testing bed with PVSV, and the testing bed with PVST. As the size of each polymorphic value set is 2, the success guess rates on PVSV are around 50%, which are significantly lower than those of unprotected dataset. We also observe that the success guess rates on PVST are slightly lower than those of PVSV. The reason is that PVSV-Constructor will be inserting values into tuple v’s polymorphic value sets until all v’s polymorphic value sets cover at least 2 true values. Thus, some polymorphic value sets of v may contain more than 2 values.Figure 1
Attack success guess.


### 6.3. Utility

In this subsection, we quantify utility loss of PVSV-Constructor and PVST-Constructor algorithms. The privacy guarantee of both PVSV-Constructor and PVST-Constructor is1/2, i.e., the polymorphic value sets constructed by PVSV-Constructor contains 2 values, and the polymorphic value sets constructed by PVST-Constructor contains at least 2 true values. The key parameters here are the size of query workload Q, the size of database D, the number of public and private attributes, and the weight ratios in the ranking function. We randomly generated 20 tuples as the query workload. By default, we picked 10 tuples from Q and set D=300,000, m=10, and m′=10. Therefore, we randomly picked 10 attributes from the testing bed and set them as public attributes. The rest of the 10 attributes were set as private attributes.Many recommendation systems of ONS applications feature top-k recommendation [1, 14, 47] where the ranked result contains a set of k tuples that will be of interest to a certain user, as it is impractical and unnecessary to return all tuples in the database to the user. Therefore, we introduce average top-k utility loss Uaul, a variant of UQ that focuses on utility loss of the top-k tuples in a ranked result. Uaul is defined as(23)Uaul=1Q∑i=1Q1D′∑v∈D′minRankv∣q,k+1−minRank′v∣q,k+1k,where D′=v∈DRankvq<kor  Rankvq<k. Intuitively, Uaul represents the average percentage rank difference relative to k over all queries and all tuples in top-k. Uaul is equivalent to UQ/QD2 when k=D. By default, we set k=100.


#### 6.3.1. Evaluation ofUaul with Varying k

We first discuss the average top-k utility loss of PVSV-Constructor, PVST-Constructor, and a baseline algorithm on varying k with other parameters set to default values. For a tuple v’s attribute Bj, the baseline algorithm constructs PvBj with vBj and a value randomly picked from VjB\vBj. The results are presented in Figure 2, which shows that the Uaul of PVSV-Constructor is significantly lower than that of the baseline algorithm. The Uaul of PVST-Constructor is also lower than that of the baseline algorithm when k≥5, even though the baseline algorithm cannot preserve privacy against authenticity-knowledgeable adversaries. The experimental results show that both PVSV and PVST can reduce utility loss with respect to rank differences. Also, note that PVST-Constructor constructs polymorphic value sets with true values, and thus, from Figure 3, we can see that some polymorphic value sets constructed by PVST-Constructor contains more than 2 values.Figure 2
Utility loss vs.k.Figure 3
Size of polymorphic value set (PVST).


#### 6.3.2. Evaluation ofUaul with Varying Sizes of Q

Figure4 presents the average top-k utility loss of PVSV-Constructor on varying Q. When Q is set to 1, 5, or 10, we randomly picked 1, 5, or 10 queries from the original Q, respectively. With increasing number of queries in the query workload, the Uaul of PVSV-Constructor increases monotonically. The reason is that PVSV-Constructor always generates the least frequent value (denoted as v′Bj) in qBjq∈Q for vBj. If Q is small, then it is possible that v′Bj∉qBjq∈Q, and thus, sv∣q=s′v∣q ∀q∈Q. However, a larger query workload covers more private attributes values, and thus, it will be harder for PVSV-Constructor to generate a value for vBj that has no impact on the rank of v for any q∈Q. Figure 5 presents the average top-k utility loss of PVST-Constructor on varying Q. We can see that the size of Q has no significant impact on the Uaul of PVST-Constructor, as the PVST-Constructor always pick a tuple v′ that is different from v in most attributes and then insert v′Bj into PvBj.Figure 4
Utility loss vs.Q.Figure 5
Utility loss vs.Q.


#### 6.3.3. Evaluation ofUaul with Varying Sizes of the Dataset

Figures6 and 7 depict the impact of the size of datasets on Uaul of PVSV-Constructor and PVST-Constructor. Datasets of 100,000 and 200,000 tuples were randomly sampled from the testing bed of 300,000 tuples. As expected, D has no significant impact on the Uaul of PVSV-Constructor since PVSV-Constructor generates values from the domain of each private attributes. D has no impact on the Uaul of PVST-Constructor, which indicates that a dataset containing 100,000 tuples is sufficient for PVST-Constructor to generate polymorphic value sets with true values.Figure 6
Utility loss vs.D.Figure 7
Utility loss vs.D


#### 6.3.4. Evaluation ofUaul with Varying m

We investigate the impact of the number of private and public attributes on average top-k utility loss. Figure 8 presents the Uaul of PVSV-Constructor with fixed m′ and varying m and with fixed m and varying m′. When m/m′ is set to 5, we randomly removed 5 attributes from the testing bed. When m/m′ is set to 15, we added 5 more categorical attributes randomly chosen from the unused attributes. We observe that the Uaul monotonically decreases with increasing number of public attributes and monotonically increases with increasing number of private attributes. As expected, a higher proportion of public attributes leads to less variant between sv∣q and s′v∣q. The results of the same experiment with PVST-Constructor are shown in Figure 9. Uaul increases as increasing number of private attributes as expected. However, Uaul also increases slightly with increasing number of public attributes. This is due to the fact that with more public attributes, there will be few tuples that share the same public attribute values. Since PVST-Constructor inserts only private attribute values from tuples sharing same public attribute values, more values will be inserted to each polymorphic value set, which introduces higher utility loss.Figure 8
Utility loss vs.m and m′.Figure 9
Utility loss vs.m and m′.


#### 6.3.5. Evaluation ofUaul with Varying Weight Ratios

Figures10 and 11 illustrate the impact of weight ratios on the average utility loss. The experiment was conducted with a fixed private attribute weight of 1 and varying public attribute weights of 1, 2, and 3. As expected, Uaul of both PVSV-Constructor and PVST-Constructor decreases as increasing weight ratio of public attributes. The reason is that as the public attribute weight increases, the part in s′v∣q caused by private attributes decreases. Therefore, less impact would be made to s′v∣q by PVSV and PVST. As a result, s′v∣q would be closer to sv∣q and the utility loss could be decreased.Figure 10
Utility loss vs. weight ratio.Figure 11
Utility loss vs. weight ratio.


## 6.1. Experimental Setup

To validate PVSV-Constructor and PVST-Constructor algorithms, we conducted experiments on a real world dataset [29] from eHarmony which contains 58 attributes and 486,464 tuples. We removed 5 noncategorical attributes and randomly picked 20 categorical attributes from the remaining 53 attributes. The domain sizes of the 20 attributes range from 2 to 15. After removing duplicate tuples, we randomly picked 300,000 tuples as our testing bed.By default, we use the ranking function from the ranked retrieval model with all weights set to 1. All experimental results were obtained on a Mac machine running Mac OS with 8 GB of RAM. The algorithms were implemented inPython.


## 6.2. Privacy

The privacy guarantee of PVSV-Constructor and PVST-Constructor were tested by performing Ranked Inference attack [35], including Point-Query, In-Query, Point-Query&Insert, and In-Query&Insert attacking methods, on the dataset. From a total of 20 attributes, 5 attributes were randomly chosen as public attributes and another 5 attributes were randomly chosen as private attributes. We randomly picked 20,000 distinct tuples from the dataset as the testing bed and randomly generated 10 tuples as the query workload. For PVSV-Constructor, we constructed a polymorphic value set of size 2 for each private attribute and each tuple in the testing bed. For PVST-Constructor, we constructed a polymorphic value set that covers at least two true values for each private attribute and each tuple. We randomly picked 1,000 tuples from the testing bed as our targets and performed 1,000 Rank Inference attacks (250 attacks for each of the four methods) on the five private attributes of target tuples. We measured the attack success guess rates based on the frequency of successful inference among all inference attempts. Figure 1 shows the success guess rates of Rank Inference attacks on the unprotected testing bed, the testing bed with PVSV, and the testing bed with PVST. As the size of each polymorphic value set is 2, the success guess rates on PVSV are around 50%, which are significantly lower than those of unprotected dataset. We also observe that the success guess rates on PVST are slightly lower than those of PVSV. The reason is that PVSV-Constructor will be inserting values into tuple v’s polymorphic value sets until all v’s polymorphic value sets cover at least 2 true values. Thus, some polymorphic value sets of v may contain more than 2 values.Figure 1
Attack success guess.


## 6.3. Utility

In this subsection, we quantify utility loss of PVSV-Constructor and PVST-Constructor algorithms. The privacy guarantee of both PVSV-Constructor and PVST-Constructor is1/2, i.e., the polymorphic value sets constructed by PVSV-Constructor contains 2 values, and the polymorphic value sets constructed by PVST-Constructor contains at least 2 true values. The key parameters here are the size of query workload Q, the size of database D, the number of public and private attributes, and the weight ratios in the ranking function. We randomly generated 20 tuples as the query workload. By default, we picked 10 tuples from Q and set D=300,000, m=10, and m′=10. Therefore, we randomly picked 10 attributes from the testing bed and set them as public attributes. The rest of the 10 attributes were set as private attributes.Many recommendation systems of ONS applications feature top-k recommendation [1, 14, 47] where the ranked result contains a set of k tuples that will be of interest to a certain user, as it is impractical and unnecessary to return all tuples in the database to the user. Therefore, we introduce average top-k utility loss Uaul, a variant of UQ that focuses on utility loss of the top-k tuples in a ranked result. Uaul is defined as(23)Uaul=1Q∑i=1Q1D′∑v∈D′minRankv∣q,k+1−minRank′v∣q,k+1k,where D′=v∈DRankvq<kor  Rankvq<k. Intuitively, Uaul represents the average percentage rank difference relative to k over all queries and all tuples in top-k. Uaul is equivalent to UQ/QD2 when k=D. By default, we set k=100.


### 6.3.1. Evaluation ofUaul with Varying k

We first discuss the average top-k utility loss of PVSV-Constructor, PVST-Constructor, and a baseline algorithm on varying k with other parameters set to default values. For a tuple v’s attribute Bj, the baseline algorithm constructs PvBj with vBj and a value randomly picked from VjB\vBj. The results are presented in Figure 2, which shows that the Uaul of PVSV-Constructor is significantly lower than that of the baseline algorithm. The Uaul of PVST-Constructor is also lower than that of the baseline algorithm when k≥5, even though the baseline algorithm cannot preserve privacy against authenticity-knowledgeable adversaries. The experimental results show that both PVSV and PVST can reduce utility loss with respect to rank differences. Also, note that PVST-Constructor constructs polymorphic value sets with true values, and thus, from Figure 3, we can see that some polymorphic value sets constructed by PVST-Constructor contains more than 2 values.Figure 2
Utility loss vs.k.Figure 3
Size of polymorphic value set (PVST).


### 6.3.2. Evaluation ofUaul with Varying Sizes of Q

Figure4 presents the average top-k utility loss of PVSV-Constructor on varying Q. When Q is set to 1, 5, or 10, we randomly picked 1, 5, or 10 queries from the original Q, respectively. With increasing number of queries in the query workload, the Uaul of PVSV-Constructor increases monotonically. The reason is that PVSV-Constructor always generates the least frequent value (denoted as v′Bj) in qBjq∈Q for vBj. If Q is small, then it is possible that v′Bj∉qBjq∈Q, and thus, sv∣q=s′v∣q ∀q∈Q. However, a larger query workload covers more private attributes values, and thus, it will be harder for PVSV-Constructor to generate a value for vBj that has no impact on the rank of v for any q∈Q. Figure 5 presents the average top-k utility loss of PVST-Constructor on varying Q. We can see that the size of Q has no significant impact on the Uaul of PVST-Constructor, as the PVST-Constructor always pick a tuple v′ that is different from v in most attributes and then insert v′Bj into PvBj.Figure 4
Utility loss vs.Q.Figure 5
Utility loss vs.Q.


### 6.3.3. Evaluation ofUaul with Varying Sizes of the Dataset

Figures6 and 7 depict the impact of the size of datasets on Uaul of PVSV-Constructor and PVST-Constructor. Datasets of 100,000 and 200,000 tuples were randomly sampled from the testing bed of 300,000 tuples. As expected, D has no significant impact on the Uaul of PVSV-Constructor since PVSV-Constructor generates values from the domain of each private attributes. D has no impact on the Uaul of PVST-Constructor, which indicates that a dataset containing 100,000 tuples is sufficient for PVST-Constructor to generate polymorphic value sets with true values.Figure 6
Utility loss vs.D.Figure 7
Utility loss vs.D


### 6.3.4. Evaluation ofUaul with Varying m

We investigate the impact of the number of private and public attributes on average top-k utility loss. Figure 8 presents the Uaul of PVSV-Constructor with fixed m′ and varying m and with fixed m and varying m′. When m/m′ is set to 5, we randomly removed 5 attributes from the testing bed. When m/m′ is set to 15, we added 5 more categorical attributes randomly chosen from the unused attributes. We observe that the Uaul monotonically decreases with increasing number of public attributes and monotonically increases with increasing number of private attributes. As expected, a higher proportion of public attributes leads to less variant between sv∣q and s′v∣q. The results of the same experiment with PVST-Constructor are shown in Figure 9. Uaul increases as increasing number of private attributes as expected. However, Uaul also increases slightly with increasing number of public attributes. This is due to the fact that with more public attributes, there will be few tuples that share the same public attribute values. Since PVST-Constructor inserts only private attribute values from tuples sharing same public attribute values, more values will be inserted to each polymorphic value set, which introduces higher utility loss.Figure 8
Utility loss vs.m and m′.Figure 9
Utility loss vs.m and m′.


### 6.3.5. Evaluation ofUaul with Varying Weight Ratios

Figures10 and 11 illustrate the impact of weight ratios on the average utility loss. The experiment was conducted with a fixed private attribute weight of 1 and varying public attribute weights of 1, 2, and 3. As expected, Uaul of both PVSV-Constructor and PVST-Constructor decreases as increasing weight ratio of public attributes. The reason is that as the public attribute weight increases, the part in s′v∣q caused by private attributes decreases. Therefore, less impact would be made to s′v∣q by PVSV and PVST. As a result, s′v∣q would be closer to sv∣q and the utility loss could be decreased.Figure 10
Utility loss vs. weight ratio.Figure 11
Utility loss vs. weight ratio.


## 6.3.1. Evaluation ofUaul with Varying k

We first discuss the average top-k utility loss of PVSV-Constructor, PVST-Constructor, and a baseline algorithm on varying k with other parameters set to default values. For a tuple v’s attribute Bj, the baseline algorithm constructs PvBj with vBj and a value randomly picked from VjB\vBj. The results are presented in Figure 2, which shows that the Uaul of PVSV-Constructor is significantly lower than that of the baseline algorithm. The Uaul of PVST-Constructor is also lower than that of the baseline algorithm when k≥5, even though the baseline algorithm cannot preserve privacy against authenticity-knowledgeable adversaries. The experimental results show that both PVSV and PVST can reduce utility loss with respect to rank differences. Also, note that PVST-Constructor constructs polymorphic value sets with true values, and thus, from Figure 3, we can see that some polymorphic value sets constructed by PVST-Constructor contains more than 2 values.Figure 2
Utility loss vs.k.Figure 3
Size of polymorphic value set (PVST).


## 6.3.2. Evaluation ofUaul with Varying Sizes of Q

Figure4 presents the average top-k utility loss of PVSV-Constructor on varying Q. When Q is set to 1, 5, or 10, we randomly picked 1, 5, or 10 queries from the original Q, respectively. With increasing number of queries in the query workload, the Uaul of PVSV-Constructor increases monotonically. The reason is that PVSV-Constructor always generates the least frequent value (denoted as v′Bj) in qBjq∈Q for vBj. If Q is small, then it is possible that v′Bj∉qBjq∈Q, and thus, sv∣q=s′v∣q ∀q∈Q. However, a larger query workload covers more private attributes values, and thus, it will be harder for PVSV-Constructor to generate a value for vBj that has no impact on the rank of v for any q∈Q. Figure 5 presents the average top-k utility loss of PVST-Constructor on varying Q. We can see that the size of Q has no significant impact on the Uaul of PVST-Constructor, as the PVST-Constructor always pick a tuple v′ that is different from v in most attributes and then insert v′Bj into PvBj.Figure 4
Utility loss vs.Q.Figure 5
Utility loss vs.Q.


## 6.3.3. Evaluation ofUaul with Varying Sizes of the Dataset

Figures6 and 7 depict the impact of the size of datasets on Uaul of PVSV-Constructor and PVST-Constructor. Datasets of 100,000 and 200,000 tuples were randomly sampled from the testing bed of 300,000 tuples. As expected, D has no significant impact on the Uaul of PVSV-Constructor since PVSV-Constructor generates values from the domain of each private attributes. D has no impact on the Uaul of PVST-Constructor, which indicates that a dataset containing 100,000 tuples is sufficient for PVST-Constructor to generate polymorphic value sets with true values.Figure 6
Utility loss vs.D.Figure 7
Utility loss vs.D


## 6.3.4. Evaluation ofUaul with Varying m

We investigate the impact of the number of private and public attributes on average top-k utility loss. Figure 8 presents the Uaul of PVSV-Constructor with fixed m′ and varying m and with fixed m and varying m′. When m/m′ is set to 5, we randomly removed 5 attributes from the testing bed. When m/m′ is set to 15, we added 5 more categorical attributes randomly chosen from the unused attributes. We observe that the Uaul monotonically decreases with increasing number of public attributes and monotonically increases with increasing number of private attributes. As expected, a higher proportion of public attributes leads to less variant between sv∣q and s′v∣q. The results of the same experiment with PVST-Constructor are shown in Figure 9. Uaul increases as increasing number of private attributes as expected. However, Uaul also increases slightly with increasing number of public attributes. This is due to the fact that with more public attributes, there will be few tuples that share the same public attribute values. Since PVST-Constructor inserts only private attribute values from tuples sharing same public attribute values, more values will be inserted to each polymorphic value set, which introduces higher utility loss.Figure 8
Utility loss vs.m and m′.Figure 9
Utility loss vs.m and m′.


## 6.3.5. Evaluation ofUaul with Varying Weight Ratios

Figures10 and 11 illustrate the impact of weight ratios on the average utility loss. The experiment was conducted with a fixed private attribute weight of 1 and varying public attribute weights of 1, 2, and 3. As expected, Uaul of both PVSV-Constructor and PVST-Constructor decreases as increasing weight ratio of public attributes. The reason is that as the public attribute weight increases, the part in s′v∣q caused by private attributes decreases. Therefore, less impact would be made to s′v∣q by PVSV and PVST. As a result, s′v∣q would be closer to sv∣q and the utility loss could be decreased.Figure 10
Utility loss vs. weight ratio.Figure 11
Utility loss vs. weight ratio.


## 7. Conclusions

In this paper, we proposed a novel framework that preserves privacy of private attributes against arbitrary attacks through the ranked retrieval model. Furthermore, we identify two categories of adversaries based on varying adversarial capabilities. For each kind of adversaries, we presented implementation of our framework. Our experimental results suggest that our implementations efficiently preserve privacy against Rank Inference attack [35]. Moreover, the implementations significantly reduce utility loss with respect to the variance in ranked results.It is our hope that this paper can motivate further research in privacy preservation of SIoT with consideration of social network features and/or variant information retrieval models, e.g., text mining.



---

*Source: 5498375-2019-08-28.xml*