Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Schnorr Signatures, Generic Group Model, Random Oracle Model, Multi-User Security, 1-out-of-N Discrete-Log