Modeling and assessing inference exposure in encrypted databases

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 online 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 toward 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 while allowing access to plaintext values by the server, which decrypts data for query execution. In this paper, we present a simple yet robust single-server solution for remote querying of encrypted databases on external 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 accessing the plaintext 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 investigate quantitative measures to model inference exposure and provide some related experimental results.

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: Bouganim, L. and Pucheral, P. 2002. Chip-secured data access: Confidential data on untrusted servers. In Proceedings of the 28th International Conference on Very Large Data Bases, Hong Kong, China. Morgan Kaufmann, San Mateo, CA, 131--142.
• 3: Boyens, C. and Günter, O. 2003. Using online services in untrusted environments---a privacy-preserving architecture. In Proceedings of the 11th European Conference on Information Systems (ECIS '03), Naples, Italy.
• 4: Alberto Caprara , Hans Kellerer , Ulrich Pferschy, A PTAS for the Multiple Subset Sum Problem with different knapsack capacities, Information Processing Letters, v.73 n.3-4, p.111-118, Feb.29.2000 [doi>10.1016/S0020-0190(00)00010-7]
• 5: Alberto Caprara , Hans Kellerer , Ulrich Pferschy, A 3/4-Approximation Algorithm for Multiple Subset Sum, Journal of Heuristics, v.9 n.2, p.99-111, March 2003 [doi>10.1023/A:1022584312032]
• 6: L. P. Cordella , P. Foggia , C. Sansone , M. Vento, Performance Evaluation of the VF Graph Matching Algorithm, Proceedings of the 10th International Conference on Image Analysis and Processing, p.1172, September 27-29, 1999
• 7: Cordella, L., Foggia, P., Sansone, C., and Vento, M. 2001. An improved algorithm for matching large graphs. In Proceedings of the 3rd IAPR TC-15 Workshop on Graph-Based Representations in Pattern Recognition, Ischia, Italy, J. Jolion, W. Kropatsch, and M. Vento, Eds. 149--159.
• 8: 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]
• 9: Damiani, E., De Capitani di Vimercati, S., Paraboschi, S., and Samarati, P. 2004. Computing range queries on obfuscated data. In Proceedings of the Information Processing and Management of Uncertainty in Knowledge-Based Systems, Perugia, Italy.
• 10: 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]
• 11: Dorothy Elizabeth Rob Denning, Cryptography and Data Security, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 12: Josep Domingo i Ferrer, A new privacy homomorphism and applications, Information Processing Letters, v.60 n.5, p.277-282, Dec. 9, 1996 [doi>10.1016/S0020-0190(96)00170-6]
• 13: Domingo-Ferrer, J. and Herrera-Joanconmartí, J. 1998. A privacy homomorphism allowing field operations on encrypted data. Jornades de Matemàtica Discreta i Algorísmica.
• 14: Foggia, P. 2001. The vflib graph matching library, version 2.0. http://amalfi.dis.unina.it/graph/db/vflib-2.0/doc/vflib.html.
• 15: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 16: 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]
• 17: Providing Database as a Service, Proceedings of the 18th International Conference on Data Engineering, p.29, February 26-March 01, 2002
• 18: Hacigümüs, H., Iyer, B., and Mehrotra, S. 2004. Efficient execution of aggregation queries over encrypted relational databases. In Proceedings of the 9th International Conference on Database Systems for Advanced Applications. Springer, Jeju Island, Korea.
• 19: Hacigümüs, H. and Mehrotra, S. 2004. Performance-conscious key management in encrypted databases. In Proceedings of the 18th Annual IFIP WG 11.3 Working Conference on Data and Applications Security, Sitges, Catalonia, Spain. Kluwer Academic Publishers, Dordrecht.
• 20: 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]
• 21: 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]
• 22: McKay, B. 1981. Practical graph isomorphism. Congressus Numerantium 30, 45--87.
• 23: Pisinger, D. 1995. Algorithms for knapsack problems. Ph.D. thesis, DIKU, University of Copenhagen, Copenhagen, Denmark. Report 95/1.
• 24: Rivest, R., Adleman, L., and Dertouzos, M. 1978. Data banks and privacy homomorphisms. In Foundations of Secure Computation. Academic Press, Orlando, FL. 169--179.
• 25: 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]
• 26: 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
• 27: J. R. Ullmann, An Algorithm for Subgraph Isomorphism, Journal of the ACM (JACM), v.23 n.1, p.31-42, Jan. 1976 [doi>10.1145/321921.321925]
• 28: 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]
• 29: 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
• 30: Whitney, H. 1932. Congruent graphs and the connectivity of graphs. Am. J. Math. 54, 150--168.

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, inference