On shared randomness and the size of secure signatures

We present an efficient signature scheme that is not existentially forgeable under adaptively chosen message attacks cite{gmr. The main feature of our scheme is that any practical number of signatures can be made while the size of the signatures remains relatively small, under the condition that all signers have access to a list of shared random strings. More precisely, let integers $l$ and $d$ be fixed and let $k$ be a security parameter. Given a list of $l$ random $(k-1)$-bit strings shared by all signers, at least $l^d$ signatures can be made by each signer in our scheme, where the size of a public key is $k$ bits. The size of a signature does not exceed $(4d-3)k$ bits. The first secure signature scheme where such trade-offs between shared randomness and the size of signatures has been realized was proposed by Dwork and Naor at Crypto '94 [1]. Their scheme is based on RSA, while their method for achieving efficiency relies on special properties of RSA that seem to go beyond the properties of general trapdoor permutations. Our contribution is to show that a secure signature scheme with similar efficiency can be based on a general cryptographic assumption that is potentially weaker than an RSA assumption, namely the existence of a family of claw-free trapdoor permutations [3], which can be constructed under the factoring assumption.