Privacy-Preserving Data Aggregation Protocols for Wireless Sensor Networks: A Survey
---
paper_title: Directed diffusion: a scalable and robust communication paradigm for sensor networks

paper_content:

Advances in processor, memory and radio technology will enable small and cheap nodes capable of sensing, communication and computation. Networks of such nodes can coordinate to perform distributed sensing of environmental phenomena. In this paper, we explore the directed diffusion paradigm for such coordination. Directed diffusion is datacentric in that all communication is for named data. All nodes in a directed diffusion-based network are application-aware. This enables diffusion to achieve energy savings by selecting empirically good paths and by caching and processing data in-network. We explore and evaluate the use of directed diffusion for a simple remote-surveillance sensor network.
---
paper_title: A New Approach for Energy-Balanced Data Aggregation in Wireless Sensor Networks

paper_content:

A wireless sensor network (WSN) is composed of a large number of sensor nodes which are resource constraints, e.g., limited power. This drives research on how to design routing protocols to gather data efficiently so that the life of the network can be prolonged. A usual concept to collect data by a sink node is to transfer data from sensor nodes to the sink node by multi-hop. However, it gives rise to two problems. The first one is the hotspot problem, in which the sensor nodes closer to the sink run out of energy sooner than other nodes. As a result, the network loses its service ability, regardless of a large amount of residual energy of the other nodes. The second one is that the network generates unnecessary traffic during data transmission for choosing a proper data sending path. To resolves the problems, we, in this paper, propose a new energy balanced and efficient data aggregation scheme for WSNs, called designated path (DP) scheme. In DP scheme, a set of paths is pre-determined and run them in round-robin fashion so that all the nodes can participate in the workload of gathering data and transferring the data to the sink. Through analytical performance evaluations and simulation results, we show that our DP scheme is more energy efficient and it can prolong the life time of the network than the existing schemes directed diffusion (DD) and hierarchical data aggregation (HDA).
---
paper_title: Approximate Aggregation Techniques for Sensor Databases

paper_content:

In the emerging area of sensor-based systems, a significant challenge is to develop scalable, fault-tolerant methods to extract useful information from the data the sensors collect. An approach to this data management problem is the use of sensor database systems, exemplified by TinyDB and Cougar, which allow users to perform aggregation queries such as MIN, COUNT and AVG on a sensor network. Due to power and range constraints, centralized approaches are generally impractical, so most systems use in-network aggregation to reduce network traffic. However, these aggregation strategies become bandwidth-intensive when combined with the fault-tolerant, multipath routing methods often used in these environments. For example, duplicate-sensitive aggregates such as SUM cannot be computed exactly using substantially less bandwidth than explicit enumeration. To avoid this expense, we investigate the use of approximate in-network aggregation using small sketches. Our contributions are as follows: 1) we generalize well known duplicate-insensitive sketches for approximating COUNT to handle SUM, 2) we present and analyze methods for using sketches to produce accurate results with low communication and computation overhead, and 3) we present an extensive experimental validation of our methods.
---
paper_title: The impact of timing in data aggregation for sensor networks

paper_content:

This paper evaluates the effect of timing in data aggregation algorithms. In-network aggregation achieves energy-efficient data propagation by processing data as it flows from information sources to sinks. Our goal is to show that the decision of when to "clock out" data as it is processed by nodes have significant performance impact in terms of data accuracy and freshness. Using the sensor network paradigm where all nodes produce information periodically, we compare three aggregation timing policies. Through extensive simulations we show that setting up the clock out timer based on a node's position in the aggregation tree results in a beneficial "cascading effect", yielding considerable energy efficiency, yet maintaining data accuracy and freshness.
---
paper_title: Privacy‐preserving robust data aggregation in wireless sensor networks

paper_content:

In-network data aggregation in wireless sensor networks (WSNs) is a technique aimed at reducing the communication overhead—sensed data are combined into partial results at intermediate nodes during message routing. However, in the above technique, some sensor nodes need to send their individual sensed values to an aggregator node, empowered with the capability to decrypt the received data to perform a partial aggregation. This scenario raises privacy concerns in applications like personal health care and the military surveillance. A few other solutions exist where the data are not disclosed to the aggregator (e.g., using privacy homomorphism (PH)), but these solutions are not robust to node or communication failure. ::: ::: The contributions of this paper are two-fold: first, we design a private data aggregation protocol that does not leak individual sensed values during the data aggregation process. In particular, neither the base station (BS) nor the other nodes are able to compromise the privacy of an individual node's sensed value. Second, the proposed protocol is robust to data-loss; if there is a node-failure or communication failure, the protocol is still able to compute the aggregate and to report to the base station the number of nodes that participated in the aggregation. To the best of our knowledge, our scheme is the first one that efficiently addresses the above issues all at once. Copyright © 2009 John Wiley & Sons, Ltd.
---
paper_title: Extending Network Lifetime for Precision-Constrained Data Aggregation in Wireless Sensor Networks

paper_content:

This paper exploits the tradeoff between data quality and energy consumption to extend the lifetime of wireless sensor networks. We consider the applications that require some aggregate form of sensed data with precision guarantees. Our key idea is to differentiate the precisions of data collected from different sensor nodes to balance their energy consumption. This is achieved by partitioning the precision constraint of data aggregation and allocating error bounds to individual sensor nodes in a coordinated fashion. Three factors affecting the lifetime of sensor nodes are identified: (1) the changing pattern of sensor readings; (2) the residual energy of sensor nodes; and (3) the communication cost between the sensor nodes and the base station. We analyze the optimal precision allocation in terms of network lifetime and propose an adaptive precision allocation scheme that dynamically adjusts the error bounds of sensor nodes. Experimental results using real data traces show that the proposed scheme significantly improves network lifetime compared to existing methods.
---
paper_title: Impact of network density on data aggregation in wireless sensor networks

