Oblix: An Efficient Oblivious Search Index

Search indices are fundamental building blocks of many systems, and there is great interest in running them on encrypted data.Unfortunately, many known schemes that enable search queries on encrypted data achieve efficiency at the expense of security, as they reveal access patterns to the encrypted data.In this paper we present Oblix, a search index for encrypted data that is oblivious (provably hides access patterns), is dynamic (supports inserts and deletes), and has good efficiency.Oblix relies on a combination of novel oblivious-access techniques and recent hardware enclave platforms (e.g., Intel SGX).In particular, a key technical contribution is the design and implementation of doubly-oblivious data structures, in which the client's accesses to its internal memory are oblivious, in addition to accesses to its external memory at the server.These algorithms are motivated by hardware enclaves like SGX, which leak access patterns to both internal and external memory.We demonstrate the usefulness of Oblix in several applications: private contact discovery for Signal, private retrieval of public keys for Key Transparency, and searchable encryption that hides access patterns and result sizes.Challenge: high round complexity.The position map has size that is linear in the number of entries in the index.In our applications (e.g., contact discovery for Signal), clients cannot store it.The standard solution is to store the position map at the ORAM server in another ORAM instance with its own (smaller) position map, and recurse until the position map is small enough for the client to store.However, this solution implies that each index lookup requires a logarithmic (in the index size) number of requests, and hence roundtrips, to the server.These roundtrips severely degrade latency.