Miyaji Laboratory

A digital signature is said to be existentially unforgeable under if an adversary who can repeatedly get a signature on a message of his choice cannot generate a signature on a new message. But an adversary can forge a signature on a previously signed message. The existential unforgeability may not be the most secure notion of a digital signature. In 2002, more secure security notion of digital signatures, which called strongly existential unforgeability, was proposed. A digital signature is said to be strongly existentially unforgeable if an adversary who can repeatedly get a signature on a message of his choice cannot even generate a signature on previously signed message. That is, a strongly existentially unforgeable signature is desirable security level for a digital signature. Despite this, many signatures have been proposed so far satisfy the existential unforgeability, not strongly one.
Various conversions from existential unforgeability signature to strongly existentially unforgeable one are studied by many researchers. Note that the notion of strongly existential unforgeability can be defined on theID-based signature as well as a usual certificate-based signature. ID-based signature is a signature under the ID-based paradigm which can use an user's ID such as an e-mail address as an user's public key. For example, ID-based signature proposed by Paterson and Schuldt is proved to be existential unforgeability but is not strongly existentially unforgeability.
The target of my study is to give an efficient construction that can convert a existential unforgeable ID-based signature to a strongly one. Recently, such a construction was proposed by Boneh et al. in the standard model. This construction converts a existential unforgeable signature with a partitioned property, which is defined by them, into a strongly unforgeable one by using a collision-resistant hash function and computational Diffie-Hellman problem. Many DLP-based signatures are partitioned signatures, but all signatures are not necessarily are partitioned. For example, DSS signature may not be a partitioned signature. The construction used the target collision resistant hash function, which is a weaker primitive than a collision resistant hash function, instead of the collision resistant hash function, is proposed by Matsuda et al. Their construction also allows only (simulatable)-partitioned unforgeable signatures as the underlying signature.
These techniques is not universal in the sense that they can not be used to construct any signature such as ID-based signature to a strongly existentially unforgeable signature. Indeed, due to the additional parametersto the original key pairs(public key and secret key) of underlying signature, their construction cannot construct strongly existentially unforgeable ID-based signature.
Another construction was proposed by Teranishi et al. This construction uses a randomized-trapdoor hash function, so called a chameleon commitment, and convert any existentially unforgeable signature to a strongly one. Around the same time, similar construction was proposed independently by Steinfeld et al. Both conversions can use an underlying signature without a partitioned property However, their construction also need some auxiliary parameters in addition to the original key pairs of an underlying signature. So, their construction may not be universal. In fact, to construct a strongly existentially unforgeable ID-based signature, a randomized-trapdoor hash function should work under the ID-based paradigm. But such a randomized-trapdoor hash function has not been proposed. Therefore, it is not clear whether a strongly existential unforgeable ID-based signature can be constructed by using these methods. Huang et al. proposed the first construction which does not require any auxiliary parameter in addition to the original key pairs of an underlying signature. Their construction converts a existentially unforgeable signature to a strongly unforgeable one by using strongly existentially unforgeable one-time signature.
Their method can construct a strongly existentially unforgeable ID-based signature from a existential unforgeable ID-based signature for the first time. This construction does not require any additional parameter to a public key of the resulting signature. But the signature itself includes the public key and a signature of the one-time signature scheme in addition to a signature of a existentially unforgeable signature, and thus, the size of resulting signature becomes rather large. In summary, all constructions by Boneh, Matsuda, Teranishi, Steinfeld and Huang require some additional (not simple) features or functions such as a partitioned property of a signature, a randomized-trapdoor hash function, and a strongly existential unforgeable one-time signature. Furthermore, these constructions by Boneh, Matsuda, Teranishi and Steinfeld may not be universal and, thus, cannot achieve strongly existentially unforgeable ID-based signature. On the other hand, the construction by Huang can achieve strongly unforgeable ID-based signature, but a signature size becomes large.
I propose the construction which is universal and simple, which does not require any complex features or functions.