Abstract. We put forward new techniques for designing signature schemes. As
a result, we present practical signature schemes based on the CDH, the RSA,
and the SIS assumptions. Our schemes compare favorably with existing schemes
based on these assumptions.
Our core idea is the use of tag-based signatures. Concretely, each signatures
contains a tag which is uniformly chosen from a suitable tag set. Intuitively, the
tag provides a way to embed instances of computational problems. Indeed, carefully
choosing these tag spaces provides new ways to partition the set of possible
message-tag pairs into “signable” and “unsignable” pairs. In our security proof,
we will thus be able to sign all adversarially requested messages, and at the same
time use an adversarially generated forgery with suitably large probability.
