In an outsourced data framework, we introduce and demonstrate mechanisms for securely storing a set of data items (documents) on an un-trusted server, while allowing for subsequent conjunctive keyword searches for matching documents. The protocols provide full computational privacy, query correctness assurances and no leaks: the server either correctly executes client queries or (if it behaves maliciously) is immediately detected. The client is then provided with strong assurances proving the authenticity and completeness of results. This is different from existing secure keyword search research efforts where a cooperating, non-malicious server behavior is assumed. Additionally, not only does the oblivious search protocol conceal the outsourced data (from the un-trusted server) but it also does not leak client access patterns, the queries themselves, the association between different queries or between newly added documents and their corresponding keywords (not even in encrypted form). These assurances come at the expense of additional computation costs which we analyze in the context of today's hardware.
