Reverse tree-based key routing: Robust data aggregation in wireless sensor networks

Efficient and privacy-preserving data aggregation in a wireless sensor network (WSN) poses a tremendous challenge: how to cope with sensors compromise---once a sensor is compromised, its crypto material is compromised and so is privacy of aggregate data. To address this challenge, we propose two operationally simple and privacy-preserving protocols: PASKOS (Privacy-preserving based on Anonymously Shared Keys and Omniscient Sink) and PASKIS (Privacy-preserving based on Anonymously Shared Keys and Ignorant Sink). They leverage the idea that each node adds to its private sensed value a keyed value (computed from anonymously shared keys) and only uses the resulting sum in the data aggregation process. Our protocols guarantee that the sink is able to efficiently retrieve the aggregated original data by removing keyed values from the received aggregate while preserving the privacy of the aggregated data. Further, both protocols guarantee a high {\em data-loss resilience}---the sink retrieves the aggregate of the sensed values of only those nodes who actually participated in the aggregation process. PASKOS effectively protects the privacy of any node against other nodes, by requiring O(logN) communication cost in the worst case and O(1) on average, and requiring O(1) memory and computation cost. PASKIS can even protect a node's privacy against a compromised sink, and it is more efficient, requiring only O(1) overhead as for computation, communication, and memory; however, these gains in efficiency are traded-off with a (slightly) decreased level of privacy. Through formal analysis and simulations, we demonstrate the superior performance of our protocols against existing solutions in terms of privacy-preserving effectiveness, efficiency, and accuracy of computed aggregation.