The emergence of healthcare cloud services has provided great convenience for both hospitals and patients. It can help hospitals save local space and facilitate the management of electronic medical records. Data stored in ciphertext form on the cloud ensures the privacy of patients’ information. However, it becomes very difficult to search for the desired data on the ciphertext. Public Key Encryption with Keyword Search (PEKS) solves this problem. PEKS faces internal keyword guessing attack due to the relatively small keyword space on the healthcare cloud. Therefore, Public Key Authenticated Encryption with Keyword Search (PAEKS) is proposed. However, with the increasing amount of medical data, those schemes based on PAEKS suffer from search inefficiency. In this paper, we propose an efficient searchable encryption scheme based on PAEKS using parallel search method, which supports fast search. Meanwhile, based on Decisional Bilinear Diffie-Hellman (DBDH) assumption, we prove that our scheme satisfies ciphertext indistinguishability and trapdoor indistinguishability under random oracle model, and resists both internal and external keyword guessing attack. Through theoretical and experimental comparisons, the results show that our scheme searches more efficiently than most of the existing PAEKS schemes, without leading to additional security losses and communication costs. Therefore, our scheme is more suitable for healthcare cloud applications.