Dynamic authenticated index structures for outsourced databases

ABSTRACT

In outsourced database (ODB)systems the database owner publishes its data through a number of remote servers, with the goal of enabling clients at the edge of the network to access and query the data more efficiently. As servers might be untrusted or can be compromised, query authentication becomes an essential component of ODB systems. Existing solutions for this problem concentrate mostly on static scenarios and are based on idealistic properties for certain cryptographic primitives. In this work, first we define a variety of essential and practical cost metrics associated with ODB systems. Then, we analytically evaluate a number of different approaches, in search for a solution that best leverages all metrics. Most importantly, we look at solutions that can handle dynamic scenarios, where owners periodically update the data residing at the servers. Finally, we discuss query freshness, a new dimension in data authentication that has not been explored before. A comprehensive experimental evaluation of the proposed and existing approaches is used to validate the analytical models and verify our claims. Our findings exhibit that the proposed solutions improve performance substantially over existing approaches, both for static and dynamic environments.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Privacy-preserving data mining, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.439-450, May 15-18, 2000, Dallas, Texas, United States
• 2: [2] Authenticated Index Structures Library. http://cs-people.bu.edu/lifeifei/aisl/.
• 3: Elisa Bertino , Barbara Carminati , Elena Ferrari , Bhavani Thuraisingham , Amar Gupta, Selective and Authentic Third-Party Distribution of XML Documents, IEEE Transactions on Knowledge and Data Engineering, v.16 n.10, p.1263-1278, October 2004 [doi>10.1109/TKDE.2004.63]
• 4: Luc Bouganim , Cosmin Cremarenco , François Dang Ngoc , Nicolas Dieu , Philippe Pucheral, Safe data sharing and data dissemination on smart devices, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066276]
• 5: [5] L. Bouganim, F. D. Ngoc, P. Pucheral, and L. Wu. Chip-secured data access: Reconciling access rights with data encryption. In Proc. of Very Large Data Bases (VLDB), pages 1133-1136, 2003.
• 6: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 7: [7] Crypto++ Library. http://www.eskimo.com/~weidai/cryptlib.html.
• 8: Premkumar Devanbu , Michael Gertz , Charles Martel , Stuart G. Stubblebine, Authentic data publication over the internet, Journal of Computer Security, v.11 n.3, p.291-314, 1 March 2003
• 9: 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
• 10: Alexandre Evfimievski , Johannes Gehrke , Ramakrishnan Srikant, Limiting privacy breaches in privacy preserving data mining, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.211-222, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773174]
• 11: 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]
• 12: 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]
• 13: Providing Database as a Service, Proceedings of the 18th International Conference on Data Engineering, p.29, February 26-March 01, 2002
• 14: [14] B. Hore, S. Mehrotra, and G. Tsudik. A privacy-preserving index for range queries. In Proc. of Very Large Data Bases (VLDB), pages 720-731, 2004.
• 15: [15] F. Li, M. Hadjieleftheriou, G. Kollios, and L. Reyzin. Authenticated Index Structures for Outsourced Database Systems. Technical Report BUCS-TR_2006-004, CS Department, Boston University, 2006.
• 16: 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]
• 17: [17] K. McCurley. The discrete logarithm problem. In Proc. of the Symposium in Applied Mathematics, pages 49-74. American Mathematical Society, 1990.
• 18: 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
• 19: S. Micali, Efficient Certificate Revocation, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 20: [20] G. Miklau and D. Suciu. Controlling access to published data using cryptography. In Proc. of Very Large Data Bases (VLDB), pages 898-909, 2003.
• 21: [21] E. Mykletun, M. Narasimha, and G. Tsudik. Authentication and integrity in outsourced databases. In Symposium on Network and Distributed Systems Security (NDSS), 2004.
• 22: [22] E. Mykletun, M. Narasimha, and G. Tsudik. Signature bouquets: Immutability for aggregated/condensed signatures. In European Symposium on Research in Computer Security (ESORICS), pages 160-176, 2004.
• 23: 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]
• 24: [24] National Institute of Standards and Technology. FIPS PUB 180-1: Secure Hash Standard. National Institute of Standards and Technology, 1995.
• 25: [25] OpenSSL. http://www.openssl.org.
• 26: 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]
• 27: 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
• 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: Shariq Rizvi , Alberto Mendelzon , S. Sudarshan , Prasan Roy, Extending query rewriting techniques for fine-grained access control, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007631]
• 30: 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
• 31: [31] R. Tamassia and N. Triandopoulos. Efficient Content Authentication over Distributed Hash Tables. Technical report, CS Department, Brown University, 2005.

INDEX TERMS

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

General Terms:
Algorithms, Performance, Security

Keywords:
authentication, cryptography, indexing, merkle trees, outsourced databases