paper_content:

In-network data aggregation is essential for wireless sensor networks where energy resources are limited. In a previously proposed data dissemination scheme (directed diffusion with opportunistic aggregation), data is opportunistically aggregated at intermediate nodes on a low-latency tree. In this paper, we explore and evaluate greedy aggregation, a novel approach that adjusts aggregation points to increase the amount of path sharing, reducing energy consumption. Our preliminary results suggest that, under investigated scenarios, greedy aggregation can achieve up to 45% energy savings over opportunistic aggregation in high-density networks without adversely impacting latency or robustness.
---
paper_title: Cache-and-query for wide area sensor databases

paper_content:

Webcams, microphones, pressure gauges and other sensors provide exciting new opportunities for querying and monitoring the physical world. In this paper we focus on querying wide area sensor databases, containing (XML) data derived from sensors spread over tens to thousands of miles. We present the first scalable system for executing XPATH queries on such databases. The system maintains the logical view of the data as a single XML document, while physically the data is fragmented across any number of host nodes. For scalability, sensor data is stored close to the sensors, but can be cached elsewhere as dictated by the queries. Our design enables self starting distributed queries that jump directly to the lowest common ancestor of the query result, dramatically reducing query response times. We present a novel query-evaluate gather technique (using XSLT) for detecting (1) which data in a local database fragment is part of the query result, and (2) how to gather the missing parts. We define partitioning and cache invariants that ensure that even partial matches on cached data are exploited and that correct answers are returned, despite our dynamic query-driven caching. Experimental results demonstrate that our techniques dramatically increase query throughputs and decrease query response times in wide area sensor databases.
---
paper_title: TAG: a Tiny AGgregation service for ad-hoc sensor networks

paper_content:

We present the Tiny AGgregation (TAG) service for aggregation in low-power, distributed, wireless environments. TAG allows users to express simple, declarative queries and have them distributed and executed efficiently in networks of low-power, wireless sensors. We discuss various generic properties of aggregates, and show how those properties affect the performance of our in network approach. We include a performance study demonstrating the advantages of our approach over traditional centralized, out-of-network methods, and discuss a variety of optimizations for improving the performance and fault tolerance of the basic solution.
---
paper_title: PDA: Privacy-Preserving Data Aggregation in Wireless Sensor Networks

paper_content:

Providing efficient data aggregation while preserving data privacy is a challenging problem in wireless sensor networks research. In this paper, we present two privacy-preserving data aggregation schemes for additive aggregation functions. The first scheme -cluster-based private data aggregation (CPDA)-leverages clustering protocol and algebraic properties of polynomials. It has the advantage of incurring less communication overhead. The second scheme -Slice-Mix-AggRegaTe (SMART)-builds on slicing techniques and the associative property of addition. It has the advantage of incurring less computation overhead. The goal of our work is to bridge the gap between collaborative data collection by wireless sensor networks and data privacy. We assess the two schemes by privacy-preservation efficacy, communication overhead, and data aggregation accuracy. We present simulation results of our schemes and compare their performance to a typical data aggregation scheme -TAG, where no data privacy protection is provided. Results show the efficacy and efficiency of our schemes. To the best of our knowledge, this paper is among the first on privacy-preserving data aggregation in wireless sensor networks.
---
paper_title: PDA: Privacy-Preserving Data Aggregation in Wireless Sensor Networks

paper_content:

Providing efficient data aggregation while preserving data privacy is a challenging problem in wireless sensor networks research. In this paper, we present two privacy-preserving data aggregation schemes for additive aggregation functions. The first scheme -cluster-based private data aggregation (CPDA)-leverages clustering protocol and algebraic properties of polynomials. It has the advantage of incurring less communication overhead. The second scheme -Slice-Mix-AggRegaTe (SMART)-builds on slicing techniques and the associative property of addition. It has the advantage of incurring less computation overhead. The goal of our work is to bridge the gap between collaborative data collection by wireless sensor networks and data privacy. We assess the two schemes by privacy-preservation efficacy, communication overhead, and data aggregation accuracy. We present simulation results of our schemes and compare their performance to a typical data aggregation scheme -TAG, where no data privacy protection is provided. Results show the efficacy and efficiency of our schemes. To the best of our knowledge, this paper is among the first on privacy-preserving data aggregation in wireless sensor networks.
---
paper_title: A New Approach for Energy-Balanced Data Aggregation in Wireless Sensor Networks

paper_content:

A wireless sensor network (WSN) is composed of a large number of sensor nodes which are resource constraints, e.g., limited power. This drives research on how to design routing protocols to gather data efficiently so that the life of the network can be prolonged. A usual concept to collect data by a sink node is to transfer data from sensor nodes to the sink node by multi-hop. However, it gives rise to two problems. The first one is the hotspot problem, in which the sensor nodes closer to the sink run out of energy sooner than other nodes. As a result, the network loses its service ability, regardless of a large amount of residual energy of the other nodes. The second one is that the network generates unnecessary traffic during data transmission for choosing a proper data sending path. To resolves the problems, we, in this paper, propose a new energy balanced and efficient data aggregation scheme for WSNs, called designated path (DP) scheme. In DP scheme, a set of paths is pre-determined and run them in round-robin fashion so that all the nodes can participate in the workload of gathering data and transferring the data to the sink. Through analytical performance evaluations and simulation results, we show that our DP scheme is more energy efficient and it can prolong the life time of the network than the existing schemes directed diffusion (DD) and hierarchical data aggregation (HDA).
---
paper_title: SDAP: A Secure Hop-by-Hop Data Aggregation Protocol for Sensor Networks

paper_content:

Hop-by-hop data aggregation is a very important technique for reducing the communication overhead and energy expenditure of sensor nodes during the process of data collection in a sensor network. However, because individual sensor readings are lost in the per-hop aggregation process, compromised nodes in the network may forge false values as the aggregation results of other nodes, tricking the base station into accepting spurious aggregation results. Here a fundamental challenge is: how can the base station obtain a good approximation of the fusion result when a fraction of sensor nodes are compromised.To answer this challenge, we propose SDAP, a Secure Hop-by-hop Data Aggregation Protocol for sensor networks. The design of SDAP is based on the principles of divide-and-conquer and commit-and-attest. First, SDAP uses a novel probabilistic grouping technique to dynamically partition the nodes in a tree topology into multiple logical groups (subtrees) of similar sizes. A commitment-based hop-by-hop aggregation is performed in each group to generate a group aggregate. The base station then identifies the suspicious groups based on the set of group aggregates. Finally, each group under suspect participates in an attestation process to prove the correctness of its group aggregate. Our analysis and simulations show that SDAP can achieve the level of efficiency close to an ordinary hop-by-hop aggregation protocol while providing certain assurance on the trustworthiness of the aggregation result. Moreover, SDAP is a general-purpose secure aggregation protocol applicable to multiple aggregation functions.
---
paper_title: SIA: Secure information aggregation in sensor networks

paper_content:

In sensor networks, data aggregation is a vital primitive enabling efficient data queries. An on-site aggregator device collects data from sensor nodes and produces a condensed summary which is forwarded to the off-site querier, thus reducing the communication cost of the query. Since the aggregator is on-site, it is vulnerable to physical compromise attacks. A compromised aggregator may report false aggregation results. Hence, it is essential that techniques are available to allow the querier to verify the integrity of the result returned by the aggregator node. ::: ::: We propose a novel framework for secure information aggregation in sensor networks. By constructing efficient random sampling mechanisms and interactive proofs, we enable the querier to verify that the answer given by the aggregator is a good approximation of the true value, even when the aggregator and a fraction of the sensor nodes are corrupted. In particular, we present efficient protocols for secure computation of the median and average of the measurements, for the estimation of the network size, for finding the minimum and maximum sensor reading, and for random sampling and leader election. Our protocols require only sublinear communication between the aggregator and the user.
---
paper_title: CDA: concealed data aggregation for reverse multicast traffic in wireless sensor networks

paper_content:

End-to-end encryption for wireless sensor networks is a challenging problem. To save the overall energy resources of the network, it is agreed that sensed data need to be consolidated and aggregated on their way to the final destination. We present an approach that (1) conceals sensed data end-to-end, by (2) still providing efficient in-network data aggregation. The aggregating intermediate nodes are not required to operate on the sensed plaintext data. We apply a particular class of encryption transformation and exemplarily discuss the approach on the basis of two aggregation functions. We use actual implementation to show that the approach is feasible and flexible and frequently even more energy efficient than hop-by-hop encryption.
---
paper_title: QoS Support in Wireless Sensor Networks : A Survey

paper_content:

In this paper, we assess the state of the art of Quality of Services (QoS) support in wireless sensor networks (WSNs). Unlike traditional end-to-end multimedia applications, many non-end-to-end mission-critical applications envisioned for WSNs have brought forward new QoS requirements on the network. Further, unique characteristics of WSNs, such as extremely resource-constrained sensors, large-scale random deployment, and novel data-centric communication protocols, pose unprecedented challenges in the area of QoS support in WSNs. Thus, we first review the techniques for QoS support in traditional networks, analyze new QoS requirements in WSNs from a wide variety of applications classified by data delivery models, and propose some non-end-to-end collective QoS parameters. Next, the challenges of QoS support in this new paradigm are presented. Finally, we comment on current research efforts and identify many exciting open issues in order to stimulate more research interest in this largely unexplored area. Keywords— Wireless networks, wireless sensor networks, QoS, collective QoS
---
paper_title: GP^2S: Generic Privacy-Preservation Solutions for Approximate Aggregation of Sensor Data (concise contribution)

paper_content:

Protecting privacy in sensor networks poses new challenges because of the potential incompatibilities between new privacy-preserving mechanisms and mechanisms already implemented in sensor networks (such as in-network data aggregation). To address this problem, we propose in this paper a set of new privacy-preservation data aggregation schemes. Different from past research, our solutions have the following features: supporting data aggregation for a variety of queries; providing privacy protection for both individual data and aggregate data; being resilient to any number of node collusion; being highly efficient.
---
paper_title: Efficient aggregation of encrypted data in wireless sensor networks

paper_content:

Wireless sensor networks (WSNs) are ad-hoc networks composed of tiny devices with limited computation and energy capacities. For such devices, data transmission is a very energy-consuming operation. It thus becomes essential to the lifetime of a WSN to minimize the number of bits sent by each device. One well-known approach is to aggregate sensor data (e.g., by adding) along the path from sensors to the sink. Aggregation becomes especially challenging if end-to-end privacy between sensors and the sink is required. In this paper, we propose a simple and provably secure additively homomorphic stream cipher that allows efficient aggregation of encrypted data. The new cipher only uses modular additions (with very small moduli) and is therefore very well suited for CPU-constrained devices. We show that aggregation based on this cipher can be used to efficiently compute statistical values such as mean, variance and standard deviation of sensed data, while achieving significant bandwidth gain.
---
paper_title: Privacy‐preserving robust data aggregation in wireless sensor networks

