Skip to content

可搜索加密与加密数据库

引子

2013年Cash等人在完整版OXT协议的文章中1提到了CryptDB，原文如下：

CryptDB supports most of SQL, including general boolean queries, over encrypted data and hence considerably more functionality than our work. It offers, though, also less privacy as CryptDB leaks statistical information on the whole queried column, not only related to matching rows, and this leakage can reveal significant information such as repeated values in the column (due to the use of deterministic encryption). Performance-wise, the schemes are hard to compare: All provided benchmarks in [33] were on databases which are several orders of magnitude smaller than ours and easily fit into RAM. Having small databases fitting into RAM side-steps the considerable challenge of efficiently dealing with high-latency storage, unavoidable for truly large databases. A related issue arises also with protocols based on the non-adaptive version of [15] which relies on a sequential linked-list implementation for the inverted index: the required inherently sequential list traversal will cause considerably latency on queries and limit scalability as soon as indices exceed the available RAM. Our implementation allows parallel list access which can hide these latency costs in overlapping network and computation costs to a mostly constatn rather than linear factor. Lastly, we like to point out that our scheme could replace CryptDB's use of the linear SSE scheme [36] for full-text search and, with corresponding support in the query optimizer, for less leaky boolean (sub-)expressions on single tables.

  1. D. Cash, S. Jarecki, C. Jutla, H. Krawczyk, M. Rosu, and M. Steiner, “Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries,” 169, 2013. Accessed: Jul. 07, 2021. [Online]. Available: https://eprint.iacr.org/2013/169 ↩