Enhancing the security of perfect blind DL-signatures

We enhance the security of Schnorr blind signatures against the novel one-more-forgery of C.P. Schnorr [Security of blind discrete log signatures against interactive attacks, in: ICICS 2001, LNCS, vol. 2229, 2001, Springer-Verlag, Berlin, pp. 1–12] and D. Wagner [A generalized birthday problem, in: Proceedings Crypto’02, LNCS, vol. 2442, Springer-Verlag, Berlin, 2002, pp. 288–303] which is possible even if the discrete logarithm is hard to compute. We show two limitations of this attack. Firstly, replacing the group G by the s-fold direct product G×s increases the work of the attack, for a given number of signer interactions, to the s-power while increasing the work of the blind signature protocol merely by a factor s. Secondly, we bound the number of additional signatures per signer interaction that can be efficiently forged by known methods. That fraction of the additional forged signatures can be made arbitrarily small. Our security proofs assume both the random oracle and the generic group model.