Security arguments for digital signatures and blind signatures

Since the appearance of public-key cryptography in the seminal Diffie-Hellm an paper, many new schemes have been proposed and many have been broken. Th us, the simple fact that a cryptographic algorithm withstands cryptanalytic attacks for several years is often considered as a kind of validation proc edure. A much more convincing line of research has tried to provide "provab le" security for cryptographic protocols. Unfortunately, in many cases, pro vable security is at the cost of a considerable loss in terms of efficiency . Another way to achieve some kind of provable security is to identify conc rete cryptographic objects, such as hash functions, with ideal random objec ts and to use arguments from relativized complexity theory. The model under lying this approach is often called the "random oracle model." We use the w ord "arguments" for security results proved in this model. As usual, these arguments are relative to well-established hard algorithmic problems such a s factorization or the discrete logarithm. In this paper we offer security arguments for a large class of known signat ure schemes. Moreover, we give for the first time an argument for a very sl ight variation of the well-known El Gamal signature scheme. In spite of the existential forgery of the original scheme, we prove that our variant resi sts existential forgeries even against an adaptively chosen-message attack. This is provided that the discrete logarithm problem is hard to solve. Next, we study the security of blind signatures which are the most importan t ingredient for anonymity in off-line electronic cash systems. We first de fine an appropriate notion of security related to the setting of electronic cash. We then propose new schemes for which one can provide security argum ents.