Provably Unforgeable Signatures

Very strong definitions of security for signature schemes have been proposed in the literature. Constructions for such schemes have been proposed, but so far they have only been of theoretical interest and have been considered far too inefficient for practical use.Here we present a new scheme that satisfies these strongest definitions and uses essentially the same amount of computation and memory as the widely applied RSA scheme. The scheme is based on the well known RSA assumption.Our signatures can be thought of as products resulting from a two-dimensional Lamport scheme, where one dimension consists of a list of public constants, and the other is the sequence of odd primes.