International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Conjunctive Keyword Search on Encrypted Data with Completeness and Computational Privacy

Authors:
Radu Sion
Bogdan Carbunar
Download:
URL: http://eprint.iacr.org/2005/172
Search ePrint
Search Google
Abstract: 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 proving the authenticity and completeness of server replies. This is different from existing research efforts, where a cooperating, non-malicious server behavior is assumed. We also strengthen the privacy guarantees. The oblivious search protocol not only hides (from the server) the outsourced data but also does not leak client access patterns, the queries themselves, the association between previously searched keywords and returned documents or between newly added documents and their corresponding keywords (not even in encrypted form). This comes naturally at the expense of additional computation costs which we analyze in the context of today's off the shelf hardware. In a reasonable scenario, a single CPU off-the-shelf PC can easily handle hundreds of such oblivious searches per minute.
BibTeX
@misc{eprint-2005-12508,
  title={Conjunctive Keyword Search on Encrypted Data with Completeness and Computational Privacy},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols /},
  url={http://eprint.iacr.org/2005/172},
  note={ sion@cs.stonybrook.edu 13108 received 10 Jun 2005, withdrawn 21 Nov 2005},
  author={Radu Sion and Bogdan Carbunar},
  year=2005
}