paper_content:

In-network data aggregation in wireless sensor networks (WSNs) is a technique aimed at reducing the communication overhead—sensed data are combined into partial results at intermediate nodes during message routing. However, in the above technique, some sensor nodes need to send their individual sensed values to an aggregator node, empowered with the capability to decrypt the received data to perform a partial aggregation. This scenario raises privacy concerns in applications like personal health care and the military surveillance. A few other solutions exist where the data are not disclosed to the aggregator (e.g., using privacy homomorphism (PH)), but these solutions are not robust to node or communication failure. ::: ::: The contributions of this paper are two-fold: first, we design a private data aggregation protocol that does not leak individual sensed values during the data aggregation process. In particular, neither the base station (BS) nor the other nodes are able to compromise the privacy of an individual node's sensed value. Second, the proposed protocol is robust to data-loss; if there is a node-failure or communication failure, the protocol is still able to compute the aggregate and to report to the base station the number of nodes that participated in the aggregation. To the best of our knowledge, our scheme is the first one that efficiently addresses the above issues all at once. Copyright © 2009 John Wiley & Sons, Ltd.
---
paper_title: PDA: Privacy-Preserving Data Aggregation in Wireless Sensor Networks

paper_content:

Providing efficient data aggregation while preserving data privacy is a challenging problem in wireless sensor networks research. In this paper, we present two privacy-preserving data aggregation schemes for additive aggregation functions. The first scheme -cluster-based private data aggregation (CPDA)-leverages clustering protocol and algebraic properties of polynomials. It has the advantage of incurring less communication overhead. The second scheme -Slice-Mix-AggRegaTe (SMART)-builds on slicing techniques and the associative property of addition. It has the advantage of incurring less computation overhead. The goal of our work is to bridge the gap between collaborative data collection by wireless sensor networks and data privacy. We assess the two schemes by privacy-preservation efficacy, communication overhead, and data aggregation accuracy. We present simulation results of our schemes and compare their performance to a typical data aggregation scheme -TAG, where no data privacy protection is provided. Results show the efficacy and efficiency of our schemes. To the best of our knowledge, this paper is among the first on privacy-preserving data aggregation in wireless sensor networks.
---
paper_title: Privacy‐preserving robust data aggregation in wireless sensor networks

paper_content:

In-network data aggregation in wireless sensor networks (WSNs) is a technique aimed at reducing the communication overhead—sensed data are combined into partial results at intermediate nodes during message routing. However, in the above technique, some sensor nodes need to send their individual sensed values to an aggregator node, empowered with the capability to decrypt the received data to perform a partial aggregation. This scenario raises privacy concerns in applications like personal health care and the military surveillance. A few other solutions exist where the data are not disclosed to the aggregator (e.g., using privacy homomorphism (PH)), but these solutions are not robust to node or communication failure. ::: ::: The contributions of this paper are two-fold: first, we design a private data aggregation protocol that does not leak individual sensed values during the data aggregation process. In particular, neither the base station (BS) nor the other nodes are able to compromise the privacy of an individual node's sensed value. Second, the proposed protocol is robust to data-loss; if there is a node-failure or communication failure, the protocol is still able to compute the aggregate and to report to the base station the number of nodes that participated in the aggregation. To the best of our knowledge, our scheme is the first one that efficiently addresses the above issues all at once. Copyright © 2009 John Wiley & Sons, Ltd.
---
paper_title: PDA: Privacy-Preserving Data Aggregation in Wireless Sensor Networks

paper_content:

Providing efficient data aggregation while preserving data privacy is a challenging problem in wireless sensor networks research. In this paper, we present two privacy-preserving data aggregation schemes for additive aggregation functions. The first scheme -cluster-based private data aggregation (CPDA)-leverages clustering protocol and algebraic properties of polynomials. It has the advantage of incurring less communication overhead. The second scheme -Slice-Mix-AggRegaTe (SMART)-builds on slicing techniques and the associative property of addition. It has the advantage of incurring less computation overhead. The goal of our work is to bridge the gap between collaborative data collection by wireless sensor networks and data privacy. We assess the two schemes by privacy-preservation efficacy, communication overhead, and data aggregation accuracy. We present simulation results of our schemes and compare their performance to a typical data aggregation scheme -TAG, where no data privacy protection is provided. Results show the efficacy and efficiency of our schemes. To the best of our knowledge, this paper is among the first on privacy-preserving data aggregation in wireless sensor networks.
---
paper_title: Secure hierarchical in-network aggregation in sensor networks

paper_content:

In-network aggregation is an essential primitive for performing queries on sensor network data. However, most aggregation algorithms assume that all intermediate nodes are trusted. In contrast, the standard threat model in sensor network security assumes that an attacker may control a fraction of the nodes, which may misbehave in an arbitrary (Byzantine) manner.We present the first algorithm for provably secure hierarchical in-network data aggregation. Our algorithm is guaranteed to detect any manipulation of the aggregate by the adversary beyond what is achievable through direct injection of data values at compromised nodes. In other words, the adversary can never gain any advantage from misrepresenting intermediate aggregation computations. Our algorithm incurs only O(Δ log2 n) node congestion, supports arbitrary tree-based aggregator topologies and retains its resistance against aggregation manipulation in the presence of arbitrary numbers of malicious nodes. The main algorithm is based on performing the sum aggregation securely by first forcing the adversary to commit to its choice of intermediate aggregation results, and then having the sensor nodes independently verify that their contributions to the aggregate are correctly incorporated. We show how to reduce secure median , count , and average to this primitive.
---
paper_title: SDAP: A Secure Hop-by-Hop Data Aggregation Protocol for Sensor Networks

