A significant amount of electronic health records (EHRs) have been kept in the cloud due to the quick development of healthcare information systems. However, storing EHRs in the cloud may raise security and data privacy issues. Because of the privacy of a patient's medical data, storing it on a cloud server requires encryption. Public-key encryption with keyword search (PEKS) solves the problem of retrieval on ciphertext, thus avoiding the problem of plaintext information leakage. However, most PEKS schemes are susceptible to inside keyword guessing attacks (KGA). Besides, transmitting the trapdoor to the cloud server requires a secure channel, which is impractical in healthcare information systems. Roughly speaking, PEKS does not protect the privacy of trapdoor and it is expensive to establish secure channels. In this paper, we propose a secure-channel free public key authenticated encryption with multi-keyword search (SCF-PAEMKS) scheme. The proposed SCF-PAEMKS scheme supports c