However, a 2002 theorem by Galbraith, Malone-Lee, and Smart states that, for the classic Schnorr signature system, single-key security tightly implies multi-key security. Struik and then Hamburg, citing this theorem, argued that key prefixing was unnecessary for multi-user security and should not be standardized.
This paper identifies an error in the 2002 proof, and an apparently insurmountable obstacle to the claimed theorem. The proof idea does, however, lead to a different theorem, stating that single-key security of the classic Schnorr signature system tightly implies multi-key security of the key-prefixed variant of the system. This produces exactly the opposite conclusion regarding standardization.
Category / Keywords: public-key cryptography / Schnorr signatures, multi-user security, proof errors Date: received 13 Oct 2015 Contact author: authorcontact-multischnorr at box cr yp to Available format(s): PDF | BibTeX Citation Version: 20151014:173152 (All versions of this report) Short URL: ia.cr/2015/996