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

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 σ over a group of size p ≈ 2 2k consists of a tuple (s, e), where e ∈ 0, 1 2k is a hash output and s ∈ Zp 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 3k bits provide k 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 3k + log S + log N bits. Here, N denotes the number of users and S denotes the size of the hint generated by our preprocessing attacker, e.g., if S = 2 k/2 , then we would obtain secure 3.75k-bit signatures for groups of up to N ≤ 2 k/4 users.

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 1-out-of-N discrete-log problem in the generic group model, with and without preprocessing.