Cramer-Damgard Signatures Revisited: Efficient Flat-Tree Signatures Based on Factoring

At Crypto 96 Cramer and Damgård proposed an efficient, tree-based, signature scheme that is provably secure against adaptive chosen message attacks under the assumption that inverting RSA is computationally infeasible. In this paper we show how to modify their basic construction in order to achieve a scheme that is provably secure under the assumption that factoring large composites of a certain form is hard. Our scheme is as efficient as the original Cramer Damgård solution while relying on a seemingly weaker intractability assumption