An efficient existentially unforgeable signature scheme and its applications

A signature scheme is existentially unforgeable if, given any polynomial (in the security parameter) number of pairs (m(1), S(m(1))), (m(2), S(m(2))),..., (m(k), S(m(k))), where S(m) denotes the signature on the message m, it is computationally infeasible to generate a pair (m(k+1), S(m(k+1))) for any message m(k+1) is not an element of {m(1),..., m(k)}. We present an existentially unforgeable signature scheme that for a reasonable setting of parameters requires at most six times the amount of time needed to generate a signature using "plain" RSA (which is not existentially unforgeable). We point out applications where our scheme is desirable.