paper_content:

Hop-by-hop data aggregation is a very important technique for reducing the communication overhead and energy expenditure of sensor nodes during the process of data collection in a sensor network. However, because individual sensor readings are lost in the per-hop aggregation process, compromised nodes in the network may forge false values as the aggregation results of other nodes, tricking the base station into accepting spurious aggregation results. Here a fundamental challenge is: how can the base station obtain a good approximation of the fusion result when a fraction of sensor nodes are compromised.To answer this challenge, we propose SDAP, a Secure Hop-by-hop Data Aggregation Protocol for sensor networks. The design of SDAP is based on the principles of divide-and-conquer and commit-and-attest. First, SDAP uses a novel probabilistic grouping technique to dynamically partition the nodes in a tree topology into multiple logical groups (subtrees) of similar sizes. A commitment-based hop-by-hop aggregation is performed in each group to generate a group aggregate. The base station then identifies the suspicious groups based on the set of group aggregates. Finally, each group under suspect participates in an attestation process to prove the correctness of its group aggregate. Our analysis and simulations show that SDAP can achieve the level of efficiency close to an ordinary hop-by-hop aggregation protocol while providing certain assurance on the trustworthiness of the aggregation result. Moreover, SDAP is a general-purpose secure aggregation protocol applicable to multiple aggregation functions.
---
paper_title: SIA: Secure information aggregation in sensor networks

paper_content:

In sensor networks, data aggregation is a vital primitive enabling efficient data queries. An on-site aggregator device collects data from sensor nodes and produces a condensed summary which is forwarded to the off-site querier, thus reducing the communication cost of the query. Since the aggregator is on-site, it is vulnerable to physical compromise attacks. A compromised aggregator may report false aggregation results. Hence, it is essential that techniques are available to allow the querier to verify the integrity of the result returned by the aggregator node. ::: ::: We propose a novel framework for secure information aggregation in sensor networks. By constructing efficient random sampling mechanisms and interactive proofs, we enable the querier to verify that the answer given by the aggregator is a good approximation of the true value, even when the aggregator and a fraction of the sensor nodes are corrupted. In particular, we present efficient protocols for secure computation of the median and average of the measurements, for the estimation of the network size, for finding the minimum and maximum sensor reading, and for random sampling and leader election. Our protocols require only sublinear communication between the aggregator and the user.
---
paper_title: Executing SQL over encrypted data in the database-service-provider model

paper_content:

Rapid advances in networking and Internet technologies have fueled the emergence of the "software as a service" model for enterprise computing. Successful examples of commercially viable software services include rent-a-spreadsheet, electronic mail services, general storage services, disaster protection services. "Database as a Service" model provides users power to create, store, modify, and retrieve data from anywhere in the world, as long as they have access to the Internet. It introduces several challenges, an important issue being data privacy. It is in this context that we specifically address the issue of data privacy.There are two main privacy issues. First, the owner of the data needs to be assured that the data stored on the service-provider site is protected against data thefts from outsiders. Second, data needs to be protected even from the service providers, if the providers themselves cannot be trusted. In this paper, we focus on the second challenge. Specifically, we explore techniques to execute SQL queries over encrypted data. Our strategy is to process as much of the query as possible at the service providers' site, without having to decrypt the data. Decryption and the remainder of the query processing are performed at the client site. The paper explores an algebraic framework to split the query to minimize the computation at the client site. Results of experiments validating our approach are also presented.
---
paper_title: A Privacy-Preserving Index for Range Queries

paper_content:

Database outsourcing is an emerging data management paradigm which has the potential to transform the IT operations of corporations. In this paper we address privacy threats in database outsourcing scenarios where trust in the service provider is limited. Specifically, we analyze the data partitioning (bucketization) technique and algorithmically develop this technique to build privacy-preserving indices on sensitive attributes of a relational table. Such indices enable an untrusted server to evaluate obfuscated range queries with minimal information leakage. We analyze the worst-case scenario of inference attacks that can potentially lead to breach of privacy (e.g., estimating the value of a data element within a small error margin) and identify statistical measures of data privacy in the context of these attacks. We also investigate precise privacy guarantees of data partitioning which form the basic building blocks of our index. We then develop a model for the fundamental privacy-utility tradeoff and design a novel algorithm for achieving the desired balance between privacy and utility (accuracy of range query evaluation) of the index.
---
paper_title: Verifiable Privacy-Preserving Range Query in Two-Tiered Sensor Networks

paper_content:

We consider a sensor network that is not fully trusted and ask the question how we preserve privacy for the collected data and how we verify the data reply from the network. We explore the problem in the context of a network augmented with storage nodes and target at range query. We use bucketing scheme to mix the data for a range, use message encryption for data integrity, and employ encoding numbers to prevent the storage nodes from dropping data.
---
paper_title: Privacy-preserving data mining

paper_content:

A fruitful direction for future data mining research will be the development of techniques that incorporate privacy concerns. Specifically, we address the following question. Since the primary task in data mining is the development of models about aggregated data, can we develop accurate models without access to precise information in individual data records? We consider the concrete case of building a decision-tree classifier from training data in which the values of individual records have been perturbed. The resulting data records look very different from the original records and the distribution of data values is also very different from the original distribution. While it is not possible to accurately estimate original values in individual data records, we propose a novel reconstruction procedure to accurately estimate the distribution of original data values. By using these reconstructed distributions, we are able to build classifiers whose accuracy is comparable to the accuracy of classifiers built with the original data.
---
paper_title: TAG: a Tiny AGgregation service for ad-hoc sensor networks

