Certificate-based encryption (CBE) is a new asymmetric encryption paradigm which combines traditional public-key encryption and identity-based encryption (IBE) while preserving some of their most attractive features. It provides an efficient implicit certificate mechanism which eliminates the third-party queries and simplifies the certificate revocation problem in the traditional PKI. It also solves the key escrow problem and the key distribution problem inherent in IBE. In this paper, we propose a quite efficient CBE scheme which is chosen-ciphertext secure in the random oracle model. The proposed CBE scheme requires computing only one bilinear pairing and introduces no redundancies in ciphertext. Compared with the existing CBE schemes, our scheme enjoys better performance on both the computation efficiency and the communication bandwidth.