Identity-based parallel key-insulated signature: Framework and construction

To minimize the damage caused by key-exposure in ID-based signatures, in ISPEC'06 Zhou et al (2006) proposed an ID-based key-insulated signature (IBKIS) scheme. However, their scheme is not strong key-insulated, i.e, if a user's helper is compromised, the adversary can derive all of this user's secret keys for any time period. Moreover, in practice, to alleviate the damage in case of key-exposure, secret keys in IBKIS schemes have to be updated at very short intervals, which will increase the risk of helper key-exposure. It is important to note that even for an IBKIS scheme with strong key-insulated security, once a user's helper and one of his secret keys are both compromised, the adversary can also derive all of this user's secret keys for any time period. Is it possible to allow frequent key-updates without increasing the risk of helper key-exposure in IBKIS systems? In this paper, we extend Hanaoka et al (2006) parallel key-insulated mechanism to ID-based signature scenarios, and present an ID-based parallel key-insulated signature (IBPKIS) scheme. Compared with Zhou et al (2006) IBKIS scheme, our scheme enjoys three attractive features: (i) it is strong key-insulated; (ii) it can allow frequent key-updates without increasing the risk of helper key-exposure, and over all, enhances the security of the system; (ii) even if one of a user's helpers and some of his secret keys are both exposed, it is impossible for an adversary to derive all of this user's secret keys.