Oracles and Signatures

Introduction

Digital signatures are all around us (though barely noticeable by the average person), especially in electronic (digital) financial transactions. Like its paper-and-pen ancestor, a signature has as its purposes guaranteeing the integrity of the data transmitted, as well as its authenticity; everybody concerned (or at least every honest user) requires that the relevant data has not been modified in transmission, and that the data purportedly sent by (say) bank B to bank A did in fact originate at B. Note that, as far as signatures are concerned, secrecy or confidentiality are not a factor. These, which were historically the most important purposes of cryptography are, when considering signatures, of no immediate importance.

The most commonly used method of creating a digital signature is by using the RSA algorithm in some form. We shall discuss this briefly in this article-with apologies to those readers who are familiar with it-and continue with a brief discussion on hash functions. This is where differences of opinion appear: many theoretical cryptologists thoroughly disapprove of the use of hash functions, or specifically of their use in security proofs, whereas practice oriented cryptologists cannot do without them. The matter in dispute is the admissibility of using hash functions as random functions in cryptographic protocols (or pseudorandom functions, where that term is used in its complexity theoretic sense-see later). When a security proof involves such use of a hash function, the proof (if correct in all other respects!) is said to be in the Random Oracle Model (ROM), if no such call on a hash function is made the proof is valid in the Standard Model. It is not quite clear whether this appropriation of the word "Standard" is justified, but we are stuck with it. Nobody will dispute that proving something in the standard model is a more demanding task than doing so in the ROM.