Identity-based encryption can simplify the certificate management problem of traditional public key cryptosystem. But it also has an inherent drawback, called the key escrow problem. A malicious key generation center (KGC) can easily generate the user’s private key to decrypt ciphertexts or perform illegal activities. In this paper, we propose an anonymous key issuing-based IBE protocol to solve the key escrow problem. The protocol separates the tasks of authentication and key generation, which are respectively implemented by two authorities. Identity-certifying authority (ICA) authenticates the user and collaborates with him to generate a pseudo-identity to hide the real one, and issues an evidence to prove its validity. KGC generates private keys for users based on their pseudo-identities. We prove the security based on recipient anonymity and ciphertext indistinguishability, with the assumption that KGC does not collude with ICA. Compared with Emura’s work, we weaken the communication restriction between KGC and ICA by allowing KGC to access the identity list stored by ICA arbitrarily, and only restrict its query method during the key generation phase, making it accessible through the index. This lowers the security assumption and makes it more realistic. Meanwhile, we eliminate the need for secure channels using blinding technique, and only require authentication channels to ensure that messages are not being tampered with. Our protocol has higher security and utility.