Cryptology ePrint Archive: Report 2010/468

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

Goichiro Hanaoka and Jian Weng

Abstract: 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.

Category / Keywords: public-key cryptography / public-key cryptography

Publication Info: A preliminary version of this paper will be presented at Seventh Conference on Security and Cryptography for Networks (SCN 2010)

Date: received 3 Sep 2010, last revised 12 Sep 2010

Contact author: cryptjweng at gmail com

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20100913:025231 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]