Abstract: Certificate-based cryptography is a new cryptographic paradigm that provides an interesting balance between identity-based cryptography and traditional public-key cryptography. It not only eliminates the third-party query problem and simplifies the complicated public-key certificate management problem in the traditional public-key infrastructure, but also solves the key escrow and key distribution problems inherent in identity-based cryptography. As an extension of key encapsulation mechanism in the certificate-based setting, certificate-based key encapsulation mechanism preserves some of the most attractive features of certificate-based cryptography. In this paper, we propose an efficient certificate-based key encapsulation mechanism from bilinear pairings which is provably-secure without the random oracle model. Under the hardness of the truncated decision q-augmented bilinear Diffie-Hellman exponent problem and the decision 1-bilinear Diffie-Hellman inversion problem, we prove in the standard model that the proposed scheme achieves indistinguishable security under adaptive chosen-ciphertext attacks. The proposed scheme is quite efficient in the computation. Its performance is competitive with the existing certificate-based key encapsulation mechanism in the random oracle model. Compared with the existing certificate-based key encapsulation mechanism in the standard model, the proposed scheme enjoys less computation cost and lower communication bandwidth, and hence, it outperforms the known standard-model certificate-based key encapsulation mechanism in the literature.