Low-leakage secure search for boolean expressions

Schemes for encrypted search face inherent trade-offs between efficiency and privacy guarantees. Whereas search in plaintext can leverage efficient structures to achieve sublinear query time in the data size, similar performance is harder to achieve for secure search. Oblivious RAM (ORAM) techniques can provide the desired efficiency for simple look-ups, but do not address the needs of complex search protocols. Several recent works achieve efficiency at the price of revealing the access pattern. We propose a new encrypted search scheme that reduces the leakage of current Boolean queries solutions, while introducing limited overhead and preserving the sublinear efficiency properties for the search protocol in the semi-honest model. Our scheme achieves a privacy-efficiency trade-off that lies between highly optimized systems such as Blind Seer [18] and OXT-OSPIR [15], which exhibit significant access pattern leakage, and the secure search solution of Gentry et al. [8], which has no leakage, but a much higher efficiency cost. Our solution is based on a hybrid approach, which integrates ORAM techniques with the efficient search index structure of the Blind Seer system. We reduce the leakage to the server to only the number of nodes visited in the search tree during query execution. Queries that execute in sublinear time in Blind Seer execute also in sublinear time in our scheme. To enable delegated queries, we develop a new protocol for oblivious PRF sum evaluation and perform secure Boolean queries in a Bloom filter that reveals only the match result. We also enable oblivious-search token generation to hide the specifics of the delegated query from the data owner issuing the search tokens. We evaluated our system by implementing a prototype and testing it on a 100,000-record database. Our results indicate that the index can be traversed at a rate of a few seconds per matching record for both conjunction and small Disjunctive Normal Form queries.