PDA: A Novel Privacy-Preserving Robust Data Aggregation Scheme in People-Centric Sensing System

Abstract

With the advancement of wireless communication technologies, mobile phones, PDAs, and car embedded devices are equipped with sensors, such as sound and image. People can apply these devices to form a new sensing network called people-centric sensing network. And this network offers new opportunities for cooperative sensing applications. However, it introduces some challenges, including security challenge and robust challenge. As sensor nodes need to send their individual sensed data to an aggregator node and these data are related to users' real life, privacy-preserving data aggregation is a challenge issue. As a node could become offline or a message could be lost before reaching the aggregator, retaining the correctness of the aggregate computed is important. In this paper, we present the design of PDA, a novel privacy-preserving robust data aggregation scheme in people-centric sensing system. Based on K-anonymity, homomorphic encryption, and secret sharing, PDA can support a wide range of statistical additive and non-additive aggregation functions such as Sum, Subtraction, Average, Count, Max/Min, and Median without leaking individual sensed data. Moreover, PDA is robust to node failure and data loss. We also evaluate the efficacy and efficiency of PDA. The result shows that our scheme can achieve the security and robust goal under a reasonable cost.

1. Introduction

Nowadays, technological advances in sensing, computation, storage, and wireless communications turn the mobile devices carried by people into a global mobile sensing device [1]. For example, currently smartphone is equipped with accelerometers, audio, location, and image sensors. So the mobile device's owner becomes sensor custodian that can use the device to collect meaningful context data [2]. Therefore, people as individuals or special interest groups can apply the new sensing devices to form sensing networks which are called people-centric sensing networks [3]. This transformation provides a chance to create intelligence systems that collect data from widespread public participations [4]. There are many systems in present, such as BikeNet [5], CitySense [6], Mobiscopes [7], Urban Sensing [8], SenseWeb [9], and CarTel [10]. They could be used to monitor environmental pollution, temperature, or noise intensity of urban areas. In order to declare the impact of people-centric sensing networks, we will introduce the CitySense. CitySense passively “senses” the most popular places based on actual real-time activity and displays a live heat map. The application intelligently leverages the inherent wisdom of crowds without any change in existing user behavior, in order to navigate people to the hottest spots in a city [6]. So we could find the most popular places to visit easily through CitySense. That is, people-centric sensing networks have a great potential to provide large-scale, flexible, and global sensing network services.

Even though people-centric sensing networks can offer many benefit's to users, there are still some challenges. One of them is that the mobile device collects context information closely related to user's real life. So the concern of user privacy is a challenge for people-centric sensing networks. As users usually do not gain a direct benefit from reporting data, users are unwilling to share their data if their privacy is at risk [11]. The procedure of data aggregation is the most likely to by attacked by adversary. The other challenge is that a node could become offline or a message could be lost before reaching the aggregator. So we should consider a solution that ensures that these problems could not affect the correctness of the aggregate computed. These challenges motivate our design of PDA, a novel privacy-preserving robust data aggregation scheme in people-centric sensing system.

Although the people-centric sensing network is becoming popular, there is relatively little work focusing on its privacy aspects and robust to node or communication failure. The shortage of prior work can be concluded in three points. The first point is that prior work has generally focused on preserving user's privacy to a certain extent [11–14]. However, these researches are not robust to node or communication failure. The second point is that these researches rarely address the privacy issues of data aggregation which is the most likely to be attacked by adversary [15–17]. The third point is that most of prior work did not suit for the peculiarity of this network. For example, the devices are no longer owned by a single authority but belong to individuals; therefore, the devices could be mobile and malicious.

Though the above analysis, we could know that none of the existing schemes could overcome the challenges that one mentioned above in people-centric sensing networks. The contributions of this paper are summarized as follows. (i)

We formulate the threat model in people-centric sensing networks. These models enable researchers to study the privacy-preserving in people-centric sensing networks conveniently.

(ii)

We present a novel scheme, PDA, to protect users' privacy against threats and be robust to node or communication failure in people-centric sensing networks. This scheme is based on K-anonymity, homomorphic encryption, and secret sharing. And it can support a wide range of statistical additive and nonadditive aggregation functions such as Subtraction, Sum, Average, Count, Max/Min, and Median.

The paper is organized as follows. We present the related work in Section 2. In Section 3, we introduce the basic of K-anonymity, homomorphic encryption, and secret sharing. We present the system architecture, threat model, and design goal in Section 4. We present our scheme in detail in Section 5. Then, we give the evaluation of PDA in Section 6. Conclusion could be found in Section 7.

2. Related Work

Although the people-centric sensing network is becoming popular, there is relatively little work focusing on its privacy aspects and robust to node or communication failure.

