Generic Transformation from Weakly to Strongly Unforgeable Signatures

Current techniques for transformingunforgeable signature schemes (the forged message has never been signed)to strongly unforgeable ones (the forged message could have been signed)require supplementary components to be added onto the original key pairsof the schemes. In addition, some of them can only be applied to acertain type of signature schemes. In this paper, we propose a newgeneric transformation technique which converts \it any unforgeablesignature scheme into a strongly unforgeable one \it without modifyingany component in the original key pair. This makes our techniqueespecially compatible for practical use. Our technique is based on \itstrong one-time signature schemes. We show that they can be constructedefficiently from any one-time signature scheme that is based on one-wayfunctions. The performance of our technique also compares favorably withthat of current ones. Besides, it is shown in this paper that ourtransformation can further be applied to schemes satisfying only a \itweak variant of unforgeability without any further modification.Furthermore, our technique can also be used for constructing stronglyunforgeable signature schemes in other cryptographic settings whichinclude certificateless signature, identity-based signature, and severalothers. To the best of our knowledge, similar extent of versatility isnot known to be supported by any of those comparable techniques. Finallyand of independent interest, we show that our generic transformationtechnique can be modified to an \it on-line/off-line signature scheme,which possesses a very efficient signing process.