Attribute-based encryption (ABE) is an exciting alternative to public-key encryption, as ABE develops encryption systems with high expressiveness, without the need for a public key infrastructure (PKI) that makes publicly available the mapping between identities (sets of attributes), public keys, and validity of the latter. Any setting, PKI or attribute- based, must provide a means to revoke users from the system. To mitigate the limitation of ABE with regard to revocation, we propose an attribute-based key-insulated encryption (ABKIE) scheme, which is a novel ABE scheme. In our ABKIE scheme, a private key can be renewed without having to make changes to its public key (a set of attributes). The scheme is secure against adaptive chosen ciphertext attacks. The formal proof of security is presented under the Selective-ID security model, i.e. without random oracles, assuming the decision Bilinear Diffie-Hellman problem is computationally hard. To the best of our knowledge, this is the first ABKIE scheme up to now. Further, this is also the first concrete ABE construction with regard to revocation.