Fuller et al.; SoK: Cryptographically proctected database search; In Proceedings of IEEE Symposium on Security and Privacy (SP), 2017-03-06 → 2017-06-02; arXiv:1703.02014, IEEE.
Protected database search systems cryptographically isolate the roles of reading from, writing to, and administering the database. This separation limits unnecessary administrator access and protects data in the case of system breaches. Since protected search was introduced in 2000, the area has grown rapidly; systems are offered by academia, start-ups, and established companies.
However, there is no best protected search system or set of techniques. Design of such systems is a balancing act between security, functionality, performance, and usability. This challenge is made more difficult by ongoing database specialization, as some users will want the functionality of SQL, NoSQL, or NewSQL databases. This database evolution will continue, and the protected search community should be able to quickly provide functionality consistent with newly invented databases.
At the same time, the community must accurately and clearly characterize the tradeoffs between different approaches. To address these challenges, we provide the following contributions:
- An identification of the important primitive operations across database paradigms. We find there are a small number of base operations that can be used and combined to support a large number of database paradigms.
- An evaluation of the current state of protected search systems in implementing these base operations. This evaluation describes the main approaches and tradeoffs for each base operation. Furthermore, it puts protected search in the context of unprotected search, identifying key gaps in functionality.
- An analysis of attacks against protected search for different base queries.
- A roadmap and tools for transforming a protected search system into a protected database, including an open-source performance evaluation platform and initial user opinions of protected search.
Bitglass, Ciphercloud, CipherQuery, Crypteron, IQrypt, Kryptnostic, Google’s Encrypted BigQuery, Microsoft’s SQL Server 2016, Azure SQL Database, PreVeil, Skyhigh, StealthMine, ZeroDB
- Single table
- With indices
- Multiple tables
- Deterministic Encryption (DET)
- preserves only equality but applying a randomized but fixed permutation to all messages.
- Order-Preserving Encryption (OPE)
- preserves the relative order of the plaintexts; range queries.
- Mutable OPE
- only reveals the order of ciphertexts; added interactivity during insertion and query execution.
- Inverted index schemes
- Tree traversal schemes
… aim to hide common results between queries.
- Oblivious RAM (ORAM)
- performance problems
- Path ORAM
- latest type of ORAM
- a second non-colluding server
Full database solutions
- enables most DBMS functionality with a performance overhead of under 30%.
- is built on top of MongoDB and reports a performance overhead of approximately 10%.
- reports slowdowns of between 20% and 300% for most queries
- EXT can occasionally beat a MySQL system with a cold cache (a somewhat strange comparison!), but are an order of magnitude slower than MySQL with a warm cache.
- reports a 500% slowdown compared to a baseline MySQL system on keyword equality and range queries.
- SummarizationSystematization of Knowledge (SoK)
- Data Base Management System (DBMS)
- searchable symmetric encryption
- property preserving encryption
- database search
- oblivious random access memory
- private information retrieval
- Property-Revealing Encryption (PRE)
- Coyler (Some VC Shop); In His Blog entitled the morning paper(all lower case)
There are 162 references. As time moves on, check the IEEE, one day they will have the paper & its references.