AN EFFICIENT EXISTENTIALLY UNFORGEABLE SIGNATURE SCHEME AND ITS APPLICATIONS

A signature scheme is existentially unforgeable if, given any polynomi al (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 th e message m, it is computationally infeasible to generate a pair (m(k1), 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 f or a reasonable setting of parameters requires at most six times the a mount of time needed to generate a signature using ''plain'' RSA (whic h is not existentially unforgeable). We point out applications where o ur scheme is desirable.