Encrypted Search: Enabling Standard Information Retrieval Techniques for Several New Secure Index Types While Preserving Confidentiality Against an Adversary With Access to Query Histories and Secure Index Contents

Encrypted Search is a way for a client to store searchable documents on untrusted systems such that the untrusted system can obliviously search the documents on the client's behalf, i.e., the untrusted system does not know what the client is searching for nor what the documents contain. Several new secure index types (which enable Encrypted Search functionality) are designed and implemented, and then compared against each other and against the more typical Bloom filter-based secure index. We compare them with respect to several performance measures: time complexity, space complexity, and retrieval accuracy with respect to two rank-ordered search heuristics, MinDist* and BM25. In order to support these search heuristics, the secure indexes must store frequency and proximity information. We investigate the risk this poses to confidentiality and explore ways to mitigate said risk. Finally, we analyze the effect the false positive rate and secure index poisoning techniques have on both confidentiality and performance. Separately, we also simulate an adversary who has access to a history of hidden (encrypted) queries and design techniques that demonstrably mitigate the risk posed by this adversary, e.g., query obfuscation, without adversely effecting retrieval accuracy.