paper_content:

We present the Tiny AGgregation (TAG) service for aggregation in low-power, distributed, wireless environments. TAG allows users to express simple, declarative queries and have them distributed and executed efficiently in networks of low-power, wireless sensors. We discuss various generic properties of aggregates, and show how those properties affect the performance of our in network approach. We include a performance study demonstrating the advantages of our approach over traditional centralized, out-of-network methods, and discuss a variety of optimizations for improving the performance and fault tolerance of the basic solution.
---
paper_title: PDA: Privacy-Preserving Data Aggregation in Wireless Sensor Networks

paper_content:

Providing efficient data aggregation while preserving data privacy is a challenging problem in wireless sensor networks research. In this paper, we present two privacy-preserving data aggregation schemes for additive aggregation functions. The first scheme -cluster-based private data aggregation (CPDA)-leverages clustering protocol and algebraic properties of polynomials. It has the advantage of incurring less communication overhead. The second scheme -Slice-Mix-AggRegaTe (SMART)-builds on slicing techniques and the associative property of addition. It has the advantage of incurring less computation overhead. The goal of our work is to bridge the gap between collaborative data collection by wireless sensor networks and data privacy. We assess the two schemes by privacy-preservation efficacy, communication overhead, and data aggregation accuracy. We present simulation results of our schemes and compare their performance to a typical data aggregation scheme -TAG, where no data privacy protection is provided. Results show the efficacy and efficiency of our schemes. To the best of our knowledge, this paper is among the first on privacy-preserving data aggregation in wireless sensor networks.
---
paper_title: SET: Detecting node clones in sensor networks

paper_content:

Sensor nodes that are deployed in hostile environments are vulnerable to capture and compromise. An adversary may obtain private information from these sensors, clone and intelligently deploy them in the network to launch a variety of insider attacks. This attack process is broadly termed as a clone attack. Currently, the defenses against clone attacks are not only very few, but also suffer from selective interruption of detection and high overhead (computation and memory). In this paper, we propose a new effective and efficient scheme, called SET, to detect such clone attacks. The key idea of SET is to detect clones by computing set operations (intersection and union) of exclusive subsets in the network. First, SET securely forms exclusive unit subsets among one-hop neighbors in the network in a distributed way. This secure subset formation also provides the authentication of nodes’ subset membership. SET then employs a tree structure to compute non-overlapped set operations and integrates interleaved authentication to prevent unauthorized falsification of subset information during forwarding. Randomization is used to further make the exclusive subset and tree formation unpredictable to an adversary. We show the reliability and resilience of SET by analyzing the probability that an adversary may effectively obstruct the set operations. Performance analysis and simulations also demonstrate that the proposed scheme is more efficient than existing schemes from both communication and memory cost standpoints.
---
paper_title: A key-management scheme for distributed sensor networks

paper_content:

Distributed Sensor Networks (DSNs) are ad-hoc mobile networks that include sensor nodes with limited computation and communication capabilities. DSNs are dynamic in the sense that they allow addition and deletion of sensor nodes after deployment to grow the network or replace failing and unreliable nodes. DSNs may be deployed in hostile areas where communication is monitored and nodes are subject to capture and surreptitious use by an adversary. Hence DSNs require cryptographic protection of communications, sensor-capture detection, key revocation and sensor disabling. In this paper, we present a key-management scheme designed to satisfy both operational and security requirements of DSNs. The scheme includes selective distribution and revocation of keys to sensor nodes as well as node re-keying without substantial computation and communication capabilities. It relies on probabilistic key sharing among the nodes of a random graph and uses simple protocols for shared-key discovery and path-key establishment, and for key revocation, re-keying, and incremental addition of nodes. The security and network connectivity characteristics supported by the key-management scheme are discussed and simulation experiments presented.
---
paper_title: Protecting Classification Privacy Data Aggregation in Wireless Sensor Networks

paper_content:

As broad deployed of wireless sensor networks, privacy concerns have emerged as the main obstacle to success. When wireless sensor networks are used in everyday life, the privacy about monitored object' sensitive data becomes an important issue. Consequently, providing efficient data aggregation privacy protection is desirable. However, the existing technique is always energy exhausting, and does not consider different privacy levels of data aggregation. In this paper, DADPP (Data Aggregation Different Privacy-Levels Protection) is proposed to deal with data aggregation privacy protection. DADPP offers different levels of data aggregation privacy based on different node-numbers for pretreating data. According to desired privacy level, all nodes within the same cluster are partitioned into many groups, any group including node- numbers belong to the same privacy level. Data are pretreated only in the same group. Compared with the existing technique, DADPP has lower energy costs while ensuring expected privacy level.
---
paper_title: Privacy‐preserving robust data aggregation in wireless sensor networks

paper_content:

In-network data aggregation in wireless sensor networks (WSNs) is a technique aimed at reducing the communication overhead—sensed data are combined into partial results at intermediate nodes during message routing. However, in the above technique, some sensor nodes need to send their individual sensed values to an aggregator node, empowered with the capability to decrypt the received data to perform a partial aggregation. This scenario raises privacy concerns in applications like personal health care and the military surveillance. A few other solutions exist where the data are not disclosed to the aggregator (e.g., using privacy homomorphism (PH)), but these solutions are not robust to node or communication failure. ::: ::: The contributions of this paper are two-fold: first, we design a private data aggregation protocol that does not leak individual sensed values during the data aggregation process. In particular, neither the base station (BS) nor the other nodes are able to compromise the privacy of an individual node's sensed value. Second, the proposed protocol is robust to data-loss; if there is a node-failure or communication failure, the protocol is still able to compute the aggregate and to report to the base station the number of nodes that participated in the aggregation. To the best of our knowledge, our scheme is the first one that efficiently addresses the above issues all at once. Copyright © 2009 John Wiley & Sons, Ltd.
---
paper_title: pDCS: Security and Privacy Support for Data-Centric Sensor Networks

