Conjunctive Keyword Search on Encrypted Data with Completeness and Computational Privacy

We introduce mechanisms for secure keyword searches on a document server. We propose protocols with computational privacy, query correctness assurances and minimal or 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 of server replies. This is di#erent from existing research e#orts, where a cooperating, non-malicious server behavior is assumed