Achieving Efficient Conjunctive Keyword Searches over Encrypted Data
Seny Kamara, and
We present two provably secure and efficient schemes for performing
conjunctive keyword searches over symmetrically encrypted data. Our
first scheme is based on Shamir Secret Sharing and provides the most
efficient search technique in this context to date. Although the
size of its trapdoors is linear in the number of documents being
searched, we empirically show that this overhead remains reasonable
in practice. Nonetheless, to address this limitation we provide an
alternative based on bilinear pairings that yields constant size
trapdoors. This latter construction is not only asymptotically more
efficient than previous secure conjunctive keyword search schemes in
the symmetric setting, but incurs significantly less storage
overhead. Additionally, unlike most previous work, our
constructions are proven secure in the standard model.
Warning: we are aware of weaknesses in this paper. Please contact us directly if you would like to discuss.