paper_content:

The demand for efficient data dissemination/access techniques to find the relevant data from within a sensor network has led to the development of data-centric sensor networks (DCS), where the sensor data as contrast to sensor nodes are named based on attributes such as event type or geographic location. However, saving data inside a network also creates security problems due to the lack of tamper-resistance of the sensor nodes and the unattended nature of the sensor network. For example, an attacker may simply locate and compromise the node storing the event of his interest. To address these security problems, we present pDCS, a privacy-enhanced DCS network which offers different levels of data privacy based on different cryptographic keys. In addition, we propose several query optimization techniques based on Euclidean Steiner Tree and Keyed Bloom Filter to minimize the query overhead while providing certain query privacy. Finally, detailed analysis and simulations show that the Keyed Bloom Filter scheme can significantly reduce the message overhead with the same level of query delay and maintain a very high level of query privacy.
---
paper_title: GP^2S: Generic Privacy-Preservation Solutions for Approximate Aggregation of Sensor Data (concise contribution)

paper_content:

Protecting privacy in sensor networks poses new challenges because of the potential incompatibilities between new privacy-preserving mechanisms and mechanisms already implemented in sensor networks (such as in-network data aggregation). To address this problem, we propose in this paper a set of new privacy-preservation data aggregation schemes. Different from past research, our solutions have the following features: supporting data aggregation for a variety of queries; providing privacy protection for both individual data and aggregate data; being resilient to any number of node collusion; being highly efficient.
---
paper_title: PDA: Privacy-Preserving Data Aggregation in Wireless Sensor Networks

paper_content:

Providing efficient data aggregation while preserving data privacy is a challenging problem in wireless sensor networks research. In this paper, we present two privacy-preserving data aggregation schemes for additive aggregation functions. The first scheme -cluster-based private data aggregation (CPDA)-leverages clustering protocol and algebraic properties of polynomials. It has the advantage of incurring less communication overhead. The second scheme -Slice-Mix-AggRegaTe (SMART)-builds on slicing techniques and the associative property of addition. It has the advantage of incurring less computation overhead. The goal of our work is to bridge the gap between collaborative data collection by wireless sensor networks and data privacy. We assess the two schemes by privacy-preservation efficacy, communication overhead, and data aggregation accuracy. We present simulation results of our schemes and compare their performance to a typical data aggregation scheme -TAG, where no data privacy protection is provided. Results show the efficacy and efficiency of our schemes. To the best of our knowledge, this paper is among the first on privacy-preserving data aggregation in wireless sensor networks.
---
paper_title: iPDA: An integrity-protecting private data aggregation scheme for wireless sensor networks

paper_content:

Data aggregation is an efficient mechanism widely used in wireless sensor networks (WSN) to collect statistics about data of interests. However, the shared-medium nature of communication makes the WSNs are vulnerable to eavesdropping and packet tampering/injection by adversaries. Hence, how to protect data privacy and data integrity are two major challenges for data aggregation in wireless sensor networks. In this paper, we present iPDA- an integrity-protecting private data aggregation scheme. In iPDA, data privacy is achieved through data slicing and assembling technique; and data integrity is achieved through redundancy by constructing disjoint aggregation paths/trees to collect data of interests. In iPDA, the data integrity-protection and data privacy-preservation mechanisms work synergistically. We evaluate the performance of iPDA scheme in terms of communication overhead and data aggregation accuracy, comparing with a typical data aggregation scheme - TAG, where no integrity protection and privacy preservation is provided. Simulation results show that iPDA achieves the design goals while still maintains the efficiency of data aggregation.
---
paper_title: CDA: concealed data aggregation for reverse multicast traffic in wireless sensor networks

paper_content:

End-to-end encryption for wireless sensor networks is a challenging problem. To save the overall energy resources of the network, it is agreed that sensed data need to be consolidated and aggregated on their way to the final destination. We present an approach that (1) conceals sensed data end-to-end, by (2) still providing efficient in-network data aggregation. The aggregating intermediate nodes are not required to operate on the sensed plaintext data. We apply a particular class of encryption transformation and exemplarily discuss the approach on the basis of two aggregation functions. We use actual implementation to show that the approach is feasible and flexible and frequently even more energy efficient than hop-by-hop encryption.
---
paper_title: Secure hierarchical in-network aggregation in sensor networks

paper_content:

In-network aggregation is an essential primitive for performing queries on sensor network data. However, most aggregation algorithms assume that all intermediate nodes are trusted. In contrast, the standard threat model in sensor network security assumes that an attacker may control a fraction of the nodes, which may misbehave in an arbitrary (Byzantine) manner.We present the first algorithm for provably secure hierarchical in-network data aggregation. Our algorithm is guaranteed to detect any manipulation of the aggregate by the adversary beyond what is achievable through direct injection of data values at compromised nodes. In other words, the adversary can never gain any advantage from misrepresenting intermediate aggregation computations. Our algorithm incurs only O(Δ log2 n) node congestion, supports arbitrary tree-based aggregator topologies and retains its resistance against aggregation manipulation in the presence of arbitrary numbers of malicious nodes. The main algorithm is based on performing the sum aggregation securely by first forcing the adversary to commit to its choice of intermediate aggregation results, and then having the sensor nodes independently verify that their contributions to the aggregate are correctly incorporated. We show how to reduce secure median , count , and average to this primitive.
---
paper_title: Order preserving encryption for numeric data

