In this paper, we address the question of providing security proofs for signature schemes in the so-called random oracle model. In particular, we establish the generality of this technique against adaptively chosen message attacks.
Our main application achieves such a security proof for a slight variant of the El Gamal signature scheme where committed values are hashed together with the message.
This is a rather surprising result since the original El Gamal is, as RSA, subject to existential forgery.

Signatures, Random Oracle Model, Forking Lemma, El Gamal

Advances in Cryptology - Proceedings of EUROCRYPT '96
(may 12 - 16, 1996, Zaragoza, Spain)
U. Maurer, Ed.
Pages 387-398, LNCS 1070, © Springer-Verlag, 1996.

Extended abstract:
Full version:		Journal of Cryptology
Talk (Slides):

David Pointcheval	(LIENS-CNRS, Ecole Normale Supérieure)
Jacques Stern	(LIENS, Ecole Normale Supérieure)