Attribute Based Key-Insulated Signatures with Message Recovery

In order tominimize the impact of secret signing key exposure in attribute based signature scenario, we design two attribute based key-insulated signature (ABKIS) with message recovery schemes for expressive linear secret-sharing scheme (LSSS)-realizable access structures utilizing only 4 bilinear pairing operations in verification process and making the message-signature length constant. The first scheme deals with small universes of attributes while the second construction supports large universe of attributes. The signing key is computed according to LSSS access structure over signer's attributes, and is later updated at discrete time periods with the help of a physically secure but computationally limited device, called helper, without changing the access structure. A signing key for some time period is used to sign every message during that time period. The original message is not required to be transmitted with the signature, however, it can be recovered during verification procedure. The size of signing key in the proposed schemes is quadratic in number of attributes. The (strong) key-insulated security of our ABKIS primitives is reduced to the classical computational Diffie Hellman Exponent problem in selective attribute set and random oracle model. We also show that both the proposed signature constructions provide signer privacy.