# Practicalm-k-Anonymization for Collaborative Data Publishing without Trusted Third Party

Authors: Jingyu Hua; An Tang; Qingyun Pan; Kim-Kwang Raymond Choo; Hong Ding; Yizhi Ren
Journal: Security and Communication Networks
 (2017)

---

## Abstract

In collaborative data publishing (CDP), anm-adversary attack refers to a scenario where up to m malicious data providers collude to infer data records contributed by other providers. Existing solutions either rely on a trusted third party (TTP) or introduce expensive computation and communication overheads. In this paper, we present a practical distributed k-anonymization scheme, m-k-anonymization, designed to defend against m-adversary attacks without relying on any TTPs. We then prove its security in the semihonest adversary model and demonstrate how an extension of the scheme can also be proven secure in a stronger adversary model. We also evaluate its efficiency using a commonly used dataset.


---

## Body

## 1. Introduction

In today’s interconnected society, our sensitive personal data are increasingly stored in various databases belonging to different online service providers. Although online service providers have the duty and vested interest to ensure the security and privacy of user data, there are instances where user data are shared or compromised. For instance, a small to medium sized online service provider may wish to mine user purchasing patterns in order to fine-tune their marketing strategy and improve sales. Such (data mining) task is likely to be outsourced to a third-party marketing company; thus, the records in the online service provider’s database will be shared with the third-party. In such a scenario, the online service provider requires a privacy-preserving data publishing (i.e., sharing) approach to ensure that the data is shared without breaching user privacy.If the records to be published are owned by a single provider, the provider can easily run algorithms, such as [1, 2] which implement k-anonymity [3] (a widely used privacy protection mechanism), to anonymize the data prior to publishing. k-anonymity is proposed to solve such problems, that is, when a data owner or provider wants to publish parts of its data which is related to some specific persons, how can it guarantee that these persons cannot be reidentified while the remaining parts of the data are still practically useful? Consider a table with n rows and m columns; each row of the table represents a record relating to a specific object and each column represents an attribute of each object. Some nonprivate attributes can be considered as quasi identifier (QI). A table satisfying k-anonymity means QI of each tuple contained in this table appears at least k times [3].However, data in the real world is unlikely to originate from a single provider. Solutions seeking to address such a scenario are known ascollaborative privacy-preserving data publishing (CPPDP). CPPDP has received considerable attention in recent years (e.g., [4–11]). A straightforward solution is for all providers to outsource their data to a TTP, who will assume control of the data as if the TTP is publishing its own data. An alternative approach uses Secure Multiparty Computation (SMC) [12], which allows providers to collaboratively compute preferred functions upon the complete dataset without revealing private data [4, 5].Although these schemes could guarantee that anonymized data satisfiesk-anonymity against outsider attackers, malicious providers (i.e., insider attackers) or vendors who have access to the provider’s systems may collude to invalidate k-anonymity by excluding their own data. Let us now consider the example described in [13], where in Table 1, T1,T2,T3,T4 are databases of four hospitals. In this example, four hospitals wish to collaboratively publish their dataset without revealing their patients’ privacy (e.g., medical diagnosis). Of the nonsensitive attributes ({Name,Age,Zip}), {Age,Zip} can be considered a quasi identifier (QI). QI refers to a set of attributes that are not unique identifiers in themselves but can be corrected to uniquely identify most tuples in the dataset [3]. Ta∗ is an anonymized dataset satisfying 2-anonymity. Each QI group includes 3 records; therefore, each QI tuple appears at least 2 times in every group. From {Age,Zip}, we cannot infer the disease information of different patients. However, if P1 is an adversary, it could remove all its data from Ta∗. Thus, the only record in this group is provided by P3, and the remaining data no longer satisfies 2-anonymity. Therefore, the attributes of disease can be achieved easily. For instance, P1 can link other datasets with the remaining part of first QI group, such as a voter list or another dataset which contains {Name,Age,Zip,etc.}. This would enable us to infer the disease ofSara by linking two datasets together. In reality, there could exist more than one adversary. m providers, for instance, might collude to remove their data to infer records contributed by other providers. This is known as the m-adversary problem in the literature.Table 1
m-adversary and m-privacy example.
(a)
T
1
Name
Age
Zip
Disease
Alice
24
98745
Cancer
Bob
35
12367
Epilepsy
Emily
22
98712
Asthma
(b)
T
2
Name
Age
Zip
Disease
Olga
32
98701
Cancer
Mark
37
12389
Flu
John
31
12399
Flu
(c)
T
3
Name
Age
Zip
Disease
Sara
20
12300
Epilepsy
Cecilia
39
98708
Flu
(d)
T
4
Name
Age
Zip
Disease
Olga
32
98701
Cancer
Frank
33
12388
Asthma
(e)
T
a
∗
Providers
Name
Age
Zip
Disease
P1
Alice
[20–30]
∗
∗
∗
∗
∗
Cancer
P1
Emily
[20–30]
∗
∗
∗
∗
∗
Asthma
P3
Sara
[20–30]
∗
∗
∗
∗
∗
Epilepsy
P2
John
[31–34]
∗
∗
∗
∗
∗
Flu
P2,P4
Olga
[31–34]
∗
∗
∗
∗
∗
Cancer
P4
Frank
[31–34]
∗
∗
∗
∗
∗
Asthma
P1
Bob
[35–40]
∗
∗
∗
∗
∗
Epilepsy
P2
Mark
[35–40]
∗
∗
∗
∗
∗
Flu
P3
Cecilia
[35–40]
∗
∗
∗
∗
∗
Flu
(f)
T
b
∗
Providers
Name
Age
Zip
Disease
P1
Alice
[20–40]
∗
∗
∗
∗
∗
Cancer
P2
Mark
[20–40]
∗
∗
∗
∗
∗
Flu
P3
Sara
[20–40]
∗
∗
∗
∗
∗
Epilepsy
P
_
1
Emily
[20–40]
987
∗
∗
Asthma
P2,P4
Olga
[20–40]
987
∗
∗
Cancer
P3
Cecilia
[20–40]
987
∗
∗
Flu
P
_
1
Bob
[20–40]
123∗∗
Epilepsy
P_4
Frank
[20–40]
123
∗
∗
Asthma
P_2
John
[20–40]
123
∗
∗
FluSeeking to address them-adversary problem, Goryczka et al. [13] introduce the concept of m-privacy which is the focus of this paper. More specifically, we focus on m-privacy with respect to k-anonymity, which is referred to as m-k-anonymity in the remainder of this paper. Suppose that the total number of providers participating in the collaborative data publishing is n, and the published data after collaborative anonymization satisfies m-k-anonymity if, and only if, subdata from any n-m providers satisfies k-anonymity. When m adversaries remove all their data, the remaining data in the table still satisfies k-anonymity. The corresponding anonymization process is the m-k-anonymization, and as an example, Tb∗ is an anonymized dataset satisfying 1-2-anonymity. From the table, we can see that each QI group in Tb∗ contains 3 records. Even if one of the providers is an adversary, that is, P1 is an adversary and it removes all its data from the first QI group, the remaining two records in the first QI group of Tb∗ still satisfy 2-anonymity.Goryczka et al. present a TTP-dependent CPPDP scheme that achievesm-k-anonymity. However, TTP does not always exist in the real world [14, 15]. This is especially true in aftermath Edward Snowden’s revelation that the US Government has been conducting large-scale government surveillance (http://masssurveillance.info/). They then present a SMC variant of this scheme based on a series of cryptographic protocols (e.g., secure sum, secure comparison, and secure size of set union) to remove the need for a TTP. However, this variant is not specially designed for m-k-anonymity, and the constituent cryptographic protocols are too time consuming to be practical for real-world deployment.In this paper, we propose a TTP-independent CPPDP scheme designed to achievem-k-anonymity in a more efficient manner. We observe that the process of k-anonymity involves no sensitive attributes, and hence, we divide our scheme into two phases. Firstly, we use a centralized server which is not required to be trusted to aggregate nonsensitive components (i.e., QI attributes) of records from each provider and anonymize these components to ensure m-k-anonymity. Secondly, we design a distributed privacy-preserving method to aggregate values of sensitive attributes for each equivalence group without breaching m-k-anonymity. In other words, we present a practical two-phase CPPDP scheme without the need for a TTP, before demonstrating that the proposed scheme achieves m-k-anonymity in the widely accepted semihonest model. In the event that providers are malicious and attempt to modify user data, users are unlikely to find out about the tampering. Therefore, we present an effective sampling-based defense strategy against such an attack. We then evaluate the time efficiency of the proposed scheme with a public dataset including 45222 records. Our evaluations demonstrate that the time overhead increases linearly with n, which is reasonable for an offline scheme.


## 2. Related Work

Recent trends in big data and cloud computing have partly contributed to renewed interest in privacy-preserving data publishing [16–19]. Existing literature on privacy-preserving data publishing can be broadly classified into the following categories.Single Provider. Most existing research focus on the scenario involving a single data owner wanting to publish its own data, such as k-anonymity [3], l-diversity [20], and t-closeness [21]. Of these privacy models, k-anonymity has the longest history, and many efficient algorithms have been developed to implement k-anonymity. Examples of a bottom-up generalization approach and a top-down specification approach is Incognito [2] and Mondrian [1], respectively.Collaborative Data Publishing. In the collaborative data publishing literature, the focus is on privacy-preserving algorithms for distributed setups. For example, Jiang and Clifton [6] propose a protocol implementing k-anonymity on a vertically partitioned dataset. The protocol presented in [7] is designed to extract anonymized data from a set of providers, which is then published to the miner. Jiang and Clifton [8] present a SMC framework for data sharing between two untrusted parties, and Jurczyk and Xiong [9] present several decentralized protocols to ensure the user’s privacy during the querying of multiple databases. Mohammed et al. [10] seek to address the privacy-preserving problem in a specific application of data mashup in the web, which is a typical distributed scenario. The authors also present distributed algorithms to integrate healthcare data [11]. The protocol presented in [5] allows protocol participants decide in advance whether its utility is acceptable prior to execution.Insider Attackers. Goryczka et al. [13] present the m-adversary problem, where data providers are considered as potential attackers. To address such a threat, they propose the m-privacy model and present an efficient and effective TTP-based anonymization scheme. A key limitation of the scheme is the need for a TTP, which is not always available in the real world. Therefore, a SMC-based variant which does not rely on TTP is proposed by Goryczka et al. However, as noted by the authors, the SMC scheme is only a conceptual scheme that is not practical for real-world deployment due to the significant time overhead of the underlying protocols. This is the gap we seek to address in this paper, by presenting a practical SMC-based m-privacy implementation.


## 3. Problem Definition

LetP={P1,P2,…,Pn} be the set of all data providers, who own a set of records, Ti. T, defined as T={T1,T2,…,Tn}, is the set of all records. Providers aim to collaboratively publish the dataset T while preventing attackers from identifying records of individuals. In such a distributed environment, the providers may not trust each other. In other words, none of the providers can be considered as a TTP, and the publisher (considered as a separate party) is also not a trusted party.Definition 1 (k-anonymity in CPPDP).
Givenn providers, P1,P2,…,Pn, each with a dataset, T1,T2,…,Tn (Ti owned by Pi), the result set of CPPDP satisfies k-anonymity if, and only if, each QI group contains at least k records: that is, ∀i(1≤i≤ng),|QIi|≥k, where ng is the number of QI groups.k-Anonymity can prevent external adversaries from inferring sensitive attributes with QIs. However, k-anonymity is unable to address the m-adversary problem, as malicious providers (i.e., insiders) may collude to remove their own data to violate the k-anonymity of the remaining data. Targeting this problem, we define a new privacy model which we coined m-k-anonymity. The m-k-anonymity model is adapted from the m-privacy model of Goryczka et al. [13]. We denote the set of records owned by all adversaries PA={Pa1,Pa2,…,Pam} to be TA; that is, TA=⋃Pi∈PATi. In other words, TA(QIi) is the set of those records owned by any adversary in group QIi.Definition 2 (m-k-anonymity).
Given a set ofn providers, P={P1,P2,…,Pn}, m adversaries, and PA={Pa1,Pa2,…,Pam}, the result satisfies m-k-anonymity if and only if, ∀PA⊂P,|PA|=m,∀i(1≤i≤ng),|QIi|-|TA(QIi)|≥k.It means that, for every equivalence group in the anonymized dataset, its size excluding the number of records owned by anym providers must be larger than k. In other words, after m colluding providers have removed their records, each group must contain more than k records.Design Goal. An efficient and practical CPPDP scheme providing m-k-anonymity without involving a TTP is designed.


## 4. Two-Phase Scheme Providingm-Privacy

### 4.1. Semihonest Model

After definingm-k-anonymity in the preceding section (see Definition 2), we will now present our two-phase scheme. In our scheme, we have two key assumptions (Assumptions 3 and 4).Assumption 3.
The adversaries are semihonest (i.e., honest but curious), who will faithfully follow the protocol. However, these adversaries will also try to infer user privacy based on the protocol interactions.Assumption 4.
There are at mostm colluding providers.


### 4.2. Two-Phase Scheme

Our scheme, based on Observation 1, consists of two phases. In the first phase, all providers transmit only data with no private attributes to the untrusted publisher, who will carry out an algorithm implementingm-k-anonymity on the received data (see Section 4.2.1). In the second phase, m+1 randomly choose providers to collaboratively aggregate data with private attributes using a suitable cryptographic system (see Section 4.2.2). An illustration of the scheme is depicted in Figure 1.Figure 1
Our proposed two-phase scheme.Observation 5.
The anonymization process fork-anonymity does not involve private attributes.


#### 4.2.1. Phase I:k-Anonymization with Insensitive Attributes

In Phase I, the providers remove private attributes from the data prior to sending it to a third-party publisher that they may not truly trust. The publisher will then run a modified Mondrian algorithm on the received data to achievem-k-anonymity. Mondrian [1], one of the most efficient algorithms implementing k-anonymity, models the dataset using a multidimensional space with each attribute contributing a dimension. k-Anonymization in this multidimensional space is to recursively partition each subspace into two smaller subspaces which do not overlap with each other until the stop condition is satisfied. Each subspace represents a QI group.To achievem-k-anonymity, we modify the termination condition of Mondrian based on Conclusion 6.Conclusion 6.
LetPji(1≤j≤m,1≤i≤ng) be m providers who have the most records in group QIi. If ∀QIi(1≤i≤ng),|QIi|-∑j=1m‍|TPji(QIi)|≥k, then the result satisfies m-k-anonymity.Conclusion6 is straightforward to draw: as the set Pji denotes the m providers contributing the most records in QIi and |QIi|-∑j=1m‍|TPji(QIi)|≥k, it is easy to infer that, after removing any m providers data from QIi, the number of remained records must be no less than k. This means each group still satisfies k-anonymity.Based on this conclusion, we modify Mondrian so that the algorithm terminates when, in every subspace, a further partition will result in the number of records, owned bym providers who have most records, being greater than the total number minus k. The output of this algorithm is a number of QIs subject to m-k-anonymity. More details on the algorithm are demonstrated in Algorithm 1. Each iteration in Algorithm 1 is divided into ng-1 frequency sets according to dimension and values. Then for each frequency set, the split value will be calculated. According to ng-1 split values, the attributes can be divided into ng subspaces. Each subspace is a group of quasi identifier. The algorithm returns QIs that consist of QI1,QI2,…,QIng.Algorithm 1:Modified Mondrian algorithm.
(1)if no allowable multidimensional cut for partition then
(2)return  ϕ: partition→statisticsummary
(3)else
(4)dim←chooseDimension
(5)fs1,…,fsng-1←frequencySet(partition,dim)
(6)splitVal1,…,splitValng-1←findMedian(fs1,…,fsng-1)
(7)QI1←{t∈partition:t.dim≤splitVal1}
(8)QI2←{t∈partition:splitVal1<t.dim≤splitVal2}
(9)⋯
(10)QIng←{t∈partition:t.dim>splitValng-1}
(11)return  QI1∪QI2∪⋯∪QIng
(12)end if


#### 4.2.2. Phase II: Private Data Aggregation

In order to ensure the security of the private data, Phase II of our scheme uses a secure public-key cryptographic algorithm of the scheme implementer’s choice, such as RSA. Every provider generates its public and private key pair, makes public the public key, and protects the private key.The publisher will first send QIs obtained in Phase I to every provider. At the same time, the publisher randomly selectsm+1 decryption providers, Pd={Pd0,Pd1,…,Pdm}, from P and sends their addresses to each provider. We denote the remaining providers as Pri(0≤i≤n-m-2). On receiving QIs, every provider iteratively assigns private attributes of every record to the group whose QI contains its value of every nonprivate attribute. The providers encrypt the private data and their group information, using m+1 decryption providers’ encryption keys one at a time, in the reverse order of the addresses they received. Note that the encryption scheme used needs to be probabilistic (i.e., basic requirement of a secure encryption scheme). In other words, the encryption scheme introduces randomness in the encryption so that the encryption of the same message will produce a different cipher text each time.As illustrated in Figure2, the chain consists of m providers. We choose Pd0 as the first decryption provider in the chain. All providers (Prn-m-2,…,Pr0,Pd0,…,Pdm) will decrypt their data and send the encrypted data to the first decryption provider Pd0. Upon receiving all encrypted data, Pd0 will decrypt and uniformly repermute the decrypted data, prior to sending the decrypted data to the next decryption provider (Pd0,…,Pdm). All decryption providers in the chain repeat the same process, sequentially. When the last decryption provider obtains the partially decrypted data, it performs the (last) decryption and submits to the publisher. This repermutation process breaks the linkage between the data and their providers.Figure 2
Phase II: private data aggregation.In our proposal, providers have to perform decryption operations, which would inevitably bring additional communication and computation overheads. However, considering the fact that the data publishing is usually performed offline, we think higher overheads are affordable so long as they are still within reasonable bounds (e.g., a couple of hours or days). The detailed complexity analysis of our proposal is shown in Section4.3. Our experiment results on real-world datasets in Section 6 also show that the time overheads are within the acceptable range.


### 4.3. Security Analysis

We now present the security proof for our proposed scheme based on Theorem7.Theorem 7.
The two-phase scheme can correctly implementm-k-anonymity in the semihonest model (described in Section 4.1).Proof.
Phase I. It is trivial to observe that data privacy will not be compromised, since the providers transmit only data with no private attributes.
Phase II. Since at most m providers are malicious and there are m+1 or more decryption providers, there must exist at least one honest decryption provider in the decryption chain (which is the worse-case scenario).
Case
1. Adversaries are in front of honest decryption providers in the decryption chain. The adversaries are not able to fully decrypt the cipher texts as they do not have all decryption keys, although knowing the cipher text produced by another provider can be useful in inferring a record’s private attribute.
Case
2. Adversaries are after honest decryption providers in the decryption chain. In this case, the adversaries could collaborate to obtain the plain text of the private data, but they are unable to map the data to their owners due to mix operations of the (one or more) honest provider(s).
Case
3. Adversaries are both before and after honest decryption providers in the decryption chain (e.g., Adversary1, Adversary2,…,Adversaryx, HonestProvider1, Adversaryx+1, HonestProvider2, Adversaryx+2,…). In this case, before data pass the honest providers, adversaries will not be able to collaborate to fully decrypt the data as they do not have all decryption keys. After the data has passed the honest provider(s), the adversaries could collaborate to decrypt the records. However, since the data has been repermuted by the honest provider(s), the adversaries will not be able to link the records to their owners. Therefore, the proposed scheme is still secure under this case.Complexity Analysis. Phase I: the complexity of the modified Mondrian algorithm is O(Nlog⁡N), similar to the performance in the original Mondrian algorithm, where N is the total number of records. As the providers submit their insensitive data directly to the publisher, the communication complexity of Phase I is O(N).Phase II: the major computations are the encryption and decryption of private attributes, but it is easy to find that every record involvesm+1 encryptions and m+1 decryptions. Thus, the computation complexity of Phase II is O(mN). Since an encrypted record is transmitted for up to m+2 times, the communication complexity of Phase II is also O(mN).


### 4.4. Discussion

In this part, we will discuss the reliability of our scheme and compare it with TTP-scheme proposed by Goryczka et al. [13].Goryczka et al. propose an anonymization algorithm based on the Binary Space Partitioning. This algorithm can be implemented in a distributed environment by a trusted third party (TTP), which is considered as a secure anonymization protocol. It consists of two subprotocols. This first one is the provider-aware anonymization protocol. The time complexity of this protocol is determined by the number of recordsN and the number of attributes |q|. The analysis on provider-aware anonymization protocol shows that its time complexity equals O(N(q+1)(q2+nps)), where n is the number of providers and ps is the maximal number of fake values. The second one is the secure fitness score protocol and its time complexity is O(n2+nps).However, it is not easy to find a trusted third party in the real world. So, our scheme is TTP-independent which can achievem-k-anonymity in a more practical manner. Since we assume that there are at most m-adversaries and the total number of providers is more than m+1, there must exist at least one honest provider. We have proved the security of this proposal in Section 4.3. Our scheme is divided into two phases. The time complexity of Phase I is O(Nlog⁡N). Phase II’s time complexity equals O(mN). The time complexity of our scheme increases linear with n, where n is the number of providers, which is reasonable for an offline scheme. According to these facts, we think that our scheme is more secure in the real-world since it does not rely on any trusted third-party. What is more, the increased computation overheads due to encryptions and decryptions are within acceptable range, which have been demonstrated by our experiments on real datasets.


## 4.1. Semihonest Model

After definingm-k-anonymity in the preceding section (see Definition 2), we will now present our two-phase scheme. In our scheme, we have two key assumptions (Assumptions 3 and 4).Assumption 3.
The adversaries are semihonest (i.e., honest but curious), who will faithfully follow the protocol. However, these adversaries will also try to infer user privacy based on the protocol interactions.Assumption 4.
There are at mostm colluding providers.


## 4.2. Two-Phase Scheme

Our scheme, based on Observation 1, consists of two phases. In the first phase, all providers transmit only data with no private attributes to the untrusted publisher, who will carry out an algorithm implementingm-k-anonymity on the received data (see Section 4.2.1). In the second phase, m+1 randomly choose providers to collaboratively aggregate data with private attributes using a suitable cryptographic system (see Section 4.2.2). An illustration of the scheme is depicted in Figure 1.Figure 1
Our proposed two-phase scheme.Observation 5.
The anonymization process fork-anonymity does not involve private attributes.


### 4.2.1. Phase I:k-Anonymization with Insensitive Attributes

In Phase I, the providers remove private attributes from the data prior to sending it to a third-party publisher that they may not truly trust. The publisher will then run a modified Mondrian algorithm on the received data to achievem-k-anonymity. Mondrian [1], one of the most efficient algorithms implementing k-anonymity, models the dataset using a multidimensional space with each attribute contributing a dimension. k-Anonymization in this multidimensional space is to recursively partition each subspace into two smaller subspaces which do not overlap with each other until the stop condition is satisfied. Each subspace represents a QI group.To achievem-k-anonymity, we modify the termination condition of Mondrian based on Conclusion 6.Conclusion 6.
LetPji(1≤j≤m,1≤i≤ng) be m providers who have the most records in group QIi. If ∀QIi(1≤i≤ng),|QIi|-∑j=1m‍|TPji(QIi)|≥k, then the result satisfies m-k-anonymity.Conclusion6 is straightforward to draw: as the set Pji denotes the m providers contributing the most records in QIi and |QIi|-∑j=1m‍|TPji(QIi)|≥k, it is easy to infer that, after removing any m providers data from QIi, the number of remained records must be no less than k. This means each group still satisfies k-anonymity.Based on this conclusion, we modify Mondrian so that the algorithm terminates when, in every subspace, a further partition will result in the number of records, owned bym providers who have most records, being greater than the total number minus k. The output of this algorithm is a number of QIs subject to m-k-anonymity. More details on the algorithm are demonstrated in Algorithm 1. Each iteration in Algorithm 1 is divided into ng-1 frequency sets according to dimension and values. Then for each frequency set, the split value will be calculated. According to ng-1 split values, the attributes can be divided into ng subspaces. Each subspace is a group of quasi identifier. The algorithm returns QIs that consist of QI1,QI2,…,QIng.Algorithm 1:Modified Mondrian algorithm.
(1)if no allowable multidimensional cut for partition then
(2)return  ϕ: partition→statisticsummary
(3)else
(4)dim←chooseDimension
(5)fs1,…,fsng-1←frequencySet(partition,dim)
(6)splitVal1,…,splitValng-1←findMedian(fs1,…,fsng-1)
(7)QI1←{t∈partition:t.dim≤splitVal1}
(8)QI2←{t∈partition:splitVal1<t.dim≤splitVal2}
(9)⋯
(10)QIng←{t∈partition:t.dim>splitValng-1}
(11)return  QI1∪QI2∪⋯∪QIng
(12)end if


### 4.2.2. Phase II: Private Data Aggregation

In order to ensure the security of the private data, Phase II of our scheme uses a secure public-key cryptographic algorithm of the scheme implementer’s choice, such as RSA. Every provider generates its public and private key pair, makes public the public key, and protects the private key.The publisher will first send QIs obtained in Phase I to every provider. At the same time, the publisher randomly selectsm+1 decryption providers, Pd={Pd0,Pd1,…,Pdm}, from P and sends their addresses to each provider. We denote the remaining providers as Pri(0≤i≤n-m-2). On receiving QIs, every provider iteratively assigns private attributes of every record to the group whose QI contains its value of every nonprivate attribute. The providers encrypt the private data and their group information, using m+1 decryption providers’ encryption keys one at a time, in the reverse order of the addresses they received. Note that the encryption scheme used needs to be probabilistic (i.e., basic requirement of a secure encryption scheme). In other words, the encryption scheme introduces randomness in the encryption so that the encryption of the same message will produce a different cipher text each time.As illustrated in Figure2, the chain consists of m providers. We choose Pd0 as the first decryption provider in the chain. All providers (Prn-m-2,…,Pr0,Pd0,…,Pdm) will decrypt their data and send the encrypted data to the first decryption provider Pd0. Upon receiving all encrypted data, Pd0 will decrypt and uniformly repermute the decrypted data, prior to sending the decrypted data to the next decryption provider (Pd0,…,Pdm). All decryption providers in the chain repeat the same process, sequentially. When the last decryption provider obtains the partially decrypted data, it performs the (last) decryption and submits to the publisher. This repermutation process breaks the linkage between the data and their providers.Figure 2
Phase II: private data aggregation.In our proposal, providers have to perform decryption operations, which would inevitably bring additional communication and computation overheads. However, considering the fact that the data publishing is usually performed offline, we think higher overheads are affordable so long as they are still within reasonable bounds (e.g., a couple of hours or days). The detailed complexity analysis of our proposal is shown in Section4.3. Our experiment results on real-world datasets in Section 6 also show that the time overheads are within the acceptable range.


## 4.2.1. Phase I:k-Anonymization with Insensitive Attributes

In Phase I, the providers remove private attributes from the data prior to sending it to a third-party publisher that they may not truly trust. The publisher will then run a modified Mondrian algorithm on the received data to achievem-k-anonymity. Mondrian [1], one of the most efficient algorithms implementing k-anonymity, models the dataset using a multidimensional space with each attribute contributing a dimension. k-Anonymization in this multidimensional space is to recursively partition each subspace into two smaller subspaces which do not overlap with each other until the stop condition is satisfied. Each subspace represents a QI group.To achievem-k-anonymity, we modify the termination condition of Mondrian based on Conclusion 6.Conclusion 6.
LetPji(1≤j≤m,1≤i≤ng) be m providers who have the most records in group QIi. If ∀QIi(1≤i≤ng),|QIi|-∑j=1m‍|TPji(QIi)|≥k, then the result satisfies m-k-anonymity.Conclusion6 is straightforward to draw: as the set Pji denotes the m providers contributing the most records in QIi and |QIi|-∑j=1m‍|TPji(QIi)|≥k, it is easy to infer that, after removing any m providers data from QIi, the number of remained records must be no less than k. This means each group still satisfies k-anonymity.Based on this conclusion, we modify Mondrian so that the algorithm terminates when, in every subspace, a further partition will result in the number of records, owned bym providers who have most records, being greater than the total number minus k. The output of this algorithm is a number of QIs subject to m-k-anonymity. More details on the algorithm are demonstrated in Algorithm 1. Each iteration in Algorithm 1 is divided into ng-1 frequency sets according to dimension and values. Then for each frequency set, the split value will be calculated. According to ng-1 split values, the attributes can be divided into ng subspaces. Each subspace is a group of quasi identifier. The algorithm returns QIs that consist of QI1,QI2,…,QIng.Algorithm 1:Modified Mondrian algorithm.
(1)if no allowable multidimensional cut for partition then
(2)return  ϕ: partition→statisticsummary
(3)else
(4)dim←chooseDimension
(5)fs1,…,fsng-1←frequencySet(partition,dim)
(6)splitVal1,…,splitValng-1←findMedian(fs1,…,fsng-1)
(7)QI1←{t∈partition:t.dim≤splitVal1}
(8)QI2←{t∈partition:splitVal1<t.dim≤splitVal2}
(9)⋯
(10)QIng←{t∈partition:t.dim>splitValng-1}
(11)return  QI1∪QI2∪⋯∪QIng
(12)end if


## 4.2.2. Phase II: Private Data Aggregation

In order to ensure the security of the private data, Phase II of our scheme uses a secure public-key cryptographic algorithm of the scheme implementer’s choice, such as RSA. Every provider generates its public and private key pair, makes public the public key, and protects the private key.The publisher will first send QIs obtained in Phase I to every provider. At the same time, the publisher randomly selectsm+1 decryption providers, Pd={Pd0,Pd1,…,Pdm}, from P and sends their addresses to each provider. We denote the remaining providers as Pri(0≤i≤n-m-2). On receiving QIs, every provider iteratively assigns private attributes of every record to the group whose QI contains its value of every nonprivate attribute. The providers encrypt the private data and their group information, using m+1 decryption providers’ encryption keys one at a time, in the reverse order of the addresses they received. Note that the encryption scheme used needs to be probabilistic (i.e., basic requirement of a secure encryption scheme). In other words, the encryption scheme introduces randomness in the encryption so that the encryption of the same message will produce a different cipher text each time.As illustrated in Figure2, the chain consists of m providers. We choose Pd0 as the first decryption provider in the chain. All providers (Prn-m-2,…,Pr0,Pd0,…,Pdm) will decrypt their data and send the encrypted data to the first decryption provider Pd0. Upon receiving all encrypted data, Pd0 will decrypt and uniformly repermute the decrypted data, prior to sending the decrypted data to the next decryption provider (Pd0,…,Pdm). All decryption providers in the chain repeat the same process, sequentially. When the last decryption provider obtains the partially decrypted data, it performs the (last) decryption and submits to the publisher. This repermutation process breaks the linkage between the data and their providers.Figure 2
Phase II: private data aggregation.In our proposal, providers have to perform decryption operations, which would inevitably bring additional communication and computation overheads. However, considering the fact that the data publishing is usually performed offline, we think higher overheads are affordable so long as they are still within reasonable bounds (e.g., a couple of hours or days). The detailed complexity analysis of our proposal is shown in Section4.3. Our experiment results on real-world datasets in Section 6 also show that the time overheads are within the acceptable range.


## 4.3. Security Analysis

We now present the security proof for our proposed scheme based on Theorem7.Theorem 7.
The two-phase scheme can correctly implementm-k-anonymity in the semihonest model (described in Section 4.1).Proof.
Phase I. It is trivial to observe that data privacy will not be compromised, since the providers transmit only data with no private attributes.
Phase II. Since at most m providers are malicious and there are m+1 or more decryption providers, there must exist at least one honest decryption provider in the decryption chain (which is the worse-case scenario).
Case
1. Adversaries are in front of honest decryption providers in the decryption chain. The adversaries are not able to fully decrypt the cipher texts as they do not have all decryption keys, although knowing the cipher text produced by another provider can be useful in inferring a record’s private attribute.
Case
2. Adversaries are after honest decryption providers in the decryption chain. In this case, the adversaries could collaborate to obtain the plain text of the private data, but they are unable to map the data to their owners due to mix operations of the (one or more) honest provider(s).
Case
3. Adversaries are both before and after honest decryption providers in the decryption chain (e.g., Adversary1, Adversary2,…,Adversaryx, HonestProvider1, Adversaryx+1, HonestProvider2, Adversaryx+2,…). In this case, before data pass the honest providers, adversaries will not be able to collaborate to fully decrypt the data as they do not have all decryption keys. After the data has passed the honest provider(s), the adversaries could collaborate to decrypt the records. However, since the data has been repermuted by the honest provider(s), the adversaries will not be able to link the records to their owners. Therefore, the proposed scheme is still secure under this case.Complexity Analysis. Phase I: the complexity of the modified Mondrian algorithm is O(Nlog⁡N), similar to the performance in the original Mondrian algorithm, where N is the total number of records. As the providers submit their insensitive data directly to the publisher, the communication complexity of Phase I is O(N).Phase II: the major computations are the encryption and decryption of private attributes, but it is easy to find that every record involvesm+1 encryptions and m+1 decryptions. Thus, the computation complexity of Phase II is O(mN). Since an encrypted record is transmitted for up to m+2 times, the communication complexity of Phase II is also O(mN).


## 4.4. Discussion

In this part, we will discuss the reliability of our scheme and compare it with TTP-scheme proposed by Goryczka et al. [13].Goryczka et al. propose an anonymization algorithm based on the Binary Space Partitioning. This algorithm can be implemented in a distributed environment by a trusted third party (TTP), which is considered as a secure anonymization protocol. It consists of two subprotocols. This first one is the provider-aware anonymization protocol. The time complexity of this protocol is determined by the number of recordsN and the number of attributes |q|. The analysis on provider-aware anonymization protocol shows that its time complexity equals O(N(q+1)(q2+nps)), where n is the number of providers and ps is the maximal number of fake values. The second one is the secure fitness score protocol and its time complexity is O(n2+nps).However, it is not easy to find a trusted third party in the real world. So, our scheme is TTP-independent which can achievem-k-anonymity in a more practical manner. Since we assume that there are at most m-adversaries and the total number of providers is more than m+1, there must exist at least one honest provider. We have proved the security of this proposal in Section 4.3. Our scheme is divided into two phases. The time complexity of Phase I is O(Nlog⁡N). Phase II’s time complexity equals O(mN). The time complexity of our scheme increases linear with n, where n is the number of providers, which is reasonable for an offline scheme. According to these facts, we think that our scheme is more secure in the real-world since it does not rely on any trusted third-party. What is more, the increased computation overheads due to encryptions and decryptions are within acceptable range, which have been demonstrated by our experiments on real datasets.


## 5. An Extended Scheme Secure against a Stronger Adversary Model

### 5.1. Fully Malicious Model

The semihonest model, while widely accepted in the literature, may not be practical in the real world. More specifically, in the semihonest model, we are trusting providers not to misbehave. For example, Choo [22, 23] remarked that “there are legitimate concerns about cloud service providers being compelled to hand over user data that reside in the cloud to government agencies without the user’s knowledge or consent due to territorial jurisdiction by a foreign government.” Similar concerns were raised in [24], which then presented an extended proxy-assisted approach to address the concern of the need to trust the cloud server not to disclose user’s proxy keys which is inherent in proxy/mediator assisted user revocation approaches.Therefore, in this section, we will present a fully malicious model, which does not require an adversary to follow the protocol. In fact, the adversary’s aim is to successfully compromise user privacy. In the remainder of this paper, we will focus on tampering attacks that can be undertaken by (malicious) decryption providers. More specifically, if a decryption provider is malicious, the provider can replace encrypted data belonging to one or more honest providers with fictitious or fabricated data. Consequently, in the published result, the adversary(ies) can remove its/their original data and the fictitious or fabricated data inserted by the decryption provider from a number of QI groups. Hence, these groups will contain fewer thank records.


### 5.2. Sampling-Based Extension

The sampling-based extension of our scheme is described as follows.From Section4.2.2, we know that every provider encrypts the private data and their group information using m+1 decryption providers’ public keys one at a time. After encrypting the private data with the respective public keys, every provider generates m+1 special strings, SSji(0≤j≤m) of Pi, and sends SSji to the decryption provider Pdj. These strings are special because they do not have any group information. Then, each provider Pi(1≤i≤n) adds s pieces of every SSji(0≤j≤m) encrypted with {Pdj,Pdj-1,…,Pd0}’s public keys, respectively, and mixes them with the encrypted private data.OncePdj has finished the necessary decryption, n∗s special strings should have been fully decrypted. Pdj can easily distinguish these fully decrypted strings from previously obtained information. Therefore, these special strings can be removed. Only when the number of every SSji(1≤i≤n) equals s could the decryption provider sends the remaining decrypted data to the next decryption provider; otherwise, the decryption provider must discard all data and inform the publisher and the other providers. We suppose adversaries remove each record with probability r; then every provider’s detection rate is 1-(1-r)s. For a specific dataset, different s correspond to different detection rate. So we can set a threshold; if the detection rate is greater than the threshold, then we choose the value of s as the number of special strings to be added by each provider. For example, in Section 6 we can choose s=300 when the detection rate is greater than 95%.Worst-Case Scenario Analysis. There is only one honest decryption provider in the decryption chain. Adversaries appearing after the honest decryption provider in the decryption chain cannot tell the data’s owners even if they fully decrypt the cipher texts because the honest provider has faithfully repermuted the data which will break the relation between the cipher texts and their providers. Adversaries appearing before the honest provider in the decryption chain have access to the information which identifies the provider. However, these adversaries will not be able to fully decrypt all data except the special strings for validation. Therefore, regardless of the method used, the adversaries could probably remove some special strings which can be detected by the honest decryption provider. This simple method fulfills our design goal (i.e., an efficient and practical CPPDP scheme providing m-k-anonymity without involving a TTP), without compromising on the quality of the result. Although the additional data do not have group information, it can be easily distinguished and removed from the result.Suppose that adversaries appearing before the honest provider in the decryption chain remove each private record ofPi independently with probability r; then the detection rate is 1-(1-r)s by Pi. By inserting additional validation strings, we will achieve a higher detection rate. However, this will result in a longer processing time.


## 5.1. Fully Malicious Model

The semihonest model, while widely accepted in the literature, may not be practical in the real world. More specifically, in the semihonest model, we are trusting providers not to misbehave. For example, Choo [22, 23] remarked that “there are legitimate concerns about cloud service providers being compelled to hand over user data that reside in the cloud to government agencies without the user’s knowledge or consent due to territorial jurisdiction by a foreign government.” Similar concerns were raised in [24], which then presented an extended proxy-assisted approach to address the concern of the need to trust the cloud server not to disclose user’s proxy keys which is inherent in proxy/mediator assisted user revocation approaches.Therefore, in this section, we will present a fully malicious model, which does not require an adversary to follow the protocol. In fact, the adversary’s aim is to successfully compromise user privacy. In the remainder of this paper, we will focus on tampering attacks that can be undertaken by (malicious) decryption providers. More specifically, if a decryption provider is malicious, the provider can replace encrypted data belonging to one or more honest providers with fictitious or fabricated data. Consequently, in the published result, the adversary(ies) can remove its/their original data and the fictitious or fabricated data inserted by the decryption provider from a number of QI groups. Hence, these groups will contain fewer thank records.


## 5.2. Sampling-Based Extension

The sampling-based extension of our scheme is described as follows.From Section4.2.2, we know that every provider encrypts the private data and their group information using m+1 decryption providers’ public keys one at a time. After encrypting the private data with the respective public keys, every provider generates m+1 special strings, SSji(0≤j≤m) of Pi, and sends SSji to the decryption provider Pdj. These strings are special because they do not have any group information. Then, each provider Pi(1≤i≤n) adds s pieces of every SSji(0≤j≤m) encrypted with {Pdj,Pdj-1,…,Pd0}’s public keys, respectively, and mixes them with the encrypted private data.OncePdj has finished the necessary decryption, n∗s special strings should have been fully decrypted. Pdj can easily distinguish these fully decrypted strings from previously obtained information. Therefore, these special strings can be removed. Only when the number of every SSji(1≤i≤n) equals s could the decryption provider sends the remaining decrypted data to the next decryption provider; otherwise, the decryption provider must discard all data and inform the publisher and the other providers. We suppose adversaries remove each record with probability r; then every provider’s detection rate is 1-(1-r)s. For a specific dataset, different s correspond to different detection rate. So we can set a threshold; if the detection rate is greater than the threshold, then we choose the value of s as the number of special strings to be added by each provider. For example, in Section 6 we can choose s=300 when the detection rate is greater than 95%.Worst-Case Scenario Analysis. There is only one honest decryption provider in the decryption chain. Adversaries appearing after the honest decryption provider in the decryption chain cannot tell the data’s owners even if they fully decrypt the cipher texts because the honest provider has faithfully repermuted the data which will break the relation between the cipher texts and their providers. Adversaries appearing before the honest provider in the decryption chain have access to the information which identifies the provider. However, these adversaries will not be able to fully decrypt all data except the special strings for validation. Therefore, regardless of the method used, the adversaries could probably remove some special strings which can be detected by the honest decryption provider. This simple method fulfills our design goal (i.e., an efficient and practical CPPDP scheme providing m-k-anonymity without involving a TTP), without compromising on the quality of the result. Although the additional data do not have group information, it can be easily distinguished and removed from the result.Suppose that adversaries appearing before the honest provider in the decryption chain remove each private record ofPi independently with probability r; then the detection rate is 1-(1-r)s by Pi. By inserting additional validation strings, we will achieve a higher detection rate. However, this will result in a longer processing time.


## 6. Experiment Setup and Findings

We now describe our experimental setup and findings.


### 6.1. Setup

We performed the experiments on several machines, each with 2.4 GHz Xeon E5 CPU and 2 G RAM. The operating systems are Ubuntu 12.04 and the implementation was built and run in Java 2 Platform Standard Edition 7.0. We used the Adult dataset (http://archive.ics.uci.edu/ml/datasets/Adult), which is a commonly used benchmark in the literature [25–27]. We combined the training and test sets in the Adult dataset and removed records with missing attributes. Thus, we ended up with a dataset of 45222 records with 14 attributes. We assigned {age, workclass, fnlwgt, education, education-num, marital-status, relationship, race, sex, capital-gain, capital-loss, hours-per-week, native-country, salary} as the QI andoccupation as a private attribute. The total datasets were uniformly distributed among n data providers so that each of them was assigned a subset of similar size. We implemented RSA due to its popularity in commercial applications; each provider generates 1024-bit keys. We considered time as the key efficiency metric in our evaluations.


### 6.2. Findings

We measured the time between the publisher executing the scheme and receiving the resulting dataset. Findings are illustrated in Figure3. In Figure 3(a), n∗3000 records were chosen from the original dataset and uniformly distributed among n providers; thus, each provider had 3000 records on average. In Figure 3(b), all 45222 records were uniformly distributed among n=10 providers.Figure 3
Execution time.
(a)
Execution time versusn (n is the number of providers)
(b)
Execution time versusm (m is the number of adversaries)According to the definition ofm-k-anonymity, there must exist at least one honest provider among n providers. Thus, n is always greater or equal to m+1. It can be seen from Figure 3(a) that the execution time is approximately linear to n, which represents the size of the complete dataset. The result is also consistent with our guess. Even in the event that there are 15 providers, the time cost is below 20 minutes when m=2. When n=15 and m=5, the time cost is below 35 minutes. This is sufficiently efficient since data publishing is usually performed offline. In addition, from Figure 3(b), we can see that the execution time increases a little faster with m. This is easy to understand since more colluding providers indicate more encryptions and decryptions for each record and these cryptographic operations are very time consuming. Fortunately, the increased rate is still acceptable since the total number of encryptions and decryptions increases linearly with m. If we assume that fewer than half of the providers may collude, the time cost is around one hour, which is reasonable for an offline algorithm.According to the literature [13], the runtime of TTP-scheme is very high. The computation time of TTP-scheme increases almost exponentially with n which represents the number of providers. So doing experiment on secure m-privacy anonymization which is a subprotocol in TTP-scheme to achieve the computation time is unrealistic. Hence, we take the same approach as the authors mentioned in [13] to estimate the magnitude of computation time on the same dataset. The result is shown in Figure 4. Figure 4(a) shows the estimated time with varying values of n. In Figure 4(a), we can see that the computation time increases exponentially with n. And Figure 4(b) describes the estimated time varying different m. Due to theprovider-aware anonymization protocol in TTP-scheme, when the number of adversaries increases, the computation time decreases exponentially.Provider-aware means that providers will be aware if there exist one or more adversaries among all providers. Thus, as the number of adversaries increases, providers will discover adversaries earlier. So the increasing m will cause the anonymization process to end earlier. In terms of TTP-scheme implementation, the secure protocols can be chosen as different algorithms, such as top-down, binary. The choice of the algorithm will not adversely affect the result of computation time.Figure 4
Estimated execution time of TTP-scheme.
(a)
Estimated execution time versusn (n is the number of providers)
(b)
Estimated execution time versusm (m is the number of adversaries)We also remark that the security of the TTP-based scheme can be guaranteed, in the sense that the m-privacy anonymization protocol in TTP-scheme is secure as long as the subprotocol in the scheme is secure. We refer interested reader to [13] for the detailed security proof. Both TTP-scheme and our TTP-independent scheme can achieve m-privacy and k-anonymity. However, our algorithm is more efficient and practical. Due to the use of a strong encryption/decryption algorithm, our scheme is more secure in practice. The execution time of our scheme on the real dataset demonstrates that it is practical for deployment, especially for an offline algorithm.The following experiments illustrate the number of special strings we need to insert in order to obtain an ideal detection rate. We ran our extended scheme 1000 times under different settings (e.g., different adversary discarding rates and numbers of special strings). Suppose that the adversaries appearing before the honest decryption provider in the decryption chain collaboratively remove each record independently with probabilityr. Figure 5(a) shows the detection rate under different s (the number of inserted validation strings) when r=0.01 and Figure 5(b) shows the detection rates to different discarding rates when s=300.Figure 5
Detection rate.
(a)
Detection rate versuss (s is the number of inserted special strings)
(b)
Detection rate versusr (r is the discarding rate)It can be seen in Figures5(a) and 5(b) that, when adversaries remove each record with probability 1% independently, inserting 300 special strings yields a detection rate larger than 95%. For our experimental settings, 300 is about 1/15 of the size of each provider’s dataset, and the extension will increase the execution time by about 1/15 as the total time is linear to the number of records. In other words, the number of validation strings to be inserted is determined by the desired detection rate and discarding rate of the context.


## 6.1. Setup

We performed the experiments on several machines, each with 2.4 GHz Xeon E5 CPU and 2 G RAM. The operating systems are Ubuntu 12.04 and the implementation was built and run in Java 2 Platform Standard Edition 7.0. We used the Adult dataset (http://archive.ics.uci.edu/ml/datasets/Adult), which is a commonly used benchmark in the literature [25–27]. We combined the training and test sets in the Adult dataset and removed records with missing attributes. Thus, we ended up with a dataset of 45222 records with 14 attributes. We assigned {age, workclass, fnlwgt, education, education-num, marital-status, relationship, race, sex, capital-gain, capital-loss, hours-per-week, native-country, salary} as the QI andoccupation as a private attribute. The total datasets were uniformly distributed among n data providers so that each of them was assigned a subset of similar size. We implemented RSA due to its popularity in commercial applications; each provider generates 1024-bit keys. We considered time as the key efficiency metric in our evaluations.


## 6.2. Findings

We measured the time between the publisher executing the scheme and receiving the resulting dataset. Findings are illustrated in Figure3. In Figure 3(a), n∗3000 records were chosen from the original dataset and uniformly distributed among n providers; thus, each provider had 3000 records on average. In Figure 3(b), all 45222 records were uniformly distributed among n=10 providers.Figure 3
Execution time.
(a)
Execution time versusn (n is the number of providers)
(b)
Execution time versusm (m is the number of adversaries)According to the definition ofm-k-anonymity, there must exist at least one honest provider among n providers. Thus, n is always greater or equal to m+1. It can be seen from Figure 3(a) that the execution time is approximately linear to n, which represents the size of the complete dataset. The result is also consistent with our guess. Even in the event that there are 15 providers, the time cost is below 20 minutes when m=2. When n=15 and m=5, the time cost is below 35 minutes. This is sufficiently efficient since data publishing is usually performed offline. In addition, from Figure 3(b), we can see that the execution time increases a little faster with m. This is easy to understand since more colluding providers indicate more encryptions and decryptions for each record and these cryptographic operations are very time consuming. Fortunately, the increased rate is still acceptable since the total number of encryptions and decryptions increases linearly with m. If we assume that fewer than half of the providers may collude, the time cost is around one hour, which is reasonable for an offline algorithm.According to the literature [13], the runtime of TTP-scheme is very high. The computation time of TTP-scheme increases almost exponentially with n which represents the number of providers. So doing experiment on secure m-privacy anonymization which is a subprotocol in TTP-scheme to achieve the computation time is unrealistic. Hence, we take the same approach as the authors mentioned in [13] to estimate the magnitude of computation time on the same dataset. The result is shown in Figure 4. Figure 4(a) shows the estimated time with varying values of n. In Figure 4(a), we can see that the computation time increases exponentially with n. And Figure 4(b) describes the estimated time varying different m. Due to theprovider-aware anonymization protocol in TTP-scheme, when the number of adversaries increases, the computation time decreases exponentially.Provider-aware means that providers will be aware if there exist one or more adversaries among all providers. Thus, as the number of adversaries increases, providers will discover adversaries earlier. So the increasing m will cause the anonymization process to end earlier. In terms of TTP-scheme implementation, the secure protocols can be chosen as different algorithms, such as top-down, binary. The choice of the algorithm will not adversely affect the result of computation time.Figure 4
Estimated execution time of TTP-scheme.
(a)
Estimated execution time versusn (n is the number of providers)
(b)
Estimated execution time versusm (m is the number of adversaries)We also remark that the security of the TTP-based scheme can be guaranteed, in the sense that the m-privacy anonymization protocol in TTP-scheme is secure as long as the subprotocol in the scheme is secure. We refer interested reader to [13] for the detailed security proof. Both TTP-scheme and our TTP-independent scheme can achieve m-privacy and k-anonymity. However, our algorithm is more efficient and practical. Due to the use of a strong encryption/decryption algorithm, our scheme is more secure in practice. The execution time of our scheme on the real dataset demonstrates that it is practical for deployment, especially for an offline algorithm.The following experiments illustrate the number of special strings we need to insert in order to obtain an ideal detection rate. We ran our extended scheme 1000 times under different settings (e.g., different adversary discarding rates and numbers of special strings). Suppose that the adversaries appearing before the honest decryption provider in the decryption chain collaboratively remove each record independently with probabilityr. Figure 5(a) shows the detection rate under different s (the number of inserted validation strings) when r=0.01 and Figure 5(b) shows the detection rates to different discarding rates when s=300.Figure 5
Detection rate.
(a)
Detection rate versuss (s is the number of inserted special strings)
(b)
Detection rate versusr (r is the discarding rate)It can be seen in Figures5(a) and 5(b) that, when adversaries remove each record with probability 1% independently, inserting 300 special strings yields a detection rate larger than 95%. For our experimental settings, 300 is about 1/15 of the size of each provider’s dataset, and the extension will increase the execution time by about 1/15 as the total time is linear to the number of records. In other words, the number of validation strings to be inserted is determined by the desired detection rate and discarding rate of the context.


## 7. Conclusion

In this paper, we studied them-adversary problem, where m (geographically dispersed) providers could collude. Existing solutions either depend on a trusted third party (TTP) or have impractical time overheads. In our proposed two-phase scheme, however, we demonstrated how our scheme can be used to implement m-k-anonymity without the need for a TTP. We also proved the security of the scheme in a semihonest adversary model. We then explained how our scheme can be extended so that it is also secure in a stronger adversary model. Lastly, our experiments demonstrated the practicality of our scheme to be deployed in a real-world context.Future research include extending the scheme to providem-privacy with respect to other privacy constraints and generalize the scheme to implement m-privacy with respect to k-anonymity on distributed incremental datasets or collaborative data republishing.



---

*Source: 9532163-2017-03-16.xml*