Ensuring correctness over untrusted private database

ABSTRACT

In this paper we address the problem of ensuring the correctness of query results returned by an untrusted private database. The database owns the data and may modify it at any time. The querier is allowed to execute queries over this database; however it may not learn anything more than the result of these legal queries. The querier does not necessarily trust the database and would like the owner to furnish proof that the data has not been modified in response to recent events such as the submission of the query. We develop two metrics that capture the correctness of query answers and propose a range of solutions that provide a trade-off between the degree of exposure of private data, and the overhead of generation and verification of the proof. Our proposed solutions are tested on real data through implementation using PostgreSQL.

REFERENCES

• 1: G. Aggarwal , M. Bawa , P. Ganesan , H. Garcia-Molina , K. Kenthapadi , N. Mishra , R. Motwani , U. Srivastava , D. Thomas , J. Widom , Y. Xu, Vision paper: enabling privacy for the paranoids, Proceedings of the Thirtieth international conference on Very large data bases, p.708-719, August 31-September 03, 2004, Toronto, Canada
• 2: S. Agrawal, V. Krishnan, and J. R. Haritsa. On addressing efficiency concerns in privacy-preserving mining. In Proceedings of Database Systems for Advanced Applications, 2004.
• 3: P. Devanbu , M. Gertz , A. Kwong , C. Martel , G. Nuckolls , S. G. Stubblebine, Flexible authentication of XML documents, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502003]
• 4: 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
• 5: Alexandre Evfimievski , Ramakrishnan Srikant , Rakesh Agarwal , Johannes Gehrke, Privacy preserving mining of association rules, Information Systems, v.29 n.4, p.343-364, June 2004 [doi>10.1016/j.is.2003.09.001]
• 6: M. Gertz, A. Kwong, C. Martel, G. Nuckolls, P. Devanbu, and S. Stubblebine. Databases that tell the truth: Authentic data publication. Bulletin of the Technical Committee on Data Engineering, 7(1), 2004.
• 7: Providing Database as a Service, Proceedings of the 18th International Conference on Data Engineering, p.29, February 26-March 01, 2002
• 8: Bijit Hore , Sharad Mehrotra , Gene Tsudik, A privacy-preserving index for range queries, Proceedings of the Thirtieth international conference on Very large data bases, p.720-731, August 31-September 03, 2004, Toronto, Canada
• 9: Murat Kantarcioglu , Chris Clifton, Privacy-Preserving Distributed Mining of Association Rules on Horizontally Partitioned Data, IEEE Transactions on Knowledge and Data Engineering, v.16 n.9, p.1026-1037, September 2004 [doi>10.1109/TKDE.2004.45]
• 10: 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
• 11: 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
• 12: PostgreSQL. http://www.postresql.org.
• 13: B. Preneel. Analysis and Design of Cryptographic Hash Functions. PhD thesis, Katholieke University Leuven, 1993.
• 14: O. Project. http://www.openssl.org.
• 15: Richard T. Snodgrass , Shilong Stanley Yao , Christian Collberg, Tamper detection in audit logs, Proceedings of the Thirtieth international conference on Very large data bases, p.504-515, August 31-September 03, 2004, Toronto, Canada

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General

          Nouns: POSTGRES
      H.2.4 Systems
          Subjects: Query processing

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.1 Public Policy Issues
          Subjects: Privacy

General Terms:
Security