Discrete-Logarithm Scheme with Shorter Secret Key

It is a variant of the discrete-logarithm scheme where half of each one-time secret key is reused for the next signature. For simplicity, it is immediately presented with subgroups of prime fields, i.e., in a form similar to Lemma 9.12. Moreover, the length of the public key is not minimized for the moment, and the scheme is presented for message blocks see Remark 10.25. 

This is a slightly simplified comparison, because k is not directly comparable between schemes relying on different cryptologic assumption. However, the two schemes just mentioned do rely on the same assumption, and it was shown in Section 9.5 that with choices of security parameters that seem reasonable at present, the secret keys in the constructions based on the factoring assumption are longer. 

It will also be written sign (sk,j, mp, because it does not depend on the rest of the sequence. In the algorithmic version, the second component of sk temp is incremented, and if it is already N when sign is called, the output is key used up . 

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 )  

It suffices to show this for the worst case, where the signer has already signed N messages, i.e., the length of rn is N, and the history therefore contains maximum information about sk (see the proof of Lemma 9.7b). 

---

Discrete-Logarithm Scheme with Shorter Secret Key... 

---