The Non-Generic Forking Lemma Sample Clauses

The Non-Generic Forking Lemma. In Chapters 4 and 5, we will need to apply a modified version of the Forking Lemma which we introduce now. Since we will need to apply the forking lemma to signature schemes that do not exactly match the format required, we present a modified version of the forking lemma for signature schemes which take as input an additional parameter, which we denote T . The value T simply acts as a placeholder value, and has no real affect on the proof of the forking lemma, but will be used in the security proofs of certain non-standard digital signature schemes in later chapters. This modified version of the Forking Lemma applies to digital signature schemes which on input a message M and a value T produce signatures of the form (r1, h, r2). Here r1 randomly distributed in a large set, h is the hash of M and r1, and r2 depends on r1, M and h. As before we require that no value r1 can appear with probability greater than 2/2l where l is the security parameter. We call such digital signature schemes non-generic digital signature schemes. The unforgeability model for non-generic (NG) signature schemes is identical to the unforgeability model for generic signature schemes (presented in Section 2.3.1) except that Sign queries take an additional value T as input. The analogous output conditions require a valid signature for some M and T and forbid an adversary from making previ- ous Sign queries on M, T . We call the resulting unforgeability model the NG signature unforgeability model. As in the more general definition of a generic signature scheme, the value r1 of an NG signature scheme does not need to be chosen randomly from a large set, but must be indistinguishable from a value chosen randomly from a large set. For instance, r1 may depend on some public parameters (or even M and T ) together with some value chosen randomly from a large set. We also explicitly allow the computation of r2 in a non-generic signature scheme to depend on values other than r1, M and h (e.g. r2 may also depend on public parameters or public keys). We also do not require r2 to be uniquely determined by r1, M and h.