Public key signatures in the multi-user settingS. D. Galbraith, J. Malone-Lee, N. P. Smart, Public key signatures in the multi-user setting. Information Processing Letters, 83 (5). ISSN xx, pp. 263–266. June 2002. No electronic version available.
This paper addresses the security of public key signature schemes in a "multi-user" setting. We bound the advantage of an adversary in producing an existential forgery on any one of a set of target public keys by the advantage of an adversary in producing an existential forgery on a single public key for any public key signature algorithm. We then improve the concrete security of this general reduction for certain specific discrete logarithm based signature algorithms such as that of Schnorr.