Security for risk bearers

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. 

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. 

That the security for risk bearers is needed is a problem, because Definition 7.11, like all computational cryptologic definitions, is asymptotic, i.e., security is only guaranteed for k sufficiently large. Thus, in a certain sense, one can only derive lower bounds for k > kQ, for an unknown kg. This seems unsatisfactory Nobody would have doubted that one needs arbitrarily long keys if one makes k sufficiently large, because in the definitions, k primarily determines the size of the problem instances and only secondarily the security. 

To quantify the security for risk bearers, it suffices for the present purpose to consider the case from Statement 1.1 above, i.e., the probability that the signer can compute a valid proof of forgery simply by applying the algorithm prove to her own correct signatures. In practice, one will require this probability to be at most, say, 2 °, or, more generally, 2 ° for some cr. The following lower bounds are proved as functions of this parameter a (in addition to o). 

To formalize the proof sketched above, first the quantification of the security for risk bearers is defined formally. 

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. 

G N exists such that all provide the security level risk bearers against for the given a. (The polynomials Qsig and Qn can be the constants O and N, respectively.) Hence Definition 11.5 does not make any new assumptions. ... 

As a first step towards lower bounds, it is stated what a certain security level for risk bearers means in the terminology with random variables. 

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

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. 

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. 

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. 

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. 

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

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

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

---