Paper 2019/1105

On the Multi-User Security of Short Schnorr Signatures

Jeremiah Blocki and Seunghoon Lee

Abstract

The Schnorr signature scheme is an efficient digital signature scheme with short signature lengths, i.e., $4k$-bit signatures for $k$-bits of security. A Schnorr signature $\sigma$ over a group of size $q\approx 2^{2k}$ consists of a tuple $(s,e) $ where $e\in \mathbb{Z}_q$ is a hash output and $s$ must be computed using the secret key. Schnorr proposed the possibility of shorter Schnorr signatures with the same security level by truncating the hash output to $k$-bits, i.e., $e < 2^k$. A previous result showed that short Schnorr signatures provide $k$-bits of single-user security in the programmable random oracle model plus (a non-standard version of) the generic group model. Another prior result demonstrated that standard Schnorr signatures provide $k$-bits of multi-user security in the programmable random oracle model plus (another non-standard version of) the generic group model. As we discuss in the paper these non-standard versions of the generic group model do not capture all generic attacks, e.g., the generic preprocessing attacks of Corrigan-Gibbs and Kogan. In this paper, we prove that short Schnorr signatures provide $k$-bits of (multi-user) security under the (standard) generic group model and the programmable random oracle model.