Signature scheme

In addition to all these possible practical applications, digital signature schemes are important building blocks for many theoretical protocols in the field of distributed computing. 

For all these reasons, digital signature schemes seem to be the part of modem cryptology that is most accepted in society and has the best chance of being promoted by governments and industry. 

Most of what was just said for the digital signatures also has to hold for the surrounding protocol connecting the signatures to real identities (technically this will be key distribution), because the authenticity and identity function can oidy be provided if both the signature scheme and this protocol work correctly. 

Three related types of cryptologic schemes are not always precisely distinguished from digital signature schemes ... 

This symmetry between senders and recipients is usually reflected in the system structure the schemes are then called symmetric authentication schemes (see Section 2.1). In contrast, digital signature schemes are sometimes called asymmetric authentication schemes. However, schemes exist that provide mere authentication and are not symmetric in this sense [OkOh91] (called non-transitive signature schemes there). 

This third demarcation seems unnecessary from a purely scientific point of view, but for several practical reasons, it is not Digital signature schemes, and authentication schemes generally, have nothing to do with keeping messages secret. For that purpose, one has secrecy schemes. 

Hence, authentication schemes, and digital signature schemes in particular, carmot be treated as a variant of secrecy schemes, but need both definitions and constructions of their own. 

This is why invisible signatures were introduced in [ChAn90]. (Conversely, if one says that the purpose of digital signature schemes is to imitate handwritten signatures as closely as possible, an invisible signature scheme does too little.)... 

This last feature gave rise to the original name undeniable . However, it is a feature common to all signature schemes and therefore not characteristic. Moreover, the old terminology is very confusing with the noun undeniability It meant both that signatures cannot be denied and the characteristic feature that they cannot be shown round, which is called invisibility here. 

Moreover, the history of digital signature schemes is so closely linked to the history of the related types of schemes mentioned in Section 1.5 that parts of the history of those also have to be outlined. 

Working on the usual assumptions of classical cryptography, one would have thought that there is no such thing as a digital signature scheme Classical cryptographic schemes assume that a sender and a recipient have a common secret, which is unknown to outsiders from whom the sender and the recipient want to protect themselves. 

The idea that digital signature schemes might exist was first published in the directive article [DiHe76]. 

Figure 2.1. Components of ordinary digital signature schemes.

A bit more precisely, the components of an ordinary digital signature scheme and their interaction are usually depicted as in Figure 2.2. ... 

The main security requirement on such a digital signature scheme is, roughly speaking, that one cannot forge signatures although one knows the public key. A necessary (but not sufficient) condition for this is that one cannot compute the secret key from the public key. 

The security of such digital signature schemes can therefore only be computational, i.e., hold in the sense of complexity theory It relies on the fact that in reality, a forger has too little time to carry out the trivial forging algorithm, and that no much more efficient forging algorithm is available. 

Digital signature schemes have one more advantage over symmetric authentication schemes, besides allowing disputes to be settled Key distribution is simpler. 

In the theoretical treatment of digital signature schemes, one simply assumes that a reliable broadcast network can be used during a special key-distribution phase. Only the real messages, later on, are sent over arbitrary channels. 

---