paper_content:

Encryption is a well established technology for protecting sensitive data. However, once encrypted, data can no longer be easily queried aside from exact matches. We present an order-preserving encryption scheme for numeric data that allows any comparison operation to be directly applied on encrypted data. Query results produced are sound (no false hits) and complete (no false drops). Our scheme handles updates gracefully and new values can be added without requiring changes in the encryption of other values. It allows standard databse indexes to be built over encrypted tables and can easily be integrated with existing database systems. The proposed scheme has been designed to be deployed in application environments in which the intruder can get access to the encrypted database, but does not have prior domain information such as the distribution of values and annot encrypt or decrypt arbitrary values of his choice. The encryption is robust against estimation of the true value in such environments.
---
paper_title: Privacy-Preserving Integrity-Assured Data Aggregation in Sensor Networks

paper_content:

Data aggregation in sensor network can improve both efficiency and privacy of network traffic.Recent work in integrity-assured data aggregation has considered aggregation as only an efficiency primitive. In this work, we address for the first time the problem of integrity-assured data aggregation with efficiency and privacy as a joint objective. Our solutions show the inherent tension between privacy-preservation and integrity-assurance of data aggregation.
---
paper_title: SIA: Secure information aggregation in sensor networks

paper_content:

In sensor networks, data aggregation is a vital primitive enabling efficient data queries. An on-site aggregator device collects data from sensor nodes and produces a condensed summary which is forwarded to the off-site querier, thus reducing the communication cost of the query. Since the aggregator is on-site, it is vulnerable to physical compromise attacks. A compromised aggregator may report false aggregation results. Hence, it is essential that techniques are available to allow the querier to verify the integrity of the result returned by the aggregator node. ::: ::: We propose a novel framework for secure information aggregation in sensor networks. By constructing efficient random sampling mechanisms and interactive proofs, we enable the querier to verify that the answer given by the aggregator is a good approximation of the true value, even when the aggregator and a fraction of the sensor nodes are corrupted. In particular, we present efficient protocols for secure computation of the median and average of the measurements, for the estimation of the network size, for finding the minimum and maximum sensor reading, and for random sampling and leader election. Our protocols require only sublinear communication between the aggregator and the user.
---
paper_title: Sampling algorithms: lower bounds and applications

paper_content:

We develop a framework to study probabilistic sampling algorithms that approximate general functions of the form \genfunc , where \domain and \range are arbitrary sets. Our goal is to obtain lower bounds on the query complexity of functions, namely the number of input variables x_i that any sampling algorithm needs to query to approximate f(x_1,\ldots,x_n) . We define two quantitative properties of functions --- the it block sensitivity and the minimum Hellinger distance --- that give us techniques to prove lower bounds on the query complexity. These techniques are quite general, easy to use, yet powerful enough to yield tight results. Our applications include the mean and higher statistical moments, the median and other selection functions, and the frequency moments, where we obtain lower bounds that are close to the corresponding upper bounds. We also point out some connections between sampling and streaming algorithms and lossy compression schemes.
---
paper_title: Keying Hash Functions for Message Authentication

paper_content:

The use of cryptographic hash functions like MD5 or SHA-1 for message authentication has become a standard approach in many applications, particularly Internet security protocols. Though very easy to implement, these mechanisms are usually based on ad hoc techniques that lack a sound security analysis. ::: ::: We present new, simple, and practical constructions of message authentication schemes based on a cryptographic hash function. Our schemes, NMAC and HMAC, are proven to be secure as long as the underlying hash function has some reasonable cryptographic strengths. Moreover we show, in a quantitative way, that the schemes retain almost all the security of the underlying hash function. The performance of our schemes is essentially that of the underlying hash function. Moreover they use the hash function (or its compression function) as a black box, so that widely available library code or hardwair can be used to implement them in a simple way, and replaceability of the underlying hash function is easily supported.
---

Title: Privacy-Preserving Data Aggregation Protocols for Wireless Sensor Networks: A Survey
Section 1: Introduction
Description 1: Introduce the background, importance, features, and applications of wireless sensor networks (WSNs), and discuss the need for privacy-preserving data aggregation.

Section 2: Application Areas
Description 2: Explain major application areas where privacy-preserving data aggregation is critical, such as health monitoring, military surveillance, and private households.

Section 3: PPDA Protocol Designing Principles, Issues and Challenges
Description 3: Discuss the principles, issues, and challenges in designing privacy-preserving data aggregation (PPDA) protocols for WSNs, including eavesdropping, data pollution, efficiency, accuracy, QoS support, idle time, dynamism, and aggregation functions.

Section 4: Classification of PPDA Protocols
Description 4: Present the criteria for classification and provide a detailed classification of existing PPDA protocols based on the techniques used to achieve privacy-preserving data aggregation.

Section 5: Comparative Study of PPDA Protocols
Description 5: Compare the existing PPDA protocols based on various metrics such as communication cost, computation cost, data pollution, privacy support type, delay, memory consumption, data integrity, accuracy, payload size, and energy consumption.

Section 6: Future Directions
Description 6: Outline the potential areas for future research in privacy-preserving data aggregation for WSNs, addressing the current limitations and suggesting new directions for further study.

Section 7: Concluding Remarks
Description 7: Summarize the survey, emphasizing the importance of PPDA protocols, the classification and comparison provided, and the future research directions.