Secure with prekey

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. 

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

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

In this section, an efficient standard fail-stop signature scheme with prekey for signing one message block is shown where the security for the risk bearer can be proved on the abstract discrete-logarithm assumption. Recall that this scheme (for subgroups of prime fields) is due to [HePe93]. 

The construction in this section is formalized so that it yields one-time standard fail-stop signature schemes with prekey that fiilfil the simplified security criteria for such schemes from Theorem 7.34, because the constructions in Sections 10.2 to... 

Theorem 10.10 (Bottom-up tree authentication). Construction 10.9 defines the components of a standard fail-stop signature scheme with prekey for signing an arbitrary number of messages. If the underlying signature scheme fulfils the simplified security criteria from Theorem 7.34, the new scheme fulfils them, too, and is therefore secure. 

The parameters have their usual meaning from the previous sections. In particular, N is the message bound, / in the information-theoretically secure signature schemes is the number of testers (i.e., recipients or courts or both, depending on the class of schemes), and k, I, cr, tr, and cr = min(security parameters with krisk bearers. As all the constructions of fail-stop signature schemes are with prekey, and the same prekey can be used for several signers, only the main public key is shown. 

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

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. 

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

---