Paper 2005/367

Searchable Keyword-Based Encryption

Dong Jin Park, Juyoung Cha, and Pil Joong Lee

Abstract

To solve the problem of searching on encrypted data, many keyword search schemes have been proposed in recent years. The goal of such schemes is to enable a user to give an untrusted storage server the ability only to test whether an encrypted document contains a few keywords without learning anything else about the document. In this paper, we are concerned with decrypting the searched results as well as searching for desired documents. In the previously proposed schemes, except for the work by Waters et al.[WBDS04], a user decrypts searched documents using his private key, $A_{priv}$, or a symmetric key. Our another goal is to enable a user to give a proxy the ability to decrypt only the ciphertexts containing desired keywords, but not other ciphertexts. We propose a new mechanism, Searchable Keyword-Based Encryption (SKBE) which satisfies both the above goals. As a result of adding the delegation of decryption ability, our mechanism works more securely and efficiently in several applications, such as email gateways, secure audit logs, and decryption key delegation systems, than any of the previously proposed schemes. We formalize this mechanism, define its security model and propose an efficient construction whose security is proved in a random oracle model under the Bilinear Diffie-Hellman Inversion assumption. The scheme is constructed based on the Public Key Encryption with Conjunctive Field Keyword Search scheme in [PKL04] by using a hybrid encryption technique.

Note: Chow[http://eprint.iacr.org/2005/377] introduced a method attacking the scheme represented in this paper's previous version. The attack is not accomplished as their description, but it is true that the previous scheme has a problem when the decryption query in their attack is issued because SKBE allows a decryption query for Ci not equal to C where C is a challenge ciphertext. We notice that our present work is modified to solve that problem, finally it is secure against the attack by Chow.