Correct signature

Now, a theorem in Riemannian geometry tells us that locally any metric (7) with the correct signature can be rewritten as (6) by an appropriate change of coordinates. At different points we use different transformations of coordinates, but always end up with the Lorentz metric in the new coordinates. So the equation (8), when written in terms of the coordinates for which the metric looks like (7), must describe the trajectory in the gravitational field. This is the geodesic equation (sum over / , 7)... 

One really needs a proof of knowledge, and not a better-known proof of language membership, because what the correct signature is cannot be defined relative to the public key and the message It depends on which of the possible secret keys a signer (or her entity) knows. 

Any value s that passes this test is called an acceptable signature on m (see Figure 6.6). This notion can be used more generally than that of a correct signature, because it only depends on the public value pk. 

To see why this is necessary, consider the basic construction idea from Section 6.1.2, and in particular. Figures 6.7 and 6.8 A proof of forgery shows the attacker the correct signature on a message. He could use it in a future dispute. The signer would lose that dispute if her entity had not stored the forged signature from the first dispute. Formally, this condition is used in the proof sketch of Lemma 7.5. 

One cannot speak of a correct signature here in the algorithmic definition, because no connection to an original skjemp is given. 

It does not matter that this set contains correct signatures, too, because it is only used to characterize the values an attacker can choose from when starting a dispute where he wants to have any chance of cheating the signer. 

Effectiveness of authentication. For all acceptable prekeys and all key pairs based on it, all correct signatures are acceptable. ... 

Thus all the security properties except for the secmity for the signer have now been proved. For the latter, one has to compute the probability with which a computationally unrestricted attacker can guess exactly the correct signature, because this was just shown to be the only way of making an improvable forgery. 

Then the a-posteriori probability that s is the correct signature on m , given all the information an attacker has, is at most... 

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

If the result is key used up instead, that is the output. Otherwise, the correct signature in the new scheme is simply... 

For instance, the complete correct signature j on m3 consists of the encircled nodes. To test it, the recipient s entity reconstructs the nodes in squares. 

A complete signature in the new scheme is one branch of this tree. More precisely, the correct signature on itij is... 

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

If i = N+l, there is one message more than the message bound, hence cannot be signed correctly in the strict sense. Therefore its correct signature is defined as if had not been signed. Thus let... 

Remark 11.3. As each correct signature is a deterministic function of the part of the secret key (in the functional version) that is actually used and the message sequence. Rule (5) implies fory = 1,. .., i,... 

Even a computationally mnestricted attacker must not be able to guess the correct signature on a given message with significant probability of success. 

Thus, on average, even a computationally unrestricted attacker must not be able to guess those correct signatures, because the signer s entity cannot disavow them by applying prove. 

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

The proof of Theorem 11.8 uses two lemmas. The first one formalizes Statement 1 from the overview, i.e., that correct signatures cannot be guessed with significant probability of success. 

---