Paper 2010/468

Generic Constructions of Parallel Key-Insulated Encryption: Stronger Security Model and Novel Schemes

Goichiro Hanaoka and Jian Weng


Exposure of a secret key is a significant threat in practice. As a notion of security against key exposure, Dodis et al. advocated key-insulated security, and proposed concrete key-insulated encryption (KIE) schemes in which secret keys are periodically updated by using a physically ``insulated'' helper key. For significantly reducing possibility of exposure of the helper key, Hanaoka et al. further proposed the notion of parallel KIE (PKIE) in which multiple helper keys are used in alternate shifts. They also pointed out that in contrast to the case of the standard KIE, PKIE cannot be straightforwardly obtained from identity-based encryption (IBE). In this paper, we first discuss that previous security models for PKIE are somewhat weak, and thus re-formalize stronger security models for PKIE. Then we clarify that PKIE can be generically constructed (even in the strenghthened security models) by using a new primitive which we call one-time forward secure public key encryption (OTFS-PKE) and show that it is possible to construct OTFS-PKE from arbitrary IBE or hierarchical IBE (without degenerating into IBE). By using our method, we can obtain various new PKIE schemes which yield desirable properties. For example, we can construct first PKIE schemes from lattice or quadratic residuosity problems (without using bilinear maps), and PKIE with short ciphertexts and cheaper computational cost for both encryption and decryption. Interestingly, the resulting schemes can be viewed as the partial solutions to the open problem left by Libert, Quisquarter and Yung in PKC'07.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. A preliminary version of this paper will be presented at Seventh Conference on Security and Cryptography for Networks (SCN 2010)
public-key cryptography
Contact author(s)
cryptjweng @ gmail com
2010-09-13: last of 2 revisions
2010-09-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Goichiro Hanaoka and Jian Weng},
      title = {Generic Constructions of Parallel Key-Insulated Encryption: Stronger Security Model and Novel Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2010/468},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.