Balancing confidentiality and efficiency in untrusted relational DBMSs

ABSTRACT

The scope and character of today's computing environments are progressively shifting from traditional, one-on-one client-server interaction to the new cooperative paradigm. It then becomes of primary importance to provide means of protecting the secrecy of the information, while guaranteeing its availability to legitimate clients. Operating on-line querying services securely on open networks is very difficult; therefore many enterprises outsource their data center operations to external application service providers. A promising direction towards prevention of unauthorized access to outsourced data is represented by encryption. However, data encryption is often supported for the sole purpose of protecting the data in storage and assumes trust in the server, that decrypts data for query execution.In this paper, we present a simple yet robust single-server solution for remote querying of encrypted databases on untrusted servers. Our approach is based on the use of indexing information attached to the encrypted database which can be used by the server to select the data to be returned in response to a query without the need of disclosing the database content. Our indexes balance the trade off between efficiency requirements in query execution and protection requirements due to possible inference attacks exploiting indexing information. We also investigate quantitative measures to model inference exposure and provide some related experimental results.

REFERENCES

• 1: L. Bouganim and P. Pucheral. Chip-secured data access: Confidential data on untrusted servers. In Proc. of the 28th International Conference on Very Large Data Bases, pages 131--142, Hong Kong, China, August 2002.
• 2: S. Ceri , M. Negri , G. Pelagatti, Horizontal data partitioning in database design, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582376]
• 3: Han‐Chieh Chao , T. Y. Wu , Jiann‐Liang Chen, Security‐enhanced packet video with dynamic multicast throughput adjustment, International Journal of Network Management, v.11 n.3, p.147-159, May 10, 2001 [doi>10.1002/nem.398 ]
• 4: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 5: George I. Davida , David L. Wells , John B. Kam, A database encryption system with subkeys, ACM Transactions on Database Systems (TODS), v.6 n.2, p.312-328, June 1981 [doi>10.1145/319566.319580]
• 6: Dorothy Elizabeth Rob Denning, Cryptography and Data Security, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 7: Shahram Ghandeharizadeh , David J. DeWitt, A Multiuser Performance Analysis of Alternative Declustering Strategies, Proceedings of the Sixth International Conference on Data Engineering, p.466-475, February 05-09, 1990
• 8: 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]
• 9: Providing Database as a Service, Proceedings of the 18th International Conference on Data Engineering, p.29, February 26-March 01, 2002
• 10: Christian D. Jensen, CryptoCache: a secure sharable file cache for roaming users, Proceedings of the 9th workshop on ACM SIGOPS European workshop: beyond the PC: new challenges for the operating system, September 17-20, 2000, Kolding, Denmark [doi>10.1145/566726.566744]
• 11: Shmuel T. Klein , Abraham Bookstein , Scott Deerwester, Storing text retrieval systems on CD-ROM: compression and encryption considerations, ACM Transactions on Information Systems (TOIS), v.7 n.3, p.230-245, July 1989 [doi>10.1145/65943.65946]
• 12: B.D. McKay. Practical graph isomorphism. Congressus Numerantium, 30:45--87, 1981.
• 13: P. Samarati, Protecting Respondents' Identities in Microdata Release, IEEE Transactions on Knowledge and Data Engineering, v.13 n.6, p.1010-1027, November 2001 [doi>10.1109/69.971193 ]
• 14: Dawn Xiaodong Song , David Wagner , Adrian Perrig, Practical Techniques for Searches on Encrypted Data, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.44, May 14-17, 2000
• 15: Jinx P. Walton, Developing an enterprise information security policy, Proceedings of the 30th annual ACM SIGUCCS conference on User services, p.153-156, November 20-23, 2002, Providence, Rhode Island, USA [doi>10.1145/588646.588678]
• 16: Julie Ward , Michael O'Sullivan , Troy Shahoumian , John Wilkes, Appia: Automatic Storage Area Network Fabric Design, Proceedings of the Conference on File and Storage Technologies, p.203-217, January 28-30, 2002
• 17: Erica Y. Yang , Jie Xu , Keith H. Bennett, Private Information Retrieval in the Presence of Malicious Failures, Proceedings of the 26th International Computer Software and Applications Conference on Prolonging Software Life: Development and Redevelopment, p.805-812, August 26-19, 2002

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

General Terms:
Design, Security

Keywords:
cryptography, database service, indexing