About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Theoretical Computer Science
Paper
Cramer-Damgård signatures revisited: Efficient flat-tree signatures based on factoring
Abstract
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. © 2006 Elsevier Ltd. All rights reserved.