Security of signature schemes in a multi-user setting (Q702188)

Some special attacks on cryptographic primitives used in the so-called multi-user setting motivate the authors to consider the security of signature schemes in this more general setting. They present a security definition for signature schemes in the multi-user setting that accounts for key substitution attacks. They prove (Theorem 6) that any signature scheme that is secure in the single-user setting to one that is secure under the new definitions. The authors consider various signature schemes -- the Schnorr signature scheme, DSA, ECDSA and the Rabin-Williams signature scheme -- and prove that all they are secure in the multiuser setting under some constraints on the parameters (Theorems 7,8,9,11).