"Certificateless Public Key Cryptography" has very appealing features, namely it does not require any public key certification (traditional Public Key Cryptography) nor having key escrow problem (Identity-Based Cryptography). Unfortunately, construction of Certificateless Public Key Encryption (CLPKE) schemes has so far depended on the use of Identity-Based Encryption, which results in the bilinear pairing-based schemes that need costly operations. In this paper, we consider a relaxation of the original model of CLPKE and propose a new CLPKE scheme that does not depend on the bilinear pairings.