Public Key Authenticated Encryption with Keyword Search Improved: Strong Security Model and Multi-keyword Construction

To efficiently and securely search encrypted files in cloud storage, Boneh et al. proposed the notion of Public Key Encryption with Keyword Search(PEKS) in 2004. However, original PEKS is susceptible to internal keyword guessing attacks(KGA) launched by server due to the limited keyword space. To resist this attack, Huang and Li introduced the notion of Public Key Authenticated Encryption with Keyword Search (PAEKS), which effectively resists KGA from server by additional authentication between the sender and receiver before encryption. Since both the sender and receiver can generate a common authentication key, a curious sender can use the authentication key to launch KGA, resulting in easily guessing keyword from a given trapdoor. To address this issue, we propose an improved security model for PAEKS that captures both offline KGA and online KGA launched by the curious sender. Then, we present a concrete Stronger Security Public Key Authenticated Encryption with Multi-keyword Search (S-PAEMKS) scheme, which not only supports multi-keyword search but also successfully counters KGA from curious senders. Finally, the experimental results show that our scheme achieves remarkable efficiency in the encryption phase and comparable efficiency in the trapdoor and testing phases.