On Provable Security for Digital Signature Algorithms

In this paper we consider provable security for ElGamal-like digital signature schemes. We point out that the good the security criterion on the underlying hash function is pseudorandomness. We extend Pointcheval-Stern's results about the use of the random oracle model to prove the security of two variants of the US Digital Signature Algorithm against adaptive attacks which issue an existential forgery. We prove that a very practical use of the random oracle model is possible whith tamper-resistant modules.