Providing freshness guarantees for outsourced databases

ABSTRACT

Database outsourcing becomes increasingly attractive as advances in network technologies eliminate the perceived performance difference between in-house databases and out-sourced databases, and price advantages of third-party data-base service providers continue to increase due to economy of scale. However, the potentially explosive growth of database outsourcing is hampered by security concerns, namely data privacy and query integrity of outsourced databases. While privacy issues of outsourced databases have been extensively studied, query integrity for outsourced databases has just started to draw attention from the database community. Currently, there still does not exist a solution that can provide complete integrity. In particular, previous studies have not examined the mechanisms for providing freshness guarantees, that is, the assurance that queries are executed against the most up-to-date data, instead of just some version of the data in the past. Providing a practical solution for freshness guarantees is challenging because continuously monitoring data's up-to-dateness is expensive. In this paper, we perform a thorough study on how to add freshness guarantees over proposed schemes (including authenticated data structure-based and probabilistic-based approaches) to provide integrity assurance. We implement our solutions and perform extensive experiments to quantify the cost. Our experiment results show that we can provide reasonable tight freshness guarantees without sacrificing much performance.

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: 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]
• 3: Mihir Bellare, Practice-Oriented Provable-Security, Proceedings of the First International Workshop on Information Security, p.221-231, September 17-19, 1997
• 4: Mihir Bellare , Anand Desai , Eron Jokipii , Phillip Rogaway, A Concrete Security Treatment of Symmetric Encryption, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.394, October 19-22, 1997
• 5: 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
• 6: Hakan Hacigümüş , Bala Iyer , Chen Li , Sharad Mehrotra, Executing SQL over encrypted data in the database-service-provider model, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564717]
• 7: Hakan Hacigümüş , Bala Iyer , Chen Li , Sharad Mehrotra, Executing SQL over encrypted data in the database-service-provider model, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564717]
• 8: Hakan Hacigümüs, Sharad Mehrotra, and Balakrishna R. Iyer. Providing database as a service. In ICDE, pages 29-. IEEE Computer Society, 2002.
• 9: Feifei Li, Marios Hadjieleftheriou, George Kollios, and Leonid Reyzin. Authenticated Index Structures Library. http://www.cs.fsu.edu/lifeifei/aisl/index.html.
• 10: 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]
• 11: 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
• 12: Einar Mykletun, Maithili Narasimha, and Gene Tsudik. Authentication and integrity in outsourced databases. In NDSS. The Internet Society, 2004.
• 13: 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]
• 14: 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
• 15: 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

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems