Security for the signer

Of course, a many-one relation between secret and public information is not sufficient for security but once one has a formal definition, one can formally prove that it is necessary. However, this is not completely trivial The security for the signer need not be violated in every single case where the secret information in her entity can be guessed. A formal treatment for a standard case of fail-stop signature schemes can be seen in Section 11.3. 

Thus the conventional definition of the security for the signer, Definitions 7.12 to 7.14, will only consider the restricted active attacks. 

Security for the signer will be defined in two ways. The reason is that previous definitions avoided the concept of probabilistic interactive functions in favour of better-known notions. (This could originally be done because only simple versions of key generation were considered.) Now it is simpler to make a forward definition that deals explicitly with an interactive attacker strategy that carries out authentications and one dispute. This section contains such a forward definition. The backward definition from previous publications and a proof that it is slightly (and unnecessarily) stronger than the forward definition are presented in Section 7.2.1. Nevertheless, some of the later sections are based on the backward definition. 

The security for the signer against attacker strategies as described above means that the probability that the attacker succeeds in computing a successful forgery that the signer cannot prove to be a forgery is very small. This criterion can be formulated quite simply with the notation introduced in the previous definition. 

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

Theorem 7.19 (Security backwards and forwards). In standard fail-stop signature schemes, security for the signer backwards implies security for the signer forwards. ... 

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. 

The proof of Part a) of the theorem can be finished quite easily. First the security for the signer from Definition 7.14 is used ... 

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

Proof sketch of Theorem 7.34. For Part a) of the theorem, the four parts of the security definition (Definition 7.15) are treated in Parts A to D of the following proof. However, effectiveness of authentication in Part B of the proof is immediately proved in the error-free sense, which also yields Part b) of the theorem. Similarly, in Part D of the proof, security for the signer backwards (Definition 7.17e) is proved immediately this implies security for the signer forwards according to Theorem 7.19 and is required in Part c) of the theorem. The requirement from Definition 7.17f is proved in Part E. 

Moreover, only the security for the signer relies on the correct execution of the main key-generation algorithm genj. Hence genj can be executed by the signer s entity alone. All other entities can test mk locally. 

The following lemmas prove the properties that all implementations of the general construction framework have. It turns out that the only desired property that caimot be proved once and for all is a certain aspect of the security for the signer. 

Now it is summarized what has to be done to make an implementation of the general construction framework secure for the signer. It has just been shown that the a-posteriori probability of a forgery being unprovable is bounded by 2 It... 

Proof. It has to be shown that Definition 9.1, with the abbreviations from Definition 9.3, is fulfilled. Lemmas 9.5 and 9.6 cover all the requirements except for the security for the signer, i.e.. Criterion 3 of Theorem 7.34. If values pk = (prek, mk) with prek = ( 1 , "V, K) and hist = (jn, s) are given, where hist is a possible history. Lemma 9.7 can be applied. Together with Lemma 9.6, it immediately yields... 

Obviously, the only property of the scheme that could be affected by this restriction of the secret key space is the security for the signer. (Effectiveness of authentication holds for each key individually.) Furthermore, Lemma 9.6b is unchanged hence only the likelihood of guessing the correct signature has to lie reconsidered. The functions % on the restricted domains are the functions which are still of bundling degree 2 by Lemma 8.17b. Hence Lemma 9.7 can be proved for them, too. Thus an upper bound on the sizes of the sets = [d e I h id) = 1 a... 

Remark 10.11 (Security for the signer forwards). Currently, security for the signer backwards has been assumed in the one-time scheme and proved in the new scheme. If one wanted to obtain a similar theorem for security forwards, one would have to increase the parameter a in Construction 10.9 by adding log2(iV). because the attacker has more chances to come into a situation where he can make an improvable successful forgery. The same holds for the following constructions. ... 

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

Actually, not arbitrary signature schemes with fail-stop security according to Chapter 5 are considered at present, but only standard fail-stop signature schemes as defined in Chapter 7, and security for the signer backwards and error-free effectiveness of authentication, at least in the case where all parties carry out key generation correctly, are assumed. ... 

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. 

For the first summand. Lemma 11.7 was used. The second summand means that the best guess of an attacker is not provable to be a forgery. As it was shown to be a successful forgery in Part a), the security for the signer can be applied. Definition 7.17f yields for all pairs (pk, histi ) of possible values of PK and Histi i, and with simplifications due to the fact that B is the correct B,... 

Remark 11.13. Similar to Remark 11.6, unforgeability in k alone, which holds on the assumptions of Theorem 11.15 (by Theorem 7.24b), implies that for all o, cr G IN, a value k exists such that all fc > /tq provide the security level a against forgery by F for the given a. (Even if one only assumes security for the signer forwards and thus Theorem 7.24a, this still holds for cr < a.) ... 

More precisely (similar to the definition of security for the signer backwards. Definition 7.17) ... 

---