Server-Aided Public Key Encryption With Keyword Search

Public key encryption with keyword search (PEKS) is a well-known cryptographic primitive for secure searchable data encryption in cloud storage. Unfortunately, it is inherently subject to the (inside) offline keyword guessing attack (KGA), which is against the data privacy of users. Existing countermeasures for dealing with this security issue mainly suffer from low efficiency and are impractical for real applications. In this paper, we provide a practical and applicable treatment on this security vulnerability by formalizing a new PEKS system named server-aided public key encryption with keyword search (SA-PEKS). In SA-PEKS, to generate the keyword ciphertext/trapdoor, the user needs to query a semitrusted third-party called keyword server (KS) by running an authentication protocol, and hence, security against the offline KGA can be obtained. We then introduce a universal transformation from any PEKS scheme to a secure SA-PEKS scheme using the deterministic blind signature. To illustrate its feasibility, we present the first instantiation of SA-PEKS scheme by utilizing the Full Domain Hash RSA signature and the PEKS scheme proposed by Boneh et al. in Eurocrypt 2004. Finally, we describe how to securely implement the client-KS protocol with a rate-limiting mechanism against online KGA and evaluate the performance of our solutions in experiments.

I. Introduction

Cloud storage outsourcing is of increasing interest in recent years for enterprises and organizations to reduce the burden of maintaining big data. In reality, end users may prefer to encrypt their outsourced data for privacy protection as they may not entirely trust the cloud storage server. This makes deployment of traditional data utilization service, such as plaintext keyword search over textual data or query over database, a difficult task. One of the typical solutions is the searchable encryption which allows the user to search and retrieve the encrypted data, and meanwhile preserve the data privacy. Searchable encryption can be realized in either symmetric [1], [2] or asymmetric encryption setting [3], [4]. The symmetric searchable encryption (SSE) is proposed by Song et al. [1] and later a formal treatment by Curtmola et al. [2]. Despite the high efficiency in SSE schemes, they suffer from complicated secret key distribution problem. Searchable encryption in public key setting, originating from store-and-forward system, such as email system, in which a receiver can search data encrypted under the receiver’s public key on an outsourced storage system, is initiated by Boneh et al. [3]. They firstly introduced a more flexible primitive, namely Public Key Encryption with Keyword Search (PEKS) that enables a user to search encrypted data in the asymmetric encryption setting. In a PEKS system, using the receiver’s public key, the sender attaches some encrypted keywords (referred to as PEKS ciphertexts) with the encrypted data. The receiver then sends the trapdoor of a to-be-searched keyword to the server for data searching. Given the trapdoor and the PEKS ciphertext, the server can test whether the keyword underlying the PEKS ciphertxt is equal to the one selected by the receiver. If so, the server sends the matching encrypted data to the receiver.