Key-Insulated Public Key Encryption with Auxiliary Helper Key: Model, Constructions and Formal Security Proofs

Thi Lan Anh PHAN  Goichiro HANAOKA  Kanta MATSUURA  Hideki IMAI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E90-A   No.9   pp.1814-1829
Publication Date: 2007/09/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e90-a.9.1814
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
key insulated public key encryption,  auxiliary helper key,  IND-KE-CCA,  

Full Text: PDF>>
Buy this Article

To deal with the problem of secret key exposure, Dodis, Katz, Xu and Yung [6] proposed a key-insulated public key encryption (KIE), which uses the secure helper key to update the secret key more often and helps to minimize the damage overall. We take this idea further in improving the helper key security by introducing an auxiliary helper key besides of the main helper key. The auxiliary helper key is used less than the main helper key and can help the system to reduce the damage even in case of helper key exposure. This paper give two different schemes of KIE with auxiliary helper key. There are trade-offs between public key length and ciphertext size, as well as between encryption algorithms and decryption algorithms in these two schemes. With these trade-offs, it is flexible to choose an efficient one to implement in reality. We also show concrete constructions with chosen-ciphertext security. The formal security proofs for all schemes are given in this paper, based on the CBDH assumption [2] in the random oracle model.