Paper 2015/1122

Schnorr Signatures in the Multi-User Setting

Eike Kiltz, 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.

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