Bandwidth-efficient attribute-based key-insulated signatures with message recovery

In order to minimize the impact of secret signing key exposure in Attribute-Based Signature (ABS) scenario, we design two key-policy Attribute-Based Key-Insulated Signature with Message Recovery (ABKIS-MR) schemes for expressive Linear Secret-Sharing Scheme (LSSS)-realizable access structures utilizing only 4 bilinear pairing operations in signature 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. We thereafter present a small attribute universe signature-policy ABKIS-MR scheme supporting LSSS-realizable access structures with significantly low communication and computation cost. The (strong) key-insulated security of our ABKIS-MR primitives is reduced to the classical computational Diffie Hellman Exponent problem in selective attribute set and random oracle model. We show that all the proposed signature constructions provide signer privacy. To the best of our knowledge, the proposed signature-policy ABKIS-MR is the first ABS scheme in signature-policy flavor dealing with key exposure problems employing key-insulation mechanism.