Blind Seer: A Scalable Private DBMS
Open accessThe DOI matches its Crossref record; 44 of the 44 references it cites were found in a registry or an index.
Abstract
Query privacy in secure DBMS is an important feature, although rarely formally considered outside the theoretical community. Because of the high overheads of guaranteeing privacy in complex queries, almost all previous works addressing practical applications consider limited queries (e.g., just keyword search), or provide a weak guarantee of privacy. In this work, we address a major open problem in private DB: efficient sub linear search for arbitrary Boolean queries. We consider scalable DBMS with provable security for all parties, including protection of the data from both server (who stores encrypted data) and client (who searches it), as well as protection of the query, and access control for the query. We design, build, and evaluate the performance of a rich DBMS system, suitable for real-world deployment on today medium-to large-scale DBs. On a modern server, we are able to query a formula over 10TB, 100M-record DB, with 70 searchable index terms per DB row, in time comparable to (insecure) MySQL (many practical queries can be privately executed with work 1.2-3 times slower than MySQL, although some queries are costlier). We support a rich query set, including searching on arbitrary boolean formulas on keywords and ranges, support for stemming, and free keyword searches over text fields. We identify and permit a reasonable and controlled amount of leakage, proving that no further leakage is possible. In particular, we allow leakage of some search pattern information, but protect the query and data, provide a high level of privacy for individual terms in the executed search formula, and hide the difference between a query that returned no results and a query that returned a very small result set. We also support private and complex access policies, integrated in the search process so that a query with empty result set and a query that fails the policy are hard to tell apart.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A public key cryptosystem and a signature scheme based on discrete logarithms
Elgamal, T. (1985) · IEEE Transactions on Information Theory · doi:10.1109/tit.1985.1057074 · Cited by 8,059 · cited 1×
“We assume that readers are familiar with pseudorandom generators (PRG), pseudorandom functions (PRF), and semihomomorphic encryption schemes with semantic security [28], e.g., ElGamal encryption [19].”
BackgroundSpace/time trade-offs in hash coding with allowable errors
Bloom, B. H. (1970) · Communications of the ACM · doi:10.1145/362686.362692 · Cited by 7,492 · cited 3×
“Given a range query [7, 11), the following canonical ranges are checked: [7, 8), [10, 11), [8, 10).”
BackgroundFully homomorphic encryption using ideal lattices
Gentry, C. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536440 · Cited by 6,806 · cited 2×
“In 2009, Gentry [21] showed that FHE is theoretically possible.”
BackgroundPractical techniques for searches on encrypted data
Song, D. X., Wagner, D., & Perrig, A. (2002) · Proceeding 2000 IEEE Symposium on Security and Privacy. S&P 2000 · doi:10.1109/secpri.2000.848445 · Cited by 3,350 · cited 3×
“There has been a long line of research on searchable symmetric encryption (SSE) [11]–[13], [17], [25], [41], [50].”
BackgroundMethodPublic Key Encryption with Keyword Search
Boneh, D., Di Crescenzo, G., Ostrovsky, R., & Persiano, G. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24676-3_30 · Cited by 3,134 · cited 2×
“Searchable encryption has also been studied in the public key setting [4], [6], [9], [10], [49].”
BackgroundGoldwasser, S., & Micali, S. (1984) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(84)90070-9 · Cited by 2,603 · cited 1×
“We assume that readers are familiar with pseudorandom generators (PRG), pseudorandom functions (PRF), and semihomomorphic encryption schemes with semantic security [28], e.”
BackgroundSearchable symmetric encryption: improved definitions and efficient constructions
Curtmola, R., Garay, J., Kamara, S., & Ostrovsky, R. (2006) · Proceedings of the 13th ACM conference on Computer and communications security · doi:10.1145/1180405.1180417 · Cited by 1,671 · cited 3×
“There has been a long line of research on searchable symmetric encryption (SSE) [11]–[13], [17], [25], [41], [50].”
BackgroundSoftware protection and simulation on oblivious RAMs
Goldreich, O., & Ostrovsky, R. (1996) · Journal of the ACM · doi:10.1145/233551.233553 · Cited by 1,617 · cited 3×
“For example, when ORAM is used to achieve sublinear secure computation between two parties [29], its basic step involves oblivious PRF evaluation.”
BackgroundMethodChor, B., Kushilevitz, E., Goldreich, O., & Sudan, M. (1998) · Journal of the ACM · doi:10.1145/293347.293350 · Cited by 1,612
A Randomized Protocol for Signing Contracts
Even, S., Goldreich, O., & Lempel, A. (1983) · Advances in Cryptology · doi:10.1007/978-1-4757-0602-4_19 · Cited by 1,450
Conjunctive, Subset, and Range Queries on Encrypted Data
Boneh, D., & Waters, B. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-70936-7_29 · Cited by 1,432 · cited 4×
“Section V-B), is naturally and cheaply achievable in our system; it appears harder/more expensive to achieve in a non-interactive system, and in fact is not considered in [10].”
BackgroundInfluentialCryptDB: protecting confidentiality with encrypted query processing
Popa, R. A., Redfield, C. M. S., Zeldovich, N., & Balakrishnan, H. (2011) · Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles · doi:10.1145/2043556.2043566 · Cited by 1,155 · cited 1×
“The CryptDB system [45] addresses the problem of DB encryption from a completely different angle, and as such is largely incomparable to our work.”
ResultPrivacy Preserving Keyword Searches on Remote Encrypted Data
Chang, Y.-C., & Mitzenmacher, M. (2005) · Lecture Notes in Computer Science · doi:10.1007/11496137_30 · Cited by 1,041 · cited 2×
“Additionally, SSE solutions often offer either a linear time search over the number of database records [12], [41], [50], or a restricted type of client’s queries [17], [32], namely single keyword search or conjunctions.”
BackgroundHighly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries
Cash, D., Jarecki, S., Jutla, C., Krawczyk, H., Roşu, M.-C., & Steiner, M. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40041-4_20 · Cited by 883 · cited 8×
“We note that the work of [11], [31] is performed independently and concurrently to ours.”
BackgroundInfluentialHow to Exchange Secrets with Oblivious TransferPreprint
Rabin, M. O. (1981) · IACR Cryptology ePrint Archive · Cited by 870
Fairplay—a secure two-party computation system
Malkhi, D., Nisan, N., Pinkas, B., & Sella, Y. (2004) · USENIX Security Symposium · Cited by 852
Homomorphic Evaluation of the AES Circuit
Gentry, C., Halevi, S., & Smart, N. P. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-32009-5_49 · Cited by 796 · cited 1×
“For example, it is possible to homomorphically compute 720 AES blocks in two and a half days [23].”
Extending Oblivious Transfers Efficiently
Ishai, Y., Kilian, J., Nissim, K., & Petrank, E. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45146-4_9 · Cited by 746 · cited 1×
“We use the Naor-Pinkas protocol [42] as a basis and optimize the performance using OT extension [30] and OT preprocessing [5].”
MethodDeterministic and Efficiently Searchable Encryption
Bellare, M., Boldyreva, A., & O’Neill, A. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-74143-5_30 · Cited by 745
Improved Garbled Circuit: Free XOR Gates and Applications
Kolesnikov, V., & Schneider, T. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-70583-3_40 · Cited by 743
Self-citationThe round complexity of secure protocols
Beaver, D., Micali, S., & Rogaway, P. (1990) · Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 · doi:10.1145/100216.100287 · Cited by 721 · cited 2×
“Then, for each gate g in the circuit, with its input wires i, j and its output wire k, a garbled gate g̃ (consisting of four ciphertexts) is constructed so that it will enable one to recover wij k from wi i and w bj j (refer to [14], [36], [40], [48] for more detail.”
BackgroundMethodA Proof of Security of Yao’s Protocol for Two-Party Computation
Lindell, Y., & Pinkas, B. (2009) · Journal of Cryptology · doi:10.1007/s00145-008-9036-8 · Cited by 651
Multi-Dimensional Range Query over Encrypted Data
Shi, E., Bethencourt, J., Chan, T.-H. H., Song, D., & Perrig, A. (2007) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2007.29 · Cited by 552
Foundations of garbled circuits
Bellare, M., Hoang, V. T., & Rogaway, P. (2012) · Proceedings of the 2012 ACM conference on Computer and communications security · doi:10.1145/2382196.2382279 · Cited by 541 · cited 2×
“In fact, due to the privacy guaranteed by Yao’s GC [7], even if the circuit C is a private input from Alice along with xA, Yao’s GC can also hide the circuit C from Bob, revealing only the topology of C.”
BackgroundFaster Secure Two-Party Computation Using Garbled Circuits
Huang, Y., Evans, D., Katz, J. I., & Malka, L. (2011) · doi:10.18130/v3hj5c · Cited by 532
Parallel and Dynamic Searchable Symmetric Encryption
Kamara, S., & Papamanthou, C. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-39884-1_22 · Cited by 528
Structured Encryption and Controlled Disclosure
Chase, M., & Kamara, S. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-17373-8_33 · Cited by 520 · cited 1×
“There has been a long line of research on searchable symmetric encryption (SSE) [11]–[13], [17], [25], [41], [50].”
BackgroundProtecting data privacy in private information retrieval schemes
Gertner, Y., Ishai, Y., Kushilevitz, E., & Malkin, T. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276723 · Cited by 445 · cited 2×
“Symmetric PIR protocols [24] additionally require that client should not learn anything more than the requested record.”
BackgroundSelf-citationSearchable Encryption Revisited: Consistency Properties, Relation to Anonymous IBE, and Extensions
Abdalla, M. F., Mihir Bellare, Y., Catalano, D., Kiltz, E., Kohno, T., Lange, T., Malone-Lee, J., Neven, G., Paillier, P., & Shi, H. (2007) · Journal of Cryptology · doi:10.1007/s00145-007-9006-6 · Cited by 350
Outsourced symmetric private information retrieval
Jarecki, S., Jutla, C. S., Krawczyk, H., Rosu, M. C., & Steiner, M. (2013) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2508859.2516730 · Cited by 247 · cited 9×
“We note that the work of [11], [31] is performed independently and concurrently to ours.”
BackgroundInfluentialPrivate Information Retrieval by KeywordsPreprint
Chor, B., Gilboa, N., & Naor, M. (1997) · IACR Cryptology ePrint Archive · Cited by 246
Protecting Data Privacy in Private Information Retrieval Schemes
Gertner, Y., Ishai, Y., Kushilevitz, E., & Malkin, T. (2000) · Journal of Computer and System Sciences · doi:10.1006/jcss.1999.1689 · Cited by 214
Self-citationComputationally Secure Oblivious Transfer
Naor, M., & Pinkas, B. (2005) · Journal of Cryptology · doi:10.1007/s00145-004-0102-6 · Cited by 180 · cited 1×
“We use the Naor-Pinkas protocol [42] as a basis and optimize the performance using OT extension [30] and OT preprocessing [5].”
MethodSecure two-party computation in sublinear (amortized) time
Gordon, S. D., Katz, J., Kolesnikov, V., Krell, F., Malkin, T., Raykova, M., & Vahlis, Y. (2012) · Proceedings of the 2012 ACM conference on Computer and communications security · doi:10.1145/2382196.2382251 · Cited by 179 · cited 3×
“For example, when ORAM is used to achieve sublinear secure computation between two parties [29], its basic step involves oblivious PRF evaluation.”
BackgroundMethodSelf-citationOptimizing ORAM and Using It Efficiently for Secure Computation
Gentry, C., Goldman, K. A., Halevi, S., Julta, C., Raykova, M., & Wichs, D. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-39077-7_1 · Cited by 168
Distributed Oblivious RAM for Secure Two-Party Computation
Lu, S., & Ostrovsky, R. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-36594-2_22 · Cited by 162 · cited 2×
“Oblivious RAM (ORAM) [27] can be used to completely hide the client’s query pattern, and can also be used as a tool to achieve sublinear amortized time for secure computation if we allow to leak the program running time [29], [39].”
BackgroundMethodA Practical Universal Circuit Construction and Secure Evaluation of Private Functions
Kolesnikov, V., & Schneider, T. H. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85230-8_7 · Cited by 130
Self-citationSecure anonymous database search
Raykova, M., Vo, B. D., Bellovin, S. M., & Malkin, T. (2009) · doi:10.1145/1655008.1655025 · Cited by 104 · cited 2×
“Using the technique from [47], we augment the BF to support inserting a number x ∈ Z2n , say with n = 32, and checking if the BF contains a number in a given range.”
BackgroundMethodSelf-citationOn the Security of the “Free-XOR” Technique
Choi, S. G., Katz, J. I., Kumaresan, R., & Zhou, H.-S. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-28914-9_3 · Cited by 94 · cited 2×
“Then, for each gate g in the circuit, with its input wires i, j and its output wire k, a garbled gate g̃ (consisting of four ciphertexts) is constructed so that it will enable one to recover wij k from wi i and w bj j (refer to [14], [36], [40], [48] for more detail.”
BackgroundMethodSelf-citationBoolean symmetric searchable encryption
Moataz, T., & Shikfa, A. (2013) · doi:10.1145/2484313.2484347 · Cited by 70 · cited 2×
“There has been a long line of research on searchable symmetric encryption (SSE) [11]–[13], [17], [25], [41], [50].”
BackgroundEfficient Techniques for Privacy-Preserving Sharing of Sensitive Information
Cristofaro, E. D., Lu, Y., & Tsudik, G. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-21599-5_18 · Cited by 46 · cited 1×
“A more efficient solution towards this end was proposed in [18].”
BackgroundEfficient Provably Secure Public Key Steganography.Preprint
Le, T. V. (2003) · IACR Cryptology ePrint Archive · Cited by 40
Private search in the real world
Pappas, V., Raykova, M., Vo, B. D., Bellovin, S. M., & Malkin, T. (2011) · Annual Computer Security Applications Conference · doi:10.1145/2076732.2076744 · Cited by 27 · cited 1×
“of [44], [47] supports single keyword search and conjunctions.”
BackgroundSelf-citationImproved Secure Two-Party Computation via Information-Theoretic Garbled Circuits
Kolesnikov, V., & Kumaresan, R. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-32928-9_12 · Cited by 14 · cited 1×
“We could use the slightly more computationally-expensive, but much less communication intensive GESS protocol of [34] or its recent extension sliced-GESS [35], instead of Yao’s GC.”
MethodSelf-citation
Cited by
Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries
Cash, D., Jarecki, S., Jutla, C., Krawczyk, H., Roşu, M.-C., & Steiner, M. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40041-4_20 · Cited by 883
Generic Attacks on Secure Outsourced Databases
Kellaris, G., Kollios, G., Nissim, K., & O'Neill, A. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978386 · Cited by 284
∑oφoς: Forward Secure Searchable Encryption
Bost, R. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978303 · Cited by 279
Non-invasive Spoofing Attacks for Anti-lock Braking Systems
Shoukry, Y., Martin, P., Tabuada, P., & Srivastava, M. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40349-1_4 · Cited by 253
Improved Reconstruction Attacks on Encrypted Data Using Range Query Leakage
Lacharite, M.-S., Minaud, B., & Paterson, K. G. (2018) · 2018 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2018.00002 · Cited by 173
“[12], as well as a scheme by Faber et al.”
Method
Metadata
- Authors
- Pappas, V., Krell, F., Vo, B., Kolesnikov, V., Malkin, T., Choi, S. G., George, W., Keromytis, A., & Bellovin, S.
- Venue
- 2014 IEEE Symposium on Security and Privacy
- Publisher
- IEEE
- Published
- 2014-05
- Pages
- 359-374
- ISSN
- 1081-6011 (ISSN-L)
- OpenAlex
- W1996453724
- Cited by
- 237
- References
- 44
- FWCI
- 15.61
- Type
- conference paper
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.