Certificateless public key cryptography (CLPKC) can solve the problems of certificate management in a public key infrastructure (PKI) and of key escrows in identity-based public key cryptography (ID-PKC). In CL-PKC, the key generation center (KGC) does not know the private keys of all users, and their public keys need not be certificated by certification authority (CA). At present, however, most certificateless encryption schemes are based on large integer factorization and discrete logarithms that are not secure in a quantum environment and the computation complexity is high. To solve these problems, we propose a new certificateless encryption scheme based on lattices, more precisely, using the hardness of the learning with errors (LWE) problem. Compared with schemes based on large integer factorization and discrete logarithms, the most operations are matrix-vector multiplication and inner products in our scheme, our approach has lower computation complexity. Our scheme can be proven to be indistinguishability chosen ciphertext attacks (IND-CPA) secure in the random oracle model.