In cloud era, it is necessary to store sensitive data in an encrypted form. This arises the interesting and challenging problem of searching on encrypted data. However, previous Public-key Encryption with Keyword Search (PEKS) inherently cannot resist against inside keyword guessing attacks. To alleviate this issue, recently Huang and Li proposed the notion of Public-key Authenticated Encryption with Keyword Search (PAEKS), which requires the data sender not only encrypting a keyword using the receiver’s public key, but also authenticating it using his secret key. This paper first revisits HL-PAEKS security model and finds that it did not capture a realistic threat, called (outside) chosen multi-ciphertext attacks. That is, an outside adversary can decide whether two encrypted files share some identical keywords or not. To resolve this issue, we propose a new PAEKS security model that captures both (outside) chosen multi-ciphertext attacks and (inside) keyword guessing attacks. Then, we give a concrete PAEKS scheme and prove its security in the new PAEKS security model. We also propose a method to simplify data sender’s key management using identity-based key exchange protocol. Finally, we provide implementation results of our schemes to show the comparable efficiency of our schemes with previous PEKS/PAEKS schemes.