Secure outsourced aggregation via one-way chains

ABSTRACT

We consider the Outsourced Aggregation model, where sensing services outsource their sensor data collection and aggregation tasks to third-party service providers called aggregators. As aggregators can be untrusted or compromised, it is essential for a sensing service to be able to verify the correctness of aggregation results. This work presents SECOA, a framework with a family of novel and optimally-secure protocols for secure outsourced aggregation. Our framework is based on a unified use of one-way chains. It supports a large and diverse set of aggregate functions, can have multiple hierarchically organized aggregators, can deterministically detect any malicious aggregation behavior without communication with sensors, and incurs a small and workload-independent communication load on sensors. We also present extensive evaluation results to demonstrate the feasibility of our framework.

REFERENCES

• 1: Speed comparison of popular crypto algorithms. http://www.cryptopp.com/benchmarks.html 2008.
• 2: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, v.58 n.1, p.137-147, Feb. 1999 [doi>10.1006/jcss.1997.1545]
• 3: Ziv Bar-Yossef , T. S. Jayram , Ravi Kumar , D. Sivakumar , Luca Trevisan, Counting Distinct Elements in a Data Stream, Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, p.1-10, September 13-15, 2002
• 4: Bellare, M., Garay, J., and Rabin, T. Fast batch verification for modular exponentiation and digital signatures. In Eurocrypt (1998).
• 5: Haowen Chan , Adrian Perrig , Bartosz Przydatek , Dawn Song, SIA: Secure information aggregation in sensor networks, Journal of Computer Security, v.15 n.1, p.69-102, January 2007
• 6: 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]
• 7: Jeffrey Considine , Feifei Li , George Kollios , John Byers, Approximate Aggregation Techniques for Sensor Databases, Proceedings of the 20th International Conference on Data Engineering, p.449, March 30-April 02, 2004
• 8: Cormode, G., and Muthukrishnan, S. An improved data stream summary: The count-min sketch and its applications. LATIN 2004: Theoretical Informatics (2004), 29--38.
• 9: Amol Deshpande , Suman Nath , Phillip B. Gibbons , Srinivasan Seshan, Cache-and-query for wide area sensor databases, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872818]
• 10: Philippe Flajolet , G. Nigel Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, v.31 n.2, p.182-209, Sept. 1985 [doi>10.1016/0022-0000(85)90041-8]
• 11: Garofalakis, M., Hellerstein, J., and Maniatis, P. Proof sketches: Verifiable in-network aggregation. In ICDE (2007).
• 12: Aman Kansal , Suman Nath , Jie Liu , Feng Zhao, SenseWeb: An Infrastructure for Shared Sensing, IEEE MultiMedia, v.14 n.4, p.8-13, October 2007 [doi>10.1109/MMUL.2007.82]
• 13: Feifei Li , Marios Hadjieleftheriou , George Kollios , Leonid Reyzin, Dynamic authenticated index structures for outsourced databases, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142488]
• 14: Mykletun, E., Narasimha, M., and Tsudik, G. Signature bouquets: Immutability for aggregated/condensed signatures. In ESORICS (2004).
• 15: Einar Mykletun , Maithili Narasimha , Gene Tsudik, Authentication and integrity in outsourced databases, ACM Transactions on Storage (TOS), v.2 n.2, p.107-138, May 2006 [doi>10.1145/1149976.1149977]
• 16: Maithili Narasimha , Gene Tsudik, DSAC: integrity for outsourced databases with signature aggregation and chaining, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099604]
• 17: Suman Nath , Phillip B. Gibbons , Srinivasan Seshan , Zachary Anderson, Synopsis diffusion for robust aggregation in sensor networks, ACM Transactions on Sensor Networks (TOSN), v.4 n.2, p.1-40, March 2008 [doi>10.1145/1340771.1340773]
• 18: 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 [doi>10.1145/1031495.1031525]
• 19: Nuckolls, G. Verified query results from hybrid authentication trees. In Data and Applications Security (DBSec) (2005).
• 20: HweeHwa Pang , Arpit Jain , Krithi Ramamritham , Kian-Lee Tan, Verifying completeness of relational query results in data publishing, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066204]
• 21: Hweehwa Pang , Kian-Lee Tan, Verifying Completeness of Relational Query Answers from Online Servers, ACM Transactions on Information and System Security (TISSEC), v.11 n.2, p.1-50, March 2008 [doi>10.1145/1330332.1330337]
• 22: HweeHwa Pang , Kian-Lee Tan, Authenticating Query Results in Edge Computing, Proceedings of the 20th International Conference on Data Engineering, p.560, March 30-April 02, 2004
• 23: 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]
• 24: Simmons, G. J. weak privacy protocol using the RSA crypto algorithm. Cryptologia 7 2 (1983), 180--182.
• 25: Radu Sion, Query execution assurance for outsourced databases, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 26: 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]
• 27: Haifeng Yu, Secure and highly-available aggregation queries in large-scale sensor networks via set sampling, Proceedings of the 2009 International Conference on Information Processing in Sensor Networks, p.1-12, April 13-16, 2009

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General
          Subjects: Security, integrity, and protection**

General Terms:
Algorithms, Security

Keywords:
secure outsourced aggregation, wide-area sensing