language: en

[Appears in Journal of the ACM, Vol. 39, No. 1, January 1992, pp. 214-233. Prelimanary version in Proceedings of the 20th Annual Symposium on Theory of Computing, ACM, 1988.]

How to Sign Given Any Trapdoor Permutation

Mihir Bellare Silvio Micali
January 1992

Abstract We present a digital signature scheme which is based on the existence of any trapdoor permutation. Our scheme is secure in the strongest possible natural sense: namely, it is secure against existential forgery under adaptive chosen message attack.

Department of Computer Science & Engineering,
Mail Code 0114,
University of California at San Diego,
9500 Gilman Drive, La Jolla, CA 92093.
E-mail: mihir@cs.ucsd.edu.

[Work done while author was at MIT, supported in part by NSF grant CCR-87-19689.]

MIT Laboratory for Computer Science,
545 Technology Square, Cambridge, MA 02139.

[Supported in part by NSF grant DCR-84-13577 and ARO grant DAALO3-86-K-0171.]

1 Introduction