Certificate-based encryption is a useful primitive that combines traditional public key encryption and identity-based encryption while preserving some of their most attractive features. It not only simplifies the cumbersome certificate management in traditional PKI, but also solves the key escrow problem inherent in identity-based encryption. In this paper, we propose a new certificate-based encryption scheme without random oracles that is provably secure against key replacement attacks. The proposed certificate-based encryption scheme is proven to be secure under the hardness of the decision 3-Party Diffie- Hellman problem in the standard model. Performance comparison shows that the proposed scheme outperforms all the previous standard-model certificate-based encryption schemes in the literature.