Recently, a lot of researches focused on identity-based encryption (IBE). The advantage of this scheme is that it can reduce the cost of the public key infrastructure by simplifying certificate management. Although IBE has its own innovations, one of its weaknesses is the key escrow problem. That is, the private key generator in IBE knows decryption keys for all identities and consequently can decrypt any ciphertexts. The certificate-based encryption (CBE) scheme proposed in EUROCRYPT 2003 provides a solution for the key escrow problem by allowing the certification authority to possess a partial decryption key that comprises the full decryption key together with the user-generated private key. In this paper, we propose new CBE schemes without pairing and prove them to be Indistinguishability under Chosen Ciphertext Attack secure in the random oracle model based on the hardness of the computational Diffie-Hellman problem. When compared with other CBE schemes, our schemes are significantly efficient in terms of performance, which makes our schemes suitable for computation-limited node (e.g., sensor, wearable device) networks. Copyright (c) 2016 John Wiley & Sons, Ltd.