DS ⇒ IBS (certificates)
Statement
Let be an EUF-CMA signature scheme for arbitrary-length messages, with message space , into which pairs are encoded injectively. The certificate construction’s runs and outputs ; samples and outputs with ; a signature on is ; and verifies for iff and . It is an EUF-ID-CMA-unforgeable identity-based signature scheme, without random oracles — BNN04, who note that the construction is folklore. Its identities and messages are bit strings, and it is -correct when is, since a signature verifies iff the certificate and the signature under both do — standard.
Sketch
A forgery either certifies a pair that the challenger never certified, a forgery under , or reuses the key certified for , whose secret key the adversary never saw, and then is a forgery under on a message that identity never signed. The reduction guesses which case occurs and, in the second, which identity — standard.