Cryptology ePrint Archive: Report 2015/1122

Schnorr Signatures in the Multi-User Setting

Eike Kiltz and Daniel Masny and Jiaxin Pan

Abstract: A theorem by Galbraith, Malone-Lee, and Smart (GMLS) from 2002 showed that, for Schnorr signatures, single-user security tightly implies multi-user security. Recently, Bernstein pointed to an error in the above theorem and promoted a key-prefixing variant of Schnorr signatures for which he proved a tight implication from single to multi-user security. Even worse, he identified an “apparently insurmountable obstacle to the claimed [GMLS] theorem”. This paper shows that, without key prefixing, single-user security of Schnorr signatures tightly implies multi-user security of the same scheme.

Category / Keywords: public-key cryptography / Schnorr signatures, multi-user security, unforgeability, tight reduction

Date: received 19 Nov 2015, withdrawn 21 Mar 2016

Contact author: Daniel Masny at rub de

Available format(s): (-- withdrawn --)

Note: Report 2016/191 subsumes and extends this work.

Version: 20160321:205222 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]