Constructing Provably Secure Identity-Based Signature Schemes

Abstract

An identity-based cryptosystem (IBC) is a public-key system where the public key can be represented by any arbitrary string such as an e-mail address. The notion was introduced by Shamir with the primary goal of simplifying certificate management. An identity-based signature(IBS) is the identity-based counter part of a digital signature. In the first (and primary) part of the work, we take a closer look at an IBS due to Galindo and Garcia–GG-IBS, for short. GG-IBS is derived through a simple and elegant concatenation of two Schnorr signatures and, importantly, does not rely on pairing. The security is established through two algorithms (both of) which use the Multiple-Forking(MF) Algorithm to reduce the problem of computing the discrete logarithm to breaking the IBS. Our focus is on the security argument : It turns out that the argument is flawed and, as a remedy, we sketch a new security argument. However, the resulting security bound is still quite loose, chiefly due to the usage of the MF Algorithm. We explore possible avenues for improving this bound and , to this end, introduce two notions pertaining to random oracles termed dependency and independency. Incorporating (in) dependency allows us to launch the nested replay attack far more effectively than in the MF Algorithm leading to a cleaner,(significantly) tighter security argument for GG-IBS, completing the final piece of the GG-IBS jigsaw. The second part of the work pertains to the notion of selective-identity (sID) for IBCs. The focus is on the problem of constructing a fully-secure IBS given an sID-secure IBS without using random oracles and with reasonable security degradation.