Practical parallel key-insulated encryption with multiple helper keys

Parallel key-insulated encryption (PKIE) usually allows two independent helper keys to be alternately used in temporary secret key update operations. At least half of temporary secret keys would be exposed and at least half of ciphertexts could be decrypted if one of the helper keys is exposed. In this paper, we propose a new PKIE scheme with mm helper keys, where m∈Z,m>2m∈Z,m>2. If one of the helper keys is exposed, only 1/m1/m temporary secret keys would be exposed and 1/m1/m ciphertexts could be decrypted, so the new PKIE scheme can greatly decrease loss due to key-exposure. The scheme is provably secure without random oracles based on a bilinear group of composite order. Most important, the scheme is practical and much more efficient than the extended ones from the previous PKIE schemes.