Prekey

A slightly more complex case occurs if the prekey must fulfil certain conditions for the signer to be secure, e.g., that it is a number with exactly 2 prime factors. If... 

In particular, a constraction exists that transforms any fail-stop signature scheme for a fixed risk bearer with 2-message initialization into one for many risk bearers where initialization only needs two rounds In the first round, the entity of each risk bearer broadcasts a separate prekey in the second round, the signer s entity broadcasts a public key. More generally, one can use parallel replications of the initialization of any fail-stop signature scheme for a fixed risk bearer, see Section 7.5.1. This soimds quite efficient however, it has so far implied that the complexity of the other transactions grows linearly with the number of risk bearers. In contrast, versions with more complex initialization exist where the complexity of the other transactions is not larger than in the case with one risk bearer, see Section 7.5.2. 

The actual definition of so-called standard fail-stop signature schemes is contained in Section 7.1. In Section 7.2, relations to alternative or additional security properties are shown. Section 7.3 presents fail-stop signature schemes with prekey, an important subclass, and proves simplified security criteria for them. Section 7.4 shows the relation between standard fail-stop signature schemes and ordinary digital signature schemes. Section 7.5 contains constructions of schemes with many risk bearers from schemes with one risk bearer. 

This is easier to see in schemes with prekey (see Definition 7.31) There, B might generate a prekey that is not good, and with an exponentially small probability, the prekey passes the zero-knowledge proof nevertheless. In this veiy unlikely case, nothing is guaranteed. 

Fail-Stop Signature Schemes with Prekey... 

First, the risk bearer s entity generates and publishes a value prek, called a prekey. 

For example, the prekey may be a number n=p q, and the risk bearer s entity may have to convince the signer s entity that n really has exactly two prime factors, but without showing it these factors, before the signer s entity generates the secret key and the main public key as certain numbers modulo n. 

Additiondly, as zero-knowledge proof schemes have error probabilities, but some properties of standard fail-stop signature schemes were required without an error probability, one sometimes has to consider all prekeys that a signer s entity may possibly accept. They are represented by a set All. 

The definition assumes that one party has to generate a value K (usually some sort of key — in the present application the prekey) with a certain probability distribution Corr (for correct ) and needs a generation algorithm gen for this task, and another party wants to be convinced that K is an element of a set Good. The first party is called the prover, the second party the verifier. More precisely, both the distribution and the set are parametrized with security parameters, and there is a precondition that all values generated with the correct distribution are elements of Good. 

CorrFam = (Corr t,o-)Lo6N a family of probability distributions, called the correct prekey distributions. 

AllFam = (Allj f j fj is a family of sets, called the family of all acceptable prekeys, and all jest decides membership in this family in time polynomial in the security parameters alone. Hence all jest is an algorithm... 

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. 

Furthermore, it suffices to define test for the same values pk e PK All as verify. Similarly, a value skjemp can only be an original temporary secret key (as in the requirement on SKJTemp in Definition 7.1) if there exist parameters par = ( 1 , 1 ) as above, a prekey prek e Allj g, and a value mk such that... 

As the zero-knowledge proof scheme in a standard fail-stop signature scheme with prekey is required to be secure in itself, and alljtest decides membership in All correctly, it is natural to reduce the security of such a scheme to criteria that only deal with the remaining components.. This is done in the following theorem. The criteria are considerably simpler than the original definitions, because interaction in key generation no longer has to be considered. The constructions in Chapters 9 and 10 only have to be proved with respect to these criteria. 

Theorem 7.34 (Simplified security criteria). If a standard fail-stop signature scheme with prekey fulfils the following three criteria, then... 

Effectiveness of authentication. For all acceptable prekeys and all key pairs based on it, all correct signatures are acceptable. ... 

Security for the risk bearer. If the risk bearer s entity generates the prekey correctly, it is infeasible to find a valid proof of forgery for it. 

Security for the signer. If a prekey is good and the signer s entity bases its main key generation on it, the resulting keys are good in a sense very similar to Definition 7.17. More precisely ... 

If this criterion were only made for good prekeys, the scheme would still be secure, but effectiveness of authentication would only be error-free if the risk bearer s entity acted correctly. 

For the risk bearer By the definition of res, an output idspj i g f 1 can only occur if res does not receive an acceptable prekey or if acc observed = FALSE. The former cannot happen to an honest risk bearer, because all correctly... 

Figure 7.3. Security for the risk bearer when giving a zero-knowledge proof concerning the prekey.

---