The area of security for heterogeneous sensor networks (HSNs) is still an open research field that requires new cryptographic solutions. Recent results have demonstrated that elliptic curve cryptography (ECC) and pairing-based cryptography (PBC) are computationally feasible on sensor devices. This allows a wide range of novel security mechanisms, like identity-based encryption (IBE), to be considered for wireless sensor networks (WSNs). In this paper we present an efficient security bootstrapping mechanism for HSNs that uses IBE and exploits the enhanced capabilities of high-end cluster heads. Our asymmetric security scheme provides authenticated key distribution without using expensive certificates. It also achieves significant savings in communication overhead and in the number of keys stored on sensor devices. We also present TinyIBE, which is to our knowledge, the first implementation of a complete identity-based encryption scheme for sensor networks. Our evaluation results and comparison with the state of the art show that TinyIBE is a superior security scheme for HSNs which provides affordable public key cryptography without requiring hardware acceleration. With this work we prove that ID-based encryption is not only possible on sensor nodes but is an attractive security solution in this application space.