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: ia.cr/2015/1122
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]