Message bound

Special message bounds, i.e., restrictions on the number of messages that can be authenticated. 

Message bound. To cover cases where only a fixed number of messages can be authenticated after an initialization, there must be an input parameter to select this number, say N. It is called the message bound. Its domain is a subset Message bounds of KJ °, where means that no upper bound exists. Recipients and courts input this number, too. ° To be prepared for complexity considerations, N is always input in unary representation. 

If the security parameters were included, they could collectively be called par, with a domain Pars, because they have no special meaning in a pure service specification. Anyway, it may be usefirl to include such a parameter par on whose value at least the minimal requirements do not depend, to provide for extensions of initialization necessitated by additional transactions. For the same reason as with the message bound N, all the users participating in initialization would have to input the same value par, and effectiveness of initialization would be guaranteed whenever they do this. This extension is omitted for brevity in the following. 

Reinitialization may be needed because the message bound from the first initialization has been reached. However, as in the second situation, the reinitialization has to be under a new identity, so that each transaction can be linked to the correct initialization. In particular, it has been required that received... 

Formal predicates. The first predicate models that the user with identity id tries to start initialization for the signer idg in the current round. It reflects that initializations for id cannot be attempted at signer access points other than idg. The parameters ids if and N are the set of possible recipients and the message bound that this user wants. 

The only exception is that authentication need not work if the message bound N has been reached. Expressing this condition in temporal. logic is probably not the most natural way, but it can be done with a flexible variable counter (i.e., counter may assume different values in different rounds — this is the opposite of a rigid variable), which is formally used to count executions of authentication. 

It was already explained in a footnote to Section 5.2.5 that it is useful to have signature schemes with restricted message bounds. In particular, pure one-time signature schemes, where only one message can be authenticated, are interesting building blocks for more general schemes. 

One could try to introduce a parameter for the maximum number of tests a recipient or court carries out with respect to a given initialization, similar to the message bound for the number of authentications. However, this would entail further changes to the requirements — at present, it is required that any recipient can have any received authenticated message disputed at any time. 

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). 

Message bound. The message bound N is also an input to each algorithm in key generation, and it is also represented in unary. 

However, one must take care with sets Message bounds that contain the element oo. For this, the convention... 

As a two-party protocol does not need identities internally, the only input parameters of A and B are the security parameters and the message bound. When the parameters k, a, and N are clear from the context, they are abbreviated as... 

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... 

Note that the functional notation does not treat the case i > N. The following formal security definitions implicitly take Property c) from Definition 7.1 for granted, i.e., they do not treat what a signer s entity might do in authentications after the message bound has been reached, because it does not do anything. 

The outputs of gertg are written (prek, aux). The first output, prefe, is called a prekey the second output, aux, is only needed to convince the signer s entity of the correctness of prek in the zero-knowledge proof. Note that the inputs to geng are only the two security parameters par = ( 1 , 1 ), and not the message bound N. 

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. 

SigScheme, a standard fail-stop signature scheme with prekey for signing message blocks from a family MFam, and with a set Message bounds. 

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. 

At the end, i.e., when the message bound has been reached, each Node / will be labeled with a one-time key pair sk tempi, mkj)-, all these pairs are based on prek. Initially, only the root is labeled with skjemp, mk). 

In the constructions in the previous two sections, the length of the secret key is linear in the message bound, i.e., the number of messages to be signed. It is shown in Chapter 11 that this cannot be avoided if one defines secret key in the functional way of Definition 7.3a, i.e., including all the secret random bits that the signer s entity ever uses. 

Hence, if this construction is applied to a binary complete tree, as assumed above, the amount of private storage needed is only logarithmic in the message bound, N. ... 

If i = N+l, there is one message more than the message bound, hence cannot be signed correctly in the strict sense. Therefore its correct signature is defined as if had not been signed. Thus let... 

---