Efficient and provably secure aggregation of encrypted data in wireless sensor networks

ABSTRACT

Wireless sensor networks (WSNs) are composed of tiny devices with limited computation and battery capacities. For such resource-constrained devices, data transmission is a very energy-consuming operation. To maximize WSN lifetime, it is essential to minimize the number of bits sent and received by each device. One natural approach is to aggregate sensor data along the path from sensors to the sink. Aggregation is especially challenging if end-to-end privacy between sensors and the sink (or aggregate integrity) is required. In this article, we propose a simple and provably secure encryption scheme that allows efficient additive aggregation of encrypted data. Only one modular addition is necessary for ciphertext aggregation. The security of the scheme is based on the indistinguishability property of a pseudorandom function (PRF), a standard cryptographic primitive. We show that aggregation based on this scheme can be used to efficiently compute statistical values, such as mean, variance, and standard deviation of sensed data, while achieving significant bandwidth savings. To protect the integrity of the aggregated data, we construct an end-to-end aggregate authentication scheme that is secure against outsider-only attacks, also based on the indistinguishability property of PRFs.

REFERENCES

• 1: Mihir Bellare , Ran Canetti , Hugo Krawczyk, Keying Hash Functions for Message Authentication, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.1-15, August 18-22, 1996
• 2: Boneh, D., Gentry, C., Lynn, B., and Shacham, H. 2003. Aggregate and verifiably encrypted signatures from bilinear maps. In Proceedings of Advances in Cryptology (EUROCRYPT'03). Lecture Notes in Computer Science, vol. 2656, 416--432.
• 3: Levente Buttyán , Péter Schaffer , István Vajda, RANBAR: RANSAC-based resilient aggregation in sensor networks, Proceedings of the fourth ACM workshop on Security of ad hoc and sensor networks, October 30-30, 2006, Alexandria, Virginia, USA [doi>10.1145/1180345.1180356]
• 4: Claude Castelluccia , Einar Mykletun , Gene Tsudik, E.cient Aggregation of encrypted data in Wireless Sensor Networks, Proceedings of the The Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, p.109-117, July 17-21, 2005 [doi>10.1109/MOBIQUITOUS.2005.25]
• 5: Castelluccia, C. and Soriente, C. 2008. ABBA: Secure aggregation in WSNS - a bins and balls approach. In Proceedings of the 6th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt).
• 6: Aldar C. Chan , Claude Castelluccia, On the Privacy of Concealed Data Aggregation, Proceedings of the 12th European symposium on Research In Computer Security, September 24-26, 2007, Dresden, Germany [doi>10.1007/978-3-540-74835-9_26]
• 7: Chan, A. C.-F. and Castelluccia, C. 2008. On the (im)possibility of aggregate message authentication codes. In Proceedings of the IEEE International Symposium on Information Theory (ISIT).
• 8: Haowen Chan , Adrian Perrig , Dawn Song, Secure hierarchical in-network aggregation in sensor networks, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180440]
• 9: Laurent Eschenauer , Virgil D. Gligor, A key-management scheme for distributed sensor networks, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586117]
• 10: Girao, J., Westhoff, D., and Schneider, M. 2004. CDA: Concealed data aggregation in wireless sensor networks. In Proceedings of the ACM Conference on Web Information Systems (WiSe).
• 11: Oded Goldreich, Foundations of Cryptography: Volume 1, Cambridge University Press, New York, NY, 2006
• 12: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 13: Goldwasser, S. and Micali, S. 1984. Probabilistic encryption. J. Comput. Syst. Sci. 28, 2, 270--299.
• 14: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 15: Lingxuan Hu , David Evans, Secure Aggregation for Wireless Networks, Proceedings of the 2003 Symposium on Applications and the Internet Workshops (SAINT'03 Workshops), p.384, January 27-31, 2003
• 16: Iwata, T. and Kurosawa, K. 2003. OMAC: One-key CBC MAC. In Proceedings of Fast Software Encryption (FSE'03). Lecture Notes in Computer Science, vol. 2887, 129--153.
• 17: Chris Karlof , Naveen Sastry , David Wagner, TinySec: a link layer security architecture for wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031515]
• 18: Karlof, C. and Wagner, D. 2003. Secure routing in wireless sensor networks: Attacks and countermeasures. In Proceedings of the IEEE Workshop on Sensor Network Protocols and Applications.
• 19: Jonathan Katz , Moti Yung, Characterization of Security Notions for Probabilistic Private-Key Encryption, Journal of Cryptology, v.19 n.1, p.67-95, January 2006 [doi>10.1007/s00145-005-0310-8]
• 20: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060303]
• 21: Moni Naor , Omer Reingold , Alon Rosen, Pseudorandom Functions and Factoring, SIAM Journal on Computing, v.31 n.5, p.1383-1404, 2002 [doi>10.1137/S0097539701389257]
• 22: M. Naor , M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.427-437, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100273]
• 23: NIST. 2001. Advanced encryption standard. National Institute of Standards and Technology. FIPS PUB 197.
• 24: Adrian Perrig , John Stankovic , David Wagner, Security in wireless sensor networks, Communications of the ACM, v.47 n.6, June 2004 [doi>10.1145/990680.990707]
• 25: Adrian Perrig , Robert Szewczyk , Victor Wen , David Culler , J. D. Tygar, SPINS: security protocols for sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.189-199, July 2001, Rome, Italy [doi>10.1145/381677.381696]
• 26: Bartosz Przydatek , Dawn Song , Adrian Perrig, SIA: secure information aggregation in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958521]
• 27: Rivest, R. L. 1995. The RC5 encryption algorithm. Dr. Dobb's J. 1008.
• 28: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 29: Vernam, G. S. 1926. Cipher printing telegraph systems for secret wire and radio telegraphic communications. J. Amer. Inst. Elect. Eng. 45, 105--115.
• 30: David Wagner, Resilient aggregation in sensor networks, Proceedings of the 2nd ACM workshop on Security of ad hoc and sensor networks, October 25-25, 2004, Washington DC, USA [doi>10.1145/1029102.1029116]
• 31: Dirk Westhoff , Joao Girao , Mithun Acharya, Concealed Data Aggregation for Reverse Multicast Traffic in Sensor Networks: Encryption, Key Distribution, and Routing Adaptation, IEEE Transactions on Mobile Computing, v.5 n.10, p.1417-1431, October 2006 [doi>10.1109/TMC.2006.144]
• 32: Anthony D. Wood , John A. Stankovic, Denial of Service in Sensor Networks, Computer, v.35 n.10, p.54-62, October 2002 [doi>10.1109/MC.2002.1039518]
• 33: Yi Yang , Xinran Wang , Sencun Zhu , Guohong Cao, SDAP: a secure hop-by-Hop data aggregation protocol for sensor networks, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132944]
• 34: Zhu, S., Setia, S., Jajodia, S., and Ning, P. 2004. An interleaved hop-by-hop authentication scheme for filtering false data in sensor networks. In Proceedings of the IEEE Symposium on Security and Privacy.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

General Terms:
Design, Security

Keywords:
Authentication, cryptography, privacy, pseudorandom functions, secure data aggregation, stream ciphers, wireless sensor networks