Provable forgery

B. Now it is shown formally that PbwkerSP ) is at least equal to the probability that an attacker using F produces a provable forgery. First, the case with one risk bearer... 

Multiple speciHcations, i.e., different specifications intended for different degrees of security, which would be redundant otherwise. For instance, with fail-stop signature schemes one first requires that no forgeries occur, but secondly, if a forgery occurs nevertheless, it should be provable. This makes sense because the second requirement is to hold on weaker assumptions than the first... 

First, a particular instance of the information an attacker has is defined as good (from our point of view, or that of the honest signer) if it leaves so much uncertainty about sk that any successful forgery is provable with high a-posteriori probability. 

Thus an outcome is called good if it guarantees that no matter what messages will be signed, the information known to the attacker will be good, and thus any successful forgery will be provable with high hkelihood. 

If m is a hash"collision with any of the messages in m, the forgery is provable with probability 1. (Note that the value skjtemp actually used in... 

Whenever / is provable in the underlying scheme, then so is f in the new scheme, i.e., if proof = prove (sk, m, s , hist) is a valid proof of forgery with respect to pk, then proof = prove sk, m, s , hist ) equals normal proof, proof) and is valid with respect to pk. Hence it suffices to prove... 

Remark 10.6 (Two variants of broken ). If a collision of the hash function occurs as a proof of forgery, it is sufficient to choose a new hash function, whereas one can retain the prekey prek from the underlying scheme and the values sk and mk. As the keys of the hash functions were assumed to be locally verifiable, only the risk bearer(s) have to publish a new key of a hash function after such a proof of forgery, whereas the signers need not send any new information. This may be helpful if one decides to use fast, but not provably collision-intractable hash functions. 

As before, one shows that in the given forgery/, the algorithm prove finds a successful one-time forgery/ = (ml, sD g Forg(TRUE, pki, histi), and one can see from the construction of prove and verify that provable(ski, pki, histi, fi) implies provable (sk, pk, hist, f ) — the only addition to Theorem 10.14 is here that one has to show that skjtempi is reconstructed correctly in prove. Hence it remains to be shown that... 

Lemma 9.6b guarantees that this one-time forgery is provable unless j/ is the correct one-time signature on m/ at Node 1. Intuitively, it remains to be shown that the additional information in auth does not make it easier for an attacker to guess this correct signature. Formally, it suffices to show that... 

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

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

---