Valid proof of forgery

If it receives an answer from the signer s entity, it uses an algorithm verify to verify that the answer is a valid proof of forgery. If yes, the output is acc = broken otherwise acc = TRUE. 

Security parameters. As some requirements on a fail-stop signature scheme have to be fulfilled information-theoretically and others only computationally, it is natural to consider two security parameters. They are called a and k, where a measures the information-theoretic security and k the computational security. The primary role of cr is that the error probability in the fail-back requirement of the signer on disputes decreases exponentially with a. In other words, a determines the probability that the signer is cheated with unprovable forgeries. The primary role of k is to ensure the correctness of broken , i.e., the larger k is, the harder it should be to compute valid proofs of forgeries (and thus forgeries in the first place). 

For disputes of Type b), it has to be shown that B does not lose anything by stopping afterwards. There are only two cases If the court s entity outputs TRUE, both B and B have succeeded, and there is no need to continue. If the court s entity outputs broken , the signer s entity must have computed a valid proof of forgery and will reuse it in all future disputes. Hence B can never succeed later, and B can just as well stop. 

Correctness of broken means that a correct entity of a court should not produce the output broken in a dispute or a transfer of a proof of forgery. With the structure assumed for standard fail-stop signature schemes, this output depends on an application of verify, hence the requirement means that no valid proofs of forgery should occur. This requirement is fulfilled computationally only, and if there are special risk bearers, one of their entities is assumed to be correct. 

In previous definitions, this requirement has been considered almost without active attacks, i.e., the attacker only takes part in one initialization (where he may try to cheat, of course) and then immediately tries to compute a valid proof of forgery. It is now shown that this is without loss of generality in standard fail-stop signature schemes. 

At the level of entities, this argument seems to need an honest court, which is not assumed here. However, the conventional definition of the correctness of broken , as sketched in the previous subsection and formalized in Definition 7.11, only says that it should be infeasible to compute a valid proof of forgery, as long as any risk bearer is honest. 

The statement of the definition is that the probability that the attacker finds a valid proof of forgery is negligibly small in the parameter k. 

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. 

Verifying proofs of forgery Valid proofs of forgery are k -collisions. More precisely, on input a pair (prek, proof), where prek = ( 1 , 1 , K) e All, which implies K e All, and where proof is a pair (s, s ),... 

A collision of the hash function cormts as a valid proof of forgery. 

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

Verifying proofs of forgery It is verified that the proof is either a collision of the hash function or a valid proof of forgery in the one-time scheme. 

To make the components polynomial-time in the interface inputs alone, each value mkj that is received in a signature is first tested with mk test, and it is verified that each value that should be an inner node of the tree, and thus a hash value, is of length len° k). Similarly, a collision in a valid proof of forgery must either consist of acceptable one-time main public keys or values of length len°(k). ... 

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. 

Verifying proofs of forgery As in Lemma 9.12, valid proofs of forgery are... 

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

Proof. Let i < W+1 be fixed. The success probability of A is at least as large as the probability that its intermediate result proofs is a valid proof of forgery, because no unsuccessful stop for a smaller value i is possible. The functional version of the corresponding part of is the following deterministic function A m/- On input (par, acc, idspi / gut, Pk, 10 with par = ( V, V, 1 ) ... 

---