Security for the risk bearer

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. 

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

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

For SigScheme, an algorithm A is defined that uses A and simulates the actions of the risk bearer s entity with respect to the family of hash functions on its own. Thus, on input ( 1 , V, prek), it computes k° = make small(k) K° <— gen°CV ) prek = prek, K°) proof A CV , "V, prek ). If proof contains a component procf, A outputs that. In Case 1, this immediately yields a contradiction to the security for the risk bearer in SigScheme. 

The security for the risk bearer follows fiom the fact that valid proofs of forgery of the underlying one-time signature scheme and collisions of the hash fimctions are assumed to be infeasible to constmct. (Formally, the two infeasibility conditions are combined as in the proof of Theorem 10.2, but without parameter transformations.) Note that the fact that many one-time key pairs are based on the same prekey prek makes no formal difference at all in Criterion 2 of Theorem 7.34. 

Proof, a) The only really interesting part of the proof is that the additional information stored non-secretly does not weaken the security for the signer — the requirements from Definitions 7.1 and 7.31 are easy to see, and effectiveness of authentication and the security for the risk bearer are unchanged in comparison with Theorem 10.14. (Recall from Theorem 10.2 that the security of the underlying scheme according to Definition 9.1 implies that in combination with message hashing, it fulfils the criteria of Theorem 7.34, and hence Theorem 10.14 can be applied.)... 

Proof. The implicit and explicit requirements fi-om Definitions 7.1 and 7.31 are obviously fulfilled, and effectiveness of authentication and the security for the risk bearer are shown as in Lemma 9.12. Furthermore, it is clear that every successful forgery /that is not the correct signature in the same position y in the sequence is provable. It remains to be shown that the reuse of halves of the one-time secret keys does not increase the likelihood with which such a forgery is the correct signature. Thus, with all the quantifiers as in Criterion 3 of Theorem 7.34 in the version of Definition 9.1, it has to be shown that for/= (m , s ) with s = (j, x , y ) ... 

The main variation is in the dependence on the recipients. Their role is similar to that of the risk bearers in fail-stop signature schemes To guarantee computational security for each recipient, even if many other participants are attacking, the entities of all recipients must take part in initialization. Hence initialization is much simpler if it is for a fixed recipient. 

Definition 7.14. A standard fail-stop signature scheme is secure for the signer forwards iff for all probabilistic interactive functions B and F (representing a cheating risk bearer colluding with a forger) and all parameters par as in Definition 7.1 or 7.2, respectively,... 

The definition of unforgeability and the proof that it follows from the security for the signer and the risk bearers (with a stronger version if the backward definition of the security for the signer is used). 

Note that these forgers are special cases of those considered with the security for the signer. In the case with several risk bearers, let B denote the combination of B and O. Hence the definition of unforgeability deals with the same probabilities PB,F,par the forward definition of the security for the signer. 

As unforgeability will be a consequence of the security for both the signer and the risk bearers, both security parameters, k and CT, may have to tend to infinity. The definition of the precise relation between them corresponds to the following theorem it can be generalized. 

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. 

The security for the users of the multi-party function evaluation protocol, except for the one who is protected information-theoretically, relies on the so-called quadratic-residuosity assumption. Hence the security for risk bearers in a fail-stop signature scheme based on this protocol also relies on this assumption. 

However, the real purpose of lower bounds is to say whenever one has certain requirements on the security, one has to pay the following price in terms of efficiency . In this section, this is more precisely If the error probability in the security for the signer is at most 7r, and the risk bearers want some security, too. 

Fail-stop security without further attributes means that the correctness of broken is required in the interest of each court individually. However, schemes with fewer special risk bearers (see Section 5.2.9) are important, because they can be much more efficient. For an overview, see Figure 6.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. 

Security for risk bearers means that the requirement correcmess of broken is fiilfilled in the computational sense. According to Section 7.1.3, it is sufficient to consider an attacker who takes part in key generation and then immediately tries to compute a vahd proof of forgery. These two parts of the attacker strategy are called Aj andA2-... 

Definition 7.11. A standard fail-stop signature scheme is secure for risk bearers iff for all probabilistic polynomial-time interactive algorithms Aj and non-interactive A2 (the two parts of the attacker strategy) and all polynomials Qsig, Qn (determining the growth of a and N as functions of k) ... 

Proof. Let F, and in the case of several risk bearers O, be given, and let B and par be defined accordingly. As F and O are probabilistic polynomial-time, a signer who tries to break the security for risk bearers can use these algorithms as subroutines in the following way ... 

The first summand was defined as the probability from the security for risk bearers (Definition 7.11). Using this definition immediately yields the desired result. 

Full standard fail-stop signature schemes themselves provide ordinary security if the output broken in disputes is replaced with TRUE. The same holds for schemes with special risk bearers if the signer plays the role of a risk bearer, too. 

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. 

The obvious advantage of this construction is that the complexity of authentication and disputes is independent of the number of risk bearers. The disadvantage is that a general suitable key-generation protocol is very inefficient however, see the last subsection for more efficient special cases. (Moreover, due to problems with definitions of multi-party function evaluation protocols, I did not even dare to call the security considerations below a proof sketch.)... 

---