Successful forgery

Forge is the event that F has produced a successful forgery, i.e., it is defined by the predicate/e Forg(acc, pk, hist). 

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. 

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. 

Before the fairly long proof, note that this lemma is easy to believe The first summand is the probability that the cheating risk bearer(s) can produce a bad key pair. The second summand deals with good keys. In this case, every successful forgery can be proved with probability at least 1 - 2 (by Definition 7.17b) hence one should expect the probability of unprovable successful forgeries to be at most 2 times the probability that any successful forgery is produced. The formal proof has to deal with the fact that all these probabilities are in different probability spaces. 

Let any successful forgery/e Forg acc,pk, hist) be given, and remember acc = TRUE. Hence... 

Recall that the computation of the Jacobi symbol is necessary to exclude trivial claws such as (2x) = 4(x). The computation of a Jacobi symbol in test is necessary to guarantee that if the signature is a successful forgery, it will pass this verification. 

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

For this, let a successful forgery/ Forg (TRUE,pA , hist ) in the new scheme be given, where pk = prek, mk). It has to be shown that (recall that the probability is over sk ) ... 

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

---