PDA: Privacy-Preserving Data Aggregation for Information Collection

Abstract

Providing efficient data aggregation while preserving data privacy is a challenging problem in wireless sensor networks research. In this article, we present two privacy-preserving data aggregation schemes for additive aggregation functions, which can be extended to approximate MAX/MIN 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.

References

1. Agrawal, R. and Srikant, R. 2000. Privacy preserving data mining. In Proceedings of the ACM SIGMOD Conference on Management of Data. 439--450.
2. Castelluccia, C., Mykletun, E., and Tsudik, G. 2005. Efficient aggregation of encrypted data in wireless sensor networks. In Proceedings of the 2nd Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services.
3. Culler, D., Estrin, D., and Srivastava, M. 2004. Overview of sensor networks. IEEE Computer 37, 8, 41--49.
4. Deshpande, A., Nath, S., Gibbons, P. B., and Seshan, S. 2003. Cache-and-query for wide area sensor databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data.
5. Du, W. and Atallah, M. J. 2001. Secure multi-party computation problems and their applications: A review and open problems. In Proceedings of the 2001 Workshop on New Security Paradigms. ACM Press, New York, NY, 13--22.
6. Eschenauer, L. and Gligor, V. D. 2002. A key-management scheme for distributed sensor networks. In Proceedings of the 9th ACM Conference on Computer and Communications Security. 41--47.
7. Evfimievski, A., Srikant, R., Agrawal, R., and Gehrke, J. 2002. Privacy preserving mining of association rules. In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.
8. Girao, J., Westhoff, D., and Schneider, M. 2005. CDA: Concealed data aggregation for reverse multicast traffic in wireless sensor networks. In Proceedings of the 40th IEEE International Conference on Communications.
9. Halpern, J. and Teague, V. 2004. Rational secret sharing and multiparty computation. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing. 623--632.
10. Han, J. and Liu, Y. 2006. Rumor riding: Anonymizing unstructured peer-to-peer systems. In Proceedings of the 14th International Conference on Network Protocols.
11. Huang, Q., Wang, H. J., and Borisov, N. 2005a. Privacy-preserving friends troubleshooting network. In Proceedings of the Symposium on Network and Distributed Systems Security.
12. Huang, Z., Du, W., and Chen, B. 2005b. Deriving private information from randomized data. In Proceedings of the ACM SIGMOD Conference.
13. Intanagonwiwat, C., Estrin, D., Govindan, R., and Heidemann, J. 2002a. Impact of network density on data aggregation in wireless sensor networks. In Proceedings of the 22nd International Conference on Distributed Computing Systems.
14. Itanagonwiwat, C., Govindan, R., and Estrin, D. 2002b. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In Proceedings of the ACM Annual International Conference on Mobile Computing and Networking.
15. Kantarcioglu, M. and Clifton, C. 2004. Privacy-preserving distributed mining of association rules on horizontally partitioned data. IEEE Trans. Knowl. Data Eng. 16, 9, 1026--1037.
16. Kargupta, H., S. Datta, Q. W., and Sivakumar, K. 2003. On the privacy preserving properties of random data perturbation techniques. In Proceedings of the IEEE International Conference on Data Mining.
17. Li, M. and Liu, Y. 2007. Underground structure monitoring with wireless sensor networks. In Proceedings of the 6th International Symposium on Information Processing in Sensor Networks.
18. Liu, D. and Ning, P. 2003. Establishing pairwise keys in distributed sensor networks. In Proceedings of the 10th ACM Conference on Computer and Communications Security. 52--61.
19. Madden, S., Franklin, M. J., and Hellerstein, J. M. 2002. TAG: A tiny AGgregation Service for ad-hoc sensor networks. In Proceedings of the ACM USENIX Symposium on Operating Systems Design and Implementation.
20. Mainwaring, A., Polastre, J., Szewczyk, R., Culler, D., and Anderson, J. 2002. Wireless sensor networks for habitat monitoring. In Proceedings of the ACM International Workshop on Wireless Sensor Network and Applications.
21. Pinkas, B. 2002. Cryptographic techniques for privacy preserving data mining. SIGKDD Explor. 4, 2, 12--19.
22. Przydatek, B., Song, D., and Perrig, A. 2003. SIA: Secure information aggregation in sensor networks. In Proceedings of the ACM SIGORS International Conference on Embedded Networked Sensor Systems.
23. Ronald Cramer, I. D. and Dziembowski, S. 2000. On the complexity of verifiable secret sharing and multiparty computation. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing. 325--334.
24. Solis, I. and Obraczka, K. 2004. The impact of timing in data aggregation for sensor networks. In Proceedings of the IEEE International Conference on Communications.
25. Tang, X. and Xu, J. 2006. Extending network lifetime for precision-constrained data aggregation in wireless sensor networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies.
26. Wagner, D. 2005. Resilient aggregation in sensor networks. In Proceedings of the 2nd ACM Workshop on Security of Ad Hoc and Sensor Networks.
27. Xu, N., Rangwala, S., Chintalapudi, K., Ganesan, D., Broad, A., Govindan, R., and Estrin, D. 2004. A wireless sensor network for structural monitoring. In Proceedings of the ACM Conference on Embedded Networked Sensor Systems.
28. Yang, Y., Wang, X., Zhu, S., and Cao, G. 2006. SDAP: A secure hop-by-hop data aggregation protocol for sensor networks. In Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing.
29. Yao, A. C. 1982. Protocols for secure computations. In Proceedings of the 23rd IEEE Symposium on the Foundations of Computer Science. 160--164.

Index Terms

• Information systems

  • Information systems applications