The notion of certificate less public key encryption (CL-PKE or CLE) was initiated by Al Riyami and Paterson and grew out of the need for a public key mechanism to eliminate the built-in key escrow of identity based encryption (IBE) without introducing digital certificates and the management overhead that this entails. Unlike other approaches that require complex private or public keys, an efficient CLE protocol is presented in this paper, which uses very small private and public keys and is appropriate for communication in low-bandwidth channels. To support our comparative claims, implementation issues and complexity results are discussed in detail.