Message block space

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. 

All the following constructions yield schemes with prekey, and the message blocks that can be signed only depend on the prekey prek, i.e., one can use message-block spaces Hence only this case is defined. First, the definitions... 

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.2. One could adapt the original security definitions (Definition 7.15) in a similar way to message-block spaces Mpj and prove an analogue of Theorem 7.34, i.e., that the simplified security criteria imply the original ones. ... 

A fannily MFam of message-block spaces consisting of integers, parametrized by... 

Message-block spaces For each prek = ( 1 , 1 , AO e All, the message-block space is simply Mig a,K fro i f e underlying family MFam. 

Theorem 9.9. Construction 9.4 yields a secure standard fail-stop signature scheme with prekey for signing one message block if the following condition holds for the parameters BundFam, MFam, and tau (i.e., the family of bundling homo-morphisms, the message-block spaces, and the function that determines the bun-... 

Message-block spaces For a prekey prek = (q,p, g, g ), the message-block... 

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

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. 

The most important complexity parameters for the discrete-logarithm scheme and the factoring schemes are summarized in Table 9.1. To enable a comparison of the schemes, the complexity parameters are presented as functions of input parameters that yield similar message-block spaces and security. This means ... 

The parameters must be chosen so that each hash value is an element of the message-block space of the underlying signature scheme. In general, this makes parameter transformations similar to Construction 8.50 necessary. 

Components for embedding hash values into message-block spaces ... 

A family of embeddings of the codomains of the hash functions into message-block spaces of the signature scheme, i.e., a family of injective functions... 

On input (sk temp, m ), the message is hashed and mapped into the message-block space as... 

Test The input to test is a triple (pk, m, s) with pk = (prek, mk) PK All. Hence prek is of the form ( V, prek, K°), and one easily sees that pk = (prek, mk) g PK(prek), i.e., pk can be used to test message blocks from Mpfek- The message is hashed and mapped into the message-block space as m = lk,prek( ° prek (which is possible for the same reasons as in sign ), and the result is... 

If one combines the standard fail-stop signature schemes for signing one message block from Definition 9.17 with message hashing, there are no particular problems, because the function rho can be used to adapt the message-block spaces. 

As 0 was excluded from the message-block space, one can divide by my. i and repeat this step for the messages my. 2,. .., niff. The rank of the resulting matrix is clearly 2N + 2. 

---