In [11], AnonySense architecture for anonymous tasking and reporting has been proposed. Shi et al. [12] present the PriSense scheme to protect privacy during the aggregation process of data. And this scheme support additive and nonadditive aggregation functions. Feng et al. [13] present a scheme to realize the data aggregation. However, it only supports additive aggregation functions such as max/min and median at the sacrifice in data accuracy. Zhang et al. [14] also present a scheme which supports both additive aggregation functions and nonadditive ones. These researches can preserve users' privacy to a certain extent. However, these researches are not robust to node or communication failure.

Wagner [15] present a scheme that protect the data aggregation in the presence of false data injection attack by a few malicious nodes and provide guidelines for selecting appropriate aggregation functions in a sensor network. Chan et al. [16] design an algorithm which the base station could detect if the computed aggregate was falsified. Conti et al. [17] present a scheme to preserve the privacy of robust data aggregation in wireless sensor network. However, these researches did not address the privacy issues of data aggregation which is the most likely to be attacked by adversary. In addition, as the devices are no longer owned by a single authority but belong to individuals in people-centric sensing network, the devices could be mobile and malicious. Therefore, these researches are not suitable for people-centric sensing applications.

Therefore, the novelty and the main differences with the existing work in the literature can be concluded in four points. (i)

PDA is looking at the new sensing network called people-centric sensing network. Most of the existing schemes cannot suit for the peculiarity of this network. For example, the devices are no longer owned by a single authority but belong to individuals; therefore, the devices could be mobile and malicious.

(ii)

The problem that PDA solved contains security challenge and robust challenge. To the best of my knowledge, PDA is the first scheme that can solve these two problems of people-centric sensing network. Moreover, we not only consider the external internal threat, but also the internal threat. This is out of reach for a lot of existing work.

(iii)

PDA is a clever use of K-anonymity, homomorphic encryption, and secret sharing. There is little research to use these schemes for robust challenge. Moreover, the combination of these schemes works very well.

3. Basic Schemes

In this section, we will introduce the basic schemes which are implemented in our scheme.

3.1. $K -$ Anonymity

Society is experiencing exponential growth in the number and variety of data collections containing person-specific information as computer technology, network connectivity, and disk storage space become increasingly affordable. But the security of the database is a big challenge. Some researches propose that we can get a certain protection by removing some sensitive message. However, in most of these cases, the remaining data can be used to reidentify individuals by linking or matching the data to other data or by looking at unique characteristics found in the released data.

In order to solve this problem, Samarati [18] propose K-anonymity in 1998. In K-anonymity, an attacker cannot distinguish the specific individual who belongs to the private information by adding a certain amount of fake individuals. Therefore, we can prevent the disclosure of personal privacy.

K-anonymity: Let $R T (A_{1}, \dots, A_{n})$ be a table and $Q I_{R T}$ the quasi-identifier associated with it. $R T$ is said to satisfy K-anonymity if and only if each sequence of data in $R T [Q I_{R T}]$ appears with at least Koccurrences in $R T [Q I_{R T}]$ .

Table 1 provides an example of a table $R T$ that adheres to K-anonymity. The quasi-identifier for the table is $Q I_{R T} = {Sex, Birth}$ and $K = 2$ . That is, for each sequence of data in $R T [Q I_{R T}]$ , there are at least 2 occurrences of those data in $R T [Q I_{R T}]$ [19].

Table 1

An example of K-anonymity.

