Certificate-based cryptography overcomes the inherent shortcomings in traditional public key cryptography and identity-based cryptography. It provides effective mechanisms to design efficient public key cryptography systems with less reliance on underlying infrastructure. As a classic primitive in public key cryptography, signcryption performs signature and encryption in a single logical step, by integrating confidentiality, integrity, authentication and non-repudiation much more efficiently than the traditional sign-then-encrypt approach. In this paper, we first define an enhanced security model for certificate-based signcryption. We then analyze an existing certificate-based signcryption scheme, and show that it is insecure due to two classic attacks. Furthermore, we propose a new certificate-based signcryption scheme. Our scheme is proven secure against adaptive chosen ciphertext attacks and adaptive chosen message attacks in the random oracle model.