Executing SQL over encrypted data in the database-service-provider model

ABSTRACT

Rapid advances in networking and Internet technologies have fueled the emergence of the "software as a service" model for enterprise computing. Successful examples of commercially viable software services include rent-a-spreadsheet, electronic mail services, general storage services, disaster protection services. "Database as a Service" model provides users power to create, store, modify, and retrieve data from anywhere in the world, as long as they have access to the Internet. It introduces several challenges, an important issue being data privacy. It is in this context that we specifically address the issue of data privacy.There are two main privacy issues. First, the owner of the data needs to be assured that the data stored on the service-provider site is protected against data thefts from outsiders. Second, data needs to be protected even from the service providers, if the providers themselves cannot be trusted. In this paper, we focus on the second challenge. Specifically, we explore techniques to execute SQL queries over encrypted data. Our strategy is to process as much of the query as possible at the service providers' site, without having to decrypt the data. Decryption and the remainder of the query processing are performed at the client site. The paper explores an algebraic framework to split the query to minimize the computation at the client site. Results of experiments validating our approach are also presented.

REFERENCES

• 1: AES. Advanced Encryption Standard. National Institute of Science and Technology, FIPS 197, 2001.
• 2: D. Song and D. Wagner and A. Perrig. Search on encrypted data. In Proc. of IEEE SRSP, 2000.
• 3: DES. Data Encryption Standard. FIPS PUB 46, Federal Information Processing Standards Publication, 1977.
• 4: Jeffrey D. Ullman , Hector Garcia-Molina , Jennifer Widom, Database Systems: The Complete Book, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 5: H. Hacigümüş, B. Iyer, C. Li, and S. Mehrotra. Executing SQL over Encrypted Data in Database-Service-Provider Model. Technical Report TR-DB-02-02, Database Research Group at University of California, Irvine, 2002.
• 6: H. Hacigümüş, B. Iyer, and S. Mehrotra. Providing Database as a Service. In Proc. of ICDE, 2002.
• 7: Yannis E. Ioannidis , Viswanath Poosala, Histogram-Based Approximation of Set-Valued Query-Answers, Proceedings of the 25th International Conference on Very Large Data Bases, p.174-185, September 07-10, 1999
• 8: H. V. Jagadish , Hui Jin , Beng Chin Ooi , Kian-Lee Tan, Global optimization of histograms, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.223-234, May 21-24, 2001, Santa Barbara, California, United States
• 9: Gregory Piatetsky-Shapiro , Charles Connell, Accurate estimation of the number of tuples satisfying a condition, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 10: R. L. Rivest and L. M. Adleman and M. L. Dertouzos. On Data Banks and Privacy Homomorphisms. In Foundations of Secure Computation, pages 169-178, 1978.
• 11: 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]
• 12: Bruce Schneier, Description of a New Variable-Length Key, 64-bit Block Cipher (Blowfish), Fast Software Encryption, Cambridge Security Workshop, p.191-204, December 09-11, 1993
• 13: Abraham Silberschatz , Henry F. Korth , S. Sudarshan , Allen B. Tucker, Database Systems Concepts, McGraw-Hill, Inc., New York, NY, 1997
• 14: TPC-H. Benchmark Specification. http://www.tpc.org.
• 15: M. Winslett and J. D. Ullman. Jeffrey D. Ullman speaks out on the future of higher education, startups, database theory, and more. SIGMOD Record, 30(3), 2001.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

          Nouns: SQL
      H.2.4 Systems
          Subjects: Distributed databases; Query processing

General Terms:
Algorithms, Documentation, Theory