|
ABSTRACT
Sensor networks promise viable solutions to many monitoring problems. However, the practical deployment of sensor networks faces many challenges imposed by real-world demands. Sensor nodes often have limited computation and communication resources and battery power. Moreover, in many applications sensors are deployed in open environments, and hence are vulnerable to physical attacks, potentially compromising the sensor's cryptographic keys.One of the basic and indispensable functionalities of sensor networks is the ability to answer queries over the data acquired by the sensors. The resource constraints and security issues make designing mechanisms for information aggregation in large sensor networks particularly challenging.In this paper, we propose a novel framework for secure information aggregation in large sensor networks. In our framework certain nodes in the sensor network, called aggregators, help aggregating information requested by a query, which substantially reduces the communication overhead. By constructing efficient random sampling mechanisms and interactive proofs, we enable the user 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 the average of the measurements, for the estimation of the network size, and for finding the minimum and maximum sensor reading. Our protocols require only sublinear communication between the aggregator and the user. To the best of our knowledge, this paper is the first on secure information aggregation in sensor networks that can handle a malicious aggregator and sensor nodes.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
 |
1
|
Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States
[doi> 10.1145/237814.237823]
|
 |
2
|
László Babai , Lance Fortnow , Leonid A. Levin , Mario Szegedy, Checking computations in polylogarithmic time, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.21-32, May 05-08, 1991, New Orleans, Louisiana, United States
[doi> 10.1145/103418.103428]
|
 |
3
|
|
| |
4
|
|
| |
5
|
|
| |
6
|
Mihir Bellare and Bennet Yee. Forward security in private key cryptography. Report 2001035, Cryptology ePrint Archive, 2001.
|
| |
7
|
Christian Cachin, Silvio Micali, and Markus Stadler. Computationally private information retrieval with polylogarithmic communication. In Proc. Eurocrypt'99, pages 402--414, 1999.
|
| |
8
|
|
 |
9
|
Moses Charikar , Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, Towards estimation error guarantees for distinct values, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.268-279, May 15-18, 2000, Dallas, Texas, United States
[doi> 10.1145/335168.335230]
|
 |
10
|
|
| |
11
|
|
 |
12
|
Funda Ergün , Ravi Kumar , Ronitt Rubinfeld, Fast approximate PCPs, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.41-50, May 01-04, 1999, Atlanta, Georgia, United States
[doi> 10.1145/301250.301267]
|
 |
13
|
Deborah Estrin , Ramesh Govindan , John Heidemann , Satish Kumar, Next century challenges: scalable coordination in sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.263-270, August 15-19, 1999, Seattle, Washington, United States
[doi> 10.1145/313451.313556]
|
| |
14
|
P. Flajolet and G. N. Martin. Probabilistic counting. In Proc. FOCS'83, pages 76--82, 1983.
|
| |
15
|
Lingxuan Hu and David Evans. Secure aggregation for wireless networks. In Workshop on Security and Assurance in Ad hoc Networks, January 2003.
|
| |
16
|
C. Intanagonwiwat, D. Estrin, R. Govindan, and J. Heidemann. Impact of network density on data aggregation in wireless sensor networks. In Proceedings of International Conference on Distributed Computing Systems, November 2001.
|
 |
17
|
J. M. Kahn , R. H. Katz , K. S. J. Pister, Next century challenges: mobile networking for “Smart Dust”, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.271-278, August 15-19, 1999, Seattle, Washington, United States
[doi> 10.1145/313451.313558]
|
| |
18
|
|
 |
19
|
|
 |
20
|
|
 |
21
|
|
| |
22
|
Ralph C. Merkle. Protocols for public key cryptosystems. In Proceedings of the IEEE Symposium on Research in Security and Privacy, pages 122--134, April 1980.
|
| |
23
|
|
| |
24
|
Adrian Perrig, Ran Canetti, J. D. Tygar, and Dawn Song. The TESLA broadcast authentication protocol. RSA CryptoBytes, 5(Summer), 2002.
|
| |
25
|
|
| |
26
|
Mark N. Wegman and J. Lawrence Carter. New hash functions and their use in authentication and set equality. JCSS, 22:265--279, 1981.
|
| |
27
|
Jerry Zhao, Ramesh Govindan, and Deborah Estrin. Computing aggregates for monitoring wireless sensor networks. In First IEEE International Workshop on Sensor Network Protocols and Applications, May 2003.
|
CITED BY 72
|
|
Nisheeth Shrivastava , Chiranjeeb Buragohain , Divyakant Agrawal , Subhash Suri, Medians and beyond: new aggregation techniques for sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA
|
|
|
|
|
|
|
|
|
Suman Nath , Phillip B. Gibbons , Srinivasan Seshan , Zachary R. Anderson, Synopsis diffusion for robust aggregation in sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA
|
|
|
|
|
|
Hao Yang , Fan Ye , Yuan Yuan , Songwu Lu , William Arbaugh, Toward resilient security in wireless sensor networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Majid Sarrafzadeh , Foad Dabiri , Roozbeh Jafari , Tammara Massey , Ani Nahapetan, Low power light-weight embedded systems, Proceedings of the 2006 international symposium on Low power electronics and design, October 04-06, 2006, Tegernsee, Bavaria, Germany
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eric Sabbah , Adnan Majeed , Kyoung-Don Kang , Ke Liu , Nael Abu-Ghazaleh, An application-driven perspective on wireless sensor network security, Proceedings of the 2nd ACM international workshop on Quality of service & security for wireless and mobile networks, October 02-02, 2006, Terromolinos, Spain
|
|
|
|
|
|
|
|
|
Fabio Picconi , Nishkam Ravi , Marco Gruteser , Liviu Iftode, Probabilistic validation of aggregated data in vehicular ad-hoc networks, Proceedings of the 3rd international workshop on Vehicular ad hoc networks, September 29-29, 2006, Los Angeles, CA, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Rabia Riaz , Ayesha Naureen , Attiya Akram , Ali Hammad Akbar , Ki-Hyung Kim , H. Farooq Ahmed, A unified security framework with three key management schemes for wireless sensor networks, Computer Communications, v.31 n.18, p.4269-4280, December, 2008
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Leonardo B. Oliveira , Adrian Ferreira , Marco A. Vilaça , Hao Chi Wong , Marshall Bern , Ricardo Dahab , Antonio A. F. Loureiro, SecLEACH-On the security of clustered sensor networks, Signal Processing, v.87 n.12, p.2882-2895, December, 2007
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Idris M. Atakli , Hongbing Hu , Yu Chen , Wei Shinn Ku , Zhou Su, Malicious node detection in wireless sensor networks using weighted trust evaluation, Proceedings of the 2008 Spring simulation multiconference, April 14-17, 2008, Ottawa, Canada
|
|
|
|
|
|
Jorge Guajardo , Boris Škorić , Pim Tuyls , Sandeep S. Kumar , Thijs Bel , Antoon H. Blom , Geert-Jan Schrijen, Anti-counterfeiting, key distribution, and key storage in an ambient world via physical unclonable functions, Information Systems Frontiers, v.11 n.1, p.19-41, March 2009
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|