Message space

With each Scheme, it must be mentioned for which value v V it fulfils the specification Specy. For instance, signature schemes for different message spaces v = M will be permitted. 

Instead, one could also fix v once and for all, e.g., one could define that the message space of all signature schemes were the set of all bit strings. As the opposite extreme, one could make V an input parameter, e.g., in initialization or in a global transaction at the system start. But in both cases, that should have been done in Section 5.2.4 already. 

Special Specification Parameters Special Message Spaces... 

Normally, one requires that arbitrary messages can be authenticated, i.e., the message space M is the set of all strings over an alphabet, say 0, 1J" ". This is the case in the GMR definition. (In this sense, something like RSA is a signature scheme only in combination with the description of how arbitrarily long messages are mapped into blocks.)... 

However, in some applications, e.g., in payment schemes, one knows that all messages to be authenticated are very short, and some signature schemes have more efficient versions for this case. This is why signature schemes for arbitrary message spaces were allowed in Section 5.2.5. It is only assumed that the message space is... 

The main variations are in the number of risk bearers and how the risk bearers participate in initialization, and in the number of recipients and the consequences on testing signatures. Furthermore, the existing schemes vary in the message space, the cryptologic assumption that the correctness of broken relies on, and in efficiency. 

Each existing scheme is based on a construction for signing one message block. However, the block size usually depends on a security parameter hence these subprotocols are not signature schemes for a certain given message space in the sense of Chapter 5 (cf. Section 9.1). 

The situation with messages spaces, cryptologic assumptions, and efficiency is similar to that with fail-stop signature schemes. 

Schemes without further attributes allow all bit strings to be authenticated. There is not so much efficiency to be gained by restricting the message space as in old fail-stop signature schemes anyway. But again, all existing schemes are based on constructions for short message blocks.

The message space can be arbitrary (in [PfWa92, Waid91] only). 

The first step of the constructions will follow the basic construction idea explained above exactly (see Chapter 9). The second step has two parts There are extensions to predefined message spaces and extensions to large message bounds (see Chapter 10). 

If the desired message space M consists of short messages only, one has to define embeddings of M into the sequence of message-block spaces given by the first step of the construction. 

Before the components of standard fail-stop signature schemes (in a conventional definition) are summarized in Definition 7.1, the specification parameters from Section 5.2.5 must be considered. Several of them have already been fixed for all standard fail-stop signature schemes, e.g., the set Dispute jresults and everything to do with sets of identities of recipients, because no dependence on the recipient is prescribed. Others cannot be seen in a conventional definition, such as Sign results. Two parameters remain, the message space and the set of message bounds. 

Definition 7.1. The components of a standard fail-stop signature scheme with one risk bearer for a non-empty message space Af c 0,1 " and a non-empty set Message bounds c IN u > are a 5-tuple Gen, sign, test, prove, verify) where... 

Definition 7.12. Let a standard fail-stop signature scheme for a message space M and a set Messagejbounds be given. 

Construction 7.38. Let the components of a secure standard fail-stop signature scheme with one risk bearer be given. The components of a scheme with an arbitrary number of risk bearers (for the same message space and the same message bounds) are constructed as follows. They are written with an asterisk to distinguish them from the components of the underlying scheme. 

Definition 9.1. A standard fail-stop signature scheme with prekey for signing message blocks is defined like a standard fail-stop signature scheme with prekey, except that there is no fixed message space M. Instead, there is a family of message-block spaces... 

Remark 9.15 (Small message spaces). The message-block spaces =... 

Moreover, one can already construct one-time fail-stop signature schemes for real finite message spaces M One only needs a number N and a polynomialtime computable injection I of M into the set 0,. .., 2 0 - 1. The scheme is changed so that any k < ko is replaced by k. This does not alter the security. Then one can map M into with i for all acceptable prekeys. ... 

Remark 9.23 (Small message spaces). As with the discrete-logarithm scheme, the message-block spaces are very simple, so that random choice of a message block and membership tests can be carried out efficiently, if they are needed in an application. 

For similar message spaces, k in the discrete-logarithm scheme is set equal to p in the factoring schemes. Note, however, that p is arbitrary, whereas k is restricted by something like 160 < k < Ipl2. 

The following construction, although lengthy, is canonical, but it is the only formal test whether the definition of schemes for signing message blocks is suitable in relation to the definition of schemes for fixed message spaces. 

Theorem 10.2 (Message hashing). Construction 10.1 defines components of a standard fail-stop signature scheme with prekey for the message space 0, 1 . If... 

The corresponding standard fail-stop signature scheme with hottom-up tree authentication (also with prekey) for the same message space has the following components, which are written with an asterisk (see Figure 10.1) The set Message bounds is the set of powers of 2. 

Definition 11.19 (Rudimentary standard information-theoretically secure signature schemes). The components of a rudimentary standard information-theoretically secure signature scheme (in functional notation) for a nonempty message space Me 0, and a non-empty set Messagejbounds c N u oo are a triple Gen, sign, test) where... 

M is called the message space, and Ke U Kd is called the key space. In computerized algorithms, the key space and message space are typically sets of all bit strings of particular lengths. As a notational convention, we denote sets by boldface letters and elements of a set by the same letter in italic typeface. The functions KeyGen, Enc, and Dec are defined as follows. 

---