Authenticated join processing in outsourced databases

ABSTRACT

Database outsourcing requires that a query server constructs a proof of result correctness, which can be verified by the client using the data owner's signature. Previous authentication techniques deal with range queries on a single relation using an authenticated data structure (ADS). On the other hand, authenticated join processing is inherently more complex than ranges since only the base relations (but not their combination) are signed by the owner. In this paper, we present three novel join algorithms depending on the ADS availability: (i) Authenticated Indexed Sort Merge Join (AISM), which utilizes a single ADS on the join attribute, (ii) Authenticated Index Merge Join (AIM) that requires an ADS (on the join attribute) for both relations, and (iii) Authenticated Sort Merge Join (ASM), which does not rely on any ADS. We experimentally demonstrate that the proposed methods outperform two benchmark algorithms, often by several orders of magnitude, on all performance metrics, and effectively shift the workload to the outsourcing service. Finally, we extend our techniques to complex queries that combine multi-way joins with selections and projections.

REFERENCES

• 1: Rakesh Agrawal , Jerry Kiernan , Ramakrishnan Srikant , Yirong Xu, Order preserving encryption for numeric data, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007632]
• 2: Nicolas Anciaux , Mehdi Benzine , Luc Bouganim , Philippe Pucheral , Dennis Shasha, GhostDB: querying visible and hidden data without leaks, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247555]
• 3: Mikhail J. Atallah , YounSun Cho , Ashish Kundu, Efficient Data Authentication in an Environment of Untrusted Third-Party Distributors, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.696-704, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497478]
• 4: Shivnath Babu , Pedro Bizarro , David DeWitt, Proactive re-optimization, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066171]
• 5: Ernesto Damiani , S. De Capitani Vimercati , Sushil Jajodia , Stefano Paraboschi , Pierangela Samarati, Balancing confidentiality and efficiency in untrusted relational DBMSs, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948124]
• 6: Premkumar T. Devanbu , Michael Gertz , Charles U. Martel , Stuart G. Stubblebine, Authentic Third-party Data Publication, Proceedings of the IFIP TC11/ WG11.3 Fourteenth Annual Working Conference on Database Security: Data and Application Security, Development and Directions, p.101-112, August 21-23, 2000
• 7: Tingjian Ge , Stan Zdonik, Light-Weight, Runtime Verification of Query Sources, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.30-41, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.40]
• 8: Hac1gümüş, H., Iyer, B., Mehrotra, S. Providing Databases as a Service. ICDE, 2002.
• 9: http://www.openssl.org
• 10: Ryan Huebsch , Joseph M. Hellerstein , Nick Lanham , Boon Thau Loo , Scott Shenker , Ion Stoica, Querying the internet with PIER, Proceedings of the 29th international conference on Very large data bases, p.321-332, September 09-12, 2003, Berlin, Germany
• 11: Ashish Kundu , Elisa Bertino, Structural signatures for tree data structures, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453876]
• 12: 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]
• 13: Feifei Li , Ke Yi , Marios Hadjieleftheriou , George Kollios, Proof-infused streams: enabling authentication of sliding window queries on streams, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 14: Qiong Luo , Sailesh Krishnamurthy , C. Mohan , Hamid Pirahesh , Honguk Woo , Bruce G. Lindsay , Jeffrey F. Naughton, Middle-tier database caching for e-business, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564763]
• 15: Charles Martel , Glen Nuckolls , Premkumar Devanbu , Michael Gertz , April Kwong , Stuart G. Stubblebine, A General Model for Authenticated Data Structures, Algorithmica, v.39 n.1, p.21-41, January 2004 [doi>10.1007/s00453-003-1076-8]
• 16: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 17: Ralph C. Merkle, A Certified Digital Signature, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.218-238, August 20-24, 1989
• 18: Narasimha M., Tsudik G. Authentication of Outsourced Databases Using Signature Aggregation and Chaining. DASFAA, 2006.
• 19: 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]
• 20: 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
• 21: Stavros Papadopoulos , Yin Yang , Dimitris Papadias, CADS: continuous authentication on data streams, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 22: Vijayshankar Raman , Lin Qiao , Wei Han , Inderpal Narang , Ying-Lin Chen , Kou-Horng Yang , Fen-Ling Ling, Lazy, adaptive rid-list intersection, and its application to index anding, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247566]
• 23: 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
• 24: Min Xie , Haixun Wang , Jian Yin , Xiaofeng Meng, Integrity auditing of outsourced data, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 25: Yin Yang , Stavros Papadopoulos , Dimitris Papadias , George Kollios, Spatial Outsourcing for Location-based Services, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.1082-1091, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497517]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Experimentation, Security

Keywords:
database outsourcing, join algorithms, query authentication