Traditionally, as soon as confidentiality becomes a concern, data are encrypted before outsourcing to a service provider. Any software-based cryptographic constructs then deployed, for server-side query processing on the encrypted data, inherently limit query expressiveness. Here, we introduce TrustedDB, an outsourced database prototype that allows clients to execute SQL queries with privacy and under regulatory compliance constraints by leveraging server-hosted, tamper-proof trusted hardware in critical query processing stages, thereby removing any limitations on the type of supported queries. Despite the cost overhead and performance limitations of trusted hardware, we show that the costs per query are orders of magnitude lower than any (existing or) potential future software-only mechanisms. TrustedDB is built and runs on actual hardware, and its performance and costs are evaluated here.

Encryption,SQL,Query,DB

[1] FIPS PUB 140-2, Security Requirements for Cryptographic Modules, http://csrc.nist.gov/groups/STM/cmvp/standards.html#02, 2013.
[2] TPC-H Benchmark, http://www.tpc.org/tpch/, 2013.
[3] IBM 4764 PCI-X Cryptographic Coprocessor, http://www-03.ibm.com/security/cryptocards/pcixcc/overview.shtml, 2007.
[4] G. Aggarwal, M. Bawa, P. Ganesan, H. Garcia-Molina, K. Kenthapadi, R. Motwani, U. Srivastava, D. Thomas, and Y. Xu, “Two Can Keep a Secret: A Distributed Architecture for Secure Database Services,” Proc. Conf. Innovative Data Systems Research(CIDR), pp. 186-199, 2005.
[5] A. Iliev and S.W. Smith, “Protecting Client Privacy with Trusted Computing at the Server,” IEEE Security and Privacy, vol. 3, no. 2, pp. 20-28, Mar./Apr. 2005.
[6] M. Bellare, “New Proofs for NMAC and HMAC: Security Without Collision-Resistance,” Proc. 26th Ann. Int’l Conf. Advances inCryptology, pp. 602-619, 2006.
[7] B. Bhattacharjee, N. Abe, K. Goldman, B. Zadrozny, C. Apte, V.R. Chillakuru, and M. del Carpio, “Using Secure Coprocessors for Privacy Preserving Collaborative Data Mining and Analysis,”
Proc.Second Int’l Workshop Data Management on New Hardware (DaMoN ’06), 2006.
[8] M. Canim, M. Kantarcioglu, B. Hore, and S. Mehrotra, “Building Disclosure Risk Aware Query Optimizers for Relational Data-bases,” Proc. VLDB Endowment, vol. 3, nos. 1/2, pp. 13-24, Sept. 2010.
[9] Y. Chen and R. Sion, “To cloud or Not to Cloud?: Musings on Costs and Viability,” Proc. Second ACM Symp. Cloud Computing(SOCC ’11), pp. 29:1-29:7, 2011.
[10] V. Ciriani, S.D.C. di Vimercati, S. Foresti, S. Jajodia, S. Paraboschi, and P. Samarati, “Combining Fragmentation and Encryption to Protect Privacy in Data Storage,” ACM Trans. Information andSystem Security, vol. 13, no. 3, pp. 22:1-22:33, July 2010.
[11] T. Denis, Cryptography for Developers,Syngress, 2007.
[12] E. Damiani, C. Vimercati, S. Jajodia, S. Paraboschi, and P. Samarati, “Balancing Confidentiality and Efficiency in Untrusted Relational DBMSs,” Proc. 10th ACM Conf. Computer and Commu-nications Security (CCS ’12), 2003.
[13] E. Mykletun and G. Tsudik, “Aggregation Queries in the Database-as-a-Service Model,” Proc. 20th IFIP WG 11.3 WorkingConf. Data and Applications Security, pp. 89-103, 2006.
[14] F.N. Afrati and V. Borkar, and M. Carey, and N. Polyzotis, and J.D. Ullman, “Map-Reduce Extensions and Recursive Queries,” Proc.14th Int’l Conf. Extending Database Technology (EDBT), pp. 1-8, 2011.
[15] V. Ganapathy, D. Thomas, T. Feder, H. Garcia-Molina, and R. Motwani, “Distributing Data for Secure Database Services,” Proc.Fourth Int’l Workshop Privacy and Anonymity in the Information Soc. (PAIS ’11), pp. 8:1-8:10, 2011.
[16] T. Ge and S. Zdonik, “Fast Secure Encryption for Indexing in a Column-Oriented DBMS,” Proc. IEEE 23rd Int’l Conf. Data Eng.(ICDE), 2007.
[17] R. Gennaro, C. Gentry, and B. Parno, “Non-Interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers,”
Proc.30th Ann. Conf.Advances in Cryptology (CRYPTO ’10), pp. 465-482, 2010.
[18] O. Goldreich, Foundations of Cryptography I. Cambridge Univ. Press, 2001.
[19] B.I.H. Hacigumus and S. Mehrotra, “Efficient Execution of Aggregation Queries over Encrypted Relational Databases,” Proc.Ninth Int’l Conf. Database Systems for Advanced Applications, vol. 2973, pp. 633-650, 2004.
[20] H. Hacigumus, B. Iyer, C. Li, and S. Mehrotra, “Executing SQL over Encrypted Data in the Database-Service-Provider Model,”
Proc. ACM SIGMOD Int’l Conf. Management of Data (SIGMOD ’02),216-227, 2002.