An efficient existentially unforgeable signature scheme and its applications

A signature scheme is existentially unfargeaMe if, given any polynomial (in the security parameter) number of pairs (m1. S(m1)), (m2. S(m2)),.... (mk. S(mk)). where 5(m) denotes the signature on the message HI, it is computationally infeasible to generate a pair (mk +1. 5(mk+1)) for any message [m1. . . mk]. 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. © 1998 International Association for Cryplologic Research.