Paper 2019/1105

On the Multi-User Security of Short Schnorr Signatures with Preprocessing

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 $p\approx 2^{2k}$ consists of a tuple $(s,e)$, where $e\in \{0,1{\}}^{2k}$ is a hash output and $s\in {\mathbb{Z}}_p$ must be computed using the secret key. While the hash output $e$ requires $2k$ bits to encode, Schnorr proposed that it might be possible to truncate the hash value without adversely impacting security. In this paper, we prove that short Schnorr signatures of length $$ bits provide $$ bits of multi-user security in the (Shoup's) generic group model and the programmable random oracle model. We further analyze the multi-user security of key-prefixed short Schnorr signatures against preprocessing attacks, showing that it is possible to obtain secure signatures of length $$ bits. Here, $$ denotes the size of the hint generated by our preprocessing attacker, e.g., if $$, then we would obtain $$-bit signatures. Our techniques easily generalize to several other Fiat-Shamir-based signature schemes, allowing us to establish analogous results for Chaum-Pedersen signatures and Katz-Wang signatures. As a building block, we also analyze the $$-out-of-$$ discrete-log problem in the generic group model, with and without preprocessing.

Note: This is the full version of the paper with the same title which appeared at EUROCRYPT 2022. Note: Improved multi-user security bounds to eliminate unnecessary dependences on N (updated on 02/2023).