General Conversion for Obtaining Strongly Existentially Unforgeable Signatures

We say that a signature scheme is strongly existentially unforgeable if no adversary, given message/signature pairs adaptively, can generate a new signature on either a signature on a new message or a new signature on a previously signed message. Strongly existentially unforgeable signature schemes are used to construct many applications, such as an IND-CCA2 secure public-key encryption scheme and a group signature scheme. We propose two general and efficient conversions, both of which transform a secure signature scheme to a strongly existentially unforgeable signature scheme. There is a tradeoff between the two conversions. The first conversion requires the random oracle, but the signature scheme transformed by the first conversion has shorter signature length than the scheme transformed by the second conversion. The second conversion does not require the random oracle. Therefore, if the original signature scheme is of the standard model, the strongly existentially unforgeable property of the converted signature scheme is proved also in the standard model. Both conversions ensure tight security reduction to the underlying security assumptions. Moreover, the transformed schemes by the first or second conversion satisfy the on-line/off-line property. That is, signers can precompute almost all operations on the signing before they are given a message.