Stephen Tu
M. Frans Kaashoek
Abstract
MONOMI is a system for securely executing analytical workloads over sensitive data on an untrusted database server. MONOMI works by encrypting the entire database and running queries over the encrypted data. MONOMI introduces split client/server query execution, which can execute arbitrarily complex queries over encrypted data, as well as several techniques that improve performance for such workloads, including per-row precomputation, space-efficient encryption, grouped homomorphic addition, and pre-filtering. Since these optimizations are good for some queries but not others, MONOMI introduces a designer for choosing an efficient physical design at the server for a given workload, and a planner to choose an efficient execution plan for a given query at runtime. A prototype of MONOMI running on top of Postgres can execute most of the queries from the TPC-H benchmark with a median overhead of only 1.24× (ranging from 1.03×to 2.33×) compared to an un-encrypted Postgres database where a compromised server would reveal all data.
- D. J. Abadi, S. R. Madden, and N. Hachem. Column-stores vs. row-stores: how different are they really? In Proc. of SIGMOD, pages 967-980, Vancouver, Canada, June 2008. Google Scholar
- S. Agrawal, S. Chaudhuri, and V. R. Narasayya. Automated selection of materialized views and indexes in SQL databases. In Proc. of the 26th VLDB, pages 496-505, Cairo, Egypt, Sept. 2000. Google Scholar
- A. Arasu, S. Blanas, K. Eguro, R. Kaushik, D. Kossmann, R. Ramamurthy, and R. Venkatesan. Orthogonal security with Cipherbase. In Proc. of the 6th CIDR, Asilomar, CA, Jan. 2013.Google Scholar
- S. Bajaj and R. Sion. TrustedDB: a trusted hardware based database with privacy and data confidentiality. In Proc. of SIGMOD, pages 205-216, Athens, Greece, June 2011. Google Scholar
- M. Bellare, P. Rogaway, and T. Spies. Addendum to "The FFX mode of operation for format-preserving encryption". http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/ proposedmodes/ffx/ffx-spec2.pdf, Sept. 2010.Google Scholar
- A. Boldyreva, N. Chenette, Y. Lee, and A. O'Neill. Order-preserving symmetric encryption. In Proc. of the 28th EUROCRYPT, pages 224-241, Cologne, Germany, Apr. 2009. Google Scholar
- A. Boldyreva, N. Chenette, Y. Lee, and A. O'Neill. Order-preserving encryption revisited: Improved security analysis and alternative solutions. In Advances in Cryptology (CRYPTO), pages 578-595, Aug. 2011. Google Scholar
- S. S. M. Chow, J.-H. Lee, and L. Subramanian. Two-party computation model for privacy-preserving queries over distributed databases. In Proc. of the 16th NDSS, Feb. 2009.Google Scholar
- V. Ciriani, S. D. C. di Vimercati, S. Foresti, S. Jajodia, S. Paraboschi, and P. Samarati. Keep a few: Outsourcing data while maintaining confidentiality. In Proc. of the 14th ESORICS, pages 440-455, Sept. 2009. Google Scholar
- A. J. Elmore, S. Das, D. Agrawal, and A. E. Abbadi. Zephyr: Live migration in shared nothing databases for elastic cloud platforms. In Proc. of SIGMOD, pages 301-312, Athens, Greece, June 2011. Google Scholar
- T. Ge and S. B. Zdonik. Answering aggregation queries in a secure system model. In Proc. of the 33rd VLDB, pages 519-530, Vienna, Austria, Sept. 2007. Google Scholar
- C. Gentry. Fully homomorphic encryption using ideal lattices. In Proc. of the 41st STOC, pages 169-178, Bethesda, MD, May-June 2009. Google Scholar
- C. Gentry, S. Halevi, and N. P. Smart. Homomorphic evaluation of the AES circuit. Cryptology ePrint Archive, Report 2012/099, June 2012.Google Scholar
- H. Hacigümüs, B. R. Iyer, C. Li, and S. Mehrotra. Executing SQL over encrypted data in the database-service-provider model. In Proc. of SIGMOD, pages 216-227, Madison, WI, June 2002. Google Scholar
- H. Hacigümüs, B. R. Iyer, and S. Mehrotra. Efficient execution of aggregation queries over encrypted relational databases. In DASFAA, pages 125-136, Mar. 2004.Google Scholar
- H. Hacigümüs, B. R. Iyer, and S. Mehrotra. Query optimization in encrypted database systems. In DASFAA, pages 43-55, Apr. 2005. Google Scholar
- S. Halevi and P. Rogaway. A tweakable enciphering mode. In Advances in Cryptology (CRYPTO), pages 482-499, Aug. 2003.Google Scholar
- R. Kumar, J. Novak, B. Pang, and A. Tomkins. On anonymizing query logs via token-based hashing. In Proc. of the 16th International World Wide Web Conference, pages 629-638, Banff, Canada, May 2007. Google Scholar
- P. O'Neil, E. O'Neil, and X. Chen. The star schema benchmark. http://www.cs.umb.edu/~poneil/StarSchemaB.pdf, Jan. 2007.Google Scholar
- P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Proc. of the 18th EUROCRYPT, pages 223-238, Prague, Czech Republic, May 1999. Google Scholar
- S. Papadomanolakis and A. Ailamaki. An integer linear programming approach to database design. In Proc. of the 23rd ICDE, pages 442-449, Istanbul, Turkey, Apr. 2007. Google Scholar
- R. A. Popa, C. M. S. Redfield, N. Zeldovich, and H. Balakrishnan. CryptDB: Protecting confidentiality with encrypted query processing. In Proc. of the 23rd SOSP, pages 85-100, Cascais, Portugal, Oct. 2011. Google Scholar
- R. A. Popa, F. H. Li, and N. Zeldovich. An ideal-security protocol for order-preserving encoding. In Proc. of the 34th IEEE Symposium on Security and Privacy, San Francisco, CA, May 2013.Google Scholar
- D. X. Song, D. Wagner, and A. Perrig. Practical techniques for searches on encrypted data. In Proc. of the 21st IEEE Symposium on Security and Privacy, pages 44-55, Oakland, CA, May 2000. Google Scholar
Index Terms
- Processing analytical queries over encrypted data
Recommendations
Efficient Hidden Vector Encryption for Conjunctive Queries on Encrypted Data
Predicate encryption has received considerable attention in applications where private and sensitive data about users can be stored in untrusted database (DB) servers. It allows users to store encrypted data at DB servers, and yet retain the ability to ...
Expressive search on encrypted data
ASIA CCS '13: Proceedings of the 8th ACM SIGSAC symposium on Information, computer and communications securityDifferent from the traditional public key encryption, searchable public key encryption allows a data owner to encrypt his data under a user's public key in such a way that the user can generate search token keys using her secret key and then query an ...
Comments