Num	Sex	Birth	Disease
1	F	78/0/*	Obesity
2	F	78/0/*	Chest pain
3	M	83/0/*	Short breath
4	M	83/0/*	Obesity

As the sensing data will be aggregated to aggregation servers and it could be malicious, we could guarantee security based on K-anonymity.

3.2. Homomorphic Encryption

Homomorphic encryption technology was originally developed in 1978 by Rivest [20]. It is an encryption transformation technology that allows operation of the ciphertext. Homomorphic encryption was first used to encrypt the statistics. It is ensured that the user can operate on sensitive data by the homogeneity of the algorithm without revealing the data information. That is, homomorphic encryption is a form of encryption which allows specific types of computations to be carried out on ciphertext and obtain an encrypted result which matches the decrypted result of operations performed on the plaintext. A cryptosystem which supports both addition and multiplication is known as fully homomorphic encryption. Using such a scheme, any circuit can be homomorphically evaluated, effectively allowing the construction of programs which may be run on encryptions of their inputs to produce an encryption of their output. This is equivalent to not knowing that the problem also gives the answer to the problem.

Homomorphic encryption is built on the foundations of algebra theory. Then we will introduce the basic idea of homomorphic encryption. Assuming that E and D are the encryption and decryption functions, plaintext data is a finite set $M = {m_{1}, m_{2}, \dots, m_{n}}$ , α and β on behalf of computing. If $D (α (E (m_{1}), E (m_{2}), \dots, E (m_{n}))) = β {m_{1}, m_{2}, \dots, m_{n}}$ is right, $(E, D, α, β)$ is called homomorphism. Homomorphic encryption has attracted many attentions of many scholars in recent years, such as Yu. Yu proposed homomorphic encryption algorithm; Craig Gentry introduced an algorithm that α and β are the same operation, and he referred to as the “ideal lattice” mathematical objects that allow people to make operation of the encryption data [21, 22].

3.3. Secret Sharing

Secret sharing distributes, preserves, and restores the secret method. And it is an important tool to achieve secure multiparty computation. Secret sharing refers to method for distributing a secret among a group of participants, each of whom is allocated a share of the secret. The secret can be reconstructed only when a sufficient number, of possibly different types, of shares are combined together; individual shares are of no use on their own [23]. Secret sharing technology extends to many areas and practice systems, such as video, voice, and other fields. It is a technology which combines theory and practice.

The general type of secret sharing is threshold method, generally with $(m, n)$ -threshold method. In this type, there are one dealer and n participants $(P_{1}, P_{2}, \dots, P_{n})$ . The dealer slices the secret S to $(s_{1}, s_{2}, \dots, s_{n})$ and shares the slices to the participants. The dealer accomplishes this by giving each participant a share in such a way that any group of m or more participants can together reconstruct the secret, but no group of fewer than m players can. That is, it takes m points to define a polynomial of degree $m - 1$ . The method is to create a polynomial of degree $m - 1$ with the secret as the first coefficient and the remaining coefficients picked at random. Next find n points on the curve and give one to each of the players. When at least m out of the n players reveal their points, there is sufficient information to fit a $(m - 1)$ th degree polynomial to them, the first coefficient being the secret [24, 25].

The basic method of secret sharing contains Shamir secret sharing method, Blakley secret sharing method, Karin-Greene-Hellman secret sharing method and so on.

4. System Architecture

In this section, we present the system model, threat model, and design goal.

4.1. System Model

The architecture of people-centric sensing system is demonstrated in Figure 1.

Figure 1

System model.

Then, we give the components of people-centric sensing system. (i)

The mobile nodes (MNs) are all kinds of devices with sensing the environment and reporting the sensed data, such as PDAs, smartphones, and laptops. And these MNs are carried by person or vehicles. Each MN has a unique ID in this system.

(ii)

The aggregation servers (ASs) provide network access services for MNs. Each AS is in charge of a certain region referred to as an area. Each MN in an area should send its sensed data to the AS which is in charge of the area. The AS should support a wide range of statistical additive and nonadditive aggregation functions such as Sum, Subtraction, Average, Count, Max/Min and Median.

(iii)

The server should realize three main functions. The first one is that the server manages MNs' identity-related information and stores the fake IDs table for K-anonymity. The second one is that the server is responsible for registering MNs that wish to participate. The third one is that the server stores the data that was computed by the ASs. It also provides services for the applications based on the data.

Without loss of generality, we give the assumption of PDA. We assume that all the mobile nodes can access to an AS. We assume that all ASs can access to the server. That is to say, each MN can access to the server through ASs. We assume that MNs report the data to the ASs when they achieve a request from the server. The server sends the request which specify what sensors to report and when to sense.

4.2. Threat Model

In people-centric sensing networks, the data which is received from MNs unavoidably relates to a lot of personal information. If the information is known by adversary, the user could suffer many troubles. In this section, we will analyze the threat mode. As the procedure of data aggregator is the most likely to be attacked by adversary, we are mainly concerned with the threat of this procedure. We separate the threats into two classes: the internal threat and the external threat.

(1) The Internal Threat. The main threat of internal attackers is that the ASs and MNs could be malicious. That is to say, the ASs and MNs could be compromised and controlled by adversaries. This model is rational in that the number of ASs and MNs is enormous and the ASs and MNs are owned by third-parties. Therefore, it is hard to guarantee that the entire ASs and MNs are reliable. The malicious ASs and MNs could reveal the privacy easily if we take no measures.

(2) The External Threat. As the internet is an open channel, the communication link is unsafe and unreliable. The external threat mainly contains two parts.

Part 1. The adversary may eavesdrop on communications between MNs and AS.

Part 2. The adversary may attempt to insert some false data to the procedure of data aggregation. That is, the adversary may damage the data integrity.

4.3. Design Goal

Our design goal in our paper is satisfying the following requirements. (i)

As the aggregation server and nodes could be compromised and controlled by adversaries, we should prevent the sensed data of an individual node from being disclosed to the aggregation server and nodes.

(ii)

As the communication link is unsafe and unreliable, we should prevent the sensed data being leaked. Moreover, we must guarantee the integrity of sensed data.

(iii)

As the nodes could become offline or a message could be lost before reaching the aggregation server, we should ensure that these problems could not affect the correctness of the aggregate computed.

5. Scheme Design

In this section, we describe our PDA scheme in detail. As we focus on the privacy-preserving robust data aggregation of people-centric sensing networks, we should support a wide range of statistical additive and nonadditive aggregation functions safely. The additive and nonadditive aggregation functions include Sum, Subtraction, Average, Count, Max/Min and Median. We will use Sum as an example to declare the scheme's realization. That is, we should prevent the sensed data of an individual node from being disclosed to the AS and other MNs during the process of computing. Moreover, we should be robust to node or communication failure. We could get the issue model as follow.

Issue Model. There are n MNs ${P_{1}, P_{2}, \dots, P_{n}}$ . Each of them has a sensed data $x_{i}, i \in [1, n]$ . These data should be computed (such as Sum). And the result should be sent to the AS. However, these MNs do not want to leak anything about their data to the other MNs and AS. Through the analysis of the problem, we know that the above problem can be solved as long as we can ensure the security of two-party computing problem. Therefore, the above model can be simplified as follow. Suppose that there are two MNs (say, Alice and Bob); each of them has a sensed data (say, $data_Alice$ and $data_Bob$ ). And one or more MNs (called third-party) $M = {M_{1}, M_{2}, \dots, M_{n}}$ exist in the model. And these third-parties are untrusted. Alice and Bob send their sensed data to the AS though these third-parties. Then the AS computes the sum of A and B. At the same time, A and B could not be disclosed to the AS and the third-parties. Moreover, we should be robust to node or communication failure. At last the result should be sent to the server.

In order to solve the issue, we present a novel scheme, PDA. The whole idea of scheme is shown in Figure 2. In order to understand the scheme intuitional, we will introduce an instance. In the instance, Alice and Bob have sensed data for computing. We assume $data_Alice = 3$ , $data_Bob = 4$ .

Figure 2

The idea of PDA.

There are five steps to realize our scheme.

5.1. Service Registration

Before the aggregation process of data, each MN needs to register for the service at our scheme. The service registration contains initialization and MN's registration.

During the initialization, the server should periodically generate fake IDs for K-anonymity and store them in a fake ID pool. The fake IDs can be generated using a cryptographic hash function, such as SHA-1. The equation is given as follows: $fake I D_{i} = SHA (fake I D_{i - 1} \oplus salt)$ .

During MN's registration, the MN should send a requested message to the server. After receiving the request, the server verifies if the MN is legal or not. After authentication, the server should pick k fake IDs from its fake ID pool. And one of them is used to replace the identity of the MN. Let this fake ID be $RID$ . The other $k - 1$ fake IDs are used to confuse the adversaries. Therefore, the server stores an entry as $(RID, I D_{1}, I D_{2}, \dots, I D_{k - 1})$ in a fake ID table. The number of fake IDs (k) depends on the MN's reporting frequency. At last, the server sends an OK message which contains the fake ID entry to the MN. The function of fake ID is realizing the anonymous transmission which is based on K-anonymity.

5.2. Authentication

As the feature of people-centric sensing network, the MNs are always moving from an AS to another one. To let the AS authenticate their identity, the MNs should send an authentication request to the AS. The request contains the MN's ID table. After receiving the authentication request, the AS forwards this request to the server. Upon receiving the message, the MS should verify the ID table's legality. If the verification succeeds, it sends a reply to the AS. On the reception of the reply, the AS sends an OK message to the MN which contains some parameters. These parameters contain a prime number P for homomorphic encryption, a prime number Q, and a random number m for secret sharing. The meaning of these parameters will be recommended in later subsection. After authentication, the communication link is established between the MN and the AS. Then the MNs could send the sensed data to the AS after receiving a task.

In our instance, we take $P = 11$ , $Q = 19$ , and $m = 3$ .

5.3. Homomorphic Encryption

After the MNs receive a task from the server, they should send the sensed data to the AS. Before sending data, the MNs will execute the data processing, homomorphic encryption. In this paper, the important point is proposing PDA, so we will use a simple algorithm to achieve homomorphic encryption. The implementation process is shown as follows. A large prime P getting from the AS is used as the key. a and b are sensed data. The encryption algorithm is $A = a + (r * P)$ , r is a random integer number, A is the ciphertext, and a is the plaintext. Therefore, the data of a and b which have been encrypted can be expressed as $(A + B) = (a + (r_{1} * P)) + (b + (r_{2} * P))$ . Then, the process of decryption is P modulo $(A + B)$ and the result is $(a + b)$ [26, 27]. So we achieve a simple homomorphic encryption algorithm. In PDA, both participants should operate their own data using the homomorphic encryption algorithm before sending to the AS. Though the operation, the AS get the sensed data which was encrypted. However, it could compute the sum of the sensed data. That is, the aggregation functions (such as Sum) could be completed without leaking individual sensed data.

In our instance, Alice and Bob use homomorphic encryption algorithm to encrypt $data_Alice$ and $data_Bob$ according to the prime number P which is negotiated. Then, we could get the ciphertext. For Alice, we take an integer $r = 3$ ; ciphertext A is $A = a + (r * P) = 3 + (3 * 11) = 36$ . For Bob, we take an integer $r = 2$ ; ciphertext B is $B = 4 + (2 * 11) = 26$ .

5.4. Secret Sharing

The general type of secret sharing is threshold method, generally with $(m, n)$ -threshold method. In this type, the dealer accomplishes this by giving each participants a share in such a way that any group of m or more participants can together reconstruct the secret but no group of fewer than m players can. In this scheme, in order to send the data after encryption to some third-parties and process the data by the third-party, we will improve the Shamir secret sharing algorithm. Shamir secret sharing algorithm is proposed by Shamir in 1979 [28]. The system relies on the idea that you can fit a unique polynomial of degree $m - 1$ to any set of m points that lie on the polynomial. It takes two points to define a straight line, three points to fully define a quadratic, four points to define a cubic curve, and so on. That is, it takes m points to define a polynomial of degree $m - 1$ . The principle of the algorithm is shown in Figure 3. Any two points in a straight line can define a straight line. So we can take any of two points in $(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{n}, y_{n})$ to obtain the equation of the line [29].

Figure 3

The principle of Shamir secret sharing.

The procedure of the algorithm is (assuming the secret is K) as follows.

Selecting a Polynomial. At first, we should select a polynomial $F (x)$ based on a prime number Q. The prime number is got from the parameter negotiation. $F (x) = (a_{m - 1} x^{m - 1} + a_{m - 2} x^{m - 2} + \dots + K) \mod Q$ , and $a_{m - 1}, a_{m - 2}, \dots, a_{1} \in [1, Q]$ .

Getting the Variables. Then, we should select n groups data $x_{1}, x_{2}, \dots, x_{n}, x_{i} \neq 0$ .

Computing the Point. At last, we should compute the point $(x_{i}, y_{i})$ , which meets the polynomial.

Therefore, we split the secret K to $(x_{i}, y_{i})$ , $i \in [1, n]$ . We can reconstruct the secret when getting more than m parts.

After homomorphic encryption, the MN will operate the data which was encrypted by homomorphic encryption through secret sharing. That is, the MN will slice the data to t points. Then, the MN will send these points to t third-parties. At the same time, the MN should pick an ID from its fake ID table and send it to the third-parties.

In our instance, Alice and Bob will perform secret sharing operation for the ciphertext. We assume that the polynomial $F (x)$ for Alice is $F (x) = (2 x^{2} + 4 x + 36) \mod 19$ . At first, Alice will compute the point of polynomial, based on $(x_{1}, x_{2}, x_{3}, x_{4})$ . Then, Alice could get four points ${(1,4), (2,14), (3,9), (4,8)}$ . At last, Alice will send the four points to four third-parties. Similarly, we assume that the polynomial $F (x)$ for Bob is $F (x) = (x^{2} + 2 x + 26) \mod 19$ . Bob will compute the point of polynomial, ${(1,10), (2,15), (3,3), (4,12)}$ [30]. At last, Bob will send the four points to four third-parties. At the same time, Alice and Bob should send its fake ID to the third-parties.

5.5. AS Operation

After the third-parties receive the points and the ID, they should forward the information to the AS. Upon receiving the points and the ID, the AS should take three steps to get the sum of the sensed data.

Step 1 (recovering the data).

The AS picks the points which have the same ID as a group. And it recovers the data for each group based on secret sharing. The procedure of recovering is as follow. At first, the AS should pick m points and select a polynomial $F (x) = (a_{m - 1} x^{m - 1} + a_{m - 2} x^{m - 2} + \dots + K) \mod Q$ . Then, the AS substitutes the m points into $F (x)$ . So we can get the data of $(a_{m - 1}, a_{m - 2}, . . ., K)$ . At last, we could get the data when setting $x = 0$ . In our instance, we pick three points ${(1,4), (2,14), (3,9)}$ and substitute them into $F (x)$ for Alice. Then, we could get that $a_{2} = 2, a_{1} = 4$ , and $K = 36$ . So the data is 36 for Alice. Similarly, the data is 26 for Bob.

Step 2 (computing the sum of data).

After recovering the data, we could compute the sum of data. In our instance, the sum of data is $R = 36 + 26 = 62$ .

Step 3 (getting the result).

As we conduct the data using homomorphic encryption, the data after computing is not the final result. In order to get the result, we should take the process of decryption which is using P modulo of the data. In our instance, the result is $R % P = 62 % 11 = 7$ . As $data_Alice + data_Bob = 3 + 4 = 7$ , we know that the result is correct. At last, the result will be sent to the server. The server can provide data to some applications which provide guidance of the social environment or people's social activities.

Through the above analysis, we compute the sum of sensed data during the procedure of aggregation. Similarly, we could support a wide range of statistical additive and nonadditive aggregation functions [12].

6. Evaluation

In this section, we evaluate the security and performance of PDA.

6.1. Security Evaluation

In this part, we analyze the security of our scheme based on the threat model discussed in Section 3. We assume that the threats contain that (1) the ASs could be compromised by adversaries; (2) the MNs could be malicious; (3) the adversary could eavesdrop all of the communications in the network; (4) the adversary could attempt to insert some false data to the procedure of data aggregation.

For ease of threat, we explain the security features of our scheme. (i)

The ASs could be compromised by adversaries. In PDA, the AS only gets the sensed data which has been encrypted by homomorphic encryption algorithm. As the AS cannot get the parameter r, it could not decrypt the data. Moreover, the AS cannot get the MNs which own the sensed data real ID as fake IDs. Therefore, the attacker obtains no useful information from the AS to compromise a single node's privacy.

(ii)

The MNs could be malicious. In PDA, the MN acts as one of third-part in the procedure of data aggregation. Each MN can only get one part of the other MNs' sensed data based on secret sharing. And fewer than m players cannot reconstruct the data. Moreover the sensed data is encrypted by homomorphic encryption algorithm. Therefore, we can compromise the privacy of a non-captured node leveraging the information.

(iii)

The adversary could eavesdrop all of the communications in the network. In PDA, each link between AS and MN transfers only one part of sensed data based on secret sharing. And fewer than m players cannot reconstruct the data. If the MN eavesdropped all of the communications in the network, it can reconstruct the sensed data. However, the sensed data is encrypted by homomorphic encryption algorithm. As the adversary cannot get the parameter r, it could not decrypt the data. Therefore, the adversary obtains no useful information to compromise a single node's privacy.

(iv)

The adversary could attempt to insert some false data to the procedure of data aggregation. In PDA, each sensed data is attached with the owner's ID. And the ID is picked from the MN's fake ID table randomly. As the adversary cannot get the fake ID table, he does not know the valid ID. The false data which was sent by the adversary is not accepted by the AS. Therefore, the adversary cannot damage the data integrity.

Through the above analysis, PDA is able to meet the security requirements of privacy-preserving data aggregation.

6.2. Performance Evaluation

In this section, we focus on the efficiency of PDA from robustness, computational complexity, and communication complexity.

6.2.1. Robustness

As the MNs could become offline or a message could be lost before reaching the AS, we should ensure that these problems could not affect the correctness of the aggregate computed. In our paper, we could achieve this goal though secret sharing. As the AS get a share from n third-parties, it can reconstruct the data but no group of fewer than $m (m < n)$ can. That is, the AS can reconstruct the sensed data when it received no less than m parts. Therefore, if the number of node failure or data loss is less than $n - m$ , we could ensure the correctness of the aggregate computed. Though the analysis, the AS can robust to node or communication failure.

6.2.2. Computational Complexity

For the people-centric sensing system, it is assumed that there are n MNs for computing. In order to compute all of the MNs' data, we should compute each two MNs' data. Therefore, the computing complexity of this process is $O (n^{2})$ . For each computation processing, the computation complexity is mainly determined by homomorphic encryption and secret sharing. The operations of homomorphic encryption and secret sharing are the simple algebraic operations. So the computation complexity is $O (k)$ that is not relevant to the size of input. The analysis shows that computational complexity of PDA is $O (n^{2})$ .

6.2.3. Communication Complexity

The primary aspect to measure the performance of a scheme is its computational complexity. But, for the problem of privacy-preserving robust data aggregation, computational complexity cannot fully describe the performance of a scheme. As the participants and third-parties will communicate each other, the communication complexity is also an important aspect to measure the performance of PDA.

The communication complexity contains the cost of secret sharing and the third-party operation. It is assumed that the number of MNs is m and the number of third-parties is n. As the MNs will send the secret input data to the third-parties and the third-parties will send the result to the AS, the communication complexity of PDA is $O (m * n)$ .

6.3. Comparison

In this section, we summarize the features of our proposal compared with other mainly relevant algorithms in Table 2.

Table 2

Comparing the features with other schemes.

	Additive and nonadditive aggregation	Privacy versus outsiders	Privacy versus MNs	Privacy versus AS	Node-failure and data-loss resilience	Suitable for people-centric sensing system
PriSense [12]	✓	✓	✓	✓	×	✓
AnonySense [11]	×	✓	✓	×	×	✓
Conti et al. scheme [17]	✓	✓	✓	✓	✓	×
Our scheme PDA	✓	✓	✓	✓	✓	✓

The feature additive and nonadditive aggregation indicates if the scheme support a wide range of statistical additive and nonadditive aggregation functions such as Sum, Subtraction, Average, Count, Max/Min, and Median. In columns 2, 3, and 4, these features indicate if the scheme protects privacy against outside eavesdropper, other MNs, or the AS. The features of node failure and data loss resilience refer to whether the AS can compute the correct aggregate when a few MNs become offline or a few messages could be lost. In columns 6 and 7, these features denote the scheme's computational and communication complexity. The last feature indicates if the scheme is suitable for the people-centric sensing networks.

Through the above analysis, our scheme is secure, scalable, and resilient to node failure and data loss.

7. Conclusion

We present PDA, a novel privacy-preserving robust data aggregation scheme in people-centric sensing system. Based on K-anonymity, homomorphic encryption, and secret sharing, PDA can support a wide range of statistical additive and nonadditive aggregation functions such as sum, subtraction, average, count, max/min and median without leaking individual sensed data. Moreover, PDA is robust to node failure and data loss. We also evaluate the efficacy and efficiency of PDA. The result shows that our scheme can achieve the security and robust goal under a reasonable cost. We believe a privacy-aware system will make people-centric sensing networks more acceptable.

Footnotes

Acknowledgments

The work described in this paper is partially supported by the Grants of the National Basic Research Program of China (973 project) under Grants nos. 2009CB320503, 2012CB315906; the project of National Science Foundation of China under Grants nos. 61070199, 61103189, 61103194, 61103182, 61202488, and 61272482; the National High Technology Research and Development Program of China (863 Program) nos. 2011AA01A103, 2012AA01A506, and 2013AA013505; the Research Fund for the Doctoral Program of Higher Education of China under Grants nos. 20114307110006, 20124307120032; the program for Changjiang Scholars and Innovative Research Team in University (no. IRT1012); Science and Technology Innovative Research Team in Higher Educational Institutions of Hunan Province (network technology); and Hunan Province Natural Science Foundation of China (11JJ7003).

References

Abdelzaher

Anokwa

Boda

Burke

Estrin

Guibas

Kansal

Madden

Reich

Mobiscopes for human spaces

IEEE Pervasive Computing 2007 6 2 20 29

2-s2.0-34247336855

10.1109/MPRV.2007.38

Campbell

A. T.

Eisenman

S. B.

Lane

N. D.

Miluzzo

Peterson

R. A.

People-centric urban sensing

Proceedings of the 2nd Annual International Workshop on Wireless Internet (WICON '06)

2006

ACM

Campbell

A. T.

Eisenman

S. B.

Lane

N. D.

Miluzzo

Peterson

R. A.

Zheng

Musolesi

Fodor

Ahn

G.-S.

The rise of people-centric sensing

IEEE Internet Computing 2008 12 4 12 21

2-s2.0-47649085662

10.1109/MIC.2008.90

Krontiris

Freiling

F. C.

Dimitriou

Location privacy in urban sensing networks: research challenges and directions

IEEE Wireless Communications 2010 17 5 30 35

2-s2.0-77958108414

10.1109/MWC.2010.5601955

Eisenman

S. B.

Miluzzo

Lane

N. D.

Peterson

R. A.

Ahn

G.-S.

Campbell

A. T.

BikeNet: a mobile sensing system for cyclist experience mapping

ACM Transactions on Sensor Networks 2009 6 1, article 6

2-s2.0-75149165677

10.1145/1653760.1653766

Welsh

Bers

Mostafavi

Doherty

CitySense: an urban-scale sensor network

Ecological Urbanism 2010

Zurich, Switzerland

Lars Müller

164 165 Harvard Graduate School of Design

Malinovskiy

Wang

Pedestrian travel pattern discovery using mobile bluetooth sensors

Proceedings of the 91st Annual Meeting of the Transportation Research Board

2012

Mun

Reddy

Shilton

Yau

Burke

Estrin

Hansen

Howard

West

Boda

PEIR, the personal environmental impact report, as a platform for participatory sensing systems research

Proceedings of the 7th ACM International Conference on Mobile Systems, Applications, and Services (MobiSys'09)

June 2009

Wroclaw, Poland

ACM

55 68

2-s2.0-70450248480

10.1145/1555816.1555823

Microsoft Research Sense Web Project

March 2013, http://research.microsoft.com/en-us/projects/senseweb/

10.

Crepaldi

Beavers

Ehrat

Kravets

Illinois vehicular project, live data sampling and opportunistic internet connectivity

Proceedings of the 3rd ACM International Workshop on Mobile Opportunistic Networks (MobiOpp '12)

March 2012

Zurich, Switzerland

ACM

85 86

2-s2.0-84860641866

10.1145/2159576.2159597

11.

Cornelius

Kapadia

Kotz

Peebles

Shin

Triandopoulos

AnonySense: privacy-aware people-centric sensing

Proceedings of the 6th International Conference on Mobile Systems, Applications, and Services (Mobisys '08)

June 2008

Breckenridge, Colo, USA

ACM

211 224

2-s2.0-57349110591

10.1145/1378600.1378624

12.

Shi

Zhang

Liu

Zhang

PriSense: privacy-preserving data aggregation in people-centric urban sensing systems

Proceedings of the IEEE International Conference on Computer Communications (INFOCOM '10)

March 2010

San Diego, Calif, USA

2-s2.0-77953308558

10.1109/INFCOM.2010.5462147

13.

Feng

Wang

Zhang

Ruan

Confidentiality protection for distributed sensor data aggregation

Proceedings of the 27th IEEE International Conference on Computer Communications (INFOCOM '08)

April 2008

Phoenix, Ariz, USA

475 483

2-s2.0-51349116601

10.1109/INFOCOM.2007.20

14.

Zhang

Wang

Feng

GP2S: generic privacy-preservation solutions for approximate aggregation of sensor data

Proceedings of the 6th IEEE Annual International Conference on Pervasive Computing and Communications (PerCom '08)

March 2008

Hong Kong

179 184

2-s2.0-49149125693

10.1109/PERCOM.2008.60

15.

Wagner

Resilient aggregation in sensor networks

Proceedings of the 4th ACM Workshop on Security of Ad Hoc and Sensor Networks (SASN '06)

October 2006

Alexandria, Va, USA

71 82

2-s2.0-34547406263

10.1145/1180345.1180355

16.

Chan

Perrig

Song

Secure hierarchical in-network aggregation in sensor networks

Proceedings of the 13th ACM Conference on Computer and Communications Security (CCS '06)

November 2006

Alexandria, Va, USA

ACM

278 287

2-s2.0-33845747795

10.1145/1180405.1180440

17.

Conti

Zhang

Roy

di Pietro

Jajodia

Mancini

L. V.

Privacy-preserving robust data aggregation in wireless sensor networks

Security and Communication Networks 2009 2 2 195 213

2-s2.0-67749093267

10.1002/sec.95

18.

Samarati

Sweeney

Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression

1998

SRI International

19.

Sweeney

k-anonymity: a model for protecting privacy

International Journal of Uncertainty, Fuzziness and Knowlege-Based Systems 2002 10 5 557 570

2-s2.0-0036811662

10.1142/S0218488502001648

20.

Rivest

R. L.

Adleman

Dertouzos

M. L.

On data banks and privacy homomorphisms

Foundations of Secure Computation 1978 32 4 169 178

21.

van Dijk

Gentry

Halevi

Vaikuntanathan

Gilbert

Fully homomorphic encryption over the integers

Advances in Cryptology—EUROCRYPT, 2010 2010 6110

Berlin, Germany

Springer

24 43 Lecture Notes in Computer Science

10.1007/978-3-642-13190-5_2

22.

Fontaine

Galand

A survey of homomorphic encryption for nonspecialists

Eurasip Journal on Information Security 2007 2007

2-s2.0-43949118608

10.1155/2007/13801

13801

23.

Feldman

A practical scheme for non-interactive verifiable secret sharing

Proceedings of the 28th IEEE Annual Symposium on Foundations of Computer Science (FOCS '87)

1987

24.

Harn

Secure secret reconstruction and multi—secret sharing schemes with unconditional security

Security and Communication Networks 2013

10.1002/sec.758

25.

Yan

Research and realization of security electronic voting plan based on homomorphic commitment verifiable secret sharing

Applied Mechanics and Materials 2013 263–266 1673 1676

10.4028/www.scientific.net/AMM.263-266.1673

26.

Prouff

Roche

Preneel

Takagi

Higher-order glitches free implementation of the AES using secure multi-party computation protocols

Cryptographic Hardware and Embedded Systems—CHES 2011 6917

Berlin, Germany

Springer

63 78 Lecture Notes in Computer Science

10.1007/978-3-642-23951-9_5

27.

Chung

K.-M.

Kalai

Vadhan

Rabin

Improved delegation of computation using fully homomorphic encryption

Advances in Cryptology—CRYPTO, 2010 2010 6223

Berlin, Germany

Springer

483 501 Lecture Notes in Computer Science

10.1007/978-3-642-14623-7_26

28.

Rivest

R. L.

Shamir

Adleman

A method for obtaining digital signatures and public-key cryptosystems

Communications of the ACM 1978 21 2 120 126

10.1145/359340.359342

29.

Oleshchuk

V. A.

Vladimir

Secure multi-party computations and privacy preservation: results and open problems

Telektronikk 2007 103 2, article 20

30.

From

S. L.

Jakobsen

Secure multi-party computation on integers [M.S. dissertation] 2006

Aarhus, Denmark

Datalogisk Institut, Aarhus Universitet

PDA: A Novel Privacy-Preserving Robust Data Aggregation Scheme in People-Centric Sensing System

Abstract

1. Introduction

2. Related Work

3. Basic Schemes

3.1. K - Anonymity

3.2. Homomorphic Encryption

3.3. Secret Sharing

4. System Architecture

4.1. System Model

4.2. Threat Model

4.3. Design Goal

5. Scheme Design

5.1. Service Registration

5.2. Authentication

5.3. Homomorphic Encryption

5.4. Secret Sharing

5.5. AS Operation

Step 1 (recovering the data).

Step 2 (computing the sum of data).

Step 3 (getting the result).

6. Evaluation

6.1. Security Evaluation

6.2. Performance Evaluation

6.2.1. Robustness

6.2.2. Computational Complexity

6.2.3. Communication Complexity

6.3. Comparison

7. Conclusion

Footnotes

Acknowledgments

References

3.1. $K -$ Anonymity