More Web Proxy on the site http://driver.im/

article

Processing analytical queries over encrypted data

Authors:

M. Frans Kaashoek,

Nickolai ZeldovichAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 6, Issue 5

Pages 289 - 300

https://doi.org/10.14778/2535573.2488336

Published: 01 March 2013 Publication History

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.

References

[1]

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.

[2]

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.

[3]

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.

[4]

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.

[5]

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.

[6]

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.

[7]

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.

[8]

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.

[9]

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.

[10]

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.

[11]

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.

[12]

C. Gentry. Fully homomorphic encryption using ideal lattices. In Proc. of the 41st STOC, pages 169-178, Bethesda, MD, May-June 2009.

[13]

C. Gentry, S. Halevi, and N. P. Smart. Homomorphic evaluation of the AES circuit. Cryptology ePrint Archive, Report 2012/099, June 2012.

[14]

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.

[15]

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.

[16]

H. Hacigümüs, B. R. Iyer, and S. Mehrotra. Query optimization in encrypted database systems. In DASFAA, pages 43-55, Apr. 2005.

[17]

S. Halevi and P. Rogaway. A tweakable enciphering mode. In Advances in Cryptology (CRYPTO), pages 482-499, Aug. 2003.

[18]

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.

[19]

P. O'Neil, E. O'Neil, and X. Chen. The star schema benchmark. http://www.cs.umb.edu/~poneil/StarSchemaB.pdf, Jan. 2007.

[20]

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.

[21]

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.

[22]

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.

[23]

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.

[24]

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.

Cited By

Zhang ZBian SZhao ZMao RZhou HHua JJin YGuan ZLuo BLiao XXu JKirda ELie D(2024)ArcEDB: An Arbitrary-Precision Encrypted Database via (Amortized) Modular Homomorphic EncryptionProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670384(4613-4627)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670384
Zhang FYang CZong RZheng XWang JMeng Y(2024)An Efficient and Scalable FHE-Based PDQ Scheme: Utilizing FFT to Design a Low Multiplication Depth Large-Integer Comparison AlgorithmIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.334824619(2258-2272)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TIFS.2023.3348246
Cao XLiu JShen YYe XRen K(2023)Frequency-Revealing Attacks against Frequency-Hiding Order-Preserving EncryptionProceedings of the VLDB Endowment10.14778/3611479.361151316:11(3124-3136)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611513
Show More Cited By

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 ...
Scalable Equi-Join Queries over Encrypted Database
CCS '24: Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security

Secure join queries over encrypted databases, the most expressive class of SQL queries, have attracted extensive attention recently. The state-of-the-art JXT (Jutla et al. ASIACRYPT 2022) enables join queries on encrypted relational databases without pre-...
Expressive search on encrypted data
ASIA CCS '13: Proceedings of the 8th ACM SIGSAC symposium on Information, computer and communications security

Different 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 6, Issue 5

March 2013

60 pages

ISSN:2150-8097

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 March 2013

Published in PVLDB Volume 6, Issue 5

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

103
Total Citations
View Citations
807
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)4

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang ZBian SZhao ZMao RZhou HHua JJin YGuan ZLuo BLiao XXu JKirda ELie D(2024)ArcEDB: An Arbitrary-Precision Encrypted Database via (Amortized) Modular Homomorphic EncryptionProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670384(4613-4627)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670384
Zhang FYang CZong RZheng XWang JMeng Y(2024)An Efficient and Scalable FHE-Based PDQ Scheme: Utilizing FFT to Design a Low Multiplication Depth Large-Integer Comparison AlgorithmIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.334824619(2258-2272)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TIFS.2023.3348246
Cao XLiu JShen YYe XRen K(2023)Frequency-Revealing Attacks against Frequency-Hiding Order-Preserving EncryptionProceedings of the VLDB Endowment10.14778/3611479.361151316:11(3124-3136)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611513
Barrios CKumar M(2023)Service Caching and Computation Reuse Strategies at the Edge: A SurveyACM Computing Surveys10.1145/360950456:2(1-38)Online publication date: 20-Jul-2023
https://dl.acm.org/doi/10.1145/3609504
Henzinger ADauterman ECorrigan-Gibbs HZeldovich NDruschel PKaufmann AMace JFlinn JSeltzer M(2023)Private Web Search with TiptoeProceedings of the 29th Symposium on Operating Systems Principles10.1145/3600006.3613134(396-416)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1145/3600006.3613134
Mangipudi SChuprikov PEugster PViering MSavvides S(2023)Generalized Policy-Based Noninterference for Efficient Confidentiality-PreservationProceedings of the ACM on Programming Languages10.1145/35912317:PLDI(267-291)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591231
Ahmad IAgrawal DAbbadi AGupta T(2022)PantheonProceedings of the VLDB Endowment10.14778/3574245.357425116:4(643-656)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.14778/3574245.3574251
Ren XSu LGu ZWang SLi FXie YBian SLi CZhang F(2022)HEDAProceedings of the VLDB Endowment10.14778/3574245.357424816:4(601-614)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.14778/3574245.3574248
Wang SLi YLi HLi FTian CSu LZhang YMa YYan LSun YCheng XXie XZou Y(2022)OperonProceedings of the VLDB Endowment10.14778/3554821.355482615:12(3332-3345)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.14778/3554821.3554826
Narasayya VChaudhuri SIves ZBonifati AEl Abbadi A(2022)Multi-Tenant Cloud Data Services: State-of-the-Art, Challenges and OpportunitiesProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3522566(2465-2473)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3522566
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents